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 <map>
     10 #include <set>
     11 
     12 #include "src/compiler/common-operator.h"
     13 #include "src/compiler/frame.h"
     14 #include "src/compiler/graph.h"
     15 #include "src/compiler/instruction-codes.h"
     16 #include "src/compiler/opcodes.h"
     17 #include "src/compiler/schedule.h"
     18 // TODO(titzer): don't include the macro-assembler?
     19 #include "src/macro-assembler.h"
     20 #include "src/zone-allocator.h"
     21 
     22 namespace v8 {
     23 namespace internal {
     24 
     25 // Forward declarations.
     26 class OStream;
     27 
     28 namespace compiler {
     29 
     30 // Forward declarations.
     31 class Linkage;
     32 
     33 // A couple of reserved opcodes are used for internal use.
     34 const InstructionCode kGapInstruction = -1;
     35 const InstructionCode kBlockStartInstruction = -2;
     36 const InstructionCode kSourcePositionInstruction = -3;
     37 
     38 
     39 #define INSTRUCTION_OPERAND_LIST(V)              \
     40   V(Constant, CONSTANT, 128)                     \
     41   V(Immediate, IMMEDIATE, 128)                   \
     42   V(StackSlot, STACK_SLOT, 128)                  \
     43   V(DoubleStackSlot, DOUBLE_STACK_SLOT, 128)     \
     44   V(Register, REGISTER, Register::kNumRegisters) \
     45   V(DoubleRegister, DOUBLE_REGISTER, DoubleRegister::kMaxNumRegisters)
     46 
     47 class InstructionOperand : public ZoneObject {
     48  public:
     49   enum Kind {
     50     INVALID,
     51     UNALLOCATED,
     52     CONSTANT,
     53     IMMEDIATE,
     54     STACK_SLOT,
     55     DOUBLE_STACK_SLOT,
     56     REGISTER,
     57     DOUBLE_REGISTER
     58   };
     59 
     60   InstructionOperand() : value_(KindField::encode(INVALID)) {}
     61   InstructionOperand(Kind kind, int index) { ConvertTo(kind, index); }
     62 
     63   Kind kind() const { return KindField::decode(value_); }
     64   int index() const { return static_cast<int>(value_) >> KindField::kSize; }
     65 #define INSTRUCTION_OPERAND_PREDICATE(name, type, number) \
     66   bool Is##name() const { return kind() == type; }
     67   INSTRUCTION_OPERAND_LIST(INSTRUCTION_OPERAND_PREDICATE)
     68   INSTRUCTION_OPERAND_PREDICATE(Unallocated, UNALLOCATED, 0)
     69   INSTRUCTION_OPERAND_PREDICATE(Ignored, INVALID, 0)
     70 #undef INSTRUCTION_OPERAND_PREDICATE
     71   bool Equals(InstructionOperand* other) const {
     72     return value_ == other->value_;
     73   }
     74 
     75   void ConvertTo(Kind kind, int index) {
     76     if (kind == REGISTER || kind == DOUBLE_REGISTER) DCHECK(index >= 0);
     77     value_ = KindField::encode(kind);
     78     value_ |= index << KindField::kSize;
     79     DCHECK(this->index() == index);
     80   }
     81 
     82   // Calls SetUpCache()/TearDownCache() for each subclass.
     83   static void SetUpCaches();
     84   static void TearDownCaches();
     85 
     86  protected:
     87   typedef BitField<Kind, 0, 3> KindField;
     88 
     89   unsigned value_;
     90 };
     91 
     92 typedef ZoneVector<InstructionOperand*> InstructionOperandVector;
     93 
     94 OStream& operator<<(OStream& os, const InstructionOperand& op);
     95 
     96 class UnallocatedOperand : public InstructionOperand {
     97  public:
     98   enum BasicPolicy { FIXED_SLOT, EXTENDED_POLICY };
     99 
    100   enum ExtendedPolicy {
    101     NONE,
    102     ANY,
    103     FIXED_REGISTER,
    104     FIXED_DOUBLE_REGISTER,
    105     MUST_HAVE_REGISTER,
    106     SAME_AS_FIRST_INPUT
    107   };
    108 
    109   // Lifetime of operand inside the instruction.
    110   enum Lifetime {
    111     // USED_AT_START operand is guaranteed to be live only at
    112     // instruction start. Register allocator is free to assign the same register
    113     // to some other operand used inside instruction (i.e. temporary or
    114     // output).
    115     USED_AT_START,
    116 
    117     // USED_AT_END operand is treated as live until the end of
    118     // instruction. This means that register allocator will not reuse it's
    119     // register for any other operand inside instruction.
    120     USED_AT_END
    121   };
    122 
    123   explicit UnallocatedOperand(ExtendedPolicy policy)
    124       : InstructionOperand(UNALLOCATED, 0) {
    125     value_ |= BasicPolicyField::encode(EXTENDED_POLICY);
    126     value_ |= ExtendedPolicyField::encode(policy);
    127     value_ |= LifetimeField::encode(USED_AT_END);
    128   }
    129 
    130   UnallocatedOperand(BasicPolicy policy, int index)
    131       : InstructionOperand(UNALLOCATED, 0) {
    132     DCHECK(policy == FIXED_SLOT);
    133     value_ |= BasicPolicyField::encode(policy);
    134     value_ |= index << FixedSlotIndexField::kShift;
    135     DCHECK(this->fixed_slot_index() == index);
    136   }
    137 
    138   UnallocatedOperand(ExtendedPolicy policy, int index)
    139       : InstructionOperand(UNALLOCATED, 0) {
    140     DCHECK(policy == FIXED_REGISTER || policy == FIXED_DOUBLE_REGISTER);
    141     value_ |= BasicPolicyField::encode(EXTENDED_POLICY);
    142     value_ |= ExtendedPolicyField::encode(policy);
    143     value_ |= LifetimeField::encode(USED_AT_END);
    144     value_ |= FixedRegisterField::encode(index);
    145   }
    146 
    147   UnallocatedOperand(ExtendedPolicy policy, Lifetime lifetime)
    148       : InstructionOperand(UNALLOCATED, 0) {
    149     value_ |= BasicPolicyField::encode(EXTENDED_POLICY);
    150     value_ |= ExtendedPolicyField::encode(policy);
    151     value_ |= LifetimeField::encode(lifetime);
    152   }
    153 
    154   UnallocatedOperand* CopyUnconstrained(Zone* zone) {
    155     UnallocatedOperand* result = new (zone) UnallocatedOperand(ANY);
    156     result->set_virtual_register(virtual_register());
    157     return result;
    158   }
    159 
    160   static const UnallocatedOperand* cast(const InstructionOperand* op) {
    161     DCHECK(op->IsUnallocated());
    162     return static_cast<const UnallocatedOperand*>(op);
    163   }
    164 
    165   static UnallocatedOperand* cast(InstructionOperand* op) {
    166     DCHECK(op->IsUnallocated());
    167     return static_cast<UnallocatedOperand*>(op);
    168   }
    169 
    170   // The encoding used for UnallocatedOperand operands depends on the policy
    171   // that is
    172   // stored within the operand. The FIXED_SLOT policy uses a compact encoding
    173   // because it accommodates a larger pay-load.
    174   //
    175   // For FIXED_SLOT policy:
    176   //     +------------------------------------------+
    177   //     |       slot_index      |  vreg  | 0 | 001 |
    178   //     +------------------------------------------+
    179   //
    180   // For all other (extended) policies:
    181   //     +------------------------------------------+
    182   //     |  reg_index  | L | PPP |  vreg  | 1 | 001 |    L ... Lifetime
    183   //     +------------------------------------------+    P ... Policy
    184   //
    185   // The slot index is a signed value which requires us to decode it manually
    186   // instead of using the BitField utility class.
    187 
    188   // The superclass has a KindField.
    189   STATIC_ASSERT(KindField::kSize == 3);
    190 
    191   // BitFields for all unallocated operands.
    192   class BasicPolicyField : public BitField<BasicPolicy, 3, 1> {};
    193   class VirtualRegisterField : public BitField<unsigned, 4, 18> {};
    194 
    195   // BitFields specific to BasicPolicy::FIXED_SLOT.
    196   class FixedSlotIndexField : public BitField<int, 22, 10> {};
    197 
    198   // BitFields specific to BasicPolicy::EXTENDED_POLICY.
    199   class ExtendedPolicyField : public BitField<ExtendedPolicy, 22, 3> {};
    200   class LifetimeField : public BitField<Lifetime, 25, 1> {};
    201   class FixedRegisterField : public BitField<int, 26, 6> {};
    202 
    203   static const int kMaxVirtualRegisters = VirtualRegisterField::kMax + 1;
    204   static const int kFixedSlotIndexWidth = FixedSlotIndexField::kSize;
    205   static const int kMaxFixedSlotIndex = (1 << (kFixedSlotIndexWidth - 1)) - 1;
    206   static const int kMinFixedSlotIndex = -(1 << (kFixedSlotIndexWidth - 1));
    207 
    208   // Predicates for the operand policy.
    209   bool HasAnyPolicy() const {
    210     return basic_policy() == EXTENDED_POLICY && extended_policy() == ANY;
    211   }
    212   bool HasFixedPolicy() const {
    213     return basic_policy() == FIXED_SLOT ||
    214            extended_policy() == FIXED_REGISTER ||
    215            extended_policy() == FIXED_DOUBLE_REGISTER;
    216   }
    217   bool HasRegisterPolicy() const {
    218     return basic_policy() == EXTENDED_POLICY &&
    219            extended_policy() == MUST_HAVE_REGISTER;
    220   }
    221   bool HasSameAsInputPolicy() const {
    222     return basic_policy() == EXTENDED_POLICY &&
    223            extended_policy() == SAME_AS_FIRST_INPUT;
    224   }
    225   bool HasFixedSlotPolicy() const { return basic_policy() == FIXED_SLOT; }
    226   bool HasFixedRegisterPolicy() const {
    227     return basic_policy() == EXTENDED_POLICY &&
    228            extended_policy() == FIXED_REGISTER;
    229   }
    230   bool HasFixedDoubleRegisterPolicy() const {
    231     return basic_policy() == EXTENDED_POLICY &&
    232            extended_policy() == FIXED_DOUBLE_REGISTER;
    233   }
    234 
    235   // [basic_policy]: Distinguish between FIXED_SLOT and all other policies.
    236   BasicPolicy basic_policy() const { return BasicPolicyField::decode(value_); }
    237 
    238   // [extended_policy]: Only for non-FIXED_SLOT. The finer-grained policy.
    239   ExtendedPolicy extended_policy() const {
    240     DCHECK(basic_policy() == EXTENDED_POLICY);
    241     return ExtendedPolicyField::decode(value_);
    242   }
    243 
    244   // [fixed_slot_index]: Only for FIXED_SLOT.
    245   int fixed_slot_index() const {
    246     DCHECK(HasFixedSlotPolicy());
    247     return static_cast<int>(value_) >> FixedSlotIndexField::kShift;
    248   }
    249 
    250   // [fixed_register_index]: Only for FIXED_REGISTER or FIXED_DOUBLE_REGISTER.
    251   int fixed_register_index() const {
    252     DCHECK(HasFixedRegisterPolicy() || HasFixedDoubleRegisterPolicy());
    253     return FixedRegisterField::decode(value_);
    254   }
    255 
    256   // [virtual_register]: The virtual register ID for this operand.
    257   int virtual_register() const { return VirtualRegisterField::decode(value_); }
    258   void set_virtual_register(unsigned id) {
    259     value_ = VirtualRegisterField::update(value_, id);
    260   }
    261 
    262   // [lifetime]: Only for non-FIXED_SLOT.
    263   bool IsUsedAtStart() {
    264     DCHECK(basic_policy() == EXTENDED_POLICY);
    265     return LifetimeField::decode(value_) == USED_AT_START;
    266   }
    267 };
    268 
    269 
    270 class MoveOperands FINAL {
    271  public:
    272   MoveOperands(InstructionOperand* source, InstructionOperand* destination)
    273       : source_(source), destination_(destination) {}
    274 
    275   InstructionOperand* source() const { return source_; }
    276   void set_source(InstructionOperand* operand) { source_ = operand; }
    277 
    278   InstructionOperand* destination() const { return destination_; }
    279   void set_destination(InstructionOperand* operand) { destination_ = operand; }
    280 
    281   // The gap resolver marks moves as "in-progress" by clearing the
    282   // destination (but not the source).
    283   bool IsPending() const { return destination_ == NULL && source_ != NULL; }
    284 
    285   // True if this move a move into the given destination operand.
    286   bool Blocks(InstructionOperand* operand) const {
    287     return !IsEliminated() && source()->Equals(operand);
    288   }
    289 
    290   // A move is redundant if it's been eliminated, if its source and
    291   // destination are the same, or if its destination is unneeded or constant.
    292   bool IsRedundant() const {
    293     return IsEliminated() || source_->Equals(destination_) || IsIgnored() ||
    294            (destination_ != NULL && destination_->IsConstant());
    295   }
    296 
    297   bool IsIgnored() const {
    298     return destination_ != NULL && destination_->IsIgnored();
    299   }
    300 
    301   // We clear both operands to indicate move that's been eliminated.
    302   void Eliminate() { source_ = destination_ = NULL; }
    303   bool IsEliminated() const {
    304     DCHECK(source_ != NULL || destination_ == NULL);
    305     return source_ == NULL;
    306   }
    307 
    308  private:
    309   InstructionOperand* source_;
    310   InstructionOperand* destination_;
    311 };
    312 
    313 OStream& operator<<(OStream& os, const MoveOperands& mo);
    314 
    315 template <InstructionOperand::Kind kOperandKind, int kNumCachedOperands>
    316 class SubKindOperand FINAL : public InstructionOperand {
    317  public:
    318   static SubKindOperand* Create(int index, Zone* zone) {
    319     DCHECK(index >= 0);
    320     if (index < kNumCachedOperands) return &cache[index];
    321     return new (zone) SubKindOperand(index);
    322   }
    323 
    324   static SubKindOperand* cast(InstructionOperand* op) {
    325     DCHECK(op->kind() == kOperandKind);
    326     return reinterpret_cast<SubKindOperand*>(op);
    327   }
    328 
    329   static void SetUpCache();
    330   static void TearDownCache();
    331 
    332  private:
    333   static SubKindOperand* cache;
    334 
    335   SubKindOperand() : InstructionOperand() {}
    336   explicit SubKindOperand(int index)
    337       : InstructionOperand(kOperandKind, index) {}
    338 };
    339 
    340 
    341 #define INSTRUCTION_TYPEDEF_SUBKIND_OPERAND_CLASS(name, type, number) \
    342   typedef SubKindOperand<InstructionOperand::type, number> name##Operand;
    343 INSTRUCTION_OPERAND_LIST(INSTRUCTION_TYPEDEF_SUBKIND_OPERAND_CLASS)
    344 #undef INSTRUCTION_TYPEDEF_SUBKIND_OPERAND_CLASS
    345 
    346 
    347 class ParallelMove FINAL : public ZoneObject {
    348  public:
    349   explicit ParallelMove(Zone* zone) : move_operands_(4, zone) {}
    350 
    351   void AddMove(InstructionOperand* from, InstructionOperand* to, Zone* zone) {
    352     move_operands_.Add(MoveOperands(from, to), zone);
    353   }
    354 
    355   bool IsRedundant() const;
    356 
    357   ZoneList<MoveOperands>* move_operands() { return &move_operands_; }
    358   const ZoneList<MoveOperands>* move_operands() const {
    359     return &move_operands_;
    360   }
    361 
    362  private:
    363   ZoneList<MoveOperands> move_operands_;
    364 };
    365 
    366 OStream& operator<<(OStream& os, const ParallelMove& pm);
    367 
    368 class PointerMap FINAL : public ZoneObject {
    369  public:
    370   explicit PointerMap(Zone* zone)
    371       : pointer_operands_(8, zone),
    372         untagged_operands_(0, zone),
    373         instruction_position_(-1) {}
    374 
    375   const ZoneList<InstructionOperand*>* GetNormalizedOperands() {
    376     for (int i = 0; i < untagged_operands_.length(); ++i) {
    377       RemovePointer(untagged_operands_[i]);
    378     }
    379     untagged_operands_.Clear();
    380     return &pointer_operands_;
    381   }
    382   int instruction_position() const { return instruction_position_; }
    383 
    384   void set_instruction_position(int pos) {
    385     DCHECK(instruction_position_ == -1);
    386     instruction_position_ = pos;
    387   }
    388 
    389   void RecordPointer(InstructionOperand* op, Zone* zone);
    390   void RemovePointer(InstructionOperand* op);
    391   void RecordUntagged(InstructionOperand* op, Zone* zone);
    392 
    393  private:
    394   friend OStream& operator<<(OStream& os, const PointerMap& pm);
    395 
    396   ZoneList<InstructionOperand*> pointer_operands_;
    397   ZoneList<InstructionOperand*> untagged_operands_;
    398   int instruction_position_;
    399 };
    400 
    401 OStream& operator<<(OStream& os, const PointerMap& pm);
    402 
    403 // TODO(titzer): s/PointerMap/ReferenceMap/
    404 class Instruction : public ZoneObject {
    405  public:
    406   size_t OutputCount() const { return OutputCountField::decode(bit_field_); }
    407   InstructionOperand* OutputAt(size_t i) const {
    408     DCHECK(i < OutputCount());
    409     return operands_[i];
    410   }
    411 
    412   bool HasOutput() const { return OutputCount() == 1; }
    413   InstructionOperand* Output() const { return OutputAt(0); }
    414 
    415   size_t InputCount() const { return InputCountField::decode(bit_field_); }
    416   InstructionOperand* InputAt(size_t i) const {
    417     DCHECK(i < InputCount());
    418     return operands_[OutputCount() + i];
    419   }
    420 
    421   size_t TempCount() const { return TempCountField::decode(bit_field_); }
    422   InstructionOperand* TempAt(size_t i) const {
    423     DCHECK(i < TempCount());
    424     return operands_[OutputCount() + InputCount() + i];
    425   }
    426 
    427   InstructionCode opcode() const { return opcode_; }
    428   ArchOpcode arch_opcode() const { return ArchOpcodeField::decode(opcode()); }
    429   AddressingMode addressing_mode() const {
    430     return AddressingModeField::decode(opcode());
    431   }
    432   FlagsMode flags_mode() const { return FlagsModeField::decode(opcode()); }
    433   FlagsCondition flags_condition() const {
    434     return FlagsConditionField::decode(opcode());
    435   }
    436 
    437   // TODO(titzer): make control and call into flags.
    438   static Instruction* New(Zone* zone, InstructionCode opcode) {
    439     return New(zone, opcode, 0, NULL, 0, NULL, 0, NULL);
    440   }
    441 
    442   static Instruction* New(Zone* zone, InstructionCode opcode,
    443                           size_t output_count, InstructionOperand** outputs,
    444                           size_t input_count, InstructionOperand** inputs,
    445                           size_t temp_count, InstructionOperand** temps) {
    446     DCHECK(opcode >= 0);
    447     DCHECK(output_count == 0 || outputs != NULL);
    448     DCHECK(input_count == 0 || inputs != NULL);
    449     DCHECK(temp_count == 0 || temps != NULL);
    450     InstructionOperand* none = NULL;
    451     USE(none);
    452     int size = static_cast<int>(RoundUp(sizeof(Instruction), kPointerSize) +
    453                                 (output_count + input_count + temp_count - 1) *
    454                                     sizeof(none));
    455     return new (zone->New(size)) Instruction(
    456         opcode, output_count, outputs, input_count, inputs, temp_count, temps);
    457   }
    458 
    459   // TODO(titzer): another holdover from lithium days; register allocator
    460   // should not need to know about control instructions.
    461   Instruction* MarkAsControl() {
    462     bit_field_ = IsControlField::update(bit_field_, true);
    463     return this;
    464   }
    465   Instruction* MarkAsCall() {
    466     bit_field_ = IsCallField::update(bit_field_, true);
    467     return this;
    468   }
    469   bool IsControl() const { return IsControlField::decode(bit_field_); }
    470   bool IsCall() const { return IsCallField::decode(bit_field_); }
    471   bool NeedsPointerMap() const { return IsCall(); }
    472   bool HasPointerMap() const { return pointer_map_ != NULL; }
    473 
    474   bool IsGapMoves() const {
    475     return opcode() == kGapInstruction || opcode() == kBlockStartInstruction;
    476   }
    477   bool IsBlockStart() const { return opcode() == kBlockStartInstruction; }
    478   bool IsSourcePosition() const {
    479     return opcode() == kSourcePositionInstruction;
    480   }
    481 
    482   bool ClobbersRegisters() const { return IsCall(); }
    483   bool ClobbersTemps() const { return IsCall(); }
    484   bool ClobbersDoubleRegisters() const { return IsCall(); }
    485   PointerMap* pointer_map() const { return pointer_map_; }
    486 
    487   void set_pointer_map(PointerMap* map) {
    488     DCHECK(NeedsPointerMap());
    489     DCHECK_EQ(NULL, pointer_map_);
    490     pointer_map_ = map;
    491   }
    492 
    493   // Placement new operator so that we can smash instructions into
    494   // zone-allocated memory.
    495   void* operator new(size_t, void* location) { return location; }
    496 
    497   void operator delete(void* pointer, void* location) { UNREACHABLE(); }
    498 
    499  protected:
    500   explicit Instruction(InstructionCode opcode)
    501       : opcode_(opcode),
    502         bit_field_(OutputCountField::encode(0) | InputCountField::encode(0) |
    503                    TempCountField::encode(0) | IsCallField::encode(false) |
    504                    IsControlField::encode(false)),
    505         pointer_map_(NULL) {}
    506 
    507   Instruction(InstructionCode opcode, size_t output_count,
    508               InstructionOperand** outputs, size_t input_count,
    509               InstructionOperand** inputs, size_t temp_count,
    510               InstructionOperand** temps)
    511       : opcode_(opcode),
    512         bit_field_(OutputCountField::encode(output_count) |
    513                    InputCountField::encode(input_count) |
    514                    TempCountField::encode(temp_count) |
    515                    IsCallField::encode(false) | IsControlField::encode(false)),
    516         pointer_map_(NULL) {
    517     for (size_t i = 0; i < output_count; ++i) {
    518       operands_[i] = outputs[i];
    519     }
    520     for (size_t i = 0; i < input_count; ++i) {
    521       operands_[output_count + i] = inputs[i];
    522     }
    523     for (size_t i = 0; i < temp_count; ++i) {
    524       operands_[output_count + input_count + i] = temps[i];
    525     }
    526   }
    527 
    528  protected:
    529   typedef BitField<size_t, 0, 8> OutputCountField;
    530   typedef BitField<size_t, 8, 16> InputCountField;
    531   typedef BitField<size_t, 24, 6> TempCountField;
    532   typedef BitField<bool, 30, 1> IsCallField;
    533   typedef BitField<bool, 31, 1> IsControlField;
    534 
    535   InstructionCode opcode_;
    536   uint32_t bit_field_;
    537   PointerMap* pointer_map_;
    538   InstructionOperand* operands_[1];
    539 };
    540 
    541 OStream& operator<<(OStream& os, const Instruction& instr);
    542 
    543 // Represents moves inserted before an instruction due to register allocation.
    544 // TODO(titzer): squash GapInstruction back into Instruction, since essentially
    545 // every instruction can possibly have moves inserted before it.
    546 class GapInstruction : public Instruction {
    547  public:
    548   enum InnerPosition {
    549     BEFORE,
    550     START,
    551     END,
    552     AFTER,
    553     FIRST_INNER_POSITION = BEFORE,
    554     LAST_INNER_POSITION = AFTER
    555   };
    556 
    557   ParallelMove* GetOrCreateParallelMove(InnerPosition pos, Zone* zone) {
    558     if (parallel_moves_[pos] == NULL) {
    559       parallel_moves_[pos] = new (zone) ParallelMove(zone);
    560     }
    561     return parallel_moves_[pos];
    562   }
    563 
    564   ParallelMove* GetParallelMove(InnerPosition pos) {
    565     return parallel_moves_[pos];
    566   }
    567 
    568   static GapInstruction* New(Zone* zone) {
    569     void* buffer = zone->New(sizeof(GapInstruction));
    570     return new (buffer) GapInstruction(kGapInstruction);
    571   }
    572 
    573   static GapInstruction* cast(Instruction* instr) {
    574     DCHECK(instr->IsGapMoves());
    575     return static_cast<GapInstruction*>(instr);
    576   }
    577 
    578   static const GapInstruction* cast(const Instruction* instr) {
    579     DCHECK(instr->IsGapMoves());
    580     return static_cast<const GapInstruction*>(instr);
    581   }
    582 
    583  protected:
    584   explicit GapInstruction(InstructionCode opcode) : Instruction(opcode) {
    585     parallel_moves_[BEFORE] = NULL;
    586     parallel_moves_[START] = NULL;
    587     parallel_moves_[END] = NULL;
    588     parallel_moves_[AFTER] = NULL;
    589   }
    590 
    591  private:
    592   friend OStream& operator<<(OStream& os, const Instruction& instr);
    593   ParallelMove* parallel_moves_[LAST_INNER_POSITION + 1];
    594 };
    595 
    596 
    597 // This special kind of gap move instruction represents the beginning of a
    598 // block of code.
    599 // TODO(titzer): move code_start and code_end from BasicBlock to here.
    600 class BlockStartInstruction FINAL : public GapInstruction {
    601  public:
    602   BasicBlock* block() const { return block_; }
    603   Label* label() { return &label_; }
    604 
    605   static BlockStartInstruction* New(Zone* zone, BasicBlock* block) {
    606     void* buffer = zone->New(sizeof(BlockStartInstruction));
    607     return new (buffer) BlockStartInstruction(block);
    608   }
    609 
    610   static BlockStartInstruction* cast(Instruction* instr) {
    611     DCHECK(instr->IsBlockStart());
    612     return static_cast<BlockStartInstruction*>(instr);
    613   }
    614 
    615  private:
    616   explicit BlockStartInstruction(BasicBlock* block)
    617       : GapInstruction(kBlockStartInstruction), block_(block) {}
    618 
    619   BasicBlock* block_;
    620   Label label_;
    621 };
    622 
    623 
    624 class SourcePositionInstruction FINAL : public Instruction {
    625  public:
    626   static SourcePositionInstruction* New(Zone* zone, SourcePosition position) {
    627     void* buffer = zone->New(sizeof(SourcePositionInstruction));
    628     return new (buffer) SourcePositionInstruction(position);
    629   }
    630 
    631   SourcePosition source_position() const { return source_position_; }
    632 
    633   static SourcePositionInstruction* cast(Instruction* instr) {
    634     DCHECK(instr->IsSourcePosition());
    635     return static_cast<SourcePositionInstruction*>(instr);
    636   }
    637 
    638   static const SourcePositionInstruction* cast(const Instruction* instr) {
    639     DCHECK(instr->IsSourcePosition());
    640     return static_cast<const SourcePositionInstruction*>(instr);
    641   }
    642 
    643  private:
    644   explicit SourcePositionInstruction(SourcePosition source_position)
    645       : Instruction(kSourcePositionInstruction),
    646         source_position_(source_position) {
    647     DCHECK(!source_position_.IsInvalid());
    648     DCHECK(!source_position_.IsUnknown());
    649   }
    650 
    651   SourcePosition source_position_;
    652 };
    653 
    654 
    655 class Constant FINAL {
    656  public:
    657   enum Type { kInt32, kInt64, kFloat64, kExternalReference, kHeapObject };
    658 
    659   explicit Constant(int32_t v) : type_(kInt32), value_(v) {}
    660   explicit Constant(int64_t v) : type_(kInt64), value_(v) {}
    661   explicit Constant(double v) : type_(kFloat64), value_(bit_cast<int64_t>(v)) {}
    662   explicit Constant(ExternalReference ref)
    663       : type_(kExternalReference), value_(bit_cast<intptr_t>(ref)) {}
    664   explicit Constant(Handle<HeapObject> obj)
    665       : type_(kHeapObject), value_(bit_cast<intptr_t>(obj)) {}
    666 
    667   Type type() const { return type_; }
    668 
    669   int32_t ToInt32() const {
    670     DCHECK_EQ(kInt32, type());
    671     return static_cast<int32_t>(value_);
    672   }
    673 
    674   int64_t ToInt64() const {
    675     if (type() == kInt32) return ToInt32();
    676     DCHECK_EQ(kInt64, type());
    677     return value_;
    678   }
    679 
    680   double ToFloat64() const {
    681     if (type() == kInt32) return ToInt32();
    682     DCHECK_EQ(kFloat64, type());
    683     return bit_cast<double>(value_);
    684   }
    685 
    686   ExternalReference ToExternalReference() const {
    687     DCHECK_EQ(kExternalReference, type());
    688     return bit_cast<ExternalReference>(static_cast<intptr_t>(value_));
    689   }
    690 
    691   Handle<HeapObject> ToHeapObject() const {
    692     DCHECK_EQ(kHeapObject, type());
    693     return bit_cast<Handle<HeapObject> >(static_cast<intptr_t>(value_));
    694   }
    695 
    696  private:
    697   Type type_;
    698   int64_t value_;
    699 };
    700 
    701 
    702 class FrameStateDescriptor : public ZoneObject {
    703  public:
    704   FrameStateDescriptor(const FrameStateCallInfo& state_info,
    705                        size_t parameters_count, size_t locals_count,
    706                        size_t stack_count,
    707                        FrameStateDescriptor* outer_state = NULL)
    708       : type_(state_info.type()),
    709         bailout_id_(state_info.bailout_id()),
    710         frame_state_combine_(state_info.state_combine()),
    711         parameters_count_(parameters_count),
    712         locals_count_(locals_count),
    713         stack_count_(stack_count),
    714         outer_state_(outer_state),
    715         jsfunction_(state_info.jsfunction()) {}
    716 
    717   FrameStateType type() const { return type_; }
    718   BailoutId bailout_id() const { return bailout_id_; }
    719   OutputFrameStateCombine state_combine() const { return frame_state_combine_; }
    720   size_t parameters_count() const { return parameters_count_; }
    721   size_t locals_count() const { return locals_count_; }
    722   size_t stack_count() const { return stack_count_; }
    723   FrameStateDescriptor* outer_state() const { return outer_state_; }
    724   MaybeHandle<JSFunction> jsfunction() const { return jsfunction_; }
    725 
    726   size_t size() const {
    727     return parameters_count_ + locals_count_ + stack_count_ +
    728            (HasContext() ? 1 : 0);
    729   }
    730 
    731   size_t GetTotalSize() const {
    732     size_t total_size = 0;
    733     for (const FrameStateDescriptor* iter = this; iter != NULL;
    734          iter = iter->outer_state_) {
    735       total_size += iter->size();
    736     }
    737     return total_size;
    738   }
    739 
    740   size_t GetHeight(OutputFrameStateCombine override) const {
    741     size_t height = size() - parameters_count();
    742     switch (override) {
    743       case kPushOutput:
    744         ++height;
    745         break;
    746       case kIgnoreOutput:
    747         break;
    748     }
    749     return height;
    750   }
    751 
    752   size_t GetFrameCount() const {
    753     size_t count = 0;
    754     for (const FrameStateDescriptor* iter = this; iter != NULL;
    755          iter = iter->outer_state_) {
    756       ++count;
    757     }
    758     return count;
    759   }
    760 
    761   size_t GetJSFrameCount() const {
    762     size_t count = 0;
    763     for (const FrameStateDescriptor* iter = this; iter != NULL;
    764          iter = iter->outer_state_) {
    765       if (iter->type_ == JS_FRAME) {
    766         ++count;
    767       }
    768     }
    769     return count;
    770   }
    771 
    772   bool HasContext() const { return type_ == JS_FRAME; }
    773 
    774  private:
    775   FrameStateType type_;
    776   BailoutId bailout_id_;
    777   OutputFrameStateCombine frame_state_combine_;
    778   size_t parameters_count_;
    779   size_t locals_count_;
    780   size_t stack_count_;
    781   FrameStateDescriptor* outer_state_;
    782   MaybeHandle<JSFunction> jsfunction_;
    783 };
    784 
    785 OStream& operator<<(OStream& os, const Constant& constant);
    786 
    787 typedef ZoneDeque<Constant> ConstantDeque;
    788 typedef std::map<int, Constant, std::less<int>,
    789                  zone_allocator<std::pair<int, Constant> > > ConstantMap;
    790 
    791 typedef ZoneDeque<Instruction*> InstructionDeque;
    792 typedef ZoneDeque<PointerMap*> PointerMapDeque;
    793 typedef ZoneVector<FrameStateDescriptor*> DeoptimizationVector;
    794 
    795 // Represents architecture-specific generated code before, during, and after
    796 // register allocation.
    797 // TODO(titzer): s/IsDouble/IsFloat64/
    798 class InstructionSequence FINAL {
    799  public:
    800   InstructionSequence(Linkage* linkage, Graph* graph, Schedule* schedule)
    801       : graph_(graph),
    802         linkage_(linkage),
    803         schedule_(schedule),
    804         constants_(ConstantMap::key_compare(),
    805                    ConstantMap::allocator_type(zone())),
    806         immediates_(zone()),
    807         instructions_(zone()),
    808         next_virtual_register_(graph->NodeCount()),
    809         pointer_maps_(zone()),
    810         doubles_(std::less<int>(), VirtualRegisterSet::allocator_type(zone())),
    811         references_(std::less<int>(),
    812                     VirtualRegisterSet::allocator_type(zone())),
    813         deoptimization_entries_(zone()) {}
    814 
    815   int NextVirtualRegister() { return next_virtual_register_++; }
    816   int VirtualRegisterCount() const { return next_virtual_register_; }
    817 
    818   int ValueCount() const { return graph_->NodeCount(); }
    819 
    820   int BasicBlockCount() const {
    821     return static_cast<int>(schedule_->rpo_order()->size());
    822   }
    823 
    824   BasicBlock* BlockAt(int rpo_number) const {
    825     return (*schedule_->rpo_order())[rpo_number];
    826   }
    827 
    828   BasicBlock* GetContainingLoop(BasicBlock* block) {
    829     return block->loop_header_;
    830   }
    831 
    832   int GetLoopEnd(BasicBlock* block) const { return block->loop_end_; }
    833 
    834   BasicBlock* GetBasicBlock(int instruction_index);
    835 
    836   int GetVirtualRegister(Node* node) const { return node->id(); }
    837 
    838   bool IsReference(int virtual_register) const;
    839   bool IsDouble(int virtual_register) const;
    840 
    841   void MarkAsReference(int virtual_register);
    842   void MarkAsDouble(int virtual_register);
    843 
    844   void AddGapMove(int index, InstructionOperand* from, InstructionOperand* to);
    845 
    846   Label* GetLabel(BasicBlock* block);
    847   BlockStartInstruction* GetBlockStart(BasicBlock* block);
    848 
    849   typedef InstructionDeque::const_iterator const_iterator;
    850   const_iterator begin() const { return instructions_.begin(); }
    851   const_iterator end() const { return instructions_.end(); }
    852 
    853   GapInstruction* GapAt(int index) const {
    854     return GapInstruction::cast(InstructionAt(index));
    855   }
    856   bool IsGapAt(int index) const { return InstructionAt(index)->IsGapMoves(); }
    857   Instruction* InstructionAt(int index) const {
    858     DCHECK(index >= 0);
    859     DCHECK(index < static_cast<int>(instructions_.size()));
    860     return instructions_[index];
    861   }
    862 
    863   Frame* frame() { return &frame_; }
    864   Graph* graph() const { return graph_; }
    865   Isolate* isolate() const { return zone()->isolate(); }
    866   Linkage* linkage() const { return linkage_; }
    867   Schedule* schedule() const { return schedule_; }
    868   const PointerMapDeque* pointer_maps() const { return &pointer_maps_; }
    869   Zone* zone() const { return graph_->zone(); }
    870 
    871   // Used by the code generator while adding instructions.
    872   int AddInstruction(Instruction* instr, BasicBlock* block);
    873   void StartBlock(BasicBlock* block);
    874   void EndBlock(BasicBlock* block);
    875 
    876   void AddConstant(int virtual_register, Constant constant) {
    877     DCHECK(constants_.find(virtual_register) == constants_.end());
    878     constants_.insert(std::make_pair(virtual_register, constant));
    879   }
    880   Constant GetConstant(int virtual_register) const {
    881     ConstantMap::const_iterator it = constants_.find(virtual_register);
    882     DCHECK(it != constants_.end());
    883     DCHECK_EQ(virtual_register, it->first);
    884     return it->second;
    885   }
    886 
    887   typedef ConstantDeque Immediates;
    888   const Immediates& immediates() const { return immediates_; }
    889 
    890   int AddImmediate(Constant constant) {
    891     int index = static_cast<int>(immediates_.size());
    892     immediates_.push_back(constant);
    893     return index;
    894   }
    895   Constant GetImmediate(int index) const {
    896     DCHECK(index >= 0);
    897     DCHECK(index < static_cast<int>(immediates_.size()));
    898     return immediates_[index];
    899   }
    900 
    901   class StateId {
    902    public:
    903     static StateId FromInt(int id) { return StateId(id); }
    904     int ToInt() const { return id_; }
    905 
    906    private:
    907     explicit StateId(int id) : id_(id) {}
    908     int id_;
    909   };
    910 
    911   StateId AddFrameStateDescriptor(FrameStateDescriptor* descriptor);
    912   FrameStateDescriptor* GetFrameStateDescriptor(StateId deoptimization_id);
    913   int GetFrameStateDescriptorCount();
    914 
    915  private:
    916   friend OStream& operator<<(OStream& os, const InstructionSequence& code);
    917 
    918   typedef std::set<int, std::less<int>, ZoneIntAllocator> VirtualRegisterSet;
    919 
    920   Graph* graph_;
    921   Linkage* linkage_;
    922   Schedule* schedule_;
    923   ConstantMap constants_;
    924   ConstantDeque immediates_;
    925   InstructionDeque instructions_;
    926   int next_virtual_register_;
    927   PointerMapDeque pointer_maps_;
    928   VirtualRegisterSet doubles_;
    929   VirtualRegisterSet references_;
    930   Frame frame_;
    931   DeoptimizationVector deoptimization_entries_;
    932 };
    933 
    934 OStream& operator<<(OStream& os, const InstructionSequence& code);
    935 
    936 }  // namespace compiler
    937 }  // namespace internal
    938 }  // namespace v8
    939 
    940 #endif  // V8_COMPILER_INSTRUCTION_H_
    941