Help understand the may_be_zero field in loop niter information

[Richard Biener]

On Thu, Jun 12, 2014 at 1:41 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> 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.
>
> 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?
>
> It seems that GCC deliberately skips boundary case.  It's ok in this
> case we can still get zero from niter info "bnd_4 - ivtmp_11" when
> "bnd_4 == 1" (i,e. len_3 == 0)
>
> 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".
>
> 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"?
>
> With these examples, my first feeling is that may_be_zero is computed
> wrongly, but searching code shows that may_be_zero is mostly used by
> ivopt.  Considering ivopt works well with it now, I am wondering if
> it's designed behavior?
>
> Anyone help?  Thanks very much.

IMHO may_be_zero should be fully correct, not only for the cases IVOPTs
cares.  Optimizations needing the value of niters may choose to apply
loop-versioning for the may_be_zero condition and doing that should
result in a valid niter value.

I think Zdenek may help here (but IIRC you already had a (partial?) patch
to fix this?)

Thanks,
Richard.

> Thanks,
> bin
> --
> Best Regards.