Home | History | Annotate | Download | only in compiler 
      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 
     22 namespace v8 {
     23 namespace internal {
     24 namespace compiler {
     25 
     26 // Forward declarations.
     27 class Schedule;
     28 
     29 
     30 class 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 
    122 typedef ZoneVector<InstructionOperand> InstructionOperandVector;
    123 
    124 
    125 struct PrintableInstructionOperand {
    126   const RegisterConfiguration* register_configuration_;
    127   InstructionOperand op_;
    128 };
    129 
    130 
    131 std::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 
    152 class 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 
    349 class 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 
    372 class 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 
    406 class 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 
    503 class 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 
    516 class 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 
    533 bool InstructionOperand::IsAnyRegister() const {
    534   return (IsAllocated() || IsExplicit()) &&
    535          LocationOperand::cast(this)->location_kind() ==
    536              LocationOperand::REGISTER;
    537 }
    538 
    539 
    540 bool InstructionOperand::IsRegister() const {
    541   return IsAnyRegister() &&
    542          !IsFloatingPoint(LocationOperand::cast(this)->representation());
    543 }
    544 
    545 bool InstructionOperand::IsFPRegister() const {
    546   return IsAnyRegister() &&
    547          IsFloatingPoint(LocationOperand::cast(this)->representation());
    548 }
    549 
    550 bool InstructionOperand::IsFloatRegister() const {
    551   return IsAnyRegister() &&
    552          LocationOperand::cast(this)->representation() ==
    553              MachineRepresentation::kFloat32;
    554 }
    555 
    556 bool InstructionOperand::IsDoubleRegister() const {
    557   return IsAnyRegister() &&
    558          LocationOperand::cast(this)->representation() ==
    559              MachineRepresentation::kFloat64;
    560 }
    561 
    562 bool InstructionOperand::IsSimd128Register() const {
    563   return IsAnyRegister() &&
    564          LocationOperand::cast(this)->representation() ==
    565              MachineRepresentation::kSimd128;
    566 }
    567 
    568 bool 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 
    575 bool 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 
    582 bool 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 
    590 bool 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 
    598 bool 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 
    606 uint64_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.
    628 struct CompareOperandModuloType {
    629   bool operator()(const InstructionOperand& a,
    630                   const InstructionOperand& b) const {
    631     return a.CompareCanonicalized(b);
    632   }
    633 };
    634 
    635 
    636 class 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 
    691 struct PrintableMoveOperands {
    692   const RegisterConfiguration* register_configuration_;
    693   const MoveOperands* move_operands_;
    694 };
    695 
    696 
    697 std::ostream& operator<<(std::ostream& os, const PrintableMoveOperands& mo);
    698 
    699 
    700 class 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 
    732 struct PrintableParallelMove {
    733   const RegisterConfiguration* register_configuration_;
    734   const ParallelMove* parallel_move_;
    735 };
    736 
    737 
    738 std::ostream& operator<<(std::ostream& os, const PrintableParallelMove& pm);
    739 
    740 
    741 class 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 
    765 std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm);
    766 
    767 class InstructionBlock;
    768 
    769 class 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 
    950 struct PrintableInstruction {
    951   const RegisterConfiguration* register_configuration_;
    952   const Instruction* instr_;
    953 };
    954 std::ostream& operator<<(std::ostream& os, const PrintableInstruction& instr);
    955 
    956 
    957 class 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 
    991 std::ostream& operator<<(std::ostream&, const RpoNumber&);
    992 
    993 
    994 class 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 
   1068 std::ostream& operator<<(std::ostream& os, const Constant& constant);
   1069 
   1070 
   1071 // Forward declarations.
   1072 class FrameStateDescriptor;
   1073 
   1074 
   1075 enum class StateValueKind { kPlain, kNested, kDuplicate };
   1076 
   1077 
   1078 class 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 
   1121 class 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 
   1166 typedef ZoneVector<FrameStateDescriptor*> DeoptimizationVector;
   1167 
   1168 
   1169 class 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.
   1193 class 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 
   1277 typedef ZoneDeque<Constant> ConstantDeque;
   1278 typedef std::map<int, Constant, std::less<int>,
   1279                  zone_allocator<std::pair<const int, Constant> > > ConstantMap;
   1280 
   1281 typedef ZoneDeque<Instruction*> InstructionDeque;
   1282 typedef ZoneDeque<ReferenceMap*> ReferenceMapDeque;
   1283 typedef ZoneVector<InstructionBlock*> InstructionBlocks;
   1284 
   1285 
   1286 // Forward declarations.
   1287 struct PrintableInstructionSequence;
   1288 
   1289 
   1290 // Represents architecture-specific generated code before, during, and after
   1291 // register allocation.
   1292 class 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 
   1483 struct PrintableInstructionSequence {
   1484   const RegisterConfiguration* register_configuration_;
   1485   const InstructionSequence* sequence_;
   1486 };
   1487 
   1488 
   1489 std::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