On Thu, Jun 12, 2014 at 7:59 PM, Zdenek Dvorak <rakd...@iuuk.mff.cuni.cz> 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. > > 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
Hi Zdenek, I spent some more time pondering over this and I think I understand the (at least one) motivation why may_be_zero acts as it is now. At least for IVOPT, the boundary condition for which loop latch is not executed doesn't need to be handled specially when trying to eliminate condition iv uses. So, I am thinking if it's ok for me to send a documentation patch to describe how it works since it's a little bit confusing for me at the first glance. Thanks, bin -- Best Regards.
