• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 MAPLE_ME_INCLUDE_BB_H
17 #define MAPLE_ME_INCLUDE_BB_H
18 #include "utils.h"
19 #include "mpl_number.h"
20 #include "ptr_list_ref.h"
21 #include "orig_symbol.h"
22 #include "ver_symbol.h"
23 #include "ssa.h"
24 
25 namespace maple {
26 class MeStmt;          // circular dependency exists, no other choice
27 class MePhiNode;       // circular dependency exists, no other choice
28 class PiassignMeStmt;  // circular dependency exists, no other choice
29 class IRMap;           // circular dependency exists, no other choice
30 enum BBKind {
31     kBBUnknown,  // uninitialized
32     kBBCondGoto,
33     kBBGoto,  // unconditional branch
34     kBBFallthru,
35     kBBReturn,
36     kBBAfterGosub,  // the BB that follows a gosub, as it is an entry point
37     kBBSwitch,
38     kBBIgoto,
39     kBBInvalid
40 };
41 
42 enum BBAttr : uint32 {
43     kBBAttrIsEntry = utils::bit_field_v<1>,
44     kBBAttrIsExit = utils::bit_field_v<2>,
45     kBBAttrWontExit = utils::bit_field_v<3>,
46     kBBAttrIsTry = utils::bit_field_v<4>,
47     kBBAttrIsTryEnd = utils::bit_field_v<5>,
48     kBBAttrIsJSCatch = utils::bit_field_v<6>,
49     kBBAttrIsJSFinally = utils::bit_field_v<7>,
50     kBBAttrIsCatch = utils::bit_field_v<8>,
51     kBBAttrIsJavaFinally = utils::bit_field_v<9>,
52     kBBAttrArtificial = utils::bit_field_v<10>,
53     kBBAttrIsInLoop = utils::bit_field_v<11>,
54     kBBAttrIsInLoopForEA = utils::bit_field_v<12>,
55     kBBAttrIsInstrument = utils::bit_field_v<13>
56 };
57 
58 constexpr uint32 kBBVectorInitialSize = 2;
59 using StmtNodes = PtrListRef<StmtNode>;
60 using MeStmts = PtrListRef<MeStmt>;
61 
62 class BB {
63 public:
64     using BBId = utils::Index<BB>;
65 
BB(MapleAllocator * alloc,MapleAllocator * versAlloc,BBId id)66     BB(MapleAllocator *alloc, MapleAllocator *versAlloc, BBId id)
67         : id(id),
68           pred(kBBVectorInitialSize, nullptr, alloc->Adapter()),
69           succ(kBBVectorInitialSize, nullptr, alloc->Adapter()),
70           succFreq(alloc->Adapter()),
71           phiList(versAlloc->Adapter()),
72           mePhiList(alloc->Adapter()),
73           meVarPiList(alloc->Adapter()),
74           group(this)
75     {
76         pred.pop_back();
77         pred.pop_back();
78         succ.pop_back();
79         succ.pop_back();
80     }
81 
BB(MapleAllocator * alloc,MapleAllocator * versAlloc,BBId id,StmtNode * firstStmt,StmtNode * lastStmt)82     BB(MapleAllocator *alloc, MapleAllocator *versAlloc, BBId id, StmtNode *firstStmt, StmtNode *lastStmt)
83         : id(id),
84           pred(kBBVectorInitialSize, nullptr, alloc->Adapter()),
85           succ(kBBVectorInitialSize, nullptr, alloc->Adapter()),
86           succFreq(alloc->Adapter()),
87           phiList(versAlloc->Adapter()),
88           mePhiList(alloc->Adapter()),
89           meVarPiList(alloc->Adapter()),
90           stmtNodeList(firstStmt, lastStmt),
91           group(this)
92     {
93         pred.pop_back();
94         pred.pop_back();
95         succ.pop_back();
96         succ.pop_back();
97     }
98 
99     virtual ~BB() = default;
100 
GetAttributes(uint32 attrKind)101     bool GetAttributes(uint32 attrKind) const
102     {
103         return (attributes & attrKind) != 0;
104     }
105 
GetAttributes()106     uint32 GetAttributes() const
107     {
108         return attributes;
109     }
110 
SetAttributes(uint32 attrKind)111     void SetAttributes(uint32 attrKind)
112     {
113         attributes |= attrKind;
114     }
115 
ClearAttributes(uint32 attrKind)116     void ClearAttributes(uint32 attrKind)
117     {
118         attributes &= (~attrKind);
119     }
120 
IsGoto()121     virtual bool IsGoto() const
122     {
123         return kind == kBBGoto;
124     }
125 
AddBackEndTry()126     virtual bool AddBackEndTry() const
127     {
128         return GetAttributes(kBBAttrIsTryEnd);
129     }
130 
131     void Dump(const MIRModule *mod);
132     void DumpHeader(const MIRModule *mod) const;
133     void DumpPhi();
134     void DumpBBAttribute(const MIRModule *mod) const;
135     std::string StrAttribute() const;
136 
137     // Only use for common entry bb
AddEntry(BB & bb)138     void AddEntry(BB &bb)
139     {
140         succ.push_back(&bb);
141     }
142 
143     // Only use for common exit bb
AddExit(BB & bb)144     void AddExit(BB &bb)
145     {
146         pred.push_back(&bb);
147     }
148 
149     // This is to help new bb to keep some flags from original bb after logically splitting.
CopyFlagsAfterSplit(const BB & bb)150     void CopyFlagsAfterSplit(const BB &bb)
151     {
152         bb.GetAttributes(kBBAttrIsTry) ? SetAttributes(kBBAttrIsTry) : ClearAttributes(kBBAttrIsTry);
153         bb.GetAttributes(kBBAttrIsTryEnd) ? SetAttributes(kBBAttrIsTryEnd) : ClearAttributes(kBBAttrIsTryEnd);
154         bb.GetAttributes(kBBAttrIsExit) ? SetAttributes(kBBAttrIsExit) : ClearAttributes(kBBAttrIsExit);
155         bb.GetAttributes(kBBAttrWontExit) ? SetAttributes(kBBAttrWontExit) : ClearAttributes(kBBAttrWontExit);
156     }
157 
GetBBId()158     BBId GetBBId() const
159     {
160         return id;
161     }
162 
SetBBId(BBId idx)163     void SetBBId(BBId idx)
164     {
165         id = idx;
166     }
167 
UintID()168     uint32 UintID() const
169     {
170         return static_cast<uint32>(id);
171     }
172 
IsEmpty()173     bool IsEmpty() const
174     {
175         return stmtNodeList.empty();
176     }
177 
SetFirst(StmtNode * stmt)178     void SetFirst(StmtNode *stmt)
179     {
180         stmtNodeList.update_front(stmt);
181     }
182 
SetLast(StmtNode * stmt)183     void SetLast(StmtNode *stmt)
184     {
185         stmtNodeList.update_back(stmt);
186     }
187 
188     // should test IsEmpty first
GetFirst()189     StmtNode &GetFirst()
190     {
191         return stmtNodeList.front();
192     }
193     // should test IsEmpty first
GetFirst()194     const StmtNode &GetFirst() const
195     {
196         return stmtNodeList.front();
197     }
198 
199     // should test IsEmpty first
GetLast()200     StmtNode &GetLast()
201     {
202         return stmtNodeList.back();
203     }
204     // should test IsEmpty first
GetLast()205     const StmtNode &GetLast() const
206     {
207         return stmtNodeList.back();
208     }
209 
210     void SetFirstMe(MeStmt *stmt);
211     void SetLastMe(MeStmt *stmt);
212     MeStmt *GetFirstMe();
213     const MeStmt *GetFirstMe() const;
214 
215     void DumpMeBB(const IRMap &irMap);
216     void MoveAllPredToSucc(BB *newSucc, BB *commonEntry);
217     void MoveAllSuccToPred(BB *newPred, BB *commonExit);
218     void RemoveStmtNode(StmtNode *stmt);
219 
InsertPi(BB & bb,PiassignMeStmt & s)220     void InsertPi(BB &bb, PiassignMeStmt &s)
221     {
222         if (meVarPiList.find(&bb) == meVarPiList.end()) {
223             std::vector<PiassignMeStmt *> tmp;
224             meVarPiList[&bb] = tmp;
225         }
226         meVarPiList[&bb].push_back(&s);
227     }
228 
GetPiList()229     MapleMap<BB *, std::vector<PiassignMeStmt *>> &GetPiList()
230     {
231         return meVarPiList;
232     }
233 
IsMeStmtEmpty()234     bool IsMeStmtEmpty() const
235     {
236         return meStmtList.empty();
237     }
238 
IsReturnBB()239     bool IsReturnBB() const
240     {
241         return kind == kBBReturn && !stmtNodeList.empty() && stmtNodeList.back().GetOpCode() == OP_return;
242     }
243 
244     void FindWillExitBBs(std::vector<bool> &visitedBBs) const;
245     const PhiNode *PhiofVerStInserted(const VersionSt &versionSt) const;
246     bool InsertPhi(MapleAllocator *alloc, VersionSt *versionSt);
247     void PrependMeStmt(MeStmt *meStmt);
248     void RemoveMeStmt(MeStmt *meStmt);
249     void AddMeStmtFirst(MeStmt *meStmt);
250     void AddMeStmtLast(MeStmt *meStmt);
251     void InsertMeStmtBefore(const MeStmt *meStmt, MeStmt *inStmt);
252     void InsertMeStmtAfter(const MeStmt *meStmt, MeStmt *inStmt);
253     void InsertMeStmtLastBr(MeStmt *inStmt);
254     void ReplaceMeStmt(MeStmt *stmt, MeStmt *newStmt);
255     void RemoveLastMeStmt();
256     void DumpMePhiList(const IRMap *irMap);
257     void DumpMeVarPiList(const IRMap *irMap);
258     void EmitBB(SSATab &ssaTab, BlockNode &curblk, bool needAnotherPass);
GetStmtNodes()259     StmtNodes &GetStmtNodes()
260     {
261         return stmtNodeList;
262     }
263 
GetStmtNodes()264     const StmtNodes &GetStmtNodes() const
265     {
266         return stmtNodeList;
267     }
268 
GetMeStmts()269     MeStmts &GetMeStmts()
270     {
271         return meStmtList;
272     }
273 
GetMeStmts()274     const MeStmts &GetMeStmts() const
275     {
276         return meStmtList;
277     }
278 
GetBBLabel()279     LabelIdx GetBBLabel() const
280     {
281         return bbLabel;
282     }
283 
SetBBLabel(LabelIdx idx)284     void SetBBLabel(LabelIdx idx)
285     {
286         bbLabel = idx;
287     }
288 
GetFrequency()289     uint32 GetFrequency() const
290     {
291         return frequency;
292     }
293 
SetFrequency(uint32 f)294     void SetFrequency(uint32 f)
295     {
296         frequency = f;
297     }
298 
GetKind()299     BBKind GetKind() const
300     {
301         return kind;
302     }
303 
SetKind(BBKind bbKind)304     void SetKind(BBKind bbKind)
305     {
306         kind = bbKind;
307     }
308 
SetKindReturn()309     void SetKindReturn()
310     {
311         SetKind(kBBReturn);
312         SetAttributes(kBBAttrIsExit);
313     }
314 
GetPred()315     const MapleVector<BB *> &GetPred() const
316     {
317         return pred;
318     }
319 
GetPred()320     MapleVector<BB *> &GetPred()
321     {
322         return pred;
323     }
324 
GetUniquePred()325     BB *GetUniquePred() const
326     {
327         if (pred.empty()) {
328             return nullptr;
329         }
330         if (pred.size() == 1) {
331             return pred.front();
332         }
333         for (size_t i = 0; i < pred.size(); ++i) {
334             if (pred.at(i) != pred.at(0)) {
335                 return nullptr;
336             }
337         }
338         return pred.front();
339     }
340 
GetPred(size_t cnt)341     const BB *GetPred(size_t cnt) const
342     {
343         DEBUG_ASSERT(cnt < pred.size(), "out of range in BB::GetPred");
344         return pred.at(cnt);
345     }
346 
GetPred(size_t cnt)347     BB *GetPred(size_t cnt)
348     {
349         DEBUG_ASSERT(cnt < pred.size(), "out of range in BB::GetPred");
350         return pred.at(cnt);
351     }
352 
SetPred(size_t cnt,BB * pp)353     void SetPred(size_t cnt, BB *pp)
354     {
355         CHECK_FATAL(cnt < pred.size(), "out of range in BB::SetPred");
356         pred[cnt] = pp;
357     }
358 
PushBackSuccFreq(uint64 freq)359     void PushBackSuccFreq(uint64 freq)
360     {
361         return succFreq.push_back(freq);
362     }
363 
GetSuccFreq()364     MapleVector<uint64> &GetSuccFreq()
365     {
366         return succFreq;
367     }
SetSuccFreq(int idx,uint64 freq)368     void SetSuccFreq(int idx, uint64 freq)
369     {
370         DEBUG_ASSERT(idx >= 0 && static_cast<size_t>(idx) <= succFreq.size(), "sanity check");
371         succFreq[static_cast<size_t>(idx)] = freq;
372     }
373 
GetSucc()374     const MapleVector<BB *> &GetSucc() const
375     {
376         return succ;
377     }
378 
GetSucc()379     MapleVector<BB *> &GetSucc()
380     {
381         return succ;
382     }
383 
GetUniqueSucc()384     BB *GetUniqueSucc()
385     {
386         if (succ.empty()) {
387             return nullptr;
388         }
389         if (succ.size() == 1) {
390             return succ.front();
391         }
392         for (size_t i = 0; i < succ.size(); ++i) {
393             if (succ.at(i) != succ.at(0)) {
394                 return nullptr;
395             }
396         }
397         return succ.front();
398     }
399 
GetSucc(size_t cnt)400     const BB *GetSucc(size_t cnt) const
401     {
402         DEBUG_ASSERT(cnt < succ.size(), "out of range in BB::GetSucc");
403         return succ.at(cnt);
404     }
405 
GetSucc(size_t cnt)406     BB *GetSucc(size_t cnt)
407     {
408         DEBUG_ASSERT(cnt < succ.size(), "out of range in BB::GetSucc");
409         return succ.at(cnt);
410     }
411 
SetSucc(size_t cnt,BB * ss)412     void SetSucc(size_t cnt, BB *ss)
413     {
414         CHECK_FATAL(cnt < succ.size(), "out of range in BB::SetSucc");
415         succ[cnt] = ss;
416     }
417 
GetPhiList()418     const MapleMap<OStIdx, PhiNode> &GetPhiList() const
419     {
420         return phiList;
421     }
GetPhiList()422     MapleMap<OStIdx, PhiNode> &GetPhiList()
423     {
424         return phiList;
425     }
ClearPhiList()426     void ClearPhiList()
427     {
428         phiList.clear();
429     }
430 
GetMePhiList()431     MapleMap<OStIdx, MePhiNode *> &GetMePhiList()
432     {
433         return mePhiList;
434     }
435 
GetMePhiList()436     const MapleMap<OStIdx, MePhiNode *> &GetMePhiList() const
437     {
438         return mePhiList;
439     }
440 
ClearMePhiList()441     void ClearMePhiList()
442     {
443         mePhiList.clear();
444     }
445 
GetEdgeFreq(const BB * bb)446     uint64 GetEdgeFreq(const BB *bb) const
447     {
448         auto iter = std::find(succ.begin(), succ.end(), bb);
449         CHECK_FATAL(iter != std::end(succ), "%d is not the successor of %d", bb->UintID(), this->UintID());
450         CHECK_FATAL(succ.size() == succFreq.size(), "succfreq size doesn't match succ size");
451         const size_t idx = static_cast<size_t>(std::distance(succ.begin(), iter));
452         return succFreq[idx];
453     }
454 
GetEdgeFreq(size_t idx)455     uint64 GetEdgeFreq(size_t idx) const
456     {
457         CHECK_FATAL(idx < succFreq.size(), "out of range in BB::GetEdgeFreq");
458         CHECK_FATAL(succ.size() == succFreq.size(), "succfreq size doesn't match succ size");
459         return succFreq[idx];
460     }
461 
SetEdgeFreq(const BB * bb,uint64 freq)462     void SetEdgeFreq(const BB *bb, uint64 freq)
463     {
464         auto iter = std::find(succ.begin(), succ.end(), bb);
465         CHECK_FATAL(iter != std::end(succ), "%d is not the successor of %d", bb->UintID(), this->UintID());
466         CHECK_FATAL(succ.size() == succFreq.size(), "succfreq size %d doesn't match succ size %d", succFreq.size(),
467                     succ.size());
468         const size_t idx = static_cast<size_t>(std::distance(succ.begin(), iter));
469         succFreq[idx] = freq;
470     }
471 
InitEdgeFreq()472     void InitEdgeFreq()
473     {
474         succFreq.resize(succ.size());
475     }
476 
GetGroup()477     BB *GetGroup() const
478     {
479         return group;
480     }
481 
SetGroup(BB * g)482     void SetGroup(BB *g)
483     {
484         group = g;
485     }
486 
ClearGroup()487     void ClearGroup()
488     {
489         group = this;
490     }
491 
492     void RemoveBBFromSucc(const BB &bb);
493     int GetPredIndex(const BB &predBB) const;
494     int GetSuccIndex(const BB &succBB) const;
495     void RemovePhiOpnd(int index);
496 
497 private:
498     BBId id;
499     LabelIdx bbLabel = 0;    // the BB's label
500     MapleVector<BB *> pred;  // predecessor list
501     MapleVector<BB *> succ;  // successor list
502     // record the edge freq from curBB to succ BB
503     MapleVector<uint64> succFreq;
504     MapleMap<OStIdx, PhiNode> phiList;
505     MapleMap<OStIdx, MePhiNode *> mePhiList;
506     MapleMap<BB *, std::vector<PiassignMeStmt *>> meVarPiList;
507     uint32 frequency = 0;
508     BBKind kind = kBBUnknown;
509     uint32 attributes = 0;
510 
511 public:
512     StmtNodes stmtNodeList;
513 
514 private:
515     MeStmts meStmtList;
516     BB *group;
517 };
518 
519 using BBId = BB::BBId;
520 
521 class SCCOfBBs {
522 public:
SCCOfBBs(uint32 index,BB * bb,MapleAllocator * alloc)523     SCCOfBBs(uint32 index, BB *bb, MapleAllocator *alloc)
524         : id(index),
525           entry(bb),
526           bbs(alloc->Adapter()),
527           predSCC(std::less<SCCOfBBs *>(), alloc->Adapter()),
528           succSCC(std::less<SCCOfBBs *>(), alloc->Adapter())
529     {
530     }
531     ~SCCOfBBs() = default;
532     void Dump();
533     void Verify(MapleVector<SCCOfBBs *> &sccOfBB);
534     void SetUp(MapleVector<SCCOfBBs *> &sccOfBB);
535     bool HasCycle() const;
AddBBNode(BB * bb)536     void AddBBNode(BB *bb)
537     {
538         bbs.push_back(bb);
539     }
Clear()540     void Clear()
541     {
542         bbs.clear();
543     }
GetID()544     uint32 GetID() const
545     {
546         return id;
547     }
GetBBs()548     const MapleVector<BB *> &GetBBs() const
549     {
550         return bbs;
551     }
GetSucc()552     const MapleSet<SCCOfBBs *> &GetSucc() const
553     {
554         return succSCC;
555     }
GetPred()556     const MapleSet<SCCOfBBs *> &GetPred() const
557     {
558         return predSCC;
559     }
HasPred()560     bool HasPred() const
561     {
562         return !predSCC.empty();
563     }
GetEntry()564     BB *GetEntry()
565     {
566         return entry;
567     }
568 
569 private:
570     uint32 id;
571     BB *entry;
572     MapleVector<BB *> bbs;
573     MapleSet<SCCOfBBs *> predSCC;
574     MapleSet<SCCOfBBs *> succSCC;
575 };
576 
577 bool ControlFlowInInfiniteLoop(const BB &bb, Opcode opcode);
578 }  // namespace maple
579 
580 namespace std {
581 template <>
582 struct hash<maple::BBId> {
583     size_t operator()(const maple::BBId &x) const
584     {
585         return x;
586     }
587 };
588 }  // namespace std
589 #endif  // MAPLE_ME_INCLUDE_BB_H
590