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 #ifndef MAPLEBE_INCLUDE_CG_DOM_H
17 #define MAPLEBE_INCLUDE_CG_DOM_H
18
19 #include "cg_phase.h"
20 #include "insn.h"
21 #include "cgbb.h"
22 #include "datainfo.h"
23 #include "maple_phase.h"
24
25 namespace maplebe {
26 class DominanceBase : public AnalysisResult {
27 public:
DominanceBase(CGFunc & func,MemPool & memPool,MemPool & tmpPool,MapleVector<BB * > & bbVec,BB & commonEntryBB,BB & commonExitBB)28 DominanceBase(CGFunc &func, MemPool &memPool, MemPool &tmpPool, MapleVector<BB *> &bbVec, BB &commonEntryBB,
29 BB &commonExitBB)
30 : AnalysisResult(&memPool),
31 domAllocator(&memPool),
32 tmpAllocator(&tmpPool),
33 bbVec(bbVec),
34 cgFunc(func),
35 commonEntryBB(commonEntryBB),
36 commonExitBB(commonExitBB)
37 {
38 }
39
40 ~DominanceBase() override = default;
41
GetCommonEntryBB()42 BB &GetCommonEntryBB() const
43 {
44 return commonEntryBB;
45 }
46
GetCommonExitBB()47 BB &GetCommonExitBB() const
48 {
49 return commonExitBB;
50 }
51
52 protected:
53 bool CommonEntryBBIsPred(const BB &bb) const;
54 MapleAllocator domAllocator; // stores the analysis results
55 MapleAllocator tmpAllocator; // can be freed after dominator computation
56 MapleVector<BB *> &bbVec;
57 CGFunc &cgFunc;
58 BB &commonEntryBB;
59 BB &commonExitBB;
60 };
61
62 class DomAnalysis : public DominanceBase {
63 public:
DomAnalysis(CGFunc & func,MemPool & memPool,MemPool & tmpPool,MapleVector<BB * > & bbVec,BB & commonEntryBB,BB & commonExitBB)64 DomAnalysis(CGFunc &func, MemPool &memPool, MemPool &tmpPool, MapleVector<BB *> &bbVec, BB &commonEntryBB,
65 BB &commonExitBB)
66 : DominanceBase(func, memPool, tmpPool, bbVec, commonEntryBB, commonExitBB),
67 postOrderIDVec(bbVec.size() + 1, -1, tmpAllocator.Adapter()),
68 reversePostOrder(tmpAllocator.Adapter()),
69 doms(bbVec.size() + 1, nullptr, domAllocator.Adapter()),
70 domFrontier(bbVec.size() + 1, MapleVector<uint32>(domAllocator.Adapter()), domAllocator.Adapter()),
71 domChildren(bbVec.size() + 1, MapleVector<uint32>(domAllocator.Adapter()), domAllocator.Adapter()),
72 iterDomFrontier(bbVec.size() + 1, MapleSet<uint32>(domAllocator.Adapter()), domAllocator.Adapter()),
73 dtPreOrder(bbVec.size() + 1, 0, domAllocator.Adapter()),
74 dtDfn(bbVec.size() + 1, -1, domAllocator.Adapter()),
75 dtDfnOut(bbVec.size() + 1, -1, domAllocator.Adapter())
76 {
77 }
78 ~DomAnalysis() override = default;
79
80 void Compute();
81 void Dump();
82
83 void GenPostOrderID();
84 void ComputeDominance();
85 void ComputeDomFrontiers();
86 void ComputeDomChildren();
87 void GetIterDomFrontier(const BB *bb, MapleSet<uint32> *dfset, uint32 bbidMarker, std::vector<bool> &visitedMap);
88 void ComputeIterDomFrontiers();
89 uint32 ComputeDtPreorder(const BB &bb, uint32 &num);
90 bool Dominate(const BB &bb1, const BB &bb2); // true if bb1 dominates bb2
91
GetReversePostOrder()92 MapleVector<BB *> &GetReversePostOrder()
93 {
94 return reversePostOrder;
95 }
96
GetDtPreOrder()97 MapleVector<uint32> &GetDtPreOrder()
98 {
99 return dtPreOrder;
100 }
101
GetDtPreOrderItem(size_t idx)102 uint32 GetDtPreOrderItem(size_t idx) const
103 {
104 return dtPreOrder[idx];
105 }
106
GetDtPreOrderSize()107 size_t GetDtPreOrderSize() const
108 {
109 return dtPreOrder.size();
110 }
111
GetDtDfnItem(size_t idx)112 uint32 GetDtDfnItem(size_t idx) const
113 {
114 return dtDfn[idx];
115 }
116
GetDtDfnSize()117 size_t GetDtDfnSize() const
118 {
119 return dtDfn.size();
120 }
121
GetDom(uint32 id)122 BB *GetDom(uint32 id)
123 {
124 DEBUG_ASSERT(id < doms.size(), "bbid out of range");
125 return doms[id];
126 }
SetDom(uint32 id,BB * bb)127 void SetDom(uint32 id, BB *bb)
128 {
129 DEBUG_ASSERT(id < doms.size(), "bbid out of range");
130 doms[id] = bb;
131 }
GetDomsSize()132 size_t GetDomsSize() const
133 {
134 return doms.size();
135 }
136
GetDomFrontier(size_t idx)137 auto &GetDomFrontier(size_t idx)
138 {
139 return domFrontier[idx];
140 }
HasDomFrontier(uint32 id,uint32 frontier)141 bool HasDomFrontier(uint32 id, uint32 frontier) const
142 {
143 return std::find(domFrontier[id].begin(), domFrontier[id].end(), frontier) != domFrontier[id].end();
144 }
145
GetDomFrontierSize()146 size_t GetDomFrontierSize() const
147 {
148 return domFrontier.size();
149 }
150
GetDomChildren()151 auto &GetDomChildren()
152 {
153 return domChildren;
154 }
155
GetDomChildren(size_t idx)156 auto &GetDomChildren(size_t idx)
157 {
158 return domChildren[idx];
159 }
160
GetIdomFrontier(uint32 idx)161 auto &GetIdomFrontier(uint32 idx)
162 {
163 return iterDomFrontier[idx];
164 }
165
GetDomChildrenSize()166 size_t GetDomChildrenSize() const
167 {
168 return domChildren.size();
169 }
170
171 private:
172 void PostOrderWalk(const BB &bb, int32 &pid, MapleVector<bool> &visitedMap);
173 BB *Intersect(BB &bb1, const BB &bb2);
174
175 MapleVector<int32> postOrderIDVec; // index is bb id
176 MapleVector<BB *> reversePostOrder; // an ordering of the BB in reverse postorder
177 MapleVector<BB *> doms; // index is bb id; immediate dominator for each BB
178 MapleVector<MapleVector<uint32>> domFrontier; // index is bb id
179 MapleVector<MapleVector<uint32>> domChildren; // index is bb id; for dom tree
180 MapleVector<MapleSet<uint32>> iterDomFrontier;
181 MapleVector<uint32> dtPreOrder; // ordering of the BBs in a preorder traversal of the dominator tree
182 MapleVector<uint32> dtDfn; // gives position of each BB in dt_preorder
183 MapleVector<uint32> dtDfnOut; // max position of all nodes in the sub tree of each BB in dt_preorder
184 };
185
186 class PostDomAnalysis : public DominanceBase {
187 public:
PostDomAnalysis(CGFunc & func,MemPool & memPool,MemPool & tmpPool,MapleVector<BB * > & bbVec,BB & commonEntryBB,BB & commonExitBB)188 PostDomAnalysis(CGFunc &func, MemPool &memPool, MemPool &tmpPool, MapleVector<BB *> &bbVec, BB &commonEntryBB,
189 BB &commonExitBB)
190 : DominanceBase(func, memPool, tmpPool, bbVec, commonEntryBB, commonExitBB),
191 pdomPostOrderIDVec(bbVec.size() + 1, -1, tmpAllocator.Adapter()),
192 pdomReversePostOrder(tmpAllocator.Adapter()),
193 pdoms(bbVec.size() + 1, nullptr, domAllocator.Adapter()),
194 pdomFrontier(bbVec.size() + 1, MapleVector<uint32>(domAllocator.Adapter()), domAllocator.Adapter()),
195 pdomChildren(bbVec.size() + 1, MapleVector<uint32>(domAllocator.Adapter()), domAllocator.Adapter()),
196 iterPdomFrontier(bbVec.size() + 1, MapleSet<uint32>(domAllocator.Adapter()), domAllocator.Adapter()),
197 pdtPreOrder(bbVec.size() + 1, 0, domAllocator.Adapter()),
198 pdtDfn(bbVec.size() + 1, -1, domAllocator.Adapter()),
199 pdtDfnOut(bbVec.size() + 1, -1, domAllocator.Adapter())
200 {
201 }
202
203 ~PostDomAnalysis() override = default;
204 void Compute();
205 void PdomGenPostOrderID();
206 void ComputePostDominance();
207 void ComputePdomFrontiers();
208 void ComputePdomChildren();
209 void GetIterPdomFrontier(const BB *bb, MapleSet<uint32> *dfset, uint32 bbidMarker, std::vector<bool> &visitedMap);
210 void ComputeIterPdomFrontiers();
211 uint32 ComputePdtPreorder(const BB &bb, uint32 &num);
212 bool PostDominate(const BB &bb1, const BB &bb2); // true if bb1 postdominates bb2
213 void Dump();
214
GetPdomFrontierItem(size_t idx)215 auto &GetPdomFrontierItem(size_t idx)
216 {
217 return pdomFrontier[idx];
218 }
219
GetPdomFrontierSize()220 size_t GetPdomFrontierSize() const
221 {
222 return pdomFrontier.size();
223 }
224
GetIpdomFrontier(uint32 idx)225 auto &GetIpdomFrontier(uint32 idx)
226 {
227 return iterPdomFrontier[idx];
228 }
229
GetPdomChildrenItem(size_t idx)230 auto &GetPdomChildrenItem(size_t idx)
231 {
232 return pdomChildren[idx];
233 }
234
ResizePdtPreOrder(size_t n)235 void ResizePdtPreOrder(size_t n)
236 {
237 pdtPreOrder.resize(n);
238 }
239
GetPdtPreOrderItem(size_t idx)240 uint32 GetPdtPreOrderItem(size_t idx) const
241 {
242 return pdtPreOrder[idx];
243 }
244
GetPdtPreOrderSize()245 size_t GetPdtPreOrderSize() const
246 {
247 return pdtPreOrder.size();
248 }
249
GetPdtDfnItem(size_t idx)250 uint32 GetPdtDfnItem(size_t idx) const
251 {
252 return pdtDfn[idx];
253 }
254
GetPdomPostOrderIDVec(size_t idx)255 int32 GetPdomPostOrderIDVec(size_t idx) const
256 {
257 return pdomPostOrderIDVec[idx];
258 }
259
GetPdomReversePostOrder(size_t idx)260 BB *GetPdomReversePostOrder(size_t idx)
261 {
262 return pdomReversePostOrder[idx];
263 }
264
GetPdomReversePostOrder()265 MapleVector<BB *> &GetPdomReversePostOrder()
266 {
267 return pdomReversePostOrder;
268 }
269
GetPdomReversePostOrderSize()270 size_t GetPdomReversePostOrderSize() const
271 {
272 return pdomReversePostOrder.size();
273 }
274
HasPdomFrontier(uint32 id,uint32 frontier)275 bool HasPdomFrontier(uint32 id, uint32 frontier) const
276 {
277 return std::find(pdomFrontier[id].begin(), pdomFrontier[id].end(), frontier) != pdomFrontier[id].end();
278 }
279
GetPdom(uint32 id)280 BB *GetPdom(uint32 id)
281 {
282 DEBUG_ASSERT(id < pdoms.size(), "bbid out of range");
283 return pdoms[id];
284 }
SetPdom(uint32 id,BB * bb)285 void SetPdom(uint32 id, BB *bb)
286 {
287 DEBUG_ASSERT(id < pdoms.size(), "bbid out of range");
288 pdoms[id] = bb;
289 }
290
291 private:
292 void PdomPostOrderWalk(const BB &bb, int32 &pid, MapleVector<bool> &visitedMap);
293 BB *PdomIntersect(BB &bb1, const BB &bb2);
294
295 MapleVector<int32> pdomPostOrderIDVec; // index is bb id
296 MapleVector<BB *> pdomReversePostOrder; // an ordering of the BB in reverse postorder
297 MapleVector<BB *> pdoms; // index is bb id; immediate dominator for each BB
298 MapleVector<MapleVector<uint32>> pdomFrontier; // index is bb id
299 MapleVector<MapleVector<uint32>> pdomChildren; // index is bb id; for pdom tree
300 MapleVector<MapleSet<uint32>> iterPdomFrontier;
301 MapleVector<uint32> pdtPreOrder; // ordering of the BBs in a preorder traversal of the post-dominator tree
302 MapleVector<uint32> pdtDfn; // gives position of each BB in pdt_preorder
303 MapleVector<uint32> pdtDfnOut; // max position of all nodes in the sub tree of each BB in pdt_preorder
304 };
305
306 MAPLE_FUNC_PHASE_DECLARE_BEGIN(CgDomAnalysis, maplebe::CGFunc);
GetResult()307 DomAnalysis *GetResult()
308 {
309 return domAnalysis;
310 }
311 DomAnalysis *domAnalysis = nullptr;
312 MAPLE_FUNC_PHASE_DECLARE_END
313
314 MAPLE_FUNC_PHASE_DECLARE_BEGIN(CgPostDomAnalysis, maplebe::CGFunc);
GetResult()315 PostDomAnalysis *GetResult()
316 {
317 return pdomAnalysis;
318 }
319 PostDomAnalysis *pdomAnalysis = nullptr;
320 MAPLE_FUNC_PHASE_DECLARE_END
321 } /* namespace maplebe */
322
323 #endif /* MAPLEBE_INCLUDE_CG_DOM_H */
324