1 // Copyright 2014 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_COMPILER_INSTRUCTION_H_ 6 #define V8_COMPILER_INSTRUCTION_H_ 7 8 #include <deque> 9 #include <iosfwd> 10 #include <map> 11 #include <set> 12 13 #include "src/compiler/common-operator.h" 14 #include "src/compiler/frame.h" 15 #include "src/compiler/instruction-codes.h" 16 #include "src/compiler/opcodes.h" 17 #include "src/compiler/source-position.h" 18 #include "src/macro-assembler.h" 19 #include "src/register-configuration.h" 20 #include "src/zone-allocator.h" 21 22 namespace v8 { 23 namespace internal { 24 namespace compiler { 25 26 // Forward declarations. 27 class Schedule; 28 29 30 class InstructionOperand { 31 public: 32 static const int kInvalidVirtualRegister = -1; 33 34 // TODO(dcarney): recover bit. INVALID can be represented as UNALLOCATED with 35 // kInvalidVirtualRegister and some DCHECKS. 36 enum Kind { INVALID, UNALLOCATED, CONSTANT, IMMEDIATE, EXPLICIT, ALLOCATED }; 37 38 InstructionOperand() : InstructionOperand(INVALID) {} 39 40 Kind kind() const { return KindField::decode(value_); } 41 42 #define INSTRUCTION_OPERAND_PREDICATE(name, type) \ 43 bool Is##name() const { return kind() == type; } 44 INSTRUCTION_OPERAND_PREDICATE(Invalid, INVALID) 45 // UnallocatedOperands are place-holder operands created before register 46 // allocation. They later are assigned registers and become AllocatedOperands. 47 INSTRUCTION_OPERAND_PREDICATE(Unallocated, UNALLOCATED) 48 // Constant operands participate in register allocation. They are allocated to 49 // registers but have a special "spilling" behavior. When a ConstantOperand 50 // value must be rematerialized, it is loaded from an immediate constant 51 // rather from an unspilled slot. 52 INSTRUCTION_OPERAND_PREDICATE(Constant, CONSTANT) 53 // ImmediateOperands do not participate in register allocation and are only 54 // embedded directly in instructions, e.g. small integers and on some 55 // platforms Objects. 56 INSTRUCTION_OPERAND_PREDICATE(Immediate, IMMEDIATE) 57 // ExplicitOperands do not participate in register allocation. They are 58 // created by the instruction selector for direct access to registers and 59 // stack slots, completely bypassing the register allocator. They are never 60 // associated with a virtual register 61 INSTRUCTION_OPERAND_PREDICATE(Explicit, EXPLICIT) 62 // AllocatedOperands are registers or stack slots that are assigned by the 63 // register allocator and are always associated with a virtual register. 64 INSTRUCTION_OPERAND_PREDICATE(Allocated, ALLOCATED) 65 #undef INSTRUCTION_OPERAND_PREDICATE 66 67 inline bool IsAnyRegister() const; 68 inline bool IsRegister() const; 69 inline bool IsFPRegister() const; 70 inline bool IsFloatRegister() const; 71 inline bool IsDoubleRegister() const; 72 inline bool IsSimd128Register() const; 73 inline bool IsStackSlot() const; 74 inline bool IsFPStackSlot() const; 75 inline bool IsFloatStackSlot() const; 76 inline bool IsDoubleStackSlot() const; 77 inline bool IsSimd128StackSlot() const; 78 79 template <typename SubKindOperand> 80 static SubKindOperand* New(Zone* zone, const SubKindOperand& op) { 81 void* buffer = zone->New(sizeof(op)); 82 return new (buffer) SubKindOperand(op); 83 } 84 85 static void ReplaceWith(InstructionOperand* dest, 86 const InstructionOperand* src) { 87 *dest = *src; 88 } 89 90 bool Equals(const InstructionOperand& that) const { 91 return this->value_ == that.value_; 92 } 93 94 bool Compare(const InstructionOperand& that) const { 95 return this->value_ < that.value_; 96 } 97 98 bool EqualsCanonicalized(const InstructionOperand& that) const { 99 return this->GetCanonicalizedValue() == that.GetCanonicalizedValue(); 100 } 101 102 bool CompareCanonicalized(const InstructionOperand& that) const { 103 return this->GetCanonicalizedValue() < that.GetCanonicalizedValue(); 104 } 105 106 bool InterferesWith(const InstructionOperand& that) const; 107 108 void Print(const RegisterConfiguration* config) const; 109 void Print() const; 110 111 protected: 112 explicit InstructionOperand(Kind kind) : value_(KindField::encode(kind)) {} 113 114 inline uint64_t GetCanonicalizedValue() const; 115 116 class KindField : public BitField64<Kind, 0, 3> {}; 117 118 uint64_t value_; 119 }; 120 121 122 typedef ZoneVector<InstructionOperand> InstructionOperandVector; 123 124 125 struct PrintableInstructionOperand { 126 const RegisterConfiguration* register_configuration_; 127 InstructionOperand op_; 128 }; 129 130 131 std::ostream& operator<<(std::ostream& os, 132 const PrintableInstructionOperand& op); 133 134 135 #define INSTRUCTION_OPERAND_CASTS(OperandType, OperandKind) \ 136 \ 137 static OperandType* cast(InstructionOperand* op) { \ 138 DCHECK_EQ(OperandKind, op->kind()); \ 139 return static_cast<OperandType*>(op); \ 140 } \ 141 \ 142 static const OperandType* cast(const InstructionOperand* op) { \ 143 DCHECK_EQ(OperandKind, op->kind()); \ 144 return static_cast<const OperandType*>(op); \ 145 } \ 146 \ 147 static OperandType cast(const InstructionOperand& op) { \ 148 DCHECK_EQ(OperandKind, op.kind()); \ 149 return *static_cast<const OperandType*>(&op); \ 150 } 151 152 class UnallocatedOperand : public InstructionOperand { 153 public: 154 enum BasicPolicy { FIXED_SLOT, EXTENDED_POLICY }; 155 156 enum ExtendedPolicy { 157 NONE, 158 ANY, 159 FIXED_REGISTER, 160 FIXED_FP_REGISTER, 161 MUST_HAVE_REGISTER, 162 MUST_HAVE_SLOT, 163 SAME_AS_FIRST_INPUT 164 }; 165 166 // Lifetime of operand inside the instruction. 167 enum Lifetime { 168 // USED_AT_START operand is guaranteed to be live only at 169 // instruction start. Register allocator is free to assign the same register 170 // to some other operand used inside instruction (i.e. temporary or 171 // output). 172 USED_AT_START, 173 174 // USED_AT_END operand is treated as live until the end of 175 // instruction. This means that register allocator will not reuse it's 176 // register for any other operand inside instruction. 177 USED_AT_END 178 }; 179 180 UnallocatedOperand(ExtendedPolicy policy, int virtual_register) 181 : UnallocatedOperand(virtual_register) { 182 value_ |= BasicPolicyField::encode(EXTENDED_POLICY); 183 value_ |= ExtendedPolicyField::encode(policy); 184 value_ |= LifetimeField::encode(USED_AT_END); 185 } 186 187 UnallocatedOperand(BasicPolicy policy, int index, int virtual_register) 188 : UnallocatedOperand(virtual_register) { 189 DCHECK(policy == FIXED_SLOT); 190 value_ |= BasicPolicyField::encode(policy); 191 value_ |= static_cast<int64_t>(index) << FixedSlotIndexField::kShift; 192 DCHECK(this->fixed_slot_index() == index); 193 } 194 195 UnallocatedOperand(ExtendedPolicy policy, int index, int virtual_register) 196 : UnallocatedOperand(virtual_register) { 197 DCHECK(policy == FIXED_REGISTER || policy == FIXED_FP_REGISTER); 198 value_ |= BasicPolicyField::encode(EXTENDED_POLICY); 199 value_ |= ExtendedPolicyField::encode(policy); 200 value_ |= LifetimeField::encode(USED_AT_END); 201 value_ |= FixedRegisterField::encode(index); 202 } 203 204 UnallocatedOperand(ExtendedPolicy policy, Lifetime lifetime, 205 int virtual_register) 206 : UnallocatedOperand(virtual_register) { 207 value_ |= BasicPolicyField::encode(EXTENDED_POLICY); 208 value_ |= ExtendedPolicyField::encode(policy); 209 value_ |= LifetimeField::encode(lifetime); 210 } 211 212 UnallocatedOperand(int reg_id, int slot_id, int virtual_register) 213 : UnallocatedOperand(FIXED_REGISTER, reg_id, virtual_register) { 214 value_ |= HasSecondaryStorageField::encode(true); 215 value_ |= SecondaryStorageField::encode(slot_id); 216 } 217 218 // Predicates for the operand policy. 219 bool HasAnyPolicy() const { 220 return basic_policy() == EXTENDED_POLICY && extended_policy() == ANY; 221 } 222 bool HasFixedPolicy() const { 223 return basic_policy() == FIXED_SLOT || 224 extended_policy() == FIXED_REGISTER || 225 extended_policy() == FIXED_FP_REGISTER; 226 } 227 bool HasRegisterPolicy() const { 228 return basic_policy() == EXTENDED_POLICY && 229 extended_policy() == MUST_HAVE_REGISTER; 230 } 231 bool HasSlotPolicy() const { 232 return basic_policy() == EXTENDED_POLICY && 233 extended_policy() == MUST_HAVE_SLOT; 234 } 235 bool HasSameAsInputPolicy() const { 236 return basic_policy() == EXTENDED_POLICY && 237 extended_policy() == SAME_AS_FIRST_INPUT; 238 } 239 bool HasFixedSlotPolicy() const { return basic_policy() == FIXED_SLOT; } 240 bool HasFixedRegisterPolicy() const { 241 return basic_policy() == EXTENDED_POLICY && 242 extended_policy() == FIXED_REGISTER; 243 } 244 bool HasFixedFPRegisterPolicy() const { 245 return basic_policy() == EXTENDED_POLICY && 246 extended_policy() == FIXED_FP_REGISTER; 247 } 248 bool HasSecondaryStorage() const { 249 return basic_policy() == EXTENDED_POLICY && 250 extended_policy() == FIXED_REGISTER && 251 HasSecondaryStorageField::decode(value_); 252 } 253 int GetSecondaryStorage() const { 254 DCHECK(HasSecondaryStorage()); 255 return SecondaryStorageField::decode(value_); 256 } 257 258 // [basic_policy]: Distinguish between FIXED_SLOT and all other policies. 259 BasicPolicy basic_policy() const { 260 DCHECK_EQ(UNALLOCATED, kind()); 261 return BasicPolicyField::decode(value_); 262 } 263 264 // [extended_policy]: Only for non-FIXED_SLOT. The finer-grained policy. 265 ExtendedPolicy extended_policy() const { 266 DCHECK(basic_policy() == EXTENDED_POLICY); 267 return ExtendedPolicyField::decode(value_); 268 } 269 270 // [fixed_slot_index]: Only for FIXED_SLOT. 271 int fixed_slot_index() const { 272 DCHECK(HasFixedSlotPolicy()); 273 return static_cast<int>(static_cast<int64_t>(value_) >> 274 FixedSlotIndexField::kShift); 275 } 276 277 // [fixed_register_index]: Only for FIXED_REGISTER or FIXED_FP_REGISTER. 278 int fixed_register_index() const { 279 DCHECK(HasFixedRegisterPolicy() || HasFixedFPRegisterPolicy()); 280 return FixedRegisterField::decode(value_); 281 } 282 283 // [virtual_register]: The virtual register ID for this operand. 284 int32_t virtual_register() const { 285 DCHECK_EQ(UNALLOCATED, kind()); 286 return static_cast<int32_t>(VirtualRegisterField::decode(value_)); 287 } 288 289 // TODO(dcarney): remove this. 290 void set_virtual_register(int32_t id) { 291 DCHECK_EQ(UNALLOCATED, kind()); 292 value_ = VirtualRegisterField::update(value_, static_cast<uint32_t>(id)); 293 } 294 295 // [lifetime]: Only for non-FIXED_SLOT. 296 bool IsUsedAtStart() const { 297 DCHECK(basic_policy() == EXTENDED_POLICY); 298 return LifetimeField::decode(value_) == USED_AT_START; 299 } 300 301 INSTRUCTION_OPERAND_CASTS(UnallocatedOperand, UNALLOCATED); 302 303 // The encoding used for UnallocatedOperand operands depends on the policy 304 // that is 305 // stored within the operand. The FIXED_SLOT policy uses a compact encoding 306 // because it accommodates a larger pay-load. 307 // 308 // For FIXED_SLOT policy: 309 // +------------------------------------------------+ 310 // | slot_index | 0 | virtual_register | 001 | 311 // +------------------------------------------------+ 312 // 313 // For all other (extended) policies: 314 // +-----------------------------------------------------+ 315 // | reg_index | L | PPP | 1 | virtual_register | 001 | 316 // +-----------------------------------------------------+ 317 // L ... Lifetime 318 // P ... Policy 319 // 320 // The slot index is a signed value which requires us to decode it manually 321 // instead of using the BitField utility class. 322 323 STATIC_ASSERT(KindField::kSize == 3); 324 325 class VirtualRegisterField : public BitField64<uint32_t, 3, 32> {}; 326 327 // BitFields for all unallocated operands. 328 class BasicPolicyField : public BitField64<BasicPolicy, 35, 1> {}; 329 330 // BitFields specific to BasicPolicy::FIXED_SLOT. 331 class FixedSlotIndexField : public BitField64<int, 36, 28> {}; 332 333 // BitFields specific to BasicPolicy::EXTENDED_POLICY. 334 class ExtendedPolicyField : public BitField64<ExtendedPolicy, 36, 3> {}; 335 class LifetimeField : public BitField64<Lifetime, 39, 1> {}; 336 class HasSecondaryStorageField : public BitField64<bool, 40, 1> {}; 337 class FixedRegisterField : public BitField64<int, 41, 6> {}; 338 class SecondaryStorageField : public BitField64<int, 47, 3> {}; 339 340 private: 341 explicit UnallocatedOperand(int virtual_register) 342 : InstructionOperand(UNALLOCATED) { 343 value_ |= 344 VirtualRegisterField::encode(static_cast<uint32_t>(virtual_register)); 345 } 346 }; 347 348 349 class ConstantOperand : public InstructionOperand { 350 public: 351 explicit ConstantOperand(int virtual_register) 352 : InstructionOperand(CONSTANT) { 353 value_ |= 354 VirtualRegisterField::encode(static_cast<uint32_t>(virtual_register)); 355 } 356 357 int32_t virtual_register() const { 358 return static_cast<int32_t>(VirtualRegisterField::decode(value_)); 359 } 360 361 static ConstantOperand* New(Zone* zone, int virtual_register) { 362 return InstructionOperand::New(zone, ConstantOperand(virtual_register)); 363 } 364 365 INSTRUCTION_OPERAND_CASTS(ConstantOperand, CONSTANT); 366 367 STATIC_ASSERT(KindField::kSize == 3); 368 class VirtualRegisterField : public BitField64<uint32_t, 3, 32> {}; 369 }; 370 371 372 class ImmediateOperand : public InstructionOperand { 373 public: 374 enum ImmediateType { INLINE, INDEXED }; 375 376 explicit ImmediateOperand(ImmediateType type, int32_t value) 377 : InstructionOperand(IMMEDIATE) { 378 value_ |= TypeField::encode(type); 379 value_ |= static_cast<int64_t>(value) << ValueField::kShift; 380 } 381 382 ImmediateType type() const { return TypeField::decode(value_); } 383 384 int32_t inline_value() const { 385 DCHECK_EQ(INLINE, type()); 386 return static_cast<int64_t>(value_) >> ValueField::kShift; 387 } 388 389 int32_t indexed_value() const { 390 DCHECK_EQ(INDEXED, type()); 391 return static_cast<int64_t>(value_) >> ValueField::kShift; 392 } 393 394 static ImmediateOperand* New(Zone* zone, ImmediateType type, int32_t value) { 395 return InstructionOperand::New(zone, ImmediateOperand(type, value)); 396 } 397 398 INSTRUCTION_OPERAND_CASTS(ImmediateOperand, IMMEDIATE); 399 400 STATIC_ASSERT(KindField::kSize == 3); 401 class TypeField : public BitField64<ImmediateType, 3, 1> {}; 402 class ValueField : public BitField64<int32_t, 32, 32> {}; 403 }; 404 405 406 class LocationOperand : public InstructionOperand { 407 public: 408 enum LocationKind { REGISTER, STACK_SLOT }; 409 410 LocationOperand(InstructionOperand::Kind operand_kind, 411 LocationOperand::LocationKind location_kind, 412 MachineRepresentation rep, int index) 413 : InstructionOperand(operand_kind) { 414 DCHECK_IMPLIES(location_kind == REGISTER, index >= 0); 415 DCHECK(IsSupportedRepresentation(rep)); 416 value_ |= LocationKindField::encode(location_kind); 417 value_ |= RepresentationField::encode(rep); 418 value_ |= static_cast<int64_t>(index) << IndexField::kShift; 419 } 420 421 int index() const { 422 DCHECK(IsStackSlot() || IsFPStackSlot()); 423 return static_cast<int64_t>(value_) >> IndexField::kShift; 424 } 425 426 int register_code() const { 427 DCHECK(IsRegister() || IsFPRegister()); 428 return static_cast<int64_t>(value_) >> IndexField::kShift; 429 } 430 431 Register GetRegister() const { 432 DCHECK(IsRegister()); 433 return Register::from_code(register_code()); 434 } 435 436 FloatRegister GetFloatRegister() const { 437 DCHECK(IsFloatRegister()); 438 return FloatRegister::from_code(register_code()); 439 } 440 441 DoubleRegister GetDoubleRegister() const { 442 // On platforms where FloatRegister, DoubleRegister, and Simd128Register 443 // are all the same type, it's convenient to treat everything as a 444 // DoubleRegister, so be lax about type checking here. 445 DCHECK(IsFPRegister()); 446 return DoubleRegister::from_code(register_code()); 447 } 448 449 Simd128Register GetSimd128Register() const { 450 DCHECK(IsSimd128Register()); 451 return Simd128Register::from_code(register_code()); 452 } 453 454 LocationKind location_kind() const { 455 return LocationKindField::decode(value_); 456 } 457 458 MachineRepresentation representation() const { 459 return RepresentationField::decode(value_); 460 } 461 462 static bool IsSupportedRepresentation(MachineRepresentation rep) { 463 switch (rep) { 464 case MachineRepresentation::kWord32: 465 case MachineRepresentation::kWord64: 466 case MachineRepresentation::kFloat32: 467 case MachineRepresentation::kFloat64: 468 case MachineRepresentation::kSimd128: 469 case MachineRepresentation::kTagged: 470 return true; 471 case MachineRepresentation::kBit: 472 case MachineRepresentation::kWord8: 473 case MachineRepresentation::kWord16: 474 case MachineRepresentation::kNone: 475 return false; 476 } 477 UNREACHABLE(); 478 return false; 479 } 480 481 static LocationOperand* cast(InstructionOperand* op) { 482 DCHECK(ALLOCATED == op->kind() || EXPLICIT == op->kind()); 483 return static_cast<LocationOperand*>(op); 484 } 485 486 static const LocationOperand* cast(const InstructionOperand* op) { 487 DCHECK(ALLOCATED == op->kind() || EXPLICIT == op->kind()); 488 return static_cast<const LocationOperand*>(op); 489 } 490 491 static LocationOperand cast(const InstructionOperand& op) { 492 DCHECK(ALLOCATED == op.kind() || EXPLICIT == op.kind()); 493 return *static_cast<const LocationOperand*>(&op); 494 } 495 496 STATIC_ASSERT(KindField::kSize == 3); 497 class LocationKindField : public BitField64<LocationKind, 3, 2> {}; 498 class RepresentationField : public BitField64<MachineRepresentation, 5, 8> {}; 499 class IndexField : public BitField64<int32_t, 35, 29> {}; 500 }; 501 502 503 class ExplicitOperand : public LocationOperand { 504 public: 505 ExplicitOperand(LocationKind kind, MachineRepresentation rep, int index); 506 507 static ExplicitOperand* New(Zone* zone, LocationKind kind, 508 MachineRepresentation rep, int index) { 509 return InstructionOperand::New(zone, ExplicitOperand(kind, rep, index)); 510 } 511 512 INSTRUCTION_OPERAND_CASTS(ExplicitOperand, EXPLICIT); 513 }; 514 515 516 class AllocatedOperand : public LocationOperand { 517 public: 518 AllocatedOperand(LocationKind kind, MachineRepresentation rep, int index) 519 : LocationOperand(ALLOCATED, kind, rep, index) {} 520 521 static AllocatedOperand* New(Zone* zone, LocationKind kind, 522 MachineRepresentation rep, int index) { 523 return InstructionOperand::New(zone, AllocatedOperand(kind, rep, index)); 524 } 525 526 INSTRUCTION_OPERAND_CASTS(AllocatedOperand, ALLOCATED); 527 }; 528 529 530 #undef INSTRUCTION_OPERAND_CASTS 531 532 533 bool InstructionOperand::IsAnyRegister() const { 534 return (IsAllocated() || IsExplicit()) && 535 LocationOperand::cast(this)->location_kind() == 536 LocationOperand::REGISTER; 537 } 538 539 540 bool InstructionOperand::IsRegister() const { 541 return IsAnyRegister() && 542 !IsFloatingPoint(LocationOperand::cast(this)->representation()); 543 } 544 545 bool InstructionOperand::IsFPRegister() const { 546 return IsAnyRegister() && 547 IsFloatingPoint(LocationOperand::cast(this)->representation()); 548 } 549 550 bool InstructionOperand::IsFloatRegister() const { 551 return IsAnyRegister() && 552 LocationOperand::cast(this)->representation() == 553 MachineRepresentation::kFloat32; 554 } 555 556 bool InstructionOperand::IsDoubleRegister() const { 557 return IsAnyRegister() && 558 LocationOperand::cast(this)->representation() == 559 MachineRepresentation::kFloat64; 560 } 561 562 bool InstructionOperand::IsSimd128Register() const { 563 return IsAnyRegister() && 564 LocationOperand::cast(this)->representation() == 565 MachineRepresentation::kSimd128; 566 } 567 568 bool InstructionOperand::IsStackSlot() const { 569 return (IsAllocated() || IsExplicit()) && 570 LocationOperand::cast(this)->location_kind() == 571 LocationOperand::STACK_SLOT && 572 !IsFloatingPoint(LocationOperand::cast(this)->representation()); 573 } 574 575 bool InstructionOperand::IsFPStackSlot() const { 576 return (IsAllocated() || IsExplicit()) && 577 LocationOperand::cast(this)->location_kind() == 578 LocationOperand::STACK_SLOT && 579 IsFloatingPoint(LocationOperand::cast(this)->representation()); 580 } 581 582 bool InstructionOperand::IsFloatStackSlot() const { 583 return (IsAllocated() || IsExplicit()) && 584 LocationOperand::cast(this)->location_kind() == 585 LocationOperand::STACK_SLOT && 586 LocationOperand::cast(this)->representation() == 587 MachineRepresentation::kFloat32; 588 } 589 590 bool InstructionOperand::IsDoubleStackSlot() const { 591 return (IsAllocated() || IsExplicit()) && 592 LocationOperand::cast(this)->location_kind() == 593 LocationOperand::STACK_SLOT && 594 LocationOperand::cast(this)->representation() == 595 MachineRepresentation::kFloat64; 596 } 597 598 bool InstructionOperand::IsSimd128StackSlot() const { 599 return (IsAllocated() || IsExplicit()) && 600 LocationOperand::cast(this)->location_kind() == 601 LocationOperand::STACK_SLOT && 602 LocationOperand::cast(this)->representation() == 603 MachineRepresentation::kSimd128; 604 } 605 606 uint64_t InstructionOperand::GetCanonicalizedValue() const { 607 if (IsAllocated() || IsExplicit()) { 608 MachineRepresentation rep = LocationOperand::cast(this)->representation(); 609 MachineRepresentation canonical = MachineRepresentation::kNone; 610 if (IsFloatingPoint(rep)) { 611 if (kSimpleFPAliasing) { 612 // Archs with simple aliasing can treat all FP operands the same. 613 canonical = MachineRepresentation::kFloat64; 614 } else { 615 // We need to distinguish FP operands of different reps when FP 616 // aliasing is not simple (e.g. ARM). 617 canonical = rep; 618 } 619 } 620 return InstructionOperand::KindField::update( 621 LocationOperand::RepresentationField::update(this->value_, canonical), 622 LocationOperand::EXPLICIT); 623 } 624 return this->value_; 625 } 626 627 // Required for maps that don't care about machine type. 628 struct CompareOperandModuloType { 629 bool operator()(const InstructionOperand& a, 630 const InstructionOperand& b) const { 631 return a.CompareCanonicalized(b); 632 } 633 }; 634 635 636 class MoveOperands final : public ZoneObject { 637 public: 638 MoveOperands(const InstructionOperand& source, 639 const InstructionOperand& destination) 640 : source_(source), destination_(destination) { 641 DCHECK(!source.IsInvalid() && !destination.IsInvalid()); 642 } 643 644 const InstructionOperand& source() const { return source_; } 645 InstructionOperand& source() { return source_; } 646 void set_source(const InstructionOperand& operand) { source_ = operand; } 647 648 const InstructionOperand& destination() const { return destination_; } 649 InstructionOperand& destination() { return destination_; } 650 void set_destination(const InstructionOperand& operand) { 651 destination_ = operand; 652 } 653 654 // The gap resolver marks moves as "in-progress" by clearing the 655 // destination (but not the source). 656 bool IsPending() const { 657 return destination_.IsInvalid() && !source_.IsInvalid(); 658 } 659 void SetPending() { destination_ = InstructionOperand(); } 660 661 // True if this move is a move into the given destination operand. 662 bool Blocks(const InstructionOperand& destination) const { 663 return !IsEliminated() && source().InterferesWith(destination); 664 } 665 666 // A move is redundant if it's been eliminated or if its source and 667 // destination are the same. 668 bool IsRedundant() const { 669 DCHECK_IMPLIES(!destination_.IsInvalid(), !destination_.IsConstant()); 670 return IsEliminated() || source_.EqualsCanonicalized(destination_); 671 } 672 673 // We clear both operands to indicate move that's been eliminated. 674 void Eliminate() { source_ = destination_ = InstructionOperand(); } 675 bool IsEliminated() const { 676 DCHECK_IMPLIES(source_.IsInvalid(), destination_.IsInvalid()); 677 return source_.IsInvalid(); 678 } 679 680 void Print(const RegisterConfiguration* config) const; 681 void Print() const; 682 683 private: 684 InstructionOperand source_; 685 InstructionOperand destination_; 686 687 DISALLOW_COPY_AND_ASSIGN(MoveOperands); 688 }; 689 690 691 struct PrintableMoveOperands { 692 const RegisterConfiguration* register_configuration_; 693 const MoveOperands* move_operands_; 694 }; 695 696 697 std::ostream& operator<<(std::ostream& os, const PrintableMoveOperands& mo); 698 699 700 class ParallelMove final : public ZoneVector<MoveOperands*>, public ZoneObject { 701 public: 702 explicit ParallelMove(Zone* zone) : ZoneVector<MoveOperands*>(zone) { 703 reserve(4); 704 } 705 706 MoveOperands* AddMove(const InstructionOperand& from, 707 const InstructionOperand& to) { 708 Zone* zone = get_allocator().zone(); 709 return AddMove(from, to, zone); 710 } 711 712 MoveOperands* AddMove(const InstructionOperand& from, 713 const InstructionOperand& to, 714 Zone* operand_allocation_zone) { 715 MoveOperands* move = new (operand_allocation_zone) MoveOperands(from, to); 716 push_back(move); 717 return move; 718 } 719 720 bool IsRedundant() const; 721 722 // Prepare this ParallelMove to insert move as if it happened in a subsequent 723 // ParallelMove. move->source() may be changed. The MoveOperand returned 724 // must be Eliminated. 725 MoveOperands* PrepareInsertAfter(MoveOperands* move) const; 726 727 private: 728 DISALLOW_COPY_AND_ASSIGN(ParallelMove); 729 }; 730 731 732 struct PrintableParallelMove { 733 const RegisterConfiguration* register_configuration_; 734 const ParallelMove* parallel_move_; 735 }; 736 737 738 std::ostream& operator<<(std::ostream& os, const PrintableParallelMove& pm); 739 740 741 class ReferenceMap final : public ZoneObject { 742 public: 743 explicit ReferenceMap(Zone* zone) 744 : reference_operands_(8, zone), instruction_position_(-1) {} 745 746 const ZoneVector<InstructionOperand>& reference_operands() const { 747 return reference_operands_; 748 } 749 int instruction_position() const { return instruction_position_; } 750 751 void set_instruction_position(int pos) { 752 DCHECK(instruction_position_ == -1); 753 instruction_position_ = pos; 754 } 755 756 void RecordReference(const AllocatedOperand& op); 757 758 private: 759 friend std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm); 760 761 ZoneVector<InstructionOperand> reference_operands_; 762 int instruction_position_; 763 }; 764 765 std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm); 766 767 class InstructionBlock; 768 769 class Instruction final { 770 public: 771 size_t OutputCount() const { return OutputCountField::decode(bit_field_); } 772 const InstructionOperand* OutputAt(size_t i) const { 773 DCHECK(i < OutputCount()); 774 return &operands_[i]; 775 } 776 InstructionOperand* OutputAt(size_t i) { 777 DCHECK(i < OutputCount()); 778 return &operands_[i]; 779 } 780 781 bool HasOutput() const { return OutputCount() == 1; } 782 const InstructionOperand* Output() const { return OutputAt(0); } 783 InstructionOperand* Output() { return OutputAt(0); } 784 785 size_t InputCount() const { return InputCountField::decode(bit_field_); } 786 const InstructionOperand* InputAt(size_t i) const { 787 DCHECK(i < InputCount()); 788 return &operands_[OutputCount() + i]; 789 } 790 InstructionOperand* InputAt(size_t i) { 791 DCHECK(i < InputCount()); 792 return &operands_[OutputCount() + i]; 793 } 794 795 size_t TempCount() const { return TempCountField::decode(bit_field_); } 796 const InstructionOperand* TempAt(size_t i) const { 797 DCHECK(i < TempCount()); 798 return &operands_[OutputCount() + InputCount() + i]; 799 } 800 InstructionOperand* TempAt(size_t i) { 801 DCHECK(i < TempCount()); 802 return &operands_[OutputCount() + InputCount() + i]; 803 } 804 805 InstructionCode opcode() const { return opcode_; } 806 ArchOpcode arch_opcode() const { return ArchOpcodeField::decode(opcode()); } 807 AddressingMode addressing_mode() const { 808 return AddressingModeField::decode(opcode()); 809 } 810 FlagsMode flags_mode() const { return FlagsModeField::decode(opcode()); } 811 FlagsCondition flags_condition() const { 812 return FlagsConditionField::decode(opcode()); 813 } 814 815 static Instruction* New(Zone* zone, InstructionCode opcode) { 816 return New(zone, opcode, 0, nullptr, 0, nullptr, 0, nullptr); 817 } 818 819 static Instruction* New(Zone* zone, InstructionCode opcode, 820 size_t output_count, InstructionOperand* outputs, 821 size_t input_count, InstructionOperand* inputs, 822 size_t temp_count, InstructionOperand* temps) { 823 DCHECK(opcode >= 0); 824 DCHECK(output_count == 0 || outputs != nullptr); 825 DCHECK(input_count == 0 || inputs != nullptr); 826 DCHECK(temp_count == 0 || temps != nullptr); 827 // TODO(jarin/mstarzinger): Handle this gracefully. See crbug.com/582702. 828 CHECK(InputCountField::is_valid(input_count)); 829 830 size_t total_extra_ops = output_count + input_count + temp_count; 831 if (total_extra_ops != 0) total_extra_ops--; 832 int size = static_cast<int>( 833 RoundUp(sizeof(Instruction), sizeof(InstructionOperand)) + 834 total_extra_ops * sizeof(InstructionOperand)); 835 return new (zone->New(size)) Instruction( 836 opcode, output_count, outputs, input_count, inputs, temp_count, temps); 837 } 838 839 Instruction* MarkAsCall() { 840 bit_field_ = IsCallField::update(bit_field_, true); 841 return this; 842 } 843 bool IsCall() const { return IsCallField::decode(bit_field_); } 844 bool NeedsReferenceMap() const { return IsCall(); } 845 bool HasReferenceMap() const { return reference_map_ != nullptr; } 846 847 bool ClobbersRegisters() const { return IsCall(); } 848 bool ClobbersTemps() const { return IsCall(); } 849 bool ClobbersDoubleRegisters() const { return IsCall(); } 850 ReferenceMap* reference_map() const { return reference_map_; } 851 852 void set_reference_map(ReferenceMap* map) { 853 DCHECK(NeedsReferenceMap()); 854 DCHECK(!reference_map_); 855 reference_map_ = map; 856 } 857 858 void OverwriteWithNop() { 859 opcode_ = ArchOpcodeField::encode(kArchNop); 860 bit_field_ = 0; 861 reference_map_ = nullptr; 862 } 863 864 bool IsNop() const { 865 return arch_opcode() == kArchNop && InputCount() == 0 && 866 OutputCount() == 0 && TempCount() == 0; 867 } 868 869 bool IsDeoptimizeCall() const { 870 return arch_opcode() == ArchOpcode::kArchDeoptimize || 871 FlagsModeField::decode(opcode()) == kFlags_deoptimize; 872 } 873 874 bool IsJump() const { return arch_opcode() == ArchOpcode::kArchJmp; } 875 bool IsRet() const { return arch_opcode() == ArchOpcode::kArchRet; } 876 bool IsTailCall() const { 877 return arch_opcode() == ArchOpcode::kArchTailCallCodeObject || 878 arch_opcode() == ArchOpcode::kArchTailCallCodeObjectFromJSFunction || 879 arch_opcode() == ArchOpcode::kArchTailCallJSFunction || 880 arch_opcode() == ArchOpcode::kArchTailCallJSFunctionFromJSFunction || 881 arch_opcode() == ArchOpcode::kArchTailCallAddress; 882 } 883 bool IsThrow() const { 884 return arch_opcode() == ArchOpcode::kArchThrowTerminator; 885 } 886 887 enum GapPosition { 888 START, 889 END, 890 FIRST_GAP_POSITION = START, 891 LAST_GAP_POSITION = END 892 }; 893 894 ParallelMove* GetOrCreateParallelMove(GapPosition pos, Zone* zone) { 895 if (parallel_moves_[pos] == nullptr) { 896 parallel_moves_[pos] = new (zone) ParallelMove(zone); 897 } 898 return parallel_moves_[pos]; 899 } 900 901 ParallelMove* GetParallelMove(GapPosition pos) { 902 return parallel_moves_[pos]; 903 } 904 905 const ParallelMove* GetParallelMove(GapPosition pos) const { 906 return parallel_moves_[pos]; 907 } 908 909 bool AreMovesRedundant() const; 910 911 ParallelMove* const* parallel_moves() const { return ¶llel_moves_[0]; } 912 ParallelMove** parallel_moves() { return ¶llel_moves_[0]; } 913 914 // The block_id may be invalidated in JumpThreading. It is only important for 915 // register allocation, to avoid searching for blocks from instruction 916 // indexes. 917 InstructionBlock* block() const { return block_; } 918 void set_block(InstructionBlock* block) { 919 DCHECK_NOT_NULL(block); 920 block_ = block; 921 } 922 923 void Print(const RegisterConfiguration* config) const; 924 void Print() const; 925 926 private: 927 explicit Instruction(InstructionCode opcode); 928 929 Instruction(InstructionCode opcode, size_t output_count, 930 InstructionOperand* outputs, size_t input_count, 931 InstructionOperand* inputs, size_t temp_count, 932 InstructionOperand* temps); 933 934 typedef BitField<size_t, 0, 8> OutputCountField; 935 typedef BitField<size_t, 8, 16> InputCountField; 936 typedef BitField<size_t, 24, 6> TempCountField; 937 typedef BitField<bool, 30, 1> IsCallField; 938 939 InstructionCode opcode_; 940 uint32_t bit_field_; 941 ParallelMove* parallel_moves_[2]; 942 ReferenceMap* reference_map_; 943 InstructionBlock* block_; 944 InstructionOperand operands_[1]; 945 946 DISALLOW_COPY_AND_ASSIGN(Instruction); 947 }; 948 949 950 struct PrintableInstruction { 951 const RegisterConfiguration* register_configuration_; 952 const Instruction* instr_; 953 }; 954 std::ostream& operator<<(std::ostream& os, const PrintableInstruction& instr); 955 956 957 class RpoNumber final { 958 public: 959 static const int kInvalidRpoNumber = -1; 960 int ToInt() const { 961 DCHECK(IsValid()); 962 return index_; 963 } 964 size_t ToSize() const { 965 DCHECK(IsValid()); 966 return static_cast<size_t>(index_); 967 } 968 bool IsValid() const { return index_ >= 0; } 969 static RpoNumber FromInt(int index) { return RpoNumber(index); } 970 static RpoNumber Invalid() { return RpoNumber(kInvalidRpoNumber); } 971 972 bool IsNext(const RpoNumber other) const { 973 DCHECK(IsValid()); 974 return other.index_ == this->index_ + 1; 975 } 976 977 // Comparison operators. 978 bool operator==(RpoNumber other) const { return index_ == other.index_; } 979 bool operator!=(RpoNumber other) const { return index_ != other.index_; } 980 bool operator>(RpoNumber other) const { return index_ > other.index_; } 981 bool operator<(RpoNumber other) const { return index_ < other.index_; } 982 bool operator<=(RpoNumber other) const { return index_ <= other.index_; } 983 bool operator>=(RpoNumber other) const { return index_ >= other.index_; } 984 985 private: 986 explicit RpoNumber(int32_t index) : index_(index) {} 987 int32_t index_; 988 }; 989 990 991 std::ostream& operator<<(std::ostream&, const RpoNumber&); 992 993 994 class Constant final { 995 public: 996 enum Type { 997 kInt32, 998 kInt64, 999 kFloat32, 1000 kFloat64, 1001 kExternalReference, 1002 kHeapObject, 1003 kRpoNumber 1004 }; 1005 1006 explicit Constant(int32_t v); 1007 explicit Constant(int64_t v) : type_(kInt64), value_(v) {} 1008 explicit Constant(float v) : type_(kFloat32), value_(bit_cast<int32_t>(v)) {} 1009 explicit Constant(double v) : type_(kFloat64), value_(bit_cast<int64_t>(v)) {} 1010 explicit Constant(ExternalReference ref) 1011 : type_(kExternalReference), value_(bit_cast<intptr_t>(ref)) {} 1012 explicit Constant(Handle<HeapObject> obj) 1013 : type_(kHeapObject), value_(bit_cast<intptr_t>(obj)) {} 1014 explicit Constant(RpoNumber rpo) : type_(kRpoNumber), value_(rpo.ToInt()) {} 1015 explicit Constant(RelocatablePtrConstantInfo info); 1016 1017 Type type() const { return type_; } 1018 1019 RelocInfo::Mode rmode() const { return rmode_; } 1020 1021 int32_t ToInt32() const { 1022 DCHECK(type() == kInt32 || type() == kInt64); 1023 const int32_t value = static_cast<int32_t>(value_); 1024 DCHECK_EQ(value_, static_cast<int64_t>(value)); 1025 return value; 1026 } 1027 1028 int64_t ToInt64() const { 1029 if (type() == kInt32) return ToInt32(); 1030 DCHECK_EQ(kInt64, type()); 1031 return value_; 1032 } 1033 1034 float ToFloat32() const { 1035 DCHECK_EQ(kFloat32, type()); 1036 return bit_cast<float>(static_cast<int32_t>(value_)); 1037 } 1038 1039 double ToFloat64() const { 1040 if (type() == kInt32) return ToInt32(); 1041 DCHECK_EQ(kFloat64, type()); 1042 return bit_cast<double>(value_); 1043 } 1044 1045 ExternalReference ToExternalReference() const { 1046 DCHECK_EQ(kExternalReference, type()); 1047 return bit_cast<ExternalReference>(static_cast<intptr_t>(value_)); 1048 } 1049 1050 RpoNumber ToRpoNumber() const { 1051 DCHECK_EQ(kRpoNumber, type()); 1052 return RpoNumber::FromInt(static_cast<int>(value_)); 1053 } 1054 1055 Handle<HeapObject> ToHeapObject() const; 1056 1057 private: 1058 Type type_; 1059 int64_t value_; 1060 #if V8_TARGET_ARCH_32_BIT 1061 RelocInfo::Mode rmode_ = RelocInfo::NONE32; 1062 #else 1063 RelocInfo::Mode rmode_ = RelocInfo::NONE64; 1064 #endif 1065 }; 1066 1067 1068 std::ostream& operator<<(std::ostream& os, const Constant& constant); 1069 1070 1071 // Forward declarations. 1072 class FrameStateDescriptor; 1073 1074 1075 enum class StateValueKind { kPlain, kNested, kDuplicate }; 1076 1077 1078 class StateValueDescriptor { 1079 public: 1080 explicit StateValueDescriptor(Zone* zone) 1081 : kind_(StateValueKind::kPlain), 1082 type_(MachineType::AnyTagged()), 1083 id_(0), 1084 fields_(zone) {} 1085 1086 static StateValueDescriptor Plain(Zone* zone, MachineType type) { 1087 return StateValueDescriptor(StateValueKind::kPlain, zone, type, 0); 1088 } 1089 static StateValueDescriptor Recursive(Zone* zone, size_t id) { 1090 return StateValueDescriptor(StateValueKind::kNested, zone, 1091 MachineType::AnyTagged(), id); 1092 } 1093 static StateValueDescriptor Duplicate(Zone* zone, size_t id) { 1094 return StateValueDescriptor(StateValueKind::kDuplicate, zone, 1095 MachineType::AnyTagged(), id); 1096 } 1097 1098 size_t size() { return fields_.size(); } 1099 ZoneVector<StateValueDescriptor>& fields() { return fields_; } 1100 int IsPlain() { return kind_ == StateValueKind::kPlain; } 1101 int IsNested() { return kind_ == StateValueKind::kNested; } 1102 int IsDuplicate() { return kind_ == StateValueKind::kDuplicate; } 1103 MachineType type() const { return type_; } 1104 MachineType GetOperandType(size_t index) const { 1105 return fields_[index].type_; 1106 } 1107 size_t id() const { return id_; } 1108 1109 private: 1110 StateValueDescriptor(StateValueKind kind, Zone* zone, MachineType type, 1111 size_t id) 1112 : kind_(kind), type_(type), id_(id), fields_(zone) {} 1113 1114 StateValueKind kind_; 1115 MachineType type_; 1116 size_t id_; 1117 ZoneVector<StateValueDescriptor> fields_; 1118 }; 1119 1120 1121 class FrameStateDescriptor : public ZoneObject { 1122 public: 1123 FrameStateDescriptor(Zone* zone, FrameStateType type, BailoutId bailout_id, 1124 OutputFrameStateCombine state_combine, 1125 size_t parameters_count, size_t locals_count, 1126 size_t stack_count, 1127 MaybeHandle<SharedFunctionInfo> shared_info, 1128 FrameStateDescriptor* outer_state = nullptr); 1129 1130 FrameStateType type() const { return type_; } 1131 BailoutId bailout_id() const { return bailout_id_; } 1132 OutputFrameStateCombine state_combine() const { return frame_state_combine_; } 1133 size_t parameters_count() const { return parameters_count_; } 1134 size_t locals_count() const { return locals_count_; } 1135 size_t stack_count() const { return stack_count_; } 1136 MaybeHandle<SharedFunctionInfo> shared_info() const { return shared_info_; } 1137 FrameStateDescriptor* outer_state() const { return outer_state_; } 1138 bool HasContext() const { 1139 return FrameStateFunctionInfo::IsJSFunctionType(type_); 1140 } 1141 1142 size_t GetSize(OutputFrameStateCombine combine = 1143 OutputFrameStateCombine::Ignore()) const; 1144 size_t GetTotalSize() const; 1145 size_t GetFrameCount() const; 1146 size_t GetJSFrameCount() const; 1147 1148 MachineType GetType(size_t index) const { 1149 return values_.GetOperandType(index); 1150 } 1151 StateValueDescriptor* GetStateValueDescriptor() { return &values_; } 1152 1153 private: 1154 FrameStateType type_; 1155 BailoutId bailout_id_; 1156 OutputFrameStateCombine frame_state_combine_; 1157 size_t parameters_count_; 1158 size_t locals_count_; 1159 size_t stack_count_; 1160 StateValueDescriptor values_; 1161 MaybeHandle<SharedFunctionInfo> const shared_info_; 1162 FrameStateDescriptor* outer_state_; 1163 }; 1164 1165 1166 typedef ZoneVector<FrameStateDescriptor*> DeoptimizationVector; 1167 1168 1169 class PhiInstruction final : public ZoneObject { 1170 public: 1171 typedef ZoneVector<InstructionOperand> Inputs; 1172 1173 PhiInstruction(Zone* zone, int virtual_register, size_t input_count); 1174 1175 void SetInput(size_t offset, int virtual_register); 1176 1177 int virtual_register() const { return virtual_register_; } 1178 const IntVector& operands() const { return operands_; } 1179 1180 // TODO(dcarney): this has no real business being here, since it's internal to 1181 // the register allocator, but putting it here was convenient. 1182 const InstructionOperand& output() const { return output_; } 1183 InstructionOperand& output() { return output_; } 1184 1185 private: 1186 const int virtual_register_; 1187 InstructionOperand output_; 1188 IntVector operands_; 1189 }; 1190 1191 1192 // Analogue of BasicBlock for Instructions instead of Nodes. 1193 class InstructionBlock final : public ZoneObject { 1194 public: 1195 InstructionBlock(Zone* zone, RpoNumber rpo_number, RpoNumber loop_header, 1196 RpoNumber loop_end, bool deferred, bool handler); 1197 1198 // Instruction indexes (used by the register allocator). 1199 int first_instruction_index() const { 1200 DCHECK(code_start_ >= 0); 1201 DCHECK(code_end_ > 0); 1202 DCHECK(code_end_ >= code_start_); 1203 return code_start_; 1204 } 1205 int last_instruction_index() const { 1206 DCHECK(code_start_ >= 0); 1207 DCHECK(code_end_ > 0); 1208 DCHECK(code_end_ >= code_start_); 1209 return code_end_ - 1; 1210 } 1211 1212 int32_t code_start() const { return code_start_; } 1213 void set_code_start(int32_t start) { code_start_ = start; } 1214 1215 int32_t code_end() const { return code_end_; } 1216 void set_code_end(int32_t end) { code_end_ = end; } 1217 1218 bool IsDeferred() const { return deferred_; } 1219 bool IsHandler() const { return handler_; } 1220 1221 RpoNumber ao_number() const { return ao_number_; } 1222 RpoNumber rpo_number() const { return rpo_number_; } 1223 RpoNumber loop_header() const { return loop_header_; } 1224 RpoNumber loop_end() const { 1225 DCHECK(IsLoopHeader()); 1226 return loop_end_; 1227 } 1228 inline bool IsLoopHeader() const { return loop_end_.IsValid(); } 1229 1230 typedef ZoneVector<RpoNumber> Predecessors; 1231 Predecessors& predecessors() { return predecessors_; } 1232 const Predecessors& predecessors() const { return predecessors_; } 1233 size_t PredecessorCount() const { return predecessors_.size(); } 1234 size_t PredecessorIndexOf(RpoNumber rpo_number) const; 1235 1236 typedef ZoneVector<RpoNumber> Successors; 1237 Successors& successors() { return successors_; } 1238 const Successors& successors() const { return successors_; } 1239 size_t SuccessorCount() const { return successors_.size(); } 1240 1241 typedef ZoneVector<PhiInstruction*> PhiInstructions; 1242 const PhiInstructions& phis() const { return phis_; } 1243 void AddPhi(PhiInstruction* phi) { phis_.push_back(phi); } 1244 1245 void set_ao_number(RpoNumber ao_number) { ao_number_ = ao_number; } 1246 1247 bool needs_frame() const { return needs_frame_; } 1248 void mark_needs_frame() { needs_frame_ = true; } 1249 1250 bool must_construct_frame() const { return must_construct_frame_; } 1251 void mark_must_construct_frame() { must_construct_frame_ = true; } 1252 1253 bool must_deconstruct_frame() const { return must_deconstruct_frame_; } 1254 void mark_must_deconstruct_frame() { must_deconstruct_frame_ = true; } 1255 1256 void set_last_deferred(RpoNumber last) { last_deferred_ = last; } 1257 RpoNumber last_deferred() const { return last_deferred_; } 1258 1259 private: 1260 Successors successors_; 1261 Predecessors predecessors_; 1262 PhiInstructions phis_; 1263 RpoNumber ao_number_; // Assembly order number. 1264 const RpoNumber rpo_number_; 1265 const RpoNumber loop_header_; 1266 const RpoNumber loop_end_; 1267 int32_t code_start_; // start index of arch-specific code. 1268 int32_t code_end_; // end index of arch-specific code. 1269 const bool deferred_; // Block contains deferred code. 1270 const bool handler_; // Block is a handler entry point. 1271 bool needs_frame_; 1272 bool must_construct_frame_; 1273 bool must_deconstruct_frame_; 1274 RpoNumber last_deferred_; 1275 }; 1276 1277 typedef ZoneDeque<Constant> ConstantDeque; 1278 typedef std::map<int, Constant, std::less<int>, 1279 zone_allocator<std::pair<const int, Constant> > > ConstantMap; 1280 1281 typedef ZoneDeque<Instruction*> InstructionDeque; 1282 typedef ZoneDeque<ReferenceMap*> ReferenceMapDeque; 1283 typedef ZoneVector<InstructionBlock*> InstructionBlocks; 1284 1285 1286 // Forward declarations. 1287 struct PrintableInstructionSequence; 1288 1289 1290 // Represents architecture-specific generated code before, during, and after 1291 // register allocation. 1292 class InstructionSequence final : public ZoneObject { 1293 public: 1294 static InstructionBlocks* InstructionBlocksFor(Zone* zone, 1295 const Schedule* schedule); 1296 // Puts the deferred blocks last. 1297 static void ComputeAssemblyOrder(InstructionBlocks* blocks); 1298 1299 InstructionSequence(Isolate* isolate, Zone* zone, 1300 InstructionBlocks* instruction_blocks); 1301 1302 int NextVirtualRegister(); 1303 int VirtualRegisterCount() const { return next_virtual_register_; } 1304 1305 const InstructionBlocks& instruction_blocks() const { 1306 return *instruction_blocks_; 1307 } 1308 1309 int InstructionBlockCount() const { 1310 return static_cast<int>(instruction_blocks_->size()); 1311 } 1312 1313 InstructionBlock* InstructionBlockAt(RpoNumber rpo_number) { 1314 return instruction_blocks_->at(rpo_number.ToSize()); 1315 } 1316 1317 int LastLoopInstructionIndex(const InstructionBlock* block) { 1318 return instruction_blocks_->at(block->loop_end().ToSize() - 1) 1319 ->last_instruction_index(); 1320 } 1321 1322 const InstructionBlock* InstructionBlockAt(RpoNumber rpo_number) const { 1323 return instruction_blocks_->at(rpo_number.ToSize()); 1324 } 1325 1326 InstructionBlock* GetInstructionBlock(int instruction_index) const; 1327 1328 static MachineRepresentation DefaultRepresentation() { 1329 return MachineType::PointerRepresentation(); 1330 } 1331 MachineRepresentation GetRepresentation(int virtual_register) const; 1332 void MarkAsRepresentation(MachineRepresentation rep, int virtual_register); 1333 1334 bool IsReference(int virtual_register) const { 1335 return GetRepresentation(virtual_register) == 1336 MachineRepresentation::kTagged; 1337 } 1338 bool IsFP(int virtual_register) const { 1339 return IsFloatingPoint(GetRepresentation(virtual_register)); 1340 } 1341 bool IsFloat(int virtual_register) const { 1342 return GetRepresentation(virtual_register) == 1343 MachineRepresentation::kFloat32; 1344 } 1345 bool IsDouble(int virtual_register) const { 1346 return GetRepresentation(virtual_register) == 1347 MachineRepresentation::kFloat64; 1348 } 1349 1350 Instruction* GetBlockStart(RpoNumber rpo) const; 1351 1352 typedef InstructionDeque::const_iterator const_iterator; 1353 const_iterator begin() const { return instructions_.begin(); } 1354 const_iterator end() const { return instructions_.end(); } 1355 const InstructionDeque& instructions() const { return instructions_; } 1356 int LastInstructionIndex() const { 1357 return static_cast<int>(instructions().size()) - 1; 1358 } 1359 1360 Instruction* InstructionAt(int index) const { 1361 DCHECK(index >= 0); 1362 DCHECK(index < static_cast<int>(instructions_.size())); 1363 return instructions_[index]; 1364 } 1365 1366 Isolate* isolate() const { return isolate_; } 1367 const ReferenceMapDeque* reference_maps() const { return &reference_maps_; } 1368 Zone* zone() const { return zone_; } 1369 1370 // Used by the instruction selector while adding instructions. 1371 int AddInstruction(Instruction* instr); 1372 void StartBlock(RpoNumber rpo); 1373 void EndBlock(RpoNumber rpo); 1374 1375 int AddConstant(int virtual_register, Constant constant) { 1376 // TODO(titzer): allow RPO numbers as constants? 1377 DCHECK(constant.type() != Constant::kRpoNumber); 1378 DCHECK(virtual_register >= 0 && virtual_register < next_virtual_register_); 1379 DCHECK(constants_.find(virtual_register) == constants_.end()); 1380 constants_.insert(std::make_pair(virtual_register, constant)); 1381 return virtual_register; 1382 } 1383 Constant GetConstant(int virtual_register) const { 1384 ConstantMap::const_iterator it = constants_.find(virtual_register); 1385 DCHECK(it != constants_.end()); 1386 DCHECK_EQ(virtual_register, it->first); 1387 return it->second; 1388 } 1389 1390 typedef ZoneVector<Constant> Immediates; 1391 Immediates& immediates() { return immediates_; } 1392 1393 ImmediateOperand AddImmediate(const Constant& constant) { 1394 if (constant.type() == Constant::kInt32 && 1395 RelocInfo::IsNone(constant.rmode())) { 1396 return ImmediateOperand(ImmediateOperand::INLINE, constant.ToInt32()); 1397 } 1398 int index = static_cast<int>(immediates_.size()); 1399 immediates_.push_back(constant); 1400 return ImmediateOperand(ImmediateOperand::INDEXED, index); 1401 } 1402 1403 Constant GetImmediate(const ImmediateOperand* op) const { 1404 switch (op->type()) { 1405 case ImmediateOperand::INLINE: 1406 return Constant(op->inline_value()); 1407 case ImmediateOperand::INDEXED: { 1408 int index = op->indexed_value(); 1409 DCHECK(index >= 0); 1410 DCHECK(index < static_cast<int>(immediates_.size())); 1411 return immediates_[index]; 1412 } 1413 } 1414 UNREACHABLE(); 1415 return Constant(static_cast<int32_t>(0)); 1416 } 1417 1418 class StateId { 1419 public: 1420 static StateId FromInt(int id) { return StateId(id); } 1421 int ToInt() const { return id_; } 1422 1423 private: 1424 explicit StateId(int id) : id_(id) {} 1425 int id_; 1426 }; 1427 1428 StateId AddFrameStateDescriptor(FrameStateDescriptor* descriptor); 1429 FrameStateDescriptor* GetFrameStateDescriptor(StateId deoptimization_id); 1430 int GetFrameStateDescriptorCount(); 1431 DeoptimizationVector const& frame_state_descriptors() const { 1432 return deoptimization_entries_; 1433 } 1434 1435 RpoNumber InputRpo(Instruction* instr, size_t index); 1436 1437 bool GetSourcePosition(const Instruction* instr, 1438 SourcePosition* result) const; 1439 void SetSourcePosition(const Instruction* instr, SourcePosition value); 1440 1441 bool ContainsCall() const { 1442 for (Instruction* instr : instructions_) { 1443 if (instr->IsCall()) return true; 1444 } 1445 return false; 1446 } 1447 void Print(const RegisterConfiguration* config) const; 1448 void Print() const; 1449 1450 void PrintBlock(const RegisterConfiguration* config, int block_id) const; 1451 void PrintBlock(int block_id) const; 1452 1453 void ValidateEdgeSplitForm() const; 1454 void ValidateDeferredBlockExitPaths() const; 1455 void ValidateDeferredBlockEntryPaths() const; 1456 void ValidateSSA() const; 1457 1458 private: 1459 friend std::ostream& operator<<(std::ostream& os, 1460 const PrintableInstructionSequence& code); 1461 1462 typedef ZoneMap<const Instruction*, SourcePosition> SourcePositionMap; 1463 1464 Isolate* isolate_; 1465 Zone* const zone_; 1466 InstructionBlocks* const instruction_blocks_; 1467 SourcePositionMap source_positions_; 1468 ConstantMap constants_; 1469 Immediates immediates_; 1470 InstructionDeque instructions_; 1471 int next_virtual_register_; 1472 ReferenceMapDeque reference_maps_; 1473 ZoneVector<MachineRepresentation> representations_; 1474 DeoptimizationVector deoptimization_entries_; 1475 1476 // Used at construction time 1477 InstructionBlock* current_block_; 1478 1479 DISALLOW_COPY_AND_ASSIGN(InstructionSequence); 1480 }; 1481 1482 1483 struct PrintableInstructionSequence { 1484 const RegisterConfiguration* register_configuration_; 1485 const InstructionSequence* sequence_; 1486 }; 1487 1488 1489 std::ostream& operator<<(std::ostream& os, 1490 const PrintableInstructionSequence& code); 1491 1492 } // namespace compiler 1493 } // namespace internal 1494 } // namespace v8 1495 1496 #endif // V8_COMPILER_INSTRUCTION_H_ 1497