1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
| ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -S -indvars < %s | FileCheck %s
; Tests in this file are specifically about correctly handling possibly poison
; producing flags when converting from one IV to another. In particular, there
; is a risk that the IV we chose to switch to is dynamically dead (i.e. there
; is no side effect which dependents on the computation thereof). Such an IV
; can produce poison on one or more iterations without triggering UB. When we
; add an additional use to such an IV, we need to ensure that our new use does
; not trigger UB where none existed in the original program.
; Provide legal integer types.
target datalayout = "n8:16:32:64"
@data = common global [240 x i8] zeroinitializer, align 16
;; In this example, the pointer IV is dynamicaly dead. As such, the fact that
;; inbounds produces poison *does not* trigger UB in the original loop. As
;; such, the pointer IV can be poison and adding a new use of the pointer
;; IV which dependends on that poison computation in a manner which might
;; trigger UB would be incorrect.
;; FIXME: This currently shows a miscompile!
define void @neg_dynamically_dead_inbounds(i1 %always_false) #0 {
; CHECK-LABEL: @neg_dynamically_dead_inbounds(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop:
; CHECK-NEXT: [[I_0:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[TMP4:%.*]], [[CONT:%.*]] ]
; CHECK-NEXT: [[P_0:%.*]] = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), [[ENTRY]] ], [ [[TMP3:%.*]], [[CONT]] ]
; CHECK-NEXT: [[TMP3]] = getelementptr inbounds i8, i8* [[P_0]], i64 1
; CHECK-NEXT: br i1 [[ALWAYS_FALSE:%.*]], label [[NEVER_EXECUTED:%.*]], label [[CONT]]
; CHECK: never_executed:
; CHECK-NEXT: store volatile i8 0, i8* [[TMP3]]
; CHECK-NEXT: br label [[CONT]]
; CHECK: cont:
; CHECK-NEXT: [[TMP4]] = add nuw i8 [[I_0]], 1
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i8 [[TMP4]], -10
; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK: exit:
; CHECK-NEXT: ret void
;
entry:
br label %loop
loop:
%i.0 = phi i8 [ 0, %entry ], [ %tmp4, %cont ]
%p.0 = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), %entry ], [ %tmp3, %cont ]
%tmp3 = getelementptr inbounds i8, i8* %p.0, i64 1
br i1 %always_false, label %never_executed, label %cont
never_executed:
store volatile i8 0, i8* %tmp3
br label %cont
cont:
%tmp4 = add i8 %i.0, 1
%tmp5 = icmp ult i8 %tmp4, -10
br i1 %tmp5, label %loop, label %exit
exit:
ret void
}
; Similiar to above, but shows how we currently guard non-constant
; memory operands in a manner which hides the latent miscompile.
define void @neg_dynamically_dead_inbounds2(i8* %a, i1 %always_false) #0 {
; CHECK-LABEL: @neg_dynamically_dead_inbounds2(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop:
; CHECK-NEXT: [[I_0:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[TMP4:%.*]], [[CONT:%.*]] ]
; CHECK-NEXT: [[P_0:%.*]] = phi i8* [ [[A:%.*]], [[ENTRY]] ], [ [[TMP3:%.*]], [[CONT]] ]
; CHECK-NEXT: [[TMP3]] = getelementptr inbounds i8, i8* [[P_0]], i64 1
; CHECK-NEXT: br i1 [[ALWAYS_FALSE:%.*]], label [[NEVER_EXECUTED:%.*]], label [[CONT]]
; CHECK: never_executed:
; CHECK-NEXT: store volatile i8 0, i8* [[TMP3]]
; CHECK-NEXT: br label [[CONT]]
; CHECK: cont:
; CHECK-NEXT: [[TMP4]] = add nuw i8 [[I_0]], 1
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i8 [[TMP4]], -10
; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK: exit:
; CHECK-NEXT: ret void
;
entry:
br label %loop
loop:
%i.0 = phi i8 [ 0, %entry ], [ %tmp4, %cont ]
%p.0 = phi i8* [ %a, %entry ], [ %tmp3, %cont ]
%tmp3 = getelementptr inbounds i8, i8* %p.0, i64 1
br i1 %always_false, label %never_executed, label %cont
never_executed:
store volatile i8 0, i8* %tmp3
br label %cont
cont:
%tmp4 = add i8 %i.0, 1
%tmp5 = icmp ult i8 %tmp4, -10
br i1 %tmp5, label %loop, label %exit
exit:
ret void
}
define void @dom_store_preinc() #0 {
; CHECK-LABEL: @dom_store_preinc(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop:
; CHECK-NEXT: [[P_0:%.*]] = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), [[ENTRY:%.*]] ], [ [[TMP3:%.*]], [[LOOP]] ]
; CHECK-NEXT: store volatile i8 0, i8* [[P_0]]
; CHECK-NEXT: [[TMP3]] = getelementptr inbounds i8, i8* [[P_0]], i64 1
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i8* [[P_0]], getelementptr ([240 x i8], [240 x i8]* @data, i64 1, i64 5)
; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK: exit:
; CHECK-NEXT: ret void
;
entry:
br label %loop
loop:
%i.0 = phi i8 [ 0, %entry ], [ %tmp4, %loop ]
%p.0 = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), %entry ], [ %tmp3, %loop ]
store volatile i8 0, i8* %p.0
%tmp3 = getelementptr inbounds i8, i8* %p.0, i64 1
%tmp4 = add i8 %i.0, 1
%tmp5 = icmp ult i8 %tmp4, -10
br i1 %tmp5, label %loop, label %exit
exit:
ret void
}
define void @dom_store_postinc() #0 {
; CHECK-LABEL: @dom_store_postinc(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop:
; CHECK-NEXT: [[P_0:%.*]] = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), [[ENTRY:%.*]] ], [ [[TMP3:%.*]], [[LOOP]] ]
; CHECK-NEXT: [[TMP3]] = getelementptr inbounds i8, i8* [[P_0]], i64 1
; CHECK-NEXT: store volatile i8 0, i8* [[TMP3]]
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i8* [[TMP3]], getelementptr ([240 x i8], [240 x i8]* @data, i64 1, i64 6)
; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK: exit:
; CHECK-NEXT: ret void
;
entry:
br label %loop
loop:
%i.0 = phi i8 [ 0, %entry ], [ %tmp4, %loop ]
%p.0 = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), %entry ], [ %tmp3, %loop ]
%tmp3 = getelementptr inbounds i8, i8* %p.0, i64 1
store volatile i8 0, i8* %tmp3
%tmp4 = add i8 %i.0, 1
%tmp5 = icmp ult i8 %tmp4, -10
br i1 %tmp5, label %loop, label %exit
exit:
ret void
}
define i8 @dom_load() #0 {
; CHECK-LABEL: @dom_load(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop:
; CHECK-NEXT: [[P_0:%.*]] = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), [[ENTRY:%.*]] ], [ [[TMP3:%.*]], [[LOOP]] ]
; CHECK-NEXT: [[TMP3]] = getelementptr inbounds i8, i8* [[P_0]], i64 1
; CHECK-NEXT: [[V:%.*]] = load i8, i8* [[TMP3]]
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i8* [[TMP3]], getelementptr ([240 x i8], [240 x i8]* @data, i64 1, i64 6)
; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK: exit:
; CHECK-NEXT: [[V_LCSSA:%.*]] = phi i8 [ [[V]], [[LOOP]] ]
; CHECK-NEXT: ret i8 [[V_LCSSA]]
;
entry:
br label %loop
loop:
%i.0 = phi i8 [ 0, %entry ], [ %tmp4, %loop ]
%p.0 = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), %entry ], [ %tmp3, %loop ]
%tmp3 = getelementptr inbounds i8, i8* %p.0, i64 1
%v = load i8, i8* %tmp3
%tmp4 = add i8 %i.0, 1
%tmp5 = icmp ult i8 %tmp4, -10
br i1 %tmp5, label %loop, label %exit
exit:
ret i8 %v
}
define i64 @dom_div(i64 %input) #0 {
; CHECK-LABEL: @dom_div(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop:
; CHECK-NEXT: [[I_0:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[TMP4:%.*]], [[LOOP]] ]
; CHECK-NEXT: [[I_1:%.*]] = phi i64 [ [[INPUT:%.*]], [[ENTRY]] ], [ [[TMP3:%.*]], [[LOOP]] ]
; CHECK-NEXT: [[TMP3]] = add nuw nsw i64 [[I_1]], 1
; CHECK-NEXT: [[V:%.*]] = udiv i64 5, [[TMP3]]
; CHECK-NEXT: [[TMP4]] = add nuw i8 [[I_0]], 1
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i8 [[TMP4]], -10
; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK: exit:
; CHECK-NEXT: [[V_LCSSA:%.*]] = phi i64 [ [[V]], [[LOOP]] ]
; CHECK-NEXT: ret i64 [[V_LCSSA]]
;
entry:
br label %loop
loop:
%i.0 = phi i8 [ 0, %entry ], [ %tmp4, %loop ]
%i.1 = phi i64 [ %input, %entry ], [ %tmp3, %loop ]
%tmp3 = add nsw nuw i64 %i.1, 1
%v = udiv i64 5, %tmp3
%tmp4 = add i8 %i.0, 1
%tmp5 = icmp ult i8 %tmp4, -10
br i1 %tmp5, label %loop, label %exit
exit:
ret i64 %v
}
; For integer IVs, we handle this trigger case by stripping the problematic
; flags which removes the potential introduction of UB.
define void @neg_dead_int_iv() #0 {
; CHECK-LABEL: @neg_dead_int_iv(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop:
; CHECK-NEXT: [[I_1:%.*]] = phi i64 [ -2, [[ENTRY:%.*]] ], [ [[TMP3:%.*]], [[LOOP]] ]
; CHECK-NEXT: [[TMP3]] = add nsw i64 [[I_1]], 1
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i64 [[TMP3]], 244
; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK: exit:
; CHECK-NEXT: ret void
;
entry:
br label %loop
loop:
%i.0 = phi i8 [ 0, %entry ], [ %tmp4, %loop ]
%i.1 = phi i64 [ -2, %entry ], [ %tmp3, %loop ]
%tmp3 = add nsw nuw i64 %i.1, 1
%tmp4 = add i8 %i.0, 1
%tmp5 = icmp ult i8 %tmp4, -10
br i1 %tmp5, label %loop, label %exit
exit:
ret void
}
|