Refactor code for adding runtime checks in vectorizer.

[mzolotukhin]

Summary

Currently this code is very hard to manage:

• variables defined in the beginning of the function might be used several screens later
• Code for adding checks isn't uniform enough (some use Instruction::Create, others use IRBuilder)
• Code for adding one check is tangled with code for adding next check, because we split basic block only at that time.

I tried to fix this issues, and hopefully that improves the code readability.

[majnemer]

Any reason we can't use the IRBuilder instead of BranchInst::Create?

A side effect is that it would make it a little easier to make:

br i1 true, label %scalar.ph, label %overflow.checked

simply:

br label %scalar.ph

by specializing the builder's CreateCondBr to "Do the Right Thing (TM)" when given a constant condition.

[mzolotukhin]

Hi David,
No actual reason for not using builder for branches too, except that it wasn't used there before (this part was uniform in code for all checks, so I kept it as is).

[mzolotukhin]

• Use IRBuilder instead of BranchInst::Create.
• Fix a bug in code generation for StrideCheck.

[mzolotukhin]

Ping.

[mzolotukhin]

Ping ^2.

[hfinkel]

I like the BypassBlock -> VectorPH rename (although I'd prefer it be named VectorPreHeader); can you please just commit that and then rebase the rest of the patch on that. It is a separable change.

[mzolotukhin]

Hi Hal,

The thing is that VectorPH already exists in the original code. Actually, the main points of this patch was to make this blocks structure more apparent - rather than having BypassBlock, LastBypassBlock, VectorPH and others, I'd prefer to have only VectorPH.

Another issue that I tried to solve here is the following. When we add a new runtime check in the original code, we

1. Add instructions for new check to the basic block with previous check. E.g.:

std::tie(FirstCheckInst, MemRuntimeCheck) = Legal->getLAI()->addRuntimeCheck(LastBypassBlock->getTerminator());

2. LastBypassBlock now contains instructions for both previous and new check. Split it:

BasicBlock *CheckBlock = LastBypassBlock->splitBasicBlock(FirstCheckInst, "vector.memcheck");

3. Add a branch instruction based on the *previous* check:

Instruction *OldTerm = LastBypassBlock->getTerminator();
BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm);
OldTerm->eraseFromParent();

4. Save the *current* check - it will be used for creating branch when we create a *next* check.

Cmp = StrideCheck;

So, I tried to remove this dependency between different checks and make code responsible for generation a single check self-dependent and isolated.

PS: I'm fine with renaming VectorPH to VectorPreHeader, I'll do that along with rebasing on top of the trunk.

[mzolotukhin]

• Rename VectorPH to VectorPreHeader.

[hfinkel]

Please commit the BypassBlock -> VectorPreHeader rename now, and then rebase this patch. That will make the remainder easier to review.

test/Transforms/LoopVectorize/induction.ll

116

You've removed the check for the icmp. Why?

[mzolotukhin]

Hi Hal,

I can't commit 's/BypassBlock/VectorPreHeader/' since the original code already has VectorPH, and having both VectorPH and VectorPreHeader simultaneously would be even more confusing. I'll try to remove as many other changes as possible though, and keep only the changes needed for this rename in a separate patch.

Thanks,
Michael

test/Transforms/LoopVectorize/induction.ll

116

I started using IRBuilder, and it folded this expression.

[mzolotukhin]

Hi Hal,

I split the patch to 4 parts, which hopefully would be easier to understand.

0001 - This is the main patch. Here we do most of the code restructuring (but I tried to keep other changes out of it).
0002 - Move some variable initializations closer to their (single) use. It saves some scrolling when reading the code.
0003 - Use IRBuilder for creating branches. Adjust the test case in which we started to fold a constant ‘icmp’.
0004 - Rename BypassBlock to VectorPreHeader. That’s the change you asked to commit, but it can’t be applied before 0001 patch.

• 0002-Move-around-some-initializations.patch5 KBDownload
• msg-31955-824.txt1 KBDownload
• 0001-Vectorizer-Refactor-code-for-runtime-checks-generation.patch8 KBDownload
• 0004-Rename-BypassBlock-to-VectorPreHeader.patch9 KBDownload
• 0003-Use-IRBuilder.patch2 KBDownload

[mzolotukhin]

Hi Hal,

I uploaded the first (biggest) part to phabricator in D10097 - hope this helps with review.
The other 3 parts should be trivial, so I didn't upload them.

Thanks,
Michael

[hfinkel]

• Original Message -----

From: "Michael Zolotukhin" <[e-mail]>
To: [e-mail], [e-mail]
Cc: "david majnemer" <[e-mail]>, [e-mail]
Sent: Wednesday, May 27, 2015 8:16:24 PM
Subject: Re: [PATCH] Refactor code for adding runtime checks in vectorizer.

Hi Hal,

I split the patch to 4 parts, which hopefully would be easier to
understand.

0001 - This is the main patch. Here we do most of the code

I'll review this one in its associated thread.

restructuring (but I tried to keep other changes out of it).
0002 - Move some variable initializations closer to their (single)
use. It saves some scrolling when reading the code.

LGTM.

0003 - Use IRBuilder for creating branches. Adjust the test case in
which we started to fold a constant ‘icmp’.

LGTM.

0004 - Rename BypassBlock to VectorPreHeader. That’s the change you
asked to commit, but it can’t be applied before 0001 patch.

LGTM.

-Hal

• F535343: 0002-Move-around-some-initializations.patch

http://reviews.llvm.org/F535343

• F535346: msg-31955-824.txt http://reviews.llvm.org/F535346
• F535344:

0001-Vectorizer-Refactor-code-for-runtime-checks-generation.patch
http://reviews.llvm.org/F535344

• F535347: 0004-Rename-BypassBlock-to-VectorPreHeader.patch

http://reviews.llvm.org/F535347

• F535345: 0003-Use-IRBuilder.patch http://reviews.llvm.org/F535345

http://reviews.llvm.org/D9332

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

[mzolotukhin]

Slightly changed variant of this refactoring has been committed (see D10097).

lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::createEmptyLoop() {
    |   [ ]_|   <-- old scalar loop to handle remainder.
     \   |
      \  v
       >[ ]     <-- exit block.
    ...
    */
 
   BasicBlock *OldBasicBlock = OrigLoop->getHeader();
-  BasicBlock *BypassBlock = OrigLoop->getLoopPreheader();
+  BasicBlock *VectorPreHeader = OrigLoop->getLoopPreheader();
   BasicBlock *ExitBlock = OrigLoop->getExitBlock();
-  assert(BypassBlock && "Invalid loop structure");
+  assert(VectorPreHeader && "Invalid loop structure");
   assert(ExitBlock && "Must have an exit block");
 
   // Some loops have a single integer induction variable, while other loops
   // don't. One example is c++ iterators that often have multiple pointer
   // induction variables. In the code below we also support a case where we
   // don't have a single induction variable.
   OldInduction = Legal->getInduction();
   Type *IdxTy = Legal->getWidestInductionType();
ExitCount = SE->getAddExpr(BackedgeTakeCount,
                              SE->getConstant(BackedgeTakeCount->getType(), 1));
 
   const DataLayout &DL = OldBasicBlock->getModule()->getDataLayout();
 
   // Expand the trip count and place the new instructions in the preheader.
   // Notice that the pre-header does not change, only the loop body.
   SCEVExpander Exp(*SE, DL, "induction");
 
-  // We need to test whether the backedge-taken count is uint##_max. Adding one
-  // to it will cause overflow and an incorrect loop trip count in the vector
-  // body. In case of overflow we want to directly jump to the scalar remainder
-  // loop.
-  Value *BackedgeCount =
-      Exp.expandCodeFor(BackedgeTakeCount, BackedgeTakeCount->getType(),
-                        BypassBlock->getTerminator());
-  if (BackedgeCount->getType()->isPointerTy())
-    BackedgeCount = CastInst::CreatePointerCast(BackedgeCount, IdxTy,
-                                                "backedge.ptrcnt.to.int",
-                                                BypassBlock->getTerminator());
-  Instruction *CheckBCOverflow =
-      CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, BackedgeCount,
-                      Constant::getAllOnesValue(BackedgeCount->getType()),
-                      "backedge.overflow", BypassBlock->getTerminator());
-
   // The loop index does not have to start at Zero. Find the original start
   // 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());
+  Builder.SetInsertPoint(VectorPreHeader->getTerminator());
+  Value *StartIdx = ExtendedIdx =
+      OldInduction
+          ? Builder.CreateZExt(
+                OldInduction->getIncomingValueForBlock(VectorPreHeader), IdxTy)
+          : ConstantInt::get(IdxTy, 0);
 
-  LoopBypassBlocks.push_back(BypassBlock);
+  LoopBypassBlocks.push_back(VectorPreHeader);
 
   // 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");
+  BasicBlock *VecBody = VectorPreHeader->splitBasicBlock(
+      VectorPreHeader->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());
+  IRBuilder<> BypassBuilder(VectorPreHeader->getTerminator());
+
+  // Generate code to check that the loops trip count that we computed by adding
+  // one to the backedge-taken count will not overflow.
+
+  // We need to test whether the backedge-taken count is uint##_max. Adding one
+  // to it will cause overflow and an incorrect loop trip count in the vector
+  // body. In case of overflow we want to directly jump to the scalar remainder
+  // loop.
+  Value *BackedgeCount =
+      Exp.expandCodeFor(BackedgeTakeCount, BackedgeTakeCount->getType(),
+                        VectorPreHeader->getTerminator());
+  if (BackedgeCount->getType()->isPointerTy())
+    BackedgeCount = BypassBuilder.CreatePointerCast(BackedgeCount, IdxTy,
+                                                    "backedge.ptrcnt.to.int");
+  Value *CheckBCOverflow = BypassBuilder.CreateICmpEQ(
+      BackedgeCount, Constant::getAllOnesValue(BackedgeCount->getType()),
+      "backedge.overflow");
+
+  BasicBlock *CheckBlock = VectorPreHeader->splitBasicBlock(
+      VectorPreHeader->getTerminator(), "overflow.checked");
+  if (ParentLoop)
+    ParentLoop->addBasicBlockToLoop(CheckBlock, *LI);
+
+  BypassBuilder.SetInsertPoint(VectorPreHeader->getTerminator());
+  BypassBuilder.CreateCondBr(CheckBCOverflow, ScalarPH, CheckBlock);
+  VectorPreHeader->getTerminator()->eraseFromParent();
+  BypassBuilder.SetInsertPoint(CheckBlock->getTerminator());
+  VectorPreHeader = CheckBlock;
+
   setDebugLocFromInst(BypassBuilder,
                       getDebugLocFromInstOrOperands(OldInduction));
+  // 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");
+
+  // Count holds the overall loop count (N).
+  Value *Count = Exp.expandCodeFor(ExitCount, ExitCount->getType(),
+                                   VectorPreHeader->getTerminator());
 
   // 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.
     if (ExitCount->getType()->isPointerTy())
       Count = BypassBuilder.CreatePointerCast(Count, IdxTy, "ptrcnt.to.int");
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 = VectorPreHeader->splitBasicBlock(
+      VectorPreHeader->getTerminator(), "vector.ph");
+  LoopBypassBlocks.push_back(VectorPreHeader);
+  BypassBuilder.SetInsertPoint(VectorPreHeader->getTerminator());
+  BypassBuilder.CreateCondBr(Cmp, MiddleBlock, CheckBlock);
+  VectorPreHeader->getTerminator()->eraseFromParent();
+  BypassBuilder.SetInsertPoint(CheckBlock->getTerminator());
+  VectorPreHeader = 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(VectorPreHeader->getTerminator());
   if (StrideCheck) {
     AddedSafetyChecks = true;
     // Create a new block containing the stride check.
-    BasicBlock *CheckBlock =
-        LastBypassBlock->splitBasicBlock(FirstCheckInst, "vector.stridecheck");
+    VectorPreHeader->setName("vector.stridecheck");
+    BasicBlock *CheckBlock = VectorPreHeader->splitBasicBlock(
+        VectorPreHeader->getTerminator(), "vector.ph");
     if (ParentLoop)
       ParentLoop->addBasicBlockToLoop(CheckBlock, *LI);
-    LoopBypassBlocks.push_back(CheckBlock);
+    LoopBypassBlocks.push_back(VectorPreHeader);
 
     // 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(VectorPreHeader->getTerminator());
+    BypassBuilder.CreateCondBr(StrideCheck, MiddleBlock, CheckBlock);
+    VectorPreHeader->getTerminator()->eraseFromParent();
+    BypassBuilder.SetInsertPoint(CheckBlock->getTerminator());
+    VectorPreHeader = 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(VectorPreHeader->getTerminator());
   if (MemRuntimeCheck) {
     AddedSafetyChecks = true;
-    // Create a new block containing the memory check.
-    BasicBlock *CheckBlock =
-        LastBypassBlock->splitBasicBlock(FirstCheckInst, "vector.memcheck");
+    VectorPreHeader->setName("vector.memcheck");
+    BasicBlock *CheckBlock = VectorPreHeader->splitBasicBlock(
+        VectorPreHeader->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(VectorPreHeader);
 
-    Cmp = MemRuntimeCheck;
-    LastBypassBlock = CheckBlock;
+    BypassBuilder.SetInsertPoint(VectorPreHeader->getTerminator());
+    BypassBuilder.CreateCondBr(MemRuntimeCheck, MiddleBlock, CheckBlock);
+    VectorPreHeader->getTerminator()->eraseFromParent();
+    BypassBuilder.SetInsertPoint(CheckBlock->getTerminator());
+    VectorPreHeader = 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, VectorPreHeader);
   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 = VectorPreHeader;
   LoopScalarPreHeader = ScalarPH;
   LoopMiddleBlock = MiddleBlock;
   LoopExitBlock = ExitBlock;
   LoopVectorBody.push_back(VecBody);
   LoopScalarBody = OldBasicBlock;
 
   LoopVectorizeHints Hints(Lp, true);
   Hints.setAlreadyVectorized();

test/Transforms/LoopVectorize/induction.ll

 ; <label>:5                                       ; preds = %1
   ret i32 %2
 }
 
 ; This loop has a backedge taken count of i32_max. We need to check for this
 ; condition and branch directly to the scalar loop.
 
 ; CHECK-LABEL: max_i32_backedgetaken
-; CHECK:  %backedge.overflow = icmp eq i32 -1, -1
-; CHECK:  br i1 %backedge.overflow, label %scalar.ph, label %overflow.checked
+; CHECK:  br i1 true, label %scalar.ph, label %overflow.checked
 
 ; CHECK: scalar.ph:
 ; CHECK:  %bc.resume.val = phi i32 [ %resume.val, %middle.block ], [ 0, %0 ]
 ; CHECK:  %bc.merge.rdx = phi i32 [ 1, %0 ], [ %5, %middle.block ]
 
 define i32 @max_i32_backedgetaken() nounwind readnone ssp uwtable {
 
   br label %1