instruction.h revision 13e2dadd00298019ed862f2b2fc5068bba730bcf 
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_H_
6#define V8_COMPILER_INSTRUCTION_H_
7
8#include <deque>
9#include <iosfwd>
10#include <map>
11#include <set>
12
13#include "src/compiler/common-operator.h"
14#include "src/compiler/frame.h"
15#include "src/compiler/instruction-codes.h"
16#include "src/compiler/opcodes.h"
17#include "src/compiler/source-position.h"
18#include "src/macro-assembler.h"
19#include "src/register-configuration.h"
20#include "src/zone-allocator.h"
21
22namespace v8 {
23namespace internal {
24namespace compiler {
25
26// Forward declarations.
27class Schedule;
28
29
30class InstructionOperand {
31 public:
32  static const int kInvalidVirtualRegister = -1;
33
34  // TODO(dcarney): recover bit. INVALID can be represented as UNALLOCATED with
35  // kInvalidVirtualRegister and some DCHECKS.
36  enum Kind { INVALID, UNALLOCATED, CONSTANT, IMMEDIATE, EXPLICIT, ALLOCATED };
37
38  InstructionOperand() : InstructionOperand(INVALID) {}
39
40  Kind kind() const { return KindField::decode(value_); }
41
42#define INSTRUCTION_OPERAND_PREDICATE(name, type) \
43  bool Is##name() const { return kind() == type; }
44  INSTRUCTION_OPERAND_PREDICATE(Invalid, INVALID)
45  // UnallocatedOperands are place-holder operands created before register
46  // allocation. They later are assigned registers and become AllocatedOperands.
47  INSTRUCTION_OPERAND_PREDICATE(Unallocated, UNALLOCATED)
48  // Constant operands participate in register allocation. They are allocated to
49  // registers but have a special "spilling" behavior. When a ConstantOperand
50  // value must be rematerialized, it is loaded from an immediate constant
51  // rather from an unspilled slot.
52  INSTRUCTION_OPERAND_PREDICATE(Constant, CONSTANT)
53  // ImmediateOperands do not participate in register allocation and are only
54  // embedded directly in instructions, e.g. small integers and on some
55  // platforms Objects.
56  INSTRUCTION_OPERAND_PREDICATE(Immediate, IMMEDIATE)
57  // ExplicitOperands do not participate in register allocation. They are
58  // created by the instruction selector for direct access to registers and
59  // stack slots, completely bypassing the register allocator. They are never
60  // associated with a virtual register
61  INSTRUCTION_OPERAND_PREDICATE(Explicit, EXPLICIT)
62  // AllocatedOperands are registers or stack slots that are assigned by the
63  // register allocator and are always associated with a virtual register.
64  INSTRUCTION_OPERAND_PREDICATE(Allocated, ALLOCATED)
65#undef INSTRUCTION_OPERAND_PREDICATE
66
67  inline bool IsAnyRegister() const;
68  inline bool IsRegister() const;
69  inline bool IsFPRegister() const;
70  inline bool IsFloatRegister() const;
71  inline bool IsDoubleRegister() const;
72  inline bool IsSimd128Register() const;
73  inline bool IsStackSlot() const;
74  inline bool IsFPStackSlot() const;
75  inline bool IsFloatStackSlot() const;
76  inline bool IsDoubleStackSlot() const;
77  inline bool IsSimd128StackSlot() const;
78
79  template <typename SubKindOperand>
80  static SubKindOperand* New(Zone* zone, const SubKindOperand& op) {
81    void* buffer = zone->New(sizeof(op));
82    return new (buffer) SubKindOperand(op);
83  }
84
85  static void ReplaceWith(InstructionOperand* dest,
86                          const InstructionOperand* src) {
87    *dest = *src;
88  }
89
90  bool Equals(const InstructionOperand& that) const {
91    return this->value_ == that.value_;
92  }
93
94  bool Compare(const InstructionOperand& that) const {
95    return this->value_ < that.value_;
96  }
97
98  bool EqualsCanonicalized(const InstructionOperand& that) const {
99    return this->GetCanonicalizedValue() == that.GetCanonicalizedValue();
100  }
101
102  bool CompareCanonicalized(const InstructionOperand& that) const {
103    return this->GetCanonicalizedValue() < that.GetCanonicalizedValue();
104  }
105
106  bool InterferesWith(const InstructionOperand& that) const;
107
108  void Print(const RegisterConfiguration* config) const;
109  void Print() const;
110
111 protected:
112  explicit InstructionOperand(Kind kind) : value_(KindField::encode(kind)) {}
113
114  inline uint64_t GetCanonicalizedValue() const;
115
116  class KindField : public BitField64<Kind, 0, 3> {};
117
118  uint64_t value_;
119};
120
121
122typedef ZoneVector<InstructionOperand> InstructionOperandVector;
123
124
125struct PrintableInstructionOperand {
126  const RegisterConfiguration* register_configuration_;
127  InstructionOperand op_;
128};
129
130
131std::ostream& operator<<(std::ostream& os,
132                         const PrintableInstructionOperand& op);
133
134
135#define INSTRUCTION_OPERAND_CASTS(OperandType, OperandKind)      \
136                                                                 \
137  static OperandType* cast(InstructionOperand* op) {             \
138    DCHECK_EQ(OperandKind, op->kind());                          \
139    return static_cast<OperandType*>(op);                        \
140  }                                                              \
141                                                                 \
142  static const OperandType* cast(const InstructionOperand* op) { \
143    DCHECK_EQ(OperandKind, op->kind());                          \
144    return static_cast<const OperandType*>(op);                  \
145  }                                                              \
146                                                                 \
147  static OperandType cast(const InstructionOperand& op) {        \
148    DCHECK_EQ(OperandKind, op.kind());                           \
149    return *static_cast<const OperandType*>(&op);                \
150  }
151
152class UnallocatedOperand : public InstructionOperand {
153 public:
154  enum BasicPolicy { FIXED_SLOT, EXTENDED_POLICY };
155
156  enum ExtendedPolicy {
157    NONE,
158    ANY,
159    FIXED_REGISTER,
160    FIXED_FP_REGISTER,
161    MUST_HAVE_REGISTER,
162    MUST_HAVE_SLOT,
163    SAME_AS_FIRST_INPUT
164  };
165
166  // Lifetime of operand inside the instruction.
167  enum Lifetime {
168    // USED_AT_START operand is guaranteed to be live only at
169    // instruction start. Register allocator is free to assign the same register
170    // to some other operand used inside instruction (i.e. temporary or
171    // output).
172    USED_AT_START,
173
174    // USED_AT_END operand is treated as live until the end of
175    // instruction. This means that register allocator will not reuse it's
176    // register for any other operand inside instruction.
177    USED_AT_END
178  };
179
180  UnallocatedOperand(ExtendedPolicy policy, int virtual_register)
181      : UnallocatedOperand(virtual_register) {
182    value_ |= BasicPolicyField::encode(EXTENDED_POLICY);
183    value_ |= ExtendedPolicyField::encode(policy);
184    value_ |= LifetimeField::encode(USED_AT_END);
185  }
186
187  UnallocatedOperand(BasicPolicy policy, int index, int virtual_register)
188      : UnallocatedOperand(virtual_register) {
189    DCHECK(policy == FIXED_SLOT);
190    value_ |= BasicPolicyField::encode(policy);
191    value_ |= static_cast<int64_t>(index) << FixedSlotIndexField::kShift;
192    DCHECK(this->fixed_slot_index() == index);
193  }
194
195  UnallocatedOperand(ExtendedPolicy policy, int index, int virtual_register)
196      : UnallocatedOperand(virtual_register) {
197    DCHECK(policy == FIXED_REGISTER || policy == FIXED_FP_REGISTER);
198    value_ |= BasicPolicyField::encode(EXTENDED_POLICY);
199    value_ |= ExtendedPolicyField::encode(policy);
200    value_ |= LifetimeField::encode(USED_AT_END);
201    value_ |= FixedRegisterField::encode(index);
202  }
203
204  UnallocatedOperand(ExtendedPolicy policy, Lifetime lifetime,
205                     int virtual_register)
206      : UnallocatedOperand(virtual_register) {
207    value_ |= BasicPolicyField::encode(EXTENDED_POLICY);
208    value_ |= ExtendedPolicyField::encode(policy);
209    value_ |= LifetimeField::encode(lifetime);
210  }
211
212  UnallocatedOperand(int reg_id, int slot_id, int virtual_register)
213      : UnallocatedOperand(FIXED_REGISTER, reg_id, virtual_register) {
214    value_ |= HasSecondaryStorageField::encode(true);
215    value_ |= SecondaryStorageField::encode(slot_id);
216  }
217
218  // Predicates for the operand policy.
219  bool HasAnyPolicy() const {
220    return basic_policy() == EXTENDED_POLICY && extended_policy() == ANY;
221  }
222  bool HasFixedPolicy() const {
223    return basic_policy() == FIXED_SLOT ||
224           extended_policy() == FIXED_REGISTER ||
225           extended_policy() == FIXED_FP_REGISTER;
226  }
227  bool HasRegisterPolicy() const {
228    return basic_policy() == EXTENDED_POLICY &&
229           extended_policy() == MUST_HAVE_REGISTER;
230  }
231  bool HasSlotPolicy() const {
232    return basic_policy() == EXTENDED_POLICY &&
233           extended_policy() == MUST_HAVE_SLOT;
234  }
235  bool HasSameAsInputPolicy() const {
236    return basic_policy() == EXTENDED_POLICY &&
237           extended_policy() == SAME_AS_FIRST_INPUT;
238  }
239  bool HasFixedSlotPolicy() const { return basic_policy() == FIXED_SLOT; }
240  bool HasFixedRegisterPolicy() const {
241    return basic_policy() == EXTENDED_POLICY &&
242           extended_policy() == FIXED_REGISTER;
243  }
244  bool HasFixedFPRegisterPolicy() const {
245    return basic_policy() == EXTENDED_POLICY &&
246           extended_policy() == FIXED_FP_REGISTER;
247  }
248  bool HasSecondaryStorage() const {
249    return basic_policy() == EXTENDED_POLICY &&
250           extended_policy() == FIXED_REGISTER &&
251           HasSecondaryStorageField::decode(value_);
252  }
253  int GetSecondaryStorage() const {
254    DCHECK(HasSecondaryStorage());
255    return SecondaryStorageField::decode(value_);
256  }
257
258  // [basic_policy]: Distinguish between FIXED_SLOT and all other policies.
259  BasicPolicy basic_policy() const {
260    DCHECK_EQ(UNALLOCATED, kind());
261    return BasicPolicyField::decode(value_);
262  }
263
264  // [extended_policy]: Only for non-FIXED_SLOT. The finer-grained policy.
265  ExtendedPolicy extended_policy() const {
266    DCHECK(basic_policy() == EXTENDED_POLICY);
267    return ExtendedPolicyField::decode(value_);
268  }
269
270  // [fixed_slot_index]: Only for FIXED_SLOT.
271  int fixed_slot_index() const {
272    DCHECK(HasFixedSlotPolicy());
273    return static_cast<int>(static_cast<int64_t>(value_) >>
274                            FixedSlotIndexField::kShift);
275  }
276
277  // [fixed_register_index]: Only for FIXED_REGISTER or FIXED_FP_REGISTER.
278  int fixed_register_index() const {
279    DCHECK(HasFixedRegisterPolicy() || HasFixedFPRegisterPolicy());
280    return FixedRegisterField::decode(value_);
281  }
282
283  // [virtual_register]: The virtual register ID for this operand.
284  int32_t virtual_register() const {
285    DCHECK_EQ(UNALLOCATED, kind());
286    return static_cast<int32_t>(VirtualRegisterField::decode(value_));
287  }
288
289  // TODO(dcarney): remove this.
290  void set_virtual_register(int32_t id) {
291    DCHECK_EQ(UNALLOCATED, kind());
292    value_ = VirtualRegisterField::update(value_, static_cast<uint32_t>(id));
293  }
294
295  // [lifetime]: Only for non-FIXED_SLOT.
296  bool IsUsedAtStart() const {
297    DCHECK(basic_policy() == EXTENDED_POLICY);
298    return LifetimeField::decode(value_) == USED_AT_START;
299  }
300
301  INSTRUCTION_OPERAND_CASTS(UnallocatedOperand, UNALLOCATED);
302
303  // The encoding used for UnallocatedOperand operands depends on the policy
304  // that is
305  // stored within the operand. The FIXED_SLOT policy uses a compact encoding
306  // because it accommodates a larger pay-load.
307  //
308  // For FIXED_SLOT policy:
309  //     +------------------------------------------------+
310  //     |      slot_index   | 0 | virtual_register | 001 |
311  //     +------------------------------------------------+
312  //
313  // For all other (extended) policies:
314  //     +-----------------------------------------------------+
315  //     |  reg_index  | L | PPP |  1 | virtual_register | 001 |
316  //     +-----------------------------------------------------+
317  //     L ... Lifetime
318  //     P ... Policy
319  //
320  // The slot index is a signed value which requires us to decode it manually
321  // instead of using the BitField utility class.
322
323  STATIC_ASSERT(KindField::kSize == 3);
324
325  class VirtualRegisterField : public BitField64<uint32_t, 3, 32> {};
326
327  // BitFields for all unallocated operands.
328  class BasicPolicyField : public BitField64<BasicPolicy, 35, 1> {};
329
330  // BitFields specific to BasicPolicy::FIXED_SLOT.
331  class FixedSlotIndexField : public BitField64<int, 36, 28> {};
332
333  // BitFields specific to BasicPolicy::EXTENDED_POLICY.
334  class ExtendedPolicyField : public BitField64<ExtendedPolicy, 36, 3> {};
335  class LifetimeField : public BitField64<Lifetime, 39, 1> {};
336  class HasSecondaryStorageField : public BitField64<bool, 40, 1> {};
337  class FixedRegisterField : public BitField64<int, 41, 6> {};
338  class SecondaryStorageField : public BitField64<int, 47, 3> {};
339
340 private:
341  explicit UnallocatedOperand(int virtual_register)
342      : InstructionOperand(UNALLOCATED) {
343    value_ |=
344        VirtualRegisterField::encode(static_cast<uint32_t>(virtual_register));
345  }
346};
347
348
349class ConstantOperand : public InstructionOperand {
350 public:
351  explicit ConstantOperand(int virtual_register)
352      : InstructionOperand(CONSTANT) {
353    value_ |=
354        VirtualRegisterField::encode(static_cast<uint32_t>(virtual_register));
355  }
356
357  int32_t virtual_register() const {
358    return static_cast<int32_t>(VirtualRegisterField::decode(value_));
359  }
360
361  static ConstantOperand* New(Zone* zone, int virtual_register) {
362    return InstructionOperand::New(zone, ConstantOperand(virtual_register));
363  }
364
365  INSTRUCTION_OPERAND_CASTS(ConstantOperand, CONSTANT);
366
367  STATIC_ASSERT(KindField::kSize == 3);
368  class VirtualRegisterField : public BitField64<uint32_t, 3, 32> {};
369};
370
371
372class ImmediateOperand : public InstructionOperand {
373 public:
374  enum ImmediateType { INLINE, INDEXED };
375
376  explicit ImmediateOperand(ImmediateType type, int32_t value)
377      : InstructionOperand(IMMEDIATE) {
378    value_ |= TypeField::encode(type);
379    value_ |= static_cast<int64_t>(value) << ValueField::kShift;
380  }
381
382  ImmediateType type() const { return TypeField::decode(value_); }
383
384  int32_t inline_value() const {
385    DCHECK_EQ(INLINE, type());
386    return static_cast<int64_t>(value_) >> ValueField::kShift;
387  }
388
389  int32_t indexed_value() const {
390    DCHECK_EQ(INDEXED, type());
391    return static_cast<int64_t>(value_) >> ValueField::kShift;
392  }
393
394  static ImmediateOperand* New(Zone* zone, ImmediateType type, int32_t value) {
395    return InstructionOperand::New(zone, ImmediateOperand(type, value));
396  }
397
398  INSTRUCTION_OPERAND_CASTS(ImmediateOperand, IMMEDIATE);
399
400  STATIC_ASSERT(KindField::kSize == 3);
401  class TypeField : public BitField64<ImmediateType, 3, 1> {};
402  class ValueField : public BitField64<int32_t, 32, 32> {};
403};
404
405
406class LocationOperand : public InstructionOperand {
407 public:
408  enum LocationKind { REGISTER, STACK_SLOT };
409
410  LocationOperand(InstructionOperand::Kind operand_kind,
411                  LocationOperand::LocationKind location_kind,
412                  MachineRepresentation rep, int index)
413      : InstructionOperand(operand_kind) {
414    DCHECK_IMPLIES(location_kind == REGISTER, index >= 0);
415    DCHECK(IsSupportedRepresentation(rep));
416    value_ |= LocationKindField::encode(location_kind);
417    value_ |= RepresentationField::encode(rep);
418    value_ |= static_cast<int64_t>(index) << IndexField::kShift;
419  }
420
421  int index() const {
422    DCHECK(IsStackSlot() || IsFPStackSlot());
423    return static_cast<int64_t>(value_) >> IndexField::kShift;
424  }
425
426  int register_code() const {
427    DCHECK(IsRegister() || IsFPRegister());
428    return static_cast<int64_t>(value_) >> IndexField::kShift;
429  }
430
431  Register GetRegister() const {
432    DCHECK(IsRegister());
433    return Register::from_code(register_code());
434  }
435
436  FloatRegister GetFloatRegister() const {
437    DCHECK(IsFloatRegister());
438    return FloatRegister::from_code(register_code());
439  }
440
441  DoubleRegister GetDoubleRegister() const {
442    // On platforms where FloatRegister, DoubleRegister, and Simd128Register
443    // are all the same type, it's convenient to treat everything as a
444    // DoubleRegister, so be lax about type checking here.
445    DCHECK(IsFPRegister());
446    return DoubleRegister::from_code(register_code());
447  }
448
449  Simd128Register GetSimd128Register() const {
450    DCHECK(IsSimd128Register());
451    return Simd128Register::from_code(register_code());
452  }
453
454  LocationKind location_kind() const {
455    return LocationKindField::decode(value_);
456  }
457
458  MachineRepresentation representation() const {
459    return RepresentationField::decode(value_);
460  }
461
462  static bool IsSupportedRepresentation(MachineRepresentation rep) {
463    switch (rep) {
464      case MachineRepresentation::kWord32:
465      case MachineRepresentation::kWord64:
466      case MachineRepresentation::kFloat32:
467      case MachineRepresentation::kFloat64:
468      case MachineRepresentation::kSimd128:
469      case MachineRepresentation::kTagged:
470        return true;
471      case MachineRepresentation::kBit:
472      case MachineRepresentation::kWord8:
473      case MachineRepresentation::kWord16:
474      case MachineRepresentation::kNone:
475        return false;
476    }
477    UNREACHABLE();
478    return false;
479  }
480
481  static LocationOperand* cast(InstructionOperand* op) {
482    DCHECK(ALLOCATED == op->kind() || EXPLICIT == op->kind());
483    return static_cast<LocationOperand*>(op);
484  }
485
486  static const LocationOperand* cast(const InstructionOperand* op) {
487    DCHECK(ALLOCATED == op->kind() || EXPLICIT == op->kind());
488    return static_cast<const LocationOperand*>(op);
489  }
490
491  static LocationOperand cast(const InstructionOperand& op) {
492    DCHECK(ALLOCATED == op.kind() || EXPLICIT == op.kind());
493    return *static_cast<const LocationOperand*>(&op);
494  }
495
496  STATIC_ASSERT(KindField::kSize == 3);
497  class LocationKindField : public BitField64<LocationKind, 3, 2> {};
498  class RepresentationField : public BitField64<MachineRepresentation, 5, 8> {};
499  class IndexField : public BitField64<int32_t, 35, 29> {};
500};
501
502
503class ExplicitOperand : public LocationOperand {
504 public:
505  ExplicitOperand(LocationKind kind, MachineRepresentation rep, int index);
506
507  static ExplicitOperand* New(Zone* zone, LocationKind kind,
508                              MachineRepresentation rep, int index) {
509    return InstructionOperand::New(zone, ExplicitOperand(kind, rep, index));
510  }
511
512  INSTRUCTION_OPERAND_CASTS(ExplicitOperand, EXPLICIT);
513};
514
515
516class AllocatedOperand : public LocationOperand {
517 public:
518  AllocatedOperand(LocationKind kind, MachineRepresentation rep, int index)
519      : LocationOperand(ALLOCATED, kind, rep, index) {}
520
521  static AllocatedOperand* New(Zone* zone, LocationKind kind,
522                               MachineRepresentation rep, int index) {
523    return InstructionOperand::New(zone, AllocatedOperand(kind, rep, index));
524  }
525
526  INSTRUCTION_OPERAND_CASTS(AllocatedOperand, ALLOCATED);
527};
528
529
530#undef INSTRUCTION_OPERAND_CASTS
531
532
533bool InstructionOperand::IsAnyRegister() const {
534  return (IsAllocated() || IsExplicit()) &&
535         LocationOperand::cast(this)->location_kind() ==
536             LocationOperand::REGISTER;
537}
538
539
540bool InstructionOperand::IsRegister() const {
541  return IsAnyRegister() &&
542         !IsFloatingPoint(LocationOperand::cast(this)->representation());
543}
544
545bool InstructionOperand::IsFPRegister() const {
546  return IsAnyRegister() &&
547         IsFloatingPoint(LocationOperand::cast(this)->representation());
548}
549
550bool InstructionOperand::IsFloatRegister() const {
551  return IsAnyRegister() &&
552         LocationOperand::cast(this)->representation() ==
553             MachineRepresentation::kFloat32;
554}
555
556bool InstructionOperand::IsDoubleRegister() const {
557  return IsAnyRegister() &&
558         LocationOperand::cast(this)->representation() ==
559             MachineRepresentation::kFloat64;
560}
561
562bool InstructionOperand::IsSimd128Register() const {
563  return IsAnyRegister() &&
564         LocationOperand::cast(this)->representation() ==
565             MachineRepresentation::kSimd128;
566}
567
568bool InstructionOperand::IsStackSlot() const {
569  return (IsAllocated() || IsExplicit()) &&
570         LocationOperand::cast(this)->location_kind() ==
571             LocationOperand::STACK_SLOT &&
572         !IsFloatingPoint(LocationOperand::cast(this)->representation());
573}
574
575bool InstructionOperand::IsFPStackSlot() const {
576  return (IsAllocated() || IsExplicit()) &&
577         LocationOperand::cast(this)->location_kind() ==
578             LocationOperand::STACK_SLOT &&
579         IsFloatingPoint(LocationOperand::cast(this)->representation());
580}
581
582bool InstructionOperand::IsFloatStackSlot() const {
583  return (IsAllocated() || IsExplicit()) &&
584         LocationOperand::cast(this)->location_kind() ==
585             LocationOperand::STACK_SLOT &&
586         LocationOperand::cast(this)->representation() ==
587             MachineRepresentation::kFloat32;
588}
589
590bool InstructionOperand::IsDoubleStackSlot() const {
591  return (IsAllocated() || IsExplicit()) &&
592         LocationOperand::cast(this)->location_kind() ==
593             LocationOperand::STACK_SLOT &&
594         LocationOperand::cast(this)->representation() ==
595             MachineRepresentation::kFloat64;
596}
597
598bool InstructionOperand::IsSimd128StackSlot() const {
599  return (IsAllocated() || IsExplicit()) &&
600         LocationOperand::cast(this)->location_kind() ==
601             LocationOperand::STACK_SLOT &&
602         LocationOperand::cast(this)->representation() ==
603             MachineRepresentation::kSimd128;
604}
605
606uint64_t InstructionOperand::GetCanonicalizedValue() const {
607  if (IsAllocated() || IsExplicit()) {
608    MachineRepresentation rep = LocationOperand::cast(this)->representation();
609    MachineRepresentation canonical = MachineRepresentation::kNone;
610    if (IsFloatingPoint(rep)) {
611      if (kSimpleFPAliasing) {
612        // Archs with simple aliasing can treat all FP operands the same.
613        canonical = MachineRepresentation::kFloat64;
614      } else {
615        // We need to distinguish FP operands of different reps when FP
616        // aliasing is not simple (e.g. ARM).
617        canonical = rep;
618      }
619    }
620    return InstructionOperand::KindField::update(
621        LocationOperand::RepresentationField::update(this->value_, canonical),
622        LocationOperand::EXPLICIT);
623  }
624  return this->value_;
625}
626
627// Required for maps that don't care about machine type.
628struct CompareOperandModuloType {
629  bool operator()(const InstructionOperand& a,
630                  const InstructionOperand& b) const {
631    return a.CompareCanonicalized(b);
632  }
633};
634
635
636class MoveOperands final : public ZoneObject {
637 public:
638  MoveOperands(const InstructionOperand& source,
639               const InstructionOperand& destination)
640      : source_(source), destination_(destination) {
641    DCHECK(!source.IsInvalid() && !destination.IsInvalid());
642  }
643
644  const InstructionOperand& source() const { return source_; }
645  InstructionOperand& source() { return source_; }
646  void set_source(const InstructionOperand& operand) { source_ = operand; }
647
648  const InstructionOperand& destination() const { return destination_; }
649  InstructionOperand& destination() { return destination_; }
650  void set_destination(const InstructionOperand& operand) {
651    destination_ = operand;
652  }
653
654  // The gap resolver marks moves as "in-progress" by clearing the
655  // destination (but not the source).
656  bool IsPending() const {
657    return destination_.IsInvalid() && !source_.IsInvalid();
658  }
659  void SetPending() { destination_ = InstructionOperand(); }
660
661  // True if this move is a move into the given destination operand.
662  bool Blocks(const InstructionOperand& destination) const {
663    return !IsEliminated() && source().InterferesWith(destination);
664  }
665
666  // A move is redundant if it's been eliminated or if its source and
667  // destination are the same.
668  bool IsRedundant() const {
669    DCHECK_IMPLIES(!destination_.IsInvalid(), !destination_.IsConstant());
670    return IsEliminated() || source_.EqualsCanonicalized(destination_);
671  }
672
673  // We clear both operands to indicate move that's been eliminated.
674  void Eliminate() { source_ = destination_ = InstructionOperand(); }
675  bool IsEliminated() const {
676    DCHECK_IMPLIES(source_.IsInvalid(), destination_.IsInvalid());
677    return source_.IsInvalid();
678  }
679
680  void Print(const RegisterConfiguration* config) const;
681  void Print() const;
682
683 private:
684  InstructionOperand source_;
685  InstructionOperand destination_;
686
687  DISALLOW_COPY_AND_ASSIGN(MoveOperands);
688};
689
690
691struct PrintableMoveOperands {
692  const RegisterConfiguration* register_configuration_;
693  const MoveOperands* move_operands_;
694};
695
696
697std::ostream& operator<<(std::ostream& os, const PrintableMoveOperands& mo);
698
699
700class ParallelMove final : public ZoneVector<MoveOperands*>, public ZoneObject {
701 public:
702  explicit ParallelMove(Zone* zone) : ZoneVector<MoveOperands*>(zone) {
703    reserve(4);
704  }
705
706  MoveOperands* AddMove(const InstructionOperand& from,
707                        const InstructionOperand& to) {
708    Zone* zone = get_allocator().zone();
709    return AddMove(from, to, zone);
710  }
711
712  MoveOperands* AddMove(const InstructionOperand& from,
713                        const InstructionOperand& to,
714                        Zone* operand_allocation_zone) {
715    MoveOperands* move = new (operand_allocation_zone) MoveOperands(from, to);
716    push_back(move);
717    return move;
718  }
719
720  bool IsRedundant() const;
721
722  // Prepare this ParallelMove to insert move as if it happened in a subsequent
723  // ParallelMove.  move->source() may be changed.  The MoveOperand returned
724  // must be Eliminated.
725  MoveOperands* PrepareInsertAfter(MoveOperands* move) const;
726
727 private:
728  DISALLOW_COPY_AND_ASSIGN(ParallelMove);
729};
730
731
732struct PrintableParallelMove {
733  const RegisterConfiguration* register_configuration_;
734  const ParallelMove* parallel_move_;
735};
736
737
738std::ostream& operator<<(std::ostream& os, const PrintableParallelMove& pm);
739
740
741class ReferenceMap final : public ZoneObject {
742 public:
743  explicit ReferenceMap(Zone* zone)
744      : reference_operands_(8, zone), instruction_position_(-1) {}
745
746  const ZoneVector<InstructionOperand>& reference_operands() const {
747    return reference_operands_;
748  }
749  int instruction_position() const { return instruction_position_; }
750
751  void set_instruction_position(int pos) {
752    DCHECK(instruction_position_ == -1);
753    instruction_position_ = pos;
754  }
755
756  void RecordReference(const AllocatedOperand& op);
757
758 private:
759  friend std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm);
760
761  ZoneVector<InstructionOperand> reference_operands_;
762  int instruction_position_;
763};
764
765std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm);
766
767class InstructionBlock;
768
769class Instruction final {
770 public:
771  size_t OutputCount() const { return OutputCountField::decode(bit_field_); }
772  const InstructionOperand* OutputAt(size_t i) const {
773    DCHECK(i < OutputCount());
774    return &operands_[i];
775  }
776  InstructionOperand* OutputAt(size_t i) {
777    DCHECK(i < OutputCount());
778    return &operands_[i];
779  }
780
781  bool HasOutput() const { return OutputCount() == 1; }
782  const InstructionOperand* Output() const { return OutputAt(0); }
783  InstructionOperand* Output() { return OutputAt(0); }
784
785  size_t InputCount() const { return InputCountField::decode(bit_field_); }
786  const InstructionOperand* InputAt(size_t i) const {
787    DCHECK(i < InputCount());
788    return &operands_[OutputCount() + i];
789  }
790  InstructionOperand* InputAt(size_t i) {
791    DCHECK(i < InputCount());
792    return &operands_[OutputCount() + i];
793  }
794
795  size_t TempCount() const { return TempCountField::decode(bit_field_); }
796  const InstructionOperand* TempAt(size_t i) const {
797    DCHECK(i < TempCount());
798    return &operands_[OutputCount() + InputCount() + i];
799  }
800  InstructionOperand* TempAt(size_t i) {
801    DCHECK(i < TempCount());
802    return &operands_[OutputCount() + InputCount() + i];
803  }
804
805  InstructionCode opcode() const { return opcode_; }
806  ArchOpcode arch_opcode() const { return ArchOpcodeField::decode(opcode()); }
807  AddressingMode addressing_mode() const {
808    return AddressingModeField::decode(opcode());
809  }
810  FlagsMode flags_mode() const { return FlagsModeField::decode(opcode()); }
811  FlagsCondition flags_condition() const {
812    return FlagsConditionField::decode(opcode());
813  }
814
815  static Instruction* New(Zone* zone, InstructionCode opcode) {
816    return New(zone, opcode, 0, nullptr, 0, nullptr, 0, nullptr);
817  }
818
819  static Instruction* New(Zone* zone, InstructionCode opcode,
820                          size_t output_count, InstructionOperand* outputs,
821                          size_t input_count, InstructionOperand* inputs,
822                          size_t temp_count, InstructionOperand* temps) {
823    DCHECK(opcode >= 0);
824    DCHECK(output_count == 0 || outputs != nullptr);
825    DCHECK(input_count == 0 || inputs != nullptr);
826    DCHECK(temp_count == 0 || temps != nullptr);
827    // TODO(jarin/mstarzinger): Handle this gracefully. See crbug.com/582702.
828    CHECK(InputCountField::is_valid(input_count));
829
830    size_t total_extra_ops = output_count + input_count + temp_count;
831    if (total_extra_ops != 0) total_extra_ops--;
832    int size = static_cast<int>(
833        RoundUp(sizeof(Instruction), sizeof(InstructionOperand)) +
834        total_extra_ops * sizeof(InstructionOperand));
835    return new (zone->New(size)) Instruction(
836        opcode, output_count, outputs, input_count, inputs, temp_count, temps);
837  }
838
839  Instruction* MarkAsCall() {
840    bit_field_ = IsCallField::update(bit_field_, true);
841    return this;
842  }
843  bool IsCall() const { return IsCallField::decode(bit_field_); }
844  bool NeedsReferenceMap() const { return IsCall(); }
845  bool HasReferenceMap() const { return reference_map_ != nullptr; }
846
847  bool ClobbersRegisters() const { return IsCall(); }
848  bool ClobbersTemps() const { return IsCall(); }
849  bool ClobbersDoubleRegisters() const { return IsCall(); }
850  ReferenceMap* reference_map() const { return reference_map_; }
851
852  void set_reference_map(ReferenceMap* map) {
853    DCHECK(NeedsReferenceMap());
854    DCHECK(!reference_map_);
855    reference_map_ = map;
856  }
857
858  void OverwriteWithNop() {
859    opcode_ = ArchOpcodeField::encode(kArchNop);
860    bit_field_ = 0;
861    reference_map_ = nullptr;
862  }
863
864  bool IsNop() const {
865    return arch_opcode() == kArchNop && InputCount() == 0 &&
866           OutputCount() == 0 && TempCount() == 0;
867  }
868
869  bool IsDeoptimizeCall() const {
870    return arch_opcode() == ArchOpcode::kArchDeoptimize ||
871           FlagsModeField::decode(opcode()) == kFlags_deoptimize;
872  }
873
874  bool IsJump() const { return arch_opcode() == ArchOpcode::kArchJmp; }
875  bool IsRet() const { return arch_opcode() == ArchOpcode::kArchRet; }
876  bool IsTailCall() const {
877    return arch_opcode() == ArchOpcode::kArchTailCallCodeObject ||
878           arch_opcode() == ArchOpcode::kArchTailCallCodeObjectFromJSFunction ||
879           arch_opcode() == ArchOpcode::kArchTailCallJSFunction ||
880           arch_opcode() == ArchOpcode::kArchTailCallJSFunctionFromJSFunction ||
881           arch_opcode() == ArchOpcode::kArchTailCallAddress;
882  }
883  bool IsThrow() const {
884    return arch_opcode() == ArchOpcode::kArchThrowTerminator;
885  }
886
887  enum GapPosition {
888    START,
889    END,
890    FIRST_GAP_POSITION = START,
891    LAST_GAP_POSITION = END
892  };
893
894  ParallelMove* GetOrCreateParallelMove(GapPosition pos, Zone* zone) {
895    if (parallel_moves_[pos] == nullptr) {
896      parallel_moves_[pos] = new (zone) ParallelMove(zone);
897    }
898    return parallel_moves_[pos];
899  }
900
901  ParallelMove* GetParallelMove(GapPosition pos) {
902    return parallel_moves_[pos];
903  }
904
905  const ParallelMove* GetParallelMove(GapPosition pos) const {
906    return parallel_moves_[pos];
907  }
908
909  bool AreMovesRedundant() const;
910
911  ParallelMove* const* parallel_moves() const { return &parallel_moves_[0]; }
912  ParallelMove** parallel_moves() { return &parallel_moves_[0]; }
913
914  // The block_id may be invalidated in JumpThreading. It is only important for
915  // register allocation, to avoid searching for blocks from instruction
916  // indexes.
917  InstructionBlock* block() const { return block_; }
918  void set_block(InstructionBlock* block) {
919    DCHECK_NOT_NULL(block);
920    block_ = block;
921  }
922
923  void Print(const RegisterConfiguration* config) const;
924  void Print() const;
925
926 private:
927  explicit Instruction(InstructionCode opcode);
928
929  Instruction(InstructionCode opcode, size_t output_count,
930              InstructionOperand* outputs, size_t input_count,
931              InstructionOperand* inputs, size_t temp_count,
932              InstructionOperand* temps);
933
934  typedef BitField<size_t, 0, 8> OutputCountField;
935  typedef BitField<size_t, 8, 16> InputCountField;
936  typedef BitField<size_t, 24, 6> TempCountField;
937  typedef BitField<bool, 30, 1> IsCallField;
938
939  InstructionCode opcode_;
940  uint32_t bit_field_;
941  ParallelMove* parallel_moves_[2];
942  ReferenceMap* reference_map_;
943  InstructionBlock* block_;
944  InstructionOperand operands_[1];
945
946  DISALLOW_COPY_AND_ASSIGN(Instruction);
947};
948
949
950struct PrintableInstruction {
951  const RegisterConfiguration* register_configuration_;
952  const Instruction* instr_;
953};
954std::ostream& operator<<(std::ostream& os, const PrintableInstruction& instr);
955
956
957class RpoNumber final {
958 public:
959  static const int kInvalidRpoNumber = -1;
960  int ToInt() const {
961    DCHECK(IsValid());
962    return index_;
963  }
964  size_t ToSize() const {
965    DCHECK(IsValid());
966    return static_cast<size_t>(index_);
967  }
968  bool IsValid() const { return index_ >= 0; }
969  static RpoNumber FromInt(int index) { return RpoNumber(index); }
970  static RpoNumber Invalid() { return RpoNumber(kInvalidRpoNumber); }
971
972  bool IsNext(const RpoNumber other) const {
973    DCHECK(IsValid());
974    return other.index_ == this->index_ + 1;
975  }
976
977  // Comparison operators.
978  bool operator==(RpoNumber other) const { return index_ == other.index_; }
979  bool operator!=(RpoNumber other) const { return index_ != other.index_; }
980  bool operator>(RpoNumber other) const { return index_ > other.index_; }
981  bool operator<(RpoNumber other) const { return index_ < other.index_; }
982  bool operator<=(RpoNumber other) const { return index_ <= other.index_; }
983  bool operator>=(RpoNumber other) const { return index_ >= other.index_; }
984
985 private:
986  explicit RpoNumber(int32_t index) : index_(index) {}
987  int32_t index_;
988};
989
990
991std::ostream& operator<<(std::ostream&, const RpoNumber&);
992
993
994class Constant final {
995 public:
996  enum Type {
997    kInt32,
998    kInt64,
999    kFloat32,
1000    kFloat64,
1001    kExternalReference,
1002    kHeapObject,
1003    kRpoNumber
1004  };
1005
1006  explicit Constant(int32_t v);
1007  explicit Constant(int64_t v) : type_(kInt64), value_(v) {}
1008  explicit Constant(float v) : type_(kFloat32), value_(bit_cast<int32_t>(v)) {}
1009  explicit Constant(double v) : type_(kFloat64), value_(bit_cast<int64_t>(v)) {}
1010  explicit Constant(ExternalReference ref)
1011      : type_(kExternalReference), value_(bit_cast<intptr_t>(ref)) {}
1012  explicit Constant(Handle<HeapObject> obj)
1013      : type_(kHeapObject), value_(bit_cast<intptr_t>(obj)) {}
1014  explicit Constant(RpoNumber rpo) : type_(kRpoNumber), value_(rpo.ToInt()) {}
1015  explicit Constant(RelocatablePtrConstantInfo info);
1016
1017  Type type() const { return type_; }
1018
1019  RelocInfo::Mode rmode() const { return rmode_; }
1020
1021  int32_t ToInt32() const {
1022    DCHECK(type() == kInt32 || type() == kInt64);
1023    const int32_t value = static_cast<int32_t>(value_);
1024    DCHECK_EQ(value_, static_cast<int64_t>(value));
1025    return value;
1026  }
1027
1028  int64_t ToInt64() const {
1029    if (type() == kInt32) return ToInt32();
1030    DCHECK_EQ(kInt64, type());
1031    return value_;
1032  }
1033
1034  float ToFloat32() const {
1035    DCHECK_EQ(kFloat32, type());
1036    return bit_cast<float>(static_cast<int32_t>(value_));
1037  }
1038
1039  double ToFloat64() const {
1040    if (type() == kInt32) return ToInt32();
1041    DCHECK_EQ(kFloat64, type());
1042    return bit_cast<double>(value_);
1043  }
1044
1045  ExternalReference ToExternalReference() const {
1046    DCHECK_EQ(kExternalReference, type());
1047    return bit_cast<ExternalReference>(static_cast<intptr_t>(value_));
1048  }
1049
1050  RpoNumber ToRpoNumber() const {
1051    DCHECK_EQ(kRpoNumber, type());
1052    return RpoNumber::FromInt(static_cast<int>(value_));
1053  }
1054
1055  Handle<HeapObject> ToHeapObject() const;
1056
1057 private:
1058  Type type_;
1059  int64_t value_;
1060#if V8_TARGET_ARCH_32_BIT
1061  RelocInfo::Mode rmode_ = RelocInfo::NONE32;
1062#else
1063  RelocInfo::Mode rmode_ = RelocInfo::NONE64;
1064#endif
1065};
1066
1067
1068std::ostream& operator<<(std::ostream& os, const Constant& constant);
1069
1070
1071// Forward declarations.
1072class FrameStateDescriptor;
1073
1074
1075enum class StateValueKind { kPlain, kNested, kDuplicate };
1076
1077
1078class StateValueDescriptor {
1079 public:
1080  explicit StateValueDescriptor(Zone* zone)
1081      : kind_(StateValueKind::kPlain),
1082        type_(MachineType::AnyTagged()),
1083        id_(0),
1084        fields_(zone) {}
1085
1086  static StateValueDescriptor Plain(Zone* zone, MachineType type) {
1087    return StateValueDescriptor(StateValueKind::kPlain, zone, type, 0);
1088  }
1089  static StateValueDescriptor Recursive(Zone* zone, size_t id) {
1090    return StateValueDescriptor(StateValueKind::kNested, zone,
1091                                MachineType::AnyTagged(), id);
1092  }
1093  static StateValueDescriptor Duplicate(Zone* zone, size_t id) {
1094    return StateValueDescriptor(StateValueKind::kDuplicate, zone,
1095                                MachineType::AnyTagged(), id);
1096  }
1097
1098  size_t size() { return fields_.size(); }
1099  ZoneVector<StateValueDescriptor>& fields() { return fields_; }
1100  int IsPlain() { return kind_ == StateValueKind::kPlain; }
1101  int IsNested() { return kind_ == StateValueKind::kNested; }
1102  int IsDuplicate() { return kind_ == StateValueKind::kDuplicate; }
1103  MachineType type() const { return type_; }
1104  MachineType GetOperandType(size_t index) const {
1105    return fields_[index].type_;
1106  }
1107  size_t id() const { return id_; }
1108
1109 private:
1110  StateValueDescriptor(StateValueKind kind, Zone* zone, MachineType type,
1111                       size_t id)
1112      : kind_(kind), type_(type), id_(id), fields_(zone) {}
1113
1114  StateValueKind kind_;
1115  MachineType type_;
1116  size_t id_;
1117  ZoneVector<StateValueDescriptor> fields_;
1118};
1119
1120
1121class FrameStateDescriptor : public ZoneObject {
1122 public:
1123  FrameStateDescriptor(Zone* zone, FrameStateType type, BailoutId bailout_id,
1124                       OutputFrameStateCombine state_combine,
1125                       size_t parameters_count, size_t locals_count,
1126                       size_t stack_count,
1127                       MaybeHandle<SharedFunctionInfo> shared_info,
1128                       FrameStateDescriptor* outer_state = nullptr);
1129
1130  FrameStateType type() const { return type_; }
1131  BailoutId bailout_id() const { return bailout_id_; }
1132  OutputFrameStateCombine state_combine() const { return frame_state_combine_; }
1133  size_t parameters_count() const { return parameters_count_; }
1134  size_t locals_count() const { return locals_count_; }
1135  size_t stack_count() const { return stack_count_; }
1136  MaybeHandle<SharedFunctionInfo> shared_info() const { return shared_info_; }
1137  FrameStateDescriptor* outer_state() const { return outer_state_; }
1138  bool HasContext() const {
1139    return FrameStateFunctionInfo::IsJSFunctionType(type_);
1140  }
1141
1142  size_t GetSize(OutputFrameStateCombine combine =
1143                     OutputFrameStateCombine::Ignore()) const;
1144  size_t GetTotalSize() const;
1145  size_t GetFrameCount() const;
1146  size_t GetJSFrameCount() const;
1147
1148  MachineType GetType(size_t index) const {
1149    return values_.GetOperandType(index);
1150  }
1151  StateValueDescriptor* GetStateValueDescriptor() { return &values_; }
1152
1153 private:
1154  FrameStateType type_;
1155  BailoutId bailout_id_;
1156  OutputFrameStateCombine frame_state_combine_;
1157  size_t parameters_count_;
1158  size_t locals_count_;
1159  size_t stack_count_;
1160  StateValueDescriptor values_;
1161  MaybeHandle<SharedFunctionInfo> const shared_info_;
1162  FrameStateDescriptor* outer_state_;
1163};
1164
1165
1166typedef ZoneVector<FrameStateDescriptor*> DeoptimizationVector;
1167
1168
1169class PhiInstruction final : public ZoneObject {
1170 public:
1171  typedef ZoneVector<InstructionOperand> Inputs;
1172
1173  PhiInstruction(Zone* zone, int virtual_register, size_t input_count);
1174
1175  void SetInput(size_t offset, int virtual_register);
1176
1177  int virtual_register() const { return virtual_register_; }
1178  const IntVector& operands() const { return operands_; }
1179
1180  // TODO(dcarney): this has no real business being here, since it's internal to
1181  // the register allocator, but putting it here was convenient.
1182  const InstructionOperand& output() const { return output_; }
1183  InstructionOperand& output() { return output_; }
1184
1185 private:
1186  const int virtual_register_;
1187  InstructionOperand output_;
1188  IntVector operands_;
1189};
1190
1191
1192// Analogue of BasicBlock for Instructions instead of Nodes.
1193class InstructionBlock final : public ZoneObject {
1194 public:
1195  InstructionBlock(Zone* zone, RpoNumber rpo_number, RpoNumber loop_header,
1196                   RpoNumber loop_end, bool deferred, bool handler);
1197
1198  // Instruction indexes (used by the register allocator).
1199  int first_instruction_index() const {
1200    DCHECK(code_start_ >= 0);
1201    DCHECK(code_end_ > 0);
1202    DCHECK(code_end_ >= code_start_);
1203    return code_start_;
1204  }
1205  int last_instruction_index() const {
1206    DCHECK(code_start_ >= 0);
1207    DCHECK(code_end_ > 0);
1208    DCHECK(code_end_ >= code_start_);
1209    return code_end_ - 1;
1210  }
1211
1212  int32_t code_start() const { return code_start_; }
1213  void set_code_start(int32_t start) { code_start_ = start; }
1214
1215  int32_t code_end() const { return code_end_; }
1216  void set_code_end(int32_t end) { code_end_ = end; }
1217
1218  bool IsDeferred() const { return deferred_; }
1219  bool IsHandler() const { return handler_; }
1220
1221  RpoNumber ao_number() const { return ao_number_; }
1222  RpoNumber rpo_number() const { return rpo_number_; }
1223  RpoNumber loop_header() const { return loop_header_; }
1224  RpoNumber loop_end() const {
1225    DCHECK(IsLoopHeader());
1226    return loop_end_;
1227  }
1228  inline bool IsLoopHeader() const { return loop_end_.IsValid(); }
1229
1230  typedef ZoneVector<RpoNumber> Predecessors;
1231  Predecessors& predecessors() { return predecessors_; }
1232  const Predecessors& predecessors() const { return predecessors_; }
1233  size_t PredecessorCount() const { return predecessors_.size(); }
1234  size_t PredecessorIndexOf(RpoNumber rpo_number) const;
1235
1236  typedef ZoneVector<RpoNumber> Successors;
1237  Successors& successors() { return successors_; }
1238  const Successors& successors() const { return successors_; }
1239  size_t SuccessorCount() const { return successors_.size(); }
1240
1241  typedef ZoneVector<PhiInstruction*> PhiInstructions;
1242  const PhiInstructions& phis() const { return phis_; }
1243  void AddPhi(PhiInstruction* phi) { phis_.push_back(phi); }
1244
1245  void set_ao_number(RpoNumber ao_number) { ao_number_ = ao_number; }
1246
1247  bool needs_frame() const { return needs_frame_; }
1248  void mark_needs_frame() { needs_frame_ = true; }
1249
1250  bool must_construct_frame() const { return must_construct_frame_; }
1251  void mark_must_construct_frame() { must_construct_frame_ = true; }
1252
1253  bool must_deconstruct_frame() const { return must_deconstruct_frame_; }
1254  void mark_must_deconstruct_frame() { must_deconstruct_frame_ = true; }
1255
1256  void set_last_deferred(RpoNumber last) { last_deferred_ = last; }
1257  RpoNumber last_deferred() const { return last_deferred_; }
1258
1259 private:
1260  Successors successors_;
1261  Predecessors predecessors_;
1262  PhiInstructions phis_;
1263  RpoNumber ao_number_;  // Assembly order number.
1264  const RpoNumber rpo_number_;
1265  const RpoNumber loop_header_;
1266  const RpoNumber loop_end_;
1267  int32_t code_start_;   // start index of arch-specific code.
1268  int32_t code_end_;     // end index of arch-specific code.
1269  const bool deferred_;  // Block contains deferred code.
1270  const bool handler_;   // Block is a handler entry point.
1271  bool needs_frame_;
1272  bool must_construct_frame_;
1273  bool must_deconstruct_frame_;
1274  RpoNumber last_deferred_;
1275};
1276
1277typedef ZoneDeque<Constant> ConstantDeque;
1278typedef std::map<int, Constant, std::less<int>,
1279                 zone_allocator<std::pair<const int, Constant> > > ConstantMap;
1280
1281typedef ZoneDeque<Instruction*> InstructionDeque;
1282typedef ZoneDeque<ReferenceMap*> ReferenceMapDeque;
1283typedef ZoneVector<InstructionBlock*> InstructionBlocks;
1284
1285
1286// Forward declarations.
1287struct PrintableInstructionSequence;
1288
1289
1290// Represents architecture-specific generated code before, during, and after
1291// register allocation.
1292class InstructionSequence final : public ZoneObject {
1293 public:
1294  static InstructionBlocks* InstructionBlocksFor(Zone* zone,
1295                                                 const Schedule* schedule);
1296  // Puts the deferred blocks last.
1297  static void ComputeAssemblyOrder(InstructionBlocks* blocks);
1298
1299  InstructionSequence(Isolate* isolate, Zone* zone,
1300                      InstructionBlocks* instruction_blocks);
1301
1302  int NextVirtualRegister();
1303  int VirtualRegisterCount() const { return next_virtual_register_; }
1304
1305  const InstructionBlocks& instruction_blocks() const {
1306    return *instruction_blocks_;
1307  }
1308
1309  int InstructionBlockCount() const {
1310    return static_cast<int>(instruction_blocks_->size());
1311  }
1312
1313  InstructionBlock* InstructionBlockAt(RpoNumber rpo_number) {
1314    return instruction_blocks_->at(rpo_number.ToSize());
1315  }
1316
1317  int LastLoopInstructionIndex(const InstructionBlock* block) {
1318    return instruction_blocks_->at(block->loop_end().ToSize() - 1)
1319        ->last_instruction_index();
1320  }
1321
1322  const InstructionBlock* InstructionBlockAt(RpoNumber rpo_number) const {
1323    return instruction_blocks_->at(rpo_number.ToSize());
1324  }
1325
1326  InstructionBlock* GetInstructionBlock(int instruction_index) const;
1327
1328  static MachineRepresentation DefaultRepresentation() {
1329    return MachineType::PointerRepresentation();
1330  }
1331  MachineRepresentation GetRepresentation(int virtual_register) const;
1332  void MarkAsRepresentation(MachineRepresentation rep, int virtual_register);
1333
1334  bool IsReference(int virtual_register) const {
1335    return GetRepresentation(virtual_register) ==
1336           MachineRepresentation::kTagged;
1337  }
1338  bool IsFP(int virtual_register) const {
1339    return IsFloatingPoint(GetRepresentation(virtual_register));
1340  }
1341  bool IsFloat(int virtual_register) const {
1342    return GetRepresentation(virtual_register) ==
1343           MachineRepresentation::kFloat32;
1344  }
1345  bool IsDouble(int virtual_register) const {
1346    return GetRepresentation(virtual_register) ==
1347           MachineRepresentation::kFloat64;
1348  }
1349
1350  Instruction* GetBlockStart(RpoNumber rpo) const;
1351
1352  typedef InstructionDeque::const_iterator const_iterator;
1353  const_iterator begin() const { return instructions_.begin(); }
1354  const_iterator end() const { return instructions_.end(); }
1355  const InstructionDeque& instructions() const { return instructions_; }
1356  int LastInstructionIndex() const {
1357    return static_cast<int>(instructions().size()) - 1;
1358  }
1359
1360  Instruction* InstructionAt(int index) const {
1361    DCHECK(index >= 0);
1362    DCHECK(index < static_cast<int>(instructions_.size()));
1363    return instructions_[index];
1364  }
1365
1366  Isolate* isolate() const { return isolate_; }
1367  const ReferenceMapDeque* reference_maps() const { return &reference_maps_; }
1368  Zone* zone() const { return zone_; }
1369
1370  // Used by the instruction selector while adding instructions.
1371  int AddInstruction(Instruction* instr);
1372  void StartBlock(RpoNumber rpo);
1373  void EndBlock(RpoNumber rpo);
1374
1375  int AddConstant(int virtual_register, Constant constant) {
1376    // TODO(titzer): allow RPO numbers as constants?
1377    DCHECK(constant.type() != Constant::kRpoNumber);
1378    DCHECK(virtual_register >= 0 && virtual_register < next_virtual_register_);
1379    DCHECK(constants_.find(virtual_register) == constants_.end());
1380    constants_.insert(std::make_pair(virtual_register, constant));
1381    return virtual_register;
1382  }
1383  Constant GetConstant(int virtual_register) const {
1384    ConstantMap::const_iterator it = constants_.find(virtual_register);
1385    DCHECK(it != constants_.end());
1386    DCHECK_EQ(virtual_register, it->first);
1387    return it->second;
1388  }
1389
1390  typedef ZoneVector<Constant> Immediates;
1391  Immediates& immediates() { return immediates_; }
1392
1393  ImmediateOperand AddImmediate(const Constant& constant) {
1394    if (constant.type() == Constant::kInt32 &&
1395        RelocInfo::IsNone(constant.rmode())) {
1396      return ImmediateOperand(ImmediateOperand::INLINE, constant.ToInt32());
1397    }
1398    int index = static_cast<int>(immediates_.size());
1399    immediates_.push_back(constant);
1400    return ImmediateOperand(ImmediateOperand::INDEXED, index);
1401  }
1402
1403  Constant GetImmediate(const ImmediateOperand* op) const {
1404    switch (op->type()) {
1405      case ImmediateOperand::INLINE:
1406        return Constant(op->inline_value());
1407      case ImmediateOperand::INDEXED: {
1408        int index = op->indexed_value();
1409        DCHECK(index >= 0);
1410        DCHECK(index < static_cast<int>(immediates_.size()));
1411        return immediates_[index];
1412      }
1413    }
1414    UNREACHABLE();
1415    return Constant(static_cast<int32_t>(0));
1416  }
1417
1418  class StateId {
1419   public:
1420    static StateId FromInt(int id) { return StateId(id); }
1421    int ToInt() const { return id_; }
1422
1423   private:
1424    explicit StateId(int id) : id_(id) {}
1425    int id_;
1426  };
1427
1428  StateId AddFrameStateDescriptor(FrameStateDescriptor* descriptor);
1429  FrameStateDescriptor* GetFrameStateDescriptor(StateId deoptimization_id);
1430  int GetFrameStateDescriptorCount();
1431  DeoptimizationVector const& frame_state_descriptors() const {
1432    return deoptimization_entries_;
1433  }
1434
1435  RpoNumber InputRpo(Instruction* instr, size_t index);
1436
1437  bool GetSourcePosition(const Instruction* instr,
1438                         SourcePosition* result) const;
1439  void SetSourcePosition(const Instruction* instr, SourcePosition value);
1440
1441  bool ContainsCall() const {
1442    for (Instruction* instr : instructions_) {
1443      if (instr->IsCall()) return true;
1444    }
1445    return false;
1446  }
1447  void Print(const RegisterConfiguration* config) const;
1448  void Print() const;
1449
1450  void PrintBlock(const RegisterConfiguration* config, int block_id) const;
1451  void PrintBlock(int block_id) const;
1452
1453  void ValidateEdgeSplitForm() const;
1454  void ValidateDeferredBlockExitPaths() const;
1455  void ValidateDeferredBlockEntryPaths() const;
1456  void ValidateSSA() const;
1457
1458 private:
1459  friend std::ostream& operator<<(std::ostream& os,
1460                                  const PrintableInstructionSequence& code);
1461
1462  typedef ZoneMap<const Instruction*, SourcePosition> SourcePositionMap;
1463
1464  Isolate* isolate_;
1465  Zone* const zone_;
1466  InstructionBlocks* const instruction_blocks_;
1467  SourcePositionMap source_positions_;
1468  ConstantMap constants_;
1469  Immediates immediates_;
1470  InstructionDeque instructions_;
1471  int next_virtual_register_;
1472  ReferenceMapDeque reference_maps_;
1473  ZoneVector<MachineRepresentation> representations_;
1474  DeoptimizationVector deoptimization_entries_;
1475
1476  // Used at construction time
1477  InstructionBlock* current_block_;
1478
1479  DISALLOW_COPY_AND_ASSIGN(InstructionSequence);
1480};
1481
1482
1483struct PrintableInstructionSequence {
1484  const RegisterConfiguration* register_configuration_;
1485  const InstructionSequence* sequence_;
1486};
1487
1488
1489std::ostream& operator<<(std::ostream& os,
1490                         const PrintableInstructionSequence& code);
1491
1492}  // namespace compiler
1493}  // namespace internal
1494}  // namespace v8
1495
1496#endif  // V8_COMPILER_INSTRUCTION_H_
1497