On Fri, Aug 30, 2013 at 6:43 PM, Bernd Edlinger <bernd.edlin...@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.edlin...@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.edlin...@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