Hi,
The algorithm choosing candidates in IVOPT has some defects that optimal iv
set can't be found in some cases. This patch slightly tunes the algorithm
to make it more accurate. The reasons are:
1) Changes in iv_ca_extend. Dependences could be changed in the loop,
causing check condition " !iv_ca_has_deps (ivs, new_cp) " in future
iterations inaccurate. This is a minor change and won't matter really much.
2) Changes in iv_ca_narrow. Start narrowing from the candidate just picked
by iv_ca_prune. Consider below example:
cand cost
0 4
1 5
2 5
use 0
cand cost dep
0 4
1 0
2 4
use 1
cand cost dep
0 4
1 5
2 4
The initial iv set is:
use cand
0 0
1 0
Which can be improved to:
use cand
0 1
1 1
But IVOPT can't find this iv set because after it extending to <use 0, cand
1; use 1, cand 0>, iv_ca_narrow won't consider "cand 1" for "use 1", because
it has higher cost than "cand 0". Consequently, IVOPT gives up and can't
find out that overall cost of "cand 1" is cheaper than "cand 0". I think
the situation is worse on targets support auto-increment addressing mode.
I also changed iv_ca_narrow by checking the overall cost, rather than single
cost_pair.
Bootstrap and test on x86/x86_64.
Arm on going, is it OK if tests pass?
Thanks,
bin
2013-11-14 Bin Cheng <bin.ch...@arm.com>
* tree-ssa-loop-ivopts.c (iv_ca_extend): Commit each candidate
and use pair instantly.
(iv_ca_narrow): New parameter. Start narrowing with START.
Apply candidate-use pair and check overall cost in narrowing.
(iv_ca_prune): Pass new argument.Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c (revision 204697)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -5653,12 +5653,12 @@ iv_ca_extend (struct ivopts_data *data, struct iv_
continue;
if (!min_ncand && !cheaper_cost_pair (new_cp, old_cp))
- continue;
+ continue;
+ iv_ca_set_cp (data, ivs, use, new_cp);
*delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
}
- iv_ca_delta_commit (data, ivs, *delta, true);
cost = iv_ca_cost (ivs);
if (n_ivs)
*n_ivs = iv_ca_n_cands (ivs);
@@ -5668,18 +5668,20 @@ iv_ca_extend (struct ivopts_data *data, struct iv_
}
/* Try narrowing set IVS by removing CAND. Return the cost of
- the new set and store the differences in DELTA. */
+ the new set and store the differences in DELTA. START is
+ the candidate with which we start narrowing. */
static comp_cost
iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
- struct iv_cand *cand, struct iv_ca_delta **delta)
+ struct iv_cand *cand, struct iv_cand *start,
+ struct iv_ca_delta **delta)
{
unsigned i, ci;
struct iv_use *use;
struct cost_pair *old_cp, *new_cp, *cp;
bitmap_iterator bi;
struct iv_cand *cnd;
- comp_cost cost;
+ comp_cost cost, best_cost, acost;
*delta = NULL;
for (i = 0; i < n_iv_uses (data); i++)
@@ -5690,7 +5692,9 @@ iv_ca_narrow (struct ivopts_data *data, struct iv_
if (old_cp->cand != cand)
continue;
- new_cp = NULL;
+ best_cost = iv_ca_cost (ivs);
+ /* Start narrowing with START. */
+ new_cp = get_use_iv_cost (data, use, start);
if (data->consider_all_candidates)
{
@@ -5705,13 +5709,15 @@ iv_ca_narrow (struct ivopts_data *data, struct iv_
if (!cp)
continue;
- if (!iv_ca_has_deps (ivs, cp))
- continue;
+ iv_ca_set_cp (data, ivs, use, cp);
+ acost = iv_ca_cost (ivs);
+ iv_ca_set_cp (data, ivs, use, old_cp);
- if (!cheaper_cost_pair (cp, new_cp))
- continue;
-
- new_cp = cp;
+ if (compare_costs (acost, best_cost) < 0)
+ {
+ best_cost = acost;
+ new_cp = cp;
+ }
}
}
else
@@ -5726,13 +5732,16 @@ iv_ca_narrow (struct ivopts_data *data, struct iv_
cp = get_use_iv_cost (data, use, cnd);
if (!cp)
continue;
- if (!iv_ca_has_deps (ivs, cp))
- continue;
- if (!cheaper_cost_pair (cp, new_cp))
- continue;
+ iv_ca_set_cp (data, ivs, use, cp);
+ acost = iv_ca_cost (ivs);
+ iv_ca_set_cp (data, ivs, use, old_cp);
- new_cp = cp;
+ if (compare_costs (acost, best_cost) < 0)
+ {
+ best_cost = acost;
+ new_cp = cp;
+ }
}
}
@@ -5776,7 +5785,7 @@ iv_ca_prune (struct ivopts_data *data, struct iv_c
if (cand == except_cand)
continue;
- acost = iv_ca_narrow (data, ivs, cand, &act_delta);
+ acost = iv_ca_narrow (data, ivs, cand, except_cand, &act_delta);
if (compare_costs (acost, best_cost) < 0)
{
