//
// The LLVM Compiler Infrastructure
//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//
//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "loopsimplify"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/Constant.h"
+#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Function.h"
#include "llvm/Type.h"
#include "llvm/ADT/DepthFirstIterator.h"
using namespace llvm;
-namespace {
- Statistic<>
- NumInserted("loopsimplify", "Number of pre-header or exit blocks inserted");
- Statistic<>
- NumNested("loopsimplify", "Number of nested loops split out");
+STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted");
+STATISTIC(NumNested , "Number of nested loops split out");
+namespace {
struct VISIBILITY_HIDDEN LoopSimplify : public FunctionPass {
+ static char ID; // Pass identification, replacement for typeid
+ LoopSimplify() : FunctionPass((intptr_t)&ID) {}
+
// AA - If we have an alias analysis object to update, this is it, otherwise
// this is null.
AliasAnalysis *AA;
LoopInfo *LI;
-
+ DominatorTree *DT;
virtual bool runOnFunction(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
// We need loop information to identify the loops...
AU.addRequired<LoopInfo>();
- AU.addRequired<DominatorSet>();
AU.addRequired<DominatorTree>();
AU.addPreserved<LoopInfo>();
- AU.addPreserved<DominatorSet>();
- AU.addPreserved<ImmediateDominators>();
- AU.addPreserved<ETForest>();
AU.addPreserved<DominatorTree>();
AU.addPreserved<DominanceFrontier>();
AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added.
}
+
+ /// verifyAnalysis() - Verify loop nest.
+ void verifyAnalysis() const {
+#ifndef NDEBUG
+ LoopInfo *NLI = &getAnalysis<LoopInfo>();
+ for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I)
+ (*I)->verifyLoop();
+#endif
+ }
+
private:
bool ProcessLoop(Loop *L);
BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix,
void PlaceSplitBlockCarefully(BasicBlock *NewBB,
std::vector<BasicBlock*> &SplitPreds,
Loop *L);
-
- void UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB,
- std::vector<BasicBlock*> &PredBlocks);
};
+ char LoopSimplify::ID = 0;
RegisterPass<LoopSimplify>
X("loopsimplify", "Canonicalize natural loops", true);
}
bool Changed = false;
LI = &getAnalysis<LoopInfo>();
AA = getAnalysisToUpdate<AliasAnalysis>();
+ DT = &getAnalysis<DominatorTree>();
// Check to see that no blocks (other than the header) in loops have
// predecessors that are not in loops. This is not valid for natural loops,
if (LI->getLoopFor(BB)) continue;
bool BlockUnreachable = false;
- TerminatorInst *TI = BB->getTerminator();
// Check to see if any successors of this block are non-loop-header loops
// that are not the header.
- for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
+ for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
// If this successor is not in a loop, BB is clearly ok.
- Loop *L = LI->getLoopFor(TI->getSuccessor(i));
+ Loop *L = LI->getLoopFor(*I);
if (!L) continue;
// If the succ is the loop header, and if L is a top-level loop, then this
// is an entrance into a loop through the header, which is also ok.
- if (L->getHeader() == TI->getSuccessor(i) && L->getParentLoop() == 0)
+ if (L->getHeader() == *I && L->getParentLoop() == 0)
continue;
// Otherwise, this is an entrance into a loop from some place invalid.
// loop by replacing the terminator.
// Remove PHI entries from the successors.
- for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
- TI->getSuccessor(i)->removePredecessor(BB);
+ for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
+ (*I)->removePredecessor(BB);
- // Add a new unreachable instruction.
+ // Add a new unreachable instruction before the old terminator.
+ TerminatorInst *TI = BB->getTerminator();
new UnreachableInst(TI);
// Delete the dead terminator.
- if (AA) AA->deleteValue(&BB->back());
- BB->getInstList().pop_back();
+ if (AA) AA->deleteValue(TI);
+ if (!TI->use_empty())
+ TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
+ TI->eraseFromParent();
Changed |= true;
}
// predecessors that are inside of the loop. This check guarantees that the
// loop preheader/header will dominate the exit blocks. If the exit block has
// predecessors from outside of the loop, split the edge now.
- std::vector<BasicBlock*> ExitBlocks;
+ SmallVector<BasicBlock*, 8> ExitBlocks;
L->getExitBlocks(ExitBlocks);
SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end());
const std::vector<BasicBlock*> &Preds) {
// Create new basic block, insert right before the original block...
- BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB->getParent(), BB);
+ BasicBlock *NewBB = BasicBlock::Create(BB->getName()+Suffix, BB->getParent(), BB);
// The preheader first gets an unconditional branch to the loop header...
- BranchInst *BI = new BranchInst(BB, NewBB);
+ BranchInst *BI = BranchInst::Create(BB, NewBB);
// For every PHI node in the block, insert a PHI node into NewBB where the
// incoming values from the out of loop edges are moved to NewBB. We have two
// If the values coming into the block are not the same, we need a PHI.
if (InVal == 0) {
// Create the new PHI node, insert it into NewBB at the end of the block
- PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI);
+ PHINode *NewPHI = PHINode::Create(PN->getType(), PN->getName()+".ph", BI);
if (AA) AA->copyValue(PN, NewPHI);
// Move all of the edges from blocks outside the loop to the new PHI
// Can we eliminate this phi node now?
if (Value *V = PN->hasConstantValue(true)) {
- if (!isa<Instruction>(V) ||
- getAnalysis<DominatorSet>().dominates(cast<Instruction>(V), PN)) {
+ Instruction *I = dyn_cast<Instruction>(V);
+ // If I is in NewBB, the Dominator call will fail, because NewBB isn't
+ // registered in DominatorTree yet. Handle this case explicitly.
+ if (!I || (I->getParent() != NewBB &&
+ getAnalysis<DominatorTree>().dominates(I, PN))) {
PN->replaceAllUsesWith(V);
if (AA) AA->deleteValue(PN);
BB->getInstList().erase(PN);
for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s)
if (TI->getSuccessor(s) == BB)
TI->setSuccessor(s, NewBB);
+
+ if (Preds[i]->getUnwindDest() == BB)
+ Preds[i]->setUnwindDest(NewBB);
}
} else { // Otherwise the loop is dead...
PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB);
}
}
+
return NewBB;
}
// We know that we have loop information to update... update it now.
if (Loop *Parent = L->getParentLoop())
- Parent->addBasicBlockToLoop(NewBB, *LI);
+ Parent->addBasicBlockToLoop(NewBB, LI->getBase());
+
+ DT->splitBlock(NewBB);
+ if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>())
+ DF->splitBlock(NewBB);
- UpdateDomInfoForRevectoredPreds(NewBB, OutsideBlocks);
-
// Make sure that NewBB is put someplace intelligent, which doesn't mess up
// code layout too horribly.
PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L);
while (SuccLoop && !SuccLoop->contains(L->getHeader()))
SuccLoop = SuccLoop->getParentLoop();
if (SuccLoop)
- SuccLoop->addBasicBlockToLoop(NewBB, *LI);
+ SuccLoop->addBasicBlockToLoop(NewBB, LI->getBase());
+
+ // Update Dominator Information
+ DT->splitBlock(NewBB);
+ if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>())
+ DF->splitBlock(NewBB);
- // Update dominator information (set, immdom, domtree, and domfrontier)
- UpdateDomInfoForRevectoredPreds(NewBB, LoopBlocks);
return NewBB;
}
/// AddBlockAndPredsToSet - Add the specified block, and all of its
/// predecessors, to the specified set, if it's not already in there. Stop
/// predecessor traversal when we reach StopBlock.
-static void AddBlockAndPredsToSet(BasicBlock *BB, BasicBlock *StopBlock,
+static void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock,
std::set<BasicBlock*> &Blocks) {
- if (!Blocks.insert(BB).second) return; // already processed.
- if (BB == StopBlock) return; // Stop here!
-
- for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I)
- AddBlockAndPredsToSet(*I, StopBlock, Blocks);
+ std::vector<BasicBlock *> WorkList;
+ WorkList.push_back(InputBB);
+ do {
+ BasicBlock *BB = WorkList.back(); WorkList.pop_back();
+ if (Blocks.insert(BB).second && BB != StopBlock)
+ // If BB is not already processed and it is not a stop block then
+ // insert its predecessor in the work list
+ for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
+ BasicBlock *WBB = *I;
+ WorkList.push_back(WBB);
+ }
+ } while(!WorkList.empty());
}
/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a
/// PHI node that tells us how to partition the loops.
-static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorSet &DS,
+static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT,
AliasAnalysis *AA) {
for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
PHINode *PN = cast<PHINode>(I);
++I;
if (Value *V = PN->hasConstantValue())
- if (!isa<Instruction>(V) || DS.dominates(cast<Instruction>(V), PN)) {
+ if (!isa<Instruction>(V) || DT->dominates(cast<Instruction>(V), PN)) {
// This is a degenerate PHI already, don't modify it!
PN->replaceAllUsesWith(V);
if (AA) AA->deleteValue(PN);
/// created.
///
Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
- PHINode *PN = FindPHIToPartitionLoops(L, getAnalysis<DominatorSet>(), AA);
+ PHINode *PN = FindPHIToPartitionLoops(L, DT, AA);
if (PN == 0) return 0; // No known way to partition.
// Pull out all predecessors that have varying values in the loop. This
BasicBlock *Header = L->getHeader();
BasicBlock *NewBB = SplitBlockPredecessors(Header, ".outer", OuterLoopPreds);
- // Update dominator information (set, immdom, domtree, and domfrontier)
- UpdateDomInfoForRevectoredPreds(NewBB, OuterLoopPreds);
+ // Update dominator information
+ DT->splitBlock(NewBB);
+ if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>())
+ DF->splitBlock(NewBB);
// Make sure that NewBB is put someplace intelligent, which doesn't mess up
// code layout too horribly.
// This block is going to be our new header block: add it to this loop and all
// parent loops.
- NewOuter->addBasicBlockToLoop(NewBB, *LI);
+ NewOuter->addBasicBlockToLoop(NewBB, LI->getBase());
// L is now a subloop of our outer loop.
NewOuter->addChildLoop(L);
// Determine which blocks should stay in L and which should be moved out to
// the Outer loop now.
- DominatorSet &DS = getAnalysis<DominatorSet>();
std::set<BasicBlock*> BlocksInL;
for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI)
- if (DS.dominates(Header, *PI))
+ if (DT->dominates(Header, *PI))
AddBlockAndPredsToSet(*PI, Header, BlocksInL);
// Scan all of the loop children of L, moving them to OuterLoop if they are
// not part of the inner loop.
- for (Loop::iterator I = L->begin(); I != L->end(); )
- if (BlocksInL.count((*I)->getHeader()))
+ const std::vector<Loop*> &SubLoops = L->getSubLoops();
+ for (size_t I = 0; I != SubLoops.size(); )
+ if (BlocksInL.count(SubLoops[I]->getHeader()))
++I; // Loop remains in L
else
- NewOuter->addChildLoop(L->removeChildLoop(I));
+ NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I));
// Now that we know which blocks are in L and which need to be moved to
// OuterLoop, move any blocks that need it.
if (*I != Preheader) BackedgeBlocks.push_back(*I);
// Create and insert the new backedge block...
- BasicBlock *BEBlock = new BasicBlock(Header->getName()+".backedge", F);
- BranchInst *BETerminator = new BranchInst(Header, BEBlock);
+ BasicBlock *BEBlock = BasicBlock::Create(Header->getName()+".backedge", F);
+ BranchInst *BETerminator = BranchInst::Create(Header, BEBlock);
// Move the new backedge block to right after the last backedge block.
Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos;
// the backedge block which correspond to any PHI nodes in the header block.
for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
- PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".be",
- BETerminator);
+ PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".be",
+ BETerminator);
NewPN->reserveOperandSpace(BackedgeBlocks.size());
if (AA) AA->copyValue(PN, NewPN);
}
// Now that all of the PHI nodes have been inserted and adjusted, modify the
- // backedge blocks to just to the BEBlock instead of the header.
+ // backedge blocks to branch to the BEBlock instead of the header.
for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) {
TerminatorInst *TI = BackedgeBlocks[i]->getTerminator();
for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op)
if (TI->getSuccessor(Op) == Header)
TI->setSuccessor(Op, BEBlock);
+
+ if (BackedgeBlocks[i]->getUnwindDest() == Header)
+ BackedgeBlocks[i]->setUnwindDest(BEBlock);
}
//===--- Update all analyses which we must preserve now -----------------===//
// Update Loop Information - we know that this block is now in the current
// loop and all parent loops.
- L->addBasicBlockToLoop(BEBlock, *LI);
-
- // Update dominator information (set, immdom, domtree, and domfrontier)
- UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks);
-}
-
-/// UpdateDomInfoForRevectoredPreds - This method is used to update the four
-/// different kinds of dominator information (dominator sets, immediate
-/// dominators, dominator trees, and dominance frontiers) after a new block has
-/// been added to the CFG.
-///
-/// This only supports the case when an existing block (known as "NewBBSucc"),
-/// had some of its predecessors factored into a new basic block. This
-/// transformation inserts a new basic block ("NewBB"), with a single
-/// unconditional branch to NewBBSucc, and moves some predecessors of
-/// "NewBBSucc" to now branch to NewBB. These predecessors are listed in
-/// PredBlocks, even though they are the same as
-/// pred_begin(NewBB)/pred_end(NewBB).
-///
-void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB,
- std::vector<BasicBlock*> &PredBlocks) {
- assert(!PredBlocks.empty() && "No predblocks??");
- assert(succ_begin(NewBB) != succ_end(NewBB) &&
- ++succ_begin(NewBB) == succ_end(NewBB) &&
- "NewBB should have a single successor!");
- BasicBlock *NewBBSucc = *succ_begin(NewBB);
- DominatorSet &DS = getAnalysis<DominatorSet>();
-
- // Update dominator information... The blocks that dominate NewBB are the
- // intersection of the dominators of predecessors, plus the block itself.
- //
- DominatorSet::DomSetType NewBBDomSet = DS.getDominators(PredBlocks[0]);
- {
- unsigned i, e = PredBlocks.size();
- // It is possible for some preds to not be reachable, and thus have empty
- // dominator sets (all blocks must dom themselves, so no domset would
- // otherwise be empty). If we see any of these, don't intersect with them,
- // as that would certainly leave the resultant set empty.
- for (i = 1; NewBBDomSet.empty(); ++i) {
- assert(i != e && "Didn't find reachable pred?");
- NewBBDomSet = DS.getDominators(PredBlocks[i]);
- }
-
- // Intersect the rest of the non-empty sets.
- for (; i != e; ++i) {
- const DominatorSet::DomSetType &PredDS = DS.getDominators(PredBlocks[i]);
- if (!PredDS.empty())
- set_intersect(NewBBDomSet, PredDS);
- }
- NewBBDomSet.insert(NewBB); // All blocks dominate themselves.
- DS.addBasicBlock(NewBB, NewBBDomSet);
- }
-
- // The newly inserted basic block will dominate existing basic blocks iff the
- // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate
- // the non-pred blocks, then they all must be the same block!
- //
- bool NewBBDominatesNewBBSucc = true;
- {
- BasicBlock *OnePred = PredBlocks[0];
- unsigned i, e = PredBlocks.size();
- for (i = 1; !DS.isReachable(OnePred); ++i) {
- assert(i != e && "Didn't find reachable pred?");
- OnePred = PredBlocks[i];
- }
-
- for (; i != e; ++i)
- if (PredBlocks[i] != OnePred && DS.isReachable(PredBlocks[i])) {
- NewBBDominatesNewBBSucc = false;
- break;
- }
-
- if (NewBBDominatesNewBBSucc)
- for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
- PI != E; ++PI)
- if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) {
- NewBBDominatesNewBBSucc = false;
- break;
- }
- }
+ L->addBasicBlockToLoop(BEBlock, LI->getBase());
- // The other scenario where the new block can dominate its successors are when
- // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc
- // already.
- if (!NewBBDominatesNewBBSucc) {
- NewBBDominatesNewBBSucc = true;
- for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
- PI != E; ++PI)
- if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) {
- NewBBDominatesNewBBSucc = false;
- break;
- }
- }
-
- // If NewBB dominates some blocks, then it will dominate all blocks that
- // NewBBSucc does.
- if (NewBBDominatesNewBBSucc) {
- BasicBlock *PredBlock = PredBlocks[0];
- Function *F = NewBB->getParent();
- for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
- if (DS.dominates(NewBBSucc, I))
- DS.addDominator(I, NewBB);
- }
-
- // Update immediate dominator information if we have it.
- BasicBlock *NewBBIDom = 0;
- if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) {
- // To find the immediate dominator of the new exit node, we trace up the
- // immediate dominators of a predecessor until we find a basic block that
- // dominates the exit block.
- //
- BasicBlock *Dom = PredBlocks[0]; // Some random predecessor.
-
- // Find a reachable pred.
- for (unsigned i = 1; !DS.isReachable(Dom); ++i) {
- assert(i != PredBlocks.size() && "Didn't find reachable pred!");
- Dom = PredBlocks[i];
- }
-
- while (!NewBBDomSet.count(Dom)) { // Loop until we find a dominator.
- assert(Dom != 0 && "No shared dominator found???");
- Dom = ID->get(Dom);
- }
-
- // Set the immediate dominator now...
- ID->addNewBlock(NewBB, Dom);
- NewBBIDom = Dom; // Reuse this if calculating DominatorTree info...
-
- // If NewBB strictly dominates other blocks, we need to update their idom's
- // now. The only block that need adjustment is the NewBBSucc block, whose
- // idom should currently be set to PredBlocks[0].
- if (NewBBDominatesNewBBSucc)
- ID->setImmediateDominator(NewBBSucc, NewBB);
- }
-
- // Update DominatorTree information if it is active.
- if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) {
- // If we don't have ImmediateDominator info around, calculate the idom as
- // above.
- DominatorTree::Node *NewBBIDomNode;
- if (NewBBIDom) {
- NewBBIDomNode = DT->getNode(NewBBIDom);
- } else {
- // Scan all the pred blocks that were pulled out. Any individual one may
- // actually be unreachable, which would mean it doesn't have dom info.
- NewBBIDomNode = 0;
- for (unsigned i = 0; !NewBBIDomNode; ++i) {
- assert(i != PredBlocks.size() && "No reachable preds?");
- NewBBIDomNode = DT->getNode(PredBlocks[i]);
- }
-
- while (!NewBBDomSet.count(NewBBIDomNode->getBlock())) {
- NewBBIDomNode = NewBBIDomNode->getIDom();
- assert(NewBBIDomNode && "No shared dominator found??");
- }
- NewBBIDom = NewBBIDomNode->getBlock();
- }
-
- // Create the new dominator tree node... and set the idom of NewBB.
- DominatorTree::Node *NewBBNode = DT->createNewNode(NewBB, NewBBIDomNode);
-
- // If NewBB strictly dominates other blocks, then it is now the immediate
- // dominator of NewBBSucc. Update the dominator tree as appropriate.
- if (NewBBDominatesNewBBSucc) {
- DominatorTree::Node *NewBBSuccNode = DT->getNode(NewBBSucc);
- DT->changeImmediateDominator(NewBBSuccNode, NewBBNode);
- }
- }
-
- // Update ET-Forest information if it is active.
- if (ETForest *EF = getAnalysisToUpdate<ETForest>()) {
- EF->addNewBlock(NewBB, NewBBIDom);
- if (NewBBDominatesNewBBSucc)
- EF->setImmediateDominator(NewBBSucc, NewBB);
- }
-
- // Update dominance frontier information...
- if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) {
- // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the
- // DF(PredBlocks[0]) without the stuff that the new block does not dominate
- // a predecessor of.
- if (NewBBDominatesNewBBSucc) {
- DominanceFrontier::iterator DFI = DF->find(PredBlocks[0]);
- if (DFI != DF->end()) {
- DominanceFrontier::DomSetType Set = DFI->second;
- // Filter out stuff in Set that we do not dominate a predecessor of.
- for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
- E = Set.end(); SetI != E;) {
- bool DominatesPred = false;
- for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI);
- PI != E; ++PI)
- if (DS.dominates(NewBB, *PI))
- DominatesPred = true;
- if (!DominatesPred)
- Set.erase(SetI++);
- else
- ++SetI;
- }
-
- DF->addBasicBlock(NewBB, Set);
- }
-
- } else {
- // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate
- // NewBBSucc, but it does dominate itself (and there is an edge (NewBB ->
- // NewBBSucc)). NewBBSucc is the single successor of NewBB.
- DominanceFrontier::DomSetType NewDFSet;
- NewDFSet.insert(NewBBSucc);
- DF->addBasicBlock(NewBB, NewDFSet);
- }
-
- // Now we must loop over all of the dominance frontiers in the function,
- // replacing occurrences of NewBBSucc with NewBB in some cases. All
- // blocks that dominate a block in PredBlocks and contained NewBBSucc in
- // their dominance frontier must be updated to contain NewBB instead.
- //
- for (unsigned i = 0, e = PredBlocks.size(); i != e; ++i) {
- BasicBlock *Pred = PredBlocks[i];
- // Get all of the dominators of the predecessor...
- const DominatorSet::DomSetType &PredDoms = DS.getDominators(Pred);
- for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(),
- PDE = PredDoms.end(); PDI != PDE; ++PDI) {
- BasicBlock *PredDom = *PDI;
-
- // If the NewBBSucc node is in DF(PredDom), then PredDom didn't
- // dominate NewBBSucc but did dominate a predecessor of it. Now we
- // change this entry to include NewBB in the DF instead of NewBBSucc.
- DominanceFrontier::iterator DFI = DF->find(PredDom);
- assert(DFI != DF->end() && "No dominance frontier for node?");
- if (DFI->second.count(NewBBSucc)) {
- // If NewBBSucc should not stay in our dominator frontier, remove it.
- // We remove it unless there is a predecessor of NewBBSucc that we
- // dominate, but we don't strictly dominate NewBBSucc.
- bool ShouldRemove = true;
- if (PredDom == NewBBSucc || !DS.dominates(PredDom, NewBBSucc)) {
- // Okay, we know that PredDom does not strictly dominate NewBBSucc.
- // Check to see if it dominates any predecessors of NewBBSucc.
- for (pred_iterator PI = pred_begin(NewBBSucc),
- E = pred_end(NewBBSucc); PI != E; ++PI)
- if (DS.dominates(PredDom, *PI)) {
- ShouldRemove = false;
- break;
- }
- }
-
- if (ShouldRemove)
- DF->removeFromFrontier(DFI, NewBBSucc);
- DF->addToFrontier(DFI, NewBB);
- }
- }
- }
- }
+ // Update dominator information
+ DT->splitBlock(BEBlock);
+ if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>())
+ DF->splitBlock(BEBlock);
}
-
projects / oota-llvm.git / blobdiff