2012-12-18 Richard Biener <rguenther@suse.de>

	PR tree-optimization/55555
	* tree-ssa-loop-niter.c (idx_infer_loop_bounds): Properly
	analyze evolution of the index for the loop it is used in.
	* tree-scalar-evolution.c (instantiate_scev_name): Take
	inner loop we will be creating a chrec for.  Generalize
	fix for PR40281 and prune invalid SCEVs.
	(instantiate_scev_poly): Likewise - pass down inner loop
	we will be creating a chrec for.
	(instantiate_scev_binary): Take and pass through inner loop.
	(instantiate_array_ref): Likewise.
	(instantiate_scev_convert): Likewise.
	(instantiate_scev_not): Likewise.
	(instantiate_scev_3): Likewise.
	(instantiate_scev_2): Likewise.
	(instantiate_scev_1): Likewise.
	(instantiate_scev_r): Likewise.
	(resolve_mixers): Adjust.
	(instantiate_scev): Likewise.

	* gcc.dg/torture/pr55555.c: New testcase.
	* gcc.dg/vect/vect-iv-11.c: Adjust.


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

1 files changed, 73 insertions, 51 deletions

diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index d19154265e3..9fc2f79ab89 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -2147,8 +2147,8 @@ loop_closed_phi_def (tree var)
   return NULL_TREE;
 }
 
-static tree instantiate_scev_r (basic_block, struct loop *, tree, bool,
-				htab_t, int);
+static tree instantiate_scev_r (basic_block, struct loop *, struct loop *,
+				tree, bool, htab_t, int);
 
 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    and EVOLUTION_LOOP, that were left under a symbolic form.
@@ -2166,7 +2166,8 @@ static tree instantiate_scev_r (basic_block, struct loop *, tree, bool,
 
 static tree
 instantiate_scev_name (basic_block instantiate_below,
-		       struct loop *evolution_loop, tree chrec,
+		       struct loop *evolution_loop, struct loop *inner_loop,
+		       tree chrec,
 		       bool fold_conversions, htab_t cache, int size_expr)
 {
   tree res;
@@ -2225,7 +2226,8 @@ instantiate_scev_name (basic_block instantiate_below,
 	  loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
 	  res = analyze_scalar_evolution (loop, chrec);
 	  res = compute_overall_effect_of_inner_loop (loop, res);
-	  res = instantiate_scev_r (instantiate_below, evolution_loop, res,
+	  res = instantiate_scev_r (instantiate_below, evolution_loop,
+				    inner_loop, res,
 				    fold_conversions, cache, size_expr);
 	}
       else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
@@ -2234,8 +2236,16 @@ instantiate_scev_name (basic_block instantiate_below,
     }
 
   else if (res != chrec_dont_know)
-    res = instantiate_scev_r (instantiate_below, evolution_loop, res,
-			      fold_conversions, cache, size_expr);
+    {
+      if (inner_loop
+	  && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
+	/* ???  We could try to compute the overall effect of the loop here.  */
+	res = chrec_dont_know;
+      else
+	res = instantiate_scev_r (instantiate_below, evolution_loop,
+				  inner_loop, res,
+				  fold_conversions, cache, size_expr);
+    }
 
   /* Store the correct value to the cache.  */
   set_instantiated_value (cache, instantiate_below, chrec, res);
@@ -2258,17 +2268,20 @@ instantiate_scev_name (basic_block instantiate_below,
 
 static tree
 instantiate_scev_poly (basic_block instantiate_below,
-		       struct loop *evolution_loop, tree chrec,
+		       struct loop *evolution_loop, struct loop *,
+		       tree chrec,
 		       bool fold_conversions, htab_t cache, int size_expr)
 {
   tree op1;
   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
+				 get_chrec_loop (chrec),
 				 CHREC_LEFT (chrec), fold_conversions, cache,
 				 size_expr);
   if (op0 == chrec_dont_know)
     return chrec_dont_know;
 
   op1 = instantiate_scev_r (instantiate_below, evolution_loop,
+			    get_chrec_loop (chrec),
 			    CHREC_RIGHT (chrec), fold_conversions, cache,
 			    size_expr);
   if (op1 == chrec_dont_know)
@@ -2277,19 +2290,8 @@ instantiate_scev_poly (basic_block instantiate_below,
   if (CHREC_LEFT (chrec) != op0
       || CHREC_RIGHT (chrec) != op1)
     {
-      unsigned var = CHREC_VARIABLE (chrec);
-
-      /* When the instantiated stride or base has an evolution in an
-	 innermost loop, return chrec_dont_know, as this is not a
-	 valid SCEV representation.  In the reduced testcase for
-	 PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no
-	 meaning.  */
-      if ((tree_is_chrec (op0) && CHREC_VARIABLE (op0) > var)
-	  || (tree_is_chrec (op1) && CHREC_VARIABLE (op1) > var))
-	return chrec_dont_know;
-
       op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
-      chrec = build_polynomial_chrec (var, op0, op1);
+      chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
     }
 
   return chrec;
@@ -2311,18 +2313,19 @@ instantiate_scev_poly (basic_block instantiate_below,
 
 static tree
 instantiate_scev_binary (basic_block instantiate_below,
-			 struct loop *evolution_loop, tree chrec, enum tree_code code,
+			 struct loop *evolution_loop, struct loop *inner_loop,
+			 tree chrec, enum tree_code code,
 			 tree type, tree c0, tree c1,
 			 bool fold_conversions, htab_t cache, int size_expr)
 {
   tree op1;
-  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
+  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
 				 c0, fold_conversions, cache,
 				 size_expr);
   if (op0 == chrec_dont_know)
     return chrec_dont_know;
 
-  op1 = instantiate_scev_r (instantiate_below, evolution_loop,
+  op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
 			    c1, fold_conversions, cache,
 			    size_expr);
   if (op1 == chrec_dont_know)
@@ -2370,12 +2373,14 @@ instantiate_scev_binary (basic_block instantiate_below,
 
 static tree
 instantiate_array_ref (basic_block instantiate_below,
-		       struct loop *evolution_loop, tree chrec,
+		       struct loop *evolution_loop, struct loop *inner_loop,
+		       tree chrec,
 		       bool fold_conversions, htab_t cache, int size_expr)
 {
   tree res;
   tree index = TREE_OPERAND (chrec, 1);
-  tree op1 = instantiate_scev_r (instantiate_below, evolution_loop, index,
+  tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
+				 inner_loop, index,
 				 fold_conversions, cache, size_expr);
 
   if (op1 == chrec_dont_know)
@@ -2406,11 +2411,13 @@ instantiate_array_ref (basic_block instantiate_below,
 
 static tree
 instantiate_scev_convert (basic_block instantiate_below,
-			  struct loop *evolution_loop, tree chrec,
+			  struct loop *evolution_loop, struct loop *inner_loop,
+			  tree chrec,
 			  tree type, tree op,
 			  bool fold_conversions, htab_t cache, int size_expr)
 {
-  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op,
+  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
+				 inner_loop, op,
 				 fold_conversions, cache, size_expr);
 
   if (op0 == chrec_dont_know)
@@ -2453,11 +2460,13 @@ instantiate_scev_convert (basic_block instantiate_below,
 
 static tree
 instantiate_scev_not (basic_block instantiate_below,
-		      struct loop *evolution_loop, tree chrec,
+		      struct loop *evolution_loop, struct loop *inner_loop,
+		      tree chrec,
 		      enum tree_code code, tree type, tree op,
 		      bool fold_conversions, htab_t cache, int size_expr)
 {
-  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op,
+  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
+				 inner_loop, op,
 				 fold_conversions, cache, size_expr);
 
   if (op0 == chrec_dont_know)
@@ -2501,24 +2510,25 @@ instantiate_scev_not (basic_block instantiate_below,
 
 static tree
 instantiate_scev_3 (basic_block instantiate_below,
-		    struct loop *evolution_loop, tree chrec,
+		    struct loop *evolution_loop, struct loop *inner_loop,
+		    tree chrec,
 		    bool fold_conversions, htab_t cache, int size_expr)
 {
   tree op1, op2;
   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
-				 TREE_OPERAND (chrec, 0),
+				 inner_loop, TREE_OPERAND (chrec, 0),
 				 fold_conversions, cache, size_expr);
   if (op0 == chrec_dont_know)
     return chrec_dont_know;
 
   op1 = instantiate_scev_r (instantiate_below, evolution_loop,
-			    TREE_OPERAND (chrec, 1),
+			    inner_loop, TREE_OPERAND (chrec, 1),
 			    fold_conversions, cache, size_expr);
   if (op1 == chrec_dont_know)
     return chrec_dont_know;
 
   op2 = instantiate_scev_r (instantiate_below, evolution_loop,
-			    TREE_OPERAND (chrec, 2),
+			    inner_loop, TREE_OPERAND (chrec, 2),
 			    fold_conversions, cache, size_expr);
   if (op2 == chrec_dont_know)
     return chrec_dont_know;
@@ -2548,18 +2558,19 @@ instantiate_scev_3 (basic_block instantiate_below,
 
 static tree
 instantiate_scev_2 (basic_block instantiate_below,
-		    struct loop *evolution_loop, tree chrec,
+		    struct loop *evolution_loop, struct loop *inner_loop,
+		    tree chrec,
 		    bool fold_conversions, htab_t cache, int size_expr)
 {
   tree op1;
   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
-				 TREE_OPERAND (chrec, 0),
+				 inner_loop, TREE_OPERAND (chrec, 0),
 				 fold_conversions, cache, size_expr);
   if (op0 == chrec_dont_know)
     return chrec_dont_know;
 
   op1 = instantiate_scev_r (instantiate_below, evolution_loop,
-			    TREE_OPERAND (chrec, 1),
+			    inner_loop, TREE_OPERAND (chrec, 1),
 			    fold_conversions, cache, size_expr);
   if (op1 == chrec_dont_know)
     return chrec_dont_know;
@@ -2587,11 +2598,12 @@ instantiate_scev_2 (basic_block instantiate_below,
 
 static tree
 instantiate_scev_1 (basic_block instantiate_below,
-		    struct loop *evolution_loop, tree chrec,
+		    struct loop *evolution_loop, struct loop *inner_loop,
+		    tree chrec,
 		    bool fold_conversions, htab_t cache, int size_expr)
 {
   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
-				 TREE_OPERAND (chrec, 0),
+				 inner_loop, TREE_OPERAND (chrec, 0),
 				 fold_conversions, cache, size_expr);
 
   if (op0 == chrec_dont_know)
@@ -2619,7 +2631,8 @@ instantiate_scev_1 (basic_block instantiate_below,
 
 static tree
 instantiate_scev_r (basic_block instantiate_below,
-		    struct loop *evolution_loop, tree chrec,
+		    struct loop *evolution_loop, struct loop *inner_loop,
+		    tree chrec,
 		    bool fold_conversions, htab_t cache, int size_expr)
 {
   /* Give up if the expression is larger than the MAX that we allow.  */
@@ -2634,31 +2647,36 @@ instantiate_scev_r (basic_block instantiate_below,
   switch (TREE_CODE (chrec))
     {
     case SSA_NAME:
-      return instantiate_scev_name (instantiate_below, evolution_loop, chrec,
+      return instantiate_scev_name (instantiate_below, evolution_loop,
+				    inner_loop, chrec,
 				    fold_conversions, cache, size_expr);
 
     case POLYNOMIAL_CHREC:
-      return instantiate_scev_poly (instantiate_below, evolution_loop, chrec,
+      return instantiate_scev_poly (instantiate_below, evolution_loop,
+				    inner_loop, chrec,
 				    fold_conversions, cache, size_expr);
 
     case POINTER_PLUS_EXPR:
     case PLUS_EXPR:
     case MINUS_EXPR:
     case MULT_EXPR:
-      return instantiate_scev_binary (instantiate_below, evolution_loop, chrec,
+      return instantiate_scev_binary (instantiate_below, evolution_loop,
+				      inner_loop, chrec,
 				      TREE_CODE (chrec), chrec_type (chrec),
 				      TREE_OPERAND (chrec, 0),
 				      TREE_OPERAND (chrec, 1),
 				      fold_conversions, cache, size_expr);
 
     CASE_CONVERT:
-      return instantiate_scev_convert (instantiate_below, evolution_loop, chrec,
+      return instantiate_scev_convert (instantiate_below, evolution_loop,
+				       inner_loop, chrec,
 				       TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
 				       fold_conversions, cache, size_expr);
 
     case NEGATE_EXPR:
     case BIT_NOT_EXPR:
-      return instantiate_scev_not (instantiate_below, evolution_loop, chrec,
+      return instantiate_scev_not (instantiate_below, evolution_loop,
+				   inner_loop, chrec,
 				   TREE_CODE (chrec), TREE_TYPE (chrec),
 				   TREE_OPERAND (chrec, 0),
 				   fold_conversions, cache, size_expr);
@@ -2671,7 +2689,8 @@ instantiate_scev_r (basic_block instantiate_below,
       return chrec_known;
 
     case ARRAY_REF:
-      return instantiate_array_ref (instantiate_below, evolution_loop, chrec,
+      return instantiate_array_ref (instantiate_below, evolution_loop,
+				    inner_loop, chrec,
 				    fold_conversions, cache, size_expr);
 
     default:
@@ -2684,15 +2703,18 @@ instantiate_scev_r (basic_block instantiate_below,
   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
     {
     case 3:
-      return instantiate_scev_3 (instantiate_below, evolution_loop, chrec,
+      return instantiate_scev_3 (instantiate_below, evolution_loop,
+				 inner_loop, chrec,
 				 fold_conversions, cache, size_expr);
 
     case 2:
-      return instantiate_scev_2 (instantiate_below, evolution_loop, chrec,
+      return instantiate_scev_2 (instantiate_below, evolution_loop,
+				 inner_loop, chrec,
 				 fold_conversions, cache, size_expr);
 
     case 1:
-      return instantiate_scev_1 (instantiate_below, evolution_loop, chrec,
+      return instantiate_scev_1 (instantiate_below, evolution_loop,
+				 inner_loop, chrec,
 				 fold_conversions, cache, size_expr);
 
     case 0:
@@ -2729,8 +2751,8 @@ instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
       fprintf (dump_file, ")\n");
     }
 
-  res = instantiate_scev_r (instantiate_below, evolution_loop, chrec, false,
-			    cache, 0);
+  res = instantiate_scev_r (instantiate_below, evolution_loop,
+			    NULL, chrec, false, cache, 0);
 
   if (dump_file && (dump_flags & TDF_SCEV))
     {
@@ -2753,8 +2775,8 @@ tree
 resolve_mixers (struct loop *loop, tree chrec)
 {
   htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
-  tree ret = instantiate_scev_r (block_before_loop (loop), loop, chrec, true,
-				 cache, 0);
+  tree ret = instantiate_scev_r (block_before_loop (loop), loop, NULL,
+				 chrec, true, cache, 0);
   htab_delete (cache);
   return ret;
 }