-//===----------------------------------------------------------------------===//
-// DominanceFrontier Implementation
-//===----------------------------------------------------------------------===//
-
-char DominanceFrontier::ID = 0;
-static RegisterPass<DominanceFrontier>
-G("domfrontier", "Dominance Frontier Construction", true, true);
-
-// NewBB is split and now it has one successor. Update dominace frontier to
-// reflect this change.
-void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
- assert(NewBB->getTerminator()->getNumSuccessors() == 1
- && "NewBB should have a single successor!");
- BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0);
-
- SmallVector<BasicBlock*, 8> PredBlocks;
- for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB);
- PI != PE; ++PI)
- PredBlocks.push_back(*PI);
-
- if (PredBlocks.empty())
- // If NewBB does not have any predecessors then it is a entry block.
- // In this case, NewBB and its successor NewBBSucc dominates all
- // other blocks.
- return;
-
- // NewBBSucc inherits original NewBB frontier.
- DominanceFrontier::iterator NewBBI = find(NewBB);
- if (NewBBI != end()) {
- DominanceFrontier::DomSetType NewBBSet = NewBBI->second;
- DominanceFrontier::DomSetType NewBBSuccSet;
- NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end());
- addBasicBlock(NewBBSucc, NewBBSuccSet);
- }
-
- // 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.
- DominatorTree &DT = getAnalysis<DominatorTree>();
- if (DT.dominates(NewBB, NewBBSucc)) {
- DominanceFrontier::iterator DFI = find(PredBlocks[0]);
- if (DFI != 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 (DT.dominates(NewBB, *PI))
- DominatesPred = true;
- if (!DominatesPred)
- Set.erase(SetI++);
- else
- ++SetI;
- }
-
- if (NewBBI != end()) {
- for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
- E = Set.end(); SetI != E; ++SetI) {
- BasicBlock *SB = *SetI;
- addToFrontier(NewBBI, SB);
- }
- } else
- 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);
- 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 (Function::iterator FI = NewBB->getParent()->begin(),
- FE = NewBB->getParent()->end(); FI != FE; ++FI) {
- DominanceFrontier::iterator DFI = find(FI);
- if (DFI == end()) continue; // unreachable block.
-
- // Only consider nodes that have NewBBSucc in their dominator frontier.
- if (!DFI->second.count(NewBBSucc)) continue;