1 ; RUN: opt < %s -basicaa -licm -S | FileCheck %s
3 declare i32 @strlen(i8*) readonly
7 ; Sink readonly function.
8 define i32 @test1(i8* %P) {
11 Loop: ; preds = %Loop, %0
12 %A = call i32 @strlen( i8* %P ) readonly
13 br i1 false, label %Loop, label %Out
17 ; CHECK-LABEL: @test1(
19 ; CHECK-NEXT: call i32 @strlen
20 ; CHECK-NEXT: ret i32 %A
23 declare double @sin(double) readnone
25 ; Sink readnone function out of loop with unknown memory behavior.
26 define double @test2(double %X) {
29 Loop: ; preds = %Loop, %0
31 %A = call double @sin( double %X ) readnone
32 br i1 true, label %Loop, label %Out
36 ; CHECK-LABEL: @test2(
38 ; CHECK-NEXT: call double @sin
39 ; CHECK-NEXT: ret double %A
42 ; This testcase checks to make sure the sinker does not cause problems with
44 define void @test3() {
46 br i1 false, label %Loop, label %Exit
49 br i1 false, label %Loop, label %Exit
51 %Y = phi i32 [ 0, %Entry ], [ %X, %Loop ]
54 ; CHECK-LABEL: @test3(
55 ; CHECK: Exit.loopexit:
56 ; CHECK-NEXT: %X.le = add i32 0, 1
57 ; CHECK-NEXT: br label %Exit
61 ; If the result of an instruction is only used outside of the loop, sink
62 ; the instruction to the exit blocks instead of executing it on every
63 ; iteration of the loop.
65 define i32 @test4(i32 %N) {
68 Loop: ; preds = %Loop, %Entry
69 %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]
70 %tmp.6 = mul i32 %N, %N_addr.0.pn ; <i32> [#uses=1]
71 %tmp.7 = sub i32 %tmp.6, %N ; <i32> [#uses=1]
72 %dec = add i32 %N_addr.0.pn, -1 ; <i32> [#uses=1]
73 %tmp.1 = icmp ne i32 %N_addr.0.pn, 1 ; <i1> [#uses=1]
74 br i1 %tmp.1, label %Loop, label %Out
77 ; CHECK-LABEL: @test4(
79 ; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
80 ; CHECK-NEXT: mul i32 %N, %[[LCSSAPHI]]
81 ; CHECK-NEXT: sub i32 %tmp.6.le, %N
85 ; To reduce register pressure, if a load is hoistable out of the loop, and the
86 ; result of the load is only used outside of the loop, sink the load instead of
89 @X = global i32 5 ; <i32*> [#uses=1]
91 define i32 @test5(i32 %N) {
94 Loop: ; preds = %Loop, %Entry
95 %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]
96 %tmp.6 = load i32, i32* @X ; <i32> [#uses=1]
97 %dec = add i32 %N_addr.0.pn, -1 ; <i32> [#uses=1]
98 %tmp.1 = icmp ne i32 %N_addr.0.pn, 1 ; <i1> [#uses=1]
99 br i1 %tmp.1, label %Loop, label %Out
102 ; CHECK-LABEL: @test5(
104 ; CHECK-NEXT: %tmp.6.le = load i32, i32* @X
105 ; CHECK-NEXT: ret i32 %tmp.6.le
110 ; The loop sinker was running from the bottom of the loop to the top, causing
111 ; it to miss opportunities to sink instructions that depended on sinking other
112 ; instructions from the loop. Instead they got hoisted, which is better than
113 ; leaving them in the loop, but increases register pressure pointlessly.
115 %Ty = type { i32, i32 }
116 @X2 = external global %Ty
118 define i32 @test6() {
121 %dead = getelementptr %Ty, %Ty* @X2, i64 0, i32 0
122 %sunk2 = load i32, i32* %dead
123 br i1 false, label %Loop, label %Out
126 ; CHECK-LABEL: @test6(
128 ; CHECK-NEXT: %dead.le = getelementptr %Ty, %Ty* @X2, i64 0, i32 0
129 ; CHECK-NEXT: %sunk2.le = load i32, i32* %dead.le
130 ; CHECK-NEXT: ret i32 %sunk2.le
135 ; This testcase ensures that we can sink instructions from loops with
138 define i32 @test7(i32 %N, i1 %C) {
141 Loop: ; preds = %ContLoop, %Entry
142 %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
143 %tmp.6 = mul i32 %N, %N_addr.0.pn
144 %tmp.7 = sub i32 %tmp.6, %N ; <i32> [#uses=2]
145 %dec = add i32 %N_addr.0.pn, -1 ; <i32> [#uses=1]
146 br i1 %C, label %ContLoop, label %Out1
148 %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
149 br i1 %tmp.1, label %Loop, label %Out2
150 Out1: ; preds = %Loop
152 Out2: ; preds = %ContLoop
154 ; CHECK-LABEL: @test7(
156 ; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
157 ; CHECK-NEXT: mul i32 %N, %[[LCSSAPHI]]
158 ; CHECK-NEXT: sub i32 %tmp.6.le, %N
161 ; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
162 ; CHECK-NEXT: mul i32 %N, %[[LCSSAPHI]]
163 ; CHECK-NEXT: sub i32 %tmp.6.le4, %N
168 ; This testcase checks to make sure we can sink values which are only live on
169 ; some exits out of the loop, and that we can do so without breaking dominator
171 define i32 @test8(i1 %C1, i1 %C2, i32* %P, i32* %Q) {
174 Loop: ; preds = %Cont, %Entry
175 br i1 %C1, label %Cont, label %exit1
176 Cont: ; preds = %Loop
177 %X = load i32, i32* %P ; <i32> [#uses=2]
178 store i32 %X, i32* %Q
179 %V = add i32 %X, 1 ; <i32> [#uses=1]
180 br i1 %C2, label %Loop, label %exit2
181 exit1: ; preds = %Loop
183 exit2: ; preds = %Cont
185 ; CHECK-LABEL: @test8(
187 ; CHECK-NEXT: ret i32 0
189 ; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %X
190 ; CHECK-NEXT: %V.le = add i32 %[[LCSSAPHI]], 1
191 ; CHECK-NEXT: ret i32 %V.le
195 define void @test9() {
197 br i1 false, label %no_exit.1.i.preheader, label %loopentry.3.i.preheader
198 no_exit.1.i.preheader: ; preds = %loopentry.2.i
199 br label %no_exit.1.i
200 no_exit.1.i: ; preds = %endif.8.i, %no_exit.1.i.preheader
201 br i1 false, label %return.i, label %endif.8.i
202 endif.8.i: ; preds = %no_exit.1.i
203 %inc.1.i = add i32 0, 1 ; <i32> [#uses=1]
204 br i1 false, label %no_exit.1.i, label %loopentry.3.i.preheader.loopexit
205 loopentry.3.i.preheader.loopexit: ; preds = %endif.8.i
206 br label %loopentry.3.i.preheader
207 loopentry.3.i.preheader: ; preds = %loopentry.3.i.preheader.loopexit, %loopentry.2.i
208 %arg_num.0.i.ph13000 = phi i32 [ 0, %loopentry.2.i ], [ %inc.1.i, %loopentry.3.i.preheader.loopexit ] ; <i32> [#uses=0]
210 return.i: ; preds = %no_exit.1.i
213 ; CHECK-LABEL: @test9(
214 ; CHECK: loopentry.3.i.preheader.loopexit:
215 ; CHECK-NEXT: %inc.1.i.le = add i32 0, 1
216 ; CHECK-NEXT: br label %loopentry.3.i.preheader
220 ; Potentially trapping instructions may be sunk as long as they are guaranteed
222 define i32 @test10(i32 %N) {
225 Loop: ; preds = %Loop, %Entry
226 %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ] ; <i32> [#uses=3]
227 %tmp.6 = sdiv i32 %N, %N_addr.0.pn ; <i32> [#uses=1]
228 %dec = add i32 %N_addr.0.pn, -1 ; <i32> [#uses=1]
229 %tmp.1 = icmp ne i32 %N_addr.0.pn, 0 ; <i1> [#uses=1]
230 br i1 %tmp.1, label %Loop, label %Out
234 ; CHECK-LABEL: @test10(
236 ; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
237 ; CHECK-NEXT: %tmp.6.le = sdiv i32 %N, %[[LCSSAPHI]]
238 ; CHECK-NEXT: ret i32 %tmp.6.le
241 ; Should delete, not sink, dead instructions.
242 define void @test11() {
245 %dead = getelementptr %Ty, %Ty* @X2, i64 0, i32 0
246 br i1 false, label %Loop, label %Out
249 ; CHECK-LABEL: @test11(
251 ; CHECK-NEXT: ret void
254 @c = common global [1 x i32] zeroinitializer, align 4
256 ; Test a *many* way nested loop with multiple exit blocks both of which exit
257 ; multiple loop nests. This exercises LCSSA corner cases.
258 define i32 @PR18753(i1* %a, i1* %b, i1* %c, i1* %d) {
263 %iv = phi i64 [ %iv.next, %l1.latch ], [ 0, %entry ]
264 %arrayidx.i = getelementptr inbounds [1 x i32], [1 x i32]* @c, i64 0, i64 %iv
268 %x0 = load i1, i1* %c, align 4
269 br i1 %x0, label %l1.latch, label %l3.preheader
275 %x1 = load i1, i1* %d, align 4
276 br i1 %x1, label %l2.latch, label %l4.preheader
282 %x2 = load i1, i1* %a
283 br i1 %x2, label %l3.latch, label %l4.body
286 call void @f(i32* %arrayidx.i)
287 %x3 = load i1, i1* %b
288 %l = trunc i64 %iv to i32
289 br i1 %x3, label %l4.latch, label %exit
293 %x4 = load i1, i1* %b, align 4
294 br i1 %x4, label %l4.header, label %exit
303 %iv.next = add nsw i64 %iv, 1
307 %lcssa = phi i32 [ %l, %l4.latch ], [ %l, %l4.body ]
308 ; CHECK-LABEL: @PR18753(
310 ; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i64 [ %iv, %l4.latch ], [ %iv, %l4.body ]
311 ; CHECK-NEXT: %l.le = trunc i64 %[[LCSSAPHI]] to i32
312 ; CHECK-NEXT: ret i32 %l.le
317 ; Can't sink stores out of exit blocks containing indirectbr instructions
318 ; because loop simplify does not create dedicated exits for such blocks. Test
319 ; that by sinking the store from lab21 to lab22, but not further.
320 define void @test12() {
321 ; CHECK-LABEL: @test12
334 br i1 undef, label %lab8, label %lab13
337 br i1 undef, label %lab13, label %lab10
351 ; CHECK: br i1 false, label %lab21, label %lab22
352 store i32 36127957, i32* undef, align 4
353 br i1 undef, label %lab21, label %lab22
358 ; CHECK-NEXT: indirectbr i8* undef
359 indirectbr i8* undef, [label %lab5, label %lab6, label %lab7]
362 ; Test that we don't crash when trying to sink stores and there's no preheader
363 ; available (which is used for creating loads that may be used by the SSA
365 define void @test13() {
366 ; CHECK-LABEL: @test13
370 br i1 undef, label %lab20, label %lab38
376 br i1 undef, label %lab22, label %lab38
385 indirectbr i8* undef, [label %lab60, label %lab38]
390 ; CHECK-NEXT: indirectbr
391 store i32 2145244101, i32* undef, align 4
392 indirectbr i8* undef, [label %lab21, label %lab19]
395 declare void @f(i32*)