test/Transforms/LowerSwitch/do-not-handle-impossible-values.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -lowerswitch -S | FileCheck %s
   3
   4 ; Check that we do not generate redundant comparisons that would have results
   5 ; known at compile time due to limited range of the value being switch'ed over.
   6 define i32 @test1(i32 %val) {
   7 ; CHECK-LABEL: @test1(
   8 ; CHECK-NEXT:  entry:
   9 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[VAL:%.*]] to i2
  10 ; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
  11 ; CHECK:       NodeBlock:
  12 ; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i2 [[TRUNC]], 1
  13 ; CHECK-NEXT:    br i1 [[PIVOT]], label [[LEAFBLOCK:%.*]], label [[CASE_1:%.*]]
  14 ; CHECK:       LeafBlock:
  15 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i2 [[TRUNC]], -2
  16 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
  17 ; CHECK:       case.1:
  18 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
  19 ; CHECK-NEXT:    br label [[EXIT:%.*]]
  20 ; CHECK:       case.2:
  21 ; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
  22 ; CHECK-NEXT:    br label [[EXIT]]
  23 ; CHECK:       NewDefault:
  24 ; CHECK-NEXT:    br label [[CASE_D:%.*]]
  25 ; CHECK:       case.D:
  26 ; CHECK-NEXT:    [[RESD:%.*]] = call i32 @caseD()
  27 ; CHECK-NEXT:    br label [[EXIT]]
  28 ; CHECK:       exit:
  29 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
  30 ; CHECK-NEXT:    ret i32 [[RES]]
  31 ;
  32 entry:
  33   %trunc = trunc i32 %val to i2
  34   switch i2 %trunc, label %case.D [
  35   i2 1, label %case.1  ; i2  1
  36   i2 2, label %case.2  ; i2 -2
  37   ]
  38   ; It's known that %val can not be less than -2 or greater than 1
  39
  40 case.1:
  41   %res1 = call i32 @case1()
  42   br label %exit
  43
  44 case.2:
  45   %res2 = call i32 @case2()
  46   br label %exit
  47
  48 case.D:
  49   %resD = call i32 @caseD()
  50   br label %exit
  51
  52 exit:
  53   %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
  54   ret i32 %res
  55 }
  56
  57 ; Check that we do not generate redundant comparisons that would have results
  58 ; known at compile time due to limited range of the value being switch'ed over.
  59 define i32 @test2() {
  60 ; CHECK-LABEL: @test2(
  61 ; CHECK-NEXT:  entry:
  62 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !0
  63 ; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
  64 ; CHECK:       NodeBlock:
  65 ; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 2
  66 ; CHECK-NEXT:    br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
  67 ; CHECK:       LeafBlock:
  68 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
  69 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
  70 ; CHECK:       case.1:
  71 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
  72 ; CHECK-NEXT:    br label [[EXIT:%.*]]
  73 ; CHECK:       case.2:
  74 ; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
  75 ; CHECK-NEXT:    br label [[EXIT]]
  76 ; CHECK:       NewDefault:
  77 ; CHECK-NEXT:    br label [[CASE_D:%.*]]
  78 ; CHECK:       case.D:
  79 ; CHECK-NEXT:    [[RESD:%.*]] = call i32 @caseD()
  80 ; CHECK-NEXT:    br label [[EXIT]]
  81 ; CHECK:       exit:
  82 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
  83 ; CHECK-NEXT:    ret i32 [[RES]]
  84 ;
  85 entry:
  86   %val = call i32 @getVal(), !range !0
  87   switch i32 %val, label %case.D [
  88   i32 1, label %case.1
  89   i32 2, label %case.2
  90   ]
  91   ; It's known that %val can not be less than 1
  92
  93 case.1:
  94   %res1 = call i32 @case1()
  95   br label %exit
  96
  97 case.2:
  98   %res2 = call i32 @case2()
  99   br label %exit
 100
 101 case.D:
 102   %resD = call i32 @caseD()
 103   br label %exit
 104
 105 exit:
 106   %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
 107   ret i32 %res
 108 }
 109
 110 ; Corner case:
 111 ; 1) some of the non-default cases are unreachable due to the !range constraint,
 112 ; 2) the default case is unreachable as non-default cases cover the range fully.
 113 define i32 @test3() {
 114 ; CHECK-LABEL: @test3(
 115 ; CHECK-NEXT:  entry:
 116 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !1
 117 ; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
 118 ; CHECK:       LeafBlock:
 119 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
 120 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
 121 ; CHECK:       NewDefault:
 122 ; CHECK-NEXT:    br label [[CASE_1:%.*]]
 123 ; CHECK:       case.1:
 124 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
 125 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 126 ; CHECK:       case.2:
 127 ; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
 128 ; CHECK-NEXT:    br label [[EXIT]]
 129 ; CHECK:       exit:
 130 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ]
 131 ; CHECK-NEXT:    ret i32 [[RES]]
 132 ;
 133 entry:
 134   %val = call i32 @getVal(), !range !1
 135   switch i32 %val, label %case.D [
 136   i32 1, label %case.1
 137   i32 2, label %case.2
 138   i32 3, label %case.1
 139   ]
 140
 141 case.1:
 142   %res1 = call i32 @case1()
 143   br label %exit
 144
 145 case.2:
 146   %res2 = call i32 @case2()
 147   br label %exit
 148
 149 case.D:
 150   %resD = call i32 @caseD()
 151   br label %exit
 152
 153 exit:
 154   %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
 155   ret i32 %res
 156 }
 157
 158 ; Corner case:
 159 ; 1) some of the non-default cases are unreachable due to the !range constraint,
 160 ; 2) the default case is still reachable as non-default cases do not cover the
 161 ;    range fully.
 162 define i32 @test4() {
 163 ; CHECK-LABEL: @test4(
 164 ; CHECK-NEXT:  entry:
 165 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !2
 166 ; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
 167 ; CHECK:       NodeBlock:
 168 ; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 2
 169 ; CHECK-NEXT:    br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
 170 ; CHECK:       LeafBlock:
 171 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
 172 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
 173 ; CHECK:       case.1:
 174 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
 175 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 176 ; CHECK:       case.2:
 177 ; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
 178 ; CHECK-NEXT:    br label [[EXIT]]
 179 ; CHECK:       NewDefault:
 180 ; CHECK-NEXT:    br label [[CASE_D:%.*]]
 181 ; CHECK:       case.D:
 182 ; CHECK-NEXT:    [[RESD:%.*]] = call i32 @caseD()
 183 ; CHECK-NEXT:    br label [[EXIT]]
 184 ; CHECK:       exit:
 185 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
 186 ; CHECK-NEXT:    ret i32 [[RES]]
 187 ;
 188 entry:
 189   %val = call i32 @getVal(), !range !2
 190   switch i32 %val, label %case.D [
 191   i32 1, label %case.1
 192   i32 2, label %case.2
 193   ]
 194
 195 case.1:
 196   %res1 = call i32 @case1()
 197   br label %exit
 198
 199 case.2:
 200   %res2 = call i32 @case2()
 201   br label %exit
 202
 203 case.D:
 204   %resD = call i32 @caseD()
 205   br label %exit
 206
 207 exit:
 208   %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
 209   ret i32 %res
 210 }
 211
 212 ; Corner case:
 213 ; 1) some of the non-default cases are unreachable due to the !range constraint,
 214 ; 2) the default case appears to be unreachable as non-default cases cover the
 215 ;    range fully, but its basic block actually is reachable from the switch via
 216 ;    one of the non-default cases.
 217 define i32 @test5(i1 %cond) {
 218 ; CHECK-LABEL: @test5(
 219 ; CHECK-NEXT:  entry:
 220 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
 221 ; CHECK:       switch:
 222 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !1
 223 ; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
 224 ; CHECK:       NodeBlock:
 225 ; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 3
 226 ; CHECK-NEXT:    br i1 [[PIVOT]], label [[LEAFBLOCK:%.*]], label [[CASE_1:%.*]]
 227 ; CHECK:       LeafBlock:
 228 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1
 229 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_1]], label [[NEWDEFAULT:%.*]]
 230 ; CHECK:       case.1:
 231 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
 232 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 233 ; CHECK:       NewDefault:
 234 ; CHECK-NEXT:    br label [[CASE_D]]
 235 ; CHECK:       case.D:
 236 ; CHECK-NEXT:    [[DELTA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 20, [[NEWDEFAULT]] ]
 237 ; CHECK-NEXT:    [[RESD_TMP:%.*]] = call i32 @caseD()
 238 ; CHECK-NEXT:    [[RESD:%.*]] = add i32 [[RESD_TMP]], [[DELTA]]
 239 ; CHECK-NEXT:    br label [[EXIT]]
 240 ; CHECK:       exit:
 241 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RESD]], [[CASE_D]] ]
 242 ; CHECK-NEXT:    ret i32 [[RES]]
 243 ;
 244 entry:
 245   br i1 %cond, label %switch, label %case.D
 246
 247 switch:
 248   %val = call i32 @getVal(), !range !1
 249   switch i32 %val, label %case.D [
 250   i32 1, label %case.1
 251   i32 2, label %case.D
 252   i32 3, label %case.1
 253   ]
 254
 255 case.1:
 256   %res1 = call i32 @case1()
 257   br label %exit
 258
 259 case.D:
 260   %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ]
 261   %resD.tmp = call i32 @caseD()
 262   %resD = add i32 %resD.tmp, %delta
 263   br label %exit
 264
 265 exit:
 266   %res = phi i32 [ %res1, %case.1 ], [ %resD, %case.D ]
 267   ret i32 %res
 268 }
 269
 270 ; Corner case:
 271 ; 1) some of the non-default cases are unreachable due to the !range constraint,
 272 ; 2) the default case appears to be unreachable as non-default cases cover the
 273 ;    range fully, but its basic block actually is reachable, though, from a
 274 ;    different basic block, not the switch itself.
 275 define i32 @test6(i1 %cond) {
 276 ; CHECK-LABEL: @test6(
 277 ; CHECK-NEXT:  entry:
 278 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
 279 ; CHECK:       switch:
 280 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !1
 281 ; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
 282 ; CHECK:       LeafBlock:
 283 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
 284 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
 285 ; CHECK:       NewDefault:
 286 ; CHECK-NEXT:    br label [[CASE_1:%.*]]
 287 ; CHECK:       case.1:
 288 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
 289 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 290 ; CHECK:       case.2:
 291 ; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
 292 ; CHECK-NEXT:    br label [[EXIT]]
 293 ; CHECK:       case.D:
 294 ; CHECK-NEXT:    [[RESD_TMP:%.*]] = call i32 @caseD()
 295 ; CHECK-NEXT:    [[RESD:%.*]] = add i32 [[RESD_TMP]], 0
 296 ; CHECK-NEXT:    br label [[EXIT]]
 297 ; CHECK:       exit:
 298 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
 299 ; CHECK-NEXT:    ret i32 [[RES]]
 300 ;
 301 entry:
 302   br i1 %cond, label %switch, label %case.D
 303
 304 switch:
 305   %val = call i32 @getVal(), !range !1
 306   switch i32 %val, label %case.D [
 307   i32 1, label %case.1
 308   i32 2, label %case.2
 309   i32 3, label %case.1
 310   ]
 311
 312 case.1:
 313   %res1 = call i32 @case1()
 314   br label %exit
 315
 316 case.2:
 317   %res2 = call i32 @case2()
 318   br label %exit
 319
 320 case.D:
 321   %delta = phi i32 [ 0, %entry ], [ 20, %switch ]
 322   %resD.tmp = call i32 @caseD()
 323   %resD = add i32 %resD.tmp, %delta
 324   br label %exit
 325
 326 exit:
 327   %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
 328   ret i32 %res
 329 }
 330
 331 ; Corner case:
 332 ; 1) switch appears to have a non-empty set of non-default cases, but all of
 333 ;    them reference the default case basic block.
 334 define i32 @test7(i1 %cond) {
 335 ; CHECK-LABEL: @test7(
 336 ; CHECK-NEXT:  entry:
 337 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
 338 ; CHECK:       switch:
 339 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !1
 340 ; CHECK-NEXT:    br label [[CASE_D]]
 341 ; CHECK:       case.D:
 342 ; CHECK-NEXT:    [[DELTA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 20, [[SWITCH]] ]
 343 ; CHECK-NEXT:    [[RESD_TMP:%.*]] = call i32 @caseD()
 344 ; CHECK-NEXT:    [[RESD:%.*]] = add i32 [[RESD_TMP]], [[DELTA]]
 345 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 346 ; CHECK:       exit:
 347 ; CHECK-NEXT:    ret i32 [[RESD]]
 348 ;
 349 entry:
 350   br i1 %cond, label %switch, label %case.D
 351
 352 switch:
 353   %val = call i32 @getVal(), !range !1
 354   switch i32 %val, label %case.D [
 355   i32 2, label %case.D
 356   ]
 357
 358 case.D:
 359   %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ]
 360   %resD.tmp = call i32 @caseD()
 361   %resD = add i32 %resD.tmp, %delta
 362   br label %exit
 363
 364 exit:
 365   ret i32 %resD
 366 }
 367
 368 ; Corner case:
 369 ; 1) some of the non-default cases are unreachable due to the !range constraint,
 370 ; 2) the default case appears to be unreachable as non-default cases cover the
 371 ;    range fully, but its basic block actually is reachable from the switch via
 372 ;    one of the non-default cases,
 373 ; 3) such cases lie at the boundary of the range of values covered by
 374 ;    non-default cases, and if removed, do not change the fact that the rest of
 375 ;    the cases fully covers the value range.
 376 define i32 @test8(i1 %cond) {
 377 ; CHECK-LABEL: @test8(
 378 ; CHECK-NEXT:  entry:
 379 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
 380 ; CHECK:       switch:
 381 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !3
 382 ; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
 383 ; CHECK:       LeafBlock:
 384 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
 385 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
 386 ; CHECK:       NewDefault:
 387 ; CHECK-NEXT:    br label [[CASE_1:%.*]]
 388 ; CHECK:       case.1:
 389 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
 390 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 391 ; CHECK:       case.2:
 392 ; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
 393 ; CHECK-NEXT:    br label [[EXIT]]
 394 ; CHECK:       case.D:
 395 ; CHECK-NEXT:    [[RESD_TMP:%.*]] = call i32 @caseD()
 396 ; CHECK-NEXT:    [[RESD:%.*]] = add i32 [[RESD_TMP]], 0
 397 ; CHECK-NEXT:    br label [[EXIT]]
 398 ; CHECK:       exit:
 399 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
 400 ; CHECK-NEXT:    ret i32 [[RES]]
 401 ;
 402 entry:
 403   br i1 %cond, label %switch, label %case.D
 404
 405 switch:
 406   %val = call i32 @getVal(), !range !3
 407   switch i32 %val, label %case.D [
 408   i32 1, label %case.1
 409   i32 2, label %case.2
 410   i32 3, label %case.D
 411   ]
 412
 413 case.1:
 414   %res1 = call i32 @case1()
 415   br label %exit
 416
 417 case.2:
 418   %res2 = call i32 @case2()
 419   br label %exit
 420
 421 case.D:
 422   %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ]
 423   %resD.tmp = call i32 @caseD()
 424   %resD = add i32 %resD.tmp, %delta
 425   br label %exit
 426
 427 exit:
 428   %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
 429   ret i32 %res
 430 }
 431
 432 ; Corner case:
 433 ; 1) the default case appears to be unreachable as non-default cases cover the
 434 ;    range fully, but its basic block actually is reachable from the switch via
 435 ;    more than one non-default case.
 436 define i32 @test9(i1 %cond, i2 %val) {
 437 ; CHECK-LABEL: @test9(
 438 ; CHECK-NEXT:  entry:
 439 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
 440 ; CHECK:       switch:
 441 ; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
 442 ; CHECK:       LeafBlock:
 443 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp sge i2 [[VAL:%.*]], 0
 444 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_1:%.*]], label [[NEWDEFAULT:%.*]]
 445 ; CHECK:       case.1:
 446 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
 447 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 448 ; CHECK:       NewDefault:
 449 ; CHECK-NEXT:    br label [[CASE_D]]
 450 ; CHECK:       case.D:
 451 ; CHECK-NEXT:    [[DELTA:%.*]] = phi i32 [ 20, [[NEWDEFAULT]] ], [ 0, [[ENTRY:%.*]] ]
 452 ; CHECK-NEXT:    [[RESD_TMP:%.*]] = call i32 @caseD()
 453 ; CHECK-NEXT:    [[RESD:%.*]] = add i32 [[RESD_TMP]], [[DELTA]]
 454 ; CHECK-NEXT:    br label [[EXIT]]
 455 ; CHECK:       exit:
 456 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RESD]], [[CASE_D]] ]
 457 ; CHECK-NEXT:    ret i32 [[RES]]
 458 ;
 459 entry:
 460   br i1 %cond, label %switch, label %case.D
 461
 462 switch:
 463   switch i2 %val, label %case.D [
 464   i2 0, label %case.1
 465   i2 1, label %case.1
 466   i2 2, label %case.D
 467   i2 3, label %case.D
 468   ]
 469
 470 case.1:
 471   %res1 = call i32 @case1()
 472   br label %exit
 473
 474 case.D:
 475   %delta = phi i32 [20, %switch ], [ 20, %switch ], [ 20, %switch ], [ 0, %entry ]
 476   %resD.tmp = call i32 @caseD()
 477   %resD = add i32 %resD.tmp, %delta
 478   br label %exit
 479
 480 exit:
 481   %res = phi i32 [ %res1, %case.1 ], [ %resD, %case.D ]
 482   ret i32 %res
 483 }
 484
 485 ; Check that we do not generate redundant comparisons that would have results
 486 ; known at compile time due to limited range of the value being switch'ed over.
 487 define i32 @test10() {
 488 ; CHECK-LABEL: @test10(
 489 ; CHECK-NEXT:  entry:
 490 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal()
 491 ; CHECK-NEXT:    [[COND_LEFT:%.*]] = icmp sge i32 [[VAL]], 1
 492 ; CHECK-NEXT:    [[COND_RIGHT:%.*]] = icmp sle i32 [[VAL]], 6
 493 ; CHECK-NEXT:    [[COND:%.*]] = and i1 [[COND_LEFT]], [[COND_RIGHT]]
 494 ; CHECK-NEXT:    br i1 [[COND]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
 495 ; CHECK:       switch:
 496 ; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
 497 ; CHECK:       LeafBlock:
 498 ; CHECK-NEXT:    [[VAL_OFF:%.*]] = add i32 [[VAL]], -3
 499 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp ule i32 [[VAL_OFF]], 1
 500 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
 501 ; CHECK:       NewDefault:
 502 ; CHECK-NEXT:    br label [[CASE_1:%.*]]
 503 ; CHECK:       case.1:
 504 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
 505 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 506 ; CHECK:       case.2:
 507 ; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
 508 ; CHECK-NEXT:    br label [[EXIT]]
 509 ; CHECK:       case.D:
 510 ; CHECK-NEXT:    br label [[EXIT]]
 511 ; CHECK:       exit:
 512 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ 0, [[CASE_D]] ]
 513 ; CHECK-NEXT:    ret i32 [[RES]]
 514 ;
 515 entry:
 516   %val = call i32 @getVal()
 517   %cond.left = icmp sge i32 %val, 1
 518   %cond.right = icmp sle i32 %val, 6
 519   %cond = and i1 %cond.left, %cond.right
 520   br i1 %cond, label %switch, label %case.D
 521
 522 switch:
 523   switch i32 %val, label %case.D [
 524   i32 1, label %case.1
 525   i32 2, label %case.1
 526   i32 3, label %case.2
 527   i32 4, label %case.2
 528   i32 5, label %case.1
 529   i32 6, label %case.1
 530   ]
 531   ; It's known that %val <- [1, 6]
 532
 533 case.1:
 534   %res1 = call i32 @case1()
 535   br label %exit
 536
 537 case.2:
 538   %res2 = call i32 @case2()
 539   br label %exit
 540
 541 case.D:
 542   %resD = phi i32 [ 20, %switch ], [ 0, %entry ]
 543   br label %exit
 544
 545 exit:
 546   %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
 547   ret i32 %res
 548 }
 549
 550 ; Check that we do not generate redundant comparisons that would have results
 551 ; known at compile time due to limited range of the value being switch'ed over.
 552 define i32 @test11() {
 553 ; CHECK-LABEL: @test11(
 554 ; CHECK-NEXT:  entry:
 555 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal()
 556 ; CHECK-NEXT:    [[VAL_ZEXT:%.*]] = zext i32 [[VAL]] to i64
 557 ; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
 558 ; CHECK:       NodeBlock:
 559 ; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i64 [[VAL_ZEXT]], 1
 560 ; CHECK-NEXT:    br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
 561 ; CHECK:       LeafBlock:
 562 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i64 [[VAL_ZEXT]], 1
 563 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
 564 ; CHECK:       case.1:
 565 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
 566 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 567 ; CHECK:       case.2:
 568 ; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
 569 ; CHECK-NEXT:    br label [[EXIT]]
 570 ; CHECK:       NewDefault:
 571 ; CHECK-NEXT:    br label [[CASE_D:%.*]]
 572 ; CHECK:       case.D:
 573 ; CHECK-NEXT:    [[RESD:%.*]] = call i32 @caseD()
 574 ; CHECK-NEXT:    br label [[EXIT]]
 575 ; CHECK:       exit:
 576 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
 577 ; CHECK-NEXT:    ret i32 [[RES]]
 578 ;
 579 entry:
 580   %val = call i32 @getVal()
 581   %val.zext = zext i32 %val to i64
 582   switch i64 %val.zext, label %case.D [
 583   i64 0, label %case.1
 584   i64 1, label %case.2
 585   ]
 586   ; It's known that %val can not be less than 0
 587
 588 case.1:
 589   %res1 = call i32 @case1()
 590   br label %exit
 591
 592 case.2:
 593   %res2 = call i32 @case2()
 594   br label %exit
 595
 596 case.D:
 597   %resD = call i32 @caseD()
 598   br label %exit
 599
 600 exit:
 601   %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
 602   ret i32 %res
 603 }
 604
 605 ; Check that we do not generate redundant comparisons that would have results
 606 ; known at compile time due to limited range of the value being switch'ed over.
 607 define void @test12() {
 608 ; CHECK-LABEL: @test12(
 609 ; CHECK-NEXT:  entry:
 610 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 611 ; CHECK:       for.body:
 612 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[LATCH:%.*]] ]
 613 ; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
 614 ; CHECK:       NodeBlock:
 615 ; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[INDVAR]], 1
 616 ; CHECK-NEXT:    br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
 617 ; CHECK:       LeafBlock:
 618 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[INDVAR]], 1
 619 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
 620 ; CHECK:       case.1:
 621 ; CHECK-NEXT:    br label [[LATCH]]
 622 ; CHECK:       case.2:
 623 ; CHECK-NEXT:    br label [[LATCH]]
 624 ; CHECK:       NewDefault:
 625 ; CHECK-NEXT:    br label [[LATCH]]
 626 ; CHECK:       latch:
 627 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[INDVAR]], 1
 628 ; CHECK-NEXT:    br i1 undef, label [[EXIT:%.*]], label [[FOR_BODY]]
 629 ; CHECK:       exit:
 630 ; CHECK-NEXT:    ret void
 631 ;
 632 entry:
 633   br label %for.body
 634
 635 for.body:
 636   %indvar = phi i32 [ 0, %entry ], [ %inc, %latch ]
 637   switch i32 %indvar, label %latch [
 638   i32 0, label %case.1
 639   i32 1, label %case.2
 640   ]
 641   ; It's known that %indvar can not be less than 0
 642
 643 case.1:
 644   br label %latch
 645
 646 case.2:
 647   br label %latch
 648
 649 latch:
 650   %inc = add nuw nsw i32 %indvar, 1
 651   br i1 undef, label %exit, label %for.body
 652
 653 exit:
 654   ret void
 655 }
 656
 657 ; Check that we do not generate redundant comparisons that would have results
 658 ; known at compile time due to limited range of the value being switch'ed over.
 659 define void @test13(i32 %val) {
 660 ; CHECK-LABEL: @test13(
 661 ; CHECK-NEXT:  entry:
 662 ; CHECK-NEXT:    [[TMP:%.*]] = and i32 [[VAL:%.*]], 7
 663 ; CHECK-NEXT:    br label [[BB33:%.*]]
 664 ; CHECK:       bb33:
 665 ; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
 666 ; CHECK:       LeafBlock:
 667 ; CHECK-NEXT:    [[TMP_OFF:%.*]] = add i32 [[TMP]], -2
 668 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp ule i32 [[TMP_OFF]], 1
 669 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[BB34:%.*]], label [[NEWDEFAULT:%.*]]
 670 ; CHECK:       bb34:
 671 ; CHECK-NEXT:    br label [[BB38:%.*]]
 672 ; CHECK:       NewDefault:
 673 ; CHECK-NEXT:    br label [[BB35:%.*]]
 674 ; CHECK:       bb35:
 675 ; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
 676 ; CHECK:       NodeBlock:
 677 ; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[TMP]], 6
 678 ; CHECK-NEXT:    br i1 [[PIVOT]], label [[LEAFBLOCK2:%.*]], label [[BB37:%.*]]
 679 ; CHECK:       LeafBlock2:
 680 ; CHECK-NEXT:    [[SWITCHLEAF3:%.*]] = icmp sle i32 [[TMP]], 1
 681 ; CHECK-NEXT:    br i1 [[SWITCHLEAF3]], label [[BB37]], label [[NEWDEFAULT1:%.*]]
 682 ; CHECK:       bb37:
 683 ; CHECK-NEXT:    br label [[BB38]]
 684 ; CHECK:       NewDefault1:
 685 ; CHECK-NEXT:    br label [[BB38]]
 686 ; CHECK:       bb38:
 687 ; CHECK-NEXT:    br label [[BB33]]
 688 ;
 689 entry:
 690   %tmp = and i32 %val, 7
 691   br label %bb33
 692
 693 bb33:
 694   switch i32 %tmp, label %bb35 [
 695   i32 2, label %bb34
 696   i32 3, label %bb34
 697   ]
 698
 699 bb34:
 700   br label %bb38
 701
 702 bb35:
 703   switch i32 %tmp, label %bb38 [
 704   i32 0, label %bb37
 705   i32 1, label %bb37
 706   i32 6, label %bb37
 707   i32 7, label %bb37
 708   ]
 709   ; It's known that %tmp <- [0, 1] U [4, 7]
 710
 711 bb37:
 712   br label %bb38
 713
 714 bb38:
 715   br label %bb33
 716 }
 717
 718 ; Check that we do not generate redundant comparisons that would have results
 719 ; known at compile time due to limited range of the value being switch'ed over.
 720 define i32 @test14() {
 721 ; CHECK-LABEL: @test14(
 722 ; CHECK-NEXT:  entry:
 723 ; CHECK-NEXT:    [[TMP:%.*]] = call i32 @getVal(), !range !4
 724 ; CHECK-NEXT:    [[VAL:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP]])
 725 ; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
 726 ; CHECK:       NodeBlock:
 727 ; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 1
 728 ; CHECK-NEXT:    br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
 729 ; CHECK:       LeafBlock:
 730 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1
 731 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
 732 ; CHECK:       case.1:
 733 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
 734 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 735 ; CHECK:       case.2:
 736 ; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
 737 ; CHECK-NEXT:    br label [[EXIT]]
 738 ; CHECK:       NewDefault:
 739 ; CHECK-NEXT:    br label [[CASE_D:%.*]]
 740 ; CHECK:       case.D:
 741 ; CHECK-NEXT:    [[RESD:%.*]] = call i32 @caseD()
 742 ; CHECK-NEXT:    br label [[EXIT]]
 743 ; CHECK:       exit:
 744 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
 745 ; CHECK-NEXT:    ret i32 [[RES]]
 746 ;
 747 entry:
 748   %tmp = call i32 @getVal(), !range !4
 749   %val = call i32 @llvm.ctpop.i32(i32 %tmp)
 750   switch i32 %val, label %case.D [
 751   i32 0, label %case.1
 752   i32 1, label %case.2
 753   ]
 754   ; It's known that %val <- [0, 2]
 755
 756 case.1:
 757   %res1 = call i32 @case1()
 758   br label %exit
 759
 760 case.2:
 761   %res2 = call i32 @case2()
 762   br label %exit
 763
 764 case.D:
 765   %resD = call i32 @caseD()
 766   br label %exit
 767
 768 exit:
 769   %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
 770   ret i32 %res
 771 }
 772
 773 ; Check that we do not generate redundant comparisons that would have results
 774 ; known at compile time due to limited range of the value being switch'ed over.
 775 define i32 @test15() {
 776 ; CHECK-LABEL: @test15(
 777 ; CHECK-NEXT:  entry:
 778 ; CHECK-NEXT:    [[TMP:%.*]] = call i32 @getVal()
 779 ; CHECK-NEXT:    [[VAL:%.*]] = urem i32 [[TMP]], 3
 780 ; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
 781 ; CHECK:       NodeBlock:
 782 ; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 1
 783 ; CHECK-NEXT:    br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
 784 ; CHECK:       LeafBlock:
 785 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1
 786 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
 787 ; CHECK:       case.1:
 788 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
 789 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 790 ; CHECK:       case.2:
 791 ; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
 792 ; CHECK-NEXT:    br label [[EXIT]]
 793 ; CHECK:       NewDefault:
 794 ; CHECK-NEXT:    br label [[CASE_D:%.*]]
 795 ; CHECK:       case.D:
 796 ; CHECK-NEXT:    [[RESD:%.*]] = call i32 @caseD()
 797 ; CHECK-NEXT:    br label [[EXIT]]
 798 ; CHECK:       exit:
 799 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
 800 ; CHECK-NEXT:    ret i32 [[RES]]
 801 ;
 802 entry:
 803   %tmp = call i32 @getVal()
 804   %val = urem i32 %tmp, 3
 805   switch i32 %val, label %case.D [
 806   i32 0, label %case.1
 807   i32 1, label %case.2
 808   ]
 809   ; It's known that %val <- [0, 2]
 810
 811 case.1:
 812   %res1 = call i32 @case1()
 813   br label %exit
 814
 815 case.2:
 816   %res2 = call i32 @case2()
 817   br label %exit
 818
 819 case.D:
 820   %resD = call i32 @caseD()
 821   br label %exit
 822
 823 exit:
 824   %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
 825   ret i32 %res
 826 }
 827
 828 ; Check that we do not generate redundant comparisons that would have results
 829 ; known at compile time due to limited range of the value being switch'ed over.
 830 define i32 @test16(float %f) {
 831 ; CHECK-LABEL: @test16(
 832 ; CHECK-NEXT:  entry:
 833 ; CHECK-NEXT:    [[I:%.*]] = fptosi float [[F:%.*]] to i64
 834 ; CHECK-NEXT:    [[COND_LEFT:%.*]] = icmp slt i64 [[I]], 0
 835 ; CHECK-NEXT:    [[CLAMP_LEFT:%.*]] = select i1 [[COND_LEFT]], i64 0, i64 [[I]]
 836 ; CHECK-NEXT:    [[COND_RIGHT:%.*]] = icmp sgt i64 [[I]], 3
 837 ; CHECK-NEXT:    [[CLAMP:%.*]] = select i1 [[COND_RIGHT]], i64 3, i64 [[CLAMP_LEFT]]
 838 ; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
 839 ; CHECK:       LeafBlock:
 840 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp sge i64 [[CLAMP]], 2
 841 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
 842 ; CHECK:       NewDefault:
 843 ; CHECK-NEXT:    br label [[CASE_1:%.*]]
 844 ; CHECK:       case.1:
 845 ; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
 846 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 847 ; CHECK:       case.2:
 848 ; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
 849 ; CHECK-NEXT:    br label [[EXIT]]
 850 ; CHECK:       exit:
 851 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ]
 852 ; CHECK-NEXT:    ret i32 [[RES]]
 853 ;
 854 entry:
 855   %i = fptosi float %f to i64
 856   %cond.left = icmp slt i64 %i, 0
 857   %clamp.left = select i1 %cond.left, i64 0, i64 %i
 858   %cond.right = icmp sgt i64 %i, 3
 859   %clamp = select i1 %cond.right, i64 3, i64 %clamp.left
 860   switch i64 %clamp, label %case.D [
 861   i64 0, label %case.1
 862   i64 1, label %case.1
 863   i64 2, label %case.2
 864   i64 3, label %case.2
 865   ]
 866   ; It's known that %val <- [0, 3]
 867
 868 case.1:
 869   %res1 = call i32 @case1()
 870   br label %exit
 871
 872 case.2:
 873   %res2 = call i32 @case2()
 874   br label %exit
 875
 876 case.D:
 877   %resD = call i32 @caseD()
 878   br label %exit
 879
 880 exit:
 881   %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
 882   ret i32 %res
 883 }
 884
 885 declare i32 @case1()
 886 declare i32 @case2()
 887 declare i32 @caseD()
 888 declare i32 @getVal()
 889 declare i32 @llvm.ctpop.i32(i32)
 890
 891 !0 = !{i32 1, i32 257}
 892 !1 = !{i32 2, i32 3}
 893 !2 = !{i32 2, i32 257}
 894 !3 = !{i32 1, i32 3}
 895 !4 = !{i32 0, i32 4}