source: icGREP/icgrep-devel/llvm-3.8.0.src/test/Analysis/ScalarEvolution/flags-from-poison.ll @ 5027

Last change on this file since 5027 was 5027, checked in by cameron, 3 years ago

Upgrade to llvm 3.8

File size: 16.5 KB
Line 
1; 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}
359
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}
Note: See TracBrowser for help on using the repository browser.