[LV] Try to sink and hoist inside candidate loops for vectorization.

[fhahn]

Summary

Hoisting and sinking instructions out of conditional blocks enables
additional vectorization by:

1. Executing memory accesses unconditionally.
2. Reducing the number of instructions that need predication.

After disabling early hoisting / sinking, we miss out on a few
vectorization opportunities. One of those is causing a ~10% performance
regression in one of the Geekbench benchmarks on AArch64.

This patch tires to recover the regression by running hoisting/sinking
inside each inner loop before vectorization. This is not ideal, because
we also hoist/sink in loops that won't be vectorized. But LV already
does similar transformations for all inner loops (e.g LoopSimplify and
LCSSA construction). Alternatively we could run a separate
loop-sink-hoist pass, but I am not sure that's worth the effort.

In the long term, the sinking/hoisting could and should be done in
VPlan, but it requires at least handling parts of legaltiy and
cost-modeling in VPlan as well.

Details about the impact on compile-time can be found here:
http://llvm-compile-time-tracker.com/compare.php?from=3a71d0de397e3a15c943ca59a00243ba8b7154da&to=c4efd69f4733b46e5de8fc2fa6e4c2495750d339&stat=instructions

NewPM-O3: geoman +0.18%
NewPM-ReleaseThinLTO: geoman +0.17%
NewPM-ReleaseLTO-g: geoman +0.18%

In terms of number of loops vectorized, we have the following changes
across MultiSource/SPEC2000/SPEC2006 on X86 with LTO

test-suite...000/186.crafty/186.crafty.test 20.00 22.00 10.0%
test-suite...006/450.soplex/450.soplex.test 85.00 86.00 1.2%
test-suite.../CINT2006/403.gcc/403.gcc.test 209.00 211.00 1.0%
test-suite...6/464.h264ref/464.h264ref.test 156.00 157.00 0.6%
test-suite...ications/JM/lencod/lencod.test 215.00 216.00 0.5%

And +0.5% more loops are vectorized in Geekbench on AArch64.

[fhahn]

Avoid using applyUpdatesPermissive, by directly handling the case with duplicated successors.

[fhahn]

remove accidental SimplifyCFG changes, they are now in D101289

[lebedev.ri]

As far as i can tell, this doesn't reintroduce the problem that was fixed by disabling early hoisting in simplifycfg, so LG.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9989

FWIW these sink/hoist helpers are fine with lazy updates.

10006–10016

I think it would be fine to sink that into hoistThenElseCodeToIf().

10025–10031

I think it would be fine to sink that into sinkCommonCodeFromPredecessors().

[fhahn]

Rebased on top of D101368, break out removing blocks that be come dead as separate cleanup in the loop.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9989

I'm not sure what the issue is exactly, but I think there are some cases where combining sinking & hoisting could result in some duplicated/outdated updates which would require applyUpdatesPermissive

10006–10016

Unfortunately I think that would be incompatible with the use in SimplifyCFG, which does not seem to handle removing BBs other than the current one well.

But I adjusted the loop to remove any blocks that became dead at the top-level, which hopefully makes things a bit clearer.

10025–10031

Thanks, that's a great idea. I put up D101368 to optionally preserve LI in sinkCommonCodeFromPredecessors

[fhahn]

Pass DTU to DeleteDeadBlock, use lazy update strategy.

[lebedev.ri]

Cautious LG, you likely want one more review.
Thanks.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9998

pred_empty(BB)

10006–10016

Hmm, true. Disregard then.

10008–10011

10015

[nikic]

I find it pretty odd that LoopVectorize would have this kind of side effect on code that's not vectorized. I don't think that's really the same as construction of LoopSimplify/LCSSA form, which is pretty much par the course for any loop pass. D84108 mentions that:

I'm proposing to harmonize this, and disable common code hoisting until late
in pipeline. Definition of late may vary, currently i've picked the same one
as for code sinking, but i suppose we could enable it as soon as right after
loop rotation happens.

I think that doing that (enabling hoisting in some post-LoopRotate SimplifyCFG run) would be cleaner than having it happen as a side-effect of LoopVectorize.

[fhahn]

In D101290#2720661, @nikic wrote:

I find it pretty odd that LoopVectorize would have this kind of side effect on code that's not vectorized. I don't think that's really the same as construction of LoopSimplify/LCSSA form, which is pretty much par the course for any loop pass. D84108 mentions that:

I'm proposing to harmonize this, and disable common code hoisting until late
in pipeline. Definition of late may vary, currently i've picked the same one
as for code sinking, but i suppose we could enable it as soon as right after
loop rotation happens.

I think that doing that (enabling hoisting in some post-LoopRotate SimplifyCFG run) would be cleaner than having it happen as a side-effect of LoopVectorize.

That's a fair point. Originally I did not adjust the SimplifyCFG runs, because we do a run of LoopRotate just before LoopVectorize in the legacy pass manager and the sinking/hoisting before may pessimize LoopRotate there. But it may not be a big issue (@lebedev.ri WDYT?), because sinking/hoisting before the second LoopRotate run should outweigh the risks of not rotating.

In general it is a bit unfortunate that LV is so sensitive to slight changes in the IR and very dependent on the specific position in the pipeline. As such, making it a bit more independent is desirable goal in general. In the future, we should be able to do the hoisting/sinking in VPlan, but that's still some way off. Unfortunately we cannot really perform the hoisting on loop that we can vectorize, because it would mess up runtime check SCEVs and a bunch of other things. Doing it in LV should disturb other passes less, but sinking/hoisting earlier is probably beneficial for a bunch of other passes as well.

I put up D101468 as an alternative, but should fix that particular vectorization issues when using O2/O3.

[lebedev.ri]

Superseded by D101468

[lebedev.ri]

The alternative solution landed some time ago.
Abandon this?

[fhahn]

In D101290#2835961, @lebedev.ri wrote:

The alternative solution landed some time ago.
Abandon this?

Yes, this is not needed for now. I'll also abandon the related patches.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/InstructionCost.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/InjectTLIMappings.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/LoopVersioning.h"
 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
+#include "llvm/Transforms/Utils/SimplifyCFGOptions.h"
 #include "llvm/Transforms/Utils/SizeOpts.h"
 #include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <cstdlib>
 #include <functional>
 #include <iterator>
if (RemainderLoopID.hasValue()) {
     // Mark the loop as already vectorized to avoid vectorizing again.
     Hints.setAlreadyVectorized();
   }
 
   assert(!verifyFunction(*L->getHeader()->getParent(), &dbgs()));
   return true;
 }
 
+static bool sinkAndHoistInstsInLoop(Loop *L, DominatorTree &DT, LoopInfo &LI,
+                                    TargetTransformInfo &TTI,
+                                    ScalarEvolution &SE) {
+  bool Changed = false;
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  SmallVector<BasicBlock *, 16> WorkList(reverse(L->blocks()));
+  while (!WorkList.empty()) {
+    BasicBlock *BB = WorkList.pop_back_val();
+    // Skip blocks that may have been removed earlier.
+    if (LI.getLoopFor(BB) != L)
+      continue;
+
+    // Remove block if it became dead.
+    if (pred_begin(BB) == pred_end(BB)) {
+      LI.removeBlock(BB);
+      DeleteDeadBlock(BB, &DTU);
+      continue;
+    }
+
+    // If BB has a conditional branch and its successors are in the same loop,
+    // try to hoist common code to BB.
+    auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
+    if (BI && BI->isConditional() &&
+        BI->getSuccessor(0)->getSinglePredecessor() &&
+        BI->getSuccessor(1)->getSinglePredecessor() &&
+        all_of(successors(BB), [&LI, L](BasicBlock *Succ) {
+          return LI.getLoopFor(Succ) == L;
+        })) {
+      auto *OldThen = BI->getSuccessor(0);
+      auto *OldElse = BI->getSuccessor(1);
+      if (hoistThenElseCodeToIf(BI, TTI, false, &DTU)) {
+        Changed = true;
+        if (OldThen->size() == 1)
+          WorkList.push_back(OldThen);
+        if (OldElse->size() == 1)
+          WorkList.push_back(OldElse);
+      }
+    }
+
+    // If all predecessors are in the current loop, try to sink instructions
+    // to BB.
+    if (all_of(predecessors(BB),
+               [&LI, L](BasicBlock *Pred) { return LI.getLoopFor(Pred) == L; }))
+      Changed |= sinkCommonCodeFromPredecessors(BB, &DTU, &LI);
+  }
+
+  if (Changed) {
+    SE.forgetTopmostLoop(L);
+#ifdef EXPENSIVE_CHECKS
+    assert(DTU.getDomTree().verify(DominatorTree::VerificationLevel::Full));
+    LI.verify(DT);
+#endif
+  }
+  return Changed;
+}
+
 LoopVectorizeResult LoopVectorizePass::runImpl(
     Function &F, ScalarEvolution &SE_, LoopInfo &LI_, TargetTransformInfo &TTI_,
     DominatorTree &DT_, BlockFrequencyInfo &BFI_, TargetLibraryInfo *TLI_,
     DemandedBits &DB_, AAResults &AA_, AssumptionCache &AC_,
     std::function<const LoopAccessInfo &(Loop &)> &GetLAA_,
     OptimizationRemarkEmitter &ORE_, ProfileSummaryInfo *PSI_) {
   SE = &SE_;
   LI = &LI_;
for (Loop *L : *LI)
     collectSupportedLoops(*L, LI, ORE, Worklist);
 
   LoopsAnalyzed += Worklist.size();
 
   // Now walk the identified inner loops.
   while (!Worklist.empty()) {
     Loop *L = Worklist.pop_back_val();
 
+    Changed |= CFGChanged |= sinkAndHoistInstsInLoop(L, *DT, *LI, *TTI, *SE);
+
     // For the inner loops we actually process, form LCSSA to simplify the
     // transform.
     Changed |= formLCSSARecursively(*L, *DT, LI, SE);
 
     Changed |= CFGChanged |= processLoop(L);
   }
 
   // Process each loop nest in the function.

llvm/test/Transforms/LoopVectorize/AArch64/prepare-hoist-sink.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -loop-vectorize -mtriple=arm64-apple-darwin -verify-dom-info -verify-loop-info -S %s | FileCheck %s
+; RUN: opt -loop-vectorize -mtriple=arm64-apple-darwin -verify-dom-info -verify-loop-info -force-vector-interleave=1 -S %s | FileCheck %s
 
 define void @test(float* %A, float* %B, float %x) {
 ; CHECK-LABEL: @test(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP:%.*]] = fcmp olt float [[X:%.*]], 2.000000e+01
-; CHECK-NEXT:    br label [[LOOP:%.*]]
-; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
-; CHECK:       then:
-; CHECK-NEXT:    [[A_GEP_0:%.*]] = getelementptr inbounds float, float* [[A:%.*]], i64 [[IV]]
-; CHECK-NEXT:    [[A_LV_0:%.*]] = load float, float* [[A_GEP_0]], align 4
-; CHECK-NEXT:    [[MUL2_I81_I:%.*]] = fmul float [[A_LV_0]], [[X]]
-; CHECK-NEXT:    [[B_GEP_0:%.*]] = getelementptr inbounds float, float* [[B:%.*]], i64 [[IV]]
-; CHECK-NEXT:    store float [[MUL2_I81_I]], float* [[B_GEP_0]], align 4
-; CHECK-NEXT:    br label [[LOOP_LATCH]]
-; CHECK:       else:
-; CHECK-NEXT:    [[A_GEP_1:%.*]] = getelementptr inbounds float, float* [[A]], i64 [[IV]]
-; CHECK-NEXT:    [[A_LV_1:%.*]] = load float, float* [[A_GEP_1]], align 4
-; CHECK-NEXT:    [[MUL2:%.*]] = fmul float [[A_LV_1]], [[X]]
-; CHECK-NEXT:    [[B_GEP_1:%.*]] = getelementptr inbounds float, float* [[B]], i64 [[IV]]
-; CHECK-NEXT:    [[B_LV:%.*]] = load float, float* [[B_GEP_1]], align 4
-; CHECK-NEXT:    [[ADD:%.*]] = fadd float [[MUL2]], [[B_LV]]
-; CHECK-NEXT:    store float [[ADD]], float* [[B_GEP_1]], align 4
-; CHECK-NEXT:    br label [[LOOP_LATCH]]
-; CHECK:       loop.latch:
-; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
-; CHECK-NEXT:    [[EXITCOND_NOT_I85_I:%.*]] = icmp eq i64 [[IV_NEXT]], 10000
-; CHECK-NEXT:    br i1 [[EXITCOND_NOT_I85_I]], label [[EXIT:%.*]], label [[LOOP]]
-; CHECK:       exit:
-; CHECK-NEXT:    ret void
+; CHECK:       vector.ph:
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x float> poison, float %x, i32 0
+; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x float> [[BROADCAST_SPLATINSERT]], <4 x float> poison, <4 x i32> zeroinitializer
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT7:%.*]] = insertelement <4 x i1> poison, i1 %cmp, i32 0
+; CHECK-NEXT:    [[BROADCAST_SPLAT8:%.*]] = shufflevector <4 x i1> [[BROADCAST_SPLATINSERT7]], <4 x i1> poison, <4 x i32> zeroinitializer
+; CHECK-NEXT:    br label %vector.body
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds float, float* %A, i64 [[TMP0]]
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds float, float* [[TMP1]], i32 0
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast float* [[TMP2]] to <4 x float>*
+; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x float>, <4 x float>* [[TMP3]], align 4
+; CHECK-NEXT:    [[TMP4:%.*]] = fmul <4 x float> [[WIDE_LOAD]], [[BROADCAST_SPLAT]]
+; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds float, float* %B, i64 [[TMP0]]
+; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds float, float* [[TMP5]], i32 0
+; CHECK-NEXT:    [[TMP7:%.*]] = bitcast float* [[TMP6]] to <4 x float>*
+; CHECK-NEXT:    [[WIDE_LOAD6:%.*]] = load <4 x float>, <4 x float>* [[TMP7]], align 4
+; CHECK-NEXT:    [[TMP8:%.*]] = fadd <4 x float> [[TMP4]], [[WIDE_LOAD6]]
+; CHECK-NEXT:    [[TMP9:%.*]] = xor <4 x i1> [[BROADCAST_SPLAT8]], <i1 true, i1 true, i1 true, i1 true>
+; CHECK-NEXT:    [[PREDPHI:%.*]] = select <4 x i1> [[BROADCAST_SPLAT8]], <4 x float> [[TMP4]], <4 x float> [[TMP8]]
+; CHECK-NEXT:    [[TMP10:%.*]] = bitcast float* [[TMP6]] to <4 x float>*
+; CHECK-NEXT:    store <4 x float> [[PREDPHI]], <4 x float>* [[TMP10]], align 4
+; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 4
+; CHECK-NEXT:    [[TMP11:%.*]] = icmp eq i64 [[INDEX_NEXT]], 10000
+; CHECK-NEXT:    br i1 [[TMP11]], label %middle.block, label %vector.body
 ;
 entry:
   %cmp = fcmp olt float %x, 20.0
   br label %loop
 
 loop:
   %iv = phi i64 [ %iv.next, %loop.latch ], [ 0, %entry ]
   br i1 %cmp, label %then, label %else

 
 define void @hoist_sink_only_cfg_update() {
 ; CHECK-LABEL: @hoist_sink_only_cfg_update(
 ; CHECK-NEXT:  for.body.preheader:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    br i1 true, label [[IF_ELSE29:%.*]], label [[IF_THEN9:%.*]]
-; CHECK:       if.then9:
 ; CHECK-NEXT:    br i1 true, label [[IF_END38:%.*]], label [[IF_END38]]
-; CHECK:       if.else29:
-; CHECK-NEXT:    br i1 true, label [[IF_END38]], label [[IF_END38]]
 ; CHECK:       if.end38:
 ; CHECK-NEXT:    br label [[CLEANUP:%.*]]
 ; CHECK:       cleanup:
 ; CHECK-NEXT:    br label [[FOR_BODY]]
 ;
 for.body.preheader:
   br label %for.body
 

 
 if.end38:                                         ; preds = %if.else29, %if.else29, %if.then9, %if.then9
   br label %cleanup
 
 cleanup:                                          ; preds = %if.end38
   br label %for.body
 }
 
-@rd = external unnamed_addr global i32, align 4
+@rd = external global i32, align 4
 
 define void @sink_with_new_split_block(i32* %ptr) {
 ; CHECK-LABEL: @sink_with_new_split_block(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[LOOP:%.*]]
-; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
-; CHECK-NEXT:    [[GEP:%.*]] = getelementptr i32, i32* [[PTR:%.*]], i32 [[IV]]
-; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[GEP]], align 4
-; CHECK-NEXT:    [[C_0:%.*]] = icmp eq i32 [[LV]], 20
-; CHECK-NEXT:    br i1 [[C_0]], label [[THEN_0:%.*]], label [[ELSE_0:%.*]]
-; CHECK:       then.0:
-; CHECK-NEXT:    store i32 281701264, i32* @rd, align 4
-; CHECK-NEXT:    br label [[LOOP_LATCH]]
-; CHECK:       else.0:
-; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[LV]], 99
-; CHECK-NEXT:    br i1 [[C_1]], label [[THEN_1:%.*]], label [[LOOP_LATCH]]
-; CHECK:       then.1:
-; CHECK-NEXT:    store i32 0, i32* @rd, align 4
-; CHECK-NEXT:    br label [[LOOP_LATCH]]
-; CHECK:       loop.latch:
-; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
-; CHECK-NEXT:    [[C_2:%.*]] = icmp ne i32 [[IV_NEXT]], 2000
-; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP]], label [[EXIT:%.*]]
-; CHECK:       exit:
-; CHECK-NEXT:    ret void
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i32 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %pred.store.continue8 ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[INDEX]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr i32, i32* %ptr, i32 [[TMP0]]
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr i32, i32* [[TMP1]], i32 0
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i32* [[TMP2]] to <4 x i32>*
+; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[TMP3]], align 4
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq <4 x i32> [[WIDE_LOAD]], <i32 20, i32 20, i32 20, i32 20>
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq <4 x i32> [[WIDE_LOAD]], <i32 99, i32 99, i32 99, i32 99>
+; CHECK-NEXT:    [[TMP6:%.*]] = xor <4 x i1> [[TMP4]], <i1 true, i1 true, i1 true, i1 true>
+; CHECK-NEXT:    [[TMP7:%.*]] = select <4 x i1> [[TMP6]], <4 x i1> [[TMP5]], <4 x i1> zeroinitializer
+; CHECK-NEXT:    [[PREDPHI:%.*]] = select <4 x i1> [[TMP4]], <4 x i32> <i32 281701264, i32 281701264, i32 281701264, i32 281701264>, <4 x i32> zeroinitializer
+; CHECK-NEXT:    [[TMP8:%.*]] = or <4 x i1> [[TMP4]], [[TMP7]]
+; CHECK-NEXT:    [[TMP9:%.*]] = extractelement <4 x i1> [[TMP8]], i32 0
+; CHECK-NEXT:    br i1 [[TMP9]], label [[PRED_STORE_IF:%.*]], label [[PRED_STORE_CONTINUE:%.*]]
+; CHECK:       pred.store.if:
+; CHECK-NEXT:    [[TMP10:%.*]] = extractelement <4 x i32> [[PREDPHI]], i32 0
+; CHECK-NEXT:    store i32 [[TMP10]], i32* @rd, align 4
+; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE]]
+; CHECK:       pred.store.continue:
+; CHECK-NEXT:    [[TMP11:%.*]] = extractelement <4 x i1> [[TMP8]], i32 1
+; CHECK-NEXT:    br i1 [[TMP11]], label [[PRED_STORE_IF3:%.*]], label [[PRED_STORE_CONTINUE4:%.*]]
+; CHECK:       pred.store.if3:
+; CHECK-NEXT:    [[TMP12:%.*]] = extractelement <4 x i32> [[PREDPHI]], i32 1
+; CHECK-NEXT:    store i32 [[TMP12]], i32* @rd, align 4
+; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE4]]
+; CHECK:       pred.store.continue4:
+; CHECK-NEXT:    [[TMP13:%.*]] = extractelement <4 x i1> [[TMP8]], i32 2
+; CHECK-NEXT:    br i1 [[TMP13]], label [[PRED_STORE_IF5:%.*]], label [[PRED_STORE_CONTINUE6:%.*]]
+; CHECK:       pred.store.if5:
+; CHECK-NEXT:    [[TMP14:%.*]] = extractelement <4 x i32> [[PREDPHI]], i32 2
+; CHECK-NEXT:    store i32 [[TMP14]], i32* @rd, align 4
+; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE6]]
+; CHECK:       pred.store.continue6:
+; CHECK-NEXT:    [[TMP15:%.*]] = extractelement <4 x i1> [[TMP8]], i32 3
+; CHECK-NEXT:    br i1 [[TMP15]], label [[PRED_STORE_IF7:%.*]], label %pred.store.continue8
+; CHECK:       pred.store.if7:
+; CHECK-NEXT:    [[TMP16:%.*]] = extractelement <4 x i32> [[PREDPHI]], i32 3
+; CHECK-NEXT:    store i32 [[TMP16]], i32* @rd, align 4,
+; CHECK-NEXT:    br label %pred.store.continue8
+; CHECK:       pred.store.continue8:
+; CHECK-NEXT:    [[INDEX_NEXT]] = add i32 [[INDEX]], 4
+; CHECK-NEXT:    [[TMP17:%.*]] = icmp eq i32 [[INDEX_NEXT]], 2000
+; CHECK-NEXT:    br i1 [[TMP17]], label %middle.block, label %vector.body
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ]
   %gep = getelementptr i32, i32* %ptr, i32 %iv
   %lv = load i32, i32* %gep

llvm/test/Transforms/LoopVectorize/first-order-recurrence-complex.ll

 define void @cannot_sink_phi(i32* %ptr) {
 ; CHECK-LABEL: @cannot_sink_phi(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop.header:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 ; CHECK-NEXT:    [[FOR:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[FOR_NEXT:%.*]], [[LOOP_LATCH]] ]
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ult i64 [[IV]], 500
-; CHECK-NEXT:    br i1 [[C_1]], label [[IF_TRUEBB:%.*]], label [[IF_FALSEBB:%.*]]
-; CHECK:       if.truebb:
-; CHECK-NEXT:    br label [[LOOP_LATCH]]
-; CHECK:       if.falsebb:
+; CHECK-NEXT:    [[DOTFOR:%.*]] = select i1 [[C_1]], i32 20, i32 [[FOR]]
 ; CHECK-NEXT:    br label [[LOOP_LATCH]]
 ; CHECK:       loop.latch:
-; CHECK-NEXT:    [[FIRST_TIME_1:%.*]] = phi i32 [ 20, [[IF_TRUEBB]] ], [ [[FOR]], [[IF_FALSEBB]] ]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ult i64 [[IV]], 800
-; CHECK-NEXT:    [[FOR_NEXT]] = select i1 [[C_2]], i32 30, i32 [[FIRST_TIME_1]]
+; CHECK-NEXT:    [[FOR_NEXT]] = select i1 [[C_2]], i32 30, i32 [[DOTFOR]]
 ; CHECK-NEXT:    [[PTR_IDX:%.*]] = getelementptr i32, i32* [[PTR:%.*]], i64 [[IV]]
 ; CHECK-NEXT:    store i32 [[FOR_NEXT]], i32* [[PTR_IDX]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
 ; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i64 [[IV_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label [[EXIT:%.*]], label [[LOOP_HEADER]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;

llvm/test/Transforms/LoopVectorize/invariant-store-vectorization.ll

 
 for.end:                                          ; preds = %for.body
   ret void
 }
 
 ; if (b[i] == k)
 ;    a = ntrunc
 ; else a = k;
-; TODO: We could vectorize this once we support multiple uniform stores to the
-; same address.
+; The function gets vectorized by sinking the conditional stores in the successor.
 ; CHECK-LABEL:inv_val_store_to_inv_address_conditional_diff_values(
-; CHECK-NOT:           load <4 x i32>
+; CHECK:           load <4 x i32>
 define void @inv_val_store_to_inv_address_conditional_diff_values(i32* %a, i64 %n, i32* %b, i32 %k) {
 entry:
   %ntrunc = trunc i64 %n to i32
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %i = phi i64 [ %i.next, %latch ], [ 0, %entry ]
   %tmp1 = getelementptr inbounds i32, i32* %b, i64 %i

 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[FOR_END:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ], [ 0, [[VECTOR_MEMCHECK]] ]
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[LATCH:%.*]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]
 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[I]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[TMP1]], align 8
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP2]], [[K]]
 ; CHECK-NEXT:    store i32 [[NTRUNC]], i32* [[TMP1]], align 4
-; CHECK-NEXT:    br i1 [[CMP]], label [[COND_STORE:%.*]], label [[COND_STORE_K:%.*]]
-; CHECK:       cond_store:
-; CHECK-NEXT:    br label [[LATCH]]
-; CHECK:       cond_store_k:
-; CHECK-NEXT:    br label [[LATCH]]
 ; CHECK:       latch:
-; CHECK-NEXT:    [[STOREVAL:%.*]] = phi i32 [ [[NTRUNC]], [[COND_STORE]] ], [ [[K]], [[COND_STORE_K]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP2]], [[K]]
+; CHECK-NEXT:    [[STOREVAL:%.*]] = select i1 [[CMP]], i32 [[NTRUNC]], i32 [[K]]
 ; CHECK-NEXT:    store i32 [[STOREVAL]], i32* [[A]], align 4
 ; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = icmp slt i64 [[I_NEXT]], [[N]]
 ; CHECK-NEXT:    br i1 [[COND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
 ; CHECK:       for.end.loopexit:
 ; CHECK-NEXT:    br label [[FOR_END]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void

 ; invariant val stored to invariant address predicated on invariant condition
 ; This is not treated as a predicated store since the block the store belongs to
 ; is the latch block (which doesn't need to be predicated).
 ; variant/invariant values being stored to invariant address.
 ; test checks that the last element of the phi is extracted and scalar stored
 ; into the uniform address within the loop.
 ; Since the condition and the phi is loop invariant, they are LICM'ed after
 ; vectorization.
-; CHECK-LABEL: inv_val_store_to_inv_address_conditional_inv
+; CHECK-LABEL: @inv_val_store_to_inv_address_conditional_inv(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[NTRUNC:%.*]] = trunc i64 [[N:%.*]] to i32
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[NTRUNC]], [[K:%.*]]
-; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 1)
-; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[SMAX]], 4
+; CHECK-NEXT:    [[SMAX4:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 1)
+; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[SMAX4]], 4
 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]
 ; CHECK:       vector.memcheck:
-; CHECK-NEXT:    [[A4:%.*]] = bitcast i32* [[A:%.*]] to i8*
+; CHECK-NEXT:    [[A3:%.*]] = bitcast i32* [[A:%.*]] to i8*
 ; CHECK-NEXT:    [[B1:%.*]] = bitcast i32* [[B:%.*]] to i8*
-; CHECK-NEXT:    [[SMAX2:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 1)
-; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i32, i32* [[B]], i64 [[SMAX2]]
-; CHECK-NEXT:    [[UGLYGEP:%.*]] = getelementptr i8, i8* [[A4]], i64 1
+; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 1)
+; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i32, i32* [[B]], i64 [[SMAX]]
+; CHECK-NEXT:    [[UGLYGEP:%.*]] = getelementptr i8, i8* [[A3]], i64 1
 ; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ugt i8* [[UGLYGEP]], [[B1]]
 ; CHECK-NEXT:    [[BOUND1:%.*]] = icmp ugt i32* [[SCEVGEP]], [[A]]
 ; CHECK-NEXT:    [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
 ; CHECK-NEXT:    br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
-; CHECK-NEXT:    [[N_VEC:%.*]] = and i64 [[SMAX]], 9223372036854775804
-; CHECK-NEXT:    [[BROADCAST_SPLATINSERT5:%.*]] = insertelement <4 x i32> poison, i32 [[NTRUNC]], i32 0
-; CHECK-NEXT:    [[BROADCAST_SPLAT6:%.*]] = shufflevector <4 x i32> [[BROADCAST_SPLATINSERT5]], <4 x i32> poison, <4 x i32> zeroinitializer
-; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <4 x i1> undef, i1 [[CMP]], i32 3
-; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <4 x i32> poison, i32 [[K]], i32 3
-; CHECK-NEXT:    [[PREDPHI:%.*]] = select <4 x i1> [[TMP2]], <4 x i32> [[BROADCAST_SPLAT6]], <4 x i32> [[TMP3]]
-; CHECK-NEXT:    [[TMP5:%.*]] = extractelement <4 x i32> [[PREDPHI]], i32 3
+; CHECK-NEXT:    [[N_VEC:%.*]] = and i64 [[SMAX4]], 9223372036854775804
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x i32> poison, i32 [[NTRUNC]], i32 0
+; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x i32> [[BROADCAST_SPLATINSERT]], <4 x i32> poison, <4 x i32> zeroinitializer
+; CHECK-NEXT:    [[BROADCAST_SPLAT6:%.*]] = insertelement <4 x i32> poison, i32 [[K]], i32 3
+; CHECK-NEXT:    [[TMP0:%.*]] = select i1 [[CMP]], <4 x i32> [[BROADCAST_SPLAT]], <4 x i32> [[BROADCAST_SPLAT6]]
+; CHECK-NEXT:    [[TMP1:%.*]] = extractelement <4 x i32> [[TMP0]], i32 3
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
-; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[INDEX]]
-; CHECK-NEXT:    [[TMP7:%.*]] = bitcast i32* [[TMP6]] to <4 x i32>*
-; CHECK-NEXT:    store <4 x i32> [[BROADCAST_SPLAT6]], <4 x i32>* [[TMP7]], align 4
-; CHECK-NEXT:    store i32 [[TMP5]], i32* [[A]], align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[INDEX]]
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i32* [[TMP2]] to <4 x i32>*
+; CHECK-NEXT:    store <4 x i32> [[BROADCAST_SPLAT]], <4 x i32>* [[TMP3]], align 4, !alias.scope !36, !noalias !39
+; CHECK-NEXT:    store i32 [[TMP1]], i32* [[A]], align 4, !alias.scope !39
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 4
-; CHECK-NEXT:    [[TMP8:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
-; CHECK-NEXT:    br i1 [[TMP8]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP41:![0-9]+]]
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[SMAX]], [[N_VEC]]
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[SMAX4]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[FOR_END:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ], [ 0, [[VECTOR_MEMCHECK]] ]
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[LATCH:%.*]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]
 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[I]]
 ; CHECK-NEXT:    store i32 [[NTRUNC]], i32* [[TMP1]], align 4
-; CHECK-NEXT:    br i1 [[CMP]], label [[COND_STORE:%.*]], label [[COND_STORE_K:%.*]]
-; CHECK:       cond_store:
-; CHECK-NEXT:    br label [[LATCH]]
-; CHECK:       cond_store_k:
 ; CHECK-NEXT:    br label [[LATCH]]
 ; CHECK:       latch:
-; CHECK-NEXT:    [[STOREVAL:%.*]] = phi i32 [ [[NTRUNC]], [[COND_STORE]] ], [ [[K]], [[COND_STORE_K]] ]
-; CHECK-NEXT:    store i32 [[STOREVAL]], i32* [[A]], align 4
+; CHECK-NEXT:    store i32 [[K]], i32* [[A]], align 4
 ; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = icmp slt i64 [[I_NEXT]], [[N]]
-; CHECK-NEXT:    br i1 [[COND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]], !llvm.loop [[LOOP42:![0-9]+]]
 ; CHECK:       for.end.loopexit:
 ; CHECK-NEXT:    br label [[FOR_END]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 define void @inv_val_store_to_inv_address_conditional_inv(i32* %a, i64 %n, i32* %b, i32 %k) {
 entry:
   %ntrunc = trunc i64 %n to i32

 }
 
 ; variant value stored to uniform address tests that the code gen extracts the
 ; last element from the variant vector and scalar stores it into the uniform
 ; address.
 define i32 @variant_val_store_to_inv_address(i32* %a, i64 %n, i32* %b, i32 %k) {
 ; CHECK-LABEL: @variant_val_store_to_inv_address(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 1)
-; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[SMAX]], 4
+; CHECK-NEXT:    [[SMAX4:%.*]] = call i64 @llvm.smax.i64(i64 [[N:%.*]], i64 1)
+; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[SMAX4]], 4
 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]
 ; CHECK:       vector.memcheck:
 ; CHECK-NEXT:    [[B2:%.*]] = bitcast i32* [[B:%.*]] to i8*
 ; CHECK-NEXT:    [[A1:%.*]] = bitcast i32* [[A:%.*]] to i8*
 ; CHECK-NEXT:    [[UGLYGEP:%.*]] = getelementptr i8, i8* [[A1]], i64 1
-; CHECK-NEXT:    [[SMAX3:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 1)
-; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i32, i32* [[B]], i64 [[SMAX3]]
+; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 1)
+; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i32, i32* [[B]], i64 [[SMAX]]
 ; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ugt i32* [[SCEVGEP]], [[A]]
 ; CHECK-NEXT:    [[BOUND1:%.*]] = icmp ugt i8* [[UGLYGEP]], [[B2]]
 ; CHECK-NEXT:    [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
 ; CHECK-NEXT:    br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
-; CHECK-NEXT:    [[N_VEC:%.*]] = and i64 [[SMAX]], 9223372036854775804
+; CHECK-NEXT:    [[N_VEC:%.*]] = and i64 [[SMAX4]], 9223372036854775804
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
-; CHECK-NEXT:    [[VEC_PHI:%.*]] = phi <4 x i32> [ zeroinitializer, [[VECTOR_PH]] ], [ [[TMP5:%.*]], [[VECTOR_BODY]] ]
-; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[INDEX]]
-; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i32* [[TMP2]] to <4 x i32>*
-; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[TMP3]], align 8, !alias.scope !36
-; CHECK-NEXT:    [[TMP4:%.*]] = extractelement <4 x i32> [[WIDE_LOAD]], i32 3
-; CHECK-NEXT:    store i32 [[TMP4]], i32* [[A]], align 4, !alias.scope !39, !noalias !36
-; CHECK-NEXT:    [[TMP5]] = add <4 x i32> [[VEC_PHI]], [[WIDE_LOAD]]
+; CHECK-NEXT:    [[VEC_PHI:%.*]] = phi <4 x i32> [ zeroinitializer, [[VECTOR_PH]] ], [ [[TMP3:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[INDEX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[TMP0]] to <4 x i32>*
+; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[TMP1]], align 8, !alias.scope !43
+; CHECK-NEXT:    [[TMP2:%.*]] = extractelement <4 x i32> [[WIDE_LOAD]], i32 3
+; CHECK-NEXT:    store i32 [[TMP2]], i32* [[A]], align 4, !alias.scope !46, !noalias !43
+; CHECK-NEXT:    [[TMP3]] = add <4 x i32> [[VEC_PHI]], [[WIDE_LOAD]]
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 4
-; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
-; CHECK-NEXT:    br i1 [[TMP6]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], [[LOOP41:!llvm.loop !.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP48:![0-9]+]]
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi <4 x i32> [ [[TMP5]], [[VECTOR_BODY]] ]
-; CHECK-NEXT:    [[TMP7:%.*]] = call i32 @llvm.vector.reduce.add.v4i32(<4 x i32> [[DOTLCSSA]])
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[SMAX]], [[N_VEC]]
+; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi <4 x i32> [ [[TMP3]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = call i32 @llvm.vector.reduce.add.v4i32(<4 x i32> [[DOTLCSSA]])
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[SMAX4]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[FOR_END:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ], [ 0, [[VECTOR_MEMCHECK]] ]
-; CHECK-NEXT:    [[BC_MERGE_RDX:%.*]] = phi i32 [ [[TMP7]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY]] ], [ 0, [[VECTOR_MEMCHECK]] ]
+; CHECK-NEXT:    [[BC_MERGE_RDX:%.*]] = phi i32 [ [[TMP5]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY]] ], [ 0, [[VECTOR_MEMCHECK]] ]
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[FOR_BODY]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[TMP3:%.*]], [[FOR_BODY]] ], [ [[BC_MERGE_RDX]], [[SCALAR_PH]] ]
 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[I]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[TMP1]], align 8
 ; CHECK-NEXT:    store i32 [[TMP2]], i32* [[A]], align 4
 ; CHECK-NEXT:    [[TMP3]] = add i32 [[TMP0]], [[TMP2]]
 ; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = icmp slt i64 [[I_NEXT]], [[N]]
-; CHECK-NEXT:    br i1 [[COND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]], [[LOOP42:!llvm.loop !.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]], !llvm.loop [[LOOP49:![0-9]+]]
 ; CHECK:       for.end.loopexit:
 ; CHECK-NEXT:    [[TMP3_LCSSA:%.*]] = phi i32 [ [[TMP3]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    br label [[FOR_END]]
 ; CHECK:       for.end:
-; CHECK-NEXT:    [[RDX_LCSSA:%.*]] = phi i32 [ [[TMP7]], [[MIDDLE_BLOCK]] ], [ [[TMP3_LCSSA]], [[FOR_END_LOOPEXIT]] ]
+; CHECK-NEXT:    [[RDX_LCSSA:%.*]] = phi i32 [ [[TMP5]], [[MIDDLE_BLOCK]] ], [ [[TMP3_LCSSA]], [[FOR_END_LOOPEXIT]] ]
 ; CHECK-NEXT:    ret i32 [[RDX_LCSSA]]
 ;
 entry:
   %ntrunc = trunc i64 %n to i32
   %cmp = icmp eq i32 %ntrunc, %k
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry

llvm/test/Transforms/LoopVectorize/tail-folding-counting-down.ll

 
 while.end:
   ret void
 }
 
 ; Make sure a loop is successfully vectorized with fold-tail when the backedge
 ; taken count is constant and used inside the loop. Issue revealed by D76992.
 ;
-define void @reuse_const_btc(i8* %A) optsize {
+define void @reuse_const_btc(i8* %A, i32* noalias %B) optsize {
 ; CHECK-LABEL: @reuse_const_btc
 ; CHECK: {{%.*}} = icmp ule <4 x i32> {{%.*}}, <i32 13, i32 13, i32 13, i32 13>
-; CHECK: {{%.*}} = select <4 x i1> {{%.*}}, <4 x i32> <i32 12, i32 12, i32 12, i32 12>, <4 x i32> <i32 13, i32 13, i32 13, i32 13>
+; CHECK: {{%.*}} = select <4 x i1> {{%.*}}, <4 x i32> <i32 12, i32 12, i32 12, i32 12>, <4 x i32> 
 ;
 entry:
   br label %loop
 
 loop:
   %riv = phi i32 [ 13, %entry ], [ %rivMinus1, %merge ]
   %sub = sub nuw nsw i32 20, %riv
   %arrayidx = getelementptr inbounds i8, i8* %A, i32 %sub
   %cond0 = icmp eq i32 %riv, 7
   br i1 %cond0, label %then, label %else
 then:
+  %B.gep = getelementptr inbounds i32, i32* %B, i32 %sub
+  %lv = load i32, i32* %B.gep
   br label %merge
 else:
   br label %merge
 merge:
-  %blend = phi i32 [ 13, %then ], [ 12, %else ]
+  %blend = phi i32 [ %lv, %then ], [ 12, %else ]
   %trunc = trunc i32 %blend to i8
   store i8 %trunc, i8* %arrayidx, align 1
   %rivMinus1 = add nuw nsw i32 %riv, -1
   %cond = icmp eq i32 %riv, 0
   br i1 %cond, label %exit, label %loop
 
 exit:
   ret void
 }