1; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
2
3define i32 @test1_factorial(i32 %x) {
4entry:
5	%tmp.1 = icmp sgt i32 %x, 0
6	br i1 %tmp.1, label %then, label %else
7then:
8	%tmp.6 = add i32 %x, -1
9	%recurse = call i32 @test1_factorial( i32 %tmp.6 )
10	%accumulate = mul i32 %recurse, %x
11	ret i32 %accumulate
12else:
13	ret i32 1
14}
15
16; CHECK-LABEL: define i32 @test1_factorial(
17; CHECK: tailrecurse:
18; CHECK: %accumulator.tr = phi i32 [ 1, %entry ], [ %accumulate, %then ]
19; CHECK: then:
20; CHECK-NOT: %recurse
21; CHECK: %accumulate = mul i32 %accumulator.tr, %x.tr
22; CHECK: else:
23; CHECK: %accumulator.ret.tr = mul i32 %accumulator.tr, 1
24; CHECK: ret i32 %accumulator.ret.tr
25
26; This is a more aggressive form of accumulator recursion insertion, which
27; requires noticing that X doesn't change as we perform the tailcall.
28
29define i32 @test2_mul(i32 %x, i32 %y) {
30entry:
31	%tmp.1 = icmp eq i32 %y, 0
32	br i1 %tmp.1, label %return, label %endif
33endif:
34	%tmp.8 = add i32 %y, -1
35	%recurse = call i32 @test2_mul( i32 %x, i32 %tmp.8 )
36	%accumulate = add i32 %recurse, %x
37	ret i32 %accumulate
38return:
39	ret i32 %x
40}
41
42; CHECK-LABEL: define i32 @test2_mul(
43; CHECK: tailrecurse:
44; CHECK: %accumulator.tr = phi i32 [ 0, %entry ], [ %accumulate, %endif ]
45; CHECK: endif:
46; CHECK-NOT: %recurse
47; CHECK: %accumulate = add i32 %accumulator.tr, %x
48; CHECK: return:
49; CHECK: %accumulator.ret.tr = add i32 %accumulator.tr, %x
50; CHECK: ret i32 %accumulator.ret.tr
51
52define i64 @test3_fib(i64 %n) nounwind readnone {
53entry:
54  switch i64 %n, label %bb1 [
55    i64 0, label %bb2
56    i64 1, label %bb2
57  ]
58
59bb1:
60  %0 = add i64 %n, -1
61  %recurse1 = tail call i64 @test3_fib(i64 %0) nounwind
62  %1 = add i64 %n, -2
63  %recurse2 = tail call i64 @test3_fib(i64 %1) nounwind
64  %accumulate = add nsw i64 %recurse2, %recurse1
65  ret i64 %accumulate
66
67bb2:
68  ret i64 %n
69}
70
71; CHECK-LABEL: define i64 @test3_fib(
72; CHECK: tailrecurse:
73; CHECK: %accumulator.tr = phi i64 [ 0, %entry ], [ %accumulate, %bb1 ]
74; CHECK: bb1:
75; CHECK-NOT: %recurse2
76; CHECK: %accumulate = add nsw i64 %accumulator.tr, %recurse1
77; CHECK: bb2:
78; CHECK: %accumulator.ret.tr = add nsw i64 %accumulator.tr, %n.tr
79; CHECK: ret i64 %accumulator.ret.tr
80
81define i32 @test4_base_case_call() local_unnamed_addr {
82entry:
83  %base = call i32 @test4_helper()
84  switch i32 %base, label %sw.default [
85    i32 1, label %cleanup
86    i32 5, label %cleanup
87    i32 7, label %cleanup
88  ]
89
90sw.default:
91  %recurse = call i32 @test4_base_case_call()
92  %accumulate = add nsw i32 %recurse, 1
93  br label %cleanup
94
95cleanup:
96  %retval.0 = phi i32 [ %accumulate, %sw.default ], [ %base, %entry ], [ %base, %entry ], [ %base, %entry ]
97  ret i32 %retval.0
98}
99
100declare i32 @test4_helper()
101
102; CHECK-LABEL: define i32 @test4_base_case_call(
103; CHECK: tailrecurse:
104; CHECK: %accumulator.tr = phi i32 [ 0, %entry ], [ %accumulate, %sw.default ]
105; CHECK: sw.default:
106; CHECK-NOT: %recurse
107; CHECK: %accumulate = add nsw i32 %accumulator.tr, 1
108; CHECK: cleanup:
109; CHECK: %accumulator.ret.tr = add nsw i32 %accumulator.tr, %base
110; CHECK: ret i32 %accumulator.ret.tr
111
112define i32 @test5_base_case_load(i32* nocapture %A, i32 %n) local_unnamed_addr {
113entry:
114  %cmp = icmp eq i32 %n, 0
115  br i1 %cmp, label %if.then, label %if.end
116
117if.then:
118  %base = load i32, i32* %A, align 4
119  ret i32 %base
120
121if.end:
122  %idxprom = zext i32 %n to i64
123  %arrayidx1 = getelementptr inbounds i32, i32* %A, i64 %idxprom
124  %load = load i32, i32* %arrayidx1, align 4
125  %sub = add i32 %n, -1
126  %recurse = tail call i32 @test5_base_case_load(i32* %A, i32 %sub)
127  %accumulate = add i32 %recurse, %load
128  ret i32 %accumulate
129}
130
131; CHECK-LABEL: define i32 @test5_base_case_load(
132; CHECK: tailrecurse:
133; CHECK: %accumulator.tr = phi i32 [ 0, %entry ], [ %accumulate, %if.end ]
134; CHECK: if.then:
135; CHECK: %accumulator.ret.tr = add i32 %accumulator.tr, %base
136; CHECK: ret i32 %accumulator.ret.tr
137; CHECK: if.end:
138; CHECK-NOT: %recurse
139; CHECK: %accumulate = add i32 %accumulator.tr, %load
140
141define i32 @test6_multiple_returns(i32 %x, i32 %y) local_unnamed_addr {
142entry:
143  switch i32 %x, label %default [
144    i32 0, label %case0
145    i32 99, label %case99
146  ]
147
148case0:
149  %helper = call i32 @test6_helper()
150  ret i32 %helper
151
152case99:
153  %sub1 = add i32 %x, -1
154  %recurse1 = call i32 @test6_multiple_returns(i32 %sub1, i32 %y)
155  ret i32 18
156
157default:
158  %sub2 = add i32 %x, -1
159  %recurse2 = call i32 @test6_multiple_returns(i32 %sub2, i32 %y)
160  %accumulate = add i32 %recurse2, %y
161  ret i32 %accumulate
162}
163
164declare i32 @test6_helper()
165
166; CHECK-LABEL: define i32 @test6_multiple_returns(
167; CHECK: tailrecurse:
168; CHECK: %accumulator.tr = phi i32 [ %accumulator.tr, %case99 ], [ 0, %entry ], [ %accumulate, %default ]
169; CHECK: %ret.tr = phi i32 [ poison, %entry ], [ %current.ret.tr, %case99 ], [ %ret.tr, %default ]
170; CHECK: %ret.known.tr = phi i1 [ false, %entry ], [ true, %case99 ], [ %ret.known.tr, %default ]
171; CHECK: case0:
172; CHECK: %accumulator.ret.tr2 = add i32 %accumulator.tr, %helper
173; CHECK: %current.ret.tr1 = select i1 %ret.known.tr, i32 %ret.tr, i32 %accumulator.ret.tr2
174; CHECK: case99:
175; CHECK-NOT: %recurse
176; CHECK: %accumulator.ret.tr = add i32 %accumulator.tr, 18
177; CHECK: %current.ret.tr = select i1 %ret.known.tr, i32 %ret.tr, i32 %accumulator.ret.tr
178; CHECK: default:
179; CHECK-NOT: %recurse
180; CHECK: %accumulate = add i32 %accumulator.tr, %y
181
182; It is only safe to transform one accumulator per function, make sure we don't
183; try to remove more.
184
185define i32 @test7_multiple_accumulators(i32 %a) local_unnamed_addr {
186entry:
187  %tobool = icmp eq i32 %a, 0
188  br i1 %tobool, label %return, label %if.end
189
190if.end:
191  %and = and i32 %a, 1
192  %tobool1 = icmp eq i32 %and, 0
193  %sub = add nsw i32 %a, -1
194  br i1 %tobool1, label %if.end3, label %if.then2
195
196if.then2:
197  %recurse1 = tail call i32 @test7_multiple_accumulators(i32 %sub)
198  %accumulate1 = add nsw i32 %recurse1, 1
199  br label %return
200
201if.end3:
202  %recurse2 = tail call i32 @test7_multiple_accumulators(i32 %sub)
203  %accumulate2 = mul nsw i32 %recurse2, 2
204  br label %return
205
206return:
207  %retval.0 = phi i32 [ %accumulate1, %if.then2 ], [ %accumulate2, %if.end3 ], [ 0, %entry ]
208  ret i32 %retval.0
209}
210
211; CHECK-LABEL: define i32 @test7_multiple_accumulators(
212; CHECK: tailrecurse:
213; CHECK: %accumulator.tr = phi i32 [ 0, %entry ], [ %accumulate1, %if.then2 ]
214; CHECK: if.then2:
215; CHECK-NOT: %recurse1
216; CHECK: %accumulate1 = add nsw i32 %accumulator.tr, 1
217; CHECK: if.end3:
218; CHECK: %recurse2
219; CHECK: %accumulator.ret.tr = add nsw i32 %accumulator.tr, %accumulate2
220; CHECK: ret i32 %accumulator.ret.tr
221; CHECK: return:
222; CHECK: %accumulator.ret.tr1 = add nsw i32 %accumulator.tr, 0
223; CHECK: ret i32 %accumulator.ret.tr1
224