1 /*
2 * Copyright (c) 2023 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 "cg_dominance.h"
17 #include "cgfunc.h"
18
19 /*
20 * This phase build dominance
21 */
22 namespace maplebe {
23 constexpr uint32 kBBVectorInitialSize = 2;
PostOrderWalk(const BB & bb,int32 & pid,MapleVector<bool> & visitedMap)24 void DomAnalysis::PostOrderWalk(const BB &bb, int32 &pid, MapleVector<bool> &visitedMap)
25 {
26 std::stack<const BB*> s;
27 s.push(&bb);
28 visitedMap[bb.GetId()] = true;
29 while (!s.empty()) {
30 auto node = s.top();
31 auto nodeId = node->GetId();
32 DEBUG_ASSERT(nodeId < visitedMap.size() && nodeId < postOrderIDVec.size(), "index out of range");
33 bool tail = true;
34 for (auto succ : node->GetSuccs()) {
35 if (!visitedMap[succ->GetId()]) {
36 tail = false;
37 visitedMap[succ->GetId()] = true;
38 s.push(succ);
39 break;
40 }
41 }
42 if (tail) {
43 s.pop();
44 postOrderIDVec[nodeId] = pid++;
45 }
46 }
47 }
48
GenPostOrderID()49 void DomAnalysis::GenPostOrderID()
50 {
51 DEBUG_ASSERT(!bbVec.empty(), "size to be allocated is 0");
52 MapleVector<bool> visitedMap(bbVec.size() + 1, false, cgFunc.GetFuncScopeAllocator()->Adapter());
53 int32 postOrderID = 0;
54 PostOrderWalk(commonEntryBB, postOrderID, visitedMap);
55 // initialize reversePostOrder
56 int32 maxPostOrderID = postOrderID - 1;
57 reversePostOrder.resize(static_cast<uint32>(maxPostOrderID + 1));
58 for (size_t i = 0; i < postOrderIDVec.size(); ++i) {
59 int32 postOrderNo = postOrderIDVec[i];
60 if (postOrderNo == -1) {
61 continue;
62 }
63 reversePostOrder[static_cast<uint32>(maxPostOrderID - postOrderNo)] = bbVec[i];
64 }
65 }
66
Intersect(BB & bb1,const BB & bb2)67 BB *DomAnalysis::Intersect(BB &bb1, const BB &bb2)
68 {
69 auto *ptrBB1 = &bb1;
70 auto *ptrBB2 = &bb2;
71 while (ptrBB1 != ptrBB2) {
72 while (postOrderIDVec[ptrBB1->GetId()] < postOrderIDVec[ptrBB2->GetId()]) {
73 ptrBB1 = GetDom(ptrBB1->GetId());
74 }
75 while (postOrderIDVec[ptrBB2->GetId()] < postOrderIDVec[ptrBB1->GetId()]) {
76 ptrBB2 = GetDom(ptrBB2->GetId());
77 }
78 }
79 return ptrBB1;
80 }
81
CommonEntryBBIsPred(const BB & bb) const82 bool DominanceBase::CommonEntryBBIsPred(const BB &bb) const
83 {
84 for (const BB *suc : commonEntryBB.GetSuccs()) {
85 if (suc == &bb) {
86 return true;
87 }
88 }
89 return false;
90 }
91
92 // Figure 3 in "A Simple, Fast Dominance Algorithm" by Keith Cooper et al.
ComputeDominance()93 void DomAnalysis::ComputeDominance()
94 {
95 SetDom(commonEntryBB.GetId(), &commonEntryBB);
96 bool changed;
97 do {
98 changed = false;
99 for (size_t i = 1; i < reversePostOrder.size(); ++i) {
100 BB *bb = reversePostOrder[i];
101 if (bb == nullptr) {
102 continue;
103 }
104 BB *pre = nullptr;
105 auto it = bb->GetPredsBegin();
106 if (CommonEntryBBIsPred(*bb) || bb->GetPreds().empty()) {
107 pre = &commonEntryBB;
108 } else {
109 pre = *it;
110 }
111 ++it;
112 while ((GetDom(pre->GetId()) == nullptr || pre == bb) && it != bb->GetPredsEnd()) {
113 pre = *it;
114 ++it;
115 }
116 BB *newIDom = pre;
117 for (; it != bb->GetPredsEnd(); ++it) {
118 pre = *it;
119 if (GetDom(pre->GetId()) != nullptr && pre != bb) {
120 newIDom = Intersect(*pre, *newIDom);
121 }
122 }
123 if (GetDom(bb->GetId()) != newIDom) {
124 SetDom(bb->GetId(), newIDom);
125 changed = true;
126 }
127 }
128 } while (changed);
129 }
130
131 // Figure 5 in "A Simple, Fast Dominance Algorithm" by Keith Cooper et al.
ComputeDomFrontiers()132 void DomAnalysis::ComputeDomFrontiers()
133 {
134 for (const BB *bb : bbVec) {
135 if (bb == nullptr || bb == &commonExitBB) {
136 continue;
137 }
138 if (bb->GetPreds().size() < kBBVectorInitialSize) {
139 continue;
140 }
141 for (BB *pre : bb->GetPreds()) {
142 BB *runner = pre;
143 while (runner != nullptr && runner != GetDom(bb->GetId()) && runner != &commonEntryBB) {
144 if (!HasDomFrontier(runner->GetId(), bb->GetId())) {
145 domFrontier[runner->GetId()].push_back(bb->GetId());
146 }
147 runner = GetDom(runner->GetId());
148 }
149 }
150 }
151 // check entry bb's predBB, such as :
152 // bb1 is commonEntryBB, bb2 is entryBB, bb2 is domFrontier of bb3 and bb7.
153 // 1
154 // |
155 // 2 <-
156 // / |
157 // 3 |
158 // / \ |
159 // 4 7---
160 // / \ ^
161 // | | |
162 // 5-->6--
163 for (BB *succ : commonEntryBB.GetSuccs()) {
164 if (succ->GetPreds().size() != 1) { // Only deal with one pred bb.
165 continue;
166 }
167 for (BB *pre : succ->GetPreds()) {
168 BB *runner = pre;
169 while (runner != GetDom(succ->GetId()) && runner != &commonEntryBB && runner != succ) {
170 if (!HasDomFrontier(runner->GetId(), succ->GetId())) {
171 domFrontier[runner->GetId()].push_back(succ->GetId());
172 }
173 runner = GetDom(runner->GetId());
174 }
175 }
176 }
177 }
178
ComputeDomChildren()179 void DomAnalysis::ComputeDomChildren()
180 {
181 for (auto *bb : reversePostOrder) {
182 if (bb == nullptr || GetDom(bb->GetId()) == nullptr) {
183 continue;
184 }
185 BB *parent = GetDom(bb->GetId());
186 if (parent == bb) {
187 continue;
188 }
189 domChildren[parent->GetId()].push_back(bb->GetId());
190 }
191 }
192
193 // bbidMarker indicates that the iterDomFrontier results for bbid < bbidMarker
194 // have been computed
GetIterDomFrontier(const BB * bb,MapleUnorderedSet<uint32> * dfset,uint32 bbidMarker,std::vector<bool> & visitedMap)195 void DomAnalysis::GetIterDomFrontier(const BB *bb, MapleUnorderedSet<uint32> *dfset, uint32 bbidMarker,
196 std::vector<bool> &visitedMap)
197 {
198 if (visitedMap[bb->GetId()]) {
199 return;
200 }
201 visitedMap[bb->GetId()] = true;
202 for (uint32 frontierbbid : domFrontier[bb->GetId()]) {
203 (void)dfset->insert(frontierbbid);
204 if (frontierbbid < bbidMarker) { // union with its computed result
205 dfset->insert(iterDomFrontier[frontierbbid].begin(), iterDomFrontier[frontierbbid].end());
206 } else { // recursive call
207 BB *frontierbb = bbVec[frontierbbid];
208 GetIterDomFrontier(frontierbb, dfset, bbidMarker, visitedMap);
209 }
210 }
211 }
212
ComputeIterDomFrontiers()213 void DomAnalysis::ComputeIterDomFrontiers()
214 {
215 for (BB *bb : bbVec) {
216 if (bb == nullptr || bb == &commonExitBB) {
217 continue;
218 }
219 std::vector<bool> visitedMap(bbVec.size(), false);
220 GetIterDomFrontier(bb, &iterDomFrontier[bb->GetId()], bb->GetId(), visitedMap);
221 }
222 }
223
ComputeDtPreorder(const BB & bb,uint32 & num)224 uint32 DomAnalysis::ComputeDtPreorder(const BB &bb, uint32 &num)
225 {
226 // {BB, parent/self BB id}
227 using Node = std::pair<const BB *, uint32>;
228 std::stack<Node> allNodes;
229 allNodes.emplace(Node{&bb, bb.GetId()});
230
231 while (!allNodes.empty()) {
232 DEBUG_ASSERT(num < dtPreOrder.size(), "index out of range in Dominance::ComputeDtPreorder");
233 Node curNode = allNodes.top();
234 allNodes.pop();
235 auto curBBId = curNode.first->GetId();
236 dtPreOrder[num] = curBBId;
237 dtDfn[curBBId] = num;
238 ++num;
239 dtDfnOut[curNode.second] = num;
240 if (domChildren[curBBId].empty()) {
241 dtDfnOut[curBBId] = num;
242 continue;
243 }
244 for (size_t idx = domChildren[curBBId].size(); idx > 0; --idx) {
245 allNodes.emplace(Node{bbVec[domChildren[curBBId][idx - 1]], curBBId});
246 }
247 }
248 return num;
249 }
250
251 // true if b1 dominates b2
Dominate(const BB & bb1,const BB & bb2)252 bool DomAnalysis::Dominate(const BB &bb1, const BB &bb2)
253 {
254 return dtDfn[bb1.GetId()] <= dtDfn[bb2.GetId()] && dtDfnOut[bb1.GetId()] >= dtDfnOut[bb2.GetId()];
255 }
256
Compute()257 void DomAnalysis::Compute()
258 {
259 GenPostOrderID();
260 ComputeDominance();
261 ComputeDomFrontiers();
262 ComputeDomChildren();
263 ComputeIterDomFrontiers();
264 uint32 num = 0;
265 (void)ComputeDtPreorder(*cgFunc.GetFirstBB(), num);
266 GetDtPreOrder().resize(num);
267 }
268
Dump()269 void DomAnalysis::Dump()
270 {
271 for (BB *bb : reversePostOrder) {
272 LogInfo::MapleLogger() << "postorder no " << postOrderIDVec[bb->GetId()];
273 LogInfo::MapleLogger() << " is bb:" << bb->GetId();
274 LogInfo::MapleLogger() << " im_dom is bb:" << GetDom(bb->GetId())->GetId();
275 LogInfo::MapleLogger() << " domfrontier: [";
276 for (uint32 id : domFrontier[bb->GetId()]) {
277 LogInfo::MapleLogger() << id << " ";
278 }
279 LogInfo::MapleLogger() << "] domchildren: [";
280 for (uint32 id : domChildren[bb->GetId()]) {
281 LogInfo::MapleLogger() << id << " ";
282 }
283 LogInfo::MapleLogger() << "]\n";
284 }
285 LogInfo::MapleLogger() << "\npreorder traversal of dominator tree:";
286 for (uint32 id : dtPreOrder) {
287 LogInfo::MapleLogger() << id << " ";
288 }
289 LogInfo::MapleLogger() << "\n\n";
290 }
291
PhaseRun(maplebe::CGFunc & f)292 bool CgDomAnalysis::PhaseRun(maplebe::CGFunc &f)
293 {
294 MemPool *domMemPool = GetPhaseMemPool();
295 domAnalysis =
296 domMemPool->New<DomAnalysis>(f, *domMemPool, *domMemPool, f.GetAllBBs(), *f.GetFirstBB(), *f.GetCommonExitBB());
297 domAnalysis->Compute();
298 if (CG_DEBUG_FUNC(f)) {
299 domAnalysis->Dump();
300 }
301 return false;
302 }
303 MAPLE_ANALYSIS_PHASE_REGISTER(CgDomAnalysis, domanalysis)
304 } /* namespace maplebe */
305