[lno]: Fixes for linear loop transforms

[Daniel Berlin]

Bootstrapped with -ftree-loop-linear on i686-pc-linux-gnu

Some more changes coming shortly.

2004-05-30  Daniel Berlin  <dberlin@dberlin.org>

	* tree-loop-linear.c (linear_transform_loops): We don't handle sibling
	loops, or loops with multiple exits, yet.
	* lambda-code.c (invariant_in_loop): Check outer loops too for
        right now.
	(lle_to_gcc_expression): Special case the coefficient == 1 cases.
	(lambda_loopnest_to_gcc_loopnest): Use correct test.

Index: lambda-code.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda-code.c,v
retrieving revision 1.1.2.8
diff -u -3 -p -r1.1.2.8 lambda-code.c
--- lambda-code.c	29 May 2004 22:09:02 -0000	1.1.2.8
+++ lambda-code.c	30 May 2004 17:10:53 -0000
@@ -1040,10 +1040,15 @@ gcc_tree_to_linear_expression (int depth
   return lle;
 }

-/* Return true if OP is invariant in LOOP.  */
+/* Return true if OP is invariant in LOOP and all outer loops.
+   XXX: We only need to verify the invariantness in all loops that
+   might now go before this loop according to the transformation.  */
+
 static bool
 invariant_in_loop (struct loop *loop, tree op)
 {
+  if (loop->depth == 0)
+    return true;
   if (TREE_CODE (op) == SSA_NAME)
     {
       if (TREE_CODE (SSA_NAME_VAR (op)) == PARM_DECL
@@ -1051,6 +1056,9 @@ invariant_in_loop (struct loop *loop, tr
 	return true;
       if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (op)))
 	return false;
+      if (loop->outer)
+	if (!invariant_in_loop (loop->outer, op))
+	  return false;
       return !flow_bb_inside_loop_p (loop,
 				     bb_for_stmt (SSA_NAME_DEF_STMT (op)));
     }
@@ -1059,7 +1067,10 @@ invariant_in_loop (struct loop *loop, tr



-/* Generate a lambda loop from a gcc loop.  */
+/* Generate a lambda loop from a gcc loop.
+   TODO: Get rid of most of this code in favor of
+   number_of_iterations_in_loop,  and SCEV stuff, now that it works
+   symbolically.  */

 static lambda_loop
 gcc_loop_to_lambda_loop (struct loop *loop, int depth,
@@ -1461,10 +1472,17 @@ lle_to_gcc_expression (lambda_linear_exp
 	      tree newname;
 	      tree mult;
 	      tree coeff;
-	      coeff = build_int_cst (integer_type_node,
-				     LLE_COEFFICIENTS (lle)[i]);
-	      mult = fold (build (MULT_EXPR, integer_type_node,
-				  VARRAY_TREE (induction_vars, i), coeff));
+	      if (LLE_COEFFICIENTS (lle)[i] == 1)
+		{
+		  mult = VARRAY_TREE (induction_vars, i);
+		}
+	      else
+		{
+		  coeff = build_int_cst (integer_type_node,
+					 LLE_COEFFICIENTS (lle)[i]);
+		  mult = fold (build (MULT_EXPR, integer_type_node,
+				      VARRAY_TREE (induction_vars, i), coeff));
+		}
 	      /* newname = coefficient * induction_variable */
 	      stmt = build (MODIFY_EXPR, void_type_node, resvar, mult);
 	      newname = make_ssa_name (resvar, stmt);
@@ -1490,10 +1508,17 @@ lle_to_gcc_expression (lambda_linear_exp
 	      tree newname;
 	      tree mult;
 	      tree coeff;
-	      coeff = build_int_cst (integer_type_node,
-				     LLE_INVARIANT_COEFFICIENTS (lle)[i]);
-	      mult = fold (build (MULT_EXPR, integer_type_node,
-				  VARRAY_TREE (invariants, i), coeff));
+	      if (LLE_INVARIANT_COEFFICIENTS (lle)[i] == 1)
+		{
+		  mult = VARRAY_TREE (invariants, i);
+		}
+	      else
+		{
+		  coeff = build_int_cst (integer_type_node,
+					 LLE_INVARIANT_COEFFICIENTS (lle)[i]);
+		  mult = fold (build (MULT_EXPR, integer_type_node,
+				      VARRAY_TREE (invariants, i), coeff));
+		}
 	      /* newname = coefficient * invariant */
 	      stmt = build (MODIFY_EXPR, void_type_node, resvar, mult);
 	      newname = make_ssa_name (resvar, stmt);
@@ -1703,7 +1728,7 @@ lambda_loopnest_to_gcc_loopnest (struct
 	    for (k = 0; k < VARRAY_ACTIVE_SIZE (old_ivs); k++)
 	      {
 		tree oldiv = VARRAY_TREE (old_ivs, k);
-		if (SSA_NAME_VAR (*use) == SSA_NAME_VAR (oldiv))
+		if (*use == oldiv)
 		  {
 		    tree newiv, stmts;
 		    lambda_body_vector lbv;
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-loop-linear.c,v
retrieving revision 1.1.2.5
diff -u -3 -p -r1.1.2.5 tree-loop-linear.c
--- tree-loop-linear.c	29 May 2004 22:09:02 -0000	1.1.2.5
+++ tree-loop-linear.c	30 May 2004 17:10:53 -0000
@@ -57,8 +57,7 @@ Software Foundation, 59 Temple Place - S
    TODO: Add dependence matrix collection and appropriate matrix
    calculations so we can determine if a given transformation matrix
    is legal for a loop.
-   TODO: Completion of partial transforms.
-*/
+   TODO: Completion of partial transforms.  */

 /* Perform a set of linear transforms on LOOPS.  */

@@ -74,15 +73,29 @@ linear_transform_loops (struct loops *lo
       lambda_loopnest before, after;
       lambda_trans_matrix trans;

-      if (!loop_nest->inner)
+      /* 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:
+         like
+         for (i = 0; i < 50; i++)_
+           {
+             for (j = 0; j < 50; j++)
+               {
+                ...
+               }
+           for (j = 0; j < 50; j++)
+               {
+                ...
+               }
+           } */
+      if (!loop_nest->inner || loop_nest->inner->next != NULL )
 	continue;
       flow_loop_scan (loop_nest, LOOP_ALL);
       flow_loop_scan (loop_nest->inner, LOOP_ALL);
-#if 0
-      if (loop_nest->num_pre_header_edges != 1
-	  || loop_nest->inner->num_pre_header_edges != 1)
-	  continue;
-#endif
+      /* We also don't handle loops with multiple exit edges.  */
+      if (loop_nest->num_exits != 1
+	  || loop_nest->inner->num_exits != 1)
+	continue;
       before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs, &invariants);
       if (!before)
 	continue;