This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Scev analysing number of loop iterations returns (2^32-1) instead of -1
- From: Tobias Grosser <grosser at fim dot uni-passau dot de>
- To: Richard Guenther <richard dot guenther at gmail dot com>
- Cc: gcc at gcc dot gnu dot org, graphite <gcc-graphite at googlegroups dot com>, Sebastian Pop <sebpop at gmail dot com>
- Date: Wed, 07 Oct 2009 19:21:04 +0200
- Subject: Re: Scev analysing number of loop iterations returns (2^32-1) instead of -1
- References: <1254926239.52806.22.camel@tobilaptop> <16634_1254926527_4ACCA8BE_16634_56_1_84fc9c000910070742k26bf6418l58fc3b873744ff63@mail.gmail.com> <1254928609.52806.28.camel@tobilaptop> <18713_1254929018_4ACCB27A_18713_21_1_84fc9c000910070823s65e65626y3964cd0726ea1a39@mail.gmail.com> <1254929718.52806.31.camel@tobilaptop> <20033_1254930256_4ACCB750_20033_7_1_84fc9c000910070844u278ab3a5obebada6e96c5efee@mail.gmail.com> <20031_1254933041_4ACCC22F_20031_60_1_1254933015.52806.32.camel@tobilaptop>
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
Tobias