Help understand the may_be_zero field in loop niter information
Richard Biener
richard.guenther@gmail.com
Fri Jun 13 09:32:00 GMT 2014
On Fri, Jun 13, 2014 at 9:43 AM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Thu, Jun 12, 2014 at 7:59 PM, Zdenek Dvorak <rakdver@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.
Probably. It's only those corner cases that can be folded from the
generic range specifying unsigned compares.
Richard.
> Thanks,
> bin
>
> --
> Best Regards.
More information about the Gcc
mailing list