Re: doloop-opt deficiency

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> 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.

note the extra negation in loop-iv.c.  I think the fix is OK.

Zdenek

> > 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