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 #include "reg_alloc_lsra.h"
17 #include <iomanip>
18 #include <queue>
19 #include <chrono>
20 #include "loop.h"
21
22 namespace maplebe {
23 /*
24 * ==================
25 * = Linear Scan RA
26 * ==================
27 */
28 namespace {
29 constexpr uint32 kSpilled = 1;
30 constexpr uint32 kMinLiveIntervalLength = 20;
31 constexpr uint32 kPrintedActiveListLength = 10;
32 /* Here, kLoopWeight is a fine-tuned empirical parameter */
33 constexpr uint32 kLoopWeight = 4;
34 } // namespace
35
36 #define IN_SPILL_RANGE \
37 (cgFunc->GetName().find(CGOptions::GetDumpFunc()) != std::string::npos && ++debugSpillCnt && \
38 (CGOptions::GetSpillRangesBegin() < debugSpillCnt) && (debugSpillCnt < CGOptions::GetSpillRangesEnd()))
39
40 #ifdef RA_PERF_ANALYSIS
41 static long bfsUS = 0;
42 static long liveIntervalUS = 0;
43 static long holesUS = 0;
44 static long lsraUS = 0;
45 static long finalizeUS = 0;
46 static long totalUS = 0;
47
printLSRATime()48 extern void printLSRATime()
49 {
50 std::cout << "============================================================\n";
51 std::cout << " LSRA sub-phase time information \n";
52 std::cout << "============================================================\n";
53 std::cout << "BFS BB sorting cost: " << bfsUS << "us \n";
54 std::cout << "live interval computing cost: " << liveIntervalUS << "us \n";
55 std::cout << "live range approximation cost: " << holesUS << "us \n";
56 std::cout << "LSRA cost: " << lsraUS << "us \n";
57 std::cout << "finalize cost: " << finalizeUS << "us \n";
58 std::cout << "LSRA total cost: " << totalUS << "us \n";
59 std::cout << "============================================================\n";
60 }
61 #endif
62
63 /*
64 * This LSRA implementation is an interpretation of the [Poletto97] paper.
65 * BFS BB ordering is used to order the instructions. The live intervals are vased on
66 * this instruction order. All vreg defines should come before an use, else a warning is
67 * given.
68 * Live interval is traversed in order from lower instruction order to higher order.
69 * When encountering a live interval for the first time, it is assumed to be live and placed
70 * inside the 'active' structure until the vreg's last access. During the time a vreg
71 * is in 'active', the vreg occupies a physical register allocation and no other vreg can
72 * be allocated the same physical register.
73 */
PrintRegSet(const MapleSet<uint32> & set,const std::string & str) const74 void LSRALinearScanRegAllocator::PrintRegSet(const MapleSet<uint32> &set, const std::string &str) const
75 {
76 LogInfo::MapleLogger() << str;
77 for (auto reg : set) {
78 LogInfo::MapleLogger() << " " << reg;
79 }
80 LogInfo::MapleLogger() << "\n";
81 }
82
CheckForReg(Operand & opnd,const Insn & insn,const LiveInterval & li,regno_t regNO,bool isDef) const83 bool LSRALinearScanRegAllocator::CheckForReg(Operand &opnd, const Insn &insn, const LiveInterval &li, regno_t regNO,
84 bool isDef) const
85 {
86 if (!opnd.IsRegister()) {
87 return false;
88 }
89 auto ®Opnd = static_cast<RegOperand &>(opnd);
90 if (regOpnd.GetRegisterType() == kRegTyCc || regOpnd.GetRegisterType() == kRegTyVary) {
91 return false;
92 }
93 if (regOpnd.GetRegisterNumber() == regNO) {
94 LogInfo::MapleLogger() << "set object circle at " << insn.GetId() << "," << li.GetRegNO()
95 << " size 5 fillcolor rgb \"";
96 if (isDef) {
97 LogInfo::MapleLogger() << "black\"\n";
98 } else {
99 LogInfo::MapleLogger() << "orange\"\n";
100 }
101 }
102 return true;
103 }
104
PrintLiveRanges(const LiveInterval & li) const105 void LSRALinearScanRegAllocator::PrintLiveRanges(const LiveInterval &li) const
106 {
107 if (li.GetAssignedReg() != 0) {
108 uint32 base = (li.GetRegType() == kRegTyInt) ? firstIntReg : firstFpReg;
109 LogInfo::MapleLogger() << "(assigned R" << (li.GetAssignedReg() - base) << ")";
110 }
111 if (li.GetStackSlot() == kSpilled) {
112 LogInfo::MapleLogger() << "(spill)";
113 }
114 if (li.IsShouldSave()) {
115 LogInfo::MapleLogger() << "(ShouldSave)";
116 }
117 for (auto range : li.GetRanges()) {
118 LogInfo::MapleLogger() << "[" << range.GetStart() << ", " << range.GetEnd() << "]"
119 << " ";
120 }
121 if (li.GetSplitNext() != nullptr) {
122 LogInfo::MapleLogger() << "### SPLIT ### ";
123 PrintLiveRanges(*li.GetSplitNext());
124 }
125 LogInfo::MapleLogger() << "\n";
126 }
127
PrintAllLiveRanges() const128 void LSRALinearScanRegAllocator::PrintAllLiveRanges() const
129 {
130 LogInfo::MapleLogger() << "func: " << cgFunc->GetName() << "\n";
131 for (auto *li : liveIntervalsArray) {
132 if (li == nullptr || li->GetRegNO() == 0) {
133 continue;
134 }
135 LogInfo::MapleLogger() << "vreg" << li->GetRegNO() << ": ";
136 if (li->GetSplitParent() != nullptr) {
137 PrintLiveRanges(*li->GetSplitParent());
138 } else {
139 PrintLiveRanges(*li);
140 }
141 }
142 }
143
144 /*
145 * This is a support routine to compute the overlapping live intervals in graph form.
146 * The output file can be viewed by gnuplot.
147 * Despite the function name of LiveRanges, it is using live intervals.
148 */
PrintLiveRangesGraph() const149 void LSRALinearScanRegAllocator::PrintLiveRangesGraph() const
150 {
151 /* ================= Output to plot.pg =============== */
152 std::ofstream out("plot.pg");
153 CHECK_FATAL(out.is_open(), "Failed to open output file: plot.pg");
154 std::streambuf *coutBuf = LogInfo::MapleLogger().rdbuf(); /* old buf */
155 LogInfo::MapleLogger().rdbuf(out.rdbuf()); /* new buf */
156
157 LogInfo::MapleLogger() << "#!/usr/bin/gnuplot\n";
158 LogInfo::MapleLogger() << "#maxInsnNum " << maxInsnNum << "\n";
159 LogInfo::MapleLogger() << "#minVregNum " << minVregNum << "\n";
160 LogInfo::MapleLogger() << "#maxVregNum " << maxVregNum << "\n";
161 LogInfo::MapleLogger() << "reset\nset terminal png\n";
162 LogInfo::MapleLogger() << "set xrange [1:" << maxInsnNum << "]\n";
163 LogInfo::MapleLogger() << "set grid\nset style data linespoints\n";
164 LogInfo::MapleLogger() << "set datafile missing '0'\n";
165 std::vector<std::vector<uint32>> graph(maxVregNum, std::vector<uint32>(maxInsnNum, 0));
166
167 uint32 minY = 0xFFFFFFFF;
168 uint32 maxY = 0;
169 for (auto *li : liveIntervalsArray) {
170 if (li == nullptr || li->GetRegNO() == 0) {
171 continue;
172 }
173 uint32 regNO = li->GetRegNO();
174 if ((li->GetLastUse() - li->GetFirstDef()) < kMinLiveIntervalLength) {
175 continue;
176 }
177 if (regNO < minY) {
178 minY = regNO;
179 }
180 if (regNO > maxY) {
181 maxY = regNO;
182 }
183 uint32 n;
184 for (n = 0; n <= (li->GetFirstDef() - 1); ++n) {
185 graph[regNO - minVregNum][n] = 0;
186 }
187 if (li->GetLastUse() >= n) {
188 for (; n <= (li->GetLastUse() - 1); ++n) {
189 graph[regNO - minVregNum][n] = regNO;
190 }
191 }
192 for (; n < maxInsnNum; ++n) {
193 graph[regNO - minVregNum][n] = 0;
194 }
195
196 for (auto *bb : bfs->sortedBBs) {
197 FOR_BB_INSNS(insn, bb) {
198 const InsnDesc *md = insn->GetDesc();
199 uint32 opndNum = insn->GetOperandSize();
200 for (uint32 iSecond = 0; iSecond < opndNum; ++iSecond) {
201 Operand &opnd = insn->GetOperand(iSecond);
202 const OpndDesc *regProp = md->GetOpndDes(iSecond);
203 DEBUG_ASSERT(regProp != nullptr,
204 "pointer is null in LSRALinearScanRegAllocator::PrintLiveRangesGraph");
205 bool isDef = regProp->IsRegDef();
206 if (opnd.IsList()) {
207 auto &listOpnd = static_cast<ListOperand &>(opnd);
208 for (auto op : listOpnd.GetOperands()) {
209 (void)CheckForReg(*op, *insn, *li, regNO, isDef);
210 }
211 } else if (opnd.IsMemoryAccessOperand()) {
212 auto &memOpnd = static_cast<MemOperand &>(opnd);
213 Operand *base = memOpnd.GetBaseRegister();
214 Operand *offset = memOpnd.GetIndexRegister();
215 if (base != nullptr && !CheckForReg(*base, *insn, *li, regNO, false)) {
216 continue;
217 }
218 if (offset != nullptr && !CheckForReg(*offset, *insn, *li, regNO, false)) {
219 continue;
220 }
221 } else {
222 (void)CheckForReg(opnd, *insn, *li, regNO, isDef);
223 }
224 }
225 }
226 }
227 }
228 LogInfo::MapleLogger() << "set yrange [" << (minY - 1) << ":" << (maxY + 1) << "]\n";
229
230 LogInfo::MapleLogger() << "plot \"plot.dat\" using 1:2 title \"R" << minVregNum << "\"";
231 for (uint32 i = 1; i < ((maxVregNum - minVregNum) + 1); ++i) {
232 LogInfo::MapleLogger() << ", \\\n\t\"\" using 1:" << (i + kDivide2) << " title \"R" << (minVregNum + i) << "\"";
233 }
234 LogInfo::MapleLogger() << ";\n";
235
236 /* ================= Output to plot.dat =============== */
237 std::ofstream out2("plot.dat");
238 CHECK_FATAL(out2.is_open(), "Failed to open output file: plot.dat");
239 LogInfo::MapleLogger().rdbuf(out2.rdbuf()); /* new buf */
240 LogInfo::MapleLogger() << "##reg";
241 for (uint32 i = minVregNum; i <= maxVregNum; ++i) {
242 LogInfo::MapleLogger() << " R" << i;
243 }
244 LogInfo::MapleLogger() << "\n";
245 for (uint32 n = 0; n < maxInsnNum; ++n) {
246 LogInfo::MapleLogger() << (n + 1);
247 for (uint32 i = minVregNum; i <= maxVregNum; ++i) {
248 LogInfo::MapleLogger() << " " << graph[i - minVregNum][n];
249 }
250 LogInfo::MapleLogger() << "\n";
251 }
252 LogInfo::MapleLogger().rdbuf(coutBuf);
253 }
254
SpillStackMapInfo()255 void LSRALinearScanRegAllocator::SpillStackMapInfo()
256 {
257 const auto &referenceMapInsns = cgFunc->GetStackMapInsns();
258
259 for (auto *insn : referenceMapInsns) {
260 auto &deoptInfo = insn->GetStackMap()->GetDeoptInfo();
261 const auto &deoptBundleInfo = deoptInfo.GetDeoptBundleInfo();
262 for (const auto &item : deoptBundleInfo) {
263 const auto *opnd = item.second;
264 if (!opnd->IsRegister()) {
265 continue;
266 }
267 auto *li = liveIntervalsArray[(static_cast<const RegOperand *>(opnd))->GetRegisterNumber()];
268 if (li != nullptr) {
269 if (needDump) {
270 PrintLiveInterval(*li, "Spill Deopt:");
271 }
272 li->SetStackSlot(kSpilled);
273 li->SetShouldSave(false);
274 }
275 }
276
277 auto *stackMapLiveIn = insn->GetStackMapLiveIn();
278 std::set<uint32> setInfo;
279 stackMapLiveIn->GetInfo().ConvertToSet(setInfo);
280 for (auto regNO : setInfo) {
281 if (!cgFunc->IsRegReference(regNO)) {
282 continue;
283 }
284 auto *li = liveIntervalsArray[regNO];
285 if (li == nullptr) {
286 continue;
287 }
288 auto itr = dereivedRef2Base.find(regNO);
289 if (itr != dereivedRef2Base.end()) {
290 DEBUG_ASSERT(liveIntervalsArray[itr->second] != nullptr, "empty li");
291 if (needDump) {
292 PrintLiveInterval(*liveIntervalsArray[itr->second], "Spill StackMap dereivedRef:");
293 }
294 liveIntervalsArray[itr->second]->SetStackSlot(kSpilled);
295 liveIntervalsArray[itr->second]->SetShouldSave(false);
296 }
297 if (needDump) {
298 PrintLiveInterval(*li, "Spill StackMap:");
299 }
300 li->SetStackSlot(kSpilled);
301 li->SetShouldSave(false);
302 }
303 }
304 }
305
PrintLiveInterval(const LiveInterval & li,const std::string & str) const306 void LSRALinearScanRegAllocator::PrintLiveInterval(const LiveInterval &li, const std::string &str) const
307 {
308 LogInfo::MapleLogger() << str << "\n";
309 if (li.GetIsCall() != nullptr) {
310 LogInfo::MapleLogger() << " firstDef " << li.GetFirstDef();
311 LogInfo::MapleLogger() << " isCall";
312 } else if (li.GetPhysUse()) {
313 LogInfo::MapleLogger() << "\tregNO " << li.GetRegNO();
314 LogInfo::MapleLogger() << " firstDef " << li.GetFirstDef();
315 LogInfo::MapleLogger() << " physUse " << li.GetPhysUse();
316 LogInfo::MapleLogger() << " endByCall " << li.IsEndByCall();
317 } else {
318 LogInfo::MapleLogger() << "\tregNO " << std::setw(5) << li.GetRegNO(); /* show regno with 5 width */
319 LogInfo::MapleLogger() << " firstDef " << std::setw(8) << li.GetFirstDef(); /* show firstDef with 8 width */
320 LogInfo::MapleLogger() << " lastUse " << std::setw(8) << li.GetLastUse(); /* show lastUse with 8 width */
321 LogInfo::MapleLogger() << " assigned " << li.GetAssignedReg();
322 LogInfo::MapleLogger() << " refCount " << li.GetRefCount();
323 LogInfo::MapleLogger() << " priority " << li.GetPriority();
324 }
325 LogInfo::MapleLogger() << "\n";
326 }
327
PrintParamQueue(const std::string & str)328 void LSRALinearScanRegAllocator::PrintParamQueue(const std::string &str)
329 {
330 LogInfo::MapleLogger() << str << "\n";
331 for (SingleQue &que : intParamQueue) {
332 if (que.empty()) {
333 continue;
334 }
335 LiveInterval *li = que.front();
336 LiveInterval *last = que.back();
337 PrintLiveInterval(*li, "");
338 while (li != last) {
339 que.pop_front();
340 que.push_back(li);
341 li = que.front();
342 PrintLiveInterval(*li, "");
343 }
344 que.pop_front();
345 que.push_back(li);
346 }
347 }
348
PrintCallQueue(const std::string & str) const349 void LSRALinearScanRegAllocator::PrintCallQueue(const std::string &str) const
350 {
351 LogInfo::MapleLogger() << str << "\n";
352 for (auto callInsnID : callQueue) {
353 LogInfo::MapleLogger() << callInsnID << " ";
354 }
355 LogInfo::MapleLogger() << "\n";
356 }
357
PrintActiveList(const std::string & str,uint32 len) const358 void LSRALinearScanRegAllocator::PrintActiveList(const std::string &str, uint32 len) const
359 {
360 uint32 count = 0;
361 LogInfo::MapleLogger() << str << " " << active.size() << "\n";
362 for (auto *li : active) {
363 PrintLiveInterval(*li, "");
364 ++count;
365 if ((len != 0) && (count == len)) {
366 break;
367 }
368 }
369 }
370
PrintActiveListSimple() const371 void LSRALinearScanRegAllocator::PrintActiveListSimple() const
372 {
373 for (const auto *li : active) {
374 uint32 assignedReg = li->GetAssignedReg();
375 LogInfo::MapleLogger() << li->GetRegNO() << "(" << assignedReg << ", ";
376 if (li->GetPhysUse()) {
377 LogInfo::MapleLogger() << "p) ";
378 } else {
379 LogInfo::MapleLogger() << li->GetFirstAcrossedCall();
380 }
381 LogInfo::MapleLogger() << "<" << li->GetFirstDef() << "," << li->GetLastUse() << ">) ";
382 }
383 LogInfo::MapleLogger() << "\n";
384 }
385
PrintLiveIntervals() const386 void LSRALinearScanRegAllocator::PrintLiveIntervals() const
387 {
388 /* vreg LogInfo */
389 for (auto *li : liveIntervalsArray) {
390 if (li == nullptr || li->GetRegNO() == 0) {
391 continue;
392 }
393 PrintLiveInterval(*li, "");
394 }
395 LogInfo::MapleLogger() << "\n";
396 /* preg LogInfo */
397 for (auto param : intParamQueue) {
398 for (auto *li : param) {
399 if (li == nullptr || li->GetRegNO() == 0) {
400 continue;
401 }
402 PrintLiveInterval(*li, "");
403 }
404 }
405 LogInfo::MapleLogger() << "\n";
406 }
407
DebugCheckActiveList() const408 void LSRALinearScanRegAllocator::DebugCheckActiveList() const
409 {
410 LiveInterval *prev = nullptr;
411 for (auto *li : active) {
412 if (prev != nullptr) {
413 if ((li->GetRegNO() <= regInfo->GetLastParamsFpReg()) &&
414 (prev->GetRegNO() > regInfo->GetLastParamsFpReg())) {
415 if (li->GetFirstDef() < prev->GetFirstDef()) {
416 LogInfo::MapleLogger() << "ERRer: active list with out of order phys + vreg\n";
417 PrintLiveInterval(*prev, "prev");
418 PrintLiveInterval(*li, "current");
419 PrintActiveList("Active", kPrintedActiveListLength);
420 }
421 }
422 if ((li->GetRegNO() <= regInfo->GetLastParamsFpReg()) &&
423 (prev->GetRegNO() <= regInfo->GetLastParamsFpReg())) {
424 if (li->GetFirstDef() < prev->GetFirstDef()) {
425 LogInfo::MapleLogger() << "ERRer: active list with out of order phys reg use\n";
426 PrintLiveInterval(*prev, "prev");
427 PrintLiveInterval(*li, "current");
428 PrintActiveList("Active", kPrintedActiveListLength);
429 }
430 }
431 } else {
432 prev = li;
433 }
434 }
435 }
436
437 /*
438 * Prepare the free physical register pool for allocation.
439 * When a physical register is allocated, it is removed from the pool.
440 * The physical register is re-inserted into the pool when the associated live
441 * interval has ended.
442 */
InitFreeRegPool()443 void LSRALinearScanRegAllocator::InitFreeRegPool()
444 {
445 for (regno_t regNO = regInfo->GetInvalidReg(); regNO < regInfo->GetAllRegNum(); ++regNO) {
446 if (!regInfo->IsAvailableReg(regNO)) {
447 continue;
448 }
449 if (regInfo->IsGPRegister(regNO)) {
450 if (regInfo->IsYieldPointReg(regNO)) {
451 continue;
452 }
453 /* ExtraSpillReg */
454 if (regInfo->IsSpillRegInRA(regNO, needExtraSpillReg)) {
455 intSpillRegSet.push_back(regNO - firstIntReg);
456 continue;
457 }
458 if (regInfo->IsCalleeSavedReg(regNO)) {
459 /* callee-saved registers */
460 (void)intCalleeRegSet.insert(regNO - firstIntReg);
461 intCalleeMask |= 1u << (regNO - firstIntReg);
462 } else {
463 /* caller-saved registers */
464 (void)intCallerRegSet.insert(regNO - firstIntReg);
465 intCallerMask |= 1u << (regNO - firstIntReg);
466 }
467 } else {
468 /* fp ExtraSpillReg */
469 if (regInfo->IsSpillRegInRA(regNO, needExtraSpillReg)) {
470 fpSpillRegSet.push_back(regNO - firstFpReg);
471 continue;
472 }
473 if (regInfo->IsCalleeSavedReg(regNO)) {
474 /* fp callee-saved registers */
475 (void)fpCalleeRegSet.insert(regNO - firstFpReg);
476 fpCalleeMask |= 1u << (regNO - firstFpReg);
477 } else {
478 /* fp caller-saved registers */
479 (void)fpCallerRegSet.insert(regNO - firstFpReg);
480 fpCallerMask |= 1u << (regNO - firstFpReg);
481 }
482 }
483 }
484
485 if (needDump) {
486 PrintRegSet(intCallerRegSet, "ALLOCATABLE_INT_CALLER");
487 PrintRegSet(intCalleeRegSet, "ALLOCATABLE_INT_CALLEE");
488 PrintRegSet(intParamRegSet, "ALLOCATABLE_INT_PARAM");
489 PrintRegSet(fpCallerRegSet, "ALLOCATABLE_FP_CALLER");
490 PrintRegSet(fpCalleeRegSet, "ALLOCATABLE_FP_CALLEE");
491 PrintRegSet(fpParamRegSet, "ALLOCATABLE_FP_PARAM");
492 LogInfo::MapleLogger() << "INT_SPILL_REGS";
493 for (uint32 intSpillRegNO : intSpillRegSet) {
494 LogInfo::MapleLogger() << " " << intSpillRegNO;
495 }
496 LogInfo::MapleLogger() << "\n";
497 LogInfo::MapleLogger() << "FP_SPILL_REGS";
498 for (uint32 fpSpillRegNO : fpSpillRegSet) {
499 LogInfo::MapleLogger() << " " << fpSpillRegNO;
500 }
501 LogInfo::MapleLogger() << "\n";
502 LogInfo::MapleLogger() << std::hex;
503 LogInfo::MapleLogger() << "INT_CALLER_MASK " << intCallerMask << "\n";
504 LogInfo::MapleLogger() << "INT_CALLEE_MASK " << intCalleeMask << "\n";
505 LogInfo::MapleLogger() << "INT_PARAM_MASK " << intParamMask << "\n";
506 LogInfo::MapleLogger() << "FP_CALLER_FP_MASK " << fpCallerMask << "\n";
507 LogInfo::MapleLogger() << "FP_CALLEE_FP_MASK " << fpCalleeMask << "\n";
508 LogInfo::MapleLogger() << "FP_PARAM_FP_MASK " << fpParamMask << "\n";
509 LogInfo::MapleLogger() << std::dec;
510 }
511 }
512
RecordPhysRegs(const RegOperand & regOpnd,uint32 insnNum,bool isDef)513 void LSRALinearScanRegAllocator::RecordPhysRegs(const RegOperand ®Opnd, uint32 insnNum, bool isDef)
514 {
515 RegType regType = regOpnd.GetRegisterType();
516 uint32 regNO = regOpnd.GetRegisterNumber();
517 if (regType == kRegTyCc || regType == kRegTyVary) {
518 return;
519 }
520 if (regInfo->IsUntouchableReg(regNO)) {
521 return;
522 }
523 if (!regInfo->IsPreAssignedReg(regNO)) {
524 return;
525 }
526 if (isDef) {
527 /* parameter/return register def is assumed to be live until a call. */
528 auto *li = memPool->New<LiveInterval>(*memPool);
529 li->SetRegNO(regNO);
530 li->SetRegType(regType);
531 li->SetStackSlot(0xFFFFFFFF);
532 li->SetFirstDef(insnNum);
533 li->SetPhysUse(insnNum);
534 li->SetAssignedReg(regNO);
535
536 if (regType == kRegTyInt) {
537 intParamQueue[regInfo->GetIntParamRegIdx(regNO)].push_back(li);
538 } else {
539 fpParamQueue[regInfo->GetFpParamRegIdx(regNO)].push_back(li);
540 }
541 } else {
542 if (regType == kRegTyInt) {
543 CHECK_FATAL(!intParamQueue[regInfo->GetIntParamRegIdx(regNO)].empty(),
544 "was not defined before use, impossible");
545 LiveInterval *li = intParamQueue[regInfo->GetIntParamRegIdx(regNO)].back();
546 li->SetPhysUse(insnNum);
547 } else {
548 CHECK_FATAL(!fpParamQueue[regInfo->GetFpParamRegIdx(regNO)].empty(),
549 "was not defined before use, impossible");
550 LiveInterval *li = fpParamQueue[regInfo->GetFpParamRegIdx(regNO)].back();
551 li->SetPhysUse(insnNum);
552 }
553 }
554 }
555
UpdateLiveIntervalState(const BB & bb,LiveInterval & li) const556 void LSRALinearScanRegAllocator::UpdateLiveIntervalState(const BB &bb, LiveInterval &li) const
557 {
558 if (bb.IsCatch()) {
559 li.SetInCatchState();
560 } else {
561 li.SetNotInCatchState();
562 }
563
564 if (bb.GetInternalFlag1()) {
565 li.SetInCleanupState();
566 } else {
567 li.SetNotInCleanupState(bb.GetId() == 1);
568 }
569 }
570
UpdateRegUsedInfo(LiveInterval & li,regno_t regNO)571 void LSRALinearScanRegAllocator::UpdateRegUsedInfo(LiveInterval &li, regno_t regNO)
572 {
573 uint32 index = regNO / (sizeof(uint64) * k8ByteSize);
574 uint64 bit = regNO % (sizeof(uint64) * k8ByteSize);
575 if ((regUsedInBB[index] & (static_cast<uint64>(1) << bit)) != 0) {
576 li.SetMultiUseInBB(true);
577 }
578 regUsedInBB[index] |= (static_cast<uint64>(1) << bit);
579
580 if (minVregNum > regNO) {
581 minVregNum = regNO;
582 }
583 if (maxVregNum < regNO) {
584 maxVregNum = regNO;
585 }
586 }
587
588 /* main entry function for live interval computation. */
SetupLiveInterval(Operand & opnd,Insn & insn,bool isDef,uint32 & nUses,uint32 regSize)589 void LSRALinearScanRegAllocator::SetupLiveInterval(Operand &opnd, Insn &insn, bool isDef, uint32 &nUses, uint32 regSize)
590 {
591 if (!opnd.IsRegister()) {
592 return;
593 }
594 auto ®Opnd = static_cast<RegOperand &>(opnd);
595 uint32 insnNum = insn.GetId();
596 if (regOpnd.IsPhysicalRegister()) {
597 RecordPhysRegs(regOpnd, insnNum, isDef);
598 return;
599 }
600 RegType regType = regOpnd.GetRegisterType();
601 if (regType == kRegTyCc || regType == kRegTyVary) {
602 return;
603 }
604
605 LiveInterval *li = nullptr;
606 uint32 regNO = regOpnd.GetRegisterNumber();
607 if (liveIntervalsArray[regNO] == nullptr) {
608 li = memPool->New<LiveInterval>(*memPool);
609 li->SetRegNO(regNO);
610 li->SetStackSlot(0xFFFFFFFF);
611 liveIntervalsArray[regNO] = li;
612 liQue.push_back(li);
613 } else {
614 li = liveIntervalsArray[regNO];
615 }
616 li->SetRegType(regType);
617
618 BB *curBB = insn.GetBB();
619 if (isDef) {
620 /* never set to 0 before, why consider this condition ? */
621 if (li->GetFirstDef() == 0) {
622 li->SetFirstDef(insnNum);
623 li->SetLastUse(insnNum + 1);
624 } else if (!curBB->IsUnreachable()) {
625 if (li->GetLastUse() < insnNum || li->IsUseBeforeDef()) {
626 li->SetLastUse(insnNum + 1);
627 }
628 }
629 /*
630 * try-catch related
631 * Not set when extending live interval with bb's livein in ComputeLiveInterval.
632 */
633 li->SetResultCount(li->GetResultCount() + 1);
634 // add range
635 li->AddRange(insn.GetId(), insn.GetId());
636 } else {
637 if (li->GetFirstDef() == 0) {
638 DEBUG_ASSERT(false, "SetupLiveInterval: use before def");
639 }
640 /*
641 * In ComputeLiveInterval when extending live interval using
642 * live-out information, li created does not have a type.
643 */
644 if (!curBB->IsUnreachable()) {
645 li->SetLastUse(insnNum);
646 }
647 ++nUses;
648 // update range
649 if (li->GetRanges().empty()) {
650 li->AddRange(insn.GetId(), insn.GetId());
651 } else {
652 li->GetRanges().back().SetEnd(insn.GetId());
653 }
654 }
655 UpdateLiveIntervalState(*curBB, *li);
656 if (isDef) {
657 li->SetMaxDefSize(std::max(regSize, li->GetMaxDefSize()));
658 } else {
659 li->SetMaxUseSize(std::max(regSize, li->GetMaxUseSize()));
660 }
661 if (li->GetMaxDefSize() == 0) {
662 li->SetSpillSize(li->GetMaxUseSize());
663 } else if (li->GetMaxUseSize() == 0) {
664 li->SetSpillSize(li->GetMaxDefSize());
665 } else {
666 li->SetSpillSize(std::min(li->GetMaxDefSize(), li->GetMaxUseSize()));
667 }
668 li->SetRefCount(li->GetRefCount() + 1);
669 li->AddUsePositions(insnNum);
670 UpdateRegUsedInfo(*li, regNO);
671
672 /* setup the def/use point for it */
673 DEBUG_ASSERT(regNO < liveIntervalsArray.size(), "out of range of vector liveIntervalsArray");
674 }
675
676 /*
677 * Support 'hole' in LSRA.
678 * For a live interval, there might be multiple segments of live ranges,
679 * and between these segments a 'hole'.
680 * Some other short lived vreg can go into these 'holes'.
681 *
682 * from : starting instruction sequence id
683 * to : ending instruction sequence id
684 */
AddRange(uint32 from,uint32 to)685 void LSRALinearScanRegAllocator::LiveInterval::AddRange(uint32 from, uint32 to)
686 {
687 if (ranges.empty()) {
688 ranges.emplace_back(from, to);
689 return;
690 }
691 /* create a new range */
692 if (from > ranges.back().GetEnd()) {
693 ranges.emplace_back(from, to);
694 return;
695 }
696 DEBUG_ASSERT(to >= ranges.back().GetStart(), "No possible on forward traverse.");
697 if (to >= ranges.back().GetEnd() && from < ranges.back().GetStart()) {
698 ranges.back().SetStart(from);
699 ranges.back().SetEnd(to);
700 return;
701 }
702 /* extend it's range forward. e.g. def-use opnd */
703 if (to >= ranges.back().GetEnd() && from < ranges.back().GetEnd()) {
704 ranges.back().SetEnd(to);
705 return;
706 }
707 return;
708 }
709
FindPosRange(uint32 pos)710 MapleVector<LSRALinearScanRegAllocator::LinearRange>::iterator LSRALinearScanRegAllocator::LiveInterval::FindPosRange(
711 uint32 pos)
712 {
713 while (rangeFinder != ranges.end()) {
714 if (rangeFinder->GetEnd() >= pos) {
715 break;
716 }
717 ++rangeFinder;
718 }
719 return rangeFinder;
720 }
721
SetupIntervalRangesByOperand(Operand & opnd,const Insn & insn,uint32 blockFrom,bool isDef)722 void LSRALinearScanRegAllocator::SetupIntervalRangesByOperand(Operand &opnd, const Insn &insn, uint32 blockFrom,
723 bool isDef)
724 {
725 auto ®Opnd = static_cast<RegOperand &>(opnd);
726 RegType regType = regOpnd.GetRegisterType();
727 if (regType == kRegTyCc || regType == kRegTyVary) {
728 return;
729 }
730 regno_t regNO = regOpnd.GetRegisterNumber();
731 if (regNO <= regInfo->GetAllRegNum()) {
732 return;
733 }
734 if (!isDef) {
735 liveIntervalsArray[regNO]->AddRange(blockFrom, insn.GetId());
736 return;
737 }
738 if (liveIntervalsArray[regNO]->GetRanges().empty()) {
739 liveIntervalsArray[regNO]->AddRange(insn.GetId(), insn.GetId());
740 } else {
741 liveIntervalsArray[regNO]->GetRanges().front().SetStart(insn.GetId());
742 }
743 liveIntervalsArray[regNO]->AddUsePositions(insn.GetId());
744 }
745
746 /* Extend live interval with live-in info */
UpdateLiveIntervalByLiveIn(const BB & bb,uint32 insnNum)747 void LSRALinearScanRegAllocator::UpdateLiveIntervalByLiveIn(const BB &bb, uint32 insnNum)
748 {
749 for (const auto ®NO : bb.GetLiveInRegNO()) {
750 if (!regInfo->IsVirtualRegister(regNO)) {
751 /* Do not consider physical regs. */
752 continue;
753 }
754 DEBUG_ASSERT(regNO < liveIntervalsArray.size(), "index out of range.");
755 LiveInterval *liOuter = liveIntervalsArray[regNO];
756 if (liOuter != nullptr) {
757 // add live interval range
758 liOuter->AddRange(insnNum, insnNum);
759 continue;
760 }
761 if (bb.IsEmpty() && bb.GetId() != 1) {
762 continue;
763 }
764 /*
765 * try-catch related
766 * Since it is livein but not seen before, its a use before def
767 * spill it temporarily
768 */
769 auto *li = memPool->New<LiveInterval>(*memPool);
770 li->SetRegNO(regNO);
771 li->SetStackSlot(kSpilled);
772 liveIntervalsArray[regNO] = li;
773 li->SetFirstDef(insnNum);
774 liQue.push_back(li);
775
776 li->SetUseBeforeDef(true);
777
778 // add live interval range
779 li->AddRange(insnNum, insnNum);
780
781 if (!bb.IsUnreachable()) {
782 if (bb.GetId() != 1) {
783 LogInfo::MapleLogger() << "ERROR: " << regNO << " use before def in bb " << bb.GetId() << " : "
784 << cgFunc->GetName() << "\n";
785 DEBUG_ASSERT(false, "There should only be [use before def in bb 1], temporarily.");
786 }
787 LogInfo::MapleLogger() << "WARNING: " << regNO << " use before def in bb " << bb.GetId() << " : "
788 << cgFunc->GetName() << "\n";
789 }
790 UpdateLiveIntervalState(bb, *li);
791 }
792 }
793
794 /* traverse live in regNO, for each live in regNO create a new liveinterval */
UpdateParamLiveIntervalByLiveIn(const BB & bb,uint32 insnNum)795 void LSRALinearScanRegAllocator::UpdateParamLiveIntervalByLiveIn(const BB &bb, uint32 insnNum)
796 {
797 for (const auto ®NO : bb.GetLiveInRegNO()) {
798 if (!regInfo->IsPreAssignedReg(regNO)) {
799 continue;
800 }
801 auto *li = memPool->New<LiveInterval>(*memPool);
802 li->SetRegNO(regNO);
803 li->SetStackSlot(0xFFFFFFFF);
804 li->SetFirstDef(insnNum);
805 li->SetPhysUse(insnNum);
806 li->SetAssignedReg(regNO);
807
808 if (regInfo->IsGPRegister(regNO)) {
809 li->SetRegType(kRegTyInt);
810 intParamQueue[regInfo->GetIntParamRegIdx(regNO)].push_back(li);
811 } else {
812 li->SetRegType(kRegTyFloat);
813 fpParamQueue[regInfo->GetFpParamRegIdx(regNO)].push_back(li);
814 }
815 UpdateLiveIntervalState(bb, *li);
816 }
817 }
818
ComputeLiveIn(BB & bb,uint32 insnNum)819 void LSRALinearScanRegAllocator::ComputeLiveIn(BB &bb, uint32 insnNum)
820 {
821 if (bb.IsEmpty() && bb.GetId() != 1) {
822 return;
823 }
824 if (needDump) {
825 LogInfo::MapleLogger() << "bb(" << bb.GetId() << ")LIVEOUT:";
826 for (const auto &liveOutRegNO : bb.GetLiveOutRegNO()) {
827 LogInfo::MapleLogger() << " " << liveOutRegNO;
828 }
829 LogInfo::MapleLogger() << ".\n";
830 LogInfo::MapleLogger() << "bb(" << bb.GetId() << ")LIVEIN:";
831 for (const auto &liveInRegNO : bb.GetLiveInRegNO()) {
832 LogInfo::MapleLogger() << " " << liveInRegNO;
833 }
834 LogInfo::MapleLogger() << ".\n";
835 }
836
837 UpdateLiveIntervalByLiveIn(bb, insnNum);
838
839 if (bb.GetFirstInsn() == nullptr) {
840 return;
841 }
842 if (!bb.GetEhPreds().empty()) {
843 bb.InsertLiveInRegNO(firstIntReg);
844 bb.InsertLiveInRegNO(firstIntReg + 1);
845 }
846 UpdateParamLiveIntervalByLiveIn(bb, insnNum);
847 if (!bb.GetEhPreds().empty()) {
848 bb.EraseLiveInRegNO(firstIntReg);
849 bb.EraseLiveInRegNO(firstIntReg + 1);
850 }
851 }
852
ComputeLiveOut(BB & bb,uint32 insnNum)853 void LSRALinearScanRegAllocator::ComputeLiveOut(BB &bb, uint32 insnNum)
854 {
855 /*
856 * traverse live out regNO
857 * for each live out regNO if the last corresponding live interval is created within this bb
858 * update this lastUse of li to the end of BB
859 */
860 for (const auto ®NO : bb.GetLiveOutRegNO()) {
861 if (regInfo->IsPreAssignedReg(static_cast<regno_t>(regNO))) {
862 LiveInterval *liOut = nullptr;
863 if (regInfo->IsGPRegister(regNO)) {
864 if (intParamQueue[regInfo->GetIntParamRegIdx(regNO)].empty()) {
865 continue;
866 }
867 liOut = intParamQueue[regInfo->GetIntParamRegIdx(regNO)].back();
868 if (bb.GetFirstInsn() && liOut->GetFirstDef() >= bb.GetFirstInsn()->GetId()) {
869 liOut->SetPhysUse(insnNum);
870 }
871 } else {
872 if (fpParamQueue[regInfo->GetFpParamRegIdx(regNO)].empty()) {
873 continue;
874 }
875 liOut = fpParamQueue[regInfo->GetFpParamRegIdx(regNO)].back();
876 if (bb.GetFirstInsn() && liOut->GetFirstDef() >= bb.GetFirstInsn()->GetId()) {
877 liOut->SetPhysUse(insnNum);
878 }
879 }
880 }
881 /* Extend live interval with live-out info */
882 LiveInterval *li = liveIntervalsArray[regNO];
883 if (li != nullptr && !bb.IsEmpty()) {
884 li->SetLastUse(bb.GetLastInsn()->GetId());
885 UpdateLiveIntervalState(bb, *li);
886 if (bb.GetKind() == BB::kBBRangeGoto) {
887 li->SetSplitForbid(true);
888 }
889
890 // update live interval range
891 if (li->GetRanges().empty()) {
892 li->AddRange(insnNum, insnNum);
893 } else {
894 li->GetRanges().back().SetEnd(insnNum);
895 }
896 }
897 }
898 }
899
ComputeLiveIntervalForEachOperand(Insn & insn)900 void LSRALinearScanRegAllocator::ComputeLiveIntervalForEachOperand(Insn &insn)
901 {
902 uint32 numUses = 0;
903 const InsnDesc *md = insn.GetDesc();
904 uint32 opndNum = insn.GetOperandSize();
905 /*
906 * we need to process src opnd first just in case the src/dest vreg are the same and the src vreg belongs to the
907 * last interval.
908 */
909 for (int32 i = opndNum - 1; i >= 0; --i) {
910 Operand &opnd = insn.GetOperand(static_cast<uint32>(i));
911 const OpndDesc *opndDesc = md->GetOpndDes(i);
912 DEBUG_ASSERT(opndDesc != nullptr, "ptr null check.");
913 if (opnd.IsRegister()) {
914 auto ®Opnd = static_cast<RegOperand&>(opnd);
915 /* Specifically, the "use-def" opnd is treated as a "use" opnd */
916 bool isUse = opndDesc->IsRegUse();
917 /* Fixup: The size in the insn md of x64 is not accurate, and the size in the fload opnd
918 does not change, so we use the size in the opnd first. */
919 auto regSize = (regOpnd.GetRegisterType() == kRegTyInt ? opndDesc->GetSize() : regOpnd.GetSize());
920 SetupLiveInterval(opnd, insn, !isUse, numUses, regSize);
921 } else if (opnd.IsMemoryAccessOperand()) {
922 bool isDef = false;
923 auto &memOpnd = static_cast<MemOperand &>(opnd);
924 Operand *base = memOpnd.GetBaseRegister();
925 Operand *offset = memOpnd.GetIndexRegister();
926 if (base != nullptr) {
927 SetupLiveInterval(*base, insn, isDef, numUses, k64BitSize);
928 }
929 if (offset != nullptr) {
930 SetupLiveInterval(*offset, insn, isDef, numUses, k64BitSize);
931 }
932 } else if (opnd.IsList()) {
933 auto &listOpnd = static_cast<ListOperand &>(opnd);
934 for (auto op : listOpnd.GetOperands()) {
935 SetupLiveInterval(*op, insn, opndDesc->IsDef(), numUses, opnd.GetSize());
936 }
937 }
938 }
939 if (numUses >= regInfo->GetNormalUseOperandNum()) {
940 needExtraSpillReg = true;
941 }
942 }
943
ComputeLoopLiveIntervalPriority(const CGFuncLoops & loop)944 void LSRALinearScanRegAllocator::ComputeLoopLiveIntervalPriority(const CGFuncLoops &loop)
945 {
946 for (const auto *lp : loop.GetInnerLoops()) {
947 /* handle nested Loops */
948 ComputeLoopLiveIntervalPriority(*lp);
949 }
950 for (auto *bb : loop.GetLoopMembers()) {
951 if (bb->IsEmpty()) {
952 continue;
953 }
954 FOR_BB_INSNS(insn, bb) {
955 ComputeLoopLiveIntervalPriorityInInsn(*insn);
956 }
957 loopBBRegSet.clear();
958 }
959 }
960
ComputeLoopLiveIntervalPriorityInInsn(const Insn & insn)961 void LSRALinearScanRegAllocator::ComputeLoopLiveIntervalPriorityInInsn(const Insn &insn)
962 {
963 uint32 opndNum = insn.GetOperandSize();
964 for (uint32 i = 0; i < opndNum; ++i) {
965 Operand &opnd = insn.GetOperand(i);
966 if (!opnd.IsRegister()) {
967 continue;
968 }
969 auto ®Opnd = static_cast<RegOperand &>(opnd);
970 if (regOpnd.IsPhysicalRegister()) {
971 continue;
972 }
973 uint32 regNo = regOpnd.GetRegisterNumber();
974 LiveInterval *li = liveIntervalsArray[regNo];
975 if (li == nullptr || loopBBRegSet.find(regNo) != loopBBRegSet.end()) {
976 continue;
977 }
978 li->SetPriority(kLoopWeight * li->GetPriority());
979 (void)loopBBRegSet.insert(regNo);
980 }
981 return;
982 }
983
ComputeLiveInterval()984 void LSRALinearScanRegAllocator::ComputeLiveInterval()
985 {
986 liQue.clear();
987 uint32 regUsedInBBSz = (cgFunc->GetMaxVReg() / (sizeof(uint64) * k8ByteSize) + 1);
988 regUsedInBB.resize(regUsedInBBSz, 0);
989 uint32 insnNum = 1;
990 for (BB *bb : bfs->sortedBBs) {
991 ComputeLiveIn(*bb, insnNum);
992 FOR_BB_INSNS(insn, bb) {
993 insn->SetId(insnNum);
994 /* skip comment and debug insn */
995 if (!insn->IsMachineInstruction()) {
996 continue;
997 }
998
999 /* RecordCall, remember calls for caller/callee allocation. */
1000 if (insn->IsCall()) {
1001 if (!insn->GetIsThrow() || !bb->GetEhSuccs().empty()) {
1002 callQueue.emplace_back(insn->GetId());
1003 }
1004 }
1005
1006 ComputeLiveIntervalForEachOperand(*insn);
1007
1008 /* handle return value for call insn */
1009 if (insn->IsCall()) {
1010 /* For all backend architectures so far, adopt all RetRegs as Def via this insn,
1011 * and then their live begins.
1012 * next optimization, you can determine which registers are actually used.
1013 */
1014 RegOperand *retReg = nullptr;
1015 if (insn->GetRetType() == Insn::kRegInt) {
1016 for (uint32 i = 0; i < regInfo->GetIntRetRegsNum(); i++) {
1017 retReg = regInfo->GetOrCreatePhyRegOperand(regInfo->GetIntRetReg(i), k64BitSize, kRegTyInt);
1018 RecordPhysRegs(*retReg, insnNum, true);
1019 }
1020 } else {
1021 for (uint32 i = 0; i < regInfo->GetFpRetRegsNum(); i++) {
1022 retReg = regInfo->GetOrCreatePhyRegOperand(regInfo->GetFpRetReg(i), k64BitSize, kRegTyFloat);
1023 RecordPhysRegs(*retReg, insnNum, true);
1024 }
1025 }
1026 }
1027 ++insnNum;
1028 }
1029
1030 ComputeLiveOut(*bb, insnNum);
1031 }
1032
1033 maxInsnNum = insnNum - 1; /* insn_num started from 1 */
1034 regUsedInBB.clear();
1035 /* calculate Live Interval weight */
1036 for (auto *li : liveIntervalsArray) {
1037 if (li == nullptr || li->GetRegNO() == 0) {
1038 continue;
1039 }
1040 if (li->GetIsCall() != nullptr || li->GetPhysUse()) {
1041 continue;
1042 }
1043 if (li->GetLastUse() > li->GetFirstDef()) {
1044 li->SetPriority(static_cast<float>(li->GetRefCount()) /
1045 static_cast<float>(li->GetLastUse() - li->GetFirstDef()));
1046 } else {
1047 li->SetPriority(static_cast<float>(li->GetRefCount()) /
1048 static_cast<float>(li->GetFirstDef() - li->GetLastUse()));
1049 }
1050 }
1051
1052 /* enhance loop Live Interval Priority */
1053 if (!cgFunc->GetLoops().empty()) {
1054 for (const auto *lp : cgFunc->GetLoops()) {
1055 ComputeLoopLiveIntervalPriority(*lp);
1056 }
1057 }
1058
1059 if (needDump) {
1060 PrintLiveIntervals();
1061 }
1062 }
1063
1064 /* Calculate the weight of a live interval for pre-spill and flexible spill */
LiveIntervalAnalysis()1065 void LSRALinearScanRegAllocator::LiveIntervalAnalysis()
1066 {
1067 for (uint32 bbIdx = 0; bbIdx < bfs->sortedBBs.size(); ++bbIdx) {
1068 BB *bb = bfs->sortedBBs[bbIdx];
1069
1070 FOR_BB_INSNS(insn, bb) {
1071 /* 1 calculate live interfere */
1072 if (!insn->IsMachineInstruction() || insn->GetId() == 0) {
1073 /* New instruction inserted by reg alloc (ie spill) */
1074 continue;
1075 }
1076 /* 1.1 simple retire from active */
1077 MapleSet<LiveInterval *, ActiveCmp>::iterator it;
1078 for (it = active.begin(); it != active.end(); /* erase will update */) {
1079 auto *li = static_cast<LiveInterval *>(*it);
1080 if (li->GetLastUse() > insn->GetId()) {
1081 break;
1082 }
1083 it = active.erase(it);
1084 }
1085 const InsnDesc *md = insn->GetDesc();
1086 uint32 opndNum = insn->GetOperandSize();
1087 for (uint32 i = 0; i < opndNum; ++i) {
1088 const OpndDesc *regProp = md->GetOpndDes(i);
1089 DEBUG_ASSERT(regProp != nullptr, "pointer is null in LSRALinearScanRegAllocator::LiveIntervalAnalysis");
1090 bool isDef = regProp->IsRegDef();
1091 Operand &opnd = insn->GetOperand(i);
1092 if (isDef) {
1093 auto ®Opnd = static_cast<RegOperand &>(opnd);
1094 if (regOpnd.IsVirtualRegister() && regOpnd.GetRegisterType() != kRegTyCc) {
1095 /* 1.2 simple insert to active */
1096 uint32 regNO = regOpnd.GetRegisterNumber();
1097 LiveInterval *li = liveIntervalsArray[regNO];
1098 // set the base reference of derived reference for stackmap
1099 if (regOpnd.GetBaseRefOpnd() != nullptr) {
1100 dereivedRef2Base[regNO] = regOpnd.GetBaseRefOpnd()->GetRegisterNumber();
1101 }
1102 if (li->GetFirstDef() == insn->GetId()) {
1103 (void)active.insert(li);
1104 }
1105 }
1106 }
1107 }
1108
1109 /* 2 get interfere info, and analysis */
1110 uint32 interNum = active.size();
1111 if (needDump) {
1112 LogInfo::MapleLogger() << "In insn " << insn->GetId() << ", " << interNum
1113 << " overlap live intervals.\n";
1114 LogInfo::MapleLogger() << "\n";
1115 }
1116
1117 /* 2.2 interfere with each other, analysis which to spill */
1118 while (interNum > CGOptions::GetOverlapNum()) {
1119 LiveInterval *lowestLi = nullptr;
1120 FindLowestPrioInActive(lowestLi);
1121 if (lowestLi != nullptr) {
1122 if (needDump) {
1123 PrintLiveInterval(*lowestLi, "Pre spilled: ");
1124 }
1125 lowestLi->SetStackSlot(kSpilled);
1126 lowestLi->SetShouldSave(false);
1127 active.erase(itFinded);
1128 interNum = active.size();
1129 } else {
1130 break;
1131 }
1132 }
1133 }
1134 }
1135 active.clear();
1136 }
1137
UpdateCallQueueAtRetirement(uint32 insnID)1138 void LSRALinearScanRegAllocator::UpdateCallQueueAtRetirement(uint32 insnID)
1139 {
1140 /*
1141 * active list is sorted based on increasing lastUse
1142 * any operand whose use is greater than current
1143 * instruction number is still in use.
1144 * If the use is less than or equal to instruction number
1145 * then it is possible to retire this live interval and
1146 * reclaim the physical register associated with it.
1147 */
1148 if (needDump) {
1149 LogInfo::MapleLogger() << "RetireActiveByInsn instr_num " << insnID << "\n";
1150 }
1151 /* Retire invalidated call from call queue */
1152 while (!callQueue.empty() && callQueue.front() <= insnID) {
1153 callQueue.pop_front();
1154 }
1155 }
1156
1157 /* update allocate info by active queue */
UpdateActiveAllocateInfo(const LiveInterval & li)1158 void LSRALinearScanRegAllocator::UpdateActiveAllocateInfo(const LiveInterval &li)
1159 {
1160 uint32 start = li.GetFirstDef();
1161 uint32 end = li.GetLastUse();
1162 if (li.GetSplitParent() != nullptr || li.IsUseBeforeDef()) {
1163 --start;
1164 }
1165 for (auto *activeLi : active) {
1166 uint32 regNO = activeLi->GetAssignedReg();
1167 uint32 rangeStartPos;
1168 auto posRange = activeLi->FindPosRange(start);
1169 if (posRange == activeLi->GetRanges().end()) {
1170 /* handle splited li */
1171 uint32 splitSafePos = activeLi->GetSplitPos();
1172 if (splitSafePos == li.GetFirstDef() && (li.GetSplitParent() != nullptr || li.IsUseBeforeDef())) {
1173 rangeStartPos = 0;
1174 } else if (splitSafePos > li.GetFirstDef()) {
1175 rangeStartPos = splitSafePos - 1;
1176 } else {
1177 rangeStartPos = UINT32_MAX;
1178 }
1179 } else if (posRange->GetEhStart() != 0 && posRange->GetEhStart() < posRange->GetStart()) {
1180 rangeStartPos = posRange->GetEhStart();
1181 } else {
1182 rangeStartPos = posRange->GetStart();
1183 }
1184 if (rangeStartPos > start) {
1185 if (rangeStartPos < end) {
1186 blockForbiddenMask |= (1UL << activeLi->GetAssignedReg());
1187 }
1188 if (rangeStartPos < freeUntilPos[regNO]) {
1189 freeUntilPos[regNO] = rangeStartPos;
1190 }
1191 } else {
1192 freeUntilPos[regNO] = 0;
1193 }
1194 }
1195 }
1196
1197 /* update allocate info by param queue */
UpdateParamAllocateInfo(const LiveInterval & li)1198 void LSRALinearScanRegAllocator::UpdateParamAllocateInfo(const LiveInterval &li)
1199 {
1200 bool isInt = (li.GetRegType() == kRegTyInt);
1201 MapleVector<SingleQue> ¶mQueue = isInt ? intParamQueue : fpParamQueue;
1202 uint32 baseReg = isInt ? firstIntReg : firstFpReg;
1203 uint32 paramNum = isInt ? regInfo->GetIntRegs().size() : regInfo->GetFpRegs().size();
1204 uint32 start = li.GetFirstDef();
1205 uint32 end = li.GetLastUse();
1206 for (uint32 i = 0; i < paramNum; ++i) {
1207 while (!paramQueue[i].empty() && paramQueue[i].front()->GetPhysUse() <= start) {
1208 if (paramQueue[i].front()->GetPhysUse() == start && li.GetSplitParent() != nullptr) {
1209 break;
1210 }
1211 paramQueue[i].pop_front();
1212 }
1213 if (paramQueue[i].empty()) {
1214 continue;
1215 }
1216 auto regNo = paramQueue[i].front()->GetRegNO();
1217 uint32 startPos = paramQueue[i].front()->GetFirstDef();
1218 if (startPos <= start) {
1219 freeUntilPos[regNo] = 0;
1220 } else {
1221 if (startPos < end) {
1222 blockForbiddenMask |= (1UL << (i + baseReg));
1223 }
1224 if (startPos < freeUntilPos[regNo]) {
1225 freeUntilPos[regNo] = startPos;
1226 }
1227 }
1228 }
1229 }
1230
1231 /* update active in retire */
RetireActive(LiveInterval & li,uint32 insnID)1232 void LSRALinearScanRegAllocator::RetireActive(LiveInterval &li, uint32 insnID)
1233 {
1234 /* Retire live intervals from active list */
1235 MapleSet<LiveInterval *, ActiveCmp>::iterator it;
1236 for (it = active.begin(); it != active.end(); /* erase will update */) {
1237 auto *activeLi = static_cast<LiveInterval *>(*it);
1238 if (activeLi->GetLastUse() > insnID) {
1239 ++it;
1240 continue;
1241 }
1242 if (activeLi->GetLastUse() == insnID) {
1243 if (li.GetSplitParent() != nullptr || activeLi->GetSplitNext() != nullptr) {
1244 ++it;
1245 continue;
1246 }
1247 if (activeLi->IsEndByMov() && activeLi->GetRegType() == li.GetRegType()) {
1248 li.SetPrefer(activeLi->GetAssignedReg());
1249 }
1250 }
1251 /* reserve split li in active */
1252 if (activeLi->GetSplitPos() >= insnID) {
1253 ++it;
1254 continue;
1255 }
1256 /*
1257 * live interval ended for this reg in active
1258 * release physical reg assigned to free reg pool
1259 */
1260 if (needDump) {
1261 LogInfo::MapleLogger() << "Removing "
1262 << "(" << activeLi->GetAssignedReg() << ")"
1263 << "from regmask\n";
1264 PrintLiveInterval(*activeLi, "\tRemoving virt_reg li\n");
1265 }
1266 it = active.erase(it);
1267 }
1268 }
1269
1270 /* find the best physical reg by freeUntilPos */
GetRegFromMask(uint32 mask,regno_t offset,const LiveInterval & li)1271 uint32 LSRALinearScanRegAllocator::GetRegFromMask(uint32 mask, regno_t offset, const LiveInterval &li)
1272 {
1273 uint32 prefer = li.GetPrefer();
1274 if (prefer != 0) {
1275 uint32 preg = li.GetPrefer() - offset;
1276 if ((mask & (1u << preg)) != 0 && freeUntilPos[prefer] >= li.GetLastUse()) {
1277 return prefer;
1278 }
1279 }
1280 uint32 bestReg = 0;
1281 uint32 maxFreeUntilPos = 0;
1282 for (uint32 preg = 0; preg < k32BitSize; ++preg) {
1283 if ((mask & (1u << preg)) == 0) {
1284 continue;
1285 }
1286 uint32 regNO = preg + offset;
1287 if (freeUntilPos[regNO] >= li.GetLastUse()) {
1288 return regNO;
1289 }
1290 if (freeUntilPos[regNO] > maxFreeUntilPos) {
1291 maxFreeUntilPos = freeUntilPos[regNO];
1292 bestReg = regNO;
1293 }
1294 }
1295 return bestReg;
1296 }
1297
1298 /* Handle adrp register assignment. Use the same register for the next instruction. */
GetSpecialPhysRegPattern(const LiveInterval & li)1299 uint32 LSRALinearScanRegAllocator::GetSpecialPhysRegPattern(const LiveInterval &li)
1300 {
1301 /* li's first def point */
1302 Insn *nInsn = nullptr;
1303 if (nInsn == nullptr || !nInsn->IsMachineInstruction() || nInsn->IsDMBInsn() || li.GetLastUse() > nInsn->GetId()) {
1304 return 0;
1305 }
1306
1307 const InsnDesc *md = nInsn->GetDesc();
1308 if (!md->GetOpndDes(0)->IsRegDef()) {
1309 return 0;
1310 }
1311 Operand &opnd = nInsn->GetOperand(0);
1312 if (!opnd.IsRegister()) {
1313 return 0;
1314 }
1315 auto ®Opnd = static_cast<RegOperand &>(opnd);
1316 if (!regOpnd.IsPhysicalRegister()) {
1317 return 0;
1318 }
1319 uint32 regNO = regOpnd.GetRegisterNumber();
1320 if (!regInfo->IsPreAssignedReg(regNO)) {
1321 return 0;
1322 }
1323
1324 /* next insn's dest is a physical param reg 'regNO'. return 'regNO' if dest of adrp is src of next insn */
1325 uint32 opndNum = nInsn->GetOperandSize();
1326 for (uint32 i = 1; i < opndNum; ++i) {
1327 Operand &src = nInsn->GetOperand(i);
1328 if (src.IsMemoryAccessOperand()) {
1329 auto &memOpnd = static_cast<MemOperand &>(src);
1330 Operand *base = memOpnd.GetBaseRegister();
1331 if (base != nullptr) {
1332 auto *regSrc = static_cast<RegOperand *>(base);
1333 uint32 srcRegNO = regSrc->GetRegisterNumber();
1334 if (li.GetRegNO() == srcRegNO) {
1335 return regNO;
1336 }
1337 }
1338 Operand *offset = memOpnd.GetIndexRegister();
1339 if (offset != nullptr) {
1340 auto *regSrc = static_cast<RegOperand *>(offset);
1341 uint32 srcRegNO = regSrc->GetRegisterNumber();
1342 if (li.GetRegNO() == srcRegNO) {
1343 return regNO;
1344 }
1345 }
1346 } else if (src.IsRegister()) {
1347 auto ®Src = static_cast<RegOperand &>(src);
1348 uint32 srcRegNO = regSrc.GetRegisterNumber();
1349 if (li.GetRegNO() == srcRegNO) {
1350 const OpndDesc *regProp = md->GetOpndDes(i);
1351 DEBUG_ASSERT(regProp != nullptr,
1352 "pointer is null in LSRALinearScanRegAllocator::GetSpecialPhysRegPattern");
1353 bool srcIsDef = regProp->IsRegDef();
1354 if (srcIsDef) {
1355 break;
1356 }
1357 return regNO;
1358 }
1359 }
1360 }
1361 return 0;
1362 }
1363
FindAvailablePhyRegByFastAlloc(LiveInterval & li)1364 uint32 LSRALinearScanRegAllocator::FindAvailablePhyRegByFastAlloc(LiveInterval &li)
1365 {
1366 uint32 regNO = 0;
1367 if (li.GetRegType() == kRegTyInt) {
1368 regNO = GetRegFromMask(intCalleeMask, firstIntReg, li);
1369 li.SetShouldSave(false);
1370 if (regNO == 0 || freeUntilPos[regNO] < li.GetLastUse()) {
1371 regNO = GetRegFromMask(intCallerMask, firstIntReg, li);
1372 li.SetShouldSave(true);
1373 }
1374 } else if (li.GetRegType() == kRegTyFloat) {
1375 regNO = GetRegFromMask(fpCalleeMask, firstFpReg, li);
1376 li.SetShouldSave(false);
1377 if (regNO == 0 || freeUntilPos[regNO] < li.GetLastUse()) {
1378 regNO = GetRegFromMask(fpCallerMask, firstFpReg, li);
1379 li.SetShouldSave(true);
1380 }
1381 }
1382 return regNO;
1383 }
1384
1385 /* Determine if live interval crosses the call */
NeedSaveAcrossCall(LiveInterval & li)1386 bool LSRALinearScanRegAllocator::NeedSaveAcrossCall(LiveInterval &li)
1387 {
1388 bool saveAcrossCall = false;
1389 for (uint32 callInsnID : callQueue) {
1390 if (callInsnID > li.GetLastUse()) {
1391 break;
1392 }
1393 if (callInsnID < li.GetFirstDef()) {
1394 continue;
1395 }
1396 /* Need to spill/fill around this call */
1397 for (auto range : li.GetRanges()) {
1398 uint32 start;
1399 if (range.GetEhStart() != 0 && range.GetEhStart() < range.GetStart()) {
1400 start = range.GetEhStart();
1401 } else {
1402 start = range.GetStart();
1403 }
1404 if (callInsnID >= start && callInsnID < range.GetEnd()) {
1405 saveAcrossCall = true;
1406 break;
1407 }
1408 }
1409 if (saveAcrossCall) {
1410 break;
1411 }
1412 }
1413 if (needDump) {
1414 if (saveAcrossCall) {
1415 LogInfo::MapleLogger() << "\t\tlive interval crosses a call\n";
1416 } else {
1417 LogInfo::MapleLogger() << "\t\tlive interval does not cross a call\n";
1418 }
1419 }
1420 return saveAcrossCall;
1421 }
1422
1423 /* Return a phys register number for the live interval. */
FindAvailablePhyReg(LiveInterval & li)1424 uint32 LSRALinearScanRegAllocator::FindAvailablePhyReg(LiveInterval &li)
1425 {
1426 if (fastAlloc) {
1427 return FindAvailablePhyRegByFastAlloc(li);
1428 }
1429 uint32 regNO = 0;
1430 if (li.GetRegType() == kRegTyInt) {
1431 regNO = FindAvailablePhyReg(li, true);
1432 } else {
1433 DEBUG_ASSERT(li.GetRegType() == kRegTyFloat, "impossible register type");
1434 regNO = FindAvailablePhyReg(li, false);
1435 }
1436 return regNO;
1437 }
1438
1439 /* Spill and reload for caller saved registers. */
InsertCallerSave(Insn & insn,Operand & opnd,bool isDef)1440 void LSRALinearScanRegAllocator::InsertCallerSave(Insn &insn, Operand &opnd, bool isDef)
1441 {
1442 auto ®Opnd = static_cast<RegOperand &>(opnd);
1443 uint32 vRegNO = regOpnd.GetRegisterNumber();
1444 if (vRegNO >= liveIntervalsArray.size()) {
1445 CHECK_FATAL(false, "index out of range in LSRALinearScanRegAllocator::InsertCallerSave");
1446 }
1447 LiveInterval *rli = liveIntervalsArray[vRegNO];
1448 auto regType = rli->GetRegType();
1449
1450 isSpillZero = false;
1451 if (!isDef && rli->IsNoNeedReloadPosition(insn.GetId())) {
1452 if (needDump) {
1453 LogInfo::MapleLogger() << "InsertCallerSave R" << rli->GetRegNO() << " assigned "
1454 << rli->GetAssignedReg() << " skipping\n";
1455 }
1456 return;
1457 }
1458
1459 if (!rli->IsShouldSave()) {
1460 return;
1461 }
1462
1463 uint32 regSize = rli->GetSpillSize();
1464 PrimType spType;
1465
1466 if (regType == kRegTyInt) {
1467 spType = (regSize <= k32BitSize) ? PTY_u32 : PTY_u64;
1468 } else {
1469 spType = (regSize <= k32BitSize) ? PTY_f32 : PTY_f64;
1470 }
1471
1472 if (needDump) {
1473 LogInfo::MapleLogger() << "InsertCallerSave R" << vRegNO << (isDef ? " def" : " use") << "\n";
1474 }
1475
1476 if (!isDef && !rli->IsCallerSpilled()) {
1477 LogInfo::MapleLogger() << "WARNING: " << vRegNO << " caller restore without spill in bb "
1478 << insn.GetBB()->GetId() << " : " << cgFunc->GetName() << "\n";
1479 }
1480 rli->SetIsCallerSpilled(true);
1481
1482 MemOperand *memOpnd = nullptr;
1483 RegOperand *phyOpnd = nullptr;
1484
1485 phyOpnd = regInfo->GetOrCreatePhyRegOperand(static_cast<regno_t>(rli->GetAssignedReg()), regSize, regType);
1486 std::string comment;
1487 bool isOutOfRange = false;
1488 if (isDef) {
1489 Insn *nextInsn = insn.GetNext();
1490 memOpnd = GetSpillMem(vRegNO, true, insn, static_cast<regno_t>(intSpillRegSet[0] + firstIntReg), isOutOfRange,
1491 regSize);
1492 Insn *stInsn = regInfo->BuildStrInsn(regSize, spType, *phyOpnd, *memOpnd);
1493 comment = " SPILL for caller_save " + std::to_string(vRegNO);
1494 ++callerSaveSpillCount;
1495 if (rli->GetLastUse() == insn.GetId() && !cgFunc->IsRegReference(vRegNO)) {
1496 regInfo->FreeSpillRegMem(vRegNO);
1497 comment += " end";
1498 }
1499 stInsn->SetComment(comment);
1500 if (isOutOfRange && nextInsn != nullptr) {
1501 insn.GetBB()->InsertInsnBefore(*nextInsn, *stInsn);
1502 } else if (isOutOfRange && nextInsn == nullptr) {
1503 insn.GetBB()->AppendInsn(*stInsn);
1504 } else {
1505 insn.GetBB()->InsertInsnAfter(insn, *stInsn);
1506 }
1507 } else {
1508 memOpnd = GetSpillMem(vRegNO, false, insn, static_cast<regno_t>(intSpillRegSet[0] + firstIntReg), isOutOfRange,
1509 regSize);
1510 Insn *ldInsn = regInfo->BuildLdrInsn(regSize, spType, *phyOpnd, *memOpnd);
1511 comment = " RELOAD for caller_save " + std::to_string(vRegNO);
1512 ++callerSaveReloadCount;
1513 if (rli->GetLastUse() == insn.GetId() && !cgFunc->IsRegReference(vRegNO)) {
1514 regInfo->FreeSpillRegMem(vRegNO);
1515 comment += " end";
1516 }
1517 ldInsn->SetComment(comment);
1518 insn.GetBB()->InsertInsnBefore(insn, *ldInsn);
1519 }
1520 }
1521
GetSpillMem(uint32 vRegNO,bool isDest,Insn & insn,regno_t regNO,bool & isOutOfRange,uint32 bitSize) const1522 MemOperand *LSRALinearScanRegAllocator::GetSpillMem(uint32 vRegNO, bool isDest, Insn &insn, regno_t regNO,
1523 bool &isOutOfRange, uint32 bitSize) const
1524 {
1525 MemOperand *memOpnd = regInfo->GetOrCreatSpillMem(vRegNO, bitSize);
1526 return regInfo->AdjustMemOperandIfOffsetOutOfRange(memOpnd, vRegNO, isDest, insn, regNO, isOutOfRange);
1527 }
1528
1529 /* Set a vreg in live interval as being marked for spill. */
SetOperandSpill(Operand & opnd)1530 void LSRALinearScanRegAllocator::SetOperandSpill(Operand &opnd)
1531 {
1532 auto ®Opnd = static_cast<RegOperand &>(opnd);
1533 uint32 regNO = regOpnd.GetRegisterNumber();
1534 if (needDump) {
1535 LogInfo::MapleLogger() << "SetOperandSpill " << regNO;
1536 LogInfo::MapleLogger() << "(" << liveIntervalsArray[regNO]->GetFirstAcrossedCall();
1537 LogInfo::MapleLogger() << ", refCount " << liveIntervalsArray[regNO]->GetRefCount() << ")\n";
1538 }
1539
1540 DEBUG_ASSERT(regNO < liveIntervalsArray.size(),
1541 "index out of vector size in LSRALinearScanRegAllocator::SetOperandSpill");
1542 LiveInterval *li = liveIntervalsArray[regNO];
1543 li->SetStackSlot(kSpilled);
1544 li->SetShouldSave(false);
1545 }
1546
1547 /*
1548 * Generate spill/reload for an operand.
1549 * spill_idx : one of 3 phys regs set aside for the purpose of spills.
1550 */
SpillOperand(Insn & insn,Operand & opnd,bool isDef,uint32 spillIdx)1551 void LSRALinearScanRegAllocator::SpillOperand(Insn &insn, Operand &opnd, bool isDef, uint32 spillIdx)
1552 {
1553 /*
1554 * Insert spill (def) and fill (use) instructions for the operand.
1555 * Keep track of the 'slot' (base 0). The actual slot on the stack
1556 * will be some 'base_slot_offset' + 'slot' off FP.
1557 * For simplification, entire 64bit register is spilled/filled.
1558 *
1559 * For example, a virtual register home 'slot' on the stack is location 5.
1560 * This represents a 64bit slot (8bytes). The base_slot_offset
1561 * from the base 'slot' determined by whoever is added, off FP.
1562 * stack address is ( FP - (5 * 8) + base_slot_offset )
1563 * So the algorithm is simple, for each virtual register that is not
1564 * allocated, it has to have a home address on the stack (a slot).
1565 * A class variable is used, start from 0, increment by 1.
1566 * Since LiveInterval already represent unique regNO information,
1567 * just add a slot number to it. Subsequent reference to a regNO
1568 * will either get an allocated physical register or a slot number
1569 * for computing the stack location.
1570 *
1571 * This function will also determine the operand to be a def or use.
1572 * For def, spill instruction(s) is appended after the insn.
1573 * For use, spill instruction(s) is prepended before the insn.
1574 * Use FP - (slot# *8) for now. Will recompute if base_slot_offset
1575 * is not 0.
1576 *
1577 * The total number of slots used will be used to compute the stack
1578 * frame size. This will require some interface external to LSRA.
1579 *
1580 * For normal instruction, two spill regs should be enough. The caller
1581 * controls which ones to use.
1582 * For more complex operations, need to break down the instruction.
1583 * eg. store v1 -> [v2 + v3] // 3 regs needed
1584 * => p1 <- v2 // address part 1
1585 * p2 <- v3 // address part 2
1586 * p1 <- p1 + p2 // freeing up p2
1587 * p2 <- v1
1588 * store p2 -> [p1]
1589 * or we can allocate more registers to the spill register set
1590 * For store multiple, need to break it down into two or more instr.
1591 */
1592 auto ®Opnd = static_cast<RegOperand &>(opnd);
1593 uint32 regNO = regOpnd.GetRegisterNumber();
1594 if (needDump) {
1595 LogInfo::MapleLogger() << "SpillOperand " << regNO << "\n";
1596 }
1597
1598 regno_t spReg;
1599 PrimType spType;
1600 CHECK_FATAL(regNO < liveIntervalsArray.size(), "index out of range in LSRALinearScanRegAllocator::SpillOperand");
1601 LiveInterval *li = liveIntervalsArray[regNO];
1602 DEBUG_ASSERT(!li->IsShouldSave(), "SpillOperand: Should not be caller");
1603 uint32 regSize = li->GetSpillSize();
1604 RegType regType = regOpnd.GetRegisterType();
1605
1606 if (li->GetRegType() == kRegTyInt) {
1607 DEBUG_ASSERT((spillIdx < intSpillRegSet.size()), "SpillOperand: ran out int spill reg");
1608 spReg = intSpillRegSet[spillIdx] + firstIntReg;
1609 spType = (regSize <= k32BitSize) ? PTY_u32 : PTY_u64;
1610 } else if (li->GetRegType() == kRegTyFloat) {
1611 DEBUG_ASSERT((spillIdx < fpSpillRegSet.size()), "SpillOperand: ran out fp spill reg");
1612 spReg = fpSpillRegSet[spillIdx] + firstFpReg;
1613 spType = (regSize <= k32BitSize) ? PTY_f32 : PTY_f64;
1614 } else {
1615 CHECK_FATAL(false, "SpillOperand: Should be int or float type");
1616 }
1617
1618 bool isOutOfRange = false;
1619 RegOperand *phyOpnd = nullptr;
1620 if (isSpillZero) {
1621 phyOpnd = &cgFunc->GetZeroOpnd(regSize);
1622 } else {
1623 phyOpnd = regInfo->GetOrCreatePhyRegOperand(static_cast<regno_t>(spReg), regSize, regType);
1624 }
1625 li->SetAssignedReg(phyOpnd->GetRegisterNumber());
1626
1627 MemOperand *memOpnd = nullptr;
1628 if (isDef) {
1629 /*
1630 * Need to assign spReg (one of the two spill reg) to the destination of the insn.
1631 * spill_vreg <- opn1 op opn2
1632 * to
1633 * spReg <- opn1 op opn2
1634 * store spReg -> spillmem
1635 */
1636 li->SetStackSlot(kSpilled);
1637
1638 ++spillCount;
1639 Insn *nextInsn = insn.GetNext();
1640 memOpnd = GetSpillMem(regNO, true, insn, static_cast<regno_t>(intSpillRegSet[spillIdx + 1] + firstIntReg),
1641 isOutOfRange, regSize);
1642 Insn *stInsn = regInfo->BuildStrInsn(regSize, spType, *phyOpnd, *memOpnd);
1643 if (li->GetLastUse() == insn.GetId() && !cgFunc->IsRegReference(regNO)) {
1644 regInfo->FreeSpillRegMem(regNO);
1645 }
1646 if (CGOptions::kVerboseCG) {
1647 std::string comment = " SPILL vreg:" + std::to_string(regNO);
1648 stInsn->SetComment(comment);
1649 }
1650
1651 if (isOutOfRange && nextInsn != nullptr) {
1652 insn.GetBB()->InsertInsnBefore(*nextInsn, *stInsn);
1653 } else if (isOutOfRange && nextInsn == nullptr) {
1654 insn.GetBB()->AppendInsn(*stInsn);
1655 } else {
1656 insn.GetBB()->InsertInsnAfter(insn, *stInsn);
1657 }
1658 } else {
1659 /* Here, reverse of isDef, change either opn1 or opn2 to the spReg. */
1660 if (li->GetStackSlot() == 0xFFFFFFFF) {
1661 LogInfo::MapleLogger() << "WARNING: " << regNO << " assigned " << li->GetAssignedReg()
1662 << " restore without spill in bb " << insn.GetBB()->GetId() << " : "
1663 << cgFunc->GetName() << "\n";
1664 }
1665 ++reloadCount;
1666 memOpnd = GetSpillMem(regNO, false, insn, static_cast<regno_t>(intSpillRegSet[spillIdx] + firstIntReg),
1667 isOutOfRange, regSize);
1668 Insn *ldInsn = regInfo->BuildLdrInsn(regSize, spType, *phyOpnd, *memOpnd);
1669 if (li->GetLastUse() == insn.GetId() && !cgFunc->IsRegReference(regNO)) {
1670 regInfo->FreeSpillRegMem(regNO);
1671 }
1672 if (CGOptions::kVerboseCG) {
1673 std::string comment = " RELOAD vreg" + std::to_string(regNO);
1674 ldInsn->SetComment(comment);
1675 }
1676 insn.GetBB()->InsertInsnBefore(insn, *ldInsn);
1677 }
1678 }
1679
1680 /* find the lowest li that meets the constraints related to li0 form current active */
FindLowestPrioInActive(LiveInterval * & targetLi,LiveInterval * li0,RegType regType)1681 void LSRALinearScanRegAllocator::FindLowestPrioInActive(LiveInterval *&targetLi, LiveInterval *li0, RegType regType)
1682 {
1683 std::map<regno_t, uint32> activeLiAssignedRegCnt;
1684 for (auto *li : active) {
1685 if (li->GetAssignedReg() != 0) {
1686 ++activeLiAssignedRegCnt[li->GetAssignedReg()];
1687 }
1688 }
1689
1690 float lowestPrio = (li0 != nullptr ? li0->GetPriority() : 1000.0);
1691 bool found = false;
1692 bool hintCalleeSavedReg = li0 && NeedSaveAcrossCall(*li0);
1693 MapleSet<LiveInterval *, ActiveCmp>::iterator lowestIt;
1694 for (auto it = active.begin(); it != active.end(); ++it) {
1695 LiveInterval *li = static_cast<LiveInterval *>(*it);
1696 regno_t regNO = li->GetAssignedReg();
1697 /* 1. Basic Constraints */
1698 if (li->GetPriority() >= lowestPrio || li->GetRegType() != regType || li->GetLiParent() || li->GetLiChild()) {
1699 continue;
1700 }
1701 /* 2. If li is pre-assigned to Physical register primitively, ignore it. */
1702 if (regInfo->IsPreAssignedReg(li->GetRegNO())) {
1703 continue;
1704 }
1705 /* 3. CalleeSavedReg is preferred here. If li is assigned to Non-CalleeSavedReg, ignore it. */
1706 if (hintCalleeSavedReg && !regInfo->IsCalleeSavedReg(regNO - firstIntReg)) {
1707 continue;
1708 }
1709 /* 4. if regNO is assigned to multiple active li, ignore it. */
1710 if (activeLiAssignedRegCnt[regNO] > 1) {
1711 continue;
1712 }
1713 lowestPrio = li->GetPriority();
1714 lowestIt = it;
1715 found = true;
1716 }
1717 if (found) {
1718 targetLi = *lowestIt;
1719 itFinded = lowestIt;
1720 }
1721 return;
1722 }
1723
1724 /* Set a vreg in live interval as being marked for spill. */
SetLiSpill(LiveInterval & li)1725 void LSRALinearScanRegAllocator::SetLiSpill(LiveInterval &li)
1726 {
1727 uint32 regNO = li.GetRegNO();
1728 if (needDump) {
1729 LogInfo::MapleLogger() << "SetLiSpill " << regNO;
1730 LogInfo::MapleLogger() << "(" << li.GetFirstAcrossedCall();
1731 LogInfo::MapleLogger() << ", refCount " << li.GetRefCount() << ")\n";
1732 }
1733 li.SetStackSlot(kSpilled);
1734 li.SetShouldSave(false);
1735 }
1736
HandleSpillForLi(LiveInterval & li)1737 uint32 LSRALinearScanRegAllocator::HandleSpillForLi(LiveInterval &li)
1738 {
1739 /* choose the lowest priority li to spill */
1740 RegType regType = li.GetRegType();
1741 LiveInterval *spillLi = nullptr;
1742 FindLowestPrioInActive(spillLi, &li, regType);
1743
1744 /*
1745 * compare spill_li with current li
1746 * spill_li is null and li->SetStackSlot(Spilled) when the li is spilled due to LiveIntervalAnalysis
1747 */
1748 if (!li.IsMustAllocate()) {
1749 if (spillLi == nullptr || li.GetStackSlot() == kSpilled || li.GetRefCount() <= spillLi->GetRefCount() ||
1750 freeUntilPos[spillLi->GetAssignedReg()] < li.GetLastUse()) {
1751 /* spill current li */
1752 if (needDump) {
1753 LogInfo::MapleLogger() << "Flexible Spill: still spill " << li.GetRegNO() << ".\n";
1754 }
1755 SetLiSpill(li);
1756 return 0;
1757 }
1758 }
1759 DEBUG_ASSERT(spillLi != nullptr, "spillLi is null in LSRALinearScanRegAllocator::HandleSpillForLi");
1760
1761 uint32 newRegNO = spillLi->GetAssignedReg();
1762 DEBUG_ASSERT(freeUntilPos[newRegNO] >= li.GetLastUse(), "phyReg has small free range.");
1763
1764 if (needDump) {
1765 LogInfo::MapleLogger() << "Flexible Spill: " << spillLi->GetRegNO() << " instead of " << li.GetRegNO() << ".\n";
1766 PrintLiveInterval(*spillLi, "TO spill: ");
1767 PrintLiveInterval(li, "Instead of: ");
1768 }
1769
1770 li.SetAssignedReg(newRegNO);
1771 if (!regInfo->IsCalleeSavedReg(newRegNO) && NeedSaveAcrossCall(li)) {
1772 li.SetShouldSave(true);
1773 }
1774
1775 /* spill this live interval */
1776 (void)active.erase(itFinded);
1777 SetLiSpill(*spillLi);
1778 spillLi->SetAssignedReg(0);
1779
1780 (void)active.insert(&li);
1781 return newRegNO;
1782 }
1783
FindAvailablePhyReg(LiveInterval & li,bool isIntReg)1784 uint32 LSRALinearScanRegAllocator::FindAvailablePhyReg(LiveInterval &li, bool isIntReg)
1785 {
1786 uint32 &callerRegMask = isIntReg ? intCallerMask : fpCallerMask;
1787 uint32 &calleeRegMask = isIntReg ? intCalleeMask : fpCalleeMask;
1788 regno_t reg0 = isIntReg ? firstIntReg : firstFpReg;
1789 regno_t bestReg = 0;
1790 regno_t secondReg = 0;
1791
1792 /* See if register is live accross a call */
1793 if (NeedSaveAcrossCall(li)) {
1794 if (!li.IsAllInCatch() && !li.IsAllInCleanupOrFirstBB()) {
1795 /* call in live interval, use callee if available */
1796 bestReg = GetRegFromMask(calleeRegMask, reg0, li);
1797 if (bestReg != 0 && freeUntilPos[bestReg] >= li.GetLastUse()) {
1798 li.SetShouldSave(false);
1799 return bestReg;
1800 }
1801 }
1802 /* can be optimize multi use between calls rather than in bb */
1803 if (bestReg == 0 || li.IsMultiUseInBB()) {
1804 secondReg = GetRegFromMask(callerRegMask, reg0, li);
1805 if (freeUntilPos[secondReg] >= li.GetLastUse()) {
1806 li.SetShouldSave(true);
1807 return secondReg;
1808 }
1809 }
1810 } else {
1811 /* Get forced register */
1812 uint32 forcedReg = GetSpecialPhysRegPattern(li);
1813 if (forcedReg != 0) {
1814 return forcedReg;
1815 }
1816
1817 bestReg = GetRegFromMask(intCallerMask, reg0, li);
1818 if (bestReg == 0) {
1819 bestReg = GetRegFromMask(intCalleeMask, reg0, li);
1820 } else if (freeUntilPos[bestReg] < li.GetLastUse()) {
1821 secondReg = GetRegFromMask(intCalleeMask, reg0, li);
1822 if (secondReg != 0) {
1823 bestReg = (freeUntilPos[bestReg] > freeUntilPos[secondReg]) ? bestReg : secondReg;
1824 }
1825 }
1826 }
1827 if (bestReg != 0 && freeUntilPos[bestReg] < li.GetLastUse()) {
1828 DEBUG_ASSERT(freeUntilPos[bestReg] != 0, "impossible");
1829 bestReg = 0;
1830 }
1831 /* try to fill in holes */
1832 /* try first split if no hole exists */
1833 return bestReg;
1834 }
1835
1836 /* Shell function to find a physical register for an operand. */
AssignPhysRegs(LiveInterval & li)1837 uint32 LSRALinearScanRegAllocator::AssignPhysRegs(LiveInterval &li)
1838 {
1839 if (spillAll && !li.IsMustAllocate()) {
1840 return 0;
1841 }
1842
1843 /* pre spilled: */
1844 if (li.GetStackSlot() != 0xFFFFFFFF && !li.IsMustAllocate()) {
1845 return 0;
1846 }
1847
1848 if (needDump) {
1849 uint32 activeSz = active.size();
1850 LogInfo::MapleLogger() << "\tAssignPhysRegs-active_sz " << activeSz << "\n";
1851 }
1852
1853 uint32 regNO = FindAvailablePhyReg(li);
1854 if (regNO != 0) {
1855 li.SetAssignedReg(regNO);
1856 if (regInfo->IsCalleeSavedReg(regNO)) {
1857 if (needDump) {
1858 LogInfo::MapleLogger()
1859 << "\tCallee-save register for save/restore in prologue/epilogue: " << regNO << "\n";
1860 }
1861 cgFunc->AddtoCalleeSaved(regNO);
1862 }
1863 }
1864 return regNO;
1865 }
1866
AssignPhysRegsForLi(LiveInterval & li)1867 void LSRALinearScanRegAllocator::AssignPhysRegsForLi(LiveInterval &li)
1868 {
1869 uint32 newRegNO = AssignPhysRegs(li);
1870 if (newRegNO == 0) {
1871 newRegNO = HandleSpillForLi(li);
1872 }
1873
1874 if (newRegNO != 0) {
1875 (void)active.insert(&li);
1876 }
1877 }
1878
1879 /* Replace Use-Def Opnd */
GetReplaceUdOpnd(Insn & insn,Operand & opnd,uint32 & spillIdx)1880 RegOperand *LSRALinearScanRegAllocator::GetReplaceUdOpnd(Insn &insn, Operand &opnd, uint32 &spillIdx)
1881 {
1882 if (!opnd.IsRegister()) {
1883 return nullptr;
1884 }
1885 const auto *regOpnd = static_cast<RegOperand *>(&opnd);
1886
1887 uint32 vRegNO = regOpnd->GetRegisterNumber();
1888 RegType regType = regOpnd->GetRegisterType();
1889 if (regType == kRegTyCc || regType == kRegTyVary) {
1890 return nullptr;
1891 }
1892 if (regInfo->IsUntouchableReg(vRegNO)) {
1893 return nullptr;
1894 }
1895 if (regOpnd->IsPhysicalRegister()) {
1896 return nullptr;
1897 }
1898
1899 DEBUG_ASSERT(vRegNO < liveIntervalsArray.size(),
1900 "index out of range of MapleVector in LSRALinearScanRegAllocator::GetReplaceUdOpnd");
1901 LiveInterval *li = liveIntervalsArray[vRegNO];
1902
1903 regno_t regNO = li->GetAssignedReg();
1904 if (regInfo->IsCalleeSavedReg(regNO)) {
1905 cgFunc->AddtoCalleeSaved(regNO);
1906 }
1907
1908 if (li->IsShouldSave()) {
1909 InsertCallerSave(insn, opnd, false);
1910 InsertCallerSave(insn, opnd, true);
1911 } else if (li->GetStackSlot() == kSpilled) {
1912 SpillOperand(insn, opnd, false, spillIdx);
1913 SpillOperand(insn, opnd, true, spillIdx);
1914 ++spillIdx;
1915 }
1916 RegOperand *phyOpnd =
1917 regInfo->GetOrCreatePhyRegOperand(static_cast<regno_t>(li->GetAssignedReg()), opnd.GetSize(), regType);
1918
1919 return phyOpnd;
1920 }
1921
1922 /*
1923 * Create an operand with physical register assigned, or a spill register
1924 * in the case where a physical register cannot be assigned.
1925 */
GetReplaceOpnd(Insn & insn,Operand & opnd,uint32 & spillIdx,bool isDef)1926 RegOperand *LSRALinearScanRegAllocator::GetReplaceOpnd(Insn &insn, Operand &opnd, uint32 &spillIdx, bool isDef)
1927 {
1928 if (!opnd.IsRegister()) {
1929 return nullptr;
1930 }
1931 const auto *regOpnd = static_cast<RegOperand *>(&opnd);
1932
1933 uint32 vRegNO = regOpnd->GetRegisterNumber();
1934 RegType regType = regOpnd->GetRegisterType();
1935 if (regType == kRegTyCc || regType == kRegTyVary) {
1936 return nullptr;
1937 }
1938 if (regInfo->IsUntouchableReg(vRegNO)) {
1939 return nullptr;
1940 }
1941 if (regOpnd->IsPhysicalRegister()) {
1942 return nullptr;
1943 }
1944
1945 DEBUG_ASSERT(vRegNO < liveIntervalsArray.size(),
1946 "index out of range of MapleVector in LSRALinearScanRegAllocator::GetReplaceOpnd");
1947 LiveInterval *li = liveIntervalsArray[vRegNO];
1948
1949 regno_t regNO = li->GetAssignedReg();
1950 if (regInfo->IsCalleeSavedReg(regNO)) {
1951 cgFunc->AddtoCalleeSaved(regNO);
1952 }
1953
1954 if (li->IsShouldSave()) {
1955 InsertCallerSave(insn, opnd, isDef);
1956 } else if (li->GetStackSlot() == kSpilled) {
1957 spillIdx = isDef ? 0 : spillIdx;
1958 SpillOperand(insn, opnd, isDef, spillIdx);
1959 if (!isDef) {
1960 ++spillIdx;
1961 }
1962 }
1963 RegOperand *phyOpnd =
1964 regInfo->GetOrCreatePhyRegOperand(static_cast<regno_t>(li->GetAssignedReg()), opnd.GetSize(), regType);
1965
1966 return phyOpnd;
1967 }
1968
1969
UpdateLocalDefWithBBLiveIn(const BB & bb)1970 bool LSRALinearScanRegAllocator::CallerSaveOpt::UpdateLocalDefWithBBLiveIn(const BB &bb)
1971 {
1972 bool changed = false;
1973 auto bbId = bb.GetId();
1974 for (uint32 i = 0; i < callerSaves.size(); ++i) {
1975 auto *li = callerSaves[i];
1976 auto &defLiveIn = localDefLiveIn[i];
1977 auto &defLiveOut = localDefLiveOut[i];
1978
1979 if (bb.GetLiveInRegNO().count(li->GetRegNO()) == 0) {
1980 continue;
1981 }
1982 if (defLiveIn.count(bbId) != 0) {
1983 continue;
1984 }
1985 bool isLocalDef = true;
1986 for (auto *pred : bb.GetPreds()) {
1987 if (defLiveOut.count(pred->GetId()) == 0) {
1988 isLocalDef = false;
1989 break;
1990 }
1991 }
1992 if (isLocalDef) {
1993 defLiveIn.insert(bb.GetId());
1994 defLiveOut.insert(bb.GetId());
1995 changed = true;
1996 }
1997 }
1998 return changed;
1999 }
2000
CollectCallerNoNeedReloadByInsn(const Insn & insn)2001 void LSRALinearScanRegAllocator::CallerSaveOpt::CollectCallerNoNeedReloadByInsn(const Insn &insn)
2002 {
2003 auto curId = insn.GetId();
2004 for (uint32 i = 0; i < callerSaves.size(); ++i) {
2005 auto *li = callerSaves[i];
2006 auto &defLiveOut = localDefLiveOut[i];
2007 auto posRange = li->FindPosRange(curId);
2008 if (posRange == li->GetRanges().end() || posRange->GetStart() > curId) {
2009 continue;
2010 }
2011 if (insn.IsCall()) {
2012 defLiveOut.erase(insn.GetBB()->GetId());
2013 continue;
2014 }
2015 auto &usePositions = li->GetUsePositions();
2016 if (std::binary_search(usePositions.begin(), usePositions.end(), curId)) {
2017 if (defLiveOut.count(insn.GetBB()->GetId()) == 0) {
2018 defLiveOut.insert(insn.GetBB()->GetId());
2019 continue;
2020 }
2021 li->AddNoNeedReloadPosition(curId);
2022 }
2023 }
2024 }
2025
Run()2026 void LSRALinearScanRegAllocator::CallerSaveOpt::Run()
2027 {
2028 bool changed;
2029 do {
2030 changed = false;
2031 for (auto *li : callerSaves) {
2032 li->InitRangeFinder();
2033 }
2034 for (BB *bb : bfs->sortedBBs) {
2035 if (!UpdateLocalDefWithBBLiveIn(*bb) && !firstTime) {
2036 continue;
2037 }
2038 changed = true;
2039 FOR_BB_INSNS(insn, bb) {
2040 if (!insn->IsMachineInstruction() || insn->GetId() == 0) {
2041 continue;
2042 }
2043 CollectCallerNoNeedReloadByInsn(*insn);
2044 }
2045 }
2046 firstTime = false;
2047 } while (changed);
2048 }
2049
2050 /* Iterate through all instructions and change the vreg to preg. */
FinalizeRegisters()2051 void LSRALinearScanRegAllocator::FinalizeRegisters()
2052 {
2053 CallerSaveOpt opt(liveIntervalsArray, bfs);
2054 opt.Run();
2055 for (BB *bb : bfs->sortedBBs) {
2056 FOR_BB_INSNS(insn, bb) {
2057 if (!insn->IsMachineInstruction() || insn->GetId() == 0) {
2058 continue;
2059 }
2060
2061 uint32 spillIdx = 0;
2062 const InsnDesc *md = insn->GetDesc();
2063 uint32 opndNum = insn->GetOperandSize();
2064
2065 /* Handle source(use) opernads first */
2066 for (uint32 i = 0; i < opndNum; ++i) {
2067 const OpndDesc *regProp = md->GetOpndDes(i);
2068 DEBUG_ASSERT(regProp != nullptr, "pointer is null in LSRALinearScanRegAllocator::FinalizeRegisters");
2069 bool isDef = regProp->IsRegDef();
2070 if (isDef) {
2071 continue;
2072 }
2073 Operand &opnd = insn->GetOperand(i);
2074 RegOperand *phyOpnd = nullptr;
2075 if (opnd.IsList()) {
2076 /* For arm32, not arm64 */
2077 } else if (opnd.IsMemoryAccessOperand()) {
2078 auto *memOpnd =
2079 static_cast<MemOperand *>(static_cast<MemOperand &>(opnd).Clone(*cgFunc->GetMemoryPool()));
2080 DEBUG_ASSERT(memOpnd != nullptr,
2081 "memopnd is null in LSRALinearScanRegAllocator::FinalizeRegisters");
2082 insn->SetOperand(i, *memOpnd);
2083 Operand *base = memOpnd->GetBaseRegister();
2084 Operand *offset = memOpnd->GetIndexRegister();
2085 if (base != nullptr) {
2086 phyOpnd = GetReplaceOpnd(*insn, *base, spillIdx, false);
2087 if (phyOpnd != nullptr) {
2088 memOpnd->SetBaseRegister(*phyOpnd);
2089 }
2090 }
2091 if (offset != nullptr) {
2092 phyOpnd = GetReplaceOpnd(*insn, *offset, spillIdx, false);
2093 if (phyOpnd != nullptr) {
2094 memOpnd->SetIndexRegister(*phyOpnd);
2095 }
2096 }
2097 } else {
2098 phyOpnd = GetReplaceOpnd(*insn, opnd, spillIdx, false);
2099 if (phyOpnd != nullptr) {
2100 insn->SetOperand(i, *phyOpnd);
2101 }
2102 }
2103 }
2104
2105 /* Handle ud(use-def) opernads */
2106 for (uint32 i = 0; i < opndNum; ++i) {
2107 const OpndDesc *regProp = md->GetOpndDes(i);
2108 DEBUG_ASSERT(regProp != nullptr, "pointer is null in LSRALinearScanRegAllocator::FinalizeRegisters");
2109 Operand &opnd = insn->GetOperand(i);
2110 bool isUseDef = regProp->IsRegDef() && regProp->IsRegUse();
2111 if (!isUseDef) {
2112 continue;
2113 }
2114 RegOperand *phyOpnd = GetReplaceUdOpnd(*insn, opnd, spillIdx);
2115 if (phyOpnd != nullptr) {
2116 insn->SetOperand(i, *phyOpnd);
2117 }
2118 }
2119
2120 /* Handle dest(def) opernads last */
2121 for (uint32 i = 0; i < opndNum; ++i) {
2122 const OpndDesc *regProp = md->GetOpndDes(i);
2123 DEBUG_ASSERT(regProp != nullptr, "pointer is null in LSRALinearScanRegAllocator::FinalizeRegisters");
2124 Operand &opnd = insn->GetOperand(i);
2125 bool isUse = (regProp->IsRegUse()) || (opnd.IsMemoryAccessOperand());
2126 if (isUse) {
2127 continue;
2128 }
2129 isSpillZero = false;
2130 RegOperand *phyOpnd = GetReplaceOpnd(*insn, opnd, spillIdx, true);
2131 if (phyOpnd != nullptr) {
2132 insn->SetOperand(i, *phyOpnd);
2133 if (isSpillZero) {
2134 insn->GetBB()->RemoveInsn(*insn);
2135 }
2136 }
2137 }
2138 }
2139 }
2140 }
2141
CollectReferenceMap()2142 void LSRALinearScanRegAllocator::CollectReferenceMap()
2143 {
2144 const auto &referenceMapInsns = cgFunc->GetStackMapInsns();
2145 if (needDump) {
2146 LogInfo::MapleLogger() << "===========reference map stack info================\n";
2147 }
2148
2149 for (auto *insn : referenceMapInsns) {
2150 auto *stackMapLiveIn = insn->GetStackMapLiveIn();
2151 std::set<uint32> setInfo;
2152 stackMapLiveIn->GetInfo().ConvertToSet(setInfo);
2153 for (auto regNO : setInfo) {
2154 if (!cgFunc->IsRegReference(regNO)) {
2155 continue;
2156 }
2157
2158 auto *li = liveIntervalsArray[regNO];
2159 if (li == nullptr) {
2160 continue;
2161 }
2162
2163 if (li->IsShouldSave() || li->GetStackSlot() == kSpilled) {
2164 auto itr = dereivedRef2Base.find(regNO);
2165 if (itr != dereivedRef2Base.end()) {
2166 MemOperand *baseRegMemOpnd = cgFunc->GetOrCreatSpillMem(itr->second, k64BitSize);
2167 int64 baseRefMemoffset = baseRegMemOpnd->GetOffsetImmediate()->GetOffsetValue();
2168 insn->GetStackMap()->GetReferenceMap().ReocordStackRoots(baseRefMemoffset);
2169 if (needDump) {
2170 LogInfo::MapleLogger() << "--------insn id: " << insn->GetId() << " base regNO: " << itr->second
2171 << " offset: " << baseRefMemoffset << std::endl;
2172 }
2173 }
2174 MemOperand *memOperand = cgFunc->GetOrCreatSpillMem(regNO, k64BitSize);
2175 int64 offset = memOperand->GetOffsetImmediate()->GetOffsetValue();
2176 insn->GetStackMap()->GetReferenceMap().ReocordStackRoots(offset);
2177 if (itr == dereivedRef2Base.end()) {
2178 insn->GetStackMap()->GetReferenceMap().ReocordStackRoots(offset);
2179 }
2180 if (needDump) {
2181 LogInfo::MapleLogger() << "--------insn id: " << insn->GetId() << " regNO: " << regNO << " offset: "
2182 << offset << std::endl;
2183 }
2184 } else {
2185 // li->GetAssignedReg - R0/RAX?
2186 CHECK_FATAL(false, "not support currently");
2187 insn->GetStackMap()->GetReferenceMap().ReocordRegisterRoots(li->GetAssignedReg());
2188 }
2189 }
2190 }
2191
2192 if (needDump) {
2193 LogInfo::MapleLogger() << "===========reference map stack info end================\n";
2194 }
2195 if (needDump) {
2196 LogInfo::MapleLogger() << "===========reference map info================\n";
2197 for (auto *insn : referenceMapInsns) {
2198 LogInfo::MapleLogger() << " referenceMap insn: ";
2199 insn->Dump();
2200 insn->GetStackMap()->GetReferenceMap().Dump();
2201 }
2202 }
2203 }
2204
SolveRegOpndDeoptInfo(const RegOperand & regOpnd,DeoptInfo & deoptInfo,int32 deoptVregNO) const2205 void LSRALinearScanRegAllocator::SolveRegOpndDeoptInfo(const RegOperand ®Opnd, DeoptInfo &deoptInfo,
2206 int32 deoptVregNO) const
2207 {
2208 if (regOpnd.IsPhysicalRegister()) {
2209 // Get Register No
2210 deoptInfo.RecordDeoptVreg2LocationInfo(deoptVregNO, LocationInfo({kInRegister, 0}));
2211 return;
2212 }
2213 // process virtual RegOperand
2214 regno_t vRegNO = regOpnd.GetRegisterNumber();
2215 LiveInterval *li = liveIntervalsArray[vRegNO];
2216 if (li->IsShouldSave() || li->GetStackSlot() == kSpilled) {
2217 MemOperand *memOpnd = cgFunc->GetOrCreatSpillMem(vRegNO, regOpnd.GetSize());
2218 SolveMemOpndDeoptInfo(*(static_cast<const MemOperand *>(memOpnd)), deoptInfo, deoptVregNO);
2219 } else {
2220 // Get Register NO
2221 deoptInfo.RecordDeoptVreg2LocationInfo(deoptVregNO, LocationInfo({kInRegister, li->GetAssignedReg()}));
2222 }
2223 }
2224
SolveMemOpndDeoptInfo(const MemOperand & memOpnd,DeoptInfo & deoptInfo,int32 deoptVregNO) const2225 void LSRALinearScanRegAllocator::SolveMemOpndDeoptInfo(const MemOperand &memOpnd, DeoptInfo &deoptInfo,
2226 int32 deoptVregNO) const
2227 {
2228 int64 offset = memOpnd.GetOffsetImmediate()->GetOffsetValue();
2229 deoptInfo.RecordDeoptVreg2LocationInfo(deoptVregNO, LocationInfo({kOnStack, offset}));
2230 }
2231
CollectDeoptInfo()2232 void LSRALinearScanRegAllocator::CollectDeoptInfo()
2233 {
2234 const auto referenceMapInsns = cgFunc->GetStackMapInsns();
2235 for (auto *insn : referenceMapInsns) {
2236 auto &deoptInfo = insn->GetStackMap()->GetDeoptInfo();
2237 const auto &deoptBundleInfo = deoptInfo.GetDeoptBundleInfo();
2238 if (deoptBundleInfo.empty()) {
2239 continue;
2240 }
2241 for (const auto &item : deoptBundleInfo) {
2242 const auto *opnd = item.second;
2243 if (opnd->IsRegister()) {
2244 SolveRegOpndDeoptInfo(*static_cast<const RegOperand *>(opnd), deoptInfo, item.first);
2245 continue;
2246 }
2247 if (opnd->IsImmediate()) {
2248 const auto *immOpnd = static_cast<const ImmOperand *>(opnd);
2249 deoptInfo.RecordDeoptVreg2LocationInfo(item.first, LocationInfo({kInConstValue, immOpnd->GetValue()}));
2250 continue;
2251 }
2252 if (opnd->IsMemoryAccessOperand()) {
2253 SolveMemOpndDeoptInfo(*(static_cast<const MemOperand *>(opnd)), deoptInfo, item.first);
2254 continue;
2255 }
2256 DEBUG_ASSERT(false, "can't reach here!");
2257 }
2258 }
2259 if (needDump) {
2260 LogInfo::MapleLogger() << "===========deopt info================\n";
2261 for (auto *insn : referenceMapInsns) {
2262 LogInfo::MapleLogger() << "---- deoptInfo insn: ";
2263 insn->Dump();
2264 insn->GetStackMap()->GetDeoptInfo().Dump();
2265 }
2266 }
2267 }
2268
SetAllocMode()2269 void LSRALinearScanRegAllocator::SetAllocMode()
2270 {
2271 if (CGOptions::IsFastAlloc()) {
2272 if (CGOptions::GetFastAllocMode() == 0) {
2273 fastAlloc = true;
2274 } else {
2275 spillAll = true;
2276 }
2277 /* In-Range spill range can still be specified (only works with --dump-func=). */
2278 } else if (cgFunc->NumBBs() > CGOptions::GetLSRABBOptSize()) {
2279 /* instruction size is checked in ComputeLieveInterval() */
2280 fastAlloc = true;
2281 }
2282
2283 if (needDump) {
2284 if (fastAlloc) {
2285 LogInfo::MapleLogger() << "fastAlloc mode on\n";
2286 }
2287 if (spillAll) {
2288 LogInfo::MapleLogger() << "spillAll mode on\n";
2289 }
2290 }
2291 }
2292
LinearScanRegAllocator()2293 void LSRALinearScanRegAllocator::LinearScanRegAllocator()
2294 {
2295 if (needDump) {
2296 PrintParamQueue("Initial param queue");
2297 PrintCallQueue("Initial call queue");
2298 }
2299 freeUntilPos.resize(regInfo->GetAllRegNum(), UINT32_MAX);
2300 MapleVector<uint32> initialPosVec(freeUntilPos);
2301 uint32 curInsnID = 0;
2302
2303 while (!liQue.empty()) {
2304 LiveInterval *li = liQue.front();
2305 liQue.pop_front();
2306 if (li->GetRangesSize() == 0) {
2307 /* range building has been skiped */
2308 li->AddRange(li->GetFirstDef(), li->GetLastUse());
2309 }
2310 li->InitRangeFinder();
2311 if (needDump) {
2312 LogInfo::MapleLogger() << "======Alloc R" << li->GetRegNO() << "======"
2313 << "\n";
2314 }
2315 blockForbiddenMask = 0;
2316 freeUntilPos = initialPosVec;
2317 DEBUG_ASSERT(li->GetFirstDef() >= curInsnID, "wrong li order");
2318 curInsnID = li->GetFirstDef();
2319 RetireActive(*li, curInsnID);
2320 UpdateCallQueueAtRetirement(curInsnID);
2321 UpdateActiveAllocateInfo(*li);
2322 UpdateParamAllocateInfo(*li);
2323 if (needDump) {
2324 DebugCheckActiveList();
2325 LogInfo::MapleLogger() << "freeUntilPos:";
2326 for (uint32 i = 0; i < freeUntilPos.size(); ++i) {
2327 LogInfo::MapleLogger() << "[" << i << "," << freeUntilPos[i] << "], ";
2328 }
2329 LogInfo::MapleLogger() << "\n";
2330 }
2331 AssignPhysRegsForLi(*li);
2332 }
2333 }
2334
2335 /* Main entrance for the LSRA register allocator */
AllocateRegisters()2336 bool LSRALinearScanRegAllocator::AllocateRegisters()
2337 {
2338 cgFunc->SetIsAfterRegAlloc();
2339 liveIntervalsArray.resize(cgFunc->GetMaxVReg());
2340 regInfo->Fini();
2341 SetAllocMode();
2342 #ifdef RA_PERF_ANALYSIS
2343 auto begin = std::chrono::system_clock::now();
2344 #endif
2345 if (needDump) {
2346 const MIRModule &mirModule = cgFunc->GetMirModule();
2347 DotGenerator::GenerateDot("RA", *cgFunc, mirModule);
2348 DotGenerator::GenerateDot("RAe", *cgFunc, mirModule, true);
2349 LogInfo::MapleLogger() << "Entering LinearScanRegAllocator: " << cgFunc->GetName() << "\n";
2350 }
2351 /* ================= LiveInterval =============== */
2352 #ifdef RA_PERF_ANALYSIS
2353 start = std::chrono::system_clock::now();
2354 #endif
2355 ComputeLiveInterval();
2356
2357 if (needDump) {
2358 PrintLiveRangesGraph();
2359 }
2360
2361 bool enableDoLSRAPreSpill = true;
2362 if (enableDoLSRAPreSpill) {
2363 LiveIntervalAnalysis();
2364 }
2365
2366 #ifdef RA_PERF_ANALYSIS
2367 end = std::chrono::system_clock::now();
2368 liveIntervalUS += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
2369 #endif
2370
2371 /* ================= LiveRange =============== */
2372 #ifdef RA_PERF_ANALYSIS
2373 start = std::chrono::system_clock::now();
2374 #endif
2375
2376 SpillStackMapInfo();
2377
2378 if (needDump) {
2379 PrintAllLiveRanges();
2380 }
2381 #ifdef RA_PERF_ANALYSIS
2382 end = std::chrono::system_clock::now();
2383 holesUS += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
2384 #endif
2385 /* ================= InitFreeRegPool =============== */
2386 InitFreeRegPool();
2387
2388 /* ================= LinearScanRegAllocator =============== */
2389 #ifdef RA_PERF_ANALYSIS
2390 start = std::chrono::system_clock::now();
2391 #endif
2392 LinearScanRegAllocator();
2393 #ifdef RA_PERF_ANALYSIS
2394 end = std::chrono::system_clock::now();
2395 lsraUS += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
2396 #endif
2397
2398 if (needDump) {
2399 PrintAllLiveRanges();
2400 }
2401
2402 #ifdef RA_PERF_ANALYSIS
2403 start = std::chrono::system_clock::now();
2404 #endif
2405 FinalizeRegisters();
2406 #ifdef RA_PERF_ANALYSIS
2407 end = std::chrono::system_clock::now();
2408 finalizeUS += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
2409 #endif
2410
2411 CollectReferenceMap();
2412 CollectDeoptInfo();
2413
2414 if (needDump) {
2415 LogInfo::MapleLogger() << "Total " << spillCount << " spillCount in " << cgFunc->GetName() << " \n";
2416 LogInfo::MapleLogger() << "Total " << reloadCount << " reloadCount\n";
2417 LogInfo::MapleLogger() << "Total "
2418 << "(" << spillCount << "+ " << callerSaveSpillCount
2419 << ") = " << (spillCount + callerSaveSpillCount) << " SPILL\n";
2420 LogInfo::MapleLogger() << "Total "
2421 << "(" << reloadCount << "+ " << callerSaveReloadCount
2422 << ") = " << (reloadCount + callerSaveReloadCount) << " RELOAD\n";
2423 uint32_t insertInsn = spillCount + callerSaveSpillCount + reloadCount + callerSaveReloadCount;
2424 float rate = (float(insertInsn) / float(maxInsnNum));
2425 LogInfo::MapleLogger() << "insn Num Befor RA:" << maxInsnNum << ", insert " << insertInsn << " insns: "
2426 << ", insertInsn/insnNumBeforRA: " << rate << "\n";
2427 }
2428
2429 bfs = nullptr; /* bfs is not utilized outside the function. */
2430
2431 #ifdef RA_PERF_ANALYSIS
2432 end = std::chrono::system_clock::now();
2433 totalUS += std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
2434 #endif
2435
2436 return true;
2437 }
2438
2439 } /* namespace maplebe */
2440