The C program below does not execute any undefined behaviors. However, the LLVM code executes an undefined operation in the "sub nsw" which poisons the rest of the computation. regehr@regehr-M51AC:souper-bug1$ cat small.c int printf(const char *, ...); int x0 = 4294967295, x1; int main() { x1 = x0 > 0 && 1 > 2147483647 - x0 || 1 + x0; if (x1) printf("x"); return 0; } regehr@regehr-M51AC:souper-bug1$ clang -O2 -w small.c -S -o - -emit-llvm ; ModuleID = 'small.c' target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @x0 = global i32 -1, align 4 @x1 = common global i32 0, align 4 ; Function Attrs: nounwind uwtable define i32 @main() #0 { entry: %0 = load i32* @x0, align 4, !tbaa !1 %cmp = icmp sgt i32 %0, 0 %sub = sub nsw i32 2147483647, %0 %cmp1 = icmp slt i32 %sub, 1 %or.cond = and i1 %cmp, %cmp1 br i1 %or.cond, label %lor.end.thread, label %lor.end lor.end.thread: ; preds = %entry store i32 1, i32* @x1, align 4, !tbaa !1 br label %if.then lor.end: ; preds = %entry %tobool = icmp ne i32 %0, -1 %lor.ext = zext i1 %tobool to i32 store i32 %lor.ext, i32* @x1, align 4, !tbaa !1 br i1 %tobool, label %if.then, label %if.end if.then: ; preds = %lor.end.thread, %lor.end %putchar = tail call i32 @putchar(i32 120) #1 br label %if.end if.end: ; preds = %if.then, %lor.end ret i32 0 } ; Function Attrs: nounwind declare i32 @putchar(i32) #1 attributes #0 = { nounwind uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" } attributes #1 = { nounwind } !llvm.ident = !{!0} !0 = metadata !{metadata !"clang version 3.6.0 (217983)"} !1 = metadata !{metadata !2, metadata !2, i64 0} !2 = metadata !{metadata !"int", metadata !3, i64 0} !3 = metadata !{metadata !"omnipotent char", metadata !4, i64 0} !4 = metadata !{metadata !"Simple C/C++ TBAA"} regehr@regehr-M51AC:souper-bug1$ clang -v clang version 3.6.0 (217983) Target: x86_64-unknown-linux-gnu Thread model: posix Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/4.8 Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/4.8.2 Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/4.9 Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/4.9.1 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.4 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.4.7 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.7 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.7.3 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8.2 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9.1 Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8 Candidate multilib: .;@m64 Candidate multilib: 32;@m32 Candidate multilib: x32;@mx32 Selected multilib: .;@m64 regehr@regehr-M51AC:souper-bug1$
This bug is caused by simplifycfg, arguably because `isSafeToSpeculativelyExecute` assumes all add/sub operations are safe to speculate. We should examine if the binary operator has uses in it's basic block first.
This raises an interesting question: is it better to drop the nsw and speculate, or to keep it and not speculate?
Or maybe not so interesting, seems pretty clear that the cost of a branch exceeds the expected value of an nsw.
Here is an example where we are in a bit of a pickle: define i32 @main(i32 %x0, i1 %cmp, i1 %cmp1) { entry: %sub = sub nsw i32 2147483647, %x0 br i1 %cmp, label %land.lhs.true, label %lor.rhs land.lhs.true: ; preds = %entry br i1 %cmp1, label %lor.end, label %lor.rhs lor.rhs: ; preds = %land.lhs.true, %entry br label %lor.end lor.end: ; preds = %lor.rhs, %land.lhs.true %phi = phi i32 [ %sub, %land.lhs.true ], [ 0, %lor.rhs ] ret i32 %phi } Note there is nothing left to hoist, just branches to fold away. Since phi poison-ness depends on *which* label it came from, %phi is poison free. However after running simplifycfg: define i32 @main(i32 %x0, i1 %cmp, i1 %cmp1) { entry: %sub = sub nsw i32 2147483647, %x0 %cmp.not = xor i1 %cmp, true %cmp1.not = xor i1 %cmp1, true %brmerge = or i1 %cmp.not, %cmp1.not %phi = select i1 %brmerge, i32 0, i32 %sub ret i32 %phi } Did we just make it possible to introduce poison into the select instruction? select's semantics are not clear at all here.
Related bug 20895 and bug 21412 which also deal with poison. Note that in 21412, we've stopped optimizing hoisting of integer divs because we can't trace poison to its root cause.
References back to the dev list discussions regarding poison and nsw: http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-December/046152.html http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-September/076592.html