llvm/test/Transforms/JumpThreading/thread-loads.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -jump-threading -S | FileCheck %s
   3 ; RUN: opt < %s -aa-pipeline=basic-aa -passes=jump-threading -S | FileCheck %s
   4
   5 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
   6 target triple = "i386-apple-darwin7"
   7
   8 ; Test that we can thread through the block with the partially redundant load (%2).
   9 ; rdar://6402033
  10 define i32 @test1(i32* %P) nounwind {
  11 ; CHECK-LABEL: @test1(
  12 ; CHECK-NEXT:  entry:
  13 ; CHECK-NEXT:    [[TMP0:%.*]] = tail call i32 (...) @f1() #[[ATTR0:[0-9]+]]
  14 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 0
  15 ; CHECK-NEXT:    br i1 [[TMP1]], label [[BB1:%.*]], label [[BB1_THREAD:%.*]]
  16 ; CHECK:       bb1.thread:
  17 ; CHECK-NEXT:    store i32 42, i32* [[P:%.*]], align 4
  18 ; CHECK-NEXT:    br label [[BB3:%.*]]
  19 ; CHECK:       bb1:
  20 ; CHECK-NEXT:    [[DOTPR:%.*]] = load i32, i32* [[P]], align 4
  21 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[DOTPR]], 36
  22 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB3]], label [[BB2:%.*]]
  23 ; CHECK:       bb2:
  24 ; CHECK-NEXT:    [[TMP3:%.*]] = tail call i32 (...) @f2() #[[ATTR0]]
  25 ; CHECK-NEXT:    ret i32 0
  26 ; CHECK:       bb3:
  27 ; CHECK-NEXT:    [[RES_02:%.*]] = phi i32 [ 1, [[BB1_THREAD]] ], [ 0, [[BB1]] ]
  28 ; CHECK-NEXT:    ret i32 [[RES_02]]
  29 ;
  30 entry:
  31   %0 = tail call i32 (...) @f1() nounwind               ; <i32> [#uses=1]
  32   %1 = icmp eq i32 %0, 0                ; <i1> [#uses=1]
  33   br i1 %1, label %bb1, label %bb
  34
  35 bb:             ; preds = %entry
  36   store i32 42, i32* %P, align 4
  37   br label %bb1
  38
  39 bb1:            ; preds = %entry, %bb
  40   %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]            ; <i32> [#uses=2]
  41   %2 = load i32, i32* %P, align 4               ; <i32> [#uses=1]
  42   %3 = icmp sgt i32 %2, 36              ; <i1> [#uses=1]
  43   br i1 %3, label %bb3, label %bb2
  44
  45 bb2:            ; preds = %bb1
  46   %4 = tail call i32 (...) @f2() nounwind               ; <i32> [#uses=0]
  47   ret i32 %res.0
  48
  49 bb3:            ; preds = %bb1
  50   ret i32 %res.0
  51 }
  52
  53 declare i32 @f1(...)
  54
  55 declare i32 @f2(...)
  56
  57
  58 ;; Check that we preserve TBAA information.
  59 ; rdar://11039258
  60
  61 define i32 @test2(i32* %P) nounwind {
  62 ; CHECK-LABEL: @test2(
  63 ; CHECK-NEXT:  entry:
  64 ; CHECK-NEXT:    [[TMP0:%.*]] = tail call i32 (...) @f1() #[[ATTR0]]
  65 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 0
  66 ; CHECK-NEXT:    br i1 [[TMP1]], label [[BB1:%.*]], label [[BB1_THREAD:%.*]]
  67 ; CHECK:       bb1.thread:
  68 ; CHECK-NEXT:    store i32 42, i32* [[P:%.*]], align 4, !tbaa [[TBAA0:![0-9]+]]
  69 ; CHECK-NEXT:    br label [[BB3:%.*]]
  70 ; CHECK:       bb1:
  71 ; CHECK-NEXT:    [[DOTPR:%.*]] = load i32, i32* [[P]], align 4, !tbaa [[TBAA0]]
  72 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[DOTPR]], 36
  73 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB3]], label [[BB2:%.*]]
  74 ; CHECK:       bb2:
  75 ; CHECK-NEXT:    [[TMP3:%.*]] = tail call i32 (...) @f2() #[[ATTR0]]
  76 ; CHECK-NEXT:    ret i32 0
  77 ; CHECK:       bb3:
  78 ; CHECK-NEXT:    [[RES_02:%.*]] = phi i32 [ 1, [[BB1_THREAD]] ], [ 0, [[BB1]] ]
  79 ; CHECK-NEXT:    ret i32 [[RES_02]]
  80 ;
  81 entry:
  82   %0 = tail call i32 (...) @f1() nounwind               ; <i32> [#uses=1]
  83   %1 = icmp eq i32 %0, 0                ; <i1> [#uses=1]
  84   br i1 %1, label %bb1, label %bb
  85
  86 bb:             ; preds = %entry
  87   store i32 42, i32* %P, align 4, !tbaa !0
  88   br label %bb1
  89
  90 bb1:            ; preds = %entry, %bb
  91   %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]
  92   %2 = load i32, i32* %P, align 4, !tbaa !0
  93   %3 = icmp sgt i32 %2, 36
  94   br i1 %3, label %bb3, label %bb2
  95
  96 bb2:            ; preds = %bb1
  97   %4 = tail call i32 (...) @f2() nounwind
  98   ret i32 %res.0
  99
 100 bb3:            ; preds = %bb1
 101   ret i32 %res.0
 102 }
 103
 104 define i32 @test3(i8** %x, i1 %f) {
 105 ; Correctly thread loads of different (but compatible) types, placing bitcasts
 106 ; as necessary in the predecessors. This is especially tricky because the same
 107 ; predecessor ends up with two entries in the PHI node and they must share
 108 ; a single cast.
 109 ; CHECK-LABEL: @test3(
 110 ; CHECK-NEXT:  entry:
 111 ; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i8** [[X:%.*]] to i32**
 112 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32*, i32** [[TMP0]], align 8
 113 ; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i32* [[TMP1]] to i8*
 114 ; CHECK-NEXT:    br i1 [[F:%.*]], label [[IF_END57:%.*]], label [[IF_END57]]
 115 ; CHECK:       if.end57:
 116 ; CHECK-NEXT:    [[TMP3:%.*]] = phi i8* [ [[TMP2]], [[ENTRY:%.*]] ], [ [[TMP2]], [[ENTRY]] ]
 117 ; CHECK-NEXT:    [[TOBOOL59:%.*]] = icmp eq i8* [[TMP3]], null
 118 ; CHECK-NEXT:    br i1 [[TOBOOL59]], label [[RETURN:%.*]], label [[IF_THEN60:%.*]]
 119 ; CHECK:       if.then60:
 120 ; CHECK-NEXT:    ret i32 42
 121 ; CHECK:       return:
 122 ; CHECK-NEXT:    ret i32 13
 123 ;
 124 entry:
 125   %0 = bitcast i8** %x to i32**
 126   %1 = load i32*, i32** %0, align 8
 127   br i1 %f, label %if.end57, label %if.then56
 128
 129 if.then56:
 130   br label %if.end57
 131
 132 if.end57:
 133   %2 = load i8*, i8** %x, align 8
 134   %tobool59 = icmp eq i8* %2, null
 135   br i1 %tobool59, label %return, label %if.then60
 136
 137 if.then60:
 138   ret i32 42
 139
 140 return:
 141   ret i32 13
 142 }
 143
 144 define i32 @test4(i32* %P) {
 145 ; CHECK-LABEL: @test4(
 146 ; CHECK-NEXT:  entry:
 147 ; CHECK-NEXT:    [[V0:%.*]] = tail call i32 (...) @f1()
 148 ; CHECK-NEXT:    [[V1:%.*]] = icmp eq i32 [[V0]], 0
 149 ; CHECK-NEXT:    br i1 [[V1]], label [[BB1:%.*]], label [[BB1_THREAD:%.*]]
 150 ; CHECK:       bb1.thread:
 151 ; CHECK-NEXT:    store atomic i32 42, i32* [[P:%.*]] unordered, align 4
 152 ; CHECK-NEXT:    br label [[BB3:%.*]]
 153 ; CHECK:       bb1:
 154 ; CHECK-NEXT:    [[V2_PR:%.*]] = load atomic i32, i32* [[P]] unordered, align 4
 155 ; CHECK-NEXT:    [[V3:%.*]] = icmp sgt i32 [[V2_PR]], 36
 156 ; CHECK-NEXT:    br i1 [[V3]], label [[BB3]], label [[BB2:%.*]]
 157 ; CHECK:       bb2:
 158 ; CHECK-NEXT:    [[V4:%.*]] = tail call i32 (...) @f2()
 159 ; CHECK-NEXT:    ret i32 0
 160 ; CHECK:       bb3:
 161 ; CHECK-NEXT:    [[RES_04:%.*]] = phi i32 [ 1, [[BB1_THREAD]] ], [ 0, [[BB1]] ]
 162 ; CHECK-NEXT:    ret i32 [[RES_04]]
 163 ;
 164 entry:
 165   %v0 = tail call i32 (...) @f1()
 166   %v1 = icmp eq i32 %v0, 0
 167   br i1 %v1, label %bb1, label %bb
 168
 169 bb:
 170   store atomic i32 42, i32* %P unordered, align 4
 171   br label %bb1
 172
 173 bb1:
 174   %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]
 175   %v2 = load atomic i32, i32* %P unordered, align 4
 176   %v3 = icmp sgt i32 %v2, 36
 177   br i1 %v3, label %bb3, label %bb2
 178
 179 bb2:
 180   %v4 = tail call i32 (...) @f2()
 181   ret i32 %res.0
 182
 183 bb3:
 184   ret i32 %res.0
 185 }
 186
 187 define i32 @test5(i32* %P) {
 188 ; Negative test
 189 ; CHECK-LABEL: @test5(
 190 ; CHECK-NEXT:  entry:
 191 ; CHECK-NEXT:    [[V0:%.*]] = tail call i32 (...) @f1()
 192 ; CHECK-NEXT:    [[V1:%.*]] = icmp eq i32 [[V0]], 0
 193 ; CHECK-NEXT:    br i1 [[V1]], label [[BB1:%.*]], label [[BB:%.*]]
 194 ; CHECK:       bb:
 195 ; CHECK-NEXT:    store atomic i32 42, i32* [[P:%.*]] release, align 4
 196 ; CHECK-NEXT:    br label [[BB1]]
 197 ; CHECK:       bb1:
 198 ; CHECK-NEXT:    [[RES_0:%.*]] = phi i32 [ 1, [[BB]] ], [ 0, [[ENTRY:%.*]] ]
 199 ; CHECK-NEXT:    [[V2:%.*]] = load atomic i32, i32* [[P]] acquire, align 4
 200 ; CHECK-NEXT:    [[V3:%.*]] = icmp sgt i32 [[V2]], 36
 201 ; CHECK-NEXT:    br i1 [[V3]], label [[BB3:%.*]], label [[BB2:%.*]]
 202 ; CHECK:       bb2:
 203 ; CHECK-NEXT:    [[V4:%.*]] = tail call i32 (...) @f2()
 204 ; CHECK-NEXT:    ret i32 [[RES_0]]
 205 ; CHECK:       bb3:
 206 ; CHECK-NEXT:    ret i32 [[RES_0]]
 207 ;
 208 entry:
 209   %v0 = tail call i32 (...) @f1()
 210   %v1 = icmp eq i32 %v0, 0
 211   br i1 %v1, label %bb1, label %bb
 212
 213 bb:
 214   store atomic i32 42, i32* %P release, align 4
 215   br label %bb1
 216
 217 bb1:
 218
 219   %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]
 220   %v2 = load atomic i32, i32* %P acquire, align 4
 221   %v3 = icmp sgt i32 %v2, 36
 222   br i1 %v3, label %bb3, label %bb2
 223
 224 bb2:
 225   %v4 = tail call i32 (...) @f2()
 226   ret i32 %res.0
 227
 228 bb3:
 229   ret i32 %res.0
 230 }
 231
 232 define i32 @test6(i32* %P) {
 233 ; Negative test
 234 ; CHECK-LABEL: @test6(
 235 ; CHECK-NEXT:  entry:
 236 ; CHECK-NEXT:    [[V0:%.*]] = tail call i32 (...) @f1()
 237 ; CHECK-NEXT:    [[V1:%.*]] = icmp eq i32 [[V0]], 0
 238 ; CHECK-NEXT:    br i1 [[V1]], label [[BB1:%.*]], label [[BB:%.*]]
 239 ; CHECK:       bb:
 240 ; CHECK-NEXT:    store i32 42, i32* [[P:%.*]], align 4
 241 ; CHECK-NEXT:    br label [[BB1]]
 242 ; CHECK:       bb1:
 243 ; CHECK-NEXT:    [[RES_0:%.*]] = phi i32 [ 1, [[BB]] ], [ 0, [[ENTRY:%.*]] ]
 244 ; CHECK-NEXT:    [[V2:%.*]] = load atomic i32, i32* [[P]] acquire, align 4
 245 ; CHECK-NEXT:    [[V3:%.*]] = icmp sgt i32 [[V2]], 36
 246 ; CHECK-NEXT:    br i1 [[V3]], label [[BB3:%.*]], label [[BB2:%.*]]
 247 ; CHECK:       bb2:
 248 ; CHECK-NEXT:    [[V4:%.*]] = tail call i32 (...) @f2()
 249 ; CHECK-NEXT:    ret i32 [[RES_0]]
 250 ; CHECK:       bb3:
 251 ; CHECK-NEXT:    ret i32 [[RES_0]]
 252 ;
 253 entry:
 254   %v0 = tail call i32 (...) @f1()
 255   %v1 = icmp eq i32 %v0, 0
 256   br i1 %v1, label %bb1, label %bb
 257
 258 bb:
 259   store i32 42, i32* %P
 260   br label %bb1
 261
 262 bb1:
 263
 264   %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]
 265   %v2 = load atomic i32, i32* %P acquire, align 4
 266   %v3 = icmp sgt i32 %v2, 36
 267   br i1 %v3, label %bb3, label %bb2
 268
 269 bb2:
 270   %v4 = tail call i32 (...) @f2()
 271   ret i32 %res.0
 272
 273 bb3:
 274   ret i32 %res.0
 275 }
 276
 277 define i32 @test7(i32* %P) {
 278 ; Negative test
 279 ; CHECK-LABEL: @test7(
 280 ; CHECK-NEXT:  entry:
 281 ; CHECK-NEXT:    [[V0:%.*]] = tail call i32 (...) @f1()
 282 ; CHECK-NEXT:    [[V1:%.*]] = icmp eq i32 [[V0]], 0
 283 ; CHECK-NEXT:    br i1 [[V1]], label [[BB1:%.*]], label [[BB:%.*]]
 284 ; CHECK:       bb:
 285 ; CHECK-NEXT:    [[VAL:%.*]] = load i32, i32* [[P:%.*]], align 4
 286 ; CHECK-NEXT:    br label [[BB1]]
 287 ; CHECK:       bb1:
 288 ; CHECK-NEXT:    [[RES_0:%.*]] = phi i32 [ 1, [[BB]] ], [ 0, [[ENTRY:%.*]] ]
 289 ; CHECK-NEXT:    [[V2:%.*]] = load atomic i32, i32* [[P]] acquire, align 4
 290 ; CHECK-NEXT:    [[V3:%.*]] = icmp sgt i32 [[V2]], 36
 291 ; CHECK-NEXT:    br i1 [[V3]], label [[BB3:%.*]], label [[BB2:%.*]]
 292 ; CHECK:       bb2:
 293 ; CHECK-NEXT:    [[V4:%.*]] = tail call i32 (...) @f2()
 294 ; CHECK-NEXT:    ret i32 [[RES_0]]
 295 ; CHECK:       bb3:
 296 ; CHECK-NEXT:    ret i32 [[RES_0]]
 297 ;
 298 entry:
 299   %v0 = tail call i32 (...) @f1()
 300   %v1 = icmp eq i32 %v0, 0
 301   br i1 %v1, label %bb1, label %bb
 302
 303 bb:
 304   %val = load i32, i32* %P
 305   br label %bb1
 306
 307 bb1:
 308
 309   %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]
 310   %v2 = load atomic i32, i32* %P acquire, align 4
 311   %v3 = icmp sgt i32 %v2, 36
 312   br i1 %v3, label %bb3, label %bb2
 313
 314 bb2:
 315   %v4 = tail call i32 (...) @f2()
 316   ret i32 %res.0
 317
 318 bb3:
 319   ret i32 %res.0
 320 }
 321
 322 ; Make sure we merge the aliasing metadata. We keep the range metadata for the
 323 ; first load, as it dominates the second load. Hence we can eliminate the
 324 ; branch.
 325 define void @test8(i32*, i32*, i32*) {
 326 ; CHECK-LABEL: @test8(
 327 ; CHECK-NEXT:  ret2:
 328 ; CHECK-NEXT:    [[A:%.*]] = load i32, i32* [[TMP0:%.*]], align 4, !range [[RNG4:![0-9]+]]
 329 ; CHECK-NEXT:    store i32 [[A]], i32* [[TMP1:%.*]], align 4
 330 ; CHECK-NEXT:    [[XXX:%.*]] = tail call i32 (...) @f1() #[[ATTR0]]
 331 ; CHECK-NEXT:    ret void
 332 ;
 333   %a = load i32, i32* %0, !tbaa !0, !range !4, !alias.scope !9, !noalias !10
 334   %b = load i32, i32* %0, !range !5
 335   store i32 %a, i32* %1
 336   %c = icmp eq i32 %b, 8
 337   br i1 %c, label %ret1, label %ret2
 338
 339 ret1:
 340   ret void
 341
 342 ret2:
 343   %xxx = tail call i32 (...) @f1() nounwind
 344   ret void
 345 }
 346
 347 ; Make sure we merge/PRE aliasing metadata correctly.  That means that
 348 ; we need to remove metadata from the existing load, and add appropriate
 349 ; metadata to the newly inserted load.
 350 define void @test9(i32*, i32*, i32*, i1 %c) {
 351 ; CHECK-LABEL: @test9(
 352 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[D1:%.*]], label [[D2:%.*]]
 353 ; CHECK:       d1:
 354 ; CHECK-NEXT:    [[A:%.*]] = load i32, i32* [[TMP0:%.*]], align 4
 355 ; CHECK-NEXT:    br label [[D3:%.*]]
 356 ; CHECK:       d2:
 357 ; CHECK-NEXT:    [[XXXX:%.*]] = tail call i32 (...) @f1() #[[ATTR0]]
 358 ; CHECK-NEXT:    [[B_PR:%.*]] = load i32, i32* [[TMP0]], align 4, !tbaa [[TBAA0]]
 359 ; CHECK-NEXT:    br label [[D3]]
 360 ; CHECK:       d3:
 361 ; CHECK-NEXT:    [[B:%.*]] = phi i32 [ [[B_PR]], [[D2]] ], [ [[A]], [[D1]] ]
 362 ; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 1, [[D2]] ], [ [[A]], [[D1]] ]
 363 ; CHECK-NEXT:    store i32 [[P]], i32* [[TMP1:%.*]], align 4
 364 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i32 [[B]], 8
 365 ; CHECK-NEXT:    br i1 [[C2]], label [[RET1:%.*]], label [[RET2:%.*]]
 366 ; CHECK:       ret1:
 367 ; CHECK-NEXT:    ret void
 368 ; CHECK:       ret2:
 369 ; CHECK-NEXT:    [[XXX:%.*]] = tail call i32 (...) @f1() #[[ATTR0]]
 370 ; CHECK-NEXT:    ret void
 371 ;
 372   br i1 %c, label %d1, label %d2
 373
 374 d1:
 375   %a = load i32, i32* %0, !range !4, !alias.scope !9, !noalias !10
 376   br label %d3
 377
 378 d2:
 379   %xxxx = tail call i32 (...) @f1() nounwind
 380   br label %d3
 381
 382 d3:
 383   %p = phi i32 [ 1, %d2 ], [ %a, %d1 ]
 384   %b = load i32, i32* %0, !tbaa !0
 385   store i32 %p, i32* %1
 386   %c2 = icmp eq i32 %b, 8
 387   br i1 %c2, label %ret1, label %ret2
 388
 389 ret1:
 390   ret void
 391
 392 ret2:
 393   %xxx = tail call i32 (...) @f1() nounwind
 394   ret void
 395 }
 396
 397 define i32 @fn_noalias(i1 %c2,i64* noalias %P, i64* noalias %P2) {
 398 ; CHECK-LABEL: @fn_noalias(
 399 ; CHECK-NEXT:  entry:
 400 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[COND2:%.*]], label [[COND1:%.*]]
 401 ; CHECK:       cond1:
 402 ; CHECK-NEXT:    [[L1:%.*]] = load i64, i64* [[P:%.*]], align 4
 403 ; CHECK-NEXT:    store i64 42, i64* [[P2:%.*]], align 4
 404 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i64 [[L1]], 0
 405 ; CHECK-NEXT:    br i1 [[C]], label [[COND2_THREAD:%.*]], label [[END:%.*]]
 406 ; CHECK:       cond2.thread:
 407 ; CHECK-NEXT:    call void @fn2(i64 [[L1]])
 408 ; CHECK-NEXT:    br label [[COND3:%.*]]
 409 ; CHECK:       cond2:
 410 ; CHECK-NEXT:    [[L2_PR:%.*]] = load i64, i64* [[P]], align 4
 411 ; CHECK-NEXT:    call void @fn2(i64 [[L2_PR]])
 412 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i64 [[L2_PR]], 0
 413 ; CHECK-NEXT:    br i1 [[C3]], label [[COND3]], label [[END]]
 414 ; CHECK:       cond3:
 415 ; CHECK-NEXT:    [[L23:%.*]] = phi i64 [ [[L1]], [[COND2_THREAD]] ], [ [[L2_PR]], [[COND2]] ]
 416 ; CHECK-NEXT:    call void @fn3(i64 [[L23]])
 417 ; CHECK-NEXT:    br label [[END]]
 418 ; CHECK:       end:
 419 ; CHECK-NEXT:    ret i32 0
 420 ;
 421 entry:
 422   br i1 %c2, label %cond2, label %cond1
 423
 424 cond1:
 425   %l1 = load i64, i64* %P
 426   store i64 42, i64* %P2
 427   %c = icmp eq i64 %l1, 0
 428   br i1 %c, label %cond2, label %end
 429
 430 cond2:
 431   %l2 = load i64, i64* %P
 432   call void @fn2(i64 %l2)
 433   %c3 = icmp eq i64 %l2,  0
 434   br i1 %c3, label %cond3, label %end
 435
 436 cond3:
 437   call void @fn3(i64 %l2)
 438   br label %end
 439
 440 end:
 441   ret i32 0
 442 }
 443
 444 ; This tests if we can thread from %sw.bb.i to %do.body.preheader.i67 through
 445 ; %sw.bb21.i. To make this happen, %l2 should be detected as a partically
 446 ; redundant load with %l3 across the store to %phase in %sw.bb21.i.
 447
 448 %struct.NEXT_MOVE = type { i32, i32, i32* }
 449 @hash_move = unnamed_addr global [65 x i32] zeroinitializer, align 4
 450 @current_move = internal global [65 x i32] zeroinitializer, align 4
 451 @last = internal unnamed_addr global [65 x i32*] zeroinitializer, align 8
 452 @next_status = internal unnamed_addr global [65 x %struct.NEXT_MOVE] zeroinitializer, align 8
 453 define fastcc i32 @Search(i64 %idxprom.i, i64 %idxprom.i89, i32 %c) {
 454 ; CHECK-LABEL: @Search(
 455 ; CHECK-NEXT:  cond.true282:
 456 ; CHECK-NEXT:    [[ARRAYIDX185:%.*]] = getelementptr inbounds [65 x i32], [65 x i32]* @hash_move, i64 0, i64 [[IDXPROM_I:%.*]]
 457 ; CHECK-NEXT:    [[ARRAYIDX307:%.*]] = getelementptr inbounds [65 x i32], [65 x i32]* @current_move, i64 0, i64 [[IDXPROM_I]]
 458 ; CHECK-NEXT:    [[ARRAYIDX89:%.*]] = getelementptr inbounds [65 x i32*], [65 x i32*]* @last, i64 0, i64 [[IDXPROM_I]]
 459 ; CHECK-NEXT:    [[PHASE:%.*]] = getelementptr inbounds [65 x %struct.NEXT_MOVE], [65 x %struct.NEXT_MOVE]* @next_status, i64 0, i64 [[IDXPROM_I]], i32 0
 460 ; CHECK-NEXT:    switch i32 [[C:%.*]], label [[CLEANUP:%.*]] [
 461 ; CHECK-NEXT:    i32 1, label [[SW_BB_I:%.*]]
 462 ; CHECK-NEXT:    i32 0, label [[SW_BB21_I:%.*]]
 463 ; CHECK-NEXT:    ]
 464 ; CHECK:       sw.bb.i:
 465 ; CHECK-NEXT:    [[CALL_I62:%.*]] = call fastcc i32* @GenerateCheckEvasions()
 466 ; CHECK-NEXT:    store i32* [[CALL_I62]], i32** [[ARRAYIDX89]], align 8
 467 ; CHECK-NEXT:    [[L2:%.*]] = load i32, i32* [[ARRAYIDX185]], align 4
 468 ; CHECK-NEXT:    [[TOBOOL_I63:%.*]] = icmp eq i32 [[L2]], 0
 469 ; CHECK-NEXT:    br i1 [[TOBOOL_I63]], label [[SW_BB21_I_THREAD:%.*]], label [[IF_THEN_I64:%.*]]
 470 ; CHECK:       sw.bb21.i.thread:
 471 ; CHECK-NEXT:    store i32 10, i32* [[PHASE]], align 8
 472 ; CHECK-NEXT:    br label [[DO_BODY_PREHEADER_I67:%.*]]
 473 ; CHECK:       if.then.i64:
 474 ; CHECK-NEXT:    store i32 7, i32* [[PHASE]], align 8
 475 ; CHECK-NEXT:    store i32 [[L2]], i32* [[ARRAYIDX307]], align 4
 476 ; CHECK-NEXT:    [[CALL16_I:%.*]] = call fastcc i32 @ValidMove(i32 [[L2]])
 477 ; CHECK-NEXT:    [[TOBOOL17_I:%.*]] = icmp eq i32 [[CALL16_I]], 0
 478 ; CHECK-NEXT:    br i1 [[TOBOOL17_I]], label [[IF_ELSE_I65:%.*]], label [[CLEANUP]]
 479 ; CHECK:       if.else.i65:
 480 ; CHECK-NEXT:    call void @f65()
 481 ; CHECK-NEXT:    br label [[SW_BB21_I]]
 482 ; CHECK:       sw.bb21.i:
 483 ; CHECK-NEXT:    [[L3_PR:%.*]] = load i32, i32* [[ARRAYIDX185]], align 4
 484 ; CHECK-NEXT:    store i32 10, i32* [[PHASE]], align 8
 485 ; CHECK-NEXT:    [[TOBOOL27_I:%.*]] = icmp eq i32 [[L3_PR]], 0
 486 ; CHECK-NEXT:    br i1 [[TOBOOL27_I]], label [[DO_BODY_PREHEADER_I67]], label [[CLEANUP]]
 487 ; CHECK:       do.body.preheader.i67:
 488 ; CHECK-NEXT:    call void @f67()
 489 ; CHECK-NEXT:    ret i32 67
 490 ; CHECK:       cleanup:
 491 ; CHECK-NEXT:    call void @Cleanup()
 492 ; CHECK-NEXT:    ret i32 0
 493 ;
 494 entry:
 495   %arrayidx185 = getelementptr inbounds [65 x i32], [65 x i32]* @hash_move, i64 0, i64 %idxprom.i
 496   %arrayidx307 = getelementptr inbounds [65 x i32], [65 x i32]* @current_move, i64 0, i64 %idxprom.i
 497   %arrayidx89 = getelementptr inbounds [65 x i32*], [65 x i32*]* @last, i64 0, i64 %idxprom.i
 498   %phase = getelementptr inbounds [65 x %struct.NEXT_MOVE], [65 x %struct.NEXT_MOVE]* @next_status, i64 0, i64 %idxprom.i, i32 0
 499   br label %cond.true282
 500
 501 cond.true282:
 502   switch i32 %c, label %sw.default.i [
 503   i32 1, label %sw.bb.i
 504   i32 0, label %sw.bb21.i
 505   ]
 506
 507 sw.default.i:
 508   br label %cleanup
 509
 510 sw.bb.i:
 511   %call.i62 = call fastcc i32* @GenerateCheckEvasions()
 512   store i32* %call.i62, i32** %arrayidx89, align 8
 513   %l2 = load i32, i32* %arrayidx185, align 4
 514   %tobool.i63 = icmp eq i32 %l2, 0
 515   br i1 %tobool.i63, label %sw.bb21.i, label %if.then.i64
 516
 517 if.then.i64:                                      ; preds = %sw.bb.i
 518   store i32 7, i32* %phase, align 8
 519   store i32 %l2, i32* %arrayidx307, align 4
 520   %call16.i = call fastcc i32 @ValidMove(i32 %l2)
 521   %tobool17.i = icmp eq i32 %call16.i, 0
 522   br i1 %tobool17.i, label %if.else.i65, label %cleanup
 523
 524 if.else.i65:
 525   call void @f65()
 526   br label %sw.bb21.i
 527
 528 sw.bb21.i:
 529   store i32 10, i32* %phase, align 8
 530   %l3= load i32, i32* %arrayidx185, align 4
 531   %tobool27.i = icmp eq i32 %l3, 0
 532   br i1 %tobool27.i, label %do.body.preheader.i67, label %cleanup
 533
 534 do.body.preheader.i67:
 535   call void @f67()
 536   ret  i32 67
 537
 538 cleanup:
 539   call void @Cleanup()
 540   ret  i32 0
 541 }
 542
 543 declare fastcc i32* @GenerateCheckEvasions()
 544 declare fastcc i32 @ValidMove(i32 %move)
 545 declare void @f67()
 546 declare void @Cleanup()
 547 declare void @f65()
 548
 549 define i32 @fn_SinglePred(i1 %c2,i64* %P) {
 550 ; CHECK-LABEL: @fn_SinglePred(
 551 ; CHECK-NEXT:  entry:
 552 ; CHECK-NEXT:    [[L1:%.*]] = load i64, i64* [[P:%.*]], align 4
 553 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i64 [[L1]], 0
 554 ; CHECK-NEXT:    br i1 [[C]], label [[COND3:%.*]], label [[COND1:%.*]]
 555 ; CHECK:       cond1:
 556 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[COND2:%.*]], label [[END:%.*]]
 557 ; CHECK:       cond2:
 558 ; CHECK-NEXT:    [[L2:%.*]] = phi i64 [ [[L1]], [[COND1]] ]
 559 ; CHECK-NEXT:    call void @fn2(i64 [[L2]])
 560 ; CHECK-NEXT:    br label [[END]]
 561 ; CHECK:       cond3:
 562 ; CHECK-NEXT:    call void @fn2(i64 [[L1]])
 563 ; CHECK-NEXT:    call void @fn3(i64 [[L1]])
 564 ; CHECK-NEXT:    br label [[END]]
 565 ; CHECK:       end:
 566 ; CHECK-NEXT:    ret i32 0
 567 ;
 568
 569 entry:
 570   %l1 = load i64, i64* %P
 571   %c = icmp eq i64 %l1, 0
 572   br i1 %c, label %cond2, label %cond1
 573
 574 cond1:
 575   br i1 %c2, label %cond2, label %end
 576
 577 cond2:
 578   %l2 = load i64, i64* %P
 579   call void @fn2(i64 %l2)
 580   %c3 = icmp eq i64 %l2,  0
 581   br i1 %c3, label %cond3, label %end
 582
 583 cond3:
 584   call void @fn3(i64 %l2)
 585   br label %end
 586
 587 end:
 588   ret i32 0
 589 }
 590
 591 define i32 @fn_SinglePredMultihop(i1 %c1, i1 %c2,i64* %P) {
 592 ; CHECK-LABEL: @fn_SinglePredMultihop(
 593 ; CHECK-NEXT:  entry:
 594 ; CHECK-NEXT:    [[L1:%.*]] = load i64, i64* [[P:%.*]], align 4
 595 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i64 [[L1]], 0
 596 ; CHECK-NEXT:    br i1 [[C0]], label [[COND3:%.*]], label [[COND0:%.*]]
 597 ; CHECK:       cond0:
 598 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[COND1:%.*]], label [[END:%.*]]
 599 ; CHECK:       cond1:
 600 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[COND2:%.*]], label [[END]]
 601 ; CHECK:       cond2:
 602 ; CHECK-NEXT:    [[L2:%.*]] = phi i64 [ [[L1]], [[COND1]] ]
 603 ; CHECK-NEXT:    call void @fn2(i64 [[L2]])
 604 ; CHECK-NEXT:    br label [[END]]
 605 ; CHECK:       cond3:
 606 ; CHECK-NEXT:    call void @fn2(i64 [[L1]])
 607 ; CHECK-NEXT:    call void @fn3(i64 [[L1]])
 608 ; CHECK-NEXT:    br label [[END]]
 609 ; CHECK:       end:
 610 ; CHECK-NEXT:    ret i32 0
 611 ;
 612
 613 entry:
 614   %l1 = load i64, i64* %P
 615   %c0 = icmp eq i64 %l1, 0
 616   br i1 %c0, label %cond2, label %cond0
 617
 618 cond0:
 619   br i1 %c1, label %cond1, label %end
 620
 621 cond1:
 622   br i1 %c2, label %cond2, label %end
 623
 624 cond2:
 625   %l2 = load i64, i64* %P
 626   call void @fn2(i64 %l2)
 627   %c3 = icmp eq i64 %l2,  0
 628   br i1 %c3, label %cond3, label %end
 629
 630 cond3:
 631   call void @fn3(i64 %l2)
 632   br label %end
 633
 634 end:
 635   ret i32 0
 636 }
 637
 638 declare void @fn2(i64)
 639 declare void @fn3(i64)
 640
 641
 642 ; Make sure we phi-translate and make the partially redundant load in
 643 ; merge fully redudant and then we can jump-thread the block with the
 644 ; store.
 645 ;
 646 define i32 @phi_translate_partial_redundant_loads(i32, i32*, i32*)  {
 647 ; CHECK-LABEL: @phi_translate_partial_redundant_loads(
 648 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ne i32 [[TMP0:%.*]], 0
 649 ; CHECK-NEXT:    br i1 [[CMP0]], label [[MERGE_THREAD:%.*]], label [[MERGE:%.*]]
 650 ; CHECK:       merge.thread:
 651 ; CHECK-NEXT:    store i32 1, i32* [[TMP1:%.*]], align 4
 652 ; CHECK-NEXT:    br label [[LEFT_X:%.*]]
 653 ; CHECK:       merge:
 654 ; CHECK-NEXT:    [[NEWLOAD_PR:%.*]] = load i32, i32* [[TMP2:%.*]], align 4
 655 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[NEWLOAD_PR]], 5
 656 ; CHECK-NEXT:    br i1 [[CMP1]], label [[LEFT_X]], label [[RIGHT_X:%.*]]
 657 ; CHECK:       left_x:
 658 ; CHECK-NEXT:    ret i32 20
 659 ; CHECK:       right_x:
 660 ; CHECK-NEXT:    ret i32 10
 661 ;
 662   %cmp0 = icmp ne i32 %0, 0
 663   br i1 %cmp0, label %left, label %right
 664
 665 left:
 666   store i32 1, i32* %1, align 4
 667   br label %merge
 668
 669 right:
 670   br label %merge
 671
 672 merge:
 673   %phiptr = phi i32* [ %1, %left ], [ %2, %right ]
 674   %newload = load i32, i32* %phiptr, align 4
 675   %cmp1 = icmp slt i32 %newload, 5
 676   br i1 %cmp1, label %left_x, label %right_x
 677
 678 left_x:
 679   ret i32 20
 680
 681 right_x:
 682   ret i32 10
 683 }
 684
 685
 686 ; CHECK: [[RNG4]] = !{i32 0, i32 1}
 687
 688 !0 = !{!3, !3, i64 0}
 689 !1 = !{!"omnipotent char", !2}
 690 !2 = !{!"Simple C/C++ TBAA"}
 691 !3 = !{!"int", !1}
 692 !4 = !{ i32 0, i32 1 }
 693 !5 = !{ i32 8, i32 10 }
 694 !6 = !{!6}
 695 !7 = !{!7, !6}
 696 !8 = !{!8, !6}
 697 !9 = !{!7}
 698 !10 = !{!8}