On Wed, May 3, 2017 at 2:43 PM, Richard Biener
<richard.guent...@gmail.com> wrote:
> On Tue, Apr 18, 2017 at 12:46 PM, Bin Cheng <bin.ch...@arm.com> wrote:
>> Hi,
>> We generally need to compute cand step in loop preheader and use it in loop
>> body.
>> Unless it's an SSA_NAME of constant integer, an invariant expression is
>> needed.
>
> I'm confused as to what this patch does. Comments talk about "Handle step as"
> but then we print "Depend on inv...". And we share bitmaps, well it seems
>
> + find_inv_vars (data, &step, &cand->inv_vars);
> +
> + iv_inv_expr_ent *inv_expr = get_loop_invariant_expr (data, step);
> + /* Share bitmap between inv_vars and inv_exprs for cand. */
> + if (inv_expr != NULL)
> + {
> + cand->inv_exprs = cand->inv_vars;
> + cand->inv_vars = NULL;
> + if (cand->inv_exprs)
> + bitmap_clear (cand->inv_exprs);
> + else
> + cand->inv_exprs = BITMAP_ALLOC (NULL);
> +
> + bitmap_set_bit (cand->inv_exprs, inv_expr->id);
>
> just shares the bitmap allocation (and leaks cand->inv_exprs?).
>
> Note that generally it might be cheaper to use bitmap_head instead of
> bitmap in the various structures (and then bitmap_initialize ()), this
> saves one indirection.
>
> Anyway, the relation between inv_vars and inv_exprs is what confuses me.
> Maybe it's the same as for cost_pair? invariants vs. loop invariants?
> whatever that means...
>
> That is, can you expand the comments in cost_pair / iv_cand for inv_vars
> vs. inv_exprs, esp what "invariant" actually means?
When we represent use with cand, there will be computation which is
loop invariant. The invariant computation is an newly created
invariant expression and is based on ssa_vars existed before ivopts.
If the invariant expression is complicated, we handle and call it as
invariant expression. We say the cost_pair depends on the inv.exprs.
If the invariant expression is simple enough, we record all existing
ssa_vars it based on in inv_vars. We say the cost_pair depends on the
inv.vars. The same words stand for struct iv_cand. If cand.step is
simple enough, we simply record the ssa_var it based on in inv_vars,
otherwise, the step is a new invariant expression which doesn't exist
before, we record it in cand.inv_exprs.
Add comment for inv_vars/inv_exprs, is this OK? I noticed there is a
redundant field cost_pair.inv_expr, I deleted it as obvious in a
standalone patch.
Thanks,
bin
>
> Thanks,
> Richard.
>
>> Thanks,
>> bin
>>
>> 2017-04-11 Bin Cheng <bin.ch...@arm.com>
>>
>> * tree-ssa-loop-ivopts.c (struct iv_cand): New field inv_exprs.
>> (dump_cand): Support iv_cand.inv_exprs.
>> (add_candidate_1): Record invariant exprs in iv_cand.inv_exprs
>> for candidates.
>> (iv_ca_set_no_cp, iv_ca_set_cp, free_loop_data): Support
>> iv_cand.inv_exprs.
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index 8a01e0a..93d7966 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -347,9 +347,10 @@ struct cost_pair
struct iv_cand *cand; /* The candidate. */
comp_cost cost; /* The cost. */
enum tree_code comp; /* For iv elimination, the comparison. */
- bitmap inv_vars; /* The list of invariants that have to be
- preserved. */
- bitmap inv_exprs; /* Loop invariant expressions. */
+ bitmap inv_vars; /* The list of invariant ssa_vars that have to be
+ preserved when representing iv_use with iv_cand. */
+ bitmap inv_exprs; /* The list of newly created invariant expressions
+ when representing iv_use with iv_cand. */
tree value; /* For final value elimination, the expression for
the final value of the iv. For iv elimination,
the new bound to compare with. */
@@ -419,8 +420,11 @@ struct iv_cand
unsigned cost_step; /* Cost of the candidate's increment operation. */
struct iv_use *ainc_use; /* For IP_{BEFORE,AFTER}_USE candidates, the place
where it is incremented. */
- bitmap inv_vars; /* The list of invariants that are used in step of the
- biv. */
+ bitmap inv_vars; /* The list of invariant ssa_vars used in step of the
+ iv_cand. */
+ bitmap inv_exprs; /* If step is more complicated than a single ssa_var,
+ hanlde it as a new invariant expression which will
+ be hoisted out of loop. */
struct iv *orig_iv; /* The original iv if this cand is added from biv with
smaller type. */
};
@@ -790,6 +794,11 @@ dump_cand (FILE *file, struct iv_cand *cand)
fprintf (file, " Depend on inv.vars: ");
dump_bitmap (file, cand->inv_vars);
}
+ if (cand->inv_exprs)
+ {
+ fprintf (file, " Depend on inv.exprs: ");
+ dump_bitmap (file, cand->inv_exprs);
+ }
if (cand->var_before)
{
@@ -3026,7 +3035,23 @@ add_candidate_1 (struct ivopts_data *data,
data->vcands.safe_push (cand);
if (TREE_CODE (step) != INTEGER_CST)
- find_inv_vars (data, &step, &cand->inv_vars);
+ {
+ find_inv_vars (data, &step, &cand->inv_vars);
+
+ iv_inv_expr_ent *inv_expr = get_loop_invariant_expr (data, step);
+ /* Share bitmap between inv_vars and inv_exprs for cand. */
+ if (inv_expr != NULL)
+ {
+ cand->inv_exprs = cand->inv_vars;
+ cand->inv_vars = NULL;
+ if (cand->inv_exprs)
+ bitmap_clear (cand->inv_exprs);
+ else
+ cand->inv_exprs = BITMAP_ALLOC (NULL);
+
+ bitmap_set_bit (cand->inv_exprs, inv_expr->id);
+ }
+ }
if (pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
cand->ainc_use = use;
@@ -5604,6 +5629,7 @@ iv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca
*ivs,
ivs->n_cands--;
ivs->cand_cost -= cp->cand->cost;
iv_ca_set_remove_invs (ivs, cp->cand->inv_vars, ivs->n_inv_var_uses);
+ iv_ca_set_remove_invs (ivs, cp->cand->inv_exprs, ivs->n_inv_expr_uses);
}
ivs->cand_use_cost -= cp->cost;
@@ -5660,6 +5686,7 @@ iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
ivs->n_cands++;
ivs->cand_cost += cp->cand->cost;
iv_ca_set_add_invs (ivs, cp->cand->inv_vars, ivs->n_inv_var_uses);
+ iv_ca_set_add_invs (ivs, cp->cand->inv_exprs, ivs->n_inv_expr_uses);
}
ivs->cand_use_cost += cp->cost;
@@ -7141,6 +7168,8 @@ free_loop_data (struct ivopts_data *data)
if (cand->inv_vars)
BITMAP_FREE (cand->inv_vars);
+ if (cand->inv_exprs)
+ BITMAP_FREE (cand->inv_exprs);
free (cand);
}
data->vcands.truncate (0);
