[VPlan] Introduce simplifyPlainCFG step in H-CFG builder.

[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 plain CFG simplification step during H-CFG
construction. This simplification is aimed at preparing the CFG to
introduce VPLoopRegions in the H-CFG (subsequent patch, working on it).
It consists of splitting some VPBasicBlocks that otherwise would belong to
more than one region.

[dcaballe]

Rebasing this patch on top of D49032

[fhahn]

lib/Transforms/Vectorize/VPlan.cpp

609

nit: no braces here

lib/Transforms/Vectorize/VPlan.h

524

You should be able to use *PredIt = New; here

1472

nit: maybe make it clear that the block is split at the bottom (no instructions are moved in the split block)

lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

328

nit: Split the pre-header VPBasicBlocks of \p VPLp and all it nested VPLoops, if it meets one of the following conditions: would be slightly more compact.

353

nit: Split the exit VPBasicBlocks of \p VPLp and all it nested VPLoops, if it meets one of the following conditions: is slightly more compact.

[fhahn]

lib/Transforms/Vectorize/VPlan.cpp

618

We should probably make sure we can use incremental DT updates via DeferredDominance and/or the DomTreeUpdater currently being developed.

[fhahn]

lib/Transforms/Vectorize/VPlanHCFGBuilder.h

57

It might be worth to mentioning that this is mostly canonicalization to make future transformations easier. And briefly describe the canonical form (not sure where the best place for that would be)

[fhahn]

Diego, are you still planning to land this patch?

[dcaballe]

Hi Florian,

We are currently defining the next set of patches to be open sourced. Let me mark this one as 'plan changes' for now since I don't know yet if it's going to be needed immediately or we would have to add significant changes to it.

Thanks,
Diego

[dcaballe]

Not needed for now

lib/Transforms/Vectorize/VPlan.h

 class InnerLoopVectorizer;
 class InterleaveGroup;
 class LoopInfo;
 template <class N, class M> class LoopInfoBase;
 class raw_ostream;
 class Value;
 class VPBasicBlock;
 class VPBlockBase;
+class VPDominatorTree;
 class VPLoop;
 typedef LoopInfoBase<VPBlockBase, VPLoop> VPLoopInfo;
 class VPRegionBlock;
 class VPlan;
 
 /// A range of powers-of-2 vectorization factors with fixed start and
 /// adjustable end. The range includes start and excludes end, e.g.,:
 /// [1, 9) = {1, 2, 4, 8}
public:
   /// This VPBlockBase must have no predecessors. This VPBlockBase is not added
   /// as successor of any VPBasicBlock in \p NewPreds.
   void setPredecessors(ArrayRef<VPBlockBase *> NewPreds) {
     assert(Predecessors.empty() && "Block predecessors already set.");
     for (auto *Pred : NewPreds)
       appendPredecessor(Pred);
   }
 
+  // Replace \p Old predecessor block with \p New block. If \p Old is a
+  // predecessor multiple times, only the first instance is replaced.
+  void replacePredecessor(VPBlockBase *Old, VPBlockBase *New) {
+    auto PredIt = std::find(Predecessors.begin(), Predecessors.end(), Old);
+    assert(PredIt != Predecessors.end() && "Predecessor not found!");
+    Predecessors[PredIt - Predecessors.begin()] = New;
+  }
+
   /// The method which generates the output IR that correspond to this
   /// VPBlockBase, thereby "executing" the VPlan.
   virtual void execute(struct VPTransformState *State) = 0;
 
   /// Delete all blocks reachable from a given VPBlockBase, inclusive.
   static void deleteCFG(VPBlockBase *Entry);
 
   void printAsOperand(raw_ostream &OS, bool PrintType) const {

 };
 
 //===----------------------------------------------------------------------===//
 // VPlan Utilities
 //===----------------------------------------------------------------------===//
 
 /// Class that provides utilities for VPBlockBases in VPlan.
 class VPBlockUtils {
+private:
+  /// Move successors and condition bit from VPBlockBase \p From to
+  /// VPBlockBase \p To.
+  static void moveSuccessors(VPBlockBase *From, VPBlockBase *To) {
+    auto &Successors = From->getSuccessors();
+    for (auto &Succ : Successors) {
+      Succ->replacePredecessor(From, To);
+      To->appendSuccessor(Succ);
+    }
+
+    // Move condition bit from From to To.
+    To->setCondBit(From->getCondBit());
+    From->setCondBit(nullptr);
+
+    // Remove successors from From.
+    Successors.clear();
+  }
+
 public:
   VPBlockUtils() = delete;
 
   /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
   /// 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
+  /// has more than one successor, its condition 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());
+
+    // Move successors, set parent and connect NewBlock.
+    moveSuccessors(BlockPtr, NewBlock);
+    VPRegionBlock *ParentRegion = BlockPtr->getParent();
+    NewBlock->setParent(ParentRegion);
+    connectBlocks(BlockPtr, NewBlock);
+
+    // If BlockPtr is parent region's exit, set NewBlock as parent region's
+    // exit.
+    if (ParentRegion && ParentRegion->getExit() == BlockPtr)
+      ParentRegion->setExit(NewBlock);
   }
 
   /// 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 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.
public:
 
   /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
   /// from the successors of \p From and \p From from the predecessors of \p To.
   static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
     assert(To && "Successor to disconnect is null.");
     From->removeSuccessor(To);
     To->removePredecessor(From);
   }
+
+  /// Split \p Block by turning Block->Successors into Block->NewSuccessor->
+  /// Successors and updates VPLoopInfo, DomTree and PostDomTree accordingly.
+  /// \return the new VPBasicBlock created as a result of the split.
+  static VPBasicBlock *splitBlock(VPBlockBase *Block, VPLoopInfo *VPLInfo,
+                                  VPDominatorTree &DomTree);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H

lib/Transforms/Vectorize/VPlan.cpp

void VPWidenMemoryInstructionRecipe::print(raw_ostream &O,
   O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
   if (User) {
     O << ", ";
     User->getOperand(0)->printAsOperand(O);
   }
   O << "\\l\"";
 }
 
+VPBasicBlock *VPBlockUtils::splitBlock(VPBlockBase *Block, VPLoopInfo *VPLInfo,
+                                       VPDominatorTree &DomTree) {
+  VPBasicBlock *NewBlock = new VPBasicBlock(Block->getName() + ".split");
+  insertBlockAfter(NewBlock, Block);
+
+  // 1. Add NewBlock to VPLoopInfo.
+  if (VPLoop *Loop = VPLInfo->getLoopFor(Block)) {
+    Loop->addBasicBlockToLoop(NewBlock, *VPLInfo);
+  }
+
+  // 2. Update domination information.
+  VPDomTreeNode *BlockDT = DomTree.getNode(Block);
+  SmallVector<VPDomTreeNode *, 2> BlockDTChildren(BlockDT->begin(),
+                                                  BlockDT->end());
+  // Block is NewBlock's idom.
+  VPDomTreeNode *NewBlockDT = DomTree.addNewBlock(NewBlock, Block /*IDom*/);
+
+  // NewBlock dominates all the other nodes dominated by Block.
+  for (VPDomTreeNode *Child : BlockDTChildren)
+    DomTree.changeImmediateDominator(Child, NewBlockDT);
+
+  return NewBlock;
+}
+
 using VPDomTree = DomTreeBase<VPBlockBase>;
 template void DomTreeBuilder::Calculate<VPDomTree>(VPDomTree &DT);

lib/Transforms/Vectorize/VPlanHCFGBuilder.h

 
 #include "VPlan.h"
 #include "VPlanDominatorTree.h"
 #include "VPlanVerifier.h"
 
 namespace llvm {
 
 class Loop;
+class VPLoop;
 
 /// Main class to build the VPlan H-CFG for an incoming IR.
 class VPlanHCFGBuilder {
 private:
   // The outermost loop of the input loop nest considered for vectorization.
   Loop *TheLoop;
 
   // Loop Info analysis.
   LoopInfo *LI;
 
   // The VPlan that will contain the H-CFG we are building.
   VPlan &Plan;
 
   // VPlan verifier utility.
   VPlanVerifier Verifier;
 
   // Dominator analysis for VPlan plain CFG to be used in the
   // construction of the H-CFG. This analysis is no longer valid once regions
   // are introduced.
   VPDominatorTree VPDomTree;
 
+  // Methods to simplify the plain CFG.
+  void simplifyPlainCFG();
+  void splitLoopsPreheader(VPLoop *VPLp);
+  void splitLoopsExit(VPLoop *VPLp);
+
 public:
   VPlanHCFGBuilder(Loop *Lp, LoopInfo *LI, VPlan &P)
       : TheLoop(Lp), LI(LI), Plan(P) {}
 
   /// Build plain CFG for TheLoop. Return a new VPRegionBlock (TopRegion)
   /// enclosing the plain CFG.
   ///
   /// This interface is mainly used for unittests. To build the proper VPlan

lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

VPRegionBlock *PlainCFGBuilder::buildPlainCFG() {
 
   // 5. Final Top Region setup. Set outermost loop pre-header and single exit as
   // Top Region entry and exit.
   TopRegion->setEntry(PreheaderVPBB);
   TopRegion->setExit(LoopExitVPBB);
   return TopRegion;
 }
 
+// Split the pre-header VPBasicBlocks of \p VPLp and all it nested VPLoops. A
+// pre-header is split if it meets one of the following conditions:
+//   1. It's the loop header of another loop.
+//   2. It has multiple predecessors (it's a potential exit of another region).
+//
+// TODO: This function is currently splitting VPBBs without taking into account
+// VPInstructions within them. In other words, VPInstructions are kept in the
+// original VPBB. Eventually, we may want to do a smarter splitting and
+// consciously move those VPInstructions that should better be in the VPBB
+// resulting from the split.
+void VPlanHCFGBuilder::splitLoopsPreheader(VPLoop *VPLp) {
+  VPLoopInfo *VPLInfo = Plan.getVPLoopInfo();
+  VPBlockBase *PH = VPLp->getLoopPreheader();
+  assert(PH && PH->getNumSuccessors() == 1 &&
+         "Expected loop pre-header with a single successor!");
+
+  // Split loop PH.
+  if (PH->getNumPredecessors() > 1 /*2*/ || VPLInfo->isLoopHeader(PH) /*1*/)
+    VPBlockUtils::splitBlock(PH, VPLInfo, VPDomTree);
+
+  // Recurse inside nested loops.
+  for (auto *VPSubLp : VPLp->getSubLoops())
+    splitLoopsPreheader(VPSubLp);
+}
+
+// Split the exit VPBasicBlocks of \p VPLp and all it nested VPLoops. An
+// exit is split if it meets one of the following conditions:
+//   1. It's the loop pre-header of another loop.
+//   2. It has multiple successors (it's a potential entry of another region).
+//      This case covers exits that are also loop latches of another loops.
+//
+// TODO: This function is currently splitting VPBBs without taking into account
+// VPInstructions within them. In other words, VPInstructions are kept in the
+// original VPBB. Eventually, we may want to do a smarter splitting and
+// consciously move those VPInstructions that should better be in the VPBB
+// resulting from the split.
+void VPlanHCFGBuilder::splitLoopsExit(VPLoop *VPLp) {
+  VPLoopInfo *VPLInfo = Plan.getVPLoopInfo();
+  VPBlockBase *Exit = VPLp->getUniqueExitBlock();
+  assert(Exit && "Only single-exit loops expected!");
+
+  // Split loop exit.
+  VPBlockBase *PotentialH = Exit->getSingleSuccessor();
+  if (!PotentialH /*2*/ || VPLInfo->isLoopHeader(PotentialH) /*1*/)
+    VPBlockUtils::splitBlock(Exit, VPLInfo, VPDomTree);
+
+  // Recurse inside nested loops.
+  for (auto *VPSubLp : VPLp->getSubLoops())
+    splitLoopsExit(VPSubLp);
+}
+
+// Main function that simplifies the plain CFG to be able to introduce
+// VPLoopRegions and non-loop VPRegionBlocks during the hierarchical CFG
+// construction. It mainly splits VPBasicBlocks that are suitable for
+// simultaneously being entry and exit blocks of two regions.
+void VPlanHCFGBuilder::simplifyPlainCFG() {
+  assert(isa<VPRegionBlock>(Plan.getEntry()) &&
+         "VPlan entry is not a VPRegionBlock");
+  VPLoopInfo *VPLInfo = Plan.getVPLoopInfo();
+
+  assert(std::distance(VPLInfo->begin(), VPLInfo->end()) == 1 &&
+         "Expected only 1 top-level loop.");
+  VPLoop *TopLoop = *VPLInfo->begin();
+
+  splitLoopsPreheader(TopLoop);
+  splitLoopsExit(TopLoop);
+}
+
 VPRegionBlock *VPlanHCFGBuilder::buildPlainCFG() {
   PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
   return PCFGBuilder.buildPlainCFG();
 }
 
 // Public interface to build a H-CFG.
 void VPlanHCFGBuilder::buildHierarchicalCFG() {
   // Build Top Region enclosing the plain CFG and set it as VPlan entry.
LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n";
              VPDomTree.print(dbgs()));
 
   // Compute VPLInfo and keep it in Plan.
   VPLoopInfo *VPLInfo = new VPLoopInfo();
   VPLInfo->analyze(VPDomTree);
   Plan.setVPLoopInfo(VPLInfo);
   LLVM_DEBUG(dbgs() << "VPLoop Info After buildPlainCFG:\n";
              VPLInfo->print(dbgs()));
+
+  // Prepare/simplify CFG for hierarchical CFG construction.
+  simplifyPlainCFG();
+
+  LLVM_DEBUG(Plan.setName("HCFGBuilder: After simplifyPlainCFG\n");
+             dbgs() << Plan);
+  LLVM_DEBUG(dbgs() << "Dominator Tree After simplifyPlainCFG\n";
+             VPDomTree.print(dbgs()));
+  LLVM_DEBUG(dbgs() << "VPLoop Info After simplifyPlainCFG:\n";
+             VPLInfo->print(dbgs()));
+
+  Verifier.verifyHierarchicalCFG(TopRegion);
 }

unittests/Transforms/Vectorize/VPlanHCFGTest.cpp

 #include "VPlanTestBase.h"
 #include "gtest/gtest.h"
 
 namespace llvm {
 namespace {
 
 class VPlanHCFGTest : public VPlanTestBase {};
 
-TEST_F(VPlanHCFGTest, testBuildHCFGInnerLoop) {
+TEST_F(VPlanHCFGTest, testBuildPlainCFGInnerLoop) {
   const char *ModuleString =
       "define void @f(i32* %A, i64 %N) {\n"
       "entry:\n"
       "  br label %for.body\n"
       "for.body:\n"
       "  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]\n"
       "  %arr.idx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv\n"
       "  %l1 = load i32, i32* %arr.idx, align 4\n"
       "  %res = add i32 %l1, 10\n"
       "  store i32 %res, i32* %arr.idx, align 4\n"
       "  %indvars.iv.next = add i64 %indvars.iv, 1\n"
       "  %exitcond = icmp ne i64 %indvars.iv.next, %N\n"
       "  br i1 %exitcond, label %for.body, label %for.end\n"
       "for.end:\n"
       "  ret void\n"
       "}\n";
 
   Module &M = parseModule(ModuleString);
 
   Function *F = M.getFunction("f");
   BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
-  auto Plan = buildHCFG(LoopHeader);
+  auto Plan = buildPlainCFG(LoopHeader);
 
   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();
TEST_F(VPlanHCFGTest, testVPInstructionToVPRecipesInner) {
   auto *Store = dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++);
   EXPECT_NE(nullptr, Store);
 
   auto *LastWiden = dyn_cast<VPWidenRecipe>(&*Iter++);
   EXPECT_NE(nullptr, LastWiden);
   EXPECT_EQ(VecBB->end(), Iter);
 }
 
+TEST_F(VPlanHCFGTest, testSimplifyPlainCFGOuterLoop) {
+  const char *ModuleString =
+      "define void @outer(i32* %a, i32* %b) {\n"
+      "entry:\n"
+      "  br label %outer.body\n"
+      "outer.body:\n" // Outer loop body + inner loop ph.
+      "  %iv35 = phi i64 [ 0, %entry ], [ %iv.next36, %outer.inc ]\n"
+      "  %0 = mul nsw i64 %iv35, 64\n"
+      "  br label %inner.body\n"
+      "inner.body:\n"
+      "  %iv = phi i64 [ 0, %outer.body ], [ %iv.next, %inner.body ]\n"
+      "  %1 = add nsw i64 %iv, %0\n"
+      "  %idx = getelementptr inbounds i32, i32* %b, i64 %1\n"
+      "  %2 = load i32, i32* %idx, align 4\n"
+      "  %idx12 = getelementptr inbounds i32, i32* %a, i64 %1\n"
+      "  store i32 %2, i32* %idx12, align 4\n"
+      "  %iv.next = add nuw nsw i64 %iv, 1\n"
+      "  %exitcond = icmp eq i64 %iv.next, 64\n"
+      "  br i1 %exitcond, label %outer.inc, label %inner.body\n"
+      "outer.inc:\n" // Outer loop latch + inner loop exit.
+      "  %iv.next36 = add nuw nsw i64 %iv35, 1\n"
+      "  %exitcond39 = icmp eq i64 %iv.next36, 64\n"
+      "  br i1 %exitcond39, label %for.end15, label %outer.body\n"
+      "for.end15:\n"
+      "  ret void\n"
+      "}\n";
+
+  Module &M = parseModule(ModuleString);
+
+  Function *F = M.getFunction("outer");
+  BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
+  auto Plan = buildHCFG(LoopHeader);
+
+  VPBasicBlock *OuterPH = Plan->getEntry()->getEntryBasicBlock();
+  EXPECT_NE(OuterPH, nullptr);
+  EXPECT_EQ(OuterPH->getCondBit(), nullptr);
+
+  VPBlockBase *OuterBody = OuterPH->getSingleSuccessor();
+  EXPECT_NE(OuterBody, nullptr);
+  EXPECT_EQ(OuterBody->getCondBit(), nullptr);
+
+  // Simplify plain CFG should have introduced an independent inner loop PH.
+  VPBasicBlock *InnerPH = OuterBody->getSingleSuccessor()->getEntryBasicBlock();
+  EXPECT_NE(InnerPH, nullptr);
+  EXPECT_EQ(InnerPH->getCondBit(), nullptr);
+
+  VPBlockBase *InnerBody = InnerPH->getSingleSuccessor();
+  EXPECT_NE(InnerBody, nullptr);
+  EXPECT_NE(InnerBody->getCondBit(), nullptr);
+
+  VPBlockBase *InnerExit = InnerBody->getSuccessors()[0];
+  EXPECT_NE(InnerExit, nullptr);
+  EXPECT_EQ(InnerExit->getCondBit(), nullptr);
+
+  // Simplify plain CFG should have introduced an independent inner loop exit.
+  VPBlockBase *OuterLatch = InnerExit->getSingleHierarchicalSuccessor();
+  EXPECT_NE(OuterLatch, nullptr);
+  EXPECT_NE(OuterLatch->getCondBit(), nullptr);
+
+  VPBlockBase *OuterExit = OuterLatch->getSuccessors()[0];
+  EXPECT_NE(OuterExit, nullptr);
+  EXPECT_EQ(OuterExit->getCondBit(), nullptr);
+}
 } // namespace
 } // namespace llvm