[VPlan] Introduce condition bit in VPBlockBase.

[dcaballe]

Summary

Context: Patch Series #1 for outer loop vectorization support in LV
using VPlan. (RFC: http://lists.llvm.org/pipermail/llvm-dev/2017-December/119523.html).

This patch introduces a VPValue in VPBlockBase to represent the condition
bit that is used as successor selector when a block has multiple successors.
This information wasn't necessary until now, when we are about to introduce
outer loop vectorization support in VPlan code gen.

Representing the condition bit as a field in VPBlockBase fits well with the VPlan recipe-based
code currently used in the inner loop vectorizer path and its decision about not representing
branches at VPlan instruction level. It also aligns well with our current internal implementation,
which will allow us to upstream patches quicker. However, we think that the explicit representation
of branches at VPlan instruction level will better fit with the VPInstruction model and its DU graph.
For that reason, we are planning to change the proposed condition bit representation (and lack of
branches) in the short term, so this patch should be seen as a stepping stone towards that direction.

[fhahn]

LGTM, thanks.

[dcaballe]

Thanks, Florian! I'll commit next week.

Diego.

lib/Transforms/Vectorize/LoopVectorize.cpp

VPRegionBlock *VPRecipeBuilder::createReplicateRegion(Instruction *Instr,
   auto *PHIRecipe =
       Instr->getType()->isVoidTy() ? nullptr : new VPPredInstPHIRecipe(Instr);
   auto *Exit = new VPBasicBlock(Twine(RegionName) + ".continue", PHIRecipe);
   auto *Pred = new VPBasicBlock(Twine(RegionName) + ".if", PredRecipe);
   VPRegionBlock *Region = new VPRegionBlock(Entry, Exit, RegionName, true);
 
   // Note: first set Entry as region entry and then connect successors starting
   // from it in order, to propagate the "parent" of each VPBasicBlock.
-  VPBlockUtils::insertTwoBlocksAfter(Pred, Exit, Entry);
+  VPBlockUtils::insertTwoBlocksAfter(Pred, Exit, BlockInMask, Entry);
   VPBlockUtils::connectBlocks(Pred, Exit);
 
   return Region;
 }
 
 bool VPRecipeBuilder::tryToCreateRecipe(Instruction *Instr, VFRange &Range,
                                         VPlanPtr &Plan, VPBasicBlock *VPBB) {
   VPRecipeBase *Recipe = nullptr;

lib/Transforms/Vectorize/VPlan.h

private:
   VPRegionBlock *Parent = nullptr;
 
   /// List of predecessor blocks.
   SmallVector<VPBlockBase *, 1> Predecessors;
 
   /// List of successor blocks.
   SmallVector<VPBlockBase *, 1> Successors;
 
+  /// Successor selector, null for zero or single successor blocks.
+  VPValue *CondBit = nullptr;
+
   /// Add \p Successor as the last successor to this block.
   void appendSuccessor(VPBlockBase *Successor) {
     assert(Successor && "Cannot add nullptr successor!");
     Successors.push_back(Successor);
   }
 
   /// Add \p Predecessor as the last predecessor to this block.
   void appendPredecessor(VPBlockBase *Predecessor) {
public:
   }
 
   /// \return the hierarchical predecessor of this VPBlockBase if it has a
   /// single hierarchical predecessor. Otherwise return a null pointer.
   VPBlockBase *getSingleHierarchicalPredecessor() {
     return getEnclosingBlockWithPredecessors()->getSinglePredecessor();
   }
 
+  /// \return the condition bit selecting the successor.
+  VPValue *getCondBit() { return CondBit; }
+
+  const VPValue *getCondBit() const { return CondBit; }
+
+  void setCondBit(VPValue *CV) { CondBit = CV; }
+
   /// Set a given VPBlockBase \p Successor as the single successor of this
   /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor.
   /// This VPBlockBase must have no successors.
   void setOneSuccessor(VPBlockBase *Successor) {
     assert(Successors.empty() && "Setting one successor when others exist.");
     appendSuccessor(Successor);
   }
 
   /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two
-  /// successors of this VPBlockBase. This VPBlockBase is not added as
-  /// predecessor of \p IfTrue or \p IfFalse. This VPBlockBase must have no
-  /// successors.
-  void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse) {
+  /// successors of this VPBlockBase. \p Condition is set as the successor
+  /// selector. This VPBlockBase is not added as predecessor of \p IfTrue or \p
+  /// IfFalse. This VPBlockBase must have no successors.
+  void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
+                        VPValue *Condition) {
     assert(Successors.empty() && "Setting two successors when others exist.");
+    assert(Condition && "Setting two successors without condition!");
+    CondBit = Condition;
     appendSuccessor(IfTrue);
     appendSuccessor(IfFalse);
   }
 
   /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase.
   /// This VPBlockBase must have no predecessors. This VPBlockBase is not added
   /// as successor of any VPBasicBlock in \p NewPreds.
   void setPredecessors(ArrayRef<VPBlockBase *> NewPreds) {

 //===----------------------------------------------------------------------===//
 
 /// Class that provides utilities for VPBlockBases in VPlan.
 class VPBlockUtils {
 public:
   VPBlockUtils() = delete;
 
   /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
-  /// NewBlock as successor of \p BlockPtr and \p Block as predecessor of \p
-  /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p NewBlock
-  /// must have neither successors nor predecessors.
+  /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
+  /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. If \p BlockPtr
+  /// has more than one successor, its conditional bit is propagated to \p
+  /// NewBlock. \p NewBlock must have neither successors nor predecessors.
   static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
     assert(NewBlock->getSuccessors().empty() &&
            "Can't insert new block with successors.");
     // TODO: move successors from BlockPtr to NewBlock when this functionality
     // is necessary. For now, setBlockSingleSuccessor will assert if BlockPtr
     // already has successors.
     BlockPtr->setOneSuccessor(NewBlock);
     NewBlock->setPredecessors({BlockPtr});
     NewBlock->setParent(BlockPtr->getParent());
   }
 
   /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
   /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
   /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
-  /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
-  /// and \p IfTrue and \p IfFalse must have neither successors nor
-  /// predecessors.
+  /// parent to \p IfTrue and \p IfFalse. \p Condition is set as the successor
+  /// selector. \p BlockPtr must have no successors and \p IfTrue and \p IfFalse
+  /// must have neither successors nor predecessors.
   static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
-                                   VPBlockBase *BlockPtr) {
+                                   VPValue *Condition, VPBlockBase *BlockPtr) {
     assert(IfTrue->getSuccessors().empty() &&
            "Can't insert IfTrue with successors.");
     assert(IfFalse->getSuccessors().empty() &&
            "Can't insert IfFalse with successors.");
-    BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
+    BlockPtr->setTwoSuccessors(IfTrue, IfFalse, Condition);
     IfTrue->setPredecessors({BlockPtr});
     IfFalse->setPredecessors({BlockPtr});
     IfTrue->setParent(BlockPtr->getParent());
     IfFalse->setParent(BlockPtr->getParent());
   }
 
   /// Connect VPBlockBases \p From and \p To bi-directionally. Append \p To to
   /// the successors of \p From and \p From to the predecessors of \p To. Both

lib/Transforms/Vectorize/VPlan.cpp

 
 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
   OS << Indent << getUID(BasicBlock) << " [label =\n";
   bumpIndent(1);
   OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\"";
   bumpIndent(1);
   for (const VPRecipeBase &Recipe : *BasicBlock)
     Recipe.print(OS, Indent);
+
+  // Dump the condition bit.
+  const VPValue *CBV = BasicBlock->getCondBit();
+  if (CBV) {
+    OS << " +\n" << Indent << " \"CondBit: ";
+    if (const VPInstruction *CBI = dyn_cast<VPInstruction>(CBV)) {
+      CBI->printAsOperand(OS);
+      OS << " (" << DOT::EscapeString(CBI->getParent()->getName()) << ")\\l\"";
+    } else
+      CBV->printAsOperand(OS);
+  }
+
   bumpIndent(-2);
   OS << "\n" << Indent << "]\n";
   dumpEdges(BasicBlock);
 }
 
 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
   OS << Indent << "subgraph " << getUID(Region) << " {\n";
   bumpIndent(1);

lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

public:
   PlainCFGBuilder(Loop *Lp, LoopInfo *LI, VPlan &P)
       : TheLoop(Lp), LI(LI), Plan(P) {}
 
   // Build the plain CFG and return its Top Region.
   VPRegionBlock *buildPlainCFG();
 };
 } // anonymous namespace
 
-// Return true if \p Inst is an incoming Instruction to be ignored in the VPlan
-// representation.
-static bool isInstructionToIgnore(Instruction *Inst) {
-  return isa<BranchInst>(Inst);
-}
-
 // Set predecessors of \p VPBB in the same order as they are in \p BB. \p VPBB
 // must have no predecessors.
 void PlainCFGBuilder::setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB) {
   SmallVector<VPBlockBase *, 8> VPBBPreds;
   // Collect VPBB predecessors.
   for (BasicBlock *Pred : predecessors(BB))
     VPBBPreds.push_back(getOrCreateVPBB(Pred));
 

 // Create new VPInstructions in a VPBasicBlock, given its BasicBlock
 // counterpart. This function must be invoked in RPO so that the operands of a
 // VPInstruction in \p BB have been visited before (except for Phi nodes).
 void PlainCFGBuilder::createVPInstructionsForVPBB(VPBasicBlock *VPBB,
                                                   BasicBlock *BB) {
   VPIRBuilder.setInsertPoint(VPBB);
   for (Instruction &InstRef : *BB) {
     Instruction *Inst = &InstRef;
-    if (isInstructionToIgnore(Inst))
-      continue;
 
-    // There should't be any VPValue for Inst at this point. Otherwise, we
+    // There shouldn't be any VPValue for Inst at this point. Otherwise, we
     // visited Inst when we shouldn't, breaking the RPO traversal order.
     assert(!IRDef2VPValue.count(Inst) &&
            "Instruction shouldn't have been visited.");
 
+    if (auto *Br = dyn_cast<BranchInst>(Inst)) {
+      // Branch instruction is not explicitly represented in VPlan but we need
+      // to represent its condition bit when it's conditional.
+      if (Br->isConditional())
+        getOrCreateVPOperand(Br->getCondition());
+
+      // Skip the rest of the Instruction processing for Branch instructions.
+      continue;
+    }
+
     VPInstruction *NewVPInst;
-    if (PHINode *Phi = dyn_cast<PHINode>(Inst)) {
+    if (auto *Phi = dyn_cast<PHINode>(Inst)) {
       // Phi node's operands may have not been visited at this point. We create
       // an empty VPInstruction that we will fix once the whole plain CFG has
       // been built.
       NewVPInst = cast<VPInstruction>(VPIRBuilder.createNaryOp(
           Inst->getOpcode(), {} /*No operands*/, Inst));
       PhisToFix.push_back(Phi);
     } else {
       // Translate LLVM-IR operands into VPValue operands and set them in the
if (NumSuccs == 1) {
       VPBasicBlock *SuccVPBB = getOrCreateVPBB(TI->getSuccessor(0));
       assert(SuccVPBB && "VPBB Successor not found.");
       VPBB->setOneSuccessor(SuccVPBB);
     } else if (NumSuccs == 2) {
       VPBasicBlock *SuccVPBB0 = getOrCreateVPBB(TI->getSuccessor(0));
       assert(SuccVPBB0 && "Successor 0 not found.");
       VPBasicBlock *SuccVPBB1 = getOrCreateVPBB(TI->getSuccessor(1));
       assert(SuccVPBB1 && "Successor 1 not found.");
-      VPBB->setTwoSuccessors(SuccVPBB0, SuccVPBB1);
+
+      // Get VPBB's condition bit.
+      assert(isa<BranchInst>(TI) && "Unsupported terminator!");
+      auto *Br = cast<BranchInst>(TI);
+      Value *BrCond = Br->getCondition();
+      // Look up the branch condition to get the corresponding VPValue
+      // representing the condition bit in VPlan (which may be in another VPBB).
+      assert(IRDef2VPValue.count(BrCond) &&
+             "Missing condition bit in IRDef2VPValue!");
+      VPValue *VPCondBit = IRDef2VPValue[BrCond];
+
+      // Link successors using condition bit.
+      VPBB->setTwoSuccessors(SuccVPBB0, SuccVPBB1, VPCondBit);
     } else
       llvm_unreachable("Number of successors not supported.");
 
     // Set VPBB predecessors in the same order as they are in the incoming BB.
     setVPBBPredsFromBB(VPBB, BB);
   }
 
   // 3. Process outermost loop exit. We created an empty VPBB for the loop

lib/Transforms/Vectorize/VPlanVerifier.cpp

 /// not specific for VPBasicBlocks or VPRegionBlocks.
 static void verifyBlocksInRegion(const VPRegionBlock *Region) {
   for (const VPBlockBase *VPB :
        make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
                   df_iterator<const VPBlockBase *>::end(Region->getExit()))) {
     // Check block's parent.
     assert(VPB->getParent() == Region && "VPBlockBase has wrong parent");
 
+    // Check block's condition bit.
+    if (VPB->getNumSuccessors() > 1)
+      assert(VPB->getCondBit() && "Missing condition bit!");
+    else
+      assert(!VPB->getCondBit() && "Unexpected condition bit!");
+
     // Check block's successors.
     const auto &Successors = VPB->getSuccessors();
     // There must be only one instance of a successor in block's successor list.
     // TODO: This won't work for switch statements.
     assert(!hasDuplicates(Successors) &&
            "Multiple instances of the same successor.");
 
     for (const VPBlockBase *Succ : Successors) {

unittests/Transforms/Vectorize/VPlanHCFGTest.cpp

TEST_F(VPlanHCFGTest, testBuildHCFGInnerLoop) {
 
   SMDiagnostic Err;
   std::unique_ptr<Module> M = parseAssemblyString(ModuleString, Err, Ctx);
 
   Function *F = M->getFunction("f");
   BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
   auto Plan = doBuildPlan(LoopHeader);
 
-  VPBlockBase *Entry = Plan->getEntry()->getEntryBasicBlock();
+  VPBasicBlock *Entry = Plan->getEntry()->getEntryBasicBlock();
   EXPECT_NE(nullptr, Entry->getSingleSuccessor());
   EXPECT_EQ(0u, Entry->getNumPredecessors());
   EXPECT_EQ(1u, Entry->getNumSuccessors());
+  EXPECT_EQ(nullptr, Entry->getCondBit());
 
   VPBasicBlock *VecBB = Entry->getSingleSuccessor()->getEntryBasicBlock();
   EXPECT_EQ(7u, VecBB->size());
   EXPECT_EQ(2u, VecBB->getNumPredecessors());
   EXPECT_EQ(2u, VecBB->getNumSuccessors());
 
   auto Iter = VecBB->begin();
   VPInstruction *Phi = dyn_cast<VPInstruction>(&*Iter++);
TEST_F(VPlanHCFGTest, testBuildHCFGInnerLoop) {
   EXPECT_EQ(Instruction::Add, IndvarAdd->getOpcode());
   EXPECT_EQ(2u, IndvarAdd->getNumOperands());
   EXPECT_EQ(Phi, IndvarAdd->getOperand(0));
 
   VPInstruction *ICmp = dyn_cast<VPInstruction>(&*Iter++);
   EXPECT_EQ(Instruction::ICmp, ICmp->getOpcode());
   EXPECT_EQ(2u, ICmp->getNumOperands());
   EXPECT_EQ(IndvarAdd, ICmp->getOperand(0));
+  EXPECT_EQ(VecBB->getCondBit(), ICmp);
 
   LoopVectorizationLegality::InductionList Inductions;
   SmallPtrSet<Instruction *, 1> DeadInstructions;
   VPlanHCFGTransforms::VPInstructionsToVPRecipes(Plan, &Inductions,
                                                  DeadInstructions);
 }
 
 TEST_F(VPlanHCFGTest, testVPInstructionToVPRecipesInner) {