Vectorizer: Refactor code for runtime checks generation.

[mzolotukhin]

Summary

This is the main part of the refactoring patch D9332, it should be easier to
review it in phabricator. The other parts are trivial, and I don't think there
is a need in uploading them (but of course I can do so, if that'll make the
review easier).

[mzolotukhin]

Ping.

[hfinkel]

lib/Transforms/Vectorize/LoopVectorize.cpp

2077

Are you eliminating the need for this anchor instruction because you're splitting the block later?

2117

loops -> loop's

[mzolotukhin]

lib/Transforms/Vectorize/LoopVectorize.cpp

2077

Yes, exactly. When we split the basic block at the moment when we're going to populate it with instructions, we no longer need any anchors.

2117

Thanks, I'll fix that.

[mzolotukhin]

• s/loops/loop's/

[mzolotukhin]

Also rebased on trunk. Does it look good?

[hfinkel]

Yes, LGTM.

[mzolotukhin]

Thanks, Hal!

I committed the patches in r241738...r241742. It's slightly different from the one posted here, because the trunk has changed recently, but the idea is the same.

Michael

lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::createEmptyLoop() {
   // value from the induction PHI node. If we don't have an induction variable
   // then we know that it starts at zero.
   Builder.SetInsertPoint(BypassBlock->getTerminator());
   Value *StartIdx = ExtendedIdx = OldInduction ?
     Builder.CreateZExt(OldInduction->getIncomingValueForBlock(BypassBlock),
                        IdxTy):
     ConstantInt::get(IdxTy, 0);
 
-  // We need an instruction to anchor the overflow check on. StartIdx needs to
-  // be defined before the overflow check branch. Because the scalar preheader
-  // is going to merge the start index and so the overflow branch block needs to
-  // contain a definition of the start index.
-  Instruction *OverflowCheckAnchor = BinaryOperator::CreateAdd(
-      StartIdx, ConstantInt::get(IdxTy, 0), "overflow.check.anchor",
-      BypassBlock->getTerminator());
-
   // Count holds the overall loop count (N).
   Value *Count = Exp.expandCodeFor(ExitCount, ExitCount->getType(),
                                    BypassBlock->getTerminator());
 
   LoopBypassBlocks.push_back(BypassBlock);
 
   // Split the single block loop into the two loop structure described above.
-  BasicBlock *VectorPH =
-  BypassBlock->splitBasicBlock(BypassBlock->getTerminator(), "vector.ph");
   BasicBlock *VecBody =
-  VectorPH->splitBasicBlock(VectorPH->getTerminator(), "vector.body");
+  BypassBlock->splitBasicBlock(BypassBlock->getTerminator(), "vector.body");
   BasicBlock *MiddleBlock =
   VecBody->splitBasicBlock(VecBody->getTerminator(), "middle.block");
   BasicBlock *ScalarPH =
   MiddleBlock->splitBasicBlock(MiddleBlock->getTerminator(), "scalar.ph");
 
   // Create and register the new vector loop.
   Loop* Lp = new Loop();
   Loop *ParentLoop = OrigLoop->getParentLoop();
 
   // 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);
     ParentLoop->addBasicBlockToLoop(ScalarPH, *LI);
-    ParentLoop->addBasicBlockToLoop(VectorPH, *LI);
     ParentLoop->addBasicBlockToLoop(MiddleBlock, *LI);
   } else {
     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);
 
   // This is the IR builder that we use to add all of the logic for bypassing
   // the new vector loop.
   IRBuilder<> BypassBuilder(BypassBlock->getTerminator());
+
+  // Generate code to check that the loops trip count that we computed by adding
+  // one to the backedge-taken count will not overflow.
+
+  BasicBlock *CheckBlock = BypassBlock->splitBasicBlock(
+      BypassBlock->getTerminator(), "overflow.checked");
+  if (ParentLoop)
+    ParentLoop->addBasicBlockToLoop(CheckBlock, *LI);
+
+  BypassBuilder.SetInsertPoint(BypassBlock->getTerminator());
+  BypassBuilder.CreateCondBr(CheckBCOverflow, ScalarPH, CheckBlock);
+  BypassBlock->getTerminator()->eraseFromParent();
+  BypassBuilder.SetInsertPoint(CheckBlock->getTerminator());
+  BypassBlock = CheckBlock;
+
   setDebugLocFromInst(BypassBuilder,
                       getDebugLocFromInstOrOperands(OldInduction));
 
   // We may need to extend the index in case there is a type mismatch.
   // We know that the count starts at zero and does not overflow.
   if (Count->getType() != IdxTy) {
     // The exit count can be of pointer type. Convert it to the correct
     // integer type.
void InnerLoopVectorizer::createEmptyLoop() {
   Value *IdxEndRoundDown = BypassBuilder.CreateAdd(CountRoundDown, StartIdx,
                                                      "end.idx.rnd.down");
 
   // 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");
 
-  BasicBlock *LastBypassBlock = BypassBlock;
-
-  // Generate code to check that the loops trip count that we computed by adding
-  // one to the backedge-taken count will not overflow.
-  {
-    auto PastOverflowCheck =
-        std::next(BasicBlock::iterator(OverflowCheckAnchor));
-    BasicBlock *CheckBlock =
-      LastBypassBlock->splitBasicBlock(PastOverflowCheck, "overflow.checked");
-    if (ParentLoop)
-      ParentLoop->addBasicBlockToLoop(CheckBlock, *LI);
-    LoopBypassBlocks.push_back(CheckBlock);
-    Instruction *OldTerm = LastBypassBlock->getTerminator();
-    BranchInst::Create(ScalarPH, CheckBlock, CheckBCOverflow, OldTerm);
-    OldTerm->eraseFromParent();
-    LastBypassBlock = CheckBlock;
-  }
+  CheckBlock = BypassBlock->splitBasicBlock(
+      BypassBlock->getTerminator(), "vector.ph");
+  LoopBypassBlocks.push_back(BypassBlock);
+  BypassBuilder.SetInsertPoint(BypassBlock->getTerminator());
+  BypassBuilder.CreateCondBr(Cmp, MiddleBlock, CheckBlock);
+  BypassBlock->getTerminator()->eraseFromParent();
+  BypassBuilder.SetInsertPoint(CheckBlock->getTerminator());
+  BypassBlock = CheckBlock;
 
   // Generate the code to check that the strides we assumed to be one are really
   // one. We want the new basic block to start at the first instruction in a
   // sequence of instructions that form a check.
   Instruction *StrideCheck;
   Instruction *FirstCheckInst;
   std::tie(FirstCheckInst, StrideCheck) =
-      addStrideCheck(LastBypassBlock->getTerminator());
+      addStrideCheck(BypassBlock->getTerminator());
   if (StrideCheck) {
     AddedSafetyChecks = true;
     // Create a new block containing the stride check.
-    BasicBlock *CheckBlock =
-        LastBypassBlock->splitBasicBlock(FirstCheckInst, "vector.stridecheck");
+    BypassBlock->setName("vector.stridecheck");
+    BasicBlock *CheckBlock = BypassBlock->splitBasicBlock(
+        BypassBlock->getTerminator(), "vector.ph");
     if (ParentLoop)
       ParentLoop->addBasicBlockToLoop(CheckBlock, *LI);
-    LoopBypassBlocks.push_back(CheckBlock);
+    LoopBypassBlocks.push_back(BypassBlock);
 
     // Replace the branch into the memory check block with a conditional branch
     // for the "few elements case".
-    Instruction *OldTerm = LastBypassBlock->getTerminator();
-    BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm);
-    OldTerm->eraseFromParent();
-
-    Cmp = StrideCheck;
-    LastBypassBlock = CheckBlock;
+    BypassBuilder.SetInsertPoint(BypassBlock->getTerminator());
+    BypassBuilder.CreateCondBr(StrideCheck, MiddleBlock, CheckBlock);
+    BypassBlock->getTerminator()->eraseFromParent();
+    BypassBuilder.SetInsertPoint(CheckBlock->getTerminator());
+    BypassBlock = CheckBlock;
   }
 
   // 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.
   Instruction *MemRuntimeCheck;
   std::tie(FirstCheckInst, MemRuntimeCheck) =
-    Legal->getLAI()->addRuntimeCheck(LastBypassBlock->getTerminator());
+    Legal->getLAI()->addRuntimeCheck(BypassBlock->getTerminator());
   if (MemRuntimeCheck) {
     AddedSafetyChecks = true;
-    // Create a new block containing the memory check.
-    BasicBlock *CheckBlock =
-        LastBypassBlock->splitBasicBlock(FirstCheckInst, "vector.memcheck");
+    BypassBlock->setName("vector.memcheck");
+    BasicBlock *CheckBlock = BypassBlock->splitBasicBlock(
+        BypassBlock->getTerminator(), "vector.ph");
+    BypassBuilder.SetInsertPoint(CheckBlock->getTerminator());
     if (ParentLoop)
       ParentLoop->addBasicBlockToLoop(CheckBlock, *LI);
-    LoopBypassBlocks.push_back(CheckBlock);
-
-    // Replace the branch into the memory check block with a conditional branch
-    // for the "few elements case".
-    Instruction *OldTerm = LastBypassBlock->getTerminator();
-    BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm);
-    OldTerm->eraseFromParent();
+    LoopBypassBlocks.push_back(BypassBlock);
 
-    Cmp = MemRuntimeCheck;
-    LastBypassBlock = CheckBlock;
+    BypassBuilder.SetInsertPoint(BypassBlock->getTerminator());
+    BypassBuilder.CreateCondBr(MemRuntimeCheck, MiddleBlock, CheckBlock);
+    BypassBlock->getTerminator()->eraseFromParent();
+    BypassBuilder.SetInsertPoint(CheckBlock->getTerminator());
+    BypassBlock = CheckBlock;
   }
 
-  LastBypassBlock->getTerminator()->eraseFromParent();
-  BranchInst::Create(MiddleBlock, VectorPH, Cmp,
-                     LastBypassBlock);
-
   // We are going to resume the execution of the scalar loop.
   // Go over all of the induction variables that we found and fix the
   // PHIs that are left in the scalar version of the loop.
   // The starting values of PHI nodes depend on the counter of the last
   // iteration in the vectorized loop.
   // If we come from a bypass edge then we need to start from the original
   // start value.
 
Value *CmpN = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, IdxEnd,
                                 MiddleBlock->getTerminator());
 
   BranchInst::Create(ExitBlock, ScalarPH, CmpN, MiddleBlock->getTerminator());
   // Remove the old terminator.
   MiddleBlock->getTerminator()->eraseFromParent();
 
   // Create i+1 and fill the PHINode.
   Value *NextIdx = Builder.CreateAdd(Induction, Step, "index.next");
-  Induction->addIncoming(StartIdx, VectorPH);
+  Induction->addIncoming(StartIdx, BypassBlock);
   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;
+  LoopVectorPreHeader = BypassBlock;
   LoopScalarPreHeader = ScalarPH;
   LoopMiddleBlock = MiddleBlock;
   LoopExitBlock = ExitBlock;
   LoopVectorBody.push_back(VecBody);
   LoopScalarBody = OldBasicBlock;
 
   LoopVectorizeHints Hints(Lp, true);
   Hints.setAlreadyVectorized();