[LV] Factor the creation of the loop induction variable out of createEmptyLoop()

[jmolloy]

Summary

It makes things easier to understand if this is in a helper method. This is part of my ongoing spaghetti-removal operation on createEmptyLoop.

[mzolotukhin]

Hi James,

Thanks for your efforts in cleaning this up. In general, LGTM, with a few remarks inline:

lib/Transforms/Vectorize/LoopVectorize.cpp

2572

DL seems to be unused. And it's not clear from the name, what it stands for. Should it be used instead of OldInduction in setDebugLocFromInst?

2589

Should Latch be used instead of Header here?

[jmolloy]

Hi Michael,

Thankyou so much for reviewing my mountain of code reviews :)

Patch updated. I've also taken your advice on other commits and checked all code changes for each commit - there's nothing unexpected in any of them.

Cheers,

James

lib/Transforms/Vectorize/LoopVectorize.cpp

2572

Good catch, thanks! Updated.

2589

I don't think so - Induction is in the latch and needs to branch back to the header.

[mzolotukhin]

lib/Transforms/Vectorize/LoopVectorize.cpp

2589

AFAIU, we have a following CFG:

(PreHeader)
    |
    |
    v
(Header)<-
    |     |
    |     |
    v     /
(Latch) --
    |
    |
    v
(Exit)

(If my graphics isn't rendered well, the edges in CFG are: PreHeader-->Header, Header-->Latch, Latch-->Header, Latch-->Exit)

Now, we're building Induction in Header. It is a PHI, and should have two incoming values: one from the preheader (L->getLoopPreheader), and one from the latch (but you use Header instead).

Am I wrong somewhere?

[mzolotukhin]

Hi James,

With this fix the patch LGTM.

Thanks,
Michael

[jmolloy]

Thanks! r246632

lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
   /// \brief Add checks for strides that were assumed to be 1.
   ///
   /// Returns the last check instruction and the first check instruction in the
   /// pair as (first, last).
   std::pair<Instruction *, Instruction *> addStrideCheck(Instruction *Loc);
 
   /// Create an empty loop, based on the loop ranges of the old loop.
   void createEmptyLoop();
+  /// Create a new induction variable inside L.
+  PHINode *createInductionVariable(Loop *L, Value *Start, Value *End,
+                                   Value *Step, Instruction *DL);
   /// Copy and widen the instructions from the old loop.
   virtual void vectorizeLoop();
 
   /// \brief The Loop exit block may have single value PHI nodes where the
   /// incoming value is 'Undef'. While vectorizing we only handled real values
   /// that were defined inside the loop. Here we fix the 'undef case'.
   /// See PR14725.
   void fixLCSSAPHIs();
InnerLoopVectorizer::addStrideCheck(Instruction *Loc) {
   Instruction *TheCheck =
       BinaryOperator::CreateAnd(Check, ConstantInt::getTrue(Ctx));
   ChkBuilder.Insert(TheCheck, "stride.not.one");
   FirstInst = getFirstInst(FirstInst, TheCheck, Loc);
 
   return std::make_pair(FirstInst, TheCheck);
 }
 
+PHINode *InnerLoopVectorizer::createInductionVariable(Loop *L,
+                                                      Value *Start,
+                                                      Value *End,
+                                                      Value *Step,
+                                                      Instruction *DebugLoc) {
+  BasicBlock *Header = L->getHeader();
+  BasicBlock *Latch = L->getLoopLatch();
+  // As we're just creating this loop, it's possible no latch exists
+  // yet. If so, use the header as this will be a single block loop.
+  if (!Latch)
+    Latch = Header;
+    
+  IRBuilder<> Builder(Header->getFirstInsertionPt());
+  setDebugLocFromInst(Builder, getDebugLocFromInstOrOperands(DebugLoc));
+  auto *Induction = Builder.CreatePHI(Start->getType(), 2, "index");
+
+  Builder.SetInsertPoint(Latch->getTerminator());
+  
+  // Create i+1 and fill the PHINode.
+  Value *Next = Builder.CreateAdd(Induction, Step, "index.next");
+  Induction->addIncoming(Start, L->getLoopPreheader());
+  Induction->addIncoming(Next, Header);
+  // Create the compare.
+  Value *ICmp = Builder.CreateICmpEQ(Next, End);
+  Builder.CreateCondBr(ICmp, L->getExitBlock(), Header);
+  
+  // Now we have two terminators. Remove the old one from the block.
+  Latch->getTerminator()->eraseFromParent();
+
+  return Induction;
+}
+
 void InnerLoopVectorizer::createEmptyLoop() {
   /*
    In this function we generate a new loop. The new loop will contain
    the vectorized instructions while the old loop will continue to run the
    scalar remainder.
 
        [ ] <-- loop iteration number check.
     /   |
if (ParentLoop) {
     LI->addTopLevelLoop(Lp);
   }
   Lp->addBasicBlockToLoop(VecBody, *LI);
 
   // Use this IR builder to create the loop instructions (Phi, Br, Cmp)
   // inside the loop.
   Builder.SetInsertPoint(VecBody->getFirstNonPHI());
 
-  // Generate the induction variable.
-  setDebugLocFromInst(Builder, getDebugLocFromInstOrOperands(OldInduction));
-  Induction = Builder.CreatePHI(IdxTy, 2, "index");
-  // The loop step is equal to the vectorization factor (num of SIMD elements)
-  // times the unroll factor (num of SIMD instructions).
-  Constant *Step = ConstantInt::get(IdxTy, VF * UF);
-
   // Generate code to check that the loop's trip count is not less than the
   // minimum loop iteration number threshold.
   BasicBlock *NewVectorPH =
       VectorPH->splitBasicBlock(VectorPH->getTerminator(), "min.iters.checked");
   if (ParentLoop)
     ParentLoop->addBasicBlockToLoop(NewVectorPH, *LI);
   ReplaceInstWithInst(VectorPH->getTerminator(),
                       BranchInst::Create(ScalarPH, NewVectorPH, CheckMinIters));
   VectorPH = NewVectorPH;
 
   // This is the IR builder that we use to add all of the logic for bypassing
   // the new vector loop.
   IRBuilder<> BypassBuilder(VectorPH->getTerminator());
   setDebugLocFromInst(BypassBuilder,
                       getDebugLocFromInstOrOperands(OldInduction));
 
   // Add the start index to the loop count to get the new end index.
   Value *IdxEnd = BypassBuilder.CreateAdd(Count, StartIdx, "end.idx");
 
   // Now we need to generate the expression for N - (N % VF), which is
   // the part that the vectorized body will execute.
+  // The loop step is equal to the vectorization factor (num of SIMD elements)
+  // times the unroll factor (num of SIMD instructions).
+  Constant *Step = ConstantInt::get(IdxTy, VF * UF);
   Value *R = BypassBuilder.CreateURem(Count, Step, "n.mod.vf");
   Value *CountRoundDown = BypassBuilder.CreateSub(Count, R, "n.vec");
   Value *IdxEndRoundDown = BypassBuilder.CreateAdd(CountRoundDown, StartIdx,
                                                      "end.idx.rnd.down");
 
+  // Generate the induction variable.
+  Induction =
+    createInductionVariable(Lp, StartIdx, IdxEndRoundDown, Step,
+                            getDebugLocFromInstOrOperands(OldInduction));
+  
   // Now, compare the new count to zero. If it is zero skip the vector loop and
   // jump to the scalar loop.
   Value *Cmp =
       BypassBuilder.CreateICmpEQ(IdxEndRoundDown, StartIdx, "cmp.zero");
   NewVectorPH =
       VectorPH->splitBasicBlock(VectorPH->getTerminator(), "vector.ph");
   if (ParentLoop)
     ParentLoop->addBasicBlockToLoop(NewVectorPH, *LI);
void InnerLoopVectorizer::createEmptyLoop() {
   // all of the iterations in the first vector loop.
   // If (N - N%VF) == N, then we *don't* need to run the remainder.
   Value *CmpN = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, IdxEnd,
                                 ResumeIndex, "cmp.n",
                                 MiddleBlock->getTerminator());
   ReplaceInstWithInst(MiddleBlock->getTerminator(),
                       BranchInst::Create(ExitBlock, ScalarPH, CmpN));
 
-  // Create i+1 and fill the PHINode.
-  Value *NextIdx = Builder.CreateAdd(Induction, Step, "index.next");
-  Induction->addIncoming(StartIdx, VectorPH);
-  Induction->addIncoming(NextIdx, VecBody);
-  // Create the compare.
-  Value *ICmp = Builder.CreateICmpEQ(NextIdx, IdxEndRoundDown);
-  Builder.CreateCondBr(ICmp, MiddleBlock, VecBody);
-
-  // Now we have two terminators. Remove the old one from the block.
-  VecBody->getTerminator()->eraseFromParent();
-
   // Get ready to start creating new instructions into the vectorized body.
   Builder.SetInsertPoint(VecBody->getFirstInsertionPt());
 
   // Save the state.
   LoopVectorPreHeader = VectorPH;
   LoopScalarPreHeader = ScalarPH;
   LoopMiddleBlock = MiddleBlock;
   LoopExitBlock = ExitBlock;