Re: doloop-opt deficiency

[Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>]

Dale Johannesen wrote:
> I think this is a simple pasto; this code was evidently copied from
> the previous block:
> 

I don't think that this was a simple pasto.  The code looks correct.
We have the same code in tree-ssa-loop-niter.c around line 436, since
we inherited this code from the rtl-level.

> Index: loop-iv.c
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/loop-iv.c,v
> retrieving revision 2.35
> diff -u -b -c -p -r2.35 loop-iv.c
> cvs diff: conflicting specifications of output style
> *** loop-iv.c	21 Jul 2005 07:24:07 -0000	2.35
> --- loop-iv.c	29 Aug 2005 23:34:12 -0000
> *************** iv_number_of_iterations (struct loop *lo
> *** 2417,2423 ****
>   	  tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
>   	  tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
>   
> ! 	  bound = simplify_gen_binary (MINUS, mode, mode_mmin,
>   				       lowpart_subreg (mode, step, comp_mode));
>   	  if (step_is_pow2)
>   	    {
> --- 2417,2423 ----
>   	  tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
>   	  tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
>   
> ! 	  bound = simplify_gen_binary (PLUS, mode, mode_mmin,
>   				       lowpart_subreg (mode, step, comp_mode));
>   	  if (step_is_pow2)
>   	    {


I don't think this fix is correct: 'bound' is used to test whether an
overflow has occured, and in the following code that uses 'bound', it
is expected to overflow for the example that you have provided:

	      /* If s is power of 2, we know that the loop is infinite if
		 a % s <= b % s and a - s overflows.  */
	      assumption = simplify_gen_relational (reverse_condition (cond),
						    SImode, mode,
						    bound, tmp0);

> 
> 
> The code as it was computed -2147483648-256 which overflows.

this is the right behavior.

> We noticed that the simple loop here

> extern int a[];
> int foo(int w) {
>   int n = w;
>   while (n >= 512)
>     {
>     a[n] = 42;
>     n -= 256;
>     }
>   }

> 
> 
> was being treated as ineligible for the doloop modification. 

The problem in this example is that the initial value of the induction
variable is not known: it is a parameter 'w'.  Consequently we have
not enough information to determine how many times it wraps, nor for
estimating the number of iterations, if you're using the -fwrapv
semantics.  

I'm not sure whether at rtl level we have this distinction of
wrapping/non wrapping operations, but from the code that I've read,
everything wraps (probably Roger Sayle knows more about the wrapping
behavior that is expected at rtl level).  Having said this, we have to
adjust the code at the tree level such that it catches this case
(conditionally on signed iv and !fwrapv).

sebastian