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