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

Submitted by Bin Cheng on April 18, 2017, 10:46 a.m.

Details

Message ID VI1PR0802MB2176BEAC53A37DCA039C0137E7190@VI1PR0802MB2176.eurprd08.prod.outlook.com
State New
Headers show

Commit Message

Bin Cheng April 18, 2017, 10:46 a.m.
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.
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(-)

Comments

Richard Guenther May 3, 2017, 1:43 p.m.
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.

Patch hide | download patch | download mbox

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