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