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
15namespace v8 {
16namespace internal {
17namespace compiler {
18
19struct 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
25inline 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.
30class 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.
78class 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