diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Analysis/CFG.cpp | 2 | ||||
| -rw-r--r-- | lib/Analysis/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | lib/Analysis/Dominators.cpp | 160 | ||||
| -rw-r--r-- | lib/StaticAnalyzer/Checkers/DebugCheckers.cpp | 4 |
4 files changed, 3 insertions, 164 deletions
diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp index 4c1652122f..de404d05f7 100644 --- a/lib/Analysis/CFG.cpp +++ b/lib/Analysis/CFG.cpp @@ -3039,7 +3039,7 @@ CFGBlock *CFG::createBlock() { // Create the block. CFGBlock *Mem = getAllocator().Allocate<CFGBlock>(); - new (Mem) CFGBlock(NumBlockIDs++, BlkBVC); + new (Mem) CFGBlock(NumBlockIDs++, BlkBVC, this); Blocks.push_back(Mem, BlkBVC); // If this is the first block, set it as the Entry and Exit. diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 4b88ad279a..7ad14c41eb 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -6,7 +6,6 @@ add_clang_library(clangAnalysis CFGReachabilityAnalysis.cpp CFGStmtMap.cpp CocoaConventions.cpp - Dominators.cpp FormatString.cpp LiveVariables.cpp PostOrderCFGView.cpp diff --git a/lib/Analysis/Dominators.cpp b/lib/Analysis/Dominators.cpp deleted file mode 100644 index 62b72287f9..0000000000 --- a/lib/Analysis/Dominators.cpp +++ /dev/null @@ -1,160 +0,0 @@ -//==- Dominators.cpp - Construct the Dominance Tree Given CFG ----*- C++ --*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements a simple, fast dominance algorithm for source-level CFGs. -// -//===----------------------------------------------------------------------===// - -#include "clang/Analysis/Analyses/Dominators.h" -#include "clang/Analysis/CFG.h" -#include "clang/Analysis/AnalysisContext.h" -#include "clang/Analysis/Analyses/PostOrderCFGView.h" - -using namespace clang; - -DominatorTree::~DominatorTree() { - IDoms.clear(); - RootNode = 0; -} - -CFGBlock * DominatorTree::getNode(const CFGBlock *B) const { - CFGBlockMapTy::const_iterator I = IDoms.find(B); - return I != IDoms.end() ? I->second : 0; -} - -bool DominatorTree::properlyDominates(const CFGBlock *A, - const CFGBlock *B) const { - if (0 == A || 0 == B || A == B) - return false; - - // The EntryBlock dominates every other block. - if (A == RootNode) - return true; - - // Note: The dominator of the EntryBlock is itself. - CFGBlock *IDom = getNode(B); - while (IDom != A && IDom != RootNode) - IDom = getNode(IDom); - - return IDom != RootNode; -} - -bool DominatorTree::dominates(const CFGBlock *A, - const CFGBlock *B) const { - if (A == B) - return true; - - return properlyDominates(A, B); -} - -const CFGBlock * DominatorTree::findNearestCommonDominator - (const CFGBlock *A, const CFGBlock *B) const { - //If A dominates B, then A is the nearest common dominator - if (dominates(A, B)) - return A; - - //If B dominates A, then B is the nearest common dominator - if (dominates(B, A)) - return B; - - //Collect all A's dominators - llvm::SmallPtrSet<CFGBlock *, 16> ADoms; - ADoms.insert(RootNode); - CFGBlock *ADom = getNode(A); - while (ADom != RootNode) { - ADoms.insert(ADom); - ADom = getNode(ADom); - } - - //Check all B's dominators against ADoms - CFGBlock *BDom = getNode(B); - while (BDom != RootNode){ - if (ADoms.count(BDom) != 0) - return BDom; - - BDom = getNode(BDom); - } - - //The RootNode dominates every other node - return RootNode; -} - -/// Constructs immediate dominator tree for a given CFG based on the algorithm -/// described in this paper: -/// -/// A Simple, Fast Dominance Algorithm -/// Keith D. Cooper, Timothy J. Harvey and Ken Kennedy -/// Software-Practice and Expreience, 2001;4:1-10. -/// -/// This implementation is simple and runs faster in practice than the classis -/// Lengauer-Tarjan algorithm. For detailed discussions, refer to the paper. -void DominatorTree::BuildDominatorTree() { - CFG *cfg = AC.getCFG(); - CFGBlock *EntryBlk = &cfg->getEntry(); - - //Sort all CFGBlocks in reverse order - PostOrderCFGView *rpocfg = AC.getAnalysis<PostOrderCFGView>(); - - //Set the root of the dominance tree - RootNode = EntryBlk; - - //Compute the immediate dominator for each CFGBlock - IDoms[EntryBlk] = EntryBlk; - bool changed = true; - while (changed){ - changed = false; - - for (PostOrderCFGView::iterator I = rpocfg->begin(), - E = rpocfg->end(); I != E; ++I){ - if (EntryBlk == *I) - continue; - if (const CFGBlock *B = *I) { - //Compute immediate dominance information for CFGBlock B - CFGBlock *IDom = 0; - for (CFGBlock::const_pred_iterator J = B->pred_begin(), - K = B->pred_end(); J != K; ++J) - if( CFGBlock *P = *J) { - if (IDoms.find(P) == IDoms.end()) - continue; - if (!IDom) - IDom = P; - else { - //intersect IDom and P - CFGBlock *B1 = IDom, *B2 = P; - while (B1 != B2) { - while ((rpocfg->getComparator())(B2,B1)) - B1 = IDoms[B1]; - while ((rpocfg->getComparator())(B1,B2)) - B2 = IDoms[B2]; - } - IDom = B1; - } - } - if (IDoms[B] != IDom) { - IDoms[B] = IDom; - changed = true; - } - } - } - }//while -} - -void DominatorTree::dump() { - CFG *cfg = AC.getCFG(); - - llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n"; - for (CFG::const_iterator I = cfg->begin(), - E = cfg->end(); I != E; ++I) { - assert(IDoms[(*I)] && - "Failed to find the immediate dominator for all CFG blocks."); - llvm::errs() << "(" << (*I)->getBlockID() - << "," << IDoms[(*I)]->getBlockID() << ")\n"; - } -} - diff --git a/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp b/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp index c06be4467a..bd1b8542f6 100644 --- a/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp +++ b/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp @@ -30,8 +30,8 @@ public: void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, BugReporter &BR) const { if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) { - DominatorTree dom(*AC); - dom.BuildDominatorTree(); + DominatorTree dom; + dom.buildDominatorTree(*AC); dom.dump(); } } |