1; RUN: opt -S -basic-aa -licm -enable-mssa-loop-dependency=false %s -enable-new-pm=0 | FileCheck -check-prefixes=CHECK,AST %s
2; RUN: opt -S -basic-aa -licm -enable-mssa-loop-dependency=true %s -enable-new-pm=0 | FileCheck  -check-prefixes=CHECK,MSSA %s
3; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck -check-prefixes=CHECK,AST %s
4; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop-mssa(licm)' < %s -S | FileCheck -check-prefixes=CHECK,MSSA %s
5
6define void @test(i32* %loc) {
7; CHECK-LABEL: @test
8; CHECK-LABEL: entry:
9; CHECK: store i32 0, i32* %loc
10; CHECK-LABEL: loop:
11entry:
12  br label %loop
13
14loop:
15  %iv = phi i32 [0, %entry], [%iv.next, %loop]
16  store i32 0, i32* %loc
17  %iv.next = add i32 %iv, 1
18  %cmp = icmp slt i32 %iv, 200
19  br i1 %cmp, label %loop, label %exit
20
21exit:
22  ret void
23}
24
25define void @test_multiexit(i32* %loc, i1 %earlycnd) {
26; CHECK-LABEL: @test_multiexit
27; CHECK-LABEL: entry:
28; CHECK: store i32 0, i32* %loc
29; CHECK-LABEL: loop:
30entry:
31  br label %loop
32
33loop:
34  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
35  store i32 0, i32* %loc
36  %iv.next = add i32 %iv, 1
37  br i1 %earlycnd, label %exit1, label %backedge
38
39backedge:
40  %cmp = icmp slt i32 %iv, 200
41  br i1 %cmp, label %loop, label %exit2
42
43exit1:
44  ret void
45exit2:
46  ret void
47}
48
49define i32* @false_negative_2use(i32* %loc) {
50; CHECK-LABEL: @false_negative_2use
51; AST-LABEL: exit:
52; AST: store i32 0, i32* %loc
53; MSSA-LABEL: entry:
54; MSSA: store i32 0, i32* %loc
55; MSSA-LABEL: loop:
56entry:
57  br label %loop
58
59loop:
60  %iv = phi i32 [0, %entry], [%iv.next, %loop]
61  store i32 0, i32* %loc
62  %iv.next = add i32 %iv, 1
63  %cmp = icmp slt i32 %iv, 200
64  br i1 %cmp, label %loop, label %exit
65
66exit:
67  ret i32* %loc
68}
69
70define void @neg_lv_value(i32* %loc) {
71; CHECK-LABEL: @neg_lv_value
72; CHECK-LABEL: exit:
73; CHECK: store i32 %iv.lcssa, i32* %loc
74entry:
75  br label %loop
76
77loop:
78  %iv = phi i32 [0, %entry], [%iv.next, %loop]
79  store i32 %iv, i32* %loc
80  %iv.next = add i32 %iv, 1
81  %cmp = icmp slt i32 %iv, 200
82  br i1 %cmp, label %loop, label %exit
83
84exit:
85  ret void
86}
87
88define void @neg_lv_addr(i32* %loc) {
89; CHECK-LABEL: @neg_lv_addr
90; CHECK-LABEL: loop:
91; CHECK: store i32 0, i32* %p
92; CHECK-LABEL: exit:
93entry:
94  br label %loop
95
96loop:
97  %iv = phi i32 [0, %entry], [%iv.next, %loop]
98  %p = getelementptr i32, i32* %loc, i32 %iv
99  store i32 0, i32* %p
100  %iv.next = add i32 %iv, 1
101  %cmp = icmp slt i32 %iv, 200
102  br i1 %cmp, label %loop, label %exit
103
104exit:
105  ret void
106}
107
108define void @neg_mod(i32* %loc) {
109; CHECK-LABEL: @neg_mod
110; CHECK-LABEL: exit:
111; CHECK: store i32 %iv.lcssa, i32* %loc
112entry:
113  br label %loop
114
115loop:
116  %iv = phi i32 [0, %entry], [%iv.next, %loop]
117  store i32 0, i32* %loc
118  store i32 %iv, i32* %loc
119  %iv.next = add i32 %iv, 1
120  %cmp = icmp slt i32 %iv, 200
121  br i1 %cmp, label %loop, label %exit
122
123exit:
124  ret void
125}
126
127; Hoisting the store is actually valid here, as it dominates the load.
128define void @neg_ref(i32* %loc) {
129; CHECK-LABEL: @neg_ref
130; CHECK-LABEL: exit1:
131; CHECK: store i32 0, i32* %loc
132; CHECK-LABEL: exit2:
133; CHECK: store i32 0, i32* %loc
134entry:
135  br label %loop
136
137loop:
138  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
139  store i32 0, i32* %loc
140  %v = load i32, i32* %loc
141  %earlycnd = icmp eq i32 %v, 198
142  br i1 %earlycnd, label %exit1, label %backedge
143
144backedge:
145  %iv.next = add i32 %iv, 1
146  %cmp = icmp slt i32 %iv, 200
147  br i1 %cmp, label %loop, label %exit2
148
149exit1:
150  ret void
151exit2:
152  ret void
153}
154
155; Hoisting the store here leads to a miscompile.
156define void @neg_ref2(i32* %loc) {
157; CHECK-LABEL: @neg_ref2
158; CHECK-LABEL: exit1:
159; CHECK: store i32 0, i32* %loc
160; CHECK-LABEL: exit2:
161; CHECK: store i32 0, i32* %loc
162entry:
163  store i32 198, i32* %loc
164  br label %loop
165
166loop:
167  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
168  %v = load i32, i32* %loc
169  store i32 0, i32* %loc
170  %earlycnd = icmp eq i32 %v, 198
171  br i1 %earlycnd, label %exit1, label %backedge
172
173backedge:
174  %iv.next = add i32 %iv, 1
175  %cmp = icmp slt i32 %iv, 200
176  br i1 %cmp, label %loop, label %exit2
177
178exit1:
179  ret void
180exit2:
181  ret void
182}
183
184declare void @modref()
185
186define void @neg_modref(i32* %loc) {
187; CHECK-LABEL: @neg_modref
188; CHECK-LABEL: loop:
189; CHECK: store i32 0, i32* %loc
190; CHECK-LABEL: exit:
191entry:
192  br label %loop
193
194loop:
195  %iv = phi i32 [0, %entry], [%iv.next, %loop]
196  store i32 0, i32* %loc
197  call void @modref()
198  %iv.next = add i32 %iv, 1
199  %cmp = icmp slt i32 %iv, 200
200  br i1 %cmp, label %loop, label %exit
201
202exit:
203  ret void
204}
205
206define void @neg_fence(i32* %loc) {
207; CHECK-LABEL: @neg_fence
208; CHECK-LABEL: loop:
209; CHECK: store i32 0, i32* %loc
210; CHECK-LABEL: exit:
211entry:
212  br label %loop
213
214loop:
215  %iv = phi i32 [0, %entry], [%iv.next, %loop]
216  store i32 0, i32* %loc
217  fence seq_cst
218  %iv.next = add i32 %iv, 1
219  %cmp = icmp slt i32 %iv, 200
220  br i1 %cmp, label %loop, label %exit
221
222exit:
223  ret void
224}
225
226define void @neg_volatile(i32* %loc) {
227; CHECK-LABEL: @neg_volatile
228; CHECK-LABEL: loop:
229; CHECK: store volatile i32 0, i32* %loc
230; CHECK-LABEL: exit:
231entry:
232  br label %loop
233
234loop:
235  %iv = phi i32 [0, %entry], [%iv.next, %loop]
236  store volatile i32 0, i32* %loc
237  %iv.next = add i32 %iv, 1
238  %cmp = icmp slt i32 %iv, 200
239  br i1 %cmp, label %loop, label %exit
240
241exit:
242  ret void
243}
244
245define void @neg_release(i32* %loc) {
246; CHECK-LABEL: @neg_release
247; CHECK-LABEL: loop:
248; CHECK: store atomic i32 0, i32* %loc release, align 4
249; CHECK-LABEL: exit:
250entry:
251  br label %loop
252
253loop:
254  %iv = phi i32 [0, %entry], [%iv.next, %loop]
255  store atomic i32 0, i32* %loc release, align 4
256  %iv.next = add i32 %iv, 1
257  %cmp = icmp slt i32 %iv, 200
258  br i1 %cmp, label %loop, label %exit
259
260exit:
261  ret void
262}
263
264define void @neg_seq_cst(i32* %loc) {
265; CHECK-LABEL: @neg_seq_cst
266; CHECK-LABEL: loop:
267; CHECK: store atomic i32 0, i32* %loc seq_cst, align 4
268; CHECK-LABEL: exit:
269entry:
270  br label %loop
271
272loop:
273  %iv = phi i32 [0, %entry], [%iv.next, %loop]
274  store atomic i32 0, i32* %loc seq_cst, align 4
275  %iv.next = add i32 %iv, 1
276  %cmp = icmp slt i32 %iv, 200
277  br i1 %cmp, label %loop, label %exit
278
279exit:
280  ret void
281}
282
283declare void @maythrow() inaccessiblememonly
284
285define void @neg_early_exit(i32* %loc) {
286; CHECK-LABEL: @neg_early_exit
287; CHECK-LABEL: body:
288; CHECK: store i32 0, i32* %loc
289; CHECK-LABEL: exit:
290entry:
291  br label %loop
292
293loop:
294  %iv = phi i32 [0, %entry], [%iv.next, %body]
295  %is_null = icmp eq i32* %loc, null
296  br i1 %is_null, label %exit, label %body
297body:
298  call void @maythrow()
299  store i32 0, i32* %loc
300  %iv.next = add i32 %iv, 1
301  %cmp = icmp slt i32 %iv, 200
302  br i1 %cmp, label %loop, label %exit
303
304exit:
305  ret void
306}
307
308define void @neg_early_throw(i32* %loc) {
309; CHECK-LABEL: @neg_early_throw
310; CHECK-LABEL: loop:
311; CHECK: store i32 0, i32* %loc
312; CHECK-LABEL: exit:
313entry:
314  br label %loop
315
316loop:
317  %iv = phi i32 [0, %entry], [%iv.next, %loop]
318  call void @maythrow()
319  store i32 0, i32* %loc
320  %iv.next = add i32 %iv, 1
321  %cmp = icmp slt i32 %iv, 200
322  br i1 %cmp, label %loop, label %exit
323
324exit:
325  ret void
326}
327
328define void @test_late_throw(i32* %loc) {
329; CHECK-LABEL: @test_late_throw
330; CHECK-LABEL: entry:
331; CHECK: store i32 0, i32* %loc
332; CHECK-LABEL: loop:
333entry:
334  br label %loop
335
336loop:
337  %iv = phi i32 [0, %entry], [%iv.next, %loop]
338  store i32 0, i32* %loc
339  call void @maythrow()
340  %iv.next = add i32 %iv, 1
341  %cmp = icmp slt i32 %iv, 200
342  br i1 %cmp, label %loop, label %exit
343
344exit:
345  ret void
346}
347
348; TODO: could validly hoist the store here since we know what value
349; the load must observe.
350define i32 @test_dominated_read(i32* %loc) {
351; CHECK-LABEL: @test_dominated_read
352; MSSA-LABEL: entry:
353; MSSA: store i32 0, i32* %loc
354; MSSA-LABEL: loop:
355; AST-LABEL: exit:
356; AST:  store i32 0, i32* %loc
357entry:
358  br label %loop
359
360loop:
361  %iv = phi i32 [0, %entry], [%iv.next, %loop]
362  store i32 0, i32* %loc
363  %reload = load i32, i32* %loc
364  %iv.next = add i32 %iv, 1
365  %cmp = icmp slt i32 %iv, 200
366  br i1 %cmp, label %loop, label %exit
367
368exit:
369  ret i32 %reload
370}
371
372; TODO: could validly hoist the store since we already hoisted the load and
373; it's no longer in the loop.
374define i32 @test_dominating_read(i32* %loc) {
375; CHECK-LABEL: @test_dominating_read
376; CHECK-LABEL: exit:
377; CHECK: store i32 0, i32* %loc
378entry:
379  br label %loop
380
381loop:
382  %iv = phi i32 [0, %entry], [%iv.next, %loop]
383  %reload = load i32, i32* %loc
384  store i32 0, i32* %loc
385  %iv.next = add i32 %iv, 1
386  %cmp = icmp slt i32 %iv, 200
387  br i1 %cmp, label %loop, label %exit
388
389exit:
390  ret i32 %reload
391}
392
393declare void @readonly() readonly
394
395; TODO: can legally hoist since value read by call is known
396define void @test_dominated_readonly(i32* %loc) {
397; CHECK-LABEL: @test_dominated_readonly
398; CHECK-LABEL: loop:
399; CHECK: store i32 0, i32* %loc
400; CHECK-LABEL: exit:
401entry:
402  br label %loop
403
404loop:
405  %iv = phi i32 [0, %entry], [%iv.next, %loop]
406  store i32 0, i32* %loc
407  call void @readonly()
408  %iv.next = add i32 %iv, 1
409  %cmp = icmp slt i32 %iv, 200
410  br i1 %cmp, label %loop, label %exit
411
412exit:
413  ret void
414}
415
416; While technically possible to hoist the store to %loc, this runs across
417; a funemental limitation of alias sets since both stores and the call are
418; within the same alias set and we can't distinguish them cheaply.
419define void @test_aliasset_fn(i32* %loc, i32* %loc2) {
420; CHECK-LABEL: @test_aliasset_fn
421; CHECK-LABEL: loop:
422; CHECK: store i32 0, i32* %loc
423; CHECK-LABEL: exit:
424entry:
425  br label %loop
426
427loop:
428  %iv = phi i32 [0, %entry], [%iv.next, %loop]
429  store i32 0, i32* %loc
430  call void @readonly()
431  store i32 %iv, i32* %loc2
432  %iv.next = add i32 %iv, 1
433  %cmp = icmp slt i32 %iv, 200
434  br i1 %cmp, label %loop, label %exit
435
436exit:
437  ret void
438}
439
440
441; If we can't tell if the value is read before the write, we can't hoist the
442; write over the potential read (since we don't know the value read)
443define void @neg_may_read(i32* %loc, i1 %maybe) {
444; CHECK-LABEL: @neg_may_read
445; CHECK-LABEL: loop:
446; CHECK: store i32 0, i32* %loc
447; CHECK-LABEL: exit:
448entry:
449  br label %loop
450
451loop:
452  %iv = phi i32 [0, %entry], [%iv.next, %merge]
453  ;; maybe is a placeholder for an unanalyzable condition
454  br i1 %maybe, label %taken, label %merge
455taken:
456  call void @readonly()
457  br label %merge
458merge:
459  store i32 0, i32* %loc
460  %iv.next = add i32 %iv, 1
461  %cmp = icmp slt i32 %iv, 200
462  br i1 %cmp, label %loop, label %exit
463
464exit:
465  ret void
466}
467