1; RUN: opt < %s -basicaa -licm -S | FileCheck %s
2
3declare i32 @strlen(i8*) readonly
4
5declare void @foo()
6
7; Sink readonly function.
8define i32 @test1(i8* %P) {
9	br label %Loop
10
11Loop:		; preds = %Loop, %0
12	%A = call i32 @strlen( i8* %P ) readonly
13	br i1 false, label %Loop, label %Out
14
15Out:		; preds = %Loop
16	ret i32 %A
17; CHECK-LABEL: @test1(
18; CHECK: Out:
19; CHECK-NEXT: call i32 @strlen
20; CHECK-NEXT: ret i32 %A
21}
22
23declare double @sin(double) readnone
24
25; Sink readnone function out of loop with unknown memory behavior.
26define double @test2(double %X) {
27	br label %Loop
28
29Loop:		; preds = %Loop, %0
30	call void @foo( )
31	%A = call double @sin( double %X ) readnone
32	br i1 true, label %Loop, label %Out
33
34Out:		; preds = %Loop
35	ret double %A
36; CHECK-LABEL: @test2(
37; CHECK: Out:
38; CHECK-NEXT: call double @sin
39; CHECK-NEXT: ret double %A
40}
41
42; This testcase checks to make sure the sinker does not cause problems with
43; critical edges.
44define void @test3() {
45Entry:
46	br i1 false, label %Loop, label %Exit
47Loop:
48	%X = add i32 0, 1
49	br i1 false, label %Loop, label %Exit
50Exit:
51	%Y = phi i32 [ 0, %Entry ], [ %X, %Loop ]
52	ret void
53
54; CHECK-LABEL: @test3(
55; CHECK:     Exit.loopexit:
56; CHECK-NEXT:  %X = add i32 0, 1
57; CHECK-NEXT:  br label %Exit
58
59}
60
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.
64;
65define i32 @test4(i32 %N) {
66Entry:
67	br label %Loop
68Loop:		; 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
75Out:		; preds = %Loop
76	ret i32 %tmp.7
77; CHECK-LABEL: @test4(
78; CHECK:     Out:
79; CHECK-NEXT:  mul i32 %N, %N_addr.0.pn
80; CHECK-NEXT:  sub i32 %tmp.6, %N
81; CHECK-NEXT:  ret i32
82}
83
84; To reduce register pressure, if a load is hoistable out of the loop, and the
85; result of the load is only used outside of the loop, sink the load instead of
86; hoisting it!
87;
88@X = global i32 5		; <i32*> [#uses=1]
89
90define i32 @test5(i32 %N) {
91Entry:
92	br label %Loop
93Loop:		; preds = %Loop, %Entry
94	%N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]
95	%tmp.6 = load i32* @X		; <i32> [#uses=1]
96	%dec = add i32 %N_addr.0.pn, -1		; <i32> [#uses=1]
97	%tmp.1 = icmp ne i32 %N_addr.0.pn, 1		; <i1> [#uses=1]
98	br i1 %tmp.1, label %Loop, label %Out
99Out:		; preds = %Loop
100	ret i32 %tmp.6
101; CHECK-LABEL: @test5(
102; CHECK:     Out:
103; CHECK-NEXT:  %tmp.6 = load i32* @X
104; CHECK-NEXT:  ret i32 %tmp.6
105}
106
107
108
109; The loop sinker was running from the bottom of the loop to the top, causing
110; it to miss opportunities to sink instructions that depended on sinking other
111; instructions from the loop.  Instead they got hoisted, which is better than
112; leaving them in the loop, but increases register pressure pointlessly.
113
114	%Ty = type { i32, i32 }
115@X2 = external global %Ty
116
117define i32 @test6() {
118	br label %Loop
119Loop:
120	%dead = getelementptr %Ty* @X2, i64 0, i32 0
121	%sunk2 = load i32* %dead
122	br i1 false, label %Loop, label %Out
123Out:		; preds = %Loop
124	ret i32 %sunk2
125; CHECK-LABEL: @test6(
126; CHECK:     Out:
127; CHECK-NEXT:  %dead = getelementptr %Ty* @X2, i64 0, i32 0
128; CHECK-NEXT:  %sunk2 = load i32* %dead
129; CHECK-NEXT:  ret i32 %sunk2
130}
131
132
133
134; This testcase ensures that we can sink instructions from loops with
135; multiple exits.
136;
137define i32 @test7(i32 %N, i1 %C) {
138Entry:
139	br label %Loop
140Loop:		; preds = %ContLoop, %Entry
141	%N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
142	%tmp.6 = mul i32 %N, %N_addr.0.pn
143	%tmp.7 = sub i32 %tmp.6, %N		; <i32> [#uses=2]
144	%dec = add i32 %N_addr.0.pn, -1		; <i32> [#uses=1]
145	br i1 %C, label %ContLoop, label %Out1
146ContLoop:
147	%tmp.1 = icmp ne i32 %N_addr.0.pn, 1
148	br i1 %tmp.1, label %Loop, label %Out2
149Out1:		; preds = %Loop
150	ret i32 %tmp.7
151Out2:		; preds = %ContLoop
152	ret i32 %tmp.7
153; CHECK-LABEL: @test7(
154; CHECK:     Out1:
155; CHECK-NEXT:  mul i32 %N, %N_addr.0.pn
156; CHECK-NEXT:  sub i32 %tmp.6, %N
157; CHECK-NEXT:  ret
158; CHECK:     Out2:
159; CHECK-NEXT:  mul i32 %N, %N_addr.0.pn
160; CHECK-NEXT:  sub i32 %tmp.6
161; CHECK-NEXT:  ret
162}
163
164
165; This testcase checks to make sure we can sink values which are only live on
166; some exits out of the loop, and that we can do so without breaking dominator
167; info.
168define i32 @test8(i1 %C1, i1 %C2, i32* %P, i32* %Q) {
169Entry:
170	br label %Loop
171Loop:		; preds = %Cont, %Entry
172	br i1 %C1, label %Cont, label %exit1
173Cont:		; preds = %Loop
174	%X = load i32* %P		; <i32> [#uses=2]
175	store i32 %X, i32* %Q
176	%V = add i32 %X, 1		; <i32> [#uses=1]
177	br i1 %C2, label %Loop, label %exit2
178exit1:		; preds = %Loop
179	ret i32 0
180exit2:		; preds = %Cont
181	ret i32 %V
182; CHECK-LABEL: @test8(
183; CHECK:     exit1:
184; CHECK-NEXT:  ret i32 0
185; CHECK:     exit2:
186; CHECK-NEXT:  %V = add i32 %X, 1
187; CHECK-NEXT:  ret i32 %V
188}
189
190
191define void @test9() {
192loopentry.2.i:
193	br i1 false, label %no_exit.1.i.preheader, label %loopentry.3.i.preheader
194no_exit.1.i.preheader:		; preds = %loopentry.2.i
195	br label %no_exit.1.i
196no_exit.1.i:		; preds = %endif.8.i, %no_exit.1.i.preheader
197	br i1 false, label %return.i, label %endif.8.i
198endif.8.i:		; preds = %no_exit.1.i
199	%inc.1.i = add i32 0, 1		; <i32> [#uses=1]
200	br i1 false, label %no_exit.1.i, label %loopentry.3.i.preheader.loopexit
201loopentry.3.i.preheader.loopexit:		; preds = %endif.8.i
202	br label %loopentry.3.i.preheader
203loopentry.3.i.preheader:		; preds = %loopentry.3.i.preheader.loopexit, %loopentry.2.i
204	%arg_num.0.i.ph13000 = phi i32 [ 0, %loopentry.2.i ], [ %inc.1.i, %loopentry.3.i.preheader.loopexit ]		; <i32> [#uses=0]
205	ret void
206return.i:		; preds = %no_exit.1.i
207	ret void
208
209; CHECK-LABEL: @test9(
210; CHECK: loopentry.3.i.preheader.loopexit:
211; CHECK-NEXT:  %inc.1.i = add i32 0, 1
212; CHECK-NEXT:  br label %loopentry.3.i.preheader
213}
214
215
216; Potentially trapping instructions may be sunk as long as they are guaranteed
217; to be executed.
218define i32 @test10(i32 %N) {
219Entry:
220	br label %Loop
221Loop:		; preds = %Loop, %Entry
222	%N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]		; <i32> [#uses=3]
223	%tmp.6 = sdiv i32 %N, %N_addr.0.pn		; <i32> [#uses=1]
224	%dec = add i32 %N_addr.0.pn, -1		; <i32> [#uses=1]
225	%tmp.1 = icmp ne i32 %N_addr.0.pn, 0		; <i1> [#uses=1]
226	br i1 %tmp.1, label %Loop, label %Out
227Out:		; preds = %Loop
228	ret i32 %tmp.6
229
230; CHECK-LABEL: @test10(
231; CHECK: Out:
232; CHECK-NEXT:  %tmp.6 = sdiv i32 %N, %N_addr.0.pn
233; CHECK-NEXT:  ret i32 %tmp.6
234}
235
236; Should delete, not sink, dead instructions.
237define void @test11() {
238	br label %Loop
239Loop:
240	%dead = getelementptr %Ty* @X2, i64 0, i32 0
241	br i1 false, label %Loop, label %Out
242Out:
243	ret void
244; CHECK-LABEL: @test11(
245; CHECK:     Out:
246; CHECK-NEXT:  ret void
247}
248
249
250