//
void ReplaceInstWithInst(Instruction *From, Instruction *To);
+/// \brief Option class for critical edge splitting.
+///
+/// This provides a builder interface for overriding the default options used
+/// during critical edge splitting.
+struct CriticalEdgeSplittingOptions {
+ AliasAnalysis *AA;
+ DominatorTree *DT;
+ LoopInfo *LI;
+ bool MergeIdenticalEdges;
+ bool DontDeleteUselessPHIs;
+ bool SplitLandingPads;
+ bool PreserveLCSSA;
+
+ CriticalEdgeSplittingOptions()
+ : AA(nullptr), DT(nullptr), LI(nullptr), MergeIdenticalEdges(false),
+ DontDeleteUselessPHIs(false), SplitLandingPads(false),
+ PreserveLCSSA(false) {}
+
+ /// \brief Basic case of setting up all the analysis.
+ CriticalEdgeSplittingOptions(AliasAnalysis *AA, DominatorTree *DT = nullptr,
+ LoopInfo *LI = nullptr)
+ : AA(AA), DT(DT), LI(LI), MergeIdenticalEdges(false),
+ DontDeleteUselessPHIs(false), SplitLandingPads(false),
+ PreserveLCSSA(false) {}
+
+ /// \brief A common pattern is to preserve the dominator tree and loop
+ /// info but not care about AA.
+ CriticalEdgeSplittingOptions(DominatorTree *DT, LoopInfo *LI)
+ : AA(nullptr), DT(DT), LI(LI), MergeIdenticalEdges(false),
+ DontDeleteUselessPHIs(false), SplitLandingPads(false),
+ PreserveLCSSA(false) {}
+
+ CriticalEdgeSplittingOptions &setMergeIdenticalEdges() {
+ MergeIdenticalEdges = true;
+ return *this;
+ }
+
+ CriticalEdgeSplittingOptions &setDontDeleteUselessPHIs() {
+ DontDeleteUselessPHIs = true;
+ return *this;
+ }
+
+ CriticalEdgeSplittingOptions &setSplitLandingPads() {
+ SplitLandingPads = true;
+ return *this;
+ }
+
+ CriticalEdgeSplittingOptions &setPreserveLCSSA() {
+ PreserveLCSSA = true;
+ return *this;
+ }
+};
+
/// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
-/// split the critical edge. This will update DominatorTree and
-/// DominatorFrontier information if it is available, thus calling this pass
-/// will not invalidate either of them. This returns the new block if the edge
-/// was split, null otherwise.
+/// split the critical edge. This will update the analyses passed in through
+/// the option struct. This returns the new block if the edge was split, null
+/// otherwise.
///
-/// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the
-/// specified successor will be merged into the same critical edge block.
-/// This is most commonly interesting with switch instructions, which may
-/// have many edges to any one destination. This ensures that all edges to that
-/// dest go to one block instead of each going to a different block, but isn't
-/// the standard definition of a "critical edge".
+/// If MergeIdenticalEdges in the options struct is true (not the default),
+/// *all* edges from TI to the specified successor will be merged into the same
+/// critical edge block. This is most commonly interesting with switch
+/// instructions, which may have many edges to any one destination. This
+/// ensures that all edges to that dest go to one block instead of each going
+/// to a different block, but isn't the standard definition of a "critical
+/// edge".
///
/// It is invalid to call this function on a critical edge that starts at an
/// IndirectBrInst. Splitting these edges will almost always create an invalid
/// to.
///
BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
- Pass *P = nullptr,
- bool MergeIdenticalEdges = false,
- bool DontDeleteUselessPHIs = false,
- bool SplitLandingPads = false);
-
-inline BasicBlock *SplitCriticalEdge(BasicBlock *BB, succ_iterator SI,
- Pass *P = nullptr) {
- return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), P);
+ const CriticalEdgeSplittingOptions &Options =
+ CriticalEdgeSplittingOptions());
+
+inline BasicBlock *
+SplitCriticalEdge(BasicBlock *BB, succ_iterator SI,
+ const CriticalEdgeSplittingOptions &Options =
+ CriticalEdgeSplittingOptions()) {
+ return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(),
+ Options);
}
/// SplitCriticalEdge - If the edge from *PI to BB is not critical, return
/// function. If P is specified, it updates the analyses
/// described above.
inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI,
- Pass *P = nullptr) {
+ const CriticalEdgeSplittingOptions &Options =
+ CriticalEdgeSplittingOptions()) {
bool MadeChange = false;
TerminatorInst *TI = (*PI)->getTerminator();
for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
if (TI->getSuccessor(i) == Succ)
- MadeChange |= !!SplitCriticalEdge(TI, i, P);
+ MadeChange |= !!SplitCriticalEdge(TI, i, Options);
return MadeChange;
}
/// SplitCriticalEdge - If an edge from Src to Dst is critical, split the edge
/// and return true, otherwise return false. This method requires that there be
-/// an edge between the two blocks. If P is specified, it updates the analyses
-/// described above.
-inline BasicBlock *SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst,
- Pass *P = nullptr,
- bool MergeIdenticalEdges = false,
- bool DontDeleteUselessPHIs = false) {
+/// an edge between the two blocks. It updates the analyses
+/// passed in the options struct
+inline BasicBlock *
+SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst,
+ const CriticalEdgeSplittingOptions &Options =
+ CriticalEdgeSplittingOptions()) {
TerminatorInst *TI = Src->getTerminator();
unsigned i = 0;
while (1) {
assert(i != TI->getNumSuccessors() && "Edge doesn't exist!");
if (TI->getSuccessor(i) == Dst)
- return SplitCriticalEdge(TI, i, P, MergeIdenticalEdges,
- DontDeleteUselessPHIs);
+ return SplitCriticalEdge(TI, i, Options);
++i;
}
}
// SplitAllCriticalEdges - Loop over all of the edges in the CFG,
-// breaking critical edges as they are found. Pass P must not be NULL.
+// breaking critical edges as they are found.
// Returns the number of broken edges.
-unsigned SplitAllCriticalEdges(Function &F, Pass *P);
+unsigned SplitAllCriticalEdges(Function &F,
+ const CriticalEdgeSplittingOptions &Options =
+ CriticalEdgeSplittingOptions());
/// SplitEdge - Split the edge connecting specified block. Pass P must
/// not be NULL.
///
/// This is required for correctness, so it must be done at -O0.
///
-static void SplitCriticalSideEffectEdges(Function &Fn, Pass *SDISel) {
+static void SplitCriticalSideEffectEdges(Function &Fn, AliasAnalysis *AA) {
// Loop for blocks with phi nodes.
for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
PHINode *PN = dyn_cast<PHINode>(BB->begin());
continue;
// Okay, we have to split this edge.
- SplitCriticalEdge(Pred->getTerminator(),
- GetSuccessorNumber(Pred, BB), SDISel, true);
+ SplitCriticalEdge(
+ Pred->getTerminator(), GetSuccessorNumber(Pred, BB),
+ CriticalEdgeSplittingOptions(AA).setMergeIdenticalEdges());
goto ReprocessBlock;
}
}
DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
- SplitCriticalSideEffectEdges(const_cast<Function&>(Fn), this);
+ SplitCriticalSideEffectEdges(const_cast<Function&>(Fn), AA);
CurDAG->init(*MF);
FuncInfo->set(Fn, *MF, CurDAG);
if (F.getName().find(".module_ctor") != std::string::npos)
return false; // Should not instrument sanitizer init functions.
if (CoverageLevel >= 3)
- SplitAllCriticalEdges(F, this);
+ SplitAllCriticalEdges(F);
SmallVector<Instruction*, 8> IndirCalls;
SmallVector<BasicBlock*, 16> AllBlocks;
for (auto &BB : F) {
/// Split the critical edge connecting the given two blocks, and return
/// the block inserted to the critical edge.
BasicBlock *GVN::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
- BasicBlock *BB = SplitCriticalEdge(Pred, Succ, this);
+ BasicBlock *BB = SplitCriticalEdge(
+ Pred, Succ, CriticalEdgeSplittingOptions(getAliasAnalysis(), DT));
if (MD)
MD->invalidateCachedPredecessors();
return BB;
return false;
do {
std::pair<TerminatorInst*, unsigned> Edge = toSplit.pop_back_val();
- SplitCriticalEdge(Edge.first, Edge.second, this);
+ SplitCriticalEdge(Edge.first, Edge.second,
+ CriticalEdgeSplittingOptions(getAliasAnalysis(), DT));
} while (!toSplit.empty());
if (MD) MD->invalidateCachedPredecessors();
return true;
// Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and
// thus is not a preheader anymore.
// Split the edge to form a real preheader.
- BasicBlock *NewPH = SplitCriticalEdge(OrigPreheader, NewHeader, this);
+ BasicBlock *NewPH = SplitCriticalEdge(
+ OrigPreheader, NewHeader,
+ CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA());
NewPH->setName(NewHeader->getName() + ".lr.ph");
// Preserve canonical loop form, which means that 'Exit' should have only
if (!PredLoop || PredLoop->contains(Exit))
continue;
SplitLatchEdge |= L->getLoopLatch() == *PI;
- BasicBlock *ExitSplit = SplitCriticalEdge(*PI, Exit, this);
+ BasicBlock *ExitSplit = SplitCriticalEdge(
+ *PI, Exit, CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA());
ExitSplit->moveBefore(Exit);
}
assert(SplitLatchEdge &&
// Split the critical edge.
BasicBlock *NewBB = nullptr;
if (!Parent->isLandingPad()) {
- NewBB = SplitCriticalEdge(BB, Parent, P,
- /*MergeIdenticalEdges=*/true,
- /*DontDeleteUselessPhis=*/true);
+ NewBB = SplitCriticalEdge(BB, Parent,
+ CriticalEdgeSplittingOptions(&DT, &LI)
+ .setMergeIdenticalEdges()
+ .setDontDeleteUselessPHIs());
} else {
SmallVector<BasicBlock*, 2> NewBBs;
SplitLandingPadPredecessors(Parent, BB, "", "", NewBBs,
// If either edge is critical, split it. This helps preserve LoopSimplify
// form for enclosing loops.
- SplitCriticalEdge(BI, 0, this, false, false, true);
- SplitCriticalEdge(BI, 1, this, false, false, true);
+ auto Options = CriticalEdgeSplittingOptions(DT, LI)
+ .setPreserveLCSSA()
+ .setSplitLandingPads();
+ SplitCriticalEdge(BI, 0, Options);
+ SplitCriticalEdge(BI, 1, Options);
}
/// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable
BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) {
unsigned SuccNum = GetSuccessorNumber(BB, Succ);
- // If this is a critical edge, let SplitCriticalEdge do it.
- TerminatorInst *LatchTerm = BB->getTerminator();
- if (SplitCriticalEdge(LatchTerm, SuccNum, P))
- return LatchTerm->getSuccessor(SuccNum);
-
+ auto *AA = P->getAnalysisIfAvailable<AliasAnalysis>();
auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
+ bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID);
+ auto Options = CriticalEdgeSplittingOptions(AA, DT, LI);
+ if (PreserveLCSSA)
+ Options.setPreserveLCSSA();
+
+ // If this is a critical edge, let SplitCriticalEdge do it.
+ TerminatorInst *LatchTerm = BB->getTerminator();
+ if (SplitCriticalEdge(LatchTerm, SuccNum, Options))
+ return LatchTerm->getSuccessor(SuccNum);
// If the edge isn't critical, then BB has a single successor or Succ has a
// single pred. Split the block.
return SplitBlock(BB, BB->getTerminator(), DT, LI);
}
-unsigned llvm::SplitAllCriticalEdges(Function &F, Pass *P) {
+unsigned
+llvm::SplitAllCriticalEdges(Function &F,
+ const CriticalEdgeSplittingOptions &Options) {
unsigned NumBroken = 0;
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
TerminatorInst *TI = I->getTerminator();
if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
- if (SplitCriticalEdge(TI, i, P))
+ if (SplitCriticalEdge(TI, i, Options))
++NumBroken;
}
return NumBroken;
}
bool runOnFunction(Function &F) override {
- unsigned N = SplitAllCriticalEdges(F, this);
+ auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+ auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
+ auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
+ auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
+ unsigned N =
+ SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI));
NumBroken += N;
return N > 0;
}
/// to.
///
BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
- Pass *P, bool MergeIdenticalEdges,
- bool DontDeleteUselessPhis,
- bool SplitLandingPads) {
- if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return nullptr;
+ const CriticalEdgeSplittingOptions &Options) {
+ if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges))
+ return nullptr;
assert(!isa<IndirectBrInst>(TI) &&
"Cannot split critical edge from IndirectBrInst");
// If there are any other edges from TIBB to DestBB, update those to go
// through the split block, making those edges non-critical as well (and
// reducing the number of phi entries in the DestBB if relevant).
- if (MergeIdenticalEdges) {
+ if (Options.MergeIdenticalEdges) {
for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
if (TI->getSuccessor(i) != DestBB) continue;
// Remove an entry for TIBB from DestBB phi nodes.
- DestBB->removePredecessor(TIBB, DontDeleteUselessPhis);
+ DestBB->removePredecessor(TIBB, Options.DontDeleteUselessPHIs);
// We found another edge to DestBB, go to NewBB instead.
TI->setSuccessor(i, NewBB);
}
}
-
-
- // If we don't have a pass object, we can't update anything...
- if (!P) return NewBB;
-
-
- auto *AA = P->getAnalysisIfAvailable<AliasAnalysis>();
- DominatorTreeWrapperPass *DTWP =
- P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
- DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
- auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
- LoopInfo *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
- bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID);
-
// If we have nothing to update, just return.
+ auto *AA = Options.AA;
+ auto *DT = Options.DT;
+ auto *LI = Options.LI;
if (!DT && !LI)
return NewBB;
"Split point for loop exit is contained in loop!");
// Update LCSSA form in the newly created exit block.
- if (PreserveLCSSA) {
+ if (Options.PreserveLCSSA) {
createPHIsForSplitLoopExit(TIBB, NewBB, DestBB);
}
assert(!DestBB->isLandingPad() &&
"We don't split edges to landing pads!");
BasicBlock *NewExitBB = SplitBlockPredecessors(
- DestBB, LoopPreds, "split", AA, DT, LI, PreserveLCSSA);
- if (PreserveLCSSA)
+ DestBB, LoopPreds, "split", AA, DT, LI, Options.PreserveLCSSA);
+ if (Options.PreserveLCSSA)
createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
}
}
projects / oota-llvm.git / commitdiff