Invalid optimization in the presence of shift instructions?

[ccadar]

Bugzilla Link	34133
Version	trunk
OS	Linux
CC	@delcypher,@efriedma-quic,@RKSimon,@nunoplopes,@regehr,@sanjoy,@rotateright

Extended Description

Consider the program below:

$ cat shift.c int a = 0; int foo(int x) { return (a < 2) || (a >> x) ; }

int main() { return foo(100); }

$ clang -O1 -emit-llvm -c shift.c $ llvm-dis shift.bc $ cat shift.ll ... define i32 @​foo(i32) local_unnamed_addr #​0 { %2 = load i32, i32* @​a, align 4, !tbaa !​1 %3 = icmp slt i32 %2, 2 %4 = ashr i32 %2, %0 %5 = icmp ne i32 %4, 0 %6 = or i1 %3, %5 %7 = zext i1 %6 to i32 ret i32 %7 } ... define i32 @​main() local_unnamed_addr #​0 { %1 = tail call i32 @​foo(i32 100) ret i32 %1 } ...

Note that in the C code, the || operator has short-circuiting behaviour, so "a >> x" should not be evaluated since the first clause is true. However, the optimization generates code that always executes the corresponding ashr instruction, which has undefined behaviour in this case, as the shift amount is 100. So is this optimization valid?

We discovered this while working with KLEE, which generates an overshift error when the code is compiled with -O1, but not with -O0, so we'd like to understand whether KLEE's behaviour is correct here. Note that UBSan does not complain here, as its instrumentation disables the optimization.

Thank you, Cristian

[nunoplopes]

There's at least llvm/llvm-project#21371 It's the same problem.

[delcypher]

Yes, there's a known bug here. See http://lists.llvm.org/pipermail/llvm-dev/2017-May/113272.html .

@​Eli : Is there a bug on bugzilla tracking this?

Just to note the sequence of optimization passes for this example is

sroa, early-cse, simplifycfg, instcombine

Without the instcombine the IR contains a select instruction which is what is discussed in mailing list post linked to.

You can see this by running something like this

clang -O0 -S -emit-llvm -o - shift.c  | opt -S -print-after-all
-print-before-all -filter-print-funcs=foo -sroa -early-cse
-simplifycfg -instcombine 2>&1 > /dev/null
| less

[efriedma-quic]

Yes, there's a known bug here. See http://lists.llvm.org/pipermail/llvm-dev/2017-May/113272.html .