This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Scev analysing number of loop iterations returns (2^32-1) instead of -1


> On Wed, Oct 7, 2009 at 7:21 PM, Tobias Grosser
> <grosser@fim.uni-passau.de> wrote:
> > On Wed, 2009-10-07 at 18:30 +0200, Tobias Grosser wrote:
> >> On Wed, 2009-10-07 at 17:44 +0200, Richard Guenther wrote:
> >> > On Wed, Oct 7, 2009 at 5:35 PM, Tobias Grosser
> >> > <grosser@fim.uni-passau.de> wrote:
> >> > > On Wed, 2009-10-07 at 17:23 +0200, Richard Guenther wrote:
> >> > >> On Wed, Oct 7, 2009 at 5:16 PM, Tobias Grosser
> >> > >> <grosser@fim.uni-passau.de> wrote:
> >> > >> > On Wed, 2009-10-07 at 16:42 +0200, Richard Guenther wrote:
> >> > >> >> On Wed, Oct 7, 2009 at 4:37 PM, Tobias Grosser
> >> > >> >> <grosser@fim.uni-passau.de> wrote:
> >> > >> >> > I try to analyse this code:
> >> > >> >> > ------------------------------------------------------
> >> > >> >> > int foo (int N)
> >> > >> >> > {
> >> > >> >> > ?int ftab[257];
> >> > >> >> > ?int i, j;
> >> > >> >> >
> >> > >> >> > ?for (i = 0; i < N ?- 7488645; i++)
> >> > >> >> > ? ?j = ftab [i];
> >> > >> >> >
> >> > >> >> > ?return j;
> >> > >> >> > }
> >> > >> >> > ------------------------------------------------------
> >> > >> >> >
> >> > >> >> > The number of iterations I get is:
> >> > >> >> >
> >> > >> >> > (unsigned int) N_5(D) + 0x0ffffffff
> >> > >> >> >
> >> > >> >> > However I expect it to be
> >> > >> >> >
> >> > >> >> > (unsigned int) N_5(D) + (-1)
> >> > >> >>
> >> > >> >> No, that would be (unsigned int) (N_5(D) + -1) instead.
> >> > >> >>
> >> > >> >> It's fold that canonicalizes this to the above form - you
> >> > >> >> simply have to deal with it (unsigned arithmetic, that is).
> >> > >> >
> >> > >> > OK. So I need to understand this better.
> >> > >> >
> >> > >> > E.g:
> >> > >> >
> >> > >> > int foo (int N)
> >> > >> > {
> >> > >> > ?int ftab[257];
> >> > >> > ?int i, j;
> >> > >> >
> >> > >> > ?for (i = 0; i < N ?- 50; i++)
> >> > >> > ? ?j = ftab [i];
> >> > >> >
> >> > >> > ?return j;
> >> > >> > }
> >> > >> >
> >> > >> > Number of latch executions: (unsigned int) N_5(D) + 0x0ffffffcd
> >> > >> >
> >> > >> > What happens if N == 5? I would expect the number of latch iterations to
> >> > >> > be 0 as i < 5 - 50 is always false. However using the upper expression I
> >> > >> > get something like
> >> > >> > 5 + 0x0ffffffcd == 0x0ffffffd2
> >> > >> > what is a lot bigger than 0.
> >> > >>
> >> > >> It's undefined if N == 5 because the loop counter would overflow.
> >> > >
> >> > >
> >> > > Why?
> >> > >
> >> > > The loop
> >> > >
> >> > > for (i=0; i < 5 - 50; i++)
> >> > >
> >> > > is equivalent to
> >> > >
> >> > > for (i=0; i < -45; i++)
> >> > >
> >> > > Which just evaluates to false and will not be executed. How can the loop
> >> > > counter overflow?
> >> >
> >> > Ah, indeed. ?Sorry for being confused. ?Is tree-niter-desc->assumptions
> >> > or ->may_be_zero non-NULL?
> >>
> >> Yes both. I attached the gdb content for both.
> >
> > (gdb) call debug_generic_expr (ndesc.assumptions)
> > 1
> > (gdb) call debug_generic_expr (ndesc.may_be_zero)
> > 0
> > (gdb) call debug_tree (ndesc.assumptions)
> > ?<integer_cst 0x29605658 type <boolean_type 0x296145b0 _Bool> constant
> > 1>
> > (gdb) call debug_tree (ndesc.may_be_zero)
> > ?<integer_cst 0x29605620 type <boolean_type 0x296145b0 _Bool> constant
> > 0>
> >
> > So it seems the "niter" expression should contain the correct solution
> > for every N. The cases where "niter" is not valid are not fullfilled
> > following the description in tree-flow.h
> 
> Yes, I would think so.  Maybe Zdenek knows more.

this is because the header of the loop was copied; i.e., the code looks
like

if (N >= 50)
  {
    the loop
  }

so # of iterations analysis knows that N >= 50, and hence the number of
iterations is N-50,

Zdenek


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]