1 /**
2 * Copyright (c) 2021-2022 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 "split_resolver.h"
23 #include "spill_fills_resolver.h"
24 #include "reg_alloc_resolver.h"
25 #include "reg_alloc_stat.h"
26
27 namespace panda::compiler {
28
RegAllocBase(Graph * graph)29 RegAllocBase::RegAllocBase(Graph *graph)
30 : RegAllocBase(graph, graph->GetArchUsedRegs(), graph->GetArchUsedVRegs(), MAX_NUM_STACK_SLOTS)
31 {
32 }
33
RegAllocBase(Graph * graph,const RegMask & reg_mask,const VRegMask & vreg_mask,size_t slots_count)34 RegAllocBase::RegAllocBase(Graph *graph, const RegMask ®_mask, const VRegMask &vreg_mask, size_t slots_count)
35 : Optimization(graph),
36 regs_mask_(graph->GetLocalAllocator()),
37 vregs_mask_(graph->GetLocalAllocator()),
38 stack_mask_(graph->GetLocalAllocator()),
39 stack_use_last_positions_(graph->GetLocalAllocator()->Adapter())
40 {
41 SetRegMask(reg_mask);
42 SetVRegMask(vreg_mask);
43 SetSlotsCount(slots_count);
44 }
45
RegAllocBase(Graph * graph,size_t regs_count)46 RegAllocBase::RegAllocBase(Graph *graph, size_t regs_count)
47 : Optimization(graph),
48 regs_mask_(graph->GetLocalAllocator()),
49 vregs_mask_(graph->GetLocalAllocator()),
50 stack_mask_(graph->GetLocalAllocator()),
51 stack_use_last_positions_(graph->GetLocalAllocator()->Adapter())
52 {
53 GetRegMask().Resize(regs_count);
54 }
55
RunImpl()56 bool RegAllocBase::RunImpl()
57 {
58 if (!Prepare()) {
59 return false;
60 }
61
62 if (!Allocate()) {
63 return false;
64 }
65
66 if (!Resolve()) {
67 return false;
68 }
69
70 if (!Finish()) {
71 return false;
72 }
73
74 #ifndef NDEBUG
75 RegAllocStat st(GetGraph()->GetAnalysis<LivenessAnalyzer>().GetLifeIntervals());
76 COMPILER_LOG(INFO, REGALLOC) << "RegAllocated " << GetPassName() << " reg " << st.GetRegCount() << " vreg "
77 << st.GetVRegCount() << " slots " << st.GetSlotCount() << " vslots "
78 << st.GetVSlotCount();
79 #endif
80
81 return true;
82 }
83
84 // Call required passes (likely will be the same)
Prepare()85 bool RegAllocBase::Prepare()
86 {
87 // Set rzero is used for dynamic mask
88 if (auto rzero = GetGraph()->GetZeroReg(); rzero != INVALID_REG) {
89 GetRegMask().Set(rzero);
90 }
91
92 // Apply pre-allocated registers on construction
93 GetGraph()->InitUsedRegs<DataType::INT64>(&GetRegMask().GetVector());
94 GetGraph()->InitUsedRegs<DataType::FLOAT64>(&GetVRegMask().GetVector());
95
96 GetGraph()->RunPass<DominatorsTree>();
97
98 // Because linear numbers should stay unchanged from Liveness
99 // pass, we have not to run any passes between. But may be ran
100 // by previous try of allocation.
101 bool res = GetGraph()->RunPass<LivenessAnalyzer>();
102 if (GetGraph()->IsBytecodeOptimizer()) {
103 GetGraph()->InitDefaultLocations();
104 }
105 InitIntervals();
106 if (!PrepareIntervals()) {
107 return false;
108 }
109 return res;
110 }
111
112 // Call resolvers (likely will be the same)
Resolve()113 bool RegAllocBase::Resolve()
114 {
115 if (options.IsCompilerDumpLifeIntervals()) {
116 GetGraph()->GetPassManager()->DumpLifeIntervals(GetPassName());
117 }
118
119 // Save stack slot information in graph for codegen.
120 GetGraph()->SetStackSlotsCount(GetTotalSlotsCount());
121
122 // Resolve Phi and SaveState
123 RegAllocResolver(GetGraph()).Resolve();
124
125 // Connect segmented life intervals
126 SplitResolver(GetGraph()).Run();
127
128 // Resolve spill-fills overwriting
129 if (GetGraph()->IsBytecodeOptimizer()) {
130 auto resolver_reg = GetRegMask().GetReserved().value();
131 auto regs_count = GetRegMask().GetSize();
132 SpillFillsResolver(GetGraph(), resolver_reg, regs_count).Run();
133 } else {
134 SpillFillsResolver(GetGraph()).Run();
135 }
136
137 return true;
138 }
139
Finish()140 bool RegAllocBase::Finish()
141 {
142 // Update loop info after inserting resolving blocks
143 GetGraph()->RunPass<LoopAnalyzer>();
144 #ifndef NDEBUG
145 GetGraph()->SetRegAllocApplied();
146 #endif // NDEBUG
147 COMPILER_LOG(DEBUG, REGALLOC) << "Regalloc " << GetPassName() << " complete";
148 return true;
149 }
150
GetPassName() const151 const char *RegAllocBase::GetPassName() const
152 {
153 return "RegAllocBase";
154 }
155
AbortIfFailed() const156 bool RegAllocBase::AbortIfFailed() const
157 {
158 return true;
159 }
160
SetType(LifeIntervals * interval)161 void RegAllocBase::SetType(LifeIntervals *interval)
162 {
163 // Skip instructions without destination register and zero-constant
164 if (interval->NoDest()) {
165 ASSERT(interval->GetLocation().IsInvalid());
166 return;
167 }
168 auto type = interval->GetInst()->GetType();
169 interval->SetType(ConvertRegType(GetGraph(), type));
170 }
171
SetPreassignedRegisters(LifeIntervals * interval)172 void RegAllocBase::SetPreassignedRegisters(LifeIntervals *interval)
173 {
174 auto inst = interval->GetInst();
175
176 if (inst->GetDstReg() != INVALID_REG) {
177 interval->SetPreassignedReg(inst->GetDstReg());
178 return;
179 }
180
181 if (inst->GetDstLocation().IsFixedRegister() && !inst->NoDest()) {
182 interval->SetPreassignedReg(inst->GetDstLocation().GetValue());
183 return;
184 }
185
186 if (inst->GetOpcode() == Opcode::Parameter) {
187 auto sf = inst->CastToParameter()->GetLocationData();
188 if (sf.GetSrc().IsAnyRegister()) {
189 auto &mask = sf.GetSrc().IsFpRegister() ? vregs_mask_ : regs_mask_;
190 if (GetGraph()->GetArch() != Arch::AARCH32 || !mask.IsSet(sf.SrcValue())) {
191 interval->SetPreassignedReg(sf.SrcValue());
192 }
193 } else if (sf.GetSrc().IsStackParameter()) {
194 interval->SetLocation(sf.GetSrc());
195 }
196 return;
197 }
198
199 if (inst->IsZeroRegInst()) {
200 interval->SetPreassignedReg(GetGraph()->GetZeroReg());
201 }
202 }
203
PrepareIntervals()204 bool RegAllocBase::PrepareIntervals()
205 {
206 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
207 for (auto interval : la.GetLifeIntervals()) {
208 if (!interval->IsPhysical()) {
209 [[maybe_unused]] auto inst = interval->GetInst();
210 ASSERT(inst->IsPhi() || inst->IsCatchPhi() || la.GetInstByLifeNumber(interval->GetBegin()) == inst ||
211 (IsPseudoUserOfMultiOutput(inst) &&
212 la.GetInstByLifeNumber(interval->GetBegin()) == inst->GetInput(0).GetInst()));
213 SetType(interval);
214 SetPreassignedRegisters(interval);
215 }
216 // perform implementation specific actions
217 PrepareInterval(interval);
218 }
219 return true;
220 }
221
222 /**
223 * Reserve one register in bytecode-optimizer mode to break cyclic spill-fills
224 * dependency by 'SpillFillResolver'
225 */
ReserveTempRegisters()226 void RegAllocBase::ReserveTempRegisters()
227 {
228 if (GetGraph()->IsBytecodeOptimizer()) {
229 auto fixup =
230 static_cast<size_t>(GetGraph()->GetRuntime()->GetMethodTotalArgumentsCount(GetGraph()->GetMethod()));
231 auto reserved_bit = GetRegMask().GetSize() - 1U - fixup;
232 GetRegMask().Reserve(reserved_bit);
233 return;
234 }
235
236 // We don't support temp registers for arm32. Reserve stack slot instead
237 if (GetGraph()->GetArch() == Arch::AARCH32) {
238 GetStackMask().Reserve(0);
239 }
240 }
241
GetTotalSlotsCount()242 size_t RegAllocBase::GetTotalSlotsCount()
243 {
244 if (GetGraph()->IsBytecodeOptimizer() || GetGraph()->GetMode().IsFastPath()) {
245 return GetStackMask().GetUsedCount();
246 }
247 auto param_slots = GetGraph()->GetStackSlotsCount();
248 auto spill_slots_count = GetStackMask().GetUsedCount();
249 size_t lang_ext_slots = 0U;
250 if (GetGraph()->GetArch() != Arch::NONE) {
251 lang_ext_slots = GetGraph()->GetRuntime()->GetLanguageExtensionSize() / PointerSize(GetGraph()->GetArch());
252 }
253
254 GetGraph()->SetExtSlotsStart(param_slots + spill_slots_count);
255 COMPILER_LOG(INFO, REGALLOC) << "Call parameters slots: " << param_slots;
256 COMPILER_LOG(INFO, REGALLOC) << "Spill slots: " << spill_slots_count;
257 COMPILER_LOG(INFO, REGALLOC) << "Language Extension slots: " << lang_ext_slots;
258 auto total_slots = RoundUp(param_slots + lang_ext_slots + spill_slots_count, 2U);
259 return total_slots;
260 }
261
ConnectIntervals(SpillFillInst * spill_fill,const LifeIntervals * src,const LifeIntervals * dst)262 void ConnectIntervals(SpillFillInst *spill_fill, const LifeIntervals *src, const LifeIntervals *dst)
263 {
264 ASSERT(spill_fill->IsSpillFill());
265 spill_fill->AddSpillFill(src->GetLocation(), dst->GetLocation(), dst->GetType());
266
267 if (dst->HasReg()) {
268 dst->GetInst()->GetBasicBlock()->GetGraph()->SetRegUsage(dst->GetReg(), dst->GetType());
269 }
270 }
271
272 } // namespace panda::compiler
273