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