test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -simplifycfg -switch-to-lookup=true -keep-loops=false -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
   3 ; RUN: opt < %s -passes='simplify-cfg<no-keep-loops;switch-to-lookup>' -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
   4 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"
   5 target triple = "x86_64-unknown-linux-gnu"
   6
   7 ; The table for @f
   8 ; CHECK: @switch.table.f = private unnamed_addr constant [7 x i32] [i32 55, i32 123, i32 0, i32 -1, i32 27, i32 62, i32 1], align 4
   9
  10 ; The char table for char
  11 ; CHECK: @switch.table.char = private unnamed_addr constant [9 x i8] c"7{\00\FF\1B>\01!T", align 1
  12
  13 ; The float table for @h
  14 ; CHECK: @switch.table.h = private unnamed_addr constant [4 x float] [float 0x40091EB860000000, float 0x3FF3BE76C0000000, float 0x4012449BA0000000, float 0x4001AE1480000000], align 4
  15
  16 ; The table for @foostring
  17 ; CHECK: @switch.table.foostring = 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)], align 8
  18
  19 ; The table for @earlyreturncrash
  20 ; CHECK: @switch.table.earlyreturncrash = private unnamed_addr constant [4 x i32] [i32 42, i32 9, i32 88, i32 5], align 4
  21
  22 ; The table for @large
  23 ; CHECK: @switch.table.large = private unnamed_addr constant [199 x i32] [i32 1, i32 4, i32 9,
  24
  25 ; The table for @cprop
  26 ; CHECK: @switch.table.cprop = private unnamed_addr constant [7 x i32] [i32 5, i32 42, i32 126, i32 -452, i32 128, i32 6, i32 7], align 4
  27
  28 ; The table for @unreachable_case
  29 ; CHECK: @switch.table.unreachable_case = 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], align 4
  30
  31 ; A simple int-to-int selection switch.
  32 ; It is dense enough to be replaced by table lookup.
  33 ; The result is directly by a ret from an otherwise empty bb,
  34 ; so we return early, directly from the lookup bb.
  35
  36 define i32 @f(i32 %c) {
  37 ; CHECK-LABEL: @f(
  38 ; CHECK-NEXT:  entry:
  39 ; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], 42
  40 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 7
  41 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
  42 ; CHECK:       switch.lookup:
  43 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [7 x i32], [7 x i32]* @switch.table.f, i32 0, i32 [[SWITCH_TABLEIDX]]
  44 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
  45 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
  46 ; CHECK:       return:
  47 ; CHECK-NEXT:    ret i32 15
  48 ;
  49 entry:
  50   switch i32 %c, label %sw.default [
  51   i32 42, label %return
  52   i32 43, label %sw.bb1
  53   i32 44, label %sw.bb2
  54   i32 45, label %sw.bb3
  55   i32 46, label %sw.bb4
  56   i32 47, label %sw.bb5
  57   i32 48, label %sw.bb6
  58   ]
  59
  60 sw.bb1: br label %return
  61 sw.bb2: br label %return
  62 sw.bb3: br label %return
  63 sw.bb4: br label %return
  64 sw.bb5: br label %return
  65 sw.bb6: br label %return
  66 sw.default: br label %return
  67 return:
  68   %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 ]
  69   ret i32 %retval.0
  70
  71 }
  72
  73 ; Same thing, but with i8's
  74
  75 define i8 @char(i32 %c) {
  76 ; CHECK-LABEL: @char(
  77 ; CHECK-NEXT:  entry:
  78 ; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], 42
  79 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 9
  80 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
  81 ; CHECK:       switch.lookup:
  82 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [9 x i8], [9 x i8]* @switch.table.char, i32 0, i32 [[SWITCH_TABLEIDX]]
  83 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i8, i8* [[SWITCH_GEP]]
  84 ; CHECK-NEXT:    ret i8 [[SWITCH_LOAD]]
  85 ; CHECK:       return:
  86 ; CHECK-NEXT:    ret i8 15
  87 ;
  88 entry:
  89   switch i32 %c, label %sw.default [
  90   i32 42, label %return
  91   i32 43, label %sw.bb1
  92   i32 44, label %sw.bb2
  93   i32 45, label %sw.bb3
  94   i32 46, label %sw.bb4
  95   i32 47, label %sw.bb5
  96   i32 48, label %sw.bb6
  97   i32 49, label %sw.bb7
  98   i32 50, label %sw.bb8
  99   ]
 100
 101 sw.bb1: br label %return
 102 sw.bb2: br label %return
 103 sw.bb3: br label %return
 104 sw.bb4: br label %return
 105 sw.bb5: br label %return
 106 sw.bb6: br label %return
 107 sw.bb7: br label %return
 108 sw.bb8: br label %return
 109 sw.default: br label %return
 110 return:
 111   %retval.0 = phi i8 [ 15, %sw.default ], [ 84, %sw.bb8 ], [ 33, %sw.bb7 ], [ 1, %sw.bb6 ], [ 62, %sw.bb5 ], [ 27, %sw.bb4 ], [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
 112   ret i8 %retval.0
 113
 114 }
 115
 116 ; A switch used to initialize two variables, an i8 and a float.
 117
 118 declare void @dummy(i8 signext, float)
 119 define void @h(i32 %x) {
 120 ; CHECK-LABEL: @h(
 121 ; CHECK-NEXT:  entry:
 122 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
 123 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[SW_EPILOG:%.*]]
 124 ; CHECK:       switch.lookup:
 125 ; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i32 [[X]], 8
 126 ; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i32 89655594, [[SWITCH_SHIFTAMT]]
 127 ; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i32 [[SWITCH_DOWNSHIFT]] to i8
 128 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x float], [4 x float]* @switch.table.h, i32 0, i32 [[X]]
 129 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load float, float* [[SWITCH_GEP]]
 130 ; CHECK-NEXT:    br label [[SW_EPILOG]]
 131 ; CHECK:       sw.epilog:
 132 ; CHECK-NEXT:    [[A_0:%.*]] = phi i8 [ [[SWITCH_MASKED]], [[SWITCH_LOOKUP]] ], [ 7, [[ENTRY:%.*]] ]
 133 ; CHECK-NEXT:    [[B_0:%.*]] = phi float [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 0x4023FAE140000000, [[ENTRY]] ]
 134 ; CHECK-NEXT:    call void @dummy(i8 signext [[A_0]], float [[B_0]])
 135 ; CHECK-NEXT:    ret void
 136 ;
 137 entry:
 138   switch i32 %x, label %sw.default [
 139   i32 0, label %sw.epilog
 140   i32 1, label %sw.bb1
 141   i32 2, label %sw.bb2
 142   i32 3, label %sw.bb3
 143   ]
 144
 145 sw.bb1: br label %sw.epilog
 146 sw.bb2: br label %sw.epilog
 147 sw.bb3: br label %sw.epilog
 148 sw.default: br label %sw.epilog
 149
 150 sw.epilog:
 151   %a.0 = phi i8 [ 7, %sw.default ], [ 5, %sw.bb3 ], [ 88, %sw.bb2 ], [ 9, %sw.bb1 ], [ 42, %entry ]
 152   %b.0 = phi float [ 0x4023FAE140000000, %sw.default ], [ 0x4001AE1480000000, %sw.bb3 ], [ 0x4012449BA0000000, %sw.bb2 ], [ 0x3FF3BE76C0000000, %sw.bb1 ], [ 0x40091EB860000000, %entry ]
 153   call void @dummy(i8 signext %a.0, float %b.0)
 154   ret void
 155
 156 }
 157
 158
 159 ; Switch used to return a string.
 160
 161 @.str = private unnamed_addr constant [4 x i8] c"foo\00", align 1
 162 @.str1 = private unnamed_addr constant [4 x i8] c"bar\00", align 1
 163 @.str2 = private unnamed_addr constant [4 x i8] c"baz\00", align 1
 164 @.str3 = private unnamed_addr constant [4 x i8] c"qux\00", align 1
 165 @.str4 = private unnamed_addr constant [6 x i8] c"error\00", align 1
 166
 167 define i8* @foostring(i32 %x)  {
 168 ; CHECK-LABEL: @foostring(
 169 ; CHECK-NEXT:  entry:
 170 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
 171 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 172 ; CHECK:       switch.lookup:
 173 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i8*], [4 x i8*]* @switch.table.foostring, i32 0, i32 [[X]]
 174 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i8*, i8** [[SWITCH_GEP]]
 175 ; CHECK-NEXT:    ret i8* [[SWITCH_LOAD]]
 176 ; CHECK:       return:
 177 ; CHECK-NEXT:    ret i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str4, i64 0, i64 0)
 178 ;
 179 entry:
 180   switch i32 %x, label %sw.default [
 181   i32 0, label %return
 182   i32 1, label %sw.bb1
 183   i32 2, label %sw.bb2
 184   i32 3, label %sw.bb3
 185   ]
 186
 187 sw.bb1: br label %return
 188 sw.bb2: br label %return
 189 sw.bb3: br label %return
 190 sw.default: br label %return
 191
 192 return:
 193   %retval.0 = phi i8* [ getelementptr inbounds ([6 x i8], [6 x i8]* @.str4, i64 0, i64 0), %sw.default ],
 194   [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str3, i64 0, i64 0), %sw.bb3 ],
 195   [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str2, i64 0, i64 0), %sw.bb2 ],
 196   [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str1, i64 0, i64 0), %sw.bb1 ],
 197   [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), %entry ]
 198   ret i8* %retval.0
 199
 200 }
 201
 202 ; Switch used to initialize two values. The first value is returned, the second
 203 ; value is not used. This used to make the transformation generate illegal code.
 204
 205 define i32 @earlyreturncrash(i32 %x)  {
 206 ; CHECK-LABEL: @earlyreturncrash(
 207 ; CHECK-NEXT:  entry:
 208 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
 209 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[SW_EPILOG:%.*]]
 210 ; CHECK:       switch.lookup:
 211 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table.earlyreturncrash, i32 0, i32 [[X]]
 212 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
 213 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
 214 ; CHECK:       sw.epilog:
 215 ; CHECK-NEXT:    ret i32 7
 216 ;
 217 entry:
 218   switch i32 %x, label %sw.default [
 219   i32 0, label %sw.epilog
 220   i32 1, label %sw.bb1
 221   i32 2, label %sw.bb2
 222   i32 3, label %sw.bb3
 223   ]
 224
 225 sw.bb1: br label %sw.epilog
 226 sw.bb2: br label %sw.epilog
 227 sw.bb3: br label %sw.epilog
 228 sw.default: br label %sw.epilog
 229
 230 sw.epilog:
 231   %a.0 = phi i32 [ 7, %sw.default ], [ 5, %sw.bb3 ], [ 88, %sw.bb2 ], [ 9, %sw.bb1 ], [ 42, %entry ]
 232   %b.0 = phi i32 [ 10, %sw.default ], [ 5, %sw.bb3 ], [ 1, %sw.bb2 ], [ 4, %sw.bb1 ], [ 3, %entry ]
 233   ret i32 %a.0
 234
 235 }
 236
 237
 238 ; Example 7 from http://blog.regehr.org/archives/320
 239 ; It is not dense enough for a regular table, but the results
 240 ; can be packed into a bitmap.
 241
 242 define i32 @crud(i8 zeroext %c)  {
 243 ; CHECK-LABEL: @crud(
 244 ; CHECK-NEXT:  entry:
 245 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[C:%.*]], 33
 246 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOR_END:%.*]], label [[SWITCH_EARLY_TEST:%.*]]
 247 ; CHECK:       switch.early.test:
 248 ; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i8 [[C]], 34
 249 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i8 [[SWITCH_TABLEIDX]], 59
 250 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[LOR_END]]
 251 ; CHECK:       switch.lookup:
 252 ; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i8 [[SWITCH_TABLEIDX]] to i59
 253 ; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i59 [[SWITCH_CAST]], 1
 254 ; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i59 -288230375765830623, [[SWITCH_SHIFTAMT]]
 255 ; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i59 [[SWITCH_DOWNSHIFT]] to i1
 256 ; CHECK-NEXT:    br label [[LOR_END]]
 257 ; CHECK:       lor.end:
 258 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[SWITCH_MASKED]], [[SWITCH_LOOKUP]] ], [ false, [[SWITCH_EARLY_TEST]] ]
 259 ; CHECK-NEXT:    [[LOR_EXT:%.*]] = zext i1 [[TMP1]] to i32
 260 ; CHECK-NEXT:    ret i32 [[LOR_EXT]]
 261 ;
 262 entry:
 263   %cmp = icmp ult i8 %c, 33
 264   br i1 %cmp, label %lor.end, label %switch.early.test
 265
 266 switch.early.test:
 267   switch i8 %c, label %lor.rhs [
 268   i8 92, label %lor.end
 269   i8 62, label %lor.end
 270   i8 60, label %lor.end
 271   i8 59, label %lor.end
 272   i8 58, label %lor.end
 273   i8 46, label %lor.end
 274   i8 44, label %lor.end
 275   i8 34, label %lor.end
 276   i8 39, label %switch.edge
 277   ]
 278
 279 switch.edge: br label %lor.end
 280 lor.rhs: br label %lor.end
 281
 282 lor.end:
 283   %0 = phi i1 [ true, %switch.early.test ],
 284   [ false, %lor.rhs ],
 285   [ true, %entry ],
 286   [ true, %switch.early.test ],
 287   [ true, %switch.early.test ],
 288   [ true, %switch.early.test ],
 289   [ true, %switch.early.test ],
 290   [ true, %switch.early.test ],
 291   [ true, %switch.early.test ],
 292   [ true, %switch.early.test ],
 293   [ true, %switch.edge ]
 294   %lor.ext = zext i1 %0 to i32
 295   ret i32 %lor.ext
 296
 297 }
 298
 299 ; PR13946
 300 define i32 @overflow(i32 %type) {
 301 ; CHECK-LABEL: @overflow(
 302 ; CHECK-NEXT:  entry:
 303 ; CHECK-NEXT:    switch i32 [[TYPE:%.*]], label [[IF_END:%.*]] [
 304 ; CHECK-NEXT:    i32 3, label [[SW_BB3:%.*]]
 305 ; CHECK-NEXT:    i32 -2147483645, label [[SW_BB3]]
 306 ; CHECK-NEXT:    i32 1, label [[SW_BB1:%.*]]
 307 ; CHECK-NEXT:    i32 2, label [[SW_BB2:%.*]]
 308 ; CHECK-NEXT:    ]
 309 ; CHECK:       sw.bb1:
 310 ; CHECK-NEXT:    br label [[IF_END]]
 311 ; CHECK:       sw.bb2:
 312 ; CHECK-NEXT:    br label [[IF_END]]
 313 ; CHECK:       sw.bb3:
 314 ; CHECK-NEXT:    br label [[IF_END]]
 315 ; CHECK:       if.end:
 316 ; CHECK-NEXT:    [[DIRENT_TYPE_0:%.*]] = phi i32 [ 6, [[SW_BB3]] ], [ 5, [[SW_BB2]] ], [ 0, [[SW_BB1]] ], [ 3, [[ENTRY:%.*]] ]
 317 ; CHECK-NEXT:    ret i32 [[DIRENT_TYPE_0]]
 318 ;
 319 entry:
 320   switch i32 %type, label %sw.default [
 321   i32 -2147483648, label %sw.bb
 322   i32 0, label %sw.bb
 323   i32 1, label %sw.bb1
 324   i32 2, label %sw.bb2
 325   i32 -2147483645, label %sw.bb3
 326   i32 3, label %sw.bb3
 327   ]
 328
 329 sw.bb: br label %if.end
 330 sw.bb1: br label %if.end
 331 sw.bb2: br label %if.end
 332 sw.bb3: br label %if.end
 333 sw.default: br label %if.end
 334 if.else: br label %if.end
 335
 336 if.end:
 337   %dirent_type.0 = phi i32 [ 3, %sw.default ], [ 6, %sw.bb3 ], [ 5, %sw.bb2 ], [ 0, %sw.bb1 ], [ 3, %sw.bb ], [ 0, %if.else ]
 338   ret i32 %dirent_type.0
 339 }
 340
 341 ; PR13985
 342 define i1 @undef(i32 %tmp) {
 343 ; CHECK-LABEL: @undef(
 344 ; CHECK-NEXT:  bb:
 345 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[TMP:%.*]], 9
 346 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[BB3:%.*]]
 347 ; CHECK:       switch.lookup:
 348 ; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = trunc i32 [[TMP]] to i9
 349 ; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i9 [[SWITCH_CAST]], 1
 350 ; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i9 3, [[SWITCH_SHIFTAMT]]
 351 ; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i9 [[SWITCH_DOWNSHIFT]] to i1
 352 ; CHECK-NEXT:    ret i1 [[SWITCH_MASKED]]
 353 ; CHECK:       bb3:
 354 ; CHECK-NEXT:    ret i1 undef
 355 ;
 356 bb:
 357   switch i32 %tmp, label %bb3 [
 358   i32 0, label %bb1
 359   i32 1, label %bb1
 360   i32 7, label %bb2
 361   i32 8, label %bb2
 362   ]
 363
 364 bb1: br label %bb3
 365 bb2: br label %bb3
 366
 367 bb3:
 368   %tmp4 = phi i1 [ undef, %bb ], [ false, %bb2 ], [ true, %bb1 ]
 369   ret i1 %tmp4
 370 }
 371
 372 ; Also handle large switches that would be rejected by
 373 ; isValueEqualityComparison()
 374
 375 define i32 @large(i32 %x) {
 376 ; CHECK-LABEL: @large(
 377 ; CHECK-NEXT:  entry:
 378 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
 379 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[X]], -10
 380 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[CMP]], i32 [[MUL]], i32 [[X]]
 381 ; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[SPEC_SELECT]], 1
 382 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 199
 383 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 384 ; CHECK:       switch.lookup:
 385 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [199 x i32], [199 x i32]* @switch.table.large, i32 0, i32 [[SWITCH_TABLEIDX]]
 386 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
 387 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
 388 ; CHECK:       return:
 389 ; CHECK-NEXT:    ret i32 0
 390 ;
 391 entry:
 392   %cmp = icmp slt i32 %x, 0
 393   br i1 %cmp, label %if.then, label %if.end
 394
 395 if.then:
 396   %mul = mul i32 %x, -10
 397   br label %if.end
 398
 399 if.end:
 400   %x.addr.0 = phi i32 [ %mul, %if.then ], [ %x, %entry ]
 401   switch i32 %x.addr.0, label %return [
 402   i32 199, label %sw.bb203
 403   i32 1, label %sw.bb1
 404   i32 2, label %sw.bb2
 405   i32 3, label %sw.bb3
 406   i32 4, label %sw.bb4
 407   i32 5, label %sw.bb5
 408   i32 6, label %sw.bb6
 409   i32 7, label %sw.bb7
 410   i32 8, label %sw.bb8
 411   i32 9, label %sw.bb9
 412   i32 10, label %sw.bb10
 413   i32 11, label %sw.bb11
 414   i32 12, label %sw.bb12
 415   i32 13, label %sw.bb13
 416   i32 14, label %sw.bb14
 417   i32 15, label %sw.bb15
 418   i32 16, label %sw.bb16
 419   i32 17, label %sw.bb17
 420   i32 18, label %sw.bb18
 421   i32 19, label %sw.bb19
 422   i32 20, label %sw.bb20
 423   i32 21, label %sw.bb21
 424   i32 22, label %sw.bb22
 425   i32 23, label %sw.bb23
 426   i32 24, label %sw.bb24
 427   i32 25, label %sw.bb25
 428   i32 26, label %sw.bb26
 429   i32 27, label %sw.bb27
 430   i32 28, label %sw.bb28
 431   i32 29, label %sw.bb29
 432   i32 30, label %sw.bb30
 433   i32 31, label %sw.bb31
 434   i32 32, label %sw.bb32
 435   i32 33, label %sw.bb33
 436   i32 34, label %sw.bb34
 437   i32 35, label %sw.bb35
 438   i32 36, label %sw.bb37
 439   i32 37, label %sw.bb38
 440   i32 38, label %sw.bb39
 441   i32 39, label %sw.bb40
 442   i32 40, label %sw.bb41
 443   i32 41, label %sw.bb42
 444   i32 42, label %sw.bb43
 445   i32 43, label %sw.bb44
 446   i32 44, label %sw.bb45
 447   i32 45, label %sw.bb47
 448   i32 46, label %sw.bb48
 449   i32 47, label %sw.bb49
 450   i32 48, label %sw.bb50
 451   i32 49, label %sw.bb51
 452   i32 50, label %sw.bb52
 453   i32 51, label %sw.bb53
 454   i32 52, label %sw.bb54
 455   i32 53, label %sw.bb55
 456   i32 54, label %sw.bb56
 457   i32 55, label %sw.bb58
 458   i32 56, label %sw.bb59
 459   i32 57, label %sw.bb60
 460   i32 58, label %sw.bb61
 461   i32 59, label %sw.bb62
 462   i32 60, label %sw.bb63
 463   i32 61, label %sw.bb64
 464   i32 62, label %sw.bb65
 465   i32 63, label %sw.bb66
 466   i32 64, label %sw.bb67
 467   i32 65, label %sw.bb68
 468   i32 66, label %sw.bb69
 469   i32 67, label %sw.bb70
 470   i32 68, label %sw.bb71
 471   i32 69, label %sw.bb72
 472   i32 70, label %sw.bb73
 473   i32 71, label %sw.bb74
 474   i32 72, label %sw.bb76
 475   i32 73, label %sw.bb77
 476   i32 74, label %sw.bb78
 477   i32 75, label %sw.bb79
 478   i32 76, label %sw.bb80
 479   i32 77, label %sw.bb81
 480   i32 78, label %sw.bb82
 481   i32 79, label %sw.bb83
 482   i32 80, label %sw.bb84
 483   i32 81, label %sw.bb85
 484   i32 82, label %sw.bb86
 485   i32 83, label %sw.bb87
 486   i32 84, label %sw.bb88
 487   i32 85, label %sw.bb89
 488   i32 86, label %sw.bb90
 489   i32 87, label %sw.bb91
 490   i32 88, label %sw.bb92
 491   i32 89, label %sw.bb93
 492   i32 90, label %sw.bb94
 493   i32 91, label %sw.bb95
 494   i32 92, label %sw.bb96
 495   i32 93, label %sw.bb97
 496   i32 94, label %sw.bb98
 497   i32 95, label %sw.bb99
 498   i32 96, label %sw.bb100
 499   i32 97, label %sw.bb101
 500   i32 98, label %sw.bb102
 501   i32 99, label %sw.bb103
 502   i32 100, label %sw.bb104
 503   i32 101, label %sw.bb105
 504   i32 102, label %sw.bb106
 505   i32 103, label %sw.bb107
 506   i32 104, label %sw.bb108
 507   i32 105, label %sw.bb109
 508   i32 106, label %sw.bb110
 509   i32 107, label %sw.bb111
 510   i32 108, label %sw.bb112
 511   i32 109, label %sw.bb113
 512   i32 110, label %sw.bb114
 513   i32 111, label %sw.bb115
 514   i32 112, label %sw.bb116
 515   i32 113, label %sw.bb117
 516   i32 114, label %sw.bb118
 517   i32 115, label %sw.bb119
 518   i32 116, label %sw.bb120
 519   i32 117, label %sw.bb121
 520   i32 118, label %sw.bb122
 521   i32 119, label %sw.bb123
 522   i32 120, label %sw.bb124
 523   i32 121, label %sw.bb125
 524   i32 122, label %sw.bb126
 525   i32 123, label %sw.bb127
 526   i32 124, label %sw.bb128
 527   i32 125, label %sw.bb129
 528   i32 126, label %sw.bb130
 529   i32 127, label %sw.bb131
 530   i32 128, label %sw.bb132
 531   i32 129, label %sw.bb133
 532   i32 130, label %sw.bb134
 533   i32 131, label %sw.bb135
 534   i32 132, label %sw.bb136
 535   i32 133, label %sw.bb137
 536   i32 134, label %sw.bb138
 537   i32 135, label %sw.bb139
 538   i32 136, label %sw.bb140
 539   i32 137, label %sw.bb141
 540   i32 138, label %sw.bb142
 541   i32 139, label %sw.bb143
 542   i32 140, label %sw.bb144
 543   i32 141, label %sw.bb145
 544   i32 142, label %sw.bb146
 545   i32 143, label %sw.bb147
 546   i32 144, label %sw.bb148
 547   i32 145, label %sw.bb149
 548   i32 146, label %sw.bb150
 549   i32 147, label %sw.bb151
 550   i32 148, label %sw.bb152
 551   i32 149, label %sw.bb153
 552   i32 150, label %sw.bb154
 553   i32 151, label %sw.bb155
 554   i32 152, label %sw.bb156
 555   i32 153, label %sw.bb157
 556   i32 154, label %sw.bb158
 557   i32 155, label %sw.bb159
 558   i32 156, label %sw.bb160
 559   i32 157, label %sw.bb161
 560   i32 158, label %sw.bb162
 561   i32 159, label %sw.bb163
 562   i32 160, label %sw.bb164
 563   i32 161, label %sw.bb165
 564   i32 162, label %sw.bb166
 565   i32 163, label %sw.bb167
 566   i32 164, label %sw.bb168
 567   i32 165, label %sw.bb169
 568   i32 166, label %sw.bb170
 569   i32 167, label %sw.bb171
 570   i32 168, label %sw.bb172
 571   i32 169, label %sw.bb173
 572   i32 170, label %sw.bb174
 573   i32 171, label %sw.bb175
 574   i32 172, label %sw.bb176
 575   i32 173, label %sw.bb177
 576   i32 174, label %sw.bb178
 577   i32 175, label %sw.bb179
 578   i32 176, label %sw.bb180
 579   i32 177, label %sw.bb181
 580   i32 178, label %sw.bb182
 581   i32 179, label %sw.bb183
 582   i32 180, label %sw.bb184
 583   i32 181, label %sw.bb185
 584   i32 182, label %sw.bb186
 585   i32 183, label %sw.bb187
 586   i32 184, label %sw.bb188
 587   i32 185, label %sw.bb189
 588   i32 186, label %sw.bb190
 589   i32 187, label %sw.bb191
 590   i32 188, label %sw.bb192
 591   i32 189, label %sw.bb193
 592   i32 190, label %sw.bb194
 593   i32 191, label %sw.bb195
 594   i32 192, label %sw.bb196
 595   i32 193, label %sw.bb197
 596   i32 194, label %sw.bb198
 597   i32 195, label %sw.bb199
 598   i32 196, label %sw.bb200
 599   i32 197, label %sw.bb201
 600   i32 198, label %sw.bb202
 601   ]
 602
 603 sw.bb1: br label %return
 604 sw.bb2: br label %return
 605 sw.bb3: br label %return
 606 sw.bb4: br label %return
 607 sw.bb5: br label %return
 608 sw.bb6: br label %return
 609 sw.bb7: br label %return
 610 sw.bb8: br label %return
 611 sw.bb9: br label %return
 612 sw.bb10: br label %return
 613 sw.bb11: br label %return
 614 sw.bb12: br label %return
 615 sw.bb13: br label %return
 616 sw.bb14: br label %return
 617 sw.bb15: br label %return
 618 sw.bb16: br label %return
 619 sw.bb17: br label %return
 620 sw.bb18: br label %return
 621 sw.bb19: br label %return
 622 sw.bb20: br label %return
 623 sw.bb21: br label %return
 624 sw.bb22: br label %return
 625 sw.bb23: br label %return
 626 sw.bb24: br label %return
 627 sw.bb25: br label %return
 628 sw.bb26: br label %return
 629 sw.bb27: br label %return
 630 sw.bb28: br label %return
 631 sw.bb29: br label %return
 632 sw.bb30: br label %return
 633 sw.bb31: br label %return
 634 sw.bb32: br label %return
 635 sw.bb33: br label %return
 636 sw.bb34: br label %return
 637 sw.bb35: br label %return
 638 sw.bb37: br label %return
 639 sw.bb38: br label %return
 640 sw.bb39: br label %return
 641 sw.bb40: br label %return
 642 sw.bb41: br label %return
 643 sw.bb42: br label %return
 644 sw.bb43: br label %return
 645 sw.bb44: br label %return
 646 sw.bb45: br label %return
 647 sw.bb47: br label %return
 648 sw.bb48: br label %return
 649 sw.bb49: br label %return
 650 sw.bb50: br label %return
 651 sw.bb51: br label %return
 652 sw.bb52: br label %return
 653 sw.bb53: br label %return
 654 sw.bb54: br label %return
 655 sw.bb55: br label %return
 656 sw.bb56: br label %return
 657 sw.bb58: br label %return
 658 sw.bb59: br label %return
 659 sw.bb60: br label %return
 660 sw.bb61: br label %return
 661 sw.bb62: br label %return
 662 sw.bb63: br label %return
 663 sw.bb64: br label %return
 664 sw.bb65: br label %return
 665 sw.bb66: br label %return
 666 sw.bb67: br label %return
 667 sw.bb68: br label %return
 668 sw.bb69: br label %return
 669 sw.bb70: br label %return
 670 sw.bb71: br label %return
 671 sw.bb72: br label %return
 672 sw.bb73: br label %return
 673 sw.bb74: br label %return
 674 sw.bb76: br label %return
 675 sw.bb77: br label %return
 676 sw.bb78: br label %return
 677 sw.bb79: br label %return
 678 sw.bb80: br label %return
 679 sw.bb81: br label %return
 680 sw.bb82: br label %return
 681 sw.bb83: br label %return
 682 sw.bb84: br label %return
 683 sw.bb85: br label %return
 684 sw.bb86: br label %return
 685 sw.bb87: br label %return
 686 sw.bb88: br label %return
 687 sw.bb89: br label %return
 688 sw.bb90: br label %return
 689 sw.bb91: br label %return
 690 sw.bb92: br label %return
 691 sw.bb93: br label %return
 692 sw.bb94: br label %return
 693 sw.bb95: br label %return
 694 sw.bb96: br label %return
 695 sw.bb97: br label %return
 696 sw.bb98: br label %return
 697 sw.bb99: br label %return
 698 sw.bb100: br label %return
 699 sw.bb101: br label %return
 700 sw.bb102: br label %return
 701 sw.bb103: br label %return
 702 sw.bb104: br label %return
 703 sw.bb105: br label %return
 704 sw.bb106: br label %return
 705 sw.bb107: br label %return
 706 sw.bb108: br label %return
 707 sw.bb109: br label %return
 708 sw.bb110: br label %return
 709 sw.bb111: br label %return
 710 sw.bb112: br label %return
 711 sw.bb113: br label %return
 712 sw.bb114: br label %return
 713 sw.bb115: br label %return
 714 sw.bb116: br label %return
 715 sw.bb117: br label %return
 716 sw.bb118: br label %return
 717 sw.bb119: br label %return
 718 sw.bb120: br label %return
 719 sw.bb121: br label %return
 720 sw.bb122: br label %return
 721 sw.bb123: br label %return
 722 sw.bb124: br label %return
 723 sw.bb125: br label %return
 724 sw.bb126: br label %return
 725 sw.bb127: br label %return
 726 sw.bb128: br label %return
 727 sw.bb129: br label %return
 728 sw.bb130: br label %return
 729 sw.bb131: br label %return
 730 sw.bb132: br label %return
 731 sw.bb133: br label %return
 732 sw.bb134: br label %return
 733 sw.bb135: br label %return
 734 sw.bb136: br label %return
 735 sw.bb137: br label %return
 736 sw.bb138: br label %return
 737 sw.bb139: br label %return
 738 sw.bb140: br label %return
 739 sw.bb141: br label %return
 740 sw.bb142: br label %return
 741 sw.bb143: br label %return
 742 sw.bb144: br label %return
 743 sw.bb145: br label %return
 744 sw.bb146: br label %return
 745 sw.bb147: br label %return
 746 sw.bb148: br label %return
 747 sw.bb149: br label %return
 748 sw.bb150: br label %return
 749 sw.bb151: br label %return
 750 sw.bb152: br label %return
 751 sw.bb153: br label %return
 752 sw.bb154: br label %return
 753 sw.bb155: br label %return
 754 sw.bb156: br label %return
 755 sw.bb157: br label %return
 756 sw.bb158: br label %return
 757 sw.bb159: br label %return
 758 sw.bb160: br label %return
 759 sw.bb161: br label %return
 760 sw.bb162: br label %return
 761 sw.bb163: br label %return
 762 sw.bb164: br label %return
 763 sw.bb165: br label %return
 764 sw.bb166: br label %return
 765 sw.bb167: br label %return
 766 sw.bb168: br label %return
 767 sw.bb169: br label %return
 768 sw.bb170: br label %return
 769 sw.bb171: br label %return
 770 sw.bb172: br label %return
 771 sw.bb173: br label %return
 772 sw.bb174: br label %return
 773 sw.bb175: br label %return
 774 sw.bb176: br label %return
 775 sw.bb177: br label %return
 776 sw.bb178: br label %return
 777 sw.bb179: br label %return
 778 sw.bb180: br label %return
 779 sw.bb181: br label %return
 780 sw.bb182: br label %return
 781 sw.bb183: br label %return
 782 sw.bb184: br label %return
 783 sw.bb185: br label %return
 784 sw.bb186: br label %return
 785 sw.bb187: br label %return
 786 sw.bb188: br label %return
 787 sw.bb189: br label %return
 788 sw.bb190: br label %return
 789 sw.bb191: br label %return
 790 sw.bb192: br label %return
 791 sw.bb193: br label %return
 792 sw.bb194: br label %return
 793 sw.bb195: br label %return
 794 sw.bb196: br label %return
 795 sw.bb197: br label %return
 796 sw.bb198: br label %return
 797 sw.bb199: br label %return
 798 sw.bb200: br label %return
 799 sw.bb201: br label %return
 800 sw.bb202: br label %return
 801 sw.bb203: br label %return
 802
 803 return:
 804   %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 ]
 805   ret i32 %retval.0
 806 }
 807
 808 define i32 @cprop(i32 %x, i32 %y) {
 809 ; CHECK-LABEL: @cprop(
 810 ; CHECK-NEXT:  entry:
 811 ; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[X:%.*]], 1
 812 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 7
 813 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 814 ; CHECK:       switch.lookup:
 815 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [7 x i32], [7 x i32]* @switch.table.cprop, i32 0, i32 [[SWITCH_TABLEIDX]]
 816 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
 817 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
 818 ; CHECK:       return:
 819 ; CHECK-NEXT:    ret i32 123
 820 ;
 821 entry:
 822   switch i32 %x, label %sw.default [
 823   i32 1, label %return
 824   i32 2, label %sw.bb1
 825   i32 3, label %sw.bb2
 826   i32 4, label %sw.bb2
 827   i32 5, label %sw.bb2
 828   i32 6, label %sw.bb3
 829   i32 7, label %sw.bb3
 830   ]
 831
 832 sw.bb1: br label %return
 833
 834 sw.bb2:
 835   %and = and i32 %x, 1
 836   %and.ptr = inttoptr i32 %and to i8*
 837   %tobool = icmp ne i8* %and.ptr, null
 838   %cond = select i1 %tobool, i32 -123, i32 456
 839   %sub = sub nsw i32 %x, %cond
 840   br label %return
 841
 842 sw.bb3:
 843   %trunc = trunc i32 %x to i8
 844   %sext = sext i8 %trunc to i32
 845   %select.i = icmp sgt i32 %sext, 0
 846   %select = select i1 %select.i, i32 %sext, i32 %y
 847   br label %return
 848
 849 sw.default:
 850   br label %return
 851
 852 return:
 853   %retval.0 = phi i32 [ 123, %sw.default ], [ %select, %sw.bb3 ], [ %sub, %sw.bb2 ], [ 42, %sw.bb1 ], [ 5, %entry ]
 854   ret i32 %retval.0
 855
 856 }
 857
 858 define i32 @unreachable_case(i32 %x)  {
 859 ; CHECK-LABEL: @unreachable_case(
 860 ; CHECK-NEXT:  entry:
 861 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 9
 862 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 863 ; CHECK:       switch.lookup:
 864 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [9 x i32], [9 x i32]* @switch.table.unreachable_case, i32 0, i32 [[X]]
 865 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
 866 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
 867 ; CHECK:       return:
 868 ; CHECK-NEXT:    ret i32 2
 869 ;
 870 entry:
 871   switch i32 %x, label %sw.default [
 872   i32 0, label %sw.bb
 873   i32 1, label %sw.bb
 874   i32 2, label %sw.bb
 875   i32 3, label %sw.bb1
 876   i32 4, label %sw.bb2
 877   i32 5, label %sw.bb3
 878   i32 6, label %sw.bb3
 879   i32 7, label %sw.bb3
 880   i32 8, label %sw.bb3
 881   ]
 882
 883 sw.bb: br label %return
 884 sw.bb1: unreachable
 885 sw.bb2: br label %return
 886 sw.bb3: br label %return
 887 sw.default: br label %return
 888
 889 return:
 890   %retval.0 = phi i32 [ 1, %sw.bb3 ], [ -1, %sw.bb2 ], [ 0, %sw.bb ], [ 2, %sw.default ]
 891   ret i32 %retval.0
 892
 893 }
 894
 895 define i32 @unreachable_default(i32 %x)  {
 896 ; CHECK-LABEL: @unreachable_default(
 897 ; CHECK-NEXT:  entry:
 898 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table.unreachable_default, i32 0, i32 [[X:%.*]]
 899 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
 900 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
 901 ;
 902 entry:
 903   switch i32 %x, label %default [
 904   i32 0, label %bb0
 905   i32 1, label %bb1
 906   i32 2, label %bb2
 907   i32 3, label %bb3
 908   ]
 909
 910 bb0: br label %return
 911 bb1: br label %return
 912 bb2: br label %return
 913 bb3: br label %return
 914 default: unreachable
 915
 916 return:
 917   %retval = phi i32 [ 42, %bb0 ], [ 52, %bb1 ], [ 1, %bb2 ], [ 2, %bb3 ]
 918   ret i32 %retval
 919
 920 }
 921
 922 ; Don't create a table with illegal type
 923 define i96 @illegaltype(i32 %c) {
 924 ; CHECK-LABEL: @illegaltype(
 925 ; CHECK-NEXT:  entry:
 926 ; CHECK-NEXT:    switch i32 [[C:%.*]], label [[SW_DEFAULT:%.*]] [
 927 ; CHECK-NEXT:    i32 42, label [[RETURN:%.*]]
 928 ; CHECK-NEXT:    i32 43, label [[SW_BB1:%.*]]
 929 ; CHECK-NEXT:    i32 44, label [[SW_BB2:%.*]]
 930 ; CHECK-NEXT:    i32 45, label [[SW_BB3:%.*]]
 931 ; CHECK-NEXT:    i32 46, label [[SW_BB4:%.*]]
 932 ; CHECK-NEXT:    ]
 933 ; CHECK:       sw.bb1:
 934 ; CHECK-NEXT:    br label [[RETURN]]
 935 ; CHECK:       sw.bb2:
 936 ; CHECK-NEXT:    br label [[RETURN]]
 937 ; CHECK:       sw.bb3:
 938 ; CHECK-NEXT:    br label [[RETURN]]
 939 ; CHECK:       sw.bb4:
 940 ; CHECK-NEXT:    br label [[RETURN]]
 941 ; CHECK:       sw.default:
 942 ; CHECK-NEXT:    br label [[RETURN]]
 943 ; CHECK:       return:
 944 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i96 [ 15, [[SW_DEFAULT]] ], [ 27, [[SW_BB4]] ], [ -1, [[SW_BB3]] ], [ 0, [[SW_BB2]] ], [ 123, [[SW_BB1]] ], [ 55, [[ENTRY:%.*]] ]
 945 ; CHECK-NEXT:    ret i96 [[RETVAL_0]]
 946 ;
 947 entry:
 948   switch i32 %c, label %sw.default [
 949   i32 42, label %return
 950   i32 43, label %sw.bb1
 951   i32 44, label %sw.bb2
 952   i32 45, label %sw.bb3
 953   i32 46, label %sw.bb4
 954   ]
 955
 956 sw.bb1: br label %return
 957 sw.bb2: br label %return
 958 sw.bb3: br label %return
 959 sw.bb4: br label %return
 960 sw.default: br label %return
 961 return:
 962   %retval.0 = phi i96 [ 15, %sw.default ], [ 27, %sw.bb4 ], [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
 963   ret i96 %retval.0
 964
 965 }
 966
 967 ; If we can build a lookup table without any holes, we don't need a default result.
 968 declare void @exit(i32)
 969 define i32 @nodefaultnoholes(i32 %c) {
 970 ; CHECK-LABEL: @nodefaultnoholes(
 971 ; CHECK-NEXT:  entry:
 972 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[C:%.*]], 4
 973 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[SW_DEFAULT:%.*]]
 974 ; CHECK:       sw.default:
 975 ; CHECK-NEXT:    call void @exit(i32 1)
 976 ; CHECK-NEXT:    unreachable
 977 ; CHECK:       switch.lookup:
 978 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table.nodefaultnoholes, i32 0, i32 [[C]]
 979 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
 980 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
 981 ;
 982 entry:
 983   switch i32 %c, label %sw.default [
 984   i32 0, label %return
 985   i32 1, label %sw.bb1
 986   i32 2, label %sw.bb2
 987   i32 3, label %sw.bb3
 988   ]
 989
 990 sw.bb1: br label %return
 991 sw.bb2: br label %return
 992 sw.bb3: br label %return
 993 sw.default: call void @exit(i32 1)
 994   unreachable
 995 return:
 996   %x = phi i32 [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
 997   ret i32 %x
 998
 999 }
1000
1001 ; This lookup table will have holes, so we need to test for the holes.
1002 define i32 @nodefaultwithholes(i32 %c) {
1003 ; CHECK-LABEL: @nodefaultwithholes(
1004 ; CHECK-NEXT:  entry:
1005 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[C:%.*]], 6
1006 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_HOLE_CHECK:%.*]], label [[SW_DEFAULT:%.*]]
1007 ; CHECK:       sw.default:
1008 ; CHECK-NEXT:    call void @exit(i32 1)
1009 ; CHECK-NEXT:    unreachable
1010 ; CHECK:       switch.hole_check:
1011 ; CHECK-NEXT:    [[SWITCH_MASKINDEX:%.*]] = trunc i32 [[C]] to i8
1012 ; CHECK-NEXT:    [[SWITCH_SHIFTED:%.*]] = lshr i8 47, [[SWITCH_MASKINDEX]]
1013 ; CHECK-NEXT:    [[SWITCH_LOBIT:%.*]] = trunc i8 [[SWITCH_SHIFTED]] to i1
1014 ; CHECK-NEXT:    br i1 [[SWITCH_LOBIT]], label [[SWITCH_LOOKUP:%.*]], label [[SW_DEFAULT]]
1015 ; CHECK:       switch.lookup:
1016 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [6 x i32], [6 x i32]* @switch.table.nodefaultwithholes, i32 0, i32 [[C]]
1017 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
1018 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
1019 ;
1020 entry:
1021   switch i32 %c, label %sw.default [
1022   i32 0, label %return
1023   i32 1, label %sw.bb1
1024   i32 2, label %sw.bb2
1025   i32 3, label %sw.bb3
1026   i32 5, label %sw.bb3
1027   ]
1028
1029 sw.bb1: br label %return
1030 sw.bb2: br label %return
1031 sw.bb3: br label %return
1032 sw.default: call void @exit(i32 1)
1033   unreachable
1034 return:
1035   %x = phi i32 [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
1036   ret i32 %x
1037
1038 ; The mask is binary 101111.
1039 }
1040
1041 ; We don't build lookup tables with holes for switches with less than four cases.
1042 define i32 @threecasesholes(i32 %c) {
1043 ; CHECK-LABEL: @threecasesholes(
1044 ; CHECK-NEXT:  entry:
1045 ; CHECK-NEXT:    switch i32 [[C:%.*]], label [[SW_DEFAULT:%.*]] [
1046 ; CHECK-NEXT:    i32 0, label [[RETURN:%.*]]
1047 ; CHECK-NEXT:    i32 1, label [[SW_BB1:%.*]]
1048 ; CHECK-NEXT:    i32 3, label [[SW_BB2:%.*]]
1049 ; CHECK-NEXT:    ]
1050 ; CHECK:       sw.bb1:
1051 ; CHECK-NEXT:    br label [[RETURN]]
1052 ; CHECK:       sw.bb2:
1053 ; CHECK-NEXT:    br label [[RETURN]]
1054 ; CHECK:       sw.default:
1055 ; CHECK-NEXT:    br label [[RETURN]]
1056 ; CHECK:       return:
1057 ; CHECK-NEXT:    [[X:%.*]] = phi i32 [ [[C]], [[SW_DEFAULT]] ], [ 5, [[SW_BB2]] ], [ 7, [[SW_BB1]] ], [ 9, [[ENTRY:%.*]] ]
1058 ; CHECK-NEXT:    ret i32 [[X]]
1059 ;
1060 entry:
1061   switch i32 %c, label %sw.default [
1062   i32 0, label %return
1063   i32 1, label %sw.bb1
1064   i32 3, label %sw.bb2
1065   ]
1066 sw.bb1: br label %return
1067 sw.bb2: br label %return
1068 sw.default: br label %return
1069 return:
1070   %x = phi i32 [ %c, %sw.default ], [ 5, %sw.bb2 ], [ 7, %sw.bb1 ], [ 9, %entry ]
1071   ret i32 %x
1072 }
1073
1074 ; We build lookup tables for switches with three or more cases.
1075 define i32 @threecases(i32 %c) {
1076 ; CHECK-LABEL: @threecases(
1077 ; CHECK-NEXT:  entry:
1078 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[C:%.*]], 3
1079 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
1080 ; CHECK:       switch.lookup:
1081 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32], [3 x i32]* @switch.table.threecases, i32 0, i32 [[C]]
1082 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
1083 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
1084 ; CHECK:       return:
1085 ; CHECK-NEXT:    ret i32 3
1086 ;
1087 entry:
1088   switch i32 %c, label %sw.default [
1089   i32 0, label %return
1090   i32 1, label %sw.bb1
1091   i32 2, label %sw.bb2
1092   ]
1093 sw.bb1:
1094   br label %return
1095 sw.bb2:
1096   br label %return
1097 sw.default:
1098   br label %return
1099 return:
1100   %x = phi i32 [ 3, %sw.default ], [ 5, %sw.bb2 ], [ 7, %sw.bb1 ], [ 10, %entry ]
1101   ret i32 %x
1102 }
1103
1104 ; We don't build tables for switches with two cases.
1105 define i32 @twocases(i32 %c) {
1106 ; CHECK-LABEL: @twocases(
1107 ; CHECK-NEXT:  entry:
1108 ; CHECK-NEXT:    [[SWITCH_SELECTCMP:%.*]] = icmp eq i32 [[C:%.*]], 1
1109 ; CHECK-NEXT:    [[SWITCH_SELECT:%.*]] = select i1 [[SWITCH_SELECTCMP]], i32 7, i32 3
1110 ; CHECK-NEXT:    [[SWITCH_SELECTCMP1:%.*]] = icmp eq i32 [[C]], 0
1111 ; CHECK-NEXT:    [[SWITCH_SELECT2:%.*]] = select i1 [[SWITCH_SELECTCMP1]], i32 9, i32 [[SWITCH_SELECT]]
1112 ; CHECK-NEXT:    ret i32 [[SWITCH_SELECT2]]
1113 ;
1114 entry:
1115   switch i32 %c, label %sw.default [
1116   i32 0, label %return
1117   i32 1, label %sw.bb1
1118   ]
1119 sw.bb1:
1120   br label %return
1121 sw.default:
1122   br label %return
1123 return:
1124   %x = phi i32 [ 3, %sw.default ], [ 7, %sw.bb1 ], [ 9, %entry ]
1125   ret i32 %x
1126 }
1127
1128 ; Don't build tables for switches with TLS variables.
1129 @tls_a = thread_local global i32 0
1130 @tls_b = thread_local global i32 0
1131 @tls_c = thread_local global i32 0
1132 @tls_d = thread_local global i32 0
1133 define i32* @tls(i32 %x) {
1134 ; CHECK-LABEL: @tls(
1135 ; CHECK-NEXT:  entry:
1136 ; CHECK-NEXT:    switch i32 [[X:%.*]], label [[SW_DEFAULT:%.*]] [
1137 ; CHECK-NEXT:    i32 0, label [[RETURN:%.*]]
1138 ; CHECK-NEXT:    i32 1, label [[SW_BB1:%.*]]
1139 ; CHECK-NEXT:    i32 2, label [[SW_BB2:%.*]]
1140 ; CHECK-NEXT:    ]
1141 ; CHECK:       sw.bb1:
1142 ; CHECK-NEXT:    br label [[RETURN]]
1143 ; CHECK:       sw.bb2:
1144 ; CHECK-NEXT:    br label [[RETURN]]
1145 ; CHECK:       sw.default:
1146 ; CHECK-NEXT:    br label [[RETURN]]
1147 ; CHECK:       return:
1148 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32* [ @tls_d, [[SW_DEFAULT]] ], [ @tls_c, [[SW_BB2]] ], [ @tls_b, [[SW_BB1]] ], [ @tls_a, [[ENTRY:%.*]] ]
1149 ; CHECK-NEXT:    ret i32* [[RETVAL_0]]
1150 ;
1151 entry:
1152   switch i32 %x, label %sw.default [
1153   i32 0, label %return
1154   i32 1, label %sw.bb1
1155   i32 2, label %sw.bb2
1156   ]
1157 sw.bb1:
1158   br label %return
1159 sw.bb2:
1160   br label %return
1161 sw.default:
1162   br label %return
1163 return:
1164   %retval.0 = phi i32* [ @tls_d, %sw.default ], [ @tls_c, %sw.bb2 ], [ @tls_b, %sw.bb1 ], [ @tls_a, %entry ]
1165   ret i32* %retval.0
1166 }
1167
1168 ; Don't build tables for switches with dllimport variables.
1169 @dllimport_a = external dllimport global [3x i32]
1170 @dllimport_b = external dllimport global [3x i32]
1171 @dllimport_c = external dllimport global [3x i32]
1172 @dllimport_d = external dllimport global [3x i32]
1173 define i32* @dllimport(i32 %x) {
1174 ; CHECK-LABEL: @dllimport(
1175 ; CHECK-NEXT:  entry:
1176 ; CHECK-NEXT:    switch i32 [[X:%.*]], label [[SW_DEFAULT:%.*]] [
1177 ; CHECK-NEXT:    i32 0, label [[RETURN:%.*]]
1178 ; CHECK-NEXT:    i32 1, label [[SW_BB1:%.*]]
1179 ; CHECK-NEXT:    i32 2, label [[SW_BB2:%.*]]
1180 ; CHECK-NEXT:    ]
1181 ; CHECK:       sw.bb1:
1182 ; CHECK-NEXT:    br label [[RETURN]]
1183 ; CHECK:       sw.bb2:
1184 ; CHECK-NEXT:    br label [[RETURN]]
1185 ; CHECK:       sw.default:
1186 ; CHECK-NEXT:    br label [[RETURN]]
1187 ; CHECK:       return:
1188 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32* [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_d, i32 0, i32 0), [[SW_DEFAULT]] ], [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_c, i32 0, i32 0), [[SW_BB2]] ], [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_b, i32 0, i32 0), [[SW_BB1]] ], [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_a, i32 0, i32 0), [[ENTRY:%.*]] ]
1189 ; CHECK-NEXT:    ret i32* [[RETVAL_0]]
1190 ;
1191 entry:
1192   switch i32 %x, label %sw.default [
1193   i32 0, label %return
1194   i32 1, label %sw.bb1
1195   i32 2, label %sw.bb2
1196   ]
1197 sw.bb1:
1198   br label %return
1199 sw.bb2:
1200   br label %return
1201 sw.default:
1202   br label %return
1203 return:
1204   %retval.0 = phi i32* [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_d, i32 0, i32 0), %sw.default ],
1205   [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_c, i32 0, i32 0), %sw.bb2 ],
1206   [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_b, i32 0, i32 0), %sw.bb1 ],
1207   [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_a, i32 0, i32 0), %entry ]
1208   ret i32* %retval.0
1209 }
1210
1211 ; We can use linear mapping.
1212 define i8 @linearmap1(i32 %c) {
1213 ; CHECK-LABEL: @linearmap1(
1214 ; CHECK-NEXT:  entry:
1215 ; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], 10
1216 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 4
1217 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
1218 ; CHECK:       switch.lookup:
1219 ; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = trunc i32 [[SWITCH_TABLEIDX]] to i8
1220 ; CHECK-NEXT:    [[SWITCH_IDX_MULT:%.*]] = mul i8 [[SWITCH_IDX_CAST]], -5
1221 ; CHECK-NEXT:    [[SWITCH_OFFSET:%.*]] = add i8 [[SWITCH_IDX_MULT]], 18
1222 ; CHECK-NEXT:    ret i8 [[SWITCH_OFFSET]]
1223 ; CHECK:       return:
1224 ; CHECK-NEXT:    ret i8 3
1225 ;
1226 entry:
1227   switch i32 %c, label %sw.default [
1228   i32 10, label %return
1229   i32 11, label %sw.bb1
1230   i32 12, label %sw.bb2
1231   i32 13, label %sw.bb3
1232   ]
1233 sw.bb1: br label %return
1234 sw.bb2: br label %return
1235 sw.bb3: br label %return
1236 sw.default: br label %return
1237 return:
1238   %x = phi i8 [ 3, %sw.default ], [ 3, %sw.bb3 ], [ 8, %sw.bb2 ], [ 13, %sw.bb1 ], [ 18, %entry ]
1239   ret i8 %x
1240 }
1241
1242 ; Linear mapping in a different configuration.
1243 define i32 @linearmap2(i8 %c) {
1244 ; CHECK-LABEL: @linearmap2(
1245 ; CHECK-NEXT:  entry:
1246 ; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i8 [[C:%.*]], -13
1247 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i8 [[SWITCH_TABLEIDX]], 4
1248 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
1249 ; CHECK:       switch.lookup:
1250 ; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = zext i8 [[SWITCH_TABLEIDX]] to i32
1251 ; CHECK-NEXT:    [[SWITCH_OFFSET:%.*]] = add i32 [[SWITCH_IDX_CAST]], 18
1252 ; CHECK-NEXT:    ret i32 [[SWITCH_OFFSET]]
1253 ; CHECK:       return:
1254 ; CHECK-NEXT:    ret i32 3
1255 ;
1256 entry:
1257   switch i8 %c, label %sw.default [
1258   i8 -10, label %return
1259   i8 -11, label %sw.bb1
1260   i8 -12, label %sw.bb2
1261   i8 -13, label %sw.bb3
1262   ]
1263 sw.bb1: br label %return
1264 sw.bb2: br label %return
1265 sw.bb3: br label %return
1266 sw.default: br label %return
1267 return:
1268   %x = phi i32 [ 3, %sw.default ], [ 18, %sw.bb3 ], [ 19, %sw.bb2 ], [ 20, %sw.bb1 ], [ 21, %entry ]
1269   ret i32 %x
1270 }
1271
1272 ; Linear mapping with overflows.
1273 define i8 @linearmap3(i32 %c) {
1274 ; CHECK-LABEL: @linearmap3(
1275 ; CHECK-NEXT:  entry:
1276 ; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], 10
1277 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 4
1278 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
1279 ; CHECK:       switch.lookup:
1280 ; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = trunc i32 [[SWITCH_TABLEIDX]] to i8
1281 ; CHECK-NEXT:    [[SWITCH_IDX_MULT:%.*]] = mul i8 [[SWITCH_IDX_CAST]], 100
1282 ; CHECK-NEXT:    ret i8 [[SWITCH_IDX_MULT]]
1283 ; CHECK:       return:
1284 ; CHECK-NEXT:    ret i8 3
1285 ;
1286 entry:
1287   switch i32 %c, label %sw.default [
1288   i32 10, label %return
1289   i32 11, label %sw.bb1
1290   i32 12, label %sw.bb2
1291   i32 13, label %sw.bb3
1292   ]
1293 sw.bb1: br label %return
1294 sw.bb2: br label %return
1295 sw.bb3: br label %return
1296 sw.default: br label %return
1297 return:
1298   %x = phi i8 [ 3, %sw.default ], [ 44, %sw.bb3 ], [ -56, %sw.bb2 ], [ 100, %sw.bb1 ], [ 0, %entry ]
1299   ret i8 %x
1300 }
1301
1302 ; Linear mapping with with multiplier 1 and offset 0.
1303 define i8 @linearmap4(i32 %c) {
1304 ; CHECK-LABEL: @linearmap4(
1305 ; CHECK-NEXT:  entry:
1306 ; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], -2
1307 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 4
1308 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
1309 ; CHECK:       switch.lookup:
1310 ; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = trunc i32 [[SWITCH_TABLEIDX]] to i8
1311 ; CHECK-NEXT:    ret i8 [[SWITCH_IDX_CAST]]
1312 ; CHECK:       return:
1313 ; CHECK-NEXT:    ret i8 3
1314 ;
1315 entry:
1316   switch i32 %c, label %sw.default [
1317   i32 -2, label %return
1318   i32 -1, label %sw.bb1
1319   i32 0, label %sw.bb2
1320   i32 1, label %sw.bb3
1321   ]
1322 sw.bb1: br label %return
1323 sw.bb2: br label %return
1324 sw.bb3: br label %return
1325 sw.default: br label %return
1326 return:
1327   %x = phi i8 [ 3, %sw.default ], [ 3, %sw.bb3 ], [ 2, %sw.bb2 ], [ 1, %sw.bb1 ], [ 0, %entry ]
1328   ret i8 %x
1329 }
1330
1331 ; Reuse the inverted table range compare.
1332 define i32 @reuse_cmp1(i32 %x) {
1333 ; CHECK-LABEL: @reuse_cmp1(
1334 ; CHECK-NEXT:  entry:
1335 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
1336 ; CHECK-NEXT:    [[INVERTED_CMP:%.*]] = xor i1 [[TMP0]], true
1337 ; CHECK-NEXT:    [[SWITCH_OFFSET:%.*]] = add i32 [[X]], 10
1338 ; CHECK-NEXT:    [[R_0:%.*]] = select i1 [[TMP0]], i32 [[SWITCH_OFFSET]], i32 0
1339 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[R_0]], 0
1340 ; CHECK-NEXT:    [[DOTR_0:%.*]] = select i1 [[INVERTED_CMP]], i32 100, i32 [[R_0]]
1341 ; CHECK-NEXT:    ret i32 [[DOTR_0]]
1342 ;
1343 entry:
1344   switch i32 %x, label %sw.default [
1345   i32 0, label %sw.bb
1346   i32 1, label %sw.bb1
1347   i32 2, label %sw.bb2
1348   i32 3, label %sw.bb3
1349   ]
1350 sw.bb: br label %sw.epilog
1351 sw.bb1: br label %sw.epilog
1352 sw.bb2: br label %sw.epilog
1353 sw.bb3: br label %sw.epilog
1354 sw.default: br label %sw.epilog
1355 sw.epilog:
1356   %r.0 = phi i32 [ 0, %sw.default ], [ 13, %sw.bb3 ], [ 12, %sw.bb2 ], [ 11, %sw.bb1 ], [ 10, %sw.bb ]
1357   %cmp = icmp eq i32 %r.0, 0       ; This compare can be "replaced".
1358   br i1 %cmp, label %if.then, label %if.end
1359 if.then: br label %return
1360 if.end: br label %return
1361 return:
1362   %retval.0 = phi i32 [ 100, %if.then ], [ %r.0, %if.end ]
1363   ret i32 %retval.0
1364 }
1365
1366 ; Reuse the table range compare.
1367 define i32 @reuse_cmp2(i32 %x) {
1368 ; CHECK-LABEL: @reuse_cmp2(
1369 ; CHECK-NEXT:  entry:
1370 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
1371 ; CHECK-NEXT:    [[X_:%.*]] = select i1 [[TMP0]], i32 [[X]], i32 4
1372 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[X_]], 4
1373 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[TMP0]], i32 [[X_]], i32 100
1374 ; CHECK-NEXT:    ret i32 [[RETVAL_0]]
1375 ;
1376 entry:
1377   switch i32 %x, label %sw.default [
1378   i32 0, label %sw.bb
1379   i32 1, label %sw.bb1
1380   i32 2, label %sw.bb2
1381   i32 3, label %sw.bb3
1382   ]
1383 sw.bb: br label %sw.epilog
1384 sw.bb1: br label %sw.epilog
1385 sw.bb2: br label %sw.epilog
1386 sw.bb3: br label %sw.epilog
1387 sw.default: br label %sw.epilog
1388 sw.epilog:
1389   %r.0 = phi i32 [ 4, %sw.default ], [ 3, %sw.bb3 ], [ 2, %sw.bb2 ], [ 1, %sw.bb1 ], [ 0, %sw.bb ]
1390   %cmp = icmp ne i32 %r.0, 4       ; This compare can be "replaced".
1391   br i1 %cmp, label %if.then, label %if.end
1392 if.then: br label %return
1393 if.end: br label %return
1394 return:
1395   %retval.0 = phi i32 [ %r.0, %if.then ], [ 100, %if.end ]
1396   ret i32 %retval.0
1397 }
1398
1399 ; Cannot reuse the table range compare, because the default value is the same
1400 ; as one of the case values.
1401 define i32 @no_reuse_cmp(i32 %x) {
1402 ; CHECK-LABEL: @no_reuse_cmp(
1403 ; CHECK-NEXT:  entry:
1404 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
1405 ; CHECK-NEXT:    [[SWITCH_OFFSET:%.*]] = add i32 [[X]], 10
1406 ; CHECK-NEXT:    [[R_0:%.*]] = select i1 [[TMP0]], i32 [[SWITCH_OFFSET]], i32 12
1407 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[R_0]], 0
1408 ; CHECK-NEXT:    [[R_0_:%.*]] = select i1 [[CMP]], i32 [[R_0]], i32 100
1409 ; CHECK-NEXT:    ret i32 [[R_0_]]
1410 ;
1411 entry:
1412   switch i32 %x, label %sw.default [
1413   i32 0, label %sw.bb
1414   i32 1, label %sw.bb1
1415   i32 2, label %sw.bb2
1416   i32 3, label %sw.bb3
1417   ]
1418 sw.bb: br label %sw.epilog
1419 sw.bb1: br label %sw.epilog
1420 sw.bb2: br label %sw.epilog
1421 sw.bb3: br label %sw.epilog
1422 sw.default: br label %sw.epilog
1423 sw.epilog:
1424   %r.0 = phi i32 [ 12, %sw.default ], [ 13, %sw.bb3 ], [ 12, %sw.bb2 ], [ 11, %sw.bb1 ], [ 10, %sw.bb ]
1425   %cmp = icmp ne i32 %r.0, 0
1426   br i1 %cmp, label %if.then, label %if.end
1427 if.then: br label %return
1428 if.end: br label %return
1429 return:
1430   %retval.0 = phi i32 [ %r.0, %if.then ], [ 100, %if.end ]
1431   ret i32 %retval.0
1432 }
1433
1434 ; Cannot reuse the table range compare, because the phi at the switch merge
1435 ; point is not dominated by the switch.
1436 define i32 @no_reuse_cmp2(i32 %x, i32 %y) {
1437 ; CHECK-LABEL: @no_reuse_cmp2(
1438 ; CHECK-NEXT:  entry:
1439 ; CHECK-NEXT:    [[EC:%.*]] = icmp ne i32 [[Y:%.*]], 0
1440 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
1441 ; CHECK-NEXT:    [[SWITCH_OFFSET:%.*]] = add i32 [[X]], 10
1442 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[TMP0]], i32 [[SWITCH_OFFSET]], i32 0
1443 ; CHECK-NEXT:    [[R_0:%.*]] = select i1 [[EC]], i32 [[SPEC_SELECT]], i32 100
1444 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[R_0]], 0
1445 ; CHECK-NEXT:    [[DOTR_0:%.*]] = select i1 [[CMP]], i32 100, i32 [[R_0]]
1446 ; CHECK-NEXT:    ret i32 [[DOTR_0]]
1447 ;
1448 entry:
1449   %ec = icmp ne i32 %y, 0
1450   br i1 %ec, label %switch.entry, label %sw.epilog
1451 switch.entry:
1452   switch i32 %x, label %sw.default [
1453   i32 0, label %sw.bb
1454   i32 1, label %sw.bb1
1455   i32 2, label %sw.bb2
1456   i32 3, label %sw.bb3
1457   ]
1458 sw.bb: br label %sw.epilog
1459 sw.bb1: br label %sw.epilog
1460 sw.bb2: br label %sw.epilog
1461 sw.bb3: br label %sw.epilog
1462 sw.default: br label %sw.epilog
1463 sw.epilog:
1464   %r.0 = phi i32 [100, %entry], [ 0, %sw.default ], [ 13, %sw.bb3 ], [ 12, %sw.bb2 ], [ 11, %sw.bb1 ], [ 10, %sw.bb ]
1465   %cmp = icmp eq i32 %r.0, 0       ; This compare can be "replaced".
1466   br i1 %cmp, label %if.then, label %if.end
1467 if.then: br label %return
1468 if.end: br label %return
1469 return:
1470   %retval.0 = phi i32 [ 100, %if.then ], [ %r.0, %if.end ]
1471   ret i32 %retval.0
1472 }
1473
1474 define void @pr20210(i8 %x, i1 %y) {
1475 ; %z has uses outside of its BB or the phi it feeds into,
1476 ; so doing a table lookup and jumping directly to while.cond would
1477 ; cause %z to cease dominating all its uses.
1478 ; CHECK-LABEL: @pr20210(
1479 ; CHECK-NEXT:  entry:
1480 ; CHECK-NEXT:    br i1 [[Y:%.*]], label [[SW:%.*]], label [[INTERMEDIATE:%.*]]
1481 ; CHECK:       sw:
1482 ; CHECK-NEXT:    switch i8 [[X:%.*]], label [[END:%.*]] [
1483 ; CHECK-NEXT:    i8 7, label [[INTERMEDIATE]]
1484 ; CHECK-NEXT:    i8 3, label [[INTERMEDIATE]]
1485 ; CHECK-NEXT:    i8 2, label [[INTERMEDIATE]]
1486 ; CHECK-NEXT:    i8 1, label [[INTERMEDIATE]]
1487 ; CHECK-NEXT:    i8 0, label [[INTERMEDIATE]]
1488 ; CHECK-NEXT:    ]
1489 ; CHECK:       intermediate:
1490 ; CHECK-NEXT:    [[Z:%.*]] = zext i8 [[X]] to i32
1491 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
1492 ; CHECK:       while.cond:
1493 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[Z]], [[INTERMEDIATE]] ], [ [[J:%.*]], [[WHILE_BODY:%.*]] ]
1494 ; CHECK-NEXT:    [[B:%.*]] = icmp ne i32 [[I]], 7
1495 ; CHECK-NEXT:    br i1 [[B]], label [[WHILE_BODY]], label [[WHILE_END:%.*]]
1496 ; CHECK:       while.body:
1497 ; CHECK-NEXT:    [[J]] = add i32 [[I]], 1
1498 ; CHECK-NEXT:    br label [[WHILE_COND]]
1499 ; CHECK:       while.end:
1500 ; CHECK-NEXT:    call void @exit(i32 [[Z]])
1501 ; CHECK-NEXT:    unreachable
1502 ; CHECK:       end:
1503 ; CHECK-NEXT:    ret void
1504 ;
1505 entry:
1506   br i1 %y, label %sw, label %intermediate
1507
1508 sw:
1509   switch i8 %x, label %end [
1510   i8 7, label %intermediate
1511   i8 3, label %intermediate
1512   i8 2, label %intermediate
1513   i8 1, label %intermediate
1514   i8 0, label %intermediate
1515   ]
1516
1517 intermediate:
1518   %z = zext i8 %x to i32
1519   br label %while.cond
1520
1521 while.cond:
1522   %i = phi i32 [ %z, %intermediate ], [ %j, %while.body ]
1523   %b = icmp ne i32 %i, 7
1524   br i1 %b, label %while.body, label %while.end
1525
1526 while.body:
1527   %j = add i32 %i, 1
1528   br label %while.cond
1529
1530 while.end:
1531   call void @exit(i32 %z)
1532   unreachable
1533
1534 end:
1535   ret void
1536 }
1537
1538 ; Make sure we do not crash due to trying to generate an unguarded
1539 ; lookup (since i3 can only hold values in the range of explicit
1540 ; values) and simultaneously trying to generate a branch to deal with
1541 ; the fact that we have holes in the range.
1542 define i32 @covered_switch_with_bit_tests(i3) {
1543 ; CHECK-LABEL: @covered_switch_with_bit_tests(
1544 ; CHECK-NEXT:  entry:
1545 ; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i3 [[TMP0:%.*]], -4
1546 ; CHECK-NEXT:    [[SWITCH_MASKINDEX:%.*]] = zext i3 [[SWITCH_TABLEIDX]] to i8
1547 ; CHECK-NEXT:    [[SWITCH_SHIFTED:%.*]] = lshr i8 -61, [[SWITCH_MASKINDEX]]
1548 ; CHECK-NEXT:    [[SWITCH_LOBIT:%.*]] = trunc i8 [[SWITCH_SHIFTED]] to i1
1549 ; CHECK-NEXT:    br i1 [[SWITCH_LOBIT]], label [[SWITCH_LOOKUP:%.*]], label [[L6:%.*]]
1550 ; CHECK:       switch.lookup:
1551 ; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i3 [[SWITCH_TABLEIDX]] to i4
1552 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i32], [8 x i32]* @switch.table.covered_switch_with_bit_tests, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]]
1553 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
1554 ; CHECK-NEXT:    br label [[L6]]
1555 ; CHECK:       l6:
1556 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ]
1557 ; CHECK-NEXT:    ret i32 [[R]]
1558 ;
1559 entry:
1560   switch i3 %0, label %l6 [
1561   i3 -3, label %l5
1562   i3 -4, label %l5
1563   i3 3, label %l1
1564   i3 2, label %l1
1565   ]
1566
1567 l1: br label %l2
1568
1569 l2:
1570   %x = phi i32 [ 1, %l1 ], [ 2, %l5 ]
1571   br label %l6
1572
1573 l5: br label %l2
1574
1575 l6:
1576   %r = phi i32 [ %x, %l2 ], [ 0, %entry ]
1577   ret i32 %r
1578 }
1579
1580 ; Speculation depth must be limited to avoid a zero-cost instruction cycle.
1581
1582 define i32 @PR26308(i1 %B, i64 %load) {
1583 ; CHECK-LABEL: @PR26308(
1584 ; CHECK-NEXT:  entry:
1585 ; CHECK-NEXT:    br label [[CLEANUP4:%.*]]
1586 ; CHECK:       cleanup4:
1587 ; CHECK-NEXT:    br label [[CLEANUP4]]
1588 ;
1589 entry:
1590   br label %while.body
1591
1592 while.body:
1593   br label %cleanup
1594
1595 cleanup:
1596   %cleanup.dest.slot.0 = phi i1 [ false, %while.body ]
1597   br i1 %cleanup.dest.slot.0, label %for.cond, label %cleanup4
1598
1599 for.cond:
1600   %e.0 = phi i64* [ undef, %cleanup ], [ %incdec.ptr, %for.cond2 ]
1601   %pi = ptrtoint i64* %e.0 to i64
1602   %incdec.ptr = getelementptr inbounds i64, i64* %e.0, i64 1
1603   br label %for.cond2
1604
1605 for.cond2:
1606   %storemerge = phi i64 [ %pi, %for.cond ], [ %load, %for.cond2 ]
1607   br i1 %B, label %for.cond2, label %for.cond
1608
1609 cleanup4:
1610   br label %while.body
1611 }
1612
1613 declare void @throw(i1)
1614
1615 define void @wineh_test(i64 %val) personality i32 (...)* @__CxxFrameHandler3 {
1616 ; CHECK-LABEL: @wineh_test(
1617 ; CHECK-NEXT:  entry:
1618 ; CHECK-NEXT:    invoke void @throw(i1 false)
1619 ; CHECK-NEXT:    to label [[UNREACHABLE:%.*]] unwind label [[CLEANUP1:%.*]]
1620 ; CHECK:       unreachable:
1621 ; CHECK-NEXT:    unreachable
1622 ; CHECK:       cleanup1:
1623 ; CHECK-NEXT:    [[CLEANUPPAD1:%.*]] = cleanuppad within none []
1624 ; CHECK-NEXT:    switch i64 [[VAL:%.*]], label [[CLEANUPDONE2:%.*]] [
1625 ; CHECK-NEXT:    i64 0, label [[CLEANUPDONE1:%.*]]
1626 ; CHECK-NEXT:    i64 1, label [[CLEANUPDONE1]]
1627 ; CHECK-NEXT:    i64 6, label [[CLEANUPDONE1]]
1628 ; CHECK-NEXT:    ]
1629 ; CHECK:       cleanupdone1:
1630 ; CHECK-NEXT:    cleanupret from [[CLEANUPPAD1]] unwind label [[CLEANUP2:%.*]]
1631 ; CHECK:       cleanupdone2:
1632 ; CHECK-NEXT:    cleanupret from [[CLEANUPPAD1]] unwind label [[CLEANUP2]]
1633 ; CHECK:       cleanup2:
1634 ; CHECK-NEXT:    [[PHI:%.*]] = phi i1 [ true, [[CLEANUPDONE1]] ], [ false, [[CLEANUPDONE2]] ]
1635 ; CHECK-NEXT:    [[CLEANUPPAD2:%.*]] = cleanuppad within none []
1636 ; CHECK-NEXT:    call void @throw(i1 [[PHI]]) [ "funclet"(token [[CLEANUPPAD2]]) ]
1637 ; CHECK-NEXT:    unreachable
1638 ;
1639 entry:
1640   invoke void @throw(i1 false)
1641   to label %unreachable unwind label %cleanup1
1642
1643 unreachable:
1644   unreachable
1645
1646 cleanup1:
1647   %cleanuppad1 = cleanuppad within none []
1648   switch i64 %val, label %cleanupdone2 [
1649   i64 0, label %cleanupdone1
1650   i64 1, label %cleanupdone1
1651   i64 6, label %cleanupdone1
1652   ]
1653
1654 cleanupdone1:
1655   cleanupret from %cleanuppad1 unwind label %cleanup2
1656
1657 cleanupdone2:
1658   cleanupret from %cleanuppad1 unwind label %cleanup2
1659
1660 cleanup2:
1661   %phi = phi i1 [ true, %cleanupdone1 ], [ false, %cleanupdone2 ]
1662   %cleanuppad2 = cleanuppad within none []
1663   call void @throw(i1 %phi) [ "funclet"(token %cleanuppad2) ]
1664   unreachable
1665 }
1666
1667 declare i32 @__CxxFrameHandler3(...)