1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -S < %s -passes=instcombine | FileCheck %s
3
4define i1 @test_direct_implication(i1 %cond) {
5; CHECK-LABEL: @test_direct_implication(
6; CHECK-NEXT:  entry:
7; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
8; CHECK:       if.true:
9; CHECK-NEXT:    br label [[MERGE:%.*]]
10; CHECK:       if.false:
11; CHECK-NEXT:    br label [[MERGE]]
12; CHECK:       merge:
13; CHECK-NEXT:    ret i1 [[COND]]
14;
15entry:
16  br i1 %cond, label %if.true, label %if.false
17
18if.true:
19  br label %merge
20
21if.false:
22  br label %merge
23
24merge:
25  %ret = phi i1 [true, %if.true], [false, %if.false]
26  ret i1 %ret
27}
28
29define i1 @test_inverted_implication(i1 %cond) {
30; CHECK-LABEL: @test_inverted_implication(
31; CHECK-NEXT:  entry:
32; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
33; CHECK:       if.true:
34; CHECK-NEXT:    br label [[MERGE:%.*]]
35; CHECK:       if.false:
36; CHECK-NEXT:    br label [[MERGE]]
37; CHECK:       merge:
38; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND]], true
39; CHECK-NEXT:    ret i1 [[TMP0]]
40;
41entry:
42  br i1 %cond, label %if.true, label %if.false
43
44if.true:
45  br label %merge
46
47if.false:
48  br label %merge
49
50merge:
51  %ret = phi i1 [false, %if.true], [true, %if.false]
52  ret i1 %ret
53}
54
55define i1 @test_edge_dominance(i1 %cmp) {
56; CHECK-LABEL: @test_edge_dominance(
57; CHECK-NEXT:  entry:
58; CHECK-NEXT:    br i1 [[CMP:%.*]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
59; CHECK:       if.then:
60; CHECK-NEXT:    br label [[IF_END]]
61; CHECK:       if.end:
62; CHECK-NEXT:    ret i1 [[CMP]]
63;
64entry:
65  br i1 %cmp, label %if.end, label %if.then
66
67if.then:
68  br label %if.end
69
70if.end:
71  %phi = phi i1 [ true, %entry ], [ false, %if.then ]
72  ret i1 %phi
73}
74
75define i1 @test_direct_implication_complex_cfg(i1 %cond, i32 %cnt1) {
76; CHECK-LABEL: @test_direct_implication_complex_cfg(
77; CHECK-NEXT:  entry:
78; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
79; CHECK:       if.true:
80; CHECK-NEXT:    br label [[LOOP1:%.*]]
81; CHECK:       loop1:
82; CHECK-NEXT:    [[IV1:%.*]] = phi i32 [ 0, [[IF_TRUE]] ], [ [[IV1_NEXT:%.*]], [[LOOP1]] ]
83; CHECK-NEXT:    [[IV1_NEXT]] = add i32 [[IV1]], 1
84; CHECK-NEXT:    [[LOOP_COND_1:%.*]] = icmp slt i32 [[IV1_NEXT]], [[CNT1:%.*]]
85; CHECK-NEXT:    br i1 [[LOOP_COND_1]], label [[LOOP1]], label [[IF_TRUE_END:%.*]]
86; CHECK:       if.true.end:
87; CHECK-NEXT:    br label [[MERGE:%.*]]
88; CHECK:       if.false:
89; CHECK-NEXT:    br label [[MERGE]]
90; CHECK:       merge:
91; CHECK-NEXT:    ret i1 [[COND]]
92;
93entry:
94  br i1 %cond, label %if.true, label %if.false
95
96if.true:
97  br label %loop1
98
99loop1:
100  %iv1 = phi i32 [0, %if.true], [%iv1.next, %loop1]
101  %iv1.next = add i32 %iv1, 1
102  %loop.cond.1 = icmp slt i32 %iv1.next, %cnt1
103  br i1 %loop.cond.1, label %loop1, label %if.true.end
104
105if.true.end:
106  br label %merge
107
108if.false:
109  br label %merge
110
111merge:
112  %ret = phi i1 [true, %if.true.end], [false, %if.false]
113  ret i1 %ret
114}
115
116define i1 @test_inverted_implication_complex_cfg(i1 %cond, i32 %cnt1) {
117; CHECK-LABEL: @test_inverted_implication_complex_cfg(
118; CHECK-NEXT:  entry:
119; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
120; CHECK:       if.true:
121; CHECK-NEXT:    br label [[LOOP1:%.*]]
122; CHECK:       loop1:
123; CHECK-NEXT:    [[IV1:%.*]] = phi i32 [ 0, [[IF_TRUE]] ], [ [[IV1_NEXT:%.*]], [[LOOP1]] ]
124; CHECK-NEXT:    [[IV1_NEXT]] = add i32 [[IV1]], 1
125; CHECK-NEXT:    [[LOOP_COND_1:%.*]] = icmp slt i32 [[IV1_NEXT]], [[CNT1:%.*]]
126; CHECK-NEXT:    br i1 [[LOOP_COND_1]], label [[LOOP1]], label [[IF_TRUE_END:%.*]]
127; CHECK:       if.true.end:
128; CHECK-NEXT:    br label [[MERGE:%.*]]
129; CHECK:       if.false:
130; CHECK-NEXT:    br label [[MERGE]]
131; CHECK:       merge:
132; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND]], true
133; CHECK-NEXT:    ret i1 [[TMP0]]
134;
135entry:
136  br i1 %cond, label %if.true, label %if.false
137
138if.true:
139  br label %loop1
140
141loop1:
142  %iv1 = phi i32 [0, %if.true], [%iv1.next, %loop1]
143  %iv1.next = add i32 %iv1, 1
144  %loop.cond.1 = icmp slt i32 %iv1.next, %cnt1
145  br i1 %loop.cond.1, label %loop1, label %if.true.end
146
147if.true.end:
148  br label %merge
149
150if.false:
151  br label %merge
152
153merge:
154  %ret = phi i1 [false, %if.true.end], [true, %if.false]
155  ret i1 %ret
156}
157
158define i1 @test_multiple_predecessors(i1 %cond, i1 %cond2) {
159; CHECK-LABEL: @test_multiple_predecessors(
160; CHECK-NEXT:  entry:
161; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
162; CHECK:       if.true:
163; CHECK-NEXT:    br label [[MERGE:%.*]]
164; CHECK:       if.false:
165; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[IF2_TRUE:%.*]], label [[IF2_FALSE:%.*]]
166; CHECK:       if2.true:
167; CHECK-NEXT:    br label [[MERGE]]
168; CHECK:       if2.false:
169; CHECK-NEXT:    br label [[MERGE]]
170; CHECK:       merge:
171; CHECK-NEXT:    ret i1 [[COND]]
172;
173entry:
174  br i1 %cond, label %if.true, label %if.false
175
176if.true:
177  br label %merge
178
179if.false:
180  br i1 %cond2, label %if2.true, label %if2.false
181
182if2.true:
183  br label %merge
184
185if2.false:
186  br label %merge
187
188merge:
189  %ret = phi i1 [ true, %if.true ], [ false, %if2.true ], [ false, %if2.false ]
190  ret i1 %ret
191}
192
193define i1 @test_multiple_predecessors_wrong_value(i1 %cond, i1 %cond2) {
194; CHECK-LABEL: @test_multiple_predecessors_wrong_value(
195; CHECK-NEXT:  entry:
196; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
197; CHECK:       if.true:
198; CHECK-NEXT:    br label [[MERGE:%.*]]
199; CHECK:       if.false:
200; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[IF2_TRUE:%.*]], label [[IF2_FALSE:%.*]]
201; CHECK:       if2.true:
202; CHECK-NEXT:    br label [[MERGE]]
203; CHECK:       if2.false:
204; CHECK-NEXT:    br label [[MERGE]]
205; CHECK:       merge:
206; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[IF_TRUE]] ], [ true, [[IF2_TRUE]] ], [ false, [[IF2_FALSE]] ]
207; CHECK-NEXT:    ret i1 [[RET]]
208;
209entry:
210  br i1 %cond, label %if.true, label %if.false
211
212if.true:
213  br label %merge
214
215if.false:
216  br i1 %cond2, label %if2.true, label %if2.false
217
218if2.true:
219  br label %merge
220
221if2.false:
222  br label %merge
223
224merge:
225  %ret = phi i1 [ true, %if.true ], [ true, %if2.true ], [ false, %if2.false ]
226  ret i1 %ret
227}
228
229define i1 @test_multiple_predecessors_no_edge_domination(i1 %cond, i1 %cond2) {
230; CHECK-LABEL: @test_multiple_predecessors_no_edge_domination(
231; CHECK-NEXT:  entry:
232; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
233; CHECK:       if.true:
234; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[MERGE:%.*]], label [[IF_FALSE]]
235; CHECK:       if.false:
236; CHECK-NEXT:    br i1 [[COND2]], label [[IF2_TRUE:%.*]], label [[IF2_FALSE:%.*]]
237; CHECK:       if2.true:
238; CHECK-NEXT:    br label [[MERGE]]
239; CHECK:       if2.false:
240; CHECK-NEXT:    br label [[MERGE]]
241; CHECK:       merge:
242; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[IF_TRUE]] ], [ false, [[IF2_TRUE]] ], [ false, [[IF2_FALSE]] ]
243; CHECK-NEXT:    ret i1 [[RET]]
244;
245entry:
246  br i1 %cond, label %if.true, label %if.false
247
248if.true:
249  br i1 %cond2, label %merge, label %if.false
250
251if.false:
252  br i1 %cond2, label %if2.true, label %if2.false
253
254if2.true:
255  br label %merge
256
257if2.false:
258  br label %merge
259
260merge:
261  %ret = phi i1 [ true, %if.true ], [ false, %if2.true ], [ false, %if2.false ]
262  ret i1 %ret
263}
264
265define i8 @test_switch(i8 %cond) {
266; CHECK-LABEL: @test_switch(
267; CHECK-NEXT:  entry:
268; CHECK-NEXT:    switch i8 [[COND:%.*]], label [[DEFAULT:%.*]] [
269; CHECK-NEXT:    i8 1, label [[SW_1:%.*]]
270; CHECK-NEXT:    i8 7, label [[SW_7:%.*]]
271; CHECK-NEXT:    i8 19, label [[SW_19:%.*]]
272; CHECK-NEXT:    ]
273; CHECK:       sw.1:
274; CHECK-NEXT:    br label [[MERGE:%.*]]
275; CHECK:       sw.7:
276; CHECK-NEXT:    br label [[MERGE]]
277; CHECK:       sw.19:
278; CHECK-NEXT:    br label [[MERGE]]
279; CHECK:       default:
280; CHECK-NEXT:    ret i8 42
281; CHECK:       merge:
282; CHECK-NEXT:    [[RET:%.*]] = phi i8 [ 1, [[SW_1]] ], [ 7, [[SW_7]] ], [ 19, [[SW_19]] ]
283; CHECK-NEXT:    ret i8 [[RET]]
284;
285entry:
286  switch i8 %cond, label %default [
287  i8 1, label %sw.1
288  i8 7, label %sw.7
289  i8 19, label %sw.19
290  ]
291
292sw.1:
293  br label %merge
294
295sw.7:
296  br label %merge
297
298sw.19:
299  br label %merge
300
301default:
302  ret i8 42
303
304merge:
305  %ret = phi i8 [ 1, %sw.1 ], [ 7, %sw.7 ], [ 19, %sw.19 ]
306  ret i8 %ret
307}
308
309define i8 @test_switch_direct_edge(i8 %cond) {
310; CHECK-LABEL: @test_switch_direct_edge(
311; CHECK-NEXT:  entry:
312; CHECK-NEXT:    switch i8 [[COND:%.*]], label [[DEFAULT:%.*]] [
313; CHECK-NEXT:    i8 1, label [[SW_1:%.*]]
314; CHECK-NEXT:    i8 7, label [[SW_7:%.*]]
315; CHECK-NEXT:    i8 19, label [[MERGE:%.*]]
316; CHECK-NEXT:    ]
317; CHECK:       sw.1:
318; CHECK-NEXT:    br label [[MERGE]]
319; CHECK:       sw.7:
320; CHECK-NEXT:    br label [[MERGE]]
321; CHECK:       default:
322; CHECK-NEXT:    ret i8 42
323; CHECK:       merge:
324; CHECK-NEXT:    [[RET:%.*]] = phi i8 [ 1, [[SW_1]] ], [ 7, [[SW_7]] ], [ 19, [[ENTRY:%.*]] ]
325; CHECK-NEXT:    ret i8 [[RET]]
326;
327entry:
328  switch i8 %cond, label %default [
329  i8 1, label %sw.1
330  i8 7, label %sw.7
331  i8 19, label %merge
332  ]
333
334sw.1:
335  br label %merge
336
337sw.7:
338  br label %merge
339
340default:
341  ret i8 42
342
343merge:
344  %ret = phi i8 [ 1, %sw.1 ], [ 7, %sw.7 ], [ 19, %entry ]
345  ret i8 %ret
346}
347
348define i8 @test_switch_duplicate_direct_edge(i8 %cond) {
349; CHECK-LABEL: @test_switch_duplicate_direct_edge(
350; CHECK-NEXT:  entry:
351; CHECK-NEXT:    switch i8 [[COND:%.*]], label [[DEFAULT:%.*]] [
352; CHECK-NEXT:    i8 1, label [[SW_1:%.*]]
353; CHECK-NEXT:    i8 7, label [[MERGE:%.*]]
354; CHECK-NEXT:    i8 19, label [[MERGE]]
355; CHECK-NEXT:    ]
356; CHECK:       sw.1:
357; CHECK-NEXT:    br label [[MERGE]]
358; CHECK:       default:
359; CHECK-NEXT:    ret i8 42
360; CHECK:       merge:
361; CHECK-NEXT:    [[RET:%.*]] = phi i8 [ 1, [[SW_1]] ], [ 7, [[ENTRY:%.*]] ], [ 7, [[ENTRY]] ]
362; CHECK-NEXT:    ret i8 [[RET]]
363;
364entry:
365  switch i8 %cond, label %default [
366  i8 1, label %sw.1
367  i8 7, label %merge
368  i8 19, label %merge
369  ]
370
371sw.1:
372  br label %merge
373
374default:
375  ret i8 42
376
377merge:
378  %ret = phi i8 [ 1, %sw.1 ], [ 7, %entry ], [ 7, %entry ]
379  ret i8 %ret
380}
381
382define i8 @test_switch_subset(i8 %cond) {
383; CHECK-LABEL: @test_switch_subset(
384; CHECK-NEXT:  entry:
385; CHECK-NEXT:    switch i8 [[COND:%.*]], label [[DEFAULT:%.*]] [
386; CHECK-NEXT:    i8 1, label [[SW_1:%.*]]
387; CHECK-NEXT:    i8 7, label [[SW_7:%.*]]
388; CHECK-NEXT:    i8 19, label [[SW_19:%.*]]
389; CHECK-NEXT:    ]
390; CHECK:       sw.1:
391; CHECK-NEXT:    br label [[MERGE:%.*]]
392; CHECK:       sw.7:
393; CHECK-NEXT:    br label [[MERGE]]
394; CHECK:       sw.19:
395; CHECK-NEXT:    ret i8 24
396; CHECK:       default:
397; CHECK-NEXT:    ret i8 42
398; CHECK:       merge:
399; CHECK-NEXT:    [[RET:%.*]] = phi i8 [ 1, [[SW_1]] ], [ 7, [[SW_7]] ]
400; CHECK-NEXT:    ret i8 [[RET]]
401;
402entry:
403  switch i8 %cond, label %default [
404  i8 1, label %sw.1
405  i8 7, label %sw.7
406  i8 19, label %sw.19
407  ]
408
409sw.1:
410  br label %merge
411
412sw.7:
413  br label %merge
414
415sw.19:
416  ret i8 24
417
418default:
419  ret i8 42
420
421merge:
422  %ret = phi i8 [ 1, %sw.1 ], [ 7, %sw.7 ]
423  ret i8 %ret
424}
425
426define i8 @test_switch_wrong_value(i8 %cond) {
427; CHECK-LABEL: @test_switch_wrong_value(
428; CHECK-NEXT:  entry:
429; CHECK-NEXT:    switch i8 [[COND:%.*]], label [[DEFAULT:%.*]] [
430; CHECK-NEXT:    i8 1, label [[SW_1:%.*]]
431; CHECK-NEXT:    i8 7, label [[SW_7:%.*]]
432; CHECK-NEXT:    i8 19, label [[SW_19:%.*]]
433; CHECK-NEXT:    ]
434; CHECK:       sw.1:
435; CHECK-NEXT:    br label [[MERGE:%.*]]
436; CHECK:       sw.7:
437; CHECK-NEXT:    br label [[MERGE]]
438; CHECK:       sw.19:
439; CHECK-NEXT:    br label [[MERGE]]
440; CHECK:       default:
441; CHECK-NEXT:    ret i8 42
442; CHECK:       merge:
443; CHECK-NEXT:    [[RET:%.*]] = phi i8 [ 1, [[SW_1]] ], [ 7, [[SW_7]] ], [ 10, [[SW_19]] ]
444; CHECK-NEXT:    ret i8 [[RET]]
445;
446entry:
447  switch i8 %cond, label %default [
448  i8 1, label %sw.1
449  i8 7, label %sw.7
450  i8 19, label %sw.19
451  ]
452
453sw.1:
454  br label %merge
455
456sw.7:
457  br label %merge
458
459sw.19:
460  br label %merge
461
462default:
463  ret i8 42
464
465merge:
466  %ret = phi i8 [ 1, %sw.1 ], [ 7, %sw.7 ], [ 10, %sw.19 ]
467  ret i8 %ret
468}
469
470define i8 @test_switch_inverted(i8 %cond) {
471; CHECK-LABEL: @test_switch_inverted(
472; CHECK-NEXT:  entry:
473; CHECK-NEXT:    switch i8 [[COND:%.*]], label [[DEFAULT:%.*]] [
474; CHECK-NEXT:    i8 0, label [[SW_0:%.*]]
475; CHECK-NEXT:    i8 1, label [[SW_1:%.*]]
476; CHECK-NEXT:    i8 2, label [[SW_2:%.*]]
477; CHECK-NEXT:    ]
478; CHECK:       sw.0:
479; CHECK-NEXT:    br label [[MERGE:%.*]]
480; CHECK:       sw.1:
481; CHECK-NEXT:    br label [[MERGE]]
482; CHECK:       sw.2:
483; CHECK-NEXT:    br label [[MERGE]]
484; CHECK:       default:
485; CHECK-NEXT:    ret i8 42
486; CHECK:       merge:
487; CHECK-NEXT:    [[RET:%.*]] = phi i8 [ -1, [[SW_0]] ], [ -2, [[SW_1]] ], [ -3, [[SW_2]] ]
488; CHECK-NEXT:    ret i8 [[RET]]
489;
490entry:
491  switch i8 %cond, label %default [
492  i8 0, label %sw.0
493  i8 1, label %sw.1
494  i8 2, label %sw.2
495  ]
496
497sw.0:
498  br label %merge
499
500sw.1:
501  br label %merge
502
503sw.2:
504  br label %merge
505
506default:
507  ret i8 42
508
509merge:
510  %ret = phi i8 [ -1, %sw.0 ], [ -2, %sw.1 ], [ -3, %sw.2 ]
511  ret i8 %ret
512}
513
514define i8 @test_switch_duplicate_edge(i8 %cond) {
515; CHECK-LABEL: @test_switch_duplicate_edge(
516; CHECK-NEXT:  entry:
517; CHECK-NEXT:    switch i8 [[COND:%.*]], label [[DEFAULT:%.*]] [
518; CHECK-NEXT:    i8 1, label [[SW_1:%.*]]
519; CHECK-NEXT:    i8 7, label [[SW_7:%.*]]
520; CHECK-NEXT:    i8 19, label [[SW_7]]
521; CHECK-NEXT:    ]
522; CHECK:       sw.1:
523; CHECK-NEXT:    br label [[MERGE:%.*]]
524; CHECK:       sw.7:
525; CHECK-NEXT:    br label [[MERGE]]
526; CHECK:       default:
527; CHECK-NEXT:    ret i8 42
528; CHECK:       merge:
529; CHECK-NEXT:    [[RET:%.*]] = phi i8 [ 1, [[SW_1]] ], [ 7, [[SW_7]] ]
530; CHECK-NEXT:    ret i8 [[RET]]
531;
532entry:
533  switch i8 %cond, label %default [
534  i8 1, label %sw.1
535  i8 7, label %sw.7
536  i8 19, label %sw.7
537  ]
538
539sw.1:
540  br label %merge
541
542sw.7:
543  br label %merge
544
545default:
546  ret i8 42
547
548merge:
549  %ret = phi i8 [ 1, %sw.1 ], [ 7, %sw.7 ]
550  ret i8 %ret
551}
552
553define i8 @test_switch_default_edge(i8 %cond) {
554; CHECK-LABEL: @test_switch_default_edge(
555; CHECK-NEXT:  entry:
556; CHECK-NEXT:    switch i8 [[COND:%.*]], label [[MERGE:%.*]] [
557; CHECK-NEXT:    i8 1, label [[SW_1:%.*]]
558; CHECK-NEXT:    i8 7, label [[SW_7:%.*]]
559; CHECK-NEXT:    i8 19, label [[SW_19:%.*]]
560; CHECK-NEXT:    ]
561; CHECK:       sw.1:
562; CHECK-NEXT:    br label [[MERGE]]
563; CHECK:       sw.7:
564; CHECK-NEXT:    br label [[MERGE]]
565; CHECK:       sw.19:
566; CHECK-NEXT:    br label [[MERGE]]
567; CHECK:       merge:
568; CHECK-NEXT:    [[RET:%.*]] = phi i8 [ 1, [[SW_1]] ], [ 7, [[SW_7]] ], [ 19, [[SW_19]] ], [ 42, [[ENTRY:%.*]] ]
569; CHECK-NEXT:    ret i8 [[RET]]
570;
571entry:
572  switch i8 %cond, label %merge [
573  i8 1, label %sw.1
574  i8 7, label %sw.7
575  i8 19, label %sw.19
576  ]
577
578sw.1:
579  br label %merge
580
581sw.7:
582  br label %merge
583
584sw.19:
585  br label %merge
586
587merge:
588  %ret = phi i8 [ 1, %sw.1 ], [ 7, %sw.7 ], [ 19, %sw.19 ], [ 42, %entry ]
589  ret i8 %ret
590}
591