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