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