Clang Project

clang_source_code/include/clang/Analysis/Analyses/Dominators.h
1//- Dominators.h - Implementation of dominators tree for Clang CFG -*- C++ -*-//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the dominators tree functionality for Clang CFGs.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
14#define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
15
16#include "clang/Analysis/AnalysisDeclContext.h"
17#include "clang/Analysis/CFG.h"
18#include "llvm/ADT/DepthFirstIterator.h"
19#include "llvm/ADT/GraphTraits.h"
20#include "llvm/ADT/iterator.h"
21#include "llvm/Support/GenericDomTree.h"
22#include "llvm/Support/GenericDomTreeConstruction.h"
23#include "llvm/Support/raw_ostream.h"
24
25// FIXME: There is no good reason for the domtree to require a print method
26// which accepts an LLVM Module, so remove this (and the method's argument that
27// needs it) when that is fixed.
28
29namespace llvm {
30
31class Module;
32
33} // namespace llvm
34
35namespace clang {
36
37using DomTreeNode = llvm::DomTreeNodeBase<CFGBlock>;
38
39/// Concrete subclass of DominatorTreeBase for Clang
40/// This class implements the dominators tree functionality given a Clang CFG.
41///
42class DominatorTree : public ManagedAnalysis {
43  virtual void anchor();
44
45public:
46  llvm::DomTreeBase<CFGBlock> *DT;
47
48  DominatorTree() {
49    DT = new llvm::DomTreeBase<CFGBlock>();
50  }
51
52  ~DominatorTree() override { delete DT; }
53
54  llvm::DomTreeBase<CFGBlock>& getBase() { return *DT; }
55
56  /// This method returns the root CFGBlock of the dominators tree.
57  CFGBlock *getRoot() const {
58    return DT->getRoot();
59  }
60
61  /// This method returns the root DomTreeNode, which is the wrapper
62  /// for CFGBlock.
63  DomTreeNode *getRootNode() const {
64    return DT->getRootNode();
65  }
66
67  /// This method compares two dominator trees.
68  /// The method returns false if the other dominator tree matches this
69  /// dominator tree, otherwise returns true.
70  bool compare(DominatorTree &Other) const {
71    DomTreeNode *R = getRootNode();
72    DomTreeNode *OtherR = Other.getRootNode();
73
74    if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
75      return true;
76
77    if (DT->compare(Other.getBase()))
78      return true;
79
80    return false;
81  }
82
83  /// This method builds the dominator tree for a given CFG
84  /// The CFG information is passed via AnalysisDeclContext
85  void buildDominatorTree(AnalysisDeclContext &AC) {
86    cfg = AC.getCFG();
87    DT->recalculate(*cfg);
88  }
89
90  /// This method dumps immediate dominators for each block,
91  /// mainly used for debug purposes.
92  void dump() {
93    llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n";
94    for (CFG::const_iterator I = cfg->begin(),
95        E = cfg->end(); I != E; ++I) {
96      if(DT->getNode(*I)->getIDom())
97        llvm::errs() << "(" << (*I)->getBlockID()
98                     << ","
99                     << DT->getNode(*I)->getIDom()->getBlock()->getBlockID()
100                     << ")\n";
101      else llvm::errs() << "(" << (*I)->getBlockID()
102                        << "," << (*I)->getBlockID() << ")\n";
103    }
104  }
105
106  /// This method tests if one CFGBlock dominates the other.
107  /// The method return true if A dominates B, false otherwise.
108  /// Note a block always dominates itself.
109  bool dominates(const CFGBlock *A, const CFGBlock *B) const {
110    return DT->dominates(A, B);
111  }
112
113  /// This method tests if one CFGBlock properly dominates the other.
114  /// The method return true if A properly dominates B, false otherwise.
115  bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {
116    return DT->properlyDominates(A, B);
117  }
118
119  /// This method finds the nearest common dominator CFG block
120  /// for CFG block A and B. If there is no such block then return NULL.
121  CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
122    return DT->findNearestCommonDominator(A, B);
123  }
124
125  const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
126                                             const CFGBlock *B) {
127    return DT->findNearestCommonDominator(A, B);
128  }
129
130  /// This method is used to update the dominator
131  /// tree information when a node's immediate dominator changes.
132  void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
133    DT->changeImmediateDominator(N, NewIDom);
134  }
135
136  /// This method tests if the given CFGBlock can be reachable from root.
137  /// Returns true if reachable, false otherwise.
138  bool isReachableFromEntry(const CFGBlock *A) {
139    return DT->isReachableFromEntry(A);
140  }
141
142  /// This method releases the memory held by the dominator tree.
143  virtual void releaseMemory() {
144    DT->releaseMemory();
145  }
146
147  /// This method converts the dominator tree to human readable form.
148  virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
149    DT->print(OS);
150  }
151
152private:
153  CFG *cfg;
154};
155
156} // namespace clang
157
158//===-------------------------------------
159/// DominatorTree GraphTraits specialization so the DominatorTree can be
160/// iterable by generic graph iterators.
161///
162namespace llvm {
163
164template <> struct GraphTraits< ::clang::DomTreeNode* > {
165  using NodeRef = ::clang::DomTreeNode *;
166  using ChildIteratorType = ::clang::DomTreeNode::iterator;
167
168  static NodeRef getEntryNode(NodeRef N) { return N; }
169  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
170  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
171
172  using nodes_iterator =
173      llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
174
175  static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
176    return nodes_iterator(df_begin(getEntryNode(N)));
177  }
178
179  static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
180    return nodes_iterator(df_end(getEntryNode(N)));
181  }
182};
183
184template <> struct GraphTraits< ::clang::DominatorTree* >
185    : public GraphTraits< ::clang::DomTreeNode* > {
186  static NodeRef getEntryNode(::clang::DominatorTree *DT) {
187    return DT->getRootNode();
188  }
189
190  static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
191    return nodes_iterator(df_begin(getEntryNode(N)));
192  }
193
194  static nodes_iterator nodes_end(::clang::DominatorTree *N) {
195    return nodes_iterator(df_end(getEntryNode(N)));
196  }
197};
198
199} // namespace llvm
200
201#endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
202
clang::DominatorTree::anchor
clang::DominatorTree::DT
clang::DominatorTree::getBase
clang::DominatorTree::getRoot
clang::DominatorTree::getRootNode
clang::DominatorTree::compare
clang::DominatorTree::buildDominatorTree
clang::DominatorTree::dump
clang::DominatorTree::dominates
clang::DominatorTree::properlyDominates
clang::DominatorTree::findNearestCommonDominator
clang::DominatorTree::findNearestCommonDominator
clang::DominatorTree::changeImmediateDominator
clang::DominatorTree::isReachableFromEntry
clang::DominatorTree::releaseMemory
clang::DominatorTree::print
clang::DominatorTree::cfg
CodeThinker, Enjoy your reading code