test/Transforms/SimplifyCFG/switch_create.ll

   1 ; RUN: opt < %s -simplifycfg -S | FileCheck %s
   2
   3 declare void @foo1()
   4
   5 declare void @foo2()
   6
   7 define void @test1(i32 %V) {
   8         %C1 = icmp eq i32 %V, 4         ; <i1> [#uses=1]
   9         %C2 = icmp eq i32 %V, 17                ; <i1> [#uses=1]
  10         %CN = or i1 %C1, %C2            ; <i1> [#uses=1]
  11         br i1 %CN, label %T, label %F
  12 T:              ; preds = %0
  13         call void @foo1( )
  14         ret void
  15 F:              ; preds = %0
  16         call void @foo2( )
  17         ret void
  18 ; CHECK-LABEL: @test1(
  19 ; CHECK:  switch i32 %V, label %F [
  20 ; CHECK:    i32 17, label %T
  21 ; CHECK:    i32 4, label %T
  22 ; CHECK:  ]
  23 }
  24
  25 define void @test2(i32 %V) {
  26         %C1 = icmp ne i32 %V, 4         ; <i1> [#uses=1]
  27         %C2 = icmp ne i32 %V, 17                ; <i1> [#uses=1]
  28         %CN = and i1 %C1, %C2           ; <i1> [#uses=1]
  29         br i1 %CN, label %T, label %F
  30 T:              ; preds = %0
  31         call void @foo1( )
  32         ret void
  33 F:              ; preds = %0
  34         call void @foo2( )
  35         ret void
  36 ; CHECK-LABEL: @test2(
  37 ; CHECK:  switch i32 %V, label %T [
  38 ; CHECK:    i32 17, label %F
  39 ; CHECK:    i32 4, label %F
  40 ; CHECK:  ]
  41 }
  42
  43 define void @test3(i32 %V) {
  44         %C1 = icmp eq i32 %V, 4         ; <i1> [#uses=1]
  45         br i1 %C1, label %T, label %N
  46 N:              ; preds = %0
  47         %C2 = icmp eq i32 %V, 17                ; <i1> [#uses=1]
  48         br i1 %C2, label %T, label %F
  49 T:              ; preds = %N, %0
  50         call void @foo1( )
  51         ret void
  52 F:              ; preds = %N
  53         call void @foo2( )
  54         ret void
  55
  56 ; CHECK-LABEL: @test3(
  57 ; CHECK: switch i32 %V, label %F [
  58 ; CHECK:     i32 4, label %T
  59 ; CHECK:     i32 17, label %T
  60 ; CHECK:   ]
  61 }
  62
  63
  64
  65 define i32 @test4(i8 zeroext %c) nounwind ssp noredzone {
  66 entry:
  67   %cmp = icmp eq i8 %c, 62
  68   br i1 %cmp, label %lor.end, label %lor.lhs.false
  69
  70 lor.lhs.false:                                    ; preds = %entry
  71   %cmp4 = icmp eq i8 %c, 34
  72   br i1 %cmp4, label %lor.end, label %lor.rhs
  73
  74 lor.rhs:                                          ; preds = %lor.lhs.false
  75   %cmp8 = icmp eq i8 %c, 92
  76   br label %lor.end
  77
  78 lor.end:                                          ; preds = %lor.rhs, %lor.lhs.false, %entry
  79   %0 = phi i1 [ true, %lor.lhs.false ], [ true, %entry ], [ %cmp8, %lor.rhs ]
  80   %lor.ext = zext i1 %0 to i32
  81   ret i32 %lor.ext
  82
  83 ; CHECK-LABEL: @test4(
  84 ; CHECK:  switch i8 %c, label %lor.rhs [
  85 ; CHECK:    i8 62, label %lor.end
  86 ; CHECK:    i8 34, label %lor.end
  87 ; CHECK:    i8 92, label %lor.end
  88 ; CHECK:  ]
  89 }
  90
  91 define i32 @test5(i8 zeroext %c) nounwind ssp noredzone {
  92 entry:
  93   switch i8 %c, label %lor.rhs [
  94     i8 62, label %lor.end
  95     i8 34, label %lor.end
  96     i8 92, label %lor.end
  97   ]
  98
  99 lor.rhs:                                          ; preds = %entry
 100   %V = icmp eq i8 %c, 92
 101   br label %lor.end
 102
 103 lor.end:                                          ; preds = %entry, %entry, %entry, %lor.rhs
 104   %0 = phi i1 [ true, %entry ], [ %V, %lor.rhs ], [ true, %entry ], [ true, %entry ]
 105   %lor.ext = zext i1 %0 to i32
 106   ret i32 %lor.ext
 107 ; CHECK-LABEL: @test5(
 108 ; CHECK:  switch i8 %c, label %lor.rhs [
 109 ; CHECK:    i8 62, label %lor.end
 110 ; CHECK:    i8 34, label %lor.end
 111 ; CHECK:    i8 92, label %lor.end
 112 ; CHECK:  ]
 113 }
 114
 115
 116 define i1 @test6({ i32, i32 }* %I) {
 117 entry:
 118         %tmp.1.i = getelementptr { i32, i32 }* %I, i64 0, i32 1         ; <i32*> [#uses=1]
 119         %tmp.2.i = load i32* %tmp.1.i           ; <i32> [#uses=6]
 120         %tmp.2 = icmp eq i32 %tmp.2.i, 14               ; <i1> [#uses=1]
 121         br i1 %tmp.2, label %shortcirc_done.4, label %shortcirc_next.0
 122 shortcirc_next.0:               ; preds = %entry
 123         %tmp.6 = icmp eq i32 %tmp.2.i, 15               ; <i1> [#uses=1]
 124         br i1 %tmp.6, label %shortcirc_done.4, label %shortcirc_next.1
 125 shortcirc_next.1:               ; preds = %shortcirc_next.0
 126         %tmp.11 = icmp eq i32 %tmp.2.i, 16              ; <i1> [#uses=1]
 127         br i1 %tmp.11, label %shortcirc_done.4, label %shortcirc_next.2
 128 shortcirc_next.2:               ; preds = %shortcirc_next.1
 129         %tmp.16 = icmp eq i32 %tmp.2.i, 17              ; <i1> [#uses=1]
 130         br i1 %tmp.16, label %shortcirc_done.4, label %shortcirc_next.3
 131 shortcirc_next.3:               ; preds = %shortcirc_next.2
 132         %tmp.21 = icmp eq i32 %tmp.2.i, 18              ; <i1> [#uses=1]
 133         br i1 %tmp.21, label %shortcirc_done.4, label %shortcirc_next.4
 134 shortcirc_next.4:               ; preds = %shortcirc_next.3
 135         %tmp.26 = icmp eq i32 %tmp.2.i, 19              ; <i1> [#uses=1]
 136         br label %UnifiedReturnBlock
 137 shortcirc_done.4:               ; preds = %shortcirc_next.3, %shortcirc_next.2, %shortcirc_next.1, %shortcirc_next.0, %entry
 138         br label %UnifiedReturnBlock
 139 UnifiedReturnBlock:             ; preds = %shortcirc_done.4, %shortcirc_next.4
 140         %UnifiedRetVal = phi i1 [ %tmp.26, %shortcirc_next.4 ], [ true, %shortcirc_done.4 ]             ; <i1> [#uses=1]
 141         ret i1 %UnifiedRetVal
 142
 143 ; CHECK-LABEL: @test6(
 144 ; CHECK: %tmp.2.i.off = add i32 %tmp.2.i, -14
 145 ; CHECK: %switch = icmp ult i32 %tmp.2.i.off, 6
 146 }
 147
 148 define void @test7(i8 zeroext %c, i32 %x) nounwind ssp noredzone {
 149 entry:
 150   %cmp = icmp ult i32 %x, 32
 151   %cmp4 = icmp eq i8 %c, 97
 152   %or.cond = or i1 %cmp, %cmp4
 153   %cmp9 = icmp eq i8 %c, 99
 154   %or.cond11 = or i1 %or.cond, %cmp9
 155   br i1 %or.cond11, label %if.then, label %if.end
 156
 157 if.then:                                          ; preds = %entry
 158   tail call void @foo1() nounwind noredzone
 159   ret void
 160
 161 if.end:                                           ; preds = %entry
 162   ret void
 163
 164 ; CHECK-LABEL: @test7(
 165 ; CHECK:   %cmp = icmp ult i32 %x, 32
 166 ; CHECK:   br i1 %cmp, label %if.then, label %switch.early.test
 167 ; CHECK: switch.early.test:
 168 ; CHECK:   switch i8 %c, label %if.end [
 169 ; CHECK:     i8 99, label %if.then
 170 ; CHECK:     i8 97, label %if.then
 171 ; CHECK:   ]
 172 }
 173
 174 define i32 @test8(i8 zeroext %c, i32 %x, i1 %C) nounwind ssp noredzone {
 175 entry:
 176   br i1 %C, label %N, label %if.then
 177 N:
 178   %cmp = icmp ult i32 %x, 32
 179   %cmp4 = icmp eq i8 %c, 97
 180   %or.cond = or i1 %cmp, %cmp4
 181   %cmp9 = icmp eq i8 %c, 99
 182   %or.cond11 = or i1 %or.cond, %cmp9
 183   br i1 %or.cond11, label %if.then, label %if.end
 184
 185 if.then:                                          ; preds = %entry
 186   %A = phi i32 [0, %entry], [42, %N]
 187   tail call void @foo1() nounwind noredzone
 188   ret i32 %A
 189
 190 if.end:                                           ; preds = %entry
 191   ret i32 0
 192
 193 ; CHECK-LABEL: @test8(
 194 ; CHECK: switch.early.test:
 195 ; CHECK:   switch i8 %c, label %if.end [
 196 ; CHECK:     i8 99, label %if.then
 197 ; CHECK:     i8 97, label %if.then
 198 ; CHECK:   ]
 199 ; CHECK:   %A = phi i32 [ 0, %entry ], [ 42, %switch.early.test ], [ 42, %N ], [ 42, %switch.early.test ]
 200 }
 201
 202 ;; This is "Example 7" from http://blog.regehr.org/archives/320
 203 define i32 @test9(i8 zeroext %c) nounwind ssp noredzone {
 204 entry:
 205   %cmp = icmp ult i8 %c, 33
 206   br i1 %cmp, label %lor.end, label %lor.lhs.false
 207
 208 lor.lhs.false:                                    ; preds = %entry
 209   %cmp4 = icmp eq i8 %c, 46
 210   br i1 %cmp4, label %lor.end, label %lor.lhs.false6
 211
 212 lor.lhs.false6:                                   ; preds = %lor.lhs.false
 213   %cmp9 = icmp eq i8 %c, 44
 214   br i1 %cmp9, label %lor.end, label %lor.lhs.false11
 215
 216 lor.lhs.false11:                                  ; preds = %lor.lhs.false6
 217   %cmp14 = icmp eq i8 %c, 58
 218   br i1 %cmp14, label %lor.end, label %lor.lhs.false16
 219
 220 lor.lhs.false16:                                  ; preds = %lor.lhs.false11
 221   %cmp19 = icmp eq i8 %c, 59
 222   br i1 %cmp19, label %lor.end, label %lor.lhs.false21
 223
 224 lor.lhs.false21:                                  ; preds = %lor.lhs.false16
 225   %cmp24 = icmp eq i8 %c, 60
 226   br i1 %cmp24, label %lor.end, label %lor.lhs.false26
 227
 228 lor.lhs.false26:                                  ; preds = %lor.lhs.false21
 229   %cmp29 = icmp eq i8 %c, 62
 230   br i1 %cmp29, label %lor.end, label %lor.lhs.false31
 231
 232 lor.lhs.false31:                                  ; preds = %lor.lhs.false26
 233   %cmp34 = icmp eq i8 %c, 34
 234   br i1 %cmp34, label %lor.end, label %lor.lhs.false36
 235
 236 lor.lhs.false36:                                  ; preds = %lor.lhs.false31
 237   %cmp39 = icmp eq i8 %c, 92
 238   br i1 %cmp39, label %lor.end, label %lor.rhs
 239
 240 lor.rhs:                                          ; preds = %lor.lhs.false36
 241   %cmp43 = icmp eq i8 %c, 39
 242   br label %lor.end
 243
 244 lor.end:                                          ; preds = %lor.rhs, %lor.lhs.false36, %lor.lhs.false31, %lor.lhs.false26, %lor.lhs.false21, %lor.lhs.false16, %lor.lhs.false11, %lor.lhs.false6, %lor.lhs.false, %entry
 245   %0 = phi i1 [ true, %lor.lhs.false36 ], [ true, %lor.lhs.false31 ], [ true, %lor.lhs.false26 ], [ true, %lor.lhs.false21 ], [ true, %lor.lhs.false16 ], [ true, %lor.lhs.false11 ], [ true, %lor.lhs.false6 ], [ true, %lor.lhs.false ], [ true, %entry ], [ %cmp43, %lor.rhs ]
 246   %conv46 = zext i1 %0 to i32
 247   ret i32 %conv46
 248
 249 ; CHECK-LABEL: @test9(
 250 ; CHECK:   %cmp = icmp ult i8 %c, 33
 251 ; CHECK:   br i1 %cmp, label %lor.end, label %switch.early.test
 252
 253 ; CHECK: switch.early.test:
 254 ; CHECK:   switch i8 %c, label %lor.rhs [
 255 ; CHECK:     i8 92, label %lor.end
 256 ; CHECK:     i8 62, label %lor.end
 257 ; CHECK:     i8 60, label %lor.end
 258 ; CHECK:     i8 59, label %lor.end
 259 ; CHECK:     i8 58, label %lor.end
 260 ; CHECK:     i8 46, label %lor.end
 261 ; CHECK:     i8 44, label %lor.end
 262 ; CHECK:     i8 34, label %lor.end
 263 ; CHECK:     i8 39, label %lor.end
 264 ; CHECK:   ]
 265 }
 266
 267 define i32 @test10(i32 %mode, i1 %Cond) {
 268   %A = icmp ne i32 %mode, 0
 269   %B = icmp ne i32 %mode, 51
 270   %C = and i1 %A, %B
 271   %D = and i1 %C, %Cond
 272   br i1 %D, label %T, label %F
 273 T:
 274   ret i32 123
 275 F:
 276   ret i32 324
 277
 278 ; CHECK-LABEL: @test10(
 279 ; CHECK:  br i1 %Cond, label %switch.early.test, label %F
 280 ; CHECK:switch.early.test:
 281 ; CHECK:  switch i32 %mode, label %T [
 282 ; CHECK:    i32 51, label %F
 283 ; CHECK:    i32 0, label %F
 284 ; CHECK:  ]
 285 }
 286
 287 ; PR8780
 288 define i32 @test11(i32 %bar) nounwind {
 289 entry:
 290   %cmp = icmp eq i32 %bar, 4
 291   %cmp2 = icmp eq i32 %bar, 35
 292   %or.cond = or i1 %cmp, %cmp2
 293   %cmp5 = icmp eq i32 %bar, 53
 294   %or.cond1 = or i1 %or.cond, %cmp5
 295   %cmp8 = icmp eq i32 %bar, 24
 296   %or.cond2 = or i1 %or.cond1, %cmp8
 297   %cmp11 = icmp eq i32 %bar, 23
 298   %or.cond3 = or i1 %or.cond2, %cmp11
 299   %cmp14 = icmp eq i32 %bar, 55
 300   %or.cond4 = or i1 %or.cond3, %cmp14
 301   %cmp17 = icmp eq i32 %bar, 12
 302   %or.cond5 = or i1 %or.cond4, %cmp17
 303   %cmp20 = icmp eq i32 %bar, 35
 304   %or.cond6 = or i1 %or.cond5, %cmp20
 305   br i1 %or.cond6, label %if.then, label %if.end
 306
 307 if.then:                                          ; preds = %entry
 308   br label %return
 309
 310 if.end:                                           ; preds = %entry
 311   br label %return
 312
 313 return:                                           ; preds = %if.end, %if.then
 314   %retval.0 = phi i32 [ 1, %if.then ], [ 0, %if.end ]
 315   ret i32 %retval.0
 316
 317 ; CHECK-LABEL: @test11(
 318 ; CHECK: switch i32 %bar, label %if.end [
 319 ; CHECK:   i32 55, label %return
 320 ; CHECK:   i32 53, label %return
 321 ; CHECK:   i32 35, label %return
 322 ; CHECK:   i32 24, label %return
 323 ; CHECK:   i32 23, label %return
 324 ; CHECK:   i32 12, label %return
 325 ; CHECK:   i32 4, label %return
 326 ; CHECK: ]
 327 }
 328
 329 define void @test12() nounwind {
 330 entry:
 331   br label %bb49.us.us
 332
 333 bb49.us.us:
 334   %A = icmp eq i32 undef, undef
 335   br i1 %A, label %bb55.us.us, label %malformed
 336
 337 bb48.us.us:
 338   %B = icmp ugt i32 undef, undef
 339   br i1 %B, label %bb55.us.us, label %bb49.us.us
 340
 341 bb55.us.us:
 342   br label %bb48.us.us
 343
 344 malformed:
 345   ret void
 346 ; CHECK-LABEL: @test12(
 347
 348 }
 349
 350 ; test13 - handle switch formation with ult.
 351 define void @test13(i32 %x) nounwind ssp noredzone {
 352 entry:
 353   %cmp = icmp ult i32 %x, 2
 354   br i1 %cmp, label %if.then, label %lor.lhs.false3
 355
 356 lor.lhs.false3:                                   ; preds = %lor.lhs.false
 357   %cmp5 = icmp eq i32 %x, 3
 358   br i1 %cmp5, label %if.then, label %lor.lhs.false6
 359
 360 lor.lhs.false6:                                   ; preds = %lor.lhs.false3
 361   %cmp8 = icmp eq i32 %x, 4
 362   br i1 %cmp8, label %if.then, label %lor.lhs.false9
 363
 364 lor.lhs.false9:                                   ; preds = %lor.lhs.false6
 365   %cmp11 = icmp eq i32 %x, 6
 366   br i1 %cmp11, label %if.then, label %if.end
 367
 368 if.then:                                          ; preds = %lor.lhs.false9, %lor.lhs.false6, %lor.lhs.false3, %lor.lhs.false, %entry
 369   call void @foo1() noredzone
 370   br label %if.end
 371
 372 if.end:                                           ; preds = %if.then, %lor.lhs.false9
 373   ret void
 374 ; CHECK-LABEL: @test13(
 375 ; CHECK:  switch i32 %x, label %if.end [
 376 ; CHECK:     i32 6, label %if.then
 377 ; CHECK:     i32 4, label %if.then
 378 ; CHECK:     i32 3, label %if.then
 379 ; CHECK:     i32 1, label %if.then
 380 ; CHECK:     i32 0, label %if.then
 381 ; CHECK:   ]
 382 }
 383
 384 ; test14 - handle switch formation with ult.
 385 define void @test14(i32 %x) nounwind ssp noredzone {
 386 entry:
 387   %cmp = icmp ugt i32 %x, 2
 388   br i1 %cmp, label %lor.lhs.false3, label %if.then
 389
 390 lor.lhs.false3:                                   ; preds = %lor.lhs.false
 391   %cmp5 = icmp ne i32 %x, 3
 392   br i1 %cmp5, label %lor.lhs.false6, label %if.then
 393
 394 lor.lhs.false6:                                   ; preds = %lor.lhs.false3
 395   %cmp8 = icmp ne i32 %x, 4
 396   br i1 %cmp8, label %lor.lhs.false9, label %if.then
 397
 398 lor.lhs.false9:                                   ; preds = %lor.lhs.false6
 399   %cmp11 = icmp ne i32 %x, 6
 400   br i1 %cmp11, label %if.end, label %if.then
 401
 402 if.then:                                          ; preds = %lor.lhs.false9, %lor.lhs.false6, %lor.lhs.false3, %lor.lhs.false, %entry
 403   call void @foo1() noredzone
 404   br label %if.end
 405
 406 if.end:                                           ; preds = %if.then, %lor.lhs.false9
 407   ret void
 408 ; CHECK-LABEL: @test14(
 409 ; CHECK:  switch i32 %x, label %if.end [
 410 ; CHECK:     i32 6, label %if.then
 411 ; CHECK:     i32 4, label %if.then
 412 ; CHECK:     i32 3, label %if.then
 413 ; CHECK:     i32 1, label %if.then
 414 ; CHECK:     i32 0, label %if.then
 415 ; CHECK:   ]
 416 }
 417
 418 ; Don't crash on ginormous ranges.
 419 define void @test15(i128 %x) nounwind {
 420   %cmp = icmp ugt i128 %x, 2
 421   br i1 %cmp, label %if.end, label %lor.false
 422
 423 lor.false:
 424   %cmp2 = icmp ne i128 %x, 100000000000000000000
 425   br i1 %cmp2, label %if.end, label %if.then
 426
 427 if.then:
 428   call void @foo1() noredzone
 429   br label %if.end
 430
 431 if.end:
 432   ret void
 433
 434 ; CHECK-LABEL: @test15(
 435 ; CHECK-NOT: switch
 436 ; CHECK: ret void
 437 }
 438
 439 ; PR8675
 440 ; rdar://5134905
 441 define zeroext i1 @test16(i32 %x) nounwind {
 442 entry:
 443 ; CHECK-LABEL: @test16(
 444 ; CHECK: %x.off = add i32 %x, -1
 445 ; CHECK: %switch = icmp ult i32 %x.off, 3
 446   %cmp.i = icmp eq i32 %x, 1
 447   br i1 %cmp.i, label %lor.end, label %lor.lhs.false
 448
 449 lor.lhs.false:
 450   %cmp.i2 = icmp eq i32 %x, 2
 451   br i1 %cmp.i2, label %lor.end, label %lor.rhs
 452
 453 lor.rhs:
 454   %cmp.i1 = icmp eq i32 %x, 3
 455   br label %lor.end
 456
 457 lor.end:
 458   %0 = phi i1 [ true, %lor.lhs.false ], [ true, %entry ], [ %cmp.i1, %lor.rhs ]
 459   ret i1 %0
 460 }
 461
 462 ; Check that we don't turn an icmp into a switch where it's not useful.
 463 define void @test17(i32 %x, i32 %y) {
 464   %cmp = icmp ult i32 %x, 3
 465   %switch = icmp ult i32 %y, 2
 466   %or.cond775 = or i1 %cmp, %switch
 467   br i1 %or.cond775, label %lor.lhs.false8, label %return
 468
 469 lor.lhs.false8:
 470   tail call void @foo1()
 471   ret void
 472
 473 return:
 474   ret void
 475
 476 ; CHECK-LABEL: @test17(
 477 ; CHECK-NOT: switch.early.test
 478 ; CHECK-NOT: switch i32
 479 ; CHECK: ret void
 480 }
 481
 482 define void @test18(i32 %arg) {
 483 bb:
 484   %tmp = and i32 %arg, -2
 485   %tmp1 = icmp eq i32 %tmp, 8
 486   %tmp2 = icmp eq i32 %arg, 10
 487   %tmp3 = or i1 %tmp1, %tmp2
 488   %tmp4 = icmp eq i32 %arg, 11
 489   %tmp5 = or i1 %tmp3, %tmp4
 490   %tmp6 = icmp eq i32 %arg, 12
 491   %tmp7 = or i1 %tmp5, %tmp6
 492   br i1 %tmp7, label %bb19, label %bb8
 493
 494 bb8:                                              ; preds = %bb
 495   %tmp9 = add i32 %arg, -13
 496   %tmp10 = icmp ult i32 %tmp9, 2
 497   %tmp11 = icmp eq i32 %arg, 16
 498   %tmp12 = or i1 %tmp10, %tmp11
 499   %tmp13 = icmp eq i32 %arg, 17
 500   %tmp14 = or i1 %tmp12, %tmp13
 501   %tmp15 = icmp eq i32 %arg, 18
 502   %tmp16 = or i1 %tmp14, %tmp15
 503   %tmp17 = icmp eq i32 %arg, 15
 504   %tmp18 = or i1 %tmp16, %tmp17
 505   br i1 %tmp18, label %bb19, label %bb20
 506
 507 bb19:                                             ; preds = %bb8, %bb
 508   tail call void @foo1()
 509   br label %bb20
 510
 511 bb20:                                             ; preds = %bb19, %bb8
 512   ret void
 513
 514 ; CHECK-LABEL: @test18(
 515 ; CHECK: %arg.off = add i32 %arg, -8
 516 ; CHECK: icmp ult i32 %arg.off, 11
 517 }