Re: [PATCH] Fix PR55555

[Richard Biener <rguenther@suse.de>]

On Mon, 17 Dec 2012, Richard Biener wrote:

> 
> The following patch fixes a miscompilation due to bogus loop iteration
> bound derived from array accesses in an inner loop.  idx_infer_loop_bounds
> analyzes the evoultion of an SSA name with respect to a loop it is not
> defined in - which seems to lead to random weird behavior.  The correct
> thing to do (as documented) is to analyze the evolution with respect
> to the loop the stmt we are interested in is in.
> 
> Bootstrap and regtest ongoing on x86_64-unknown-linux-gnu.

Which shows that the very old fix for PR40281 isn't complete
(the patch regresses PR55687 again).  So the following extends
that fix.  I wonder whether we instead want to pass down
CHREC_VARIABLE and avoid doing the instantiation in the first
place ...

Bootstrap and regtest ongoing on x86_64-unknown-linux-gnu.

Comments welcome.

Thanks,
Richard.

2012-12-17  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_poly): Generalize
	fix for PR40281 and prune invalid SCEVs.

	* gcc.dg/torture/pr55555.c: New testcase.

Index: gcc/tree-ssa-loop-niter.c
===================================================================
*** gcc/tree-ssa-loop-niter.c	(revision 194552)
--- gcc/tree-ssa-loop-niter.c	(working copy)
*************** idx_infer_loop_bounds (tree base, tree *
*** 2671,2677 ****
        upper = false;
      }
  
!   ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
    init = initial_condition (ev);
    step = evolution_part_in_loop_num (ev, loop->num);
  
--- 2671,2682 ----
        upper = false;
      }
  
!   struct loop *dloop = loop_containing_stmt (data->stmt);
!   if (!dloop)
!     return true;
! 
!   ev = analyze_scalar_evolution (dloop, *idx);
!   ev = instantiate_parameters (loop, ev);
    init = initial_condition (ev);
    step = evolution_part_in_loop_num (ev, loop->num);
  
Index: gcc/tree-scalar-evolution.c
===================================================================
*** gcc/tree-scalar-evolution.c	(revision 194552)
--- gcc/tree-scalar-evolution.c	(working copy)
*************** instantiate_scev_poly (basic_block insta
*** 2268,2295 ****
    if (op0 == chrec_dont_know)
      return chrec_dont_know;
  
    op1 = instantiate_scev_r (instantiate_below, evolution_loop,
  			    CHREC_RIGHT (chrec), fold_conversions, cache,
  			    size_expr);
    if (op1 == chrec_dont_know)
      return chrec_dont_know;
  
!   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);
      }
  
    return chrec;
--- 2268,2322 ----
    if (op0 == chrec_dont_know)
      return chrec_dont_know;
  
+   /* 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_does_not_contain_chrecs (op0))
+     ;
+   else
+     {
+       tree tem = op0;
+       while (TREE_CODE (tem) != POLYNOMIAL_CHREC)
+ 	{
+ 	  if (CONVERT_EXPR_P (tem))
+ 	    tem = TREE_OPERAND (tem, 0);
+ 	  else
+ 	    return chrec_dont_know;
+ 	}
+       if (!flow_loop_nested_p (get_chrec_loop (tem), get_chrec_loop (chrec)))
+ 	return chrec_dont_know;
+     }
+ 
    op1 = instantiate_scev_r (instantiate_below, evolution_loop,
  			    CHREC_RIGHT (chrec), fold_conversions, cache,
  			    size_expr);
    if (op1 == chrec_dont_know)
      return chrec_dont_know;
  
!   /* See above.  */
!   if (tree_does_not_contain_chrecs (op1))
!     ;
!   else
      {
!       tree tem = op1;
!       while (TREE_CODE (tem) != POLYNOMIAL_CHREC)
! 	{
! 	  if (CONVERT_EXPR_P (tem))
! 	    tem = TREE_OPERAND (tem, 0);
! 	  else
! 	    return chrec_dont_know;
! 	}
!       if (!flow_loop_nested_p (get_chrec_loop (tem), get_chrec_loop (chrec)))
  	return chrec_dont_know;
+     }
  
+   if (CHREC_LEFT (chrec) != op0
+       || CHREC_RIGHT (chrec) != op1)
+     {
        op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
!       chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
      }
  
    return chrec;
Index: gcc/testsuite/gcc.dg/torture/pr55555.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr55555.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/pr55555.c	(working copy)
***************
*** 0 ****
--- 1,34 ----
+ /* { dg-do run } */
+ 
+ double s[4] = { 1.0, 2.0, 3.0, 4.0 }, pol_x[2] = { 5.0, 6.0 };
+ 
+ __attribute__((noinline)) int
+ foo (void)
+ {
+   double coef_x[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
+   int lxp = 0;
+   if (lxp <= 1)
+     do
+       {
+ 	double t = pol_x[lxp];
+ 	long S;
+ 	long l = lxp * 4L - 1;
+ 	for (S = 1; S <= 4; S++)
+ 	  coef_x[S + l] = coef_x[S + l] + s[S - 1] * t;
+       }
+     while (lxp++ != 1);
+   asm volatile ("" : : "r" (coef_x) : "memory");
+   for (lxp = 0; lxp < 8; lxp++)
+     if (coef_x[lxp] != ((lxp & 3) + 1) * (5.0 + (lxp >= 4)))
+       __builtin_abort ();
+   return 1;
+ }
+ 
+ int
+ main ()
+ {
+   asm volatile ("" : : : "memory");
+   if (!foo ())
+     __builtin_abort ();
+   return 0;
+ }