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