On Thu, Jun 12, 2014 at 1:41 PM, Bin.Cheng <amker.ch...@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.
