deps/v8/src/compiler/instruction.cc

   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 #include "src/compiler/common-operator.h"
   6 #include "src/compiler/graph.h"
   7 #include "src/compiler/instruction.h"
   8 #include "src/compiler/schedule.h"
   9
  10 namespace v8 {
  11 namespace internal {
  12 namespace compiler {
  13
  14 std::ostream& operator<<(std::ostream& os,
  15                          const PrintableInstructionOperand& printable) {
  16   const InstructionOperand& op = *printable.op_;
  17   const RegisterConfiguration* conf = printable.register_configuration_;
  18   switch (op.kind()) {
  19     case InstructionOperand::UNALLOCATED: {
  20       const UnallocatedOperand* unalloc = UnallocatedOperand::cast(&op);
  21       os << "v" << unalloc->virtual_register();
  22       if (unalloc->basic_policy() == UnallocatedOperand::FIXED_SLOT) {
  23         return os << "(=" << unalloc->fixed_slot_index() << "S)";
  24       }
  25       switch (unalloc->extended_policy()) {
  26         case UnallocatedOperand::NONE:
  27           return os;
  28         case UnallocatedOperand::FIXED_REGISTER:
  29           return os << "(=" << conf->general_register_name(
  30                                    unalloc->fixed_register_index()) << ")";
  31         case UnallocatedOperand::FIXED_DOUBLE_REGISTER:
  32           return os << "(=" << conf->double_register_name(
  33                                    unalloc->fixed_register_index()) << ")";
  34         case UnallocatedOperand::MUST_HAVE_REGISTER:
  35           return os << "(R)";
  36         case UnallocatedOperand::MUST_HAVE_SLOT:
  37           return os << "(S)";
  38         case UnallocatedOperand::SAME_AS_FIRST_INPUT:
  39           return os << "(1)";
  40         case UnallocatedOperand::ANY:
  41           return os << "(-)";
  42       }
  43     }
  44     case InstructionOperand::CONSTANT:
  45       return os << "[constant:" << op.index() << "]";
  46     case InstructionOperand::IMMEDIATE:
  47       return os << "[immediate:" << op.index() << "]";
  48     case InstructionOperand::STACK_SLOT:
  49       return os << "[stack:" << op.index() << "]";
  50     case InstructionOperand::DOUBLE_STACK_SLOT:
  51       return os << "[double_stack:" << op.index() << "]";
  52     case InstructionOperand::REGISTER:
  53       return os << "[" << conf->general_register_name(op.index()) << "|R]";
  54     case InstructionOperand::DOUBLE_REGISTER:
  55       return os << "[" << conf->double_register_name(op.index()) << "|R]";
  56     case InstructionOperand::INVALID:
  57       return os << "(x)";
  58   }
  59   UNREACHABLE();
  60   return os;
  61 }
  62
  63
  64 std::ostream& operator<<(std::ostream& os,
  65                          const PrintableMoveOperands& printable) {
  66   const MoveOperands& mo = *printable.move_operands_;
  67   PrintableInstructionOperand printable_op = {printable.register_configuration_,
  68                                               mo.destination()};
  69
  70   os << printable_op;
  71   if (!mo.source()->Equals(mo.destination())) {
  72     printable_op.op_ = mo.source();
  73     os << " = " << printable_op;
  74   }
  75   return os << ";";
  76 }
  77
  78
  79 bool ParallelMove::IsRedundant() const {
  80   for (int i = 0; i < move_operands_.length(); ++i) {
  81     if (!move_operands_[i].IsRedundant()) return false;
  82   }
  83   return true;
  84 }
  85
  86
  87 MoveOperands* ParallelMove::PrepareInsertAfter(MoveOperands* move) const {
  88   auto move_ops = move_operands();
  89   MoveOperands* replacement = nullptr;
  90   MoveOperands* to_eliminate = nullptr;
  91   for (auto curr = move_ops->begin(); curr != move_ops->end(); ++curr) {
  92     if (curr->IsEliminated()) continue;
  93     if (curr->destination()->Equals(move->source())) {
  94       DCHECK(!replacement);
  95       replacement = curr;
  96       if (to_eliminate != nullptr) break;
  97     } else if (curr->destination()->Equals(move->destination())) {
  98       DCHECK(!to_eliminate);
  99       to_eliminate = curr;
 100       if (replacement != nullptr) break;
 101     }
 102   }
 103   DCHECK_IMPLIES(replacement == to_eliminate, replacement == nullptr);
 104   if (replacement != nullptr) move->set_source(replacement->source());
 105   return to_eliminate;
 106 }
 107
 108
 109 Instruction::Instruction(InstructionCode opcode)
 110     : opcode_(opcode),
 111       bit_field_(OutputCountField::encode(0) | InputCountField::encode(0) |
 112                  TempCountField::encode(0) | IsCallField::encode(false)),
 113       pointer_map_(NULL) {}
 114
 115
 116 Instruction::Instruction(InstructionCode opcode, size_t output_count,
 117                          InstructionOperand* outputs, size_t input_count,
 118                          InstructionOperand* inputs, size_t temp_count,
 119                          InstructionOperand* temps)
 120     : opcode_(opcode),
 121       bit_field_(OutputCountField::encode(output_count) |
 122                  InputCountField::encode(input_count) |
 123                  TempCountField::encode(temp_count) |
 124                  IsCallField::encode(false)),
 125       pointer_map_(NULL) {
 126   size_t offset = 0;
 127   for (size_t i = 0; i < output_count; ++i) {
 128     DCHECK(!outputs[i].IsInvalid());
 129     operands_[offset++] = outputs[i];
 130   }
 131   for (size_t i = 0; i < input_count; ++i) {
 132     DCHECK(!inputs[i].IsInvalid());
 133     operands_[offset++] = inputs[i];
 134   }
 135   for (size_t i = 0; i < temp_count; ++i) {
 136     DCHECK(!temps[i].IsInvalid());
 137     operands_[offset++] = temps[i];
 138   }
 139 }
 140
 141
 142 bool GapInstruction::IsRedundant() const {
 143   for (int i = GapInstruction::FIRST_INNER_POSITION;
 144        i <= GapInstruction::LAST_INNER_POSITION; i++) {
 145     if (parallel_moves_[i] != NULL && !parallel_moves_[i]->IsRedundant())
 146       return false;
 147   }
 148   return true;
 149 }
 150
 151
 152 std::ostream& operator<<(std::ostream& os,
 153                          const PrintableParallelMove& printable) {
 154   const ParallelMove& pm = *printable.parallel_move_;
 155   bool first = true;
 156   for (ZoneList<MoveOperands>::iterator move = pm.move_operands()->begin();
 157        move != pm.move_operands()->end(); ++move) {
 158     if (move->IsEliminated()) continue;
 159     if (!first) os << " ";
 160     first = false;
 161     PrintableMoveOperands pmo = {printable.register_configuration_, move};
 162     os << pmo;
 163   }
 164   return os;
 165 }
 166
 167
 168 void PointerMap::RecordPointer(InstructionOperand* op, Zone* zone) {
 169   // Do not record arguments as pointers.
 170   if (op->IsStackSlot() && op->index() < 0) return;
 171   DCHECK(!op->IsDoubleRegister() && !op->IsDoubleStackSlot());
 172   pointer_operands_.Add(op, zone);
 173 }
 174
 175
 176 void PointerMap::RemovePointer(InstructionOperand* op) {
 177   // Do not record arguments as pointers.
 178   if (op->IsStackSlot() && op->index() < 0) return;
 179   DCHECK(!op->IsDoubleRegister() && !op->IsDoubleStackSlot());
 180   for (int i = 0; i < pointer_operands_.length(); ++i) {
 181     if (pointer_operands_[i]->Equals(op)) {
 182       pointer_operands_.Remove(i);
 183       --i;
 184     }
 185   }
 186 }
 187
 188
 189 void PointerMap::RecordUntagged(InstructionOperand* op, Zone* zone) {
 190   // Do not record arguments as pointers.
 191   if (op->IsStackSlot() && op->index() < 0) return;
 192   DCHECK(!op->IsDoubleRegister() && !op->IsDoubleStackSlot());
 193   untagged_operands_.Add(op, zone);
 194 }
 195
 196
 197 std::ostream& operator<<(std::ostream& os, const PointerMap& pm) {
 198   os << "{";
 199   for (ZoneList<InstructionOperand*>::iterator op =
 200            pm.pointer_operands_.begin();
 201        op != pm.pointer_operands_.end(); ++op) {
 202     if (op != pm.pointer_operands_.begin()) os << ";";
 203     os << *op;
 204   }
 205   return os << "}";
 206 }
 207
 208
 209 std::ostream& operator<<(std::ostream& os, const ArchOpcode& ao) {
 210   switch (ao) {
 211 #define CASE(Name) \
 212   case k##Name:    \
 213     return os << #Name;
 214     ARCH_OPCODE_LIST(CASE)
 215 #undef CASE
 216   }
 217   UNREACHABLE();
 218   return os;
 219 }
 220
 221
 222 std::ostream& operator<<(std::ostream& os, const AddressingMode& am) {
 223   switch (am) {
 224     case kMode_None:
 225       return os;
 226 #define CASE(Name)   \
 227   case kMode_##Name: \
 228     return os << #Name;
 229       TARGET_ADDRESSING_MODE_LIST(CASE)
 230 #undef CASE
 231   }
 232   UNREACHABLE();
 233   return os;
 234 }
 235
 236
 237 std::ostream& operator<<(std::ostream& os, const FlagsMode& fm) {
 238   switch (fm) {
 239     case kFlags_none:
 240       return os;
 241     case kFlags_branch:
 242       return os << "branch";
 243     case kFlags_set:
 244       return os << "set";
 245   }
 246   UNREACHABLE();
 247   return os;
 248 }
 249
 250
 251 std::ostream& operator<<(std::ostream& os, const FlagsCondition& fc) {
 252   switch (fc) {
 253     case kEqual:
 254       return os << "equal";
 255     case kNotEqual:
 256       return os << "not equal";
 257     case kSignedLessThan:
 258       return os << "signed less than";
 259     case kSignedGreaterThanOrEqual:
 260       return os << "signed greater than or equal";
 261     case kSignedLessThanOrEqual:
 262       return os << "signed less than or equal";
 263     case kSignedGreaterThan:
 264       return os << "signed greater than";
 265     case kUnsignedLessThan:
 266       return os << "unsigned less than";
 267     case kUnsignedGreaterThanOrEqual:
 268       return os << "unsigned greater than or equal";
 269     case kUnsignedLessThanOrEqual:
 270       return os << "unsigned less than or equal";
 271     case kUnsignedGreaterThan:
 272       return os << "unsigned greater than";
 273     case kUnorderedEqual:
 274       return os << "unordered equal";
 275     case kUnorderedNotEqual:
 276       return os << "unordered not equal";
 277     case kOverflow:
 278       return os << "overflow";
 279     case kNotOverflow:
 280       return os << "not overflow";
 281   }
 282   UNREACHABLE();
 283   return os;
 284 }
 285
 286
 287 std::ostream& operator<<(std::ostream& os,
 288                          const PrintableInstruction& printable) {
 289   const Instruction& instr = *printable.instr_;
 290   PrintableInstructionOperand printable_op = {printable.register_configuration_,
 291                                               NULL};
 292   if (instr.OutputCount() > 1) os << "(";
 293   for (size_t i = 0; i < instr.OutputCount(); i++) {
 294     if (i > 0) os << ", ";
 295     printable_op.op_ = instr.OutputAt(i);
 296     os << printable_op;
 297   }
 298
 299   if (instr.OutputCount() > 1) os << ") = ";
 300   if (instr.OutputCount() == 1) os << " = ";
 301
 302   if (instr.IsGapMoves()) {
 303     const GapInstruction* gap = GapInstruction::cast(&instr);
 304     os << "gap ";
 305     for (int i = GapInstruction::FIRST_INNER_POSITION;
 306          i <= GapInstruction::LAST_INNER_POSITION; i++) {
 307       os << "(";
 308       if (gap->parallel_moves_[i] != NULL) {
 309         PrintableParallelMove ppm = {printable.register_configuration_,
 310                                      gap->parallel_moves_[i]};
 311         os << ppm;
 312       }
 313       os << ") ";
 314     }
 315   } else if (instr.IsSourcePosition()) {
 316     const SourcePositionInstruction* pos =
 317         SourcePositionInstruction::cast(&instr);
 318     os << "position (" << pos->source_position().raw() << ")";
 319   } else {
 320     os << ArchOpcodeField::decode(instr.opcode());
 321     AddressingMode am = AddressingModeField::decode(instr.opcode());
 322     if (am != kMode_None) {
 323       os << " : " << AddressingModeField::decode(instr.opcode());
 324     }
 325     FlagsMode fm = FlagsModeField::decode(instr.opcode());
 326     if (fm != kFlags_none) {
 327       os << " && " << fm << " if "
 328          << FlagsConditionField::decode(instr.opcode());
 329     }
 330   }
 331   if (instr.InputCount() > 0) {
 332     for (size_t i = 0; i < instr.InputCount(); i++) {
 333       printable_op.op_ = instr.InputAt(i);
 334       os << " " << printable_op;
 335     }
 336   }
 337   return os;
 338 }
 339
 340
 341 Constant::Constant(int32_t v) : type_(kInt32), value_(v) {}
 342
 343
 344 std::ostream& operator<<(std::ostream& os, const Constant& constant) {
 345   switch (constant.type()) {
 346     case Constant::kInt32:
 347       return os << constant.ToInt32();
 348     case Constant::kInt64:
 349       return os << constant.ToInt64() << "l";
 350     case Constant::kFloat32:
 351       return os << constant.ToFloat32() << "f";
 352     case Constant::kFloat64:
 353       return os << constant.ToFloat64();
 354     case Constant::kExternalReference:
 355       return os << static_cast<const void*>(
 356                        constant.ToExternalReference().address());
 357     case Constant::kHeapObject:
 358       return os << Brief(*constant.ToHeapObject());
 359     case Constant::kRpoNumber:
 360       return os << "RPO" << constant.ToRpoNumber().ToInt();
 361   }
 362   UNREACHABLE();
 363   return os;
 364 }
 365
 366
 367 PhiInstruction::PhiInstruction(Zone* zone, int virtual_register,
 368                                size_t input_count)
 369     : virtual_register_(virtual_register),
 370       output_(UnallocatedOperand(UnallocatedOperand::NONE, virtual_register)),
 371       operands_(input_count, zone),
 372       inputs_(input_count, zone) {}
 373
 374
 375 void PhiInstruction::SetInput(size_t offset, int virtual_register) {
 376   DCHECK(inputs_[offset].IsInvalid());
 377   auto input = UnallocatedOperand(UnallocatedOperand::ANY, virtual_register);
 378   inputs_[offset] = input;
 379   operands_[offset] = virtual_register;
 380 }
 381
 382
 383 InstructionBlock::InstructionBlock(Zone* zone, RpoNumber rpo_number,
 384                                    RpoNumber loop_header, RpoNumber loop_end,
 385                                    bool deferred)
 386     : successors_(zone),
 387       predecessors_(zone),
 388       phis_(zone),
 389       ao_number_(rpo_number),
 390       rpo_number_(rpo_number),
 391       loop_header_(loop_header),
 392       loop_end_(loop_end),
 393       code_start_(-1),
 394       code_end_(-1),
 395       deferred_(deferred) {}
 396
 397
 398 size_t InstructionBlock::PredecessorIndexOf(RpoNumber rpo_number) const {
 399   size_t j = 0;
 400   for (InstructionBlock::Predecessors::const_iterator i = predecessors_.begin();
 401        i != predecessors_.end(); ++i, ++j) {
 402     if (*i == rpo_number) break;
 403   }
 404   return j;
 405 }
 406
 407
 408 static RpoNumber GetRpo(const BasicBlock* block) {
 409   if (block == NULL) return RpoNumber::Invalid();
 410   return RpoNumber::FromInt(block->rpo_number());
 411 }
 412
 413
 414 static RpoNumber GetLoopEndRpo(const BasicBlock* block) {
 415   if (!block->IsLoopHeader()) return RpoNumber::Invalid();
 416   return RpoNumber::FromInt(block->loop_end()->rpo_number());
 417 }
 418
 419
 420 static InstructionBlock* InstructionBlockFor(Zone* zone,
 421                                              const BasicBlock* block) {
 422   InstructionBlock* instr_block = new (zone)
 423       InstructionBlock(zone, GetRpo(block), GetRpo(block->loop_header()),
 424                        GetLoopEndRpo(block), block->deferred());
 425   // Map successors and precessors
 426   instr_block->successors().reserve(block->SuccessorCount());
 427   for (BasicBlock* successor : block->successors()) {
 428     instr_block->successors().push_back(GetRpo(successor));
 429   }
 430   instr_block->predecessors().reserve(block->PredecessorCount());
 431   for (BasicBlock* predecessor : block->predecessors()) {
 432     instr_block->predecessors().push_back(GetRpo(predecessor));
 433   }
 434   return instr_block;
 435 }
 436
 437
 438 InstructionBlocks* InstructionSequence::InstructionBlocksFor(
 439     Zone* zone, const Schedule* schedule) {
 440   InstructionBlocks* blocks = zone->NewArray<InstructionBlocks>(1);
 441   new (blocks) InstructionBlocks(
 442       static_cast<int>(schedule->rpo_order()->size()), NULL, zone);
 443   size_t rpo_number = 0;
 444   for (BasicBlockVector::const_iterator it = schedule->rpo_order()->begin();
 445        it != schedule->rpo_order()->end(); ++it, ++rpo_number) {
 446     DCHECK(!(*blocks)[rpo_number]);
 447     DCHECK(GetRpo(*it).ToSize() == rpo_number);
 448     (*blocks)[rpo_number] = InstructionBlockFor(zone, *it);
 449   }
 450   ComputeAssemblyOrder(blocks);
 451   return blocks;
 452 }
 453
 454
 455 void InstructionSequence::ComputeAssemblyOrder(InstructionBlocks* blocks) {
 456   int ao = 0;
 457   for (auto const block : *blocks) {
 458     if (!block->IsDeferred()) {
 459       block->set_ao_number(RpoNumber::FromInt(ao++));
 460     }
 461   }
 462   for (auto const block : *blocks) {
 463     if (block->IsDeferred()) {
 464       block->set_ao_number(RpoNumber::FromInt(ao++));
 465     }
 466   }
 467 }
 468
 469
 470 InstructionSequence::InstructionSequence(Isolate* isolate,
 471                                          Zone* instruction_zone,
 472                                          InstructionBlocks* instruction_blocks)
 473     : isolate_(isolate),
 474       zone_(instruction_zone),
 475       instruction_blocks_(instruction_blocks),
 476       block_starts_(zone()),
 477       constants_(ConstantMap::key_compare(),
 478                  ConstantMap::allocator_type(zone())),
 479       immediates_(zone()),
 480       instructions_(zone()),
 481       next_virtual_register_(0),
 482       pointer_maps_(zone()),
 483       doubles_(std::less<int>(), VirtualRegisterSet::allocator_type(zone())),
 484       references_(std::less<int>(), VirtualRegisterSet::allocator_type(zone())),
 485       deoptimization_entries_(zone()) {
 486   block_starts_.reserve(instruction_blocks_->size());
 487 }
 488
 489
 490 int InstructionSequence::NextVirtualRegister() {
 491   int virtual_register = next_virtual_register_++;
 492   CHECK_NE(virtual_register, InstructionOperand::kInvalidVirtualRegister);
 493   return virtual_register;
 494 }
 495
 496
 497 GapInstruction* InstructionSequence::GetBlockStart(RpoNumber rpo) const {
 498   const InstructionBlock* block = InstructionBlockAt(rpo);
 499   return GapInstruction::cast(InstructionAt(block->code_start()));
 500 }
 501
 502
 503 void InstructionSequence::StartBlock(RpoNumber rpo) {
 504   DCHECK(block_starts_.size() == rpo.ToSize());
 505   InstructionBlock* block = InstructionBlockAt(rpo);
 506   int code_start = static_cast<int>(instructions_.size());
 507   block->set_code_start(code_start);
 508   block_starts_.push_back(code_start);
 509 }
 510
 511
 512 void InstructionSequence::EndBlock(RpoNumber rpo) {
 513   int end = static_cast<int>(instructions_.size());
 514   InstructionBlock* block = InstructionBlockAt(rpo);
 515   if (block->code_start() == end) {  // Empty block.  Insert a nop.
 516     AddInstruction(Instruction::New(zone(), kArchNop));
 517     end = static_cast<int>(instructions_.size());
 518   }
 519   DCHECK(block->code_start() >= 0 && block->code_start() < end);
 520   block->set_code_end(end);
 521 }
 522
 523
 524 int InstructionSequence::AddInstruction(Instruction* instr) {
 525   GapInstruction* gap = GapInstruction::New(zone());
 526   instructions_.push_back(gap);
 527   int index = static_cast<int>(instructions_.size());
 528   instructions_.push_back(instr);
 529   if (instr->NeedsPointerMap()) {
 530     DCHECK(instr->pointer_map() == NULL);
 531     PointerMap* pointer_map = new (zone()) PointerMap(zone());
 532     pointer_map->set_instruction_position(index);
 533     instr->set_pointer_map(pointer_map);
 534     pointer_maps_.push_back(pointer_map);
 535   }
 536   return index;
 537 }
 538
 539
 540 const InstructionBlock* InstructionSequence::GetInstructionBlock(
 541     int instruction_index) const {
 542   DCHECK(instruction_blocks_->size() == block_starts_.size());
 543   auto begin = block_starts_.begin();
 544   auto end = std::lower_bound(begin, block_starts_.end(), instruction_index,
 545                               std::less_equal<int>());
 546   size_t index = std::distance(begin, end) - 1;
 547   auto block = instruction_blocks_->at(index);
 548   DCHECK(block->code_start() <= instruction_index &&
 549          instruction_index < block->code_end());
 550   return block;
 551 }
 552
 553
 554 bool InstructionSequence::IsReference(int virtual_register) const {
 555   return references_.find(virtual_register) != references_.end();
 556 }
 557
 558
 559 bool InstructionSequence::IsDouble(int virtual_register) const {
 560   return doubles_.find(virtual_register) != doubles_.end();
 561 }
 562
 563
 564 void InstructionSequence::MarkAsReference(int virtual_register) {
 565   references_.insert(virtual_register);
 566 }
 567
 568
 569 void InstructionSequence::MarkAsDouble(int virtual_register) {
 570   doubles_.insert(virtual_register);
 571 }
 572
 573
 574 void InstructionSequence::AddGapMove(int index, InstructionOperand* from,
 575                                      InstructionOperand* to) {
 576   GapAt(index)->GetOrCreateParallelMove(GapInstruction::START, zone())->AddMove(
 577       from, to, zone());
 578 }
 579
 580
 581 InstructionSequence::StateId InstructionSequence::AddFrameStateDescriptor(
 582     FrameStateDescriptor* descriptor) {
 583   int deoptimization_id = static_cast<int>(deoptimization_entries_.size());
 584   deoptimization_entries_.push_back(descriptor);
 585   return StateId::FromInt(deoptimization_id);
 586 }
 587
 588 FrameStateDescriptor* InstructionSequence::GetFrameStateDescriptor(
 589     InstructionSequence::StateId state_id) {
 590   return deoptimization_entries_[state_id.ToInt()];
 591 }
 592
 593
 594 int InstructionSequence::GetFrameStateDescriptorCount() {
 595   return static_cast<int>(deoptimization_entries_.size());
 596 }
 597
 598
 599 FrameStateDescriptor::FrameStateDescriptor(
 600     Zone* zone, const FrameStateCallInfo& state_info, size_t parameters_count,
 601     size_t locals_count, size_t stack_count, FrameStateDescriptor* outer_state)
 602     : type_(state_info.type()),
 603       bailout_id_(state_info.bailout_id()),
 604       frame_state_combine_(state_info.state_combine()),
 605       parameters_count_(parameters_count),
 606       locals_count_(locals_count),
 607       stack_count_(stack_count),
 608       types_(zone),
 609       outer_state_(outer_state),
 610       jsfunction_(state_info.jsfunction()) {
 611   types_.resize(GetSize(), kMachNone);
 612 }
 613
 614 size_t FrameStateDescriptor::GetSize(OutputFrameStateCombine combine) const {
 615   size_t size = parameters_count() + locals_count() + stack_count() +
 616                 (HasContext() ? 1 : 0);
 617   switch (combine.kind()) {
 618     case OutputFrameStateCombine::kPushOutput:
 619       size += combine.GetPushCount();
 620       break;
 621     case OutputFrameStateCombine::kPokeAt:
 622       break;
 623   }
 624   return size;
 625 }
 626
 627
 628 size_t FrameStateDescriptor::GetTotalSize() const {
 629   size_t total_size = 0;
 630   for (const FrameStateDescriptor* iter = this; iter != NULL;
 631        iter = iter->outer_state_) {
 632     total_size += iter->GetSize();
 633   }
 634   return total_size;
 635 }
 636
 637
 638 size_t FrameStateDescriptor::GetFrameCount() const {
 639   size_t count = 0;
 640   for (const FrameStateDescriptor* iter = this; iter != NULL;
 641        iter = iter->outer_state_) {
 642     ++count;
 643   }
 644   return count;
 645 }
 646
 647
 648 size_t FrameStateDescriptor::GetJSFrameCount() const {
 649   size_t count = 0;
 650   for (const FrameStateDescriptor* iter = this; iter != NULL;
 651        iter = iter->outer_state_) {
 652     if (iter->type_ == JS_FRAME) {
 653       ++count;
 654     }
 655   }
 656   return count;
 657 }
 658
 659
 660 MachineType FrameStateDescriptor::GetType(size_t index) const {
 661   return types_[index];
 662 }
 663
 664
 665 void FrameStateDescriptor::SetType(size_t index, MachineType type) {
 666   DCHECK(index < GetSize());
 667   types_[index] = type;
 668 }
 669
 670
 671 std::ostream& operator<<(std::ostream& os, const RpoNumber& rpo) {
 672   return os << rpo.ToSize();
 673 }
 674
 675
 676 std::ostream& operator<<(std::ostream& os,
 677                          const PrintableInstructionSequence& printable) {
 678   const InstructionSequence& code = *printable.sequence_;
 679   for (size_t i = 0; i < code.immediates_.size(); ++i) {
 680     Constant constant = code.immediates_[i];
 681     os << "IMM#" << i << ": " << constant << "\n";
 682   }
 683   int i = 0;
 684   for (ConstantMap::const_iterator it = code.constants_.begin();
 685        it != code.constants_.end(); ++i, ++it) {
 686     os << "CST#" << i << ": v" << it->first << " = " << it->second << "\n";
 687   }
 688   for (int i = 0; i < code.InstructionBlockCount(); i++) {
 689     RpoNumber rpo = RpoNumber::FromInt(i);
 690     const InstructionBlock* block = code.InstructionBlockAt(rpo);
 691     CHECK(block->rpo_number() == rpo);
 692
 693     os << "B" << block->rpo_number();
 694     os << ": AO#" << block->ao_number();
 695     if (block->IsDeferred()) os << " (deferred)";
 696     if (block->IsLoopHeader()) {
 697       os << " loop blocks: [" << block->rpo_number() << ", "
 698          << block->loop_end() << ")";
 699     }
 700     os << "  instructions: [" << block->code_start() << ", "
 701        << block->code_end() << ")\n  predecessors:";
 702
 703     for (auto pred : block->predecessors()) {
 704       os << " B" << pred.ToInt();
 705     }
 706     os << "\n";
 707
 708     for (auto phi : block->phis()) {
 709       PrintableInstructionOperand printable_op = {
 710           printable.register_configuration_, &phi->output()};
 711       os << "     phi: " << printable_op << " =";
 712       for (auto input : phi->inputs()) {
 713         printable_op.op_ = &input;
 714         os << " " << printable_op;
 715       }
 716       os << "\n";
 717     }
 718
 719     ScopedVector<char> buf(32);
 720     PrintableInstruction printable_instr;
 721     printable_instr.register_configuration_ = printable.register_configuration_;
 722     for (int j = block->first_instruction_index();
 723          j <= block->last_instruction_index(); j++) {
 724       // TODO(svenpanne) Add some basic formatting to our streams.
 725       SNPrintF(buf, "%5d", j);
 726       printable_instr.instr_ = code.InstructionAt(j);
 727       os << "   " << buf.start() << ": " << printable_instr << "\n";
 728     }
 729
 730     for (auto succ : block->successors()) {
 731       os << " B" << succ.ToInt();
 732     }
 733     os << "\n";
 734   }
 735   return os;
 736 }
 737
 738 }  // namespace compiler
 739 }  // namespace internal
 740 }  // namespace v8