On Oct 24, 2011, at 5:25 PM, Ted Kremenek wrote: > Author: kremenek > Date: Mon Oct 24 19:25:24 2011 > New Revision: 142885 > > URL: http://llvm.org/viewvc/llvm-project?rev=142885&view=rev > Log: > Add source-level dominators analysis. Patch by Guoping Long!
This reimplements a bunch of code that we already have templates out based on Graph type (see llvm/Analysis/DominatorInternals.h). Why duplicate it? AFAICT, this is also slower than the version in llvm/Analysis. -Chris > > Added: > cfe/trunk/include/clang/Analysis/Analyses/Dominators.h > cfe/trunk/lib/Analysis/Dominators.cpp > cfe/trunk/test/Analysis/domtest.c > Modified: > cfe/trunk/lib/Analysis/CMakeLists.txt > cfe/trunk/lib/StaticAnalyzer/Checkers/Checkers.td > cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp > > Added: cfe/trunk/include/clang/Analysis/Analyses/Dominators.h > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/Analysis/Analyses/Dominators.h?rev=142885&view=auto > ============================================================================== > --- cfe/trunk/include/clang/Analysis/Analyses/Dominators.h (added) > +++ cfe/trunk/include/clang/Analysis/Analyses/Dominators.h Mon Oct 24 > 19:25:24 2011 > @@ -0,0 +1,156 @@ > +//==- 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. > +// > +//===----------------------------------------------------------------------===// > + > +#ifndef LLVM_CLANG_DOMINATORS_H > +#define LLVM_CLANG_DOMINATORS_H > + > +#include "clang/Analysis/CFG.h" > +#include "clang/Analysis/AnalysisContext.h" > +#include "llvm/ADT/DenseMap.h" > + > +namespace clang { > + > +class CFG; > +class CFGBlock; > + > +class DominatorTree : public ManagedAnalysis { > + typedef llvm::DenseMap<const CFGBlock *, CFGBlock*> CFGBlockMapTy; > + > +public: > + DominatorTree(AnalysisDeclContext &ac) > + : AC(ac) {}; > + > + virtual ~DominatorTree(); > + > + /// Return the immediate dominator node given a CFGBlock. > + /// For entry block, the dominator is itself. > + /// This is the same as using operator[] on this class. > + CFGBlock *getNode(const CFGBlock *B) const; > + > + /// This returns the Entry Block for the given CFG > + CFGBlock *getRootNode() { return RootNode; } > + const CFGBlock *getRootNode() const { return RootNode; } > + > + /// Returns true iff A dominates B and A != B. > + /// Note that this is not a constant time operation. > + bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const; > + > + /// Returns true iff A dominates B. > + bool dominates(const CFGBlock *A, const CFGBlock *B) const; > + > + /// Find nearest common dominator for blocks A and B. > + /// Common dominator always exists, ex: entry block. > + const CFGBlock *findNearestCommonDominator(const CFGBlock *A, > + const CFGBlock *B) const; > + > + /// 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 BuildDominatorTree(); > + > + /// Dump the immediate dominance tree > + void dump(); > + > +private: > + AnalysisDeclContext &AC; > + CFGBlock *RootNode; > + CFGBlockMapTy IDoms; > +}; > + > +} // end namespace clang > + > +#endif > +//==- 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. > +// > +//===----------------------------------------------------------------------===// > + > +#ifndef LLVM_CLANG_DOMINATORS_H > +#define LLVM_CLANG_DOMINATORS_H > + > +#include "clang/Analysis/CFG.h" > +#include "clang/Analysis/AnalysisDeclContext.h" > +#include "llvm/ADT/DenseMap.h" > + > +namespace clang { > + > +class CFG; > +class CFGBlock; > + > +class DominatorTree : public ManagedAnalysis { > + typedef llvm::DenseMap<const CFGBlock *, CFGBlock*> CFGBlockMapTy; > + > +public: > + DominatorTree(AnalysisDeclContext &ac) > + : AC(ac) {}; > + > + virtual ~DominatorTree(); > + > + /// Return the immediate dominator node given a CFGBlock. > + /// For entry block, the dominator is itself. > + /// This is the same as using operator[] on this class. > + CFGBlock *getNode(const CFGBlock *B) const; > + > + /// This returns the Entry Block for the given CFG > + CFGBlock *getRootNode() { return RootNode; } > + const CFGBlock *getRootNode() const { return RootNode; } > + > + /// Returns true iff A dominates B and A != B. > + /// Note that this is not a constant time operation. > + bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const; > + > + /// Returns true iff A dominates B. > + bool dominates(const CFGBlock *A, const CFGBlock *B) const; > + > + /// Find nearest common dominator for blocks A and B. > + /// Common dominator always exists, ex: entry block. > + const CFGBlock *findNearestCommonDominator(const CFGBlock *A, > + const CFGBlock *B) const; > + > + /// 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 BuildDominatorTree(); > + > + /// Dump the immediate dominance tree > + void dump(); > + > +private: > + AnalysisDeclContext &AC; > + CFGBlock *RootNode; > + CFGBlockMapTy IDoms; > +}; > + > +} // end namespace clang > + > +#endif > > Modified: cfe/trunk/lib/Analysis/CMakeLists.txt > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Analysis/CMakeLists.txt?rev=142885&r1=142884&r2=142885&view=diff > ============================================================================== > --- cfe/trunk/lib/Analysis/CMakeLists.txt (original) > +++ cfe/trunk/lib/Analysis/CMakeLists.txt Mon Oct 24 19:25:24 2011 > @@ -6,6 +6,7 @@ > CFGReachabilityAnalysis.cpp > CFGStmtMap.cpp > CocoaConventions.cpp > + Dominators.cpp > FormatString.cpp > LiveVariables.cpp > PostOrderCFGView.cpp > > Added: cfe/trunk/lib/Analysis/Dominators.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Analysis/Dominators.cpp?rev=142885&view=auto > ============================================================================== > --- cfe/trunk/lib/Analysis/Dominators.cpp (added) > +++ cfe/trunk/lib/Analysis/Dominators.cpp Mon Oct 24 19:25:24 2011 > @@ -0,0 +1,160 @@ > +//==- 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"; > + } > +} > + > > Modified: cfe/trunk/lib/StaticAnalyzer/Checkers/Checkers.td > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Checkers/Checkers.td?rev=142885&r1=142884&r2=142885&view=diff > ============================================================================== > --- cfe/trunk/lib/StaticAnalyzer/Checkers/Checkers.td (original) > +++ cfe/trunk/lib/StaticAnalyzer/Checkers/Checkers.td Mon Oct 24 19:25:24 2011 > @@ -359,6 +359,10 @@ > > let ParentPackage = Debug in { > > +def DominatorsTreeDumper : Checker<"DumpDominators">, > + HelpText<"Print the dominance tree for a given CFG">, > + DescFile<"DebugCheckers.cpp">; > + > def LiveVariablesDumper : Checker<"DumpLiveVars">, > HelpText<"Print results of live variable analysis">, > DescFile<"DebugCheckers.cpp">; > > Modified: cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp?rev=142885&r1=142884&r2=142885&view=diff > ============================================================================== > --- cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp (original) > +++ cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp Mon Oct 24 > 19:25:24 2011 > @@ -15,11 +15,34 @@ > #include "clang/StaticAnalyzer/Core/Checker.h" > #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" > #include "clang/Analysis/Analyses/LiveVariables.h" > +#include "clang/Analysis/Analyses/Dominators.h" > > using namespace clang; > using namespace ento; > > //===----------------------------------------------------------------------===// > +// DominatorsTreeDumper > +//===----------------------------------------------------------------------===// > + > +namespace { > +class DominatorsTreeDumper : public Checker<check::ASTCodeBody> { > +public: > + void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, > + BugReporter &BR) const { > + if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) { > + DominatorTree dom(*AC); > + dom.BuildDominatorTree(); > + dom.dump(); > + } > + } > +}; > +} > + > +void ento::registerDominatorsTreeDumper(CheckerManager &mgr) { > + mgr.registerChecker<DominatorsTreeDumper>(); > +} > + > +//===----------------------------------------------------------------------===// > // LiveVariablesDumper > //===----------------------------------------------------------------------===// > > > Added: cfe/trunk/test/Analysis/domtest.c > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/domtest.c?rev=142885&view=auto > ============================================================================== > --- cfe/trunk/test/Analysis/domtest.c (added) > +++ cfe/trunk/test/Analysis/domtest.c Mon Oct 24 19:25:24 2011 > @@ -0,0 +1,165 @@ > +// RUN: %clang -cc1 -analyze -analyzer-checker=debug.DumpDominators %s 2>&1 > | FileCheck %s > + > +// Test the DominatorsTree implementation with various control flows > +int test1() > +{ > + int x = 6; > + int y = x/2; > + int z; > + > + while(y > 0) { > + if(y < x) { > + x = x/y; > + y = y-1; > + }else{ > + z = x - y; > + } > + x = x - 1; > + x = x - 1; > + } > + z = x+y; > + z = 3; > + return 0; > +} > + > +// CHECK: Immediate dominance tree (Node#,IDom#): > +// CHECK: (0,1) > +// CHECK: (1,2) > +// CHECK: (2,8) > +// CHECK: (3,4) > +// CHECK: (4,7) > +// CHECK: (5,7) > +// CHECK: (6,7) > +// CHECK: (7,2) > +// CHECK: (8,9) > +// CHECK: (9,9) > + > +int test2() > +{ > + int x,y,z; > + > + x = 10; y = 100; > + if(x > 0){ > + y = 1; > + }else{ > + while(x<=0){ > + x++; > + y++; > + } > + } > + z = y; > + > + return 0; > +} > + > +// CHECK: Immediate dominance tree (Node#,IDom#): > +// CHECK: (0,1) > +// CHECK: (1,6) > +// CHECK: (2,6) > +// CHECK: (3,4) > +// CHECK: (4,2) > +// CHECK: (5,6) > +// CHECK: (6,7) > +// CHECK: (7,7) > + > +int test3() > +{ > + int x,y,z; > + > + x = y = z = 1; > + if(x>0) { > + while(x>=0){ > + while(y>=x) { > + x = x-1; > + y = y/2; > + } > + } > + } > + z = y; > + > + return 0; > +} > + > +// CHECK: Immediate dominance tree (Node#,IDom#): > +// CHECK: (0,1) > +// CHECK: (1,7) > +// CHECK: (2,7) > +// CHECK: (3,4) > +// CHECK: (4,2) > +// CHECK: (5,6) > +// CHECK: (6,4) > +// CHECK: (7,8) > +// CHECK: (8,8) > + > +int test4() > +{ > + int y = 3; > + while(y > 0) { > + if(y < 3) { > + while(y>0) > + y ++; > + }else{ > + while(y<10) > + y ++; > + } > + } > + return 0; > +} > + > +// CHECK: Immediate dominance tree (Node#,IDom#): > +// CHECK: (0,1) > +// CHECK: (1,2) > +// CHECK: (2,11) > +// CHECK: (3,10) > +// CHECK: (4,10) > +// CHECK: (5,6) > +// CHECK: (6,4) > +// CHECK: (7,10) > +// CHECK: (8,9) > +// CHECK: (9,7) > +// CHECK: (10,2) > +// CHECK: (11,12) > +// CHECK: (12,12) > + > +int test5() > +{ > + int x,y,z,a,b,c; > + x = 1; > + y = 2; > + z = 3; > + a = 4; > + b = 5; > + c = 6; > + if ( x < 10 ) { > + if ( y < 10 ) { > + if ( z < 10 ) { > + x = 4; > + } else { > + x = 5; > + } > + a = 10; > + } else { > + x = 6; > + } > + b = 10; > + } else { > + x = 7; > + } > + c = 11; > + return 0; > +} > + > +// CHECK: Immediate dominance tree (Node#,IDom#): > +// CHECK: (0,1) > +// CHECK: (1,10) > +// CHECK: (2,10) > +// CHECK: (3,9) > +// CHECK: (4,9) > +// CHECK: (5,8) > +// CHECK: (6,8) > +// CHECK: (7,8) > +// CHECK: (8,9) > +// CHECK: (9,10) > +// CHECK: (10,11) > +// CHECK: (11,11) > + > > > _______________________________________________ > cfe-commits mailing list > [email protected] > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
