1 /*
2 * Copyright (c) 2021 - 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 "regAllocator.h"
17
18 #include "compiler/core/codeGen.h"
19 #include "checker/types/type.h"
20
21 #include <algorithm>
22 #include <vector>
23
24 namespace panda::es2panda::compiler {
25 // AllocatorBase
26
AllocatorBase(CodeGen * const cg)27 AllocatorBase::AllocatorBase(CodeGen *const cg) noexcept : cg_(cg) {}
28
PushBack(IRNode * const ins) const29 void AllocatorBase::PushBack(IRNode *const ins) const
30 {
31 cg_->Insns().push_back(ins);
32 }
33
GetCodeGen()34 CodeGen &AllocatorBase::GetCodeGen() noexcept
35 {
36 return *cg_;
37 }
38
GetCodeGen() const39 const CodeGen &AllocatorBase::GetCodeGen() const noexcept
40 {
41 return *cg_;
42 }
43
Allocator()44 ArenaAllocator &AllocatorBase::Allocator() noexcept
45 {
46 return *cg_->Allocator();
47 }
48
Allocator() const49 const ArenaAllocator &AllocatorBase::Allocator() const noexcept
50 {
51 return *cg_->Allocator();
52 }
53
54 // SimpleAllocator
55
SimpleAllocator(CodeGen * const cg)56 SimpleAllocator::SimpleAllocator(CodeGen *const cg) noexcept : AllocatorBase(cg) {}
57
AllocLabel(std::string && id)58 Label *SimpleAllocator::AllocLabel(std::string &&id)
59 {
60 const auto *lastInsNode =
61 GetCodeGen().Insns().empty() ? FIRST_NODE_OF_FUNCTION : GetCodeGen().Insns().back()->Node();
62 return Alloc<Label>(lastInsNode, std::move(id));
63 }
64
AddLabel(Label * const label) const65 void SimpleAllocator::AddLabel(Label *const label) const
66 {
67 PushBack(label);
68 }
69
70 // RegAllocatorBase
71
RegAllocatorBase(CodeGen * const cg,RegSpiller * const spiller)72 RegAllocatorBase::RegAllocatorBase(CodeGen *const cg, RegSpiller *const spiller) noexcept
73 : AllocatorBase(cg), spiller_(spiller)
74 {
75 }
76
Spiller()77 RegSpiller &RegAllocatorBase::Spiller() noexcept
78 {
79 return *spiller_;
80 }
81
Spiller() const82 const RegSpiller &RegAllocatorBase::Spiller() const noexcept
83 {
84 return *spiller_;
85 }
86
RegIndicesValid(const IRNode * const ins,const Span<VReg * > & registers)87 std::pair<bool, std::size_t> RegAllocatorBase::RegIndicesValid(const IRNode *const ins, const Span<VReg *> ®isters)
88 {
89 const auto &formats = ins->GetFormats();
90 std::size_t limit = 0;
91
92 for (const auto &format : formats) {
93 for (const auto &formatItem : format.GetFormatItem()) {
94 if (formatItem.IsVReg()) {
95 limit = 1U << formatItem.BitWidth();
96 break;
97 }
98 }
99
100 if (std::all_of(registers.begin(), registers.end(),
101 [limit](const VReg *const reg) { return reg->IsValid(limit); })) {
102 return {true, limit};
103 }
104 }
105
106 return {false, limit};
107 }
108
Spill(IRNode * const ins,const VReg reg) const109 VReg RegAllocatorBase::Spill(IRNode *const ins, const VReg reg) const
110 {
111 const auto [spill_info, origin_type] = spiller_->New();
112
113 if (origin_type != nullptr) {
114 if (auto *const mov = spiller_->MoveReg(ins->Node(), spill_info.SpillReg(), spill_info.OriginReg(), true);
115 mov != nullptr) {
116 PushBack(mov);
117 }
118 }
119
120 if (auto *const mov = spiller_->MoveReg(ins->Node(), spill_info.OriginReg(), reg, false); mov != nullptr) {
121 PushBack(mov);
122 spiller_->GetCodeGen()->SetVRegType(spill_info.OriginReg(), origin_type);
123 }
124
125 return spill_info.OriginReg();
126 }
127
Restore(const IRNode * const ins) const128 void RegAllocatorBase::Restore(const IRNode *const ins) const
129 {
130 const auto spillInfo = spiller_->Restore();
131 if (spiller_->GetCodeGen()->GetVRegType(spillInfo.OriginReg()) == nullptr) {
132 return;
133 }
134
135 if (auto *const mov = spiller_->MoveReg(ins->Node(), spillInfo.OriginReg(), spillInfo.SpillReg(), false);
136 mov != nullptr) {
137 PushBack(mov);
138 }
139 }
140
141 // RegAllocator
142
RegAllocator(CodeGen * const cg,RegSpiller * const spiller)143 RegAllocator::RegAllocator(CodeGen *const cg, RegSpiller *const spiller) noexcept : RegAllocatorBase(cg, spiller) {}
144
Run(IRNode * const ins,const int32_t spillMax)145 void RegAllocator::Run(IRNode *const ins, const int32_t spillMax)
146 {
147 ASSERT(Spiller().Restored());
148 std::array<VReg *, IRNode::MAX_REG_OPERAND> regs {};
149 const auto regCnt = ins->Registers(®s);
150 const auto registers =
151 Span<VReg *>(regs.data(), regs.data() + (spillMax == std::numeric_limits<int32_t>::max() ? regCnt : spillMax));
152
153 std::array<OutVReg, IRNode::MAX_REG_OPERAND> dstRegs {};
154 ins->OutRegisters(&dstRegs);
155
156 const auto [indices_valid, limit] = RegIndicesValid(ins, registers);
157 if (indices_valid) {
158 PushBack(ins);
159 return;
160 }
161
162 const auto rs = Spiller().Start(GetCodeGen());
163
164 std::unordered_set<VReg> validRegs;
165 for (auto *const reg : registers) {
166 if (!reg->IsValid(limit)) {
167 continue;
168 }
169
170 validRegs.insert(*reg);
171 }
172
173 std::vector<IRNode *> dstMoves;
174 size_t i = 0;
175 for (auto *const reg : registers) {
176 auto dstInfo = dstRegs[i++];
177 if (reg->IsValid(limit)) {
178 continue;
179 }
180
181 Spiller().Adjust(validRegs);
182
183 auto r = Spill(ins, *reg);
184
185 if (dstInfo.reg != nullptr) {
186 dstMoves.push_back(GetCodeGen().AllocMov(ins->Node(), dstInfo, r));
187 }
188
189 *reg = r;
190 }
191
192 PushBack(ins);
193
194 for (auto *mov : dstMoves) {
195 PushBack(mov);
196 }
197
198 while (!Spiller().Restored()) {
199 Restore(ins);
200 }
201
202 Spiller().Finalize();
203 }
204
205 // RangeRegAllocator
206
RangeRegAllocator(CodeGen * const cg,RegSpiller * const spiller)207 RangeRegAllocator::RangeRegAllocator(CodeGen *const cg, RegSpiller *const spiller) noexcept
208 : RegAllocatorBase(cg, spiller)
209 {
210 }
211
Run(IRNode * const ins,VReg rangeStart,const std::size_t argCount)212 void RangeRegAllocator::Run(IRNode *const ins, VReg rangeStart, const std::size_t argCount)
213 {
214 ASSERT(Spiller().Restored());
215 const auto rangeEnd = rangeStart + argCount;
216
217 std::array<VReg *, IRNode::MAX_REG_OPERAND> regs {};
218 const auto regCnt = ins->Registers(®s);
219 const auto registers = Span<VReg *>(regs.data(), regs.data() + regCnt);
220 if (RegIndicesValid(ins, registers).first) {
221 PushBack(ins);
222 return;
223 }
224
225 const auto rs = Spiller().Start(GetCodeGen());
226
227 auto regIter = registers.begin();
228 const auto regIterEnd = regIter + registers.size() - 1; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
229
230 while (regIter != regIterEnd) {
231 auto *const reg = *regIter;
232
233 *reg = Spill(ins, *reg);
234 regIter++; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
235 }
236
237 auto *const regStartReg = *regIter;
238 auto reg = rangeStart++;
239 *regStartReg = Spill(ins, reg);
240
241 while (rangeStart != rangeEnd) {
242 reg = rangeStart++;
243 Spill(ins, reg);
244 }
245
246 PushBack(ins);
247
248 while (!Spiller().Restored()) {
249 Restore(ins);
250 }
251
252 Spiller().Finalize();
253 }
254 } // namespace panda::es2panda::compiler
255