Thanks for pointing out this. I shall do the refactoring. Chris, why do you think this implementation is slower than the version in llvm/Analysis (based on the classical Lengauer-Tarjan algorithm)? My patch was based on this 2001 paper: K. D. Cooper "A Simple, Fast Dominance Algorithm", which actually included an interesting analysis and comparison with the classical Lengauer-Tarjan algorithm. I believe the implementation in core LLVM shall be very stable and efficient. I am just interested in know why choosing this.
-- Guoping 2011/10/24 Ted Kremenek <[email protected]> > Good point Chris. I think reusing the existing dominators logic in > llvm/Analysis makes good sense. We already implement several graph traits > already for the source level CFG. > > Guoping: now that we have this base implementation, including API, in > Clang, would you be interested in refactoring it to use the dominators logic > in llvm/Analysis. Otherwise, I'll look into refactoring it. > > Sent from my iPad > > On Oct 24, 2011, at 5:33 PM, Chris Lattner <[email protected]> wrote: > > > > > 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
