1// Copyright (c) 2017 Google Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#ifndef SOURCE_OPT_DOMINATOR_ANALYSIS_H_
16#define SOURCE_OPT_DOMINATOR_ANALYSIS_H_
17
18#include <cstdint>
19#include <map>
20
21#include "source/opt/dominator_tree.h"
22
23namespace spvtools {
24namespace opt {
25
26// Interface to perform dominator or postdominator analysis on a given function.
27class DominatorAnalysisBase {
28 public:
29 explicit DominatorAnalysisBase(bool is_post_dom) : tree_(is_post_dom) {}
30
31 // Calculates the dominator (or postdominator) tree for given function |f|.
32 inline void InitializeTree(const CFG& cfg, const Function* f) {
33 tree_.InitializeTree(cfg, f);
34 }
35
36 // Returns true if BasicBlock |a| dominates BasicBlock |b|.
37 inline bool Dominates(const BasicBlock* a, const BasicBlock* b) const {
38 if (!a || !b) return false;
39 return Dominates(a->id(), b->id());
40 }
41
42 // Returns true if BasicBlock |a| dominates BasicBlock |b|. Same as above only
43 // using the BasicBlock IDs.
44 inline bool Dominates(uint32_t a, uint32_t b) const {
45 return tree_.Dominates(a, b);
46 }
47
48 // Returns true if instruction |a| dominates instruction |b|.
49 bool Dominates(Instruction* a, Instruction* b) const;
50
51 // Returns true if BasicBlock |a| strictly dominates BasicBlock |b|.
52 inline bool StrictlyDominates(const BasicBlock* a,
53 const BasicBlock* b) const {
54 if (!a || !b) return false;
55 return StrictlyDominates(a->id(), b->id());
56 }
57
58 // Returns true if BasicBlock |a| strictly dominates BasicBlock |b|. Same as
59 // above only using the BasicBlock IDs.
60 inline bool StrictlyDominates(uint32_t a, uint32_t b) const {
61 return tree_.StrictlyDominates(a, b);
62 }
63
64 // Returns the immediate dominator of |node| or returns nullptr if it is has
65 // no dominator.
66 inline BasicBlock* ImmediateDominator(const BasicBlock* node) const {
67 if (!node) return nullptr;
68 return tree_.ImmediateDominator(node);
69 }
70
71 // Returns the immediate dominator of |node_id| or returns nullptr if it is
72 // has no dominator. Same as above but operates on IDs.
73 inline BasicBlock* ImmediateDominator(uint32_t node_id) const {
74 return tree_.ImmediateDominator(node_id);
75 }
76
77 // Returns true if |node| is reachable from the entry.
78 inline bool IsReachable(const BasicBlock* node) const {
79 if (!node) return false;
80 return tree_.ReachableFromRoots(node->id());
81 }
82
83 // Returns true if |node_id| is reachable from the entry.
84 inline bool IsReachable(uint32_t node_id) const {
85 return tree_.ReachableFromRoots(node_id);
86 }
87
88 // Dump the tree structure into the given |out| stream in the dot format.
89 inline void DumpAsDot(std::ostream& out) const { tree_.DumpTreeAsDot(out); }
90
91 // Returns true if this is a postdomiator tree.
92 inline bool IsPostDominator() const { return tree_.IsPostDominator(); }
93
94 // Returns the tree itself for manual operations, such as traversing the
95 // roots.
96 // For normal dominance relationships the methods above should be used.
97 inline DominatorTree& GetDomTree() { return tree_; }
98 inline const DominatorTree& GetDomTree() const { return tree_; }
99
100 // Force the dominator tree to be removed
101 inline void ClearTree() { tree_.ClearTree(); }
102
103 // Applies the std::function |func| to dominator tree nodes in dominator
104 // order.
105 void Visit(std::function<bool(DominatorTreeNode*)> func) {
106 tree_.Visit(func);
107 }
108
109 // Applies the std::function |func| to dominator tree nodes in dominator
110 // order.
111 void Visit(std::function<bool(const DominatorTreeNode*)> func) const {
112 tree_.Visit(func);
113 }
114
115 // Returns the most immediate basic block that dominates both |b1| and |b2|.
116 // If there is no such basic block, nullptr is returned.
117 BasicBlock* CommonDominator(BasicBlock* b1, BasicBlock* b2) const;
118
119 protected:
120 DominatorTree tree_;
121};
122
123// Derived class for normal dominator analysis.
124class DominatorAnalysis : public DominatorAnalysisBase {
125 public:
126 DominatorAnalysis() : DominatorAnalysisBase(false) {}
127};
128
129// Derived class for postdominator analysis.
130class PostDominatorAnalysis : public DominatorAnalysisBase {
131 public:
132 PostDominatorAnalysis() : DominatorAnalysisBase(true) {}
133};
134
135} // namespace opt
136} // namespace spvtools
137
138#endif // SOURCE_OPT_DOMINATOR_ANALYSIS_H_
139