diff mbox

-ftree-loop-linear fixes (PR tree-optimization/46970)

Message ID 20101217231141.GG2198@tyan-ft48-01.lab.bos.redhat.com
State New
Headers show

Commit Message

Jakub Jelinek Dec. 17, 2010, 11:11 p.m. UTC 
Hi!

gcc_loop_to_lambda_loop doesn't reject both when loop exit condition's
SSA_NAME defined in the loop has defining statement a phi, or
some statement where a single ssa use of it has defining statement a phi,
but actually seems to expect only the latter case, because for the new iv
it uses in the exit condition the incremented iv instead of the phi result.

Additionally, it doesn't check whether the statement really in the middle
is an increment by step, nor whether step isn't e.g. 0x100000001ULL when
it stores into a host int LL_STEP field.

This patch tries to fix that.  The upper bound adjustment still looks unsafe
to me in case it overflows, but that has been a problem before the patch and
is not solved by the patch and would probably need much bigger changes in
lambda-code.c.

Bootstrapped/regtested on x86_64-linux and i686-linux.

2010-12-17  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/46970
	* lambda-code.c (gcc_loop_to_lambda_loop): Give up if
	step doesn't fit into host int or if def stmt of inductionvar
	is neither PHI nor increment by step.  If exit condition
	compares induction variable before increment, adjust ubound
	differently.

	* gcc.dg/pr46970-1.c: New test.
	* gcc.dg/pr46970-2.c: New test.


	Jakub

Comments

Sebastian Pop Dec. 20, 2010, 5:05 a.m. UTC | #1 
On Fri, Dec 17, 2010 at 17:11, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> gcc_loop_to_lambda_loop doesn't reject both when loop exit condition's
> SSA_NAME defined in the loop has defining statement a phi, or
> some statement where a single ssa use of it has defining statement a phi,
> but actually seems to expect only the latter case, because for the new iv
> it uses in the exit condition the incremented iv instead of the phi result.
>
> Additionally, it doesn't check whether the statement really in the middle
> is an increment by step, nor whether step isn't e.g. 0x100000001ULL when
> it stores into a host int LL_STEP field.
>
> This patch tries to fix that.  The upper bound adjustment still looks unsafe
> to me in case it overflows, but that has been a problem before the patch and
> is not solved by the patch and would probably need much bigger changes in
> lambda-code.c.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux.
>
> 2010-12-17  Jakub Jelinek  <jakub@redhat.com>
>
>        PR tree-optimization/46970
>        * lambda-code.c (gcc_loop_to_lambda_loop): Give up if
>        step doesn't fit into host int or if def stmt of inductionvar
>        is neither PHI nor increment by step.  If exit condition
>        compares induction variable before increment, adjust ubound
>        differently.
>
>        * gcc.dg/pr46970-1.c: New test.
>        * gcc.dg/pr46970-2.c: New test.
>

The patch looks good to me, but I cannot approve it.

>   /* We might have some leftover.  */
> -  if (gimple_cond_code (exit_cond) == LT_EXPR)
> -    extra = -1 * stepint;
> -  else if (gimple_cond_code (exit_cond) == NE_EXPR)
> -    extra = -1 * stepint;
> -  else if (gimple_cond_code (exit_cond) == GT_EXPR)
> -    extra = -1 * stepint;
> -  else if (gimple_cond_code (exit_cond) == EQ_EXPR)
> -    extra = 1 * stepint;
> +  if (SSA_NAME_DEF_STMT (inductionvar) != phi)
> +    {
> +      if (gimple_cond_code (exit_cond) == LT_EXPR)
> +       extra = -1 * stepint;
> +      else if (gimple_cond_code (exit_cond) == NE_EXPR)
> +       extra = -1 * stepint;
> +      else if (gimple_cond_code (exit_cond) == GT_EXPR)
> +       extra = -1 * stepint;
> +      else if (gimple_cond_code (exit_cond) == EQ_EXPR)
> +       extra = 1 * stepint;
> +    }
> +  else
> +    {
> +      if (gimple_cond_code (exit_cond) == LE_EXPR)
> +       extra = 1 * stepint;
> +      else if (gimple_cond_code (exit_cond) == GE_EXPR)
> +       extra = 1 * stepint;
> +    }

It would be easier to read the following equivalent code:

if (SSA_NAME_DEF_STMT (inductionvar) != phi)
  {
    enum tree_code code = gimple_cond_code (exit_cond);

    if (code == LT_EXPR
        || code == NE_EXPR
	|| code == GT_EXPR)
     extra = -1 * stepint;
    else if (code == EQ_EXPR)
     extra = 1 * stepint;
  }
else
  {
    enum tree_code code = gimple_cond_code (exit_cond);

    if (code == LE_EXPR
        || code == GE_EXPR)
     extra = 1 * stepint;
  }
diff mbox

Patch

--- gcc/lambda-code.c.jj	2010-08-20 16:05:41.000000000 +0200
+++ gcc/lambda-code.c	2010-12-17 17:57:32.000000000 +0100
@@ -1289,7 +1289,7 @@  gcc_loop_to_lambda_loop (struct loop *lo
   if (gimple_code (phi) != GIMPLE_PHI)
     {
       tree op = SINGLE_SSA_TREE_OPERAND (phi, SSA_OP_USE);
-      if (!op)
+      if (!op || !is_gimple_assign (phi))
 	{
 
 	  if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1332,7 +1332,9 @@  gcc_loop_to_lambda_loop (struct loop *lo
 
       return NULL;
     }
-  if (TREE_CODE (step) != INTEGER_CST)
+  if (!host_integerp (step, 0)
+      || (HOST_WIDE_INT) TREE_INT_CST_LOW (step)
+	  != (int) TREE_INT_CST_LOW (step))
     {
 
       if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1366,6 +1368,32 @@  gcc_loop_to_lambda_loop (struct loop *lo
       return NULL;
     }
 
+  if (SSA_NAME_DEF_STMT (inductionvar) != phi)
+    {
+      gimple stmt = SSA_NAME_DEF_STMT (inductionvar);
+      tree rhs2;
+      int stepintval = stepint;
+      switch (gimple_assign_rhs_code (stmt))
+	{
+	case MINUS_EXPR:
+	  stepintval = -stepint;
+	  /* FALLTHRU */
+	case PLUS_EXPR:
+	case POINTER_PLUS_EXPR:
+	  rhs2 = gimple_assign_rhs2 (stmt);
+	  if (TREE_CODE (rhs2) == INTEGER_CST
+	      && (HOST_WIDE_INT) TREE_INT_CST_LOW (rhs2) == stepintval
+	      && TREE_INT_CST_HIGH (rhs2) == (stepintval >= 0 ? 0 : -1))
+	    break;
+	  /* FALLTHRU */
+	default:
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "Unable to convert loop: Cannot find PHI node for induction variable\n");
+	  return NULL;
+	}
+    }
+
   if (flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, 0)->src))
     {
       lboundvar = PHI_ARG_DEF (phi, 1);
@@ -1417,14 +1445,24 @@  gcc_loop_to_lambda_loop (struct loop *lo
 
 
   /* We might have some leftover.  */
-  if (gimple_cond_code (exit_cond) == LT_EXPR)
-    extra = -1 * stepint;
-  else if (gimple_cond_code (exit_cond) == NE_EXPR)
-    extra = -1 * stepint;
-  else if (gimple_cond_code (exit_cond) == GT_EXPR)
-    extra = -1 * stepint;
-  else if (gimple_cond_code (exit_cond) == EQ_EXPR)
-    extra = 1 * stepint;
+  if (SSA_NAME_DEF_STMT (inductionvar) != phi)
+    {
+      if (gimple_cond_code (exit_cond) == LT_EXPR)
+	extra = -1 * stepint;
+      else if (gimple_cond_code (exit_cond) == NE_EXPR)
+	extra = -1 * stepint;
+      else if (gimple_cond_code (exit_cond) == GT_EXPR)
+	extra = -1 * stepint;
+      else if (gimple_cond_code (exit_cond) == EQ_EXPR)
+	extra = 1 * stepint;
+    }
+  else
+    {
+      if (gimple_cond_code (exit_cond) == LE_EXPR)
+	extra = 1 * stepint;
+      else if (gimple_cond_code (exit_cond) == GE_EXPR)
+	extra = 1 * stepint;
+    }
 
   ubound = gcc_tree_to_linear_expression (depth, uboundvar,
 					  outerinductionvars,
--- gcc/testsuite/gcc.dg/pr46970-1.c.jj	2010-12-17 16:08:01.000000000 +0100
+++ gcc/testsuite/gcc.dg/pr46970-1.c	2010-12-17 16:07:46.000000000 +0100
@@ -0,0 +1,27 @@ 
+/* PR tree-optimization/46970 */
+/* { dg-do run } */
+/* { dg-options "-Os -ftree-loop-linear" } */
+
+int
+foo (int n, int *a)
+{
+  int i, j;
+
+  for (i = 0; i < n; i++)
+    for (j = 0; j < n; j++)
+      a[j] = i + n;
+
+  for (j = 0; j < n; j++)
+    if (a[j] != i + n - 1)
+      __builtin_abort ();
+
+  return 0;
+}
+
+int
+main ()
+{
+  int a[16];
+  foo (16, a);
+  return 0;
+}
--- gcc/testsuite/gcc.dg/pr46970-2.c.jj	2010-12-17 18:01:05.000000000 +0100
+++ gcc/testsuite/gcc.dg/pr46970-2.c	2010-12-17 16:43:46.000000000 +0100
@@ -0,0 +1,28 @@ 
+/* { dg-do run } */
+/* { dg-options "-O2 -ftree-loop-linear" } */
+/* { dg-require-effective-target size32plus } */
+
+double u[1782225];
+
+__attribute__((noinline, noclone)) int
+foo (int N, int *res)
+{
+  unsigned int i, j;
+  double sum = 0;
+  for (i = 0; i < N; i++)
+    for (j = 0; j < N; j++)
+      sum = sum + u[i + 1335 * j];
+  *res = sum + N;
+}
+
+int
+main (void)
+{
+  int i;
+  for (i = 0; i < 1782225; i++)
+    u[i] = 1.0;
+  foo (64, &i);
+  if (i != 4160)
+    __builtin_abort ();
+  return 0;
+}