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 
23 namespace spvtools {
24 namespace opt {
25 
26 // Interface to perform dominator or postdominator analysis on a given function.
27 class DominatorAnalysisBase {
28  public:
DominatorAnalysisBase(bool is_post_dom)29   explicit DominatorAnalysisBase(bool is_post_dom) : tree_(is_post_dom) {}
30 
31   // Calculates the dominator (or postdominator) tree for given function |f|.
InitializeTree(const CFG & cfg,const 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|.
Dominates(const BasicBlock * a,const 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.
Dominates(uint32_t a,uint32_t b)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|.
StrictlyDominates(const BasicBlock * a,const 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.
StrictlyDominates(uint32_t a,uint32_t b)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.
ImmediateDominator(const BasicBlock * node)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.
ImmediateDominator(uint32_t node_id)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.
IsReachable(const BasicBlock * node)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.
IsReachable(uint32_t node_id)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.
DumpAsDot(std::ostream & out)89   inline void DumpAsDot(std::ostream& out) const { tree_.DumpTreeAsDot(out); }
90 
91   // Returns true if this is a postdomiator tree.
IsPostDominator()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.
GetDomTree()97   inline DominatorTree& GetDomTree() { return tree_; }
GetDomTree()98   inline const DominatorTree& GetDomTree() const { return tree_; }
99 
100   // Force the dominator tree to be removed
ClearTree()101   inline void ClearTree() { tree_.ClearTree(); }
102 
103   // Applies the std::function |func| to dominator tree nodes in dominator
104   // order.
Visit(std::function<bool (DominatorTreeNode *)> func)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.
Visit(std::function<bool (const DominatorTreeNode *)> func)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.
124 class DominatorAnalysis : public DominatorAnalysisBase {
125  public:
DominatorAnalysis()126   DominatorAnalysis() : DominatorAnalysisBase(false) {}
127 };
128 
129 // Derived class for postdominator analysis.
130 class PostDominatorAnalysis : public DominatorAnalysisBase {
131  public:
PostDominatorAnalysis()132   PostDominatorAnalysis() : DominatorAnalysisBase(true) {}
133 };
134 
135 }  // namespace opt
136 }  // namespace spvtools
137 
138 #endif  // SOURCE_OPT_DOMINATOR_ANALYSIS_H_
139