instruction.h 55.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/double.h"
19
#include "src/globals.h"
20 21
#include "src/macro-assembler.h"
#include "src/register-configuration.h"
22
#include "src/source-position.h"
23
#include "src/zone/zone-allocator.h"
24 25 26 27 28

namespace v8 {
namespace internal {
namespace compiler {

29
class Schedule;
30
class SourcePositionTable;
31

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

36 37 38 39 40 41 42 43 44 45 46
  enum Kind {
    INVALID,
    UNALLOCATED,
    CONSTANT,
    IMMEDIATE,
    // Location operand kinds.
    EXPLICIT,
    ALLOCATED,
    FIRST_LOCATION_OPERAND_KIND = EXPLICIT
    // Location operand kinds must be last.
  };
47

48
  InstructionOperand() : InstructionOperand(INVALID) {}
49

50
  Kind kind() const { return KindField::decode(value_); }
51

52
#define INSTRUCTION_OPERAND_PREDICATE(name, type) \
53
  bool Is##name() const { return kind() == type; }
54
  INSTRUCTION_OPERAND_PREDICATE(Invalid, INVALID)
55 56
  // UnallocatedOperands are place-holder operands created before register
  // allocation. They later are assigned registers and become AllocatedOperands.
57
  INSTRUCTION_OPERAND_PREDICATE(Unallocated, UNALLOCATED)
58 59 60 61
  // 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.
62
  INSTRUCTION_OPERAND_PREDICATE(Constant, CONSTANT)
63 64 65
  // ImmediateOperands do not participate in register allocation and are only
  // embedded directly in instructions, e.g. small integers and on some
  // platforms Objects.
66
  INSTRUCTION_OPERAND_PREDICATE(Immediate, IMMEDIATE)
67 68 69 70 71 72 73
  // 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.
74
  INSTRUCTION_OPERAND_PREDICATE(Allocated, ALLOCATED)
75
#undef INSTRUCTION_OPERAND_PREDICATE
76

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

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

99 100 101
  static void ReplaceWith(InstructionOperand* dest,
                          const InstructionOperand* src) {
    *dest = *src;
102 103
  }

104 105 106 107 108 109 110 111
  bool Equals(const InstructionOperand& that) const {
    return this->value_ == that.value_;
  }

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

112 113
  bool EqualsCanonicalized(const InstructionOperand& that) const {
    return this->GetCanonicalizedValue() == that.GetCanonicalizedValue();
114 115
  }

116 117
  bool CompareCanonicalized(const InstructionOperand& that) const {
    return this->GetCanonicalizedValue() < that.GetCanonicalizedValue();
118 119
  }

120
  bool InterferesWith(const InstructionOperand& other) const;
121

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

126
 protected:
127
  explicit InstructionOperand(Kind kind) : value_(KindField::encode(kind)) {}
128

129
  inline uint64_t GetCanonicalizedValue() const;
130

131
  class KindField : public BitField64<Kind, 0, 3> {};
132 133

  uint64_t value_;
134 135
};

136

137 138 139
typedef ZoneVector<InstructionOperand> InstructionOperandVector;


140 141
struct PrintableInstructionOperand {
  const RegisterConfiguration* register_configuration_;
142
  InstructionOperand op_;
143 144
};

145

146 147
std::ostream& operator<<(std::ostream& os,
                         const PrintableInstructionOperand& op);
148

149

150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166
#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);                \
  }

167
class UnallocatedOperand final : public InstructionOperand {
168 169 170 171 172
 public:
  enum BasicPolicy { FIXED_SLOT, EXTENDED_POLICY };

  enum ExtendedPolicy {
    NONE,
173 174
    REGISTER_OR_SLOT,
    REGISTER_OR_SLOT_OR_CONSTANT,
175
    FIXED_REGISTER,
176
    FIXED_FP_REGISTER,
177
    MUST_HAVE_REGISTER,
178
    MUST_HAVE_SLOT,
179 180 181 182 183
    SAME_AS_FIRST_INPUT
  };

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

189 190 191
    // USED_AT_END operand is treated as live until the end of instruction.
    // This means that register allocator will not reuse its register for any
    // other operand inside instruction.
192 193 194
    USED_AT_END
  };

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

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

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

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

227 228 229 230 231 232
  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);
  }

233 234 235 236 237 238
  UnallocatedOperand(const UnallocatedOperand& other, int virtual_register) {
    DCHECK_NE(kInvalidVirtualRegister, virtual_register);
    value_ = VirtualRegisterField::update(
        other.value_, static_cast<uint32_t>(virtual_register));
  }

239
  // Predicates for the operand policy.
240 241 242 243 244 245 246
  bool HasRegisterOrSlotPolicy() const {
    return basic_policy() == EXTENDED_POLICY &&
           extended_policy() == REGISTER_OR_SLOT;
  }
  bool HasRegisterOrSlotOrConstantPolicy() const {
    return basic_policy() == EXTENDED_POLICY &&
           extended_policy() == REGISTER_OR_SLOT_OR_CONSTANT;
247 248 249 250
  }
  bool HasFixedPolicy() const {
    return basic_policy() == FIXED_SLOT ||
           extended_policy() == FIXED_REGISTER ||
251
           extended_policy() == FIXED_FP_REGISTER;
252 253 254 255 256
  }
  bool HasRegisterPolicy() const {
    return basic_policy() == EXTENDED_POLICY &&
           extended_policy() == MUST_HAVE_REGISTER;
  }
257 258 259 260
  bool HasSlotPolicy() const {
    return basic_policy() == EXTENDED_POLICY &&
           extended_policy() == MUST_HAVE_SLOT;
  }
261 262 263 264 265 266 267 268 269
  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;
  }
270
  bool HasFixedFPRegisterPolicy() const {
271
    return basic_policy() == EXTENDED_POLICY &&
272
           extended_policy() == FIXED_FP_REGISTER;
273
  }
274 275 276 277 278 279 280 281 282
  bool HasSecondaryStorage() const {
    return basic_policy() == EXTENDED_POLICY &&
           extended_policy() == FIXED_REGISTER &&
           HasSecondaryStorageField::decode(value_);
  }
  int GetSecondaryStorage() const {
    DCHECK(HasSecondaryStorage());
    return SecondaryStorageField::decode(value_);
  }
283 284

  // [basic_policy]: Distinguish between FIXED_SLOT and all other policies.
285 286 287
  BasicPolicy basic_policy() const {
    return BasicPolicyField::decode(value_);
  }
288 289 290

  // [extended_policy]: Only for non-FIXED_SLOT. The finer-grained policy.
  ExtendedPolicy extended_policy() const {
291
    DCHECK(basic_policy() == EXTENDED_POLICY);
292 293 294 295 296
    return ExtendedPolicyField::decode(value_);
  }

  // [fixed_slot_index]: Only for FIXED_SLOT.
  int fixed_slot_index() const {
297
    DCHECK(HasFixedSlotPolicy());
298
    return static_cast<int>(static_cast<int64_t>(value_) >>
299
                            FixedSlotIndexField::kShift);
300 301
  }

302
  // [fixed_register_index]: Only for FIXED_REGISTER or FIXED_FP_REGISTER.
303
  int fixed_register_index() const {
304
    DCHECK(HasFixedRegisterPolicy() || HasFixedFPRegisterPolicy());
305 306 307 308
    return FixedRegisterField::decode(value_);
  }

  // [virtual_register]: The virtual register ID for this operand.
309
  int32_t virtual_register() const {
310
    return static_cast<int32_t>(VirtualRegisterField::decode(value_));
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
    UNREACHABLE();
498 499
  }

500 501 502
  // Return true if the locations can be moved to one another.
  bool IsCompatible(LocationOperand* op);

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

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

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

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

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

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

  INSTRUCTION_OPERAND_CASTS(ExplicitOperand, EXPLICIT);
};


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

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

  INSTRUCTION_OPERAND_CASTS(AllocatedOperand, ALLOCATED);
};


552 553
#undef INSTRUCTION_OPERAND_CASTS

554 555 556 557 558 559 560 561 562 563 564 565 566
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());
}
567

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


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

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

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

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

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

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

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

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

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

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

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

642
uint64_t InstructionOperand::GetCanonicalizedValue() const {
643
  if (IsAnyLocationOperand()) {
644
    MachineRepresentation canonical = MachineRepresentation::kNone;
645
    if (IsFPRegister()) {
646 647 648 649 650 651 652 653
      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();
      }
654
    }
655
    return InstructionOperand::KindField::update(
656
        LocationOperand::RepresentationField::update(this->value_, canonical),
657
        LocationOperand::EXPLICIT);
658 659 660 661 662 663 664 665
  }
  return this->value_;
}

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

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

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

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

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

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

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

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

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

  DISALLOW_COPY_AND_ASSIGN(MoveOperands);
719 720
};

721 722 723 724 725 726 727 728 729

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


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

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

738 739
  MoveOperands* AddMove(const InstructionOperand& from,
                        const InstructionOperand& to) {
740 741 742 743 744 745 746 747
    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);
748 749
    push_back(move);
    return move;
750 751 752 753
  }

  bool IsRedundant() const;

dcarney's avatar
dcarney committed
754
  // Prepare this ParallelMove to insert move as if it happened in a subsequent
755 756 757 758
  // 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
759

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

764 765 766 767 768 769 770 771 772

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


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

773

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

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

  void set_instruction_position(int pos) {
785
    DCHECK_EQ(-1, instruction_position_);
786 787 788
    instruction_position_ = pos;
  }

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

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

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

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

800 801
class InstructionBlock;

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

814
  bool HasOutput() const { return OutputCount() > 0; }
815 816
  const InstructionOperand* Output() const { return OutputAt(0); }
  InstructionOperand* Output() { return OutputAt(0); }
817

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

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

  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) {
849
    return New(zone, opcode, 0, nullptr, 0, nullptr, 0, nullptr);
850 851 852
  }

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

863 864 865
    size_t total_extra_ops = output_count + input_count + temp_count;
    if (total_extra_ops != 0) total_extra_ops--;
    int size = static_cast<int>(
866 867
        RoundUp(sizeof(Instruction), sizeof(InstructionOperand)) +
        total_extra_ops * sizeof(InstructionOperand));
868 869 870 871 872 873 874 875 876
    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_); }
877
  bool NeedsReferenceMap() const { return IsCall(); }
878
  bool HasReferenceMap() const { return reference_map_ != nullptr; }
879 880 881 882

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

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

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

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

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

905 906 907 908
  bool IsTrap() const {
    return FlagsModeField::decode(opcode()) == kFlags_trap;
  }

909 910 911 912 913
  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 ||
914 915
           arch_opcode() == ArchOpcode::kArchTailCallAddress ||
           arch_opcode() == ArchOpcode::kArchTailCallWasm;
916 917 918 919 920
  }
  bool IsThrow() const {
    return arch_opcode() == ArchOpcode::kArchThrowTerminator;
  }

921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947
  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]; }

948 949 950 951 952 953 954 955 956
  // 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;
  }

957 958 959
  // APIs to aid debugging. For general-stream APIs, use operator<<
  void Print(const RegisterConfiguration* config) const;
  void Print() const;
960

961 962 963 964 965 966 967 968
  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;

969
 private:
970
  explicit Instruction(InstructionCode opcode);
971

972
  Instruction(InstructionCode opcode, size_t output_count,
973 974 975
              InstructionOperand* outputs, size_t input_count,
              InstructionOperand* inputs, size_t temp_count,
              InstructionOperand* temps);
976 977 978 979 980

  typedef BitField<bool, 30, 1> IsCallField;

  InstructionCode opcode_;
  uint32_t bit_field_;
981
  ParallelMove* parallel_moves_[2];
982
  ReferenceMap* reference_map_;
983
  InstructionBlock* block_;
984
  InstructionOperand operands_[1];
985 986

  DISALLOW_COPY_AND_ASSIGN(Instruction);
987 988
};

989 990 991 992 993 994 995

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

996

997
class RpoNumber final {
998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016
 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;
  }

1017 1018 1019 1020 1021 1022 1023
  // 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_; }
1024 1025 1026 1027 1028 1029 1030 1031 1032

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


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

1033
class V8_EXPORT_PRIVATE Constant final {
1034
 public:
1035 1036 1037 1038 1039 1040
  enum Type {
    kInt32,
    kInt64,
    kFloat32,
    kFloat64,
    kExternalReference,
1041 1042
    kHeapObject,
    kRpoNumber
1043
  };
1044

1045
  explicit Constant(int32_t v);
1046
  explicit Constant(int64_t v) : type_(kInt64), value_(v) {}
1047
  explicit Constant(float v) : type_(kFloat32), value_(bit_cast<int32_t>(v)) {}
1048
  explicit Constant(double v) : type_(kFloat64), value_(bit_cast<int64_t>(v)) {}
1049
  explicit Constant(ExternalReference ref)
1050
      : type_(kExternalReference), value_(bit_cast<intptr_t>(ref)) {}
1051
  explicit Constant(Handle<HeapObject> obj)
1052
      : type_(kHeapObject), value_(bit_cast<intptr_t>(obj)) {}
1053
  explicit Constant(RpoNumber rpo) : type_(kRpoNumber), value_(rpo.ToInt()) {}
1054
  explicit Constant(RelocatablePtrConstantInfo info);
1055 1056 1057

  Type type() const { return type_; }

1058 1059
  RelocInfo::Mode rmode() const { return rmode_; }

1060
  int32_t ToInt32() const {
1061 1062 1063 1064
    DCHECK(type() == kInt32 || type() == kInt64);
    const int32_t value = static_cast<int32_t>(value_);
    DCHECK_EQ(value_, static_cast<int64_t>(value));
    return value;
1065 1066 1067 1068
  }

  int64_t ToInt64() const {
    if (type() == kInt32) return ToInt32();
1069
    DCHECK_EQ(kInt64, type());
1070 1071 1072
    return value_;
  }

1073
  float ToFloat32() const {
1074 1075 1076
    // 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.
1077 1078 1079 1080
    DCHECK_EQ(kFloat32, type());
    return bit_cast<float>(static_cast<int32_t>(value_));
  }

1081 1082 1083 1084 1085
  uint32_t ToFloat32AsInt() const {
    DCHECK_EQ(kFloat32, type());
    return bit_cast<uint32_t>(static_cast<int32_t>(value_));
  }

1086
  Double ToFloat64() const {
1087
    DCHECK_EQ(kFloat64, type());
1088
    return Double(bit_cast<uint64_t>(value_));
1089 1090
  }

1091
  ExternalReference ToExternalReference() const {
1092
    DCHECK_EQ(kExternalReference, type());
1093
    return bit_cast<ExternalReference>(static_cast<intptr_t>(value_));
1094 1095
  }

1096
  RpoNumber ToRpoNumber() const {
1097
    DCHECK_EQ(kRpoNumber, type());
1098
    return RpoNumber::FromInt(static_cast<int>(value_));
1099 1100
  }

1101
  Handle<HeapObject> ToHeapObject() const;
1102
  Handle<Code> ToCode() const;
1103 1104 1105

 private:
  Type type_;
1106
  RelocInfo::Mode rmode_ = RelocInfo::NONE;
1107
  int64_t value_;
1108 1109
};

1110

1111 1112 1113 1114 1115 1116
std::ostream& operator<<(std::ostream& os, const Constant& constant);


// Forward declarations.
class FrameStateDescriptor;

1117
enum class StateValueKind : uint8_t {
1118
  kArgumentsElements,
1119
  kArgumentsLength,
1120 1121 1122 1123 1124
  kPlain,
  kOptimizedOut,
  kNested,
  kDuplicate
};
1125 1126 1127

class StateValueDescriptor {
 public:
1128
  StateValueDescriptor()
1129
      : kind_(StateValueKind::kPlain), type_(MachineType::AnyTagged()) {}
1130

1131
  static StateValueDescriptor ArgumentsElements(ArgumentsStateType type) {
1132 1133
    StateValueDescriptor descr(StateValueKind::kArgumentsElements,
                               MachineType::AnyTagged());
1134
    descr.args_type_ = type;
1135
    return descr;
1136
  }
1137
  static StateValueDescriptor ArgumentsLength(ArgumentsStateType type) {
1138 1139
    StateValueDescriptor descr(StateValueKind::kArgumentsLength,
                               MachineType::AnyTagged());
1140
    descr.args_type_ = type;
1141 1142
    return descr;
  }
1143
  static StateValueDescriptor Plain(MachineType type) {
1144
    return StateValueDescriptor(StateValueKind::kPlain, type);
1145
  }
1146 1147
  static StateValueDescriptor OptimizedOut() {
    return StateValueDescriptor(StateValueKind::kOptimizedOut,
1148
                                MachineType::AnyTagged());
1149 1150
  }
  static StateValueDescriptor Recursive(size_t id) {
1151 1152 1153 1154
    StateValueDescriptor descr(StateValueKind::kNested,
                               MachineType::AnyTagged());
    descr.id_ = id;
    return descr;
1155
  }
1156
  static StateValueDescriptor Duplicate(size_t id) {
1157 1158 1159 1160
    StateValueDescriptor descr(StateValueKind::kDuplicate,
                               MachineType::AnyTagged());
    descr.id_ = id;
    return descr;
1161 1162
  }

1163 1164 1165
  bool IsArgumentsElements() const {
    return kind_ == StateValueKind::kArgumentsElements;
  }
1166 1167 1168
  bool IsArgumentsLength() const {
    return kind_ == StateValueKind::kArgumentsLength;
  }
1169 1170 1171 1172
  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; }
1173
  MachineType type() const { return type_; }
1174 1175 1176 1177 1178
  size_t id() const {
    DCHECK(kind_ == StateValueKind::kDuplicate ||
           kind_ == StateValueKind::kNested);
    return id_;
  }
1179
  ArgumentsStateType arguments_type() const {
1180 1181
    DCHECK(kind_ == StateValueKind::kArgumentsElements ||
           kind_ == StateValueKind::kArgumentsLength);
1182
    return args_type_;
1183
  }
1184 1185

 private:
1186 1187
  StateValueDescriptor(StateValueKind kind, MachineType type)
      : kind_(kind), type_(type) {}
1188 1189 1190

  StateValueKind kind_;
  MachineType type_;
1191 1192
  union {
    size_t id_;
1193
    ArgumentsStateType args_type_;
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 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243
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;
  };

1244 1245
  void ReserveSize(size_t size) { fields_.reserve(size); }

1246 1247 1248 1249 1250 1251 1252
  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;
  }
1253 1254
  void PushArgumentsElements(ArgumentsStateType type) {
    fields_.push_back(StateValueDescriptor::ArgumentsElements(type));
1255
  }
1256 1257
  void PushArgumentsLength(ArgumentsStateType type) {
    fields_.push_back(StateValueDescriptor::ArgumentsLength(type));
1258
  }
1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275
  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_;
};
1276

1277 1278
class FrameStateDescriptor : public ZoneObject {
 public:
1279 1280
  FrameStateDescriptor(Zone* zone, FrameStateType type, BailoutId bailout_id,
                       OutputFrameStateCombine state_combine,
1281 1282
                       size_t parameters_count, size_t locals_count,
                       size_t stack_count,
1283
                       MaybeHandle<SharedFunctionInfo> shared_info,
1284
                       FrameStateDescriptor* outer_state = nullptr);
1285

1286
  FrameStateType type() const { return type_; }
1287
  BailoutId bailout_id() const { return bailout_id_; }
1288
  OutputFrameStateCombine state_combine() const { return frame_state_combine_; }
1289 1290 1291
  size_t parameters_count() const { return parameters_count_; }
  size_t locals_count() const { return locals_count_; }
  size_t stack_count() const { return stack_count_; }
1292
  MaybeHandle<SharedFunctionInfo> shared_info() const { return shared_info_; }
1293
  FrameStateDescriptor* outer_state() const { return outer_state_; }
1294
  bool HasContext() const {
1295 1296
    return FrameStateFunctionInfo::IsJSFunctionType(type_) ||
           type_ == FrameStateType::kBuiltinContinuation;
1297
  }
1298

1299
  size_t GetSize() const;
1300 1301 1302
  size_t GetTotalSize() const;
  size_t GetFrameCount() const;
  size_t GetJSFrameCount() const;
1303

1304
  StateValueList* GetStateValueDescriptors() { return &values_; }
1305

1306 1307
  static const int kImpossibleValue = 0xdead;

1308
 private:
1309
  FrameStateType type_;
1310
  BailoutId bailout_id_;
1311
  OutputFrameStateCombine frame_state_combine_;
1312 1313 1314
  size_t parameters_count_;
  size_t locals_count_;
  size_t stack_count_;
1315
  StateValueList values_;
1316
  MaybeHandle<SharedFunctionInfo> const shared_info_;
1317
  FrameStateDescriptor* outer_state_;
1318 1319
};

1320 1321 1322 1323 1324
// 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() {}
1325
  DeoptimizationEntry(FrameStateDescriptor* descriptor, DeoptimizeKind kind,
1326 1327 1328 1329 1330
                      DeoptimizeReason reason, VectorSlotPair const& feedback)
      : descriptor_(descriptor),
        kind_(kind),
        reason_(reason),
        feedback_(feedback) {}
1331 1332

  FrameStateDescriptor* descriptor() const { return descriptor_; }
1333
  DeoptimizeKind kind() const { return kind_; }
1334
  DeoptimizeReason reason() const { return reason_; }
1335
  VectorSlotPair const& feedback() const { return feedback_; }
1336

1337 1338
 private:
  FrameStateDescriptor* descriptor_ = nullptr;
1339
  DeoptimizeKind kind_ = DeoptimizeKind::kEager;
1340
  DeoptimizeReason reason_ = DeoptimizeReason::kUnknown;
1341
  VectorSlotPair feedback_ = VectorSlotPair();
1342
};
1343

1344
typedef ZoneVector<DeoptimizationEntry> DeoptimizationVector;
1345

1346 1347
class V8_EXPORT_PRIVATE PhiInstruction final
    : public NON_EXPORTED_BASE(ZoneObject) {
1348
 public:
1349
  typedef ZoneVector<InstructionOperand> Inputs;
1350

1351 1352 1353
  PhiInstruction(Zone* zone, int virtual_register, size_t input_count);

  void SetInput(size_t offset, int virtual_register);
1354
  void RenameInput(size_t offset, int virtual_register);
1355 1356 1357

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

1359 1360
  // TODO(dcarney): this has no real business being here, since it's internal to
  // the register allocator, but putting it here was convenient.
1361 1362
  const InstructionOperand& output() const { return output_; }
  InstructionOperand& output() { return output_; }
1363 1364 1365

 private:
  const int virtual_register_;
1366
  InstructionOperand output_;
1367 1368 1369 1370 1371
  IntVector operands_;
};


// Analogue of BasicBlock for Instructions instead of Nodes.
1372 1373
class V8_EXPORT_PRIVATE InstructionBlock final
    : public NON_EXPORTED_BASE(ZoneObject) {
1374
 public:
1375
  InstructionBlock(Zone* zone, RpoNumber rpo_number, RpoNumber loop_header,
1376
                   RpoNumber loop_end, bool deferred, bool handler);
1377 1378 1379

  // Instruction indexes (used by the register allocator).
  int first_instruction_index() const {
1380 1381 1382
    DCHECK_LE(0, code_start_);
    DCHECK_LT(0, code_end_);
    DCHECK_GE(code_end_, code_start_);
1383 1384 1385
    return code_start_;
  }
  int last_instruction_index() const {
1386 1387 1388
    DCHECK_LE(0, code_start_);
    DCHECK_LT(0, code_end_);
    DCHECK_GE(code_end_, code_start_);
1389 1390 1391 1392 1393 1394 1395 1396 1397
    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; }

1398
  bool IsDeferred() const { return deferred_; }
1399
  bool IsHandler() const { return handler_; }
1400

1401 1402 1403 1404
  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 {
1405 1406 1407 1408 1409
    DCHECK(IsLoopHeader());
    return loop_end_;
  }
  inline bool IsLoopHeader() const { return loop_end_.IsValid(); }

1410
  typedef ZoneVector<RpoNumber> Predecessors;
1411
  Predecessors& predecessors() { return predecessors_; }
1412 1413
  const Predecessors& predecessors() const { return predecessors_; }
  size_t PredecessorCount() const { return predecessors_.size(); }
1414
  size_t PredecessorIndexOf(RpoNumber rpo_number) const;
1415

1416
  typedef ZoneVector<RpoNumber> Successors;
1417
  Successors& successors() { return successors_; }
1418 1419 1420 1421 1422
  const Successors& successors() const { return successors_; }
  size_t SuccessorCount() const { return successors_.size(); }

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

1426
  void set_ao_number(RpoNumber ao_number) { ao_number_ = ao_number; }
1427

1428 1429 1430 1431 1432 1433 1434 1435 1436
  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; }

1437 1438 1439 1440
 private:
  Successors successors_;
  Predecessors predecessors_;
  PhiInstructions phis_;
1441 1442 1443 1444
  RpoNumber ao_number_;  // Assembly order number.
  const RpoNumber rpo_number_;
  const RpoNumber loop_header_;
  const RpoNumber loop_end_;
1445 1446 1447
  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.
1448
  const bool handler_;   // Block is a handler entry point.
1449 1450 1451
  bool needs_frame_;
  bool must_construct_frame_;
  bool must_deconstruct_frame_;
1452 1453
};

1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464
class InstructionSequence;

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

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

1465
typedef ZoneDeque<Constant> ConstantDeque;
1466
typedef std::map<int, Constant, std::less<int>,
1467 1468
                 ZoneAllocator<std::pair<const int, Constant> > >
    ConstantMap;
1469

1470
typedef ZoneDeque<Instruction*> InstructionDeque;
1471
typedef ZoneDeque<ReferenceMap*> ReferenceMapDeque;
1472
typedef ZoneVector<InstructionBlock*> InstructionBlocks;
1473

1474 1475

// Forward declarations.
1476 1477 1478
struct PrintableInstructionSequence;


1479 1480
// Represents architecture-specific generated code before, during, and after
// register allocation.
1481 1482
class V8_EXPORT_PRIVATE InstructionSequence final
    : public NON_EXPORTED_BASE(ZoneObject) {
1483
 public:
1484 1485
  static InstructionBlocks* InstructionBlocksFor(Zone* zone,
                                                 const Schedule* schedule);
1486 1487
  // Puts the deferred blocks last.
  static void ComputeAssemblyOrder(InstructionBlocks* blocks);
1488

1489 1490
  InstructionSequence(Isolate* isolate, Zone* zone,
                      InstructionBlocks* instruction_blocks);
1491

1492
  int NextVirtualRegister();
1493 1494
  int VirtualRegisterCount() const { return next_virtual_register_; }

1495
  const InstructionBlocks& instruction_blocks() const {
1496
    return *instruction_blocks_;
1497 1498
  }

1499
  int InstructionBlockCount() const {
1500
    return static_cast<int>(instruction_blocks_->size());
1501 1502
  }

1503
  InstructionBlock* InstructionBlockAt(RpoNumber rpo_number) {
1504
    return instruction_blocks_->at(rpo_number.ToSize());
1505 1506
  }

1507
  int LastLoopInstructionIndex(const InstructionBlock* block) {
1508
    return instruction_blocks_->at(block->loop_end().ToSize() - 1)
1509 1510 1511
        ->last_instruction_index();
  }

1512
  const InstructionBlock* InstructionBlockAt(RpoNumber rpo_number) const {
1513
    return instruction_blocks_->at(rpo_number.ToSize());
1514 1515
  }

1516
  InstructionBlock* GetInstructionBlock(int instruction_index) const;
1517

1518 1519
  static MachineRepresentation DefaultRepresentation() {
    return MachineType::PointerRepresentation();
1520
  }
1521 1522
  MachineRepresentation GetRepresentation(int virtual_register) const;
  void MarkAsRepresentation(MachineRepresentation rep, int virtual_register);
1523
  int representation_mask() const { return representation_mask_; }
1524

1525
  bool IsReference(int virtual_register) const {
1526
    return CanBeTaggedPointer(GetRepresentation(virtual_register));
1527
  }
1528
  bool IsFP(int virtual_register) const {
1529
    return IsFloatingPoint(GetRepresentation(virtual_register));
1530
  }
1531

1532
  Instruction* GetBlockStart(RpoNumber rpo) const;
1533 1534 1535 1536

  typedef InstructionDeque::const_iterator const_iterator;
  const_iterator begin() const { return instructions_.begin(); }
  const_iterator end() const { return instructions_.end(); }
1537
  const InstructionDeque& instructions() const { return instructions_; }
1538 1539 1540
  int LastInstructionIndex() const {
    return static_cast<int>(instructions().size()) - 1;
  }
1541 1542

  Instruction* InstructionAt(int index) const {
1543 1544
    DCHECK_LE(0, index);
    DCHECK_GT(instructions_.size(), index);
1545 1546 1547
    return instructions_[index];
  }

1548
  Isolate* isolate() const { return isolate_; }
1549
  const ReferenceMapDeque* reference_maps() const { return &reference_maps_; }
1550
  Zone* zone() const { return zone_; }
1551

1552 1553
  // Used by the instruction selector while adding instructions.
  int AddInstruction(Instruction* instr);
1554 1555
  void StartBlock(RpoNumber rpo);
  void EndBlock(RpoNumber rpo);
1556

1557
  int AddConstant(int virtual_register, Constant constant) {
1558
    // TODO(titzer): allow RPO numbers as constants?
1559
    DCHECK_NE(Constant::kRpoNumber, constant.type());
1560
    DCHECK(virtual_register >= 0 && virtual_register < next_virtual_register_);
1561
    DCHECK(constants_.find(virtual_register) == constants_.end());
1562
    constants_.insert(std::make_pair(virtual_register, constant));
1563
    return virtual_register;
1564 1565 1566
  }
  Constant GetConstant(int virtual_register) const {
    ConstantMap::const_iterator it = constants_.find(virtual_register);
1567 1568
    DCHECK(it != constants_.end());
    DCHECK_EQ(virtual_register, it->first);
1569 1570 1571
    return it->second;
  }

1572 1573
  typedef ZoneVector<Constant> Immediates;
  Immediates& immediates() { return immediates_; }
1574

1575
  ImmediateOperand AddImmediate(const Constant& constant) {
1576 1577
    if (constant.type() == Constant::kInt32 &&
        RelocInfo::IsNone(constant.rmode())) {
1578 1579
      return ImmediateOperand(ImmediateOperand::INLINE, constant.ToInt32());
    }
1580
    int index = static_cast<int>(immediates_.size());
1581
    immediates_.push_back(constant);
1582 1583 1584 1585 1586 1587 1588 1589 1590
    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();
1591 1592
        DCHECK_LE(0, index);
        DCHECK_GT(immediates_.size(), index);
1593 1594 1595 1596
        return immediates_[index];
      }
    }
    UNREACHABLE();
1597 1598
  }

1599
  int AddDeoptimizationEntry(FrameStateDescriptor* descriptor,
1600 1601
                             DeoptimizeKind kind, DeoptimizeReason reason,
                             VectorSlotPair const& feedback);
1602 1603 1604
  DeoptimizationEntry const& GetDeoptimizationEntry(int deoptimization_id);
  int GetDeoptimizationEntryCount() const {
    return static_cast<int>(deoptimization_entries_.size());
1605
  }
1606

1607
  RpoNumber InputRpo(Instruction* instr, size_t index);
1608

1609 1610 1611 1612
  bool GetSourcePosition(const Instruction* instr,
                         SourcePosition* result) const;
  void SetSourcePosition(const Instruction* instr, SourcePosition value);

1613 1614 1615 1616 1617 1618 1619
  bool ContainsCall() const {
    for (Instruction* instr : instructions_) {
      if (instr->IsCall()) return true;
    }
    return false;
  }

1620 1621 1622 1623 1624 1625
  // 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;
1626

1627 1628 1629 1630
  void ValidateEdgeSplitForm() const;
  void ValidateDeferredBlockExitPaths() const;
  void ValidateDeferredBlockEntryPaths() const;
  void ValidateSSA() const;
1631

1632 1633 1634 1635
  static void SetRegisterConfigurationForTesting(
      const RegisterConfiguration* regConfig);
  static void ClearRegisterConfigurationForTesting();

1636
 private:
1637 1638
  friend V8_EXPORT_PRIVATE std::ostream& operator<<(
      std::ostream& os, const PrintableInstructionSequence& code);
1639

1640
  typedef ZoneMap<const Instruction*, SourcePosition> SourcePositionMap;
1641

1642 1643 1644
  static const RegisterConfiguration* RegisterConfigurationForTesting();
  static const RegisterConfiguration* registerConfigurationForTesting_;

1645
  Isolate* isolate_;
1646
  Zone* const zone_;
1647
  InstructionBlocks* const instruction_blocks_;
1648
  SourcePositionMap source_positions_;
1649
  ConstantMap constants_;
1650
  Immediates immediates_;
1651 1652
  InstructionDeque instructions_;
  int next_virtual_register_;
1653
  ReferenceMapDeque reference_maps_;
1654
  ZoneVector<MachineRepresentation> representations_;
1655
  int representation_mask_;
1656
  DeoptimizationVector deoptimization_entries_;
1657

1658 1659 1660
  // Used at construction time
  InstructionBlock* current_block_;

1661
  DISALLOW_COPY_AND_ASSIGN(InstructionSequence);
1662 1663
};

1664 1665 1666 1667 1668 1669

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

1670 1671
V8_EXPORT_PRIVATE std::ostream& operator<<(
    std::ostream& os, const PrintableInstructionSequence& code);
1672 1673 1674 1675 1676 1677

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

#endif  // V8_COMPILER_INSTRUCTION_H_