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