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