1; RUN: opt -passes='loop(simple-loop-unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s
2; RUN: opt -passes='loop-mssa(simple-loop-unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s
3; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -verify-memoryssa -S < %s | FileCheck %s
4
5declare i32 @a()
6declare i32 @b()
7declare i32 @c()
8declare i32 @d()
9
10declare void @sink1(i32)
11declare void @sink2(i32)
12
13declare i1 @cond()
14declare i32 @cond.i32()
15
16; Negative test: we cannot unswitch convergent calls.
17define void @test_no_unswitch_convergent(i1* %ptr, i1 %cond) {
18; CHECK-LABEL: @test_no_unswitch_convergent(
19entry:
20  br label %loop_begin
21; CHECK-NEXT:  entry:
22; CHECK-NEXT:    br label %loop_begin
23;
24; We shouldn't have unswitched into any other block either.
25; CHECK-NOT:     br i1 %cond
26
27loop_begin:
28  br i1 %cond, label %loop_a, label %loop_b
29; CHECK:       loop_begin:
30; CHECK-NEXT:    br i1 %cond, label %loop_a, label %loop_b
31
32loop_a:
33  call i32 @a() convergent
34  br label %loop_latch
35
36loop_b:
37  call i32 @b()
38  br label %loop_latch
39
40loop_latch:
41  %v = load i1, i1* %ptr
42  br i1 %v, label %loop_begin, label %loop_exit
43
44loop_exit:
45  ret void
46}
47
48; Negative test: we cannot unswitch noduplicate calls.
49define void @test_no_unswitch_noduplicate(i1* %ptr, i1 %cond) {
50; CHECK-LABEL: @test_no_unswitch_noduplicate(
51entry:
52  br label %loop_begin
53; CHECK-NEXT:  entry:
54; CHECK-NEXT:    br label %loop_begin
55;
56; We shouldn't have unswitched into any other block either.
57; CHECK-NOT:     br i1 %cond
58
59loop_begin:
60  br i1 %cond, label %loop_a, label %loop_b
61; CHECK:       loop_begin:
62; CHECK-NEXT:    br i1 %cond, label %loop_a, label %loop_b
63
64loop_a:
65  call i32 @a() noduplicate
66  br label %loop_latch
67
68loop_b:
69  call i32 @b()
70  br label %loop_latch
71
72loop_latch:
73  %v = load i1, i1* %ptr
74  br i1 %v, label %loop_begin, label %loop_exit
75
76loop_exit:
77  ret void
78}
79
80declare i32 @__CxxFrameHandler3(...)
81
82; Negative test: we cannot unswitch when tokens are used across blocks as we
83; might introduce PHIs.
84define void @test_no_unswitch_cross_block_token(i1* %ptr, i1 %cond) nounwind personality i32 (...)* @__CxxFrameHandler3 {
85; CHECK-LABEL: @test_no_unswitch_cross_block_token(
86entry:
87  br label %loop_begin
88; CHECK-NEXT:  entry:
89; CHECK-NEXT:    br label %loop_begin
90;
91; We shouldn't have unswitched into any other block either.
92; CHECK-NOT:     br i1 %cond
93
94loop_begin:
95  br i1 %cond, label %loop_a, label %loop_b
96; CHECK:       loop_begin:
97; CHECK-NEXT:    br i1 %cond, label %loop_a, label %loop_b
98
99loop_a:
100  call i32 @a()
101  br label %loop_cont
102
103loop_b:
104  call i32 @b()
105  br label %loop_cont
106
107loop_cont:
108  invoke i32 @a()
109          to label %loop_latch unwind label %loop_catch
110
111loop_latch:
112  br label %loop_begin
113
114loop_catch:
115  %catch = catchswitch within none [label %loop_catch_latch, label %loop_exit] unwind to caller
116
117loop_catch_latch:
118  %catchpad_latch = catchpad within %catch []
119  catchret from %catchpad_latch to label %loop_begin
120
121loop_exit:
122  %catchpad_exit = catchpad within %catch []
123  catchret from %catchpad_exit to label %exit
124
125exit:
126  ret void
127}
128
129
130; Non-trivial loop unswitching where there are two distinct trivial conditions
131; to unswitch within the loop.
132define i32 @test1(i1* %ptr, i1 %cond1, i1 %cond2) {
133; CHECK-LABEL: @test1(
134entry:
135  br label %loop_begin
136; CHECK-NEXT:  entry:
137; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
138
139loop_begin:
140  br i1 %cond1, label %loop_a, label %loop_b
141
142loop_a:
143  call i32 @a()
144  br label %latch
145; The 'loop_a' unswitched loop.
146;
147; CHECK:       entry.split.us:
148; CHECK-NEXT:    br label %loop_begin.us
149;
150; CHECK:       loop_begin.us:
151; CHECK-NEXT:    br label %loop_a.us
152;
153; CHECK:       loop_a.us:
154; CHECK-NEXT:    call i32 @a()
155; CHECK-NEXT:    br label %latch.us
156;
157; CHECK:       latch.us:
158; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
159; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
160;
161; CHECK:       loop_exit.split.us:
162; CHECK-NEXT:    br label %loop_exit
163
164loop_b:
165  br i1 %cond2, label %loop_b_a, label %loop_b_b
166; The second unswitched condition.
167;
168; CHECK:       entry.split:
169; CHECK-NEXT:    br i1 %cond2, label %entry.split.split.us, label %entry.split.split
170
171loop_b_a:
172  call i32 @b()
173  br label %latch
174; The 'loop_b_a' unswitched loop.
175;
176; CHECK:       entry.split.split.us:
177; CHECK-NEXT:    br label %loop_begin.us1
178;
179; CHECK:       loop_begin.us1:
180; CHECK-NEXT:    br label %loop_b.us
181;
182; CHECK:       loop_b.us:
183; CHECK-NEXT:    br label %loop_b_a.us
184;
185; CHECK:       loop_b_a.us:
186; CHECK-NEXT:    call i32 @b()
187; CHECK-NEXT:    br label %latch.us2
188;
189; CHECK:       latch.us2:
190; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
191; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us1, label %loop_exit.split.split.us
192;
193; CHECK:       loop_exit.split.split.us:
194; CHECK-NEXT:    br label %loop_exit.split
195
196loop_b_b:
197  call i32 @c()
198  br label %latch
199; The 'loop_b_b' unswitched loop.
200;
201; CHECK:       entry.split.split:
202; CHECK-NEXT:    br label %loop_begin
203;
204; CHECK:       loop_begin:
205; CHECK-NEXT:    br label %loop_b
206;
207; CHECK:       loop_b:
208; CHECK-NEXT:    br label %loop_b_b
209;
210; CHECK:       loop_b_b:
211; CHECK-NEXT:    call i32 @c()
212; CHECK-NEXT:    br label %latch
213;
214; CHECK:       latch:
215; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
216; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split.split
217;
218; CHECK:       loop_exit.split.split:
219; CHECK-NEXT:    br label %loop_exit.split
220
221latch:
222  %v = load i1, i1* %ptr
223  br i1 %v, label %loop_begin, label %loop_exit
224
225loop_exit:
226  ret i32 0
227; CHECK:       loop_exit.split:
228; CHECK-NEXT:    br label %loop_exit
229;
230; CHECK:       loop_exit:
231; CHECK-NEXT:    ret
232}
233
234define i32 @test2(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr, i32* %c.ptr) {
235; CHECK-LABEL: @test2(
236entry:
237  br label %loop_begin
238; CHECK-NEXT:  entry:
239; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
240
241loop_begin:
242  %v = load i1, i1* %ptr
243  br i1 %cond1, label %loop_a, label %loop_b
244
245loop_a:
246  %a = load i32, i32* %a.ptr
247  %ac = load i32, i32* %c.ptr
248  br i1 %v, label %loop_begin, label %loop_exit
249; The 'loop_a' unswitched loop.
250;
251; CHECK:       entry.split.us:
252; CHECK-NEXT:    br label %loop_begin.us
253;
254; CHECK:       loop_begin.us:
255; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
256; CHECK-NEXT:    br label %loop_a.us
257;
258; CHECK:       loop_a.us:
259; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
260; CHECK-NEXT:    %[[AC:.*]] = load i32, i32* %c.ptr
261; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.backedge.us, label %loop_exit.split.us
262;
263; CHECK:       loop_exit.split.us:
264; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a.us ]
265; CHECK-NEXT:    %[[AC_LCSSA:.*]] = phi i32 [ %[[AC]], %loop_a.us ]
266; CHECK-NEXT:    br label %loop_exit
267
268loop_b:
269  %b = load i32, i32* %b.ptr
270  %bc = load i32, i32* %c.ptr
271  br i1 %v, label %loop_begin, label %loop_exit
272; The 'loop_b' unswitched loop.
273;
274; CHECK:       entry.split:
275; CHECK-NEXT:    br label %loop_begin
276;
277; CHECK:       loop_begin:
278; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
279; CHECK-NEXT:    br label %loop_b
280;
281; CHECK:       loop_b:
282; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
283; CHECK-NEXT:    %[[BC:.*]] = load i32, i32* %c.ptr
284; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.backedge, label %loop_exit.split
285;
286; CHECK:       loop_exit.split:
287; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ]
288; CHECK-NEXT:    %[[BC_LCSSA:.*]] = phi i32 [ %[[BC]], %loop_b ]
289; CHECK-NEXT:    br label %loop_exit
290
291loop_exit:
292  %ab.phi = phi i32 [ %a, %loop_a ], [ %b, %loop_b ]
293  %c.phi = phi i32 [ %ac, %loop_a ], [ %bc, %loop_b ]
294  %result = add i32 %ab.phi, %c.phi
295  ret i32 %result
296; CHECK:       loop_exit:
297; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA]], %loop_exit.split.us ]
298; CHECK-NEXT:    %[[C_PHI:.*]] = phi i32 [ %[[BC_LCSSA]], %loop_exit.split ], [ %[[AC_LCSSA]], %loop_exit.split.us ]
299; CHECK-NEXT:    %[[RESULT:.*]] = add i32 %[[AB_PHI]], %[[C_PHI]]
300; CHECK-NEXT:    ret i32 %[[RESULT]]
301}
302
303; Test a non-trivial unswitch of an exiting edge to an exit block with other
304; in-loop predecessors.
305define i32 @test3a(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
306; CHECK-LABEL: @test3a(
307entry:
308  br label %loop_begin
309; CHECK-NEXT:  entry:
310; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
311
312loop_begin:
313  %v = load i1, i1* %ptr
314  %a = load i32, i32* %a.ptr
315  br i1 %cond1, label %loop_exit, label %loop_b
316; The 'loop_exit' clone.
317;
318; CHECK:       entry.split.us:
319; CHECK-NEXT:    br label %loop_begin.us
320;
321; CHECK:       loop_begin.us:
322; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
323; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
324; CHECK-NEXT:    br label %loop_exit.split.us
325;
326; CHECK:       loop_exit.split.us:
327; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin.us ]
328; CHECK-NEXT:    br label %loop_exit
329
330loop_b:
331  %b = load i32, i32* %b.ptr
332  br i1 %v, label %loop_begin, label %loop_exit
333; The 'loop_b' unswitched loop.
334;
335; CHECK:       entry.split:
336; CHECK-NEXT:    br label %loop_begin
337;
338; CHECK:       loop_begin:
339; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
340; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
341; CHECK-NEXT:    br label %loop_b
342;
343; CHECK:       loop_b:
344; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
345; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
346;
347; CHECK:       loop_exit.split:
348; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ]
349; CHECK-NEXT:    br label %loop_exit
350
351loop_exit:
352  %ab.phi = phi i32 [ %a, %loop_begin ], [ %b, %loop_b ]
353  ret i32 %ab.phi
354; CHECK:       loop_exit:
355; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA]], %loop_exit.split.us ]
356; CHECK-NEXT:    ret i32 %[[AB_PHI]]
357}
358
359; Test a non-trivial unswitch of an exiting edge to an exit block with other
360; in-loop predecessors. This is the same as @test3a but with the reversed order
361; of successors so that the exiting edge is *not* the cloned edge.
362define i32 @test3b(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
363; CHECK-LABEL: @test3b(
364entry:
365  br label %loop_begin
366; CHECK-NEXT:  entry:
367; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
368
369loop_begin:
370  %v = load i1, i1* %ptr
371  %a = load i32, i32* %a.ptr
372  br i1 %cond1, label %loop_b, label %loop_exit
373; The 'loop_b' unswitched loop.
374;
375; CHECK:       entry.split.us:
376; CHECK-NEXT:    br label %loop_begin.us
377;
378; CHECK:       loop_begin.us:
379; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
380; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
381; CHECK-NEXT:    br label %loop_b.us
382;
383; CHECK:       loop_b.us:
384; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
385; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
386;
387; CHECK:       loop_exit.split.us:
388; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b.us ]
389; CHECK-NEXT:    br label %loop_exit
390
391loop_b:
392  %b = load i32, i32* %b.ptr
393  br i1 %v, label %loop_begin, label %loop_exit
394; The original loop, now non-looping due to unswitching..
395;
396; CHECK:       entry.split:
397; CHECK-NEXT:    br label %loop_begin
398;
399; CHECK:       loop_begin:
400; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
401; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
402; CHECK-NEXT:    br label %loop_exit.split
403;
404; CHECK:       loop_exit.split:
405; CHECK-NEXT:    br label %loop_exit
406
407loop_exit:
408  %ab.phi = phi i32 [ %b, %loop_b ], [ %a, %loop_begin ]
409  ret i32 %ab.phi
410; CHECK:       loop_exit:
411; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[A]], %loop_exit.split ], [ %[[B_LCSSA]], %loop_exit.split.us ]
412; CHECK-NEXT:    ret i32 %[[AB_PHI]]
413}
414
415; Test a non-trivial unswitch of an exiting edge to an exit block with no other
416; in-loop predecessors.
417define void @test4a(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
418; CHECK-LABEL: @test4a(
419entry:
420  br label %loop_begin
421; CHECK-NEXT:  entry:
422; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
423
424loop_begin:
425  %v = load i1, i1* %ptr
426  %a = load i32, i32* %a.ptr
427  br i1 %cond1, label %loop_exit1, label %loop_b
428; The 'loop_exit' clone.
429;
430; CHECK:       entry.split.us:
431; CHECK-NEXT:    br label %loop_begin.us
432;
433; CHECK:       loop_begin.us:
434; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
435; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
436; CHECK-NEXT:    br label %loop_exit1.split.us
437;
438; CHECK:       loop_exit1.split.us:
439; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin.us ]
440; CHECK-NEXT:    br label %loop_exit1
441
442loop_b:
443  %b = load i32, i32* %b.ptr
444  br i1 %v, label %loop_begin, label %loop_exit2
445; The 'loop_b' unswitched loop.
446;
447; CHECK:       entry.split:
448; CHECK-NEXT:    br label %loop_begin
449;
450; CHECK:       loop_begin:
451; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
452; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
453; CHECK-NEXT:    br label %loop_b
454;
455; CHECK:       loop_b:
456; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
457; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit2
458
459loop_exit1:
460  %a.phi = phi i32 [ %a, %loop_begin ]
461  call void @sink1(i32 %a.phi)
462  ret void
463; CHECK:       loop_exit1:
464; CHECK-NEXT:    call void @sink1(i32 %[[A_LCSSA]])
465; CHECK-NEXT:    ret void
466
467loop_exit2:
468  %b.phi = phi i32 [ %b, %loop_b ]
469  call void @sink2(i32 %b.phi)
470  ret void
471; CHECK:       loop_exit2:
472; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ]
473; CHECK-NEXT:    call void @sink2(i32 %[[B_LCSSA]])
474; CHECK-NEXT:    ret void
475}
476
477; Test a non-trivial unswitch of an exiting edge to an exit block with no other
478; in-loop predecessors. This is the same as @test4a but with the edges reversed
479; so that the exiting edge is *not* the cloned edge.
480define void @test4b(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
481; CHECK-LABEL: @test4b(
482entry:
483  br label %loop_begin
484; CHECK-NEXT:  entry:
485; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
486
487loop_begin:
488  %v = load i1, i1* %ptr
489  %a = load i32, i32* %a.ptr
490  br i1 %cond1, label %loop_b, label %loop_exit1
491; The 'loop_b' clone.
492;
493; CHECK:       entry.split.us:
494; CHECK-NEXT:    br label %loop_begin.us
495;
496; CHECK:       loop_begin.us:
497; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
498; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
499; CHECK-NEXT:    br label %loop_b.us
500;
501; CHECK:       loop_b.us:
502; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
503; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit2.split.us
504;
505; CHECK:       loop_exit2.split.us:
506; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b.us ]
507; CHECK-NEXT:    br label %loop_exit2
508
509loop_b:
510  %b = load i32, i32* %b.ptr
511  br i1 %v, label %loop_begin, label %loop_exit2
512; The 'loop_exit' unswitched path.
513;
514; CHECK:       entry.split:
515; CHECK-NEXT:    br label %loop_begin
516;
517; CHECK:       loop_begin:
518; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
519; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
520; CHECK-NEXT:    br label %loop_exit1
521
522loop_exit1:
523  %a.phi = phi i32 [ %a, %loop_begin ]
524  call void @sink1(i32 %a.phi)
525  ret void
526; CHECK:       loop_exit1:
527; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ]
528; CHECK-NEXT:    call void @sink1(i32 %[[A_PHI]])
529; CHECK-NEXT:    ret void
530
531loop_exit2:
532  %b.phi = phi i32 [ %b, %loop_b ]
533  call void @sink2(i32 %b.phi)
534  ret void
535; CHECK:       loop_exit2:
536; CHECK-NEXT:    call void @sink2(i32 %[[B_LCSSA]])
537; CHECK-NEXT:    ret void
538}
539
540; Test a non-trivial unswitch of an exiting edge to an exit block with no other
541; in-loop predecessors. This is the same as @test4a but with a common merge
542; block after the independent loop exits. This requires a different structural
543; update to the dominator tree.
544define void @test4c(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
545; CHECK-LABEL: @test4c(
546entry:
547  br label %loop_begin
548; CHECK-NEXT:  entry:
549; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
550
551loop_begin:
552  %v = load i1, i1* %ptr
553  %a = load i32, i32* %a.ptr
554  br i1 %cond1, label %loop_exit1, label %loop_b
555; The 'loop_exit' clone.
556;
557; CHECK:       entry.split.us:
558; CHECK-NEXT:    br label %loop_begin.us
559;
560; CHECK:       loop_begin.us:
561; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
562; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
563; CHECK-NEXT:    br label %loop_exit1.split.us
564;
565; CHECK:       loop_exit1.split.us:
566; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin.us ]
567; CHECK-NEXT:    br label %loop_exit1
568
569loop_b:
570  %b = load i32, i32* %b.ptr
571  br i1 %v, label %loop_begin, label %loop_exit2
572; The 'loop_b' unswitched loop.
573;
574; CHECK:       entry.split:
575; CHECK-NEXT:    br label %loop_begin
576;
577; CHECK:       loop_begin:
578; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
579; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
580; CHECK-NEXT:    br label %loop_b
581;
582; CHECK:       loop_b:
583; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
584; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit2
585
586loop_exit1:
587  %a.phi = phi i32 [ %a, %loop_begin ]
588  call void @sink1(i32 %a.phi)
589  br label %exit
590; CHECK:       loop_exit1:
591; CHECK-NEXT:    call void @sink1(i32 %[[A_LCSSA]])
592; CHECK-NEXT:    br label %exit
593
594loop_exit2:
595  %b.phi = phi i32 [ %b, %loop_b ]
596  call void @sink2(i32 %b.phi)
597  br label %exit
598; CHECK:       loop_exit2:
599; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ]
600; CHECK-NEXT:    call void @sink2(i32 %[[B_LCSSA]])
601; CHECK-NEXT:    br label %exit
602
603exit:
604  ret void
605; CHECK:       exit:
606; CHECK-NEXT:    ret void
607}
608
609; Test that we can unswitch a condition out of multiple layers of a loop nest.
610define i32 @test5(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
611; CHECK-LABEL: @test5(
612entry:
613  br label %loop_begin
614; CHECK-NEXT:  entry:
615; CHECK-NEXT:    br i1 %cond1, label %loop_begin.split.us, label %entry.split
616;
617; CHECK:       entry.split:
618; CHECK-NEXT:    br label %loop_begin
619;
620; CHECK:       loop_begin:
621; CHECK-NEXT:    br label %loop_begin.split
622
623loop_begin:
624  br label %inner_loop_begin
625
626inner_loop_begin:
627  %v = load i1, i1* %ptr
628  %a = load i32, i32* %a.ptr
629  br i1 %cond1, label %loop_exit, label %inner_loop_b
630; The 'loop_exit' clone.
631;
632; CHECK:       loop_begin.split.us:
633; CHECK-NEXT:    br label %inner_loop_begin.us
634;
635; CHECK:       inner_loop_begin.us:
636; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
637; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
638; CHECK-NEXT:    br label %loop_exit.loopexit.split.us
639;
640; CHECK:       loop_exit.loopexit.split.us:
641; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_begin.us ]
642; CHECK-NEXT:    br label %loop_exit
643
644inner_loop_b:
645  %b = load i32, i32* %b.ptr
646  br i1 %v, label %inner_loop_begin, label %loop_latch
647; The 'inner_loop_b' unswitched loop.
648;
649; CHECK:       loop_begin.split:
650; CHECK-NEXT:    br label %inner_loop_begin
651;
652; CHECK:       inner_loop_begin:
653; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
654; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
655; CHECK-NEXT:    br label %inner_loop_b
656;
657; CHECK:       inner_loop_b:
658; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
659; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_begin, label %loop_latch
660
661loop_latch:
662  %b.phi = phi i32 [ %b, %inner_loop_b ]
663  %v2 = load i1, i1* %ptr
664  br i1 %v2, label %loop_begin, label %loop_exit
665; CHECK:       loop_latch:
666; CHECK-NEXT:    %[[B_INNER_LCSSA:.*]] = phi i32 [ %[[B]], %inner_loop_b ]
667; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr
668; CHECK-NEXT:    br i1 %[[V2]], label %loop_begin, label %loop_exit.loopexit1
669
670loop_exit:
671  %ab.phi = phi i32 [ %a, %inner_loop_begin ], [ %b.phi, %loop_latch ]
672  ret i32 %ab.phi
673; CHECK:       loop_exit.loopexit:
674; CHECK-NEXT:    br label %loop_exit
675;
676; CHECK:       loop_exit.loopexit1:
677; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B_INNER_LCSSA]], %loop_latch ]
678; CHECK-NEXT:    br label %loop_exit
679;
680; CHECK:       loop_exit:
681; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.loopexit ], [ %[[B_LCSSA]], %loop_exit.loopexit1 ]
682; CHECK-NEXT:    ret i32 %[[AB_PHI]]
683}
684
685; Test that we can unswitch a condition where we end up only cloning some of
686; the nested loops and needing to delete some of the nested loops.
687define i32 @test6(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
688; CHECK-LABEL: @test6(
689entry:
690  br label %loop_begin
691; CHECK-NEXT:  entry:
692; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
693
694loop_begin:
695  %v = load i1, i1* %ptr
696  br i1 %cond1, label %loop_a, label %loop_b
697
698loop_a:
699  br label %loop_a_inner
700
701loop_a_inner:
702  %va = load i1, i1* %ptr
703  %a = load i32, i32* %a.ptr
704  br i1 %va, label %loop_a_inner, label %loop_a_inner_exit
705
706loop_a_inner_exit:
707  %a.lcssa = phi i32 [ %a, %loop_a_inner ]
708  br label %latch
709; The 'loop_a' cloned loop.
710;
711; CHECK:       entry.split.us:
712; CHECK-NEXT:    br label %loop_begin.us
713;
714; CHECK:       loop_begin.us:
715; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
716; CHECK-NEXT:    br label %loop_a.us
717;
718; CHECK:       loop_a.us:
719; CHECK-NEXT:    br label %loop_a_inner.us
720;
721; CHECK:       loop_a_inner.us
722; CHECK-NEXT:    %[[VA:.*]] = load i1, i1* %ptr
723; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
724; CHECK-NEXT:    br i1 %[[VA]], label %loop_a_inner.us, label %loop_a_inner_exit.us
725;
726; CHECK:       loop_a_inner_exit.us:
727; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a_inner.us ]
728; CHECK-NEXT:    br label %latch.us
729;
730; CHECK:       latch.us:
731; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %loop_a_inner_exit.us ]
732; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
733;
734; CHECK:       loop_exit.split.us:
735; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_PHI]], %latch.us ]
736; CHECK-NEXT:    br label %loop_exit
737
738loop_b:
739  br label %loop_b_inner
740
741loop_b_inner:
742  %vb = load i1, i1* %ptr
743  %b = load i32, i32* %b.ptr
744  br i1 %vb, label %loop_b_inner, label %loop_b_inner_exit
745
746loop_b_inner_exit:
747  %b.lcssa = phi i32 [ %b, %loop_b_inner ]
748  br label %latch
749
750latch:
751  %ab.phi = phi i32 [ %a.lcssa, %loop_a_inner_exit ], [ %b.lcssa, %loop_b_inner_exit ]
752  br i1 %v, label %loop_begin, label %loop_exit
753; The 'loop_b' unswitched loop.
754;
755; CHECK:       entry.split:
756; CHECK-NEXT:    br label %loop_begin
757;
758; CHECK:       loop_begin:
759; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
760; CHECK-NEXT:    br label %loop_b
761;
762; CHECK:       loop_b:
763; CHECK-NEXT:    br label %loop_b_inner
764;
765; CHECK:       loop_b_inner
766; CHECK-NEXT:    %[[VB:.*]] = load i1, i1* %ptr
767; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
768; CHECK-NEXT:    br i1 %[[VB]], label %loop_b_inner, label %loop_b_inner_exit
769;
770; CHECK:       loop_b_inner_exit:
771; CHECK-NEXT:    %[[B_INNER_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b_inner ]
772; CHECK-NEXT:    br label %latch
773;
774; CHECK:       latch:
775; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
776;
777; CHECK:       loop_exit.split:
778; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B_INNER_LCSSA]], %latch ]
779; CHECK-NEXT:    br label %loop_exit
780
781loop_exit:
782  %ab.lcssa = phi i32 [ %ab.phi, %latch ]
783  ret i32 %ab.lcssa
784; CHECK:       loop_exit:
785; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA]], %loop_exit.split.us ]
786; CHECK-NEXT:    ret i32 %[[AB_PHI]]
787}
788
789; Test that when unswitching a deeply nested loop condition in a way that
790; produces a non-loop clone that can reach multiple exit blocks which are part
791; of different outer loops we correctly divide the cloned loop blocks between
792; the outer loops based on reachability.
793define i32 @test7a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
794; CHECK-LABEL: @test7a(
795entry:
796  br label %loop_begin
797; CHECK-NEXT:  entry:
798; CHECK-NEXT:    br label %loop_begin
799
800loop_begin:
801  %a = load i32, i32* %a.ptr
802  br label %inner_loop_begin
803; CHECK:       loop_begin:
804; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
805; CHECK-NEXT:    br label %inner_loop_begin
806
807inner_loop_begin:
808  %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ]
809  %cond = load i1, i1* %cond.ptr
810  %b = load i32, i32* %b.ptr
811  br label %inner_inner_loop_begin
812; CHECK:       inner_loop_begin:
813; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ]
814; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
815; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
816; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %[[COND]]
817; CHECK-NEXT:    br i1 %[[FROZEN]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
818
819inner_inner_loop_begin:
820  %v1 = load i1, i1* %ptr
821  br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b
822
823inner_inner_loop_a:
824  %v2 = load i1, i1* %ptr
825  br i1 %v2, label %loop_exit, label %inner_inner_loop_c
826
827inner_inner_loop_b:
828  %v3 = load i1, i1* %ptr
829  br i1 %v3, label %inner_inner_loop_exit, label %inner_inner_loop_c
830
831inner_inner_loop_c:
832  %v4 = load i1, i1* %ptr
833  br i1 %v4, label %inner_loop_exit, label %inner_inner_loop_d
834
835inner_inner_loop_d:
836  br i1 %cond, label %inner_loop_exit, label %inner_inner_loop_begin
837; The cloned copy that always exits with the adjustments required to fix up
838; loop exits.
839;
840; CHECK:       inner_loop_begin.split.us:
841; CHECK-NEXT:    br label %inner_inner_loop_begin.us
842;
843; CHECK:       inner_inner_loop_begin.us:
844; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
845; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us
846;
847; CHECK:       inner_inner_loop_b.us:
848; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
849; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_exit.split.us, label %inner_inner_loop_c.us.loopexit
850;
851; CHECK:       inner_inner_loop_a.us:
852; CHECK-NEXT:    %[[A_NEW_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_begin.us ]
853; CHECK-NEXT:    %[[B_NEW_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_begin.us ]
854; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
855; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split.us, label %inner_inner_loop_c.us
856;
857; CHECK:       inner_inner_loop_c.us.loopexit:
858; CHECK-NEXT:    br label %inner_inner_loop_c.us
859;
860; CHECK:       inner_inner_loop_c.us:
861; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
862; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit.split.us, label %inner_inner_loop_d.us
863;
864; CHECK:       inner_inner_loop_d.us:
865; CHECK-NEXT:    br label %inner_loop_exit.loopexit.split
866;
867; CHECK:       inner_inner_loop_exit.split.us:
868; CHECK-NEXT:    br label %inner_inner_loop_exit
869;
870; CHECK:       loop_exit.split.us:
871; CHECK-NEXT:    %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_NEW_LCSSA]], %inner_inner_loop_a.us ]
872; CHECK-NEXT:    %[[B_LCSSA_US:.*]] = phi i32 [ %[[B_NEW_LCSSA]], %inner_inner_loop_a.us ]
873; CHECK-NEXT:    br label %loop_exit
874;
875; CHECK:       inner_loop_exit.loopexit.split.us:
876; CHECK-NEXT:    br label %inner_loop_exit.loopexit
877;
878; The original copy that continues to loop.
879;
880; CHECK:       inner_loop_begin.split:
881; CHECK-NEXT:    br label %inner_inner_loop_begin
882;
883; CHECK:       inner_inner_loop_begin:
884; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
885; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b
886;
887; CHECK:       inner_inner_loop_a:
888; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
889; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split, label %inner_inner_loop_c
890;
891; CHECK:       inner_inner_loop_b:
892; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
893; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_exit.split, label %inner_inner_loop_c
894;
895; CHECK:       inner_inner_loop_c:
896; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
897; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit.split, label %inner_inner_loop_d
898;
899; CHECK:       inner_inner_loop_d:
900; CHECK-NEXT:    br label %inner_inner_loop_begin
901;
902; CHECK:       inner_inner_loop_exit.split:
903; CHECK-NEXT:    br label %inner_inner_loop_exit
904
905inner_inner_loop_exit:
906  %a2 = load i32, i32* %a.ptr
907  %v5 = load i1, i1* %ptr
908  br i1 %v5, label %inner_loop_exit, label %inner_loop_begin
909; CHECK:       inner_inner_loop_exit:
910; CHECK-NEXT:    %[[A2]] = load i32, i32* %a.ptr
911; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
912; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin
913
914inner_loop_exit:
915  br label %loop_begin
916; CHECK:       inner_loop_exit.loopexit.split:
917; CHECK-NEXT:    br label %inner_loop_exit.loopexit
918;
919; CHECK:       inner_loop_exit.loopexit:
920; CHECK-NEXT:    br label %inner_loop_exit
921;
922; CHECK:       inner_loop_exit.loopexit1:
923; CHECK-NEXT:    br label %inner_loop_exit
924;
925; CHECK:       inner_loop_exit:
926; CHECK-NEXT:    br label %loop_begin
927
928loop_exit:
929  %a.lcssa = phi i32 [ %a.phi, %inner_inner_loop_a ]
930  %b.lcssa = phi i32 [ %b, %inner_inner_loop_a ]
931  %result = add i32 %a.lcssa, %b.lcssa
932  ret i32 %result
933; CHECK:       loop_exit.split:
934; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a ]
935; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_a ]
936; CHECK-NEXT:    br label %loop_exit
937;
938; CHECK:       loop_exit:
939; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ]
940; CHECK-NEXT:    %[[B_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[B_LCSSA_US]], %loop_exit.split.us ]
941; CHECK-NEXT:    %[[RESULT:.*]] = add i32 %[[A_PHI]], %[[B_PHI]]
942; CHECK-NEXT:    ret i32 %[[RESULT]]
943}
944
945; Same pattern as @test7a but here the original loop becomes a non-loop that
946; can reach multiple exit blocks which are part of different outer loops.
947define i32 @test7b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
948; CHECK-LABEL: @test7b(
949entry:
950  br label %loop_begin
951; CHECK-NEXT:  entry:
952; CHECK-NEXT:    br label %loop_begin
953
954loop_begin:
955  %a = load i32, i32* %a.ptr
956  br label %inner_loop_begin
957; CHECK:       loop_begin:
958; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
959; CHECK-NEXT:    br label %inner_loop_begin
960
961inner_loop_begin:
962  %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ]
963  %cond = load i1, i1* %cond.ptr
964  %b = load i32, i32* %b.ptr
965  br label %inner_inner_loop_begin
966; CHECK:       inner_loop_begin:
967; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ]
968; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
969; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
970; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %[[COND]]
971; CHECK-NEXT:    br i1 %[[FROZEN]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
972
973inner_inner_loop_begin:
974  %v1 = load i1, i1* %ptr
975  br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b
976
977inner_inner_loop_a:
978  %v2 = load i1, i1* %ptr
979  br i1 %v2, label %loop_exit, label %inner_inner_loop_c
980
981inner_inner_loop_b:
982  %v3 = load i1, i1* %ptr
983  br i1 %v3, label %inner_inner_loop_exit, label %inner_inner_loop_c
984
985inner_inner_loop_c:
986  %v4 = load i1, i1* %ptr
987  br i1 %v4, label %inner_loop_exit, label %inner_inner_loop_d
988
989inner_inner_loop_d:
990  br i1 %cond, label %inner_inner_loop_begin, label %inner_loop_exit
991; The cloned copy that continues looping.
992;
993; CHECK:       inner_loop_begin.split.us:
994; CHECK-NEXT:    br label %inner_inner_loop_begin.us
995;
996; CHECK:       inner_inner_loop_begin.us:
997; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
998; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us
999;
1000; CHECK:       inner_inner_loop_b.us:
1001; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1002; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_exit.split.us, label %inner_inner_loop_c.us
1003;
1004; CHECK:       inner_inner_loop_a.us:
1005; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1006; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split.us, label %inner_inner_loop_c.us
1007;
1008; CHECK:       inner_inner_loop_c.us:
1009; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1010; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit.split.us, label %inner_inner_loop_d.us
1011;
1012; CHECK:       inner_inner_loop_d.us:
1013; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1014;
1015; CHECK:       inner_inner_loop_exit.split.us:
1016; CHECK-NEXT:    br label %inner_inner_loop_exit
1017;
1018; CHECK:       loop_exit.split.us:
1019; CHECK-NEXT:    %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a.us ]
1020; CHECK-NEXT:    %[[B_LCSSA_US:.*]] = phi i32 [ %[[B]], %inner_inner_loop_a.us ]
1021; CHECK-NEXT:    br label %loop_exit
1022;
1023; CHECK:       inner_loop_exit.loopexit.split.us:
1024; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1025;
1026; The original copy that now always exits and needs adjustments for exit
1027; blocks.
1028;
1029; CHECK:       inner_loop_begin.split:
1030; CHECK-NEXT:    br label %inner_inner_loop_begin
1031;
1032; CHECK:       inner_inner_loop_begin:
1033; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1034; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b
1035;
1036; CHECK:       inner_inner_loop_a:
1037; CHECK-NEXT:    %[[A_NEW_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_begin ]
1038; CHECK-NEXT:    %[[B_NEW_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_begin ]
1039; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1040; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split, label %inner_inner_loop_c
1041;
1042; CHECK:       inner_inner_loop_b:
1043; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1044; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_exit.split, label %inner_inner_loop_c.loopexit
1045;
1046; CHECK:       inner_inner_loop_c.loopexit:
1047; CHECK-NEXT:    br label %inner_inner_loop_c
1048;
1049; CHECK:       inner_inner_loop_c:
1050; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1051; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit.split, label %inner_inner_loop_d
1052;
1053; CHECK:       inner_inner_loop_d:
1054; CHECK-NEXT:    br label %inner_loop_exit.loopexit.split
1055;
1056; CHECK:       inner_inner_loop_exit.split:
1057; CHECK-NEXT:    br label %inner_inner_loop_exit
1058
1059inner_inner_loop_exit:
1060  %a2 = load i32, i32* %a.ptr
1061  %v5 = load i1, i1* %ptr
1062  br i1 %v5, label %inner_loop_exit, label %inner_loop_begin
1063; CHECK:       inner_inner_loop_exit:
1064; CHECK-NEXT:    %[[A2]] = load i32, i32* %a.ptr
1065; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1066; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin
1067
1068inner_loop_exit:
1069  br label %loop_begin
1070; CHECK:       inner_loop_exit.loopexit.split:
1071; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1072;
1073; CHECK:       inner_loop_exit.loopexit:
1074; CHECK-NEXT:    br label %inner_loop_exit
1075;
1076; CHECK:       inner_loop_exit.loopexit1:
1077; CHECK-NEXT:    br label %inner_loop_exit
1078;
1079; CHECK:       inner_loop_exit:
1080; CHECK-NEXT:    br label %loop_begin
1081
1082loop_exit:
1083  %a.lcssa = phi i32 [ %a.phi, %inner_inner_loop_a ]
1084  %b.lcssa = phi i32 [ %b, %inner_inner_loop_a ]
1085  %result = add i32 %a.lcssa, %b.lcssa
1086  ret i32 %result
1087; CHECK:       loop_exit.split:
1088; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_NEW_LCSSA]], %inner_inner_loop_a ]
1089; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B_NEW_LCSSA]], %inner_inner_loop_a ]
1090; CHECK-NEXT:    br label %loop_exit
1091;
1092; CHECK:       loop_exit:
1093; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ]
1094; CHECK-NEXT:    %[[B_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[B_LCSSA_US]], %loop_exit.split.us ]
1095; CHECK-NEXT:    %[[RESULT:.*]] = add i32 %[[A_PHI]], %[[B_PHI]]
1096; CHECK-NEXT:    ret i32 %[[RESULT]]
1097}
1098
1099; Test that when the exit block set of an inner loop changes to start at a less
1100; high level of the loop nest we correctly hoist the loop up the nest.
1101define i32 @test8a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1102; CHECK-LABEL: @test8a(
1103entry:
1104  br label %loop_begin
1105; CHECK-NEXT:  entry:
1106; CHECK-NEXT:    br label %loop_begin
1107
1108loop_begin:
1109  %a = load i32, i32* %a.ptr
1110  br label %inner_loop_begin
1111; CHECK:       loop_begin:
1112; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1113; CHECK-NEXT:    br label %inner_loop_begin
1114
1115inner_loop_begin:
1116  %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ]
1117  %cond = load i1, i1* %cond.ptr
1118  %b = load i32, i32* %b.ptr
1119  br label %inner_inner_loop_begin
1120; CHECK:       inner_loop_begin:
1121; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ]
1122; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1123; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1124; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %[[COND]]
1125; CHECK-NEXT:    br i1 %[[FROZEN]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
1126
1127inner_inner_loop_begin:
1128  %v1 = load i1, i1* %ptr
1129  br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b
1130
1131inner_inner_loop_a:
1132  %v2 = load i1, i1* %ptr
1133  br i1 %v2, label %inner_inner_loop_latch, label %inner_loop_exit
1134
1135inner_inner_loop_b:
1136  br i1 %cond, label %inner_inner_loop_latch, label %inner_inner_loop_exit
1137
1138inner_inner_loop_latch:
1139  br label %inner_inner_loop_begin
1140; The cloned region is now an exit from the inner loop.
1141;
1142; CHECK:       inner_loop_begin.split.us:
1143; CHECK-NEXT:    %[[A_INNER_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_begin ]
1144; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1145;
1146; CHECK:       inner_inner_loop_begin.us:
1147; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1148; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us
1149;
1150; CHECK:       inner_inner_loop_b.us:
1151; CHECK-NEXT:    br label %inner_inner_loop_latch.us
1152;
1153; CHECK:       inner_inner_loop_a.us:
1154; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1155; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_latch.us, label %inner_loop_exit.loopexit.split.us
1156;
1157; CHECK:       inner_inner_loop_latch.us:
1158; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1159;
1160; CHECK:       inner_loop_exit.loopexit.split.us:
1161; CHECK-NEXT:    %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA]], %inner_inner_loop_a.us ]
1162; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1163;
1164; The original region exits the loop earlier.
1165;
1166; CHECK:       inner_loop_begin.split:
1167; CHECK-NEXT:    br label %inner_inner_loop_begin
1168;
1169; CHECK:       inner_inner_loop_begin:
1170; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1171; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b
1172;
1173; CHECK:       inner_inner_loop_a:
1174; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1175; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_latch, label %inner_loop_exit.loopexit.split
1176;
1177; CHECK:       inner_inner_loop_b:
1178; CHECK-NEXT:    br label %inner_inner_loop_exit
1179;
1180; CHECK:       inner_inner_loop_latch:
1181; CHECK-NEXT:    br label %inner_inner_loop_begin
1182
1183inner_inner_loop_exit:
1184  %a2 = load i32, i32* %a.ptr
1185  %v4 = load i1, i1* %ptr
1186  br i1 %v4, label %inner_loop_exit, label %inner_loop_begin
1187; CHECK:       inner_inner_loop_exit:
1188; CHECK-NEXT:    %[[A2]] = load i32, i32* %a.ptr
1189; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1190; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin
1191
1192inner_loop_exit:
1193  %v5 = load i1, i1* %ptr
1194  br i1 %v5, label %loop_exit, label %loop_begin
1195; CHECK:       inner_loop_exit.loopexit.split:
1196; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a ]
1197; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1198;
1199; CHECK:       inner_loop_exit.loopexit:
1200; CHECK-NEXT:    %[[A_INNER_US_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit.split ], [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit.split.us ]
1201; CHECK-NEXT:    br label %inner_loop_exit
1202;
1203; CHECK:       inner_loop_exit.loopexit1:
1204; CHECK-NEXT:    %[[A_INNER_LCSSA2:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_exit ]
1205; CHECK-NEXT:    br label %inner_loop_exit
1206;
1207; CHECK:       inner_loop_exit:
1208; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA2]], %inner_loop_exit.loopexit1 ], [ %[[A_INNER_US_PHI]], %inner_loop_exit.loopexit ]
1209; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1210; CHECK-NEXT:    br i1 %[[V]], label %loop_exit, label %loop_begin
1211
1212loop_exit:
1213  %a.lcssa = phi i32 [ %a.phi, %inner_loop_exit ]
1214  ret i32 %a.lcssa
1215; CHECK:       loop_exit:
1216; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ]
1217; CHECK-NEXT:    ret i32 %[[A_LCSSA]]
1218}
1219
1220; Same pattern as @test8a but where the original loop looses an exit block and
1221; needs to be hoisted up the nest.
1222define i32 @test8b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1223; CHECK-LABEL: @test8b(
1224entry:
1225  br label %loop_begin
1226; CHECK-NEXT:  entry:
1227; CHECK-NEXT:    br label %loop_begin
1228
1229loop_begin:
1230  %a = load i32, i32* %a.ptr
1231  br label %inner_loop_begin
1232; CHECK:       loop_begin:
1233; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1234; CHECK-NEXT:    br label %inner_loop_begin
1235
1236inner_loop_begin:
1237  %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ]
1238  %cond = load i1, i1* %cond.ptr
1239  %b = load i32, i32* %b.ptr
1240  br label %inner_inner_loop_begin
1241; CHECK:       inner_loop_begin:
1242; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ]
1243; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1244; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1245; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %[[COND]]
1246; CHECK-NEXT:    br i1 %[[FROZEN]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
1247
1248inner_inner_loop_begin:
1249  %v1 = load i1, i1* %ptr
1250  br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b
1251
1252inner_inner_loop_a:
1253  %v2 = load i1, i1* %ptr
1254  br i1 %v2, label %inner_inner_loop_latch, label %inner_loop_exit
1255
1256inner_inner_loop_b:
1257  br i1 %cond, label %inner_inner_loop_exit, label %inner_inner_loop_latch
1258
1259inner_inner_loop_latch:
1260  br label %inner_inner_loop_begin
1261; The cloned region is similar to before but with one earlier exit.
1262;
1263; CHECK:       inner_loop_begin.split.us:
1264; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1265;
1266; CHECK:       inner_inner_loop_begin.us:
1267; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1268; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us
1269;
1270; CHECK:       inner_inner_loop_b.us:
1271; CHECK-NEXT:    br label %inner_inner_loop_exit.split.us
1272;
1273; CHECK:       inner_inner_loop_a.us:
1274; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1275; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_latch.us, label %inner_loop_exit.loopexit.split.us
1276;
1277; CHECK:       inner_inner_loop_latch.us:
1278; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1279;
1280; CHECK:       inner_inner_loop_exit.split.us:
1281; CHECK-NEXT:    br label %inner_inner_loop_exit
1282;
1283; CHECK:       inner_loop_exit.loopexit.split.us:
1284; CHECK-NEXT:    %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a.us ]
1285; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1286;
1287; The original region is now an exit in the preheader.
1288;
1289; CHECK:       inner_loop_begin.split:
1290; CHECK-NEXT:    %[[A_INNER_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_begin ]
1291; CHECK-NEXT:    br label %inner_inner_loop_begin
1292;
1293; CHECK:       inner_inner_loop_begin:
1294; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1295; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b
1296;
1297; CHECK:       inner_inner_loop_a:
1298; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1299; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_latch, label %inner_loop_exit.loopexit.split
1300;
1301; CHECK:       inner_inner_loop_b:
1302; CHECK-NEXT:    br label %inner_inner_loop_latch
1303;
1304; CHECK:       inner_inner_loop_latch:
1305; CHECK-NEXT:    br label %inner_inner_loop_begin
1306
1307inner_inner_loop_exit:
1308  %a2 = load i32, i32* %a.ptr
1309  %v4 = load i1, i1* %ptr
1310  br i1 %v4, label %inner_loop_exit, label %inner_loop_begin
1311; CHECK:       inner_inner_loop_exit:
1312; CHECK-NEXT:    %[[A2]] = load i32, i32* %a.ptr
1313; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1314; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin
1315
1316inner_loop_exit:
1317  %v5 = load i1, i1* %ptr
1318  br i1 %v5, label %loop_exit, label %loop_begin
1319; CHECK:       inner_loop_exit.loopexit.split:
1320; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA]], %inner_inner_loop_a ]
1321; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1322;
1323; CHECK:       inner_loop_exit.loopexit:
1324; CHECK-NEXT:    %[[A_INNER_US_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit.split ], [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit.split.us ]
1325; CHECK-NEXT:    br label %inner_loop_exit
1326;
1327; CHECK:       inner_loop_exit.loopexit1:
1328; CHECK-NEXT:    %[[A_INNER_LCSSA2:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_exit ]
1329; CHECK-NEXT:    br label %inner_loop_exit
1330;
1331; CHECK:       inner_loop_exit:
1332; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA2]], %inner_loop_exit.loopexit1 ], [ %[[A_INNER_US_PHI]], %inner_loop_exit.loopexit ]
1333; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1334; CHECK-NEXT:    br i1 %[[V]], label %loop_exit, label %loop_begin
1335
1336loop_exit:
1337  %a.lcssa = phi i32 [ %a.phi, %inner_loop_exit ]
1338  ret i32 %a.lcssa
1339; CHECK:       loop_exit:
1340; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ]
1341; CHECK-NEXT:    ret i32 %[[A_LCSSA]]
1342}
1343
1344; Test for when unswitching produces a clone of an inner loop but
1345; the clone no longer has an exiting edge *at all* and loops infinitely.
1346; Because it doesn't ever exit to the outer loop it is no longer an inner loop
1347; but needs to be hoisted up the nest to be a top-level loop.
1348define i32 @test9a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1349; CHECK-LABEL: @test9a(
1350entry:
1351  br label %loop_begin
1352; CHECK-NEXT:  entry:
1353; CHECK-NEXT:    br label %loop_begin
1354
1355loop_begin:
1356  %b = load i32, i32* %b.ptr
1357  %cond = load i1, i1* %cond.ptr
1358  br label %inner_loop_begin
1359; CHECK:       loop_begin:
1360; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1361; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1362; CHECK-NEXT:    br i1 %[[COND]], label %loop_begin.split.us, label %loop_begin.split
1363
1364inner_loop_begin:
1365  %a = load i32, i32* %a.ptr
1366  br i1 %cond, label %inner_loop_latch, label %inner_loop_exit
1367
1368inner_loop_latch:
1369  call void @sink1(i32 %b)
1370  br label %inner_loop_begin
1371; The cloned inner loop ends up as an infinite loop and thus being a top-level
1372; loop with the preheader as an exit block of the outer loop.
1373;
1374; CHECK:       loop_begin.split.us
1375; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_begin ]
1376; CHECK-NEXT:    br label %inner_loop_begin.us
1377;
1378; CHECK:       inner_loop_begin.us:
1379; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1380; CHECK-NEXT:    br label %inner_loop_latch.us
1381;
1382; CHECK:       inner_loop_latch.us:
1383; CHECK-NEXT:    call void @sink1(i32 %[[B_LCSSA]])
1384; CHECK-NEXT:    br label %inner_loop_begin.us
1385;
1386; The original loop becomes boring non-loop code.
1387;
1388; CHECK:       loop_begin.split
1389; CHECK-NEXT:    br label %inner_loop_begin
1390;
1391; CHECK:       inner_loop_begin:
1392; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1393; CHECK-NEXT:    br label %inner_loop_exit
1394
1395inner_loop_exit:
1396  %a.inner_lcssa = phi i32 [ %a, %inner_loop_begin ]
1397  %v = load i1, i1* %ptr
1398  br i1 %v, label %loop_begin, label %loop_exit
1399; CHECK:       inner_loop_exit:
1400; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_begin ]
1401; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1402; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit
1403
1404loop_exit:
1405  %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ]
1406  ret i32 %a.lcssa
1407; CHECK:       loop_exit:
1408; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit ]
1409; CHECK-NEXT:    ret i32 %[[A_LCSSA]]
1410}
1411
1412; The same core pattern as @test9a, but instead of the cloned loop becoming an
1413; infinite loop, the original loop has its only exit unswitched and the
1414; original loop becomes infinite and must be hoisted out of the loop nest.
1415define i32 @test9b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1416; CHECK-LABEL: @test9b(
1417entry:
1418  br label %loop_begin
1419; CHECK-NEXT:  entry:
1420; CHECK-NEXT:    br label %loop_begin
1421
1422loop_begin:
1423  %b = load i32, i32* %b.ptr
1424  %cond = load i1, i1* %cond.ptr
1425  br label %inner_loop_begin
1426; CHECK:       loop_begin:
1427; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1428; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1429; CHECK-NEXT:    br i1 %[[COND]], label %loop_begin.split.us, label %loop_begin.split
1430
1431inner_loop_begin:
1432  %a = load i32, i32* %a.ptr
1433  br i1 %cond, label %inner_loop_exit, label %inner_loop_latch
1434
1435inner_loop_latch:
1436  call void @sink1(i32 %b)
1437  br label %inner_loop_begin
1438; The cloned inner loop becomes a boring non-loop.
1439;
1440; CHECK:       loop_begin.split.us
1441; CHECK-NEXT:    br label %inner_loop_begin.us
1442;
1443; CHECK:       inner_loop_begin.us:
1444; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1445; CHECK-NEXT:    br label %inner_loop_exit.split.us
1446;
1447; CHECK:       inner_loop_exit.split.us
1448; CHECK-NEXT:    %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_loop_begin.us ]
1449; CHECK-NEXT:    br label %inner_loop_exit
1450;
1451; The original loop becomes an infinite loop and thus a top-level loop with the
1452; preheader as an exit block for the outer loop.
1453;
1454; CHECK:       loop_begin.split
1455; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_begin ]
1456; CHECK-NEXT:    br label %inner_loop_begin
1457;
1458; CHECK:       inner_loop_begin:
1459; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1460; CHECK-NEXT:    br label %inner_loop_latch
1461;
1462; CHECK:       inner_loop_latch:
1463; CHECK-NEXT:    call void @sink1(i32 %[[B_LCSSA]])
1464; CHECK-NEXT:    br label %inner_loop_begin
1465
1466inner_loop_exit:
1467  %a.inner_lcssa = phi i32 [ %a, %inner_loop_begin ]
1468  %v = load i1, i1* %ptr
1469  br i1 %v, label %loop_begin, label %loop_exit
1470; CHECK:       inner_loop_exit:
1471; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1472; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit
1473
1474loop_exit:
1475  %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ]
1476  ret i32 %a.lcssa
1477; CHECK:       loop_exit:
1478; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %inner_loop_exit ]
1479; CHECK-NEXT:    ret i32 %[[A_LCSSA]]
1480}
1481
1482; Test that requires re-forming dedicated exits for the cloned loop.
1483define i32 @test10a(i1* %ptr, i1 %cond, i32* %a.ptr) {
1484; CHECK-LABEL: @test10a(
1485entry:
1486  br label %loop_begin
1487; CHECK-NEXT:  entry:
1488; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %cond
1489; CHECK-NEXT:    br i1 %[[FROZEN]], label %entry.split.us, label %entry.split
1490
1491loop_begin:
1492  %a = load i32, i32* %a.ptr
1493  %v1 = load i1, i1* %ptr
1494  br i1 %v1, label %loop_a, label %loop_b
1495
1496loop_a:
1497  %v2 = load i1, i1* %ptr
1498  br i1 %v2, label %loop_exit, label %loop_begin
1499
1500loop_b:
1501  br i1 %cond, label %loop_exit, label %loop_begin
1502; The cloned loop with one edge as a direct exit.
1503;
1504; CHECK:       entry.split.us:
1505; CHECK-NEXT:    br label %loop_begin.us
1506;
1507; CHECK:       loop_begin.us:
1508; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1509; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1510; CHECK-NEXT:    br i1 %[[V]], label %loop_a.us, label %loop_b.us
1511;
1512; CHECK:       loop_b.us:
1513; CHECK-NEXT:    %[[A_LCSSA_B:.*]] = phi i32 [ %[[A]], %loop_begin.us ]
1514; CHECK-NEXT:    br label %loop_exit.split.us
1515;
1516; CHECK:       loop_a.us:
1517; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1518; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split.us.loopexit, label %loop_begin.backedge.us
1519;
1520; CHECK:       loop_begin.backedge.us:
1521; CHECK-NEXT:    br label %loop_begin.us
1522;
1523; CHECK:       loop_exit.split.us.loopexit:
1524; CHECK-NEXT:    %[[A_LCSSA_A:.*]] = phi i32 [ %[[A]], %loop_a.us ]
1525; CHECK-NEXT:    br label %loop_exit
1526;
1527; CHECK:       loop_exit.split.us:
1528; CHECK-NEXT:    %[[A_PHI_US:.*]] = phi i32 [ %[[A_LCSSA_B]], %loop_b.us ], [ %[[A_LCSSA_A]], %loop_exit.split.us.loopexit ]
1529; CHECK-NEXT:    br label %loop_exit
1530
1531; The original loop without one 'loop_exit' edge.
1532;
1533; CHECK:       entry.split:
1534; CHECK-NEXT:    br label %loop_begin
1535;
1536; CHECK:       loop_begin:
1537; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1538; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1539; CHECK-NEXT:    br i1 %[[V]], label %loop_a, label %loop_b
1540;
1541; CHECK:       loop_a:
1542; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1543; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split, label %loop_begin.backedge
1544;
1545; CHECK:       loop_begin.backedge:
1546; CHECK-NEXT:    br label %loop_begin
1547;
1548; CHECK:       loop_b:
1549; CHECK-NEXT:    br label %loop_begin.backedge
1550;
1551; CHECK:       loop_exit.split:
1552; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a ]
1553; CHECK-NEXT:    br label %loop_exit
1554
1555loop_exit:
1556  %a.lcssa = phi i32 [ %a, %loop_a ], [ %a, %loop_b ]
1557  ret i32 %a.lcssa
1558; CHECK:       loop_exit:
1559; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[A_PHI_US]], %loop_exit.split.us ]
1560; CHECK-NEXT:    ret i32 %[[A_PHI]]
1561}
1562
1563; Test that requires re-forming dedicated exits for the original loop.
1564define i32 @test10b(i1* %ptr, i1 %cond, i32* %a.ptr) {
1565; CHECK-LABEL: @test10b(
1566entry:
1567  br label %loop_begin
1568; CHECK-NEXT:  entry:
1569; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %cond
1570; CHECK-NEXT:    br i1 %[[FROZEN]], label %entry.split.us, label %entry.split
1571
1572loop_begin:
1573  %a = load i32, i32* %a.ptr
1574  %v1 = load i1, i1* %ptr
1575  br i1 %v1, label %loop_a, label %loop_b
1576
1577loop_a:
1578  %v2 = load i1, i1* %ptr
1579  br i1 %v2, label %loop_begin, label %loop_exit
1580
1581loop_b:
1582  br i1 %cond, label %loop_begin, label %loop_exit
1583; The cloned loop without one of the exits.
1584;
1585; CHECK:       entry.split.us:
1586; CHECK-NEXT:    br label %loop_begin.us
1587;
1588; CHECK:       loop_begin.us:
1589; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1590; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1591; CHECK-NEXT:    br i1 %[[V]], label %loop_a.us, label %loop_b.us
1592;
1593; CHECK:       loop_b.us:
1594; CHECK-NEXT:    br label %loop_begin.backedge.us
1595;
1596; CHECK:       loop_a.us:
1597; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1598; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.backedge.us, label %loop_exit.split.us
1599;
1600; CHECK:       loop_begin.backedge.us:
1601; CHECK-NEXT:    br label %loop_begin.us
1602;
1603; CHECK:       loop_exit.split.us:
1604; CHECK-NEXT:    %[[A_LCSSA_US:.*]] = phi i32 [ %[[A]], %loop_a.us ]
1605; CHECK-NEXT:    br label %loop_exit
1606
1607; The original loop without one 'loop_exit' edge.
1608;
1609; CHECK:       entry.split:
1610; CHECK-NEXT:    br label %loop_begin
1611;
1612; CHECK:       loop_begin:
1613; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1614; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1615; CHECK-NEXT:    br i1 %[[V]], label %loop_a, label %loop_b
1616;
1617; CHECK:       loop_a:
1618; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1619; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.backedge, label %loop_exit.split.loopexit
1620;
1621; CHECK:       loop_begin.backedge:
1622; CHECK-NEXT:    br label %loop_begin
1623;
1624; CHECK:       loop_b:
1625; CHECK-NEXT:    %[[A_LCSSA_B:.*]] = phi i32 [ %[[A]], %loop_begin ]
1626; CHECK-NEXT:    br label %loop_exit.split
1627;
1628; CHECK:       loop_exit.split.loopexit:
1629; CHECK-NEXT:    %[[A_LCSSA_A:.*]] = phi i32 [ %[[A]], %loop_a ]
1630; CHECK-NEXT:    br label %loop_exit.split
1631;
1632; CHECK:       loop_exit.split:
1633; CHECK-NEXT:    %[[A_PHI_SPLIT:.*]] = phi i32 [ %[[A_LCSSA_B]], %loop_b ], [ %[[A_LCSSA_A]], %loop_exit.split.loopexit ]
1634; CHECK-NEXT:    br label %loop_exit
1635
1636loop_exit:
1637  %a.lcssa = phi i32 [ %a, %loop_a ], [ %a, %loop_b ]
1638  ret i32 %a.lcssa
1639; CHECK:       loop_exit:
1640; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_PHI_SPLIT]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ]
1641; CHECK-NEXT:    ret i32 %[[A_PHI]]
1642}
1643
1644; Check that if a cloned inner loop after unswitching doesn't loop and directly
1645; exits even an outer loop, we don't add the cloned preheader to the outer
1646; loop and do add the needed LCSSA phi nodes for the new exit block from the
1647; outer loop.
1648define i32 @test11a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1649; CHECK-LABEL: @test11a(
1650entry:
1651  br label %loop_begin
1652; CHECK-NEXT:  entry:
1653; CHECK-NEXT:    br label %loop_begin
1654
1655loop_begin:
1656  %b = load i32, i32* %b.ptr
1657  %v1 = load i1, i1* %ptr
1658  br i1 %v1, label %loop_latch, label %inner_loop_ph
1659; CHECK:       loop_begin:
1660; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1661; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1662; CHECK-NEXT:    br i1 %[[V]], label %loop_latch, label %inner_loop_ph
1663
1664inner_loop_ph:
1665  %cond = load i1, i1* %cond.ptr
1666  br label %inner_loop_begin
1667; CHECK:       inner_loop_ph:
1668; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1669; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %[[COND]]
1670; CHECK-NEXT:    br i1 %[[FROZEN]], label %inner_loop_ph.split.us, label %inner_loop_ph.split
1671
1672inner_loop_begin:
1673  call void @sink1(i32 %b)
1674  %a = load i32, i32* %a.ptr
1675  br i1 %cond, label %loop_exit, label %inner_loop_a
1676
1677inner_loop_a:
1678  %v2 = load i1, i1* %ptr
1679  br i1 %v2, label %inner_loop_exit, label %inner_loop_begin
1680; The cloned path doesn't actually loop and is an exit from the outer loop as
1681; well.
1682;
1683; CHECK:       inner_loop_ph.split.us:
1684; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_loop_ph ]
1685; CHECK-NEXT:    br label %inner_loop_begin.us
1686;
1687; CHECK:       inner_loop_begin.us:
1688; CHECK-NEXT:    call void @sink1(i32 %[[B_LCSSA]])
1689; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1690; CHECK-NEXT:    br label %loop_exit.loopexit.split.us
1691;
1692; CHECK:       loop_exit.loopexit.split.us:
1693; CHECK-NEXT:    %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_loop_begin.us ]
1694; CHECK-NEXT:    br label %loop_exit.loopexit
1695;
1696; The original remains a loop losing the exit edge.
1697;
1698; CHECK:       inner_loop_ph.split:
1699; CHECK-NEXT:    br label %inner_loop_begin
1700;
1701; CHECK:       inner_loop_begin:
1702; CHECK-NEXT:    call void @sink1(i32 %[[B]])
1703; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1704; CHECK-NEXT:    br label %inner_loop_a
1705;
1706; CHECK:       inner_loop_a:
1707; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1708; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit, label %inner_loop_begin
1709
1710inner_loop_exit:
1711  %a.inner_lcssa = phi i32 [ %a, %inner_loop_a ]
1712  %v3 = load i1, i1* %ptr
1713  br i1 %v3, label %loop_latch, label %loop_exit
1714; CHECK:       inner_loop_exit:
1715; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_a ]
1716; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1717; CHECK-NEXT:    br i1 %[[V]], label %loop_latch, label %loop_exit.loopexit1
1718
1719loop_latch:
1720  br label %loop_begin
1721; CHECK:       loop_latch:
1722; CHECK-NEXT:    br label %loop_begin
1723
1724loop_exit:
1725  %a.lcssa = phi i32 [ %a, %inner_loop_begin ], [ %a.inner_lcssa, %inner_loop_exit ]
1726  ret i32 %a.lcssa
1727; CHECK:       loop_exit.loopexit:
1728; CHECK-NEXT:    br label %loop_exit
1729;
1730; CHECK:       loop_exit.loopexit1:
1731; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit ]
1732; CHECK-NEXT:    br label %loop_exit
1733;
1734; CHECK:       loop_exit:
1735; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %loop_exit.loopexit ], [ %[[A_LCSSA]], %loop_exit.loopexit1 ]
1736; CHECK-NEXT:    ret i32 %[[A_PHI]]
1737}
1738
1739; Check that if the original inner loop after unswitching doesn't loop and
1740; directly exits even an outer loop, we remove the original preheader from the
1741; outer loop and add needed LCSSA phi nodes for the new exit block from the
1742; outer loop.
1743define i32 @test11b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1744; CHECK-LABEL: @test11b(
1745entry:
1746  br label %loop_begin
1747; CHECK-NEXT:  entry:
1748; CHECK-NEXT:    br label %loop_begin
1749
1750loop_begin:
1751  %b = load i32, i32* %b.ptr
1752  %v1 = load i1, i1* %ptr
1753  br i1 %v1, label %loop_latch, label %inner_loop_ph
1754; CHECK:       loop_begin:
1755; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1756; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1757; CHECK-NEXT:    br i1 %[[V]], label %loop_latch, label %inner_loop_ph
1758
1759inner_loop_ph:
1760  %cond = load i1, i1* %cond.ptr
1761  br label %inner_loop_begin
1762; CHECK:       inner_loop_ph:
1763; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1764; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %[[COND]]
1765; CHECK-NEXT:    br i1 %[[FROZEN]], label %inner_loop_ph.split.us, label %inner_loop_ph.split
1766
1767inner_loop_begin:
1768  call void @sink1(i32 %b)
1769  %a = load i32, i32* %a.ptr
1770  br i1 %cond, label %inner_loop_a, label %loop_exit
1771
1772inner_loop_a:
1773  %v2 = load i1, i1* %ptr
1774  br i1 %v2, label %inner_loop_exit, label %inner_loop_begin
1775; The cloned path continues to loop without the exit out of the entire nest.
1776;
1777; CHECK:       inner_loop_ph.split.us:
1778; CHECK-NEXT:    br label %inner_loop_begin.us
1779;
1780; CHECK:       inner_loop_begin.us:
1781; CHECK-NEXT:    call void @sink1(i32 %[[B]])
1782; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1783; CHECK-NEXT:    br label %inner_loop_a.us
1784;
1785; CHECK:       inner_loop_a.us:
1786; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1787; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.split.us, label %inner_loop_begin.us
1788;
1789; CHECK:       inner_loop_exit.split.us:
1790; CHECK-NEXT:    %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_loop_a.us ]
1791; CHECK-NEXT:    br label %inner_loop_exit
1792;
1793; The original remains a loop losing the exit edge.
1794;
1795; CHECK:       inner_loop_ph.split:
1796; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_loop_ph ]
1797; CHECK-NEXT:    br label %inner_loop_begin
1798;
1799; CHECK:       inner_loop_begin:
1800; CHECK-NEXT:    call void @sink1(i32 %[[B_LCSSA]])
1801; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1802; CHECK-NEXT:    br label %loop_exit.loopexit
1803
1804inner_loop_exit:
1805  %a.inner_lcssa = phi i32 [ %a, %inner_loop_a ]
1806  %v3 = load i1, i1* %ptr
1807  br i1 %v3, label %loop_latch, label %loop_exit
1808; CHECK:       inner_loop_exit:
1809; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1810; CHECK-NEXT:    br i1 %[[V]], label %loop_latch, label %loop_exit.loopexit1
1811
1812loop_latch:
1813  br label %loop_begin
1814; CHECK:       loop_latch:
1815; CHECK-NEXT:    br label %loop_begin
1816
1817loop_exit:
1818  %a.lcssa = phi i32 [ %a, %inner_loop_begin ], [ %a.inner_lcssa, %inner_loop_exit ]
1819  ret i32 %a.lcssa
1820; CHECK:       loop_exit.loopexit:
1821; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_begin ]
1822; CHECK-NEXT:    br label %loop_exit
1823;
1824; CHECK:       loop_exit.loopexit1:
1825; CHECK-NEXT:    %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %inner_loop_exit ]
1826; CHECK-NEXT:    br label %loop_exit
1827;
1828; CHECK:       loop_exit:
1829; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.loopexit ], [ %[[A_LCSSA_US]], %loop_exit.loopexit1 ]
1830; CHECK-NEXT:    ret i32 %[[A_PHI]]
1831}
1832
1833; Like test11a, but checking that when the whole thing is wrapped in yet
1834; another loop, we correctly attribute the cloned preheader to that outermost
1835; loop rather than only handling the case where the preheader is not in any loop
1836; at all.
1837define i32 @test12a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1838; CHECK-LABEL: @test12a(
1839entry:
1840  br label %loop_begin
1841; CHECK-NEXT:  entry:
1842; CHECK-NEXT:    br label %loop_begin
1843
1844loop_begin:
1845  br label %inner_loop_begin
1846; CHECK:       loop_begin:
1847; CHECK-NEXT:    br label %inner_loop_begin
1848
1849inner_loop_begin:
1850  %b = load i32, i32* %b.ptr
1851  %v1 = load i1, i1* %ptr
1852  br i1 %v1, label %inner_loop_latch, label %inner_inner_loop_ph
1853; CHECK:       inner_loop_begin:
1854; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1855; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1856; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_latch, label %inner_inner_loop_ph
1857
1858inner_inner_loop_ph:
1859  %cond = load i1, i1* %cond.ptr
1860  br label %inner_inner_loop_begin
1861; CHECK:       inner_inner_loop_ph:
1862; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1863; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %[[COND]]
1864; CHECK-NEXT:    br i1 %[[FROZEN]], label %inner_inner_loop_ph.split.us, label %inner_inner_loop_ph.split
1865
1866inner_inner_loop_begin:
1867  call void @sink1(i32 %b)
1868  %a = load i32, i32* %a.ptr
1869  br i1 %cond, label %inner_loop_exit, label %inner_inner_loop_a
1870
1871inner_inner_loop_a:
1872  %v2 = load i1, i1* %ptr
1873  br i1 %v2, label %inner_inner_loop_exit, label %inner_inner_loop_begin
1874; The cloned path doesn't actually loop and is an exit from the outer loop as
1875; well.
1876;
1877; CHECK:       inner_inner_loop_ph.split.us:
1878; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_ph ]
1879; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1880;
1881; CHECK:       inner_inner_loop_begin.us:
1882; CHECK-NEXT:    call void @sink1(i32 %[[B_LCSSA]])
1883; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1884; CHECK-NEXT:    br label %inner_loop_exit.loopexit.split.us
1885;
1886; CHECK:       inner_loop_exit.loopexit.split.us:
1887; CHECK-NEXT:    %[[A_INNER_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_inner_loop_begin.us ]
1888; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1889;
1890; The original remains a loop losing the exit edge.
1891;
1892; CHECK:       inner_inner_loop_ph.split:
1893; CHECK-NEXT:    br label %inner_inner_loop_begin
1894;
1895; CHECK:       inner_inner_loop_begin:
1896; CHECK-NEXT:    call void @sink1(i32 %[[B]])
1897; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1898; CHECK-NEXT:    br label %inner_inner_loop_a
1899;
1900; CHECK:       inner_inner_loop_a:
1901; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1902; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_exit, label %inner_inner_loop_begin
1903
1904inner_inner_loop_exit:
1905  %a.inner_inner_lcssa = phi i32 [ %a, %inner_inner_loop_a ]
1906  %v3 = load i1, i1* %ptr
1907  br i1 %v3, label %inner_loop_latch, label %inner_loop_exit
1908; CHECK:       inner_inner_loop_exit:
1909; CHECK-NEXT:    %[[A_INNER_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_inner_loop_a ]
1910; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1911; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_latch, label %inner_loop_exit.loopexit1
1912
1913inner_loop_latch:
1914  br label %inner_loop_begin
1915; CHECK:       inner_loop_latch:
1916; CHECK-NEXT:    br label %inner_loop_begin
1917
1918inner_loop_exit:
1919  %a.inner_lcssa = phi i32 [ %a, %inner_inner_loop_begin ], [ %a.inner_inner_lcssa, %inner_inner_loop_exit ]
1920  %v4 = load i1, i1* %ptr
1921  br i1 %v4, label %loop_begin, label %loop_exit
1922; CHECK:       inner_loop_exit.loopexit:
1923; CHECK-NEXT:    br label %inner_loop_exit
1924;
1925; CHECK:       inner_loop_exit.loopexit1:
1926; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA]], %inner_inner_loop_exit ]
1927; CHECK-NEXT:    br label %inner_loop_exit
1928;
1929; CHECK:       inner_loop_exit:
1930; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA_US]], %inner_loop_exit.loopexit ], [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit1 ]
1931; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1932; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit
1933
1934loop_exit:
1935  %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ]
1936  ret i32 %a.lcssa
1937; CHECK:       loop_exit:
1938; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ]
1939; CHECK-NEXT:    ret i32 %[[A_LCSSA]]
1940}
1941
1942; Like test11b, but checking that when the whole thing is wrapped in yet
1943; another loop, we correctly sink the preheader to the outermost loop rather
1944; than only handling the case where the preheader is completely removed from
1945; a loop.
1946define i32 @test12b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1947; CHECK-LABEL: @test12b(
1948entry:
1949  br label %loop_begin
1950; CHECK-NEXT:  entry:
1951; CHECK-NEXT:    br label %loop_begin
1952
1953loop_begin:
1954  br label %inner_loop_begin
1955; CHECK:       loop_begin:
1956; CHECK-NEXT:    br label %inner_loop_begin
1957
1958inner_loop_begin:
1959  %b = load i32, i32* %b.ptr
1960  %v1 = load i1, i1* %ptr
1961  br i1 %v1, label %inner_loop_latch, label %inner_inner_loop_ph
1962; CHECK:       inner_loop_begin:
1963; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1964; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1965; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_latch, label %inner_inner_loop_ph
1966
1967inner_inner_loop_ph:
1968  %cond = load i1, i1* %cond.ptr
1969  br label %inner_inner_loop_begin
1970; CHECK:       inner_inner_loop_ph:
1971; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1972; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %[[COND]]
1973; CHECK-NEXT:    br i1 %[[FROZEN]], label %inner_inner_loop_ph.split.us, label %inner_inner_loop_ph.split
1974
1975inner_inner_loop_begin:
1976  call void @sink1(i32 %b)
1977  %a = load i32, i32* %a.ptr
1978  br i1 %cond, label %inner_inner_loop_a, label %inner_loop_exit
1979
1980inner_inner_loop_a:
1981  %v2 = load i1, i1* %ptr
1982  br i1 %v2, label %inner_inner_loop_exit, label %inner_inner_loop_begin
1983; The cloned path continues to loop without the exit out of the entire nest.
1984;
1985; CHECK:       inner_inner_loop_ph.split.us:
1986; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1987;
1988; CHECK:       inner_inner_loop_begin.us:
1989; CHECK-NEXT:    call void @sink1(i32 %[[B]])
1990; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1991; CHECK-NEXT:    br label %inner_inner_loop_a.us
1992;
1993; CHECK:       inner_inner_loop_a.us:
1994; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1995; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_exit.split.us, label %inner_inner_loop_begin.us
1996;
1997; CHECK:       inner_inner_loop_exit.split.us:
1998; CHECK-NEXT:    %[[A_INNER_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_inner_loop_a.us ]
1999; CHECK-NEXT:    br label %inner_inner_loop_exit
2000;
2001; The original remains a loop losing the exit edge.
2002;
2003; CHECK:       inner_inner_loop_ph.split:
2004; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_ph ]
2005; CHECK-NEXT:    br label %inner_inner_loop_begin
2006;
2007; CHECK:       inner_inner_loop_begin:
2008; CHECK-NEXT:    call void @sink1(i32 %[[B_LCSSA]])
2009; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
2010; CHECK-NEXT:    br label %inner_loop_exit.loopexit
2011
2012inner_inner_loop_exit:
2013  %a.inner_inner_lcssa = phi i32 [ %a, %inner_inner_loop_a ]
2014  %v3 = load i1, i1* %ptr
2015  br i1 %v3, label %inner_loop_latch, label %inner_loop_exit
2016; CHECK:       inner_inner_loop_exit:
2017; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2018; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_latch, label %inner_loop_exit.loopexit1
2019
2020inner_loop_latch:
2021  br label %inner_loop_begin
2022; CHECK:       inner_loop_latch:
2023; CHECK-NEXT:    br label %inner_loop_begin
2024
2025inner_loop_exit:
2026  %a.inner_lcssa = phi i32 [ %a, %inner_inner_loop_begin ], [ %a.inner_inner_lcssa, %inner_inner_loop_exit ]
2027  %v4 = load i1, i1* %ptr
2028  br i1 %v4, label %loop_begin, label %loop_exit
2029; CHECK:       inner_loop_exit.loopexit:
2030; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_inner_loop_begin ]
2031; CHECK-NEXT:    br label %inner_loop_exit
2032;
2033; CHECK:       inner_loop_exit.loopexit1:
2034; CHECK-NEXT:    %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA_US]], %inner_inner_loop_exit ]
2035; CHECK-NEXT:    br label %inner_loop_exit
2036;
2037; CHECK:       inner_loop_exit:
2038; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit ], [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit1 ]
2039; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2040; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit
2041
2042loop_exit:
2043  %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ]
2044  ret i32 %a.lcssa
2045; CHECK:       loop_exit:
2046; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ]
2047; CHECK-NEXT:    ret i32 %[[A_LCSSA]]
2048}
2049
2050; Test where the cloned loop has an inner loop that has to be traversed to form
2051; the cloned loop, and where this inner loop has multiple blocks, and where the
2052; exiting block that connects the inner loop to the cloned loop is not the header
2053; block. This ensures that we correctly handle interesting corner cases of
2054; traversing back to the header when establishing the cloned loop.
2055define i32 @test13a(i1* %ptr, i1 %cond, i32* %a.ptr, i32* %b.ptr) {
2056; CHECK-LABEL: @test13a(
2057entry:
2058  br label %loop_begin
2059; CHECK-NEXT:  entry:
2060; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %cond
2061; CHECK-NEXT:    br i1 %[[FROZEN]], label %entry.split.us, label %entry.split
2062
2063loop_begin:
2064  %a = load i32, i32* %a.ptr
2065  %v1 = load i1, i1* %ptr
2066  br i1 %v1, label %loop_a, label %loop_b
2067
2068loop_a:
2069  %v2 = load i1, i1* %ptr
2070  br i1 %v2, label %loop_exit, label %loop_latch
2071
2072loop_b:
2073  %b = load i32, i32* %b.ptr
2074  br i1 %cond, label %loop_b_inner_ph, label %loop_exit
2075
2076loop_b_inner_ph:
2077  br label %loop_b_inner_header
2078
2079loop_b_inner_header:
2080  %v3 = load i1, i1* %ptr
2081  br i1 %v3, label %loop_b_inner_latch, label %loop_b_inner_body
2082
2083loop_b_inner_body:
2084  %v4 = load i1, i1* %ptr
2085  br i1 %v4, label %loop_b_inner_latch, label %loop_b_inner_exit
2086
2087loop_b_inner_latch:
2088  br label %loop_b_inner_header
2089
2090loop_b_inner_exit:
2091  br label %loop_latch
2092
2093loop_latch:
2094  br label %loop_begin
2095; The cloned loop contains an inner loop within it.
2096;
2097; CHECK:       entry.split.us:
2098; CHECK-NEXT:    br label %loop_begin.us
2099;
2100; CHECK:       loop_begin.us:
2101; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
2102; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2103; CHECK-NEXT:    br i1 %[[V]], label %loop_a.us, label %loop_b.us
2104;
2105; CHECK:       loop_b.us:
2106; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
2107; CHECK-NEXT:    br label %loop_b_inner_ph.us
2108;
2109; CHECK:       loop_b_inner_ph.us:
2110; CHECK-NEXT:    br label %loop_b_inner_header.us
2111;
2112; CHECK:       loop_b_inner_header.us:
2113; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2114; CHECK-NEXT:    br i1 %[[V]], label %loop_b_inner_latch.us, label %loop_b_inner_body.us
2115;
2116; CHECK:       loop_b_inner_body.us:
2117; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2118; CHECK-NEXT:    br i1 %[[V]], label %loop_b_inner_latch.us, label %loop_b_inner_exit.us
2119;
2120; CHECK:       loop_b_inner_exit.us:
2121; CHECK-NEXT:    br label %loop_latch.us
2122;
2123; CHECK:       loop_b_inner_latch.us:
2124; CHECK-NEXT:    br label %loop_b_inner_header.us
2125;
2126; CHECK:       loop_a.us:
2127; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2128; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split.us, label %loop_latch.us
2129;
2130; CHECK:       loop_latch.us:
2131; CHECK-NEXT:    br label %loop_begin.us
2132;
2133; CHECK:       loop_exit.split.us:
2134; CHECK-NEXT:    %[[A_LCSSA_US:.*]] = phi i32 [ %[[A]], %loop_a.us ]
2135; CHECK-NEXT:    br label %loop_exit
2136;
2137; And the original loop no longer contains an inner loop.
2138;
2139; CHECK:       entry.split:
2140; CHECK-NEXT:    br label %loop_begin
2141;
2142; CHECK:       loop_begin:
2143; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
2144; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2145; CHECK-NEXT:    br i1 %[[V]], label %loop_a, label %loop_b
2146;
2147; CHECK:       loop_a:
2148; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2149; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split.loopexit, label %loop_latch
2150;
2151; CHECK:       loop_b:
2152; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
2153; CHECK-NEXT:    br label %loop_exit.split
2154;
2155; CHECK:       loop_latch:
2156; CHECK-NEXT:    br label %loop_begin
2157
2158loop_exit:
2159  %lcssa = phi i32 [ %a, %loop_a ], [ %b, %loop_b ]
2160  ret i32 %lcssa
2161; CHECK:       loop_exit.split.loopexit:
2162; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a ]
2163; CHECK-NEXT:    br label %loop_exit.split
2164;
2165; CHECK:       loop_exit.split:
2166; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[B]], %loop_b ], [ %[[A_LCSSA]], %loop_exit.split.loopexit ]
2167; CHECK-NEXT:    br label %loop_exit
2168;
2169; CHECK:       loop_exit:
2170; CHECK-NEXT:    %[[AB_PHI_US:.*]] = phi i32 [ %[[AB_PHI]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ]
2171; CHECK-NEXT:    ret i32 %[[AB_PHI_US]]
2172}
2173
2174; Test where the original loop has an inner loop that has to be traversed to
2175; rebuild the loop, and where this inner loop has multiple blocks, and where
2176; the exiting block that connects the inner loop to the original loop is not
2177; the header block. This ensures that we correctly handle interesting corner
2178; cases of traversing back to the header when re-establishing the original loop
2179; still exists after unswitching.
2180define i32 @test13b(i1* %ptr, i1 %cond, i32* %a.ptr, i32* %b.ptr) {
2181; CHECK-LABEL: @test13b(
2182entry:
2183  br label %loop_begin
2184; CHECK-NEXT:  entry:
2185; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %cond
2186; CHECK-NEXT:    br i1 %[[FROZEN]], label %entry.split.us, label %entry.split
2187
2188loop_begin:
2189  %a = load i32, i32* %a.ptr
2190  %v1 = load i1, i1* %ptr
2191  br i1 %v1, label %loop_a, label %loop_b
2192
2193loop_a:
2194  %v2 = load i1, i1* %ptr
2195  br i1 %v2, label %loop_exit, label %loop_latch
2196
2197loop_b:
2198  %b = load i32, i32* %b.ptr
2199  br i1 %cond, label %loop_exit, label %loop_b_inner_ph
2200
2201loop_b_inner_ph:
2202  br label %loop_b_inner_header
2203
2204loop_b_inner_header:
2205  %v3 = load i1, i1* %ptr
2206  br i1 %v3, label %loop_b_inner_latch, label %loop_b_inner_body
2207
2208loop_b_inner_body:
2209  %v4 = load i1, i1* %ptr
2210  br i1 %v4, label %loop_b_inner_latch, label %loop_b_inner_exit
2211
2212loop_b_inner_latch:
2213  br label %loop_b_inner_header
2214
2215loop_b_inner_exit:
2216  br label %loop_latch
2217
2218loop_latch:
2219  br label %loop_begin
2220; The cloned loop doesn't contain an inner loop.
2221;
2222; CHECK:       entry.split.us:
2223; CHECK-NEXT:    br label %loop_begin.us
2224;
2225; CHECK:       loop_begin.us:
2226; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
2227; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2228; CHECK-NEXT:    br i1 %[[V]], label %loop_a.us, label %loop_b.us
2229;
2230; CHECK:       loop_b.us:
2231; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
2232; CHECK-NEXT:    br label %loop_exit.split.us
2233;
2234; CHECK:       loop_a.us:
2235; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2236; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split.us.loopexit, label %loop_latch.us
2237;
2238; CHECK:       loop_latch.us:
2239; CHECK-NEXT:    br label %loop_begin.us
2240;
2241; CHECK:       loop_exit.split.us.loopexit:
2242; CHECK-NEXT:    %[[A_LCSSA_US:.*]] = phi i32 [ %[[A]], %loop_a.us ]
2243; CHECK-NEXT:    br label %loop_exit.split.us
2244;
2245; CHECK:       loop_exit.split.us:
2246; CHECK-NEXT:    %[[AB_PHI_US:.*]] = phi i32 [ %[[B]], %loop_b.us ], [ %[[A_LCSSA_US]], %loop_exit.split.us.loopexit ]
2247; CHECK-NEXT:    br label %loop_exit
2248;
2249; But the original loop contains an inner loop that must be traversed.;
2250;
2251; CHECK:       entry.split:
2252; CHECK-NEXT:    br label %loop_begin
2253;
2254; CHECK:       loop_begin:
2255; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
2256; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2257; CHECK-NEXT:    br i1 %[[V]], label %loop_a, label %loop_b
2258;
2259; CHECK:       loop_a:
2260; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2261; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split, label %loop_latch
2262;
2263; CHECK:       loop_b:
2264; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
2265; CHECK-NEXT:    br label %loop_b_inner_ph
2266;
2267; CHECK:       loop_b_inner_ph:
2268; CHECK-NEXT:    br label %loop_b_inner_header
2269;
2270; CHECK:       loop_b_inner_header:
2271; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2272; CHECK-NEXT:    br i1 %[[V]], label %loop_b_inner_latch, label %loop_b_inner_body
2273;
2274; CHECK:       loop_b_inner_body:
2275; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2276; CHECK-NEXT:    br i1 %[[V]], label %loop_b_inner_latch, label %loop_b_inner_exit
2277;
2278; CHECK:       loop_b_inner_latch:
2279; CHECK-NEXT:    br label %loop_b_inner_header
2280;
2281; CHECK:       loop_b_inner_exit:
2282; CHECK-NEXT:    br label %loop_latch
2283;
2284; CHECK:       loop_latch:
2285; CHECK-NEXT:    br label %loop_begin
2286
2287loop_exit:
2288  %lcssa = phi i32 [ %a, %loop_a ], [ %b, %loop_b ]
2289  ret i32 %lcssa
2290; CHECK:       loop_exit.split:
2291; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a ]
2292; CHECK-NEXT:    br label %loop_exit
2293;
2294; CHECK:       loop_exit:
2295; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[AB_PHI_US]], %loop_exit.split.us ]
2296; CHECK-NEXT:    ret i32 %[[AB_PHI]]
2297}
2298
2299define i32 @test20(i32* %var, i32 %cond1, i32 %cond2) {
2300; CHECK-LABEL: @test20(
2301entry:
2302  br label %loop_begin
2303; CHECK-NEXT:  entry:
2304; CHECK-NEXT:    switch i32 %cond2, label %[[ENTRY_SPLIT_EXIT:.*]] [
2305; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
2306; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_A]]
2307; CHECK-NEXT:      i32 13, label %[[ENTRY_SPLIT_B:.*]]
2308; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_A]]
2309; CHECK-NEXT:      i32 42, label %[[ENTRY_SPLIT_C:.*]]
2310; CHECK-NEXT:    ]
2311
2312loop_begin:
2313  %var_val = load i32, i32* %var
2314  switch i32 %cond2, label %loop_exit [
2315    i32 0, label %loop_a
2316    i32 1, label %loop_a
2317    i32 13, label %loop_b
2318    i32 2, label %loop_a
2319    i32 42, label %loop_c
2320  ]
2321
2322loop_a:
2323  call i32 @a()
2324  br label %loop_latch
2325; Unswitched 'a' loop.
2326;
2327; CHECK:       [[ENTRY_SPLIT_A]]:
2328; CHECK-NEXT:    br label %[[LOOP_BEGIN_A:.*]]
2329;
2330; CHECK:       [[LOOP_BEGIN_A]]:
2331; CHECK-NEXT:    %{{.*}} = load i32, i32* %var
2332; CHECK-NEXT:    br label %[[LOOP_A:.*]]
2333;
2334; CHECK:       [[LOOP_A]]:
2335; CHECK-NEXT:    call i32 @a()
2336; CHECK-NEXT:    br label %[[LOOP_LATCH_A:.*]]
2337;
2338; CHECK:       [[LOOP_LATCH_A]]:
2339; CHECK:         br label %[[LOOP_BEGIN_A]]
2340
2341loop_b:
2342  call i32 @b()
2343  br label %loop_latch
2344; Unswitched 'b' loop.
2345;
2346; CHECK:       [[ENTRY_SPLIT_B]]:
2347; CHECK-NEXT:    br label %[[LOOP_BEGIN_B:.*]]
2348;
2349; CHECK:       [[LOOP_BEGIN_B]]:
2350; CHECK-NEXT:    %{{.*}} = load i32, i32* %var
2351; CHECK-NEXT:    br label %[[LOOP_B:.*]]
2352;
2353; CHECK:       [[LOOP_B]]:
2354; CHECK-NEXT:    call i32 @b()
2355; CHECK-NEXT:    br label %[[LOOP_LATCH_B:.*]]
2356;
2357; CHECK:       [[LOOP_LATCH_B]]:
2358; CHECK:         br label %[[LOOP_BEGIN_B]]
2359
2360loop_c:
2361  call i32 @c() noreturn nounwind
2362  br label %loop_latch
2363; Unswitched 'c' loop.
2364;
2365; CHECK:       [[ENTRY_SPLIT_C]]:
2366; CHECK-NEXT:    br label %[[LOOP_BEGIN_C:.*]]
2367;
2368; CHECK:       [[LOOP_BEGIN_C]]:
2369; CHECK-NEXT:    %{{.*}} = load i32, i32* %var
2370; CHECK-NEXT:    br label %[[LOOP_C:.*]]
2371;
2372; CHECK:       [[LOOP_C]]:
2373; CHECK-NEXT:    call i32 @c()
2374; CHECK-NEXT:    br label %[[LOOP_LATCH_C:.*]]
2375;
2376; CHECK:       [[LOOP_LATCH_C]]:
2377; CHECK:         br label %[[LOOP_BEGIN_C]]
2378
2379loop_latch:
2380  br label %loop_begin
2381
2382loop_exit:
2383  %lcssa = phi i32 [ %var_val, %loop_begin ]
2384  ret i32 %lcssa
2385; Unswitched exit edge (no longer a loop).
2386;
2387; CHECK:       [[ENTRY_SPLIT_EXIT]]:
2388; CHECK-NEXT:    br label %loop_begin
2389;
2390; CHECK:       loop_begin:
2391; CHECK-NEXT:    %[[V:.*]] = load i32, i32* %var
2392; CHECK-NEXT:    br label %loop_exit
2393;
2394; CHECK:       loop_exit:
2395; CHECK-NEXT:    %[[LCSSA:.*]] = phi i32 [ %[[V]], %loop_begin ]
2396; CHECK-NEXT:    ret i32 %[[LCSSA]]
2397}
2398
2399; Negative test: we do not switch when the loop contains unstructured control
2400; flows as it would significantly complicate the process as novel loops might
2401; be formed, etc.
2402define void @test_no_unswitch_unstructured_cfg(i1* %ptr, i1 %cond) {
2403; CHECK-LABEL: @test_no_unswitch_unstructured_cfg(
2404entry:
2405  br label %loop_begin
2406
2407loop_begin:
2408  br i1 %cond, label %loop_left, label %loop_right
2409
2410loop_left:
2411  %v1 = load i1, i1* %ptr
2412  br i1 %v1, label %loop_right, label %loop_merge
2413
2414loop_right:
2415  %v2 = load i1, i1* %ptr
2416  br i1 %v2, label %loop_left, label %loop_merge
2417
2418loop_merge:
2419  %v3 = load i1, i1* %ptr
2420  br i1 %v3, label %loop_latch, label %loop_exit
2421
2422loop_latch:
2423  br label %loop_begin
2424
2425loop_exit:
2426  ret void
2427}
2428
2429; A test reduced out of 403.gcc with interesting nested loops that trigger
2430; multiple unswitches. A key component of this test is that there are multiple
2431; paths to reach an inner loop after unswitching, and one of them is via the
2432; predecessors of the unswitched loop header. That can allow us to find the loop
2433; through multiple different paths.
2434define void @test21(i1 %a, i1 %b) {
2435; CHECK-LABEL: @test21(
2436bb:
2437  br label %bb3
2438; CHECK-NOT:     br i1 %a
2439;
2440; CHECK:         %[[FROZEN:.+]] = freeze i1 %a
2441; CHECK-NEXT:    br i1 %[[FROZEN]], label %[[BB_SPLIT_US:.*]], label %[[BB_SPLIT:.*]]
2442;
2443; CHECK-NOT:     br i1 %a
2444; CHECK-NOT:     br i1 %b
2445;
2446; CHECK:       [[BB_SPLIT]]:
2447; CHECK:         br i1 %b
2448;
2449; CHECK-NOT:     br i1 %a
2450; CHECK-NOT:     br i1 %b
2451
2452bb3:
2453  %tmp1.0 = phi i32 [ 0, %bb ], [ %tmp1.3, %bb23 ]
2454  br label %bb7
2455
2456bb7:
2457  %tmp.0 = phi i1 [ true, %bb3 ], [ false, %bb19 ]
2458  %tmp1.1 = phi i32 [ %tmp1.0, %bb3 ], [ %tmp1.2.lcssa, %bb19 ]
2459  br i1 %tmp.0, label %bb11.preheader, label %bb23
2460
2461bb11.preheader:
2462  br i1 %a, label %bb19, label %bb14.lr.ph
2463
2464bb14.lr.ph:
2465  br label %bb14
2466
2467bb14:
2468  %tmp2.02 = phi i32 [ 0, %bb14.lr.ph ], [ 1, %bb14 ]
2469  br i1 %b, label %bb11.bb19_crit_edge, label %bb14
2470
2471bb11.bb19_crit_edge:
2472  %split = phi i32 [ %tmp2.02, %bb14 ]
2473  br label %bb19
2474
2475bb19:
2476  %tmp1.2.lcssa = phi i32 [ %split, %bb11.bb19_crit_edge ], [ %tmp1.1, %bb11.preheader ]
2477  %tmp21 = icmp eq i32 %tmp1.2.lcssa, 0
2478  br i1 %tmp21, label %bb23, label %bb7
2479
2480bb23:
2481  %tmp1.3 = phi i32 [ %tmp1.2.lcssa, %bb19 ], [ %tmp1.1, %bb7 ]
2482  br label %bb3
2483}
2484
2485; A test reduced out of 400.perlbench that when unswitching the `%stop`
2486; condition clones a loop nest outside of a containing loop. This excercises a
2487; different cloning path from our other test cases and in turn verifying the
2488; resulting structure can catch any failures to correctly clone these nested
2489; loops.
2490declare void @f()
2491declare void @g()
2492declare i32 @h(i32 %arg)
2493define void @test22(i32 %arg) {
2494; CHECK-LABEL: define void @test22(
2495entry:
2496  br label %loop1.header
2497
2498loop1.header:
2499  %stop = phi i1 [ true, %loop1.latch ], [ false, %entry ]
2500  %i = phi i32 [ %i.lcssa, %loop1.latch ], [ %arg, %entry ]
2501; CHECK:         %[[I:.*]] = phi i32 [ %{{.*}}, %loop1.latch ], [ %arg, %entry ]
2502  br i1 %stop, label %loop1.exit, label %loop1.body.loop2.ph
2503; CHECK:         br i1 %stop, label %loop1.exit, label %loop1.body.loop2.ph
2504
2505loop1.body.loop2.ph:
2506  br label %loop2.header
2507; Just check that the we unswitched the key condition and that leads to the
2508; inner loop header.
2509;
2510; CHECK:       loop1.body.loop2.ph:
2511; CHECK-NEXT:    br i1 %stop, label %[[SPLIT_US:.*]], label %[[SPLIT:.*]]
2512;
2513; CHECK:       [[SPLIT_US]]:
2514; CHECK-NEXT:    br label %[[LOOP2_HEADER_US:.*]]
2515;
2516; CHECK:       [[LOOP2_HEADER_US]]:
2517; CHECK-NEXT:    %{{.*}} = phi i32 [ %[[I]], %[[SPLIT_US]] ]
2518;
2519; CHECK:       [[SPLIT]]:
2520; CHECK-NEXT:    br label %[[LOOP2_HEADER:.*]]
2521;
2522; CHECK:       [[LOOP2_HEADER]]:
2523; CHECK-NEXT:    %{{.*}} = phi i32 [ %[[I]], %[[SPLIT]] ]
2524
2525loop2.header:
2526  %i.inner = phi i32 [ %i, %loop1.body.loop2.ph ], [ %i.next, %loop2.latch ]
2527  br label %loop3.header
2528
2529loop3.header:
2530  %sw = call i32 @h(i32 %i.inner)
2531  switch i32 %sw, label %loop3.exit [
2532    i32 32, label %loop3.header
2533    i32 59, label %loop2.latch
2534    i32 36, label %loop1.latch
2535  ]
2536
2537loop2.latch:
2538  %i.next = add i32 %i.inner, 1
2539  br i1 %stop, label %loop2.exit, label %loop2.header
2540
2541loop1.latch:
2542  %i.lcssa = phi i32 [ %i.inner, %loop3.header ]
2543  br label %loop1.header
2544
2545loop3.exit:
2546  call void @f()
2547  ret void
2548
2549loop2.exit:
2550  call void @g()
2551  ret void
2552
2553loop1.exit:
2554  call void @g()
2555  ret void
2556}
2557
2558; Test that when we are unswitching and need to rebuild the loop block set we
2559; correctly skip past inner loops. We want to use the inner loop to efficiently
2560; skip whole subregions of the outer loop blocks but just because the header of
2561; the outer loop is also the preheader of an inner loop shouldn't confuse this
2562; walk.
2563define void @test23(i1 %arg, i1* %ptr) {
2564; CHECK-LABEL: define void @test23(
2565entry:
2566  br label %outer.header
2567; CHECK:       entry:
2568; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %arg
2569; CHECK-NEXT:    br i1 %[[FROZEN]],
2570;
2571; Just verify that we unswitched the correct bits. We should call `@f` twice in
2572; one unswitch and `@f` and then `@g` in the other.
2573; CHECK:         call void
2574; CHECK-SAME:              @f
2575; CHECK:         call void
2576; CHECK-SAME:              @f
2577;
2578; CHECK:         call void
2579; CHECK-SAME:              @f
2580; CHECK:         call void
2581; CHECK-SAME:              @g
2582
2583outer.header:
2584  br label %inner.header
2585
2586inner.header:
2587  call void @f()
2588  br label %inner.latch
2589
2590inner.latch:
2591  %inner.cond = load i1, i1* %ptr
2592  br i1 %inner.cond, label %inner.header, label %outer.body
2593
2594outer.body:
2595  br i1 %arg, label %outer.body.left, label %outer.body.right
2596
2597outer.body.left:
2598  call void @f()
2599  br label %outer.latch
2600
2601outer.body.right:
2602  call void @g()
2603  br label %outer.latch
2604
2605outer.latch:
2606  %outer.cond = load i1, i1* %ptr
2607  br i1 %outer.cond, label %outer.header, label %exit
2608
2609exit:
2610  ret void
2611}
2612
2613; Non-trivial loop unswitching where there are two invariant conditions, but the
2614; second one is only in the cloned copy of the loop after unswitching.
2615define i32 @test24(i1* %ptr, i1 %cond1, i1 %cond2) {
2616; CHECK-LABEL: @test24(
2617entry:
2618  br label %loop_begin
2619; CHECK-NEXT:  entry:
2620; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
2621
2622loop_begin:
2623  br i1 %cond1, label %loop_a, label %loop_b
2624
2625loop_a:
2626  br i1 %cond2, label %loop_a_a, label %loop_a_c
2627; The second unswitched condition.
2628;
2629; CHECK:       entry.split.us:
2630; CHECK-NEXT:    br i1 %cond2, label %entry.split.us.split.us, label %entry.split.us.split
2631
2632loop_a_a:
2633  call i32 @a()
2634  br label %latch
2635; The 'loop_a_a' unswitched loop.
2636;
2637; CHECK:       entry.split.us.split.us:
2638; CHECK-NEXT:    br label %loop_begin.us.us
2639;
2640; CHECK:       loop_begin.us.us:
2641; CHECK-NEXT:    br label %loop_a.us.us
2642;
2643; CHECK:       loop_a.us.us:
2644; CHECK-NEXT:    br label %loop_a_a.us.us
2645;
2646; CHECK:       loop_a_a.us.us:
2647; CHECK-NEXT:    call i32 @a()
2648; CHECK-NEXT:    br label %latch.us.us
2649;
2650; CHECK:       latch.us.us:
2651; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2652; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us.us, label %loop_exit.split.us.split.us
2653;
2654; CHECK:       loop_exit.split.us.split.us:
2655; CHECK-NEXT:    br label %loop_exit.split
2656
2657loop_a_c:
2658  call i32 @c()
2659  br label %latch
2660; The 'loop_a_c' unswitched loop.
2661;
2662; CHECK:       entry.split.us.split:
2663; CHECK-NEXT:    br label %loop_begin.us
2664;
2665; CHECK:       loop_begin.us:
2666; CHECK-NEXT:    br label %loop_a.us
2667;
2668; CHECK:       loop_a.us:
2669; CHECK-NEXT:    br label %loop_a_c.us
2670;
2671; CHECK:       loop_a_c.us:
2672; CHECK-NEXT:    call i32 @c()
2673; CHECK-NEXT:    br label %latch
2674;
2675; CHECK:       latch.us:
2676; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2677; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us.split
2678;
2679; CHECK:       loop_exit.split.us.split:
2680; CHECK-NEXT:    br label %loop_exit.split
2681
2682loop_b:
2683  call i32 @b()
2684  br label %latch
2685; The 'loop_b' unswitched loop.
2686;
2687; CHECK:       entry.split:
2688; CHECK-NEXT:    br label %loop_begin
2689;
2690; CHECK:       loop_begin:
2691; CHECK-NEXT:    br label %loop_b
2692;
2693; CHECK:       loop_b:
2694; CHECK-NEXT:    call i32 @b()
2695; CHECK-NEXT:    br label %latch
2696;
2697; CHECK:       latch:
2698; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2699; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
2700;
2701; CHECK:       loop_exit.split:
2702; CHECK-NEXT:    br label %loop_exit
2703
2704latch:
2705  %v = load i1, i1* %ptr
2706  br i1 %v, label %loop_begin, label %loop_exit
2707
2708loop_exit:
2709  ret i32 0
2710; CHECK:       loop_exit:
2711; CHECK-NEXT:    ret
2712}
2713
2714; Non-trivial partial loop unswitching of an invariant input to an 'or'.
2715define i32 @test25(i1* %ptr, i1 %cond) {
2716; CHECK-LABEL: @test25(
2717entry:
2718  br label %loop_begin
2719; CHECK-NEXT:  entry:
2720; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
2721
2722loop_begin:
2723  %v1 = load i1, i1* %ptr
2724  %cond_or = or i1 %v1, %cond
2725  br i1 %cond_or, label %loop_a, label %loop_b
2726
2727loop_a:
2728  call i32 @a()
2729  br label %latch
2730; The 'loop_a' unswitched loop.
2731;
2732; CHECK:       entry.split.us:
2733; CHECK-NEXT:    br label %loop_begin.us
2734;
2735; CHECK:       loop_begin.us:
2736; CHECK-NEXT:    br label %loop_a.us
2737;
2738; CHECK:       loop_a.us:
2739; CHECK-NEXT:    call i32 @a()
2740; CHECK-NEXT:    br label %latch.us
2741;
2742; CHECK:       latch.us:
2743; CHECK-NEXT:    %[[V2_US:.*]] = load i1, i1* %ptr
2744; CHECK-NEXT:    br i1 %[[V2_US]], label %loop_begin.us, label %loop_exit.split.us
2745;
2746; CHECK:       loop_exit.split.us:
2747; CHECK-NEXT:    br label %loop_exit
2748
2749loop_b:
2750  call i32 @b()
2751  br label %latch
2752; The original loop.
2753;
2754; CHECK:       entry.split:
2755; CHECK-NEXT:    br label %loop_begin
2756;
2757; CHECK:       loop_begin:
2758; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr
2759; CHECK-NEXT:    %[[OR:.*]] = or i1 %[[V1]], false
2760; CHECK-NEXT:    br i1 %[[OR]], label %loop_a, label %loop_b
2761;
2762; CHECK:       loop_a:
2763; CHECK-NEXT:    call i32 @a()
2764; CHECK-NEXT:    br label %latch
2765;
2766; CHECK:       loop_b:
2767; CHECK-NEXT:    call i32 @b()
2768; CHECK-NEXT:    br label %latch
2769
2770latch:
2771  %v2 = load i1, i1* %ptr
2772  br i1 %v2, label %loop_begin, label %loop_exit
2773; CHECK:       latch:
2774; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr
2775; CHECK-NEXT:    br i1 %[[V2]], label %loop_begin, label %loop_exit.split
2776
2777loop_exit:
2778  ret i32 0
2779; CHECK:       loop_exit.split:
2780; CHECK-NEXT:    br label %loop_exit
2781;
2782; CHECK:       loop_exit:
2783; CHECK-NEXT:    ret
2784}
2785
2786; Non-trivial partial loop unswitching of multiple invariant inputs to an `and`
2787; chain.
2788define i32 @test26(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2, i1 %cond3) {
2789; CHECK-LABEL: @test26(
2790entry:
2791  br label %loop_begin
2792; CHECK-NEXT:  entry:
2793; CHECK-NEXT:    %[[INV_AND:.*]] = and i1 %cond3, %cond1
2794; CHECK-NEXT:    br i1 %[[INV_AND]], label %entry.split, label %entry.split.us
2795
2796loop_begin:
2797  %v1 = load i1, i1* %ptr1
2798  %v2 = load i1, i1* %ptr2
2799  %cond_and1 = and i1 %v1, %cond1
2800  %cond_or1 = or i1 %v2, %cond2
2801  %cond_and2 = and i1 %cond_and1, %cond_or1
2802  %cond_and3 = and i1 %cond_and2, %cond3
2803  br i1 %cond_and3, label %loop_a, label %loop_b
2804; The 'loop_b' unswitched loop.
2805;
2806; CHECK:       entry.split.us:
2807; CHECK-NEXT:    br label %loop_begin.us
2808;
2809; CHECK:       loop_begin.us:
2810; CHECK-NEXT:    br label %loop_b.us
2811;
2812; CHECK:       loop_b.us:
2813; CHECK-NEXT:    call i32 @b()
2814; CHECK-NEXT:    br label %latch.us
2815;
2816; CHECK:       latch.us:
2817; CHECK-NEXT:    %[[V3_US:.*]] = load i1, i1* %ptr3
2818; CHECK-NEXT:    br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us
2819;
2820; CHECK:       loop_exit.split.us:
2821; CHECK-NEXT:    br label %loop_exit
2822
2823; The original loop.
2824;
2825; CHECK:       entry.split:
2826; CHECK-NEXT:    br label %loop_begin
2827;
2828; CHECK:       loop_begin:
2829; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr1
2830; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr2
2831; CHECK-NEXT:    %[[AND1:.*]] = and i1 %[[V1]], true
2832; CHECK-NEXT:    %[[OR1:.*]] = or i1 %[[V2]], %cond2
2833; CHECK-NEXT:    %[[AND2:.*]] = and i1 %[[AND1]], %[[OR1]]
2834; CHECK-NEXT:    %[[AND3:.*]] = and i1 %[[AND2]], true
2835; CHECK-NEXT:    br i1 %[[AND3]], label %loop_a, label %loop_b
2836
2837loop_a:
2838  call i32 @a()
2839  br label %latch
2840; CHECK:       loop_a:
2841; CHECK-NEXT:    call i32 @a()
2842; CHECK-NEXT:    br label %latch
2843
2844loop_b:
2845  call i32 @b()
2846  br label %latch
2847; CHECK:       loop_b:
2848; CHECK-NEXT:    call i32 @b()
2849; CHECK-NEXT:    br label %latch
2850
2851latch:
2852  %v3 = load i1, i1* %ptr3
2853  br i1 %v3, label %loop_begin, label %loop_exit
2854; CHECK:       latch:
2855; CHECK-NEXT:    %[[V3:.*]] = load i1, i1* %ptr3
2856; CHECK-NEXT:    br i1 %[[V3]], label %loop_begin, label %loop_exit.split
2857
2858loop_exit:
2859  ret i32 0
2860; CHECK:       loop_exit.split:
2861; CHECK-NEXT:    br label %loop_exit
2862;
2863; CHECK:       loop_exit:
2864; CHECK-NEXT:    ret
2865}
2866
2867; Non-trivial partial loop unswitching of multiple invariant inputs to an `or`
2868; chain. Basically an inverted version of corresponding `and` test (test26).
2869define i32 @test27(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2, i1 %cond3) {
2870; CHECK-LABEL: @test27(
2871entry:
2872  br label %loop_begin
2873; CHECK-NEXT:  entry:
2874; CHECK-NEXT:    %[[INV_OR:.*]] = or i1 %cond3, %cond1
2875; CHECK-NEXT:    br i1 %[[INV_OR]], label %entry.split.us, label %entry.split
2876
2877loop_begin:
2878  %v1 = load i1, i1* %ptr1
2879  %v2 = load i1, i1* %ptr2
2880  %cond_or1 = or i1 %v1, %cond1
2881  %cond_and1 = and i1 %v2, %cond2
2882  %cond_or2 = or i1 %cond_or1, %cond_and1
2883  %cond_or3 = or i1 %cond_or2, %cond3
2884  br i1 %cond_or3, label %loop_b, label %loop_a
2885; The 'loop_b' unswitched loop.
2886;
2887; CHECK:       entry.split.us:
2888; CHECK-NEXT:    br label %loop_begin.us
2889;
2890; CHECK:       loop_begin.us:
2891; CHECK-NEXT:    br label %loop_b.us
2892;
2893; CHECK:       loop_b.us:
2894; CHECK-NEXT:    call i32 @b()
2895; CHECK-NEXT:    br label %latch.us
2896;
2897; CHECK:       latch.us:
2898; CHECK-NEXT:    %[[V3_US:.*]] = load i1, i1* %ptr3
2899; CHECK-NEXT:    br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us
2900;
2901; CHECK:       loop_exit.split.us:
2902; CHECK-NEXT:    br label %loop_exit
2903
2904; The original loop.
2905;
2906; CHECK:       entry.split:
2907; CHECK-NEXT:    br label %loop_begin
2908;
2909; CHECK:       loop_begin:
2910; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr1
2911; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr2
2912; CHECK-NEXT:    %[[OR1:.*]] = or i1 %[[V1]], false
2913; CHECK-NEXT:    %[[AND1:.*]] = and i1 %[[V2]], %cond2
2914; CHECK-NEXT:    %[[OR2:.*]] = or i1 %[[OR1]], %[[AND1]]
2915; CHECK-NEXT:    %[[OR3:.*]] = or i1 %[[OR2]], false
2916; CHECK-NEXT:    br i1 %[[OR3]], label %loop_b, label %loop_a
2917
2918loop_a:
2919  call i32 @a()
2920  br label %latch
2921; CHECK:       loop_a:
2922; CHECK-NEXT:    call i32 @a()
2923; CHECK-NEXT:    br label %latch
2924
2925loop_b:
2926  call i32 @b()
2927  br label %latch
2928; CHECK:       loop_b:
2929; CHECK-NEXT:    call i32 @b()
2930; CHECK-NEXT:    br label %latch
2931
2932latch:
2933  %v3 = load i1, i1* %ptr3
2934  br i1 %v3, label %loop_begin, label %loop_exit
2935; CHECK:       latch:
2936; CHECK-NEXT:    %[[V3:.*]] = load i1, i1* %ptr3
2937; CHECK-NEXT:    br i1 %[[V3]], label %loop_begin, label %loop_exit.split
2938
2939loop_exit:
2940  ret i32 0
2941; CHECK:       loop_exit.split:
2942; CHECK-NEXT:    br label %loop_exit
2943;
2944; CHECK:       loop_exit:
2945; CHECK-NEXT:    ret
2946}
2947
2948; Non-trivial unswitching of a switch.
2949define i32 @test28(i1* %ptr, i32 %cond) {
2950; CHECK-LABEL: @test28(
2951entry:
2952  br label %loop_begin
2953; CHECK-NEXT:  entry:
2954; CHECK-NEXT:    switch i32 %cond, label %[[ENTRY_SPLIT_LATCH:.*]] [
2955; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
2956; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_B:.*]]
2957; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_C:.*]]
2958; CHECK-NEXT:    ]
2959
2960loop_begin:
2961  switch i32 %cond, label %latch [
2962    i32 0, label %loop_a
2963    i32 1, label %loop_b
2964    i32 2, label %loop_c
2965  ]
2966
2967loop_a:
2968  call i32 @a()
2969  br label %latch
2970; Unswitched 'a' loop.
2971;
2972; CHECK:       [[ENTRY_SPLIT_A]]:
2973; CHECK-NEXT:    br label %[[LOOP_BEGIN_A:.*]]
2974;
2975; CHECK:       [[LOOP_BEGIN_A]]:
2976; CHECK-NEXT:    br label %[[LOOP_A:.*]]
2977;
2978; CHECK:       [[LOOP_A]]:
2979; CHECK-NEXT:    call i32 @a()
2980; CHECK-NEXT:    br label %[[LOOP_LATCH_A:.*]]
2981;
2982; CHECK:       [[LOOP_LATCH_A]]:
2983; CHECK-NEXT:    %[[V_A:.*]] = load i1, i1* %ptr
2984; CHECK:         br i1 %[[V_A]], label %[[LOOP_BEGIN_A]], label %[[LOOP_EXIT_A:.*]]
2985;
2986; CHECK:       [[LOOP_EXIT_A]]:
2987; CHECK-NEXT:    br label %loop_exit
2988
2989loop_b:
2990  call i32 @b()
2991  br label %latch
2992; Unswitched 'b' loop.
2993;
2994; CHECK:       [[ENTRY_SPLIT_B]]:
2995; CHECK-NEXT:    br label %[[LOOP_BEGIN_B:.*]]
2996;
2997; CHECK:       [[LOOP_BEGIN_B]]:
2998; CHECK-NEXT:    br label %[[LOOP_B:.*]]
2999;
3000; CHECK:       [[LOOP_B]]:
3001; CHECK-NEXT:    call i32 @b()
3002; CHECK-NEXT:    br label %[[LOOP_LATCH_B:.*]]
3003;
3004; CHECK:       [[LOOP_LATCH_B]]:
3005; CHECK-NEXT:    %[[V_B:.*]] = load i1, i1* %ptr
3006; CHECK:         br i1 %[[V_B]], label %[[LOOP_BEGIN_B]], label %[[LOOP_EXIT_B:.*]]
3007;
3008; CHECK:       [[LOOP_EXIT_B]]:
3009; CHECK-NEXT:    br label %loop_exit
3010
3011loop_c:
3012  call i32 @c()
3013  br label %latch
3014; Unswitched 'c' loop.
3015;
3016; CHECK:       [[ENTRY_SPLIT_C]]:
3017; CHECK-NEXT:    br label %[[LOOP_BEGIN_C:.*]]
3018;
3019; CHECK:       [[LOOP_BEGIN_C]]:
3020; CHECK-NEXT:    br label %[[LOOP_C:.*]]
3021;
3022; CHECK:       [[LOOP_C]]:
3023; CHECK-NEXT:    call i32 @c()
3024; CHECK-NEXT:    br label %[[LOOP_LATCH_C:.*]]
3025;
3026; CHECK:       [[LOOP_LATCH_C]]:
3027; CHECK-NEXT:    %[[V_C:.*]] = load i1, i1* %ptr
3028; CHECK:         br i1 %[[V_C]], label %[[LOOP_BEGIN_C]], label %[[LOOP_EXIT_C:.*]]
3029;
3030; CHECK:       [[LOOP_EXIT_C]]:
3031; CHECK-NEXT:    br label %loop_exit
3032
3033latch:
3034  %v = load i1, i1* %ptr
3035  br i1 %v, label %loop_begin, label %loop_exit
3036; Unswitched the 'latch' only loop.
3037;
3038; CHECK:       [[ENTRY_SPLIT_LATCH]]:
3039; CHECK-NEXT:    br label %[[LOOP_BEGIN_LATCH:.*]]
3040;
3041; CHECK:       [[LOOP_BEGIN_LATCH]]:
3042; CHECK-NEXT:    br label %[[LOOP_LATCH_LATCH:.*]]
3043;
3044; CHECK:       [[LOOP_LATCH_LATCH]]:
3045; CHECK-NEXT:    %[[V_LATCH:.*]] = load i1, i1* %ptr
3046; CHECK:         br i1 %[[V_LATCH]], label %[[LOOP_BEGIN_LATCH]], label %[[LOOP_EXIT_LATCH:.*]]
3047;
3048; CHECK:       [[LOOP_EXIT_LATCH]]:
3049; CHECK-NEXT:    br label %loop_exit
3050
3051loop_exit:
3052  ret i32 0
3053; CHECK:       loop_exit:
3054; CHECK-NEXT:    ret i32 0
3055}
3056
3057; A test case designed to exercise unusual properties of switches: they
3058; can introduce multiple edges to successors. These need lots of special case
3059; handling as they get collapsed in many cases (domtree, the unswitch itself)
3060; but not in all cases (the PHI node operands).
3061define i32 @test29(i32 %arg) {
3062; CHECK-LABEL: @test29(
3063entry:
3064  br label %header
3065; CHECK-NEXT:  entry:
3066; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i32 %arg
3067; CHECK-NEXT:    switch i32 %[[FROZEN]], label %[[ENTRY_SPLIT_C:.*]] [
3068; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
3069; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_A]]
3070; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_B:.*]]
3071; CHECK-NEXT:      i32 3, label %[[ENTRY_SPLIT_C]]
3072; CHECK-NEXT:    ]
3073
3074header:
3075  %tmp = call i32 @d()
3076  %cmp1 = icmp eq i32 %tmp, 0
3077  ; We set up a chain through all the successors of the switch that doesn't
3078  ; involve the switch so that we can have interesting PHI nodes in them.
3079  br i1 %cmp1, label %body.a, label %dispatch
3080
3081dispatch:
3082  ; Switch with multiple successors. We arrange the last successor to be the
3083  ; default to make the test case easier to read. This has a duplicate edge
3084  ; both to the default destination (which is completely superfluous but
3085  ; technically valid IR) and to a regular successor.
3086  switch i32 %arg, label %body.c [
3087    i32 0, label %body.a
3088    i32 1, label %body.a
3089    i32 2, label %body.b
3090    i32 3, label %body.c
3091  ]
3092
3093body.a:
3094  %tmp.a.phi = phi i32 [ 0, %header ], [ %tmp, %dispatch ], [ %tmp, %dispatch ]
3095  %tmp.a = call i32 @a()
3096  %tmp.a.sum = add i32 %tmp.a.phi, %tmp.a
3097  br label %body.b
3098; Unswitched 'a' loop.
3099;
3100; CHECK:       [[ENTRY_SPLIT_A]]:
3101; CHECK-NEXT:    br label %[[HEADER_A:.*]]
3102;
3103; CHECK:       [[HEADER_A]]:
3104; CHECK-NEXT:    %[[TMP_A:.*]] = call i32 @d()
3105; CHECK-NEXT:    %[[CMP1_A:.*]] = icmp eq i32 %[[TMP_A]], 0
3106; CHECK-NEXT:    br i1 %[[CMP1_A]], label %[[BODY_A_A:.*]], label %[[DISPATCH_A:.*]]
3107;
3108; CHECK:       [[DISPATCH_A]]:
3109; CHECK-NEXT:    br label %[[BODY_A_A]]
3110;
3111; CHECK:       [[BODY_A_A]]:
3112; CHECK-NEXT:    %[[TMP_A_PHI_A:.*]] = phi i32 [ 0, %[[HEADER_A]] ], [ %[[TMP_A]], %[[DISPATCH_A]] ]
3113; CHECK-NEXT:    %[[TMP_A_A:.*]] = call i32 @a()
3114; CHECK-NEXT:    %[[TMP_A_SUM_A:.*]] = add i32 %[[TMP_A_PHI_A]], %[[TMP_A_A]]
3115; CHECK-NEXT:    br label %[[BODY_B_A:.*]]
3116;
3117; CHECK:       [[BODY_B_A]]:
3118; CHECK-NEXT:    %[[TMP_B_PHI_A:.*]] = phi i32 [ %[[TMP_A_SUM_A]], %[[BODY_A_A]] ]
3119; CHECK-NEXT:    %[[TMP_B_A:.*]] = call i32 @b()
3120; CHECK-NEXT:    %[[TMP_B_SUM_A:.*]] = add i32 %[[TMP_B_PHI_A]], %[[TMP_B_A]]
3121; CHECK-NEXT:    br label %[[BODY_C_A:.*]]
3122;
3123; CHECK:       [[BODY_C_A]]:
3124; CHECK-NEXT:    %[[TMP_C_PHI_A:.*]] = phi i32 [ %[[TMP_B_SUM_A]], %[[BODY_B_A]] ]
3125; CHECK-NEXT:    %[[TMP_C_A:.*]] = call i32 @c()
3126; CHECK-NEXT:    %[[TMP_C_SUM_A:.*]] = add i32 %[[TMP_C_PHI_A]], %[[TMP_C_A]]
3127; CHECK-NEXT:    br label %[[LATCH_A:.*]]
3128;
3129; CHECK:       [[LATCH_A]]:
3130; CHECK-NEXT:    %[[CMP2_A:.*]] = icmp slt i32 %[[TMP_C_SUM_A]], 42
3131; CHECK:         br i1 %[[CMP2_A]], label %[[HEADER_A]], label %[[LOOP_EXIT_A:.*]]
3132;
3133; CHECK:       [[LOOP_EXIT_A]]:
3134; CHECK-NEXT:    %[[LCSSA_A:.*]] = phi i32 [ %[[TMP_C_SUM_A]], %[[LATCH_A]] ]
3135; CHECK-NEXT:    br label %exit
3136
3137body.b:
3138  %tmp.b.phi = phi i32 [ %tmp, %dispatch ], [ %tmp.a.sum, %body.a ]
3139  %tmp.b = call i32 @b()
3140  %tmp.b.sum = add i32 %tmp.b.phi, %tmp.b
3141  br label %body.c
3142; Unswitched 'b' loop.
3143;
3144; CHECK:       [[ENTRY_SPLIT_B]]:
3145; CHECK-NEXT:    br label %[[HEADER_B:.*]]
3146;
3147; CHECK:       [[HEADER_B]]:
3148; CHECK-NEXT:    %[[TMP_B:.*]] = call i32 @d()
3149; CHECK-NEXT:    %[[CMP1_B:.*]] = icmp eq i32 %[[TMP_B]], 0
3150; CHECK-NEXT:    br i1 %[[CMP1_B]], label %[[BODY_A_B:.*]], label %[[DISPATCH_B:.*]]
3151;
3152; CHECK:       [[DISPATCH_B]]:
3153; CHECK-NEXT:    br label %[[BODY_B_B:.*]]
3154;
3155; CHECK:       [[BODY_A_B]]:
3156; CHECK-NEXT:    %[[TMP_A_PHI_B:.*]] = phi i32 [ 0, %[[HEADER_B]] ]
3157; CHECK-NEXT:    %[[TMP_A_B:.*]] = call i32 @a()
3158; CHECK-NEXT:    %[[TMP_A_SUM_B:.*]] = add i32 %[[TMP_A_PHI_B]], %[[TMP_A_B]]
3159; CHECK-NEXT:    br label %[[BODY_B_B:.*]]
3160;
3161; CHECK:       [[BODY_B_B]]:
3162; CHECK-NEXT:    %[[TMP_B_PHI_B:.*]] = phi i32 [ %[[TMP_B]], %[[DISPATCH_B]] ], [ %[[TMP_A_SUM_B]], %[[BODY_A_B]] ]
3163; CHECK-NEXT:    %[[TMP_B_B:.*]] = call i32 @b()
3164; CHECK-NEXT:    %[[TMP_B_SUM_B:.*]] = add i32 %[[TMP_B_PHI_B]], %[[TMP_B_B]]
3165; CHECK-NEXT:    br label %[[BODY_C_B:.*]]
3166;
3167; CHECK:       [[BODY_C_B]]:
3168; CHECK-NEXT:    %[[TMP_C_PHI_B:.*]] = phi i32 [ %[[TMP_B_SUM_B]], %[[BODY_B_B]] ]
3169; CHECK-NEXT:    %[[TMP_C_B:.*]] = call i32 @c()
3170; CHECK-NEXT:    %[[TMP_C_SUM_B:.*]] = add i32 %[[TMP_C_PHI_B]], %[[TMP_C_B]]
3171; CHECK-NEXT:    br label %[[LATCH_B:.*]]
3172;
3173; CHECK:       [[LATCH_B]]:
3174; CHECK-NEXT:    %[[CMP2_B:.*]] = icmp slt i32 %[[TMP_C_SUM_B]], 42
3175; CHECK:         br i1 %[[CMP2_B]], label %[[HEADER_B]], label %[[LOOP_EXIT_B:.*]]
3176;
3177; CHECK:       [[LOOP_EXIT_B]]:
3178; CHECK-NEXT:    %[[LCSSA_B:.*]] = phi i32 [ %[[TMP_C_SUM_B]], %[[LATCH_B]] ]
3179; CHECK-NEXT:    br label %[[EXIT_SPLIT:.*]]
3180
3181body.c:
3182  %tmp.c.phi = phi i32 [ %tmp, %dispatch ], [ %tmp, %dispatch ], [ %tmp.b.sum, %body.b ]
3183  %tmp.c = call i32 @c()
3184  %tmp.c.sum = add i32 %tmp.c.phi, %tmp.c
3185  br label %latch
3186; Unswitched 'c' loop.
3187;
3188; CHECK:       [[ENTRY_SPLIT_C]]:
3189; CHECK-NEXT:    br label %[[HEADER_C:.*]]
3190;
3191; CHECK:       [[HEADER_C]]:
3192; CHECK-NEXT:    %[[TMP_C:.*]] = call i32 @d()
3193; CHECK-NEXT:    %[[CMP1_C:.*]] = icmp eq i32 %[[TMP_C]], 0
3194; CHECK-NEXT:    br i1 %[[CMP1_C]], label %[[BODY_A_C:.*]], label %[[DISPATCH_C:.*]]
3195;
3196; CHECK:       [[DISPATCH_C]]:
3197; CHECK-NEXT:    br label %[[BODY_C_C:.*]]
3198;
3199; CHECK:       [[BODY_A_C]]:
3200; CHECK-NEXT:    %[[TMP_A_PHI_C:.*]] = phi i32 [ 0, %[[HEADER_C]] ]
3201; CHECK-NEXT:    %[[TMP_A_C:.*]] = call i32 @a()
3202; CHECK-NEXT:    %[[TMP_A_SUM_C:.*]] = add i32 %[[TMP_A_PHI_C]], %[[TMP_A_C]]
3203; CHECK-NEXT:    br label %[[BODY_B_C:.*]]
3204;
3205; CHECK:       [[BODY_B_C]]:
3206; CHECK-NEXT:    %[[TMP_B_PHI_C:.*]] = phi i32 [ %[[TMP_A_SUM_C]], %[[BODY_A_C]] ]
3207; CHECK-NEXT:    %[[TMP_B_C:.*]] = call i32 @b()
3208; CHECK-NEXT:    %[[TMP_B_SUM_C:.*]] = add i32 %[[TMP_B_PHI_C]], %[[TMP_B_C]]
3209; CHECK-NEXT:    br label %[[BODY_C_C:.*]]
3210;
3211; CHECK:       [[BODY_C_C]]:
3212; CHECK-NEXT:    %[[TMP_C_PHI_C:.*]] = phi i32 [ %[[TMP_C]], %[[DISPATCH_C]] ], [ %[[TMP_B_SUM_C]], %[[BODY_B_C]] ]
3213; CHECK-NEXT:    %[[TMP_C_C:.*]] = call i32 @c()
3214; CHECK-NEXT:    %[[TMP_C_SUM_C:.*]] = add i32 %[[TMP_C_PHI_C]], %[[TMP_C_C]]
3215; CHECK-NEXT:    br label %[[LATCH_C:.*]]
3216;
3217; CHECK:       [[LATCH_C]]:
3218; CHECK-NEXT:    %[[CMP2_C:.*]] = icmp slt i32 %[[TMP_C_SUM_C]], 42
3219; CHECK:         br i1 %[[CMP2_C]], label %[[HEADER_C]], label %[[LOOP_EXIT_C:.*]]
3220;
3221; CHECK:       [[LOOP_EXIT_C]]:
3222; CHECK-NEXT:    %[[LCSSA_C:.*]] = phi i32 [ %[[TMP_C_SUM_C]], %[[LATCH_C]] ]
3223; CHECK-NEXT:    br label %[[EXIT_SPLIT]]
3224
3225latch:
3226  %cmp2 = icmp slt i32 %tmp.c.sum, 42
3227  br i1 %cmp2, label %header, label %exit
3228
3229exit:
3230  %lcssa.phi = phi i32 [ %tmp.c.sum, %latch ]
3231  ret i32 %lcssa.phi
3232; CHECK:       [[EXIT_SPLIT]]:
3233; CHECK-NEXT:    %[[EXIT_PHI1:.*]] = phi i32 [ %[[LCSSA_C]], %[[LOOP_EXIT_C]] ], [ %[[LCSSA_B]], %[[LOOP_EXIT_B]] ]
3234; CHECK-NEXT:    br label %exit
3235
3236; CHECK:       exit:
3237; CHECK-NEXT:    %[[EXIT_PHI2:.*]] = phi i32 [ %[[EXIT_PHI1]], %[[EXIT_SPLIT]] ], [ %[[LCSSA_A]], %[[LOOP_EXIT_A]] ]
3238; CHECK-NEXT:    ret i32 %[[EXIT_PHI2]]
3239}
3240
3241; Similar to @test29 but designed to have one of the duplicate edges be
3242; a loop exit edge as those can in some cases be special. Among other things,
3243; this includes an LCSSA phi with multiple entries despite being a dedicated
3244; exit block.
3245define i32 @test30(i32 %arg) {
3246; CHECK-LABEL: define i32 @test30(
3247entry:
3248  br label %header
3249; CHECK-NEXT:  entry:
3250; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i32 %arg
3251; CHECK-NEXT:    switch i32 %[[FROZEN]], label %[[ENTRY_SPLIT_EXIT:.*]] [
3252; CHECK-NEXT:      i32 -1, label %[[ENTRY_SPLIT_EXIT]]
3253; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
3254; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_B:.*]]
3255; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_B]]
3256; CHECK-NEXT:    ]
3257
3258header:
3259  %tmp = call i32 @d()
3260  %cmp1 = icmp eq i32 %tmp, 0
3261  br i1 %cmp1, label %body.a, label %dispatch
3262
3263dispatch:
3264  switch i32 %arg, label %loop.exit1 [
3265    i32 -1, label %loop.exit1
3266    i32 0, label %body.a
3267    i32 1, label %body.b
3268    i32 2, label %body.b
3269  ]
3270
3271body.a:
3272  %tmp.a.phi = phi i32 [ 0, %header ], [ %tmp, %dispatch ]
3273  %tmp.a = call i32 @a()
3274  %tmp.a.sum = add i32 %tmp.a.phi, %tmp.a
3275  br label %body.b
3276; Unswitched 'a' loop.
3277;
3278; CHECK:       [[ENTRY_SPLIT_A]]:
3279; CHECK-NEXT:    br label %[[HEADER_A:.*]]
3280;
3281; CHECK:       [[HEADER_A]]:
3282; CHECK-NEXT:    %[[TMP_A:.*]] = call i32 @d()
3283; CHECK-NEXT:    %[[CMP1_A:.*]] = icmp eq i32 %[[TMP_A]], 0
3284; CHECK-NEXT:    br i1 %[[CMP1_A]], label %[[BODY_A_A:.*]], label %[[DISPATCH_A:.*]]
3285;
3286; CHECK:       [[DISPATCH_A]]:
3287; CHECK-NEXT:    br label %[[BODY_A_A]]
3288;
3289; CHECK:       [[BODY_A_A]]:
3290; CHECK-NEXT:    %[[TMP_A_PHI_A:.*]] = phi i32 [ 0, %[[HEADER_A]] ], [ %[[TMP_A]], %[[DISPATCH_A]] ]
3291; CHECK-NEXT:    %[[TMP_A_A:.*]] = call i32 @a()
3292; CHECK-NEXT:    %[[TMP_A_SUM_A:.*]] = add i32 %[[TMP_A_PHI_A]], %[[TMP_A_A]]
3293; CHECK-NEXT:    br label %[[BODY_B_A:.*]]
3294;
3295; CHECK:       [[BODY_B_A]]:
3296; CHECK-NEXT:    %[[TMP_B_PHI_A:.*]] = phi i32 [ %[[TMP_A_SUM_A]], %[[BODY_A_A]] ]
3297; CHECK-NEXT:    %[[TMP_B_A:.*]] = call i32 @b()
3298; CHECK-NEXT:    %[[TMP_B_SUM_A:.*]] = add i32 %[[TMP_B_PHI_A]], %[[TMP_B_A]]
3299; CHECK-NEXT:    br label %[[LATCH_A:.*]]
3300;
3301; CHECK:       [[LATCH_A]]:
3302; CHECK-NEXT:    %[[CMP2_A:.*]] = icmp slt i32 %[[TMP_B_SUM_A]], 42
3303; CHECK:         br i1 %[[CMP2_A]], label %[[HEADER_A]], label %[[LOOP_EXIT_A:.*]]
3304;
3305; CHECK:       [[LOOP_EXIT_A]]:
3306; CHECK-NEXT:    %[[LCSSA_A:.*]] = phi i32 [ %[[TMP_B_SUM_A]], %[[LATCH_A]] ]
3307; CHECK-NEXT:    br label %loop.exit2
3308
3309body.b:
3310  %tmp.b.phi = phi i32 [ %tmp, %dispatch ], [ %tmp, %dispatch ], [ %tmp.a.sum, %body.a ]
3311  %tmp.b = call i32 @b()
3312  %tmp.b.sum = add i32 %tmp.b.phi, %tmp.b
3313  br label %latch
3314; Unswitched 'b' loop.
3315;
3316; CHECK:       [[ENTRY_SPLIT_B]]:
3317; CHECK-NEXT:    br label %[[HEADER_B:.*]]
3318;
3319; CHECK:       [[HEADER_B]]:
3320; CHECK-NEXT:    %[[TMP_B:.*]] = call i32 @d()
3321; CHECK-NEXT:    %[[CMP1_B:.*]] = icmp eq i32 %[[TMP_B]], 0
3322; CHECK-NEXT:    br i1 %[[CMP1_B]], label %[[BODY_A_B:.*]], label %[[DISPATCH_B:.*]]
3323;
3324; CHECK:       [[DISPATCH_B]]:
3325; CHECK-NEXT:    br label %[[BODY_B_B]]
3326;
3327; CHECK:       [[BODY_A_B]]:
3328; CHECK-NEXT:    %[[TMP_A_PHI_B:.*]] = phi i32 [ 0, %[[HEADER_B]] ]
3329; CHECK-NEXT:    %[[TMP_A_B:.*]] = call i32 @a()
3330; CHECK-NEXT:    %[[TMP_A_SUM_B:.*]] = add i32 %[[TMP_A_PHI_B]], %[[TMP_A_B]]
3331; CHECK-NEXT:    br label %[[BODY_B_B:.*]]
3332;
3333; CHECK:       [[BODY_B_B]]:
3334; CHECK-NEXT:    %[[TMP_B_PHI_B:.*]] = phi i32 [ %[[TMP_B]], %[[DISPATCH_B]] ], [ %[[TMP_A_SUM_B]], %[[BODY_A_B]] ]
3335; CHECK-NEXT:    %[[TMP_B_B:.*]] = call i32 @b()
3336; CHECK-NEXT:    %[[TMP_B_SUM_B:.*]] = add i32 %[[TMP_B_PHI_B]], %[[TMP_B_B]]
3337; CHECK-NEXT:    br label %[[LATCH_B:.*]]
3338;
3339; CHECK:       [[LATCH_B]]:
3340; CHECK-NEXT:    %[[CMP2_B:.*]] = icmp slt i32 %[[TMP_B_SUM_B]], 42
3341; CHECK:         br i1 %[[CMP2_B]], label %[[HEADER_B]], label %[[LOOP_EXIT_B:.*]]
3342;
3343; CHECK:       [[LOOP_EXIT_B]]:
3344; CHECK-NEXT:    %[[LCSSA_B:.*]] = phi i32 [ %[[TMP_B_SUM_B]], %[[LATCH_B]] ]
3345; CHECK-NEXT:    br label %[[LOOP_EXIT2_SPLIT:.*]]
3346
3347latch:
3348  %cmp2 = icmp slt i32 %tmp.b.sum, 42
3349  br i1 %cmp2, label %header, label %loop.exit2
3350
3351loop.exit1:
3352  %l1.phi = phi i32 [ %tmp, %dispatch ], [ %tmp, %dispatch ]
3353  br label %exit
3354; Unswitched 'exit' loop.
3355;
3356; CHECK:       [[ENTRY_SPLIT_EXIT]]:
3357; CHECK-NEXT:    br label %[[HEADER_EXIT:.*]]
3358;
3359; CHECK:       [[HEADER_EXIT]]:
3360; CHECK-NEXT:    %[[TMP_EXIT:.*]] = call i32 @d()
3361; CHECK-NEXT:    %[[CMP1_EXIT:.*]] = icmp eq i32 %[[TMP_EXIT]], 0
3362; CHECK-NEXT:    br i1 %[[CMP1_EXIT]], label %[[BODY_A_EXIT:.*]], label %[[DISPATCH_EXIT:.*]]
3363;
3364; CHECK:       [[DISPATCH_EXIT]]:
3365; CHECK-NEXT:    %[[TMP_LCSSA:.*]] = phi i32 [ %[[TMP_EXIT]], %[[HEADER_EXIT]] ]
3366; CHECK-NEXT:    br label %loop.exit1
3367;
3368; CHECK:       [[BODY_A_EXIT]]:
3369; CHECK-NEXT:    %[[TMP_A_PHI_EXIT:.*]] = phi i32 [ 0, %[[HEADER_EXIT]] ]
3370; CHECK-NEXT:    %[[TMP_A_EXIT:.*]] = call i32 @a()
3371; CHECK-NEXT:    %[[TMP_A_SUM_EXIT:.*]] = add i32 %[[TMP_A_PHI_EXIT]], %[[TMP_A_EXIT]]
3372; CHECK-NEXT:    br label %[[BODY_B_EXIT:.*]]
3373;
3374; CHECK:       [[BODY_B_EXIT]]:
3375; CHECK-NEXT:    %[[TMP_B_PHI_EXIT:.*]] = phi i32 [ %[[TMP_A_SUM_EXIT]], %[[BODY_A_EXIT]] ]
3376; CHECK-NEXT:    %[[TMP_B_EXIT:.*]] = call i32 @b()
3377; CHECK-NEXT:    %[[TMP_B_SUM_EXIT:.*]] = add i32 %[[TMP_B_PHI_EXIT]], %[[TMP_B_EXIT]]
3378; CHECK-NEXT:    br label %[[LATCH_EXIT:.*]]
3379;
3380; CHECK:       [[LATCH_EXIT]]:
3381; CHECK-NEXT:    %[[CMP2_EXIT:.*]] = icmp slt i32 %[[TMP_B_SUM_EXIT]], 42
3382; CHECK:         br i1 %[[CMP2_EXIT]], label %[[HEADER_EXIT]], label %[[LOOP_EXIT_EXIT:.*]]
3383;
3384; CHECK:       loop.exit1:
3385; CHECK-NEXT:    %[[L1_PHI:.*]] = phi i32 [ %[[TMP_LCSSA]], %[[DISPATCH_EXIT]] ]
3386; CHECK-NEXT:    br label %exit
3387;
3388; CHECK:       [[LOOP_EXIT_EXIT]]:
3389; CHECK-NEXT:    %[[L2_PHI:.*]] = phi i32 [ %[[TMP_B_SUM_EXIT]], %[[LATCH_EXIT]] ]
3390; CHECK-NEXT:    br label %[[LOOP_EXIT2_SPLIT]]
3391
3392loop.exit2:
3393  %l2.phi = phi i32 [ %tmp.b.sum, %latch ]
3394  br label %exit
3395; CHECK:       [[LOOP_EXIT2_SPLIT]]:
3396; CHECK-NEXT:    %[[LOOP_EXIT_PHI1:.*]] = phi i32 [ %[[L2_PHI]], %[[LOOP_EXIT_EXIT]] ], [ %[[LCSSA_B]], %[[LOOP_EXIT_B]] ]
3397; CHECK-NEXT:    br label %loop.exit2
3398;
3399; CHECK:       loop.exit2:
3400; CHECK-NEXT:    %[[LOOP_EXIT_PHI2:.*]] = phi i32 [ %[[LOOP_EXIT_PHI1]], %[[LOOP_EXIT2_SPLIT]] ], [ %[[LCSSA_A]], %[[LOOP_EXIT_A]] ]
3401; CHECK-NEXT:    br label %exit
3402
3403exit:
3404  %l.phi = phi i32 [ %l1.phi, %loop.exit1 ], [ %l2.phi, %loop.exit2 ]
3405  ret i32 %l.phi
3406; CHECK:       exit:
3407; CHECK-NEXT:    %[[EXIT_PHI:.*]] = phi i32 [ %[[L1_PHI]], %loop.exit1 ], [ %[[LOOP_EXIT_PHI2]], %loop.exit2 ]
3408; CHECK-NEXT:    ret i32 %[[EXIT_PHI]]
3409}
3410
3411; Unswitch will not actually change the loop nest from:
3412;   A < B < C
3413define void @hoist_inner_loop0() {
3414; CHECK-LABEL: define void @hoist_inner_loop0(
3415entry:
3416  br label %a.header
3417; CHECK:       entry:
3418; CHECK-NEXT:    br label %a.header
3419
3420a.header:
3421  br label %b.header
3422; CHECK:       a.header:
3423; CHECK-NEXT:    br label %b.header
3424
3425b.header:
3426  %v1 = call i1 @cond()
3427  br label %c.header
3428; CHECK:       b.header:
3429; CHECK-NEXT:    %v1 = call i1 @cond()
3430; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %v1
3431; CHECK-NEXT:    br i1 %[[FROZEN]], label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
3432;
3433; CHECK:       [[B_HEADER_SPLIT_US]]:
3434; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3435;
3436; CHECK:       [[C_HEADER_US]]:
3437; CHECK-NEXT:    call i32 @c()
3438; CHECK-NEXT:    br label %[[B_LATCH_SPLIT_US:.*]]
3439;
3440; CHECK:       [[B_LATCH_SPLIT_US]]:
3441; CHECK-NEXT:    br label %b.latch
3442;
3443; CHECK:       [[B_HEADER_SPLIT]]:
3444; CHECK-NEXT:    br label %c.header
3445
3446c.header:
3447  call i32 @c()
3448  br i1 %v1, label %b.latch, label %c.latch
3449; CHECK:       c.header:
3450; CHECK-NEXT:    call i32 @c()
3451; CHECK-NEXT:    br label %c.latch
3452
3453c.latch:
3454  %v2 = call i1 @cond()
3455  br i1 %v2, label %c.header, label %b.latch
3456; CHECK:       c.latch:
3457; CHECK-NEXT:    %v2 = call i1 @cond()
3458; CHECK-NEXT:    br i1 %v2, label %c.header, label %[[B_LATCH_SPLIT:.*]]
3459
3460b.latch:
3461  %v3 = call i1 @cond()
3462  br i1 %v3, label %b.header, label %a.latch
3463; CHECK:       [[B_LATCH_SPLIT]]:
3464; CHECK-NEXT:    br label %b.latch
3465;
3466; CHECK:       b.latch:
3467; CHECK-NEXT:    %v3 = call i1 @cond()
3468; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
3469
3470a.latch:
3471  br label %a.header
3472; CHECK:       a.latch:
3473; CHECK-NEXT:    br label %a.header
3474
3475exit:
3476  ret void
3477; CHECK:       exit:
3478; CHECK-NEXT:    ret void
3479}
3480
3481; Unswitch will transform the loop nest from:
3482;   A < B < C
3483; into
3484;   A < (B, C)
3485define void @hoist_inner_loop1(i32* %ptr) {
3486; CHECK-LABEL: define void @hoist_inner_loop1(
3487entry:
3488  br label %a.header
3489; CHECK:       entry:
3490; CHECK-NEXT:    br label %a.header
3491
3492a.header:
3493  %x.a = load i32, i32* %ptr
3494  br label %b.header
3495; CHECK:       a.header:
3496; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3497; CHECK-NEXT:    br label %b.header
3498
3499b.header:
3500  %x.b = load i32, i32* %ptr
3501  %v1 = call i1 @cond()
3502  br label %c.header
3503; CHECK:       b.header:
3504; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3505; CHECK-NEXT:    %v1 = call i1 @cond()
3506; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %v1
3507; CHECK-NEXT:    br i1 %[[FROZEN]], label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
3508;
3509; CHECK:       [[B_HEADER_SPLIT_US]]:
3510; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3511;
3512; CHECK:       [[C_HEADER_US]]:
3513; CHECK-NEXT:    call i32 @c()
3514; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
3515;
3516; CHECK:       [[B_LATCH_US]]:
3517; CHECK-NEXT:    br label %b.latch
3518;
3519; CHECK:       [[B_HEADER_SPLIT]]:
3520; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
3521; CHECK-NEXT:    br label %c.header
3522
3523c.header:
3524  call i32 @c()
3525  br i1 %v1, label %b.latch, label %c.latch
3526; CHECK:       c.header:
3527; CHECK-NEXT:    call i32 @c()
3528; CHECK-NEXT:    br label %c.latch
3529
3530c.latch:
3531  ; Use values from other loops to check LCSSA form.
3532  store i32 %x.a, i32* %ptr
3533  store i32 %x.b, i32* %ptr
3534  %v2 = call i1 @cond()
3535  br i1 %v2, label %c.header, label %a.exit.c
3536; CHECK:       c.latch:
3537; CHECK-NEXT:    store i32 %x.a, i32* %ptr
3538; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3539; CHECK-NEXT:    %v2 = call i1 @cond()
3540; CHECK-NEXT:    br i1 %v2, label %c.header, label %a.exit.c
3541
3542b.latch:
3543  %v3 = call i1 @cond()
3544  br i1 %v3, label %b.header, label %a.exit.b
3545; CHECK:       b.latch:
3546; CHECK-NEXT:    %v3 = call i1 @cond()
3547; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.exit.b
3548
3549a.exit.c:
3550  br label %a.latch
3551; CHECK:       a.exit.c
3552; CHECK-NEXT:    br label %a.latch
3553
3554a.exit.b:
3555  br label %a.latch
3556; CHECK:       a.exit.b:
3557; CHECK-NEXT:    br label %a.latch
3558
3559a.latch:
3560  br label %a.header
3561; CHECK:       a.latch:
3562; CHECK-NEXT:    br label %a.header
3563
3564exit:
3565  ret void
3566; CHECK:       exit:
3567; CHECK-NEXT:    ret void
3568}
3569
3570; Unswitch will transform the loop nest from:
3571;   A < B < C
3572; into
3573;   (A < B), C
3574define void @hoist_inner_loop2(i32* %ptr) {
3575; CHECK-LABEL: define void @hoist_inner_loop2(
3576entry:
3577  br label %a.header
3578; CHECK:       entry:
3579; CHECK-NEXT:    br label %a.header
3580
3581a.header:
3582  %x.a = load i32, i32* %ptr
3583  br label %b.header
3584; CHECK:       a.header:
3585; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3586; CHECK-NEXT:    br label %b.header
3587
3588b.header:
3589  %x.b = load i32, i32* %ptr
3590  %v1 = call i1 @cond()
3591  br label %c.header
3592; CHECK:       b.header:
3593; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3594; CHECK-NEXT:    %v1 = call i1 @cond()
3595; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %v1
3596; CHECK-NEXT:    br i1 %[[FROZEN]], label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
3597;
3598; CHECK:       [[B_HEADER_SPLIT_US]]:
3599; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3600;
3601; CHECK:       [[C_HEADER_US]]:
3602; CHECK-NEXT:    call i32 @c()
3603; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
3604;
3605; CHECK:       [[B_LATCH_US]]:
3606; CHECK-NEXT:    br label %b.latch
3607;
3608; CHECK:       [[B_HEADER_SPLIT]]:
3609; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
3610; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
3611; CHECK-NEXT:    br label %c.header
3612
3613c.header:
3614  call i32 @c()
3615  br i1 %v1, label %b.latch, label %c.latch
3616; CHECK:       c.header:
3617; CHECK-NEXT:    call i32 @c()
3618; CHECK-NEXT:    br label %c.latch
3619
3620c.latch:
3621  ; Use values from other loops to check LCSSA form.
3622  store i32 %x.a, i32* %ptr
3623  store i32 %x.b, i32* %ptr
3624  %v2 = call i1 @cond()
3625  br i1 %v2, label %c.header, label %exit
3626; CHECK:       c.latch:
3627; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
3628; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3629; CHECK-NEXT:    %v2 = call i1 @cond()
3630; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
3631
3632b.latch:
3633  %v3 = call i1 @cond()
3634  br i1 %v3, label %b.header, label %a.latch
3635; CHECK:       b.latch:
3636; CHECK-NEXT:    %v3 = call i1 @cond()
3637; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
3638
3639a.latch:
3640  br label %a.header
3641; CHECK:       a.latch:
3642; CHECK-NEXT:    br label %a.header
3643
3644exit:
3645  ret void
3646; CHECK:       exit:
3647; CHECK-NEXT:    ret void
3648}
3649
3650; Same as @hoist_inner_loop2 but with a nested loop inside the hoisted loop.
3651; Unswitch will transform the loop nest from:
3652;   A < B < C < D
3653; into
3654;   (A < B), (C < D)
3655define void @hoist_inner_loop3(i32* %ptr) {
3656; CHECK-LABEL: define void @hoist_inner_loop3(
3657entry:
3658  br label %a.header
3659; CHECK:       entry:
3660; CHECK-NEXT:    br label %a.header
3661
3662a.header:
3663  %x.a = load i32, i32* %ptr
3664  br label %b.header
3665; CHECK:       a.header:
3666; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3667; CHECK-NEXT:    br label %b.header
3668
3669b.header:
3670  %x.b = load i32, i32* %ptr
3671  %v1 = call i1 @cond()
3672  br label %c.header
3673; CHECK:       b.header:
3674; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3675; CHECK-NEXT:    %v1 = call i1 @cond()
3676; CHECK-NEXT:    %[[FROZEN:.+]] = freeze i1 %v1
3677; CHECK-NEXT:    br i1 %[[FROZEN]], label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
3678;
3679; CHECK:       [[B_HEADER_SPLIT_US]]:
3680; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3681;
3682; CHECK:       [[C_HEADER_US]]:
3683; CHECK-NEXT:    call i32 @c()
3684; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
3685;
3686; CHECK:       [[B_LATCH_US]]:
3687; CHECK-NEXT:    br label %b.latch
3688;
3689; CHECK:       [[B_HEADER_SPLIT]]:
3690; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
3691; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
3692; CHECK-NEXT:    br label %c.header
3693
3694c.header:
3695  call i32 @c()
3696  br i1 %v1, label %b.latch, label %c.body
3697; CHECK:       c.header:
3698; CHECK-NEXT:    call i32 @c()
3699; CHECK-NEXT:    br label %c.body
3700
3701c.body:
3702  %x.c = load i32, i32* %ptr
3703  br label %d.header
3704; CHECK:       c.body:
3705; CHECK-NEXT:    %x.c = load i32, i32* %ptr
3706; CHECK-NEXT:    br label %d.header
3707
3708d.header:
3709  ; Use values from other loops to check LCSSA form.
3710  store i32 %x.a, i32* %ptr
3711  store i32 %x.b, i32* %ptr
3712  store i32 %x.c, i32* %ptr
3713  %v2 = call i1 @cond()
3714  br i1 %v2, label %d.header, label %c.latch
3715; CHECK:       d.header:
3716; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
3717; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3718; CHECK-NEXT:    store i32 %x.c, i32* %ptr
3719; CHECK-NEXT:    %v2 = call i1 @cond()
3720; CHECK-NEXT:    br i1 %v2, label %d.header, label %c.latch
3721
3722c.latch:
3723  %v3 = call i1 @cond()
3724  br i1 %v3, label %c.header, label %exit
3725; CHECK:       c.latch:
3726; CHECK-NEXT:    %v3 = call i1 @cond()
3727; CHECK-NEXT:    br i1 %v3, label %c.header, label %exit
3728
3729b.latch:
3730  %v4 = call i1 @cond()
3731  br i1 %v4, label %b.header, label %a.latch
3732; CHECK:       b.latch:
3733; CHECK-NEXT:    %v4 = call i1 @cond()
3734; CHECK-NEXT:    br i1 %v4, label %b.header, label %a.latch
3735
3736a.latch:
3737  br label %a.header
3738; CHECK:       a.latch:
3739; CHECK-NEXT:    br label %a.header
3740
3741exit:
3742  ret void
3743; CHECK:       exit:
3744; CHECK-NEXT:    ret void
3745}
3746
3747; This test is designed to exercise checking multiple remaining exits from the
3748; loop being unswitched.
3749; Unswitch will transform the loop nest from:
3750;   A < B < C < D
3751; into
3752;   A < B < (C, D)
3753define void @hoist_inner_loop4() {
3754; CHECK-LABEL: define void @hoist_inner_loop4(
3755entry:
3756  br label %a.header
3757; CHECK:       entry:
3758; CHECK-NEXT:    br label %a.header
3759
3760a.header:
3761  br label %b.header
3762; CHECK:       a.header:
3763; CHECK-NEXT:    br label %b.header
3764
3765b.header:
3766  br label %c.header
3767; CHECK:       b.header:
3768; CHECK-NEXT:    br label %c.header
3769
3770c.header:
3771  %v1 = call i1 @cond()
3772  br label %d.header
3773; CHECK:       c.header:
3774; CHECK-NEXT:    %v1 = call i1 @cond()
3775; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %v1
3776; CHECK-NEXT:    br i1 [[FROZEN]], label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]]
3777;
3778; CHECK:       [[C_HEADER_SPLIT_US]]:
3779; CHECK-NEXT:    br label %[[D_HEADER_US:.*]]
3780;
3781; CHECK:       [[D_HEADER_US]]:
3782; CHECK-NEXT:    call i32 @d()
3783; CHECK-NEXT:    br label %[[C_LATCH_US:.*]]
3784;
3785; CHECK:       [[C_LATCH_US]]:
3786; CHECK-NEXT:    br label %c.latch
3787;
3788; CHECK:       [[C_HEADER_SPLIT]]:
3789; CHECK-NEXT:    br label %d.header
3790
3791d.header:
3792  call i32 @d()
3793  br i1 %v1, label %c.latch, label %d.exiting1
3794; CHECK:       d.header:
3795; CHECK-NEXT:    call i32 @d()
3796; CHECK-NEXT:    br label %d.exiting1
3797
3798d.exiting1:
3799  %v2 = call i1 @cond()
3800  br i1 %v2, label %d.exiting2, label %a.latch
3801; CHECK:       d.exiting1:
3802; CHECK-NEXT:    %v2 = call i1 @cond()
3803; CHECK-NEXT:    br i1 %v2, label %d.exiting2, label %a.latch
3804
3805d.exiting2:
3806  %v3 = call i1 @cond()
3807  br i1 %v3, label %d.exiting3, label %loopexit.d
3808; CHECK:       d.exiting2:
3809; CHECK-NEXT:    %v3 = call i1 @cond()
3810; CHECK-NEXT:    br i1 %v3, label %d.exiting3, label %loopexit.d
3811
3812d.exiting3:
3813  %v4 = call i1 @cond()
3814  br i1 %v4, label %d.latch, label %b.latch
3815; CHECK:       d.exiting3:
3816; CHECK-NEXT:    %v4 = call i1 @cond()
3817; CHECK-NEXT:    br i1 %v4, label %d.latch, label %b.latch
3818
3819d.latch:
3820  br label %d.header
3821; CHECK:       d.latch:
3822; CHECK-NEXT:    br label %d.header
3823
3824c.latch:
3825  %v5 = call i1 @cond()
3826  br i1 %v5, label %c.header, label %loopexit.c
3827; CHECK:       c.latch:
3828; CHECK-NEXT:    %v5 = call i1 @cond()
3829; CHECK-NEXT:    br i1 %v5, label %c.header, label %loopexit.c
3830
3831b.latch:
3832  br label %b.header
3833; CHECK:       b.latch:
3834; CHECK-NEXT:    br label %b.header
3835
3836a.latch:
3837  br label %a.header
3838; CHECK:       a.latch:
3839; CHECK-NEXT:    br label %a.header
3840
3841loopexit.d:
3842  br label %exit
3843; CHECK:       loopexit.d:
3844; CHECK-NEXT:    br label %exit
3845
3846loopexit.c:
3847  br label %exit
3848; CHECK:       loopexit.c:
3849; CHECK-NEXT:    br label %exit
3850
3851exit:
3852  ret void
3853; CHECK:       exit:
3854; CHECK-NEXT:    ret void
3855}
3856
3857; Unswitch will transform the loop nest from:
3858;   A < B < C < D
3859; into
3860;   A < ((B < C), D)
3861define void @hoist_inner_loop5(i32* %ptr) {
3862; CHECK-LABEL: define void @hoist_inner_loop5(
3863entry:
3864  br label %a.header
3865; CHECK:       entry:
3866; CHECK-NEXT:    br label %a.header
3867
3868a.header:
3869  %x.a = load i32, i32* %ptr
3870  br label %b.header
3871; CHECK:       a.header:
3872; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3873; CHECK-NEXT:    br label %b.header
3874
3875b.header:
3876  %x.b = load i32, i32* %ptr
3877  br label %c.header
3878; CHECK:       b.header:
3879; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3880; CHECK-NEXT:    br label %c.header
3881
3882c.header:
3883  %x.c = load i32, i32* %ptr
3884  %v1 = call i1 @cond()
3885  br label %d.header
3886; CHECK:       c.header:
3887; CHECK-NEXT:    %x.c = load i32, i32* %ptr
3888; CHECK-NEXT:    %v1 = call i1 @cond()
3889; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %v1
3890; CHECK-NEXT:    br i1 [[FROZEN]], label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]]
3891;
3892; CHECK:       [[C_HEADER_SPLIT_US]]:
3893; CHECK-NEXT:    br label %[[D_HEADER_US:.*]]
3894;
3895; CHECK:       [[D_HEADER_US]]:
3896; CHECK-NEXT:    call i32 @d()
3897; CHECK-NEXT:    br label %[[C_LATCH_US:.*]]
3898;
3899; CHECK:       [[C_LATCH_US]]:
3900; CHECK-NEXT:    br label %c.latch
3901;
3902; CHECK:       [[C_HEADER_SPLIT]]:
3903; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %c.header ]
3904; CHECK-NEXT:    %[[X_C_LCSSA:.*]] = phi i32 [ %x.c, %c.header ]
3905; CHECK-NEXT:    br label %d.header
3906
3907d.header:
3908  call i32 @d()
3909  br i1 %v1, label %c.latch, label %d.latch
3910; CHECK:       d.header:
3911; CHECK-NEXT:    call i32 @d()
3912; CHECK-NEXT:    br label %d.latch
3913
3914d.latch:
3915  ; Use values from other loops to check LCSSA form.
3916  store i32 %x.a, i32* %ptr
3917  store i32 %x.b, i32* %ptr
3918  store i32 %x.c, i32* %ptr
3919  %v2 = call i1 @cond()
3920  br i1 %v2, label %d.header, label %a.latch
3921; CHECK:       d.latch:
3922; CHECK-NEXT:    store i32 %x.a, i32* %ptr
3923; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3924; CHECK-NEXT:    store i32 %[[X_C_LCSSA]], i32* %ptr
3925; CHECK-NEXT:    %v2 = call i1 @cond()
3926; CHECK-NEXT:    br i1 %v2, label %d.header, label %a.latch
3927
3928c.latch:
3929  %v3 = call i1 @cond()
3930  br i1 %v3, label %c.header, label %b.latch
3931; CHECK:       c.latch:
3932; CHECK-NEXT:    %v3 = call i1 @cond()
3933; CHECK-NEXT:    br i1 %v3, label %c.header, label %b.latch
3934
3935b.latch:
3936  br label %b.header
3937; CHECK:       b.latch:
3938; CHECK-NEXT:    br label %b.header
3939
3940a.latch:
3941  br label %a.header
3942; CHECK:       a.latch:
3943; CHECK-NEXT:    br label %a.header
3944
3945exit:
3946  ret void
3947; CHECK:       exit:
3948; CHECK-NEXT:    ret void
3949}
3950
3951define void @hoist_inner_loop_switch(i32* %ptr) {
3952; CHECK-LABEL: define void @hoist_inner_loop_switch(
3953entry:
3954  br label %a.header
3955; CHECK:       entry:
3956; CHECK-NEXT:    br label %a.header
3957
3958a.header:
3959  %x.a = load i32, i32* %ptr
3960  br label %b.header
3961; CHECK:       a.header:
3962; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3963; CHECK-NEXT:    br label %b.header
3964
3965b.header:
3966  %x.b = load i32, i32* %ptr
3967  %v1 = call i32 @cond.i32()
3968  br label %c.header
3969; CHECK:       b.header:
3970; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3971; CHECK-NEXT:    %v1 = call i32 @cond.i32()
3972; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i32 %v1
3973; CHECK-NEXT:    switch i32 [[FROZEN]], label %[[B_HEADER_SPLIT:.*]] [
3974; CHECK-NEXT:      i32 1, label %[[B_HEADER_SPLIT_US:.*]]
3975; CHECK-NEXT:      i32 2, label %[[B_HEADER_SPLIT_US]]
3976; CHECK-NEXT:      i32 3, label %[[B_HEADER_SPLIT_US]]
3977; CHECK-NEXT:    ]
3978;
3979; CHECK:       [[B_HEADER_SPLIT_US]]:
3980; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3981;
3982; CHECK:       [[C_HEADER_US]]:
3983; CHECK-NEXT:    call i32 @c()
3984; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
3985;
3986; CHECK:       [[B_LATCH_US]]:
3987; CHECK-NEXT:    br label %b.latch
3988;
3989; CHECK:       [[B_HEADER_SPLIT]]:
3990; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
3991; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
3992; CHECK-NEXT:    br label %c.header
3993
3994c.header:
3995  call i32 @c()
3996  switch i32 %v1, label %c.latch [
3997    i32 1, label %b.latch
3998    i32 2, label %b.latch
3999    i32 3, label %b.latch
4000  ]
4001; CHECK:       c.header:
4002; CHECK-NEXT:    call i32 @c()
4003; CHECK-NEXT:    br label %c.latch
4004
4005c.latch:
4006  ; Use values from other loops to check LCSSA form.
4007  store i32 %x.a, i32* %ptr
4008  store i32 %x.b, i32* %ptr
4009  %v2 = call i1 @cond()
4010  br i1 %v2, label %c.header, label %exit
4011; CHECK:       c.latch:
4012; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
4013; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
4014; CHECK-NEXT:    %v2 = call i1 @cond()
4015; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
4016
4017b.latch:
4018  %v3 = call i1 @cond()
4019  br i1 %v3, label %b.header, label %a.latch
4020; CHECK:       b.latch:
4021; CHECK-NEXT:    %v3 = call i1 @cond()
4022; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
4023
4024a.latch:
4025  br label %a.header
4026; CHECK:       a.latch:
4027; CHECK-NEXT:    br label %a.header
4028
4029exit:
4030  ret void
4031; CHECK:       exit:
4032; CHECK-NEXT:    ret void
4033}
4034
4035; A devilish pattern. This is a crafty, crafty test case designed to risk
4036; creating indirect cycles with trivial and non-trivial unswitching. The inner
4037; loop has a switch with a trivial exit edge that can be unswitched, but the
4038; rest of the switch cannot be unswitched because its cost is too high.
4039; However, the unswitching of the trivial edge creates a new switch in the
4040; outer loop. *This* switch isn't trivial, but has a low cost to unswitch. When
4041; we unswitch this switch from the outer loop, we will remove it completely and
4042; create a clone of the inner loop on one side. This clone will then again be
4043; viable for unswitching the inner-most loop. This lets us check that the
4044; unswitching doesn't end up cycling infinitely even when the cycle is
4045; indirect and due to revisiting a loop after cloning.
4046define void @test31(i32 %arg) {
4047; CHECK-LABEL: define void @test31(
4048entry:
4049  br label %outer.header
4050; CHECK-NEXT:  entry:
4051; CHECK-NEXT:    switch i32 %arg, label %[[ENTRY_SPLIT:.*]] [
4052; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_US:.*]]
4053; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_US]]
4054; CHECK-NEXT:    ]
4055;
4056; CHECK:       [[ENTRY_SPLIT_US]]:
4057; CHECK-NEXT:    switch i32 %arg, label %[[ENTRY_SPLIT_US_SPLIT:.*]] [
4058; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_US_SPLIT_US:.*]]
4059; CHECK-NEXT:    ]
4060
4061outer.header:
4062  br label %inner.header
4063
4064inner.header:
4065  switch i32 %arg, label %inner.loopexit1 [
4066    i32 1, label %inner.body1
4067    i32 2, label %inner.body2
4068  ]
4069
4070inner.body1:
4071  %a = call i32 @a()
4072  br label %inner.latch
4073; The (super convoluted) fully unswitched loop around `@a`.
4074;
4075; CHECK:       [[ENTRY_SPLIT_US_SPLIT_US]]:
4076; CHECK-NEXT:    br label %[[OUTER_HEADER_US_US:.*]]
4077;
4078; CHECK:       [[OUTER_HEADER_US_US]]:
4079; CHECK-NEXT:    br label %[[OUTER_HEADER_SPLIT_US_US:.*]]
4080;
4081; CHECK:       [[OUTER_LATCH_US_US:.*]]:
4082; CHECK-NEXT:    %[[OUTER_COND_US_US:.*]] = call i1 @cond()
4083; CHECK-NEXT:    br i1 %[[OUTER_COND_US_US]], label %[[OUTER_HEADER_US_US]], label %[[EXIT_SPLIT_US_SPLIT_US:.*]]
4084;
4085; CHECK:       [[OUTER_HEADER_SPLIT_US_US]]:
4086; CHECK-NEXT:    br label %[[OUTER_HEADER_SPLIT_SPLIT_US_US_US:.*]]
4087;
4088; CHECK:       [[INNER_LOOPEXIT2_US_US:.*]]:
4089; CHECK-NEXT:    br label %[[OUTER_LATCH_US_US]]
4090;
4091; CHECK:       [[OUTER_HEADER_SPLIT_SPLIT_US_US_US]]:
4092; CHECK-NEXT:    br label %[[INNER_HEADER_US_US_US:.*]]
4093;
4094; CHECK:       [[INNER_HEADER_US_US_US]]:
4095; CHECK-NEXT:    br label %[[INNER_BODY1_US_US_US:.*]]
4096;
4097; CHECK:       [[INNER_BODY1_US_US_US]]:
4098; CHECK-NEXT:    %[[A:.*]] = call i32 @a()
4099; CHECK-NEXT:    br label %[[INNER_LATCH_US_US_US:.*]]
4100;
4101; CHECK:       [[INNER_LATCH_US_US_US]]:
4102; CHECK-NEXT:    %[[PHI_A:.*]] = phi i32 [ %[[A]], %[[INNER_BODY1_US_US_US]] ]
4103; CHECK-NEXT:    call void @sink1(i32 0)
4104; CHECK-NEXT:    call void @sink1(i32 0)
4105; CHECK-NEXT:    call void @sink1(i32 0)
4106; CHECK-NEXT:    call void @sink1(i32 0)
4107; CHECK-NEXT:    call void @sink1(i32 0)
4108; CHECK-NEXT:    call void @sink1(i32 0)
4109; CHECK-NEXT:    call void @sink1(i32 0)
4110; CHECK-NEXT:    call void @sink1(i32 0)
4111; CHECK-NEXT:    call void @sink1(i32 0)
4112; CHECK-NEXT:    call void @sink1(i32 0)
4113; CHECK-NEXT:    call void @sink1(i32 %[[PHI_A]])
4114; CHECK-NEXT:    %[[INNER_COND_US_US_US:.*]] = call i1 @cond()
4115; CHECK-NEXT:    br i1 %[[INNER_COND_US_US_US]], label %[[INNER_HEADER_US_US_US]], label %[[INNER_LOOPEXIT2_SPLIT_US_US_US:.*]]
4116;
4117; CHECK:       [[INNER_LOOPEXIT2_SPLIT_US_US_US]]:
4118; CHECK-NEXT:    br label %[[INNER_LOOPEXIT2_US_US]]
4119;
4120; CHECK:       [[EXIT_SPLIT_US_SPLIT_US]]:
4121; CHECK-NEXT:    br label %[[EXIT_SPLIT_US:.*]]
4122
4123
4124inner.body2:
4125  %b = call i32 @b()
4126  br label %inner.latch
4127; The fully unswitched loop around `@b`.
4128;
4129; CHECK:       [[ENTRY_SPLIT_US_SPLIT]]:
4130; CHECK-NEXT:    br label %[[OUTER_HEADER_US:.*]]
4131;
4132; CHECK:       [[OUTER_HEADER_US]]:
4133; CHECK-NEXT:    br label %[[OUTER_HEADER_SPLIT_US:.*]]
4134;
4135; CHECK:       [[INNER_HEADER_US:.*]]:
4136; CHECK-NEXT:    br label %[[INNER_BODY2_US:.*]]
4137;
4138; CHECK:       [[INNER_BODY2_US]]:
4139; CHECK-NEXT:    %[[B:.*]] = call i32 @b()
4140; CHECK-NEXT:    br label %[[INNER_LATCH_US:.*]]
4141;
4142; CHECK:       [[INNER_LATCH_US]]:
4143; CHECK-NEXT:    call void @sink1(i32 0)
4144; CHECK-NEXT:    call void @sink1(i32 0)
4145; CHECK-NEXT:    call void @sink1(i32 0)
4146; CHECK-NEXT:    call void @sink1(i32 0)
4147; CHECK-NEXT:    call void @sink1(i32 0)
4148; CHECK-NEXT:    call void @sink1(i32 0)
4149; CHECK-NEXT:    call void @sink1(i32 0)
4150; CHECK-NEXT:    call void @sink1(i32 0)
4151; CHECK-NEXT:    call void @sink1(i32 0)
4152; CHECK-NEXT:    call void @sink1(i32 0)
4153; CHECK-NEXT:    call void @sink1(i32 %[[B]])
4154; CHECK-NEXT:    %[[INNER_COND_US:.*]] = call i1 @cond()
4155; CHECK-NEXT:    br i1 %[[INNER_COND_US]], label %[[INNER_HEADER_US]], label %[[INNER_LOOPEXIT2_SPLIT_US:.*]]
4156;
4157; CHECK:       [[INNER_LOOPEXIT2_SPLIT_US]]:
4158; CHECK-NEXT:    br label %[[INNER_LOOPEXIT2_US:.*]]
4159;
4160; CHECK:       [[OUTER_LATCH_US:.*]]:
4161; CHECK-NEXT:    %[[OUTER_COND_US:.*]] = call i1 @cond()
4162; CHECK-NEXT:    br i1 %[[OUTER_COND_US]], label %[[OUTER_HEADER_US]], label %[[EXIT_SPLIT_US_SPLIT:.*]]
4163;
4164; CHECK:       [[OUTER_HEADER_SPLIT_US]]:
4165; CHECK-NEXT:    br label %[[OUTER_HEADER_SPLIT_SPLIT_US:.*]]
4166;
4167; CHECK:       [[OUTER_HEADER_SPLIT_SPLIT_US]]:
4168; CHECK-NEXT:    br label %[[INNER_HEADER_US]]
4169;
4170; CHECK:       [[INNER_LOOPEXIT2_US]]:
4171; CHECK-NEXT:    br label %[[OUTER_LATCH_US]]
4172;
4173; CHECK:       [[EXIT_SPLIT_US]]:
4174; CHECK-NEXT:    br label %exit
4175
4176inner.latch:
4177  %phi = phi i32 [ %a, %inner.body1 ], [ %b, %inner.body2 ]
4178  ; Make 10 junk calls here to ensure we're over the "50" cost threshold of
4179  ; non-trivial unswitching for this inner switch.
4180  call void @sink1(i32 0)
4181  call void @sink1(i32 0)
4182  call void @sink1(i32 0)
4183  call void @sink1(i32 0)
4184  call void @sink1(i32 0)
4185  call void @sink1(i32 0)
4186  call void @sink1(i32 0)
4187  call void @sink1(i32 0)
4188  call void @sink1(i32 0)
4189  call void @sink1(i32 0)
4190  call void @sink1(i32 %phi)
4191  %inner.cond = call i1 @cond()
4192  br i1 %inner.cond, label %inner.header, label %inner.loopexit2
4193
4194inner.loopexit1:
4195  br label %outer.latch
4196; The unswitched `loopexit1` path.
4197;
4198; CHECK:       [[ENTRY_SPLIT]]:
4199; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
4200;
4201; CHECK:       outer.header:
4202; CHECK-NEXT:    br label %inner.loopexit1
4203;
4204; CHECK:       inner.loopexit1:
4205; CHECK-NEXT:    br label %outer.latch
4206;
4207; CHECK:       outer.latch:
4208; CHECK-NEXT:    %outer.cond = call i1 @cond()
4209; CHECK-NEXT:    br i1 %outer.cond, label %outer.header, label %[[EXIT_SPLIT:.*]]
4210;
4211; CHECK:       [[EXIT_SPLIT]]:
4212; CHECK-NEXT:    br label %exit
4213
4214inner.loopexit2:
4215  br label %outer.latch
4216
4217outer.latch:
4218  %outer.cond = call i1 @cond()
4219  br i1 %outer.cond, label %outer.header, label %exit
4220
4221exit:
4222  ret void
4223; CHECK:       exit:
4224; CHECK-NEXT:    ret void
4225}
4226
4227; Non-trivial partial loop unswitching of multiple invariant inputs to an `and`
4228; chain (select version).
4229define i32 @test32(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2) {
4230; CHECK-LABEL: @test32(
4231entry:
4232  br label %loop_begin
4233; CHECK-NEXT:  entry:
4234; CHECK-NEXT:    %[[INV_AND:.*]] = and i1 %cond2, %cond1
4235; CHECK-NEXT:    br i1 %[[INV_AND]], label %entry.split, label %entry.split.us
4236
4237loop_begin:
4238  %v1 = load i1, i1* %ptr1
4239  %v2 = load i1, i1* %ptr2
4240  %cond_and1 = select i1 %v1, i1 %cond1, i1 false
4241  %cond_and2 = select i1 %cond_and1, i1 %cond2, i1 false
4242  br i1 %cond_and2, label %loop_a, label %loop_b
4243; The 'loop_b' unswitched loop.
4244;
4245; CHECK:       entry.split.us:
4246; CHECK-NEXT:    br label %loop_begin.us
4247;
4248; CHECK:       loop_begin.us:
4249; CHECK-NEXT:    %[[V2_US]] = load i1, i1* %ptr2, align 1
4250; CHECK-NEXT:    br label %loop_b.us
4251;
4252; CHECK:       loop_b.us:
4253; CHECK-NEXT:    call i32 @b()
4254; CHECK-NEXT:    br label %latch.us
4255;
4256; CHECK:       latch.us:
4257; CHECK-NEXT:    %[[V3_US:.*]] = load i1, i1* %ptr3, align 1
4258; CHECK-NEXT:    br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us
4259;
4260; CHECK:       loop_exit.split.us:
4261; CHECK-NEXT:    br label %loop_exit
4262
4263; The original loop.
4264;
4265; CHECK:       entry.split:
4266; CHECK-NEXT:    br label %loop_begin
4267;
4268; CHECK:       loop_begin:
4269; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr1
4270; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr2
4271; CHECK-NEXT:    %[[AND1:.*]] = select i1 %[[V1]], i1 true, i1 false
4272; CHECK-NEXT:    %[[AND2:.*]] = select i1 %[[AND1]], i1 true, i1 false
4273; CHECK-NEXT:    br i1 %[[V1]], label %loop_a, label %loop_b
4274
4275loop_a:
4276  call i32 @a()
4277  br label %latch
4278; CHECK:       loop_a:
4279; CHECK-NEXT:    call i32 @a()
4280; CHECK-NEXT:    br label %latch
4281
4282loop_b:
4283  call i32 @b()
4284  br label %latch
4285; CHECK:       loop_b:
4286; CHECK-NEXT:    call i32 @b()
4287; CHECK-NEXT:    br label %latch
4288
4289latch:
4290  %v3 = load i1, i1* %ptr3
4291  br i1 %v3, label %loop_begin, label %loop_exit
4292; CHECK:       latch:
4293; CHECK-NEXT:    %[[V3:.*]] = load i1, i1* %ptr3, align 1
4294; CHECK-NEXT:    br i1 %[[V3]], label %loop_begin, label %loop_exit.split
4295
4296loop_exit:
4297  ret i32 0
4298; CHECK:       loop_exit.split:
4299; CHECK-NEXT:    br label %loop_exit
4300;
4301; CHECK:       loop_exit:
4302; CHECK-NEXT:    ret
4303}
4304
4305; Non-trivial partial loop unswitching of multiple invariant inputs to an `or`
4306; chain (select version).
4307define i32 @test33(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2) {
4308; CHECK-LABEL: @test33(
4309entry:
4310  br label %loop_begin
4311; CHECK-NEXT:  entry:
4312; CHECK-NEXT:    %[[INV_OR:.*]] = or i1 %cond2, %cond1
4313; CHECK-NEXT:    br i1 %[[INV_OR]], label %entry.split.us, label %entry.split
4314
4315loop_begin:
4316  %v1 = load i1, i1* %ptr1
4317  %v2 = load i1, i1* %ptr2
4318  %cond_and1 = select i1 %v1, i1 true, i1 %cond1
4319  %cond_and2 = select i1 %cond_and1, i1 true, i1 %cond2
4320  br i1 %cond_and2, label %loop_b, label %loop_a
4321; The 'loop_b' unswitched loop.
4322;
4323; CHECK:       entry.split.us:
4324; CHECK-NEXT:    br label %loop_begin.us
4325;
4326; CHECK:       loop_begin.us:
4327; CHECK-NEXT:    %[[V2_US]] = load i1, i1* %ptr2, align 1
4328; CHECK-NEXT:    br label %loop_b.us
4329;
4330; CHECK:       loop_b.us:
4331; CHECK-NEXT:    call i32 @b()
4332; CHECK-NEXT:    br label %latch.us
4333;
4334; CHECK:       latch.us:
4335; CHECK-NEXT:    %[[V3_US:.*]] = load i1, i1* %ptr3, align 1
4336; CHECK-NEXT:    br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us
4337;
4338; CHECK:       loop_exit.split.us:
4339; CHECK-NEXT:    br label %loop_exit
4340
4341; The original loop.
4342;
4343; CHECK:       entry.split:
4344; CHECK-NEXT:    br label %loop_begin
4345;
4346; CHECK:       loop_begin:
4347; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr1
4348; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr2
4349; CHECK-NEXT:    %[[AND1:.*]] = select i1 %[[V1]], i1 true, i1 false
4350; CHECK-NEXT:    %[[AND2:.*]] = select i1 %[[AND1]], i1 true, i1 false
4351; CHECK-NEXT:    br i1 %[[V1]], label %loop_b, label %loop_a
4352
4353loop_a:
4354  call i32 @a()
4355  br label %latch
4356; CHECK:       loop_a:
4357; CHECK-NEXT:    call i32 @a()
4358; CHECK-NEXT:    br label %latch
4359
4360loop_b:
4361  call i32 @b()
4362  br label %latch
4363; CHECK:       loop_b:
4364; CHECK-NEXT:    call i32 @b()
4365; CHECK-NEXT:    br label %latch
4366
4367latch:
4368  %v3 = load i1, i1* %ptr3
4369  br i1 %v3, label %loop_begin, label %loop_exit
4370; CHECK:       latch:
4371; CHECK-NEXT:    %[[V3:.*]] = load i1, i1* %ptr3, align 1
4372; CHECK-NEXT:    br i1 %[[V3]], label %loop_begin, label %loop_exit.split
4373
4374loop_exit:
4375  ret i32 0
4376; CHECK:       loop_exit.split:
4377; CHECK-NEXT:    br label %loop_exit
4378;
4379; CHECK:       loop_exit:
4380; CHECK-NEXT:    ret
4381}
4382