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