undefined behavior introduced by optimizer

[Quuxplusone]

Bugzilla Link	PR20997
Status	NEW
Importance	P normal
Reported by	John Regehr (regehr@cs.utah.edu)
Reported on	2014-09-18 18:28:20 -0700
Last modified on	2017-08-13 22:37:50 -0700
Version	trunk
Hardware	PC Linux
CC	david.majnemer@gmail.com, llvm-bugs@lists.llvm.org, peter@pcc.me.uk, raimondas.sasnauskas@cs.rwth-aachen.de, rnk@google.com, sanjoy@playingwithpointers.com, santosh.nagarakatte@gmail.com, spatel+llvm@rotateright.com
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also	PR21412, PR20895, PR34133

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$

[Quuxplusone]

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.

[Quuxplusone]

This raises an interesting question: is it better to drop the nsw and speculate, or to keep it and not speculate?

[Quuxplusone]

Or maybe not so interesting, seems pretty clear that the cost of a branch exceeds the expected value of an nsw.

[Quuxplusone]

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.

[Quuxplusone]

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.

[Quuxplusone]

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