Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

undefined behavior introduced by optimizer #21371

Closed
regehr opened this issue Sep 19, 2014 · 8 comments
Closed

undefined behavior introduced by optimizer #21371

regehr opened this issue Sep 19, 2014 · 8 comments
Labels
bugzilla Issues migrated from bugzilla llvm:optimizations

Comments

@regehr
Copy link
Contributor

regehr commented Sep 19, 2014

Bugzilla Link 20997
Version trunk
OS Linux
CC @majnemer,@pcc,@rnk,@sanjoy,@rotateright

Extended Description

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$
@majnemer
Copy link
Mannequin

majnemer mannequin commented Sep 19, 2014

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.

@regehr
Copy link
Contributor Author

regehr commented Sep 19, 2014

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

@regehr
Copy link
Contributor Author

regehr commented Sep 19, 2014

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

@majnemer
Copy link
Mannequin

majnemer mannequin commented Sep 19, 2014

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.

@rotateright
Copy link
Contributor

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.

@rotateright
Copy link
Contributor

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

@nunoplopes
Copy link
Member

mentioned in issue llvm/llvm-bugzilla-archive#34133

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 9, 2021
@nikic
Copy link
Contributor

nikic commented May 24, 2022

This class of issues has been fixed by logical and/or changes.

@nikic nikic closed this as completed May 24, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bugzilla Issues migrated from bugzilla llvm:optimizations
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@nikic @regehr @nunoplopes @EugeneZelenko @rotateright