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.table.1 = private unnamed_addr constant [4 x float] [float 0x40091EB860000000, float 0x3FF3BE76C0000000, float 0x4012449BA0000000, float 0x4001AE1480000000] 11 12 ; The table for @foostring 13 ; CHECK: @switch.table.2 = private unnamed_addr constant [4 x i8*] [i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str1, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str2, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str3, i64 0, i64 0)] 14 15 ; The table for @earlyreturncrash 16 ; CHECK: @switch.table.3 = private unnamed_addr constant [4 x i32] [i32 42, i32 9, i32 88, i32 5] 17 18 ; The table for @large. 19 ; CHECK: @switch.table.4 = private unnamed_addr constant [199 x i32] [i32 1, i32 4, i32 9, 20 21 ; The table for @cprop 22 ; CHECK: @switch.table.5 = private unnamed_addr constant [7 x i32] [i32 5, i32 42, i32 126, i32 -452, i32 128, i32 6, i32 7] 23 24 ; The table for @unreachable_case 25 ; CHECK: @switch.table.6 = private unnamed_addr constant [9 x i32] [i32 0, i32 0, i32 0, i32 2, i32 -1, i32 1, i32 1, i32 1, i32 1] 26 27 ; A simple int-to-int selection switch. 28 ; It is dense enough to be replaced by table lookup. 29 ; The result is directly by a ret from an otherwise empty bb, 30 ; so we return early, directly from the lookup bb. 31 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], [7 x i32]* @switch.table, i32 0, i32 %switch.tableidx 62 ; CHECK-NEXT: %switch.load = load i32, i32* %switch.gep 63 ; CHECK-NEXT: ret i32 %switch.load 64 ; CHECK: return: 65 ; CHECK-NEXT: ret i32 15 66 } 67 68 ; A switch used to initialize two variables, an i8 and a float. 69 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], [4 x float]* @switch.table.1, i32 0, i32 %switch.tableidx 101 ; CHECK-NEXT: %switch.load = load float, float* %switch.gep 102 ; CHECK-NEXT: br label %sw.epilog 103 ; CHECK: sw.epilog: 104 ; CHECK-NEXT: %a.0 = phi i8 [ %switch.masked, %switch.lookup ], [ 7, %entry ] 105 ; CHECK-NEXT: %b.0 = phi float [ %switch.load, %switch.lookup ], [ 0x4023FAE140000000, %entry ] 106 ; CHECK-NEXT: call void @dummy(i8 signext %a.0, float %b.0) 107 ; CHECK-NEXT: ret void 108 } 109 110 111 ; Switch used to return a string. 112 113 @.str = private unnamed_addr constant [4 x i8] c"foo\00", align 1 114 @.str1 = private unnamed_addr constant [4 x i8] c"bar\00", align 1 115 @.str2 = private unnamed_addr constant [4 x i8] c"baz\00", align 1 116 @.str3 = private unnamed_addr constant [4 x i8] c"qux\00", align 1 117 @.str4 = private unnamed_addr constant [6 x i8] c"error\00", align 1 118 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], [6 x i8]* @.str4, i64 0, i64 0), %sw.default ], 135 [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str3, i64 0, i64 0), %sw.bb3 ], 136 [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str2, i64 0, i64 0), %sw.bb2 ], 137 [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str1, i64 0, i64 0), %sw.bb1 ], 138 [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), %entry ] 139 ret i8* %retval.0 140 141 ; CHECK-LABEL: @foostring( 142 ; CHECK: entry: 143 ; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0 144 ; CHECK-NEXT: %0 = icmp ult i32 %switch.tableidx, 4 145 ; CHECK-NEXT: br i1 %0, label %switch.lookup, label %return 146 ; CHECK: switch.lookup: 147 ; CHECK-NEXT: %switch.gep = getelementptr inbounds [4 x i8*], [4 x i8*]* @switch.table.2, i32 0, i32 %switch.tableidx 148 ; CHECK-NEXT: %switch.load = load i8*, i8** %switch.gep 149 ; CHECK-NEXT: ret i8* %switch.load 150 } 151 152 ; Switch used to initialize two values. The first value is returned, the second 153 ; value is not used. This used to make the transformation generate illegal code. 154 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], [4 x i32]* @switch.table.3, i32 0, i32 %switch.tableidx 177 ; CHECK-NEXT: %switch.load = load i32, i32* %switch.gep 178 ; CHECK-NEXT: ret i32 %switch.load 179 ; CHECK: sw.epilog: 180 ; CHECK-NEXT: ret i32 7 181 } 182 183 184 ; Example 7 from http://blog.regehr.org/archives/320 185 ; It is not dense enough for a regular table, but the results 186 ; can be packed into a bitmap. 187 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], [7 x i32]* @switch.table.5, i32 0, i32 %switch.tableidx 753 } 754 755 define i32 @unreachable_case(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: br label %return 774 775 return: 776 %retval.0 = phi i32 [ 1, %sw.bb3 ], [ -1, %sw.bb2 ], [ 0, %sw.bb ], [ 2, %sw.default ] 777 ret i32 %retval.0 778 779 ; CHECK-LABEL: @unreachable_case( 780 ; CHECK: switch.lookup: 781 ; CHECK: getelementptr inbounds [9 x i32], [9 x i32]* @switch.table.6, i32 0, i32 %switch.tableidx 782 } 783 784 define i32 @unreachable_default(i32 %x) { 785 entry: 786 switch i32 %x, label %default [ 787 i32 0, label %bb0 788 i32 1, label %bb1 789 i32 2, label %bb2 790 i32 3, label %bb3 791 ] 792 793 bb0: br label %return 794 bb1: br label %return 795 bb2: br label %return 796 bb3: br label %return 797 default: unreachable 798 799 return: 800 %retval = phi i32 [ 42, %bb0 ], [ 52, %bb1 ], [ 1, %bb2 ], [ 2, %bb3 ] 801 ret i32 %retval 802 803 ; CHECK-LABEL: @unreachable_default( 804 ; CHECK: entry: 805 ; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0 806 ; CHECK-NOT: icmp 807 ; CHECK-NOT: br 1i 808 ; CHECK-NEXT: %switch.gep = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table.7, i32 0, i32 %switch.tableidx 809 ; CHECK-NEXT: %switch.load = load i32, i32* %switch.gep 810 ; CHECK-NEXT: ret i32 %switch.load 811 } 812 813 ; Don't create a table with illegal type 814 define i96 @illegaltype(i32 %c) { 815 entry: 816 switch i32 %c, label %sw.default [ 817 i32 42, label %return 818 i32 43, label %sw.bb1 819 i32 44, label %sw.bb2 820 i32 45, label %sw.bb3 821 i32 46, label %sw.bb4 822 ] 823 824 sw.bb1: br label %return 825 sw.bb2: br label %return 826 sw.bb3: br label %return 827 sw.bb4: br label %return 828 sw.default: br label %return 829 return: 830 %retval.0 = phi i96 [ 15, %sw.default ], [ 27, %sw.bb4 ], [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ] 831 ret i96 %retval.0 832 833 ; CHECK-LABEL: @illegaltype( 834 ; CHECK-NOT: @switch.table 835 ; CHECK: switch i32 %c 836 } 837 838 ; If we can build a lookup table without any holes, we don't need a default result. 839 declare void @exit(i32) 840 define i32 @nodefaultnoholes(i32 %c) { 841 entry: 842 switch i32 %c, label %sw.default [ 843 i32 0, label %return 844 i32 1, label %sw.bb1 845 i32 2, label %sw.bb2 846 i32 3, label %sw.bb3 847 ] 848 849 sw.bb1: br label %return 850 sw.bb2: br label %return 851 sw.bb3: br label %return 852 sw.default: call void @exit(i32 1) 853 unreachable 854 return: 855 %x = phi i32 [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ] 856 ret i32 %x 857 858 ; CHECK-LABEL: @nodefaultnoholes( 859 ; CHECK: @switch.table 860 ; CHECK-NOT: switch i32 861 } 862 863 ; This lookup table will have holes, so we need to test for the holes. 864 define i32 @nodefaultwithholes(i32 %c) { 865 entry: 866 switch i32 %c, label %sw.default [ 867 i32 0, label %return 868 i32 1, label %sw.bb1 869 i32 2, label %sw.bb2 870 i32 3, label %sw.bb3 871 i32 5, label %sw.bb3 872 ] 873 874 sw.bb1: br label %return 875 sw.bb2: br label %return 876 sw.bb3: br label %return 877 sw.default: call void @exit(i32 1) 878 unreachable 879 return: 880 %x = phi i32 [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ] 881 ret i32 %x 882 883 ; CHECK-LABEL: @nodefaultwithholes( 884 ; CHECK: entry: 885 ; CHECK: br i1 %{{.*}}, label %switch.hole_check, label %sw.default 886 ; CHECK: switch.hole_check: 887 ; CHECK-NEXT: %switch.maskindex = trunc i32 %switch.tableidx to i8 888 ; CHECK-NEXT: %switch.shifted = lshr i8 47, %switch.maskindex 889 ; The mask is binary 101111. 890 ; CHECK-NEXT: %switch.lobit = trunc i8 %switch.shifted to i1 891 ; CHECK-NEXT: br i1 %switch.lobit, label %switch.lookup, label %sw.default 892 ; CHECK-NOT: switch i32 893 } 894 895 ; We don't build lookup tables with holes for switches with less than four cases. 896 define i32 @threecasesholes(i32 %c) { 897 entry: 898 switch i32 %c, label %sw.default [ 899 i32 0, label %return 900 i32 1, label %sw.bb1 901 i32 3, label %sw.bb2 902 ] 903 sw.bb1: br label %return 904 sw.bb2: br label %return 905 sw.default: br label %return 906 return: 907 %x = phi i32 [ %c, %sw.default ], [ 5, %sw.bb2 ], [ 7, %sw.bb1 ], [ 9, %entry ] 908 ret i32 %x 909 ; CHECK-LABEL: @threecasesholes( 910 ; CHECK: switch i32 911 ; CHECK-NOT: @switch.table 912 } 913 914 ; We build lookup tables for switches with three or more cases. 915 define i32 @threecases(i32 %c) { 916 entry: 917 switch i32 %c, label %sw.default [ 918 i32 0, label %return 919 i32 1, label %sw.bb1 920 i32 2, label %sw.bb2 921 ] 922 sw.bb1: br label %return 923 sw.bb2: br label %return 924 sw.default: br label %return 925 return: 926 %x = phi i32 [ 3, %sw.default ], [ 5, %sw.bb2 ], [ 7, %sw.bb1 ], [ 10, %entry ] 927 ret i32 %x 928 ; CHECK-LABEL: @threecases( 929 ; CHECK-NOT: switch i32 930 ; CHECK: @switch.table 931 } 932 933 ; We don't build tables for switches with two cases. 934 define i32 @twocases(i32 %c) { 935 entry: 936 switch i32 %c, label %sw.default [ 937 i32 0, label %return 938 i32 1, label %sw.bb1 939 ] 940 sw.bb1: br label %return 941 sw.default: br label %return 942 return: 943 %x = phi i32 [ 3, %sw.default ], [ 7, %sw.bb1 ], [ 9, %entry ] 944 ret i32 %x 945 ; CHECK-LABEL: @twocases( 946 ; CHECK-NOT: switch i32 947 ; CHECK-NOT: @switch.table 948 ; CHECK: %switch.selectcmp 949 ; CHECK-NEXT: %switch.select 950 ; CHECK-NEXT: %switch.selectcmp1 951 ; CHECK-NEXT: %switch.select2 952 } 953 954 ; Don't build tables for switches with TLS variables. 955 @tls_a = thread_local global i32 0 956 @tls_b = thread_local global i32 0 957 @tls_c = thread_local global i32 0 958 @tls_d = thread_local global i32 0 959 define i32* @tls(i32 %x) { 960 entry: 961 switch i32 %x, label %sw.default [ 962 i32 0, label %return 963 i32 1, label %sw.bb1 964 i32 2, label %sw.bb2 965 ] 966 sw.bb1: 967 br label %return 968 sw.bb2: 969 br label %return 970 sw.default: 971 br label %return 972 return: 973 %retval.0 = phi i32* [ @tls_d, %sw.default ], [ @tls_c, %sw.bb2 ], [ @tls_b, %sw.bb1 ], [ @tls_a, %entry ] 974 ret i32* %retval.0 975 ; CHECK-LABEL: @tls( 976 ; CHECK: switch i32 977 ; CHECK-NOT: @switch.table 978 } 979 980 ; Don't build tables for switches with dllimport variables. 981 @dllimport_a = external dllimport global [3x i32] 982 @dllimport_b = external dllimport global [3x i32] 983 @dllimport_c = external dllimport global [3x i32] 984 @dllimport_d = external dllimport global [3x i32] 985 define i32* @dllimport(i32 %x) { 986 entry: 987 switch i32 %x, label %sw.default [ 988 i32 0, label %return 989 i32 1, label %sw.bb1 990 i32 2, label %sw.bb2 991 ] 992 sw.bb1: 993 br label %return 994 sw.bb2: 995 br label %return 996 sw.default: 997 br label %return 998 return: 999 %retval.0 = phi i32* [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_d, i32 0, i32 0), %sw.default ], 1000 [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_c, i32 0, i32 0), %sw.bb2 ], 1001 [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_b, i32 0, i32 0), %sw.bb1 ], 1002 [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_a, i32 0, i32 0), %entry ] 1003 ret i32* %retval.0 1004 ; CHECK-LABEL: @dllimport( 1005 ; CHECK: switch i32 1006 ; CHECK-NOT: @switch.table 1007 } 1008 1009 ; We can use linear mapping. 1010 define i8 @linearmap1(i32 %c) { 1011 entry: 1012 switch i32 %c, label %sw.default [ 1013 i32 10, label %return 1014 i32 11, label %sw.bb1 1015 i32 12, label %sw.bb2 1016 i32 13, label %sw.bb3 1017 ] 1018 sw.bb1: br label %return 1019 sw.bb2: br label %return 1020 sw.bb3: br label %return 1021 sw.default: br label %return 1022 return: 1023 %x = phi i8 [ 3, %sw.default ], [ 3, %sw.bb3 ], [ 8, %sw.bb2 ], [ 13, %sw.bb1 ], [ 18, %entry ] 1024 ret i8 %x 1025 ; CHECK-LABEL: @linearmap1( 1026 ; CHECK: entry: 1027 ; CHECK-NEXT: %switch.tableidx = sub i32 %c, 10 1028 ; CHECK: switch.lookup: 1029 ; CHECK-NEXT: %switch.idx.cast = trunc i32 %switch.tableidx to i8 1030 ; CHECK-NEXT: %switch.idx.mult = mul i8 %switch.idx.cast, -5 1031 ; CHECK-NEXT: %switch.offset = add i8 %switch.idx.mult, 18 1032 ; CHECK-NEXT: ret i8 %switch.offset 1033 } 1034 1035 ; Linear mapping in a different configuration. 1036 define i32 @linearmap2(i8 %c) { 1037 entry: 1038 switch i8 %c, label %sw.default [ 1039 i8 -10, label %return 1040 i8 -11, label %sw.bb1 1041 i8 -12, label %sw.bb2 1042 i8 -13, label %sw.bb3 1043 ] 1044 sw.bb1: br label %return 1045 sw.bb2: br label %return 1046 sw.bb3: br label %return 1047 sw.default: br label %return 1048 return: 1049 %x = phi i32 [ 3, %sw.default ], [ 18, %sw.bb3 ], [ 19, %sw.bb2 ], [ 20, %sw.bb1 ], [ 21, %entry ] 1050 ret i32 %x 1051 ; CHECK-LABEL: @linearmap2( 1052 ; CHECK: entry: 1053 ; CHECK-NEXT: %switch.tableidx = sub i8 %c, -13 1054 ; CHECK: switch.lookup: 1055 ; CHECK-NEXT: %switch.idx.cast = zext i8 %switch.tableidx to i32 1056 ; CHECK-NEXT: %switch.offset = add i32 %switch.idx.cast, 18 1057 ; CHECK-NEXT: ret i32 %switch.offset 1058 } 1059 1060 ; Linear mapping with overflows. 1061 define i8 @linearmap3(i32 %c) { 1062 entry: 1063 switch i32 %c, label %sw.default [ 1064 i32 10, label %return 1065 i32 11, label %sw.bb1 1066 i32 12, label %sw.bb2 1067 i32 13, label %sw.bb3 1068 ] 1069 sw.bb1: br label %return 1070 sw.bb2: br label %return 1071 sw.bb3: br label %return 1072 sw.default: br label %return 1073 return: 1074 %x = phi i8 [ 3, %sw.default ], [ 44, %sw.bb3 ], [ -56, %sw.bb2 ], [ 100, %sw.bb1 ], [ 0, %entry ] 1075 ret i8 %x 1076 ; CHECK-LABEL: @linearmap3( 1077 ; CHECK: entry: 1078 ; CHECK-NEXT: %switch.tableidx = sub i32 %c, 10 1079 ; CHECK: switch.lookup: 1080 ; CHECK-NEXT: %switch.idx.cast = trunc i32 %switch.tableidx to i8 1081 ; CHECK-NEXT: %switch.idx.mult = mul i8 %switch.idx.cast, 100 1082 ; CHECK-NEXT: ret i8 %switch.idx.mult 1083 } 1084 1085 ; Linear mapping with with multiplier 1 and offset 0. 1086 define i8 @linearmap4(i32 %c) { 1087 entry: 1088 switch i32 %c, label %sw.default [ 1089 i32 -2, label %return 1090 i32 -1, label %sw.bb1 1091 i32 0, label %sw.bb2 1092 i32 1, label %sw.bb3 1093 ] 1094 sw.bb1: br label %return 1095 sw.bb2: br label %return 1096 sw.bb3: br label %return 1097 sw.default: br label %return 1098 return: 1099 %x = phi i8 [ 3, %sw.default ], [ 3, %sw.bb3 ], [ 2, %sw.bb2 ], [ 1, %sw.bb1 ], [ 0, %entry ] 1100 ret i8 %x 1101 ; CHECK-LABEL: @linearmap4( 1102 ; CHECK: entry: 1103 ; CHECK-NEXT: %switch.tableidx = sub i32 %c, -2 1104 ; CHECK: switch.lookup: 1105 ; CHECK-NEXT: %switch.idx.cast = trunc i32 %switch.tableidx to i8 1106 ; CHECK-NEXT: ret i8 %switch.idx.cast 1107 } 1108 1109 ; Reuse the inverted table range compare. 1110 define i32 @reuse_cmp1(i32 %x) { 1111 entry: 1112 switch i32 %x, label %sw.default [ 1113 i32 0, label %sw.bb 1114 i32 1, label %sw.bb1 1115 i32 2, label %sw.bb2 1116 i32 3, label %sw.bb3 1117 ] 1118 sw.bb: br label %sw.epilog 1119 sw.bb1: br label %sw.epilog 1120 sw.bb2: br label %sw.epilog 1121 sw.bb3: br label %sw.epilog 1122 sw.default: br label %sw.epilog 1123 sw.epilog: 1124 %r.0 = phi i32 [ 0, %sw.default ], [ 13, %sw.bb3 ], [ 12, %sw.bb2 ], [ 11, %sw.bb1 ], [ 10, %sw.bb ] 1125 %cmp = icmp eq i32 %r.0, 0 ; This compare can be "replaced". 1126 br i1 %cmp, label %if.then, label %if.end 1127 if.then: br label %return 1128 if.end: br label %return 1129 return: 1130 %retval.0 = phi i32 [ 100, %if.then ], [ %r.0, %if.end ] 1131 ret i32 %retval.0 1132 ; CHECK-LABEL: @reuse_cmp1( 1133 ; CHECK: entry: 1134 ; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0 1135 ; CHECK-NEXT: [[C:%.+]] = icmp ult i32 %switch.tableidx, 4 1136 ; CHECK-NEXT: %inverted.cmp = xor i1 [[C]], true 1137 ; CHECK: [[R:%.+]] = select i1 %inverted.cmp, i32 100, i32 {{.*}} 1138 ; CHECK-NEXT: ret i32 [[R]] 1139 } 1140 1141 ; Reuse the table range compare. 1142 define i32 @reuse_cmp2(i32 %x) { 1143 entry: 1144 switch i32 %x, label %sw.default [ 1145 i32 0, label %sw.bb 1146 i32 1, label %sw.bb1 1147 i32 2, label %sw.bb2 1148 i32 3, label %sw.bb3 1149 ] 1150 sw.bb: br label %sw.epilog 1151 sw.bb1: br label %sw.epilog 1152 sw.bb2: br label %sw.epilog 1153 sw.bb3: br label %sw.epilog 1154 sw.default: br label %sw.epilog 1155 sw.epilog: 1156 %r.0 = phi i32 [ 4, %sw.default ], [ 3, %sw.bb3 ], [ 2, %sw.bb2 ], [ 1, %sw.bb1 ], [ 0, %sw.bb ] 1157 %cmp = icmp ne i32 %r.0, 4 ; This compare can be "replaced". 1158 br i1 %cmp, label %if.then, label %if.end 1159 if.then: br label %return 1160 if.end: br label %return 1161 return: 1162 %retval.0 = phi i32 [ %r.0, %if.then ], [ 100, %if.end ] 1163 ret i32 %retval.0 1164 ; CHECK-LABEL: @reuse_cmp2( 1165 ; CHECK: entry: 1166 ; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0 1167 ; CHECK-NEXT: [[C:%.+]] = icmp ult i32 %switch.tableidx, 4 1168 ; CHECK: [[R:%.+]] = select i1 [[C]], i32 {{.*}}, i32 100 1169 ; CHECK-NEXT: ret i32 [[R]] 1170 } 1171 1172 ; Cannot reuse the table range compare, because the default value is the same 1173 ; as one of the case values. 1174 define i32 @no_reuse_cmp(i32 %x) { 1175 entry: 1176 switch i32 %x, label %sw.default [ 1177 i32 0, label %sw.bb 1178 i32 1, label %sw.bb1 1179 i32 2, label %sw.bb2 1180 i32 3, label %sw.bb3 1181 ] 1182 sw.bb: br label %sw.epilog 1183 sw.bb1: br label %sw.epilog 1184 sw.bb2: br label %sw.epilog 1185 sw.bb3: br label %sw.epilog 1186 sw.default: br label %sw.epilog 1187 sw.epilog: 1188 %r.0 = phi i32 [ 12, %sw.default ], [ 13, %sw.bb3 ], [ 12, %sw.bb2 ], [ 11, %sw.bb1 ], [ 10, %sw.bb ] 1189 %cmp = icmp ne i32 %r.0, 0 1190 br i1 %cmp, label %if.then, label %if.end 1191 if.then: br label %return 1192 if.end: br label %return 1193 return: 1194 %retval.0 = phi i32 [ %r.0, %if.then ], [ 100, %if.end ] 1195 ret i32 %retval.0 1196 ; CHECK-LABEL: @no_reuse_cmp( 1197 ; CHECK: [[S:%.+]] = select 1198 ; CHECK-NEXT: %cmp = icmp ne i32 [[S]], 0 1199 ; CHECK-NEXT: [[R:%.+]] = select i1 %cmp, i32 [[S]], i32 100 1200 ; CHECK-NEXT: ret i32 [[R]] 1201 } 1202 1203 ; Cannot reuse the table range compare, because the phi at the switch merge 1204 ; point is not dominated by the switch. 1205 define i32 @no_reuse_cmp2(i32 %x, i32 %y) { 1206 entry: 1207 %ec = icmp ne i32 %y, 0 1208 br i1 %ec, label %switch.entry, label %sw.epilog 1209 switch.entry: 1210 switch i32 %x, label %sw.default [ 1211 i32 0, label %sw.bb 1212 i32 1, label %sw.bb1 1213 i32 2, label %sw.bb2 1214 i32 3, label %sw.bb3 1215 ] 1216 sw.bb: br label %sw.epilog 1217 sw.bb1: br label %sw.epilog 1218 sw.bb2: br label %sw.epilog 1219 sw.bb3: br label %sw.epilog 1220 sw.default: br label %sw.epilog 1221 sw.epilog: 1222 %r.0 = phi i32 [100, %entry], [ 0, %sw.default ], [ 13, %sw.bb3 ], [ 12, %sw.bb2 ], [ 11, %sw.bb1 ], [ 10, %sw.bb ] 1223 %cmp = icmp eq i32 %r.0, 0 ; This compare can be "replaced". 1224 br i1 %cmp, label %if.then, label %if.end 1225 if.then: br label %return 1226 if.end: br label %return 1227 return: 1228 %retval.0 = phi i32 [ 100, %if.then ], [ %r.0, %if.end ] 1229 ret i32 %retval.0 1230 ; CHECK-LABEL: @no_reuse_cmp2( 1231 ; CHECK: %r.0 = phi 1232 ; CHECK-NEXT: %cmp = icmp eq i32 %r.0, 0 1233 ; CHECK-NEXT: [[R:%.+]] = select i1 %cmp 1234 ; CHECK-NEXT: ret i32 [[R]] 1235 } 1236 1237 define void @pr20210(i8 %x, i1 %y) { 1238 ; %z has uses outside of its BB or the phi it feeds into, 1239 ; so doing a table lookup and jumping directly to while.cond would 1240 ; cause %z to cease dominating all its uses. 1241 1242 entry: 1243 br i1 %y, label %sw, label %intermediate 1244 1245 sw: 1246 switch i8 %x, label %end [ 1247 i8 7, label %intermediate 1248 i8 3, label %intermediate 1249 i8 2, label %intermediate 1250 i8 1, label %intermediate 1251 i8 0, label %intermediate 1252 ] 1253 1254 intermediate: 1255 %z = zext i8 %x to i32 1256 br label %while.cond 1257 1258 while.cond: 1259 %i = phi i32 [ %z, %intermediate ], [ %j, %while.body ] 1260 %b = icmp ne i32 %i, 7 1261 br i1 %b, label %while.body, label %while.end 1262 1263 while.body: 1264 %j = add i32 %i, 1 1265 br label %while.cond 1266 1267 while.end: 1268 call void @exit(i32 %z) 1269 unreachable 1270 1271 end: 1272 ret void 1273 ; CHECK-LABEL: @pr20210 1274 ; CHECK: switch i8 %x 1275 } 1276 1277 ; Make sure we do not crash due to trying to generate an unguarded 1278 ; lookup (since i3 can only hold values in the range of explicit 1279 ; values) and simultaneously trying to generate a branch to deal with 1280 ; the fact that we have holes in the range. 1281 define i32 @covered_switch_with_bit_tests(i3) { 1282 entry: 1283 switch i3 %0, label %l6 [ 1284 i3 -3, label %l5 1285 i3 -4, label %l5 1286 i3 3, label %l1 1287 i3 2, label %l1 1288 ] 1289 1290 l1: br label %l2 1291 1292 l2: 1293 %x = phi i32 [ 1, %l1 ], [ 2, %l5 ] 1294 br label %l6 1295 1296 l5: br label %l2 1297 1298 l6: 1299 %r = phi i32 [ %x, %l2 ], [ 0, %entry ] 1300 ret i32 %r 1301 ; CHECK-LABEL: @covered_switch_with_bit_tests 1302 ; CHECK: entry 1303 ; CHECK-NEXT: switch 1304 } 1305
