Re: [PATCH] PR58143/58227 wrong code at -O3

[Richard Biener <richard dot guenther at gmail dot com>]

On Fri, Aug 30, 2013 at 6:43 PM, Bernd Edlinger
<bernd.edlinger@hotmail.de> wrote:
> On Thu, 29 Aug 2013 11:54:22, Richard Biener wrote:
>> On Wed, Aug 28, 2013 at 11:24 PM, Bernd Edlinger
>> <bernd.edlinger@hotmail.de> wrote:
>>> The lim pass (aka loop invariant motion) can move conditional expressions with
>>> possible undefined behavior out of the if statement inside a loop which may cause the
>>> loop optimization to silently generate wrong code as PR tree-optimization/58143 and
>>> PR tree-optimization/58227 demonstrate.
>>>
>>> This patch prevents lim from moving code that might cause undefined behavior.
>>>
>>> This triggered a minor regression in gcc.target/i386/pr53397-1.c:
>>> Here lim used to move the expression "2*step" out of the loop, but this may cause
>>> undefined behavior on case of overflow, I propose to resolve this by adding
>>> -fno-strict-overflow. The test case looks pretty constructed anyway.
>>>
>>> The patch was boot-strapped and regression tested on i686-pc-linux-gnu and
>>> X86_64-linux-gnu
>>>
>>> OK for trunk?
>>
>> 2013-08-28 Bernd Edlinger <bernd.edlinger@hotmail.de>
>>
>> PR tree-optimization/58143
>> PR tree-optimization/58227
>> Prevent lim from moving conditional expressions
>> if that could trigger undefined behavior.
>> * gimple.h (gimple_could_trap_p_2): New function.
>> * gimple.c (gimple_could_trap_p_2): New function.
>> (gimple_could_trap_p_1): Call gimple_could_trap_p_2.
>> * tree-ssa-loop-im.c (movement_possibility): Likewise.
>>
>> Please fold the overall comment into the movement_possibility changelog.
>>
>
> done.
>
>> Can you instead of introducing gimple_could_trap_p_2 simply change the
>> signature and name of gimple_could_trap_p_1 please? It is only called
>> three times.
>> A proper name could be gimple_could_trap_or_invoke_undefined_p.
>>
>
> done.
>
>> That you need to change the two testcases makes me nervous (also please
>> use -fwrapv, not -fno-strict-overflow) - did you check what happens for them?
>>
>
> Yes, I looked at that again.  That is an interesting story.
> Initially the function looks like:
>
> for (a = 1; a < step; a++) {
>    for (b = 0; b <n; b += 2 * step) {
>
> when the lim pass is invoked that looks like:
>
> if (step> 1 && n> 0) {
>   for (a = 1; a < step; a++) {
>     pretmp = step * 2;
>     for (b = 0; b < n; b += pretmp) {
>
> Well "step*2" was initially at loop level 2, but now I see, it is actually at loop level 1.
>
> When lim does not move this out of the loop the test case fails.
> But if lim moves this statement out of the loop despite the possible undefined
> behavior, the test case passes.
>
> Now I think this is good opportunity for a simple heuristic:
>
> If a statement is at loop level 1 we can move it out of the loop,
> regardless of the fact, that it may invoke undefined behavior, because if it is
> moved then out of any loops, and thus it cannot be an induction variable and
> cause problems with aggressive loop optimizations later.

VRP can still cause wrong-code issues (it's probably hard to generate a
testcase though).  Also a less conservative check would be to see
whether we hoist _into_ loop level 0 (though we cannot check that at
the point where you placed the check).

> Only statements with possible undefined behavior in nested loops can become
> induction variable if lim moves them from one loop into an outer loop.
>
> Therefore with extremely much luck the test case will pass unmodified.
> I tried it, and the patch passes bootstrap and causes zero regressions
> with this heuristic.
>
> Ok for trunk now?

Jakub mentioned another possibility - make sure the moved expression
does not invoke undefined behavior by computing in an unsigned type.

That said, for the sake of backporting we need a patch as simple as
possible - so it would be interesting to see whether the patch without
the loop 1 heuristic has any effect on say SPEC CPU 2006 performance.

Thanks,
Richard.

> Thanks
> Bernd.
>
>> Thanks,
>> Richard.
>>
>>
>>
>>> Regards
>>> Bernd Edlinger