deps/v8/src/compiler/instruction.h

   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/register-configuration.h"
  18 #include "src/compiler/source-position.h"
  19 #include "src/zone-allocator.h"
  20
  21 namespace v8 {
  22 namespace internal {
  23 namespace compiler {
  24
  25 class Schedule;
  26
  27 // A couple of reserved opcodes are used for internal use.
  28 const InstructionCode kGapInstruction = -1;
  29 const InstructionCode kSourcePositionInstruction = -2;
  30
  31 #define INSTRUCTION_OPERAND_LIST(V)     \
  32   V(Constant, CONSTANT)                 \
  33   V(Immediate, IMMEDIATE)               \
  34   V(StackSlot, STACK_SLOT)              \
  35   V(DoubleStackSlot, DOUBLE_STACK_SLOT) \
  36   V(Register, REGISTER)                 \
  37   V(DoubleRegister, DOUBLE_REGISTER)
  38
  39 class InstructionOperand {
  40  public:
  41   static const int kInvalidVirtualRegister = -1;
  42
  43   enum Kind {
  44     INVALID,
  45     UNALLOCATED,
  46     CONSTANT,
  47     IMMEDIATE,
  48     STACK_SLOT,
  49     DOUBLE_STACK_SLOT,
  50     REGISTER,
  51     DOUBLE_REGISTER
  52   };
  53
  54   InstructionOperand() { ConvertTo(INVALID, 0, kInvalidVirtualRegister); }
  55
  56   InstructionOperand(Kind kind, int index) {
  57     DCHECK(kind != UNALLOCATED && kind != INVALID);
  58     ConvertTo(kind, index, kInvalidVirtualRegister);
  59   }
  60
  61   static InstructionOperand* New(Zone* zone, Kind kind, int index) {
  62     return New(zone, InstructionOperand(kind, index));
  63   }
  64
  65   Kind kind() const { return KindField::decode(value_); }
  66   // TODO(dcarney): move this to subkind operand.
  67   int index() const {
  68     DCHECK(kind() != UNALLOCATED && kind() != INVALID);
  69     return static_cast<int64_t>(value_) >> IndexField::kShift;
  70   }
  71 #define INSTRUCTION_OPERAND_PREDICATE(name, type) \
  72   bool Is##name() const { return kind() == type; }
  73   INSTRUCTION_OPERAND_LIST(INSTRUCTION_OPERAND_PREDICATE)
  74   INSTRUCTION_OPERAND_PREDICATE(Unallocated, UNALLOCATED)
  75   INSTRUCTION_OPERAND_PREDICATE(Invalid, INVALID)
  76 #undef INSTRUCTION_OPERAND_PREDICATE
  77   bool Equals(const InstructionOperand* other) const {
  78     return value_ == other->value_;
  79   }
  80
  81   void ConvertTo(Kind kind, int index) {
  82     DCHECK(kind != UNALLOCATED && kind != INVALID);
  83     ConvertTo(kind, index, kInvalidVirtualRegister);
  84   }
  85
  86   // Useful for map/set keys.
  87   bool operator<(const InstructionOperand& op) const {
  88     return value_ < op.value_;
  89   }
  90
  91  protected:
  92   template <typename SubKindOperand>
  93   static SubKindOperand* New(Zone* zone, const SubKindOperand& op) {
  94     void* buffer = zone->New(sizeof(op));
  95     return new (buffer) SubKindOperand(op);
  96   }
  97
  98   InstructionOperand(Kind kind, int index, int virtual_register) {
  99     ConvertTo(kind, index, virtual_register);
 100   }
 101
 102   void ConvertTo(Kind kind, int index, int virtual_register) {
 103     if (kind == REGISTER || kind == DOUBLE_REGISTER) DCHECK(index >= 0);
 104     if (kind != UNALLOCATED) {
 105       DCHECK(virtual_register == kInvalidVirtualRegister);
 106     }
 107     value_ = KindField::encode(kind);
 108     value_ |=
 109         VirtualRegisterField::encode(static_cast<uint32_t>(virtual_register));
 110     value_ |= static_cast<int64_t>(index) << IndexField::kShift;
 111     DCHECK(((kind == UNALLOCATED || kind == INVALID) && index == 0) ||
 112            this->index() == index);
 113   }
 114
 115   typedef BitField64<Kind, 0, 3> KindField;
 116   typedef BitField64<uint32_t, 3, 32> VirtualRegisterField;
 117   typedef BitField64<int32_t, 35, 29> IndexField;
 118
 119   uint64_t value_;
 120 };
 121
 122 struct PrintableInstructionOperand {
 123   const RegisterConfiguration* register_configuration_;
 124   const InstructionOperand* op_;
 125 };
 126
 127 std::ostream& operator<<(std::ostream& os,
 128                          const PrintableInstructionOperand& op);
 129
 130 class UnallocatedOperand : public InstructionOperand {
 131  public:
 132   enum BasicPolicy { FIXED_SLOT, EXTENDED_POLICY };
 133
 134   enum ExtendedPolicy {
 135     NONE,
 136     ANY,
 137     FIXED_REGISTER,
 138     FIXED_DOUBLE_REGISTER,
 139     MUST_HAVE_REGISTER,
 140     MUST_HAVE_SLOT,
 141     SAME_AS_FIRST_INPUT
 142   };
 143
 144   // Lifetime of operand inside the instruction.
 145   enum Lifetime {
 146     // USED_AT_START operand is guaranteed to be live only at
 147     // instruction start. Register allocator is free to assign the same register
 148     // to some other operand used inside instruction (i.e. temporary or
 149     // output).
 150     USED_AT_START,
 151
 152     // USED_AT_END operand is treated as live until the end of
 153     // instruction. This means that register allocator will not reuse it's
 154     // register for any other operand inside instruction.
 155     USED_AT_END
 156   };
 157
 158   UnallocatedOperand(ExtendedPolicy policy, int virtual_register)
 159       : InstructionOperand(UNALLOCATED, 0, virtual_register) {
 160     value_ |= BasicPolicyField::encode(EXTENDED_POLICY);
 161     value_ |= ExtendedPolicyField::encode(policy);
 162     value_ |= LifetimeField::encode(USED_AT_END);
 163   }
 164
 165   UnallocatedOperand(BasicPolicy policy, int index, int virtual_register)
 166       : InstructionOperand(UNALLOCATED, 0, virtual_register) {
 167     DCHECK(policy == FIXED_SLOT);
 168     value_ |= BasicPolicyField::encode(policy);
 169     value_ |= static_cast<int64_t>(index) << FixedSlotIndexField::kShift;
 170     DCHECK(this->fixed_slot_index() == index);
 171   }
 172
 173   UnallocatedOperand(ExtendedPolicy policy, int index, int virtual_register)
 174       : InstructionOperand(UNALLOCATED, 0, virtual_register) {
 175     DCHECK(policy == FIXED_REGISTER || policy == FIXED_DOUBLE_REGISTER);
 176     value_ |= BasicPolicyField::encode(EXTENDED_POLICY);
 177     value_ |= ExtendedPolicyField::encode(policy);
 178     value_ |= LifetimeField::encode(USED_AT_END);
 179     value_ |= FixedRegisterField::encode(index);
 180   }
 181
 182   UnallocatedOperand(ExtendedPolicy policy, Lifetime lifetime,
 183                      int virtual_register)
 184       : InstructionOperand(UNALLOCATED, 0, virtual_register) {
 185     value_ |= BasicPolicyField::encode(EXTENDED_POLICY);
 186     value_ |= ExtendedPolicyField::encode(policy);
 187     value_ |= LifetimeField::encode(lifetime);
 188   }
 189
 190   UnallocatedOperand* Copy(Zone* zone) { return New(zone, *this); }
 191
 192   UnallocatedOperand* CopyUnconstrained(Zone* zone) {
 193     return New(zone, UnallocatedOperand(ANY, virtual_register()));
 194   }
 195
 196   static const UnallocatedOperand* cast(const InstructionOperand* op) {
 197     DCHECK(op->IsUnallocated());
 198     return static_cast<const UnallocatedOperand*>(op);
 199   }
 200
 201   static UnallocatedOperand* cast(InstructionOperand* op) {
 202     DCHECK(op->IsUnallocated());
 203     return static_cast<UnallocatedOperand*>(op);
 204   }
 205
 206   static UnallocatedOperand cast(const InstructionOperand& op) {
 207     DCHECK(op.IsUnallocated());
 208     return *static_cast<const UnallocatedOperand*>(&op);
 209   }
 210
 211   // The encoding used for UnallocatedOperand operands depends on the policy
 212   // that is
 213   // stored within the operand. The FIXED_SLOT policy uses a compact encoding
 214   // because it accommodates a larger pay-load.
 215   //
 216   // For FIXED_SLOT policy:
 217   //     +------------------------------------------------+
 218   //     |      slot_index   | 0 | virtual_register | 001 |
 219   //     +------------------------------------------------+
 220   //
 221   // For all other (extended) policies:
 222   //     +-----------------------------------------------------+
 223   //     |  reg_index  | L | PPP |  1 | virtual_register | 001 |
 224   //     +-----------------------------------------------------+
 225   //     L ... Lifetime
 226   //     P ... Policy
 227   //
 228   // The slot index is a signed value which requires us to decode it manually
 229   // instead of using the BitField utility class.
 230
 231   // All bits fit into the index field.
 232   STATIC_ASSERT(IndexField::kShift == 35);
 233
 234   // BitFields for all unallocated operands.
 235   class BasicPolicyField : public BitField64<BasicPolicy, 35, 1> {};
 236
 237   // BitFields specific to BasicPolicy::FIXED_SLOT.
 238   class FixedSlotIndexField : public BitField64<int, 36, 28> {};
 239
 240   // BitFields specific to BasicPolicy::EXTENDED_POLICY.
 241   class ExtendedPolicyField : public BitField64<ExtendedPolicy, 36, 3> {};
 242   class LifetimeField : public BitField64<Lifetime, 39, 1> {};
 243   class FixedRegisterField : public BitField64<int, 40, 6> {};
 244
 245   // Predicates for the operand policy.
 246   bool HasAnyPolicy() const {
 247     return basic_policy() == EXTENDED_POLICY && extended_policy() == ANY;
 248   }
 249   bool HasFixedPolicy() const {
 250     return basic_policy() == FIXED_SLOT ||
 251            extended_policy() == FIXED_REGISTER ||
 252            extended_policy() == FIXED_DOUBLE_REGISTER;
 253   }
 254   bool HasRegisterPolicy() const {
 255     return basic_policy() == EXTENDED_POLICY &&
 256            extended_policy() == MUST_HAVE_REGISTER;
 257   }
 258   bool HasSlotPolicy() const {
 259     return basic_policy() == EXTENDED_POLICY &&
 260            extended_policy() == MUST_HAVE_SLOT;
 261   }
 262   bool HasSameAsInputPolicy() const {
 263     return basic_policy() == EXTENDED_POLICY &&
 264            extended_policy() == SAME_AS_FIRST_INPUT;
 265   }
 266   bool HasFixedSlotPolicy() const { return basic_policy() == FIXED_SLOT; }
 267   bool HasFixedRegisterPolicy() const {
 268     return basic_policy() == EXTENDED_POLICY &&
 269            extended_policy() == FIXED_REGISTER;
 270   }
 271   bool HasFixedDoubleRegisterPolicy() const {
 272     return basic_policy() == EXTENDED_POLICY &&
 273            extended_policy() == FIXED_DOUBLE_REGISTER;
 274   }
 275
 276   // [basic_policy]: Distinguish between FIXED_SLOT and all other policies.
 277   BasicPolicy basic_policy() const {
 278     DCHECK_EQ(UNALLOCATED, kind());
 279     return BasicPolicyField::decode(value_);
 280   }
 281
 282   // [extended_policy]: Only for non-FIXED_SLOT. The finer-grained policy.
 283   ExtendedPolicy extended_policy() const {
 284     DCHECK(basic_policy() == EXTENDED_POLICY);
 285     return ExtendedPolicyField::decode(value_);
 286   }
 287
 288   // [fixed_slot_index]: Only for FIXED_SLOT.
 289   int fixed_slot_index() const {
 290     DCHECK(HasFixedSlotPolicy());
 291     return static_cast<int>(static_cast<int64_t>(value_) >>
 292                             FixedSlotIndexField::kShift);
 293   }
 294
 295   // [fixed_register_index]: Only for FIXED_REGISTER or FIXED_DOUBLE_REGISTER.
 296   int fixed_register_index() const {
 297     DCHECK(HasFixedRegisterPolicy() || HasFixedDoubleRegisterPolicy());
 298     return FixedRegisterField::decode(value_);
 299   }
 300
 301   // [virtual_register]: The virtual register ID for this operand.
 302   int32_t virtual_register() const {
 303     DCHECK_EQ(UNALLOCATED, kind());
 304     return static_cast<int32_t>(VirtualRegisterField::decode(value_));
 305   }
 306
 307   // TODO(dcarney): remove this.
 308   void set_virtual_register(int32_t id) {
 309     DCHECK_EQ(UNALLOCATED, kind());
 310     value_ = VirtualRegisterField::update(value_, static_cast<uint32_t>(id));
 311   }
 312
 313   // [lifetime]: Only for non-FIXED_SLOT.
 314   bool IsUsedAtStart() const {
 315     DCHECK(basic_policy() == EXTENDED_POLICY);
 316     return LifetimeField::decode(value_) == USED_AT_START;
 317   }
 318 };
 319
 320
 321 class MoveOperands FINAL {
 322  public:
 323   MoveOperands(InstructionOperand* source, InstructionOperand* destination)
 324       : source_(source), destination_(destination) {}
 325
 326   InstructionOperand* source() const { return source_; }
 327   void set_source(InstructionOperand* operand) { source_ = operand; }
 328
 329   InstructionOperand* destination() const { return destination_; }
 330   void set_destination(InstructionOperand* operand) { destination_ = operand; }
 331
 332   // The gap resolver marks moves as "in-progress" by clearing the
 333   // destination (but not the source).
 334   bool IsPending() const { return destination_ == NULL && source_ != NULL; }
 335
 336   // True if this move a move into the given destination operand.
 337   bool Blocks(InstructionOperand* operand) const {
 338     return !IsEliminated() && source()->Equals(operand);
 339   }
 340
 341   // A move is redundant if it's been eliminated, if its source and
 342   // destination are the same, or if its destination is  constant.
 343   bool IsRedundant() const {
 344     return IsEliminated() || source_->Equals(destination_) ||
 345            (destination_ != NULL && destination_->IsConstant());
 346   }
 347
 348   // We clear both operands to indicate move that's been eliminated.
 349   void Eliminate() { source_ = destination_ = NULL; }
 350   bool IsEliminated() const {
 351     DCHECK(source_ != NULL || destination_ == NULL);
 352     return source_ == NULL;
 353   }
 354
 355  private:
 356   InstructionOperand* source_;
 357   InstructionOperand* destination_;
 358 };
 359
 360
 361 struct PrintableMoveOperands {
 362   const RegisterConfiguration* register_configuration_;
 363   const MoveOperands* move_operands_;
 364 };
 365
 366
 367 std::ostream& operator<<(std::ostream& os, const PrintableMoveOperands& mo);
 368
 369
 370 #define INSTRUCTION_SUBKIND_OPERAND_CLASS(SubKind, kOperandKind)        \
 371   class SubKind##Operand FINAL : public InstructionOperand {            \
 372    public:                                                              \
 373     explicit SubKind##Operand(int index)                                \
 374         : InstructionOperand(kOperandKind, index) {}                    \
 375                                                                         \
 376     static SubKind##Operand* New(int index, Zone* zone) {               \
 377       return InstructionOperand::New(zone, SubKind##Operand(index));    \
 378     }                                                                   \
 379                                                                         \
 380     static SubKind##Operand* cast(InstructionOperand* op) {             \
 381       DCHECK(op->kind() == kOperandKind);                               \
 382       return reinterpret_cast<SubKind##Operand*>(op);                   \
 383     }                                                                   \
 384                                                                         \
 385     static const SubKind##Operand* cast(const InstructionOperand* op) { \
 386       DCHECK(op->kind() == kOperandKind);                               \
 387       return reinterpret_cast<const SubKind##Operand*>(op);             \
 388     }                                                                   \
 389                                                                         \
 390     static SubKind##Operand cast(const InstructionOperand& op) {        \
 391       DCHECK(op.kind() == kOperandKind);                                \
 392       return *static_cast<const SubKind##Operand*>(&op);                \
 393     }                                                                   \
 394   };
 395 INSTRUCTION_OPERAND_LIST(INSTRUCTION_SUBKIND_OPERAND_CLASS)
 396 #undef INSTRUCTION_SUBKIND_OPERAND_CLASS
 397
 398
 399 class ParallelMove FINAL : public ZoneObject {
 400  public:
 401   explicit ParallelMove(Zone* zone) : move_operands_(4, zone) {}
 402
 403   void AddMove(InstructionOperand* from, InstructionOperand* to, Zone* zone) {
 404     move_operands_.Add(MoveOperands(from, to), zone);
 405   }
 406
 407   bool IsRedundant() const;
 408
 409   ZoneList<MoveOperands>* move_operands() { return &move_operands_; }
 410   const ZoneList<MoveOperands>* move_operands() const {
 411     return &move_operands_;
 412   }
 413
 414   // Prepare this ParallelMove to insert move as if it happened in a subsequent
 415   // ParallelMove.  move->source() may be changed.  The MoveOperand returned
 416   // must be Eliminated and, as it points directly into move_operands_, it must
 417   // be Eliminated before any further mutation.
 418   MoveOperands* PrepareInsertAfter(MoveOperands* move) const;
 419
 420  private:
 421   ZoneList<MoveOperands> move_operands_;
 422 };
 423
 424
 425 struct PrintableParallelMove {
 426   const RegisterConfiguration* register_configuration_;
 427   const ParallelMove* parallel_move_;
 428 };
 429
 430
 431 std::ostream& operator<<(std::ostream& os, const PrintableParallelMove& pm);
 432
 433
 434 class PointerMap FINAL : public ZoneObject {
 435  public:
 436   explicit PointerMap(Zone* zone)
 437       : pointer_operands_(8, zone),
 438         untagged_operands_(0, zone),
 439         instruction_position_(-1) {}
 440
 441   const ZoneList<InstructionOperand*>* GetNormalizedOperands() {
 442     for (int i = 0; i < untagged_operands_.length(); ++i) {
 443       RemovePointer(untagged_operands_[i]);
 444     }
 445     untagged_operands_.Clear();
 446     return &pointer_operands_;
 447   }
 448   int instruction_position() const { return instruction_position_; }
 449
 450   void set_instruction_position(int pos) {
 451     DCHECK(instruction_position_ == -1);
 452     instruction_position_ = pos;
 453   }
 454
 455   void RecordPointer(InstructionOperand* op, Zone* zone);
 456   void RemovePointer(InstructionOperand* op);
 457   void RecordUntagged(InstructionOperand* op, Zone* zone);
 458
 459  private:
 460   friend std::ostream& operator<<(std::ostream& os, const PointerMap& pm);
 461
 462   ZoneList<InstructionOperand*> pointer_operands_;
 463   ZoneList<InstructionOperand*> untagged_operands_;
 464   int instruction_position_;
 465 };
 466
 467 std::ostream& operator<<(std::ostream& os, const PointerMap& pm);
 468
 469 // TODO(titzer): s/PointerMap/ReferenceMap/
 470 class Instruction {
 471  public:
 472   size_t OutputCount() const { return OutputCountField::decode(bit_field_); }
 473   const InstructionOperand* OutputAt(size_t i) const {
 474     DCHECK(i < OutputCount());
 475     return &operands_[i];
 476   }
 477   InstructionOperand* OutputAt(size_t i) {
 478     DCHECK(i < OutputCount());
 479     return &operands_[i];
 480   }
 481
 482   bool HasOutput() const { return OutputCount() == 1; }
 483   const InstructionOperand* Output() const { return OutputAt(0); }
 484   InstructionOperand* Output() { return OutputAt(0); }
 485
 486   size_t InputCount() const { return InputCountField::decode(bit_field_); }
 487   const InstructionOperand* InputAt(size_t i) const {
 488     DCHECK(i < InputCount());
 489     return &operands_[OutputCount() + i];
 490   }
 491   InstructionOperand* InputAt(size_t i) {
 492     DCHECK(i < InputCount());
 493     return &operands_[OutputCount() + i];
 494   }
 495
 496   size_t TempCount() const { return TempCountField::decode(bit_field_); }
 497   const InstructionOperand* TempAt(size_t i) const {
 498     DCHECK(i < TempCount());
 499     return &operands_[OutputCount() + InputCount() + i];
 500   }
 501   InstructionOperand* TempAt(size_t i) {
 502     DCHECK(i < TempCount());
 503     return &operands_[OutputCount() + InputCount() + i];
 504   }
 505
 506   InstructionCode opcode() const { return opcode_; }
 507   ArchOpcode arch_opcode() const { return ArchOpcodeField::decode(opcode()); }
 508   AddressingMode addressing_mode() const {
 509     return AddressingModeField::decode(opcode());
 510   }
 511   FlagsMode flags_mode() const { return FlagsModeField::decode(opcode()); }
 512   FlagsCondition flags_condition() const {
 513     return FlagsConditionField::decode(opcode());
 514   }
 515
 516   // TODO(titzer): make call into a flags.
 517   static Instruction* New(Zone* zone, InstructionCode opcode) {
 518     return New(zone, opcode, 0, NULL, 0, NULL, 0, NULL);
 519   }
 520
 521   static Instruction* New(Zone* zone, InstructionCode opcode,
 522                           size_t output_count, InstructionOperand* outputs,
 523                           size_t input_count, InstructionOperand* inputs,
 524                           size_t temp_count, InstructionOperand* temps) {
 525     DCHECK(opcode >= 0);
 526     DCHECK(output_count == 0 || outputs != NULL);
 527     DCHECK(input_count == 0 || inputs != NULL);
 528     DCHECK(temp_count == 0 || temps != NULL);
 529     size_t total_extra_ops = output_count + input_count + temp_count;
 530     if (total_extra_ops != 0) total_extra_ops--;
 531     int size = static_cast<int>(
 532         RoundUp(sizeof(Instruction), sizeof(InstructionOperand)) +
 533         total_extra_ops * sizeof(InstructionOperand));
 534     return new (zone->New(size)) Instruction(
 535         opcode, output_count, outputs, input_count, inputs, temp_count, temps);
 536   }
 537
 538   Instruction* MarkAsCall() {
 539     bit_field_ = IsCallField::update(bit_field_, true);
 540     return this;
 541   }
 542   bool IsCall() const { return IsCallField::decode(bit_field_); }
 543   bool NeedsPointerMap() const { return IsCall(); }
 544   bool HasPointerMap() const { return pointer_map_ != NULL; }
 545
 546   bool IsGapMoves() const { return opcode() == kGapInstruction; }
 547   bool IsSourcePosition() const {
 548     return opcode() == kSourcePositionInstruction;
 549   }
 550
 551   bool ClobbersRegisters() const { return IsCall(); }
 552   bool ClobbersTemps() const { return IsCall(); }
 553   bool ClobbersDoubleRegisters() const { return IsCall(); }
 554   PointerMap* pointer_map() const { return pointer_map_; }
 555
 556   void set_pointer_map(PointerMap* map) {
 557     DCHECK(NeedsPointerMap());
 558     DCHECK(!pointer_map_);
 559     pointer_map_ = map;
 560   }
 561
 562   void OverwriteWithNop() {
 563     opcode_ = ArchOpcodeField::encode(kArchNop);
 564     bit_field_ = 0;
 565     pointer_map_ = NULL;
 566   }
 567
 568   bool IsNop() const {
 569     return arch_opcode() == kArchNop && InputCount() == 0 &&
 570            OutputCount() == 0 && TempCount() == 0;
 571   }
 572
 573  protected:
 574   explicit Instruction(InstructionCode opcode);
 575   Instruction(InstructionCode opcode, size_t output_count,
 576               InstructionOperand* outputs, size_t input_count,
 577               InstructionOperand* inputs, size_t temp_count,
 578               InstructionOperand* temps);
 579
 580   typedef BitField<size_t, 0, 8> OutputCountField;
 581   typedef BitField<size_t, 8, 16> InputCountField;
 582   typedef BitField<size_t, 24, 6> TempCountField;
 583   typedef BitField<bool, 30, 1> IsCallField;
 584
 585   InstructionCode opcode_;
 586   uint32_t bit_field_;
 587   PointerMap* pointer_map_;
 588   InstructionOperand operands_[1];
 589
 590  private:
 591   DISALLOW_COPY_AND_ASSIGN(Instruction);
 592 };
 593
 594
 595 struct PrintableInstruction {
 596   const RegisterConfiguration* register_configuration_;
 597   const Instruction* instr_;
 598 };
 599 std::ostream& operator<<(std::ostream& os, const PrintableInstruction& instr);
 600
 601
 602 // Represents moves inserted before an instruction due to register allocation.
 603 // TODO(titzer): squash GapInstruction back into Instruction, since essentially
 604 // every instruction can possibly have moves inserted before it.
 605 class GapInstruction : public Instruction {
 606  public:
 607   enum InnerPosition {
 608     START,
 609     END,
 610     FIRST_INNER_POSITION = START,
 611     LAST_INNER_POSITION = END
 612   };
 613
 614   ParallelMove* GetOrCreateParallelMove(InnerPosition pos, Zone* zone) {
 615     if (parallel_moves_[pos] == NULL) {
 616       parallel_moves_[pos] = new (zone) ParallelMove(zone);
 617     }
 618     return parallel_moves_[pos];
 619   }
 620
 621   ParallelMove* GetParallelMove(InnerPosition pos) {
 622     return parallel_moves_[pos];
 623   }
 624
 625   const ParallelMove* GetParallelMove(InnerPosition pos) const {
 626     return parallel_moves_[pos];
 627   }
 628
 629   bool IsRedundant() const;
 630
 631   ParallelMove** parallel_moves() { return parallel_moves_; }
 632
 633   static GapInstruction* New(Zone* zone) {
 634     void* buffer = zone->New(sizeof(GapInstruction));
 635     return new (buffer) GapInstruction(kGapInstruction);
 636   }
 637
 638   static GapInstruction* cast(Instruction* instr) {
 639     DCHECK(instr->IsGapMoves());
 640     return static_cast<GapInstruction*>(instr);
 641   }
 642
 643   static const GapInstruction* cast(const Instruction* instr) {
 644     DCHECK(instr->IsGapMoves());
 645     return static_cast<const GapInstruction*>(instr);
 646   }
 647
 648  protected:
 649   explicit GapInstruction(InstructionCode opcode) : Instruction(opcode) {
 650     parallel_moves_[START] = NULL;
 651     parallel_moves_[END] = NULL;
 652   }
 653
 654  private:
 655   friend std::ostream& operator<<(std::ostream& os,
 656                                   const PrintableInstruction& instr);
 657   ParallelMove* parallel_moves_[LAST_INNER_POSITION + 1];
 658 };
 659
 660
 661 class SourcePositionInstruction FINAL : public Instruction {
 662  public:
 663   static SourcePositionInstruction* New(Zone* zone, SourcePosition position) {
 664     void* buffer = zone->New(sizeof(SourcePositionInstruction));
 665     return new (buffer) SourcePositionInstruction(position);
 666   }
 667
 668   SourcePosition source_position() const { return source_position_; }
 669
 670   static SourcePositionInstruction* cast(Instruction* instr) {
 671     DCHECK(instr->IsSourcePosition());
 672     return static_cast<SourcePositionInstruction*>(instr);
 673   }
 674
 675   static const SourcePositionInstruction* cast(const Instruction* instr) {
 676     DCHECK(instr->IsSourcePosition());
 677     return static_cast<const SourcePositionInstruction*>(instr);
 678   }
 679
 680  private:
 681   explicit SourcePositionInstruction(SourcePosition source_position)
 682       : Instruction(kSourcePositionInstruction),
 683         source_position_(source_position) {
 684     DCHECK(!source_position_.IsInvalid());
 685     DCHECK(!source_position_.IsUnknown());
 686   }
 687
 688   SourcePosition source_position_;
 689 };
 690
 691
 692 class RpoNumber FINAL {
 693  public:
 694   static const int kInvalidRpoNumber = -1;
 695   int ToInt() const {
 696     DCHECK(IsValid());
 697     return index_;
 698   }
 699   size_t ToSize() const {
 700     DCHECK(IsValid());
 701     return static_cast<size_t>(index_);
 702   }
 703   bool IsValid() const { return index_ >= 0; }
 704   static RpoNumber FromInt(int index) { return RpoNumber(index); }
 705   static RpoNumber Invalid() { return RpoNumber(kInvalidRpoNumber); }
 706
 707   bool IsNext(const RpoNumber other) const {
 708     DCHECK(IsValid());
 709     return other.index_ == this->index_ + 1;
 710   }
 711
 712   bool operator==(RpoNumber other) const {
 713     return this->index_ == other.index_;
 714   }
 715
 716  private:
 717   explicit RpoNumber(int32_t index) : index_(index) {}
 718   int32_t index_;
 719 };
 720
 721
 722 std::ostream& operator<<(std::ostream&, const RpoNumber&);
 723
 724
 725 class Constant FINAL {
 726  public:
 727   enum Type {
 728     kInt32,
 729     kInt64,
 730     kFloat32,
 731     kFloat64,
 732     kExternalReference,
 733     kHeapObject,
 734     kRpoNumber
 735   };
 736
 737   explicit Constant(int32_t v);
 738   explicit Constant(int64_t v) : type_(kInt64), value_(v) {}
 739   explicit Constant(float v) : type_(kFloat32), value_(bit_cast<int32_t>(v)) {}
 740   explicit Constant(double v) : type_(kFloat64), value_(bit_cast<int64_t>(v)) {}
 741   explicit Constant(ExternalReference ref)
 742       : type_(kExternalReference), value_(bit_cast<intptr_t>(ref)) {}
 743   explicit Constant(Handle<HeapObject> obj)
 744       : type_(kHeapObject), value_(bit_cast<intptr_t>(obj)) {}
 745   explicit Constant(RpoNumber rpo) : type_(kRpoNumber), value_(rpo.ToInt()) {}
 746
 747   Type type() const { return type_; }
 748
 749   int32_t ToInt32() const {
 750     DCHECK(type() == kInt32 || type() == kInt64);
 751     const int32_t value = static_cast<int32_t>(value_);
 752     DCHECK_EQ(value_, static_cast<int64_t>(value));
 753     return value;
 754   }
 755
 756   int64_t ToInt64() const {
 757     if (type() == kInt32) return ToInt32();
 758     DCHECK_EQ(kInt64, type());
 759     return value_;
 760   }
 761
 762   float ToFloat32() const {
 763     DCHECK_EQ(kFloat32, type());
 764     return bit_cast<float>(static_cast<int32_t>(value_));
 765   }
 766
 767   double ToFloat64() const {
 768     if (type() == kInt32) return ToInt32();
 769     DCHECK_EQ(kFloat64, type());
 770     return bit_cast<double>(value_);
 771   }
 772
 773   ExternalReference ToExternalReference() const {
 774     DCHECK_EQ(kExternalReference, type());
 775     return bit_cast<ExternalReference>(static_cast<intptr_t>(value_));
 776   }
 777
 778   RpoNumber ToRpoNumber() const {
 779     DCHECK_EQ(kRpoNumber, type());
 780     return RpoNumber::FromInt(static_cast<int>(value_));
 781   }
 782
 783   Handle<HeapObject> ToHeapObject() const {
 784     DCHECK_EQ(kHeapObject, type());
 785     return bit_cast<Handle<HeapObject> >(static_cast<intptr_t>(value_));
 786   }
 787
 788  private:
 789   Type type_;
 790   int64_t value_;
 791 };
 792
 793
 794 class FrameStateDescriptor : public ZoneObject {
 795  public:
 796   FrameStateDescriptor(Zone* zone, const FrameStateCallInfo& state_info,
 797                        size_t parameters_count, size_t locals_count,
 798                        size_t stack_count,
 799                        FrameStateDescriptor* outer_state = NULL);
 800
 801   FrameStateType type() const { return type_; }
 802   BailoutId bailout_id() const { return bailout_id_; }
 803   OutputFrameStateCombine state_combine() const { return frame_state_combine_; }
 804   size_t parameters_count() const { return parameters_count_; }
 805   size_t locals_count() const { return locals_count_; }
 806   size_t stack_count() const { return stack_count_; }
 807   FrameStateDescriptor* outer_state() const { return outer_state_; }
 808   MaybeHandle<JSFunction> jsfunction() const { return jsfunction_; }
 809   bool HasContext() const { return type_ == JS_FRAME; }
 810
 811   size_t GetSize(OutputFrameStateCombine combine =
 812                      OutputFrameStateCombine::Ignore()) const;
 813   size_t GetTotalSize() const;
 814   size_t GetFrameCount() const;
 815   size_t GetJSFrameCount() const;
 816
 817   MachineType GetType(size_t index) const;
 818   void SetType(size_t index, MachineType type);
 819
 820  private:
 821   FrameStateType type_;
 822   BailoutId bailout_id_;
 823   OutputFrameStateCombine frame_state_combine_;
 824   size_t parameters_count_;
 825   size_t locals_count_;
 826   size_t stack_count_;
 827   ZoneVector<MachineType> types_;
 828   FrameStateDescriptor* outer_state_;
 829   MaybeHandle<JSFunction> jsfunction_;
 830 };
 831
 832 std::ostream& operator<<(std::ostream& os, const Constant& constant);
 833
 834
 835 class PhiInstruction FINAL : public ZoneObject {
 836  public:
 837   typedef ZoneVector<InstructionOperand> Inputs;
 838
 839   PhiInstruction(Zone* zone, int virtual_register, size_t input_count);
 840
 841   void SetInput(size_t offset, int virtual_register);
 842
 843   int virtual_register() const { return virtual_register_; }
 844   const IntVector& operands() const { return operands_; }
 845
 846   const InstructionOperand& output() const { return output_; }
 847   InstructionOperand& output() { return output_; }
 848   const Inputs& inputs() const { return inputs_; }
 849   Inputs& inputs() { return inputs_; }
 850
 851  private:
 852   // TODO(dcarney): some of these fields are only for verification, move them to
 853   // verifier.
 854   const int virtual_register_;
 855   InstructionOperand output_;
 856   IntVector operands_;
 857   Inputs inputs_;
 858 };
 859
 860
 861 // Analogue of BasicBlock for Instructions instead of Nodes.
 862 class InstructionBlock FINAL : public ZoneObject {
 863  public:
 864   InstructionBlock(Zone* zone, RpoNumber rpo_number, RpoNumber loop_header,
 865                    RpoNumber loop_end, bool deferred);
 866
 867   // Instruction indexes (used by the register allocator).
 868   int first_instruction_index() const {
 869     DCHECK(code_start_ >= 0);
 870     DCHECK(code_end_ > 0);
 871     DCHECK(code_end_ >= code_start_);
 872     return code_start_;
 873   }
 874   int last_instruction_index() const {
 875     DCHECK(code_start_ >= 0);
 876     DCHECK(code_end_ > 0);
 877     DCHECK(code_end_ >= code_start_);
 878     return code_end_ - 1;
 879   }
 880
 881   int32_t code_start() const { return code_start_; }
 882   void set_code_start(int32_t start) { code_start_ = start; }
 883
 884   int32_t code_end() const { return code_end_; }
 885   void set_code_end(int32_t end) { code_end_ = end; }
 886
 887   bool IsDeferred() const { return deferred_; }
 888
 889   RpoNumber ao_number() const { return ao_number_; }
 890   RpoNumber rpo_number() const { return rpo_number_; }
 891   RpoNumber loop_header() const { return loop_header_; }
 892   RpoNumber loop_end() const {
 893     DCHECK(IsLoopHeader());
 894     return loop_end_;
 895   }
 896   inline bool IsLoopHeader() const { return loop_end_.IsValid(); }
 897
 898   typedef ZoneVector<RpoNumber> Predecessors;
 899   Predecessors& predecessors() { return predecessors_; }
 900   const Predecessors& predecessors() const { return predecessors_; }
 901   size_t PredecessorCount() const { return predecessors_.size(); }
 902   size_t PredecessorIndexOf(RpoNumber rpo_number) const;
 903
 904   typedef ZoneVector<RpoNumber> Successors;
 905   Successors& successors() { return successors_; }
 906   const Successors& successors() const { return successors_; }
 907   size_t SuccessorCount() const { return successors_.size(); }
 908
 909   typedef ZoneVector<PhiInstruction*> PhiInstructions;
 910   const PhiInstructions& phis() const { return phis_; }
 911   void AddPhi(PhiInstruction* phi) { phis_.push_back(phi); }
 912
 913   void set_ao_number(RpoNumber ao_number) { ao_number_ = ao_number; }
 914
 915  private:
 916   Successors successors_;
 917   Predecessors predecessors_;
 918   PhiInstructions phis_;
 919   RpoNumber ao_number_;  // Assembly order number.
 920   const RpoNumber rpo_number_;
 921   const RpoNumber loop_header_;
 922   const RpoNumber loop_end_;
 923   int32_t code_start_;   // start index of arch-specific code.
 924   int32_t code_end_;     // end index of arch-specific code.
 925   const bool deferred_;  // Block contains deferred code.
 926 };
 927
 928 typedef ZoneDeque<Constant> ConstantDeque;
 929 typedef std::map<int, Constant, std::less<int>,
 930                  zone_allocator<std::pair<int, Constant> > > ConstantMap;
 931
 932 typedef ZoneDeque<Instruction*> InstructionDeque;
 933 typedef ZoneDeque<PointerMap*> PointerMapDeque;
 934 typedef ZoneVector<FrameStateDescriptor*> DeoptimizationVector;
 935 typedef ZoneVector<InstructionBlock*> InstructionBlocks;
 936
 937 struct PrintableInstructionSequence;
 938
 939
 940 // Represents architecture-specific generated code before, during, and after
 941 // register allocation.
 942 // TODO(titzer): s/IsDouble/IsFloat64/
 943 class InstructionSequence FINAL : public ZoneObject {
 944  public:
 945   static InstructionBlocks* InstructionBlocksFor(Zone* zone,
 946                                                  const Schedule* schedule);
 947   // Puts the deferred blocks last.
 948   static void ComputeAssemblyOrder(InstructionBlocks* blocks);
 949
 950   InstructionSequence(Isolate* isolate, Zone* zone,
 951                       InstructionBlocks* instruction_blocks);
 952
 953   int NextVirtualRegister();
 954   int VirtualRegisterCount() const { return next_virtual_register_; }
 955
 956   const InstructionBlocks& instruction_blocks() const {
 957     return *instruction_blocks_;
 958   }
 959
 960   int InstructionBlockCount() const {
 961     return static_cast<int>(instruction_blocks_->size());
 962   }
 963
 964   InstructionBlock* InstructionBlockAt(RpoNumber rpo_number) {
 965     return instruction_blocks_->at(rpo_number.ToSize());
 966   }
 967
 968   int LastLoopInstructionIndex(const InstructionBlock* block) {
 969     return instruction_blocks_->at(block->loop_end().ToSize() - 1)
 970         ->last_instruction_index();
 971   }
 972
 973   const InstructionBlock* InstructionBlockAt(RpoNumber rpo_number) const {
 974     return instruction_blocks_->at(rpo_number.ToSize());
 975   }
 976
 977   const InstructionBlock* GetInstructionBlock(int instruction_index) const;
 978
 979   bool IsReference(int virtual_register) const;
 980   bool IsDouble(int virtual_register) const;
 981
 982   void MarkAsReference(int virtual_register);
 983   void MarkAsDouble(int virtual_register);
 984
 985   void AddGapMove(int index, InstructionOperand* from, InstructionOperand* to);
 986
 987   GapInstruction* GetBlockStart(RpoNumber rpo) const;
 988
 989   typedef InstructionDeque::const_iterator const_iterator;
 990   const_iterator begin() const { return instructions_.begin(); }
 991   const_iterator end() const { return instructions_.end(); }
 992   const InstructionDeque& instructions() const { return instructions_; }
 993
 994   GapInstruction* GapAt(int index) const {
 995     return GapInstruction::cast(InstructionAt(index));
 996   }
 997   bool IsGapAt(int index) const { return InstructionAt(index)->IsGapMoves(); }
 998   Instruction* InstructionAt(int index) const {
 999     DCHECK(index >= 0);
1000     DCHECK(index < static_cast<int>(instructions_.size()));
1001     return instructions_[index];
1002   }
1003
1004   Isolate* isolate() const { return isolate_; }
1005   const PointerMapDeque* pointer_maps() const { return &pointer_maps_; }
1006   Zone* zone() const { return zone_; }
1007
1008   // Used by the instruction selector while adding instructions.
1009   int AddInstruction(Instruction* instr);
1010   void StartBlock(RpoNumber rpo);
1011   void EndBlock(RpoNumber rpo);
1012
1013   int AddConstant(int virtual_register, Constant constant) {
1014     // TODO(titzer): allow RPO numbers as constants?
1015     DCHECK(constant.type() != Constant::kRpoNumber);
1016     DCHECK(virtual_register >= 0 && virtual_register < next_virtual_register_);
1017     DCHECK(constants_.find(virtual_register) == constants_.end());
1018     constants_.insert(std::make_pair(virtual_register, constant));
1019     return virtual_register;
1020   }
1021   Constant GetConstant(int virtual_register) const {
1022     ConstantMap::const_iterator it = constants_.find(virtual_register);
1023     DCHECK(it != constants_.end());
1024     DCHECK_EQ(virtual_register, it->first);
1025     return it->second;
1026   }
1027
1028   typedef ZoneVector<Constant> Immediates;
1029   Immediates& immediates() { return immediates_; }
1030
1031   int AddImmediate(Constant constant) {
1032     int index = static_cast<int>(immediates_.size());
1033     immediates_.push_back(constant);
1034     return index;
1035   }
1036   Constant GetImmediate(int index) const {
1037     DCHECK(index >= 0);
1038     DCHECK(index < static_cast<int>(immediates_.size()));
1039     return immediates_[index];
1040   }
1041
1042   class StateId {
1043    public:
1044     static StateId FromInt(int id) { return StateId(id); }
1045     int ToInt() const { return id_; }
1046
1047    private:
1048     explicit StateId(int id) : id_(id) {}
1049     int id_;
1050   };
1051
1052   StateId AddFrameStateDescriptor(FrameStateDescriptor* descriptor);
1053   FrameStateDescriptor* GetFrameStateDescriptor(StateId deoptimization_id);
1054   int GetFrameStateDescriptorCount();
1055
1056   RpoNumber InputRpo(Instruction* instr, size_t index) {
1057     InstructionOperand* operand = instr->InputAt(index);
1058     Constant constant = operand->IsImmediate() ? GetImmediate(operand->index())
1059                                                : GetConstant(operand->index());
1060     return constant.ToRpoNumber();
1061   }
1062
1063  private:
1064   friend std::ostream& operator<<(std::ostream& os,
1065                                   const PrintableInstructionSequence& code);
1066
1067   typedef std::set<int, std::less<int>, ZoneIntAllocator> VirtualRegisterSet;
1068
1069   Isolate* isolate_;
1070   Zone* const zone_;
1071   InstructionBlocks* const instruction_blocks_;
1072   IntVector block_starts_;
1073   ConstantMap constants_;
1074   Immediates immediates_;
1075   InstructionDeque instructions_;
1076   int next_virtual_register_;
1077   PointerMapDeque pointer_maps_;
1078   VirtualRegisterSet doubles_;
1079   VirtualRegisterSet references_;
1080   DeoptimizationVector deoptimization_entries_;
1081
1082   DISALLOW_COPY_AND_ASSIGN(InstructionSequence);
1083 };
1084
1085
1086 struct PrintableInstructionSequence {
1087   const RegisterConfiguration* register_configuration_;
1088   const InstructionSequence* sequence_;
1089 };
1090
1091
1092 std::ostream& operator<<(std::ostream& os,
1093                          const PrintableInstructionSequence& code);
1094
1095 }  // namespace compiler
1096 }  // namespace internal
1097 }  // namespace v8
1098
1099 #endif  // V8_COMPILER_INSTRUCTION_H_