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