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