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
14namespace v8 {
15namespace internal {
16namespace compiler {
17
18// Helper struct containing data about a table or lookup switch.
19struct 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.
31class OperandGenerator {
32 public:
33  explicit OperandGenerator(InstructionSelector* selector)
34      : selector_(selector) {}
35
36  InstructionOperand NoOutput() {
37    return InstructionOperand();  // Generates an invalid operand.
38  }
39
40  InstructionOperand DefineAsRegister(Node* node) {
41    return Define(node,
42                  UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
43                                     GetVReg(node)));
44  }
45
46  InstructionOperand DefineSameAsFirst(Node* node) {
47    return Define(node,
48                  UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT,
49                                     GetVReg(node)));
50  }
51
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>
58  InstructionOperand DefineAsFixed(Node* node, FPRegType reg) {
59    return Define(node,
60                  UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
61                                     reg.code(), GetVReg(node)));
62  }
63
64  InstructionOperand DefineAsConstant(Node* node) {
65    return DefineAsConstant(node, ToConstant(node));
66  }
67
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
75  InstructionOperand DefineAsLocation(Node* node, LinkageLocation location) {
76    return Define(node, ToUnallocatedOperand(location, GetVReg(node)));
77  }
78
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
87  InstructionOperand Use(Node* node) {
88    return Use(node, UnallocatedOperand(UnallocatedOperand::NONE,
89                                        UnallocatedOperand::USED_AT_START,
90                                        GetVReg(node)));
91  }
92
93  InstructionOperand UseAnyAtEnd(Node* node) {
94    return Use(node, UnallocatedOperand(UnallocatedOperand::ANY,
95                                        UnallocatedOperand::USED_AT_END,
96                                        GetVReg(node)));
97  }
98
99  InstructionOperand UseAny(Node* node) {
100    return Use(node, UnallocatedOperand(UnallocatedOperand::ANY,
101                                        UnallocatedOperand::USED_AT_START,
102                                        GetVReg(node)));
103  }
104
105  InstructionOperand UseRegister(Node* node) {
106    return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
107                                        UnallocatedOperand::USED_AT_START,
108                                        GetVReg(node)));
109  }
110
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.
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.
125  InstructionOperand UseUniqueRegister(Node* node) {
126    return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
127                                        GetVReg(node)));
128  }
129
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>
136  InstructionOperand UseFixed(Node* node, FPRegType reg) {
137    return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
138                                        reg.code(), GetVReg(node)));
139  }
140
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
152  InstructionOperand UseImmediate(int immediate) {
153    return sequence()->AddImmediate(Constant(immediate));
154  }
155
156  InstructionOperand UseImmediate(Node* node) {
157    return sequence()->AddImmediate(ToConstant(node));
158  }
159
160  InstructionOperand UseNegatedImmediate(Node* node) {
161    return sequence()->AddImmediate(ToNegatedConstant(node));
162  }
163
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.
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
179  InstructionOperand TempRegister() {
180    return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
181                              UnallocatedOperand::USED_AT_START,
182                              sequence()->NextVirtualRegister());
183  }
184
185  int AllocateVirtualRegister() { return sequence()->NextVirtualRegister(); }
186
187  InstructionOperand DefineSameAsFirstForVreg(int vreg) {
188    return UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT, vreg);
189  }
190
191  InstructionOperand DefineAsRegistertForVreg(int vreg) {
192    return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg);
193  }
194
195  InstructionOperand UseRegisterForVreg(int vreg) {
196    return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
197                              UnallocatedOperand::USED_AT_START, vreg);
198  }
199
200  InstructionOperand TempDoubleRegister() {
201    UnallocatedOperand op = UnallocatedOperand(
202        UnallocatedOperand::MUST_HAVE_REGISTER,
203        UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister());
204    sequence()->MarkAsRepresentation(MachineRepresentation::kFloat64,
205                                     op.virtual_register());
206    return op;
207  }
208
209  InstructionOperand TempRegister(Register reg) {
210    return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, reg.code(),
211                              InstructionOperand::kInvalidVirtualRegister);
212  }
213
214  InstructionOperand TempImmediate(int32_t imm) {
215    return sequence()->AddImmediate(Constant(imm));
216  }
217
218  InstructionOperand TempLocation(LinkageLocation location) {
219    return ToUnallocatedOperand(location, sequence()->NextVirtualRegister());
220  }
221
222  InstructionOperand Label(BasicBlock* block) {
223    return sequence()->AddImmediate(
224        Constant(RpoNumber::FromInt(block->rpo_number())));
225  }
226
227 protected:
228  InstructionSelector* selector() const { return selector_; }
229  InstructionSequence* sequence() const { return selector()->sequence(); }
230  Zone* zone() const { return selector()->instruction_zone(); }
231
232 private:
233  int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); }
234
235  static Constant ToConstant(const Node* node) {
236    switch (node->opcode()) {
237      case IrOpcode::kInt32Constant:
238        return Constant(OpParameter<int32_t>(node));
239      case IrOpcode::kInt64Constant:
240        return Constant(OpParameter<int64_t>(node));
241      case IrOpcode::kFloat32Constant:
242        return Constant(OpParameter<float>(node));
243      case IrOpcode::kRelocatableInt32Constant:
244      case IrOpcode::kRelocatableInt64Constant:
245        return Constant(OpParameter<RelocatablePtrConstantInfo>(node));
246      case IrOpcode::kFloat64Constant:
247      case IrOpcode::kNumberConstant:
248        return Constant(OpParameter<double>(node));
249      case IrOpcode::kExternalConstant:
250      case IrOpcode::kComment:
251        return Constant(OpParameter<ExternalReference>(node));
252      case IrOpcode::kHeapConstant:
253        return Constant(OpParameter<Handle<HeapObject>>(node));
254      default:
255        break;
256    }
257    UNREACHABLE();
258    return Constant(static_cast<int32_t>(0));
259  }
260
261  static Constant ToNegatedConstant(const Node* node) {
262    switch (node->opcode()) {
263      case IrOpcode::kInt32Constant:
264        return Constant(-OpParameter<int32_t>(node));
265      case IrOpcode::kInt64Constant:
266        return Constant(-OpParameter<int64_t>(node));
267      default:
268        break;
269    }
270    UNREACHABLE();
271    return Constant(static_cast<int32_t>(0));
272  }
273
274  UnallocatedOperand Define(Node* node, UnallocatedOperand operand) {
275    DCHECK_NOT_NULL(node);
276    DCHECK_EQ(operand.virtual_register(), GetVReg(node));
277    selector()->MarkAsDefined(node);
278    return operand;
279  }
280
281  UnallocatedOperand Use(Node* node, UnallocatedOperand operand) {
282    DCHECK_NOT_NULL(node);
283    DCHECK_EQ(operand.virtual_register(), GetVReg(node));
284    selector()->MarkAsUsed(node);
285    return operand;
286  }
287
288  UnallocatedOperand ToDualLocationUnallocatedOperand(
289      LinkageLocation primary_location, LinkageLocation secondary_location,
290      int virtual_register) {
291    // We only support the primary location being a register and the secondary
292    // one a slot.
293    DCHECK(primary_location.IsRegister() &&
294           secondary_location.IsCalleeFrameSlot());
295    int reg_id = primary_location.AsRegister();
296    int slot_id = secondary_location.AsCalleeFrameSlot();
297    return UnallocatedOperand(reg_id, slot_id, virtual_register);
298  }
299
300  UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
301                                          int virtual_register) {
302    if (location.IsAnyRegister()) {
303      // any machine register.
304      return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
305                                virtual_register);
306    }
307    if (location.IsCallerFrameSlot()) {
308      // a location on the caller frame.
309      return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
310                                location.AsCallerFrameSlot(), virtual_register);
311    }
312    if (location.IsCalleeFrameSlot()) {
313      // a spill location on this (callee) frame.
314      return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
315                                location.AsCalleeFrameSlot(), virtual_register);
316    }
317    // a fixed register.
318    if (IsFloatingPoint(location.GetType().representation())) {
319      return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
320                                location.AsRegister(), virtual_register);
321    }
322    return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
323                              location.AsRegister(), virtual_register);
324  }
325
326  InstructionSelector* selector_;
327};
328
329
330// The flags continuation is a way to combine a branch or a materialization
331// of a boolean value with an instruction that sets the flags register.
332// The whole instruction is treated as a unit by the register allocator, and
333// thus no spills or moves can be introduced between the flags-setting
334// instruction and the branch or set it should be combined with.
335class FlagsContinuation final {
336 public:
337  FlagsContinuation() : mode_(kFlags_none) {}
338
339  // Creates a new flags continuation from the given condition and true/false
340  // blocks.
341  FlagsContinuation(FlagsCondition condition, BasicBlock* true_block,
342                    BasicBlock* false_block)
343      : mode_(kFlags_branch),
344        condition_(condition),
345        true_block_(true_block),
346        false_block_(false_block) {
347    DCHECK_NOT_NULL(true_block);
348    DCHECK_NOT_NULL(false_block);
349  }
350
351  // Creates a new flags continuation for an eager deoptimization exit.
352  static FlagsContinuation ForDeoptimize(FlagsCondition condition,
353                                         DeoptimizeKind kind,
354                                         DeoptimizeReason reason,
355                                         Node* frame_state) {
356    return FlagsContinuation(condition, kind, reason, frame_state);
357  }
358
359  // Creates a new flags continuation for a boolean value.
360  static FlagsContinuation ForSet(FlagsCondition condition, Node* result) {
361    return FlagsContinuation(condition, result);
362  }
363
364  // Creates a new flags continuation for a wasm trap.
365  static FlagsContinuation ForTrap(FlagsCondition condition,
366                                   Runtime::FunctionId trap_id, Node* result) {
367    return FlagsContinuation(condition, trap_id, result);
368  }
369
370  bool IsNone() const { return mode_ == kFlags_none; }
371  bool IsBranch() const { return mode_ == kFlags_branch; }
372  bool IsDeoptimize() const { return mode_ == kFlags_deoptimize; }
373  bool IsSet() const { return mode_ == kFlags_set; }
374  bool IsTrap() const { return mode_ == kFlags_trap; }
375  FlagsCondition condition() const {
376    DCHECK(!IsNone());
377    return condition_;
378  }
379  DeoptimizeKind kind() const {
380    DCHECK(IsDeoptimize());
381    return kind_;
382  }
383  DeoptimizeReason reason() const {
384    DCHECK(IsDeoptimize());
385    return reason_;
386  }
387  Node* frame_state() const {
388    DCHECK(IsDeoptimize());
389    return frame_state_or_result_;
390  }
391  Node* result() const {
392    DCHECK(IsSet());
393    return frame_state_or_result_;
394  }
395  Runtime::FunctionId trap_id() const {
396    DCHECK(IsTrap());
397    return trap_id_;
398  }
399  BasicBlock* true_block() const {
400    DCHECK(IsBranch());
401    return true_block_;
402  }
403  BasicBlock* false_block() const {
404    DCHECK(IsBranch());
405    return false_block_;
406  }
407
408  void Negate() {
409    DCHECK(!IsNone());
410    condition_ = NegateFlagsCondition(condition_);
411  }
412
413  void Commute() {
414    DCHECK(!IsNone());
415    condition_ = CommuteFlagsCondition(condition_);
416  }
417
418  void Overwrite(FlagsCondition condition) { condition_ = condition; }
419
420  void OverwriteAndNegateIfEqual(FlagsCondition condition) {
421    DCHECK(condition_ == kEqual || condition_ == kNotEqual);
422    bool negate = condition_ == kEqual;
423    condition_ = condition;
424    if (negate) Negate();
425  }
426
427  void OverwriteUnsignedIfSigned() {
428    switch (condition_) {
429      case kSignedLessThan:
430        condition_ = kUnsignedLessThan;
431        break;
432      case kSignedLessThanOrEqual:
433        condition_ = kUnsignedLessThanOrEqual;
434        break;
435      case kSignedGreaterThan:
436        condition_ = kUnsignedGreaterThan;
437        break;
438      case kSignedGreaterThanOrEqual:
439        condition_ = kUnsignedGreaterThanOrEqual;
440        break;
441      default:
442        break;
443    }
444  }
445
446  // Encodes this flags continuation into the given opcode.
447  InstructionCode Encode(InstructionCode opcode) {
448    opcode |= FlagsModeField::encode(mode_);
449    if (mode_ != kFlags_none) {
450      opcode |= FlagsConditionField::encode(condition_);
451    }
452    return opcode;
453  }
454
455 private:
456  FlagsContinuation(FlagsCondition condition, DeoptimizeKind kind,
457                    DeoptimizeReason reason, Node* frame_state)
458      : mode_(kFlags_deoptimize),
459        condition_(condition),
460        kind_(kind),
461        reason_(reason),
462        frame_state_or_result_(frame_state) {
463    DCHECK_NOT_NULL(frame_state);
464  }
465  FlagsContinuation(FlagsCondition condition, Node* result)
466      : mode_(kFlags_set),
467        condition_(condition),
468        frame_state_or_result_(result) {
469    DCHECK_NOT_NULL(result);
470  }
471
472  FlagsContinuation(FlagsCondition condition, Runtime::FunctionId trap_id,
473                    Node* result)
474      : mode_(kFlags_trap),
475        condition_(condition),
476        frame_state_or_result_(result),
477        trap_id_(trap_id) {
478    DCHECK_NOT_NULL(result);
479  }
480
481  FlagsMode const mode_;
482  FlagsCondition condition_;
483  DeoptimizeKind kind_;          // Only valid if mode_ == kFlags_deoptimize
484  DeoptimizeReason reason_;      // Only valid if mode_ == kFlags_deoptimize
485  Node* frame_state_or_result_;  // Only valid if mode_ == kFlags_deoptimize
486                                 // or mode_ == kFlags_set.
487  BasicBlock* true_block_;       // Only valid if mode_ == kFlags_branch.
488  BasicBlock* false_block_;      // Only valid if mode_ == kFlags_branch.
489  Runtime::FunctionId trap_id_;  // Only valid if mode_ == kFlags_trap.
490};
491
492}  // namespace compiler
493}  // namespace internal
494}  // namespace v8
495
496#endif  // V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_
497