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
