instruction.h 54.5 KB
Newer Older
1 2 3 4 5 6 7 8
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_INSTRUCTION_H_
#define V8_COMPILER_INSTRUCTION_H_

#include <deque>
9
#include <iosfwd>
10 11 12
#include <map>
#include <set>

13
#include "src/base/compiler-specific.h"
14 15 16 17
#include "src/compiler/common-operator.h"
#include "src/compiler/frame.h"
#include "src/compiler/instruction-codes.h"
#include "src/compiler/opcodes.h"
18
#include "src/globals.h"
19 20
#include "src/macro-assembler.h"
#include "src/register-configuration.h"
21
#include "src/zone/zone-allocator.h"
22 23 24

namespace v8 {
namespace internal {
25 26 27

class SourcePosition;

28 29
namespace compiler {

30
class Schedule;
31
class SourcePositionTable;
32

33
class V8_EXPORT_PRIVATE InstructionOperand {
34
 public:
35 36
  static const int kInvalidVirtualRegister = -1;

37 38
  // TODO(dcarney): recover bit. INVALID can be represented as UNALLOCATED with
  // kInvalidVirtualRegister and some DCHECKS.
39 40 41 42 43 44 45 46 47 48 49
  enum Kind {
    INVALID,
    UNALLOCATED,
    CONSTANT,
    IMMEDIATE,
    // Location operand kinds.
    EXPLICIT,
    ALLOCATED,
    FIRST_LOCATION_OPERAND_KIND = EXPLICIT
    // Location operand kinds must be last.
  };
50

51
  InstructionOperand() : InstructionOperand(INVALID) {}
52

53
  Kind kind() const { return KindField::decode(value_); }
54

55
#define INSTRUCTION_OPERAND_PREDICATE(name, type) \
56
  bool Is##name() const { return kind() == type; }
57
  INSTRUCTION_OPERAND_PREDICATE(Invalid, INVALID)
58 59
  // UnallocatedOperands are place-holder operands created before register
  // allocation. They later are assigned registers and become AllocatedOperands.
60
  INSTRUCTION_OPERAND_PREDICATE(Unallocated, UNALLOCATED)
61 62 63 64
  // Constant operands participate in register allocation. They are allocated to
  // registers but have a special "spilling" behavior. When a ConstantOperand
  // value must be rematerialized, it is loaded from an immediate constant
  // rather from an unspilled slot.
65
  INSTRUCTION_OPERAND_PREDICATE(Constant, CONSTANT)
66 67 68
  // ImmediateOperands do not participate in register allocation and are only
  // embedded directly in instructions, e.g. small integers and on some
  // platforms Objects.
69
  INSTRUCTION_OPERAND_PREDICATE(Immediate, IMMEDIATE)
70 71 72 73 74 75 76
  // ExplicitOperands do not participate in register allocation. They are
  // created by the instruction selector for direct access to registers and
  // stack slots, completely bypassing the register allocator. They are never
  // associated with a virtual register
  INSTRUCTION_OPERAND_PREDICATE(Explicit, EXPLICIT)
  // AllocatedOperands are registers or stack slots that are assigned by the
  // register allocator and are always associated with a virtual register.
77
  INSTRUCTION_OPERAND_PREDICATE(Allocated, ALLOCATED)
78
#undef INSTRUCTION_OPERAND_PREDICATE
79

80 81 82
  inline bool IsAnyLocationOperand() const;
  inline bool IsLocationOperand() const;
  inline bool IsFPLocationOperand() const;
83
  inline bool IsAnyRegister() const;
84
  inline bool IsRegister() const;
85 86
  inline bool IsFPRegister() const;
  inline bool IsFloatRegister() const;
87
  inline bool IsDoubleRegister() const;
88
  inline bool IsSimd128Register() const;
89
  inline bool IsAnyStackSlot() const;
90
  inline bool IsStackSlot() const;
91 92
  inline bool IsFPStackSlot() const;
  inline bool IsFloatStackSlot() const;
93
  inline bool IsDoubleStackSlot() const;
94
  inline bool IsSimd128StackSlot() const;
95

96 97 98 99
  template <typename SubKindOperand>
  static SubKindOperand* New(Zone* zone, const SubKindOperand& op) {
    void* buffer = zone->New(sizeof(op));
    return new (buffer) SubKindOperand(op);
100 101
  }

102 103 104
  static void ReplaceWith(InstructionOperand* dest,
                          const InstructionOperand* src) {
    *dest = *src;
105 106
  }

107 108 109 110 111 112 113 114
  bool Equals(const InstructionOperand& that) const {
    return this->value_ == that.value_;
  }

  bool Compare(const InstructionOperand& that) const {
    return this->value_ < that.value_;
  }

115 116
  bool EqualsCanonicalized(const InstructionOperand& that) const {
    return this->GetCanonicalizedValue() == that.GetCanonicalizedValue();
117 118
  }

119 120
  bool CompareCanonicalized(const InstructionOperand& that) const {
    return this->GetCanonicalizedValue() < that.GetCanonicalizedValue();
121 122
  }

123
  bool InterferesWith(const InstructionOperand& other) const;
124

125 126 127
  // APIs to aid debugging. For general-stream APIs, use operator<<
  void Print(const RegisterConfiguration* config) const;
  void Print() const;
128

129
 protected:
130
  explicit InstructionOperand(Kind kind) : value_(KindField::encode(kind)) {}
131

132
  inline uint64_t GetCanonicalizedValue() const;
133

134
  class KindField : public BitField64<Kind, 0, 3> {};
135 136

  uint64_t value_;
137 138
};

139

140 141 142
typedef ZoneVector<InstructionOperand> InstructionOperandVector;


143 144
struct PrintableInstructionOperand {
  const RegisterConfiguration* register_configuration_;
145
  InstructionOperand op_;
146 147
};

148

149 150
std::ostream& operator<<(std::ostream& os,
                         const PrintableInstructionOperand& op);
151

152

153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
#define INSTRUCTION_OPERAND_CASTS(OperandType, OperandKind)      \
                                                                 \
  static OperandType* cast(InstructionOperand* op) {             \
    DCHECK_EQ(OperandKind, op->kind());                          \
    return static_cast<OperandType*>(op);                        \
  }                                                              \
                                                                 \
  static const OperandType* cast(const InstructionOperand* op) { \
    DCHECK_EQ(OperandKind, op->kind());                          \
    return static_cast<const OperandType*>(op);                  \
  }                                                              \
                                                                 \
  static OperandType cast(const InstructionOperand& op) {        \
    DCHECK_EQ(OperandKind, op.kind());                           \
    return *static_cast<const OperandType*>(&op);                \
  }

170 171 172 173 174 175 176 177
class UnallocatedOperand : public InstructionOperand {
 public:
  enum BasicPolicy { FIXED_SLOT, EXTENDED_POLICY };

  enum ExtendedPolicy {
    NONE,
    ANY,
    FIXED_REGISTER,
178
    FIXED_FP_REGISTER,
179
    MUST_HAVE_REGISTER,
180
    MUST_HAVE_SLOT,
181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
    SAME_AS_FIRST_INPUT
  };

  // Lifetime of operand inside the instruction.
  enum Lifetime {
    // USED_AT_START operand is guaranteed to be live only at
    // instruction start. Register allocator is free to assign the same register
    // to some other operand used inside instruction (i.e. temporary or
    // output).
    USED_AT_START,

    // USED_AT_END operand is treated as live until the end of
    // instruction. This means that register allocator will not reuse it's
    // register for any other operand inside instruction.
    USED_AT_END
  };

198
  UnallocatedOperand(ExtendedPolicy policy, int virtual_register)
199
      : UnallocatedOperand(virtual_register) {
200 201 202 203 204
    value_ |= BasicPolicyField::encode(EXTENDED_POLICY);
    value_ |= ExtendedPolicyField::encode(policy);
    value_ |= LifetimeField::encode(USED_AT_END);
  }

205
  UnallocatedOperand(BasicPolicy policy, int index, int virtual_register)
206
      : UnallocatedOperand(virtual_register) {
207
    DCHECK(policy == FIXED_SLOT);
208
    value_ |= BasicPolicyField::encode(policy);
209
    value_ |= static_cast<int64_t>(index) << FixedSlotIndexField::kShift;
210
    DCHECK(this->fixed_slot_index() == index);
211 212
  }

213
  UnallocatedOperand(ExtendedPolicy policy, int index, int virtual_register)
214
      : UnallocatedOperand(virtual_register) {
215
    DCHECK(policy == FIXED_REGISTER || policy == FIXED_FP_REGISTER);
216 217 218 219 220 221
    value_ |= BasicPolicyField::encode(EXTENDED_POLICY);
    value_ |= ExtendedPolicyField::encode(policy);
    value_ |= LifetimeField::encode(USED_AT_END);
    value_ |= FixedRegisterField::encode(index);
  }

222 223
  UnallocatedOperand(ExtendedPolicy policy, Lifetime lifetime,
                     int virtual_register)
224
      : UnallocatedOperand(virtual_register) {
225 226 227 228 229
    value_ |= BasicPolicyField::encode(EXTENDED_POLICY);
    value_ |= ExtendedPolicyField::encode(policy);
    value_ |= LifetimeField::encode(lifetime);
  }

230 231 232 233 234 235
  UnallocatedOperand(int reg_id, int slot_id, int virtual_register)
      : UnallocatedOperand(FIXED_REGISTER, reg_id, virtual_register) {
    value_ |= HasSecondaryStorageField::encode(true);
    value_ |= SecondaryStorageField::encode(slot_id);
  }

236 237 238 239 240 241 242
  // Predicates for the operand policy.
  bool HasAnyPolicy() const {
    return basic_policy() == EXTENDED_POLICY && extended_policy() == ANY;
  }
  bool HasFixedPolicy() const {
    return basic_policy() == FIXED_SLOT ||
           extended_policy() == FIXED_REGISTER ||
243
           extended_policy() == FIXED_FP_REGISTER;
244 245 246 247 248
  }
  bool HasRegisterPolicy() const {
    return basic_policy() == EXTENDED_POLICY &&
           extended_policy() == MUST_HAVE_REGISTER;
  }
249 250 251 252
  bool HasSlotPolicy() const {
    return basic_policy() == EXTENDED_POLICY &&
           extended_policy() == MUST_HAVE_SLOT;
  }
253 254 255 256 257 258 259 260 261
  bool HasSameAsInputPolicy() const {
    return basic_policy() == EXTENDED_POLICY &&
           extended_policy() == SAME_AS_FIRST_INPUT;
  }
  bool HasFixedSlotPolicy() const { return basic_policy() == FIXED_SLOT; }
  bool HasFixedRegisterPolicy() const {
    return basic_policy() == EXTENDED_POLICY &&
           extended_policy() == FIXED_REGISTER;
  }
262
  bool HasFixedFPRegisterPolicy() const {
263
    return basic_policy() == EXTENDED_POLICY &&
264
           extended_policy() == FIXED_FP_REGISTER;
265
  }
266 267 268 269 270 271 272 273 274
  bool HasSecondaryStorage() const {
    return basic_policy() == EXTENDED_POLICY &&
           extended_policy() == FIXED_REGISTER &&
           HasSecondaryStorageField::decode(value_);
  }
  int GetSecondaryStorage() const {
    DCHECK(HasSecondaryStorage());
    return SecondaryStorageField::decode(value_);
  }
275 276

  // [basic_policy]: Distinguish between FIXED_SLOT and all other policies.
277 278 279 280
  BasicPolicy basic_policy() const {
    DCHECK_EQ(UNALLOCATED, kind());
    return BasicPolicyField::decode(value_);
  }
281 282 283

  // [extended_policy]: Only for non-FIXED_SLOT. The finer-grained policy.
  ExtendedPolicy extended_policy() const {
284
    DCHECK(basic_policy() == EXTENDED_POLICY);
285 286 287 288 289
    return ExtendedPolicyField::decode(value_);
  }

  // [fixed_slot_index]: Only for FIXED_SLOT.
  int fixed_slot_index() const {
290
    DCHECK(HasFixedSlotPolicy());
291
    return static_cast<int>(static_cast<int64_t>(value_) >>
292
                            FixedSlotIndexField::kShift);
293 294
  }

295
  // [fixed_register_index]: Only for FIXED_REGISTER or FIXED_FP_REGISTER.
296
  int fixed_register_index() const {
297
    DCHECK(HasFixedRegisterPolicy() || HasFixedFPRegisterPolicy());
298 299 300 301
    return FixedRegisterField::decode(value_);
  }

  // [virtual_register]: The virtual register ID for this operand.
302 303
  int32_t virtual_register() const {
    DCHECK_EQ(UNALLOCATED, kind());
304
    return static_cast<int32_t>(VirtualRegisterField::decode(value_));
305 306 307 308 309
  }

  // TODO(dcarney): remove this.
  void set_virtual_register(int32_t id) {
    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 317
    return LifetimeField::decode(value_) == USED_AT_START;
  }
318 319

  INSTRUCTION_OPERAND_CASTS(UnallocatedOperand, UNALLOCATED);
320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353

  // The encoding used for UnallocatedOperand operands depends on the policy
  // that is
  // stored within the operand. The FIXED_SLOT policy uses a compact encoding
  // because it accommodates a larger pay-load.
  //
  // For FIXED_SLOT policy:
  //     +------------------------------------------------+
  //     |      slot_index   | 0 | virtual_register | 001 |
  //     +------------------------------------------------+
  //
  // For all other (extended) policies:
  //     +-----------------------------------------------------+
  //     |  reg_index  | L | PPP |  1 | virtual_register | 001 |
  //     +-----------------------------------------------------+
  //     L ... Lifetime
  //     P ... Policy
  //
  // The slot index is a signed value which requires us to decode it manually
  // instead of using the BitField utility class.

  STATIC_ASSERT(KindField::kSize == 3);

  class VirtualRegisterField : public BitField64<uint32_t, 3, 32> {};

  // BitFields for all unallocated operands.
  class BasicPolicyField : public BitField64<BasicPolicy, 35, 1> {};

  // BitFields specific to BasicPolicy::FIXED_SLOT.
  class FixedSlotIndexField : public BitField64<int, 36, 28> {};

  // BitFields specific to BasicPolicy::EXTENDED_POLICY.
  class ExtendedPolicyField : public BitField64<ExtendedPolicy, 36, 3> {};
  class LifetimeField : public BitField64<Lifetime, 39, 1> {};
354 355 356
  class HasSecondaryStorageField : public BitField64<bool, 40, 1> {};
  class FixedRegisterField : public BitField64<int, 41, 6> {};
  class SecondaryStorageField : public BitField64<int, 47, 3> {};
357 358 359 360 361 362 363

 private:
  explicit UnallocatedOperand(int virtual_register)
      : InstructionOperand(UNALLOCATED) {
    value_ |=
        VirtualRegisterField::encode(static_cast<uint32_t>(virtual_register));
  }
364 365 366
};


367 368 369
class ConstantOperand : public InstructionOperand {
 public:
  explicit ConstantOperand(int virtual_register)
370 371 372 373
      : InstructionOperand(CONSTANT) {
    value_ |=
        VirtualRegisterField::encode(static_cast<uint32_t>(virtual_register));
  }
374 375 376 377 378 379 380 381 382

  int32_t virtual_register() const {
    return static_cast<int32_t>(VirtualRegisterField::decode(value_));
  }

  static ConstantOperand* New(Zone* zone, int virtual_register) {
    return InstructionOperand::New(zone, ConstantOperand(virtual_register));
  }

383
  INSTRUCTION_OPERAND_CASTS(ConstantOperand, CONSTANT);
384 385 386

  STATIC_ASSERT(KindField::kSize == 3);
  class VirtualRegisterField : public BitField64<uint32_t, 3, 32> {};
387 388 389 390 391
};


class ImmediateOperand : public InstructionOperand {
 public:
392 393 394 395 396 397
  enum ImmediateType { INLINE, INDEXED };

  explicit ImmediateOperand(ImmediateType type, int32_t value)
      : InstructionOperand(IMMEDIATE) {
    value_ |= TypeField::encode(type);
    value_ |= static_cast<int64_t>(value) << ValueField::kShift;
398
  }
399

400 401 402 403 404 405 406 407 408 409
  ImmediateType type() const { return TypeField::decode(value_); }

  int32_t inline_value() const {
    DCHECK_EQ(INLINE, type());
    return static_cast<int64_t>(value_) >> ValueField::kShift;
  }

  int32_t indexed_value() const {
    DCHECK_EQ(INDEXED, type());
    return static_cast<int64_t>(value_) >> ValueField::kShift;
410 411
  }

412 413
  static ImmediateOperand* New(Zone* zone, ImmediateType type, int32_t value) {
    return InstructionOperand::New(zone, ImmediateOperand(type, value));
414 415
  }

416
  INSTRUCTION_OPERAND_CASTS(ImmediateOperand, IMMEDIATE);
417 418

  STATIC_ASSERT(KindField::kSize == 3);
419 420
  class TypeField : public BitField64<ImmediateType, 3, 1> {};
  class ValueField : public BitField64<int32_t, 32, 32> {};
421 422 423
};


424
class LocationOperand : public InstructionOperand {
425
 public:
426
  enum LocationKind { REGISTER, STACK_SLOT };
427

428 429
  LocationOperand(InstructionOperand::Kind operand_kind,
                  LocationOperand::LocationKind location_kind,
430
                  MachineRepresentation rep, int index)
431 432
      : InstructionOperand(operand_kind) {
    DCHECK_IMPLIES(location_kind == REGISTER, index >= 0);
433
    DCHECK(IsSupportedRepresentation(rep));
434
    value_ |= LocationKindField::encode(location_kind);
435
    value_ |= RepresentationField::encode(rep);
436
    value_ |= static_cast<int64_t>(index) << IndexField::kShift;
437 438
  }

439
  int index() const {
440
    DCHECK(IsStackSlot() || IsFPStackSlot());
441 442 443
    return static_cast<int64_t>(value_) >> IndexField::kShift;
  }

444 445 446 447 448
  int register_code() const {
    DCHECK(IsRegister() || IsFPRegister());
    return static_cast<int64_t>(value_) >> IndexField::kShift;
  }

449
  Register GetRegister() const {
450
    DCHECK(IsRegister());
451
    return Register::from_code(register_code());
452 453
  }

454 455
  FloatRegister GetFloatRegister() const {
    DCHECK(IsFloatRegister());
456
    return FloatRegister::from_code(register_code());
457 458
  }

459
  DoubleRegister GetDoubleRegister() const {
460 461 462
    // On platforms where FloatRegister, DoubleRegister, and Simd128Register
    // are all the same type, it's convenient to treat everything as a
    // DoubleRegister, so be lax about type checking here.
463
    DCHECK(IsFPRegister());
464
    return DoubleRegister::from_code(register_code());
465 466
  }

467 468
  Simd128Register GetSimd128Register() const {
    DCHECK(IsSimd128Register());
469
    return Simd128Register::from_code(register_code());
470 471
  }

472 473
  LocationKind location_kind() const {
    return LocationKindField::decode(value_);
474 475
  }

476 477 478
  MachineRepresentation representation() const {
    return RepresentationField::decode(value_);
  }
479

480 481 482 483 484 485
  static bool IsSupportedRepresentation(MachineRepresentation rep) {
    switch (rep) {
      case MachineRepresentation::kWord32:
      case MachineRepresentation::kWord64:
      case MachineRepresentation::kFloat32:
      case MachineRepresentation::kFloat64:
486
      case MachineRepresentation::kSimd128:
487 488
      case MachineRepresentation::kTaggedSigned:
      case MachineRepresentation::kTaggedPointer:
489
      case MachineRepresentation::kTagged:
490
        return true;
491 492 493 494
      case MachineRepresentation::kBit:
      case MachineRepresentation::kWord8:
      case MachineRepresentation::kWord16:
      case MachineRepresentation::kNone:
495 496
        return false;
    }
497 498
    UNREACHABLE();
    return false;
499 500
  }

501
  static LocationOperand* cast(InstructionOperand* op) {
502
    DCHECK(op->IsAnyLocationOperand());
503 504 505 506
    return static_cast<LocationOperand*>(op);
  }

  static const LocationOperand* cast(const InstructionOperand* op) {
507
    DCHECK(op->IsAnyLocationOperand());
508 509 510 511
    return static_cast<const LocationOperand*>(op);
  }

  static LocationOperand cast(const InstructionOperand& op) {
512
    DCHECK(op.IsAnyLocationOperand());
513 514
    return *static_cast<const LocationOperand*>(&op);
  }
515

516
  STATIC_ASSERT(KindField::kSize == 3);
517
  class LocationKindField : public BitField64<LocationKind, 3, 2> {};
518
  class RepresentationField : public BitField64<MachineRepresentation, 5, 8> {};
519
  class IndexField : public BitField64<int32_t, 35, 29> {};
520
};
521

522 523
class V8_EXPORT_PRIVATE ExplicitOperand
    : public NON_EXPORTED_BASE(LocationOperand) {
524
 public:
525
  ExplicitOperand(LocationKind kind, MachineRepresentation rep, int index);
526 527

  static ExplicitOperand* New(Zone* zone, LocationKind kind,
528 529
                              MachineRepresentation rep, int index) {
    return InstructionOperand::New(zone, ExplicitOperand(kind, rep, index));
530 531 532 533 534 535 536 537
  }

  INSTRUCTION_OPERAND_CASTS(ExplicitOperand, EXPLICIT);
};


class AllocatedOperand : public LocationOperand {
 public:
538 539
  AllocatedOperand(LocationKind kind, MachineRepresentation rep, int index)
      : LocationOperand(ALLOCATED, kind, rep, index) {}
540 541

  static AllocatedOperand* New(Zone* zone, LocationKind kind,
542 543
                               MachineRepresentation rep, int index) {
    return InstructionOperand::New(zone, AllocatedOperand(kind, rep, index));
544 545 546 547 548 549
  }

  INSTRUCTION_OPERAND_CASTS(AllocatedOperand, ALLOCATED);
};


550 551
#undef INSTRUCTION_OPERAND_CASTS

552 553 554 555 556 557 558 559 560 561 562 563 564
bool InstructionOperand::IsAnyLocationOperand() const {
  return this->kind() >= FIRST_LOCATION_OPERAND_KIND;
}

bool InstructionOperand::IsLocationOperand() const {
  return IsAnyLocationOperand() &&
         !IsFloatingPoint(LocationOperand::cast(this)->representation());
}

bool InstructionOperand::IsFPLocationOperand() const {
  return IsAnyLocationOperand() &&
         IsFloatingPoint(LocationOperand::cast(this)->representation());
}
565

566
bool InstructionOperand::IsAnyRegister() const {
567
  return IsAnyLocationOperand() &&
568
         LocationOperand::cast(this)->location_kind() ==
569 570 571 572 573 574
             LocationOperand::REGISTER;
}


bool InstructionOperand::IsRegister() const {
  return IsAnyRegister() &&
575
         !IsFloatingPoint(LocationOperand::cast(this)->representation());
576
}
577

578
bool InstructionOperand::IsFPRegister() const {
579
  return IsAnyRegister() &&
580
         IsFloatingPoint(LocationOperand::cast(this)->representation());
581 582
}

583 584 585 586 587 588 589 590 591 592 593 594
bool InstructionOperand::IsFloatRegister() const {
  return IsAnyRegister() &&
         LocationOperand::cast(this)->representation() ==
             MachineRepresentation::kFloat32;
}

bool InstructionOperand::IsDoubleRegister() const {
  return IsAnyRegister() &&
         LocationOperand::cast(this)->representation() ==
             MachineRepresentation::kFloat64;
}

595 596 597 598 599 600
bool InstructionOperand::IsSimd128Register() const {
  return IsAnyRegister() &&
         LocationOperand::cast(this)->representation() ==
             MachineRepresentation::kSimd128;
}

601 602
bool InstructionOperand::IsAnyStackSlot() const {
  return IsAnyLocationOperand() &&
603
         LocationOperand::cast(this)->location_kind() ==
604 605 606 607 608
             LocationOperand::STACK_SLOT;
}

bool InstructionOperand::IsStackSlot() const {
  return IsAnyStackSlot() &&
609
         !IsFloatingPoint(LocationOperand::cast(this)->representation());
610 611
}

612
bool InstructionOperand::IsFPStackSlot() const {
613
  return IsAnyStackSlot() &&
614
         IsFloatingPoint(LocationOperand::cast(this)->representation());
615
}
616

617
bool InstructionOperand::IsFloatStackSlot() const {
618
  return IsAnyLocationOperand() &&
619 620 621 622 623 624 625
         LocationOperand::cast(this)->location_kind() ==
             LocationOperand::STACK_SLOT &&
         LocationOperand::cast(this)->representation() ==
             MachineRepresentation::kFloat32;
}

bool InstructionOperand::IsDoubleStackSlot() const {
626
  return IsAnyLocationOperand() &&
627 628 629 630 631 632
         LocationOperand::cast(this)->location_kind() ==
             LocationOperand::STACK_SLOT &&
         LocationOperand::cast(this)->representation() ==
             MachineRepresentation::kFloat64;
}

633
bool InstructionOperand::IsSimd128StackSlot() const {
634
  return IsAnyLocationOperand() &&
635 636 637 638 639 640
         LocationOperand::cast(this)->location_kind() ==
             LocationOperand::STACK_SLOT &&
         LocationOperand::cast(this)->representation() ==
             MachineRepresentation::kSimd128;
}

641
uint64_t InstructionOperand::GetCanonicalizedValue() const {
642
  if (IsAnyLocationOperand()) {
643
    MachineRepresentation canonical = MachineRepresentation::kNone;
644
    if (IsFPRegister()) {
645 646 647 648 649 650 651 652
      if (kSimpleFPAliasing) {
        // We treat all FP register operands the same for simple aliasing.
        canonical = MachineRepresentation::kFloat64;
      } else {
        // We need to distinguish FP register operands of different reps when
        // aliasing is not simple (e.g. ARM).
        canonical = LocationOperand::cast(this)->representation();
      }
653
    }
654
    return InstructionOperand::KindField::update(
655
        LocationOperand::RepresentationField::update(this->value_, canonical),
656
        LocationOperand::EXPLICIT);
657 658 659 660 661 662 663 664
  }
  return this->value_;
}

// Required for maps that don't care about machine type.
struct CompareOperandModuloType {
  bool operator()(const InstructionOperand& a,
                  const InstructionOperand& b) const {
665
    return a.CompareCanonicalized(b);
666 667 668
  }
};

669 670
class V8_EXPORT_PRIVATE MoveOperands final
    : public NON_EXPORTED_BASE(ZoneObject) {
671
 public:
672 673 674 675 676
  MoveOperands(const InstructionOperand& source,
               const InstructionOperand& destination)
      : source_(source), destination_(destination) {
    DCHECK(!source.IsInvalid() && !destination.IsInvalid());
  }
677

678 679 680
  const InstructionOperand& source() const { return source_; }
  InstructionOperand& source() { return source_; }
  void set_source(const InstructionOperand& operand) { source_ = operand; }
681

682 683 684 685 686
  const InstructionOperand& destination() const { return destination_; }
  InstructionOperand& destination() { return destination_; }
  void set_destination(const InstructionOperand& operand) {
    destination_ = operand;
  }
687 688 689

  // The gap resolver marks moves as "in-progress" by clearing the
  // destination (but not the source).
690 691 692 693
  bool IsPending() const {
    return destination_.IsInvalid() && !source_.IsInvalid();
  }
  void SetPending() { destination_ = InstructionOperand(); }
694

695 696
  // A move is redundant if it's been eliminated or if its source and
  // destination are the same.
697
  bool IsRedundant() const {
698
    DCHECK_IMPLIES(!destination_.IsInvalid(), !destination_.IsConstant());
699
    return IsEliminated() || source_.EqualsCanonicalized(destination_);
700 701 702
  }

  // We clear both operands to indicate move that's been eliminated.
703
  void Eliminate() { source_ = destination_ = InstructionOperand(); }
704
  bool IsEliminated() const {
705 706
    DCHECK_IMPLIES(source_.IsInvalid(), destination_.IsInvalid());
    return source_.IsInvalid();
707 708
  }

709 710 711
  // APIs to aid debugging. For general-stream APIs, use operator<<
  void Print(const RegisterConfiguration* config) const;
  void Print() const;
712

713
 private:
714 715 716 717
  InstructionOperand source_;
  InstructionOperand destination_;

  DISALLOW_COPY_AND_ASSIGN(MoveOperands);
718 719
};

720 721 722 723 724 725 726 727 728

struct PrintableMoveOperands {
  const RegisterConfiguration* register_configuration_;
  const MoveOperands* move_operands_;
};


std::ostream& operator<<(std::ostream& os, const PrintableMoveOperands& mo);

729 730 731
class V8_EXPORT_PRIVATE ParallelMove final
    : public NON_EXPORTED_BASE(ZoneVector<MoveOperands *>),
      public NON_EXPORTED_BASE(ZoneObject) {
732
 public:
733 734 735
  explicit ParallelMove(Zone* zone) : ZoneVector<MoveOperands*>(zone) {
    reserve(4);
  }
736

737 738
  MoveOperands* AddMove(const InstructionOperand& from,
                        const InstructionOperand& to) {
739 740 741 742 743 744 745 746
    Zone* zone = get_allocator().zone();
    return AddMove(from, to, zone);
  }

  MoveOperands* AddMove(const InstructionOperand& from,
                        const InstructionOperand& to,
                        Zone* operand_allocation_zone) {
    MoveOperands* move = new (operand_allocation_zone) MoveOperands(from, to);
747 748
    push_back(move);
    return move;
749 750 751 752
  }

  bool IsRedundant() const;

dcarney's avatar
dcarney committed
753
  // Prepare this ParallelMove to insert move as if it happened in a subsequent
754 755 756 757
  // ParallelMove.  move->source() may be changed.  Any MoveOperands added to
  // to_eliminate must be Eliminated.
  void PrepareInsertAfter(MoveOperands* move,
                          ZoneVector<MoveOperands*>* to_eliminate) const;
dcarney's avatar
dcarney committed
758

759
 private:
760
  DISALLOW_COPY_AND_ASSIGN(ParallelMove);
761 762
};

763 764 765 766 767 768 769 770 771

struct PrintableParallelMove {
  const RegisterConfiguration* register_configuration_;
  const ParallelMove* parallel_move_;
};


std::ostream& operator<<(std::ostream& os, const PrintableParallelMove& pm);

772

773
class ReferenceMap final : public ZoneObject {
774
 public:
775 776 777 778 779
  explicit ReferenceMap(Zone* zone)
      : reference_operands_(8, zone), instruction_position_(-1) {}

  const ZoneVector<InstructionOperand>& reference_operands() const {
    return reference_operands_;
780 781 782 783
  }
  int instruction_position() const { return instruction_position_; }

  void set_instruction_position(int pos) {
784
    DCHECK(instruction_position_ == -1);
785 786 787
    instruction_position_ = pos;
  }

788
  void RecordReference(const AllocatedOperand& op);
789 790

 private:
791
  friend std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm);
792

793
  ZoneVector<InstructionOperand> reference_operands_;
794 795 796
  int instruction_position_;
};

797
std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm);
798

799 800
class InstructionBlock;

801
class V8_EXPORT_PRIVATE Instruction final {
802 803
 public:
  size_t OutputCount() const { return OutputCountField::decode(bit_field_); }
804 805 806 807 808
  const InstructionOperand* OutputAt(size_t i) const {
    DCHECK(i < OutputCount());
    return &operands_[i];
  }
  InstructionOperand* OutputAt(size_t i) {
809
    DCHECK(i < OutputCount());
810
    return &operands_[i];
811 812
  }

813
  bool HasOutput() const { return OutputCount() == 1; }
814 815
  const InstructionOperand* Output() const { return OutputAt(0); }
  InstructionOperand* Output() { return OutputAt(0); }
816

817
  size_t InputCount() const { return InputCountField::decode(bit_field_); }
818
  const InstructionOperand* InputAt(size_t i) const {
819
    DCHECK(i < InputCount());
820
    return &operands_[OutputCount() + i];
821
  }
822
  InstructionOperand* InputAt(size_t i) {
823
    DCHECK(i < InputCount());
824
    return &operands_[OutputCount() + i];
825
  }
826 827

  size_t TempCount() const { return TempCountField::decode(bit_field_); }
828 829 830 831 832
  const InstructionOperand* TempAt(size_t i) const {
    DCHECK(i < TempCount());
    return &operands_[OutputCount() + InputCount() + i];
  }
  InstructionOperand* TempAt(size_t i) {
833
    DCHECK(i < TempCount());
834
    return &operands_[OutputCount() + InputCount() + i];
835 836 837 838 839 840 841 842 843 844 845 846 847
  }

  InstructionCode opcode() const { return opcode_; }
  ArchOpcode arch_opcode() const { return ArchOpcodeField::decode(opcode()); }
  AddressingMode addressing_mode() const {
    return AddressingModeField::decode(opcode());
  }
  FlagsMode flags_mode() const { return FlagsModeField::decode(opcode()); }
  FlagsCondition flags_condition() const {
    return FlagsConditionField::decode(opcode());
  }

  static Instruction* New(Zone* zone, InstructionCode opcode) {
848
    return New(zone, opcode, 0, nullptr, 0, nullptr, 0, nullptr);
849 850 851
  }

  static Instruction* New(Zone* zone, InstructionCode opcode,
852 853 854
                          size_t output_count, InstructionOperand* outputs,
                          size_t input_count, InstructionOperand* inputs,
                          size_t temp_count, InstructionOperand* temps) {
855
    DCHECK(opcode >= 0);
856 857 858
    DCHECK(output_count == 0 || outputs != nullptr);
    DCHECK(input_count == 0 || inputs != nullptr);
    DCHECK(temp_count == 0 || temps != nullptr);
859 860 861
    // TODO(jarin/mstarzinger): Handle this gracefully. See crbug.com/582702.
    CHECK(InputCountField::is_valid(input_count));

862 863 864
    size_t total_extra_ops = output_count + input_count + temp_count;
    if (total_extra_ops != 0) total_extra_ops--;
    int size = static_cast<int>(
865 866
        RoundUp(sizeof(Instruction), sizeof(InstructionOperand)) +
        total_extra_ops * sizeof(InstructionOperand));
867 868 869 870 871 872 873 874 875
    return new (zone->New(size)) Instruction(
        opcode, output_count, outputs, input_count, inputs, temp_count, temps);
  }

  Instruction* MarkAsCall() {
    bit_field_ = IsCallField::update(bit_field_, true);
    return this;
  }
  bool IsCall() const { return IsCallField::decode(bit_field_); }
876
  bool NeedsReferenceMap() const { return IsCall(); }
877
  bool HasReferenceMap() const { return reference_map_ != nullptr; }
878 879 880 881

  bool ClobbersRegisters() const { return IsCall(); }
  bool ClobbersTemps() const { return IsCall(); }
  bool ClobbersDoubleRegisters() const { return IsCall(); }
882
  ReferenceMap* reference_map() const { return reference_map_; }
883

884 885 886 887
  void set_reference_map(ReferenceMap* map) {
    DCHECK(NeedsReferenceMap());
    DCHECK(!reference_map_);
    reference_map_ = map;
888 889
  }

890 891 892
  void OverwriteWithNop() {
    opcode_ = ArchOpcodeField::encode(kArchNop);
    bit_field_ = 0;
893
    reference_map_ = nullptr;
894 895
  }

896
  bool IsNop() const { return arch_opcode() == kArchNop; }
897

898 899 900 901 902 903 904 905 906 907
  bool IsDeoptimizeCall() const {
    return arch_opcode() == ArchOpcode::kArchDeoptimize ||
           FlagsModeField::decode(opcode()) == kFlags_deoptimize;
  }

  bool IsJump() const { return arch_opcode() == ArchOpcode::kArchJmp; }
  bool IsRet() const { return arch_opcode() == ArchOpcode::kArchRet; }
  bool IsTailCall() const {
    return arch_opcode() == ArchOpcode::kArchTailCallCodeObject ||
           arch_opcode() == ArchOpcode::kArchTailCallCodeObjectFromJSFunction ||
908 909
           arch_opcode() == ArchOpcode::kArchTailCallJSFunctionFromJSFunction ||
           arch_opcode() == ArchOpcode::kArchTailCallAddress;
910 911 912 913 914
  }
  bool IsThrow() const {
    return arch_opcode() == ArchOpcode::kArchThrowTerminator;
  }

915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941
  enum GapPosition {
    START,
    END,
    FIRST_GAP_POSITION = START,
    LAST_GAP_POSITION = END
  };

  ParallelMove* GetOrCreateParallelMove(GapPosition pos, Zone* zone) {
    if (parallel_moves_[pos] == nullptr) {
      parallel_moves_[pos] = new (zone) ParallelMove(zone);
    }
    return parallel_moves_[pos];
  }

  ParallelMove* GetParallelMove(GapPosition pos) {
    return parallel_moves_[pos];
  }

  const ParallelMove* GetParallelMove(GapPosition pos) const {
    return parallel_moves_[pos];
  }

  bool AreMovesRedundant() const;

  ParallelMove* const* parallel_moves() const { return &parallel_moves_[0]; }
  ParallelMove** parallel_moves() { return &parallel_moves_[0]; }

942 943 944 945 946 947 948 949 950
  // The block_id may be invalidated in JumpThreading. It is only important for
  // register allocation, to avoid searching for blocks from instruction
  // indexes.
  InstructionBlock* block() const { return block_; }
  void set_block(InstructionBlock* block) {
    DCHECK_NOT_NULL(block);
    block_ = block;
  }

951 952 953
  // APIs to aid debugging. For general-stream APIs, use operator<<
  void Print(const RegisterConfiguration* config) const;
  void Print() const;
954

955 956 957 958 959 960 961 962
  typedef BitField<size_t, 0, 8> OutputCountField;
  typedef BitField<size_t, 8, 16> InputCountField;
  typedef BitField<size_t, 24, 6> TempCountField;

  static const size_t kMaxOutputCount = OutputCountField::kMax;
  static const size_t kMaxInputCount = InputCountField::kMax;
  static const size_t kMaxTempCount = TempCountField::kMax;

963
 private:
964
  explicit Instruction(InstructionCode opcode);
965

966
  Instruction(InstructionCode opcode, size_t output_count,
967 968 969
              InstructionOperand* outputs, size_t input_count,
              InstructionOperand* inputs, size_t temp_count,
              InstructionOperand* temps);
970 971 972 973 974

  typedef BitField<bool, 30, 1> IsCallField;

  InstructionCode opcode_;
  uint32_t bit_field_;
975
  ParallelMove* parallel_moves_[2];
976
  ReferenceMap* reference_map_;
977
  InstructionBlock* block_;
978
  InstructionOperand operands_[1];
979 980

  DISALLOW_COPY_AND_ASSIGN(Instruction);
981 982
};

983 984 985 986 987 988 989

struct PrintableInstruction {
  const RegisterConfiguration* register_configuration_;
  const Instruction* instr_;
};
std::ostream& operator<<(std::ostream& os, const PrintableInstruction& instr);

990

991
class RpoNumber final {
992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010
 public:
  static const int kInvalidRpoNumber = -1;
  int ToInt() const {
    DCHECK(IsValid());
    return index_;
  }
  size_t ToSize() const {
    DCHECK(IsValid());
    return static_cast<size_t>(index_);
  }
  bool IsValid() const { return index_ >= 0; }
  static RpoNumber FromInt(int index) { return RpoNumber(index); }
  static RpoNumber Invalid() { return RpoNumber(kInvalidRpoNumber); }

  bool IsNext(const RpoNumber other) const {
    DCHECK(IsValid());
    return other.index_ == this->index_ + 1;
  }

1011 1012 1013 1014 1015 1016 1017
  // Comparison operators.
  bool operator==(RpoNumber other) const { return index_ == other.index_; }
  bool operator!=(RpoNumber other) const { return index_ != other.index_; }
  bool operator>(RpoNumber other) const { return index_ > other.index_; }
  bool operator<(RpoNumber other) const { return index_ < other.index_; }
  bool operator<=(RpoNumber other) const { return index_ <= other.index_; }
  bool operator>=(RpoNumber other) const { return index_ >= other.index_; }
1018 1019 1020 1021 1022 1023 1024 1025 1026

 private:
  explicit RpoNumber(int32_t index) : index_(index) {}
  int32_t index_;
};


std::ostream& operator<<(std::ostream&, const RpoNumber&);

1027
class V8_EXPORT_PRIVATE Constant final {
1028
 public:
1029 1030 1031 1032 1033 1034
  enum Type {
    kInt32,
    kInt64,
    kFloat32,
    kFloat64,
    kExternalReference,
1035 1036
    kHeapObject,
    kRpoNumber
1037
  };
1038

1039
  explicit Constant(int32_t v);
1040
  explicit Constant(int64_t v) : type_(kInt64), value_(v) {}
1041
  explicit Constant(float v) : type_(kFloat32), value_(bit_cast<int32_t>(v)) {}
1042
  explicit Constant(double v) : type_(kFloat64), value_(bit_cast<int64_t>(v)) {}
1043
  explicit Constant(ExternalReference ref)
1044
      : type_(kExternalReference), value_(bit_cast<intptr_t>(ref)) {}
1045
  explicit Constant(Handle<HeapObject> obj)
1046
      : type_(kHeapObject), value_(bit_cast<intptr_t>(obj)) {}
1047
  explicit Constant(RpoNumber rpo) : type_(kRpoNumber), value_(rpo.ToInt()) {}
1048
  explicit Constant(RelocatablePtrConstantInfo info);
1049 1050 1051

  Type type() const { return type_; }

1052 1053
  RelocInfo::Mode rmode() const { return rmode_; }

1054
  int32_t ToInt32() const {
1055 1056 1057 1058
    DCHECK(type() == kInt32 || type() == kInt64);
    const int32_t value = static_cast<int32_t>(value_);
    DCHECK_EQ(value_, static_cast<int64_t>(value));
    return value;
1059 1060 1061 1062
  }

  int64_t ToInt64() const {
    if (type() == kInt32) return ToInt32();
1063
    DCHECK_EQ(kInt64, type());
1064 1065 1066
    return value_;
  }

1067
  float ToFloat32() const {
1068 1069 1070
    // TODO(ahaas): We should remove this function. If value_ has the bit
    // representation of a signalling NaN, then returning it as float can cause
    // the signalling bit to flip, and value_ is returned as a quiet NaN.
1071 1072 1073 1074
    DCHECK_EQ(kFloat32, type());
    return bit_cast<float>(static_cast<int32_t>(value_));
  }

1075 1076 1077 1078 1079
  uint32_t ToFloat32AsInt() const {
    DCHECK_EQ(kFloat32, type());
    return bit_cast<uint32_t>(static_cast<int32_t>(value_));
  }

1080
  double ToFloat64() const {
1081 1082 1083
    // TODO(ahaas): We should remove this function. If value_ has the bit
    // representation of a signalling NaN, then returning it as float can cause
    // the signalling bit to flip, and value_ is returned as a quiet NaN.
1084
    if (type() == kInt32) return ToInt32();
1085
    DCHECK_EQ(kFloat64, type());
1086
    return bit_cast<double>(value_);
1087 1088
  }

1089 1090 1091 1092 1093 1094
  uint64_t ToFloat64AsInt() const {
    if (type() == kInt32) return ToInt32();
    DCHECK_EQ(kFloat64, type());
    return bit_cast<uint64_t>(value_);
  }

1095
  ExternalReference ToExternalReference() const {
1096
    DCHECK_EQ(kExternalReference, type());
1097
    return bit_cast<ExternalReference>(static_cast<intptr_t>(value_));
1098 1099
  }

1100
  RpoNumber ToRpoNumber() const {
1101
    DCHECK_EQ(kRpoNumber, type());
1102
    return RpoNumber::FromInt(static_cast<int>(value_));
1103 1104
  }

1105
  Handle<HeapObject> ToHeapObject() const;
1106 1107 1108 1109

 private:
  Type type_;
  int64_t value_;
1110 1111 1112 1113 1114
#if V8_TARGET_ARCH_32_BIT
  RelocInfo::Mode rmode_ = RelocInfo::NONE32;
#else
  RelocInfo::Mode rmode_ = RelocInfo::NONE64;
#endif
1115 1116
};

1117

1118 1119 1120 1121 1122 1123
std::ostream& operator<<(std::ostream& os, const Constant& constant);


// Forward declarations.
class FrameStateDescriptor;

1124
enum class StateValueKind : uint8_t {
1125
  kArguments,
1126 1127 1128 1129 1130
  kPlain,
  kOptimizedOut,
  kNested,
  kDuplicate
};
1131 1132 1133

class StateValueDescriptor {
 public:
1134
  StateValueDescriptor()
1135 1136
      : kind_(StateValueKind::kPlain),
        type_(MachineType::AnyTagged()),
1137
        id_(0) {}
1138

1139 1140 1141 1142
  static StateValueDescriptor Arguments() {
    return StateValueDescriptor(StateValueKind::kArguments,
                                MachineType::AnyTagged(), 0);
  }
1143 1144
  static StateValueDescriptor Plain(MachineType type) {
    return StateValueDescriptor(StateValueKind::kPlain, type, 0);
1145
  }
1146 1147 1148 1149 1150 1151
  static StateValueDescriptor OptimizedOut() {
    return StateValueDescriptor(StateValueKind::kOptimizedOut,
                                MachineType::AnyTagged(), 0);
  }
  static StateValueDescriptor Recursive(size_t id) {
    return StateValueDescriptor(StateValueKind::kNested,
1152 1153
                                MachineType::AnyTagged(), id);
  }
1154 1155
  static StateValueDescriptor Duplicate(size_t id) {
    return StateValueDescriptor(StateValueKind::kDuplicate,
1156 1157 1158
                                MachineType::AnyTagged(), id);
  }

1159 1160 1161 1162 1163
  bool IsArguments() const { return kind_ == StateValueKind::kArguments; }
  bool IsPlain() const { return kind_ == StateValueKind::kPlain; }
  bool IsOptimizedOut() const { return kind_ == StateValueKind::kOptimizedOut; }
  bool IsNested() const { return kind_ == StateValueKind::kNested; }
  bool IsDuplicate() const { return kind_ == StateValueKind::kDuplicate; }
1164 1165 1166 1167
  MachineType type() const { return type_; }
  size_t id() const { return id_; }

 private:
1168 1169
  StateValueDescriptor(StateValueKind kind, MachineType type, size_t id)
      : kind_(kind), type_(type), id_(id) {}
1170 1171 1172 1173 1174 1175

  StateValueKind kind_;
  MachineType type_;
  size_t id_;
};

1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222
class StateValueList {
 public:
  explicit StateValueList(Zone* zone) : fields_(zone), nested_(zone) {}

  size_t size() { return fields_.size(); }

  struct Value {
    StateValueDescriptor* desc;
    StateValueList* nested;

    Value(StateValueDescriptor* desc, StateValueList* nested)
        : desc(desc), nested(nested) {}
  };

  class iterator {
   public:
    // Bare minimum of operators needed for range iteration.
    bool operator!=(const iterator& other) const {
      return field_iterator != other.field_iterator;
    }
    bool operator==(const iterator& other) const {
      return field_iterator == other.field_iterator;
    }
    iterator& operator++() {
      if (field_iterator->IsNested()) {
        nested_iterator++;
      }
      ++field_iterator;
      return *this;
    }
    Value operator*() {
      StateValueDescriptor* desc = &(*field_iterator);
      StateValueList* nested = desc->IsNested() ? *nested_iterator : nullptr;
      return Value(desc, nested);
    }

   private:
    friend class StateValueList;

    iterator(ZoneVector<StateValueDescriptor>::iterator it,
             ZoneVector<StateValueList*>::iterator nested)
        : field_iterator(it), nested_iterator(nested) {}

    ZoneVector<StateValueDescriptor>::iterator field_iterator;
    ZoneVector<StateValueList*>::iterator nested_iterator;
  };

1223 1224
  void ReserveSize(size_t size) { fields_.reserve(size); }

1225 1226 1227 1228 1229 1230 1231
  StateValueList* PushRecursiveField(Zone* zone, size_t id) {
    fields_.push_back(StateValueDescriptor::Recursive(id));
    StateValueList* nested =
        new (zone->New(sizeof(StateValueList))) StateValueList(zone);
    nested_.push_back(nested);
    return nested;
  }
1232
  void PushArguments() { fields_.push_back(StateValueDescriptor::Arguments()); }
1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249
  void PushDuplicate(size_t id) {
    fields_.push_back(StateValueDescriptor::Duplicate(id));
  }
  void PushPlain(MachineType type) {
    fields_.push_back(StateValueDescriptor::Plain(type));
  }
  void PushOptimizedOut() {
    fields_.push_back(StateValueDescriptor::OptimizedOut());
  }

  iterator begin() { return iterator(fields_.begin(), nested_.begin()); }
  iterator end() { return iterator(fields_.end(), nested_.end()); }

 private:
  ZoneVector<StateValueDescriptor> fields_;
  ZoneVector<StateValueList*> nested_;
};
1250

1251 1252
class FrameStateDescriptor : public ZoneObject {
 public:
1253 1254
  FrameStateDescriptor(Zone* zone, FrameStateType type, BailoutId bailout_id,
                       OutputFrameStateCombine state_combine,
1255 1256
                       size_t parameters_count, size_t locals_count,
                       size_t stack_count,
1257
                       MaybeHandle<SharedFunctionInfo> shared_info,
1258
                       FrameStateDescriptor* outer_state = nullptr);
1259

1260
  FrameStateType type() const { return type_; }
1261
  BailoutId bailout_id() const { return bailout_id_; }
1262
  OutputFrameStateCombine state_combine() const { return frame_state_combine_; }
1263 1264 1265
  size_t parameters_count() const { return parameters_count_; }
  size_t locals_count() const { return locals_count_; }
  size_t stack_count() const { return stack_count_; }
1266
  MaybeHandle<SharedFunctionInfo> shared_info() const { return shared_info_; }
1267
  FrameStateDescriptor* outer_state() const { return outer_state_; }
1268
  bool HasContext() const {
1269
    return FrameStateFunctionInfo::IsJSFunctionType(type_);
1270
  }
1271

1272
  size_t GetSize(OutputFrameStateCombine combine =
1273 1274 1275 1276
                     OutputFrameStateCombine::Ignore()) const;
  size_t GetTotalSize() const;
  size_t GetFrameCount() const;
  size_t GetJSFrameCount() const;
1277

1278
  StateValueList* GetStateValueDescriptors() { return &values_; }
1279

1280 1281
  static const int kImpossibleValue = 0xdead;

1282
 private:
1283
  FrameStateType type_;
1284
  BailoutId bailout_id_;
1285
  OutputFrameStateCombine frame_state_combine_;
1286 1287 1288
  size_t parameters_count_;
  size_t locals_count_;
  size_t stack_count_;
1289
  StateValueList values_;
1290
  MaybeHandle<SharedFunctionInfo> const shared_info_;
1291
  FrameStateDescriptor* outer_state_;
1292 1293
};

1294 1295 1296 1297 1298
// A deoptimization entry is a pair of the reason why we deoptimize and the
// frame state descriptor that we have to go back to.
class DeoptimizationEntry final {
 public:
  DeoptimizationEntry() {}
1299 1300 1301
  DeoptimizationEntry(FrameStateDescriptor* descriptor, DeoptimizeKind kind,
                      DeoptimizeReason reason)
      : descriptor_(descriptor), kind_(kind), reason_(reason) {}
1302 1303

  FrameStateDescriptor* descriptor() const { return descriptor_; }
1304
  DeoptimizeKind kind() const { return kind_; }
1305
  DeoptimizeReason reason() const { return reason_; }
1306

1307 1308
 private:
  FrameStateDescriptor* descriptor_ = nullptr;
1309
  DeoptimizeKind kind_ = DeoptimizeKind::kEager;
1310 1311
  DeoptimizeReason reason_ = DeoptimizeReason::kNoReason;
};
1312

1313
typedef ZoneVector<DeoptimizationEntry> DeoptimizationVector;
1314

1315 1316
class V8_EXPORT_PRIVATE PhiInstruction final
    : public NON_EXPORTED_BASE(ZoneObject) {
1317
 public:
1318
  typedef ZoneVector<InstructionOperand> Inputs;
1319

1320 1321 1322
  PhiInstruction(Zone* zone, int virtual_register, size_t input_count);

  void SetInput(size_t offset, int virtual_register);
1323
  void RenameInput(size_t offset, int virtual_register);
1324 1325 1326

  int virtual_register() const { return virtual_register_; }
  const IntVector& operands() const { return operands_; }
1327

1328 1329
  // TODO(dcarney): this has no real business being here, since it's internal to
  // the register allocator, but putting it here was convenient.
1330 1331
  const InstructionOperand& output() const { return output_; }
  InstructionOperand& output() { return output_; }
1332 1333 1334

 private:
  const int virtual_register_;
1335
  InstructionOperand output_;
1336 1337 1338 1339 1340
  IntVector operands_;
};


// Analogue of BasicBlock for Instructions instead of Nodes.
1341 1342
class V8_EXPORT_PRIVATE InstructionBlock final
    : public NON_EXPORTED_BASE(ZoneObject) {
1343
 public:
1344
  InstructionBlock(Zone* zone, RpoNumber rpo_number, RpoNumber loop_header,
1345
                   RpoNumber loop_end, bool deferred, bool handler);
1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366

  // Instruction indexes (used by the register allocator).
  int first_instruction_index() const {
    DCHECK(code_start_ >= 0);
    DCHECK(code_end_ > 0);
    DCHECK(code_end_ >= code_start_);
    return code_start_;
  }
  int last_instruction_index() const {
    DCHECK(code_start_ >= 0);
    DCHECK(code_end_ > 0);
    DCHECK(code_end_ >= code_start_);
    return code_end_ - 1;
  }

  int32_t code_start() const { return code_start_; }
  void set_code_start(int32_t start) { code_start_ = start; }

  int32_t code_end() const { return code_end_; }
  void set_code_end(int32_t end) { code_end_ = end; }

1367
  bool IsDeferred() const { return deferred_; }
1368
  bool IsHandler() const { return handler_; }
1369

1370 1371 1372 1373
  RpoNumber ao_number() const { return ao_number_; }
  RpoNumber rpo_number() const { return rpo_number_; }
  RpoNumber loop_header() const { return loop_header_; }
  RpoNumber loop_end() const {
1374 1375 1376 1377 1378
    DCHECK(IsLoopHeader());
    return loop_end_;
  }
  inline bool IsLoopHeader() const { return loop_end_.IsValid(); }

1379
  typedef ZoneVector<RpoNumber> Predecessors;
1380
  Predecessors& predecessors() { return predecessors_; }
1381 1382
  const Predecessors& predecessors() const { return predecessors_; }
  size_t PredecessorCount() const { return predecessors_.size(); }
1383
  size_t PredecessorIndexOf(RpoNumber rpo_number) const;
1384

1385
  typedef ZoneVector<RpoNumber> Successors;
1386
  Successors& successors() { return successors_; }
1387 1388 1389 1390 1391
  const Successors& successors() const { return successors_; }
  size_t SuccessorCount() const { return successors_.size(); }

  typedef ZoneVector<PhiInstruction*> PhiInstructions;
  const PhiInstructions& phis() const { return phis_; }
1392
  PhiInstruction* PhiAt(size_t i) const { return phis_[i]; }
1393 1394
  void AddPhi(PhiInstruction* phi) { phis_.push_back(phi); }

1395
  void set_ao_number(RpoNumber ao_number) { ao_number_ = ao_number; }
1396

1397 1398 1399 1400 1401 1402 1403 1404 1405
  bool needs_frame() const { return needs_frame_; }
  void mark_needs_frame() { needs_frame_ = true; }

  bool must_construct_frame() const { return must_construct_frame_; }
  void mark_must_construct_frame() { must_construct_frame_ = true; }

  bool must_deconstruct_frame() const { return must_deconstruct_frame_; }
  void mark_must_deconstruct_frame() { must_deconstruct_frame_ = true; }

1406 1407 1408 1409
 private:
  Successors successors_;
  Predecessors predecessors_;
  PhiInstructions phis_;
1410 1411 1412 1413
  RpoNumber ao_number_;  // Assembly order number.
  const RpoNumber rpo_number_;
  const RpoNumber loop_header_;
  const RpoNumber loop_end_;
1414 1415 1416
  int32_t code_start_;   // start index of arch-specific code.
  int32_t code_end_;     // end index of arch-specific code.
  const bool deferred_;  // Block contains deferred code.
1417
  const bool handler_;   // Block is a handler entry point.
1418 1419 1420
  bool needs_frame_;
  bool must_construct_frame_;
  bool must_deconstruct_frame_;
1421 1422
};

1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433
class InstructionSequence;

struct PrintableInstructionBlock {
  const RegisterConfiguration* register_configuration_;
  const InstructionBlock* block_;
  const InstructionSequence* code_;
};

std::ostream& operator<<(std::ostream& os,
                         const PrintableInstructionBlock& printable_block);

1434
typedef ZoneDeque<Constant> ConstantDeque;
1435
typedef std::map<int, Constant, std::less<int>,
1436
                 zone_allocator<std::pair<const int, Constant> > > ConstantMap;
1437

1438
typedef ZoneDeque<Instruction*> InstructionDeque;
1439
typedef ZoneDeque<ReferenceMap*> ReferenceMapDeque;
1440
typedef ZoneVector<InstructionBlock*> InstructionBlocks;
1441

1442 1443

// Forward declarations.
1444 1445 1446
struct PrintableInstructionSequence;


1447 1448
// Represents architecture-specific generated code before, during, and after
// register allocation.
1449 1450
class V8_EXPORT_PRIVATE InstructionSequence final
    : public NON_EXPORTED_BASE(ZoneObject) {
1451
 public:
1452 1453
  static InstructionBlocks* InstructionBlocksFor(Zone* zone,
                                                 const Schedule* schedule);
1454 1455
  // Puts the deferred blocks last.
  static void ComputeAssemblyOrder(InstructionBlocks* blocks);
1456

1457 1458
  InstructionSequence(Isolate* isolate, Zone* zone,
                      InstructionBlocks* instruction_blocks);
1459

1460
  int NextVirtualRegister();
1461 1462
  int VirtualRegisterCount() const { return next_virtual_register_; }

1463
  const InstructionBlocks& instruction_blocks() const {
1464
    return *instruction_blocks_;
1465 1466
  }

1467
  int InstructionBlockCount() const {
1468
    return static_cast<int>(instruction_blocks_->size());
1469 1470
  }

1471
  InstructionBlock* InstructionBlockAt(RpoNumber rpo_number) {
1472
    return instruction_blocks_->at(rpo_number.ToSize());
1473 1474
  }

1475
  int LastLoopInstructionIndex(const InstructionBlock* block) {
1476
    return instruction_blocks_->at(block->loop_end().ToSize() - 1)
1477 1478 1479
        ->last_instruction_index();
  }

1480
  const InstructionBlock* InstructionBlockAt(RpoNumber rpo_number) const {
1481
    return instruction_blocks_->at(rpo_number.ToSize());
1482 1483
  }

1484
  InstructionBlock* GetInstructionBlock(int instruction_index) const;
1485

1486 1487
  static MachineRepresentation DefaultRepresentation() {
    return MachineType::PointerRepresentation();
1488
  }
1489 1490
  MachineRepresentation GetRepresentation(int virtual_register) const;
  void MarkAsRepresentation(MachineRepresentation rep, int virtual_register);
1491
  int representation_mask() const { return representation_mask_; }
1492

1493
  bool IsReference(int virtual_register) const {
1494
    return CanBeTaggedPointer(GetRepresentation(virtual_register));
1495
  }
1496
  bool IsFP(int virtual_register) const {
1497
    return IsFloatingPoint(GetRepresentation(virtual_register));
1498
  }
1499

1500
  Instruction* GetBlockStart(RpoNumber rpo) const;
1501 1502 1503 1504

  typedef InstructionDeque::const_iterator const_iterator;
  const_iterator begin() const { return instructions_.begin(); }
  const_iterator end() const { return instructions_.end(); }
1505
  const InstructionDeque& instructions() const { return instructions_; }
1506 1507 1508
  int LastInstructionIndex() const {
    return static_cast<int>(instructions().size()) - 1;
  }
1509 1510

  Instruction* InstructionAt(int index) const {
1511 1512
    DCHECK(index >= 0);
    DCHECK(index < static_cast<int>(instructions_.size()));
1513 1514 1515
    return instructions_[index];
  }

1516
  Isolate* isolate() const { return isolate_; }
1517
  const ReferenceMapDeque* reference_maps() const { return &reference_maps_; }
1518
  Zone* zone() const { return zone_; }
1519

1520 1521
  // Used by the instruction selector while adding instructions.
  int AddInstruction(Instruction* instr);
1522 1523
  void StartBlock(RpoNumber rpo);
  void EndBlock(RpoNumber rpo);
1524

1525
  int AddConstant(int virtual_register, Constant constant) {
1526 1527
    // TODO(titzer): allow RPO numbers as constants?
    DCHECK(constant.type() != Constant::kRpoNumber);
1528
    DCHECK(virtual_register >= 0 && virtual_register < next_virtual_register_);
1529
    DCHECK(constants_.find(virtual_register) == constants_.end());
1530
    constants_.insert(std::make_pair(virtual_register, constant));
1531
    return virtual_register;
1532 1533 1534
  }
  Constant GetConstant(int virtual_register) const {
    ConstantMap::const_iterator it = constants_.find(virtual_register);
1535 1536
    DCHECK(it != constants_.end());
    DCHECK_EQ(virtual_register, it->first);
1537 1538 1539
    return it->second;
  }

1540 1541
  typedef ZoneVector<Constant> Immediates;
  Immediates& immediates() { return immediates_; }
1542

1543
  ImmediateOperand AddImmediate(const Constant& constant) {
1544 1545
    if (constant.type() == Constant::kInt32 &&
        RelocInfo::IsNone(constant.rmode())) {
1546 1547
      return ImmediateOperand(ImmediateOperand::INLINE, constant.ToInt32());
    }
1548
    int index = static_cast<int>(immediates_.size());
1549
    immediates_.push_back(constant);
1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565
    return ImmediateOperand(ImmediateOperand::INDEXED, index);
  }

  Constant GetImmediate(const ImmediateOperand* op) const {
    switch (op->type()) {
      case ImmediateOperand::INLINE:
        return Constant(op->inline_value());
      case ImmediateOperand::INDEXED: {
        int index = op->indexed_value();
        DCHECK(index >= 0);
        DCHECK(index < static_cast<int>(immediates_.size()));
        return immediates_[index];
      }
    }
    UNREACHABLE();
    return Constant(static_cast<int32_t>(0));
1566 1567
  }

1568
  int AddDeoptimizationEntry(FrameStateDescriptor* descriptor,
1569
                             DeoptimizeKind kind, DeoptimizeReason reason);
1570 1571 1572
  DeoptimizationEntry const& GetDeoptimizationEntry(int deoptimization_id);
  int GetDeoptimizationEntryCount() const {
    return static_cast<int>(deoptimization_entries_.size());
1573
  }
1574

1575
  RpoNumber InputRpo(Instruction* instr, size_t index);
1576

1577 1578 1579 1580
  bool GetSourcePosition(const Instruction* instr,
                         SourcePosition* result) const;
  void SetSourcePosition(const Instruction* instr, SourcePosition value);

1581 1582 1583 1584 1585 1586 1587
  bool ContainsCall() const {
    for (Instruction* instr : instructions_) {
      if (instr->IsCall()) return true;
    }
    return false;
  }

1588 1589 1590 1591 1592 1593
  // APIs to aid debugging. For general-stream APIs, use operator<<
  void Print(const RegisterConfiguration* config) const;
  void Print() const;

  void PrintBlock(const RegisterConfiguration* config, int block_id) const;
  void PrintBlock(int block_id) const;
1594

1595 1596 1597 1598
  void ValidateEdgeSplitForm() const;
  void ValidateDeferredBlockExitPaths() const;
  void ValidateDeferredBlockEntryPaths() const;
  void ValidateSSA() const;
1599

1600 1601 1602 1603
  static void SetRegisterConfigurationForTesting(
      const RegisterConfiguration* regConfig);
  static void ClearRegisterConfigurationForTesting();

1604
 private:
1605 1606
  friend V8_EXPORT_PRIVATE std::ostream& operator<<(
      std::ostream& os, const PrintableInstructionSequence& code);
1607

1608
  typedef ZoneMap<const Instruction*, SourcePosition> SourcePositionMap;
1609

1610 1611 1612
  static const RegisterConfiguration* RegisterConfigurationForTesting();
  static const RegisterConfiguration* registerConfigurationForTesting_;

1613
  Isolate* isolate_;
1614
  Zone* const zone_;
1615
  InstructionBlocks* const instruction_blocks_;
1616
  SourcePositionMap source_positions_;
1617
  ConstantMap constants_;
1618
  Immediates immediates_;
1619 1620
  InstructionDeque instructions_;
  int next_virtual_register_;
1621
  ReferenceMapDeque reference_maps_;
1622
  ZoneVector<MachineRepresentation> representations_;
1623
  int representation_mask_;
1624
  DeoptimizationVector deoptimization_entries_;
1625

1626 1627 1628
  // Used at construction time
  InstructionBlock* current_block_;

1629
  DISALLOW_COPY_AND_ASSIGN(InstructionSequence);
1630 1631
};

1632 1633 1634 1635 1636 1637

struct PrintableInstructionSequence {
  const RegisterConfiguration* register_configuration_;
  const InstructionSequence* sequence_;
};

1638 1639
V8_EXPORT_PRIVATE std::ostream& operator<<(
    std::ostream& os, const PrintableInstructionSequence& code);
1640 1641 1642 1643 1644 1645

}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_INSTRUCTION_H_