blob: b1fe7f1138b6c7dd72e1043e129ea43260634c56 [file] [log] [blame]
Jingyue Wu42f1d672015-07-28 18:22:40 +00001; RUN: opt < %s -S -analyze -scalar-evolution | FileCheck %s
2
3; Positive and negative tests for inferring flags like nsw from
4; reasoning about how a poison value from overflow would trigger
5; undefined behavior.
6
7define void @foo() {
8 ret void
9}
10
11; Example where an add should get the nsw flag, so that a sext can be
12; distributed over the add.
13define void @test-add-nsw(float* %input, i32 %offset, i32 %numIterations) {
14; CHECK-LABEL: @test-add-nsw
15entry:
16 br label %loop
17loop:
18 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
19
20; CHECK: %index32 =
21; CHECK: --> {%offset,+,1}<nsw>
22 %index32 = add nsw i32 %i, %offset
23
24; CHECK: %index64 =
25; CHECK: --> {(sext i32 %offset to i64),+,1}<nsw>
26 %index64 = sext i32 %index32 to i64
27
28 %ptr = getelementptr inbounds float, float* %input, i64 %index64
29 %nexti = add nsw i32 %i, 1
30 %f = load float, float* %ptr, align 4
31 call void @foo()
32 %exitcond = icmp eq i32 %nexti, %numIterations
33 br i1 %exitcond, label %exit, label %loop
34exit:
35 ret void
36}
37
38; Example where an add should get the nuw flag.
39define void @test-add-nuw(float* %input, i32 %offset, i32 %numIterations) {
40; CHECK-LABEL: @test-add-nuw
41entry:
42 br label %loop
43loop:
44 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
45
46; CHECK: %index32 =
47; CHECK: --> {%offset,+,1}<nuw>
48 %index32 = add nuw i32 %i, %offset
49
50 %ptr = getelementptr inbounds float, float* %input, i32 %index32
51 %nexti = add nuw i32 %i, 1
52 %f = load float, float* %ptr, align 4
53 %exitcond = icmp eq i32 %nexti, %numIterations
54 br i1 %exitcond, label %exit, label %loop
55
56exit:
57 ret void
58}
59
60; With no load to trigger UB from poison, we cannot infer nsw.
61define void @test-add-no-load(float* %input, i32 %offset, i32 %numIterations) {
62; CHECK-LABEL: @test-add-no-load
63entry:
64 br label %loop
65loop:
66 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
67
68; CHECK: %index32 =
69; CHECK: --> {%offset,+,1}<nw>
70 %index32 = add nsw i32 %i, %offset
71
72 %ptr = getelementptr inbounds float, float* %input, i32 %index32
73 %nexti = add nuw i32 %i, 1
74 %exitcond = icmp eq i32 %nexti, %numIterations
75 br i1 %exitcond, label %exit, label %loop
76
77exit:
78 ret void
79}
80
81; The current code is only supposed to look at the loop header, so
82; it should not infer nsw in this case, as that would require looking
83; outside the loop header.
84define void @test-add-not-header(float* %input, i32 %offset, i32 %numIterations) {
85; CHECK-LABEL: @test-add-not-header
86entry:
87 br label %loop
88loop:
89 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
90 br label %loop2
91loop2:
92
93; CHECK: %index32 =
94; CHECK: --> {%offset,+,1}<nw>
95 %index32 = add nsw i32 %i, %offset
96
97 %ptr = getelementptr inbounds float, float* %input, i32 %index32
98 %nexti = add nsw i32 %i, 1
99 %f = load float, float* %ptr, align 4
100 %exitcond = icmp eq i32 %nexti, %numIterations
101 br i1 %exitcond, label %exit, label %loop
102exit:
103 ret void
104}
105
106; Same thing as test-add-not-header, but in this case only the load
107; instruction is outside the loop header.
108define void @test-add-not-header2(float* %input, i32 %offset, i32 %numIterations) {
109; CHECK-LABEL: @test-add-not-header2
110entry:
111 br label %loop
112loop:
113 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
114
115; CHECK: %index32 =
116; CHECK: --> {%offset,+,1}<nw>
117 %index32 = add nsw i32 %i, %offset
118
119 %ptr = getelementptr inbounds float, float* %input, i32 %index32
120 %nexti = add nsw i32 %i, 1
121 br label %loop2
122loop2:
123 %f = load float, float* %ptr, align 4
124 %exitcond = icmp eq i32 %nexti, %numIterations
125 br i1 %exitcond, label %exit, label %loop
126exit:
127 ret void
128}
129
130; The call instruction makes it not guaranteed that the add will be
131; executed, since it could run forever or throw an exception, so we
132; cannot assume that the UB is realized.
133define void @test-add-call(float* %input, i32 %offset, i32 %numIterations) {
134; CHECK-LABEL: @test-add-call
135entry:
136 br label %loop
137loop:
138 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
139
140; CHECK: %index32 =
141; CHECK: --> {%offset,+,1}<nw>
142 call void @foo()
143 %index32 = add nsw i32 %i, %offset
144
145 %ptr = getelementptr inbounds float, float* %input, i32 %index32
146 %nexti = add nsw i32 %i, 1
147 %f = load float, float* %ptr, align 4
148 %exitcond = icmp eq i32 %nexti, %numIterations
149 br i1 %exitcond, label %exit, label %loop
150exit:
151 ret void
152}
153
154; Same issue as test-add-call, but this time the call is between the
155; producer of poison and the load that consumes it.
156define void @test-add-call2(float* %input, i32 %offset, i32 %numIterations) {
157; CHECK-LABEL: @test-add-call2
158entry:
159 br label %loop
160loop:
161 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
162
163; CHECK: %index32 =
164; CHECK: --> {%offset,+,1}<nw>
165 %index32 = add nsw i32 %i, %offset
166
167 %ptr = getelementptr inbounds float, float* %input, i32 %index32
168 %nexti = add nsw i32 %i, 1
169 call void @foo()
170 %f = load float, float* %ptr, align 4
171 %exitcond = icmp eq i32 %nexti, %numIterations
172 br i1 %exitcond, label %exit, label %loop
173exit:
174 ret void
175}
176
177; Without inbounds, GEP does not propagate poison in the very
178; conservative approach used here.
179define void @test-add-no-inbounds(float* %input, i32 %offset, i32 %numIterations) {
180; CHECK-LABEL: @test-add-no-inbounds
181entry:
182 br label %loop
183loop:
184 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
185
186; CHECK: %index32 =
187; CHECK: --> {%offset,+,1}<nw>
188 %index32 = add nsw i32 %i, %offset
189
190 %ptr = getelementptr float, float* %input, i32 %index32
191 %nexti = add nsw i32 %i, 1
192 %f = load float, float* %ptr, align 4
193 %exitcond = icmp eq i32 %nexti, %numIterations
194 br i1 %exitcond, label %exit, label %loop
195exit:
196 ret void
197}
198
199; Multiplication by a non-zero constant propagates poison if there is
200; a nuw or nsw flag on the multiplication.
201define void @test-add-mul-propagates(float* %input, i32 %offset, i32 %numIterations) {
202; CHECK-LABEL: @test-add-mul-propagates
203entry:
204 br label %loop
205loop:
206 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
207
208; CHECK: %index32 =
209; CHECK: --> {%offset,+,1}<nsw>
210 %index32 = add nsw i32 %i, %offset
211
212 %indexmul = mul nuw i32 %index32, 2
213 %ptr = getelementptr inbounds float, float* %input, i32 %indexmul
214 %nexti = add nsw i32 %i, 1
215 %f = load float, float* %ptr, align 4
216 %exitcond = icmp eq i32 %nexti, %numIterations
217 br i1 %exitcond, label %exit, label %loop
218exit:
219 ret void
220}
221
222; Multiplication by a non-constant should not propagate poison in the
223; very conservative approach used here.
224define void @test-add-mul-no-propagation(float* %input, i32 %offset, i32 %numIterations) {
225; CHECK-LABEL: @test-add-mul-no-propagation
226entry:
227 br label %loop
228loop:
229 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
230
231; CHECK: %index32 =
232; CHECK: --> {%offset,+,1}<nw>
233 %index32 = add nsw i32 %i, %offset
234
235 %indexmul = mul nsw i32 %index32, %offset
236 %ptr = getelementptr inbounds float, float* %input, i32 %indexmul
237 %nexti = add nsw i32 %i, 1
238 %f = load float, float* %ptr, align 4
239 %exitcond = icmp eq i32 %nexti, %numIterations
240 br i1 %exitcond, label %exit, label %loop
241exit:
242 ret void
243}
244
245; Multiplication by a non-zero constant does not propagate poison
246; without a no-wrap flag.
247define void @test-add-mul-no-propagation2(float* %input, i32 %offset, i32 %numIterations) {
248; CHECK-LABEL: @test-add-mul-no-propagation2
249entry:
250 br label %loop
251loop:
252 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
253
254; CHECK: %index32 =
255; CHECK: --> {%offset,+,1}<nw>
256 %index32 = add nsw i32 %i, %offset
257
258 %indexmul = mul i32 %index32, 2
259 %ptr = getelementptr inbounds float, float* %input, i32 %indexmul
260 %nexti = add nsw i32 %i, 1
261 %f = load float, float* %ptr, align 4
262 %exitcond = icmp eq i32 %nexti, %numIterations
263 br i1 %exitcond, label %exit, label %loop
264exit:
265 ret void
266}
267
268; Division by poison triggers UB.
269define void @test-add-div(float* %input, i32 %offset, i32 %numIterations) {
270; CHECK-LABEL: @test-add-div
271entry:
272 br label %loop
273loop:
274 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
275
276; CHECK: %j =
277; CHECK: --> {%offset,+,1}<nsw>
278 %j = add nsw i32 %i, %offset
279
280 %q = sdiv i32 %numIterations, %j
281 %nexti = add nsw i32 %i, 1
282 %exitcond = icmp eq i32 %nexti, %numIterations
283 br i1 %exitcond, label %exit, label %loop
284exit:
285 ret void
286}
287
288; Remainder of poison by non-poison divisor does not trigger UB.
289define void @test-add-div2(float* %input, i32 %offset, i32 %numIterations) {
290; CHECK-LABEL: @test-add-div2
291entry:
292 br label %loop
293loop:
294 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
295
296; CHECK: %j =
297; CHECK: --> {%offset,+,1}<nw>
298 %j = add nsw i32 %i, %offset
299
300 %q = sdiv i32 %j, %numIterations
301 %nexti = add nsw i32 %i, 1
302 %exitcond = icmp eq i32 %nexti, %numIterations
303 br i1 %exitcond, label %exit, label %loop
304exit:
305 ret void
306}
307
308; Store to poison address triggers UB.
309define void @test-add-store(float* %input, i32 %offset, i32 %numIterations) {
310; CHECK-LABEL: @test-add-store
311entry:
312 br label %loop
313loop:
314 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
315
316; CHECK: %index32 =
317; CHECK: --> {%offset,+,1}<nsw>
318 %index32 = add nsw i32 %i, %offset
319
320 %ptr = getelementptr inbounds float, float* %input, i32 %index32
321 %nexti = add nsw i32 %i, 1
322 store float 1.0, float* %ptr, align 4
323 %exitcond = icmp eq i32 %nexti, %numIterations
324 br i1 %exitcond, label %exit, label %loop
325exit:
326 ret void
327}
328
329; Three sequential adds where the middle add should have nsw. There is
330; a special case for sequential adds and this test covers that. We have to
331; put the final add first in the program since otherwise the special case
332; is not triggered, hence the strange basic block ordering.
333define void @test-add-twice(float* %input, i32 %offset, i32 %numIterations) {
334; CHECK-LABEL: @test-add-twice
335entry:
336 br label %loop
337loop2:
338; CHECK: %seq =
339; CHECK: --> {(2 + %offset),+,1}<nw>
340 %seq = add nsw nuw i32 %index32, 1
341 %exitcond = icmp eq i32 %nexti, %numIterations
342 br i1 %exitcond, label %exit, label %loop
343
344loop:
345 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
346
347 %j = add nsw i32 %i, 1
348; CHECK: %index32 =
349; CHECK: --> {(1 + %offset),+,1}<nsw>
350 %index32 = add nsw i32 %j, %offset
351
352 %ptr = getelementptr inbounds float, float* %input, i32 %index32
353 %nexti = add nsw i32 %i, 1
354 store float 1.0, float* %ptr, align 4
355 br label %loop2
356exit:
357 ret void
358}
Bjarke Hammersholt Roune9791ed42015-08-14 22:45:26 +0000359
360; Example where a mul should get the nsw flag, so that a sext can be
361; distributed over the mul.
362define void @test-mul-nsw(float* %input, i32 %stride, i32 %numIterations) {
363; CHECK-LABEL: @test-mul-nsw
364entry:
365 br label %loop
366loop:
367 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
368
369; CHECK: %index32 =
370; CHECK: --> {0,+,%stride}<nsw>
371 %index32 = mul nsw i32 %i, %stride
372
373; CHECK: %index64 =
374; CHECK: --> {0,+,(sext i32 %stride to i64)}<nsw>
375 %index64 = sext i32 %index32 to i64
376
377 %ptr = getelementptr inbounds float, float* %input, i64 %index64
378 %nexti = add nsw i32 %i, 1
379 %f = load float, float* %ptr, align 4
380 %exitcond = icmp eq i32 %nexti, %numIterations
381 br i1 %exitcond, label %exit, label %loop
382exit:
383 ret void
384}
385
386; Example where a mul should get the nuw flag.
387define void @test-mul-nuw(float* %input, i32 %stride, i32 %numIterations) {
388; CHECK-LABEL: @test-mul-nuw
389entry:
390 br label %loop
391loop:
392 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
393
394; CHECK: %index32 =
395; CHECK: --> {0,+,%stride}<nuw>
396 %index32 = mul nuw i32 %i, %stride
397
398 %ptr = getelementptr inbounds float, float* %input, i32 %index32
399 %nexti = add nuw i32 %i, 1
400 %f = load float, float* %ptr, align 4
401 %exitcond = icmp eq i32 %nexti, %numIterations
402 br i1 %exitcond, label %exit, label %loop
403
404exit:
405 ret void
406}
407
408; Example where a shl should get the nsw flag, so that a sext can be
409; distributed over the shl.
410define void @test-shl-nsw(float* %input, i32 %start, i32 %numIterations) {
411; CHECK-LABEL: @test-shl-nsw
412entry:
413 br label %loop
414loop:
415 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
416
417; CHECK: %index32 =
418; CHECK: --> {(256 * %start),+,256}<nsw>
419 %index32 = shl nsw i32 %i, 8
420
421; CHECK: %index64 =
422; CHECK: --> {(sext i32 (256 * %start) to i64),+,256}<nsw>
423 %index64 = sext i32 %index32 to i64
424
425 %ptr = getelementptr inbounds float, float* %input, i64 %index64
426 %nexti = add nsw i32 %i, 1
427 %f = load float, float* %ptr, align 4
428 %exitcond = icmp eq i32 %nexti, %numIterations
429 br i1 %exitcond, label %exit, label %loop
430exit:
431 ret void
432}
433
434; Example where a shl should get the nuw flag.
435define void @test-shl-nuw(float* %input, i32 %numIterations) {
436; CHECK-LABEL: @test-shl-nuw
437entry:
438 br label %loop
439loop:
440 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
441
442; CHECK: %index32 =
443; CHECK: --> {0,+,512}<nuw>
444 %index32 = shl nuw i32 %i, 9
445
446 %ptr = getelementptr inbounds float, float* %input, i32 %index32
447 %nexti = add nuw i32 %i, 1
448 %f = load float, float* %ptr, align 4
449 %exitcond = icmp eq i32 %nexti, %numIterations
450 br i1 %exitcond, label %exit, label %loop
451
452exit:
453 ret void
454}
455
456; Example where a sub should *not* get the nsw flag, because of how
457; scalar evolution represents A - B as A + (-B) and -B can wrap even
458; in cases where A - B does not.
459define void @test-sub-no-nsw(float* %input, i32 %start, i32 %sub, i32 %numIterations) {
460; CHECK-LABEL: @test-sub-no-nsw
461entry:
462 br label %loop
463loop:
464 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
465
466; CHECK: %index32 =
467; CHECK: --> {((-1 * %sub) + %start),+,1}<nw>
468 %index32 = sub nsw i32 %i, %sub
469 %index64 = sext i32 %index32 to i64
470
471 %ptr = getelementptr inbounds float, float* %input, i64 %index64
472 %nexti = add nsw i32 %i, 1
473 %f = load float, float* %ptr, align 4
474 %exitcond = icmp eq i32 %nexti, %numIterations
475 br i1 %exitcond, label %exit, label %loop
476exit:
477 ret void
478}
479
480; Example where a sub should get the nsw flag as the RHS cannot be the
481; minimal signed value.
482define void @test-sub-nsw(float* %input, i32 %start, i32 %sub, i32 %numIterations) {
483; CHECK-LABEL: @test-sub-nsw
484entry:
485 %halfsub = ashr i32 %sub, 1
486 br label %loop
487loop:
488 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
489
490; CHECK: %index32 =
491; CHECK: --> {((-1 * %halfsub)<nsw> + %start),+,1}<nsw>
492 %index32 = sub nsw i32 %i, %halfsub
493 %index64 = sext i32 %index32 to i64
494
495 %ptr = getelementptr inbounds float, float* %input, i64 %index64
496 %nexti = add nsw i32 %i, 1
497 %f = load float, float* %ptr, align 4
498 %exitcond = icmp eq i32 %nexti, %numIterations
499 br i1 %exitcond, label %exit, label %loop
500exit:
501 ret void
502}
503
504; Example where a sub should get the nsw flag, since the LHS is non-negative,
505; which implies that the RHS cannot be the minimal signed value.
506define void @test-sub-nsw-lhs-non-negative(float* %input, i32 %sub, i32 %numIterations) {
507; CHECK-LABEL: @test-sub-nsw-lhs-non-negative
508entry:
509 br label %loop
510loop:
511 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
512
513; CHECK: %index32 =
514; CHECK: --> {(-1 * %sub),+,1}<nsw>
515 %index32 = sub nsw i32 %i, %sub
516
517; CHECK: %index64 =
518; CHECK: --> {(sext i32 (-1 * %sub) to i64),+,1}<nsw>
519 %index64 = sext i32 %index32 to i64
520
521 %ptr = getelementptr inbounds float, float* %input, i64 %index64
522 %nexti = add nsw i32 %i, 1
523 %f = load float, float* %ptr, align 4
524 %exitcond = icmp eq i32 %nexti, %numIterations
525 br i1 %exitcond, label %exit, label %loop
526exit:
527 ret void
528}
529
530; Two adds with a sub in the middle and the sub should have nsw. There is
531; a special case for sequential adds/subs and this test covers that. We have to
532; put the final add first in the program since otherwise the special case
533; is not triggered, hence the strange basic block ordering.
534define void @test-sub-with-add(float* %input, i32 %offset, i32 %numIterations) {
535; CHECK-LABEL: @test-sub-with-add
536entry:
537 br label %loop
538loop2:
539; CHECK: %seq =
540; CHECK: --> {(2 + (-1 * %offset)),+,1}<nw>
541 %seq = add nsw nuw i32 %index32, 1
542 %exitcond = icmp eq i32 %nexti, %numIterations
543 br i1 %exitcond, label %exit, label %loop
544
545loop:
546 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
547
548 %j = add nsw i32 %i, 1
549; CHECK: %index32 =
550; CHECK: --> {(1 + (-1 * %offset)),+,1}<nsw>
551 %index32 = sub nsw i32 %j, %offset
552
553 %ptr = getelementptr inbounds float, float* %input, i32 %index32
554 %nexti = add nsw i32 %i, 1
555 store float 1.0, float* %ptr, align 4
556 br label %loop2
557exit:
558 ret void
559}
560
561
562; Subtraction of two recurrences. The addition in the SCEV that this
563; maps to is NSW, but the negation of the RHS does not since that
564; recurrence could be the most negative representable value.
565define void @subrecurrences(i32 %outer_l, i32 %inner_l, i32 %val) {
566; CHECK-LABEL: @subrecurrences
567 entry:
568 br label %outer
569
570outer:
571 %o_idx = phi i32 [ 0, %entry ], [ %o_idx.inc, %outer.be ]
572 %o_idx.inc = add nsw i32 %o_idx, 1
573 %cond = icmp eq i32 %o_idx, %val
574 br i1 %cond, label %inner, label %outer.be
575
576inner:
577 %i_idx = phi i32 [ 0, %outer ], [ %i_idx.inc, %inner ]
578 %i_idx.inc = add nsw i32 %i_idx, 1
579; CHECK: %v =
580; CHECK-NEXT: --> {{[{][{]}}-1,+,-1}<nw><%outer>,+,1}<nsw><%inner>
581 %v = sub nsw i32 %i_idx, %o_idx.inc
582 %forub = udiv i32 1, %v
583 %cond2 = icmp eq i32 %i_idx, %inner_l
584 br i1 %cond2, label %outer.be, label %inner
585
586outer.be:
587 %cond3 = icmp eq i32 %o_idx, %outer_l
588 br i1 %cond3, label %exit, label %outer
589
590exit:
591 ret void
592}