PR middle-end/20256

	PR middle-end/26435
	* tree-loop-linear.c (linear_transform_loops): Don't test perfect_nest_p.
	Call rewrite_into_loop_closed_ssa only when something changed.
	* lambda.h (gcc_loopnest_to_lambda_loopnest): Update declaration.
	* lambda-code.c (can_convert_to_perfect_nest): Declared.
	(gcc_loopnest_to_lambda_loopnest): Removed need_perfect_nest parameter.
	Test for perfect_nest_p here.  Fix formating.
	(replace_uses_equiv_to_x_with_y): Fix formating.
	(stmt_uses_op): Removed.
	(can_convert_to_perfect_nest): Removed loopivs parameter.
	Complete the test by checking the scalar dependences.
	(perfect_nestify): Remove the test for can_convert_to_perfect_nest.
	Fix formating.



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

1 files changed, 97 insertions, 63 deletions

diff --git a/gcc/lambda-code.c b/gcc/lambda-code.c
index 3a28ee30c9d..60f1be209ce 100644
--- a/gcc/lambda-code.c
+++ b/gcc/lambda-code.c
@@ -147,6 +147,7 @@ static lambda_lattice lambda_lattice_new (int, int);
 static lambda_lattice lambda_lattice_compute_base (lambda_loopnest);
 
 static tree find_induction_var_from_exit_cond (struct loop *);
+static bool can_convert_to_perfect_nest (struct loop *);
 
 /* Create a new lambda body vector.  */
 
@@ -1457,14 +1458,13 @@ DEF_VEC_ALLOC_P(lambda_loop,heap);
 
 lambda_loopnest
 gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
-				 struct loop * loop_nest,
+				 struct loop *loop_nest,
 				 VEC(tree,heap) **inductionvars,
-				 VEC(tree,heap) **invariants,
-				 bool need_perfect_nest)
+				 VEC(tree,heap) **invariants)
 {
   lambda_loopnest ret = NULL;
-  struct loop *temp;
-  int depth = 0;
+  struct loop *temp = loop_nest;
+  int depth = depth_of_nest (loop_nest);
   size_t i;
   VEC(lambda_loop,heap) *loops = NULL;
   VEC(tree,heap) *uboundvars = NULL;
@@ -1472,9 +1472,11 @@ gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
   VEC(int,heap) *steps = NULL;
   lambda_loop newloop;
   tree inductionvar = NULL;
-  
-  depth = depth_of_nest (loop_nest);
-  temp = loop_nest;
+  bool perfect_nest = perfect_nest_p (loop_nest);
+
+  if (!perfect_nest && !can_convert_to_perfect_nest (loop_nest))
+    goto fail;
+
   while (temp)
     {
       newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
@@ -1482,12 +1484,14 @@ gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
 					 &lboundvars, &uboundvars,
 					 &steps);
       if (!newloop)
-	return NULL;
+	goto fail;
+
       VEC_safe_push (tree, heap, *inductionvars, inductionvar);
       VEC_safe_push (lambda_loop, heap, loops, newloop);
       temp = temp->inner;
     }
-  if (need_perfect_nest)
+
+  if (!perfect_nest)
     {
       if (!perfect_nestify (currloops, loop_nest, 
 			    lboundvars, uboundvars, steps, *inductionvars))
@@ -1501,9 +1505,12 @@ gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
 	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++)
     LN_LOOPS (ret)[i] = newloop;
+
  fail:
   VEC_free (lambda_loop, heap, loops);
   VEC_free (tree, heap, uboundvars);
@@ -2110,13 +2117,12 @@ replace_uses_equiv_to_x_with_y (struct loop *loop, tree stmt, tree x,
     {
       tree use = USE_FROM_PTR (use_p);
       tree step = NULL_TREE;
-      tree access_fn = NULL_TREE;
-      
-      
-      access_fn = instantiate_parameters
-	(loop, analyze_scalar_evolution (loop, use));
-      if (access_fn != NULL_TREE && access_fn != chrec_dont_know)
-	step = evolution_part_in_loop_num (access_fn, loop->num);
+      tree scev = instantiate_parameters (loop,
+					  analyze_scalar_evolution (loop, use));
+
+      if (scev != NULL_TREE && scev != chrec_dont_know)
+	step = evolution_part_in_loop_num (scev, loop->num);
+
       if ((step && step != chrec_dont_know 
 	   && TREE_CODE (step) == INTEGER_CST
 	   && int_cst_value (step) == xstep)
@@ -2125,22 +2131,6 @@ replace_uses_equiv_to_x_with_y (struct loop *loop, tree stmt, tree x,
     }
 }
 
-/* Return TRUE if STMT uses tree OP in it's uses.  */
-
-static bool
-stmt_uses_op (tree stmt, tree op)
-{
-  ssa_op_iter iter;
-  tree use;
-
-  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
-    {
-      if (use == op)
-	return true;
-    }
-  return false;
-}
-
 /* Return true if STMT is an exit PHI for LOOP */
 
 static bool
@@ -2210,14 +2200,12 @@ can_put_after_inner_loop (struct loop *loop, tree stmt)
 
 
 
-/* Return TRUE if LOOP is an imperfect nest that we can convert to a perfect
-   one.  LOOPIVS is a vector of induction variables, one per loop.  
-   ATM, we only handle imperfect nests of depth 2, where all of the statements
-   occur after the inner loop.  */
+/* Return TRUE if LOOP is an imperfect nest that we can convert to a
+   perfect one.  At the moment, we only handle imperfect nests of
+   depth 2, where all of the statements occur after the inner loop.  */
 
 static bool
-can_convert_to_perfect_nest (struct loop *loop,
-			     VEC(tree,heap) *loopivs)
+can_convert_to_perfect_nest (struct loop *loop)
 {
   basic_block *bbs;
   tree exit_condition, phi;
@@ -2237,19 +2225,13 @@ can_convert_to_perfect_nest (struct loop *loop,
 	{
 	  for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
 	    { 
-	      size_t j;
 	      tree stmt = bsi_stmt (bsi);
-	      tree iv;
-	      
+
 	      if (stmt == exit_condition
 		  || not_interesting_stmt (stmt)
 		  || stmt_is_bumper_for_loop (loop, stmt))
 		continue;
-	      /* If the statement uses inner loop ivs, we == screwed.  */
-	      for (j = 1; VEC_iterate (tree, loopivs, j, iv); j++)
-		if (stmt_uses_op (stmt, iv))
-		  goto fail;
-	      
+
 	      /* If this is a scalar operation that can be put back
 	         into the inner loop, or after the inner loop, through
 		 copying, then do so. This works on the theory that
@@ -2258,10 +2240,65 @@ can_convert_to_perfect_nest (struct loop *loop,
 		 win we get from rearranging the memory walk
 		 the loop is doing so that it has better
 		 cache behavior.  */
-	      if (TREE_CODE (stmt) == MODIFY_EXPR
-		  && (can_put_in_inner_loop (loop->inner, stmt)
-		      || can_put_after_inner_loop (loop, stmt)))
-		continue;
+	      if (TREE_CODE (stmt) == MODIFY_EXPR)
+		{
+		  use_operand_p use_a, use_b;
+		  imm_use_iterator imm_iter;
+		  ssa_op_iter op_iter, op_iter1;
+		  tree op0 = TREE_OPERAND (stmt, 0);
+		  tree scev = instantiate_parameters
+		    (loop, analyze_scalar_evolution (loop, op0));
+
+		  /* If the IV is simple, it can be duplicated.  */
+		  if (!automatically_generated_chrec_p (scev))
+		    {
+		      tree step = evolution_part_in_loop_num (scev, loop->num);
+		      if (step && step != chrec_dont_know 
+			  && TREE_CODE (step) == INTEGER_CST)
+			continue;
+		    }
+
+		  /* The statement should not define a variable used
+		     in the inner loop.  */
+		  if (TREE_CODE (op0) == SSA_NAME)
+		    FOR_EACH_IMM_USE_FAST (use_a, imm_iter, op0)
+		      if (bb_for_stmt (USE_STMT (use_a))->loop_father
+			  == loop->inner)
+			goto fail;
+
+		  FOR_EACH_SSA_USE_OPERAND (use_a, stmt, op_iter, SSA_OP_USE)
+		    {
+		      tree node, op = USE_FROM_PTR (use_a);
+
+		      /* The variables should not be used in both loops.  */
+		      FOR_EACH_IMM_USE_FAST (use_b, imm_iter, op)
+		      if (bb_for_stmt (USE_STMT (use_b))->loop_father
+			  == loop->inner)
+			goto fail;
+
+		      /* The statement should not use the value of a
+			 scalar that was modified in the loop.  */
+		      node = SSA_NAME_DEF_STMT (op);
+		      if (TREE_CODE (node) == PHI_NODE)
+			FOR_EACH_PHI_ARG (use_b, node, op_iter1, SSA_OP_USE)
+			  {
+			    tree arg = USE_FROM_PTR (use_b);
+
+			    if (TREE_CODE (arg) == SSA_NAME)
+			      {
+				tree arg_stmt = SSA_NAME_DEF_STMT (arg);
+
+				if (bb_for_stmt (arg_stmt)->loop_father
+				    == loop->inner)
+				  goto fail;
+			      }
+			  }
+		    }
+
+		  if (can_put_in_inner_loop (loop->inner, stmt)
+		      || can_put_after_inner_loop (loop, stmt))
+		    continue;
+		}
 
 	      /* Otherwise, if the bb of a statement we care about isn't
 		 dominated by the header of the inner loop, then we can't
@@ -2351,14 +2388,10 @@ perfect_nestify (struct loops *loops,
   tree stmt;
   tree oldivvar, ivvar, ivvarinced;
   VEC(tree,heap) *phis = NULL;
-
-  if (!can_convert_to_perfect_nest (loop, loopivs))
-    return false;
-
-  /* Create the new loop */
-
+  
+  /* Create the new loop.  */
   olddest = loop->single_exit->dest;
-  preheaderbb =  loop_split_edge_with (loop->single_exit, NULL);
+  preheaderbb = loop_split_edge_with (loop->single_exit, NULL);
   headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
   
   /* Push the exit phi nodes that we are moving.  */
@@ -2490,7 +2523,7 @@ perfect_nestify (struct loops *loops,
 		    }
 		  
 		  /* Make copies of this statement to put it back next
-		     to its uses. */
+		     to its uses.  */
 		  FOR_EACH_IMM_USE_STMT (imm_stmt, imm_iter, 
 					 TREE_OPERAND (stmt, 0))
 		    {
@@ -2506,8 +2539,10 @@ perfect_nestify (struct loops *loops,
 			  newname = SSA_NAME_VAR (newname);
 			  newname = make_ssa_name (newname, newstmt);
 			  TREE_OPERAND (newstmt, 0) = newname;
+
 			  FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
 			    SET_USE (use_p, newname);
+
 			  bsi_insert_before (&tobsi, newstmt, BSI_SAME_STMT);
 			  update_stmt (newstmt);
 			  update_stmt (imm_stmt);
@@ -2535,10 +2570,9 @@ perfect_nestify (struct loops *loops,
 		      continue;
 		    }
 		  
-		  replace_uses_equiv_to_x_with_y (loop, stmt, 
-						  oldivvar,  
-						  VEC_index (int, steps, 0),
-						  ivvar);
+		  replace_uses_equiv_to_x_with_y 
+		    (loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar);
+
 		  bsi_move_before (&bsi, &tobsi);
 		  
 		  /* If the statement has any virtual operands, they may