This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Help understand the may_be_zero field in loop niter information


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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]