| 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: |
| 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. |
| 124 |
class DominatorAnalysis : public DominatorAnalysisBase { |
| 125 |
public: |
| 126 |
DominatorAnalysis() : DominatorAnalysisBase(false) {} |
| 127 |
}; |
| 128 |
|
| 129 |
// Derived class for postdominator analysis. |
| 130 |
class 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_ |