Re: [PATCH PR66388]Compute use with cand of smaller precision by further exercising scev overflow info.

["Bin.Cheng" <amker dot cheng at gmail dot com>]

On Fri, Jul 24, 2015 at 7:23 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Fri, Jul 24, 2015 at 1:09 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>> On Thu, Jul 23, 2015 at 10:06 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Fri, Jul 17, 2015 at 8:27 AM, Bin Cheng <bin.cheng@arm.com> wrote:
>>>> Hi,
>>>> This patch is to fix PR66388.  It's an old issue but recently became worse
>>>> after my scev overflow change.  IVOPT now can only compute iv use with
>>>> candidate which has at least same type precision.  See below code:
>>>>
>>>>   if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
>>>>     {
>>>>       /* We do not have a precision to express the values of use.  */
>>>>       return infinite_cost;
>>>>     }
>>>>
>>>> This is not always true.  It's possible to compute with a candidate of
>>>> smaller precision if it has enough stepping periods to express the iv use.
>>>> Just as code in iv_elimination.  Well, since now we have iv no_overflow
>>>> information, we can use that to prove it's safe.  Actually I am thinking
>>>> about improving iv elimination with overflow information too.  So this patch
>>>> relaxes the constraint to allow computation of uses with smaller precision
>>>> candidates.
>>>>
>>>> Benchmark data shows several cases in spec2k6 are obviously improved on
>>>> aarch64:
>>>> 400.perlbench                2.32%
>>>> 445.gobmk                    0.86%
>>>> 456.hmmer                    11.72%
>>>> 464.h264ref                  1.93%
>>>> 473.astar                    0.75%
>>>> 433.milc                     -1.49%
>>>> 436.cactusADM                6.61%
>>>> 444.namd                     -0.76%
>>>>
>>>> I looked into assembly code of 456.hmmer&436.cactusADM, and can confirm hot
>>>> loops are reduced.  Also perf data could confirm the improvement in
>>>> 456.hmmer.
>>>> I looked into 433.milc and found most hot functions are not affected by this
>>>> patch.  But I do observe two kinds of regressions described as below:
>>>> A)  For some loops, auto-increment addressing mode is generated before this
>>>> patch, but "base + index<<scale" is generated after. I don't worry about
>>>> this too much because auto-increment support in IVO hasn't been enabled on
>>>> AArch64 yet. On the contrary, we should worry that auto-increment support is
>>>> too aggressive in IVO, resulting in auto-increment addressing mode generated
>>>> where it shouldn't. I suspect the regression we monitored before is caused
>>>> by such kind of reason.
>>>> B) This patch enables computation of 64 bits address iv use with 32 bits biv
>>>> candidate.  So there will be a sign extension before the candidate can be
>>>> used in memory reference as an index. I already increased the cost by 2 for
>>>> such biv candidates but there still be some peculiar cases... Decreasing
>>>> cost in determine_iv_cost for biv candidates makes this worse.  It does that
>>>> to make debugging simpler, nothing to do with performance.
>>>>
>>>> Bootstrap and test on x86_64.  It fixes failure of pr49781-1.c.
>>>> Unfortunately, it introduces new failure of
>>>> g++.dg/debug/dwarf2/deallocator.C.  I looked into the test and found with
>>>> this patch, the loop is transformed into a shape that can be later
>>>> eliminated(because it can be proved never loop back?).  We can further
>>>> discuss if it's this patch's problem or the case should be tuned.
>>>> Also bootstrap and test on aarch64.
>>>>
>>>> So what's your opinion?
>>>
>>> Looks sensible, but the deallocator.C fail looks odd.  I presume that
>>> i + j is simplified in a way that either the first or the second iteration
>>> must exit the loop via the return and thus the scan for deallocator.C:34
>>> fails?  How does this happen - I can only see this happen if we unroll
>>> the loop and then run into VRP.  So does IVOPTs now affect non-loop
>>> code as well?  Ah, at the moment we use an IV that runs backward.
>>>
>>> Still curious if this isn't a wrong-code issue...
>>>
>>
>> Tree dump just before ivopts is as below:
>> {
>>   struct t test;
>>   struct t test;
>>   int j;
>>   struct t test_outside;
>>   unsigned int ivtmp_1;
>>   int _11;
>>   unsigned int ivtmp_26;
>>
>>   <bb 2>:
>>   t::t (&test_outside);
>>   # DEBUG j => 0
>>   # DEBUG j => 0
>>
>>   <bb 3>:
>>   # j_27 = PHI <j_14(6), 0(2)>
>>   # ivtmp_1 = PHI <ivtmp_26(6), 10(2)>
>>   # DEBUG j => j_27
>>   t::t (&test);
>>   t::foo (&test);
>>   _11 = i_10(D) + j_27;
>>   if (_11 != 0)
>>     goto <bb 4>;
>>   else
>>     goto <bb 5>;
>>
>>   <bb 4>:
>>   t::bar (&test);
>>   t::~t (&test);
>>   test ={v} {CLOBBER};
>>   goto <bb 12>;
>>
>>   <bb 5>:
>>   t::~t (&test);
>>   test ={v} {CLOBBER};
>>   j_14 = j_27 + 1;
>>   # DEBUG j => j_14
>>   # DEBUG j => j_14
>>   ivtmp_26 = ivtmp_1 - 1;
>>   if (ivtmp_26 == 0)
>>     goto <bb 7>;
>>   else
>>     goto <bb 6>;
>>
>>   <bb 6>:
>>   goto <bb 3>;
>>
>>   <bb 7>:
>>   if (i_10(D) != 0)
>>     goto <bb 8>;
>>   else
>>     goto <bb 11>;
>>
>>   <bb 8>:
>>   t::t (&test);
>>   if (i_10(D) == 10)
>>     goto <bb 9>;
>>   else
>>     goto <bb 10>;
>>
>>   <bb 9>:
>>   t::bar (&test);
>>
>>   <bb 10>:
>>   t::~t (&test);
>>   test ={v} {CLOBBER};
>>
>>   <bb 11>:
>>   t::foo (&test_outside);
>>
>>   <bb 12>:
>>   t::~t (&test_outside);
>>   test_outside ={v} {CLOBBER};
>>   return;
>>
>> }
>>
>> The only difference the patch made, is candidate 8 is not converted
>> into unsigned type any more because _11 is now considered not
>> overflow.
>>
>> Before patch:
>> candidate 8
>>   var_before ivtmp.9
>>   var_after ivtmp.9
>>   incremented before exit test
>>   type unsigned int
>>   base (unsigned int) i_10(D)
>>   step 1
>> After patch:
>> candidate 8
>>   var_before ivtmp.9
>>   var_after ivtmp.9
>>   incremented before exit test
>>   type int
>>   base i_10(D)
>>   step 1
>>   iv doesn't overflow wrto loop niter
>>
>> Mark {i_10(D), 1}_loop not overflow seems reasonable.  But I am not
>> sure because use 0 is before candidate stepping, thus we can't assume
>> it will not overflow at use 1?
>>
>> After IVO, the code is transformed into:
>> {
>>   int ivtmp.9;
>>   struct t test;
>>   struct t test;
>>   int j;
>>   struct t test_outside;
>>   unsigned int _29;
>>   unsigned int _30;
>>   int _31;
>>
>>   <bb 2>:
>>   t::t (&test_outside);
>>   # DEBUG j => 0
>>   # DEBUG j => 0
>>   _29 = (unsigned int) i_10(D);
>>   _30 = _29 + 10;
>
> From lookign at the source:
>
>   for (int j = 0; j < 10; j++)
>     {
>       t test;
>       test.foo();
>       if (i + j)
>         {
>           test.bar();
>           return;
>         }
>     }
>
> we know that i + 9 does not overflow but we don't know
> that i + 10 does not overflow.   Compute of _31 is done
> in unsigned, so that's ok.
>
>>   _31 = (int) _30;
>>
>>   <bb 3>:
>>   # ivtmp.9_25 = PHI <ivtmp.9_2(6), i_10(D)(2)>
>>   # DEBUG j => (int) ((unsigned int) ivtmp.9_25 - (unsigned int) i_10(D))
>>   t::t (&test);
>>   t::foo (&test);
>>   if (ivtmp.9_25 != 0)
>>     goto <bb 4>;
>>   else
>>     goto <bb 5>;
>>
>>   <bb 4>:
>>   t::bar (&test);
>>   t::~t (&test);
>>   test ={v} {CLOBBER};
>>   goto <bb 12>;
>>
>>   <bb 5>:
>>   t::~t (&test);
>>   test ={v} {CLOBBER};
>>   # DEBUG D#1 => (int) (((unsigned int) ivtmp.9_25 - (unsigned int)
>> i_10(D)) + 1)
>>   # DEBUG j => D#1
>>   # DEBUG j => D#1
>>   ivtmp.9_2 = ivtmp.9_25 + 1;
>
> But here we actually perform i_10 + 10 in the last iteration which might
> overflow and thus this stmt generated by IVO possibly invokes undefined behavior
> in the last iteration.
>
> Yes, we later figure out we at most iterate twice but I suppose
> behavior would be
> the same if we'd change the loop to
>
>   for (int j = 0; j < 10; j++)
>     {
>       t test;
>       test.foo();
>       if (i + j)
>         {
>           test.bar();
>         }
>     }
>
> so in the end the transform looks wrong to me (using 'int' for the IV and not
> 'unsigned int').  We could write the exit test as ivtmp.9_2 > _31 and compute
> _31 as i_10 + 9 to fix that for example.
Right.
The no overflow information is computed with respect to loop niter.
The patch lacks change in iv elimination that makes sure the
elimination happens within niter too.  The check is unnecessary before
because every candidate is computed in unsigned type.  I need to make
sure no overflow information is only used within niter range when
rewriting uses.  So far seems iv elimination is the only case that may
compute iv one step more than loop niter.

Thanks,
bin
>
> Richard.
>