BreakCriticalEdges.cpp [plain text]
#define DEBUG_TYPE "break-crit-edges"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ProfileInfo.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/Type.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;
STATISTIC(NumBroken, "Number of blocks inserted");
namespace {
struct BreakCriticalEdges : public FunctionPass {
static char ID; BreakCriticalEdges() : FunctionPass(ID) {
initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry());
}
virtual bool runOnFunction(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addPreserved<DominatorTree>();
AU.addPreserved<LoopInfo>();
AU.addPreserved<ProfileInfo>();
AU.addPreservedID(LoopSimplifyID);
}
};
}
char BreakCriticalEdges::ID = 0;
INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges",
"Break critical edges in CFG", false, false)
char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID;
FunctionPass *llvm::createBreakCriticalEdgesPass() {
return new BreakCriticalEdges();
}
bool BreakCriticalEdges::runOnFunction(Function &F) {
bool Changed = false;
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, this)) {
++NumBroken;
Changed = true;
}
}
return Changed;
}
bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
bool AllowIdenticalEdges) {
assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
if (TI->getNumSuccessors() == 1) return false;
const BasicBlock *Dest = TI->getSuccessor(SuccNum);
const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest);
assert(I != E && "No preds, but we have an edge to the block?");
const BasicBlock *FirstPred = *I;
++I; if (!AllowIdenticalEdges)
return I != E;
while (I != E) {
const BasicBlock *P = *I;
if (P != FirstPred)
return true;
E = pred_end(P);
++I;
}
return false;
}
static void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds,
BasicBlock *SplitBB,
BasicBlock *DestBB) {
assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!");
for (BasicBlock::iterator I = DestBB->begin();
PHINode *PN = dyn_cast<PHINode>(I); ++I) {
unsigned Idx = PN->getBasicBlockIndex(SplitBB);
Value *V = PN->getIncomingValue(Idx);
if (const PHINode *VP = dyn_cast<PHINode>(V))
if (VP->getParent() == SplitBB)
continue;
PHINode *NewPN =
PHINode::Create(PN->getType(), Preds.size(), "split",
SplitBB->isLandingPad() ?
SplitBB->begin() : SplitBB->getTerminator());
for (unsigned i = 0, e = Preds.size(); i != e; ++i)
NewPN->addIncoming(V, Preds[i]);
PN->setIncomingValue(Idx, NewPN);
}
}
BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
Pass *P, bool MergeIdenticalEdges,
bool DontDeleteUselessPhis,
bool SplitLandingPads) {
if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0;
assert(!isa<IndirectBrInst>(TI) &&
"Cannot split critical edge from IndirectBrInst");
BasicBlock *TIBB = TI->getParent();
BasicBlock *DestBB = TI->getSuccessor(SuccNum);
if (DestBB->isLandingPad()) return 0;
BasicBlock *NewBB = BasicBlock::Create(TI->getContext(),
TIBB->getName() + "." + DestBB->getName() + "_crit_edge");
BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
NewBI->setDebugLoc(TI->getDebugLoc());
TI->setSuccessor(SuccNum, NewBB);
Function &F = *TIBB->getParent();
Function::iterator FBBI = TIBB;
F.getBasicBlockList().insert(++FBBI, NewBB);
{
unsigned BBIdx = 0;
for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
if (PN->getIncomingBlock(BBIdx) != TIBB)
BBIdx = PN->getBasicBlockIndex(TIBB);
PN->setIncomingBlock(BBIdx, NewBB);
}
}
if (MergeIdenticalEdges) {
for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
if (TI->getSuccessor(i) != DestBB) continue;
DestBB->removePredecessor(TIBB, DontDeleteUselessPhis);
TI->setSuccessor(i, NewBB);
}
}
if (P == 0) return NewBB;
DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>();
LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>();
ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>();
if (DT == 0 && LI == 0 && PI == 0)
return NewBB;
SmallVector<BasicBlock*, 8> OtherPreds;
if (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
if (PN->getIncomingBlock(i) != NewBB)
OtherPreds.push_back(PN->getIncomingBlock(i));
} else {
for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB);
I != E; ++I) {
BasicBlock *P = *I;
if (P != NewBB)
OtherPreds.push_back(P);
}
}
bool NewBBDominatesDestBB = true;
if (DT) {
DomTreeNode *TINode = DT->getNode(TIBB);
if (TINode) { DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB);
DomTreeNode *DestBBNode = 0;
if (!OtherPreds.empty()) {
DestBBNode = DT->getNode(DestBB);
while (!OtherPreds.empty() && NewBBDominatesDestBB) {
if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back()))
NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode);
OtherPreds.pop_back();
}
OtherPreds.clear();
}
if (NewBBDominatesDestBB) {
if (!DestBBNode) DestBBNode = DT->getNode(DestBB);
DT->changeImmediateDominator(DestBBNode, NewBBNode);
}
}
}
if (LI) {
if (Loop *TIL = LI->getLoopFor(TIBB)) {
if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
if (TIL == DestLoop) {
DestLoop->addBasicBlockToLoop(NewBB, LI->getBase());
} else if (TIL->contains(DestLoop)) {
TIL->addBasicBlockToLoop(NewBB, LI->getBase());
} else if (DestLoop->contains(TIL)) {
DestLoop->addBasicBlockToLoop(NewBB, LI->getBase());
} else {
assert(DestLoop->getHeader() == DestBB &&
"Should not create irreducible loops!");
if (Loop *P = DestLoop->getParentLoop())
P->addBasicBlockToLoop(NewBB, LI->getBase());
}
}
if (!TIL->contains(DestBB) &&
P->mustPreserveAnalysisID(LoopSimplifyID)) {
assert(!TIL->contains(NewBB) &&
"Split point for loop exit is contained in loop!");
if (P->mustPreserveAnalysisID(LCSSAID))
createPHIsForSplitLoopExit(TIBB, NewBB, DestBB);
SmallVector<BasicBlock *, 4> ExitBlocks;
TIL->getExitBlocks(ExitBlocks);
for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
SmallVector<BasicBlock *, 4> Preds;
bool HasPredOutsideOfLoop = false;
BasicBlock *Exit = ExitBlocks[i];
for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit);
I != E; ++I) {
BasicBlock *P = *I;
if (TIL->contains(P)) {
if (isa<IndirectBrInst>(P->getTerminator())) {
Preds.clear();
break;
}
Preds.push_back(P);
} else {
HasPredOutsideOfLoop = true;
}
}
if (!Preds.empty() && HasPredOutsideOfLoop) {
if (!Exit->isLandingPad()) {
BasicBlock *NewExitBB =
SplitBlockPredecessors(Exit, Preds, "split", P);
if (P->mustPreserveAnalysisID(LCSSAID))
createPHIsForSplitLoopExit(Preds, NewExitBB, Exit);
} else if (SplitLandingPads) {
SmallVector<BasicBlock*, 8> NewBBs;
SplitLandingPadPredecessors(Exit, Preds,
".split1", ".split2",
P, NewBBs);
if (P->mustPreserveAnalysisID(LCSSAID))
createPHIsForSplitLoopExit(Preds, NewBBs[0], Exit);
}
}
}
}
assert((!P->mustPreserveAnalysisID(LCSSAID) ||
P->mustPreserveAnalysisID(LoopSimplifyID)) &&
"SplitCriticalEdge doesn't know how to update LCCSA form "
"without LoopSimplify!");
}
}
if (PI)
PI->splitEdge(TIBB, DestBB, NewBB, MergeIdenticalEdges);
return NewBB;
}