2004-10-16 Daniel Berlin <dberlin@dberlin.org>

	Fix PR tree-optimization/17672
	Fix PR tree-optimization/18168

	* lambda-code.c (lambda_lattice_compute_base): Fix reversed
	assert test.
	(gcc_tree_to_linear_expression): Add extra to existing constant.
	(depth_of_nest): Factor out function used in various places.
	(gcc_loop_to_lambda_loop): Clean up code a little bit. No
	functional changes.
	(find_induction_var_from_exit_cond): Stop guessing, and just
	get the right answer :).
	(gcc_loopnest_to_lambda_loopnest): Remove useless pre-allocation.
	Print out message about result of attempt to create perfect nest.
	(lbv_to_gcc_expression): Add type argument, use it to do math
	and induction variable creation.
	(lle_to_gcc_expression): Ditto.
	(lambda_loopnest_to_gcc_loopnest): Create new iv with same type as
	oldiv. Pass type argument to lle_to_gcc_expression and
	lbv_to_gcc_expression.
	Reset number of iterations after transformation.
	(perfect_nestify): Remove useless pre-allocation, and cleanup
	a small amount.

	* tree-data-ref.c (build_classic_dist_vector): Return false for
	dependences completely outside of the loop nest we asked about.
	(build_classic_dir_vector): Ditto.
	(compute_data_dependences_for_loop): Only add dependence relations
	inside the loop we asked about.

	* tree-loop-linear.c (linear_transform_loops): Use DDR_SIZE_VECT.
	Compute immediate uses.

	* tree-optimize.c: Move linear_transform_loops to before ivcanon.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@89945 138bc75d-0d04-0410-961f-82ee72b054a4

10 files changed, 380 insertions, 181 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d35a73c759a..bfae47a04d3 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,39 @@
+2004-10-16  Daniel Berlin  <dberlin@dberlin.org>
+
+	Fix PR tree-optimization/17672
+	Fix PR tree-optimization/18168
+	
+	* lambda-code.c (lambda_lattice_compute_base): Fix reversed
+	assert test.
+	(gcc_tree_to_linear_expression): Add extra to existing constant.
+	(depth_of_nest): Factor out function used in various places.
+	(gcc_loop_to_lambda_loop): Clean up code a little bit. No
+	functional changes.
+	(find_induction_var_from_exit_cond): Stop guessing, and just
+	get the right answer :).
+	(gcc_loopnest_to_lambda_loopnest): Remove useless pre-allocation.
+	Print out message about result of attempt to create perfect nest.
+	(lbv_to_gcc_expression): Add type argument, use it to do math
+	and induction variable creation.
+	(lle_to_gcc_expression): Ditto.
+	(lambda_loopnest_to_gcc_loopnest): Create new iv with same type as
+	oldiv. Pass type argument to lle_to_gcc_expression and 
+	lbv_to_gcc_expression.
+	Reset number of iterations after transformation.
+	(perfect_nestify): Remove useless pre-allocation, and cleanup
+	a small amount.
+
+	* tree-data-ref.c (build_classic_dist_vector): Return false for
+	dependences completely outside of the loop nest we asked about.
+	(build_classic_dir_vector): Ditto.
+	(compute_data_dependences_for_loop): Only add dependence relations
+	inside the loop we asked about.
+	
+	* tree-loop-linear.c (linear_transform_loops): Use DDR_SIZE_VECT.
+	Compute immediate uses.
+	
+	* tree-optimize.c: Move linear_transform_loops to before ivcanon.
+	
 2004-11-01  Kazu Hirata  <kazu@cs.umass.edu>
 
 	* tree-cfg.c (thread_jumps): Fix a comment typo.
diff --git a/gcc/lambda-code.c b/gcc/lambda-code.c
index 38c1fd1f4e0..d564f431ea4 100644
--- a/gcc/lambda-code.c
+++ b/gcc/lambda-code.c
@@ -51,7 +51,7 @@
  Keshav Pingali for formal proofs that the various statements below are
  correct. 
 
- A loop iteration space are the points traversed by the loop.  A point in the
+ A loop iteration space represents the points traversed by the loop.  A point in the
  iteration space can be represented by a vector of size <loop depth>.  You can
  therefore represent the iteration space as a integral combinations of a set
  of basis vectors. 
@@ -116,7 +116,6 @@
  of the lattice.  */
 
 
-
 DEF_VEC_GC_P(int);
 
 static bool perfect_nestify (struct loops *, 
@@ -416,7 +415,7 @@ 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);
-	  gcc_assert (expression && LLE_NEXT (expression) 
+	  gcc_assert (expression && !LLE_NEXT (expression) 
 		      && LLE_DENOMINATOR (expression) == 1);
 
 	  /* The lower triangular portion of the base is going to be the
@@ -491,7 +490,7 @@ lcm (int a, int b)
 
 /* Perform Fourier-Motzkin elimination to calculate the bounds of the
    auxillary nest.
-   Fourier-Motzkin is a way of reducing systems of linear inequality so that
+   Fourier-Motzkin is a way of reducing systems of linear inequalities so that
    it is easy to calculate the answer and bounds.
    A sketch of how it works:
    Given a system of linear inequalities, ai * xj >= bk, you can always
@@ -1150,7 +1149,7 @@ gcc_tree_to_linear_expression (int depth, tree expr,
 	lle = lambda_linear_expression_new (depth, 2 * depth);
 	LLE_CONSTANT (lle) = TREE_INT_CST_LOW (expr);
 	if (extra != 0)
-	  LLE_CONSTANT (lle) = extra;
+	  LLE_CONSTANT (lle) += extra;
 
 	LLE_DENOMINATOR (lle) = 1;
       }
@@ -1193,6 +1192,21 @@ gcc_tree_to_linear_expression (int depth, tree expr,
   return lle;
 }
 
+/* Return the depth of the loopnest NEST */
+
+static int 
+depth_of_nest (struct loop *nest)
+{
+  size_t depth = 0;
+  while (nest)
+    {
+      depth++;
+      nest = nest->inner;
+    }
+  return depth;
+}
+
+
 /* Return true if OP is invariant in LOOP and all outer loops.  */
 
 static bool
@@ -1236,7 +1250,7 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth,
   tree test;
   int stepint;
   int extra = 0;
-  tree lboundvar, uboundvar;
+  tree lboundvar, uboundvar, uboundresult;
   use_optype uses;
 
   /* Find out induction var and exit condition.  */
@@ -1291,16 +1305,17 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth,
 	}
 
     }
+
   /* The induction variable name/version we want to put in the array is the
      result of the induction variable phi node.  */
   *ourinductionvar = PHI_RESULT (phi);
   access_fn = instantiate_parameters
     (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
-  if (!access_fn)
+  if (access_fn == chrec_dont_know)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
-		 "Unable to convert loop: Access function for induction variable phi is NULL\n");
+		 "Unable to convert loop: Access function for induction variable phi is unknown\n");
 
       return NULL;
     }
@@ -1402,19 +1417,19 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth,
     extra = -1 * stepint;
   else if (TREE_CODE (test) == GT_EXPR)
     extra = -1 * stepint;
-
-  ubound = gcc_tree_to_linear_expression (depth,
-					  uboundvar,
+  else if (TREE_CODE (test) == EQ_EXPR)
+    extra = 1 * stepint;
+  
+  ubound = gcc_tree_to_linear_expression (depth, uboundvar,
 					  outerinductionvars,
 					  *invariants, extra);
-  VEC_safe_push (tree, *uboundvars, build (PLUS_EXPR, integer_type_node,
-					uboundvar,
-					build_int_cst (integer_type_node, extra)));
+  uboundresult = build (PLUS_EXPR, TREE_TYPE (uboundvar), uboundvar,
+			build_int_cst (TREE_TYPE (uboundvar), extra));
+  VEC_safe_push (tree, *uboundvars, uboundresult);
   VEC_safe_push (tree, *lboundvars, lboundvar);
   VEC_safe_push (int, *steps, stepint);
   if (!ubound)
     {
-
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
 		 "Unable to convert loop: Cannot convert upper bound to linear expression\n");
@@ -1444,26 +1459,17 @@ find_induction_var_from_exit_cond (struct loop *loop)
   test = TREE_OPERAND (expr, 0);
   if (!COMPARISON_CLASS_P (test))
     return NULL_TREE;
-  /* 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:
-    case EQ_EXPR:
+
+  /* Find the side that is invariant in this loop. The ivar must be the other
+     side.  */
+  
+  if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 0)))
       ivarop = TREE_OPERAND (test, 1);
-      break;
-    default:
-      gcc_unreachable();
-    }
+  else if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 1)))
+      ivarop = TREE_OPERAND (test, 0);
+  else
+    return NULL_TREE;
+
   if (TREE_CODE (ivarop) != SSA_NAME)
     return NULL_TREE;
   return ivarop;
@@ -1488,25 +1494,14 @@ gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
   struct loop *temp;
   int depth = 0;
   size_t i;
-  VEC (lambda_loop) *loops;
-  VEC (tree) *uboundvars;
-  VEC (tree) *lboundvars;
-  VEC (int) *steps;
+  VEC (lambda_loop) *loops = NULL;
+  VEC (tree) *uboundvars = NULL;
+  VEC (tree) *lboundvars  = NULL;
+  VEC (int) *steps = NULL;
   lambda_loop newloop;
   tree inductionvar = NULL;
-
-  temp = loop_nest;
-  while (temp)
-    {
-      depth++;
-      temp = temp->inner;
-    }
-  loops = VEC_alloc (lambda_loop, 1);
-  *inductionvars = VEC_alloc (tree, 1);
-  *invariants = VEC_alloc (tree, 1);
-  lboundvars = VEC_alloc (tree, 1);
-  uboundvars = VEC_alloc (tree, 1);
-  steps = VEC_alloc (int, 1);
+  
+  depth = depth_of_nest (loop_nest);
   temp = loop_nest;
   while (temp)
     {
@@ -1520,13 +1515,19 @@ gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
       VEC_safe_push (lambda_loop, loops, newloop);
       temp = temp->inner;
     }
-  if (need_perfect_nest 
-      && !perfect_nestify (currloops, loop_nest, 
-			   lboundvars, uboundvars, steps, *inductionvars))
+  if (need_perfect_nest)
     {
-      if (dump_file)
-	fprintf (dump_file, "Not a perfect nest and couldn't convert to one.\n");    
-      return NULL;
+      if (!perfect_nestify (currloops, loop_nest, 
+			    lboundvars, uboundvars, steps, *inductionvars))
+	{
+	  if (dump_file)
+	    fprintf (dump_file, "Not a perfect loop nest and couldn't convert to one.\n");    
+	  return NULL;
+	}
+      else if (dump_file)
+	fprintf (dump_file, "Successfully converted loop nest to perfect loop nest.\n");
+
+      
     }
   ret = lambda_loopnest_new (depth, 2 * depth);
   for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++)
@@ -1536,22 +1537,26 @@ gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
 
 }
 
+
 /* Convert a lambda body vector LBV to a gcc tree, and return the new tree. 
    STMTS_TO_INSERT is a pointer to a tree where the statements we need to be
    inserted for us are stored.  INDUCTION_VARS is the array of induction
-   variables for the loop this LBV is from.  */
+   variables for the loop this LBV is from.  TYPE is the tree type to use for
+   the variables and trees involved.  */
 
 static tree
-lbv_to_gcc_expression (lambda_body_vector lbv,
-		       VEC (tree) *induction_vars, tree * stmts_to_insert)
+lbv_to_gcc_expression (lambda_body_vector lbv, 
+		       tree type, VEC (tree) *induction_vars, 
+		       tree * stmts_to_insert)
 {
   tree stmts, stmt, resvar, name;
+  tree iv;
   size_t i;
   tree_stmt_iterator tsi;
 
   /* Create a statement list and a linear expression temporary.  */
   stmts = alloc_stmt_list ();
-  resvar = create_tmp_var (integer_type_node, "lbvtmp");
+  resvar = create_tmp_var (type, "lbvtmp");
   add_referenced_tmp_var (resvar);
 
   /* Start at 0.  */
@@ -1561,41 +1566,45 @@ lbv_to_gcc_expression (lambda_body_vector lbv,
   tsi = tsi_last (stmts);
   tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
 
-  for (i = 0; i < VEC_length (tree ,induction_vars) ; i++)
+  for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
     {
       if (LBV_COEFFICIENTS (lbv)[i] != 0)
 	{
 	  tree newname;
-
+	  tree coeffmult;
+	  
 	  /* newname = coefficient * induction_variable */
+	  coeffmult = build_int_cst (type, LBV_COEFFICIENTS (lbv)[i]);
 	  stmt = build (MODIFY_EXPR, void_type_node, resvar,
-			fold (build (MULT_EXPR, integer_type_node,
-				     VEC_index (tree, induction_vars, i),
-				     build_int_cst (integer_type_node,
-						    LBV_COEFFICIENTS (lbv)[i]))));
+			fold (build (MULT_EXPR, type, iv, coeffmult)));
+
 	  newname = make_ssa_name (resvar, stmt);
 	  TREE_OPERAND (stmt, 0) = newname;
+	  fold_stmt (&stmt);
 	  tsi = tsi_last (stmts);
 	  tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+
 	  /* name = name + newname */
 	  stmt = build (MODIFY_EXPR, void_type_node, resvar,
-			build (PLUS_EXPR, integer_type_node, name, newname));
+			build (PLUS_EXPR, type, name, newname));
 	  name = make_ssa_name (resvar, stmt);
 	  TREE_OPERAND (stmt, 0) = name;
+	  fold_stmt (&stmt);
 	  tsi = tsi_last (stmts);
 	  tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+
 	}
     }
 
   /* Handle any denominator that occurs.  */
   if (LBV_DENOMINATOR (lbv) != 1)
     {
+      tree denominator = build_int_cst (type, LBV_DENOMINATOR (lbv));
       stmt = build (MODIFY_EXPR, void_type_node, resvar,
-		    build (CEIL_DIV_EXPR, integer_type_node,
-			   name, build_int_cst (integer_type_node,
-						LBV_DENOMINATOR (lbv))));
+		    build (CEIL_DIV_EXPR, type, name, denominator));
       name = make_ssa_name (resvar, stmt);
       TREE_OPERAND (stmt, 0) = name;
+      fold_stmt (&stmt);
       tsi = tsi_last (stmts);
       tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
     }
@@ -1608,6 +1617,7 @@ lbv_to_gcc_expression (lambda_body_vector lbv,
    Return the tree that represents the final value of the expression.
    LLE is the linear expression to convert.
    OFFSET is the linear offset to apply to the expression.
+   TYPE is the tree type to use for the variables and math. 
    INDUCTION_VARS is a vector of induction variables for the loops.
    INVARIANTS is a vector of the loop nest invariants.
    WRAP specifies what tree code to wrap the results in, if there is more than
@@ -1618,6 +1628,7 @@ lbv_to_gcc_expression (lambda_body_vector lbv,
 static tree
 lle_to_gcc_expression (lambda_linear_expression lle,
 		       lambda_linear_expression offset,
+		       tree type,
 		       VEC(tree) *induction_vars,
 		       VEC(tree) *invariants,
 		       enum tree_code wrap, tree * stmts_to_insert)
@@ -1625,14 +1636,14 @@ lle_to_gcc_expression (lambda_linear_expression lle,
   tree stmts, stmt, resvar, name;
   size_t i;
   tree_stmt_iterator tsi;
-  VEC(tree) *results;
+  tree iv, invar;
+  VEC(tree) *results = NULL;
 
   name = NULL_TREE;
   /* Create a statement list and a linear expression temporary.  */
   stmts = alloc_stmt_list ();
-  resvar = create_tmp_var (integer_type_node, "lletmp");
+  resvar = create_tmp_var (type, "lletmp");
   add_referenced_tmp_var (resvar);
-  results = VEC_alloc (tree, 1);
 
   /* Build up the linear expressions, and put the variable representing the
      result in the results array.  */
@@ -1642,13 +1653,14 @@ lle_to_gcc_expression (lambda_linear_expression lle,
       stmt = build (MODIFY_EXPR, void_type_node, resvar, integer_zero_node);
       name = make_ssa_name (resvar, stmt);
       TREE_OPERAND (stmt, 0) = name;
+      fold_stmt (&stmt);
       tsi = tsi_last (stmts);
       tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
 
       /* First do the induction variables.  
          at the end, name = name + all the induction variables added
          together.  */
-      for (i = 0; i < VEC_length (tree ,induction_vars); i++)
+      for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
 	{
 	  if (LLE_COEFFICIENTS (lle)[i] != 0)
 	    {
@@ -1663,26 +1675,25 @@ lle_to_gcc_expression (lambda_linear_expression lle,
 		}
 	      else
 		{
-		  coeff = build_int_cst (integer_type_node,
+		  coeff = build_int_cst (type,
 					 LLE_COEFFICIENTS (lle)[i]);
-		  mult = fold (build (MULT_EXPR, integer_type_node,
-				      VEC_index (tree, induction_vars, i),
-				      coeff));
+		  mult = fold (build (MULT_EXPR, type, iv, coeff));
 		}
 
 	      /* newname = mult */
 	      stmt = build (MODIFY_EXPR, void_type_node, resvar, mult);
 	      newname = make_ssa_name (resvar, stmt);
 	      TREE_OPERAND (stmt, 0) = newname;
+	      fold_stmt (&stmt);
 	      tsi = tsi_last (stmts);
 	      tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
 
 	      /* name = name + newname */
 	      stmt = build (MODIFY_EXPR, void_type_node, resvar,
-			    build (PLUS_EXPR, integer_type_node,
-				   name, newname));
+			    build (PLUS_EXPR, type, name, newname));
 	      name = make_ssa_name (resvar, stmt);
 	      TREE_OPERAND (stmt, 0) = name;
+	      fold_stmt (&stmt);
 	      tsi = tsi_last (stmts);
 	      tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
 	    }
@@ -1691,41 +1702,39 @@ lle_to_gcc_expression (lambda_linear_expression lle,
       /* Handle our invariants.
          At the end, we have name = name + result of adding all multiplied
          invariants.  */
-      for (i = 0; i < VEC_length (tree, invariants); i++)
+      for (i = 0; VEC_iterate (tree, invariants, i, invar); i++)
 	{
 	  if (LLE_INVARIANT_COEFFICIENTS (lle)[i] != 0)
 	    {
 	      tree newname;
 	      tree mult;
 	      tree coeff;
-
+	      int invcoeff = LLE_INVARIANT_COEFFICIENTS (lle)[i];
 	      /* mult = invariant * coefficient  */
-	      if (LLE_INVARIANT_COEFFICIENTS (lle)[i] == 1)
+	      if (invcoeff == 1)
 		{
-		  mult = VEC_index (tree, invariants, i);
+		  mult = invar;
 		}
 	      else
 		{
-		  coeff = build_int_cst (integer_type_node,
-					 LLE_INVARIANT_COEFFICIENTS (lle)[i]);
-		  mult = fold (build (MULT_EXPR, integer_type_node,
-				      VEC_index (tree, invariants, i),
-				      coeff));
+		  coeff = build_int_cst (type, invcoeff);
+		  mult = fold (build (MULT_EXPR, type, invar, coeff));
 		}
 
 	      /* newname = mult */
 	      stmt = build (MODIFY_EXPR, void_type_node, resvar, mult);
 	      newname = make_ssa_name (resvar, stmt);
 	      TREE_OPERAND (stmt, 0) = newname;
+	      fold_stmt (&stmt);
 	      tsi = tsi_last (stmts);
 	      tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
 
 	      /* name = name + newname */
 	      stmt = build (MODIFY_EXPR, void_type_node, resvar,
-			    build (PLUS_EXPR, integer_type_node,
-				   name, newname));
+			    build (PLUS_EXPR, type, name, newname));
 	      name = make_ssa_name (resvar, stmt);
 	      TREE_OPERAND (stmt, 0) = name;
+	      fold_stmt (&stmt);
 	      tsi = tsi_last (stmts);
 	      tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
 	    }
@@ -1736,11 +1745,11 @@ lle_to_gcc_expression (lambda_linear_expression lle,
       if (LLE_CONSTANT (lle) != 0)
 	{
 	  stmt = build (MODIFY_EXPR, void_type_node, resvar,
-			build (PLUS_EXPR, integer_type_node,
-			       name, build_int_cst (integer_type_node,
-						    LLE_CONSTANT (lle))));
+			build (PLUS_EXPR, type, name, 
+			       build_int_cst (type, LLE_CONSTANT (lle))));
 	  name = make_ssa_name (resvar, stmt);
 	  TREE_OPERAND (stmt, 0) = name;
+	  fold_stmt (&stmt);
 	  tsi = tsi_last (stmts);
 	  tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
 	}
@@ -1750,11 +1759,11 @@ lle_to_gcc_expression (lambda_linear_expression lle,
       if (LLE_CONSTANT (offset) != 0)
 	{
 	  stmt = build (MODIFY_EXPR, void_type_node, resvar,
-			build (PLUS_EXPR, integer_type_node,
-			       name, build_int_cst (integer_type_node,
-						    LLE_CONSTANT (offset))));
+			build (PLUS_EXPR, type, name, 
+			       build_int_cst (type, LLE_CONSTANT (offset))));
 	  name = make_ssa_name (resvar, stmt);
 	  TREE_OPERAND (stmt, 0) = name;
+	  fold_stmt (&stmt);
 	  tsi = tsi_last (stmts);
 	  tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
 	}
@@ -1764,14 +1773,12 @@ lle_to_gcc_expression (lambda_linear_expression lle,
 	{
 	  if (wrap == MAX_EXPR)
 	    stmt = build (MODIFY_EXPR, void_type_node, resvar,
-			  build (CEIL_DIV_EXPR, integer_type_node,
-				 name, build_int_cst (integer_type_node,
-						      LLE_DENOMINATOR (lle))));
+			  build (CEIL_DIV_EXPR, type, name, 
+				 build_int_cst (type, LLE_DENOMINATOR (lle))));
 	  else if (wrap == MIN_EXPR)
 	    stmt = build (MODIFY_EXPR, void_type_node, resvar,
-			  build (FLOOR_DIV_EXPR, integer_type_node,
-				 name, build_int_cst (integer_type_node,
-						      LLE_DENOMINATOR (lle))));
+			  build (FLOOR_DIV_EXPR, type, name, 
+				 build_int_cst (type, LLE_DENOMINATOR (lle))));
 	  else
 	    gcc_unreachable();
 
@@ -1794,7 +1801,7 @@ lle_to_gcc_expression (lambda_linear_expression lle,
       tree op1 = VEC_index (tree, results, 0);
       tree op2 = VEC_index (tree, results, 1);
       stmt = build (MODIFY_EXPR, void_type_node, resvar,
-		    build (wrap, integer_type_node, op1, op2));
+		    build (wrap, type, op1, op2));
       name = make_ssa_name (resvar, stmt);
       TREE_OPERAND (stmt, 0) = name;
       tsi = tsi_last (stmts);
@@ -1816,6 +1823,7 @@ lle_to_gcc_expression (lambda_linear_expression lle,
    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.  */
+
 void
 lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
 				 VEC(tree) *old_ivs,
@@ -1827,7 +1835,9 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
   struct loop *temp;
   size_t i = 0;
   size_t depth = 0;
-  VEC(tree) *new_ivs;
+  VEC(tree) *new_ivs = NULL;
+  tree oldiv;
+  
   block_stmt_iterator bsi;
 
   if (dump_file)
@@ -1836,13 +1846,7 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
       fprintf (dump_file, "Inverse of transformation matrix:\n");
       print_lambda_trans_matrix (dump_file, transform);
     }
-  temp = old_loopnest;
-  new_ivs = VEC_alloc (tree, 1);
-  while (temp)
-    {
-      temp = temp->inner;
-      depth++;
-    }
+  depth = depth_of_nest (old_loopnest);
   temp = old_loopnest;
 
   while (temp)
@@ -1853,9 +1857,14 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
       enum tree_code testtype;
       tree newupperbound, newlowerbound;
       lambda_linear_expression offset;
+      tree type;
+
+      oldiv = VEC_index (tree, old_ivs, i);
+      type = TREE_TYPE (oldiv);
+
       /* First, build the new induction variable temporary  */
 
-      ivvar = create_tmp_var (integer_type_node, "lnivtmp");
+      ivvar = create_tmp_var (type, "lnivtmp");
       add_referenced_tmp_var (ivvar);
 
       VEC_safe_push (tree, new_ivs, ivvar);
@@ -1865,14 +1874,15 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
       /* Linear offset is a bit tricky to handle.  Punt on the unhandled
          cases for now.  */
       offset = LL_LINEAR_OFFSET (newloop);
-
+      
       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),
 					     LL_LINEAR_OFFSET (newloop),
+					     type,
 					     new_ivs,
 					     invariants, MAX_EXPR, &stmts);
       bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
@@ -1881,6 +1891,7 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
          basic block of the exit condition */
       newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop),
 					     LL_LINEAR_OFFSET (newloop),
+					     type,
 					     new_ivs,
 					     invariants, MIN_EXPR, &stmts);
       exitcond = get_loop_exit_condition (temp);
@@ -1894,49 +1905,62 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
       bb = EDGE_PRED (temp->latch, 0)->src;
       bsi = bsi_last (bb);
       create_iv (newlowerbound,
-		 build_int_cst (integer_type_node, LL_STEP (newloop)),
+		 build_int_cst (type, LL_STEP (newloop)),
 		 ivvar, temp, &bsi, false, &ivvar,
 		 &ivvarinced);
 
       /* Replace the exit condition with the new upper bound
          comparison.  */
+      
       testtype = LL_STEP (newloop) >= 0 ? LE_EXPR : GE_EXPR;
+      
+      /* Since we don't know which cond_expr part currently points to each
+	 edge, check which one is invariant and make sure we reverse the
+	 comparison if we are trying to replace a <= 50 with 50 >= newiv.
+	 This ensures that we still canonicalize to <invariant> <test>
+	 <induction variable>.  */
+      if (!expr_invariant_in_loop_p (temp, TREE_OPERAND (exitcond, 0)))
+	testtype = swap_tree_comparison (testtype);
+	
       COND_EXPR_COND (exitcond) = build (testtype,
 					 boolean_type_node,
-					 ivvarinced, newupperbound);
+					 newupperbound, ivvarinced);
       modify_stmt (exitcond);
       VEC_replace (tree, new_ivs, i, ivvar);
 
       i++;
       temp = temp->inner;
     }
-  
+
   /* Rewrite uses of the old ivs so that they are now specified in terms of
      the new ivs.  */
-  temp = old_loopnest;
-  for (i = 0; i < VEC_length (tree, old_ivs); i++)
+
+  for (i = 0; VEC_iterate (tree, old_ivs, i, oldiv); i++)
     {
       int j;
-      tree oldiv = VEC_index (tree, old_ivs, i);
       dataflow_t imm = get_immediate_uses (SSA_NAME_DEF_STMT (oldiv));
       for (j = 0; j < num_immediate_uses (imm); j++)
 	{
 	  tree stmt = immediate_use (imm, j);
 	  use_operand_p use_p;
 	  ssa_op_iter iter;
+	  gcc_assert (TREE_CODE (stmt) != PHI_NODE);
 	  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
 	    {
 	      if (USE_FROM_PTR (use_p) == oldiv)
 		{
 		  tree newiv, stmts;
-		  lambda_body_vector lbv;
+		  lambda_body_vector lbv, newlbv;
 		  /* Compute the new expression for the induction
 		     variable.  */
 		  depth = VEC_length (tree, new_ivs);
 		  lbv = lambda_body_vector_new (depth);
 		  LBV_COEFFICIENTS (lbv)[i] = 1;
-		  lbv = lambda_body_vector_compute_new (transform, lbv);
-		  newiv = lbv_to_gcc_expression (lbv, new_ivs, &stmts);
+		  
+		  newlbv = lambda_body_vector_compute_new (transform, lbv);
+
+		  newiv = lbv_to_gcc_expression (newlbv, TREE_TYPE (oldiv),
+						 new_ivs, &stmts);
 		  bsi = bsi_for_stmt (stmt);
 		  /* Insert the statements to build that
 		     expression.  */
@@ -2048,6 +2072,8 @@ stmt_is_bumper_for_loop (struct loop *loop, tree stmt)
     }
   return false;
 }
+
+
 /* Return true if LOOP is a perfect loop nest.
    Perfect loop nests are those loop nests where all code occurs in the
    innermost loop body.
@@ -2250,14 +2276,12 @@ perfect_nestify (struct loops *loops,
   tree phi;
   tree uboundvar;
   tree stmt;
-  tree ivvar, ivvarinced;
-  VEC (tree) *phis;
+  tree oldivvar, ivvar, ivvarinced;
+  VEC (tree) *phis = NULL;
 
   if (!can_convert_to_perfect_nest (loop, loopivs))
     return false;
 
-  phis = VEC_alloc (tree, 1);
-  
   /* Create the new loop */
 
   olddest = loop->single_exit->dest;
@@ -2278,21 +2302,24 @@ perfect_nestify (struct loops *loops,
       mark_for_rewrite (PHI_RESULT (phi));
     }
   e = redirect_edge_and_branch (EDGE_SUCC (preheaderbb, 0), headerbb);
-  unmark_all_for_rewrite ();
-  bb_ann (olddest)->phi_nodes = NULL;
-  /* Add back the old exit phis.  */
+
+  /* Remove the exit phis from the old basic block.  */
+  while (phi_nodes (olddest) != NULL)
+    remove_phi_node (phi_nodes (olddest), NULL, olddest);
+
+  /* and add them to the new basic block.  */
   while (VEC_length (tree, phis) != 0)
     {
       tree def;
       tree phiname;
       def = VEC_pop (tree, phis);
-      phiname = VEC_pop (tree, phis);
-      
+      phiname = VEC_pop (tree, phis);      
       phi = create_phi_node (phiname, preheaderbb);
       add_phi_arg (&phi, def, EDGE_PRED (preheaderbb, 0));
-    } 
-      
+    }       
   flush_pending_stmts (e);
+  unmark_all_for_rewrite ();
+
   bodybb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
   latchbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
   make_edge (headerbb, bodybb, EDGE_FALLTHRU); 
@@ -2329,8 +2356,7 @@ perfect_nestify (struct loops *loops,
   add_referenced_tmp_var (ivvar);
   bsi = bsi_last (EDGE_PRED (newloop->latch, 0)->src);
   create_iv (VEC_index (tree, lbounds, 0),
-	     build_int_cst (integer_type_node, 
-			    VEC_index (int, steps, 0)),
+	     build_int_cst (integer_type_node, VEC_index (int, steps, 0)),
 	     ivvar, newloop, &bsi, false, &ivvar, &ivvarinced);	     
 
   /* Create the new upper bound.  This may be not just a variable, so we copy
@@ -2344,14 +2370,15 @@ perfect_nestify (struct loops *loops,
   uboundvar = make_ssa_name (uboundvar, stmt);
   TREE_OPERAND (stmt, 0) = uboundvar;
   bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
-  COND_EXPR_COND (exit_condition) = build (LE_EXPR, 
+  COND_EXPR_COND (exit_condition) = build (GE_EXPR, 
 					   boolean_type_node,
-					   ivvarinced, 
-					   uboundvar);
+					   uboundvar,
+					   ivvarinced);
 
   bbs = get_loop_body (loop); 
   /* Now replace the induction variable in the moved statements with the
      correct loop induction variable.  */
+  oldivvar = VEC_index (tree, loopivs, 0);
   for (i = 0; i < loop->num_nodes; i++)
     {
       block_stmt_iterator tobsi = bsi_last (bodybb);
@@ -2370,9 +2397,7 @@ perfect_nestify (struct loops *loops,
 		  bsi_next (&bsi);
 		  continue;
 		}
-	      replace_uses_of_x_with_y (stmt, 
-					VEC_index (tree, loopivs, 0),
-					ivvar);
+	      replace_uses_of_x_with_y (stmt, oldivvar, ivvar);
 	      bsi_move_before (&bsi, &tobsi);
 	    }
 	}
@@ -2425,9 +2450,7 @@ lambda_transform_legal_p (lambda_trans_matrix trans,
   for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
     {
       ddr = (struct data_dependence_relation *) 
-	VARRAY_GENERIC_PTR (dependence_relations, i);
-
-     
+	VARRAY_GENERIC_PTR (dependence_relations, i);     
 
       /* Don't care about relations for which we know that there is no
 	 dependence, nor about read-read (aka. output-dependences):
@@ -2435,9 +2458,15 @@ lambda_transform_legal_p (lambda_trans_matrix trans,
       if (DDR_ARE_DEPENDENT (ddr) == chrec_known
 	  || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
 	continue;
+
       /* Conservatively answer: "this transformation is not valid".  */
       if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 	return false;
+	  
+      /* If the dependence could not be captured by a distance vector,
+	 conservatively answer that the transform is not valid.  */
+      if (DDR_DIST_VECT (ddr) == NULL)
+	return false;
 
       /* Compute trans.dist_vect */
       lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops, 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-1.c
new file mode 100644
index 00000000000..bbeef87b61e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-1.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+double u[1782225];
+int foo(int N, int *res)
+{
+  int i, j;
+  double sum = 0.0;
+  /* This loop should be converted to a perfect nest and
+     interchanged. */
+  for (i = 0; i < N; i++)
+    {
+      for (j = 0; j < N; j++)
+	sum = sum + u[i + 1335 * j];
+      
+      u[1336 * i] *= 2;
+    }
+  *res = sum + N;
+}
+/* { dg-final { scan-tree-dump-times "converted loop nest to perfect
+   loop nest" 1 "ltrans"} } */ 
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */ 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-2.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-2.c
new file mode 100644
index 00000000000..7ab3e6c6897
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-2.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+double u[1782225];
+int foo(int N, int *res)
+{
+  unsigned int i, j;
+  double sum = 0;
+  
+  /* This loop should be converted to a perfect nest and
+     interchanged.  */
+  for (i = 0; i < N; i++)
+    {
+      for (j = 0; j < N; j++)
+	{
+	  sum = sum + u[i + 1335 * j];
+	  if (j == N - 1)
+	    u[1336 * i] *= 2;
+	}
+    }
+  *res = sum + N;
+}
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} {
+   xfail *-*-*} } */ 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-3.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-3.c
new file mode 100644
index 00000000000..81c347c7aa6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-3.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+double u[1782225];
+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;
+}
+
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */ 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-4.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-4.c
new file mode 100644
index 00000000000..5f43da17d23
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-4.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O20 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+double u[1782225];
+int foo(int N, int *res)
+{
+  int i, j;
+  double sum = 0;
+  for (i = 0; i < N; i++)	
+    for (j = 0; j < N; j++)
+      sum = sum + u[i + 1335 * j];
+  
+  for (i = 0; i < N; i++)
+    u[1336 * i] *= 2;
+  *res = sum + N;
+}
+
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */ 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-5.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-5.c
new file mode 100644
index 00000000000..43a20119d42
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-5.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+typedef struct rtx_
+{
+} *rtx;
+static rtx regno_save_mem[53][16 / 4 + 1];
+extern set_mem_alias_set (rtx, rtx);
+int main(void)
+{
+  int i, j;
+  for (i = 0; i < 53; i++)
+    for (j = (16 / (0 ? 8 : 4)); j > 0; j--)
+      if (regno_save_mem[i][j] != 0)
+        set_mem_alias_set (regno_save_mem[i][j], 0);
+}
+
+/* { dg-final { scan-tree-dump-times "Linear expression:  constant: 1   invariants:   denominator: 1" 1 "ltrans" } } */
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */ 
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index c34ae7fb5de..9a0126c3317 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1772,9 +1772,12 @@ subscript_dependence_tester (struct data_dependence_relation *ddr)
    DDR is the data dependence relation to build a vector from.
    NB_LOOPS is the total number of loops we are considering.
    FIRST_LOOP is the loop->num of the first loop in the analyzed 
-   loop nest.  */
+   loop nest.  
+   Return FALSE if the dependence relation is outside of the loop nest
+   starting with FIRST_LOOP. 
+   Return TRUE otherwise.  */
 
-static void
+static bool
 build_classic_dist_vector (struct data_dependence_relation *ddr, 
 			   int nb_loops, unsigned int first_loop)
 {
@@ -1787,7 +1790,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
   lambda_vector_clear (init_v, nb_loops);
   
   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
-    return;
+    return true;
   
   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
     {
@@ -1797,7 +1800,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	{
 	  non_affine_dependence_relation (ddr);
-	  return;
+	  return true;
 	}
 
       access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
@@ -1811,6 +1814,15 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
 	  int loop_nb_b = CHREC_VARIABLE (access_fn_b);
 	  struct loop *loop_a = current_loops->parray[loop_nb_a];
 	  struct loop *loop_b = current_loops->parray[loop_nb_b];
+	  struct loop *loop_first = current_loops->parray[first_loop];
+
+	  /* If the loops for both variables are at a lower depth than 
+	     the first_loop's depth, then they can't possibly have a
+	     dependency at this level of the loop.  */
+	     
+	  if (loop_a->depth < loop_first->depth
+	      && loop_b->depth < loop_first->depth)
+	    return false;
 
 	  if (loop_nb_a != loop_nb_b
 	      && !flow_loop_nested_p (loop_a, loop_b)
@@ -1828,7 +1840,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
 		 the dependence relation cannot be captured by the
 		 distance abstraction.  */
 	      non_affine_dependence_relation (ddr);
-	      return;
+	      return true;
 	    }
 
 	  /* The dependence is carried by the outermost loop.  Example:
@@ -1850,7 +1862,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
 	  if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	    {
 	      non_affine_dependence_relation (ddr);
-	      return;
+	      return true;
 	    }
 	  
 	  dist = int_cst_value (SUB_DISTANCE (subscript));
@@ -1865,7 +1877,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
 	      && dist_v[loop_nb] != dist)
 	    {
 	      finalize_ddr_dependent (ddr, chrec_known);
-	      return;
+	      return true;
 	    }
 
 	  dist_v[loop_nb] = dist;
@@ -1928,6 +1940,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
   
   DDR_DIST_VECT (ddr) = dist_v;
   DDR_SIZE_VECT (ddr) = nb_loops;
+  return true;
 }
 
 /* Compute the classic per loop direction vector.  
@@ -1935,9 +1948,12 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
    DDR is the data dependence relation to build a vector from.
    NB_LOOPS is the total number of loops we are considering.
    FIRST_LOOP is the loop->num of the first loop in the analyzed 
-   loop nest.  */
+   loop nest.
+   Return FALSE if the dependence relation is outside of the loop nest
+   starting with FIRST_LOOP. 
+   Return TRUE otherwise.  */
 
-static void
+static bool
 build_classic_dir_vector (struct data_dependence_relation *ddr, 
 			  int nb_loops, unsigned int first_loop)
 {
@@ -1950,7 +1966,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
   lambda_vector_clear (init_v, nb_loops);
   
   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
-    return;
+    return true;
   
   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
     {
@@ -1960,7 +1976,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	{
 	  non_affine_dependence_relation (ddr);
-	  return;
+	  return true;
 	}
 
       access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
@@ -1974,6 +1990,14 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
 	  int loop_nb_b = CHREC_VARIABLE (access_fn_b);
 	  struct loop *loop_a = current_loops->parray[loop_nb_a];
 	  struct loop *loop_b = current_loops->parray[loop_nb_b];
+	  struct loop *loop_first = current_loops->parray[first_loop];
+ 
+	  /* If the loops for both variables are at a lower depth than 
+	     the first_loop's depth, then they can't possibly matter */
+	     
+	  if (loop_a->depth < loop_first->depth
+	      && loop_b->depth < loop_first->depth)
+	    return false;
 
 	  if (loop_nb_a != loop_nb_b
 	      && !flow_loop_nested_p (loop_a, loop_b)
@@ -1991,7 +2015,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
 		 the dependence relation cannot be captured by the
 		 distance abstraction.  */
 	      non_affine_dependence_relation (ddr);
-	      return;
+	      return true;
 	    }
 
 	  /* The dependence is carried by the outermost loop.  Example:
@@ -2014,7 +2038,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
 	  if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	    {
 	      non_affine_dependence_relation (ddr);
-	      return;
+	      return true;
 	    }
 
 	  dist = int_cst_value (SUB_DISTANCE (subscript));
@@ -2038,7 +2062,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
 	      && (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
 	    {
 	      finalize_ddr_dependent (ddr, chrec_known);
-	      return;
+	      return true;
 	    }
 	  
 	  dir_v[loop_nb] = dir;
@@ -2099,6 +2123,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
   
   DDR_DIR_VECT (ddr) = dir_v;
   DDR_SIZE_VECT (ddr) = nb_loops;
+  return true;
 }
 
 /* Returns true when all the access functions of A are affine or
@@ -2195,10 +2220,8 @@ compute_all_dependences (varray_type datarefs,
    DATAREFS.  Returns chrec_dont_know when failing to analyze a
    difficult case, returns NULL_TREE otherwise.
    
-   FIXME: This is a "dumb" walker over all the trees in the loop body.
-   Find another technique that avoids this costly walk.  This is
-   acceptable for the moment, since this function is used only for
-   debugging purposes.  */
+   TODO: This function should be made smarter so that it can handle address
+   arithmetic as if they were array accesses, etc.  */
 
 tree 
 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
@@ -2226,7 +2249,7 @@ find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
 	      && !V_MUST_DEF_OPS (ann)
 	      && !V_MAY_DEF_OPS (ann))
 	    continue;
-
+	  
 	  /* In the GIMPLE representation, a modify expression
   	     contains a single load or store to memory.  */
 	  if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
@@ -2238,7 +2261,6 @@ find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
 	    VARRAY_PUSH_GENERIC_PTR 
 		    (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1), 
 					       true));
-
   	  else
 	    {
 	      if (dont_know_node_not_inserted)
@@ -2251,7 +2273,6 @@ find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
 		  DR_BASE_NAME (res) = NULL;
 		  DR_IS_READ (res) = false;
 		  VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
-
 		  dont_know_node_not_inserted = false;
 		}
 	    }
@@ -2286,6 +2307,7 @@ compute_data_dependences_for_loop (unsigned nb_loops,
 				   varray_type *dependence_relations)
 {
   unsigned int i;
+  varray_type allrelations;
 
   /* If one of the data references is not computable, give up without
      spending time to compute other dependences.  */
@@ -2302,14 +2324,18 @@ compute_data_dependences_for_loop (unsigned nb_loops,
       return;
     }
 
-  compute_all_dependences (*datarefs, dependence_relations);
+  VARRAY_GENERIC_PTR_INIT (allrelations, 1, "Data dependence relations");
+  compute_all_dependences (*datarefs, &allrelations);
 
-  for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++)
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (allrelations); i++)
     {
       struct data_dependence_relation *ddr;
-      ddr = VARRAY_GENERIC_PTR (*dependence_relations, i);
-      build_classic_dist_vector (ddr, nb_loops, loop->num);
-      build_classic_dir_vector (ddr, nb_loops, loop->num);    
+      ddr = VARRAY_GENERIC_PTR (allrelations, i);
+      if (build_classic_dist_vector (ddr, nb_loops, loop->num))
+	{
+	  VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
+	  build_classic_dir_vector (ddr, nb_loops, loop->num);
+	}
     }
 }
 
diff --git a/gcc/tree-loop-linear.c b/gcc/tree-loop-linear.c
index de16a1ecf92..07afe5dabb0 100644
--- a/gcc/tree-loop-linear.c
+++ b/gcc/tree-loop-linear.c
@@ -127,7 +127,6 @@ gather_interchange_stats (varray_type dependence_relations,
 	  (*dependence_steps) += 0;
 	  continue;
 	}
-
       dist = DDR_DIST_VECT (ddr)[loop_number];
       if (dist == 0)
 	(*nb_deps_not_carried_by_loop) += 1;
@@ -240,6 +239,7 @@ linear_transform_loops (struct loops *loops)
 {
   unsigned int i;
 
+  compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
   for (i = 1; i < loops->num; i++)
     {
       unsigned int depth = 0;
@@ -247,8 +247,8 @@ linear_transform_loops (struct loops *loops)
       varray_type dependence_relations;
       struct loop *loop_nest = loops->parray[i];
       struct loop *temp;
-      VEC (tree) *oldivs;
-      VEC (tree) *invariants;
+      VEC (tree) *oldivs = NULL;
+      VEC (tree) *invariants = NULL;
       lambda_loopnest before, after;
       lambda_trans_matrix trans;
       bool problem = false;
@@ -306,11 +306,11 @@ linear_transform_loops (struct loops *loops)
 		{
 		  fprintf (dump_file, "DISTANCE_V (");
 		  print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), 
-				       loops->num);
+				       DDR_SIZE_VECT (ddr));
 		  fprintf (dump_file, ")\n");
 		  fprintf (dump_file, "DIRECTION_V (");
 		  print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), 
-				       loops->num);
+				       DDR_SIZE_VECT (ddr));
 		  fprintf (dump_file, ")\n");
 		}
 	    }
@@ -319,6 +319,7 @@ linear_transform_loops (struct loops *loops)
       /* Build the transformation matrix.  */
       trans = lambda_trans_matrix_new (depth, depth);
       lambda_matrix_id (LTM_MATRIX (trans), depth);
+
       trans = try_interchange_loops (trans, depth, dependence_relations,
 				     datarefs, loop_nest->num);
 
@@ -359,11 +360,17 @@ linear_transform_loops (struct loops *loops)
 	}
       lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
 				       after, trans);
+      if (dump_file)
+	fprintf (dump_file, "Successfully transformed loop.\n");
       oldivs = NULL;
       invariants = NULL;
       free_dependence_relations (dependence_relations);
       free_data_refs (datarefs);
     }
-  rewrite_into_loop_closed_ssa ();
   free_df ();
+  scev_reset ();
+  rewrite_into_loop_closed_ssa ();
+#ifdef ENABLE_CHECKING
+  verify_loop_closed_ssa ();
+#endif
 }
diff --git a/gcc/tree-optimize.c b/gcc/tree-optimize.c
index e2eb8812fa5..7089c2705d8 100644
--- a/gcc/tree-optimize.c
+++ b/gcc/tree-optimize.c
@@ -392,11 +392,11 @@ init_tree_optimization_passes (void)
   NEXT_PASS (pass_loop_init);
   NEXT_PASS (pass_lim);
   NEXT_PASS (pass_unswitch);
-  NEXT_PASS (pass_iv_canon);
   NEXT_PASS (pass_record_bounds);
+  NEXT_PASS (pass_linear_transform);
+  NEXT_PASS (pass_iv_canon);
   NEXT_PASS (pass_if_conversion);
   NEXT_PASS (pass_vectorize);
-  NEXT_PASS (pass_linear_transform);
   NEXT_PASS (pass_complete_unroll);
   NEXT_PASS (pass_iv_optimize);
   NEXT_PASS (pass_loop_done);