[PATCH GCC8][17/33]Treat complex cand step as invriant expression

[PATCH GCC8][17/33]Treat complex cand step as invriant expression

[Bin Cheng]

[-- Attachment #1: Type: text/plain, Size: 502 bytes --]

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.

Thanks,
bin

2017-04-11  Bin Cheng  <bin.cheng@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.

[-- Attachment #2: 0017-treat-cand_step-as-inv_expr-20170225.txt --]
[-- Type: text/plain, Size: 2883 bytes --]

From 06806d09f557854a5987b83a044a5eb5433cda60 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Wed, 1 Mar 2017 14:50:11 +0000
Subject: [PATCH 17/33] treat-cand_step-as-inv_expr-20170225.txt

---
 gcc/tree-ssa-loop-ivopts.c | 28 +++++++++++++++++++++++++++-
 1 file changed, 27 insertions(+), 1 deletion(-)

diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index c3e9bce..2c6fa76 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -421,6 +421,7 @@ struct iv_cand
 			      where it is incremented.  */
   bitmap inv_vars;	/* The list of invariants that are used in step of the
 			   biv.  */
+  bitmap inv_exprs;	/* Hanlde step as inv expr if it's not simple.  */
   struct iv *orig_iv;	/* The original iv if this cand is added from biv with
 			   smaller type.  */
 };
@@ -790,6 +791,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)
     {
@@ -3032,7 +3038,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;
@@ -5606,6 +5628,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;
@@ -5662,6 +5685,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;
@@ -7143,6 +7167,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);
-- 
1.9.1

Re: [PATCH GCC8][17/33]Treat complex cand step as invriant expression

[Richard Biener]

On Tue, Apr 18, 2017 at 12:46 PM, Bin Cheng <Bin.Cheng@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?

Thanks,
Richard.

> Thanks,
> bin
>
> 2017-04-11  Bin Cheng  <bin.cheng@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.

Re: [PATCH GCC8][17/33]Treat complex cand step as invriant expression

[Bin.Cheng]

[-- Attachment #1: Type: text/plain, Size: 2940 bytes --]

On Wed, May 3, 2017 at 2:43 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, Apr 18, 2017 at 12:46 PM, Bin Cheng <Bin.Cheng@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.cheng@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.

[-- Attachment #2: 0017-treat-cand_step-as-inv_expr-20170501.txt --]
[-- Type: text/plain, Size: 3615 bytes --]

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);

Re: [PATCH GCC8][17/33]Treat complex cand step as invriant expression

[Richard Biener via gcc-patches]

On Thu, May 4, 2017 at 7:55 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Wed, May 3, 2017 at 2:43 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Tue, Apr 18, 2017 at 12:46 PM, Bin Cheng <Bin.Cheng@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 for the explanation.

Ok.

Thanks,
Richard.

> Thanks,
> bin
>>
>> Thanks,
>> Richard.
>>
>>> Thanks,
>>> bin
>>>
>>> 2017-04-11  Bin Cheng  <bin.cheng@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.