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.
Thanks, I realized that boundary condition is described by niter part
of information and it's more conveniently handled in this way for
consumer of may_be_zero like IVOPT. One problem is with below
example:
<bb 6>:
vectp_a.8_57 = &a;
vectp_b.11_61 = &b;
_67 = _1 * 4;
vectp_a.15_66 = &a + _67;
<bb 7>:
# vectp_a.7_58 = PHI <vectp_a.8_57(6), vectp_a.7_59(14)>
# vectp_b.10_62 = PHI <vectp_b.11_61(6), vectp_b.10_63(14)>
# vectp_a.14_68 = PHI <vectp_a.15_66(6), vectp_a.14_69(14)>
# ivtmp_9 = PHI <0(6), ivtmp_71(14)>
vect__6.9_60 = MEM[(float *)vectp_a.7_58];
vect__7.12_64 = MEM[(float *)vectp_b.10_62];
vect__8.13_65 = vect__6.9_60 + vect__7.12_64;
MEM[(float *)vectp_a.14_68] = vect__8.13_65;
vectp_a.7_59 = vectp_a.7_58 + 16;
vectp_b.10_63 = vectp_b.10_62 + 16;
vectp_a.14_69 = vectp_a.14_68 + 16;
ivtmp_71 = ivtmp_9 + 1;
if (ivtmp_71 < bnd.4_36)
goto <bb 14>;
else
goto <bb 9>;
<bb 14>:
goto <bb 7>;
After ivopt:
<bb 6>:
vectp_a.8_57 = &a;
vectp_b.11_61 = &b;
_67 = _1 * 4;
vectp_a.15_66 = &a + _67;
<bb 7>:
# ivtmp.24_26 = PHI <0(6), ivtmp.24_33(14)>
# ivtmp.27_88 = PHI <0(6), ivtmp.27_89(14)>
vect__6.9_60 = MEM[symbol: a, index: ivtmp.27_88, offset: 0B];
vect__7.12_64 = MEM[symbol: b, index: ivtmp.27_88, offset: 0B];
vect__8.13_65 = vect__6.9_60 + vect__7.12_64;
MEM[base: vectp_a.15_66, index: ivtmp.27_88, offset: 0B] = vect__8.13_65;
ivtmp.24_33 = ivtmp.24_26 + 1;
ivtmp.27_89 = ivtmp.27_88 + 16;
if (ivtmp.24_33 < bnd.4_36)
goto <bb 14>;
else
goto <bb 9>;
<bb 14>:
goto <bb 7>;
Ideally, "(ivtmp.24_33 < bnd.4_36)" should be eliminated by using
"ivtmp.27_89". One blocker is may_be_zero information like below:
Analyzing # of iterations of loop 1
exit condition [1, + , 1] < _38 + 1
bounds on difference of bases: -1 ... 4294967294
result:
zero if _38 == 4294967295
# of iterations _38, bounded by 4294967294
number of iterations _38; zero if _38 == 4294967295
"_38 == 4294967295" is folded from "_38 + 1 < 1", only the folded form
can't be handled by iv_elimination_compare_lt.
It seems I should investigate how to extend iv_elimination_compare_lt
to handle more general may_be_zero information.
Thanks,
bin
--
Best Regards.
