This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH GCC]Catch more MEM_REFs sharing common addressing part in gimple strength reduction


On Mon, 2013-09-02 at 11:15 +0200, Richard Biener wrote:
> On Mon, Sep 2, 2013 at 8:56 AM, bin.cheng <bin.cheng@arm.com> wrote:
> > Hi,
> >
> > The gimple-ssa-strength-reduction pass handles CAND_REFs in order to find
> > different MEM_REFs sharing common part in addressing expression.  If such
> > MEM_REFs are found, the pass rewrites MEM_REFs, and produces more efficient
> > addressing expression during the RTL passes.
> > The pass analyzes addressing expression in each MEM_REF to see if it can be
> > formalized as follows:
> >      base:    MEM_REF (T1, C1)
> >      offset:  MULT_EXPR (PLUS_EXPR (T2, C2), C3)
> >      bitpos:  C4 * BITS_PER_UNIT
> > Then restructures it into below form:
> >      MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
> >               C1 + (C2 * C3) + C4)
> > At last, rewrite the MEM_REFs if there are two or more sharing common
> > (non-constant) part.
> > The problem is it doesn't back trace T2.  If T2 is recorded as a CAND_ADD in
> > form of "T2' + C5", the MEM_REF should be restructure into:
> >      MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2', C3)),
> >               C1 + (C2 * C3) + C4 + (C5 * C3))
> >
> > The patch also includes a test case to illustrate the problem.
> >
> > Bootstrapped and tested on x86/x86_64/arm-a15, is it ok?
> 
> This looks ok to me if Bill is ok with it.

This is a good generalization and I'm fine with it.  There are a few
minor nits that should be corrected, outlined below.

> 
> Thanks,
> Richard.
> 
> > Thanks.
> > bin
> >
> > 2013-09-02  Bin Cheng  <bin.cheng@arm.com>
> >
> >         * gimple-ssa-strength-reduction.c (backtrace_base_for_ref): New.
> >         (restructure_reference): Call backtrace_base_for_ref.
> >
> > gcc/testsuite/ChangeLog
> > 2013-09-02  Bin Cheng  <bin.cheng@arm.com>
> >
> >         * gcc.dg/tree-ssa/slsr-39.c: New test.
> 

>>Index: gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c
>>===================================================================
>>--- >>gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c	>>(revision 0)
>>+++ >>gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c	>>(revision 0)
>>@@ -0,0 +1,26 @@
>>+/* Verify straight-line strength reduction for back-tracing
>>+   CADN_ADD for T2 in:

CAND_ADD

>>+
>>+    *PBASE:    T1
>>+    *POFFSET:  MULT_EXPR (T2, C3)
>>+    *PINDEX:   C1 + (C2 * C3) + C4  */
>>+
>>+/* { dg-do compile } */
>>+/* { dg-options "-O2 -fdump-tree-slsr" } */
>>+
>>+typedef int arr_2[50][50];
>>+
>>+void foo (arr_2 a2, int v1)
>>+{
>>+  int i, j;
>>+
>>+  i = v1 + 5;
>>+  j = i;
>>+  a2 [i] [j++] = i;
>>+  a2 [i] [j++] = i;
>>+  a2 [i] [i-1] += 1;
>>+  return;
>>+}
>>+
>>+/* { dg-final { scan-tree-dump-times "MEM" 4 "slsr" } } */
>>+/* { dg-final { cleanup-tree-dump "slsr" } } */
>>Index: gcc/gimple-ssa-strength-reduction.c
>>===================================================================
>>--- >>gcc/gimple-ssa-strength-reduction.c	>>(revision 202067)
>>+++ >>gcc/gimple-ssa-strength-reduction.c	>>(working copy)
>>@@ -750,6 +750,57 @@ slsr_process_phi (gimple phi, bool speed)
>>   add_cand_for_stmt (phi, c);
>> }
>> 
>>+/* Given PBASE which is a pointer to tree, loop up the defining

look up

>>+   statement for it and check whether the candidate is in the
>>+   form of:
>>+
>>+     X = B + (1 * S), S is integer constant
>>+     X = B + (i * S), S is integer one
>>+
>>+   If so, set PBASE to the candiate's base_expr and return double

candidate's

>>+   int (i * S).
>>+   Otherwise, just return double int zero.  */

This is sufficient, since you are properly checking the next_interp
chain.  Another possible form would be

    X = (B + i) * 1,

but if this is present, then one of the forms you're checking for should
also be present, so there's no need to check the MULT_CANDs.

>>+
>>+static double_int
>>+backtrace_base_for_ref (tree *pbase)
>>+{
>>+  tree base_in = *pbase;
>>+  slsr_cand_t base_cand;
>>+
>>+  STRIP_NOPS (base_in);
>>+  if (TREE_CODE (base_in) != SSA_NAME)
>>+    return tree_to_double_int (integer_zero_node);
>>+
>>+  base_cand = base_cand_from_table (base_in);
>>+
>>+  while (base_cand && base_cand->kind != CAND_PHI)
>>+    {
>>+      if (base_cand->kind == CAND_ADD
>>+	  && base_cand->index.is_one ()
>>+	  && TREE_CODE (base_cand->stride) == INTEGER_CST)
>>+	{
>>+	  /* X = B + (1 * S), S is integer constant.  */
>>+	  *pbase = base_cand->base_expr;
>>+	  return tree_to_double_int (base_cand->stride);
>>+	}
>>+      else if (base_cand->kind == CAND_ADD
>>+	       && TREE_CODE (base_cand->stride) == INTEGER_CST
>>+	       && integer_onep (base_cand->stride))
>>+        {
>>+	  /* X = B + (i * S), S is integer one.  */
>>+	  *pbase = base_cand->base_expr;
>>+	  return base_cand->index;
>>+	}
>>+
>>+      if (base_cand->next_interp)
>>+	base_cand = lookup_cand (base_cand->next_interp);
>>+      else
>>+	base_cand = NULL;
>>+    }
>>+
>>+  return tree_to_double_int (integer_zero_node);
>>+}
>>+
>> /* Look for the following pattern:
>> 
>>     *PBASE:    MEM_REF (T1, C1)
>>@@ -767,8 +818,15 @@ slsr_process_phi (gimple phi, bool speed)
>> 
>>     *PBASE:    T1
>>     *POFFSET:  MULT_EXPR (T2, C3)
>>-    *PINDEX:   C1 + (C2 * C3) + C4  */
>>+    *PINDEX:   C1 + (C2 * C3) + C4
>> 
>>+   When T2 is recorded by an CAND_ADD in the form of (T2' + C5), It
                             ^                                      ^
                             a                                      it

>>+   will be further restructured to:
>>+
>>+    *PBASE:    T1
>>+    *POFFSET:  MULT_EXPR (T2', C3)
>>+    *PINDEX:   C1 + (C2 * C3) + C4 + (C5 * C3)  */
>>+
>> static bool
>> restructure_reference (tree *pbase, tree *poffset, double_int
*pindex,
>> 		       tree *ptype)
>>@@ -777,7 +835,7 @@ restructure_reference (tree *pbase, tree *poffset,
>>   double_int index = *pindex;
>>   double_int bpu = double_int::from_uhwi (BITS_PER_UNIT);
>>   tree mult_op0, mult_op1, t1, t2, type;
>>-  double_int c1, c2, c3, c4;
>>+  double_int c1, c2, c3, c4, c5;
>> 
>>   if (!base
>>       || !offset
>>@@ -823,11 +881,12 @@ restructure_reference (tree *pbase, tree
*poffset,
>>     }
>> 
>>   c4 = index.udiv (bpu, FLOOR_DIV_EXPR);
>>+  c5 = backtrace_base_for_ref (&t2);
>> 
>>   *pbase = t1;
>>-  *poffset = fold_build2 (MULT_EXPR, sizetype, t2,
>>-			  double_int_to_tree (sizetype, c3));
>>-  *pindex = c1 + c2 * c3 + c4;
>>+  *poffset = size_binop (MULT_EXPR, fold_convert (sizetype, t2),
>>+			 double_int_to_tree (sizetype, c3));

I am not sure why you changed this call.  fold_build2 is a more
efficient call than size_binop.  size_binop makes several checks that
will fail in this case, and then calls fold_build2_loc, right?  Not a
big deal but seems like changing it back would be better.  Perhaps I'm
missing something (as usual ;).

Thanks,
Bill

>>+  *pindex = c1 + c2 * c3 + c4 + c5 * c3;
>>   *ptype = type;
>> 
>>   return true;



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]