Preliminary patch for PR23820 and PR24309

["Sebastian Pop" <sebpop at gmail dot com>]

Hi,

Attached is a patch that fixes both problems with the lambda
framework.  While testing, I observed that ltrans-3.c now fails
because there are more than 3 basic blocks in the outer loop, making
the new implementation of the perfect_nest_p saying that this is not a
perfect nest.

What is the name of the pass that cannonicalizes the CFG removing
empty basic blocks containing only labels, or just a goto, as the
following one?


 bb_9 (preds = {bb_7 }, succs = {bb_10 })
    {
    <bb 9>:

    }

Thanks,
Sebastian

Index: tree-loop-linear.c
===================================================================
--- tree-loop-linear.c	(revision 129032)
+++ tree-loop-linear.c	(working copy)
@@ -244,6 +244,46 @@ try_interchange_loops (lambda_trans_matr
   return trans;
 }
 
+/* Return the number of nested loops in LOOP_NEST, or 0 if the loops
+   are not perfectly nested.  */
+
+static unsigned int
+perfect_loop_nest_depth (struct loop *loop_nest)
+{
+  struct loop *temp;
+  unsigned int depth = 1;
+
+  /* If it's not a loop nest, we don't want it.  We also don't handle
+     sibling loops properly, which are loops of the following form:
+
+     | for (i = 0; i < 50; i++)
+     |   {
+     |     for (j = 0; j < 50; j++)
+     |       {
+     |        ...
+     |       }
+     |     for (j = 0; j < 50; j++)
+     |       {
+     |        ...
+     |       }
+     |   }
+  */
+
+  if (!loop_nest->inner || !single_exit (loop_nest))
+    return 0;
+
+  for (temp = loop_nest->inner; temp; temp = temp->inner)
+    {
+      /* If we have a sibling loop or multiple exit edges, jump ship.  */
+      if (temp->next || !single_exit (temp))
+	return 0;
+
+      depth++;
+    }
+
+  return depth;
+}
+
 /* Perform a set of linear transforms on loops.  */
 
 void
@@ -263,47 +303,18 @@ linear_transform_loops (void)
       unsigned int depth = 0;
       VEC (ddr_p, heap) *dependence_relations;
       VEC (data_reference_p, heap) *datarefs;
-      struct loop *temp;
       lambda_loopnest before, after;
       lambda_trans_matrix trans;
-      bool problem = false;
       struct obstack lambda_obstack;
       gcc_obstack_init (&lambda_obstack);
 
-      /* If it's not a loop nest, we don't want it.
-         We also don't handle sibling loops properly, 
-         which are loops of the following form:
-         for (i = 0; i < 50; i++)
-           {
-             for (j = 0; j < 50; j++)
-               {
-	        ...
-               }
-             for (j = 0; j < 50; j++)
-               {
-                ...
-               }
-           } */
-      if (!loop_nest->inner || !single_exit (loop_nest))
+      depth = perfect_loop_nest_depth (loop_nest);
+      if (depth == 0)
 	continue;
+
       VEC_truncate (tree, oldivs, 0);
       VEC_truncate (tree, invariants, 0);
-      depth = 1;
-      for (temp = loop_nest->inner; temp; temp = temp->inner)
-	{
-	  /* If we have a sibling loop or multiple exit edges, jump ship.  */
-	  if (temp->next || !single_exit (temp))
-	    {
-	      problem = true;
-	      break;
-	    }
-	  depth ++;
-	}
-      if (problem)
-	continue;
 
-      /* Analyze data references and dependence relations using scev.  */      
- 
       datarefs = VEC_alloc (data_reference_p, heap, 10);
       dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
       compute_data_dependences_for_loop (loop_nest, true, &datarefs,
@@ -353,12 +364,12 @@ linear_transform_loops (void)
 	  print_lambda_loopnest (dump_file, after, 'u');
 	}
 
-      lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
-				       &remove_ivs,
-                                       after, trans, &lambda_obstack);
-      modified = true;
+      modified = lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, 
+						  invariants, &remove_ivs,
+						  after, trans,
+						  &lambda_obstack);
 
-      if (dump_file)
+      if (modified && dump_file)
 	fprintf (dump_file, "Successfully transformed loop.\n");
 
     free_and_continue:
Index: testsuite/gcc.dg/tree-ssa/pr23820.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/pr23820.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/pr23820.c	(revision 0)
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-loop-linear" } */
+
+int t [2][4];
+
+void foo (void)
+{
+  int i, j, k, v;
+  float e;
+  for (;;)
+    {
+      v = 0;
+      for (j = 0; j < 2; j ++)
+        {
+          for (k = 2; k < 4; k ++)
+            {
+              e = 0.0;
+              for (i = 0; i < 4; i ++)
+                e += t [j][i];
+              if (e)
+                v = j;
+            }
+        }
+      t [v][0] = 0;
+    }
+}
Index: testsuite/gcc.dg/tree-ssa/pr24309.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/pr24309.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/pr24309.c	(revision 0)
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-loop-linear" } */
+
+float weight[10];
+void lsp_weight_quant(float *x, char *cdbk)
+{
+   int i,j;
+   float dist;
+   int best_id=0;
+   for (i=0;i<16;i++)
+   {
+      for (j=0;j<10;j++)
+         dist=dist+weight[j];
+      if (dist<0)
+         best_id=i;
+   }
+   x[j] = cdbk[best_id*10+j];
+}
Index: lambda.h
===================================================================
--- lambda.h	(revision 129032)
+++ lambda.h	(working copy)
@@ -204,7 +204,7 @@ lambda_loopnest gcc_loopnest_to_lambda_l
 						 VEC(tree,heap) **,
                                                  VEC(tree,heap) **,
                                                  struct obstack *);
-void lambda_loopnest_to_gcc_loopnest (struct loop *,
+bool lambda_loopnest_to_gcc_loopnest (struct loop *,
 				      VEC(tree,heap) *, VEC(tree,heap) *,
 				      VEC(tree,heap) **,
                                       lambda_loopnest, lambda_trans_matrix,
Index: lambda-code.c
===================================================================
--- lambda-code.c	(revision 129032)
+++ lambda-code.c	(working copy)
@@ -1675,6 +1675,37 @@ remove_iv (tree iv_stmt)
     }
 }
 
+/* Return true if we are sure that the code generation cannot be
+   performed for this loop nest.  */
+
+static bool
+lambda_cannot_generate_loop_nest (VEC (tree, heap) *old_ivs)
+{
+  unsigned i;
+  tree oldiv;
+
+  for (i = 0; VEC_iterate (tree, old_ivs, i, oldiv); i++)
+    {
+      imm_use_iterator imm_iter;
+      tree oldiv_def;
+      tree oldiv_stmt = SSA_NAME_DEF_STMT (oldiv);
+      tree stmt;
+
+      if (TREE_CODE (oldiv_stmt) == PHI_NODE)
+        oldiv_def = PHI_RESULT (oldiv_stmt);
+      else
+	oldiv_def = SINGLE_SSA_TREE_OPERAND (oldiv_stmt, SSA_OP_DEF);
+      gcc_assert (oldiv_def != NULL_TREE);
+
+      FOR_EACH_IMM_USE_STMT (stmt, imm_iter, oldiv_def)
+        {
+	  if (TREE_CODE (stmt) == PHI_NODE)
+	    return true;
+	}
+    }
+
+  return false;
+}
 
 /* Transform a lambda loopnest NEW_LOOPNEST, which had TRANSFORM applied to
    it, back into gcc code.  This changes the
@@ -1686,9 +1717,11 @@ remove_iv (tree iv_stmt)
    INVARIANTS is a vector of loop invariants from the old loopnest.
    NEW_LOOPNEST is the new lambda loopnest to replace OLD_LOOPNEST with.
    TRANSFORM is the matrix transform that was applied to OLD_LOOPNEST to get 
-   NEW_LOOPNEST.  */
+   NEW_LOOPNEST.  
+
+   Returns true when the code generation succeeded.  */
 
-void
+bool
 lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
 				 VEC(tree,heap) *old_ivs,
 				 VEC(tree,heap) *invariants,
@@ -1705,6 +1738,14 @@ lambda_loopnest_to_gcc_loopnest (struct 
   
   block_stmt_iterator bsi;
 
+  if (lambda_cannot_generate_loop_nest (old_ivs))
+    {
+      if (dump_file)
+	fprintf (dump_file, "Lambda code generation failed to produce code.\n");
+
+      return false;
+    }
+
   if (dump_file)
     {
       transform = lambda_trans_matrix_inverse (transform);
@@ -1865,6 +1906,8 @@ lambda_loopnest_to_gcc_loopnest (struct 
       VEC_safe_push (tree, heap, *remove_ivs, oldiv_stmt);
     }
   VEC_free (tree, heap, new_ivs);
+
+  return true;
 }
 
 /* Return TRUE if this is not interesting statement from the perspective of
@@ -1969,18 +2012,30 @@ bool
 perfect_nest_p (struct loop *loop)
 {
   basic_block *bbs;
-  size_t i;
+  size_t i, n_bb = 0;
   tree exit_cond;
 
+  /* Loops at depth 0 are perfect nests.  */
   if (!loop->inner)
     return true;
+
   bbs = get_loop_body (loop);
   exit_cond = get_loop_exit_condition (loop);
+
   for (i = 0; i < loop->num_nodes; i++)
     {
       if (bbs[i]->loop_father == loop)
 	{
 	  block_stmt_iterator bsi;
+
+	  /* A nest is not perfect when there are more than three
+	     basic blocks per non innermost loop.  */
+	  if (n_bb++ >= 3)
+	    {
+	      free (bbs);
+	      return false;
+	    }
+
 	  for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
 	    {
 	      tree stmt = bsi_stmt (bsi);
@@ -1993,11 +2048,10 @@ perfect_nest_p (struct loop *loop)
 	    }
 	}
     }
+
   free (bbs);
-  /* See if the inner loops are perfectly nested as well.  */
-  if (loop->inner)    
-    return perfect_nest_p (loop->inner);
-  return true;
+
+  return perfect_nest_p (loop->inner);
 }
 
 /* Replace the USES of X in STMT, or uses with the same step as X with Y.