test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

   1 ; RUN: opt < %s -simplifycfg -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
   2
   3 target 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"
   4 target 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]* @.str, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8]* @.str1, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8]* @.str2, i64 0, i64 0), i8* getelementptr inbounds ([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
  25 ; CHECK: @switch.table6 = private unnamed_addr constant [5 x i32] [i32 0, i32 0, i32 0, 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
  32 define i32 @f(i32 %c) {
  33 entry:
  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
  44 sw.bb1: br label %return
  45 sw.bb2: br label %return
  46 sw.bb3: br label %return
  47 sw.bb4: br label %return
  48 sw.bb5: br label %return
  49 sw.bb6: br label %return
  50 sw.default: br label %return
  51 return:
  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]* @switch.table, i32 0, i32 %switch.tableidx
  62 ; CHECK-NEXT: %switch.load = load 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
  70 declare void @dummy(i8 signext, float)
  71 define void @h(i32 %x) {
  72 entry:
  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
  80 sw.bb1: br label %sw.epilog
  81 sw.bb2: br label %sw.epilog
  82 sw.bb3: br label %sw.epilog
  83 sw.default: br label %sw.epilog
  84
  85 sw.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]* @switch.table1, i32 0, i32 %switch.tableidx
 101 ; CHECK-NEXT: %switch.load = load 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
 119 define i8* @foostring(i32 %x)  {
 120 entry:
 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
 128 sw.bb1: br label %return
 129 sw.bb2: br label %return
 130 sw.bb3: br label %return
 131 sw.default: br label %return
 132
 133 return:
 134   %retval.0 = phi i8* [ getelementptr inbounds ([6 x i8]* @.str4, i64 0, i64 0), %sw.default ],
 135                       [ getelementptr inbounds ([4 x i8]* @.str3, i64 0, i64 0), %sw.bb3 ],
 136                       [ getelementptr inbounds ([4 x i8]* @.str2, i64 0, i64 0), %sw.bb2 ],
 137                       [ getelementptr inbounds ([4 x i8]* @.str1, i64 0, i64 0), %sw.bb1 ],
 138                       [ getelementptr inbounds ([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*]* @switch.table2, i32 0, i32 %switch.tableidx
 148 ; CHECK-NEXT: %switch.load = load 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
 155 define i32 @earlyreturncrash(i32 %x)  {
 156 entry:
 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
 164 sw.bb1: br label %sw.epilog
 165 sw.bb2: br label %sw.epilog
 166 sw.bb3: br label %sw.epilog
 167 sw.default: br label %sw.epilog
 168
 169 sw.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]* @switch.table3, i32 0, i32 %switch.tableidx
 177 ; CHECK-NEXT: %switch.load = load 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
 188 define i32 @crud(i8 zeroext %c)  {
 189 entry:
 190   %cmp = icmp ult i8 %c, 33
 191   br i1 %cmp, label %lor.end, label %switch.early.test
 192
 193 switch.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
 206 switch.edge: br label %lor.end
 207 lor.rhs: br label %lor.end
 208
 209 lor.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
 245 define i32 @overflow(i32 %type) {
 246 entry:
 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
 256 sw.bb: br label %if.end
 257 sw.bb1: br label %if.end
 258 sw.bb2: br label %if.end
 259 sw.bb3: br label %if.end
 260 sw.default: br label %if.end
 261 if.else: br label %if.end
 262
 263 if.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
 272 define i1 @undef(i32 %tmp) {
 273 bb:
 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
 281 bb1: br label %bb3
 282 bb2: br label %bb3
 283
 284 bb3:
 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
 296 define i32 @large(i32 %x) {
 297 entry:
 298   %cmp = icmp slt i32 %x, 0
 299   br i1 %cmp, label %if.then, label %if.end
 300
 301 if.then:
 302   %mul = mul i32 %x, -10
 303   br label %if.end
 304
 305 if.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
 509 sw.bb1: br label %return
 510 sw.bb2: br label %return
 511 sw.bb3: br label %return
 512 sw.bb4: br label %return
 513 sw.bb5: br label %return
 514 sw.bb6: br label %return
 515 sw.bb7: br label %return
 516 sw.bb8: br label %return
 517 sw.bb9: br label %return
 518 sw.bb10: br label %return
 519 sw.bb11: br label %return
 520 sw.bb12: br label %return
 521 sw.bb13: br label %return
 522 sw.bb14: br label %return
 523 sw.bb15: br label %return
 524 sw.bb16: br label %return
 525 sw.bb17: br label %return
 526 sw.bb18: br label %return
 527 sw.bb19: br label %return
 528 sw.bb20: br label %return
 529 sw.bb21: br label %return
 530 sw.bb22: br label %return
 531 sw.bb23: br label %return
 532 sw.bb24: br label %return
 533 sw.bb25: br label %return
 534 sw.bb26: br label %return
 535 sw.bb27: br label %return
 536 sw.bb28: br label %return
 537 sw.bb29: br label %return
 538 sw.bb30: br label %return
 539 sw.bb31: br label %return
 540 sw.bb32: br label %return
 541 sw.bb33: br label %return
 542 sw.bb34: br label %return
 543 sw.bb35: br label %return
 544 sw.bb37: br label %return
 545 sw.bb38: br label %return
 546 sw.bb39: br label %return
 547 sw.bb40: br label %return
 548 sw.bb41: br label %return
 549 sw.bb42: br label %return
 550 sw.bb43: br label %return
 551 sw.bb44: br label %return
 552 sw.bb45: br label %return
 553 sw.bb47: br label %return
 554 sw.bb48: br label %return
 555 sw.bb49: br label %return
 556 sw.bb50: br label %return
 557 sw.bb51: br label %return
 558 sw.bb52: br label %return
 559 sw.bb53: br label %return
 560 sw.bb54: br label %return
 561 sw.bb55: br label %return
 562 sw.bb56: br label %return
 563 sw.bb58: br label %return
 564 sw.bb59: br label %return
 565 sw.bb60: br label %return
 566 sw.bb61: br label %return
 567 sw.bb62: br label %return
 568 sw.bb63: br label %return
 569 sw.bb64: br label %return
 570 sw.bb65: br label %return
 571 sw.bb66: br label %return
 572 sw.bb67: br label %return
 573 sw.bb68: br label %return
 574 sw.bb69: br label %return
 575 sw.bb70: br label %return
 576 sw.bb71: br label %return
 577 sw.bb72: br label %return
 578 sw.bb73: br label %return
 579 sw.bb74: br label %return
 580 sw.bb76: br label %return
 581 sw.bb77: br label %return
 582 sw.bb78: br label %return
 583 sw.bb79: br label %return
 584 sw.bb80: br label %return
 585 sw.bb81: br label %return
 586 sw.bb82: br label %return
 587 sw.bb83: br label %return
 588 sw.bb84: br label %return
 589 sw.bb85: br label %return
 590 sw.bb86: br label %return
 591 sw.bb87: br label %return
 592 sw.bb88: br label %return
 593 sw.bb89: br label %return
 594 sw.bb90: br label %return
 595 sw.bb91: br label %return
 596 sw.bb92: br label %return
 597 sw.bb93: br label %return
 598 sw.bb94: br label %return
 599 sw.bb95: br label %return
 600 sw.bb96: br label %return
 601 sw.bb97: br label %return
 602 sw.bb98: br label %return
 603 sw.bb99: br label %return
 604 sw.bb100: br label %return
 605 sw.bb101: br label %return
 606 sw.bb102: br label %return
 607 sw.bb103: br label %return
 608 sw.bb104: br label %return
 609 sw.bb105: br label %return
 610 sw.bb106: br label %return
 611 sw.bb107: br label %return
 612 sw.bb108: br label %return
 613 sw.bb109: br label %return
 614 sw.bb110: br label %return
 615 sw.bb111: br label %return
 616 sw.bb112: br label %return
 617 sw.bb113: br label %return
 618 sw.bb114: br label %return
 619 sw.bb115: br label %return
 620 sw.bb116: br label %return
 621 sw.bb117: br label %return
 622 sw.bb118: br label %return
 623 sw.bb119: br label %return
 624 sw.bb120: br label %return
 625 sw.bb121: br label %return
 626 sw.bb122: br label %return
 627 sw.bb123: br label %return
 628 sw.bb124: br label %return
 629 sw.bb125: br label %return
 630 sw.bb126: br label %return
 631 sw.bb127: br label %return
 632 sw.bb128: br label %return
 633 sw.bb129: br label %return
 634 sw.bb130: br label %return
 635 sw.bb131: br label %return
 636 sw.bb132: br label %return
 637 sw.bb133: br label %return
 638 sw.bb134: br label %return
 639 sw.bb135: br label %return
 640 sw.bb136: br label %return
 641 sw.bb137: br label %return
 642 sw.bb138: br label %return
 643 sw.bb139: br label %return
 644 sw.bb140: br label %return
 645 sw.bb141: br label %return
 646 sw.bb142: br label %return
 647 sw.bb143: br label %return
 648 sw.bb144: br label %return
 649 sw.bb145: br label %return
 650 sw.bb146: br label %return
 651 sw.bb147: br label %return
 652 sw.bb148: br label %return
 653 sw.bb149: br label %return
 654 sw.bb150: br label %return
 655 sw.bb151: br label %return
 656 sw.bb152: br label %return
 657 sw.bb153: br label %return
 658 sw.bb154: br label %return
 659 sw.bb155: br label %return
 660 sw.bb156: br label %return
 661 sw.bb157: br label %return
 662 sw.bb158: br label %return
 663 sw.bb159: br label %return
 664 sw.bb160: br label %return
 665 sw.bb161: br label %return
 666 sw.bb162: br label %return
 667 sw.bb163: br label %return
 668 sw.bb164: br label %return
 669 sw.bb165: br label %return
 670 sw.bb166: br label %return
 671 sw.bb167: br label %return
 672 sw.bb168: br label %return
 673 sw.bb169: br label %return
 674 sw.bb170: br label %return
 675 sw.bb171: br label %return
 676 sw.bb172: br label %return
 677 sw.bb173: br label %return
 678 sw.bb174: br label %return
 679 sw.bb175: br label %return
 680 sw.bb176: br label %return
 681 sw.bb177: br label %return
 682 sw.bb178: br label %return
 683 sw.bb179: br label %return
 684 sw.bb180: br label %return
 685 sw.bb181: br label %return
 686 sw.bb182: br label %return
 687 sw.bb183: br label %return
 688 sw.bb184: br label %return
 689 sw.bb185: br label %return
 690 sw.bb186: br label %return
 691 sw.bb187: br label %return
 692 sw.bb188: br label %return
 693 sw.bb189: br label %return
 694 sw.bb190: br label %return
 695 sw.bb191: br label %return
 696 sw.bb192: br label %return
 697 sw.bb193: br label %return
 698 sw.bb194: br label %return
 699 sw.bb195: br label %return
 700 sw.bb196: br label %return
 701 sw.bb197: br label %return
 702 sw.bb198: br label %return
 703 sw.bb199: br label %return
 704 sw.bb200: br label %return
 705 sw.bb201: br label %return
 706 sw.bb202: br label %return
 707 sw.bb203: br label %return
 708
 709 return:
 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
 714 define i32 @cprop(i32 %x, i32 %y) {
 715 entry:
 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
 726 sw.bb1: br label %return
 727
 728 sw.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
 736 sw.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
 743 sw.default:
 744   br label %return
 745
 746 return:
 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]* @switch.table5, i32 0, i32 %switch.tableidx
 753 }
 754
 755 define i32 @unreachable(i32 %x)  {
 756 entry:
 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
 769 sw.bb: br label %return
 770 sw.bb1: unreachable
 771 sw.bb2: br label %return
 772 sw.bb3: br label %return
 773 sw.default: unreachable
 774
 775 return:
 776   %retval.0 = phi i32 [ 1, %sw.bb3 ], [ -1, %sw.bb2 ], [ 0, %sw.bb ]
 777   ret i32 %retval.0
 778
 779 ; CHECK-LABEL: @unreachable(
 780 ; CHECK: switch.lookup:
 781 ; CHECK: getelementptr inbounds [5 x i32]* @switch.table6, i32 0, i32 %switch.tableidx
 782 }
 783
 784 ; Don't create a table with illegal type
 785 define i96 @illegaltype(i32 %c) {
 786 entry:
 787   switch i32 %c, label %sw.default [
 788     i32 42, label %return
 789     i32 43, label %sw.bb1
 790     i32 44, label %sw.bb2
 791     i32 45, label %sw.bb3
 792     i32 46, label %sw.bb4
 793   ]
 794
 795 sw.bb1: br label %return
 796 sw.bb2: br label %return
 797 sw.bb3: br label %return
 798 sw.bb4: br label %return
 799 sw.default: br label %return
 800 return:
 801   %retval.0 = phi i96 [ 15, %sw.default ], [ 27, %sw.bb4 ], [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
 802   ret i96 %retval.0
 803
 804 ; CHECK-LABEL: @illegaltype(
 805 ; CHECK-NOT: @switch.table
 806 ; CHECK: switch i32 %c
 807 }
 808
 809 ; If we can build a lookup table without any holes, we don't need a default result.
 810 declare void @exit(i32)
 811 define i32 @nodefaultnoholes(i32 %c) {
 812 entry:
 813   switch i32 %c, label %sw.default [
 814     i32 0, label %return
 815     i32 1, label %sw.bb1
 816     i32 2, label %sw.bb2
 817     i32 3, label %sw.bb3
 818   ]
 819
 820 sw.bb1: br label %return
 821 sw.bb2: br label %return
 822 sw.bb3: br label %return
 823 sw.default: call void @exit(i32 1)
 824             unreachable
 825 return:
 826   %x = phi i32 [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
 827   ret i32 %x
 828
 829 ; CHECK-LABEL: @nodefaultnoholes(
 830 ; CHECK: @switch.table
 831 ; CHECK-NOT: switch i32
 832 }
 833
 834 ; This lookup table will have holes, so we need to test for the holes.
 835 define i32 @nodefaultwithholes(i32 %c) {
 836 entry:
 837   switch i32 %c, label %sw.default [
 838     i32 0, label %return
 839     i32 1, label %sw.bb1
 840     i32 2, label %sw.bb2
 841     i32 3, label %sw.bb3
 842     i32 5, label %sw.bb3
 843   ]
 844
 845 sw.bb1: br label %return
 846 sw.bb2: br label %return
 847 sw.bb3: br label %return
 848 sw.default: call void @exit(i32 1)
 849             unreachable
 850 return:
 851   %x = phi i32 [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
 852   ret i32 %x
 853
 854 ; CHECK-LABEL: @nodefaultwithholes(
 855 ; CHECK: entry:
 856 ; CHECK: br i1 %{{.*}}, label %switch.hole_check, label %sw.default
 857 ; CHECK: switch.hole_check:
 858 ; CHECK-NEXT: %switch.maskindex = trunc i32 %switch.tableidx to i8
 859 ; CHECK-NEXT: %switch.shifted = lshr i8 47, %switch.maskindex
 860 ; The mask is binary 101111.
 861 ; CHECK-NEXT: %switch.lobit = trunc i8 %switch.shifted to i1
 862 ; CHECK-NEXT: br i1 %switch.lobit, label %switch.lookup, label %sw.default
 863 ; CHECK-NOT: switch i32
 864 }
 865
 866 ; We don't build lookup tables with holes for switches with less than four cases.
 867 define i32 @threecasesholes(i32 %c) {
 868 entry:
 869   switch i32 %c, label %sw.default [
 870     i32 0, label %return
 871     i32 1, label %sw.bb1
 872     i32 3, label %sw.bb2
 873   ]
 874 sw.bb1: br label %return
 875 sw.bb2: br label %return
 876 sw.default: br label %return
 877 return:
 878   %x = phi i32 [ %c, %sw.default ], [ 5, %sw.bb2 ], [ 7, %sw.bb1 ], [ 9, %entry ]
 879   ret i32 %x
 880 ; CHECK-LABEL: @threecasesholes(
 881 ; CHECK: switch i32
 882 ; CHECK-NOT: @switch.table
 883 }
 884
 885 ; We build lookup tables for switches with three or more cases.
 886 define i32 @threecases(i32 %c) {
 887 entry:
 888   switch i32 %c, label %sw.default [
 889     i32 0, label %return
 890     i32 1, label %sw.bb1
 891     i32 2, label %sw.bb2
 892   ]
 893 sw.bb1: br label %return
 894 sw.bb2: br label %return
 895 sw.default: br label %return
 896 return:
 897   %x = phi i32 [ 3, %sw.default ], [ 5, %sw.bb2 ], [ 7, %sw.bb1 ], [ 10, %entry ]
 898   ret i32 %x
 899 ; CHECK-LABEL: @threecases(
 900 ; CHECK-NOT: switch i32
 901 ; CHECK: @switch.table
 902 }
 903
 904 ; We don't build tables for switches with two cases.
 905 define i32 @twocases(i32 %c) {
 906 entry:
 907   switch i32 %c, label %sw.default [
 908     i32 0, label %return
 909     i32 1, label %sw.bb1
 910   ]
 911 sw.bb1: br label %return
 912 sw.default: br label %return
 913 return:
 914   %x = phi i32 [ 3, %sw.default ], [ 7, %sw.bb1 ], [ 9, %entry ]
 915   ret i32 %x
 916 ; CHECK-LABEL: @twocases(
 917 ; CHECK-NOT: switch i32
 918 ; CHECK-NOT: @switch.table
 919 ; CHECK: %switch.selectcmp
 920 ; CHECK-NEXT: %switch.select
 921 ; CHECK-NEXT: %switch.selectcmp1
 922 ; CHECK-NEXT: %switch.select2
 923 }
 924
 925 ; Don't build tables for switches with TLS variables.
 926 @tls_a = thread_local global i32 0
 927 @tls_b = thread_local global i32 0
 928 @tls_c = thread_local global i32 0
 929 @tls_d = thread_local global i32 0
 930 define i32* @tls(i32 %x) {
 931 entry:
 932   switch i32 %x, label %sw.default [
 933     i32 0, label %return
 934     i32 1, label %sw.bb1
 935     i32 2, label %sw.bb2
 936   ]
 937 sw.bb1:
 938   br label %return
 939 sw.bb2:
 940   br label %return
 941 sw.default:
 942   br label %return
 943 return:
 944   %retval.0 = phi i32* [ @tls_d, %sw.default ], [ @tls_c, %sw.bb2 ], [ @tls_b, %sw.bb1 ], [ @tls_a, %entry ]
 945   ret i32* %retval.0
 946 ; CHECK-LABEL: @tls(
 947 ; CHECK: switch i32
 948 ; CHECK-NOT: @switch.table
 949 }
 950
 951 ; Don't build tables for switches with dllimport variables.
 952 @dllimport_a = external dllimport global [3x i32]
 953 @dllimport_b = external dllimport global [3x i32]
 954 @dllimport_c = external dllimport global [3x i32]
 955 @dllimport_d = external dllimport global [3x i32]
 956 define i32* @dllimport(i32 %x) {
 957 entry:
 958   switch i32 %x, label %sw.default [
 959     i32 0, label %return
 960     i32 1, label %sw.bb1
 961     i32 2, label %sw.bb2
 962   ]
 963 sw.bb1:
 964   br label %return
 965 sw.bb2:
 966   br label %return
 967 sw.default:
 968   br label %return
 969 return:
 970   %retval.0 = phi i32* [ getelementptr inbounds ([3 x i32]* @dllimport_d, i32 0, i32 0), %sw.default ],
 971                        [ getelementptr inbounds ([3 x i32]* @dllimport_c, i32 0, i32 0), %sw.bb2 ],
 972                        [ getelementptr inbounds ([3 x i32]* @dllimport_b, i32 0, i32 0), %sw.bb1 ],
 973                        [ getelementptr inbounds ([3 x i32]* @dllimport_a, i32 0, i32 0), %entry ]
 974   ret i32* %retval.0
 975 ; CHECK-LABEL: @dllimport(
 976 ; CHECK: switch i32
 977 ; CHECK-NOT: @switch.table
 978 }
 979
 980 ; We can use linear mapping.
 981 define i8 @linearmap1(i32 %c) {
 982 entry:
 983   switch i32 %c, label %sw.default [
 984     i32 10, label %return
 985     i32 11, label %sw.bb1
 986     i32 12, label %sw.bb2
 987     i32 13, label %sw.bb3
 988   ]
 989 sw.bb1: br label %return
 990 sw.bb2: br label %return
 991 sw.bb3: br label %return
 992 sw.default: br label %return
 993 return:
 994   %x = phi i8 [ 3, %sw.default ], [ 3, %sw.bb3 ], [ 8, %sw.bb2 ], [ 13, %sw.bb1 ], [ 18, %entry ]
 995   ret i8 %x
 996 ; CHECK-LABEL: @linearmap1(
 997 ; CHECK: entry:
 998 ; CHECK-NEXT: %switch.tableidx = sub i32 %c, 10
 999 ; CHECK: switch.lookup:
1000 ; CHECK-NEXT: %switch.idx.cast = trunc i32 %switch.tableidx to i8
1001 ; CHECK-NEXT: %switch.idx.mult = mul i8 %switch.idx.cast, -5
1002 ; CHECK-NEXT: %switch.offset = add i8 %switch.idx.mult, 18
1003 ; CHECK-NEXT: ret i8 %switch.offset
1004 }
1005
1006 ; Linear mapping in a different configuration.
1007 define i32 @linearmap2(i8 %c) {
1008 entry:
1009   switch i8 %c, label %sw.default [
1010     i8 -10, label %return
1011     i8 -11, label %sw.bb1
1012     i8 -12, label %sw.bb2
1013     i8 -13, label %sw.bb3
1014   ]
1015 sw.bb1: br label %return
1016 sw.bb2: br label %return
1017 sw.bb3: br label %return
1018 sw.default: br label %return
1019 return:
1020   %x = phi i32 [ 3, %sw.default ], [ 18, %sw.bb3 ], [ 19, %sw.bb2 ], [ 20, %sw.bb1 ], [ 21, %entry ]
1021   ret i32 %x
1022 ; CHECK-LABEL: @linearmap2(
1023 ; CHECK: entry:
1024 ; CHECK-NEXT: %switch.tableidx = sub i8 %c, -13
1025 ; CHECK: switch.lookup:
1026 ; CHECK-NEXT: %switch.idx.cast = zext i8 %switch.tableidx to i32
1027 ; CHECK-NEXT: %switch.offset = add i32 %switch.idx.cast, 18
1028 ; CHECK-NEXT: ret i32 %switch.offset
1029 }
1030
1031 ; Linear mapping with overflows.
1032 define i8 @linearmap3(i32 %c) {
1033 entry:
1034   switch i32 %c, label %sw.default [
1035     i32 10, label %return
1036     i32 11, label %sw.bb1
1037     i32 12, label %sw.bb2
1038     i32 13, label %sw.bb3
1039   ]
1040 sw.bb1: br label %return
1041 sw.bb2: br label %return
1042 sw.bb3: br label %return
1043 sw.default: br label %return
1044 return:
1045   %x = phi i8 [ 3, %sw.default ], [ 44, %sw.bb3 ], [ -56, %sw.bb2 ], [ 100, %sw.bb1 ], [ 0, %entry ]
1046   ret i8 %x
1047 ; CHECK-LABEL: @linearmap3(
1048 ; CHECK: entry:
1049 ; CHECK-NEXT: %switch.tableidx = sub i32 %c, 10
1050 ; CHECK: switch.lookup:
1051 ; CHECK-NEXT: %switch.idx.cast = trunc i32 %switch.tableidx to i8
1052 ; CHECK-NEXT: %switch.idx.mult = mul i8 %switch.idx.cast, 100
1053 ; CHECK-NEXT: ret i8 %switch.idx.mult
1054 }
1055
1056 ; Linear mapping with with multiplier 1 and offset 0.
1057 define i8 @linearmap4(i32 %c) {
1058 entry:
1059   switch i32 %c, label %sw.default [
1060     i32 -2, label %return
1061     i32 -1, label %sw.bb1
1062     i32 0, label %sw.bb2
1063     i32 1, label %sw.bb3
1064   ]
1065 sw.bb1: br label %return
1066 sw.bb2: br label %return
1067 sw.bb3: br label %return
1068 sw.default: br label %return
1069 return:
1070   %x = phi i8 [ 3, %sw.default ], [ 3, %sw.bb3 ], [ 2, %sw.bb2 ], [ 1, %sw.bb1 ], [ 0, %entry ]
1071   ret i8 %x
1072 ; CHECK-LABEL: @linearmap4(
1073 ; CHECK: entry:
1074 ; CHECK-NEXT: %switch.tableidx = sub i32 %c, -2
1075 ; CHECK: switch.lookup:
1076 ; CHECK-NEXT: %switch.idx.cast = trunc i32 %switch.tableidx to i8
1077 ; CHECK-NEXT: ret i8 %switch.idx.cast
1078 }
1079
1080 ; Reuse the inverted table range compare.
1081 define i32 @reuse_cmp1(i32 %x) {
1082 entry:
1083   switch i32 %x, label %sw.default [
1084     i32 0, label %sw.bb
1085     i32 1, label %sw.bb1
1086     i32 2, label %sw.bb2
1087     i32 3, label %sw.bb3
1088   ]
1089 sw.bb: br label %sw.epilog
1090 sw.bb1: br label %sw.epilog
1091 sw.bb2: br label %sw.epilog
1092 sw.bb3: br label %sw.epilog
1093 sw.default: br label %sw.epilog
1094 sw.epilog:
1095   %r.0 = phi i32 [ 0, %sw.default ], [ 13, %sw.bb3 ], [ 12, %sw.bb2 ], [ 11, %sw.bb1 ], [ 10, %sw.bb ]
1096   %cmp = icmp eq i32 %r.0, 0       ; This compare can be "replaced".
1097   br i1 %cmp, label %if.then, label %if.end
1098 if.then: br label %return
1099 if.end: br label %return
1100 return:
1101   %retval.0 = phi i32 [ 100, %if.then ], [ %r.0, %if.end ]
1102   ret i32 %retval.0
1103 ; CHECK-LABEL: @reuse_cmp1(
1104 ; CHECK: entry:
1105 ; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0
1106 ; CHECK-NEXT: [[C:%.+]] = icmp ult i32 %switch.tableidx, 4
1107 ; CHECK-NEXT: %inverted.cmp = xor i1 [[C]], true
1108 ; CHECK:      [[R:%.+]] = select i1 %inverted.cmp, i32 100, i32 {{.*}}
1109 ; CHECK-NEXT: ret i32 [[R]]
1110 }
1111
1112 ; Reuse the table range compare.
1113 define i32 @reuse_cmp2(i32 %x) {
1114 entry:
1115   switch i32 %x, label %sw.default [
1116     i32 0, label %sw.bb
1117     i32 1, label %sw.bb1
1118     i32 2, label %sw.bb2
1119     i32 3, label %sw.bb3
1120   ]
1121 sw.bb: br label %sw.epilog
1122 sw.bb1: br label %sw.epilog
1123 sw.bb2: br label %sw.epilog
1124 sw.bb3: br label %sw.epilog
1125 sw.default: br label %sw.epilog
1126 sw.epilog:
1127   %r.0 = phi i32 [ 4, %sw.default ], [ 3, %sw.bb3 ], [ 2, %sw.bb2 ], [ 1, %sw.bb1 ], [ 0, %sw.bb ]
1128   %cmp = icmp ne i32 %r.0, 4       ; This compare can be "replaced".
1129   br i1 %cmp, label %if.then, label %if.end
1130 if.then: br label %return
1131 if.end: br label %return
1132 return:
1133   %retval.0 = phi i32 [ %r.0, %if.then ], [ 100, %if.end ]
1134   ret i32 %retval.0
1135 ; CHECK-LABEL: @reuse_cmp2(
1136 ; CHECK: entry:
1137 ; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0
1138 ; CHECK-NEXT: [[C:%.+]] = icmp ult i32 %switch.tableidx, 4
1139 ; CHECK:      [[R:%.+]] = select i1 [[C]], i32 {{.*}}, i32 100
1140 ; CHECK-NEXT: ret i32 [[R]]
1141 }
1142
1143 ; Cannot reuse the table range compare, because the default value is the same
1144 ; as one of the case values.
1145 define i32 @no_reuse_cmp(i32 %x) {
1146 entry:
1147   switch i32 %x, label %sw.default [
1148     i32 0, label %sw.bb
1149     i32 1, label %sw.bb1
1150     i32 2, label %sw.bb2
1151     i32 3, label %sw.bb3
1152   ]
1153 sw.bb: br label %sw.epilog
1154 sw.bb1: br label %sw.epilog
1155 sw.bb2: br label %sw.epilog
1156 sw.bb3: br label %sw.epilog
1157 sw.default: br label %sw.epilog
1158 sw.epilog:
1159   %r.0 = phi i32 [ 12, %sw.default ], [ 13, %sw.bb3 ], [ 12, %sw.bb2 ], [ 11, %sw.bb1 ], [ 10, %sw.bb ]
1160   %cmp = icmp ne i32 %r.0, 0
1161   br i1 %cmp, label %if.then, label %if.end
1162 if.then: br label %return
1163 if.end: br label %return
1164 return:
1165   %retval.0 = phi i32 [ %r.0, %if.then ], [ 100, %if.end ]
1166   ret i32 %retval.0
1167 ; CHECK-LABEL: @no_reuse_cmp(
1168 ; CHECK:  [[S:%.+]] = select
1169 ; CHECK-NEXT:  %cmp = icmp ne i32 [[S]], 0
1170 ; CHECK-NEXT:  [[R:%.+]] = select i1 %cmp, i32 [[S]], i32 100
1171 ; CHECK-NEXT:  ret i32 [[R]]
1172 }
1173
1174 ; Cannot reuse the table range compare, because the phi at the switch merge
1175 ; point is not dominated by the switch.
1176 define i32 @no_reuse_cmp2(i32 %x, i32 %y) {
1177 entry:
1178   %ec = icmp ne i32 %y, 0
1179   br i1 %ec, label %switch.entry, label %sw.epilog
1180 switch.entry:
1181   switch i32 %x, label %sw.default [
1182     i32 0, label %sw.bb
1183     i32 1, label %sw.bb1
1184     i32 2, label %sw.bb2
1185     i32 3, label %sw.bb3
1186   ]
1187 sw.bb: br label %sw.epilog
1188 sw.bb1: br label %sw.epilog
1189 sw.bb2: br label %sw.epilog
1190 sw.bb3: br label %sw.epilog
1191 sw.default: br label %sw.epilog
1192 sw.epilog:
1193   %r.0 = phi i32 [100, %entry], [ 0, %sw.default ], [ 13, %sw.bb3 ], [ 12, %sw.bb2 ], [ 11, %sw.bb1 ], [ 10, %sw.bb ]
1194   %cmp = icmp eq i32 %r.0, 0       ; This compare can be "replaced".
1195   br i1 %cmp, label %if.then, label %if.end
1196 if.then: br label %return
1197 if.end: br label %return
1198 return:
1199   %retval.0 = phi i32 [ 100, %if.then ], [ %r.0, %if.end ]
1200   ret i32 %retval.0
1201 ; CHECK-LABEL: @no_reuse_cmp2(
1202 ; CHECK:  %r.0 = phi
1203 ; CHECK-NEXT:  %cmp = icmp eq i32 %r.0, 0
1204 ; CHECK-NEXT:  [[R:%.+]] = select i1 %cmp
1205 ; CHECK-NEXT:  ret i32 [[R]]
1206 }
1207
1208 define void @pr20210(i8 %x, i1 %y) {
1209 ; %z has uses outside of its BB or the phi it feeds into,
1210 ; so doing a table lookup and jumping directly to while.cond would
1211 ; cause %z to cease dominating all its uses.
1212
1213 entry:
1214   br i1 %y, label %sw, label %intermediate
1215
1216 sw:
1217   switch i8 %x, label %end [
1218     i8 7, label %intermediate
1219     i8 3, label %intermediate
1220     i8 2, label %intermediate
1221     i8 1, label %intermediate
1222     i8 0, label %intermediate
1223   ]
1224
1225 intermediate:
1226   %z = zext i8 %x to i32
1227   br label %while.cond
1228
1229 while.cond:
1230   %i = phi i32 [ %z, %intermediate ], [ %j, %while.body ]
1231   %b = icmp ne i32 %i, 7
1232   br i1 %b, label %while.body, label %while.end
1233
1234 while.body:
1235   %j = add i32 %i, 1
1236   br label %while.cond
1237
1238 while.end:
1239   call void @exit(i32 %z)
1240   unreachable
1241
1242 end:
1243   ret void
1244 ; CHECK-LABEL: @pr20210
1245 ; CHECK: switch i8 %x
1246 }