diff options
author | Stephen Hines <srhines@google.com> | 2014-12-01 14:51:49 -0800 |
---|---|---|
committer | Stephen Hines <srhines@google.com> | 2014-12-02 16:08:10 -0800 |
commit | 37ed9c199ca639565f6ce88105f9e39e898d82d0 (patch) | |
tree | 8fb36d3910e3ee4c4e1b7422f4f017108efc52f5 /lib/Analysis/DominanceFrontier.cpp | |
parent | d2327b22152ced7bc46dc629fc908959e8a52d03 (diff) | |
download | external_llvm-37ed9c199ca639565f6ce88105f9e39e898d82d0.zip external_llvm-37ed9c199ca639565f6ce88105f9e39e898d82d0.tar.gz external_llvm-37ed9c199ca639565f6ce88105f9e39e898d82d0.tar.bz2 |
Update aosp/master LLVM for rebase to r222494.
Change-Id: Ic787f5e0124df789bd26f3f24680f45e678eef2d
Diffstat (limited to 'lib/Analysis/DominanceFrontier.cpp')
-rw-r--r-- | lib/Analysis/DominanceFrontier.cpp | 135 |
1 files changed, 26 insertions, 109 deletions
diff --git a/lib/Analysis/DominanceFrontier.cpp b/lib/Analysis/DominanceFrontier.cpp index 74594f8..7ba91bc 100644 --- a/lib/Analysis/DominanceFrontier.cpp +++ b/lib/Analysis/DominanceFrontier.cpp @@ -8,133 +8,50 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/DominanceFrontier.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" +#include "llvm/Analysis/DominanceFrontierImpl.h" + using namespace llvm; +namespace llvm { +template class DominanceFrontierBase<BasicBlock>; +template class ForwardDominanceFrontierBase<BasicBlock>; +} + char DominanceFrontier::ID = 0; + INITIALIZE_PASS_BEGIN(DominanceFrontier, "domfrontier", "Dominance Frontier Construction", true, true) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_END(DominanceFrontier, "domfrontier", "Dominance Frontier Construction", true, true) -namespace { - class DFCalculateWorkObject { - public: - DFCalculateWorkObject(BasicBlock *B, BasicBlock *P, - const DomTreeNode *N, - const DomTreeNode *PN) - : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} - BasicBlock *currentBB; - BasicBlock *parentBB; - const DomTreeNode *Node; - const DomTreeNode *parentNode; - }; +DominanceFrontier::DominanceFrontier() + : FunctionPass(ID), + Base() { + initializeDominanceFrontierPass(*PassRegistry::getPassRegistry()); } -void DominanceFrontier::anchor() { } - -const DominanceFrontier::DomSetType & -DominanceFrontier::calculate(const DominatorTree &DT, - const DomTreeNode *Node) { - BasicBlock *BB = Node->getBlock(); - DomSetType *Result = nullptr; - - std::vector<DFCalculateWorkObject> workList; - SmallPtrSet<BasicBlock *, 32> visited; - - workList.push_back(DFCalculateWorkObject(BB, nullptr, Node, nullptr)); - do { - DFCalculateWorkObject *currentW = &workList.back(); - assert (currentW && "Missing work object."); - - BasicBlock *currentBB = currentW->currentBB; - BasicBlock *parentBB = currentW->parentBB; - const DomTreeNode *currentNode = currentW->Node; - const DomTreeNode *parentNode = currentW->parentNode; - assert (currentBB && "Invalid work object. Missing current Basic Block"); - assert (currentNode && "Invalid work object. Missing current Node"); - DomSetType &S = Frontiers[currentBB]; - - // Visit each block only once. - if (visited.count(currentBB) == 0) { - visited.insert(currentBB); - - // Loop over CFG successors to calculate DFlocal[currentNode] - for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB); - SI != SE; ++SI) { - // Does Node immediately dominate this successor? - if (DT[*SI]->getIDom() != currentNode) - S.insert(*SI); - } - } - - // At this point, S is DFlocal. Now we union in DFup's of our children... - // Loop through and visit the nodes that Node immediately dominates (Node's - // children in the IDomTree) - bool visitChild = false; - for (DomTreeNode::const_iterator NI = currentNode->begin(), - NE = currentNode->end(); NI != NE; ++NI) { - DomTreeNode *IDominee = *NI; - BasicBlock *childBB = IDominee->getBlock(); - if (visited.count(childBB) == 0) { - workList.push_back(DFCalculateWorkObject(childBB, currentBB, - IDominee, currentNode)); - visitChild = true; - } - } - - // If all children are visited or there is any child then pop this block - // from the workList. - if (!visitChild) { - - if (!parentBB) { - Result = &S; - break; - } - - DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); - DomSetType &parentSet = Frontiers[parentBB]; - for (; CDFI != CDFE; ++CDFI) { - if (!DT.properlyDominates(parentNode, DT[*CDFI])) - parentSet.insert(*CDFI); - } - workList.pop_back(); - } +void DominanceFrontier::releaseMemory() { + Base.releaseMemory(); +} - } while (!workList.empty()); +bool DominanceFrontier::runOnFunction(Function &) { + releaseMemory(); + Base.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree()); + return false; +} - return *Result; +void DominanceFrontier::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired<DominatorTreeWrapperPass>(); } -void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const { - for (const_iterator I = begin(), E = end(); I != E; ++I) { - OS << " DomFrontier for BB "; - if (I->first) - I->first->printAsOperand(OS, false); - else - OS << " <<exit node>>"; - OS << " is:\t"; - - const std::set<BasicBlock*> &BBs = I->second; - - for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); - I != E; ++I) { - OS << ' '; - if (*I) - (*I)->printAsOperand(OS, false); - else - OS << "<<exit node>>"; - } - OS << "\n"; - } +void DominanceFrontier::print(raw_ostream &OS, const Module *) const { + Base.print(OS); } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) -void DominanceFrontierBase::dump() const { +void DominanceFrontier::dump() const { print(dbgs()); } #endif - |