Dominators.h revision 58f6f1e37ab32fdd0c8bab6771d8e09bc139e9ed 
1//==- Dominators.cpp - 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//==- Dominators.cpp - Construct the Dominance Tree Given CFG ----*- C++ --*-==//
80//
81//                     The LLVM Compiler Infrastructure
82//
83// This file is distributed under the University of Illinois Open Source
84// License. See LICENSE.TXT for details.
85//
86//===----------------------------------------------------------------------===//
87//
88// This file implements a simple, fast dominance algorithm for source-level CFGs.
89//
90//===----------------------------------------------------------------------===//
91
92#ifndef LLVM_CLANG_DOMINATORS_H
93#define LLVM_CLANG_DOMINATORS_H
94
95#include "clang/Analysis/CFG.h"
96#include "clang/Analysis/AnalysisDeclContext.h"
97#include "llvm/ADT/DenseMap.h"
98
99namespace clang {
100
101class CFG;
102class CFGBlock;
103
104class DominatorTree : public ManagedAnalysis {
105  typedef llvm::DenseMap<const CFGBlock *, CFGBlock*> CFGBlockMapTy;
106
107public:
108  DominatorTree(AnalysisDeclContext &ac)
109      : AC(ac) {};
110
111  virtual ~DominatorTree();
112
113  /// Return the immediate dominator node given a CFGBlock.
114  /// For entry block, the dominator is itself.
115  /// This is the same as using operator[] on this class.
116  CFGBlock *getNode(const CFGBlock *B) const;
117
118  /// This returns the Entry Block for the given CFG
119  CFGBlock *getRootNode() { return RootNode; }
120  const CFGBlock *getRootNode() const { return RootNode; }
121
122  /// Returns true iff A dominates B and A != B.
123  /// Note that this is not a constant time operation.
124  bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const;
125
126  /// Returns true iff A dominates B.
127  bool dominates(const CFGBlock *A, const CFGBlock *B) const;
128
129  /// Find nearest common dominator for blocks A and B.
130  /// Common dominator always exists, ex: entry block.
131  const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
132                                       const CFGBlock *B) const;
133
134  /// Constructs immediate dominator tree for a given CFG based on the algorithm
135  /// described in this paper:
136  ///
137  ///  A Simple, Fast Dominance Algorithm
138  ///  Keith D. Cooper, Timothy J. Harvey and Ken Kennedy
139  ///  Software-Practice and Expreience, 2001;4:1-10.
140  ///
141  /// This implementation is simple and runs faster in practice than the classis
142  /// Lengauer-Tarjan algorithm. For detailed discussions, refer to the paper.
143  void BuildDominatorTree();
144
145  /// Dump the immediate dominance tree
146  void dump();
147
148private:
149  AnalysisDeclContext &AC;
150  CFGBlock *RootNode;
151  CFGBlockMapTy IDoms;
152};
153
154} // end namespace clang
155
156#endif
157