test/Transforms/JumpThreading/basic.ll

   1 ; RUN: opt %s -jump-threading -S -enable-jump-threading-lvi | FileCheck %s
   2
   3 declare i32 @f1()
   4 declare i32 @f2()
   5 declare void @f3()
   6
   7 define i32 @test1(i1 %cond) {
   8 ; CHECK: @test1
   9
  10         br i1 %cond, label %T1, label %F1
  11
  12 T1:
  13         %v1 = call i32 @f1()
  14         br label %Merge
  15
  16 F1:
  17         %v2 = call i32 @f2()
  18         br label %Merge
  19
  20 Merge:
  21         %A = phi i1 [true, %T1], [false, %F1]
  22         %B = phi i32 [%v1, %T1], [%v2, %F1]
  23         br i1 %A, label %T2, label %F2
  24
  25 T2:
  26 ; CHECK: T2:
  27 ; CHECK: ret i32 %v1
  28         call void @f3()
  29         ret i32 %B
  30
  31 F2:
  32 ; CHECK: F2:
  33 ; CHECK: ret i32 %v2
  34         ret i32 %B
  35 }
  36
  37
  38 ;; cond is known false on Entry -> F1 edge!
  39 define i32 @test2(i1 %cond) {
  40 ; CHECK: @test2
  41 Entry:
  42         br i1 %cond, label %T1, label %F1
  43
  44 T1:
  45 ; CHECK: %v1 = call i32 @f1()
  46 ; CHECK: ret i32 47
  47         %v1 = call i32 @f1()
  48         br label %Merge
  49
  50 F1:
  51         br i1 %cond, label %Merge, label %F2
  52
  53 Merge:
  54         %B = phi i32 [47, %T1], [192, %F1]
  55         ret i32 %B
  56
  57 F2:
  58         call void @f3()
  59         ret i32 12
  60 }
  61
  62
  63 ; Undef handling.
  64 define i32 @test3(i1 %cond) {
  65 ; CHECK: @test3
  66 ; CHECK-NEXT: T1:
  67 ; CHECK-NEXT: ret i32 42
  68         br i1 undef, label %T1, label %F1
  69
  70 T1:
  71         ret i32 42
  72
  73 F1:
  74         ret i32 17
  75 }
  76
  77 define i32 @test4(i1 %cond, i1 %cond2) {
  78 ; CHECK: @test4
  79
  80         br i1 %cond, label %T1, label %F1
  81
  82 T1:
  83 ; CHECK:   %v1 = call i32 @f1()
  84 ; CHECK-NEXT:   br label %T
  85
  86         %v1 = call i32 @f1()
  87         br label %Merge
  88
  89 F1:
  90         %v2 = call i32 @f2()
  91 ; CHECK:   %v2 = call i32 @f2()
  92 ; CHECK-NEXT:   br i1 %cond2,
  93         br label %Merge
  94
  95 Merge:
  96         %A = phi i1 [undef, %T1], [%cond2, %F1]
  97         %B = phi i32 [%v1, %T1], [%v2, %F1]
  98         br i1 %A, label %T2, label %F2
  99
 100 T2:
 101         call void @f3()
 102         ret i32 %B
 103
 104 F2:
 105         ret i32 %B
 106 }
 107
 108
 109 ;; This tests that the branch in 'merge' can be cloned up into T1.
 110 define i32 @test5(i1 %cond, i1 %cond2) {
 111 ; CHECK: @test5
 112
 113         br i1 %cond, label %T1, label %F1
 114
 115 T1:
 116 ; CHECK: T1:
 117 ; CHECK-NEXT:   %v1 = call i32 @f1()
 118 ; CHECK-NEXT:   %cond3 = icmp eq i32 %v1, 412
 119 ; CHECK-NEXT:   br i1 %cond3, label %T2, label %F2
 120
 121         %v1 = call i32 @f1()
 122         %cond3 = icmp eq i32 %v1, 412
 123         br label %Merge
 124
 125 F1:
 126         %v2 = call i32 @f2()
 127         br label %Merge
 128
 129 Merge:
 130         %A = phi i1 [%cond3, %T1], [%cond2, %F1]
 131         %B = phi i32 [%v1, %T1], [%v2, %F1]
 132         br i1 %A, label %T2, label %F2
 133
 134 T2:
 135         call void @f3()
 136         ret i32 %B
 137
 138 F2:
 139         ret i32 %B
 140 }
 141
 142
 143 ;; Lexically duplicated conditionals should be threaded.
 144
 145
 146 define i32 @test6(i32 %A) {
 147 ; CHECK: @test6
 148         %tmp455 = icmp eq i32 %A, 42
 149         br i1 %tmp455, label %BB1, label %BB2
 150
 151 BB2:
 152 ; CHECK: call i32 @f1()
 153 ; CHECK-NEXT: call void @f3()
 154 ; CHECK-NEXT: ret i32 4
 155         call i32 @f1()
 156         br label %BB1
 157
 158
 159 BB1:
 160         %tmp459 = icmp eq i32 %A, 42
 161         br i1 %tmp459, label %BB3, label %BB4
 162
 163 BB3:
 164         call i32 @f2()
 165         ret i32 3
 166
 167 BB4:
 168         call void @f3()
 169         ret i32 4
 170 }
 171
 172
 173 ;; This tests that the branch in 'merge' can be cloned up into T1.
 174 ;; rdar://7367025
 175 define i32 @test7(i1 %cond, i1 %cond2) {
 176 Entry:
 177 ; CHECK: @test7
 178         %v1 = call i32 @f1()
 179         br i1 %cond, label %Merge, label %F1
 180
 181 F1:
 182         %v2 = call i32 @f2()
 183         br label %Merge
 184
 185 Merge:
 186         %B = phi i32 [%v1, %Entry], [%v2, %F1]
 187         %M = icmp ne i32 %B, %v1
 188         %N = icmp eq i32 %B, 47
 189         %O = and i1 %M, %N
 190         br i1 %O, label %T2, label %F2
 191
 192 ; CHECK: Merge:
 193 ; CHECK-NOT: phi
 194 ; CHECK-NEXT:   %v2 = call i32 @f2()
 195
 196 T2:
 197         call void @f3()
 198         ret i32 %B
 199
 200 F2:
 201         ret i32 %B
 202 ; CHECK: F2:
 203 ; CHECK-NEXT: phi i32
 204 }
 205
 206
 207 declare i1 @test8a()
 208
 209 define i32 @test8b(i1 %cond, i1 %cond2) {
 210 ; CHECK: @test8b
 211 T0:
 212         %A = call i1 @test8a()
 213         br i1 %A, label %T1, label %F1
 214
 215 ; CHECK: T0:
 216 ; CHECK-NEXT: call
 217 ; CHECK-NEXT: br i1 %A, label %T1, label %Y
 218
 219 T1:
 220         %B = call i1 @test8a()
 221         br i1 %B, label %T2, label %F1
 222
 223 ; CHECK: T1:
 224 ; CHECK-NEXT: call
 225 ; CHECK-NEXT: br i1 %B, label %T2, label %Y
 226 T2:
 227         %C = call i1 @test8a()
 228         br i1 %cond, label %T3, label %F1
 229
 230 ; CHECK: T2:
 231 ; CHECK-NEXT: call
 232 ; CHECK-NEXT: br i1 %cond, label %T3, label %Y
 233 T3:
 234         ret i32 0
 235
 236 F1:
 237         %D = phi i32 [0, %T0], [0, %T1], [1, %T2]
 238         %E = icmp eq i32 %D, 1
 239         %F = and i1 %E, %cond
 240         br i1 %F, label %X, label %Y
 241 X:
 242         call i1 @test8a()
 243         ret i32 1
 244 Y:
 245         ret i32 2
 246 }
 247
 248
 249 ;;; Verify that we can handle constraint propagation through "xor x, 1".
 250 define i32 @test9(i1 %cond, i1 %cond2) {
 251 Entry:
 252 ; CHECK: @test9
 253         %v1 = call i32 @f1()
 254         br i1 %cond, label %Merge, label %F1
 255
 256 ; CHECK: Entry:
 257 ; CHECK-NEXT:  %v1 = call i32 @f1()
 258 ; CHECK-NEXT:  br i1 %cond, label %F2, label %Merge
 259
 260 F1:
 261         %v2 = call i32 @f2()
 262         br label %Merge
 263
 264 Merge:
 265         %B = phi i32 [%v1, %Entry], [%v2, %F1]
 266         %M = icmp eq i32 %B, %v1
 267         %M1 = xor i1 %M, 1
 268         %N = icmp eq i32 %B, 47
 269         %O = and i1 %M1, %N
 270         br i1 %O, label %T2, label %F2
 271
 272 ; CHECK: Merge:
 273 ; CHECK-NOT: phi
 274 ; CHECK-NEXT:   %v2 = call i32 @f2()
 275
 276 T2:
 277         %Q = zext i1 %M to i32
 278         ret i32 %Q
 279
 280 F2:
 281         ret i32 %B
 282 ; CHECK: F2:
 283 ; CHECK-NEXT: phi i32
 284 }
 285
 286
 287
 288 ; CHECK: @test10
 289 declare i32 @test10f1()
 290 declare i32 @test10f2()
 291 declare void @test10f3()
 292
 293 ;; Non-local condition threading.
 294 define i32 @test10g(i1 %cond) {
 295 ; CHECK: @test10g
 296 ; CHECK-NEXT:   br i1 %cond, label %T2, label %F2
 297         br i1 %cond, label %T1, label %F1
 298
 299 T1:
 300         %v1 = call i32 @test10f1()
 301         br label %Merge
 302
 303 ; CHECK: %v1 = call i32 @test10f1()
 304 ; CHECK-NEXT: call void @f3()
 305 ; CHECK-NEXT: ret i32 %v1
 306
 307 F1:
 308         %v2 = call i32 @test10f2()
 309         br label %Merge
 310
 311 Merge:
 312         %B = phi i32 [%v1, %T1], [%v2, %F1]
 313         br i1 %cond, label %T2, label %F2
 314
 315 T2:
 316         call void @f3()
 317         ret i32 %B
 318
 319 F2:
 320         ret i32 %B
 321 }
 322
 323
 324 ; Impossible conditional constraints should get threaded.  BB3 is dead here.
 325 define i32 @test11(i32 %A) {
 326 ; CHECK: @test11
 327 ; CHECK-NEXT: icmp
 328 ; CHECK-NEXT: br i1 %tmp455, label %BB4, label %BB2
 329         %tmp455 = icmp eq i32 %A, 42
 330         br i1 %tmp455, label %BB1, label %BB2
 331
 332 BB2:
 333 ; CHECK: call i32 @f1()
 334 ; CHECK-NEXT: ret i32 %C
 335         %C = call i32 @f1()
 336         ret i32 %C
 337
 338
 339 BB1:
 340         %tmp459 = icmp eq i32 %A, 43
 341         br i1 %tmp459, label %BB3, label %BB4
 342
 343 BB3:
 344         call i32 @f2()
 345         ret i32 3
 346
 347 BB4:
 348         call void @f3()
 349         ret i32 4
 350 }
 351
 352 ;; Correlated value through boolean expression.  GCC PR18046.
 353 define void @test12(i32 %A) {
 354 ; CHECK: @test12
 355 entry:
 356   %cond = icmp eq i32 %A, 0
 357   br i1 %cond, label %bb, label %bb1
 358 ; Should branch to the return block instead of through BB1.
 359 ; CHECK: entry:
 360 ; CHECK-NEXT: %cond = icmp eq i32 %A, 0
 361 ; CHECK-NEXT: br i1 %cond, label %bb1, label %return
 362
 363 bb:
 364   %B = call i32 @test10f2()
 365   br label %bb1
 366
 367 bb1:
 368   %C = phi i32 [ %A, %entry ], [ %B, %bb ]
 369   %cond4 = icmp eq i32 %C, 0
 370   br i1 %cond4, label %bb2, label %return
 371
 372 ; CHECK: bb1:
 373 ; CHECK-NEXT: %B = call i32 @test10f2()
 374 ; CHECK-NEXT: %cond4 = icmp eq i32 %B, 0
 375 ; CHECK-NEXT: br i1 %cond4, label %bb2, label %return
 376
 377 bb2:
 378   %D = call i32 @test10f2()
 379   ret void
 380
 381 return:
 382   ret void
 383 }
 384
 385
 386 ;;; Duplicate condition to avoid xor of cond.
 387 ;;; TODO: Make this happen.
 388 define i32 @testXX(i1 %cond, i1 %cond2) {
 389 Entry:
 390 ; CHECK: @testXX
 391         %v1 = call i32 @f1()
 392         br i1 %cond, label %Merge, label %F1
 393
 394 F1:
 395         br label %Merge
 396
 397 Merge:
 398         %B = phi i1 [true, %Entry], [%cond2, %F1]
 399         %M = icmp eq i32 %v1, 192
 400         %N = xor i1 %B, %M
 401         br i1 %N, label %T2, label %F2
 402
 403 T2:
 404         ret i32 123
 405
 406 F2:
 407         ret i32 %v1
 408 }
 409
 410