1 | // Copyright 2014 the V8 project authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. |
4 | |
5 | #ifndef V8_COMPILER_BACKEND_INSTRUCTION_SELECTOR_IMPL_H_ |
6 | #define V8_COMPILER_BACKEND_INSTRUCTION_SELECTOR_IMPL_H_ |
7 | |
8 | #include "src/compiler/backend/instruction-selector.h" |
9 | #include "src/compiler/backend/instruction.h" |
10 | #include "src/compiler/common-operator.h" |
11 | #include "src/compiler/linkage.h" |
12 | #include "src/compiler/schedule.h" |
13 | #include "src/macro-assembler.h" |
14 | |
15 | namespace v8 { |
16 | namespace internal { |
17 | namespace compiler { |
18 | |
19 | struct CaseInfo { |
20 | int32_t value; // The case value. |
21 | int32_t order; // The order for lowering to comparisons (less means earlier). |
22 | BasicBlock* branch; // The basic blocks corresponding to the case value. |
23 | }; |
24 | |
25 | inline bool operator<(const CaseInfo& l, const CaseInfo& r) { |
26 | return l.order < r.order; |
27 | } |
28 | |
29 | // Helper struct containing data about a table or lookup switch. |
30 | class SwitchInfo { |
31 | public: |
32 | SwitchInfo(ZoneVector<CaseInfo>& cases, int32_t min_value, int32_t max_value, |
33 | BasicBlock* default_branch) |
34 | : cases_(cases), |
35 | min_value_(min_value), |
36 | max_value_(min_value), |
37 | default_branch_(default_branch) { |
38 | if (cases.size() != 0) { |
39 | DCHECK_LE(min_value, max_value); |
40 | // Note that {value_range} can be 0 if {min_value} is -2^31 and |
41 | // {max_value} is 2^31-1, so don't assume that it's non-zero below. |
42 | value_range_ = |
43 | 1u + bit_cast<uint32_t>(max_value) - bit_cast<uint32_t>(min_value); |
44 | } else { |
45 | value_range_ = 0; |
46 | } |
47 | } |
48 | |
49 | // Ensure that comparison order of if-cascades is preserved. |
50 | std::vector<CaseInfo> CasesSortedByOriginalOrder() const { |
51 | std::vector<CaseInfo> result(cases_.begin(), cases_.end()); |
52 | std::stable_sort(result.begin(), result.end()); |
53 | return result; |
54 | } |
55 | std::vector<CaseInfo> CasesSortedByValue() const { |
56 | std::vector<CaseInfo> result(cases_.begin(), cases_.end()); |
57 | std::stable_sort(result.begin(), result.end(), |
58 | [](CaseInfo a, CaseInfo b) { return a.value < b.value; }); |
59 | return result; |
60 | } |
61 | const ZoneVector<CaseInfo>& CasesUnsorted() const { return cases_; } |
62 | int32_t min_value() const { return min_value_; } |
63 | int32_t max_value() const { return max_value_; } |
64 | size_t value_range() const { return value_range_; } |
65 | size_t case_count() const { return cases_.size(); } |
66 | BasicBlock* default_branch() const { return default_branch_; } |
67 | |
68 | private: |
69 | const ZoneVector<CaseInfo>& cases_; |
70 | int32_t min_value_; // minimum value of {cases_} |
71 | int32_t max_value_; // maximum value of {cases_} |
72 | size_t value_range_; // |max_value - min_value| + 1 |
73 | BasicBlock* default_branch_; |
74 | }; |
75 | |
76 | // A helper class for the instruction selector that simplifies construction of |
77 | // Operands. This class implements a base for architecture-specific helpers. |
78 | class OperandGenerator { |
79 | public: |
80 | explicit OperandGenerator(InstructionSelector* selector) |
81 | : selector_(selector) {} |
82 | |
83 | InstructionOperand NoOutput() { |
84 | return InstructionOperand(); // Generates an invalid operand. |
85 | } |
86 | |
87 | InstructionOperand DefineAsRegister(Node* node) { |
88 | return Define(node, |
89 | UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, |
90 | GetVReg(node))); |
91 | } |
92 | |
93 | InstructionOperand DefineSameAsFirst(Node* node) { |
94 | return Define(node, |
95 | UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT, |
96 | GetVReg(node))); |
97 | } |
98 | |
99 | InstructionOperand DefineAsFixed(Node* node, Register reg) { |
100 | return Define(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, |
101 | reg.code(), GetVReg(node))); |
102 | } |
103 | |
104 | template <typename FPRegType> |
105 | InstructionOperand DefineAsFixed(Node* node, FPRegType reg) { |
106 | return Define(node, |
107 | UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER, |
108 | reg.code(), GetVReg(node))); |
109 | } |
110 | |
111 | InstructionOperand DefineAsConstant(Node* node) { |
112 | return DefineAsConstant(node, ToConstant(node)); |
113 | } |
114 | |
115 | InstructionOperand DefineAsConstant(Node* node, Constant constant) { |
116 | selector()->MarkAsDefined(node); |
117 | int virtual_register = GetVReg(node); |
118 | sequence()->AddConstant(virtual_register, constant); |
119 | return ConstantOperand(virtual_register); |
120 | } |
121 | |
122 | InstructionOperand DefineAsLocation(Node* node, LinkageLocation location) { |
123 | return Define(node, ToUnallocatedOperand(location, GetVReg(node))); |
124 | } |
125 | |
126 | InstructionOperand DefineAsDualLocation(Node* node, |
127 | LinkageLocation primary_location, |
128 | LinkageLocation secondary_location) { |
129 | return Define(node, |
130 | ToDualLocationUnallocatedOperand( |
131 | primary_location, secondary_location, GetVReg(node))); |
132 | } |
133 | |
134 | InstructionOperand Use(Node* node) { |
135 | return Use(node, UnallocatedOperand(UnallocatedOperand::NONE, |
136 | UnallocatedOperand::USED_AT_START, |
137 | GetVReg(node))); |
138 | } |
139 | |
140 | InstructionOperand UseAnyAtEnd(Node* node) { |
141 | return Use(node, UnallocatedOperand(UnallocatedOperand::REGISTER_OR_SLOT, |
142 | UnallocatedOperand::USED_AT_END, |
143 | GetVReg(node))); |
144 | } |
145 | |
146 | InstructionOperand UseAny(Node* node) { |
147 | return Use(node, UnallocatedOperand(UnallocatedOperand::REGISTER_OR_SLOT, |
148 | UnallocatedOperand::USED_AT_START, |
149 | GetVReg(node))); |
150 | } |
151 | |
152 | InstructionOperand UseRegisterOrSlotOrConstant(Node* node) { |
153 | return Use(node, UnallocatedOperand( |
154 | UnallocatedOperand::REGISTER_OR_SLOT_OR_CONSTANT, |
155 | UnallocatedOperand::USED_AT_START, GetVReg(node))); |
156 | } |
157 | |
158 | InstructionOperand UseUniqueRegisterOrSlotOrConstant(Node* node) { |
159 | return Use(node, UnallocatedOperand( |
160 | UnallocatedOperand::REGISTER_OR_SLOT_OR_CONSTANT, |
161 | GetVReg(node))); |
162 | } |
163 | |
164 | InstructionOperand UseRegister(Node* node) { |
165 | return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, |
166 | UnallocatedOperand::USED_AT_START, |
167 | GetVReg(node))); |
168 | } |
169 | |
170 | InstructionOperand UseUniqueSlot(Node* node) { |
171 | return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_SLOT, |
172 | GetVReg(node))); |
173 | } |
174 | |
175 | // Use register or operand for the node. If a register is chosen, it won't |
176 | // alias any temporary or output registers. |
177 | InstructionOperand UseUnique(Node* node) { |
178 | return Use(node, |
179 | UnallocatedOperand(UnallocatedOperand::NONE, GetVReg(node))); |
180 | } |
181 | |
182 | // Use a unique register for the node that does not alias any temporary or |
183 | // output registers. |
184 | InstructionOperand UseUniqueRegister(Node* node) { |
185 | return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, |
186 | GetVReg(node))); |
187 | } |
188 | |
189 | InstructionOperand UseFixed(Node* node, Register reg) { |
190 | return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, |
191 | reg.code(), GetVReg(node))); |
192 | } |
193 | |
194 | template <typename FPRegType> |
195 | InstructionOperand UseFixed(Node* node, FPRegType reg) { |
196 | return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER, |
197 | reg.code(), GetVReg(node))); |
198 | } |
199 | |
200 | InstructionOperand UseExplicit(LinkageLocation location) { |
201 | MachineRepresentation rep = InstructionSequence::DefaultRepresentation(); |
202 | if (location.IsRegister()) { |
203 | return ExplicitOperand(LocationOperand::REGISTER, rep, |
204 | location.AsRegister()); |
205 | } else { |
206 | return ExplicitOperand(LocationOperand::STACK_SLOT, rep, |
207 | location.GetLocation()); |
208 | } |
209 | } |
210 | |
211 | InstructionOperand UseImmediate(int immediate) { |
212 | return sequence()->AddImmediate(Constant(immediate)); |
213 | } |
214 | |
215 | InstructionOperand UseImmediate(Node* node) { |
216 | return sequence()->AddImmediate(ToConstant(node)); |
217 | } |
218 | |
219 | InstructionOperand UseNegatedImmediate(Node* node) { |
220 | return sequence()->AddImmediate(ToNegatedConstant(node)); |
221 | } |
222 | |
223 | InstructionOperand UseLocation(Node* node, LinkageLocation location) { |
224 | return Use(node, ToUnallocatedOperand(location, GetVReg(node))); |
225 | } |
226 | |
227 | // Used to force gap moves from the from_location to the to_location |
228 | // immediately before an instruction. |
229 | InstructionOperand UsePointerLocation(LinkageLocation to_location, |
230 | LinkageLocation from_location) { |
231 | UnallocatedOperand casted_from_operand = |
232 | UnallocatedOperand::cast(TempLocation(from_location)); |
233 | selector_->Emit(kArchNop, casted_from_operand); |
234 | return ToUnallocatedOperand(to_location, |
235 | casted_from_operand.virtual_register()); |
236 | } |
237 | |
238 | InstructionOperand TempRegister() { |
239 | return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, |
240 | UnallocatedOperand::USED_AT_START, |
241 | sequence()->NextVirtualRegister()); |
242 | } |
243 | |
244 | int AllocateVirtualRegister() { return sequence()->NextVirtualRegister(); } |
245 | |
246 | InstructionOperand DefineSameAsFirstForVreg(int vreg) { |
247 | return UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT, vreg); |
248 | } |
249 | |
250 | InstructionOperand DefineAsRegistertForVreg(int vreg) { |
251 | return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg); |
252 | } |
253 | |
254 | InstructionOperand UseRegisterForVreg(int vreg) { |
255 | return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, |
256 | UnallocatedOperand::USED_AT_START, vreg); |
257 | } |
258 | |
259 | InstructionOperand TempDoubleRegister() { |
260 | UnallocatedOperand op = UnallocatedOperand( |
261 | UnallocatedOperand::MUST_HAVE_REGISTER, |
262 | UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister()); |
263 | sequence()->MarkAsRepresentation(MachineRepresentation::kFloat64, |
264 | op.virtual_register()); |
265 | return op; |
266 | } |
267 | |
268 | InstructionOperand TempSimd128Register() { |
269 | UnallocatedOperand op = UnallocatedOperand( |
270 | UnallocatedOperand::MUST_HAVE_REGISTER, |
271 | UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister()); |
272 | sequence()->MarkAsRepresentation(MachineRepresentation::kSimd128, |
273 | op.virtual_register()); |
274 | return op; |
275 | } |
276 | |
277 | InstructionOperand TempRegister(Register reg) { |
278 | return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, reg.code(), |
279 | InstructionOperand::kInvalidVirtualRegister); |
280 | } |
281 | |
282 | InstructionOperand TempImmediate(int32_t imm) { |
283 | return sequence()->AddImmediate(Constant(imm)); |
284 | } |
285 | |
286 | InstructionOperand TempLocation(LinkageLocation location) { |
287 | return ToUnallocatedOperand(location, sequence()->NextVirtualRegister()); |
288 | } |
289 | |
290 | InstructionOperand Label(BasicBlock* block) { |
291 | return sequence()->AddImmediate( |
292 | Constant(RpoNumber::FromInt(block->rpo_number()))); |
293 | } |
294 | |
295 | protected: |
296 | InstructionSelector* selector() const { return selector_; } |
297 | InstructionSequence* sequence() const { return selector()->sequence(); } |
298 | Zone* zone() const { return selector()->instruction_zone(); } |
299 | |
300 | private: |
301 | int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); } |
302 | |
303 | static Constant ToConstant(const Node* node) { |
304 | switch (node->opcode()) { |
305 | case IrOpcode::kInt32Constant: |
306 | return Constant(OpParameter<int32_t>(node->op())); |
307 | case IrOpcode::kInt64Constant: |
308 | return Constant(OpParameter<int64_t>(node->op())); |
309 | case IrOpcode::kFloat32Constant: |
310 | return Constant(OpParameter<float>(node->op())); |
311 | case IrOpcode::kRelocatableInt32Constant: |
312 | case IrOpcode::kRelocatableInt64Constant: |
313 | return Constant(OpParameter<RelocatablePtrConstantInfo>(node->op())); |
314 | case IrOpcode::kFloat64Constant: |
315 | case IrOpcode::kNumberConstant: |
316 | return Constant(OpParameter<double>(node->op())); |
317 | case IrOpcode::kExternalConstant: |
318 | return Constant(OpParameter<ExternalReference>(node->op())); |
319 | case IrOpcode::kComment: { |
320 | // We cannot use {intptr_t} here, since the Constant constructor would |
321 | // be ambiguous on some architectures. |
322 | using ptrsize_int_t = |
323 | std::conditional<kSystemPointerSize == 8, int64_t, int32_t>::type; |
324 | return Constant(reinterpret_cast<ptrsize_int_t>( |
325 | OpParameter<const char*>(node->op()))); |
326 | } |
327 | case IrOpcode::kHeapConstant: |
328 | return Constant(HeapConstantOf(node->op())); |
329 | case IrOpcode::kDelayedStringConstant: |
330 | return Constant(StringConstantBaseOf(node->op())); |
331 | case IrOpcode::kDeadValue: { |
332 | switch (DeadValueRepresentationOf(node->op())) { |
333 | case MachineRepresentation::kBit: |
334 | case MachineRepresentation::kWord32: |
335 | case MachineRepresentation::kTagged: |
336 | case MachineRepresentation::kTaggedSigned: |
337 | case MachineRepresentation::kTaggedPointer: |
338 | case MachineRepresentation::kCompressed: |
339 | case MachineRepresentation::kCompressedSigned: |
340 | case MachineRepresentation::kCompressedPointer: |
341 | return Constant(static_cast<int32_t>(0)); |
342 | case MachineRepresentation::kFloat64: |
343 | return Constant(static_cast<double>(0)); |
344 | case MachineRepresentation::kFloat32: |
345 | return Constant(static_cast<float>(0)); |
346 | default: |
347 | UNREACHABLE(); |
348 | } |
349 | break; |
350 | } |
351 | default: |
352 | break; |
353 | } |
354 | UNREACHABLE(); |
355 | } |
356 | |
357 | static Constant ToNegatedConstant(const Node* node) { |
358 | switch (node->opcode()) { |
359 | case IrOpcode::kInt32Constant: |
360 | return Constant(-OpParameter<int32_t>(node->op())); |
361 | case IrOpcode::kInt64Constant: |
362 | return Constant(-OpParameter<int64_t>(node->op())); |
363 | default: |
364 | break; |
365 | } |
366 | UNREACHABLE(); |
367 | } |
368 | |
369 | UnallocatedOperand Define(Node* node, UnallocatedOperand operand) { |
370 | DCHECK_NOT_NULL(node); |
371 | DCHECK_EQ(operand.virtual_register(), GetVReg(node)); |
372 | selector()->MarkAsDefined(node); |
373 | return operand; |
374 | } |
375 | |
376 | UnallocatedOperand Use(Node* node, UnallocatedOperand operand) { |
377 | DCHECK_NOT_NULL(node); |
378 | DCHECK_EQ(operand.virtual_register(), GetVReg(node)); |
379 | selector()->MarkAsUsed(node); |
380 | return operand; |
381 | } |
382 | |
383 | UnallocatedOperand ToDualLocationUnallocatedOperand( |
384 | LinkageLocation primary_location, LinkageLocation secondary_location, |
385 | int virtual_register) { |
386 | // We only support the primary location being a register and the secondary |
387 | // one a slot. |
388 | DCHECK(primary_location.IsRegister() && |
389 | secondary_location.IsCalleeFrameSlot()); |
390 | int reg_id = primary_location.AsRegister(); |
391 | int slot_id = secondary_location.AsCalleeFrameSlot(); |
392 | return UnallocatedOperand(reg_id, slot_id, virtual_register); |
393 | } |
394 | |
395 | UnallocatedOperand ToUnallocatedOperand(LinkageLocation location, |
396 | int virtual_register) { |
397 | if (location.IsAnyRegister()) { |
398 | // any machine register. |
399 | return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, |
400 | virtual_register); |
401 | } |
402 | if (location.IsCallerFrameSlot()) { |
403 | // a location on the caller frame. |
404 | return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT, |
405 | location.AsCallerFrameSlot(), virtual_register); |
406 | } |
407 | if (location.IsCalleeFrameSlot()) { |
408 | // a spill location on this (callee) frame. |
409 | return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT, |
410 | location.AsCalleeFrameSlot(), virtual_register); |
411 | } |
412 | // a fixed register. |
413 | if (IsFloatingPoint(location.GetType().representation())) { |
414 | return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER, |
415 | location.AsRegister(), virtual_register); |
416 | } |
417 | return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, |
418 | location.AsRegister(), virtual_register); |
419 | } |
420 | |
421 | InstructionSelector* selector_; |
422 | }; |
423 | |
424 | } // namespace compiler |
425 | } // namespace internal |
426 | } // namespace v8 |
427 | |
428 | #endif // V8_COMPILER_BACKEND_INSTRUCTION_SELECTOR_IMPL_H_ |
429 | |