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

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