1; RUN: opt < %s -simplifycfg -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
2
3target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
4target triple = "x86_64-unknown-linux-gnu"
5
6; The table for @f
7; CHECK: @switch.table = private unnamed_addr constant [7 x i32] [i32 55, i32 123, i32 0, i32 -1, i32 27, i32 62, i32 1]
8
9; The float table for @h
10; CHECK: @switch.table1 = private unnamed_addr constant [4 x float] [float 0x40091EB860000000, float 0x3FF3BE76C0000000, float 0x4012449BA0000000, float 0x4001AE1480000000]
11
12; The table for @foostring
13; CHECK: @switch.table2 = private unnamed_addr constant [4 x i8*] [i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str1, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str2, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str3, i64 0, i64 0)]
14
15; The table for @earlyreturncrash
16; CHECK: @switch.table3 = private unnamed_addr constant [4 x i32] [i32 42, i32 9, i32 88, i32 5]
17
18; The table for @large.
19; CHECK: @switch.table4 = private unnamed_addr constant [199 x i32] [i32 1, i32 4, i32 9,
20
21; The table for @cprop
22; CHECK: @switch.table5 = private unnamed_addr constant [7 x i32] [i32 5, i32 42, i32 126, i32 -452, i32 128, i32 6, i32 7]
23
24; The table for @unreachable_case
25; CHECK: @switch.table6 = private unnamed_addr constant [9 x i32] [i32 0, i32 0, i32 0, i32 2, i32 -1, i32 1, i32 1, i32 1, i32 1]
26
27; A simple int-to-int selection switch.
28; It is dense enough to be replaced by table lookup.
29; The result is directly by a ret from an otherwise empty bb,
30; so we return early, directly from the lookup bb.
31
32define i32 @f(i32 %c) {
33entry:
34  switch i32 %c, label %sw.default [
35    i32 42, label %return
36    i32 43, label %sw.bb1
37    i32 44, label %sw.bb2
38    i32 45, label %sw.bb3
39    i32 46, label %sw.bb4
40    i32 47, label %sw.bb5
41    i32 48, label %sw.bb6
42  ]
43
44sw.bb1: br label %return
45sw.bb2: br label %return
46sw.bb3: br label %return
47sw.bb4: br label %return
48sw.bb5: br label %return
49sw.bb6: br label %return
50sw.default: br label %return
51return:
52  %retval.0 = phi i32 [ 15, %sw.default ], [ 1, %sw.bb6 ], [ 62, %sw.bb5 ], [ 27, %sw.bb4 ], [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
53  ret i32 %retval.0
54
55; CHECK-LABEL: @f(
56; CHECK: entry:
57; CHECK-NEXT: %switch.tableidx = sub i32 %c, 42
58; CHECK-NEXT: %0 = icmp ult i32 %switch.tableidx, 7
59; CHECK-NEXT: br i1 %0, label %switch.lookup, label %return
60; CHECK: switch.lookup:
61; CHECK-NEXT: %switch.gep = getelementptr inbounds [7 x i32], [7 x i32]* @switch.table, i32 0, i32 %switch.tableidx
62; CHECK-NEXT: %switch.load = load i32, i32* %switch.gep
63; CHECK-NEXT: ret i32 %switch.load
64; CHECK: return:
65; CHECK-NEXT: ret i32 15
66}
67
68; A switch used to initialize two variables, an i8 and a float.
69
70declare void @dummy(i8 signext, float)
71define void @h(i32 %x) {
72entry:
73  switch i32 %x, label %sw.default [
74    i32 0, label %sw.epilog
75    i32 1, label %sw.bb1
76    i32 2, label %sw.bb2
77    i32 3, label %sw.bb3
78  ]
79
80sw.bb1: br label %sw.epilog
81sw.bb2: br label %sw.epilog
82sw.bb3: br label %sw.epilog
83sw.default: br label %sw.epilog
84
85sw.epilog:
86  %a.0 = phi i8 [ 7, %sw.default ], [ 5, %sw.bb3 ], [ 88, %sw.bb2 ], [ 9, %sw.bb1 ], [ 42, %entry ]
87  %b.0 = phi float [ 0x4023FAE140000000, %sw.default ], [ 0x4001AE1480000000, %sw.bb3 ], [ 0x4012449BA0000000, %sw.bb2 ], [ 0x3FF3BE76C0000000, %sw.bb1 ], [ 0x40091EB860000000, %entry ]
88  call void @dummy(i8 signext %a.0, float %b.0)
89  ret void
90
91; CHECK-LABEL: @h(
92; CHECK: entry:
93; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0
94; CHECK-NEXT: %0 = icmp ult i32 %switch.tableidx, 4
95; CHECK-NEXT: br i1 %0, label %switch.lookup, label %sw.epilog
96; CHECK: switch.lookup:
97; CHECK-NEXT: %switch.shiftamt = mul i32 %switch.tableidx, 8
98; CHECK-NEXT: %switch.downshift = lshr i32 89655594, %switch.shiftamt
99; CHECK-NEXT: %switch.masked = trunc i32 %switch.downshift to i8
100; CHECK-NEXT: %switch.gep = getelementptr inbounds [4 x float], [4 x float]* @switch.table1, i32 0, i32 %switch.tableidx
101; CHECK-NEXT: %switch.load = load float, float* %switch.gep
102; CHECK-NEXT: br label %sw.epilog
103; CHECK: sw.epilog:
104; CHECK-NEXT: %a.0 = phi i8 [ %switch.masked, %switch.lookup ], [ 7, %entry ]
105; CHECK-NEXT: %b.0 = phi float [ %switch.load, %switch.lookup ], [ 0x4023FAE140000000, %entry ]
106; CHECK-NEXT: call void @dummy(i8 signext %a.0, float %b.0)
107; CHECK-NEXT: ret void
108}
109
110
111; Switch used to return a string.
112
113@.str = private unnamed_addr constant [4 x i8] c"foo\00", align 1
114@.str1 = private unnamed_addr constant [4 x i8] c"bar\00", align 1
115@.str2 = private unnamed_addr constant [4 x i8] c"baz\00", align 1
116@.str3 = private unnamed_addr constant [4 x i8] c"qux\00", align 1
117@.str4 = private unnamed_addr constant [6 x i8] c"error\00", align 1
118
119define i8* @foostring(i32 %x)  {
120entry:
121  switch i32 %x, label %sw.default [
122    i32 0, label %return
123    i32 1, label %sw.bb1
124    i32 2, label %sw.bb2
125    i32 3, label %sw.bb3
126  ]
127
128sw.bb1: br label %return
129sw.bb2: br label %return
130sw.bb3: br label %return
131sw.default: br label %return
132
133return:
134  %retval.0 = phi i8* [ getelementptr inbounds ([6 x i8], [6 x i8]* @.str4, i64 0, i64 0), %sw.default ],
135                      [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str3, i64 0, i64 0), %sw.bb3 ],
136                      [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str2, i64 0, i64 0), %sw.bb2 ],
137                      [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str1, i64 0, i64 0), %sw.bb1 ],
138                      [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), %entry ]
139  ret i8* %retval.0
140
141; CHECK-LABEL: @foostring(
142; CHECK: entry:
143; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0
144; CHECK-NEXT: %0 = icmp ult i32 %switch.tableidx, 4
145; CHECK-NEXT: br i1 %0, label %switch.lookup, label %return
146; CHECK: switch.lookup:
147; CHECK-NEXT: %switch.gep = getelementptr inbounds [4 x i8*], [4 x i8*]* @switch.table2, i32 0, i32 %switch.tableidx
148; CHECK-NEXT: %switch.load = load i8*, i8** %switch.gep
149; CHECK-NEXT: ret i8* %switch.load
150}
151
152; Switch used to initialize two values. The first value is returned, the second
153; value is not used. This used to make the transformation generate illegal code.
154
155define i32 @earlyreturncrash(i32 %x)  {
156entry:
157  switch i32 %x, label %sw.default [
158    i32 0, label %sw.epilog
159    i32 1, label %sw.bb1
160    i32 2, label %sw.bb2
161    i32 3, label %sw.bb3
162  ]
163
164sw.bb1: br label %sw.epilog
165sw.bb2: br label %sw.epilog
166sw.bb3: br label %sw.epilog
167sw.default: br label %sw.epilog
168
169sw.epilog:
170  %a.0 = phi i32 [ 7, %sw.default ], [ 5, %sw.bb3 ], [ 88, %sw.bb2 ], [ 9, %sw.bb1 ], [ 42, %entry ]
171  %b.0 = phi i32 [ 10, %sw.default ], [ 5, %sw.bb3 ], [ 1, %sw.bb2 ], [ 4, %sw.bb1 ], [ 3, %entry ]
172  ret i32 %a.0
173
174; CHECK-LABEL: @earlyreturncrash(
175; CHECK: switch.lookup:
176; CHECK-NEXT: %switch.gep = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table3, i32 0, i32 %switch.tableidx
177; CHECK-NEXT: %switch.load = load i32, i32* %switch.gep
178; CHECK-NEXT: ret i32 %switch.load
179; CHECK: sw.epilog:
180; CHECK-NEXT: ret i32 7
181}
182
183
184; Example 7 from http://blog.regehr.org/archives/320
185; It is not dense enough for a regular table, but the results
186; can be packed into a bitmap.
187
188define i32 @crud(i8 zeroext %c)  {
189entry:
190  %cmp = icmp ult i8 %c, 33
191  br i1 %cmp, label %lor.end, label %switch.early.test
192
193switch.early.test:
194  switch i8 %c, label %lor.rhs [
195    i8 92, label %lor.end
196    i8 62, label %lor.end
197    i8 60, label %lor.end
198    i8 59, label %lor.end
199    i8 58, label %lor.end
200    i8 46, label %lor.end
201    i8 44, label %lor.end
202    i8 34, label %lor.end
203    i8 39, label %switch.edge
204  ]
205
206switch.edge: br label %lor.end
207lor.rhs: br label %lor.end
208
209lor.end:
210  %0 = phi i1 [ true, %switch.early.test ],
211              [ false, %lor.rhs ],
212              [ true, %entry ],
213              [ true, %switch.early.test ],
214              [ true, %switch.early.test ],
215              [ true, %switch.early.test ],
216              [ true, %switch.early.test ],
217              [ true, %switch.early.test ],
218              [ true, %switch.early.test ],
219              [ true, %switch.early.test ],
220              [ true, %switch.edge ]
221  %lor.ext = zext i1 %0 to i32
222  ret i32 %lor.ext
223
224; CHECK-LABEL: @crud(
225; CHECK: entry:
226; CHECK-NEXT: %cmp = icmp ult i8 %c, 33
227; CHECK-NEXT: br i1 %cmp, label %lor.end, label %switch.early.test
228; CHECK: switch.early.test:
229; CHECK-NEXT: %switch.tableidx = sub i8 %c, 34
230; CHECK-NEXT: %0 = icmp ult i8 %switch.tableidx, 59
231; CHECK-NEXT: br i1 %0, label %switch.lookup, label %lor.end
232; CHECK: switch.lookup:
233; CHECK-NEXT: %switch.cast = zext i8 %switch.tableidx to i59
234; CHECK-NEXT: %switch.shiftamt = mul i59 %switch.cast, 1
235; CHECK-NEXT: %switch.downshift = lshr i59 -288230375765830623, %switch.shiftamt
236; CHECK-NEXT: %switch.masked = trunc i59 %switch.downshift to i1
237; CHECK-NEXT: br label %lor.end
238; CHECK: lor.end:
239; CHECK-NEXT: %1 = phi i1 [ true, %entry ], [ %switch.masked, %switch.lookup ], [ false, %switch.early.test ]
240; CHECK-NEXT: %lor.ext = zext i1 %1 to i32
241; CHECK-NEXT: ret i32 %lor.ext
242}
243
244; PR13946
245define i32 @overflow(i32 %type) {
246entry:
247  switch i32 %type, label %sw.default [
248    i32 -2147483648, label %sw.bb
249    i32 0, label %sw.bb
250    i32 1, label %sw.bb1
251    i32 2, label %sw.bb2
252    i32 -2147483645, label %sw.bb3
253    i32 3, label %sw.bb3
254  ]
255
256sw.bb: br label %if.end
257sw.bb1: br label %if.end
258sw.bb2: br label %if.end
259sw.bb3: br label %if.end
260sw.default: br label %if.end
261if.else: br label %if.end
262
263if.end:
264  %dirent_type.0 = phi i32 [ 3, %sw.default ], [ 6, %sw.bb3 ], [ 5, %sw.bb2 ], [ 0, %sw.bb1 ], [ 3, %sw.bb ], [ 0, %if.else ]
265  ret i32 %dirent_type.0
266; CHECK-LABEL: define i32 @overflow(
267; CHECK: switch
268; CHECK: phi
269}
270
271; PR13985
272define i1 @undef(i32 %tmp) {
273bb:
274  switch i32 %tmp, label %bb3 [
275    i32 0, label %bb1
276    i32 1, label %bb1
277    i32 7, label %bb2
278    i32 8, label %bb2
279  ]
280
281bb1: br label %bb3
282bb2: br label %bb3
283
284bb3:
285  %tmp4 = phi i1 [ undef, %bb ], [ false, %bb2 ], [ true, %bb1 ]
286  ret i1 %tmp4
287; CHECK-LABEL: define i1 @undef(
288; CHECK: %switch.cast = trunc i32 %switch.tableidx to i9
289; CHECK: %switch.downshift = lshr i9 3, %switch.shiftamt
290}
291
292; Also handle large switches that would be rejected by
293; isValueEqualityComparison()
294; CHECK: large
295; CHECK-NOT: switch i32
296define i32 @large(i32 %x) {
297entry:
298  %cmp = icmp slt i32 %x, 0
299  br i1 %cmp, label %if.then, label %if.end
300
301if.then:
302  %mul = mul i32 %x, -10
303  br label %if.end
304
305if.end:
306  %x.addr.0 = phi i32 [ %mul, %if.then ], [ %x, %entry ]
307  switch i32 %x.addr.0, label %return [
308    i32 199, label %sw.bb203
309    i32 1, label %sw.bb1
310    i32 2, label %sw.bb2
311    i32 3, label %sw.bb3
312    i32 4, label %sw.bb4
313    i32 5, label %sw.bb5
314    i32 6, label %sw.bb6
315    i32 7, label %sw.bb7
316    i32 8, label %sw.bb8
317    i32 9, label %sw.bb9
318    i32 10, label %sw.bb10
319    i32 11, label %sw.bb11
320    i32 12, label %sw.bb12
321    i32 13, label %sw.bb13
322    i32 14, label %sw.bb14
323    i32 15, label %sw.bb15
324    i32 16, label %sw.bb16
325    i32 17, label %sw.bb17
326    i32 18, label %sw.bb18
327    i32 19, label %sw.bb19
328    i32 20, label %sw.bb20
329    i32 21, label %sw.bb21
330    i32 22, label %sw.bb22
331    i32 23, label %sw.bb23
332    i32 24, label %sw.bb24
333    i32 25, label %sw.bb25
334    i32 26, label %sw.bb26
335    i32 27, label %sw.bb27
336    i32 28, label %sw.bb28
337    i32 29, label %sw.bb29
338    i32 30, label %sw.bb30
339    i32 31, label %sw.bb31
340    i32 32, label %sw.bb32
341    i32 33, label %sw.bb33
342    i32 34, label %sw.bb34
343    i32 35, label %sw.bb35
344    i32 36, label %sw.bb37
345    i32 37, label %sw.bb38
346    i32 38, label %sw.bb39
347    i32 39, label %sw.bb40
348    i32 40, label %sw.bb41
349    i32 41, label %sw.bb42
350    i32 42, label %sw.bb43
351    i32 43, label %sw.bb44
352    i32 44, label %sw.bb45
353    i32 45, label %sw.bb47
354    i32 46, label %sw.bb48
355    i32 47, label %sw.bb49
356    i32 48, label %sw.bb50
357    i32 49, label %sw.bb51
358    i32 50, label %sw.bb52
359    i32 51, label %sw.bb53
360    i32 52, label %sw.bb54
361    i32 53, label %sw.bb55
362    i32 54, label %sw.bb56
363    i32 55, label %sw.bb58
364    i32 56, label %sw.bb59
365    i32 57, label %sw.bb60
366    i32 58, label %sw.bb61
367    i32 59, label %sw.bb62
368    i32 60, label %sw.bb63
369    i32 61, label %sw.bb64
370    i32 62, label %sw.bb65
371    i32 63, label %sw.bb66
372    i32 64, label %sw.bb67
373    i32 65, label %sw.bb68
374    i32 66, label %sw.bb69
375    i32 67, label %sw.bb70
376    i32 68, label %sw.bb71
377    i32 69, label %sw.bb72
378    i32 70, label %sw.bb73
379    i32 71, label %sw.bb74
380    i32 72, label %sw.bb76
381    i32 73, label %sw.bb77
382    i32 74, label %sw.bb78
383    i32 75, label %sw.bb79
384    i32 76, label %sw.bb80
385    i32 77, label %sw.bb81
386    i32 78, label %sw.bb82
387    i32 79, label %sw.bb83
388    i32 80, label %sw.bb84
389    i32 81, label %sw.bb85
390    i32 82, label %sw.bb86
391    i32 83, label %sw.bb87
392    i32 84, label %sw.bb88
393    i32 85, label %sw.bb89
394    i32 86, label %sw.bb90
395    i32 87, label %sw.bb91
396    i32 88, label %sw.bb92
397    i32 89, label %sw.bb93
398    i32 90, label %sw.bb94
399    i32 91, label %sw.bb95
400    i32 92, label %sw.bb96
401    i32 93, label %sw.bb97
402    i32 94, label %sw.bb98
403    i32 95, label %sw.bb99
404    i32 96, label %sw.bb100
405    i32 97, label %sw.bb101
406    i32 98, label %sw.bb102
407    i32 99, label %sw.bb103
408    i32 100, label %sw.bb104
409    i32 101, label %sw.bb105
410    i32 102, label %sw.bb106
411    i32 103, label %sw.bb107
412    i32 104, label %sw.bb108
413    i32 105, label %sw.bb109
414    i32 106, label %sw.bb110
415    i32 107, label %sw.bb111
416    i32 108, label %sw.bb112
417    i32 109, label %sw.bb113
418    i32 110, label %sw.bb114
419    i32 111, label %sw.bb115
420    i32 112, label %sw.bb116
421    i32 113, label %sw.bb117
422    i32 114, label %sw.bb118
423    i32 115, label %sw.bb119
424    i32 116, label %sw.bb120
425    i32 117, label %sw.bb121
426    i32 118, label %sw.bb122
427    i32 119, label %sw.bb123
428    i32 120, label %sw.bb124
429    i32 121, label %sw.bb125
430    i32 122, label %sw.bb126
431    i32 123, label %sw.bb127
432    i32 124, label %sw.bb128
433    i32 125, label %sw.bb129
434    i32 126, label %sw.bb130
435    i32 127, label %sw.bb131
436    i32 128, label %sw.bb132
437    i32 129, label %sw.bb133
438    i32 130, label %sw.bb134
439    i32 131, label %sw.bb135
440    i32 132, label %sw.bb136
441    i32 133, label %sw.bb137
442    i32 134, label %sw.bb138
443    i32 135, label %sw.bb139
444    i32 136, label %sw.bb140
445    i32 137, label %sw.bb141
446    i32 138, label %sw.bb142
447    i32 139, label %sw.bb143
448    i32 140, label %sw.bb144
449    i32 141, label %sw.bb145
450    i32 142, label %sw.bb146
451    i32 143, label %sw.bb147
452    i32 144, label %sw.bb148
453    i32 145, label %sw.bb149
454    i32 146, label %sw.bb150
455    i32 147, label %sw.bb151
456    i32 148, label %sw.bb152
457    i32 149, label %sw.bb153
458    i32 150, label %sw.bb154
459    i32 151, label %sw.bb155
460    i32 152, label %sw.bb156
461    i32 153, label %sw.bb157
462    i32 154, label %sw.bb158
463    i32 155, label %sw.bb159
464    i32 156, label %sw.bb160
465    i32 157, label %sw.bb161
466    i32 158, label %sw.bb162
467    i32 159, label %sw.bb163
468    i32 160, label %sw.bb164
469    i32 161, label %sw.bb165
470    i32 162, label %sw.bb166
471    i32 163, label %sw.bb167
472    i32 164, label %sw.bb168
473    i32 165, label %sw.bb169
474    i32 166, label %sw.bb170
475    i32 167, label %sw.bb171
476    i32 168, label %sw.bb172
477    i32 169, label %sw.bb173
478    i32 170, label %sw.bb174
479    i32 171, label %sw.bb175
480    i32 172, label %sw.bb176
481    i32 173, label %sw.bb177
482    i32 174, label %sw.bb178
483    i32 175, label %sw.bb179
484    i32 176, label %sw.bb180
485    i32 177, label %sw.bb181
486    i32 178, label %sw.bb182
487    i32 179, label %sw.bb183
488    i32 180, label %sw.bb184
489    i32 181, label %sw.bb185
490    i32 182, label %sw.bb186
491    i32 183, label %sw.bb187
492    i32 184, label %sw.bb188
493    i32 185, label %sw.bb189
494    i32 186, label %sw.bb190
495    i32 187, label %sw.bb191
496    i32 188, label %sw.bb192
497    i32 189, label %sw.bb193
498    i32 190, label %sw.bb194
499    i32 191, label %sw.bb195
500    i32 192, label %sw.bb196
501    i32 193, label %sw.bb197
502    i32 194, label %sw.bb198
503    i32 195, label %sw.bb199
504    i32 196, label %sw.bb200
505    i32 197, label %sw.bb201
506    i32 198, label %sw.bb202
507  ]
508
509sw.bb1: br label %return
510sw.bb2: br label %return
511sw.bb3: br label %return
512sw.bb4: br label %return
513sw.bb5: br label %return
514sw.bb6: br label %return
515sw.bb7: br label %return
516sw.bb8: br label %return
517sw.bb9: br label %return
518sw.bb10: br label %return
519sw.bb11: br label %return
520sw.bb12: br label %return
521sw.bb13: br label %return
522sw.bb14: br label %return
523sw.bb15: br label %return
524sw.bb16: br label %return
525sw.bb17: br label %return
526sw.bb18: br label %return
527sw.bb19: br label %return
528sw.bb20: br label %return
529sw.bb21: br label %return
530sw.bb22: br label %return
531sw.bb23: br label %return
532sw.bb24: br label %return
533sw.bb25: br label %return
534sw.bb26: br label %return
535sw.bb27: br label %return
536sw.bb28: br label %return
537sw.bb29: br label %return
538sw.bb30: br label %return
539sw.bb31: br label %return
540sw.bb32: br label %return
541sw.bb33: br label %return
542sw.bb34: br label %return
543sw.bb35: br label %return
544sw.bb37: br label %return
545sw.bb38: br label %return
546sw.bb39: br label %return
547sw.bb40: br label %return
548sw.bb41: br label %return
549sw.bb42: br label %return
550sw.bb43: br label %return
551sw.bb44: br label %return
552sw.bb45: br label %return
553sw.bb47: br label %return
554sw.bb48: br label %return
555sw.bb49: br label %return
556sw.bb50: br label %return
557sw.bb51: br label %return
558sw.bb52: br label %return
559sw.bb53: br label %return
560sw.bb54: br label %return
561sw.bb55: br label %return
562sw.bb56: br label %return
563sw.bb58: br label %return
564sw.bb59: br label %return
565sw.bb60: br label %return
566sw.bb61: br label %return
567sw.bb62: br label %return
568sw.bb63: br label %return
569sw.bb64: br label %return
570sw.bb65: br label %return
571sw.bb66: br label %return
572sw.bb67: br label %return
573sw.bb68: br label %return
574sw.bb69: br label %return
575sw.bb70: br label %return
576sw.bb71: br label %return
577sw.bb72: br label %return
578sw.bb73: br label %return
579sw.bb74: br label %return
580sw.bb76: br label %return
581sw.bb77: br label %return
582sw.bb78: br label %return
583sw.bb79: br label %return
584sw.bb80: br label %return
585sw.bb81: br label %return
586sw.bb82: br label %return
587sw.bb83: br label %return
588sw.bb84: br label %return
589sw.bb85: br label %return
590sw.bb86: br label %return
591sw.bb87: br label %return
592sw.bb88: br label %return
593sw.bb89: br label %return
594sw.bb90: br label %return
595sw.bb91: br label %return
596sw.bb92: br label %return
597sw.bb93: br label %return
598sw.bb94: br label %return
599sw.bb95: br label %return
600sw.bb96: br label %return
601sw.bb97: br label %return
602sw.bb98: br label %return
603sw.bb99: br label %return
604sw.bb100: br label %return
605sw.bb101: br label %return
606sw.bb102: br label %return
607sw.bb103: br label %return
608sw.bb104: br label %return
609sw.bb105: br label %return
610sw.bb106: br label %return
611sw.bb107: br label %return
612sw.bb108: br label %return
613sw.bb109: br label %return
614sw.bb110: br label %return
615sw.bb111: br label %return
616sw.bb112: br label %return
617sw.bb113: br label %return
618sw.bb114: br label %return
619sw.bb115: br label %return
620sw.bb116: br label %return
621sw.bb117: br label %return
622sw.bb118: br label %return
623sw.bb119: br label %return
624sw.bb120: br label %return
625sw.bb121: br label %return
626sw.bb122: br label %return
627sw.bb123: br label %return
628sw.bb124: br label %return
629sw.bb125: br label %return
630sw.bb126: br label %return
631sw.bb127: br label %return
632sw.bb128: br label %return
633sw.bb129: br label %return
634sw.bb130: br label %return
635sw.bb131: br label %return
636sw.bb132: br label %return
637sw.bb133: br label %return
638sw.bb134: br label %return
639sw.bb135: br label %return
640sw.bb136: br label %return
641sw.bb137: br label %return
642sw.bb138: br label %return
643sw.bb139: br label %return
644sw.bb140: br label %return
645sw.bb141: br label %return
646sw.bb142: br label %return
647sw.bb143: br label %return
648sw.bb144: br label %return
649sw.bb145: br label %return
650sw.bb146: br label %return
651sw.bb147: br label %return
652sw.bb148: br label %return
653sw.bb149: br label %return
654sw.bb150: br label %return
655sw.bb151: br label %return
656sw.bb152: br label %return
657sw.bb153: br label %return
658sw.bb154: br label %return
659sw.bb155: br label %return
660sw.bb156: br label %return
661sw.bb157: br label %return
662sw.bb158: br label %return
663sw.bb159: br label %return
664sw.bb160: br label %return
665sw.bb161: br label %return
666sw.bb162: br label %return
667sw.bb163: br label %return
668sw.bb164: br label %return
669sw.bb165: br label %return
670sw.bb166: br label %return
671sw.bb167: br label %return
672sw.bb168: br label %return
673sw.bb169: br label %return
674sw.bb170: br label %return
675sw.bb171: br label %return
676sw.bb172: br label %return
677sw.bb173: br label %return
678sw.bb174: br label %return
679sw.bb175: br label %return
680sw.bb176: br label %return
681sw.bb177: br label %return
682sw.bb178: br label %return
683sw.bb179: br label %return
684sw.bb180: br label %return
685sw.bb181: br label %return
686sw.bb182: br label %return
687sw.bb183: br label %return
688sw.bb184: br label %return
689sw.bb185: br label %return
690sw.bb186: br label %return
691sw.bb187: br label %return
692sw.bb188: br label %return
693sw.bb189: br label %return
694sw.bb190: br label %return
695sw.bb191: br label %return
696sw.bb192: br label %return
697sw.bb193: br label %return
698sw.bb194: br label %return
699sw.bb195: br label %return
700sw.bb196: br label %return
701sw.bb197: br label %return
702sw.bb198: br label %return
703sw.bb199: br label %return
704sw.bb200: br label %return
705sw.bb201: br label %return
706sw.bb202: br label %return
707sw.bb203: br label %return
708
709return:
710  %retval.0 = phi i32 [ 39204, %sw.bb202 ], [ 38809, %sw.bb201 ], [ 38416, %sw.bb200 ], [ 38025, %sw.bb199 ], [ 37636, %sw.bb198 ], [ 37249, %sw.bb197 ], [ 36864, %sw.bb196 ], [ 36481, %sw.bb195 ], [ 36100, %sw.bb194 ], [ 35721, %sw.bb193 ], [ 35344, %sw.bb192 ], [ 34969, %sw.bb191 ], [ 34596, %sw.bb190 ], [ 34225, %sw.bb189 ], [ 33856, %sw.bb188 ], [ 33489, %sw.bb187 ], [ 33124, %sw.bb186 ], [ 32761, %sw.bb185 ], [ 32400, %sw.bb184 ], [ 32041, %sw.bb183 ], [ 31684, %sw.bb182 ], [ 31329, %sw.bb181 ], [ 30976, %sw.bb180 ], [ 30625, %sw.bb179 ], [ 30276, %sw.bb178 ], [ 29929, %sw.bb177 ], [ 29584, %sw.bb176 ], [ 29241, %sw.bb175 ], [ 28900, %sw.bb174 ], [ 28561, %sw.bb173 ], [ 28224, %sw.bb172 ], [ 27889, %sw.bb171 ], [ 27556, %sw.bb170 ], [ 27225, %sw.bb169 ], [ 26896, %sw.bb168 ], [ 26569, %sw.bb167 ], [ 26244, %sw.bb166 ], [ 25921, %sw.bb165 ], [ 25600, %sw.bb164 ], [ 25281, %sw.bb163 ], [ 24964, %sw.bb162 ], [ 24649, %sw.bb161 ], [ 24336, %sw.bb160 ], [ 24025, %sw.bb159 ], [ 23716, %sw.bb158 ], [ 23409, %sw.bb157 ], [ 23104, %sw.bb156 ], [ 22801, %sw.bb155 ], [ 22500, %sw.bb154 ], [ 22201, %sw.bb153 ], [ 21904, %sw.bb152 ], [ 21609, %sw.bb151 ], [ 21316, %sw.bb150 ], [ 21025, %sw.bb149 ], [ 20736, %sw.bb148 ], [ 20449, %sw.bb147 ], [ 20164, %sw.bb146 ], [ 19881, %sw.bb145 ], [ 19600, %sw.bb144 ], [ 19321, %sw.bb143 ], [ 19044, %sw.bb142 ], [ 18769, %sw.bb141 ], [ 18496, %sw.bb140 ], [ 18225, %sw.bb139 ], [ 17956, %sw.bb138 ], [ 17689, %sw.bb137 ], [ 17424, %sw.bb136 ], [ 17161, %sw.bb135 ], [ 16900, %sw.bb134 ], [ 16641, %sw.bb133 ], [ 16384, %sw.bb132 ], [ 16129, %sw.bb131 ], [ 15876, %sw.bb130 ], [ 15625, %sw.bb129 ], [ 15376, %sw.bb128 ], [ 15129, %sw.bb127 ], [ 14884, %sw.bb126 ], [ 14641, %sw.bb125 ], [ 14400, %sw.bb124 ], [ 14161, %sw.bb123 ], [ 13924, %sw.bb122 ], [ 13689, %sw.bb121 ], [ 13456, %sw.bb120 ], [ 13225, %sw.bb119 ], [ 12996, %sw.bb118 ], [ 12769, %sw.bb117 ], [ 12544, %sw.bb116 ], [ 12321, %sw.bb115 ], [ 12100, %sw.bb114 ], [ 11881, %sw.bb113 ], [ 11664, %sw.bb112 ], [ 11449, %sw.bb111 ], [ 11236, %sw.bb110 ], [ 11025, %sw.bb109 ], [ 10816, %sw.bb108 ], [ 10609, %sw.bb107 ], [ 10404, %sw.bb106 ], [ 10201, %sw.bb105 ], [ 10000, %sw.bb104 ], [ 9801, %sw.bb103 ], [ 9604, %sw.bb102 ], [ 9409, %sw.bb101 ], [ 9216, %sw.bb100 ], [ 9025, %sw.bb99 ], [ 8836, %sw.bb98 ], [ 8649, %sw.bb97 ], [ 8464, %sw.bb96 ], [ 8281, %sw.bb95 ], [ 8100, %sw.bb94 ], [ 7921, %sw.bb93 ], [ 7744, %sw.bb92 ], [ 7569, %sw.bb91 ], [ 7396, %sw.bb90 ], [ 7225, %sw.bb89 ], [ 7056, %sw.bb88 ], [ 6889, %sw.bb87 ], [ 6724, %sw.bb86 ], [ 6561, %sw.bb85 ], [ 6400, %sw.bb84 ], [ 6241, %sw.bb83 ], [ 6084, %sw.bb82 ], [ 5929, %sw.bb81 ], [ 5776, %sw.bb80 ], [ 5625, %sw.bb79 ], [ 5476, %sw.bb78 ], [ 5329, %sw.bb77 ], [ 5184, %sw.bb76 ], [ 5112, %sw.bb74 ], [ 4900, %sw.bb73 ], [ 4761, %sw.bb72 ], [ 4624, %sw.bb71 ], [ 4489, %sw.bb70 ], [ 4356, %sw.bb69 ], [ 4225, %sw.bb68 ], [ 4096, %sw.bb67 ], [ 3969, %sw.bb66 ], [ 3844, %sw.bb65 ], [ 3721, %sw.bb64 ], [ 3600, %sw.bb63 ], [ 3481, %sw.bb62 ], [ 3364, %sw.bb61 ], [ 3249, %sw.bb60 ], [ 3136, %sw.bb59 ], [ 3025, %sw.bb58 ], [ 2970, %sw.bb56 ], [ 2809, %sw.bb55 ], [ 2704, %sw.bb54 ], [ 2601, %sw.bb53 ], [ 2500, %sw.bb52 ], [ 2401, %sw.bb51 ], [ 2304, %sw.bb50 ], [ 2209, %sw.bb49 ], [ 2116, %sw.bb48 ], [ 2025, %sw.bb47 ], [ 1980, %sw.bb45 ], [ 1849, %sw.bb44 ], [ 1764, %sw.bb43 ], [ 1681, %sw.bb42 ], [ 1600, %sw.bb41 ], [ 1521, %sw.bb40 ], [ 1444, %sw.bb39 ], [ 1369, %sw.bb38 ], [ 1296, %sw.bb37 ], [ 1260, %sw.bb35 ], [ 1156, %sw.bb34 ], [ 1089, %sw.bb33 ], [ 1024, %sw.bb32 ], [ 961, %sw.bb31 ], [ 900, %sw.bb30 ], [ 841, %sw.bb29 ], [ 784, %sw.bb28 ], [ 729, %sw.bb27 ], [ 676, %sw.bb26 ], [ 625, %sw.bb25 ], [ 576, %sw.bb24 ], [ 529, %sw.bb23 ], [ 484, %sw.bb22 ], [ 441, %sw.bb21 ], [ 400, %sw.bb20 ], [ 361, %sw.bb19 ], [ 342, %sw.bb18 ], [ 289, %sw.bb17 ], [ 256, %sw.bb16 ], [ 225, %sw.bb15 ], [ 196, %sw.bb14 ], [ 169, %sw.bb13 ], [ 144, %sw.bb12 ], [ 121, %sw.bb11 ], [ 100, %sw.bb10 ], [ 81, %sw.bb9 ], [ 64, %sw.bb8 ], [ 49, %sw.bb7 ], [ 36, %sw.bb6 ], [ 25, %sw.bb5 ], [ 16, %sw.bb4 ], [ 9, %sw.bb3 ], [ 4, %sw.bb2 ], [ 1, %sw.bb1 ], [ 39601, %sw.bb203 ], [ 0, %if.end ]
711  ret i32 %retval.0
712}
713
714define i32 @cprop(i32 %x, i32 %y) {
715entry:
716  switch i32 %x, label %sw.default [
717    i32 1, label %return
718    i32 2, label %sw.bb1
719    i32 3, label %sw.bb2
720    i32 4, label %sw.bb2
721    i32 5, label %sw.bb2
722    i32 6, label %sw.bb3
723    i32 7, label %sw.bb3
724  ]
725
726sw.bb1: br label %return
727
728sw.bb2:
729  %and = and i32 %x, 1
730  %and.ptr = inttoptr i32 %and to i8*
731  %tobool = icmp ne i8* %and.ptr, null
732  %cond = select i1 %tobool, i32 -123, i32 456
733  %sub = sub nsw i32 %x, %cond
734  br label %return
735
736sw.bb3:
737  %trunc = trunc i32 %x to i8
738  %sext = sext i8 %trunc to i32
739  %select.i = icmp sgt i32 %sext, 0
740  %select = select i1 %select.i, i32 %sext, i32 %y
741  br label %return
742
743sw.default:
744  br label %return
745
746return:
747  %retval.0 = phi i32 [ 123, %sw.default ], [ %select, %sw.bb3 ], [ %sub, %sw.bb2 ], [ 42, %sw.bb1 ], [ 5, %entry ]
748  ret i32 %retval.0
749
750; CHECK-LABEL: @cprop(
751; CHECK: switch.lookup:
752; CHECK: %switch.gep = getelementptr inbounds [7 x i32], [7 x i32]* @switch.table5, i32 0, i32 %switch.tableidx
753}
754
755define i32 @unreachable_case(i32 %x)  {
756entry:
757  switch i32 %x, label %sw.default [
758    i32 0, label %sw.bb
759    i32 1, label %sw.bb
760    i32 2, label %sw.bb
761    i32 3, label %sw.bb1
762    i32 4, label %sw.bb2
763    i32 5, label %sw.bb3
764    i32 6, label %sw.bb3
765    i32 7, label %sw.bb3
766    i32 8, label %sw.bb3
767  ]
768
769sw.bb: br label %return
770sw.bb1: unreachable
771sw.bb2: br label %return
772sw.bb3: br label %return
773sw.default: br label %return
774
775return:
776  %retval.0 = phi i32 [ 1, %sw.bb3 ], [ -1, %sw.bb2 ], [ 0, %sw.bb ], [ 2, %sw.default ]
777  ret i32 %retval.0
778
779; CHECK-LABEL: @unreachable_case(
780; CHECK: switch.lookup:
781; CHECK: getelementptr inbounds [9 x i32], [9 x i32]* @switch.table6, i32 0, i32 %switch.tableidx
782}
783
784define i32 @unreachable_default(i32 %x)  {
785entry:
786  switch i32 %x, label %default [
787    i32 0, label %bb0
788    i32 1, label %bb1
789    i32 2, label %bb2
790    i32 3, label %bb3
791  ]
792
793bb0: br label %return
794bb1: br label %return
795bb2: br label %return
796bb3: br label %return
797default: unreachable
798
799return:
800  %retval = phi i32 [ 42, %bb0 ], [ 52, %bb1 ], [ 1, %bb2 ], [ 2, %bb3 ]
801  ret i32 %retval
802
803; CHECK-LABEL: @unreachable_default(
804; CHECK: entry:
805; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0
806; CHECK-NOT: icmp
807; CHECK-NOT: br 1i
808; CHECK-NEXT: %switch.gep = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table7, i32 0, i32 %switch.tableidx
809; CHECK-NEXT: %switch.load = load i32, i32* %switch.gep
810; CHECK-NEXT: ret i32 %switch.load
811}
812
813; Don't create a table with illegal type
814define i96 @illegaltype(i32 %c) {
815entry:
816  switch i32 %c, label %sw.default [
817    i32 42, label %return
818    i32 43, label %sw.bb1
819    i32 44, label %sw.bb2
820    i32 45, label %sw.bb3
821    i32 46, label %sw.bb4
822  ]
823
824sw.bb1: br label %return
825sw.bb2: br label %return
826sw.bb3: br label %return
827sw.bb4: br label %return
828sw.default: br label %return
829return:
830  %retval.0 = phi i96 [ 15, %sw.default ], [ 27, %sw.bb4 ], [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
831  ret i96 %retval.0
832
833; CHECK-LABEL: @illegaltype(
834; CHECK-NOT: @switch.table
835; CHECK: switch i32 %c
836}
837
838; If we can build a lookup table without any holes, we don't need a default result.
839declare void @exit(i32)
840define i32 @nodefaultnoholes(i32 %c) {
841entry:
842  switch i32 %c, label %sw.default [
843    i32 0, label %return
844    i32 1, label %sw.bb1
845    i32 2, label %sw.bb2
846    i32 3, label %sw.bb3
847  ]
848
849sw.bb1: br label %return
850sw.bb2: br label %return
851sw.bb3: br label %return
852sw.default: call void @exit(i32 1)
853            unreachable
854return:
855  %x = phi i32 [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
856  ret i32 %x
857
858; CHECK-LABEL: @nodefaultnoholes(
859; CHECK: @switch.table
860; CHECK-NOT: switch i32
861}
862
863; This lookup table will have holes, so we need to test for the holes.
864define i32 @nodefaultwithholes(i32 %c) {
865entry:
866  switch i32 %c, label %sw.default [
867    i32 0, label %return
868    i32 1, label %sw.bb1
869    i32 2, label %sw.bb2
870    i32 3, label %sw.bb3
871    i32 5, label %sw.bb3
872  ]
873
874sw.bb1: br label %return
875sw.bb2: br label %return
876sw.bb3: br label %return
877sw.default: call void @exit(i32 1)
878            unreachable
879return:
880  %x = phi i32 [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
881  ret i32 %x
882
883; CHECK-LABEL: @nodefaultwithholes(
884; CHECK: entry:
885; CHECK: br i1 %{{.*}}, label %switch.hole_check, label %sw.default
886; CHECK: switch.hole_check:
887; CHECK-NEXT: %switch.maskindex = trunc i32 %switch.tableidx to i8
888; CHECK-NEXT: %switch.shifted = lshr i8 47, %switch.maskindex
889; The mask is binary 101111.
890; CHECK-NEXT: %switch.lobit = trunc i8 %switch.shifted to i1
891; CHECK-NEXT: br i1 %switch.lobit, label %switch.lookup, label %sw.default
892; CHECK-NOT: switch i32
893}
894
895; We don't build lookup tables with holes for switches with less than four cases.
896define i32 @threecasesholes(i32 %c) {
897entry:
898  switch i32 %c, label %sw.default [
899    i32 0, label %return
900    i32 1, label %sw.bb1
901    i32 3, label %sw.bb2
902  ]
903sw.bb1: br label %return
904sw.bb2: br label %return
905sw.default: br label %return
906return:
907  %x = phi i32 [ %c, %sw.default ], [ 5, %sw.bb2 ], [ 7, %sw.bb1 ], [ 9, %entry ]
908  ret i32 %x
909; CHECK-LABEL: @threecasesholes(
910; CHECK: switch i32
911; CHECK-NOT: @switch.table
912}
913
914; We build lookup tables for switches with three or more cases.
915define i32 @threecases(i32 %c) {
916entry:
917  switch i32 %c, label %sw.default [
918    i32 0, label %return
919    i32 1, label %sw.bb1
920    i32 2, label %sw.bb2
921  ]
922sw.bb1: br label %return
923sw.bb2: br label %return
924sw.default: br label %return
925return:
926  %x = phi i32 [ 3, %sw.default ], [ 5, %sw.bb2 ], [ 7, %sw.bb1 ], [ 10, %entry ]
927  ret i32 %x
928; CHECK-LABEL: @threecases(
929; CHECK-NOT: switch i32
930; CHECK: @switch.table
931}
932
933; We don't build tables for switches with two cases.
934define i32 @twocases(i32 %c) {
935entry:
936  switch i32 %c, label %sw.default [
937    i32 0, label %return
938    i32 1, label %sw.bb1
939  ]
940sw.bb1: br label %return
941sw.default: br label %return
942return:
943  %x = phi i32 [ 3, %sw.default ], [ 7, %sw.bb1 ], [ 9, %entry ]
944  ret i32 %x
945; CHECK-LABEL: @twocases(
946; CHECK-NOT: switch i32
947; CHECK-NOT: @switch.table
948; CHECK: %switch.selectcmp
949; CHECK-NEXT: %switch.select
950; CHECK-NEXT: %switch.selectcmp1
951; CHECK-NEXT: %switch.select2
952}
953
954; Don't build tables for switches with TLS variables.
955@tls_a = thread_local global i32 0
956@tls_b = thread_local global i32 0
957@tls_c = thread_local global i32 0
958@tls_d = thread_local global i32 0
959define i32* @tls(i32 %x) {
960entry:
961  switch i32 %x, label %sw.default [
962    i32 0, label %return
963    i32 1, label %sw.bb1
964    i32 2, label %sw.bb2
965  ]
966sw.bb1:
967  br label %return
968sw.bb2:
969  br label %return
970sw.default:
971  br label %return
972return:
973  %retval.0 = phi i32* [ @tls_d, %sw.default ], [ @tls_c, %sw.bb2 ], [ @tls_b, %sw.bb1 ], [ @tls_a, %entry ]
974  ret i32* %retval.0
975; CHECK-LABEL: @tls(
976; CHECK: switch i32
977; CHECK-NOT: @switch.table
978}
979
980; Don't build tables for switches with dllimport variables.
981@dllimport_a = external dllimport global [3x i32]
982@dllimport_b = external dllimport global [3x i32]
983@dllimport_c = external dllimport global [3x i32]
984@dllimport_d = external dllimport global [3x i32]
985define i32* @dllimport(i32 %x) {
986entry:
987  switch i32 %x, label %sw.default [
988    i32 0, label %return
989    i32 1, label %sw.bb1
990    i32 2, label %sw.bb2
991  ]
992sw.bb1:
993  br label %return
994sw.bb2:
995  br label %return
996sw.default:
997  br label %return
998return:
999  %retval.0 = phi i32* [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_d, i32 0, i32 0), %sw.default ],
1000                       [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_c, i32 0, i32 0), %sw.bb2 ],
1001                       [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_b, i32 0, i32 0), %sw.bb1 ],
1002                       [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_a, i32 0, i32 0), %entry ]
1003  ret i32* %retval.0
1004; CHECK-LABEL: @dllimport(
1005; CHECK: switch i32
1006; CHECK-NOT: @switch.table
1007}
1008
1009; We can use linear mapping.
1010define i8 @linearmap1(i32 %c) {
1011entry:
1012  switch i32 %c, label %sw.default [
1013    i32 10, label %return
1014    i32 11, label %sw.bb1
1015    i32 12, label %sw.bb2
1016    i32 13, label %sw.bb3
1017  ]
1018sw.bb1: br label %return
1019sw.bb2: br label %return
1020sw.bb3: br label %return
1021sw.default: br label %return
1022return:
1023  %x = phi i8 [ 3, %sw.default ], [ 3, %sw.bb3 ], [ 8, %sw.bb2 ], [ 13, %sw.bb1 ], [ 18, %entry ]
1024  ret i8 %x
1025; CHECK-LABEL: @linearmap1(
1026; CHECK: entry:
1027; CHECK-NEXT: %switch.tableidx = sub i32 %c, 10
1028; CHECK: switch.lookup:
1029; CHECK-NEXT: %switch.idx.cast = trunc i32 %switch.tableidx to i8
1030; CHECK-NEXT: %switch.idx.mult = mul i8 %switch.idx.cast, -5
1031; CHECK-NEXT: %switch.offset = add i8 %switch.idx.mult, 18
1032; CHECK-NEXT: ret i8 %switch.offset
1033}
1034
1035; Linear mapping in a different configuration.
1036define i32 @linearmap2(i8 %c) {
1037entry:
1038  switch i8 %c, label %sw.default [
1039    i8 -10, label %return
1040    i8 -11, label %sw.bb1
1041    i8 -12, label %sw.bb2
1042    i8 -13, label %sw.bb3
1043  ]
1044sw.bb1: br label %return
1045sw.bb2: br label %return
1046sw.bb3: br label %return
1047sw.default: br label %return
1048return:
1049  %x = phi i32 [ 3, %sw.default ], [ 18, %sw.bb3 ], [ 19, %sw.bb2 ], [ 20, %sw.bb1 ], [ 21, %entry ]
1050  ret i32 %x
1051; CHECK-LABEL: @linearmap2(
1052; CHECK: entry:
1053; CHECK-NEXT: %switch.tableidx = sub i8 %c, -13
1054; CHECK: switch.lookup:
1055; CHECK-NEXT: %switch.idx.cast = zext i8 %switch.tableidx to i32
1056; CHECK-NEXT: %switch.offset = add i32 %switch.idx.cast, 18
1057; CHECK-NEXT: ret i32 %switch.offset
1058}
1059
1060; Linear mapping with overflows.
1061define i8 @linearmap3(i32 %c) {
1062entry:
1063  switch i32 %c, label %sw.default [
1064    i32 10, label %return
1065    i32 11, label %sw.bb1
1066    i32 12, label %sw.bb2
1067    i32 13, label %sw.bb3
1068  ]
1069sw.bb1: br label %return
1070sw.bb2: br label %return
1071sw.bb3: br label %return
1072sw.default: br label %return
1073return:
1074  %x = phi i8 [ 3, %sw.default ], [ 44, %sw.bb3 ], [ -56, %sw.bb2 ], [ 100, %sw.bb1 ], [ 0, %entry ]
1075  ret i8 %x
1076; CHECK-LABEL: @linearmap3(
1077; CHECK: entry:
1078; CHECK-NEXT: %switch.tableidx = sub i32 %c, 10
1079; CHECK: switch.lookup:
1080; CHECK-NEXT: %switch.idx.cast = trunc i32 %switch.tableidx to i8
1081; CHECK-NEXT: %switch.idx.mult = mul i8 %switch.idx.cast, 100
1082; CHECK-NEXT: ret i8 %switch.idx.mult
1083}
1084
1085; Linear mapping with with multiplier 1 and offset 0.
1086define i8 @linearmap4(i32 %c) {
1087entry:
1088  switch i32 %c, label %sw.default [
1089    i32 -2, label %return
1090    i32 -1, label %sw.bb1
1091    i32 0, label %sw.bb2
1092    i32 1, label %sw.bb3
1093  ]
1094sw.bb1: br label %return
1095sw.bb2: br label %return
1096sw.bb3: br label %return
1097sw.default: br label %return
1098return:
1099  %x = phi i8 [ 3, %sw.default ], [ 3, %sw.bb3 ], [ 2, %sw.bb2 ], [ 1, %sw.bb1 ], [ 0, %entry ]
1100  ret i8 %x
1101; CHECK-LABEL: @linearmap4(
1102; CHECK: entry:
1103; CHECK-NEXT: %switch.tableidx = sub i32 %c, -2
1104; CHECK: switch.lookup:
1105; CHECK-NEXT: %switch.idx.cast = trunc i32 %switch.tableidx to i8
1106; CHECK-NEXT: ret i8 %switch.idx.cast
1107}
1108
1109; Reuse the inverted table range compare.
1110define i32 @reuse_cmp1(i32 %x) {
1111entry:
1112  switch i32 %x, label %sw.default [
1113    i32 0, label %sw.bb
1114    i32 1, label %sw.bb1
1115    i32 2, label %sw.bb2
1116    i32 3, label %sw.bb3
1117  ]
1118sw.bb: br label %sw.epilog
1119sw.bb1: br label %sw.epilog
1120sw.bb2: br label %sw.epilog
1121sw.bb3: br label %sw.epilog
1122sw.default: br label %sw.epilog
1123sw.epilog:
1124  %r.0 = phi i32 [ 0, %sw.default ], [ 13, %sw.bb3 ], [ 12, %sw.bb2 ], [ 11, %sw.bb1 ], [ 10, %sw.bb ]
1125  %cmp = icmp eq i32 %r.0, 0       ; This compare can be "replaced".
1126  br i1 %cmp, label %if.then, label %if.end
1127if.then: br label %return
1128if.end: br label %return
1129return:
1130  %retval.0 = phi i32 [ 100, %if.then ], [ %r.0, %if.end ]
1131  ret i32 %retval.0
1132; CHECK-LABEL: @reuse_cmp1(
1133; CHECK: entry:
1134; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0
1135; CHECK-NEXT: [[C:%.+]] = icmp ult i32 %switch.tableidx, 4
1136; CHECK-NEXT: %inverted.cmp = xor i1 [[C]], true
1137; CHECK:      [[R:%.+]] = select i1 %inverted.cmp, i32 100, i32 {{.*}}
1138; CHECK-NEXT: ret i32 [[R]]
1139}
1140
1141; Reuse the table range compare.
1142define i32 @reuse_cmp2(i32 %x) {
1143entry:
1144  switch i32 %x, label %sw.default [
1145    i32 0, label %sw.bb
1146    i32 1, label %sw.bb1
1147    i32 2, label %sw.bb2
1148    i32 3, label %sw.bb3
1149  ]
1150sw.bb: br label %sw.epilog
1151sw.bb1: br label %sw.epilog
1152sw.bb2: br label %sw.epilog
1153sw.bb3: br label %sw.epilog
1154sw.default: br label %sw.epilog
1155sw.epilog:
1156  %r.0 = phi i32 [ 4, %sw.default ], [ 3, %sw.bb3 ], [ 2, %sw.bb2 ], [ 1, %sw.bb1 ], [ 0, %sw.bb ]
1157  %cmp = icmp ne i32 %r.0, 4       ; This compare can be "replaced".
1158  br i1 %cmp, label %if.then, label %if.end
1159if.then: br label %return
1160if.end: br label %return
1161return:
1162  %retval.0 = phi i32 [ %r.0, %if.then ], [ 100, %if.end ]
1163  ret i32 %retval.0
1164; CHECK-LABEL: @reuse_cmp2(
1165; CHECK: entry:
1166; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0
1167; CHECK-NEXT: [[C:%.+]] = icmp ult i32 %switch.tableidx, 4
1168; CHECK:      [[R:%.+]] = select i1 [[C]], i32 {{.*}}, i32 100
1169; CHECK-NEXT: ret i32 [[R]]
1170}
1171
1172; Cannot reuse the table range compare, because the default value is the same
1173; as one of the case values.
1174define i32 @no_reuse_cmp(i32 %x) {
1175entry:
1176  switch i32 %x, label %sw.default [
1177    i32 0, label %sw.bb
1178    i32 1, label %sw.bb1
1179    i32 2, label %sw.bb2
1180    i32 3, label %sw.bb3
1181  ]
1182sw.bb: br label %sw.epilog
1183sw.bb1: br label %sw.epilog
1184sw.bb2: br label %sw.epilog
1185sw.bb3: br label %sw.epilog
1186sw.default: br label %sw.epilog
1187sw.epilog:
1188  %r.0 = phi i32 [ 12, %sw.default ], [ 13, %sw.bb3 ], [ 12, %sw.bb2 ], [ 11, %sw.bb1 ], [ 10, %sw.bb ]
1189  %cmp = icmp ne i32 %r.0, 0
1190  br i1 %cmp, label %if.then, label %if.end
1191if.then: br label %return
1192if.end: br label %return
1193return:
1194  %retval.0 = phi i32 [ %r.0, %if.then ], [ 100, %if.end ]
1195  ret i32 %retval.0
1196; CHECK-LABEL: @no_reuse_cmp(
1197; CHECK:  [[S:%.+]] = select
1198; CHECK-NEXT:  %cmp = icmp ne i32 [[S]], 0
1199; CHECK-NEXT:  [[R:%.+]] = select i1 %cmp, i32 [[S]], i32 100
1200; CHECK-NEXT:  ret i32 [[R]]
1201}
1202
1203; Cannot reuse the table range compare, because the phi at the switch merge
1204; point is not dominated by the switch.
1205define i32 @no_reuse_cmp2(i32 %x, i32 %y) {
1206entry:
1207  %ec = icmp ne i32 %y, 0
1208  br i1 %ec, label %switch.entry, label %sw.epilog
1209switch.entry:
1210  switch i32 %x, label %sw.default [
1211    i32 0, label %sw.bb
1212    i32 1, label %sw.bb1
1213    i32 2, label %sw.bb2
1214    i32 3, label %sw.bb3
1215  ]
1216sw.bb: br label %sw.epilog
1217sw.bb1: br label %sw.epilog
1218sw.bb2: br label %sw.epilog
1219sw.bb3: br label %sw.epilog
1220sw.default: br label %sw.epilog
1221sw.epilog:
1222  %r.0 = phi i32 [100, %entry], [ 0, %sw.default ], [ 13, %sw.bb3 ], [ 12, %sw.bb2 ], [ 11, %sw.bb1 ], [ 10, %sw.bb ]
1223  %cmp = icmp eq i32 %r.0, 0       ; This compare can be "replaced".
1224  br i1 %cmp, label %if.then, label %if.end
1225if.then: br label %return
1226if.end: br label %return
1227return:
1228  %retval.0 = phi i32 [ 100, %if.then ], [ %r.0, %if.end ]
1229  ret i32 %retval.0
1230; CHECK-LABEL: @no_reuse_cmp2(
1231; CHECK:  %r.0 = phi
1232; CHECK-NEXT:  %cmp = icmp eq i32 %r.0, 0
1233; CHECK-NEXT:  [[R:%.+]] = select i1 %cmp
1234; CHECK-NEXT:  ret i32 [[R]]
1235}
1236
1237define void @pr20210(i8 %x, i1 %y) {
1238; %z has uses outside of its BB or the phi it feeds into,
1239; so doing a table lookup and jumping directly to while.cond would
1240; cause %z to cease dominating all its uses.
1241
1242entry:
1243  br i1 %y, label %sw, label %intermediate
1244
1245sw:
1246  switch i8 %x, label %end [
1247    i8 7, label %intermediate
1248    i8 3, label %intermediate
1249    i8 2, label %intermediate
1250    i8 1, label %intermediate
1251    i8 0, label %intermediate
1252  ]
1253
1254intermediate:
1255  %z = zext i8 %x to i32
1256  br label %while.cond
1257
1258while.cond:
1259  %i = phi i32 [ %z, %intermediate ], [ %j, %while.body ]
1260  %b = icmp ne i32 %i, 7
1261  br i1 %b, label %while.body, label %while.end
1262
1263while.body:
1264  %j = add i32 %i, 1
1265  br label %while.cond
1266
1267while.end:
1268  call void @exit(i32 %z)
1269  unreachable
1270
1271end:
1272  ret void
1273; CHECK-LABEL: @pr20210
1274; CHECK: switch i8 %x
1275}
1276