• 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 MAPLEBE_INCLUDE_CG_REG_ALLOC_LSRA_H
17 #define MAPLEBE_INCLUDE_CG_REG_ALLOC_LSRA_H
18 #include "reg_alloc.h"
19 #include "cgfunc.h"
20 #include "optimize_common.h"
21 
22 namespace maplebe {
23 class LSRALinearScanRegAllocator : public RegAllocator {
24     enum RegInCatch : uint8 {
25         /*
26          * RA do not want to allocate certain registers if a live interval is
27          * only inside of catch blocks.
28          */
29         kRegCatchNotInit = 0, /* unitialized state */
30         kRegNOtInCatch = 1,   /* interval is part or all outside of catch */
31         kRegAllInCatch = 2,   /* inteval is completely inside catch */
32     };
33 
34     enum RegInCleanup : uint8 {
35         /* Similar to reg_in_catch_t */
36         kRegCleanupNotInit = 0,       /* unitialized state */
37         kRegAllInFirstbb = 1,         /* interval is all in the first bb */
38         kRegAllOutCleanup = 2,        /* interval is all outside of cleanup, must in normal bb, may in first bb. */
39         kRegInCleanupAndFirstbb = 3,  /* inteval is in cleanup and first bb. */
40         kRegInCleanupAndNormalbb = 4, /* inteval is in cleanup and non-first bb. */
41         kRegAllInCleanup = 5          /* inteval is inside cleanup, except for bb 1 */
42     };
43 
44     class LinearRange {
45     public:
46         LinearRange() = default;
47 
LinearRange(uint32 start,uint32 end)48         LinearRange(uint32 start, uint32 end) : start(start), end(end) {}
49 
50         ~LinearRange() = default;
51 
GetStart()52         uint32 GetStart() const
53         {
54             return start;
55         }
56 
SetStart(uint32 position)57         void SetStart(uint32 position)
58         {
59             start = position;
60         }
61 
GetEnd()62         uint32 GetEnd() const
63         {
64             return end;
65         }
66 
SetEnd(uint32 position)67         void SetEnd(uint32 position)
68         {
69             end = position;
70         }
71 
GetEhStart()72         uint32 GetEhStart() const
73         {
74             return ehStart;
75         }
76 
SetEhStart(uint32 position)77         void SetEhStart(uint32 position)
78         {
79             ehStart = position;
80         }
81     private:
82         uint32 start = 0;
83         uint32 end = 0;
84         uint32 ehStart = 0;
85     };
86 
87     class LiveInterval {
88     public:
LiveInterval(MemPool & memPool)89         explicit LiveInterval(MemPool &memPool)
90             : memPool(&memPool),
91               alloc(&memPool),
92               ranges(alloc.Adapter()),
93               usePositions(alloc.Adapter()),
94               noReloadPos(alloc.Adapter()) {}
95 
96         virtual ~LiveInterval() = default;
97 
98         void AddRange(uint32 from, uint32 to);
99         void AddUsePos(uint32 pos);
100 
101         LiveInterval *SplitAt(uint32 pos);
102 
103         LiveInterval *SplitBetween(const BB &startBB, const BB &endBB);
104 
InitRangeFinder()105         void InitRangeFinder()
106         {
107             rangeFinder = ranges.begin();
108         }
109 
110         MapleVector<LinearRange>::iterator FindPosRange(uint32 pos);
111 
GetSplitPos()112         uint32 GetSplitPos() const
113         {
114             return splitSafePos;
115         }
116 
SetSplitPos(uint32 position)117         void SetSplitPos(uint32 position)
118         {
119             splitSafePos = position;
120         }
121 
GetIsCall()122         const Insn *GetIsCall() const
123         {
124             return isCall;
125         }
126 
SetIsCall(Insn & newIsCall)127         void SetIsCall(Insn &newIsCall)
128         {
129             isCall = &newIsCall;
130         }
131 
GetPhysUse()132         uint32 GetPhysUse() const
133         {
134             return physUse;
135         }
136 
SetPhysUse(uint32 newPhysUse)137         void SetPhysUse(uint32 newPhysUse)
138         {
139             physUse = newPhysUse;
140         }
141 
GetLastUse()142         uint32 GetLastUse() const
143         {
144             return lastUse;
145         }
146 
SetLastUse(uint32 newLastUse)147         void SetLastUse(uint32 newLastUse)
148         {
149             lastUse = newLastUse;
150         }
151 
GetRegNO()152         uint32 GetRegNO() const
153         {
154             return regNO;
155         }
156 
SetRegNO(uint32 newRegNO)157         void SetRegNO(uint32 newRegNO)
158         {
159             regNO = newRegNO;
160         }
161 
GetAssignedReg()162         uint32 GetAssignedReg() const
163         {
164             return assignedReg;
165         }
166 
SetAssignedReg(uint32 newAssignedReg)167         void SetAssignedReg(uint32 newAssignedReg)
168         {
169             assignedReg = newAssignedReg;
170         }
171 
GetFirstDef()172         uint32 GetFirstDef() const
173         {
174             return firstDef;
175         }
176 
SetFirstDef(uint32 newFirstDef)177         void SetFirstDef(uint32 newFirstDef)
178         {
179             firstDef = newFirstDef;
180         }
181 
GetStackSlot()182         uint32 GetStackSlot() const
183         {
184             return stackSlot;
185         }
186 
SetStackSlot(uint32 newStkSlot)187         void SetStackSlot(uint32 newStkSlot)
188         {
189             stackSlot = newStkSlot;
190         }
191 
GetRegType()192         RegType GetRegType() const
193         {
194             return regType;
195         }
196 
SetRegType(RegType newRegType)197         void SetRegType(RegType newRegType)
198         {
199             regType = newRegType;
200         }
201 
GetFirstAcrossedCall()202         uint32 GetFirstAcrossedCall() const
203         {
204             return firstAcrossedCall;
205         }
206 
SetFirstAcrossedCall(uint32 newFirstAcrossedCall)207         void SetFirstAcrossedCall(uint32 newFirstAcrossedCall)
208         {
209             firstAcrossedCall = newFirstAcrossedCall;
210         }
211 
IsEndByCall()212         bool IsEndByCall() const
213         {
214             return endByCall;
215         }
216 
SetEndByMov(bool isEndByMov)217         void SetEndByMov(bool isEndByMov)
218         {
219             endByMov = isEndByMov;
220         }
221 
IsEndByMov()222         bool IsEndByMov() const
223         {
224             return endByMov;
225         }
226 
SetPrefer(uint32 preg)227         void SetPrefer(uint32 preg)
228         {
229             prefer = preg;
230         }
231 
GetPrefer()232         uint32 GetPrefer() const
233         {
234             return prefer;
235         }
236 
IsUseBeforeDef()237         bool IsUseBeforeDef() const
238         {
239             return useBeforeDef;
240         }
241 
SetUseBeforeDef(bool newUseBeforeDef)242         void SetUseBeforeDef(bool newUseBeforeDef)
243         {
244             useBeforeDef = newUseBeforeDef;
245         }
246 
IsShouldSave()247         bool IsShouldSave() const
248         {
249             return shouldSave;
250         }
251 
SetShouldSave(bool newShouldSave)252         void SetShouldSave(bool newShouldSave)
253         {
254             shouldSave = newShouldSave;
255         }
256 
IsMultiUseInBB()257         bool IsMultiUseInBB() const
258         {
259             return multiUseInBB;
260         }
261 
SetMultiUseInBB(bool newMultiUseInBB)262         void SetMultiUseInBB(bool newMultiUseInBB)
263         {
264             multiUseInBB = newMultiUseInBB;
265         }
266 
IsThrowVal()267         bool IsThrowVal() const
268         {
269             return isThrowVal;
270         }
271 
IsCallerSpilled()272         bool IsCallerSpilled() const
273         {
274             return isCallerSpilled;
275         }
276 
SetIsCallerSpilled(bool newIsCallerSpilled)277         void SetIsCallerSpilled(bool newIsCallerSpilled)
278         {
279             isCallerSpilled = newIsCallerSpilled;
280         }
281 
IsMustAllocate()282         bool IsMustAllocate() const
283         {
284             return mustAllocate;
285         }
286 
SetMustAllocate(bool newMustAllocate)287         void SetMustAllocate(bool newMustAllocate)
288         {
289             mustAllocate = newMustAllocate;
290         }
291 
IsSplitForbidden()292         bool IsSplitForbidden() const
293         {
294             return splitForbidden;
295         }
296 
SetSplitForbid(bool isForbidden)297         void SetSplitForbid(bool isForbidden)
298         {
299             splitForbidden = isForbidden;
300         }
301 
GetRefCount()302         uint32 GetRefCount() const
303         {
304             return refCount;
305         }
306 
SetRefCount(uint32 newRefCount)307         void SetRefCount(uint32 newRefCount)
308         {
309             refCount = newRefCount;
310         }
311 
AddUsePositions(uint32 insertId)312         void AddUsePositions(uint32 insertId)
313         {
314             (void)usePositions.push_back(insertId);
315         }
316 
GetUsePositions()317         const MapleVector<uint32> &GetUsePositions() const
318         {
319             return usePositions;
320         }
321 
GetSplitNext()322         LiveInterval *GetSplitNext()
323         {
324             return splitNext;
325         }
326 
GetSplitNext()327         const LiveInterval *GetSplitNext() const
328         {
329             return splitNext;
330         }
331 
GetSplitParent()332         const LiveInterval *GetSplitParent() const
333         {
334             return splitParent;
335         }
SetSplitParent(LiveInterval & li)336         void SetSplitParent(LiveInterval &li)
337         {
338             splitParent = &li;
339         }
340 
GetPriority()341         float GetPriority() const
342         {
343             return priority;
344         }
345 
SetPriority(float newPriority)346         void SetPriority(float newPriority)
347         {
348             priority = newPriority;
349         }
350 
GetRanges()351         const MapleVector<LinearRange> &GetRanges() const
352         {
353             return ranges;
354         }
355 
GetRanges()356         MapleVector<LinearRange> &GetRanges()
357         {
358             return ranges;
359         }
360 
GetRangesSize()361         size_t GetRangesSize() const
362         {
363             return ranges.size();
364         }
365 
GetLiParent()366         const LiveInterval *GetLiParent() const
367         {
368             return liveParent;
369         }
370 
SetLiParent(LiveInterval * newLiParent)371         void SetLiParent(LiveInterval *newLiParent)
372         {
373             liveParent = newLiParent;
374         }
375 
SetLiParentChild(LiveInterval * child)376         void SetLiParentChild(LiveInterval *child) const
377         {
378             liveParent->SetLiChild(child);
379         }
380 
GetLiChild()381         const LiveInterval *GetLiChild() const
382         {
383             return liveChild;
384         }
385 
SetLiChild(LiveInterval * newLiChild)386         void SetLiChild(LiveInterval *newLiChild)
387         {
388             liveChild = newLiChild;
389         }
390 
GetResultCount()391         uint32 GetResultCount() const
392         {
393             return resultCount;
394         }
395 
SetResultCount(uint32 newResultCount)396         void SetResultCount(uint32 newResultCount)
397         {
398             resultCount = newResultCount;
399         }
400 
SetInCatchState()401         void SetInCatchState()
402         {
403             /*
404              * Once in REG_NOT_IN_CATCH, it is irreversible since once an interval
405              * is not in a catch, it is not completely in a catch.
406              */
407             if (inCatchState == kRegNOtInCatch) {
408                 return;
409             }
410             inCatchState = kRegAllInCatch;
411         }
412 
SetNotInCatchState()413         void SetNotInCatchState()
414         {
415             inCatchState = kRegNOtInCatch;
416         }
417 
IsAllInCatch()418         bool IsAllInCatch() const
419         {
420             return (inCatchState == kRegAllInCatch);
421         }
422 
SetInCleanupState()423         void SetInCleanupState()
424         {
425             switch (inCleanUpState) {
426                 case kRegCleanupNotInit:
427                     inCleanUpState = kRegAllInCleanup;
428                     break;
429                 case kRegAllInFirstbb:
430                     inCleanUpState = kRegInCleanupAndFirstbb;
431                     break;
432                 case kRegAllOutCleanup:
433                     inCleanUpState = kRegInCleanupAndNormalbb;
434                     break;
435                 case kRegInCleanupAndFirstbb:
436                     break;
437                 case kRegInCleanupAndNormalbb:
438                     break;
439                 case kRegAllInCleanup:
440                     break;
441                 default:
442                     DEBUG_ASSERT(false, "CG Internal error.");
443                     break;
444             }
445         }
446 
SetNotInCleanupState(bool isFirstBB)447         void SetNotInCleanupState(bool isFirstBB)
448         {
449             switch (inCleanUpState) {
450                 case kRegCleanupNotInit: {
451                     if (isFirstBB) {
452                         inCleanUpState = kRegAllInFirstbb;
453                     } else {
454                         inCleanUpState = kRegAllOutCleanup;
455                     }
456                     break;
457                 }
458                 case kRegAllInFirstbb: {
459                     if (!isFirstBB) {
460                         inCleanUpState = kRegAllOutCleanup;
461                     }
462                     break;
463                 }
464                 case kRegAllOutCleanup:
465                     break;
466                 case kRegInCleanupAndFirstbb: {
467                     if (!isFirstBB) {
468                         inCleanUpState = kRegInCleanupAndNormalbb;
469                     }
470                     break;
471                 }
472                 case kRegInCleanupAndNormalbb:
473                     break;
474                 case kRegAllInCleanup: {
475                     if (isFirstBB) {
476                         inCleanUpState = kRegInCleanupAndFirstbb;
477                     } else {
478                         inCleanUpState = kRegInCleanupAndNormalbb;
479                     }
480                     break;
481                 }
482                 default:
483                     DEBUG_ASSERT(false, "CG Internal error.");
484                     break;
485             }
486         }
487 
IsAllInCleanupOrFirstBB()488         bool IsAllInCleanupOrFirstBB() const
489         {
490             return (inCleanUpState == kRegAllInCleanup) || (inCleanUpState == kRegInCleanupAndFirstbb);
491         }
492 
IsAllOutCleanup()493         bool IsAllOutCleanup() const
494         {
495             return (inCleanUpState == kRegAllInFirstbb) || (inCleanUpState == kRegAllOutCleanup);
496         }
497 
GetSpillSize()498         uint32 GetSpillSize() const
499         {
500             return spillSize;
501         }
502 
SetSpillSize(uint32 size)503         void SetSpillSize(uint32 size)
504         {
505             spillSize = size;
506         }
507 
GetMaxDefSize()508         uint32 GetMaxDefSize() const
509         {
510             return maxDefSize;
511         }
512 
SetMaxDefSize(uint32 size)513         void SetMaxDefSize(uint32 size)
514         {
515             maxDefSize = size;
516         }
517 
GetMaxUseSize()518         uint32 GetMaxUseSize() const
519         {
520             return maxUseSize;
521         }
522 
SetMaxUseSize(uint32 size)523         void SetMaxUseSize(uint32 size)
524         {
525             maxUseSize = size;
526         }
527 
IsNoNeedReloadPosition(uint32 insnId)528         bool IsNoNeedReloadPosition(uint32 insnId) const
529         {
530             return (noReloadPos.find(insnId) != noReloadPos.end());
531         }
532 
AddNoNeedReloadPosition(uint32 insnId)533         void AddNoNeedReloadPosition(uint32 insnId)
534         {
535             noReloadPos.insert(insnId);
536         }
537     private:
538         MemPool *memPool;
539         MapleAllocator alloc;
540         Insn *isCall = nullptr;
541         uint32 firstDef = 0;
542         uint32 lastUse = 0;
543         uint32 splitSafePos = 0; /* splitNext's start positon */
544         uint32 physUse = 0;
545         uint32 regNO = 0;
546         /* physical register, using cg defined reg based on R0/V0. */
547         uint32 assignedReg = 0;
548         uint32 stackSlot = -1;
549         RegType regType = kRegTyUndef;
550         uint32 spillSize = 0;               /* use min(maxDefSize, maxUseSize) */
551         uint32 maxDefSize = 0;
552         uint32 maxUseSize = 0;
553         uint32 firstAcrossedCall = 0;
554         bool endByCall = false;
555         bool endByMov = false; /* do move coalesce */
556         uint32 prefer = 0;     /* prefer register */
557         bool useBeforeDef = false;
558         bool shouldSave = false;
559         bool multiUseInBB = false; /* vreg has more than 1 use in bb */
560         bool isThrowVal = false;
561         bool isCallerSpilled = false; /* only for R0(R1?) which are used for explicit incoming value of throwval; */
562         bool mustAllocate = false;    /* The register cannot be spilled (clinit pair) */
563         bool splitForbidden = false;  /* can not split if true */
564         uint32 refCount = 0;
565         float priority = 0.0;
566         MapleVector<LinearRange> ranges;
567         MapleVector<LinearRange>::iterator rangeFinder;
568         MapleVector<uint32> usePositions;
569         LiveInterval *splitNext = nullptr;         /* next split part */
570         LiveInterval *splitParent = nullptr;       /* parent split part */
571         LiveInterval *liveParent = nullptr;        /* Current li is in aother li's hole. */
572         LiveInterval *liveChild = nullptr;         /* Another li is in current li's hole. */
573         uint32 resultCount = 0;                    /* number of times this vreg has been written */
574         uint8 inCatchState = kRegCatchNotInit;     /* part or all of live interval is outside of catch blocks */
575         uint8 inCleanUpState = kRegCleanupNotInit; /* part or all of live interval is outside of cleanup blocks */
576         MapleUnorderedSet<uint32> noReloadPos;       /* Should save reg need reload at this positions */
577     };
578 
579     /* used to resolve Phi and Split */
580     class MoveInfo {
581     public:
582         MoveInfo() = default;
MoveInfo(LiveInterval & fromLi,LiveInterval & toLi,BB & bb,bool isEnd)583         MoveInfo(LiveInterval &fromLi, LiveInterval &toLi, BB &bb, bool isEnd)
584             : fromLi(&fromLi), toLi(&toLi), bb(&bb), isEnd(isEnd)
585         {
586         }
587         ~MoveInfo() = default;
588 
Init(LiveInterval & firstLi,LiveInterval & secondLi,BB & targetBB,bool endMove)589         void Init(LiveInterval &firstLi, LiveInterval &secondLi, BB &targetBB, bool endMove)
590         {
591             fromLi = &firstLi;
592             toLi = &secondLi;
593             bb = &targetBB;
594             isEnd = endMove;
595         }
596 
GetFromLi()597         const LiveInterval *GetFromLi() const
598         {
599             return fromLi;
600         }
601 
GetToLi()602         const LiveInterval *GetToLi() const
603         {
604             return toLi;
605         }
606 
GetBB()607         BB *GetBB()
608         {
609             return bb;
610         }
611 
GetBB()612         const BB *GetBB() const
613         {
614             return bb;
615         }
616 
IsEndMove()617         bool IsEndMove() const
618         {
619             return isEnd;
620         }
621 
Dump()622         void Dump() const
623         {
624             LogInfo::MapleLogger() << "from:R" << fromLi->GetRegNO() << " to:R" << toLi->GetRegNO() << " in "
625                                    << bb->GetId() << "\n";
626         }
627 
628     private:
629         LiveInterval *fromLi = nullptr;
630         LiveInterval *toLi = nullptr;
631         BB *bb = nullptr;
632         bool isEnd = true;
633     };
634 
635     struct ActiveCmp {
operatorActiveCmp636         bool operator()(const LiveInterval *lhs, const LiveInterval *rhs) const
637         {
638             CHECK_NULL_FATAL(lhs);
639             CHECK_NULL_FATAL(rhs);
640             /* elements considered equal if return false */
641             if (lhs == rhs) {
642                 return false;
643             }
644             if (lhs->GetFirstDef() == rhs->GetFirstDef() && lhs->GetLastUse() == rhs->GetLastUse() &&
645                 lhs->GetRegNO() == rhs->GetRegNO() && lhs->GetRegType() == rhs->GetRegType() &&
646                 lhs->GetAssignedReg() == rhs->GetAssignedReg()) {
647                 return false;
648             }
649             if (lhs->GetFirstDef() == rhs->GetFirstDef() && lhs->GetLastUse() == rhs->GetLastUse() &&
650                 lhs->GetPhysUse() == rhs->GetPhysUse() && lhs->GetRegType() == rhs->GetRegType()) {
651                 return lhs->GetRegNO() < rhs->GetRegNO();
652             }
653             if (lhs->GetPhysUse() != 0 && rhs->GetPhysUse() != 0) {
654                 if (lhs->GetFirstDef() == rhs->GetFirstDef()) {
655                     return lhs->GetPhysUse() < rhs->GetPhysUse();
656                 } else {
657                     return lhs->GetFirstDef() < rhs->GetFirstDef();
658                 }
659             }
660             /* At this point, lhs != rhs */
661             if (lhs->GetLastUse() == rhs->GetLastUse()) {
662                 return lhs->GetFirstDef() <= rhs->GetFirstDef();
663             }
664             return lhs->GetLastUse() < rhs->GetLastUse();
665         }
666     };
667 
668     class CallerSaveOpt {
669     public:
CallerSaveOpt(const MapleVector<LiveInterval * > & liveIntervalsArray,Bfs * bbSort)670         CallerSaveOpt(const MapleVector<LiveInterval*> &liveIntervalsArray, Bfs *bbSort) : bfs(bbSort)
671         {
672             for (auto *li : liveIntervalsArray) {
673                 if (li != nullptr && li->IsShouldSave()) {
674                     callerSaves.emplace_back(li);
675                 }
676             }
677             localDefLiveIn.resize(callerSaves.size());
678             localDefLiveOut.resize(callerSaves.size());
679         }
680 
681         void Run();
682     private:
683         using LocalDefBBSet = std::unordered_set<uint32>;
684 
685         bool firstTime = true;
686         Bfs *bfs = nullptr;
687         std::vector<LiveInterval*> callerSaves;
688         std::vector<LocalDefBBSet> localDefLiveIn;
689         std::vector<LocalDefBBSet> localDefLiveOut;
690 
691         bool UpdateLocalDefWithBBLiveIn(const BB &bb);
692         void CollectCallerNoNeedReloadByInsn(const Insn &insn);
693     };
694 public:
LSRALinearScanRegAllocator(CGFunc & cgFunc,MemPool & memPool,Bfs * bbSort)695     LSRALinearScanRegAllocator(CGFunc &cgFunc, MemPool &memPool, Bfs *bbSort)
696         : RegAllocator(cgFunc, memPool),
697           liveIntervalsArray(alloc.Adapter()),
698           initialQue(alloc.Adapter()),
699           intParamQueue(alloc.Adapter()),
700           fpParamQueue(alloc.Adapter()),
701           callQueue(alloc.Adapter()),
702           active(alloc.Adapter()),
703           freeUntilPos(alloc.Adapter()),
704           intCallerRegSet(alloc.Adapter()),
705           intCalleeRegSet(alloc.Adapter()),
706           intParamRegSet(alloc.Adapter()),
707           intSpillRegSet(alloc.Adapter()),
708           fpCallerRegSet(alloc.Adapter()),
709           fpCalleeRegSet(alloc.Adapter()),
710           fpParamRegSet(alloc.Adapter()),
711           fpSpillRegSet(alloc.Adapter()),
712           bfs(bbSort),
713           liQue(alloc.Adapter()),
714           splitPosMap(alloc.Adapter()),
715           splitInsnMap(alloc.Adapter()),
716           moveInfoVec(alloc.Adapter()),
717           dereivedRef2Base(alloc.Adapter())
718     {
719         regInfo = cgFunc.GetTargetRegInfo();
720         regInfo->Init();
721         for (uint32 i = 0; i < regInfo->GetIntRegs().size(); ++i) {
722             intParamQueue.push_back(initialQue);
723         }
724         for (uint32 i = 0; i < regInfo->GetFpRegs().size(); ++i) {
725             fpParamQueue.push_back(initialQue);
726         }
727         firstIntReg = *regInfo->GetIntRegs().begin();
728         firstFpReg = *regInfo->GetFpRegs().begin();
729     }
730     ~LSRALinearScanRegAllocator() override = default;
731 
732     bool AllocateRegisters() override;
733     void PreWork();
734     bool CheckForReg(Operand &opnd, const Insn &insn, const LiveInterval &li, regno_t regNO, bool isDef) const;
735     void PrintRegSet(const MapleSet<uint32> &set, const std::string &str) const;
736     void PrintLiveInterval(const LiveInterval &li, const std::string &str) const;
737     void PrintLiveRanges(const LiveInterval &li) const;
738     void PrintAllLiveRanges() const;
739     void PrintLiveRangesGraph() const;
740     void SpillStackMapInfo();
741     void PrintParamQueue(const std::string &str);
742     void PrintCallQueue(const std::string &str) const;
743     void PrintActiveList(const std::string &str, uint32 len = 0) const;
744     void PrintActiveListSimple() const;
745     void PrintLiveIntervals() const;
746     void DebugCheckActiveList() const;
747     void InitFreeRegPool();
748     void RecordCall(Insn &insn);
749     void RecordPhysRegs(const RegOperand &regOpnd, uint32 insnNum, bool isDef);
750     void UpdateLiveIntervalState(const BB &bb, LiveInterval &li) const;
751     void UpdateRegUsedInfo(LiveInterval &li, regno_t regNO);
752     void SetupLiveInterval(Operand &opnd, Insn &insn, bool isDef, uint32 &nUses, uint32 regSize);
753     void UpdateLiveIntervalByLiveIn(const BB &bb, uint32 insnNum);
754     void UpdateParamLiveIntervalByLiveIn(const BB &bb, uint32 insnNum);
755     void ComputeLiveIn(BB &bb, uint32 insnNum);
756     void ComputeLiveOut(BB &bb, uint32 insnNum);
757     void ComputeLiveIntervalForEachOperand(Insn &insn);
758     void ComputeLiveInterval();
759     void FindLowestPrioInActive(LiveInterval *&targetLi, LiveInterval *li = nullptr, RegType regType = kRegTyInt);
760     void LiveIntervalAnalysis();
761     void UpdateCallQueueAtRetirement(uint32 insnID);
762     void UpdateActiveAllocateInfo(const LiveInterval &li);
763     void UpdateParamAllocateInfo(const LiveInterval &li);
764     void RetireActive(LiveInterval &li, uint32 insnID);
765     void AssignPhysRegsForLi(LiveInterval &li);
766     LiveInterval *GetLiveIntervalAt(uint32 regNO, uint32 pos);
767     bool OpndNeedAllocation(const Insn &insn, Operand &opnd, bool isDef, uint32 insnNum);
768     void InsertParamToActive(Operand &opnd);
769     void InsertToActive(Operand &opnd, uint32 insnNum);
770     void ReleasePregToSet(const LiveInterval &li, uint32 preg);
771     void UpdateActiveAtRetirement(uint32 insnID);
772     void RetireFromActive(const Insn &insn);
773     void AssignPhysRegsForInsn(Insn &insn);
774     RegOperand *GetReplaceOpnd(Insn &insn, Operand &opnd, uint32 &spillIdx, bool isDef);
775     RegOperand *GetReplaceUdOpnd(Insn &insn, Operand &opnd, uint32 &spillIdx);
776     void ResolveSplitBBEdge(BB &bb);
777     void SetAllocMode();
778     void LinearScanRegAllocator();
779     void FinalizeRegisters();
780     void ResolveMoveVec();
781     void CollectReferenceMap();
782     void SolveRegOpndDeoptInfo(const RegOperand &regOpnd, DeoptInfo &deoptInfo, int32 deoptVregNO) const;
783     void SolveMemOpndDeoptInfo(const MemOperand &memOpnd, DeoptInfo &deoptInfo, int32 deoptVregNO) const;
784     void CollectDeoptInfo();
785     void SpillOperand(Insn &insn, Operand &opnd, bool isDef, uint32 spillIdx);
786     void SetOperandSpill(Operand &opnd);
787     regno_t HandleSpillForLi(LiveInterval &li);
788     RegOperand *HandleSpillForInsn(const Insn &insn, Operand &opnd);
789     MemOperand *GetSpillMem(uint32 vregNO, bool isDest, Insn &insn, regno_t regNO, bool &isOutOfRange,
790                             uint32 bitSize) const;
791     void InsertCallerSave(Insn &insn, Operand &opnd, bool isDef);
792     uint32 GetRegFromMask(uint32 mask, regno_t offset, const LiveInterval &li);
793     uint32 GetSpecialPhysRegPattern(const LiveInterval &li);
794     uint32 GetRegFromSet(MapleSet<uint32> &set, regno_t offset, LiveInterval &li, regno_t forcedReg = 0) const;
795     uint32 AssignSpecialPhysRegPattern(const Insn &insn, LiveInterval &li);
796     uint32 FindAvailablePhyReg(LiveInterval &li);
797     uint32 AssignPhysRegs(LiveInterval &li);
798     void SetupIntervalRangesByOperand(Operand &opnd, const Insn &insn, uint32 blockFrom, bool isDef);
799     bool SplitLiveInterval(LiveInterval &li, uint32 pos);
800     void LiveIntervalQueueInsert(LiveInterval &li);
801     void ComputeLoopLiveIntervalPriority(const CGFuncLoops &loop);
802     void ComputeLoopLiveIntervalPriorityInInsn(const Insn &insn);
803     void SetLiSpill(LiveInterval &li);
804 
805 private:
806     uint32 FindAvailablePhyRegByFastAlloc(LiveInterval &li);
807     bool NeedSaveAcrossCall(LiveInterval &li);
808     uint32 FindAvailablePhyReg(LiveInterval &li, bool isIntReg);
809 
810     RegisterInfo *regInfo = nullptr;
811     regno_t firstIntReg = 0;
812     regno_t firstFpReg = 0;
813 
814     /* Comparison function for LiveInterval */
815     static constexpr uint32 kMaxSpillRegNum = 3;
816     static constexpr uint32 kMaxFpSpill = 2;
817     MapleVector<LiveInterval *> liveIntervalsArray;
818     MapleQueue<LiveInterval *> initialQue;
819     using SingleQue = MapleQueue<LiveInterval *>;
820     MapleVector<SingleQue> intParamQueue;
821     MapleVector<SingleQue> fpParamQueue;
822     MapleQueue<uint32> callQueue;
823     MapleSet<LiveInterval *, ActiveCmp> active;
824     MapleSet<LiveInterval *, ActiveCmp>::iterator itFinded;
825     MapleVector<uint32> freeUntilPos;
826 
827     /* Change these into vectors so it can be added and deleted easily. */
828     MapleSet<regno_t> intCallerRegSet;   /* integer caller saved */
829     MapleSet<regno_t> intCalleeRegSet;   /*         callee       */
830     MapleSet<regno_t> intParamRegSet;    /*         parameters    */
831     MapleVector<regno_t> intSpillRegSet; /* integer regs put aside for spills */
832 
833     /* and register */
834     uint32 intCallerMask = 0;          /* bit mask for all possible caller int */
835     uint32 intCalleeMask = 0;          /*                           callee     */
836     uint32 intParamMask = 0;           /*     (physical-register)   parameter  */
837     MapleSet<uint32> fpCallerRegSet;   /* float caller saved */
838     MapleSet<uint32> fpCalleeRegSet;   /*       callee       */
839     MapleSet<uint32> fpParamRegSet;    /*       parameter    */
840     MapleVector<uint32> fpSpillRegSet; /* float regs put aside for spills */
841     std::unordered_set<uint32> loopBBRegSet;
842     Bfs *bfs = nullptr;
843     uint32 fpCallerMask = 0;       /* bit mask for all possible caller fp */
844     uint32 fpCalleeMask = 0;       /*                           callee    */
845     uint32 fpParamMask = 0;        /*      (physical-register)  parameter */
846     uint64 blockForbiddenMask = 0; /* bit mask for forbidden physical reg */
847     uint32 debugSpillCnt = 0;
848     std::vector<uint64> regUsedInBB;
849     uint32 maxInsnNum = 0;
850     regno_t minVregNum = 0xFFFFFFFF;
851     regno_t maxVregNum = 0;
852     bool fastAlloc = false;
853     bool spillAll = false;
854     bool needExtraSpillReg = false;
855     bool isSpillZero = false;
856     uint64 spillCount = 0;
857     uint64 reloadCount = 0;
858     uint64 callerSaveSpillCount = 0;
859     uint64 callerSaveReloadCount = 0;
860     MapleQueue<LiveInterval *> liQue;
861     MapleMultiMap<uint32, LiveInterval *> splitPosMap; /* LiveInterval split position */
862     MapleUnorderedMap<uint32, Insn *> splitInsnMap;    /* split insn */
863     MapleVector<MoveInfo> moveInfoVec;                 /* insertion of move(PHI&Split) is based on this */
864     MapleUnorderedMap<regno_t, regno_t> dereivedRef2Base;
865 };
866 } /* namespace maplebe */
867 
868 #endif /* MAPLEBE_INCLUDE_CG_REG_ALLOC_LSRA_H */
869