BreakCriticalEdges: Update PostDominatorTree

[kuhar]

Looks OK.

lib/Transforms/Scalar/LinearizeCFG.cpp

2607

Old comment?

[arsenm]

lib/Transforms/Scalar/LinearizeCFG.cpp

2607

This pass doesn't even exist upstream yet, so this shouldn't be in the patch at all

[arsenm]

r354673

include/llvm/Analysis/PostDominators.h

 class Function;
 class raw_ostream;
 
 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
 /// compute the post-dominator tree.
 class PostDominatorTree : public PostDomTreeBase<BasicBlock> {
 public:
   using Base = PostDomTreeBase<BasicBlock>;
+  PostDominatorTree() = default;
+  explicit PostDominatorTree(Function &F) { recalculate(F); }
 
   /// Handle invalidation explicitly.
   bool invalidate(Function &F, const PreservedAnalyses &PA,
                   FunctionAnalysisManager::Invalidator &);
 };
 
 /// \brief Analysis pass which computes a \c PostDominatorTree.
 class PostDominatorTreeAnalysis

include/llvm/Transforms/Utils/BasicBlockUtils.h

 class BranchProbabilityInfo;
 class DeferredDominance;
 class DominatorTree;
 class Function;
 class Instruction;
 class LoopInfo;
 class MDNode;
 class MemoryDependenceResults;
+class PostDominatorTree;
 class ReturnInst;
 class TargetLibraryInfo;
 class Value;
 
 /// Delete the specified block, which must have no predecessors.
 void DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT = nullptr);
 
 /// We know that BB has one predecessor. If there are any single-entry PHI nodes

 void ReplaceInstWithInst(Instruction *From, Instruction *To);
 
 /// Option class for critical edge splitting.
 ///
 /// This provides a builder interface for overriding the default options used
 /// during critical edge splitting.
 struct CriticalEdgeSplittingOptions {
   DominatorTree *DT;
+  PostDominatorTree *PDT;
   LoopInfo *LI;
   bool MergeIdenticalEdges = false;
   bool DontDeleteUselessPHIs = false;
   bool PreserveLCSSA = false;
 
   CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr,
-                               LoopInfo *LI = nullptr)
-      : DT(DT), LI(LI) {}
+                               LoopInfo *LI = nullptr,
+                               PostDominatorTree *PDT = nullptr)
+    : DT(DT), PDT(PDT), LI(LI) {}
 
   CriticalEdgeSplittingOptions &setMergeIdenticalEdges() {
     MergeIdenticalEdges = true;
     return *this;
   }
 
   CriticalEdgeSplittingOptions &setDontDeleteUselessPHIs() {
     DontDeleteUselessPHIs = true;

lib/Transforms/Scalar/LinearizeCFG.cpp

if (hasOnlyUniformBranches(R, *DA)) {
 
       return false;
     }
 #endif
   }
 
   SmallVector<BasicBlock *, 8> OrderedUnstructuredBlocks;
 
   // FIXME: PDT update
-  CriticalEdgeSplittingOptions CESO(DT);
+  CriticalEdgeSplittingOptions CESO(DT, nullptr, PDT);
   SplitAllCriticalEdges(*Func, CESO);
 
   //DenseSet<BasicBlock *> UnstructuredBlocks;
   //SetVector<BasicBlock *> UnstructuredBlocks;
   if (LinearizeWholeFunction) {
     // Process the entire function.
     for (BasicBlock *BB : ReversePostOrderTraversal<Function *>(Func)) {
       OrderedUnstructuredBlocks.push_back(BB);

lib/Transforms/Utils/BreakCriticalEdges.cpp

 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
struct BreakCriticalEdges : public FunctionPass {
     static char ID; // Pass identification, replacement for typeid
     BreakCriticalEdges() : FunctionPass(ID) {
       initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override {
       auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
       auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
+
+      auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
+      auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
+
       auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
       auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
       unsigned N =
-          SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI));
+        SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI, PDT));
       NumBroken += N;
       return N > 0;
     }
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addPreserved<DominatorTreeWrapperPass>();
       AU.addPreserved<LoopInfoWrapperPass>();
 
for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
 
       // We found another edge to DestBB, go to NewBB instead.
       TI->setSuccessor(i, NewBB);
     }
   }
 
   // If we have nothing to update, just return.
   auto *DT = Options.DT;
+  auto *PDT = Options.PDT;
   auto *LI = Options.LI;
-  if (!DT && !LI)
+  if (!DT && !PDT && !LI)
     return NewBB;
 
-  if (DT) {
+  if (DT || PDT) {
     // Update the DominatorTree.
     //       ---> NewBB -----\
     //      /                 V
     //  TIBB -------\\------> DestBB
     //
     // First, inform the DT about the new path from TIBB to DestBB via NewBB,
     // then delete the old edge from TIBB to DestBB. By doing this in that order
     // DestBB stays reachable in the DT the whole time and its subtree doesn't
     // get disconnected.
     SmallVector<DominatorTree::UpdateType, 3> Updates;
     Updates.push_back({DominatorTree::Insert, TIBB, NewBB});
     Updates.push_back({DominatorTree::Insert, NewBB, DestBB});
     if (llvm::find(successors(TIBB), DestBB) == succ_end(TIBB))
       Updates.push_back({DominatorTree::Delete, TIBB, DestBB});
 
+    if (DT)
       DT->applyUpdates(Updates);
+    if (PDT)
+      PDT->applyUpdates(Updates);
   }
 
   // Update LoopInfo if it is around.
   if (LI) {
     if (Loop *TIL = LI->getLoopFor(TIBB)) {
       // If one or the other blocks were not in a loop, the new block is not
       // either, and thus LI doesn't need to be updated.
       if (Loop *DestLoop = LI->getLoopFor(DestBB)) {

unittests/Transforms/Utils/BasicBlockUtils.cpp

 //===- BasicBlockUtils.cpp - Unit tests for BasicBlockUtils ---------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
TEST(BasicBlockUtils, SplitBlockPredecessors) {
   auto *F = M->getFunction("basic_func");
   DominatorTree DT(*F);
 
   // Make sure the dominator tree is properly updated if calling this on the
   // entry block.
   SplitBlockPredecessors(&F->getEntryBlock(), {}, "split.entry", &DT);
   EXPECT_TRUE(DT.verify());
 }
+
+TEST(BasicBlockUtils, SplitCriticalEdge) {
+  LLVMContext C;
+
+  std::unique_ptr<Module> M = parseIR(
+    C,
+    "define void @crit_edge(i1 %cond0, i1 %cond1) {\n"
+    "entry:\n"
+    "  br i1 %cond0, label %bb0, label %bb1\n"
+    "bb0:\n"
+    "  br label %bb1\n"
+    "bb1:\n"
+    "  br label %bb2\n"
+    "bb2:\n"
+    "  ret void\n"
+    "}\n"
+    "\n"
+    );
+
+  auto *F = M->getFunction("crit_edge");
+  DominatorTree DT(*F);
+  PostDominatorTree PDT(*F);
+
+  CriticalEdgeSplittingOptions CESO(&DT, nullptr, &PDT);
+  EXPECT_EQ(1u, SplitAllCriticalEdges(*F, CESO));
+  EXPECT_TRUE(DT.verify());
+  EXPECT_TRUE(PDT.verify());
+}