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.h"
9 #include "src/compiler/instruction-selector.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 // Helper struct containing data about a table or lookup switch.
19 struct SwitchInfo {
20   int32_t min_value;           // minimum value of {case_values}
21   int32_t max_value;           // maximum value of {case_values}
22   size_t value_range;          // |max_value - min_value| + 1
23   size_t case_count;           // number of cases
24   int32_t* case_values;        // actual case values, unsorted
25   BasicBlock** case_branches;  // basic blocks corresponding to case values
26   BasicBlock* default_branch;  // default branch target
27 };
28 
29 // A helper class for the instruction selector that simplifies construction of
30 // Operands. This class implements a base for architecture-specific helpers.
31 class OperandGenerator {
32  public:
OperandGenerator(InstructionSelector * selector)33   explicit OperandGenerator(InstructionSelector* selector)
34       : selector_(selector) {}
35 
NoOutput()36   InstructionOperand NoOutput() {
37     return InstructionOperand();  // Generates an invalid operand.
38   }
39 
DefineAsRegister(Node * node)40   InstructionOperand DefineAsRegister(Node* node) {
41     return Define(node,
42                   UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
43                                      GetVReg(node)));
44   }
45 
DefineSameAsFirst(Node * node)46   InstructionOperand DefineSameAsFirst(Node* node) {
47     return Define(node,
48                   UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT,
49                                      GetVReg(node)));
50   }
51 
DefineAsFixed(Node * node,Register reg)52   InstructionOperand DefineAsFixed(Node* node, Register reg) {
53     return Define(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
54                                            reg.code(), GetVReg(node)));
55   }
56 
57   template <typename FPRegType>
DefineAsFixed(Node * node,FPRegType reg)58   InstructionOperand DefineAsFixed(Node* node, FPRegType reg) {
59     return Define(node,
60                   UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
61                                      reg.code(), GetVReg(node)));
62   }
63 
DefineAsConstant(Node * node)64   InstructionOperand DefineAsConstant(Node* node) {
65     return DefineAsConstant(node, ToConstant(node));
66   }
67 
DefineAsConstant(Node * node,Constant constant)68   InstructionOperand DefineAsConstant(Node* node, Constant constant) {
69     selector()->MarkAsDefined(node);
70     int virtual_register = GetVReg(node);
71     sequence()->AddConstant(virtual_register, constant);
72     return ConstantOperand(virtual_register);
73   }
74 
DefineAsLocation(Node * node,LinkageLocation location)75   InstructionOperand DefineAsLocation(Node* node, LinkageLocation location) {
76     return Define(node, ToUnallocatedOperand(location, GetVReg(node)));
77   }
78 
DefineAsDualLocation(Node * node,LinkageLocation primary_location,LinkageLocation secondary_location)79   InstructionOperand DefineAsDualLocation(Node* node,
80                                           LinkageLocation primary_location,
81                                           LinkageLocation secondary_location) {
82     return Define(node,
83                   ToDualLocationUnallocatedOperand(
84                       primary_location, secondary_location, GetVReg(node)));
85   }
86 
Use(Node * node)87   InstructionOperand Use(Node* node) {
88     return Use(node, UnallocatedOperand(UnallocatedOperand::NONE,
89                                         UnallocatedOperand::USED_AT_START,
90                                         GetVReg(node)));
91   }
92 
UseAnyAtEnd(Node * node)93   InstructionOperand UseAnyAtEnd(Node* node) {
94     return Use(node, UnallocatedOperand(UnallocatedOperand::ANY,
95                                         UnallocatedOperand::USED_AT_END,
96                                         GetVReg(node)));
97   }
98 
UseAny(Node * node)99   InstructionOperand UseAny(Node* node) {
100     return Use(node, UnallocatedOperand(UnallocatedOperand::ANY,
101                                         UnallocatedOperand::USED_AT_START,
102                                         GetVReg(node)));
103   }
104 
UseRegister(Node * node)105   InstructionOperand UseRegister(Node* node) {
106     return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
107                                         UnallocatedOperand::USED_AT_START,
108                                         GetVReg(node)));
109   }
110 
UseUniqueSlot(Node * node)111   InstructionOperand UseUniqueSlot(Node* node) {
112     return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_SLOT,
113                                         GetVReg(node)));
114   }
115 
116   // Use register or operand for the node. If a register is chosen, it won't
117   // alias any temporary or output registers.
UseUnique(Node * node)118   InstructionOperand UseUnique(Node* node) {
119     return Use(node,
120                UnallocatedOperand(UnallocatedOperand::NONE, GetVReg(node)));
121   }
122 
123   // Use a unique register for the node that does not alias any temporary or
124   // output registers.
UseUniqueRegister(Node * node)125   InstructionOperand UseUniqueRegister(Node* node) {
126     return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
127                                         GetVReg(node)));
128   }
129 
UseFixed(Node * node,Register reg)130   InstructionOperand UseFixed(Node* node, Register reg) {
131     return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
132                                         reg.code(), GetVReg(node)));
133   }
134 
135   template <typename FPRegType>
UseFixed(Node * node,FPRegType reg)136   InstructionOperand UseFixed(Node* node, FPRegType reg) {
137     return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
138                                         reg.code(), GetVReg(node)));
139   }
140 
UseExplicit(LinkageLocation location)141   InstructionOperand UseExplicit(LinkageLocation location) {
142     MachineRepresentation rep = InstructionSequence::DefaultRepresentation();
143     if (location.IsRegister()) {
144       return ExplicitOperand(LocationOperand::REGISTER, rep,
145                              location.AsRegister());
146     } else {
147       return ExplicitOperand(LocationOperand::STACK_SLOT, rep,
148                              location.GetLocation());
149     }
150   }
151 
UseImmediate(int immediate)152   InstructionOperand UseImmediate(int immediate) {
153     return sequence()->AddImmediate(Constant(immediate));
154   }
155 
UseImmediate(Node * node)156   InstructionOperand UseImmediate(Node* node) {
157     return sequence()->AddImmediate(ToConstant(node));
158   }
159 
UseNegatedImmediate(Node * node)160   InstructionOperand UseNegatedImmediate(Node* node) {
161     return sequence()->AddImmediate(ToNegatedConstant(node));
162   }
163 
UseLocation(Node * node,LinkageLocation location)164   InstructionOperand UseLocation(Node* node, LinkageLocation location) {
165     return Use(node, ToUnallocatedOperand(location, GetVReg(node)));
166   }
167 
168   // Used to force gap moves from the from_location to the to_location
169   // immediately before an instruction.
UsePointerLocation(LinkageLocation to_location,LinkageLocation from_location)170   InstructionOperand UsePointerLocation(LinkageLocation to_location,
171                                         LinkageLocation from_location) {
172     UnallocatedOperand casted_from_operand =
173         UnallocatedOperand::cast(TempLocation(from_location));
174     selector_->Emit(kArchNop, casted_from_operand);
175     return ToUnallocatedOperand(to_location,
176                                 casted_from_operand.virtual_register());
177   }
178 
TempRegister()179   InstructionOperand TempRegister() {
180     return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
181                               UnallocatedOperand::USED_AT_START,
182                               sequence()->NextVirtualRegister());
183   }
184 
TempDoubleRegister()185   InstructionOperand TempDoubleRegister() {
186     UnallocatedOperand op = UnallocatedOperand(
187         UnallocatedOperand::MUST_HAVE_REGISTER,
188         UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister());
189     sequence()->MarkAsRepresentation(MachineRepresentation::kFloat64,
190                                      op.virtual_register());
191     return op;
192   }
193 
TempRegister(Register reg)194   InstructionOperand TempRegister(Register reg) {
195     return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, reg.code(),
196                               InstructionOperand::kInvalidVirtualRegister);
197   }
198 
TempImmediate(int32_t imm)199   InstructionOperand TempImmediate(int32_t imm) {
200     return sequence()->AddImmediate(Constant(imm));
201   }
202 
TempLocation(LinkageLocation location)203   InstructionOperand TempLocation(LinkageLocation location) {
204     return ToUnallocatedOperand(location, sequence()->NextVirtualRegister());
205   }
206 
Label(BasicBlock * block)207   InstructionOperand Label(BasicBlock* block) {
208     return sequence()->AddImmediate(
209         Constant(RpoNumber::FromInt(block->rpo_number())));
210   }
211 
212  protected:
selector()213   InstructionSelector* selector() const { return selector_; }
sequence()214   InstructionSequence* sequence() const { return selector()->sequence(); }
zone()215   Zone* zone() const { return selector()->instruction_zone(); }
216 
217  private:
GetVReg(Node * node)218   int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); }
219 
ToConstant(const Node * node)220   static Constant ToConstant(const Node* node) {
221     switch (node->opcode()) {
222       case IrOpcode::kInt32Constant:
223         return Constant(OpParameter<int32_t>(node));
224       case IrOpcode::kInt64Constant:
225         return Constant(OpParameter<int64_t>(node));
226       case IrOpcode::kFloat32Constant:
227         return Constant(OpParameter<float>(node));
228       case IrOpcode::kRelocatableInt32Constant:
229       case IrOpcode::kRelocatableInt64Constant:
230         return Constant(OpParameter<RelocatablePtrConstantInfo>(node));
231       case IrOpcode::kFloat64Constant:
232       case IrOpcode::kNumberConstant:
233         return Constant(OpParameter<double>(node));
234       case IrOpcode::kExternalConstant:
235       case IrOpcode::kComment:
236         return Constant(OpParameter<ExternalReference>(node));
237       case IrOpcode::kHeapConstant:
238         return Constant(OpParameter<Handle<HeapObject>>(node));
239       default:
240         break;
241     }
242     UNREACHABLE();
243     return Constant(static_cast<int32_t>(0));
244   }
245 
ToNegatedConstant(const Node * node)246   static Constant ToNegatedConstant(const Node* node) {
247     switch (node->opcode()) {
248       case IrOpcode::kInt32Constant:
249         return Constant(-OpParameter<int32_t>(node));
250       case IrOpcode::kInt64Constant:
251         return Constant(-OpParameter<int64_t>(node));
252       default:
253         break;
254     }
255     UNREACHABLE();
256     return Constant(static_cast<int32_t>(0));
257   }
258 
Define(Node * node,UnallocatedOperand operand)259   UnallocatedOperand Define(Node* node, UnallocatedOperand operand) {
260     DCHECK_NOT_NULL(node);
261     DCHECK_EQ(operand.virtual_register(), GetVReg(node));
262     selector()->MarkAsDefined(node);
263     return operand;
264   }
265 
Use(Node * node,UnallocatedOperand operand)266   UnallocatedOperand Use(Node* node, UnallocatedOperand operand) {
267     DCHECK_NOT_NULL(node);
268     DCHECK_EQ(operand.virtual_register(), GetVReg(node));
269     selector()->MarkAsUsed(node);
270     return operand;
271   }
272 
ToDualLocationUnallocatedOperand(LinkageLocation primary_location,LinkageLocation secondary_location,int virtual_register)273   UnallocatedOperand ToDualLocationUnallocatedOperand(
274       LinkageLocation primary_location, LinkageLocation secondary_location,
275       int virtual_register) {
276     // We only support the primary location being a register and the secondary
277     // one a slot.
278     DCHECK(primary_location.IsRegister() &&
279            secondary_location.IsCalleeFrameSlot());
280     int reg_id = primary_location.AsRegister();
281     int slot_id = secondary_location.AsCalleeFrameSlot();
282     return UnallocatedOperand(reg_id, slot_id, virtual_register);
283   }
284 
ToUnallocatedOperand(LinkageLocation location,int virtual_register)285   UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
286                                           int virtual_register) {
287     if (location.IsAnyRegister()) {
288       // any machine register.
289       return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
290                                 virtual_register);
291     }
292     if (location.IsCallerFrameSlot()) {
293       // a location on the caller frame.
294       return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
295                                 location.AsCallerFrameSlot(), virtual_register);
296     }
297     if (location.IsCalleeFrameSlot()) {
298       // a spill location on this (callee) frame.
299       return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
300                                 location.AsCalleeFrameSlot(), virtual_register);
301     }
302     // a fixed register.
303     if (IsFloatingPoint(location.GetType().representation())) {
304       return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
305                                 location.AsRegister(), virtual_register);
306     }
307     return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
308                               location.AsRegister(), virtual_register);
309   }
310 
311   InstructionSelector* selector_;
312 };
313 
314 
315 // The flags continuation is a way to combine a branch or a materialization
316 // of a boolean value with an instruction that sets the flags register.
317 // The whole instruction is treated as a unit by the register allocator, and
318 // thus no spills or moves can be introduced between the flags-setting
319 // instruction and the branch or set it should be combined with.
320 class FlagsContinuation final {
321  public:
FlagsContinuation()322   FlagsContinuation() : mode_(kFlags_none) {}
323 
324   // Creates a new flags continuation from the given condition and true/false
325   // blocks.
FlagsContinuation(FlagsCondition condition,BasicBlock * true_block,BasicBlock * false_block)326   FlagsContinuation(FlagsCondition condition, BasicBlock* true_block,
327                     BasicBlock* false_block)
328       : mode_(kFlags_branch),
329         condition_(condition),
330         true_block_(true_block),
331         false_block_(false_block) {
332     DCHECK_NOT_NULL(true_block);
333     DCHECK_NOT_NULL(false_block);
334   }
335 
336   // Creates a new flags continuation for an eager deoptimization exit.
ForDeoptimize(FlagsCondition condition,DeoptimizeReason reason,Node * frame_state)337   static FlagsContinuation ForDeoptimize(FlagsCondition condition,
338                                          DeoptimizeReason reason,
339                                          Node* frame_state) {
340     return FlagsContinuation(condition, reason, frame_state);
341   }
342 
343   // Creates a new flags continuation for a boolean value.
ForSet(FlagsCondition condition,Node * result)344   static FlagsContinuation ForSet(FlagsCondition condition, Node* result) {
345     return FlagsContinuation(condition, result);
346   }
347 
IsNone()348   bool IsNone() const { return mode_ == kFlags_none; }
IsBranch()349   bool IsBranch() const { return mode_ == kFlags_branch; }
IsDeoptimize()350   bool IsDeoptimize() const { return mode_ == kFlags_deoptimize; }
IsSet()351   bool IsSet() const { return mode_ == kFlags_set; }
condition()352   FlagsCondition condition() const {
353     DCHECK(!IsNone());
354     return condition_;
355   }
reason()356   DeoptimizeReason reason() const {
357     DCHECK(IsDeoptimize());
358     return reason_;
359   }
frame_state()360   Node* frame_state() const {
361     DCHECK(IsDeoptimize());
362     return frame_state_or_result_;
363   }
result()364   Node* result() const {
365     DCHECK(IsSet());
366     return frame_state_or_result_;
367   }
true_block()368   BasicBlock* true_block() const {
369     DCHECK(IsBranch());
370     return true_block_;
371   }
false_block()372   BasicBlock* false_block() const {
373     DCHECK(IsBranch());
374     return false_block_;
375   }
376 
Negate()377   void Negate() {
378     DCHECK(!IsNone());
379     condition_ = NegateFlagsCondition(condition_);
380   }
381 
Commute()382   void Commute() {
383     DCHECK(!IsNone());
384     condition_ = CommuteFlagsCondition(condition_);
385   }
386 
Overwrite(FlagsCondition condition)387   void Overwrite(FlagsCondition condition) { condition_ = condition; }
388 
OverwriteAndNegateIfEqual(FlagsCondition condition)389   void OverwriteAndNegateIfEqual(FlagsCondition condition) {
390     DCHECK(condition_ == kEqual || condition_ == kNotEqual);
391     bool negate = condition_ == kEqual;
392     condition_ = condition;
393     if (negate) Negate();
394   }
395 
OverwriteUnsignedIfSigned()396   void OverwriteUnsignedIfSigned() {
397     switch (condition_) {
398       case kSignedLessThan:
399         condition_ = kUnsignedLessThan;
400         break;
401       case kSignedLessThanOrEqual:
402         condition_ = kUnsignedLessThanOrEqual;
403         break;
404       case kSignedGreaterThan:
405         condition_ = kUnsignedGreaterThan;
406         break;
407       case kSignedGreaterThanOrEqual:
408         condition_ = kUnsignedGreaterThanOrEqual;
409         break;
410       default:
411         break;
412     }
413   }
414 
415   // Encodes this flags continuation into the given opcode.
Encode(InstructionCode opcode)416   InstructionCode Encode(InstructionCode opcode) {
417     opcode |= FlagsModeField::encode(mode_);
418     if (mode_ != kFlags_none) {
419       opcode |= FlagsConditionField::encode(condition_);
420     }
421     return opcode;
422   }
423 
424  private:
FlagsContinuation(FlagsCondition condition,DeoptimizeReason reason,Node * frame_state)425   FlagsContinuation(FlagsCondition condition, DeoptimizeReason reason,
426                     Node* frame_state)
427       : mode_(kFlags_deoptimize),
428         condition_(condition),
429         reason_(reason),
430         frame_state_or_result_(frame_state) {
431     DCHECK_NOT_NULL(frame_state);
432   }
FlagsContinuation(FlagsCondition condition,Node * result)433   FlagsContinuation(FlagsCondition condition, Node* result)
434       : mode_(kFlags_set),
435         condition_(condition),
436         frame_state_or_result_(result) {
437     DCHECK_NOT_NULL(result);
438   }
439 
440   FlagsMode const mode_;
441   FlagsCondition condition_;
442   DeoptimizeReason reason_;      // Only value if mode_ == kFlags_deoptimize
443   Node* frame_state_or_result_;  // Only valid if mode_ == kFlags_deoptimize
444                                  // or mode_ == kFlags_set.
445   BasicBlock* true_block_;       // Only valid if mode_ == kFlags_branch.
446   BasicBlock* false_block_;      // Only valid if mode_ == kFlags_branch.
447 };
448 
449 }  // namespace compiler
450 }  // namespace internal
451 }  // namespace v8
452 
453 #endif  // V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_
454