1; RUN: opt < %s -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=true -unroll-runtime-multi-exit=true -verify-loop-lcssa -verify-dom-info -verify-loop-info -S | FileCheck %s -check-prefix=EPILOG-NO-IC
2; RUN: opt < %s -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=true -unroll-runtime-multi-exit=true -verify-loop-lcssa -verify-dom-info -verify-loop-info -instcombine -S | FileCheck %s -check-prefix=EPILOG
3; RUN: opt < %s -loop-unroll -unroll-runtime -unroll-count=2 -unroll-runtime-epilog=true -unroll-runtime-multi-exit=true -verify-loop-lcssa -verify-dom-info -verify-loop-info -instcombine
4; RUN: opt < %s -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=false -unroll-runtime-multi-exit=true -verify-loop-lcssa -verify-dom-info -verify-loop-info -instcombine -S | FileCheck %s -check-prefix=PROLOG
5; RUN: opt < %s -loop-unroll -unroll-runtime -unroll-runtime-epilog=false -unroll-count=2 -unroll-runtime-multi-exit=true -verify-loop-lcssa -verify-dom-info -verify-loop-info -instcombine
6
7; REQUIRES: asserts
8
9; the third and fifth RUNs generate an epilog/prolog remainder block for all the test
10; cases below (it does not generate a loop).
11
12; test with three exiting and three exit blocks.
13; none of the exit blocks have successors
14define void @test1(i64 %trip, i1 %cond) {
15; EPILOG: test1(
16; EPILOG-NEXT:  entry:
17; EPILOG-NEXT:    [[TMP0:%.*]] = add i64 [[TRIP:%.*]], -1
18; EPILOG-NEXT:    [[XTRAITER:%.*]] = and i64 [[TRIP]], 7
19; EPILOG-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[TMP0]], 7
20; EPILOG-NEXT:    br i1 [[TMP1]], label %exit2.loopexit.unr-lcssa, label [[ENTRY_NEW:%.*]]
21; EPILOG:       entry.new:
22; EPILOG-NEXT:    [[UNROLL_ITER:%.*]] = sub i64 [[TRIP]], [[XTRAITER]]
23; EPILOG-NEXT:    br label [[LOOP_HEADER:%.*]]
24; EPILOG:  loop_latch.epil:
25; EPILOG-NEXT:     %epil.iter.sub = add i64 %epil.iter, -1
26; EPILOG-NEXT:     %epil.iter.cmp = icmp eq i64 %epil.iter.sub, 0
27; EPILOG-NEXT:     br i1 %epil.iter.cmp, label %exit2.loopexit.epilog-lcssa, label %loop_header.epil
28; EPILOG:  loop_latch.7:
29; EPILOG-NEXT:     %niter.nsub.7 = add i64 %niter, -8
30; EPILOG-NEXT:     %niter.ncmp.7 = icmp eq i64 %niter.nsub.7, 0
31; EPILOG-NEXT:     br i1 %niter.ncmp.7, label %exit2.loopexit.unr-lcssa.loopexit, label %loop_header
32
33; PROLOG: test1(
34; PROLOG-NEXT:  entry:
35; PROLOG-NEXT:    [[TMP0:%.*]] = add i64 [[TRIP:%.*]], -1
36; PROLOG-NEXT:    [[XTRAITER:%.*]] = and i64 [[TRIP]], 7
37; PROLOG-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[XTRAITER]], 0
38; PROLOG-NEXT:    br i1 [[TMP1]], label %loop_header.prol.loopexit, label %loop_header.prol.preheader
39; PROLOG:       loop_header.prol:
40; PROLOG-NEXT:    %iv.prol = phi i64 [ 0, %loop_header.prol.preheader ], [ %iv_next.prol, %loop_latch.prol ]
41; PROLOG-NEXT:    %prol.iter = phi i64 [ [[XTRAITER]], %loop_header.prol.preheader ], [ %prol.iter.sub, %loop_latch.prol ]
42; PROLOG-NEXT:    br i1 %cond, label %loop_latch.prol, label %loop_exiting_bb1.prol
43; PROLOG:       loop_latch.prol:
44; PROLOG-NEXT:    %iv_next.prol = add i64 %iv.prol, 1
45; PROLOG-NEXT:    %prol.iter.sub = add i64 %prol.iter, -1
46; PROLOG-NEXT:    %prol.iter.cmp = icmp eq i64 %prol.iter.sub, 0
47; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol.loopexit.unr-lcssa, label %loop_header.prol
48; PROLOG:  loop_latch.7:
49; PROLOG-NEXT:     %iv_next.7 = add i64 %iv, 8
50; PROLOG-NEXT:     %cmp.7 = icmp eq i64 %iv_next.7, %trip
51; PROLOG-NEXT:     br i1 %cmp.7, label %exit2.loopexit.unr-lcssa, label %loop_header
52entry:
53  br label %loop_header
54
55loop_header:
56  %iv = phi i64 [ 0, %entry ], [ %iv_next, %loop_latch ]
57  br i1 %cond, label %loop_latch, label %loop_exiting_bb1
58
59loop_exiting_bb1:
60  br i1 false, label %loop_exiting_bb2, label %exit1
61
62loop_exiting_bb2:
63  br i1 false, label %loop_latch, label %exit3
64
65exit3:
66  ret void
67
68loop_latch:
69  %iv_next = add i64 %iv, 1
70  %cmp = icmp ne i64 %iv_next, %trip
71  br i1 %cmp, label %loop_header, label %exit2.loopexit
72
73exit1:
74 ret void
75
76exit2.loopexit:
77  ret void
78}
79
80
81; test with three exiting and two exit blocks.
82; The non-latch exit block has 2 unique predecessors.
83; There are 2 values passed to the exit blocks that are calculated at every iteration.
84; %sum.02 and %add. Both of these are incoming values for phi from every exiting
85; unrolled block.
86define i32 @test2(i32* nocapture %a, i64 %n) {
87; EPILOG: test2(
88; EPILOG: for.exit2.loopexit:
89; EPILOG-NEXT:    %retval.ph = phi i32 [ 42, %for.exiting_block ], [ %sum.02, %header ], [ %add, %for.body ], [ 42, %for.exiting_block.1 ], [ %add.1, %for.body.1 ], [ 42, %for.exiting_block.2 ], [ %add.2, %for.body.2 ], [ 42, %for.exiting_block.3 ],
90; EPILOG-NEXT:    br label %for.exit2
91; EPILOG: for.exit2.loopexit2:
92; EPILOG-NEXT:    %retval.ph3 = phi i32 [ 42, %for.exiting_block.epil ], [ %sum.02.epil, %header.epil ]
93; EPILOG-NEXT:    br label %for.exit2
94; EPILOG: for.exit2:
95; EPILOG-NEXT:    %retval = phi i32 [ %retval.ph, %for.exit2.loopexit ], [ %retval.ph3, %for.exit2.loopexit2 ]
96; EPILOG-NEXT:    ret i32 %retval
97; EPILOG: %niter.nsub.7 = add i64 %niter, -8
98
99; PROLOG: test2(
100; PROLOG: for.exit2.loopexit:
101; PROLOG-NEXT:    %retval.ph = phi i32 [ 42, %for.exiting_block ], [ %sum.02, %header ], [ %add, %for.body ], [ 42, %for.exiting_block.1 ], [ %add.1, %for.body.1 ], [ 42, %for.exiting_block.2 ], [ %add.2, %for.body.2 ], [ 42, %for.exiting_block.3 ],
102; PROLOG-NEXT:    br label %for.exit2
103; PROLOG: for.exit2.loopexit1:
104; PROLOG-NEXT:    %retval.ph2 = phi i32 [ 42, %for.exiting_block.prol ], [ %sum.02.prol, %header.prol ]
105; PROLOG-NEXT:    br label %for.exit2
106; PROLOG: for.exit2:
107; PROLOG-NEXT:    %retval = phi i32 [ %retval.ph, %for.exit2.loopexit ], [ %retval.ph2, %for.exit2.loopexit1 ]
108; PROLOG-NEXT:    ret i32 %retval
109; PROLOG: %indvars.iv.next.7 = add i64 %indvars.iv, 8
110
111entry:
112  br label %header
113
114header:
115  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
116  %sum.02 = phi i32 [ %add, %for.body ], [ 0, %entry ]
117  br i1 false, label %for.exit2, label %for.exiting_block
118
119for.exiting_block:
120 %cmp = icmp eq i64 %n, 42
121 br i1 %cmp, label %for.exit2, label %for.body
122
123for.body:
124  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
125  %0 = load i32, i32* %arrayidx, align 4
126  %add = add nsw i32 %0, %sum.02
127  %indvars.iv.next = add i64 %indvars.iv, 1
128  %exitcond = icmp eq i64 %indvars.iv.next, %n
129  br i1 %exitcond, label %for.end, label %header
130
131for.end:                                          ; preds = %for.body
132  %sum.0.lcssa = phi i32 [ %add, %for.body ]
133  ret i32 %sum.0.lcssa
134
135for.exit2:
136  %retval = phi i32 [ %sum.02, %header ], [ 42, %for.exiting_block ]
137  ret i32 %retval
138}
139
140; test with two exiting and three exit blocks.
141; the non-latch exiting block has a switch.
142define void @test3(i64 %trip, i64 %add) {
143; EPILOG: test3(
144; EPILOG-NEXT:  entry:
145; EPILOG-NEXT:    [[TMP0:%.*]] = add i64 [[TRIP:%.*]], -1
146; EPILOG-NEXT:    [[XTRAITER:%.*]] = and i64 [[TRIP]], 7
147; EPILOG-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[TMP0]], 7
148; EPILOG-NEXT:    br i1 [[TMP1]], label %exit2.loopexit.unr-lcssa, label [[ENTRY_NEW:%.*]]
149; EPILOG:       entry.new:
150; EPILOG-NEXT:    %unroll_iter = sub i64 [[TRIP]], [[XTRAITER]]
151; EPILOG-NEXT:    br label [[LOOP_HEADER:%.*]]
152; EPILOG:  loop_header:
153; EPILOG-NEXT:     %sum = phi i64 [ 0, %entry.new ], [ %sum.next.7, %loop_latch.7 ]
154; EPILOG-NEXT:     %niter = phi i64 [ %unroll_iter, %entry.new ], [ %niter.nsub.7, %loop_latch.7 ]
155; EPILOG:  loop_exiting_bb1.7:
156; EPILOG-NEXT:     switch i64 %sum.next.6, label %loop_latch.7
157; EPILOG:  loop_latch.7:
158; EPILOG-NEXT:     %sum.next.7 = add i64 %sum.next.6, %add
159; EPILOG-NEXT:     %niter.nsub.7 = add i64 %niter, -8
160; EPILOG-NEXT:     %niter.ncmp.7 = icmp eq i64 %niter.nsub.7, 0
161; EPILOG-NEXT:     br i1 %niter.ncmp.7, label %exit2.loopexit.unr-lcssa.loopexit, label %loop_header
162
163; PROLOG:  test3(
164; PROLOG-NEXT:  entry:
165; PROLOG-NEXT:    [[TMP0:%.*]] = add i64 [[TRIP:%.*]], -1
166; PROLOG-NEXT:    [[XTRAITER:%.*]] = and i64 [[TRIP]], 7
167; PROLOG-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[XTRAITER]], 0
168; PROLOG-NEXT:    br i1 [[TMP1]], label %loop_header.prol.loopexit, label %loop_header.prol.preheader
169; PROLOG:  loop_header:
170; PROLOG-NEXT:     %iv = phi i64 [ %iv.unr, %entry.new ], [ %iv_next.7, %loop_latch.7 ]
171; PROLOG-NEXT:     %sum = phi i64 [ %sum.unr, %entry.new ], [ %sum.next.7, %loop_latch.7 ]
172; PROLOG:  loop_exiting_bb1.7:
173; PROLOG-NEXT:     switch i64 %sum.next.6, label %loop_latch.7
174; PROLOG:  loop_latch.7:
175; PROLOG-NEXT:     %iv_next.7 = add nuw nsw i64 %iv, 8
176; PROLOG-NEXT:     %sum.next.7 = add i64 %sum.next.6, %add
177; PROLOG-NEXT:     %cmp.7 = icmp eq i64 %iv_next.7, %trip
178; PROLOG-NEXT:     br i1 %cmp.7, label %exit2.loopexit.unr-lcssa, label %loop_header
179entry:
180  br label %loop_header
181
182loop_header:
183  %iv = phi i64 [ 0, %entry ], [ %iv_next, %loop_latch ]
184  %sum = phi i64 [ 0, %entry ], [ %sum.next, %loop_latch ]
185  br i1 undef, label %loop_latch, label %loop_exiting_bb1
186
187loop_exiting_bb1:
188   switch i64 %sum, label %loop_latch [
189     i64 24, label %exit1
190     i64 42, label %exit3
191   ]
192
193exit3:
194  ret void
195
196loop_latch:
197  %iv_next = add nuw nsw i64 %iv, 1
198  %sum.next = add i64 %sum, %add
199  %cmp = icmp ne i64 %iv_next, %trip
200  br i1 %cmp, label %loop_header, label %exit2.loopexit
201
202exit1:
203 ret void
204
205exit2.loopexit:
206  ret void
207}
208
209; FIXME: Support multiple exiting blocks to the same latch exit block.
210; Three exiting blocks where header and latch exit to same LatchExit.
211define i32 @hdr_latch_same_exit(i32* nocapture %a, i64 %n, i1 %cond) {
212; EPILOG: hdr_latch_same_exit(
213; EPILOG-NOT: .unr
214; EPILOG-NOT: .epil
215
216; PROLOG: hdr_latch_same_exit(
217; PROLOG-NOT: .unr
218; PROLOG-NOT: .prol
219entry:
220  br label %header
221
222header:
223  %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %entry ]
224  %sum.02 = phi i32 [ %add, %latch ], [ 0, %entry ]
225  br i1 %cond, label %latchExit, label %for.exiting_block
226
227for.exiting_block:
228 %cmp = icmp eq i64 %n, 42
229 br i1 %cmp, label %for.exit2, label %latch
230
231latch:                                         ; preds = %latch, %entry
232  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
233  %0 = load i32, i32* %arrayidx, align 4
234  %add = add nsw i32 %0, %sum.02
235  %indvars.iv.next = add i64 %indvars.iv, 1
236  %exitcond = icmp eq i64 %indvars.iv.next, %n
237  br i1 %exitcond, label %latchExit, label %header
238
239latchExit:                                          ; preds = %latch, %entry
240  %result = phi i32 [ 0, %header ], [ %add, %latch ]
241  ret i32 %result
242
243for.exit2:
244  ret i32 42
245}
246
247; Two exiting blocks to latch where the exiting blocks are Latch and a
248; non-header
249; FIXME: We should unroll this loop.
250define i32 @otherblock_latch_same_exit(i32* nocapture %a, i64 %n, i1 %cond) {
251; EPILOG: otherblock_latch_same_exit(
252; EPILOG-NOT: .unr
253; EPILOG-NOT: .epil
254
255; PROLOG: otherblock_latch_same_exit(
256; PROLOG-NOT: .unr
257; PROLOG-NOT: .prol
258entry:
259  br label %header
260
261header:
262  %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %entry ]
263  %sum.02 = phi i32 [ %add, %latch ], [ 0, %entry ]
264  br i1 %cond, label %for.exit2, label %for.exiting_block
265
266for.exiting_block:
267 %cmp = icmp eq i64 %n, 42
268 br i1 %cmp, label %latchExit, label %latch
269
270latch:                                         ; preds = %latch, %entry
271  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
272  %0 = load i32, i32* %arrayidx, align 4
273  %add = add nsw i32 %0, %sum.02
274  %indvars.iv.next = add i64 %indvars.iv, 1
275  %exitcond = icmp eq i64 %indvars.iv.next, %n
276  br i1 %exitcond, label %latchExit, label %header
277
278latchExit:                                          ; preds = %latch, %entry
279  %result = phi i32 [ 2, %for.exiting_block ], [ %add, %latch ]
280  ret i32 %result
281
282for.exit2:
283  ret i32 42
284}
285
286; Two exiting blocks to latch where the exiting blocks are Latch and a
287; non-header
288; Same as above test except the incoming value for latch Phi is from the header
289; FIXME: We should be able to runtime unroll.
290define i32 @otherblock_latch_same_exit2(i32* nocapture %a, i64 %n, i1 %cond) {
291; EPILOG: otherblock_latch_same_exit2(
292; EPILOG-NOT: .unr
293; EPILOG-NOT: .epil
294
295; PROLOG: otherblock_latch_same_exit2(
296; PROLOG-NOT: .unr
297; PROLOG-NOT: .prol
298entry:
299  br label %header
300
301header:
302  %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %entry ]
303  %sum.02 = phi i32 [ %add, %latch ], [ 0, %entry ]
304  br i1 %cond, label %for.exit2, label %for.exiting_block
305
306for.exiting_block:
307 %cmp = icmp eq i64 %n, 42
308 br i1 %cmp, label %latchExit, label %latch
309
310latch:                                         ; preds = %latch, %entry
311  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
312  %0 = load i32, i32* %arrayidx, align 4
313  %add = add nsw i32 %0, %sum.02
314  %indvars.iv.next = add i64 %indvars.iv, 1
315  %exitcond = icmp eq i64 %indvars.iv.next, %n
316  br i1 %exitcond, label %latchExit, label %header
317
318latchExit:                                          ; preds = %latch, %entry
319  %result = phi i32 [ %sum.02, %for.exiting_block ], [ %add, %latch ]
320  ret i32 %result
321
322for.exit2:
323  ret i32 42
324}
325
326; Two exiting blocks to latch where the exiting blocks are Latch and a
327; non-header
328; Same as above test except the incoming value for cloned latch Phi is from the
329; for.exiting_block.
330; FIXME: We should be able to runtime unroll.
331define i32 @otherblock_latch_same_exit3(i32* nocapture %a, i64 %n, i1 %cond) {
332; EPILOG: otherblock_latch_same_exit3(
333; EPILOG-NOT: .unr
334; EPILOG-NOT: .epil
335
336; PROLOG: otherblock_latch_same_exit3(
337; PROLOG-NOT: .unr
338; PROLOG-NOT: .prol
339entry:
340  br label %header
341
342header:
343  %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %entry ]
344  %sum.02 = phi i32 [ %add, %latch ], [ 0, %entry ]
345  br i1 %cond, label %for.exit2, label %for.exiting_block
346
347for.exiting_block:
348 %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
349 %0 = load i32, i32* %arrayidx, align 4
350 %add = add nsw i32 %0, %sum.02
351 %cmp = icmp eq i64 %n, 42
352 br i1 %cmp, label %latchExit, label %latch
353
354latch:                                         ; preds = %latch, %entry
355  %indvars.iv.next = add i64 %indvars.iv, 1
356  %exitcond = icmp eq i64 %indvars.iv.next, %n
357  br i1 %exitcond, label %latchExit, label %header
358
359latchExit:                                          ; preds = %latch, %entry
360  %result = phi i32 [ %sum.02, %for.exiting_block ], [ %add, %latch ]
361  ret i32 %result
362
363for.exit2:
364  ret i32 42
365}
366
367; FIXME: Support multiple exiting blocks to the unique exit block (LatchExit).
368; Only 2 blocks in loop: header and latch where both exit to same LatchExit.
369define void @unique_exit(i32 %arg) {
370; EPILOG: unique_exit(
371; EPILOG-NOT: .unr
372; EPILOG-NOT: .epil
373
374; PROLOG: unique_exit(
375; PROLOG-NOT: .unr
376; PROLOG-NOT: .prol
377entry:
378  %tmp = icmp sgt i32 undef, %arg
379  br i1 %tmp, label %preheader, label %returnblock
380
381preheader:                                 ; preds = %entry
382  br label %header
383
384header:                                           ; preds = %preheader, %latch
385  %tmp4 = phi i32 [ %inc, %latch ], [ %arg, %preheader ]
386  %inc = add nsw i32 %tmp4, 1
387  br i1 true, label %latchExit, label %latch
388
389latch:                                            ; preds = %header
390  %cmp = icmp slt i32 %inc, undef
391  br i1 %cmp, label %header, label %latchExit
392
393latchExit:                                ; preds = %header, %latch
394  %tmp2.ph = phi i32 [ %tmp4, %header ], [ -1, %latch ]
395  br label %returnblock
396
397returnblock:                                         ; preds = %latchExit, %entry
398  %tmp2 = phi i32 [ -1, %entry ], [ %tmp2.ph, %latchExit ]
399  ret void
400}
401
402; two exiting and two exit blocks.
403; the non-latch exiting block has duplicate edges to the non-latch exit block.
404define i64 @test5(i64 %trip, i64 %add, i1 %cond) {
405; EPILOG: test5(
406; EPILOG:   exit1.loopexit:
407; EPILOG-NEXT:      %result.ph = phi i64 [ %ivy, %loop_exiting ], [ %ivy, %loop_exiting ], [ %ivy.1, %loop_exiting.1 ], [ %ivy.1, %loop_exiting.1 ], [ %ivy.2, %loop_exiting.2 ],
408; EPILOG-NEXT:      br label %exit1
409; EPILOG:   exit1.loopexit2:
410; EPILOG-NEXT:      %ivy.epil = add i64 %iv.epil, %add
411; EPILOG-NEXT:      br label %exit1
412; EPILOG:   exit1:
413; EPILOG-NEXT:      %result = phi i64 [ %result.ph, %exit1.loopexit ], [ %ivy.epil, %exit1.loopexit2 ]
414; EPILOG-NEXT:      ret i64 %result
415; EPILOG:   loop_latch.7:
416; EPILOG:      %niter.nsub.7 = add i64 %niter, -8
417
418; PROLOG: test5(
419; PROLOG:   exit1.loopexit:
420; PROLOG-NEXT:      %result.ph = phi i64 [ %ivy, %loop_exiting ], [ %ivy, %loop_exiting ], [ %ivy.1, %loop_exiting.1 ], [ %ivy.1, %loop_exiting.1 ], [ %ivy.2, %loop_exiting.2 ],
421; PROLOG-NEXT:      br label %exit1
422; PROLOG:   exit1.loopexit1:
423; PROLOG-NEXT:      %ivy.prol = add i64 %iv.prol, %add
424; PROLOG-NEXT:      br label %exit1
425; PROLOG:   exit1:
426; PROLOG-NEXT:      %result = phi i64 [ %result.ph, %exit1.loopexit ], [ %ivy.prol, %exit1.loopexit1 ]
427; PROLOG-NEXT:      ret i64 %result
428; PROLOG:   loop_latch.7:
429; PROLOG:      %iv_next.7 = add nuw nsw i64 %iv, 8
430entry:
431  br label %loop_header
432
433loop_header:
434  %iv = phi i64 [ 0, %entry ], [ %iv_next, %loop_latch ]
435  %sum = phi i64 [ 0, %entry ], [ %sum.next, %loop_latch ]
436  br i1 %cond, label %loop_latch, label %loop_exiting
437
438loop_exiting:
439   %ivy = add i64 %iv, %add
440   switch i64 %sum, label %loop_latch [
441     i64 24, label %exit1
442     i64 42, label %exit1
443   ]
444
445loop_latch:
446  %iv_next = add nuw nsw i64 %iv, 1
447  %sum.next = add i64 %sum, %add
448  %cmp = icmp ne i64 %iv_next, %trip
449  br i1 %cmp, label %loop_header, label %latchexit
450
451exit1:
452 %result = phi i64 [ %ivy, %loop_exiting ], [ %ivy, %loop_exiting ]
453 ret i64 %result
454
455latchexit:
456  ret i64 %sum.next
457}
458
459; test when exit blocks have successors.
460define i32 @test6(i32* nocapture %a, i64 %n, i1 %cond, i32 %x) {
461; EPILOG: test6(
462; EPILOG:   for.exit2.loopexit:
463; EPILOG-NEXT:      %retval.ph = phi i32 [ 42, %for.exiting_block ], [ %sum.02, %header ], [ %add, %latch ], [ 42, %for.exiting_block.1 ], [ %add.1, %latch.1 ], [ 42, %for.exiting_block.2 ], [ %add.2, %latch.2 ],
464; EPILOG-NEXT:      br label %for.exit2
465; EPILOG:   for.exit2.loopexit2:
466; EPILOG-NEXT:      %retval.ph3 = phi i32 [ 42, %for.exiting_block.epil ], [ %sum.02.epil, %header.epil ]
467; EPILOG-NEXT:      br label %for.exit2
468; EPILOG:   for.exit2:
469; EPILOG-NEXT:      %retval = phi i32 [ %retval.ph, %for.exit2.loopexit ], [ %retval.ph3, %for.exit2.loopexit2 ]
470; EPILOG-NEXT:      br i1 %cond, label %exit_true, label %exit_false
471; EPILOG:   latch.7:
472; EPILOG:           %niter.nsub.7 = add i64 %niter, -8
473
474; PROLOG: test6(
475; PROLOG:   for.exit2.loopexit:
476; PROLOG-NEXT:      %retval.ph = phi i32 [ 42, %for.exiting_block ], [ %sum.02, %header ], [ %add, %latch ], [ 42, %for.exiting_block.1 ], [ %add.1, %latch.1 ], [ 42, %for.exiting_block.2 ], [ %add.2, %latch.2 ],
477; PROLOG-NEXT:      br label %for.exit2
478; PROLOG:   for.exit2.loopexit1:
479; PROLOG-NEXT:      %retval.ph2 = phi i32 [ 42, %for.exiting_block.prol ], [ %sum.02.prol, %header.prol ]
480; PROLOG-NEXT:      br label %for.exit2
481; PROLOG:   for.exit2:
482; PROLOG-NEXT:      %retval = phi i32 [ %retval.ph, %for.exit2.loopexit ], [ %retval.ph2, %for.exit2.loopexit1 ]
483; PROLOG-NEXT:      br i1 %cond, label %exit_true, label %exit_false
484; PROLOG: latch.7:
485; PROLOG:   %indvars.iv.next.7 = add i64 %indvars.iv, 8
486entry:
487  br label %header
488
489header:
490  %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %entry ]
491  %sum.02 = phi i32 [ %add, %latch ], [ 0, %entry ]
492  br i1 false, label %for.exit2, label %for.exiting_block
493
494for.exiting_block:
495 %cmp = icmp eq i64 %n, 42
496 br i1 %cmp, label %for.exit2, label %latch
497
498latch:
499  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
500  %load = load i32, i32* %arrayidx, align 4
501  %add = add nsw i32 %load, %sum.02
502  %indvars.iv.next = add i64 %indvars.iv, 1
503  %exitcond = icmp eq i64 %indvars.iv.next, %n
504  br i1 %exitcond, label %latch_exit, label %header
505
506latch_exit:
507  %sum.0.lcssa = phi i32 [ %add, %latch ]
508  ret i32 %sum.0.lcssa
509
510for.exit2:
511  %retval = phi i32 [ %sum.02, %header ], [ 42, %for.exiting_block ]
512  %addx = add i32 %retval, %x
513  br i1 %cond, label %exit_true, label %exit_false
514
515exit_true:
516  ret i32 %retval
517
518exit_false:
519  ret i32 %addx
520}
521
522; test when value in exit block does not have VMap.
523define i32 @test7(i32 %arg, i32 %arg1, i32 %arg2) {
524; EPILOG-NO-IC: test7(
525; EPILOG-NO-IC: loopexit1.loopexit:
526; EPILOG-NO-IC-NEXT:  %sext3.ph = phi i32 [ %shft, %header ], [ %shft, %latch ], [ %shft, %latch.1 ], [ %shft, %latch.2 ], [ %shft, %latch.3 ], [ %shft, %latch.4 ], [ %shft, %latch.5 ], [ %shft, %latch.6 ]
527; EPILOG-NO-IC-NEXT:  br label %loopexit1
528; EPILOG-NO-IC: loopexit1.loopexit1:
529; EPILOG-NO-IC-NEXT:  %sext3.ph2 = phi i32 [ %shft, %header.epil ]
530; EPILOG-NO-IC-NEXT:  br label %loopexit1
531; EPILOG-NO-IC: loopexit1:
532; EPILOG-NO-IC-NEXT:   %sext3 = phi i32 [ %sext3.ph, %loopexit1.loopexit ], [ %sext3.ph2, %loopexit1.loopexit1 ]
533bb:
534  %tmp = icmp slt i32 undef, 2
535  %sext = sext i32 undef to i64
536  %shft = ashr exact i32 %arg, 16
537  br i1 %tmp, label %loopexit2, label %preheader
538
539preheader:                                              ; preds = %bb2
540  br label %header
541
542header:                                              ; preds = %latch, %preheader
543  %tmp6 = phi i64 [ 1, %preheader ], [ %add, %latch ]
544  br i1 false, label %loopexit1, label %latch
545
546latch:                                              ; preds = %header
547  %add = add nuw nsw i64 %tmp6, 1
548  %tmp9 = icmp slt i64 %add, %sext
549  br i1 %tmp9, label %header, label %latchexit
550
551latchexit:                                             ; preds = %latch
552  unreachable
553
554loopexit2:                                             ; preds = %bb2
555 ret i32 %shft
556
557loopexit1:                                             ; preds = %header
558  %sext3 = phi i32 [ %shft, %header ]
559  ret i32 %sext3
560}
561
562; Nested loop and inner loop is unrolled
563; FIXME: we cannot unroll with epilog remainder currently, because
564; the outer loop does not contain the epilog preheader and epilog exit (while
565; infact it should). This causes us to choke up on LCSSA form being incorrect in
566; outer loop. However, the exit block where LCSSA fails, is infact still within
567; the outer loop. For now, we just bail out in presence of outer loop and epilog
568; loop is generated.
569; The outer loop header is the preheader for the inner loop and the inner header
570; branches back to the outer loop.
571define void @test8() {
572; EPILOG: test8(
573; EPILOG-NOT: niter
574
575; PROLOG: test8(
576; PROLOG: outerloop:
577; PROLOG-NEXT: phi i64 [ 3, %bb ], [ 0, %outerloop.loopexit ]
578; PROLOG:      %lcmp.mod = icmp eq i64
579; PROLOG-NEXT: br i1 %lcmp.mod, label %innerH.prol.loopexit, label %innerH.prol.preheader
580; PROLOG: latch.6:
581; PROLOG-NEXT: br i1 false, label %outerloop.loopexit.loopexit, label %latch.7
582; PROLOG: latch.7:
583; PROLOG-NEXT: %tmp4.7 = add nuw nsw i64 %tmp3, 8
584; PROLOG-NEXT: %tmp6.7 = icmp ult i64 %tmp3, 92
585; PROLOG-NEXT: br i1 %tmp6.7, label %innerH, label %exit.unr-lcssa
586bb:
587  br label %outerloop
588
589outerloop:                                              ; preds = %innerH, %bb
590  %tmp = phi i64 [ 3, %bb ], [ 0, %innerH ]
591  br label %innerH
592
593innerH:                                              ; preds = %latch, %outerloop
594  %tmp3 = phi i64 [ %tmp4, %latch ], [ %tmp, %outerloop ]
595  %tmp4 = add nuw nsw i64 %tmp3, 1
596  br i1 false, label %outerloop, label %latch
597
598latch:                                              ; preds = %innerH
599  %tmp6 = icmp ult i64 %tmp4, 100
600  br i1 %tmp6, label %innerH, label %exit
601
602exit:                                              ; preds = %latch
603  ret void
604}
605
606declare i8 addrspace(1)* @foo(i32)
607; inner loop prolog unrolled
608; a value from outer loop is used in exit block of inner loop.
609; Don't create VMap entries for such values (%trip).
610define i8 addrspace(1)* @test9(i8* nocapture readonly %arg, i32 %n) {
611; PROLOG: test9(
612; PROLOG: header.prol:
613; PROLOG-NEXT: %phi.prol = phi i64 [ 0, %header.prol.preheader ], [ %iv.next.prol, %latch.prol ]
614; PROLOG: latch.prol:
615; PROLOG-NOT: trip
616; PROLOG:     br i1 %prol.iter.cmp, label %header.prol.loopexit.unr-lcssa, label %header.prol
617bb:
618  br label %outerloopHdr
619
620outerloopHdr:                                              ; preds = %outerLatch, %bb
621  %trip = add i32 %n, -1
622  %outercnd = icmp slt i32 0, %trip
623  br i1 %outercnd, label %preheader, label %outerLatch
624
625preheader:                                              ; preds = %outerloopHdr
626  %tmp4 = zext i32 0 to i64
627  br label %header
628
629header:                                              ; preds = %latch, %preheader
630  %phi = phi i64 [ %tmp4, %preheader ], [ %iv.next, %latch ]
631  %tmp7 = trunc i64 %phi to i32
632  br i1 true, label %latch, label %innerexit
633
634innerexit:                                              ; preds = %header
635  %tmp9 = call i8 addrspace(1)* @foo(i32 %trip)
636  ret i8 addrspace(1)* %tmp9
637
638latch:                                             ; preds = %header
639  %tmp11 = add nsw i32 %tmp7, 1
640  %innercnd = icmp slt i32 %tmp11, %trip
641  %iv.next = add nuw nsw i64 %phi, 1
642  br i1 %innercnd, label %header, label %outerLatch
643
644outerLatch:                                             ; preds = %latch, %outerloopHdr
645  br label %outerloopHdr
646}
647