• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 #include "optimizer/ir/basicblock.h"
17 #include "optimizer/ir/graph.h"
18 #include "optimizer/analysis/rpo.h"
19 #include "dominators_tree.h"
20 
21 namespace panda::compiler {
DominatorsTree(Graph * graph)22 DominatorsTree::DominatorsTree(Graph *graph) : Analysis(graph) {}
23 
RunImpl()24 bool DominatorsTree::RunImpl()
25 {
26     for (auto block : GetGraph()->GetBlocksRPO()) {
27         block->ClearDominatedBlocks();
28         block->ClearDominator();
29     }
30 
31     Init(GetGraph()->GetVectorBlocks().size());
32     DfsNumbering(GetGraph()->GetStartBlock());
33     auto dfs_blocks = static_cast<size_t>(dfs_num_);
34     ASSERT_PRINT(dfs_blocks == (GetGraph()->GetBlocksRPO().size() - 1), "There is an unreachable block");
35 
36     for (size_t i = dfs_blocks; i > 0; i--) {
37         ComputeImmediateDominators(GetVertex(i));
38     }
39 
40     for (size_t i = 1; i <= dfs_blocks; i++) {
41         AdjustImmediateDominators(GetVertex(i));
42     }
43     return true;
44 }
45 
46 /*
47  * Adjust immediate dominators,
48  * Update dominator information for 'block'
49  */
AdjustImmediateDominators(BasicBlock * block)50 void DominatorsTree::AdjustImmediateDominators(BasicBlock *block)
51 {
52     ASSERT(block != nullptr);
53 
54     if (GetIdom(block) != GetVertex(GetSemi(block))) {
55         SetIdom(block, GetIdom(GetIdom(block)));
56     }
57     SetDomPair(GetIdom(block), block);
58 }
59 
60 /*
61  * Compute initial values for semidominators,
62  * store blocks with the same semidominator in the same bucket,
63  * compute immediate dominators for blocks in the bucket of 'block' parent
64  */
ComputeImmediateDominators(BasicBlock * block)65 void DominatorsTree::ComputeImmediateDominators(BasicBlock *block)
66 {
67     ASSERT(block != nullptr);
68 
69     for (auto pred : block->GetPredsBlocks()) {
70         auto eval = Eval(pred);
71         if (GetSemi(eval) < GetSemi(block)) {
72             SetSemi(block, GetSemi(eval));
73         }
74     }
75 
76     auto vertex = GetVertex(GetSemi(block));
77     GetBucket(vertex).push_back(block);
78     auto parent = GetParent(block);
79     Link(parent, block);
80 
81     auto &bucket = GetBucket(parent);
82     while (!bucket.empty()) {
83         auto v = *bucket.rbegin();
84         auto eval = Eval(v);
85         if (GetSemi(eval) < GetSemi(v)) {
86             SetIdom(v, eval);
87         } else {
88             SetIdom(v, parent);
89         }
90         bucket.pop_back();
91     }
92 }
93 
94 /*
95  * Compress ancestor path to 'block' to the block whose label has the maximal semidominator number
96  */
Compress(BasicBlock * block)97 void DominatorsTree::Compress(BasicBlock *block)
98 {
99     auto anc = GetAncestor(block);
100     ASSERT(anc != nullptr);
101 
102     if (GetAncestor(anc) != nullptr) {
103         Compress(anc);
104         if (GetSemi(GetLabel(anc)) < GetSemi(GetLabel(block))) {
105             SetLabel(block, GetLabel(anc));
106         }
107         SetAncestor(block, GetAncestor(anc));
108     }
109 }
110 
111 /*
112  *  Depth-first search with numbering blocks in order they are reaching
113  */
DfsNumbering(BasicBlock * block)114 void DominatorsTree::DfsNumbering(BasicBlock *block)
115 {
116     dfs_num_++;
117     ASSERT_PRINT(static_cast<size_t>(dfs_num_) < vertices_->size(), "DFS-number overflow");
118     ASSERT(block != nullptr);
119 
120     SetVertex(dfs_num_, block);
121     SetLabel(block, block);
122     SetSemi(block, dfs_num_);
123     SetAncestor(block, nullptr);
124 
125     for (auto succ : block->GetSuccsBlocks()) {
126         if (GetSemi(succ) == DEFAULT_DFS_VAL) {
127             SetParent(succ, block);
128             DfsNumbering(succ);
129         }
130     }
131 }
132 
133 /*
134  * Return 'block' if it is the root of a tree
135  * Otherwise, after tree compressing
136  * return the block in the ancestors chain with the minimal semidominator DFS-number
137  */
Eval(BasicBlock * block)138 BasicBlock *DominatorsTree::Eval(BasicBlock *block)
139 {
140     ASSERT(block != nullptr);
141     if (GetAncestor(block) == nullptr) {
142         return block;
143     }
144     Compress(block);
145     return GetLabel(block);
146 }
147 
148 /*
149  * Initialize data structures to start DFS
150  */
Init(size_t blocks_count)151 void DominatorsTree::Init(size_t blocks_count)
152 {
153     auto allocator = GetGraph()->GetLocalAllocator();
154     ancestors_ = allocator->New<BlocksVector>(allocator->Adapter());
155     buckets_ = allocator->New<ArenaVector<BlocksVector>>(allocator->Adapter());
156     idoms_ = allocator->New<BlocksVector>(allocator->Adapter());
157     labels_ = allocator->New<BlocksVector>(allocator->Adapter());
158     parents_ = allocator->New<BlocksVector>(allocator->Adapter());
159     semi_ = allocator->New<ArenaVector<int32_t>>(allocator->Adapter());
160     vertices_ = allocator->New<BlocksVector>(allocator->Adapter());
161 
162     ancestors_->resize(blocks_count);
163     idoms_->resize(blocks_count);
164     labels_->resize(blocks_count);
165     parents_->resize(blocks_count);
166     vertices_->resize(blocks_count);
167     semi_->resize(blocks_count);
168 
169     std::fill(vertices_->begin(), vertices_->end(), nullptr);
170     std::fill(semi_->begin(), semi_->end(), DEFAULT_DFS_VAL);
171 
172     buckets_->resize(blocks_count, BlocksVector(allocator->Adapter()));
173     for (auto &bucket : *buckets_) {
174         bucket.clear();
175     }
176 
177     dfs_num_ = DEFAULT_DFS_VAL;
178 }
179 
180 /* static */
SetDomPair(BasicBlock * dominator,BasicBlock * block)181 void DominatorsTree::SetDomPair(BasicBlock *dominator, BasicBlock *block)
182 {
183     block->SetDominator(dominator);
184     dominator->AddDominatedBlock(block);
185 }
186 
187 /*
188  * Check if there is path from `start_block` to `target_block` excluding `exclude_block`
189  */
IsPathBetweenBlocks(BasicBlock * start_block,BasicBlock * target_block,BasicBlock * exclude_block)190 static bool IsPathBetweenBlocks(BasicBlock *start_block, BasicBlock *target_block, BasicBlock *exclude_block)
191 {
192     auto marker_holder = MarkerHolder(target_block->GetGraph());
193     auto marker = marker_holder.GetMarker();
194     return BlocksPathDfsSearch(marker, start_block, target_block, exclude_block);
195 }
196 
UpdateAfterResolverInsertion(BasicBlock * predecessor,BasicBlock * successor,BasicBlock * resolver)197 void DominatorsTree::UpdateAfterResolverInsertion(BasicBlock *predecessor, BasicBlock *successor, BasicBlock *resolver)
198 {
199     SetValid(true);
200     SetDomPair(predecessor, resolver);
201 
202     if (successor->GetDominator() == predecessor) {
203         bool resolver_dominate_phi_block = true;
204         for (auto succ : predecessor->GetSuccsBlocks()) {
205             if (succ == resolver) {
206                 continue;
207             }
208             if (IsPathBetweenBlocks(succ, successor, resolver)) {
209                 resolver_dominate_phi_block = false;
210                 break;
211             }
212         }
213 
214         if (resolver_dominate_phi_block) {
215             predecessor->RemoveDominatedBlock(successor);
216             SetDomPair(resolver, successor);
217         }
218     }
219 }
220 
221 /* static */
GetBlockId(BasicBlock * block)222 inline uint32_t DominatorsTree::GetBlockId(BasicBlock *block)
223 {
224     return block->GetId();
225 }
226 }  // namespace panda::compiler
227