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