Dominators.h revision 790c372f38bcc85927feae107d1e0bacae5dfbc1
1//==- Dominators.h - Construct the Dominance Tree Given CFG -----*- C++ --*-==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements a simple, fast dominance algorithm for source-level CFGs. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_CLANG_DOMINATORS_H 15#define LLVM_CLANG_DOMINATORS_H 16 17#include "clang/Analysis/CFG.h" 18#include "clang/Analysis/AnalysisContext.h" 19#include "llvm/ADT/DenseMap.h" 20 21namespace clang { 22 23class CFG; 24class CFGBlock; 25 26class DominatorTree : public ManagedAnalysis { 27 typedef llvm::DenseMap<const CFGBlock *, CFGBlock*> CFGBlockMapTy; 28 29public: 30 DominatorTree(AnalysisDeclContext &ac) 31 : AC(ac) {} 32 33 virtual ~DominatorTree(); 34 35 /// Return the immediate dominator node given a CFGBlock. 36 /// For entry block, the dominator is itself. 37 /// This is the same as using operator[] on this class. 38 CFGBlock *getNode(const CFGBlock *B) const; 39 40 /// This returns the Entry Block for the given CFG 41 CFGBlock *getRootNode() { return RootNode; } 42 const CFGBlock *getRootNode() const { return RootNode; } 43 44 /// Returns true iff A dominates B and A != B. 45 /// Note that this is not a constant time operation. 46 bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const; 47 48 /// Returns true iff A dominates B. 49 bool dominates(const CFGBlock *A, const CFGBlock *B) const; 50 51 /// Find nearest common dominator for blocks A and B. 52 /// Common dominator always exists, ex: entry block. 53 const CFGBlock *findNearestCommonDominator(const CFGBlock *A, 54 const CFGBlock *B) const; 55 56 /// Constructs immediate dominator tree for a given CFG based on the algorithm 57 /// described in this paper: 58 /// 59 /// A Simple, Fast Dominance Algorithm 60 /// Keith D. Cooper, Timothy J. Harvey and Ken Kennedy 61 /// Software-Practice and Expreience, 2001;4:1-10. 62 /// 63 /// This implementation is simple and runs faster in practice than the classis 64 /// Lengauer-Tarjan algorithm. For detailed discussions, refer to the paper. 65 void BuildDominatorTree(); 66 67 /// Dump the immediate dominance tree 68 void dump(); 69 70private: 71 AnalysisDeclContext &AC; 72 CFGBlock *RootNode; 73 CFGBlockMapTy IDoms; 74}; 75 76} // end namespace clang 77 78#endif 79 80