1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -loop-deletion -S | FileCheck %s
3; RUN: opt < %s -passes='loop(loop-deletion)' -S | FileCheck %s
4
5; The idea is that we know that %is.positive is true on the 1st iteration,
6; it means that we can evaluate %merge.phi = %sub on the 1st iteration,
7; and therefore prove that %sum.next = %sum + %sub = %sum + %limit - %sum = %limit,
8; and predicate is false.
9
10; TODO: We can break the backedge here.
11define i32 @test_ne(i32 %limit) {
12; CHECK-LABEL: @test_ne(
13; CHECK-NEXT:  entry:
14; CHECK-NEXT:    [[LOOP_GUARD:%.*]] = icmp sgt i32 [[LIMIT:%.*]], 0
15; CHECK-NEXT:    br i1 [[LOOP_GUARD]], label [[LOOP_PREHEADER:%.*]], label [[FAILURE:%.*]]
16; CHECK:       loop.preheader:
17; CHECK-NEXT:    br label [[LOOP:%.*]]
18; CHECK:       loop:
19; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
20; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[LIMIT]], [[SUM]]
21; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
22; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]]
23; CHECK:       if.false:
24; CHECK-NEXT:    br label [[BACKEDGE]]
25; CHECK:       backedge:
26; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ]
27; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
28; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], [[LIMIT]]
29; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
30; CHECK:       done:
31; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
32; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
33; CHECK:       failure:
34; CHECK-NEXT:    unreachable
35;
36entry:
37  %loop_guard = icmp sgt i32 %limit, 0
38  br i1 %loop_guard, label %loop, label %failure
39
40loop:                                             ; preds = %backedge, %entry
41  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
42  %sub = sub i32 %limit, %sum
43  %is.positive = icmp sgt i32 %sub, 0
44  br i1 %is.positive, label %backedge, label %if.false
45
46if.false:                                         ; preds = %loop
47  br label %backedge
48
49backedge:                                         ; preds = %if.false, %loop
50  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %loop ]
51  %sum.next = add i32 %sum, %merge.phi
52  %loop.cond = icmp ne i32 %sum.next, %limit
53  br i1 %loop.cond, label %loop, label %done
54
55done:                                             ; preds = %backedge
56  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
57  ret i32 %sum.next.lcssa
58
59failure:
60  unreachable
61}
62
63; TODO: We can break the backedge here.
64define i32 @test_slt(i32 %limit) {
65; CHECK-LABEL: @test_slt(
66; CHECK-NEXT:  entry:
67; CHECK-NEXT:    [[LOOP_GUARD:%.*]] = icmp sgt i32 [[LIMIT:%.*]], 0
68; CHECK-NEXT:    br i1 [[LOOP_GUARD]], label [[LOOP_PREHEADER:%.*]], label [[FAILURE:%.*]]
69; CHECK:       loop.preheader:
70; CHECK-NEXT:    br label [[LOOP:%.*]]
71; CHECK:       loop:
72; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
73; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[LIMIT]], [[SUM]]
74; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
75; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]]
76; CHECK:       if.false:
77; CHECK-NEXT:    br label [[BACKEDGE]]
78; CHECK:       backedge:
79; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ]
80; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
81; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[SUM_NEXT]], [[LIMIT]]
82; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
83; CHECK:       done:
84; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
85; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
86; CHECK:       failure:
87; CHECK-NEXT:    unreachable
88;
89entry:
90  %loop_guard = icmp sgt i32 %limit, 0
91  br i1 %loop_guard, label %loop, label %failure
92
93loop:                                             ; preds = %backedge, %entry
94  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
95  %sub = sub i32 %limit, %sum
96  %is.positive = icmp sgt i32 %sub, 0
97  br i1 %is.positive, label %backedge, label %if.false
98
99if.false:                                         ; preds = %loop
100  br label %backedge
101
102backedge:                                         ; preds = %if.false, %loop
103  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %loop ]
104  %sum.next = add i32 %sum, %merge.phi
105  %loop.cond = icmp slt i32 %sum.next, %limit
106  br i1 %loop.cond, label %loop, label %done
107
108done:                                             ; preds = %backedge
109  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
110  ret i32 %sum.next.lcssa
111
112failure:
113  unreachable
114}
115
116; TODO: We can break the backedge here.
117define i32 @test_ult(i32 %limit) {
118; CHECK-LABEL: @test_ult(
119; CHECK-NEXT:  entry:
120; CHECK-NEXT:    [[LOOP_GUARD:%.*]] = icmp sgt i32 [[LIMIT:%.*]], 0
121; CHECK-NEXT:    br i1 [[LOOP_GUARD]], label [[LOOP_PREHEADER:%.*]], label [[FAILURE:%.*]]
122; CHECK:       loop.preheader:
123; CHECK-NEXT:    br label [[LOOP:%.*]]
124; CHECK:       loop:
125; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
126; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[LIMIT]], [[SUM]]
127; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
128; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]]
129; CHECK:       if.false:
130; CHECK-NEXT:    br label [[BACKEDGE]]
131; CHECK:       backedge:
132; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ]
133; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
134; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[SUM_NEXT]], [[LIMIT]]
135; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
136; CHECK:       done:
137; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
138; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
139; CHECK:       failure:
140; CHECK-NEXT:    unreachable
141;
142entry:
143  %loop_guard = icmp sgt i32 %limit, 0
144  br i1 %loop_guard, label %loop, label %failure
145
146loop:                                             ; preds = %backedge, %entry
147  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
148  %sub = sub i32 %limit, %sum
149  %is.positive = icmp sgt i32 %sub, 0
150  br i1 %is.positive, label %backedge, label %if.false
151
152if.false:                                         ; preds = %loop
153  br label %backedge
154
155backedge:                                         ; preds = %if.false, %loop
156  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %loop ]
157  %sum.next = add i32 %sum, %merge.phi
158  %loop.cond = icmp ult i32 %sum.next, %limit
159  br i1 %loop.cond, label %loop, label %done
160
161done:                                             ; preds = %backedge
162  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
163  ret i32 %sum.next.lcssa
164
165failure:
166  unreachable
167}
168
169; TODO: We can break the backedge here.
170define i32 @test_sgt(i32 %limit) {
171; CHECK-LABEL: @test_sgt(
172; CHECK-NEXT:  entry:
173; CHECK-NEXT:    [[LOOP_GUARD:%.*]] = icmp sgt i32 [[LIMIT:%.*]], 0
174; CHECK-NEXT:    br i1 [[LOOP_GUARD]], label [[LOOP_PREHEADER:%.*]], label [[FAILURE:%.*]]
175; CHECK:       loop.preheader:
176; CHECK-NEXT:    br label [[LOOP:%.*]]
177; CHECK:       loop:
178; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
179; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[LIMIT]], [[SUM]]
180; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
181; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]]
182; CHECK:       if.false:
183; CHECK-NEXT:    br label [[BACKEDGE]]
184; CHECK:       backedge:
185; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ]
186; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
187; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp sgt i32 [[SUM_NEXT]], [[LIMIT]]
188; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
189; CHECK:       done:
190; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
191; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
192; CHECK:       failure:
193; CHECK-NEXT:    unreachable
194;
195entry:
196  %loop_guard = icmp sgt i32 %limit, 0
197  br i1 %loop_guard, label %loop, label %failure
198
199loop:                                             ; preds = %backedge, %entry
200  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
201  %sub = sub i32 %limit, %sum
202  %is.positive = icmp sgt i32 %sub, 0
203  br i1 %is.positive, label %backedge, label %if.false
204
205if.false:                                         ; preds = %loop
206  br label %backedge
207
208backedge:                                         ; preds = %if.false, %loop
209  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %loop ]
210  %sum.next = add i32 %sum, %merge.phi
211  %loop.cond = icmp sgt i32 %sum.next, %limit
212  br i1 %loop.cond, label %loop, label %done
213
214done:                                             ; preds = %backedge
215  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
216  ret i32 %sum.next.lcssa
217
218failure:
219  unreachable
220}
221
222; TODO: We can break the backedge here.
223define i32 @test_ugt(i32 %limit) {
224; CHECK-LABEL: @test_ugt(
225; CHECK-NEXT:  entry:
226; CHECK-NEXT:    [[LOOP_GUARD:%.*]] = icmp sgt i32 [[LIMIT:%.*]], 0
227; CHECK-NEXT:    br i1 [[LOOP_GUARD]], label [[LOOP_PREHEADER:%.*]], label [[FAILURE:%.*]]
228; CHECK:       loop.preheader:
229; CHECK-NEXT:    br label [[LOOP:%.*]]
230; CHECK:       loop:
231; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
232; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[LIMIT]], [[SUM]]
233; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
234; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]]
235; CHECK:       if.false:
236; CHECK-NEXT:    br label [[BACKEDGE]]
237; CHECK:       backedge:
238; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ]
239; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
240; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ugt i32 [[SUM_NEXT]], [[LIMIT]]
241; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
242; CHECK:       done:
243; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
244; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
245; CHECK:       failure:
246; CHECK-NEXT:    unreachable
247;
248entry:
249  %loop_guard = icmp sgt i32 %limit, 0
250  br i1 %loop_guard, label %loop, label %failure
251
252loop:                                             ; preds = %backedge, %entry
253  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
254  %sub = sub i32 %limit, %sum
255  %is.positive = icmp sgt i32 %sub, 0
256  br i1 %is.positive, label %backedge, label %if.false
257
258if.false:                                         ; preds = %loop
259  br label %backedge
260
261backedge:                                         ; preds = %if.false, %loop
262  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %loop ]
263  %sum.next = add i32 %sum, %merge.phi
264  %loop.cond = icmp ugt i32 %sum.next, %limit
265  br i1 %loop.cond, label %loop, label %done
266
267done:                                             ; preds = %backedge
268  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
269  ret i32 %sum.next.lcssa
270
271failure:
272  unreachable
273}
274
275; TODO: We can break the backedge here.
276define i32 @test_multiple_pred(i32 %limit) {
277; CHECK-LABEL: @test_multiple_pred(
278; CHECK-NEXT:  entry:
279; CHECK-NEXT:    [[LOOP_GUARD:%.*]] = icmp sgt i32 [[LIMIT:%.*]], 0
280; CHECK-NEXT:    br i1 [[LOOP_GUARD]], label [[LOOP_PREHEADER:%.*]], label [[FAILURE:%.*]]
281; CHECK:       loop.preheader:
282; CHECK-NEXT:    br label [[LOOP:%.*]]
283; CHECK:       loop:
284; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
285; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[LIMIT]], [[SUM]]
286; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
287; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
288; CHECK:       if.true:
289; CHECK-NEXT:    switch i32 [[LIMIT]], label [[FAILURE_LOOPEXIT:%.*]] [
290; CHECK-NEXT:    i32 100, label [[BACKEDGE]]
291; CHECK-NEXT:    i32 200, label [[BACKEDGE]]
292; CHECK-NEXT:    ]
293; CHECK:       if.false:
294; CHECK-NEXT:    br label [[BACKEDGE]]
295; CHECK:       backedge:
296; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[IF_TRUE]] ], [ [[SUB]], [[IF_TRUE]] ]
297; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
298; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], [[LIMIT]]
299; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
300; CHECK:       done:
301; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
302; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
303; CHECK:       failure.loopexit:
304; CHECK-NEXT:    br label [[FAILURE]]
305; CHECK:       failure:
306; CHECK-NEXT:    unreachable
307;
308entry:
309  %loop_guard = icmp sgt i32 %limit, 0
310  br i1 %loop_guard, label %loop, label %failure
311
312loop:                                             ; preds = %backedge, %entry
313  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
314  %sub = sub i32 %limit, %sum
315  %is.positive = icmp sgt i32 %sub, 0
316  br i1 %is.positive, label %if.true, label %if.false
317
318if.true:
319  switch i32 %limit, label %failure [
320  i32 100, label %backedge
321  i32 200, label %backedge
322  ]
323
324if.false:                                         ; preds = %loop
325  br label %backedge
326
327backedge:
328  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %if.true ], [ %sub, %if.true ]
329  %sum.next = add i32 %sum, %merge.phi
330  %loop.cond = icmp ne i32 %sum.next, %limit
331  br i1 %loop.cond, label %loop, label %done
332
333done:                                             ; preds = %backedge
334  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
335  ret i32 %sum.next.lcssa
336
337failure:
338  unreachable
339}
340
341define i32 @test_ne_const() {
342; CHECK-LABEL: @test_ne_const(
343; CHECK-NEXT:  entry:
344; CHECK-NEXT:    br label [[LOOP:%.*]]
345; CHECK:       loop:
346; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
347; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
348; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
349; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]]
350; CHECK:       if.false:
351; CHECK-NEXT:    br label [[BACKEDGE]]
352; CHECK:       backedge:
353; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ]
354; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
355; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
356; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
357; CHECK:       backedge.loop_crit_edge:
358; CHECK-NEXT:    unreachable
359; CHECK:       done:
360; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
361; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
362; CHECK:       failure:
363; CHECK-NEXT:    unreachable
364;
365entry:
366
367  br label %loop
368
369loop:                                             ; preds = %backedge, %entry
370  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
371  %sub = sub i32 4, %sum
372  %is.positive = icmp sgt i32 %sub, 0
373  br i1 %is.positive, label %backedge, label %if.false
374
375if.false:                                         ; preds = %loop
376  br label %backedge
377
378backedge:                                         ; preds = %if.false, %loop
379  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %loop ]
380  %sum.next = add i32 %sum, %merge.phi
381  %loop.cond = icmp ne i32 %sum.next, 4
382  br i1 %loop.cond, label %loop, label %done
383
384done:                                             ; preds = %backedge
385  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
386  ret i32 %sum.next.lcssa
387
388failure:
389  unreachable
390}
391
392define i32 @test_slt_const() {
393; CHECK-LABEL: @test_slt_const(
394; CHECK-NEXT:  entry:
395; CHECK-NEXT:    br label [[LOOP:%.*]]
396; CHECK:       loop:
397; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
398; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
399; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
400; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]]
401; CHECK:       if.false:
402; CHECK-NEXT:    br label [[BACKEDGE]]
403; CHECK:       backedge:
404; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ]
405; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
406; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[SUM_NEXT]], 4
407; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
408; CHECK:       backedge.loop_crit_edge:
409; CHECK-NEXT:    unreachable
410; CHECK:       done:
411; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
412; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
413; CHECK:       failure:
414; CHECK-NEXT:    unreachable
415;
416entry:
417
418  br label %loop
419
420loop:                                             ; preds = %backedge, %entry
421  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
422  %sub = sub i32 4, %sum
423  %is.positive = icmp sgt i32 %sub, 0
424  br i1 %is.positive, label %backedge, label %if.false
425
426if.false:                                         ; preds = %loop
427  br label %backedge
428
429backedge:                                         ; preds = %if.false, %loop
430  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %loop ]
431  %sum.next = add i32 %sum, %merge.phi
432  %loop.cond = icmp slt i32 %sum.next, 4
433  br i1 %loop.cond, label %loop, label %done
434
435done:                                             ; preds = %backedge
436  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
437  ret i32 %sum.next.lcssa
438
439failure:
440  unreachable
441}
442
443define i32 @test_ult_const() {
444; CHECK-LABEL: @test_ult_const(
445; CHECK-NEXT:  entry:
446; CHECK-NEXT:    br label [[LOOP:%.*]]
447; CHECK:       loop:
448; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
449; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
450; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
451; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]]
452; CHECK:       if.false:
453; CHECK-NEXT:    br label [[BACKEDGE]]
454; CHECK:       backedge:
455; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ]
456; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
457; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[SUM_NEXT]], 4
458; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
459; CHECK:       backedge.loop_crit_edge:
460; CHECK-NEXT:    unreachable
461; CHECK:       done:
462; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
463; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
464; CHECK:       failure:
465; CHECK-NEXT:    unreachable
466;
467entry:
468
469  br label %loop
470
471loop:                                             ; preds = %backedge, %entry
472  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
473  %sub = sub i32 4, %sum
474  %is.positive = icmp sgt i32 %sub, 0
475  br i1 %is.positive, label %backedge, label %if.false
476
477if.false:                                         ; preds = %loop
478  br label %backedge
479
480backedge:                                         ; preds = %if.false, %loop
481  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %loop ]
482  %sum.next = add i32 %sum, %merge.phi
483  %loop.cond = icmp ult i32 %sum.next, 4
484  br i1 %loop.cond, label %loop, label %done
485
486done:                                             ; preds = %backedge
487  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
488  ret i32 %sum.next.lcssa
489
490failure:
491  unreachable
492}
493
494define i32 @test_sgt_const() {
495; CHECK-LABEL: @test_sgt_const(
496; CHECK-NEXT:  entry:
497; CHECK-NEXT:    br label [[LOOP:%.*]]
498; CHECK:       loop:
499; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
500; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
501; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
502; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]]
503; CHECK:       if.false:
504; CHECK-NEXT:    br label [[BACKEDGE]]
505; CHECK:       backedge:
506; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ]
507; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
508; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp sgt i32 [[SUM_NEXT]], 4
509; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
510; CHECK:       backedge.loop_crit_edge:
511; CHECK-NEXT:    unreachable
512; CHECK:       done:
513; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
514; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
515; CHECK:       failure:
516; CHECK-NEXT:    unreachable
517;
518entry:
519
520  br label %loop
521
522loop:                                             ; preds = %backedge, %entry
523  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
524  %sub = sub i32 4, %sum
525  %is.positive = icmp sgt i32 %sub, 0
526  br i1 %is.positive, label %backedge, label %if.false
527
528if.false:                                         ; preds = %loop
529  br label %backedge
530
531backedge:                                         ; preds = %if.false, %loop
532  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %loop ]
533  %sum.next = add i32 %sum, %merge.phi
534  %loop.cond = icmp sgt i32 %sum.next, 4
535  br i1 %loop.cond, label %loop, label %done
536
537done:                                             ; preds = %backedge
538  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
539  ret i32 %sum.next.lcssa
540
541failure:
542  unreachable
543}
544
545define i32 @test_ugt_const() {
546; CHECK-LABEL: @test_ugt_const(
547; CHECK-NEXT:  entry:
548; CHECK-NEXT:    br label [[LOOP:%.*]]
549; CHECK:       loop:
550; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
551; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
552; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
553; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]]
554; CHECK:       if.false:
555; CHECK-NEXT:    br label [[BACKEDGE]]
556; CHECK:       backedge:
557; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ]
558; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
559; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ugt i32 [[SUM_NEXT]], 4
560; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
561; CHECK:       backedge.loop_crit_edge:
562; CHECK-NEXT:    unreachable
563; CHECK:       done:
564; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
565; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
566; CHECK:       failure:
567; CHECK-NEXT:    unreachable
568;
569entry:
570
571  br label %loop
572
573loop:                                             ; preds = %backedge, %entry
574  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
575  %sub = sub i32 4, %sum
576  %is.positive = icmp sgt i32 %sub, 0
577  br i1 %is.positive, label %backedge, label %if.false
578
579if.false:                                         ; preds = %loop
580  br label %backedge
581
582backedge:                                         ; preds = %if.false, %loop
583  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %loop ]
584  %sum.next = add i32 %sum, %merge.phi
585  %loop.cond = icmp ugt i32 %sum.next, 4
586  br i1 %loop.cond, label %loop, label %done
587
588done:                                             ; preds = %backedge
589  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
590  ret i32 %sum.next.lcssa
591
592failure:
593  unreachable
594}
595
596define i32 @test_multiple_pred_const() {
597; CHECK-LABEL: @test_multiple_pred_const(
598; CHECK-NEXT:  entry:
599; CHECK-NEXT:    br label [[LOOP:%.*]]
600; CHECK:       loop:
601; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
602; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
603; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
604; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
605; CHECK:       if.true:
606; CHECK-NEXT:    switch i32 4, label [[FAILURE:%.*]] [
607; CHECK-NEXT:    i32 100, label [[BACKEDGE:%.*]]
608; CHECK-NEXT:    i32 200, label [[BACKEDGE]]
609; CHECK-NEXT:    ]
610; CHECK:       if.false:
611; CHECK-NEXT:    br label [[BACKEDGE]]
612; CHECK:       backedge:
613; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[IF_TRUE]] ], [ [[SUB]], [[IF_TRUE]] ]
614; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
615; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
616; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
617; CHECK:       backedge.loop_crit_edge:
618; CHECK-NEXT:    unreachable
619; CHECK:       done:
620; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
621; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
622; CHECK:       failure:
623; CHECK-NEXT:    unreachable
624;
625entry:
626
627  br label %loop
628
629loop:                                             ; preds = %backedge, %entry
630  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
631  %sub = sub i32 4, %sum
632  %is.positive = icmp sgt i32 %sub, 0
633  br i1 %is.positive, label %if.true, label %if.false
634
635if.true:
636  switch i32 4, label %failure [
637  i32 100, label %backedge
638  i32 200, label %backedge
639  ]
640
641if.false:                                         ; preds = %loop
642  br label %backedge
643
644backedge:
645  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %if.true ], [ %sub, %if.true ]
646  %sum.next = add i32 %sum, %merge.phi
647  %loop.cond = icmp ne i32 %sum.next, 4
648  br i1 %loop.cond, label %loop, label %done
649
650done:                                             ; preds = %backedge
651  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
652  ret i32 %sum.next.lcssa
653
654failure:
655  unreachable
656}
657
658define i32 @test_multiple_pred_2(i1 %cond, i1 %cond2) {
659; CHECK-LABEL: @test_multiple_pred_2(
660; CHECK-NEXT:  entry:
661; CHECK-NEXT:    br label [[LOOP:%.*]]
662; CHECK:       loop:
663; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
664; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
665; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
666; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
667; CHECK:       if.true:
668; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_TRUE_2:%.*]]
669; CHECK:       if.true.1:
670; CHECK-NEXT:    br label [[BACKEDGE:%.*]]
671; CHECK:       if.true.2:
672; CHECK-NEXT:    br label [[BACKEDGE]]
673; CHECK:       if.false:
674; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[IF_FALSE_1:%.*]], label [[IF_FALSE_2:%.*]]
675; CHECK:       if.false.1:
676; CHECK-NEXT:    br label [[BACKEDGE]]
677; CHECK:       if.false.2:
678; CHECK-NEXT:    br label [[BACKEDGE]]
679; CHECK:       backedge:
680; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE_1]] ], [ 0, [[IF_FALSE_2]] ], [ [[SUB]], [[IF_TRUE_1]] ], [ [[SUB]], [[IF_TRUE_2]] ]
681; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
682; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
683; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
684; CHECK:       backedge.loop_crit_edge:
685; CHECK-NEXT:    unreachable
686; CHECK:       done:
687; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
688; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
689; CHECK:       failure:
690; CHECK-NEXT:    unreachable
691;
692entry:
693
694  br label %loop
695
696loop:                                             ; preds = %backedge, %entry
697  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
698  %sub = sub i32 4, %sum
699  %is.positive = icmp sgt i32 %sub, 0
700  br i1 %is.positive, label %if.true, label %if.false
701
702if.true:
703  br i1 %cond, label %if.true.1, label %if.true.2
704
705if.true.1:
706  br label %backedge
707
708if.true.2:
709  br label %backedge
710
711if.false:                                         ; preds = %loop
712  br i1 %cond2, label %if.false.1, label %if.false.2
713
714if.false.1:
715  br label %backedge
716
717if.false.2:
718  br label %backedge
719
720backedge:
721  %merge.phi = phi i32 [ 0, %if.false.1 ], [ 0, %if.false.2 ], [ %sub, %if.true.1 ], [ %sub, %if.true.2 ]
722  %sum.next = add i32 %sum, %merge.phi
723  %loop.cond = icmp ne i32 %sum.next, 4
724  br i1 %loop.cond, label %loop, label %done
725
726done:                                             ; preds = %backedge
727  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
728  ret i32 %sum.next.lcssa
729
730failure:
731  unreachable
732}
733
734define i32 @test_multiple_pred_undef_1(i1 %cond, i1 %cond2) {
735; CHECK-LABEL: @test_multiple_pred_undef_1(
736; CHECK-NEXT:  entry:
737; CHECK-NEXT:    br label [[LOOP:%.*]]
738; CHECK:       loop:
739; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
740; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
741; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
742; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
743; CHECK:       if.true:
744; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_TRUE_2:%.*]]
745; CHECK:       if.true.1:
746; CHECK-NEXT:    br label [[BACKEDGE:%.*]]
747; CHECK:       if.true.2:
748; CHECK-NEXT:    br label [[BACKEDGE]]
749; CHECK:       if.false:
750; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[IF_FALSE_1:%.*]], label [[IF_FALSE_2:%.*]]
751; CHECK:       if.false.1:
752; CHECK-NEXT:    br label [[BACKEDGE]]
753; CHECK:       if.false.2:
754; CHECK-NEXT:    br label [[BACKEDGE]]
755; CHECK:       backedge:
756; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE_1]] ], [ 0, [[IF_FALSE_2]] ], [ [[SUB]], [[IF_TRUE_1]] ], [ undef, [[IF_TRUE_2]] ]
757; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
758; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
759; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
760; CHECK:       backedge.loop_crit_edge:
761; CHECK-NEXT:    unreachable
762; CHECK:       done:
763; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
764; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
765; CHECK:       failure:
766; CHECK-NEXT:    unreachable
767;
768entry:
769  br label %loop
770
771loop:                                             ; preds = %backedge, %entry
772  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
773  %sub = sub i32 4, %sum
774  %is.positive = icmp sgt i32 %sub, 0
775  br i1 %is.positive, label %if.true, label %if.false
776
777if.true:
778  br i1 %cond, label %if.true.1, label %if.true.2
779
780if.true.1:
781  br label %backedge
782
783if.true.2:
784  br label %backedge
785
786if.false:                                         ; preds = %loop
787  br i1 %cond2, label %if.false.1, label %if.false.2
788
789if.false.1:
790  br label %backedge
791
792if.false.2:
793  br label %backedge
794
795backedge:
796  %merge.phi = phi i32 [ 0, %if.false.1 ], [ 0, %if.false.2 ], [ %sub, %if.true.1 ], [ undef, %if.true.2 ]
797  %sum.next = add i32 %sum, %merge.phi
798  %loop.cond = icmp ne i32 %sum.next, 4
799  br i1 %loop.cond, label %loop, label %done
800
801done:                                             ; preds = %backedge
802  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
803  ret i32 %sum.next.lcssa
804
805failure:
806  unreachable
807}
808
809define i32 @test_multiple_pred_undef_2(i1 %cond, i1 %cond2) {
810; CHECK-LABEL: @test_multiple_pred_undef_2(
811; CHECK-NEXT:  entry:
812; CHECK-NEXT:    br label [[LOOP:%.*]]
813; CHECK:       loop:
814; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
815; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
816; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
817; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
818; CHECK:       if.true:
819; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_TRUE_2:%.*]]
820; CHECK:       if.true.1:
821; CHECK-NEXT:    br label [[BACKEDGE:%.*]]
822; CHECK:       if.true.2:
823; CHECK-NEXT:    br label [[BACKEDGE]]
824; CHECK:       if.false:
825; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[IF_FALSE_1:%.*]], label [[IF_FALSE_2:%.*]]
826; CHECK:       if.false.1:
827; CHECK-NEXT:    br label [[BACKEDGE]]
828; CHECK:       if.false.2:
829; CHECK-NEXT:    br label [[BACKEDGE]]
830; CHECK:       backedge:
831; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE_1]] ], [ 0, [[IF_FALSE_2]] ], [ undef, [[IF_TRUE_1]] ], [ [[SUB]], [[IF_TRUE_2]] ]
832; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
833; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
834; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
835; CHECK:       backedge.loop_crit_edge:
836; CHECK-NEXT:    unreachable
837; CHECK:       done:
838; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
839; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
840; CHECK:       failure:
841; CHECK-NEXT:    unreachable
842;
843entry:
844  br label %loop
845
846loop:                                             ; preds = %backedge, %entry
847  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
848  %sub = sub i32 4, %sum
849  %is.positive = icmp sgt i32 %sub, 0
850  br i1 %is.positive, label %if.true, label %if.false
851
852if.true:
853  br i1 %cond, label %if.true.1, label %if.true.2
854
855if.true.1:
856  br label %backedge
857
858if.true.2:
859  br label %backedge
860
861if.false:                                         ; preds = %loop
862  br i1 %cond2, label %if.false.1, label %if.false.2
863
864if.false.1:
865  br label %backedge
866
867if.false.2:
868  br label %backedge
869
870backedge:
871  %merge.phi = phi i32 [ 0, %if.false.1 ], [ 0, %if.false.2 ], [ undef, %if.true.1 ], [ %sub, %if.true.2 ]
872  %sum.next = add i32 %sum, %merge.phi
873  %loop.cond = icmp ne i32 %sum.next, 4
874  br i1 %loop.cond, label %loop, label %done
875
876done:                                             ; preds = %backedge
877  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
878  ret i32 %sum.next.lcssa
879
880failure:
881  unreachable
882}
883
884define i32 @test_multiple_pred_undef_3(i1 %cond, i1 %cond2) {
885; CHECK-LABEL: @test_multiple_pred_undef_3(
886; CHECK-NEXT:  entry:
887; CHECK-NEXT:    br label [[LOOP:%.*]]
888; CHECK:       loop:
889; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
890; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
891; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
892; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
893; CHECK:       if.true:
894; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_TRUE_2:%.*]]
895; CHECK:       if.true.1:
896; CHECK-NEXT:    br label [[BACKEDGE:%.*]]
897; CHECK:       if.true.2:
898; CHECK-NEXT:    br label [[BACKEDGE]]
899; CHECK:       if.false:
900; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[IF_FALSE_1:%.*]], label [[IF_FALSE_2:%.*]]
901; CHECK:       if.false.1:
902; CHECK-NEXT:    br label [[BACKEDGE]]
903; CHECK:       if.false.2:
904; CHECK-NEXT:    br label [[BACKEDGE]]
905; CHECK:       backedge:
906; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE_1]] ], [ 0, [[IF_FALSE_2]] ], [ undef, [[IF_TRUE_1]] ], [ undef, [[IF_TRUE_2]] ]
907; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
908; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
909; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
910; CHECK:       backedge.loop_crit_edge:
911; CHECK-NEXT:    unreachable
912; CHECK:       done:
913; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
914; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
915; CHECK:       failure:
916; CHECK-NEXT:    unreachable
917;
918entry:
919  br label %loop
920
921loop:                                             ; preds = %backedge, %entry
922  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
923  %sub = sub i32 4, %sum
924  %is.positive = icmp sgt i32 %sub, 0
925  br i1 %is.positive, label %if.true, label %if.false
926
927if.true:
928  br i1 %cond, label %if.true.1, label %if.true.2
929
930if.true.1:
931  br label %backedge
932
933if.true.2:
934  br label %backedge
935
936if.false:                                         ; preds = %loop
937  br i1 %cond2, label %if.false.1, label %if.false.2
938
939if.false.1:
940  br label %backedge
941
942if.false.2:
943  br label %backedge
944
945backedge:
946  %merge.phi = phi i32 [ 0, %if.false.1 ], [ 0, %if.false.2 ], [ undef, %if.true.1 ], [ undef, %if.true.2 ]
947  %sum.next = add i32 %sum, %merge.phi
948  %loop.cond = icmp ne i32 %sum.next, 4
949  br i1 %loop.cond, label %loop, label %done
950
951done:                                             ; preds = %backedge
952  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
953  ret i32 %sum.next.lcssa
954
955failure:
956  unreachable
957}
958
959; TODO: We can break the backedge here.
960define i32 @test_select(i32 %limit) {
961; CHECK-LABEL: @test_select(
962; CHECK-NEXT:  entry:
963; CHECK-NEXT:    [[LOOP_GUARD:%.*]] = icmp sgt i32 [[LIMIT:%.*]], 0
964; CHECK-NEXT:    br i1 [[LOOP_GUARD]], label [[LOOP_PREHEADER:%.*]], label [[FAILURE:%.*]]
965; CHECK:       loop.preheader:
966; CHECK-NEXT:    br label [[LOOP:%.*]]
967; CHECK:       loop:
968; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[LOOP]] ], [ 0, [[LOOP_PREHEADER]] ]
969; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[LIMIT]], [[SUM]]
970; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
971; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[IS_POSITIVE]], i32 [[SUB]], i32 0
972; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[SEL]]
973; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], [[LIMIT]]
974; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
975; CHECK:       done:
976; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[LOOP]] ]
977; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
978; CHECK:       failure:
979; CHECK-NEXT:    unreachable
980;
981entry:
982  %loop_guard = icmp sgt i32 %limit, 0
983  br i1 %loop_guard, label %loop, label %failure
984
985loop:                                             ; preds = %backedge, %entry
986  %sum = phi i32 [ 0, %entry ], [ %sum.next, %loop ]
987  %sub = sub i32 %limit, %sum
988  %is.positive = icmp sgt i32 %sub, 0
989  %sel = select i1 %is.positive, i32 %sub, i32 0
990  %sum.next = add i32 %sum, %sel
991  %loop.cond = icmp ne i32 %sum.next, %limit
992  br i1 %loop.cond, label %loop, label %done
993
994done:                                             ; preds = %backedge
995  %sum.next.lcssa = phi i32 [ %sum.next, %loop ]
996  ret i32 %sum.next.lcssa
997
998failure:
999  unreachable
1000}
1001
1002; TODO: We can break the backedge here.
1003define i32 @test_select_const(i32 %x) {
1004; CHECK-LABEL: @test_select_const(
1005; CHECK-NEXT:  entry:
1006; CHECK-NEXT:    br label [[LOOP:%.*]]
1007; CHECK:       loop:
1008; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ]
1009; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
1010; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
1011; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[IS_POSITIVE]], i32 [[SUB]], i32 [[X:%.*]]
1012; CHECK-NEXT:    [[SEL_COND:%.*]] = icmp sgt i32 [[SEL]], 0
1013; CHECK-NEXT:    br i1 [[SEL_COND]], label [[BACKEDGE]], label [[IF_FALSE:%.*]]
1014; CHECK:       if.false:
1015; CHECK-NEXT:    br label [[BACKEDGE]]
1016; CHECK:       backedge:
1017; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ]
1018; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
1019; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
1020; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
1021; CHECK:       done:
1022; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
1023; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
1024;
1025entry:
1026  br label %loop
1027
1028loop:                                             ; preds = %backedge, %entry
1029  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
1030  %sub = sub i32 4, %sum
1031  %is.positive = icmp sgt i32 %sub, 0
1032  %sel = select i1 %is.positive, i32 %sub, i32 %x
1033  %sel.cond = icmp sgt i32 %sel, 0
1034  br i1 %sel.cond, label %backedge, label %if.false
1035
1036if.false:                                         ; preds = %loop
1037  br label %backedge
1038
1039backedge:                                         ; preds = %if.false, %loop
1040  %merge.phi = phi i32 [ 0, %if.false ], [ %sub, %loop ]
1041  %sum.next = add i32 %sum, %merge.phi
1042  %loop.cond = icmp ne i32 %sum.next, 4
1043  br i1 %loop.cond, label %loop, label %done
1044
1045done:                                             ; preds = %backedge
1046  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
1047  ret i32 %sum.next.lcssa
1048}
1049
1050
1051
1052; Switch tests
1053
1054; Here switch will always jump to the default label
1055define i32 @test_switch_ne_default() {
1056; CHECK-LABEL: @test_switch_ne_default(
1057; CHECK-NEXT:  entry:
1058; CHECK-NEXT:    br label [[LOOP:%.*]]
1059; CHECK:       loop:
1060; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
1061; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
1062; CHECK-NEXT:    switch i32 [[SUB]], label [[DEFAULT:%.*]] [
1063; CHECK-NEXT:    i32 0, label [[ONZERO:%.*]]
1064; CHECK-NEXT:    i32 1, label [[ONONE:%.*]]
1065; CHECK-NEXT:    i32 2, label [[ONTWO:%.*]]
1066; CHECK-NEXT:    ]
1067; CHECK:       default:
1068; CHECK-NEXT:    br label [[BACKEDGE:%.*]]
1069; CHECK:       onzero:
1070; CHECK-NEXT:    br label [[BACKEDGE]]
1071; CHECK:       onone:
1072; CHECK-NEXT:    br label [[BACKEDGE]]
1073; CHECK:       ontwo:
1074; CHECK-NEXT:    br label [[BACKEDGE]]
1075; CHECK:       backedge:
1076; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ [[SUB]], [[DEFAULT]] ], [ 0, [[ONZERO]] ], [ 1, [[ONONE]] ], [ 2, [[ONTWO]] ]
1077; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
1078; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
1079; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
1080; CHECK:       backedge.loop_crit_edge:
1081; CHECK-NEXT:    unreachable
1082; CHECK:       done:
1083; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
1084; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
1085;
1086entry:
1087  br label %loop
1088
1089loop:                                             ; preds = %backedge, %entry
1090  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
1091  %sub = sub i32 4, %sum
1092  switch i32 %sub, label %default [
1093  i32 0, label %onzero
1094  i32 1, label %onone
1095  i32 2, label %ontwo
1096  ]
1097
1098default:                                          ; preds = %loop
1099  br label %backedge
1100
1101onzero:                                           ; preds = %loop
1102  br label %backedge
1103
1104onone:                                            ; preds = %loop
1105  br label %backedge
1106
1107ontwo:                                            ; preds = %loop
1108  br label %backedge
1109
1110backedge:                                         ; preds = %ontwo, %onone, %onzero, %default
1111  %merge.phi = phi i32 [ %sub, %default ], [ 0, %onzero ], [ 1, %onone ], [ 2, %ontwo ]
1112  %sum.next = add i32 %sum, %merge.phi
1113  %loop.cond = icmp ne i32 %sum.next, 4
1114  br i1 %loop.cond, label %loop, label %done
1115
1116done:                                             ; preds = %backedge
1117  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
1118  ret i32 %sum.next.lcssa
1119}
1120
1121; Here switch will always jump to the %ontwo label
1122define i32 @test_switch_ne_one_case() {
1123; CHECK-LABEL: @test_switch_ne_one_case(
1124; CHECK-NEXT:  entry:
1125; CHECK-NEXT:    br label [[LOOP:%.*]]
1126; CHECK:       loop:
1127; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
1128; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
1129; CHECK-NEXT:    switch i32 [[SUB]], label [[DEFAULT:%.*]] [
1130; CHECK-NEXT:    i32 0, label [[ONZERO:%.*]]
1131; CHECK-NEXT:    i32 1, label [[ONONE:%.*]]
1132; CHECK-NEXT:    i32 4, label [[ONTWO:%.*]]
1133; CHECK-NEXT:    ]
1134; CHECK:       default:
1135; CHECK-NEXT:    br label [[BACKEDGE:%.*]]
1136; CHECK:       onzero:
1137; CHECK-NEXT:    br label [[BACKEDGE]]
1138; CHECK:       onone:
1139; CHECK-NEXT:    br label [[BACKEDGE]]
1140; CHECK:       ontwo:
1141; CHECK-NEXT:    br label [[BACKEDGE]]
1142; CHECK:       backedge:
1143; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 2, [[DEFAULT]] ], [ 0, [[ONZERO]] ], [ 1, [[ONONE]] ], [ [[SUB]], [[ONTWO]] ]
1144; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
1145; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
1146; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
1147; CHECK:       backedge.loop_crit_edge:
1148; CHECK-NEXT:    unreachable
1149; CHECK:       done:
1150; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
1151; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
1152;
1153entry:
1154  br label %loop
1155
1156loop:                                             ; preds = %backedge, %entry
1157  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
1158  %sub = sub i32 4, %sum
1159  switch i32 %sub, label %default [
1160  i32 0, label %onzero
1161  i32 1, label %onone
1162  i32 4, label %ontwo
1163  ]
1164
1165default:                                          ; preds = %loop
1166  br label %backedge
1167
1168onzero:                                           ; preds = %loop
1169  br label %backedge
1170
1171onone:                                            ; preds = %loop
1172  br label %backedge
1173
1174ontwo:                                            ; preds = %loop
1175  br label %backedge
1176
1177backedge:                                         ; preds = %ontwo, %onone, %onzero, %default
1178  %merge.phi = phi i32 [ 2, %default ], [ 0, %onzero ], [ 1, %onone ], [ %sub, %ontwo ]
1179  %sum.next = add i32 %sum, %merge.phi
1180  %loop.cond = icmp ne i32 %sum.next, 4
1181  br i1 %loop.cond, label %loop, label %done
1182
1183done:                                             ; preds = %backedge
1184  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
1185  ret i32 %sum.next.lcssa
1186}
1187
1188; Here switch will always jump to the %backedge label, but there are two jumps to this label in switch
1189define i32 @test_switch_ne_one_case_identical_jumps() {
1190; CHECK-LABEL: @test_switch_ne_one_case_identical_jumps(
1191; CHECK-NEXT:  entry:
1192; CHECK-NEXT:    br label [[LOOP:%.*]]
1193; CHECK:       loop:
1194; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
1195; CHECK-NEXT:    [[SUB:%.*]] = sub i32 2, [[SUM]]
1196; CHECK-NEXT:    switch i32 [[SUB]], label [[DEFAULT:%.*]] [
1197; CHECK-NEXT:    i32 0, label [[FIRST_BLOCK:%.*]]
1198; CHECK-NEXT:    i32 1, label [[BACKEDGE:%.*]]
1199; CHECK-NEXT:    i32 2, label [[BACKEDGE]]
1200; CHECK-NEXT:    ]
1201; CHECK:       default:
1202; CHECK-NEXT:    br label [[BACKEDGE]]
1203; CHECK:       first_block:
1204; CHECK-NEXT:    br label [[BACKEDGE]]
1205; CHECK:       backedge:
1206; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[DEFAULT]] ], [ 1, [[FIRST_BLOCK]] ], [ [[SUB]], [[LOOP]] ], [ [[SUB]], [[LOOP]] ]
1207; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
1208; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 2
1209; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
1210; CHECK:       backedge.loop_crit_edge:
1211; CHECK-NEXT:    unreachable
1212; CHECK:       done:
1213; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
1214; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
1215;
1216entry:
1217  br label %loop
1218
1219loop:                                             ; preds = %backedge, %entry
1220  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
1221  %sub = sub i32 2, %sum
1222  switch i32 %sub, label %default [
1223  i32 0, label %first_block
1224  i32 1, label %backedge
1225  i32 2, label %backedge
1226  ]
1227
1228default:                                          ; preds = %loop
1229  br label %backedge
1230
1231first_block:                                      ; preds = %loop
1232  br label %backedge
1233
1234backedge:                                         ; preds = %first_block, %default, %loop, %loop
1235  %merge.phi = phi i32 [ 0, %default ], [ 1, %first_block ], [ %sub, %loop ], [ %sub, %loop ]
1236  %sum.next = add i32 %sum, %merge.phi
1237  %loop.cond = icmp ne i32 %sum.next, 2
1238  br i1 %loop.cond, label %loop, label %done
1239
1240done:                                             ; preds = %backedge
1241  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
1242  ret i32 %sum.next.lcssa
1243}
1244