V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
instruction-selector-impl.h
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<kPointerSize == 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  return Constant(static_cast<int32_t>(0));
339  case MachineRepresentation::kFloat64:
340  return Constant(static_cast<double>(0));
341  case MachineRepresentation::kFloat32:
342  return Constant(static_cast<float>(0));
343  default:
344  UNREACHABLE();
345  }
346  break;
347  }
348  default:
349  break;
350  }
351  UNREACHABLE();
352  }
353 
354  static Constant ToNegatedConstant(const Node* node) {
355  switch (node->opcode()) {
356  case IrOpcode::kInt32Constant:
357  return Constant(-OpParameter<int32_t>(node->op()));
358  case IrOpcode::kInt64Constant:
359  return Constant(-OpParameter<int64_t>(node->op()));
360  default:
361  break;
362  }
363  UNREACHABLE();
364  }
365 
366  UnallocatedOperand Define(Node* node, UnallocatedOperand operand) {
367  DCHECK_NOT_NULL(node);
368  DCHECK_EQ(operand.virtual_register(), GetVReg(node));
369  selector()->MarkAsDefined(node);
370  return operand;
371  }
372 
373  UnallocatedOperand Use(Node* node, UnallocatedOperand operand) {
374  DCHECK_NOT_NULL(node);
375  DCHECK_EQ(operand.virtual_register(), GetVReg(node));
376  selector()->MarkAsUsed(node);
377  return operand;
378  }
379 
380  UnallocatedOperand ToDualLocationUnallocatedOperand(
381  LinkageLocation primary_location, LinkageLocation secondary_location,
382  int virtual_register) {
383  // We only support the primary location being a register and the secondary
384  // one a slot.
385  DCHECK(primary_location.IsRegister() &&
386  secondary_location.IsCalleeFrameSlot());
387  int reg_id = primary_location.AsRegister();
388  int slot_id = secondary_location.AsCalleeFrameSlot();
389  return UnallocatedOperand(reg_id, slot_id, virtual_register);
390  }
391 
392  UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
393  int virtual_register) {
394  if (location.IsAnyRegister()) {
395  // any machine register.
396  return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
397  virtual_register);
398  }
399  if (location.IsCallerFrameSlot()) {
400  // a location on the caller frame.
401  return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
402  location.AsCallerFrameSlot(), virtual_register);
403  }
404  if (location.IsCalleeFrameSlot()) {
405  // a spill location on this (callee) frame.
406  return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
407  location.AsCalleeFrameSlot(), virtual_register);
408  }
409  // a fixed register.
410  if (IsFloatingPoint(location.GetType().representation())) {
411  return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
412  location.AsRegister(), virtual_register);
413  }
414  return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
415  location.AsRegister(), virtual_register);
416  }
417 
418  InstructionSelector* selector_;
419 };
420 
421 } // namespace compiler
422 } // namespace internal
423 } // namespace v8
424 
425 #endif // V8_COMPILER_BACKEND_INSTRUCTION_SELECTOR_IMPL_H_
v8
Definition: libplatform.h:13
uint32_t