#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/Compiler.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
STATISTIC(NumBroken, "Number of blocks inserted");
namespace {
- struct VISIBILITY_HIDDEN BreakCriticalEdges : public FunctionPass {
+ struct BreakCriticalEdges : public FunctionPass {
static char ID; // Pass identification, replacement for typeid
BreakCriticalEdges() : FunctionPass(&ID) {}
AU.addPreserved<DominatorTree>();
AU.addPreserved<DominanceFrontier>();
AU.addPreserved<LoopInfo>();
+ AU.addPreserved<ProfileInfo>();
// No loop canonicalization guarantees are broken by this pass.
AU.addPreservedID(LoopSimplifyID);
bool Changed = false;
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
TerminatorInst *TI = I->getTerminator();
- if (TI->getNumSuccessors() > 1)
+ if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
if (SplitCriticalEdge(TI, i, this)) {
++NumBroken;
return false;
}
+/// CreatePHIsForSplitLoopExit - When a loop exit edge is split, LCSSA form
+/// may require new PHIs in the new exit block. This function inserts the
+/// new PHIs, as needed. Preds is a list of preds inside the loop, SplitBB
+/// is the new loop exit block, and DestBB is the old loop exit, now the
+/// successor of SplitBB.
+static void CreatePHIsForSplitLoopExit(SmallVectorImpl<BasicBlock *> &Preds,
+ BasicBlock *SplitBB,
+ BasicBlock *DestBB) {
+ // SplitBB shouldn't have anything non-trivial in it yet.
+ assert(SplitBB->getFirstNonPHI() == SplitBB->getTerminator() &&
+ "SplitBB has non-PHI nodes!");
+
+ // For each PHI in the destination block...
+ for (BasicBlock::iterator I = DestBB->begin();
+ PHINode *PN = dyn_cast<PHINode>(I); ++I) {
+ unsigned Idx = PN->getBasicBlockIndex(SplitBB);
+ Value *V = PN->getIncomingValue(Idx);
+ // If the input is a PHI which already satisfies LCSSA, don't create
+ // a new one.
+ if (const PHINode *VP = dyn_cast<PHINode>(V))
+ if (VP->getParent() == SplitBB)
+ continue;
+ // Otherwise a new PHI is needed. Create one and populate it.
+ PHINode *NewPN = PHINode::Create(PN->getType(), "split",
+ SplitBB->getTerminator());
+ for (unsigned i = 0, e = Preds.size(); i != e; ++i)
+ NewPN->addIncoming(V, Preds[i]);
+ // Update the original PHI.
+ PN->setIncomingValue(Idx, NewPN);
+ }
+}
+
/// 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 any of them. This returns true if the edge was split,
-/// false otherwise. This ensures that all edges to that dest go to one block
-/// instead of each going to a different block.
-//
+/// 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.
+///
+/// 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".
+///
+/// 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
+/// program because the address of the new block won't be the one that is jumped
+/// to.
+///
BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
Pass *P, bool MergeIdenticalEdges) {
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 (TIL == DestLoop) {
// Both in the same loop, the NewBB joins loop.
DestLoop->addBasicBlockToLoop(NewBB, LI->getBase());
- } else if (TIL->contains(DestLoop->getHeader())) {
+ } else if (TIL->contains(DestLoop)) {
// Edge from an outer loop to an inner loop. Add to the outer loop.
TIL->addBasicBlockToLoop(NewBB, LI->getBase());
- } else if (DestLoop->contains(TIL->getHeader())) {
+ } else if (DestLoop->contains(TIL)) {
// Edge from an inner loop to an outer loop. Add to the outer loop.
DestLoop->addBasicBlockToLoop(NewBB, LI->getBase());
} else {
// the loop, to maintain a LoopSimplify guarantee.
if (!TIL->contains(DestBB) &&
P->mustPreserveAnalysisID(LoopSimplifyID)) {
+ assert(!TIL->contains(NewBB) &&
+ "Split point for loop exit is contained in loop!");
+
+ // Update LCSSA form in the newly created exit block.
+ if (P->mustPreserveAnalysisID(LCSSAID)) {
+ SmallVector<BasicBlock *, 1> OrigPred;
+ OrigPred.push_back(TIBB);
+ CreatePHIsForSplitLoopExit(OrigPred, NewBB, DestBB);
+ }
+
// For each unique exit block...
SmallVector<BasicBlock *, 4> ExitBlocks;
TIL->getExitBlocks(ExitBlocks);
// Collect all the preds that are inside the loop, and note
// whether there are any preds outside the loop.
SmallVector<BasicBlock *, 4> Preds;
- bool AllPredsInLoop = false;
+ bool HasPredOutsideOfLoop = false;
BasicBlock *Exit = ExitBlocks[i];
for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit);
I != E; ++I)
if (TIL->contains(*I))
Preds.push_back(*I);
else
- AllPredsInLoop = true;
+ HasPredOutsideOfLoop = true;
// If there are any preds not in the loop, we'll need to split
// the edges. The Preds.empty() check is needed because a block
// may appear multiple times in the list. We can't use
// getUniqueExitBlocks above because that depends on LoopSimplify
// form, which we're in the process of restoring!
- if (Preds.empty() || !AllPredsInLoop) continue;
- BasicBlock *NewBB = SplitBlockPredecessors(Exit,
- Preds.data(), Preds.size(),
- "split", P);
- // Update LCSSA form. This is fairly simple in LoopSimplify form:
- // just move the existing LCSSA-mandated PHI nodes from the old exit
- // block to the new one.
- if (P->mustPreserveAnalysisID(LCSSAID))
- for (BasicBlock::iterator I = Exit->begin();
- PHINode *PN = dyn_cast<PHINode>(I); ++I)
- PN->moveBefore(NewBB->getTerminator());
+ if (!Preds.empty() && HasPredOutsideOfLoop) {
+ BasicBlock *NewExitBB =
+ SplitBlockPredecessors(Exit, Preds.data(), Preds.size(),
+ "split", P);
+ if (P->mustPreserveAnalysisID(LCSSAID))
+ CreatePHIsForSplitLoopExit(Preds, NewExitBB, Exit);
+ }
}
}
// LCSSA form was updated above for the case where LoopSimplify is
"SplitCriticalEdge doesn't know how to update LCCSA form "
"without LoopSimplify!");
}
+ }
+ // Update ProfileInfo if it is around.
+ if (ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>()) {
+ PI->splitEdge(TIBB,DestBB,NewBB,MergeIdenticalEdges);
}
return NewBB;
projects / oota-llvm.git / blobdiff