1 /*
2 * Copyright (c) 2021-2025 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 ark::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 dfsBlocks = static_cast<size_t>(dfsNum_);
34 ASSERT_PRINT(dfsBlocks == (GetGraph()->GetBlocksRPO().size() - 1), "There is an unreachable block");
35
36 for (size_t i = dfsBlocks; i > 0; i--) {
37 ComputeImmediateDominators(GetVertex(i));
38 }
39
40 for (size_t i = 1; i <= dfsBlocks; 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, parent);
87 } else {
88 SetIdom(v, eval);
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 dfsNum_++;
117 ASSERT_PRINT(static_cast<size_t>(dfsNum_) < vertices_->size(), "DFS-number overflow");
118 ASSERT(block != nullptr);
119
120 SetVertex(dfsNum_, block);
121 SetLabel(block, block);
122 SetSemi(block, dfsNum_);
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 blocksCount)151 void DominatorsTree::Init(size_t blocksCount)
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 auto maxSize = GetGraph()->GetVectorBlocks().size();
163 if (blocksCount > maxSize) {
164 blocksCount = maxSize;
165 }
166 ancestors_->resize(blocksCount);
167 idoms_->resize(blocksCount);
168 labels_->resize(blocksCount);
169 parents_->resize(blocksCount);
170 vertices_->resize(blocksCount);
171 semi_->resize(blocksCount);
172
173 std::fill(vertices_->begin(), vertices_->end(), nullptr);
174 std::fill(semi_->begin(), semi_->end(), DEFAULT_DFS_VAL);
175
176 buckets_->resize(blocksCount, BlocksVector(allocator->Adapter()));
177 for (auto &bucket : *buckets_) {
178 bucket.clear();
179 }
180
181 dfsNum_ = DEFAULT_DFS_VAL;
182 }
183
184 /* static */
SetDomPair(BasicBlock * dominator,BasicBlock * block)185 void DominatorsTree::SetDomPair(BasicBlock *dominator, BasicBlock *block)
186 {
187 ASSERT(block != nullptr);
188 block->SetDominator(dominator);
189 ASSERT(dominator != nullptr);
190 dominator->AddDominatedBlock(block);
191 }
192
193 /*
194 * Check if there is path from `start_block` to `target_block` excluding `exclude_block`
195 */
IsPathBetweenBlocks(BasicBlock * startBlock,BasicBlock * targetBlock,BasicBlock * excludeBlock)196 static bool IsPathBetweenBlocks(BasicBlock *startBlock, BasicBlock *targetBlock, BasicBlock *excludeBlock)
197 {
198 auto markerHolder = MarkerHolder(targetBlock->GetGraph());
199 auto marker = markerHolder.GetMarker();
200 return BlocksPathDfsSearch(marker, startBlock, targetBlock, excludeBlock);
201 }
202
UpdateAfterResolverInsertion(BasicBlock * predecessor,BasicBlock * successor,BasicBlock * resolver)203 void DominatorsTree::UpdateAfterResolverInsertion(BasicBlock *predecessor, BasicBlock *successor, BasicBlock *resolver)
204 {
205 SetValid(true);
206 SetDomPair(predecessor, resolver);
207
208 if (successor->GetDominator() == predecessor) {
209 bool resolverDominatePhiBlock = true;
210 for (auto succ : predecessor->GetSuccsBlocks()) {
211 if (succ == resolver) {
212 continue;
213 }
214 if (IsPathBetweenBlocks(succ, successor, resolver)) {
215 resolverDominatePhiBlock = false;
216 break;
217 }
218 }
219
220 if (resolverDominatePhiBlock) {
221 predecessor->RemoveDominatedBlock(successor);
222 SetDomPair(resolver, successor);
223 }
224 }
225 }
226
227 /* static */
GetBlockId(BasicBlock * block)228 inline uint32_t DominatorsTree::GetBlockId(BasicBlock *block)
229 {
230 return block->GetId();
231 }
232 } // namespace ark::compiler
233