Makefile.in (tree-loop-linear.o): Added.

2004-09-08  Daniel Berlin  <dberlin@dberlin.org>

	* Makefile.in (tree-loop-linear.o): Added.
	(OBJS-common): Add tree-loop-linear.o
	* common.opt: New flag, ftree-loop-linear.
	* timevar.def: New timevar, TV_TREE_LOOP_LINEAR.
	* tree-flow.h: Add prototype for linear_transform_loops.
	* tree-optimize.c: Add linear transform after vectorization.
	* tree-pass.h: Add struct pass_linear_transform.
	* tree-ssa-loop.c: Add pass_linear_transform.
	* tree-loop-linear.c: New file.
	* lambda-code.c: gcc_assertify.
	(gcc_loop_to_lambda_loop): Handle all exit tests.
	Handle case where we have (invariant >= induction var).
	(find_induction_var_from_exit_cond): Ditto.

From-SVN: r87190

1 files changed, 60 insertions, 44 deletions

diff --git a/gcc/lambda-code.c b/gcc/lambda-code.c
index be11950..6ae4cb2 100644
--- a/gcc/lambda-code.c
+++ b/gcc/lambda-code.c
@@ -169,8 +169,7 @@ lambda_body_vector_compute_new (lambda_trans_matrix transform,
   int depth;
 
   /* Make sure the matrix is square.  */
-  if (LTM_ROWSIZE (transform) != LTM_COLSIZE (transform))
-    abort ();
+  gcc_assert (LTM_ROWSIZE (transform) == LTM_COLSIZE (transform));
 
   depth = LTM_ROWSIZE (transform);
 
@@ -297,8 +296,7 @@ print_lambda_loop (FILE * outfile, lambda_loop loop, int depth,
   int step;
   lambda_linear_expression expr;
 
-  if (!loop)
-    abort ();
+  gcc_assert (loop);
 
   expr = LL_LINEAR_OFFSET (loop);
   step = LL_STEP (loop);
@@ -393,8 +391,7 @@ lambda_lattice_compute_base (lambda_loopnest nest)
   for (i = 0; i < depth; i++)
     {
       loop = LN_LOOPS (nest)[i];
-      if (!loop)
-	abort ();
+      gcc_assert (loop);
       step = LL_STEP (loop);
       /* If we have a step of 1, then the base is one, and the
          origin and invariant coefficients are 0.  */
@@ -412,9 +409,8 @@ lambda_lattice_compute_base (lambda_loopnest nest)
 	  /* Otherwise, we need the lower bound expression (which must
 	     be an affine function)  to determine the base.  */
 	  expression = LL_LOWER_BOUND (loop);
-	  if (!expression
-	      || LLE_NEXT (expression) || LLE_DENOMINATOR (expression) != 1)
-	    abort ();
+	  gcc_assert (expression && LLE_NEXT (expression) 
+		      && LLE_DENOMINATOR (expression) == 1);
 
 	  /* The lower triangular portion of the base is going to be the
 	     coefficient times the step */
@@ -556,8 +552,8 @@ lambda_compute_auxillary_space (lambda_loopnest nest,
 
 	  size++;
 	  /* Need to increase matrix sizes above.  */
-	  if (size > 127)
-	    abort ();
+	  gcc_assert (size <= 127);
+	  
 	}
 
       /* Then do the exact same thing for the upper bounds.  */
@@ -585,8 +581,8 @@ lambda_compute_auxillary_space (lambda_loopnest nest,
 	  A[size][i] = LLE_DENOMINATOR (expression);
 	  size++;
 	  /* Need to increase matrix sizes above.  */
-	  if (size > 127)
-	    abort ();
+	  gcc_assert (size <= 127);
+
 	}
     }
 
@@ -1205,7 +1201,7 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth,
   tree test;
   int stepint;
   int extra = 0;
-
+  tree uboundvar;
   use_optype uses;
 
   /* Find out induction var and set the pointer so that the caller can
@@ -1225,19 +1221,7 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth,
     }
 
   test = TREE_OPERAND (exit_cond, 0);
-  if (TREE_CODE (test) != LE_EXPR
-      && TREE_CODE (test) != LT_EXPR && TREE_CODE (test) != NE_EXPR)
-    {
 
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	{
-	  fprintf (dump_file,
-		   "Unable to convert loop: Loop exit test uses unhandled test condition:");
-	  print_generic_stmt (dump_file, test, 0);
-	  fprintf (dump_file, "\n");
-	}
-      return NULL;
-    }
   if (SSA_NAME_DEF_STMT (inductionvar) == NULL_TREE)
     {
 
@@ -1349,25 +1333,39 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth,
 
       return NULL;
     }
-  if (TREE_CODE (TREE_OPERAND (test, 1)) == SSA_NAME)
-    if (invariant_in_loop (loop, TREE_OPERAND (test, 1)))
-      VEC_safe_push (tree, *invariants, TREE_OPERAND (test, 1));
+  /* One part of the test may be a loop invariant tree.  */
+  if (TREE_CODE (TREE_OPERAND (test, 1)) == SSA_NAME
+      && invariant_in_loop (loop, TREE_OPERAND (test, 1)))
+    VEC_safe_push (tree, *invariants, TREE_OPERAND (test, 1));
+  else if (TREE_CODE (TREE_OPERAND (test, 0)) == SSA_NAME
+	   && invariant_in_loop (loop, TREE_OPERAND (test, 0)))
+    VEC_safe_push (tree, *invariants, TREE_OPERAND (test, 0));
+  
+  /* The non-induction variable part of the test is the upper bound variable.
+   */
+  if (TREE_OPERAND (test, 0) == inductionvar)
+    uboundvar = TREE_OPERAND (test, 1);
+  else
+    uboundvar = TREE_OPERAND (test, 0);
+    
 
   /* We only size the vectors assuming we have, at max, 2 times as many
      invariants as we do loops (one for each bound).
      This is just an arbitrary number, but it has to be matched against the
      code below.  */
-  if (VEC_length (tree, *invariants) > (unsigned int) (2 * depth))
-    abort ();
+  gcc_assert (VEC_length (tree, *invariants) <= (unsigned int) (2 * depth));
+  
 
   /* We might have some leftover.  */
   if (TREE_CODE (test) == LT_EXPR)
     extra = -1 * stepint;
   else if (TREE_CODE (test) == NE_EXPR)
     extra = -1 * stepint;
+  else if (TREE_CODE (test) == GT_EXPR)
+    extra = -1 * stepint;
 
   ubound = gcc_tree_to_linear_expression (depth,
-					  TREE_OPERAND (test, 1),
+					  uboundvar,
 					  outerinductionvars,
 					  *invariants, extra);
   if (!ubound)
@@ -1393,6 +1391,7 @@ static tree
 find_induction_var_from_exit_cond (struct loop *loop)
 {
   tree expr = get_loop_exit_condition (loop);
+  tree ivarop;
   tree test;
   if (expr == NULL_TREE)
     return NULL_TREE;
@@ -1401,9 +1400,28 @@ find_induction_var_from_exit_cond (struct loop *loop)
   test = TREE_OPERAND (expr, 0);
   if (TREE_CODE_CLASS (TREE_CODE (test)) != '<')
     return NULL_TREE;
-  if (TREE_CODE (TREE_OPERAND (test, 0)) != SSA_NAME)
+ /* This is a guess.  We say that for a <,!=,<= b, a is the induction
+     variable.
+     For >, >=, we guess b is the induction variable.
+     If we are wrong, it'll fail the rest of the induction variable tests, and
+     everything will be fine anyway.  */
+  switch (TREE_CODE (test))
+    {
+    case LT_EXPR:
+    case LE_EXPR:
+    case NE_EXPR:
+      ivarop = TREE_OPERAND (test, 0);
+      break;
+    case GT_EXPR:
+    case GE_EXPR:
+      ivarop = TREE_OPERAND (test, 1);
+      break;
+    default:
+      gcc_unreachable();
+    }
+  if (TREE_CODE (ivarop) != SSA_NAME)
     return NULL_TREE;
-  return TREE_OPERAND (test, 0);
+  return ivarop;
 }
 
 DEF_VEC_GC_P(lambda_loop);
@@ -1693,7 +1711,7 @@ lle_to_gcc_expression (lambda_linear_expression lle,
 				 name, build_int_cst (integer_type_node,
 						      LLE_DENOMINATOR (lle))));
 	  else
-	    abort ();
+	    gcc_unreachable();
 
 	  /* name = {ceil, floor}(name/denominator) */
 	  name = make_ssa_name (resvar, stmt);
@@ -1706,9 +1724,8 @@ lle_to_gcc_expression (lambda_linear_expression lle,
 
   /* Again, out of laziness, we don't handle this case yet.  It's not
      hard, it just hasn't occurred.  */
-  if (VEC_length (tree, results) > 2)
-    abort ();
-
+  gcc_assert (VEC_length (tree, results) <= 2);
+  
   /* We may need to wrap the results in a MAX_EXPR or MIN_EXPR.  */
   if (VEC_length (tree, results) > 1)
     {
@@ -1788,10 +1805,9 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
          cases for now.  */
       offset = LL_LINEAR_OFFSET (newloop);
 
-      if (LLE_DENOMINATOR (offset) != 1
-	  || !lambda_vector_zerop (LLE_COEFFICIENTS (offset), depth))
-	abort ();
-
+      gcc_assert (LLE_DENOMINATOR (offset) == 1 &&
+		  lambda_vector_zerop (LLE_COEFFICIENTS (offset), depth));
+      
       /* Now build the  new lower bounds, and insert the statements
          necessary to generate it on the loop preheader.  */
       newlowerbound = lle_to_gcc_expression (LL_LOWER_BOUND (newloop),
@@ -1929,8 +1945,8 @@ lambda_transform_legal_p (lambda_trans_matrix trans,
   struct data_dependence_relation *ddr;
 
 #if defined ENABLE_CHECKING
-  if (LTM_COLSIZE (trans) != nb_loops || LTM_ROWSIZE (trans) != nb_loops)
-    abort ();
+  gcc_assert (LTM_COLSIZE (trans) == nb_loops 
+	      && LTM_ROWSIZE (trans) == nb_loops);
 #endif
 
   /* When there is an unknown relation in the dependence_relations, we