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, 0, 0, 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 // Apply pre-allocated registers on construction
88 GetGraph()->InitUsedRegs<DataType::INT64>(&GetRegMask().GetVector());
89 GetGraph()->InitUsedRegs<DataType::FLOAT64>(&GetVRegMask().GetVector());
90
91 GetGraph()->RunPass<DominatorsTree>();
92
93 // Because linear numbers should stay unchanged from Liveness
94 // pass, we have not to run any passes between. But may be ran
95 // by previous try of allocation.
96 bool res = GetGraph()->RunPass<LivenessAnalyzer>();
97 if (GetGraph()->IsBytecodeOptimizer()) {
98 GetGraph()->InitDefaultLocations();
99 }
100 InitIntervals();
101 if (!PrepareIntervals()) {
102 return false;
103 }
104 return res;
105 }
106
107 // Call resolvers (likely will be the same)
Resolve()108 bool RegAllocBase::Resolve()
109 {
110 if (options.IsCompilerDumpLifeIntervals()) {
111 GetGraph()->GetPassManager()->DumpLifeIntervals(GetPassName());
112 }
113
114 // Save stack slot information in graph for codegen.
115 GetGraph()->SetStackSlotsCount(GetTotalSlotsCount());
116
117 // Resolve Phi and SaveState
118 RegAllocResolver(GetGraph()).Resolve();
119
120 // Connect segmented life intervals
121 SplitResolver(GetGraph()).Run();
122
123 // Resolve spill-fills overwriting
124 if (GetGraph()->IsBytecodeOptimizer()) {
125 auto resolver_reg = GetRegMask().GetReserved().value();
126 auto regs_count = GetRegMask().GetSize();
127 SpillFillsResolver(GetGraph(), resolver_reg, regs_count).Run();
128 } else {
129 SpillFillsResolver(GetGraph()).Run();
130 }
131
132 return true;
133 }
134
Finish()135 bool RegAllocBase::Finish()
136 {
137 // Update loop info after inserting resolving blocks
138 GetGraph()->RunPass<LoopAnalyzer>();
139 #ifndef NDEBUG
140 GetGraph()->SetRegAllocApplied();
141 #endif // NDEBUG
142 COMPILER_LOG(DEBUG, REGALLOC) << "Regalloc " << GetPassName() << " complete";
143 return true;
144 }
145
GetPassName() const146 const char *RegAllocBase::GetPassName() const
147 {
148 return "RegAllocBase";
149 }
150
AbortIfFailed() const151 bool RegAllocBase::AbortIfFailed() const
152 {
153 return true;
154 }
155
SetType(LifeIntervals * interval)156 void RegAllocBase::SetType(LifeIntervals *interval)
157 {
158 // Skip instructions without destination register and zero-constant
159 if (interval->NoDest()) {
160 ASSERT(interval->GetLocation().IsInvalid());
161 return;
162 }
163 auto type = interval->GetInst()->GetType();
164 interval->SetType(ConvertRegType(GetGraph(), type));
165 }
166
SetPreassignedRegisters(LifeIntervals * interval)167 void RegAllocBase::SetPreassignedRegisters(LifeIntervals *interval)
168 {
169 auto inst = interval->GetInst();
170 if (inst->GetDstReg() != INVALID_REG) {
171 interval->SetPreassignedReg(inst->GetDstReg());
172 return;
173 }
174
175 if (inst->GetDstLocation().IsFixedRegister() && !inst->NoDest()) {
176 interval->SetPreassignedReg(inst->GetDstLocation().GetValue());
177 return;
178 }
179
180 if (inst->GetOpcode() == Opcode::Parameter) {
181 auto sf = inst->CastToParameter()->GetLocationData();
182 if (sf.GetSrc().IsAnyRegister()) {
183 auto &mask = sf.GetSrc().IsFpRegister() ? vregs_mask_ : regs_mask_;
184 if (GetGraph()->GetArch() != Arch::AARCH32 || !mask.IsSet(sf.SrcValue())) {
185 interval->SetPreassignedReg(sf.SrcValue());
186 }
187 } else if (sf.GetSrc().IsStackParameter()) {
188 interval->SetLocation(sf.GetSrc());
189 }
190 return;
191 }
192
193 if (inst->IsZeroRegInst()) {
194 interval->SetPreassignedReg(INVALID_REG);
195 }
196 }
197
PrepareIntervals()198 bool RegAllocBase::PrepareIntervals()
199 {
200 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
201 for (auto interval : la.GetLifeIntervals()) {
202 if (!interval->IsPhysical()) {
203 [[maybe_unused]] auto inst = interval->GetInst();
204 ASSERT(inst->IsPhi() || inst->IsCatchPhi() || la.GetInstByLifeNumber(interval->GetBegin()) == inst);
205 SetType(interval);
206 SetPreassignedRegisters(interval);
207 }
208 // perform implementation specific actions
209 PrepareInterval(interval);
210 }
211 return true;
212 }
213
214 /**
215 * Reserve one register in bytecode-optimizer mode to break cyclic spill-fills
216 * dependency by 'SpillFillResolver'
217 */
ReserveTempRegisters()218 void RegAllocBase::ReserveTempRegisters()
219 {
220 if (GetGraph()->IsBytecodeOptimizer()) {
221 auto fixup =
222 static_cast<size_t>(GetGraph()->GetRuntime()->GetMethodTotalArgumentsCount(GetGraph()->GetMethod()));
223 auto reserved_bit = GetRegMask().GetSize() - 1U - fixup;
224 GetRegMask().Reserve(reserved_bit);
225 return;
226 }
227
228 // We don't support temp registers for arm32. Reserve stack slot instead
229 if (GetGraph()->GetArch() == Arch::AARCH32) {
230 GetStackMask().Reserve(0);
231 }
232 }
233
GetTotalSlotsCount()234 size_t RegAllocBase::GetTotalSlotsCount()
235 {
236 if (GetGraph()->IsBytecodeOptimizer() || GetGraph()->GetMode().IsFastPath()) {
237 return GetStackMask().GetUsedCount();
238 }
239 auto param_slots = GetGraph()->GetStackSlotsCount();
240 auto spill_slots_count = GetStackMask().GetUsedCount();
241 size_t lang_ext_slots = 0U;
242
243 GetGraph()->SetExtSlotsStart(param_slots + spill_slots_count);
244 COMPILER_LOG(INFO, REGALLOC) << "Call parameters slots: " << param_slots;
245 COMPILER_LOG(INFO, REGALLOC) << "Spill slots: " << spill_slots_count;
246 COMPILER_LOG(INFO, REGALLOC) << "Language Extension slots: " << lang_ext_slots;
247 auto total_slots = RoundUp(param_slots + lang_ext_slots + spill_slots_count, 2U);
248 return total_slots;
249 }
250
ConnectIntervals(SpillFillInst * spill_fill,const LifeIntervals * src,const LifeIntervals * dst)251 void ConnectIntervals(SpillFillInst *spill_fill, const LifeIntervals *src, const LifeIntervals *dst)
252 {
253 ASSERT(spill_fill->IsSpillFill());
254 spill_fill->AddSpillFill(src->GetLocation(), dst->GetLocation(), dst->GetType());
255
256 if (dst->HasReg()) {
257 dst->GetInst()->GetBasicBlock()->GetGraph()->SetRegUsage(dst->GetReg(), dst->GetType());
258 }
259 }
260
261 } // namespace panda::compiler
262