[LV] Remove unneeded createHeaderBranch.(NFCI)

[fhahn]

Summary

The only remaining use was to get the exit block of the loop. Instead of
relying on the loop, use the successor of VectorHeaderBB
(LoopMiddleBlock) directly to set VPTransformState::CFG::ExitB

Depends on D121621.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

634

It still also allocates a loop object for the new vector loop, placing the header in it, and could return it, but doing so would be useless - the loop is retrieved when needed from its header block.

7597

Would be good to set here the minimal fields of State needed, PrevBB/VectorLoopPreHeader being an anchor, and complement other caching fields later - possibly LastBB included?

llvm/lib/Transforms/Vectorize/VPlan.cpp

912

Is it no longer possible to retrieve LoopMiddleBlock as the exit block of L, at this time? (Intentionally, from the summary: "Instead of relying on the loop ...")
Alternatively, retrieve LastBB/LoopMiddleBlock as VectorHeaderBB->getSingleSuccessor(); ?

[fhahn]

Add back loop creation part to the comment, move all initial CFGTransformState initialization to single place as suggested, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

634

Ah yes, added back the bit about allocating the loop, thanks!

7597

I tried to move all revenant initializations here.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7597

Oh, no, sorry ... I meant LVP should (continue to) set the minimal amount of fields in State here, and let VPlan complement whatever additional fields it needs later, as done now. Wanted to make sure if ExitBB needs to be set to middleBlock here, instead of setting it later to L->getExitBlock() in VPlan::execute() as done now, say because the creation of L is to be moved to later?

[fhahn]

Move initialization of State::CFG back to VPlan::execute.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7597

Oh, no, sorry ... I meant LVP should (continue to) set the minimal amount of fields in State here,

Ah right that makes sense. I updated the patch to only set VectorPreHeader here and set the other fields in VPlan::execute based on that.

[Ayal]

This is fine, thanks!

Couple of minor nits, plus Summary can be updated:
"use ILV::LoopMiddleBlock directly to set VPTransformState::CFG::LastBB" >>
"use successor of VectorHeaderBB (LoopMiddleBlock) directly to set VPTransformState::CFG::ExitBB"

llvm/lib/Transforms/Vectorize/VPlan.cpp

908

nit: simpler and clearer to set

BasicBlock *VectorHeaderBB = State->CFG.VectorPreHeader->getSingleSuccessor();
State->CFG.PrevBB = VectorHeaderBB;

911

nit: (irrespective of this patch) can fold as L is used only here

State->CurrentVectorLoop = State->LI->getLoopFor(VectorHeaderBB);

[fhahn]

In D121623#3416318, @Ayal wrote:

This is fine, thanks!

Couple of minor nits, plus Summary can be updated:
"use ILV::LoopMiddleBlock directly to set VPTransformState::CFG::LastBB" >>
"use successor of VectorHeaderBB (LoopMiddleBlock) directly to set VPTransformState::CFG::ExitBB"

Thanks, the nits should be addressedd in the latest version. I'll update the description and plan to land this soon.

llvm/lib/Transforms/Vectorize/VPlan.cpp

908

Simplified as suggested, thanks!

911

Done separately in 2c494f094123

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
   /// vectorization factor.
   using ScalarParts = SmallVector<SmallVector<Value *, 4>, 2>;
 
   /// Set up the values of the IVs correctly when exiting the vector loop.
   void fixupIVUsers(PHINode *OrigPhi, const InductionDescriptor &II,
                     Value *CountRoundDown, Value *EndValue,
                     BasicBlock *MiddleBlock, BasicBlock *VectorHeader);
 
-  /// Introduce a conditional branch (on true, condition to be set later) at the
-  /// end of the header=latch connecting it to itself (across the backedge) and
-  /// to the exit block of \p L.
-  void createHeaderBranch(Loop *L);
-
   /// Handle all cross-iteration phis in the header.
   void fixCrossIterationPHIs(VPTransformState &State);
 
   /// Create the exit value of first order recurrences in the middle block and
   /// update their users.
   void fixFirstOrderRecurrence(VPFirstOrderRecurrencePHIRecipe *PhiR,
                                VPTransformState &State);
 
protected:
 
   /// Emit bypass checks to check any memory assumptions we may have made.
   /// Returns the block containing the checks or nullptr if no checks have been
   /// added.
   BasicBlock *emitMemRuntimeChecks(BasicBlock *Bypass);
 
   /// Emit basic blocks (prefixed with \p Prefix) for the iteration check,
   /// vector loop preheader, middle block and scalar preheader. Also
-  /// allocate a loop object for the new vector loop and return it.
-  Loop *createVectorLoopSkeleton(StringRef Prefix);
+  /// allocate a loop object for the new vector loop.
+  void createVectorLoopSkeleton(StringRef Prefix);
 
   /// Create new phi nodes for the induction variables to resume iteration count
   /// in the scalar epilogue, from where the vectorized loop left off.
   /// In cases where the loop skeleton is more complicated (eg. epilogue
   /// vectorization) and the resume values can come from an additional bypass
   /// block, the \p AdditionalBypass pair provides information about the bypass
   /// block and the end value on the edge from bypass to this loop.
   void createInductionResumeValues(
void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr,
   if (auto *II = dyn_cast<AssumeInst>(Cloned))
     AC->registerAssumption(II);
 
   // End if-block.
   if (IfPredicateInstr)
     PredicatedInstructions.push_back(Cloned);
 }
 
-void InnerLoopVectorizer::createHeaderBranch(Loop *L) {
-  BasicBlock *Header = L->getHeader();
-  assert(!L->getLoopLatch() && "loop should not have a latch at this point");
-
-  IRBuilder<> B(Header->getTerminator());
-  Instruction *OldInst =
-      getDebugLocFromInstOrOperands(Legal->getPrimaryInduction());
-  setDebugLocFromInst(OldInst, &B);
-
-  // Connect the header to the exit and header blocks and replace the old
-  // terminator.
-  B.CreateCondBr(B.getTrue(), L->getUniqueExitBlock(), Header);
-
-  // Now we have two terminators. Remove the old one from the block.
-  Header->getTerminator()->eraseFromParent();
-}
-
 Value *InnerLoopVectorizer::getOrCreateTripCount(BasicBlock *InsertBlock) {
   if (TripCount)
     return TripCount;
 
   assert(InsertBlock);
   IRBuilder<> Builder(InsertBlock->getTerminator());
   // Find the loop boundaries.
   ScalarEvolution *SE = PSE.getSE();
BasicBlock *InnerLoopVectorizer::emitMemRuntimeChecks(BasicBlock *Bypass) {
   LVer = std::make_unique<LoopVersioning>(
       *Legal->getLAI(),
       Legal->getLAI()->getRuntimePointerChecking()->getChecks(), OrigLoop, LI,
       DT, PSE.getSE());
   LVer->prepareNoAliasMetadata();
   return MemCheckBlock;
 }
 
-Loop *InnerLoopVectorizer::createVectorLoopSkeleton(StringRef Prefix) {
+void InnerLoopVectorizer::createVectorLoopSkeleton(StringRef Prefix) {
   LoopScalarBody = OrigLoop->getHeader();
   LoopVectorPreHeader = OrigLoop->getLoopPreheader();
   assert(LoopVectorPreHeader && "Invalid loop structure");
   LoopExitBlock = OrigLoop->getUniqueExitBlock(); // may be nullptr
   assert((LoopExitBlock || Cost->requiresScalarEpilogue(VF)) &&
          "multiple exit loop without required epilogue?");
 
   LoopMiddleBlock =
void InnerLoopVectorizer::createVectorLoopSkeleton(StringRef Prefix) {
   // Insert the new loop into the loop nest and register the new basic blocks
   // before calling any utilities such as SCEV that require valid LoopInfo.
   if (ParentLoop) {
     ParentLoop->addChildLoop(Lp);
   } else {
     LI->addTopLevelLoop(Lp);
   }
   Lp->addBasicBlockToLoop(LoopVectorBody, *LI);
-  return Lp;
 }
 
 void InnerLoopVectorizer::createInductionResumeValues(
     std::pair<BasicBlock *, Value *> AdditionalBypass) {
   assert(((AdditionalBypass.first && AdditionalBypass.second) ||
           (!AdditionalBypass.first && !AdditionalBypass.second)) &&
          "Inconsistent information about additional bypass.");
 
(opt)  v      <-- edge from middle to exit iff epilogue is not required.
   // wrong, and not simply for SCEV.  The trip count of the original loop
   // simply happens to be prone to hitting this in practice.  In theory, we
   // can hit the same issue for any SCEV, or ValueTracking query done during
   // mutation.  See PR49900.
   getOrCreateTripCount(OrigLoop->getLoopPreheader());
 
   // Create an empty vector loop, and prepare basic blocks for the runtime
   // checks.
-  Loop *Lp = createVectorLoopSkeleton("");
+  createVectorLoopSkeleton("");
 
   // Now, compare the new count to zero. If it is zero skip the vector loop and
   // jump to the scalar loop. This check also covers the case where the
   // backedge-taken count is uint##_max: adding one to it will overflow leading
   // to an incorrect trip count of zero. In this (rare) case we will also jump
   // to the scalar loop.
   emitMinimumIterationCountCheck(LoopScalarPreHeader);
 
   // Generate the code to check any assumptions that we've made for SCEV
   // expressions.
   emitSCEVChecks(LoopScalarPreHeader);
 
   // Generate the code that checks in runtime if arrays overlap. We put the
   // checks into a separate block to make the more common case of few elements
   // faster.
   emitMemRuntimeChecks(LoopScalarPreHeader);
 
-  createHeaderBranch(Lp);
-
   // Emit phis for the new starting index of the scalar loop.
   createInductionResumeValues();
 
   return {completeLoopSkeleton(OrigLoopID), nullptr};
 }
 
 // Fix up external users of the induction variable. At this point, we are
 // in LCSSA form, with all external PHIs that use the IV having one input value,
void LoopVectorizationPlanner::executePlan(ElementCount BestVF, unsigned BestUF,
   LLVM_DEBUG(dbgs() << "Executing best plan with VF=" << BestVF << ", UF=" << BestUF
                     << '\n');
 
   // Perform the actual loop transformation.
 
   // 1. Create a new empty loop. Unlink the old loop and connect the new one.
   VPTransformState State{BestVF, BestUF, LI, DT, ILV.Builder, &ILV, &BestVPlan};
   Value *CanonicalIVStartValue;
-  std::tie(State.CFG.PrevBB, CanonicalIVStartValue) =
+  std::tie(State.CFG.VectorPreHeader, CanonicalIVStartValue) =
       ILV.createVectorizedLoopSkeleton();
   ILV.collectPoisonGeneratingRecipes(State);
 
   ILV.printDebugTracesAtStart();
 
   //===------------------------------------------------===//
   //
   // Notice: any optimization or new instruction that go
   // into the code below should also be implemented in
   // the cost-model.

 // EpilogueVectorizerMainLoop
 //===--------------------------------------------------------------------===//
 
 /// This function is partially responsible for generating the control flow
 /// depicted in https://llvm.org/docs/Vectorizers.html#epilogue-vectorization.
 std::pair<BasicBlock *, Value *>
 EpilogueVectorizerMainLoop::createEpilogueVectorizedLoopSkeleton() {
   MDNode *OrigLoopID = OrigLoop->getLoopID();
-  Loop *Lp = createVectorLoopSkeleton("");
+  createVectorLoopSkeleton("");
 
   // Generate the code to check the minimum iteration count of the vector
   // epilogue (see below).
   EPI.EpilogueIterationCountCheck =
       emitMinimumIterationCountCheck(LoopScalarPreHeader, true);
   EPI.EpilogueIterationCountCheck->setName("iter.check");
 
   // Generate the code to check any assumptions that we've made for SCEV
EpilogueVectorizerMainLoop::createEpilogueVectorizedLoopSkeleton() {
   // trip count. Note: the branch will get updated later on when we vectorize
   // the epilogue.
   EPI.MainLoopIterationCountCheck =
       emitMinimumIterationCountCheck(LoopScalarPreHeader, false);
 
   // Generate the induction variable.
   Value *CountRoundDown = getOrCreateVectorTripCount(LoopVectorPreHeader);
   EPI.VectorTripCount = CountRoundDown;
-  createHeaderBranch(Lp);
 
   // Skip induction resume value creation here because they will be created in
   // the second pass. If we created them here, they wouldn't be used anyway,
   // because the vplan in the second pass still contains the inductions from the
   // original loop.
 
   return {completeLoopSkeleton(OrigLoopID), nullptr};
 }

 // EpilogueVectorizerEpilogueLoop
 //===--------------------------------------------------------------------===//
 
 /// This function is partially responsible for generating the control flow
 /// depicted in https://llvm.org/docs/Vectorizers.html#epilogue-vectorization.
 std::pair<BasicBlock *, Value *>
 EpilogueVectorizerEpilogueLoop::createEpilogueVectorizedLoopSkeleton() {
   MDNode *OrigLoopID = OrigLoop->getLoopID();
-  Loop *Lp = createVectorLoopSkeleton("vec.epilog.");
+  createVectorLoopSkeleton("vec.epilog.");
 
   // Now, compare the remaining count and if there aren't enough iterations to
   // execute the vectorized epilogue skip to the scalar part.
   BasicBlock *VecEpilogueIterationCountCheck = LoopVectorPreHeader;
   VecEpilogueIterationCountCheck->setName("vec.epilog.iter.check");
   LoopVectorPreHeader =
       SplitBlock(LoopVectorPreHeader, LoopVectorPreHeader->getTerminator(), DT,
                  LI, nullptr, "vec.epilog.ph");
EpilogueVectorizerEpilogueLoop::createEpilogueVectorizedLoopSkeleton() {
   // vector epilogue preheader
   Type *IdxTy = Legal->getWidestInductionType();
   PHINode *EPResumeVal = PHINode::Create(IdxTy, 2, "vec.epilog.resume.val",
                                          LoopVectorPreHeader->getFirstNonPHI());
   EPResumeVal->addIncoming(EPI.VectorTripCount, VecEpilogueIterationCountCheck);
   EPResumeVal->addIncoming(ConstantInt::get(IdxTy, 0),
                            EPI.MainLoopIterationCountCheck);
 
-  // Generate the induction variable.
-  createHeaderBranch(Lp);
-
   // Generate induction resume values. These variables save the new starting
   // indexes for the scalar loop. They are used to test if there are any tail
   // iterations left once the vector loop has completed.
   // Note that when the vectorized epilogue is skipped due to iteration count
   // check, then the resume value for the induction variable comes from
   // the trip count of the main vector loop, hence passing the AdditionalBypass
   // argument.
   createInductionResumeValues({VecEpilogueIterationCountCheck,

llvm/lib/Transforms/Vectorize/VPlan.cpp

void VPlan::prepareToExecute(Value *TripCountV, Value *VectorTripCountV,
   // Check if the trip count is needed, and if so build it.
   if (TripCount && TripCount->getNumUsers()) {
     for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part)
       State.set(TripCount, TripCountV, Part);
   }
 
   // Check if the backedge taken count is needed, and if so build it.
   if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
-    IRBuilder<> Builder(State.CFG.PrevBB->getTerminator());
+    IRBuilder<> Builder(State.CFG.VectorPreHeader->getTerminator());
     auto *TCMO = Builder.CreateSub(TripCountV,
                                    ConstantInt::get(TripCountV->getType(), 1),
                                    "trip.count.minus.1");
     auto VF = State.VF;
     Value *VTCMO =
         VF.isScalar() ? TCMO : Builder.CreateVectorSplat(VF, TCMO, "broadcast");
     for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part)
       State.set(BackedgeTakenCount, VTCMO, Part);
if (CanonicalIVStartValue) {
     IV->setOperand(0, VPV);
   }
 }
 
 /// Generate the code inside the body of the vectorized loop. Assumes a single
 /// LoopVectorBody basic-block was created for this. Introduce additional
 /// basic-blocks as needed, and fill them all.
 void VPlan::execute(VPTransformState *State) {
-  // 0. Set the reverse mapping from VPValues to Values for code generation.
+  // Set the reverse mapping from VPValues to Values for code generation.
   for (auto &Entry : Value2VPValue)
     State->VPValue2Value[Entry.second] = Entry.first;
 
-  BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
-  State->CFG.VectorPreHeader = VectorPreHeaderBB;
-  BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
-  assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
-
+  // Initialize CFG state.
+  State->CFG.PrevBB = State->CFG.VectorPreHeader->getSingleSuccessor();
+  State->CFG.PrevVPBB = nullptr;
+  BasicBlock *VectorHeaderBB = State->CFG.PrevBB;
+  State->CFG.ExitBB = VectorHeaderBB->getSingleSuccessor();
   Loop *L = State->LI->getLoopFor(VectorHeaderBB);
   State->CurrentVectorLoop = L;
-  State->CFG.ExitBB = L->getExitBlock();
 
   // Remove the edge between Header and Latch to allow other connections.
   // Temporarily terminate with unreachable until CFG is rewired.
   // Note: this asserts the generated code's assumption that
   // getFirstInsertionPt() can be dereferenced into an Instruction.
   VectorHeaderBB->getTerminator()->eraseFromParent();
   State->Builder.SetInsertPoint(VectorHeaderBB);
   UnreachableInst *Terminator = State->Builder.CreateUnreachable();
   State->Builder.SetInsertPoint(Terminator);
 
   // Generate code in loop body.
-  State->CFG.PrevVPBB = nullptr;
-  State->CFG.PrevBB = VectorHeaderBB;
-
   for (VPBlockBase *Block : depth_first(Entry))
     Block->execute(State);
 
   // Setup branch terminator successors for VPBBs in VPBBsToFix based on
   // VPBB's successors.
   for (auto VPBB : State->CFG.VPBBsToFix) {
     assert(EnableVPlanNativePath &&
            "Unexpected VPBBsToFix in non VPlan-native path");