1; RUN: opt < %s -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=false -unroll-runtime-multi-exit=true -unroll-count=4  -verify-dom-info -S | FileCheck %s
2
3; REQUIRES: asserts
4; The tests below are for verifying dom tree after runtime unrolling
5; with multiple exit/exiting blocks.
6
7; We explicitly set the unroll count so that expensiveTripCount computation is allowed.
8
9; mergedexit block has edges from loop exit blocks.
10define i64 @test1() {
11; CHECK-LABEL: test1(
12; CHECK-LABEL: headerexit:
13; CHECK-NEXT:    %addphi = phi i64 [ %add.iv, %header ], [ %add.iv.1, %header.1 ], [ %add.iv.2, %header.2 ], [ %add.iv.3, %header.3 ]
14; CHECK-NEXT:    br label %mergedexit
15; CHECK-LABEL: latchexit:
16; CHECK-NEXT:    %shftphi = phi i64 [ %shft, %latch ], [ %shft.1, %latch.1 ], [ %shft.2, %latch.2 ], [ %shft.3, %latch.3 ]
17; CHECK-NEXT:    br label %mergedexit
18; CHECK-LABEL: mergedexit:
19; CHECK-NEXT:    %retval = phi i64 [ %addphi, %headerexit ], [ %shftphi, %latchexit ]
20; CHECK-NEXT:    ret i64 %retval
21entry:
22  br label %preheader
23
24preheader:                                              ; preds = %bb
25  %trip = zext i32 undef to i64
26  br label %header
27
28header:                                              ; preds = %latch, %preheader
29  %iv = phi i64 [ 2, %preheader ], [ %add.iv, %latch ]
30  %add.iv = add nuw nsw i64 %iv, 2
31  %cmp1 = icmp ult i64 %add.iv, %trip
32  br i1 %cmp1, label %latch, label %headerexit
33
34latch:                                             ; preds = %header
35  %shft = ashr i64 %add.iv, 1
36  %cmp2 = icmp ult i64 %shft, %trip
37  br i1 %cmp2, label %header, label %latchexit
38
39headerexit:                                              ; preds = %header
40  %addphi = phi i64 [ %add.iv, %header ]
41  br label %mergedexit
42
43latchexit:                                              ; preds = %latch
44 %shftphi = phi i64 [ %shft, %latch ]
45  br label %mergedexit
46
47mergedexit:                                              ; preds = %latchexit, %headerexit
48  %retval = phi i64 [ %addphi, %headerexit ], [ %shftphi, %latchexit ]
49  ret i64 %retval
50}
51
52; mergedexit has edges from loop exit blocks and a block outside the loop.
53define  void @test2(i1 %cond, i32 %n) {
54; CHECK-LABEL: header.1:
55; CHECK-NEXT:    %add.iv.1 = add nuw nsw i64 %add.iv, 2
56; CHECK:         br i1 %cmp1.1, label %latch.1, label %headerexit
57; CHECK-LABEL: latch.3:
58; CHECK:         %cmp2.3 = icmp ult i64 %shft.3, %trip
59; CHECK-NEXT:    br i1 %cmp2.3, label %header, label %latchexit, !llvm.loop
60entry:
61  br i1 %cond, label %preheader, label %mergedexit
62
63preheader:                                              ; preds = %entry
64  %trip = zext i32 %n to i64
65  br label %header
66
67header:                                              ; preds = %latch, %preheader
68  %iv = phi i64 [ 2, %preheader ], [ %add.iv, %latch ]
69  %add.iv = add nuw nsw i64 %iv, 2
70  %cmp1 = icmp ult i64 %add.iv, %trip
71  br i1 %cmp1, label %latch, label %headerexit
72
73latch:                                             ; preds = %header
74  %shft = ashr i64 %add.iv, 1
75  %cmp2 = icmp ult i64 %shft, %trip
76  br i1 %cmp2, label %header, label %latchexit
77
78headerexit:                                              ; preds = %header
79  br label %mergedexit
80
81latchexit:                                              ; preds = %latch
82  br label %mergedexit
83
84mergedexit:                                              ; preds = %latchexit, %headerexit, %entry
85  ret void
86}
87
88
89; exitsucc is from loop exit block only.
90define i64 @test3(i32 %n) {
91; CHECK-LABEL: test3(
92; CHECK-LABEL:  headerexit:
93; CHECK-NEXT:     br label %exitsucc
94; CHECK-LABEL:  latchexit:
95; CHECK-NEXT:     %shftphi = phi i64 [ %shft, %latch ], [ %shft.1, %latch.1 ], [ %shft.2, %latch.2 ], [ %shft.3, %latch.3 ]
96; CHECK-NEXT:     ret i64 %shftphi
97; CHECK-LABEL:  exitsucc:
98; CHECK-NEXT:     ret i64 96
99entry:
100  br label %preheader
101
102preheader:                                              ; preds = %bb
103  %trip = zext i32 %n to i64
104  br label %header
105
106header:                                              ; preds = %latch, %preheader
107  %iv = phi i64 [ 2, %preheader ], [ %add.iv, %latch ]
108  %add.iv = add nuw nsw i64 %iv, 2
109  %cmp1 = icmp ult i64 %add.iv, %trip
110  br i1 %cmp1, label %latch, label %headerexit
111
112latch:                                             ; preds = %header
113  %shft = ashr i64 %add.iv, 1
114  %cmp2 = icmp ult i64 %shft, %trip
115  br i1 %cmp2, label %header, label %latchexit
116
117headerexit:                                              ; preds = %header
118  br label %exitsucc
119
120latchexit:                                              ; preds = %latch
121  %shftphi = phi i64 [ %shft, %latch ]
122  ret i64 %shftphi
123
124exitsucc:                                              ; preds = %headerexit
125  ret i64 96
126}
127
128; exit block (%default) has an exiting block and another exit block as predecessors.
129define void @test4(i16 %c3) {
130; CHECK-LABEL: test4
131
132; CHECK-LABEL: exiting.prol:
133; CHECK-NEXT:   switch i16 %c3, label %default.loopexit.loopexit1 [
134
135; CHECK-LABEL: exiting:
136; CHECK-NEXT:   switch i16 %c3, label %default.loopexit.loopexit [
137
138; CHECK-LABEL: default.loopexit.loopexit:
139; CHECK-NEXT:   br label %default.loopexit
140
141; CHECK-LABEL: default.loopexit.loopexit1:
142; CHECK-NEXT:   br label %default.loopexit
143
144; CHECK-LABEL: default.loopexit:
145; CHECK-NEXT:   br label %default
146preheader:
147  %c1 = zext i32 undef to i64
148  br label %header
149
150header:                                       ; preds = %latch, %preheader
151  %indvars.iv = phi i64 [ 0, %preheader ], [ %indvars.iv.next, %latch ]
152  br label %exiting
153
154exiting:                                           ; preds = %header
155  switch i16 %c3, label %default [
156    i16 45, label %otherexit
157    i16 95, label %latch
158  ]
159
160latch:                                          ; preds = %exiting
161  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
162  %c2 = icmp ult i64 %indvars.iv.next, %c1
163  br i1 %c2, label %header, label %latchexit
164
165latchexit:                                          ; preds = %latch
166  ret void
167
168default:                                          ; preds = %otherexit, %exiting
169  ret void
170
171otherexit:                                           ; preds = %exiting
172  br label %default
173}
174
175; exit block (%exitB) has an exiting block and another exit block as predecessors.
176; exiting block comes from inner loop.
177define void @test5(i1 %c) {
178; CHECK-LABEL: test5
179; CHECK-LABEL: bb1:
180; CHECK-NEXT:   br i1 false, label %outerH.prol.preheader, label %outerH.prol.loopexit
181
182; CHECK-LABEL: outerH.prol.preheader:
183; CHECK-NEXT:   br label %outerH.prol
184
185; CHECK-LABEL: outerH.prol:
186; CHECK-NEXT:   %tmp4.prol = phi i32 [ %tmp6.prol, %outerLatch.prol ], [ undef, %outerH.prol.preheader ]
187; CHECK-NEXT:   %prol.iter = phi i32 [ 0, %outerH.prol.preheader ], [ %prol.iter.sub, %outerLatch.prol ]
188; CHECK-NEXT:   br label %innerH.prol
189bb:
190  %tmp = icmp sgt i32 undef, 79
191  br i1 %tmp, label %outerLatchExit, label %bb1
192
193bb1:                                              ; preds = %bb
194  br label %outerH
195
196outerH:                                              ; preds = %outerLatch, %bb1
197  %tmp4 = phi i32 [ %tmp6, %outerLatch ], [ undef, %bb1 ]
198  br label %innerH
199
200innerH:                                              ; preds = %innerLatch, %outerH
201  br i1 %c, label %innerexiting, label %otherexitB
202
203innerexiting:                                             ; preds = %innerH
204  br i1 %c, label %innerLatch, label %exitB
205
206innerLatch:                                             ; preds = %innerexiting
207  %tmp13 = fcmp olt double undef, 2.000000e+00
208  br i1 %tmp13, label %innerH, label %outerLatch
209
210outerLatch:                                              ; preds = %innerLatch
211  %tmp6 = add i32 %tmp4, 1
212  %tmp7 = icmp sgt i32 %tmp6, 79
213  br i1 %tmp7, label %outerLatchExit, label %outerH
214
215outerLatchExit:                                              ; preds = %outerLatch, %bb
216  ret void
217
218exitB:                                             ; preds = %innerexiting, %otherexitB
219  ret void
220
221otherexitB:                                              ; preds = %innerH
222  br label %exitB
223
224}
225
226; Blocks reachable from exits (not_zero44) have the IDom as the block within the loop (Header).
227; Update the IDom to the preheader.
228define void @test6(i1 %c) {
229; CHECK-LABEL: test6
230; CHECK-LABEL: header.prol.preheader:
231; CHECK-NEXT:    br label %header.prol
232
233; CHECK-LABEL: header.prol:
234; CHECK-NEXT:    %indvars.iv.prol = phi i64 [ undef, %header.prol.preheader ], [ %indvars.iv.next.prol, %latch.prol ]
235; CHECK-NEXT:    %prol.iter = phi i64 [ %xtraiter, %header.prol.preheader ], [ %prol.iter.sub, %latch.prol ]
236
237; CHECK-NEXT:    br i1 %c, label %latch.prol, label %otherexit.loopexit1
238
239; CHECK-LABEL: header.prol.loopexit.unr-lcssa:
240; CHECK-NEXT:    %indvars.iv.unr.ph = phi i64 [ %indvars.iv.next.prol, %latch.prol ]
241; CHECK-NEXT:    br label %header.prol.loopexit
242
243; CHECK-LABEL: header.prol.loopexit:
244; CHECK-NEXT:    %indvars.iv.unr = phi i64 [ undef, %entry ], [ %indvars.iv.unr.ph, %header.prol.loopexit.unr-lcssa ]
245; CHECK-NEXT:    %5 = icmp ult i64 %2, 3
246; CHECK-NEXT:    br i1 %5, label %latchexit, label %entry.new
247
248; CHECK-LABEL: entry.new:
249; CHECK-NEXT:    br label %header
250entry:
251  br label %header
252
253header:                                          ; preds = %latch, %entry
254  %indvars.iv = phi i64 [ undef, %entry ], [ %indvars.iv.next, %latch ]
255  br i1 %c, label %latch, label %otherexit
256
257latch:                                         ; preds = %header
258  %indvars.iv.next = add nsw i64 %indvars.iv, 2
259  %0 = icmp slt i64 %indvars.iv.next, 616
260  br i1 %0, label %header, label %latchexit
261
262latchexit:                                          ; preds = %latch
263  br label %latchexitsucc
264
265otherexit:                                 ; preds = %header
266  br label %otherexitsucc
267
268otherexitsucc:                                          ; preds = %otherexit
269  br label %not_zero44
270
271not_zero44:                                       ; preds = %latchexitsucc, %otherexitsucc
272  unreachable
273
274latchexitsucc:                                      ; preds = %latchexit
275  br label %not_zero44
276}
277
278