Help understand the may_be_zero field in loop niter information

[Zdenek Dvorak]

Hi,

> > I noticed there is below code/comments about may_be_zero field in loop
> > niter desc:
> >
> >   tree may_be_zero;    /* The boolean expression.  If it evaluates to true,
> >                the loop will exit in the first iteration (i.e.
> >                its latch will not be executed), even if the niter
> >                field says otherwise.  */
> >
> > I had difficulty in understanding this because I ran into some cases
> > in which it didn't behave as said.

actually, in all the examples below, the field behaves as described,
i.e.,

the number of iterations = may_be_zero ? 0 : niter;

In particular, the fact that may_be_zero is false *does not imply*
that the number of iterations as described by niter is non-zero.

> > Example1, the dump of loop before sccp is like:
> >
> >   <bb 2>:
> >   bnd_4 = len_3(D) + 1;
> >
> >   <bb 3>:
> >   # ivtmp_1 = PHI <0(2), ivtmp_11(4)>
> >   _6 = ivtmp_1 + len_3(D);
> >   _7 = a[ivtmp_1];
> >   _8 = b[ivtmp_1];
> >   _9 = _7 + _8;
> >   a[_6] = _9;
> >   ivtmp_11 = ivtmp_1 + 1;
> >   if (bnd_4 > ivtmp_11)
> >     goto <bb 4>;
> >   else
> >     goto <bb 5>;
> >
> >   <bb 4>:
> >   goto <bb 3>;
> >
> > The loop niter information analyzed in sccp is like:
> >
> > Analyzing # of iterations of loop 1
> >   exit condition [1, + , 1] < len_3(D) + 1
> >   bounds on difference of bases: -1 ... 4294967294
> >   result:
> >     zero if len_3(D) == 4294967295
> >     # of iterations len_3(D), bounded by 4294967294
> >
> > Qeustion1, shouldn't it be like "len_3 +1 <= 1" because the latch
> > won't be executed when "len_3 == 0", right?

the analysis determines the number of iterations as len_3, that is
0 if len_3 == 0.  So, the information is computed correctly here.

> > But when boundary condition is the only case that latch get ZERO
> > executed, the may_be_zero info will not be computed.  See example2,
> > with dump of loop before sccp like:
> >
> > foo (int M)
> >
> >   <bb 2>:
> >   if (M_4(D) > 0)
> >     goto <bb 4>;
> >   else
> >     goto <bb 3>;
> >
> >   <bb 3>:
> >   return;
> >
> >   <bb 4>:
> >
> >   <bb 5>:
> >   # i_13 = PHI <0(4), i_10(6)>
> >   _5 = i_13 + M_4(D);
> >   _6 = a[i_13];
> >   _7 = b[i_13];
> >   _8 = _6 + _7;
> >   a[_5] = _8;
> >   i_10 = i_13 + 1;
> >   if (M_4(D) > i_10)
> >     goto <bb 6>;
> >   else
> >     goto <bb 3>;
> >
> >   <bb 6>:
> >   goto <bb 5>;
> >
> > The niter information analyzed in sccp is like:
> >
> > Analyzing # of iterations of loop 1
> >   exit condition [1, + , 1](no_overflow) < M_4(D)
> >   bounds on difference of bases: 0 ... 2147483646
> >   result:
> >     # of iterations (unsigned int) M_4(D) + 4294967295, bounded by 2147483646
> >
> > So may_be_zero is always false here, but the latch may be ZERO
> > executed when "M_4 == 1".

Again, this is correct, since then ((unsigned int) M_4) + 4294967295 == 0.

> > Start from Example1, we can create Example3 which makes no sense to
> > me.  Again, the dump of loop is like:
> >
> >   <bb 2>:
> >   bnd_4 = len_3(D) + 1;
> >
> >   <bb 3>:
> >   # ivtmp_1 = PHI <0(2), ivtmp_11(4)>
> >   _6 = ivtmp_1 + len_3(D);
> >   _7 = a[ivtmp_1];
> >   _8 = b[ivtmp_1];
> >   _9 = _7 + _8;
> >   a[_6] = _9;
> >   ivtmp_11 = ivtmp_1 + 4;
> >   if (bnd_4 > ivtmp_11)
> >     goto <bb 4>;
> >   else
> >     goto <bb 5>;
> >
> >   <bb 4>:
> >   goto <bb 3>;
> >
> >   <bb 5>:
> >   return 0;
> >
> > The niter info is like:
> >
> > Analyzing # of iterations of loop 1
> >   exit condition [4, + , 4] < len_3(D) + 1
> >   bounds on difference of bases: -4 ... 4294967291
> >   result:
> >     under assumptions len_3(D) + 1 <= 4294967292
> >     zero if len_3(D) == 4294967295
> >     # of iterations len_3(D) / 4, bounded by 1073741823
> >
> > The problem is: won't latch be ZERO executed when "len_3 == 0/1/2/3"?

Again, in all these cases the number of iterations is len_3 / 4 == 0.

Zdenek