1 /*
2 * Copyright (c) 2021-2024 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_base.h"
17 #include "reg_type.h"
18 #include "optimizer/ir/basicblock.h"
19 #include "optimizer/ir/datatype.h"
20 #include "optimizer/ir/graph.h"
21 #include "optimizer/analysis/dominators_tree.h"
22 #include "optimizer/optimizations/locations_builder.h"
23 #include "split_resolver.h"
24 #include "spill_fills_resolver.h"
25 #include "reg_alloc_resolver.h"
26 #include "reg_alloc_stat.h"
27
28 namespace ark::compiler {
29
RegAllocBase(Graph * graph)30 RegAllocBase::RegAllocBase(Graph *graph)
31 : RegAllocBase(graph, graph->GetArchUsedRegs(), graph->GetArchUsedVRegs(), GetMaxNumStackSlots())
32 {
33 }
34
RegAllocBase(Graph * graph,const RegMask & regMask,const VRegMask & vregMask,size_t slotsCount)35 RegAllocBase::RegAllocBase(Graph *graph, const RegMask ®Mask, const VRegMask &vregMask, size_t slotsCount)
36 : Optimization(graph),
37 regsMask_(graph->GetLocalAllocator()),
38 vregsMask_(graph->GetLocalAllocator()),
39 stackMask_(graph->GetLocalAllocator()),
40 stackUseLastPositions_(graph->GetLocalAllocator()->Adapter())
41 {
42 SetRegMask(regMask);
43 SetVRegMask(vregMask);
44 SetSlotsCount(slotsCount);
45 }
46
RegAllocBase(Graph * graph,size_t regsCount)47 RegAllocBase::RegAllocBase(Graph *graph, size_t regsCount)
48 : Optimization(graph),
49 regsMask_(graph->GetLocalAllocator()),
50 vregsMask_(graph->GetLocalAllocator()),
51 stackMask_(graph->GetLocalAllocator()),
52 stackUseLastPositions_(graph->GetLocalAllocator()->Adapter())
53 {
54 GetRegMask().Resize(regsCount);
55 }
56
RegAllocBase(Graph * graph,LocationMask mask)57 RegAllocBase::RegAllocBase(Graph *graph, LocationMask mask)
58 : Optimization(graph),
59 regsMask_(std::move(mask)),
60 vregsMask_(graph->GetLocalAllocator()),
61 stackMask_(graph->GetLocalAllocator()),
62 stackUseLastPositions_(graph->GetLocalAllocator()->Adapter())
63 {
64 }
65
RunImpl()66 bool RegAllocBase::RunImpl()
67 {
68 if (!Prepare()) {
69 return false;
70 }
71
72 if (!Allocate()) {
73 return false;
74 }
75
76 if (!Resolve()) {
77 return false;
78 }
79
80 if (!Finish()) {
81 return false;
82 }
83
84 #ifndef NDEBUG
85 RegAllocStat st(GetGraph()->GetAnalysis<LivenessAnalyzer>().GetLifeIntervals());
86 COMPILER_LOG(INFO, REGALLOC) << "RegAllocated " << GetPassName() << " reg " << st.GetRegCount() << " vreg "
87 << st.GetVRegCount() << " slots " << st.GetSlotCount() << " vslots "
88 << st.GetVSlotCount();
89 #endif
90
91 return true;
92 }
93
94 // Call required passes (likely will be the same)
Prepare()95 bool RegAllocBase::Prepare()
96 {
97 // Set rzero is used for dynamic mask
98 if (auto rzero = GetGraph()->GetZeroReg(); rzero != GetInvalidReg()) {
99 GetRegMask().Set(rzero);
100 }
101
102 // Apply pre-allocated registers on construction
103 GetGraph()->InitUsedRegs<DataType::INT64>(&GetRegMask().GetVector());
104 GetGraph()->InitUsedRegs<DataType::FLOAT64>(&GetVRegMask().GetVector());
105
106 GetGraph()->RunPass<DominatorsTree>();
107
108 // Because linear numbers should stay unchanged from Liveness
109 // pass, we have not to run any passes between. But may be ran
110 // by previous try of allocation.
111 if (!GetGraph()->RunPass<LivenessAnalyzer>()) {
112 return false;
113 }
114 if (GetGraph()->IsBytecodeOptimizer()) {
115 GetGraph()->InitDefaultLocations();
116 }
117 InitIntervals();
118 PrepareIntervals();
119 return true;
120 }
121
122 // Call resolvers (likely will be the same)
Resolve()123 bool RegAllocBase::Resolve()
124 {
125 if (g_options.IsCompilerDumpLifeIntervals()) {
126 GetGraph()->GetPassManager()->DumpLifeIntervals(GetPassName());
127 }
128
129 // Save stack slot information in graph for codegen.
130 GetGraph()->SetStackSlotsCount(GetTotalSlotsCount());
131
132 // Resolve Phi and SaveState
133 RegAllocResolver(GetGraph()).Resolve();
134
135 // Connect segmented life intervals
136 SplitResolver(GetGraph()).Run();
137
138 // Resolve spill-fills overwriting
139 if (GetGraph()->IsBytecodeOptimizer()) {
140 auto resolverReg = GetRegMask().GetReserved().value();
141 auto regsCount = GetRegMask().GetSize();
142 SpillFillsResolver(GetGraph(), resolverReg, regsCount).Run();
143 } else {
144 SpillFillsResolver(GetGraph()).Run();
145 }
146
147 #ifndef NDEBUG
148 if (!GetGraph()->IsBytecodeOptimizer() && g_options.IsCompilerVerifyRegalloc() &&
149 !GetGraph()->RunPass<RegAllocVerifier>()) {
150 LOG(FATAL, COMPILER) << "Regalloc verification failed";
151 }
152 #endif // NDEBUG
153 return true;
154 }
155
Finish()156 bool RegAllocBase::Finish()
157 {
158 // Update loop info after inserting resolving blocks
159 GetGraph()->RunPass<LoopAnalyzer>();
160 #ifdef COMPILER_DEBUG_CHECKS
161 GetGraph()->SetRegAllocApplied();
162 #endif // COMPILER_DEBUG_CHECKS
163 COMPILER_LOG(DEBUG, REGALLOC) << "Regalloc " << GetPassName() << " complete";
164 return true;
165 }
166
GetPassName() const167 const char *RegAllocBase::GetPassName() const
168 {
169 return "RegAllocBase";
170 }
171
AbortIfFailed() const172 bool RegAllocBase::AbortIfFailed() const
173 {
174 return true;
175 }
176
SetType(LifeIntervals * interval)177 void RegAllocBase::SetType(LifeIntervals *interval)
178 {
179 // Skip instructions without destination register and zero-constant
180 if (interval->NoDest()) {
181 ASSERT(interval->GetLocation().IsInvalid());
182 return;
183 }
184 auto type = interval->GetInst()->GetType();
185 interval->SetType(ConvertRegType(GetGraph(), type));
186 }
187
SetPreassignedRegisters(LifeIntervals * interval)188 void RegAllocBase::SetPreassignedRegisters(LifeIntervals *interval)
189 {
190 auto inst = interval->GetInst();
191 if (inst->GetDstReg() != GetInvalidReg()) {
192 interval->SetPreassignedReg(inst->GetDstReg());
193 return;
194 }
195
196 if (inst->GetDstLocation().IsFixedRegister() && !inst->NoDest()) {
197 interval->SetPreassignedReg(inst->GetDstLocation().GetValue());
198 return;
199 }
200
201 if (inst->GetOpcode() == Opcode::Parameter) {
202 auto sf = inst->CastToParameter()->GetLocationData();
203 if (sf.GetSrc().IsAnyRegister()) {
204 auto &mask = sf.GetSrc().IsFpRegister() ? vregsMask_ : regsMask_;
205 if (GetGraph()->GetArch() != Arch::AARCH32 || !mask.IsSet(sf.SrcValue())) {
206 interval->SetPreassignedReg(sf.SrcValue());
207 }
208 } else if (sf.GetSrc().IsStackParameter()) {
209 interval->SetLocation(sf.GetSrc());
210 }
211 return;
212 }
213
214 if (inst->IsZeroRegInst()) {
215 interval->SetPreassignedReg(GetGraph()->GetZeroReg());
216 }
217 }
218
PrepareIntervals()219 void RegAllocBase::PrepareIntervals()
220 {
221 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
222 for (auto interval : la.GetLifeIntervals()) {
223 if (interval->HasInst()) {
224 [[maybe_unused]] auto inst = interval->GetInst();
225 ASSERT(inst->IsPhi() || inst->IsCatchPhi() || la.GetInstByLifeNumber(interval->GetBegin()) == inst ||
226 (IsPseudoUserOfMultiOutput(inst) &&
227 la.GetInstByLifeNumber(interval->GetBegin()) == inst->GetInput(0).GetInst()));
228 SetType(interval);
229 SetPreassignedRegisters(interval);
230 }
231 // perform implementation specific actions
232 PrepareInterval(interval);
233 }
234 }
235
236 /**
237 * Reserve one register in bytecode-optimizer mode to break cyclic spill-fills
238 * dependency by 'SpillFillResolver'
239 */
ReserveTempRegisters()240 void RegAllocBase::ReserveTempRegisters()
241 {
242 if (GetGraph()->IsBytecodeOptimizer()) {
243 auto fixup =
244 static_cast<int32_t>(GetGraph()->GetRuntime()->GetMethodTotalArgumentsCount(GetGraph()->GetMethod()));
245 auto reservedBit = GetRegMask().GetSize() - 1 - fixup;
246 GetRegMask().Reserve(reservedBit);
247 return;
248 }
249
250 // We don't support temp registers for arm32. Reserve stack slot instead
251 if (GetGraph()->GetArch() == Arch::AARCH32) {
252 GetStackMask().Reserve(0);
253 }
254 }
255
GetTotalSlotsCount()256 size_t RegAllocBase::GetTotalSlotsCount()
257 {
258 if (GetGraph()->IsBytecodeOptimizer() || GetGraph()->GetMode().IsFastPath()) {
259 return GetStackMask().GetUsedCount();
260 }
261 auto paramSlots = GetGraph()->GetStackSlotsCount();
262 auto spillSlotsCount = GetStackMask().GetUsedCount();
263 size_t langExtSlots = 0U;
264 if (GetGraph()->GetArch() != Arch::NONE) {
265 langExtSlots = GetGraph()->GetRuntime()->GetLanguageExtensionSize(GetGraph()->GetArch()) /
266 PointerSize(GetGraph()->GetArch());
267 // We reserve space in frame for currect method and all inlined methods
268 langExtSlots *= GetGraph()->GetMaxInliningDepth() + 1;
269 }
270
271 // language extension slots lies after spill slots
272 GetGraph()->SetExtSlotsStart(spillSlotsCount);
273 COMPILER_LOG(INFO, REGALLOC) << "Call parameters slots: " << paramSlots;
274 COMPILER_LOG(INFO, REGALLOC) << "Spill slots: " << spillSlotsCount;
275 COMPILER_LOG(INFO, REGALLOC) << "Language Extension slots: " << langExtSlots;
276 auto totalSlots = RoundUp(paramSlots + langExtSlots + spillSlotsCount, 2U);
277 return totalSlots;
278 }
279
ConnectIntervals(SpillFillInst * spillFill,const LifeIntervals * src,const LifeIntervals * dst)280 void ConnectIntervals(SpillFillInst *spillFill, const LifeIntervals *src, const LifeIntervals *dst)
281 {
282 ASSERT(spillFill->IsSpillFill());
283 spillFill->AddSpillFill(src->GetLocation(), dst->GetLocation(), dst->GetType());
284
285 if (dst->HasReg()) {
286 dst->GetInst()->GetBasicBlock()->GetGraph()->SetRegUsage(dst->GetReg(), dst->GetType());
287 }
288 }
289
TryToSpillConstant(LifeIntervals * interval,Graph * graph)290 bool TryToSpillConstant(LifeIntervals *interval, Graph *graph)
291 {
292 auto inst = interval->GetInst();
293 ASSERT(inst != nullptr);
294 if (!inst->IsConst() || graph->IsBytecodeOptimizer() || !g_options.IsCompilerRematConst()) {
295 return false;
296 }
297 auto immSlot = graph->AddSpilledConstant(inst->CastToConstant());
298 if (immSlot == GetInvalidImmTableSlot()) {
299 return false;
300 }
301 interval->SetLocation(Location::MakeConstant(immSlot));
302 COMPILER_LOG(DEBUG, REGALLOC) << interval->GetLocation().ToString(graph->GetArch())
303 << " was assigned to the interval " << interval->ToString();
304 return true;
305 }
306
307 } // namespace ark::compiler
308