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