• 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     class LinearRange {
30     public:
31         LinearRange() = default;
32 
LinearRange(uint32 start,uint32 end)33         LinearRange(uint32 start, uint32 end) : start(start), end(end) {}
34 
35         ~LinearRange() = default;
36 
GetStart()37         uint32 GetStart() const
38         {
39             return start;
40         }
41 
SetStart(uint32 position)42         void SetStart(uint32 position)
43         {
44             start = position;
45         }
46 
GetEnd()47         uint32 GetEnd() const
48         {
49             return end;
50         }
51 
SetEnd(uint32 position)52         void SetEnd(uint32 position)
53         {
54             end = position;
55         }
56     private:
57         uint32 start = 0;
58         uint32 end = 0;
59     };
60 
61     class LiveInterval {
62     public:
LiveInterval(MemPool & memPool)63         explicit LiveInterval(MemPool &memPool)
64             : memPool(&memPool),
65               alloc(&memPool),
66               ranges(alloc.Adapter()),
67               usePositions(alloc.Adapter()),
68               noReloadPos(alloc.Adapter()) {}
69 
70         virtual ~LiveInterval() = default;
71 
72         void AddRange(uint32 from, uint32 to);
73         void AddUsePos(uint32 pos);
74 
InitRangeFinder()75         void InitRangeFinder()
76         {
77             rangeFinder = ranges.begin();
78         }
79 
80         MapleVector<LinearRange>::iterator FindPosRange(uint32 pos);
81 
GetPhysUse()82         uint32 GetPhysUse() const
83         {
84             return physUse;
85         }
86 
SetPhysUse(uint32 newPhysUse)87         void SetPhysUse(uint32 newPhysUse)
88         {
89             physUse = newPhysUse;
90         }
91 
GetLastUse()92         uint32 GetLastUse() const
93         {
94             return lastUse;
95         }
96 
SetLastUse(uint32 newLastUse)97         void SetLastUse(uint32 newLastUse)
98         {
99             lastUse = newLastUse;
100         }
101 
GetRegNO()102         uint32 GetRegNO() const
103         {
104             return regNO;
105         }
106 
SetRegNO(uint32 newRegNO)107         void SetRegNO(uint32 newRegNO)
108         {
109             regNO = newRegNO;
110         }
111 
GetAssignedReg()112         uint32 GetAssignedReg() const
113         {
114             return assignedReg;
115         }
116 
SetAssignedReg(uint32 newAssignedReg)117         void SetAssignedReg(uint32 newAssignedReg)
118         {
119             assignedReg = newAssignedReg;
120         }
121 
GetFirstDef()122         uint32 GetFirstDef() const
123         {
124             return firstDef;
125         }
126 
SetFirstDef(uint32 newFirstDef)127         void SetFirstDef(uint32 newFirstDef)
128         {
129             firstDef = newFirstDef;
130         }
131 
GetStackSlot()132         uint32 GetStackSlot() const
133         {
134             return stackSlot;
135         }
136 
SetStackSlot(uint32 newStkSlot)137         void SetStackSlot(uint32 newStkSlot)
138         {
139             stackSlot = newStkSlot;
140         }
141 
GetRegType()142         RegType GetRegType() const
143         {
144             return regType;
145         }
146 
SetRegType(RegType newRegType)147         void SetRegType(RegType newRegType)
148         {
149             regType = newRegType;
150         }
151 
SetPrefer(uint32 preg)152         void SetPrefer(uint32 preg)
153         {
154             prefer = preg;
155         }
156 
GetPrefer()157         uint32 GetPrefer() const
158         {
159             return prefer;
160         }
161 
IsUseBeforeDef()162         bool IsUseBeforeDef() const
163         {
164             return useBeforeDef;
165         }
166 
SetUseBeforeDef(bool newUseBeforeDef)167         void SetUseBeforeDef(bool newUseBeforeDef)
168         {
169             useBeforeDef = newUseBeforeDef;
170         }
171 
IsShouldSave()172         bool IsShouldSave() const
173         {
174             return shouldSave;
175         }
176 
SetShouldSave(bool newShouldSave)177         void SetShouldSave(bool newShouldSave)
178         {
179             shouldSave = newShouldSave;
180         }
181 
IsMultiUseInBB()182         bool IsMultiUseInBB() const
183         {
184             return multiUseInBB;
185         }
186 
SetMultiUseInBB(bool newMultiUseInBB)187         void SetMultiUseInBB(bool newMultiUseInBB)
188         {
189             multiUseInBB = newMultiUseInBB;
190         }
191 
GetRefCount()192         uint32 GetRefCount() const
193         {
194             return refCount;
195         }
196 
SetRefCount(uint32 newRefCount)197         void SetRefCount(uint32 newRefCount)
198         {
199             refCount = newRefCount;
200         }
201 
AddUsePositions(uint32 insertId)202         void AddUsePositions(uint32 insertId)
203         {
204             (void)usePositions.push_back(insertId);
205         }
206 
GetUsePositions()207         const MapleVector<uint32> &GetUsePositions() const
208         {
209             return usePositions;
210         }
211 
GetPriority()212         float GetPriority() const
213         {
214             return priority;
215         }
216 
SetPriority(float newPriority)217         void SetPriority(float newPriority)
218         {
219             priority = newPriority;
220         }
221 
GetRanges()222         const MapleVector<LinearRange> &GetRanges() const
223         {
224             return ranges;
225         }
226 
GetRanges()227         MapleVector<LinearRange> &GetRanges()
228         {
229             return ranges;
230         }
231 
GetRangesSize()232         size_t GetRangesSize() const
233         {
234             return ranges.size();
235         }
236 
GetSpillSize()237         uint32 GetSpillSize() const
238         {
239             return spillSize;
240         }
241 
SetSpillSize(uint32 size)242         void SetSpillSize(uint32 size)
243         {
244             spillSize = size;
245         }
246 
GetMaxDefSize()247         uint32 GetMaxDefSize() const
248         {
249             return maxDefSize;
250         }
251 
SetMaxDefSize(uint32 size)252         void SetMaxDefSize(uint32 size)
253         {
254             maxDefSize = size;
255         }
256 
GetMaxUseSize()257         uint32 GetMaxUseSize() const
258         {
259             return maxUseSize;
260         }
261 
SetMaxUseSize(uint32 size)262         void SetMaxUseSize(uint32 size)
263         {
264             maxUseSize = size;
265         }
266 
IsNoNeedReloadPosition(uint32 insnId)267         bool IsNoNeedReloadPosition(uint32 insnId) const
268         {
269             return (noReloadPos.find(insnId) != noReloadPos.end());
270         }
271 
AddNoNeedReloadPosition(uint32 insnId)272         void AddNoNeedReloadPosition(uint32 insnId)
273         {
274             noReloadPos.insert(insnId);
275         }
276     private:
277         MemPool *memPool;
278         MapleAllocator alloc;
279         uint32 firstDef = 0;
280         uint32 lastUse = 0;
281         uint32 physUse = 0;
282         uint32 regNO = 0;
283         /* physical register, using cg defined reg based on R0/V0. */
284         uint32 assignedReg = 0;
285         uint32 stackSlot = -1;
286         RegType regType = kRegTyUndef;
287         uint32 spillSize = 0;               /* use min(maxDefSize, maxUseSize) */
288         uint32 maxDefSize = 0;
289         uint32 maxUseSize = 0;
290         uint32 prefer = 0;     /* prefer register */
291         bool useBeforeDef = false;
292         bool shouldSave = false;
293         bool multiUseInBB = false; /* vreg has more than 1 use in bb */
294         uint32 refCount = 0;
295         float priority = 0.0;
296         MapleVector<LinearRange> ranges;
297         MapleVector<LinearRange>::iterator rangeFinder;
298         MapleVector<uint32> usePositions;
299         MapleUnorderedSet<uint32> noReloadPos;       /* Should save reg need reload at this positions */
300     };
301 
302     struct ActiveCmp {
operatorActiveCmp303         bool operator()(const LiveInterval *lhs, const LiveInterval *rhs) const
304         {
305             CHECK_NULL_FATAL(lhs);
306             CHECK_NULL_FATAL(rhs);
307             /* elements considered equal if return false */
308             if (lhs == rhs) {
309                 return false;
310             }
311             if (lhs->GetFirstDef() == rhs->GetFirstDef() && lhs->GetLastUse() == rhs->GetLastUse() &&
312                 lhs->GetRegType() == rhs->GetRegType()) {
313                 if (lhs->GetRegNO() == rhs->GetRegNO() && lhs->GetAssignedReg() == rhs->GetAssignedReg()) {
314                     return false;
315                 }
316                 if (lhs->GetPhysUse() == rhs->GetPhysUse()) {
317                     return lhs->GetRegNO() < rhs->GetRegNO();
318                 }
319             }
320             if (lhs->GetPhysUse() != 0 && rhs->GetPhysUse() != 0) {
321                 if (lhs->GetFirstDef() == rhs->GetFirstDef()) {
322                     return lhs->GetPhysUse() < rhs->GetPhysUse();
323                 } else {
324                     return lhs->GetFirstDef() < rhs->GetFirstDef();
325                 }
326             }
327             /* At this point, lhs != rhs */
328             if (lhs->GetLastUse() == rhs->GetLastUse()) {
329                 return lhs->GetFirstDef() <= rhs->GetFirstDef();
330             }
331             return lhs->GetLastUse() < rhs->GetLastUse();
332         }
333     };
334 
335     class CallerSaveOpt {
336     public:
CallerSaveOpt(const MapleVector<LiveInterval * > & liveIntervalsArray,Bfs * bbSort)337         CallerSaveOpt(const MapleVector<LiveInterval*> &liveIntervalsArray, Bfs *bbSort) : bfs(bbSort)
338         {
339             for (auto *li : liveIntervalsArray) {
340                 if (li != nullptr && li->IsShouldSave()) {
341                     callerSaves.emplace_back(li);
342                 }
343             }
344             localDefLiveIn.resize(callerSaves.size());
345             localDefAfterInsn.resize(callerSaves.size());
346         }
347 
348         void Run();
349     private:
350         bool firstTime = true;
351         Bfs *bfs = nullptr;
352         std::vector<LiveInterval*> callerSaves;
353         std::vector<std::unordered_set<uint32>> localDefLiveIn;         // bbid: which is defined in livein
354         std::vector<std::unordered_map<uint32, uint32>> localDefAfterInsn;  // bbid: def-insnid
355 
356         bool UpdateLocalDefWithBBLiveIn(const BB &bb);
357         void CollectCallerNoNeedReloadByInsn(const Insn &insn);
358     };
359 
360 public:
LSRALinearScanRegAllocator(CGFunc & cgFunc,MemPool & memPool,Bfs * bbSort,LoopAnalysis & loop)361     LSRALinearScanRegAllocator(CGFunc &cgFunc, MemPool &memPool, Bfs *bbSort, LoopAnalysis &loop)
362         : RegAllocator(cgFunc, memPool),
363           loopInfo(loop),
364           liveIntervalsArray(alloc.Adapter()),
365           initialQue(alloc.Adapter()),
366           intParamQueue(alloc.Adapter()),
367           fpParamQueue(alloc.Adapter()),
368           callQueue(alloc.Adapter()),
369           active(alloc.Adapter()),
370           freeUntilPos(alloc.Adapter()),
371 #ifdef ARK_LITECG_DEBUG
372           intCallerRegSet(alloc.Adapter()),
373           intCalleeRegSet(alloc.Adapter()),
374           intParamRegSet(alloc.Adapter()),
375 #endif
376           intSpillRegSet(alloc.Adapter()),
377 #ifdef ARK_LITECG_DEBUG
378           fpCallerRegSet(alloc.Adapter()),
379           fpCalleeRegSet(alloc.Adapter()),
380           fpParamRegSet(alloc.Adapter()),
381 #endif
382           fpSpillRegSet(alloc.Adapter()),
383           loopBBRegSet(alloc.Adapter()),
384           bfs(bbSort),
385           regUsedInBB(alloc.Adapter()),
386           liQue(alloc.Adapter()),
387           derivedRef2Base(alloc.Adapter())
388     {
389         for (uint32 i = 0; i < regInfo->GetIntRegs().size(); ++i) {
390             intParamQueue.push_back(initialQue);
391         }
392         for (uint32 i = 0; i < regInfo->GetFpRegs().size(); ++i) {
393             fpParamQueue.push_back(initialQue);
394         }
395         firstIntReg = *regInfo->GetIntRegs().begin();
396         firstFpReg = *regInfo->GetFpRegs().begin();
397     }
398     ~LSRALinearScanRegAllocator() override = default;
399 
400     bool AllocateRegisters() override;
401     void PrintRegSet(const MapleSet<uint32> &set, const std::string &str) const;
402     void PrintLiveInterval(const LiveInterval &li, const std::string &str) const;
403     void PrintLiveRanges(const LiveInterval &li) const;
404     void PrintAllLiveRanges() const;
405     void SpillStackMapInfo();
406     void PrintParamQueue(const std::string &str);
407     void PrintCallQueue(const std::string &str) const;
408     void PrintActiveList(const std::string &str, uint32 len = 0) const;
409     void PrintLiveIntervals() const;
410     void DebugCheckActiveList() const;
411     void InitFreeRegPool();
412     void RecordPhysRegs(const RegOperand &regOpnd, uint32 insnNum, bool isDef);
413     void UpdateRegUsedInfo(LiveInterval &li, regno_t regNO);
414     void SetupLiveInterval(Operand &opnd, Insn &insn, bool isDef, uint32 &nUses, uint32 regSize);
415     void UpdateLiveIntervalByLiveIn(const BB &bb, uint32 insnNum);
416     void UpdateParamLiveIntervalByLiveIn(const BB &bb, uint32 insnNum);
417     void ComputeLiveIn(BB &bb, uint32 insnNum);
418     void ComputeLiveOut(BB &bb, uint32 insnNum);
419     void ComputeLiveIntervalForEachOperand(Insn &insn);
420     void ComputeLiveInterval();
421     void FindLowestPrioInActive(LiveInterval *&targetLi, LiveInterval *li = nullptr, RegType regType = kRegTyInt);
422     void LiveIntervalAnalysis();
423     void UpdateCallQueueAtRetirement(uint32 insnID);
424     void UpdateActiveAllocateInfo(const LiveInterval &li);
425     void UpdateParamAllocateInfo(const LiveInterval &li);
426     void RetireActive(LiveInterval &li, uint32 insnID);
427     void AssignPhysRegsForLi(LiveInterval &li);
428     RegOperand *GetReplaceOpnd(Insn &insn, Operand &opnd, uint32 &spillIdx, bool isDef);
429     RegOperand *GetReplaceUdOpnd(Insn &insn, Operand &opnd, uint32 &spillIdx);
430     void SetAllocMode();
431     void LinearScanRegAllocator();
432     void FinalizeFreeReferenceSpillStack(Insn &insn);
433     void FinalizeUseRegisters(Insn &insn, uint32 &spillIdx);
434     void FinalizeUseDefRegisters(Insn &insn, uint32 &spillIdx);
435     void FinalizeDefRegisters(Insn &insn, uint32 &spillIdx);
436     void FinalizeRegisters();
437     void CollectReferenceMap();
438     void SolveRegOpndDeoptInfo(const RegOperand &regOpnd, DeoptInfo &deoptInfo, int32 deoptVregNO) const;
439     void SolveMemOpndDeoptInfo(const MemOperand &memOpnd, DeoptInfo &deoptInfo, int32 deoptVregNO) const;
440     void CollectDeoptInfo();
441     void SpillOperand(Insn &insn, Operand &opnd, bool isDef, uint32 spillIdx);
442     RegOperand *GetSpillPhyRegOperand(Insn &insn, regno_t regNo, uint32 regSize, RegType regType);
443     regno_t HandleSpillForLi(LiveInterval &li);
444     MemOperand *GetSpillMem(uint32 vregNO, bool isDest, Insn &insn, regno_t regNO, bool &isOutOfRange,
445                             uint32 bitSize) const;
446     void InsertCallerSave(Insn &insn, Operand &opnd, bool isDef, uint32 spillIdx);
447     uint32 GetRegFromMask(uint32 mask, regno_t offset, const LiveInterval &li);
448     uint32 FindAvailablePhyReg(LiveInterval &li);
449     uint32 AssignPhysRegs(LiveInterval &li);
450     void ComputeLoopLiveIntervalPriority(const LoopDesc &loop);
451     void ComputeLoopLiveIntervalPriorityInInsn(const Insn &insn);
452     void SetLiSpill(LiveInterval &li);
453     void SetStackMapDerivedInfo();
454     void CollectStackMapInfo();
455     void ComputeLiveIntervalForCall(Insn &insn);
456 private:
457     bool NeedSaveAcrossCall(LiveInterval &li);
458     uint32 FindAvailablePhyRegAcrossCall(LiveInterval &li, bool isIntReg);
459     uint32 FindAvailablePhyReg(LiveInterval &li, bool isIntReg);
460 
461     LoopAnalysis &loopInfo;
462     regno_t firstIntReg = 0;
463     regno_t firstFpReg = 0;
464 
465     /* Comparison function for LiveInterval */
466     static constexpr uint32 kMaxSpillRegNum = 3;
467     static constexpr uint32 kMaxFpSpill = 2;
468     MapleVector<LiveInterval *> liveIntervalsArray;
469     MapleQueue<LiveInterval *> initialQue;
470     using SingleQue = MapleQueue<LiveInterval *>;
471     MapleVector<SingleQue> intParamQueue;
472     MapleVector<SingleQue> fpParamQueue;
473     MapleQueue<uint32> callQueue;
474     MapleSet<LiveInterval *, ActiveCmp> active;
475     MapleSet<LiveInterval *, ActiveCmp>::iterator itFinded;
476     MapleVector<uint32> freeUntilPos;
477 
478     /* Change these into vectors so it can be added and deleted easily. */
479 #ifdef ARK_LITECG_DEBUG
480     MapleSet<regno_t> intCallerRegSet;   /* integer caller saved */
481     MapleSet<regno_t> intCalleeRegSet;   /*         callee       */
482     MapleSet<regno_t> intParamRegSet;    /*         parameters    */
483 #endif
484     MapleVector<regno_t> intSpillRegSet; /* integer regs put aside for spills */
485 
486     /* and register */
487     uint32 intCallerMask = 0;          /* bit mask for all possible caller int */
488     uint32 intCalleeMask = 0;          /*                           callee     */
489     uint32 intParamMask = 0;           /*     (physical-register)   parameter  */
490 #ifdef ARK_LITECG_DEBUG
491     MapleSet<uint32> fpCallerRegSet;   /* float caller saved */
492     MapleSet<uint32> fpCalleeRegSet;   /*       callee       */
493     MapleSet<uint32> fpParamRegSet;    /*       parameter    */
494 #endif
495     MapleVector<uint32> fpSpillRegSet; /* float regs put aside for spills */
496     MapleUnorderedSet<uint32> loopBBRegSet;
497     Bfs *bfs = nullptr;
498     uint32 fpCallerMask = 0;       /* bit mask for all possible caller fp */
499     uint32 fpCalleeMask = 0;       /*                           callee    */
500     uint32 fpParamMask = 0;        /*      (physical-register)  parameter */
501     uint64 blockForbiddenMask = 0; /* bit mask for forbidden physical reg */
502     uint32 debugSpillCnt = 0;
503     MapleVector<uint64> regUsedInBB;
504     uint32 maxInsnNum = 0;
505     regno_t minVregNum = 0xFFFFFFFF;
506     regno_t maxVregNum = 0;
507     bool spillAll = false;
508     bool needExtraSpillReg = false;
509     bool multiVregMov = false; /*mov vreg vreg*/
510     uint64 spillCount = 0;
511     uint64 reloadCount = 0;
512     uint64 callerSaveSpillCount = 0;
513     uint64 callerSaveReloadCount = 0;
514     MapleQueue<LiveInterval *> liQue;
515     MapleUnorderedMap<regno_t, RegOperand*> derivedRef2Base;
516 };
517 } /* namespace maplebe */
518 
519 #endif /* MAPLEBE_INCLUDE_CG_REG_ALLOC_LSRA_H */
520