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