LLVM's Undef and Poison Values

 
Undef and Poison:
Present and Future
 
Juneyoung Lee
Seoul National University
 
1
 
This talk is based on joint work with
Sanjoy Das, Chung-Kil Hur, Nuno P. Lopes, David Majnemer, John Regehr
What is This Talk About?
 
•
LLVM has a notion of 
undef & poison values
.
•
Their semantics has been unclear, causing real-world problems.
 
 
 
 
 
 
•
Recently, efforts have been made to address the problem.
•
I will talk about the 
background
, 
current status
, and 
future directions
.
2
 
Background
Undefined Behavior,
Undef, and Poison
 
3
Undefined Behavior
•
Behavior of a program that violates the language standard
•
Behavioral refinement: 
Compiler assumes the source has no UB
4
 
int
 x;
 
if
 (cond) x = 3;
 f(x);
 
movl
    $3, %edi
 
call
    f
false
UB
UB
C
A
s
m
I
n
d
e
t
e
r
m
i
n
a
t
e
v
a
l
u
e
I
n
d
e
t
e
r
m
i
n
a
t
e
v
a
l
u
e
Motivation for Undef
5
New LLVM ‘undef’ Value, 
http://www.nondot.org/sabre/LLVMNotes/UndefinedValue.txt
 
Problem
IR didn’t have a notion of ‘
uninitialized value
’
 
; br cond, ...
 x = 
phi
(3,       )
 
call
 f(x)
I
R
 
int
 x;
 
if
 (cond) x = 3;
 f(x);
C
?
?
undef
•
Example: C’s bitfield
6
New LLVM ‘undef’ Value, 
http://www.nondot.org/sabre/LLVMNotes/UndefinedValue.txt
 
struct
 {
   
int
 x: 2, y: 6;
 } a;
 a.x = 1;
 a = alloca
 b = 
load
 a
 v = (b & ~3) | 1
 
store
 v, a
 
C
I
R
I
n
d
e
t
e
r
m
i
n
a
t
e
v
a
l
u
e
UB
UB
Definition of Undef
•
undef
 of type T is the 
set
 consisting of 
all
 defined values of T.
•
A (partially) undefined value is a subset of 
undef
.
•
An operation on undefined values is defined in element-wise manner
7
 
struct
 {
   
int
 x: 2, y: 6;
 } a;
 a.x = 1;
 a = 
alloca
 i8
 b = 
load
 i8 a
 v = (b & ~3) | 1
 
store
 v, a
C
I
R
u
n
d
e
f
 
=
 
{
0
,
 
1
,
 
.
.
.
,
 
2
5
5
}
8
 
b
i
t
s
:
 
*
*
*
*
*
*
*
*
******00
******01
 
🙂
The nsw story, 
https://groups.google.com/g/llvm-dev/c/sDYaYV_ZF-g/m/5Ektu6vM_0oJ
Motivation for Poison
8
 
int32_t
 i = 0;
 
while
 (i <= y) {
   arr[i] = ...;
   i = i + 1;
 }
 
int64_t
 i = 0;
 
while
 (i <= y) {
   arr[i] = ...;
   i = i + 1;
 }
I
R
I
R
Needs to
signext i to 64
(expensive)
Problem
Needed a value that represents 
signed overflow
 in LLVM IR,
But 
undef
 was too weak & UB was too strong.
•
Example: Widening an induction variable
No signext
needed
(cheap)
 
Motivation for Poison
 
9
 
int32_t
 i = 0;
 
while
 (i <= y) {
   arr[i] = ...;
   i = i + 1;
 }
 
int64_t
 i = 0;
 
while
 (i <= y) {
   arr[i] = ...;
   i = i + 1;
 }
I
R
I
R
 
•
Example: Widening an induction variable
INT32_MAX
INT32_MAX
Problem
Needed a value that represents 
signed overflow
 in LLVM IR,
But 
undef
 was too weak & UB was too strong.
always 
true
can be 
false
 
The nsw story, 
https://groups.google.com/g/llvm-dev/c/sDYaYV_ZF-g/m/5Ektu6vM_0oJ
Motivation for Poison
10
 
int32_t
 i = 0;
 
while
 (i <= y) {
   arr[i] = ...;
   i = i 
+nsw
 1;
 }
 
int64_t
 i = 0;
 
while
 (i <= y) {
   arr[i] = ...;
   i = i 
+nsw
 1;
 }
I
R
I
R
•
Example: Widening an induction variable
Problem
Needed a value that represents 
signed overflow
 in LLVM IR,
But 
undef
 was too weak & UB was too strong.
INT32_MAX
?
?
?
The nsw story, 
https://groups.google.com/g/llvm-dev/c/sDYaYV_ZF-g/m/5Ektu6vM_0oJ
p
o
i
s
o
n
!
INT32_MAX
always 
true
Definition of Poison
11
•
poison
 is a special value that represents 
a violation of an assumption
•
Each operation either propagates 
poison
 or raise UB
•
(Property) 
poison
 is refined by any (defined or undefined) value
 
🙂
 
int32_t
 i = 0;
 
while
 (i <= y) {
   arr[i] = ...;
   i = i 
+nsw
 1;
 }
 
int64_t
 i = 0;
 
while
 (i <= y) {
   arr[i] = ...;
   i = i 
+nsw
 1;
 }
I
R
I
R
poison
I
N
T
3
2
_
M
A
X
I
N
T
3
2
_
M
A
X
+
1
f
a
l
s
e
I
N
T
3
2
_
M
A
X
poison
 
poison
 
 
false is 
allowed
INT32_MAX
INT32_MAX
p
o
i
s
o
n
!
12
Comparison of Undef and Poison
1. 
poison
 and 
undef
 can fold to a different (defined) value at each use
 y = load uninit_var
 use1(
y
)
 use2(
y
)
 use1(
0
)
 use2(
1
)
 z = INT_MAX < (INT_MAX +nsw 1)
 use1(
z
)
 use2(
z
)
 use1(
0
)
 use2(
1
)
poison
undef
poison
Comparison of Undef and Poison
2. Undefined values do not admit certain arithmetic properties
13
 y = x * 2
 y = x + x
 y = x * 2
 y = x + x
?
A
.
 
I
f
 
x
 
i
s
 
p
o
i
s
o
n
:
poison
poison
B
.
 
I
f
 
x
 
i
s
 
u
n
d
e
f
:
 y = x * 2
 y = x + x
I
R
I
R
14
 y = x + undef
 y = undef
poison
poison
 x = c ? undef : y
 x = y
poison
true
undef
poison
poison
 
 
undef
: 
allowed
undef
 
 
poison
: 
disallowed
Comparison of Undef and Poison
3. 
poison
 is more undefined than 
undef
https://reviews.llvm.org/D83360
 
15
 
struct
 {
   
int
 x: 2, y: 6;
 } a;
 a.x = 1;
 a = 
alloca
 i8
 b = 
load
 i8 a
 v = (b & ~3) | 1
 
store
 v, a
C
I
R
poison
poison
poison
 
☹️
Comparison of Undef and Poison
4. 
poison
 cannot be used for uninitialized bitfields
 
Summary: UB, Undef, and Poison
 
•
Undefined behavior is the strongest one
•
poison
 is a notion of deferred UB
•
Undefined values are sets of values
 
16
Defined values
Defined values
Undefined values
Undefined values
UB
UB
Poison values
Poison values
 
Least
Defined
 
Most
Defined
 
Recent Progresses in
Fixing UB-related Problems in LLVM
 
 
17
1
. Semantics Are Clarified at LangRef.
18
 br undef, A, B
 switch undef, ...
UB
UB
 z = select poison, x, y
B
r
a
n
c
h
 
T
e
r
n
a
r
y
 
O
p
.
 
shufflevector’s undef mask, memset(undef, val, 0), padding of aggregates, ...
 // MSAN 
does not like undefs as branch condition
 which can be introduced
 // with "explicit branch".
 
if
 (ExtraCase && 
BB
->
getParent
()->
hasFnAttribute
(
Attribute
::SanitizeMemory))
   
return
 
false
;
https://reviews.llvm.org/D76973
 
https://reviews.llvm.org/D86189
 
https://reviews.llvm.org/D70641
 
https://reviews.llvm.org/D86643
  
 
A
n
d
 
a
l
s
o
 
2
. Undef/Poison-related Bugs
    Are Found with Alive2
 
•
Alive2 is a translation validation tool for LLVM: 
https://alive2.llvm.org
 
 
 
 
•
llvm/test/Transforms: 23 bugs reported, 17 fixed, 37 failures remaining
•
Project Zero LLVM Bugs: 
https://web.ist.utl.pt/nuno.lopes/alive2/
 
 
 
19
src.ll
tgt.ll
 
o
p
t
It’s correct / incorrect!
 
3.
 
Freeze to the Rescue
 
20
 y = x * 2
 y = x + x
undef
D
e
f
i
n
i
t
i
o
n
 
o
f
 
“
y
 
=
 
f
r
e
e
z
e
 
x
”
•
If x is 
poison
 or 
undefined value
: return a defined, nondeterministically chosen, value
•
Otherwise: return 
x
 
•
Officially added to LLVM 10.0
undef
 
3.
 
Freeze to the Rescue
 
21
 y = x * 2
 x’ = 
freeze
 x
 y = x’ + x’
0
D
e
f
i
n
i
t
i
o
n
 
o
f
 
“
y
 
=
 
f
r
e
e
z
e
 
x
”
•
If x is 
poison
 or 
undefined value
: return a defined, nondeterministically chosen, value
•
Otherwise: return 
x
1
2
 
(
N
o
n
d
e
t
e
r
m
i
n
i
s
t
i
c
a
l
l
y
 
c
h
o
s
e
n
)
0
2
 
•
Officially added to LLVM 10.0
 
(
o
n
e
 
o
f
 
e
v
e
n
 
n
u
m
b
e
r
s
)
undef
undef
Fixing “Select 
 Branch” Using Freeze
22
 z = select c, x, y
poison
poison
 if (c) z = x
 else   z = y
poison
UB
UB
 z = select c, x, y
 if (
freeze
(c)) z = x
 else   z = y
poison
true
false
https://reviews.llvm.org/D84940
 
https://reviews.llvm.org/D76179
 
3.
 
Freeze to the Rescue
Fixing DivRemPairs Using Freeze
23
 a = x / y
 b = x % y
 a = x / y
 b = x - (a * y)
1
undef
undef
0
undef
1
undef
undef
undef
https://reviews.llvm.org/D76483
 
3.
 
Freeze to the Rescue
1
undef
undef
24
 a = x / y
 b = x % y
 x’= 
freeze
 x
 a = x’ / y
 b = x’ - (a * y)
n
n
undef
n
0
I
n
 
t
h
e
 
f
u
l
l
 
p
a
t
c
h
,
 
y
 
i
s
 
f
r
o
z
e
n
 
a
s
 
w
e
l
l
b
e
c
a
u
s
e
 
g
i
v
i
n
g
 
a
n
 
u
n
d
e
f
i
n
e
d
 
v
a
l
u
e
 
t
o
 
y
 
c
a
u
s
e
s
 
a
 
b
u
g
 
t
o
o
.
1
 
n
 
i
s
 
a
 
d
e
f
i
n
e
d
 
v
a
l
u
e
!
Fixing DivRemPairs Using Freeze
3.
 
Freeze to the Rescue
1
undef
undef
0
1
undef
 
Performance Regression Matters
 
•
There are optimizations/analyses unaware of freeze
•
Fixing DivRemPairs: ~2% slowdown in 505.mcf_r with LTO, -O3
•
Reason: SCEV wasn’t aware of freeze 
 
LSR disabled
•
Solution: added a pass that hoists freeze out of a loop to remove the slowdown
 
25
 
https://reviews.llvm.org/D77523
 
4. Some Optimizations Were Removed
 
Folding select with undef operand
 
 
•
It can be easily fixed with freeze, but simply disabled
 
26
 x = c ? undef : y
 x = y
 
https://reviews.llvm.org/D83360
https://reviews.llvm.org/D85684
 
5. Patches Have Landed to Recover
    Performance
 
A.
Insert fewer freeze instructions
•
ValueTracking::isGuaranteedNotToBeUndefOrPoison
•
Library functions (e.g. 
printf
) have 
noundef
 at arguments/return values
B.
Make optimizations & analyses aware of freeze
•
GVN, LICM, EarlyCSE, JumpThreading, ... are aware of freeze
•
computeKnownBits
, 
isKnownZero
 understand freeze
 
27
 
https://reviews.llvm.org/D29013
https://reviews.llvm.org/D75808
https://reviews.llvm.org/D85345
 
Future Directions
 
 
28
1. Use Non-Undef/Poison Assumption
    From Source Language
 
•
(Ongoing) Attach 
noundef
 to function arguments when lowering C 
to IR
•
Passing ill-defined values as function arguments raise UB in C/C++
•
Attaching 
noundef
 is in progress (mainly by MSan folks)
•
(Suggestion) Attach
!noundef
 metadata to instructions
•
Certain erroneous operations raise UB in C/C++
•
e.g., Signed overflow, OOB pointer, Loading ill-defined values of non-char type
 
29
https://reviews.llvm.org/D81678
 
2. Improve Undef/Poison Analysis
30
 @f(
i32
 %n) {
 loop:
   %i    = 
phi
 [0,   %entry]
               [%i’, %loop]
   
%i’
   = %i 
+nsw
 
1
   %cmp  = %i’ 
<=
 %n
   
br
 %cmp, loop, exit
 }
Q: Is 
%i’
 never undef & poison?
A: 
Yes
!
(1)
non-undef:  
%i’
 increments from 0
(2)
non-poison: “
br
 %cmp
” raises 
UB
                    
if 
poison
.
poison
UB
UB
poison
poison
poison
3. Make More Optimizations
    Freeze-Aware
 
•
Optimizations
•
SimplifyCFG, InstCombine, InstSimplify
-
Reenable unnecessarily disabled patterns in the presence of freeze.
•
Vectorizer
-
Update vectorization algorithms to handle freeze
•
Analyses
•
Freeze makes difference between Must & May Analyses
-
Holds for: one of possible values vs. all possible values
31
https://reviews.llvm.org/D75808
https://reviews.llvm.org/D87445
 
Non-Undef/Poison Assumption From
Source is Helpful
 
•
Baseline: Fix 16 more bugs by inserting freeze or conditionally enabling it
•
Attach 
noundef
 to function args & 
!noundef
 to value read when lowering from C/C++
•
Run SPEC CPU2017 with –O3, count the unremoved freeze insts.
 
32
Making Things Simpler by
Removing 
undef
 
•
undef
 is hard to reason about due to partially undefined values
•
Alive2 detected 
>30
 miscompilations only caused by 
undef
•
Might be possible to use 
poison
 and 
freeze
 instead of 
undef
33
https://bugs.llvm.org/show_bug.cgi?id=33165
 
Summary
 
1.
LLVM has 
undef
 and 
poison
 values
2.
Miscompilations can be fixed with freeze
 by removing corner cases
3.
Cost of using freeze has been reduced over time
4.
Suggest removing 
undef
 and using 
poison
 only
34

								

								
								

										

												
Slide Note

												
Good morning everyone.
I’m Juneyoung Lee, from Seoul National University, and I’m happy to give a talk for this LLVM developer meeting.
Today, I’m going to talk about an important topic in LLVM, which is undef and poison values

										

								


								
						

							
						


							

								

									
										
Embed
									
									
										
Share
									

									
									
									

								

								
							


							

							 
 							 
 							 
						  


							
							

								
This talk dives into LLVM's concept of undef and poison values, addressing the uncertainties and real-world problems associated with their semantics. The discussion covers the background, current status, and future directions of these values, shedding light on their importance in program behavior and compiler assumptions. Motivations for resolving issues related to uninitialized values and signed overflow in LLVM IR are explored, offering insights into the evolving landscape of program optimization and standard compliance.


								
    
																		
  •   LLVM
    • 
																	
  •    Undef
    • 
																	
  •    Poison Values
    • 
																	
  •    Compiler Optimization
    • 
																	
  •    Undefined Behavior
    • 
																

								

								

									

										veno_im
										

											 veno_im Follow
											

										

									

									
Uploaded on Oct 03, 2024 | 0 Views

								

								


								

									
Download Presentation

									
								

								
Please find below an Image/Link to download the presentation.

								
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
									Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.


									
									

									


										 
										 
										 
										 

									

									

									

									

										
 E N D 

									


								
Presentation Transcript

								

								
  1. Undef and Poison: Present and Future Juneyoung Lee Seoul National University This talk is based on joint work with Sanjoy Das, Chung-Kil Hur, Nuno P. Lopes, David Majnemer, John Regehr 1
    2. 
            
            
            
  2. What is This Talk About?     LLVM has a notion of undef & poison values.     Their semantics has been unclear, causing real-world problems.     Recently, efforts have been made to address the problem.     I will talk about the background, current status, and future directions. 2
    3. 
            
            
            
  3. Background Undefined Behavior, Undef, and Poison 3
    4. 
            
            
            
  4. Undefined Behavior     Behavior of a program that violates the language standard     Behavioral refinement: Compiler assumes the source has no UB UB C Indeterminate  value Asm false int x; if (cond) x = 3; f(x); movl call $3, %edi f Indeterminate  value 4
    5. 
            
            
            
  5. Motivation for Undef Problem IR didn   t have a notion of    uninitialized value    C IR int x; if (cond) x = 3; ; br cond, ... x = phi(3,       ) call f(x) ?? undef f(x); 5 New LLVM    undef    Value, http://www.nondot.org/sabre/LLVMNotes/UndefinedValue.txt
    6. 
            
            
            
  6. Undef  Indeterminate Value     Example: C   s bitfield UB C Indeterminate  value IR struct { int x: 2, y: 6; } a; a.x = 1; a = alloca b = load a v = (b & ~3) | 1 store v, a 6 New LLVM    undef    Value, http://www.nondot.org/sabre/LLVMNotes/UndefinedValue.txt
    7. 
            
            
            
  7. Definition of Undef     undef of type T is the set consisting of all defined values of T.     A (partially) undefined value is a subset of undef.     An operation on undefined values is defined in element-wise manner C IR struct { int x: 2, y: 6; } a; a.x = 1; undef = {0, 1, ..., 255} 8 bits: ******** a = alloca i8 b = load i8 a v = (b & ~3) | 1 store v, a ******01 ******00 7
    8. 
            
            
            
  8. Motivation for Poison Problem Needed a value that represents signed overflow in LLVM IR, But undef was too weak & UB was too strong.     Example: Widening an induction variable IR IR int32_t i = 0; while (i <= y) { arr[i] = ...; i = i + 1; } int64_t i = 0; while (i <= y) { arr[i] = ...; i = i + 1; } No signext needed (cheap) Needs to signext i to 64 The nsw story, https://groups.google.com/g/llvm-dev/c/sDYaYV_ZF-g/m/5Ektu6vM_0oJ (expensive) 8
    9. 
            
            
            
  9. Motivation for Poison Problem Needed a value that represents signed overflow in LLVM IR, But undef was too weak & UB was too strong.     Example: Widening an induction variable can be false always true IR IR int32_t i = 0; while (i <= y) { arr[i] = ...; i = i + 1; } int64_t i = 0; while (i <= y) { arr[i] = ...; i = i + 1; } INT32_MAX INT32_MAX The nsw story, https://groups.google.com/g/llvm-dev/c/sDYaYV_ZF-g/m/5Ektu6vM_0oJ 9
    10. 
            
            
            
  10. Motivation for Poison Problem Needed a value that represents signed overflow in LLVM IR, But undef was too weak & UB was too strong.     Example: Widening an induction variable always true IR IR int32_t i = 0; while (i <= y) { arr[i] = ...; i = i +nsw 1; } INT32_MAX int64_t i = 0; while (i <= y) { arr[i] = ...; i = i +nsw 1; } undef     INT32_MAX is still true 2. Raising UB blocks code motion INT32_MAX 1. ??? poison! 10 The nsw story, https://groups.google.com/g/llvm-dev/c/sDYaYV_ZF-g/m/5Ektu6vM_0oJ
    11. 
            
            
            
  11. Definition of Poison     poison is a special value that represents a violation of an assumption     Each operation either propagates poison or raise UB     (Property) poison is refined by any (defined or undefined) value     false is allowed  poison     false poison IR IR int32_t i = 0; while (i <= y) { arr[i] = ...; i = i +nsw 1; } INT32_MAX int64_t i = 0; while (i <= y) { arr[i] = ...; i = i +nsw 1; } INT32_MAX poison INT32_MAX INT32_MAX INT32_MAX+1 poison! 11
    12. 
            
            
            
  12. Comparison of Undef and Poison 1. poison and undef can fold to a different (defined) value at each use undef y = load uninit_var use1(y) use2(y) use1(0) use2(1) poison poison z = INT_MAX < (INT_MAX +nsw 1) use1(z) use2(z) use1(0) use2(1) 12
    13. 
            
            
            
  13. Comparison of Undef and Poison 2. Undefined values do not admit certain arithmetic properties ? IR IR y = x * 2 y = x + x A. If x is poison: poison y = x * 2 y = x + x poison B. If x is undef: {?,?,?,?..} y = x * 2 y = x + x {?,?,?,..} 13
    14. 
            
            
            
  14. Comparison of Undef and Poison 3. poison is more undefined than undef     undef: allowed poison     poison poison y = x + undef y = undef     poison: disallowed undef     undef true poison poison x = c ? undef : y x = y 14 https://reviews.llvm.org/D83360
    15. 
            
            
            
  15. Comparison of Undef and Poison 4. poison cannot be used for uninitialized bitfields C IR poison struct { int x: 2, y: 6; } a; a.x = 1; a = alloca i8 b = load i8 a v = (b & ~3) | 1 store v, a poison poison 15
    16. 
            
            
            
  16. Summary: UB, Undef, and Poison Least  Defined UB     Undefined behavior is the strongest one Poison values     poison is a notion of deferred UB Undefined values     Undefined values are sets of values Most  Defined Defined values 16
    17. 
            
            
            
  17. Recent Progresses in Fixing UB-related Problems in LLVM 17
    18. 
            
            
            
  18. 1. Semantics Are Clarified at LangRef. Branch br undef, A, B UB switch undef, ... // MSAN does not like undefs as branch condition which can be introduced // with "explicit branch". if (ExtraCase && BB->getParent()->hasFnAttribute(Attribute::SanitizeMemory)) return false; ? = poison Ternary Op. z = select poison, x, y And also  shufflevector   s undef mask, memset(undef, val, 0), padding of aggregates, ... https://reviews.llvm.org/D76973 https://reviews.llvm.org/D86189 https://reviews.llvm.org/D70641 https://reviews.llvm.org/D86643 18
    19. 
            
            
            
  19. 2. Undef/Poison-related Bugs Are Found with Alive2     Alive2 is a translation validation tool for LLVM: https://alive2.llvm.org src.ll It   s correct / incorrect! opt tgt.ll     llvm/test/Transforms: 23 bugs reported, 17 fixed, 37 failures remaining     Project Zero LLVM Bugs: https://web.ist.utl.pt/nuno.lopes/alive2/ 19
    20. 
            
            
            
  20. 3. Freeze to the Rescue     Officially added to LLVM 10.0 Definition of    y = freeze x        If x is poison or undefined value: return a defined, nondeterministically chosen, value     Otherwise: return x undef undef y = x * 2 y = x + x {?,?,?,?..} {?,?,?,..} 20
    21. 
            
            
            
  21. 3. Freeze to the Rescue     Officially added to LLVM 10.0 Definition of    y = freeze x        If x is poison or undefined value: return a defined, nondeterministically chosen, value     Otherwise: return x (Nondeterministically chosen) 1 2     0 undef undef x    = freeze x y = x    + x    y = x * 2 {?,?,?,..} 2     0 (one of even numbers) 21
    22. 
            
            
            
  22. 3. Freeze to the Rescue Fixing    Select         Branch    Using Freeze UB poison if (c) z = x else   z = y z = select c, x, y poison poison false true poison if (freeze(c)) z = x else   z = y z = select c, x, y https://reviews.llvm.org/D84940 https://reviews.llvm.org/D76179 22
    23. 
            
            
            
  23. 3. Freeze to the Rescue Fixing DivRemPairs Using Freeze 1 1 undef undef undef undef a = x / y b = x % y a = x / y b = x - (a * y) 0 1 undef undef undef undef 23 https://reviews.llvm.org/D76483
    24. 
            
            
            
  24. 3. Freeze to the Rescue Fixing DivRemPairs Using Freeze n is a defined value! n undef 1 undef undef x   = freeze x a = x    / y b = x    - (a * y) a = x / y b = x % y n 1 0 0 1 undef n In the full patch, y is frozen as well because giving an undefined value to y causes a bug too. 24
    25. 
            
            
            
  25. Performance Regression Matters     There are optimizations/analyses unaware of freeze     Fixing DivRemPairs: ~2% slowdown in 505.mcf_r with LTO, -O3     Reason: SCEV wasn   t aware of freeze     LSR disabled     Solution: added a pass that hoists freeze out of a loop to remove the slowdown 25 https://reviews.llvm.org/D77523
    26. 
            
            
            
  26. 4. Some Optimizations Were Removed Folding select with undef operand x = c ? undef : y x = y     It can be easily fixed with freeze, but simply disabled https://reviews.llvm.org/D83360 https://reviews.llvm.org/D85684 26
    27. 
            
            
            
  27. 5. Patches Have Landed to Recover Performance A. Insert fewer freeze instructions     ValueTracking::isGuaranteedNotToBeUndefOrPoison     Library functions (e.g. printf) have noundef at arguments/return values B. Make optimizations & analyses aware of freeze     GVN, LICM, EarlyCSE, JumpThreading, ... are aware of freeze     computeKnownBits, isKnownZero understand freeze https://reviews.llvm.org/D29013 https://reviews.llvm.org/D75808 https://reviews.llvm.org/D85345 27
    28. 
            
            
            
  28. Future Directions 28
    29. 
            
            
            
  29. 1. Use Non-Undef/Poison Assumption From Source Language     (Ongoing) Attach noundef to function arguments when lowering C to IR     Passing ill-defined values as function arguments raise UB in C/C++     Attaching noundef is in progress (mainly by MSan folks)     (Suggestion) Attach!noundef metadata to instructions     Certain erroneous operations raise UB in C/C++     e.g., Signed overflow, OOB pointer, Loading ill-defined values of non-char type 29 https://reviews.llvm.org/D81678
    30. 
            
            
            
  30. 2. Improve Undef/Poison Analysis @f(i32 %n) { loop: %i poison Q: Is %i    never undef & poison? = phi [0,   %entry] [%i   , %loop] = %i +nsw 1 = %i    <= %n br %cmp, loop, exit UB A: Yes! poison poison %i    %cmp (1) non-undef:  %i    increments from 0 (2) non-poison:    br %cmp    raises UB if poison. poison } 30
    31. 
            
            
            
  31. 3. Make More Optimizations Freeze-Aware     Optimizations     SimplifyCFG, InstCombine, InstSimplify - Reenable unnecessarily disabled patterns in the presence of freeze.     Vectorizer - Update vectorization algorithms to handle freeze     Analyses     Freeze makes difference between Must & May Analyses - Holds for: one of possible values vs. all possible values https://reviews.llvm.org/D75808 https://reviews.llvm.org/D87445 31
    32. 
            
            
            
  32. Non-Undef/Poison Assumption From Source is Helpful     Baseline: Fix 16 more bugs by inserting freeze or conditionally enabling it     Attach noundef to function args & !noundef to value read when lowering from C/C++      Run SPEC CPU2017 with    O3, count the unremoved freeze insts. Add noundef to fn args Add noundef to fn args & var reads SPEC CPU2017 Base # of freeze insts. 42K 36K (86%) 24K (57%) 49 ~ 95% (Avg. 77%) 27 ~ 80% (Avg. 51%) # of freeze per bench. 32
    33. 
            
            
            
  33. Making Things Simpler by Removing undef     undef is hard to reason about due to partially undefined values     Alive2 detected >30 miscompilations only caused by undef     Might be possible to use poison and freeze instead of undef 33 https://bugs.llvm.org/show_bug.cgi?id=33165
    34. 
            
            
            
  34. Summary 1. LLVM has undef and poison values 2. Miscompilations can be fixed with freeze by removing corner cases 3. Cost of using freeze has been reduced over time 4. Suggest removing undef and using poison only 34
    35. 
            
            
            
							

							

					

					
					
					

						
Related

						

						


							
							
							
							

						

							

									

      

        
          

            

              LLVM Instrumentation Overview
            

            

              
LLVM Instrumentation Overview

              
maude

            

          

        
      


     

      

        
          

            

              Implementing Our Values in Action Toolkit for Team Development
            

            

              
Implementing Our Values in Action Toolkit for Team Development

              
zackary

            

          

        
      


     

      

        
          

            

              Family Morals, Values, and Rules
            

            

              
Family Morals, Values, and Rules

              
fergus

            

          

        
      


     

      

        
          

            

              Dushi Visha: A Cumulative Poison in Ayurveda
            

            

              
Dushi Visha: A Cumulative Poison in Ayurveda

              
treasure

            

          

        
      


     

      

        
          

            

              Leveraging Artifact Dependency Graphs for Software Vulnerability Detection
            

            

              
Leveraging Artifact Dependency Graphs for Software Vulnerability Detection

              
eithne

            

          

        
      


     

      

        
          

            

              Growing Careers for Positive Change: Aligning Actions with Values
            

            

              
Growing Careers for Positive Change: Aligning Actions with Values

              
cyril

            

          

        
      


     

      

        
          

            

              Values, Beliefs, and Personal Values in Everyday Life
            

            

              
Values, Beliefs, and Personal Values in Everyday Life

              
isla

            

          

        
      


     

      

        
          

            

              The Importance of Values in Building Harmonious Communities
            

            

              
The Importance of Values in Building Harmonious Communities

              
hadrian

            

          

        
      


     

      

        
          

            

              Ethics, Values, and Universal Morality
            

            

              
Ethics, Values, and Universal Morality

              
philomena

            

          

        
      


     

      

        
          

            

              Personal Values in Everyday Life
            

            

              
Personal Values in Everyday Life

              
clementine

            

          

        
      


     

      

        
          

            

              Core Values in Higher Education Institutions
            

            

              
Core Values in Higher Education Institutions

              
chloe

            

          

        
      


     

      

        
          

            

              The Difference Between LLVM Profile-Instr-Generate and Profile-Generate Options
            

            

              
The Difference Between LLVM Profile-Instr-Generate and Profile-Generate Options

              
corben

            

          

        
      


     

      

        
          

            

              LLVM Memory Review and Function Example
            

            

              
LLVM Memory Review and Function Example

              
aliyahen

            

          

        
      


     

      

        
          

            

              LLVM Line Coverage Profiling Implementation Overview
            

            

              
LLVM Line Coverage Profiling Implementation Overview

              
aden

            

          

        
      


     

      

        
          

            

              Falcon: An Optimizing Java JIT Compiler Overview
            

            

              
Falcon: An Optimizing Java JIT Compiler Overview

              
mar_red

            

          

        
      


     

      

        
          

            

              Exploring Values Education in Nordic Preschools
            

            

              
Exploring Values Education in Nordic Preschools

              
kpixl

            

          

        
      


     

      

        
          

            

              Moral and Constitutional Values in Relation to Judiciary
            

            

              
Moral and Constitutional Values in Relation to Judiciary

              
christlyn

            

          

        
      


     

      

        
          

            

              Hazardous Plants Identification and Safety Guide
            

            

              
Hazardous Plants Identification and Safety Guide

              
wesly

            

          

        
      


     

      

        
          

            

              The Importance of Core Values in Parish Life
            

            

              
The Importance of Core Values in Parish Life

              
die_vi

            

          

        
      


     

      

        
          

            

              Teachers' Perceptions on Inclusive Values for Differentiated Science Instruction
            

            

              
Teachers' Perceptions on Inclusive Values for Differentiated Science Instruction

              
kcost

            

          

        
      


     

      

        
          

            

              Compiler Optimizations in LLVM: Challenges and Solutions
            

            

              
Compiler Optimizations in LLVM: Challenges and Solutions

              
myer_rm

            

          

        
      


     

      

        
          

            

              Automated Software Testing with LLVM Pass and Code Instrumentation
            

            

              
Automated Software Testing with LLVM Pass and Code Instrumentation

              
alli_3

            

          

        
      


     							

						

					

					

				


				

			

		
		

			

				
				

					
More Related Content

					

						

														

					

				

				
			

		












 





  
  
  



giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#