1 /* 2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd. 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 16 #ifndef COMPILER_OPTIMIZER_ANALYSIS_DOMINATORS_TREE_H 17 #define COMPILER_OPTIMIZER_ANALYSIS_DOMINATORS_TREE_H 18 19 #include "optimizer/pass.h" 20 #include "utils/arena_containers.h" 21 22 namespace ark::compiler { 23 class BasicBlock; 24 class Graph; 25 26 /// This class builds dominators tree, using Lengauer-Tarjan algorithm 27 class DominatorsTree : public Analysis { 28 public: 29 using BlocksVector = ArenaVector<BasicBlock *>; 30 31 explicit DominatorsTree(Graph *graph); 32 33 NO_MOVE_SEMANTIC(DominatorsTree); 34 NO_COPY_SEMANTIC(DominatorsTree); 35 ~DominatorsTree() override = default; 36 37 bool RunImpl() override; 38 GetPassName()39 const char *GetPassName() const override 40 { 41 return "DominatorTree"; 42 } 43 44 static void SetDomPair(BasicBlock *dominator, BasicBlock *block); 45 46 void UpdateAfterResolverInsertion(BasicBlock *predecessor, BasicBlock *successor, BasicBlock *resolver); 47 48 private: 49 /* 50 * The ancestor of 'block', nullptr for the tree root 51 */ SetAncestor(BasicBlock * dest,BasicBlock * block)52 void SetAncestor(BasicBlock *dest, BasicBlock *block) 53 { 54 (*ancestors_)[GetBlockId(dest)] = block; 55 } GetAncestor(BasicBlock * block)56 BasicBlock *GetAncestor(BasicBlock *block) const 57 { 58 return (*ancestors_)[GetBlockId(block)]; 59 } 60 61 /* 62 * A set of blocks whose semidominator is 'block' 63 */ GetBucket(BasicBlock * block)64 BlocksVector &GetBucket(BasicBlock *block) 65 { 66 return (*buckets_)[GetBlockId(block)]; 67 } 68 69 /* 70 * The immediate dominator of 'block' 71 */ SetIdom(BasicBlock * dest,BasicBlock * block)72 void SetIdom(BasicBlock *dest, BasicBlock *block) 73 { 74 (*idoms_)[GetBlockId(dest)] = block; 75 } GetIdom(BasicBlock * block)76 BasicBlock *GetIdom(BasicBlock *block) const 77 { 78 return (*idoms_)[GetBlockId(block)]; 79 } 80 81 /* 82 * The block in the ancestors chain with the minimal semidominator DFS-number for 'block' 83 */ SetLabel(BasicBlock * dest,BasicBlock * block)84 void SetLabel(BasicBlock *dest, BasicBlock *block) 85 { 86 (*labels_)[GetBlockId(dest)] = block; 87 } GetLabel(BasicBlock * block)88 BasicBlock *GetLabel(BasicBlock *block) const 89 { 90 return (*labels_)[GetBlockId(block)]; 91 } 92 93 /* 94 * The parent of 'block' in the spanning tree generated by DFS 95 */ SetParent(BasicBlock * dest,BasicBlock * block)96 void SetParent(BasicBlock *dest, BasicBlock *block) 97 { 98 (*parents_)[GetBlockId(dest)] = block; 99 } GetParent(BasicBlock * block)100 BasicBlock *GetParent(BasicBlock *block) const 101 { 102 return (*parents_)[GetBlockId(block)]; 103 } 104 105 /* 106 * The DFS-number of the semidominator of 'block' 107 */ SetSemi(BasicBlock * dest,int32_t value)108 void SetSemi(BasicBlock *dest, int32_t value) 109 { 110 (*semi_)[GetBlockId(dest)] = value; 111 } GetSemi(BasicBlock * block)112 int32_t GetSemi(BasicBlock *block) const 113 { 114 return (*semi_)[GetBlockId(block)]; 115 } 116 117 /* 118 * The block whose DFS-number is 'index' 119 */ SetVertex(size_t index,BasicBlock * block)120 void SetVertex(size_t index, BasicBlock *block) 121 { 122 (*vertices_)[index] = block; 123 } GetVertex(size_t index)124 BasicBlock *GetVertex(size_t index) const 125 { 126 return (*vertices_)[index]; 127 } 128 129 void AdjustImmediateDominators(BasicBlock *block); 130 void ComputeImmediateDominators(BasicBlock *block); 131 void Compress(BasicBlock *block); 132 void DfsNumbering(BasicBlock *block); 133 BasicBlock *Eval(BasicBlock *block); 134 void Init(size_t blocksCount); Link(BasicBlock * parent,BasicBlock * block)135 void Link(BasicBlock *parent, BasicBlock *block) 136 { 137 SetAncestor(block, parent); 138 } 139 static uint32_t GetBlockId(BasicBlock *block); 140 141 private: 142 static constexpr int32_t DEFAULT_DFS_VAL = -1; 143 // number of the block according to the order it is reached during the DFS 144 int32_t dfsNum_ {DEFAULT_DFS_VAL}; 145 BlocksVector *ancestors_ {nullptr}; 146 ArenaVector<BlocksVector> *buckets_ {nullptr}; 147 BlocksVector *idoms_ {nullptr}; 148 BlocksVector *labels_ {nullptr}; 149 BlocksVector *parents_ {nullptr}; 150 ArenaVector<int32_t> *semi_ {nullptr}; 151 BlocksVector *vertices_ {nullptr}; 152 }; 153 } // namespace ark::compiler 154 155 #endif // COMPILER_OPTIMIZER_ANALYSIS_DOMINATORS_TREE_H 156