Home | History | Annotate | Download | only in compiler 
      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 #include "src/compiler/state-values-utils.h"
     10 
     11 namespace v8 {
     12 namespace internal {
     13 namespace compiler {
     14 
     15 
     16 FlagsCondition CommuteFlagsCondition(FlagsCondition condition) {
     17   switch (condition) {
     18     case kSignedLessThan:
     19       return kSignedGreaterThan;
     20     case kSignedGreaterThanOrEqual:
     21       return kSignedLessThanOrEqual;
     22     case kSignedLessThanOrEqual:
     23       return kSignedGreaterThanOrEqual;
     24     case kSignedGreaterThan:
     25       return kSignedLessThan;
     26     case kUnsignedLessThan:
     27       return kUnsignedGreaterThan;
     28     case kUnsignedGreaterThanOrEqual:
     29       return kUnsignedLessThanOrEqual;
     30     case kUnsignedLessThanOrEqual:
     31       return kUnsignedGreaterThanOrEqual;
     32     case kUnsignedGreaterThan:
     33       return kUnsignedLessThan;
     34     case kFloatLessThanOrUnordered:
     35       return kFloatGreaterThanOrUnordered;
     36     case kFloatGreaterThanOrEqual:
     37       return kFloatLessThanOrEqual;
     38     case kFloatLessThanOrEqual:
     39       return kFloatGreaterThanOrEqual;
     40     case kFloatGreaterThanOrUnordered:
     41       return kFloatLessThanOrUnordered;
     42     case kFloatLessThan:
     43       return kFloatGreaterThan;
     44     case kFloatGreaterThanOrEqualOrUnordered:
     45       return kFloatLessThanOrEqualOrUnordered;
     46     case kFloatLessThanOrEqualOrUnordered:
     47       return kFloatGreaterThanOrEqualOrUnordered;
     48     case kFloatGreaterThan:
     49       return kFloatLessThan;
     50     case kEqual:
     51     case kNotEqual:
     52     case kOverflow:
     53     case kNotOverflow:
     54     case kUnorderedEqual:
     55     case kUnorderedNotEqual:
     56       return condition;
     57   }
     58   UNREACHABLE();
     59   return condition;
     60 }
     61 
     62 
     63 void InstructionOperand::Print(const RegisterConfiguration* config) const {
     64   OFStream os(stdout);
     65   PrintableInstructionOperand wrapper;
     66   wrapper.register_configuration_ = config;
     67   wrapper.op_ = *this;
     68   os << wrapper << std::endl;
     69 }
     70 
     71 
     72 void InstructionOperand::Print() const {
     73   const RegisterConfiguration* config =
     74       RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN);
     75   Print(config);
     76 }
     77 
     78 
     79 std::ostream& operator<<(std::ostream& os,
     80                          const PrintableInstructionOperand& printable) {
     81   const InstructionOperand& op = printable.op_;
     82   const RegisterConfiguration* conf = printable.register_configuration_;
     83   switch (op.kind()) {
     84     case InstructionOperand::UNALLOCATED: {
     85       const UnallocatedOperand* unalloc = UnallocatedOperand::cast(&op);
     86       os << "v" << unalloc->virtual_register();
     87       if (unalloc->basic_policy() == UnallocatedOperand::FIXED_SLOT) {
     88         return os << "(=" << unalloc->fixed_slot_index() << "S)";
     89       }
     90       switch (unalloc->extended_policy()) {
     91         case UnallocatedOperand::NONE:
     92           return os;
     93         case UnallocatedOperand::FIXED_REGISTER:
     94           return os << "(="
     95                     << conf->GetGeneralRegisterName(
     96                            unalloc->fixed_register_index())
     97                     << ")";
     98         case UnallocatedOperand::FIXED_DOUBLE_REGISTER:
     99           return os << "(="
    100                     << conf->GetDoubleRegisterName(
    101                            unalloc->fixed_register_index())
    102                     << ")";
    103         case UnallocatedOperand::MUST_HAVE_REGISTER:
    104           return os << "(R)";
    105         case UnallocatedOperand::MUST_HAVE_SLOT:
    106           return os << "(S)";
    107         case UnallocatedOperand::SAME_AS_FIRST_INPUT:
    108           return os << "(1)";
    109         case UnallocatedOperand::ANY:
    110           return os << "(-)";
    111       }
    112     }
    113     case InstructionOperand::CONSTANT:
    114       return os << "[constant:" << ConstantOperand::cast(op).virtual_register()
    115                 << "]";
    116     case InstructionOperand::IMMEDIATE: {
    117       auto imm = ImmediateOperand::cast(op);
    118       switch (imm.type()) {
    119         case ImmediateOperand::INLINE:
    120           return os << "#" << imm.inline_value();
    121         case ImmediateOperand::INDEXED:
    122           return os << "[immediate:" << imm.indexed_value() << "]";
    123       }
    124     }
    125     case InstructionOperand::EXPLICIT:
    126     case InstructionOperand::ALLOCATED: {
    127       auto allocated = LocationOperand::cast(op);
    128       if (op.IsStackSlot()) {
    129         os << "[stack:" << LocationOperand::cast(op).index();
    130       } else if (op.IsDoubleStackSlot()) {
    131         os << "[double_stack:" << LocationOperand::cast(op).index();
    132       } else if (op.IsRegister()) {
    133         os << "[" << LocationOperand::cast(op).GetRegister().ToString() << "|R";
    134       } else {
    135         DCHECK(op.IsDoubleRegister());
    136         os << "[" << LocationOperand::cast(op).GetDoubleRegister().ToString()
    137            << "|R";
    138       }
    139       if (allocated.IsExplicit()) {
    140         os << "|E";
    141       }
    142       switch (allocated.representation()) {
    143         case MachineRepresentation::kNone:
    144           os << "|-";
    145           break;
    146         case MachineRepresentation::kBit:
    147           os << "|b";
    148           break;
    149         case MachineRepresentation::kWord8:
    150           os << "|w8";
    151           break;
    152         case MachineRepresentation::kWord16:
    153           os << "|w16";
    154           break;
    155         case MachineRepresentation::kWord32:
    156           os << "|w32";
    157           break;
    158         case MachineRepresentation::kWord64:
    159           os << "|w64";
    160           break;
    161         case MachineRepresentation::kFloat32:
    162           os << "|f32";
    163           break;
    164         case MachineRepresentation::kFloat64:
    165           os << "|f64";
    166           break;
    167         case MachineRepresentation::kTagged:
    168           os << "|t";
    169           break;
    170       }
    171       return os << "]";
    172     }
    173     case InstructionOperand::INVALID:
    174       return os << "(x)";
    175   }
    176   UNREACHABLE();
    177   return os;
    178 }
    179 
    180 
    181 void MoveOperands::Print(const RegisterConfiguration* config) const {
    182   OFStream os(stdout);
    183   PrintableInstructionOperand wrapper;
    184   wrapper.register_configuration_ = config;
    185   wrapper.op_ = destination();
    186   os << wrapper << " = ";
    187   wrapper.op_ = source();
    188   os << wrapper << std::endl;
    189 }
    190 
    191 
    192 void MoveOperands::Print() const {
    193   const RegisterConfiguration* config =
    194       RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN);
    195   Print(config);
    196 }
    197 
    198 
    199 std::ostream& operator<<(std::ostream& os,
    200                          const PrintableMoveOperands& printable) {
    201   const MoveOperands& mo = *printable.move_operands_;
    202   PrintableInstructionOperand printable_op = {printable.register_configuration_,
    203                                               mo.destination()};
    204   os << printable_op;
    205   if (!mo.source().Equals(mo.destination())) {
    206     printable_op.op_ = mo.source();
    207     os << " = " << printable_op;
    208   }
    209   return os << ";";
    210 }
    211 
    212 
    213 bool ParallelMove::IsRedundant() const {
    214   for (auto move : *this) {
    215     if (!move->IsRedundant()) return false;
    216   }
    217   return true;
    218 }
    219 
    220 
    221 MoveOperands* ParallelMove::PrepareInsertAfter(MoveOperands* move) const {
    222   MoveOperands* replacement = nullptr;
    223   MoveOperands* to_eliminate = nullptr;
    224   for (auto curr : *this) {
    225     if (curr->IsEliminated()) continue;
    226     if (curr->destination().EqualsCanonicalized(move->source())) {
    227       DCHECK(!replacement);
    228       replacement = curr;
    229       if (to_eliminate != nullptr) break;
    230     } else if (curr->destination().EqualsCanonicalized(move->destination())) {
    231       DCHECK(!to_eliminate);
    232       to_eliminate = curr;
    233       if (replacement != nullptr) break;
    234     }
    235   }
    236   DCHECK_IMPLIES(replacement == to_eliminate, replacement == nullptr);
    237   if (replacement != nullptr) move->set_source(replacement->source());
    238   return to_eliminate;
    239 }
    240 
    241 
    242 ExplicitOperand::ExplicitOperand(LocationKind kind, MachineRepresentation rep,
    243                                  int index)
    244     : LocationOperand(EXPLICIT, kind, rep, index) {
    245   DCHECK_IMPLIES(kind == REGISTER && !IsFloatingPoint(rep),
    246                  Register::from_code(index).IsAllocatable());
    247   DCHECK_IMPLIES(kind == REGISTER && IsFloatingPoint(rep),
    248                  DoubleRegister::from_code(index).IsAllocatable());
    249 }
    250 
    251 
    252 Instruction::Instruction(InstructionCode opcode)
    253     : opcode_(opcode),
    254       bit_field_(OutputCountField::encode(0) | InputCountField::encode(0) |
    255                  TempCountField::encode(0) | IsCallField::encode(false)),
    256       reference_map_(nullptr) {
    257   parallel_moves_[0] = nullptr;
    258   parallel_moves_[1] = nullptr;
    259 }
    260 
    261 
    262 Instruction::Instruction(InstructionCode opcode, size_t output_count,
    263                          InstructionOperand* outputs, size_t input_count,
    264                          InstructionOperand* inputs, size_t temp_count,
    265                          InstructionOperand* temps)
    266     : opcode_(opcode),
    267       bit_field_(OutputCountField::encode(output_count) |
    268                  InputCountField::encode(input_count) |
    269                  TempCountField::encode(temp_count) |
    270                  IsCallField::encode(false)),
    271       reference_map_(nullptr) {
    272   parallel_moves_[0] = nullptr;
    273   parallel_moves_[1] = nullptr;
    274   size_t offset = 0;
    275   for (size_t i = 0; i < output_count; ++i) {
    276     DCHECK(!outputs[i].IsInvalid());
    277     operands_[offset++] = outputs[i];
    278   }
    279   for (size_t i = 0; i < input_count; ++i) {
    280     DCHECK(!inputs[i].IsInvalid());
    281     operands_[offset++] = inputs[i];
    282   }
    283   for (size_t i = 0; i < temp_count; ++i) {
    284     DCHECK(!temps[i].IsInvalid());
    285     operands_[offset++] = temps[i];
    286   }
    287 }
    288 
    289 
    290 bool Instruction::AreMovesRedundant() const {
    291   for (int i = Instruction::FIRST_GAP_POSITION;
    292        i <= Instruction::LAST_GAP_POSITION; i++) {
    293     if (parallel_moves_[i] != nullptr && !parallel_moves_[i]->IsRedundant()) {
    294       return false;
    295     }
    296   }
    297   return true;
    298 }
    299 
    300 
    301 void Instruction::Print(const RegisterConfiguration* config) const {
    302   OFStream os(stdout);
    303   PrintableInstruction wrapper;
    304   wrapper.instr_ = this;
    305   wrapper.register_configuration_ = config;
    306   os << wrapper << std::endl;
    307 }
    308 
    309 
    310 void Instruction::Print() const {
    311   const RegisterConfiguration* config =
    312       RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN);
    313   Print(config);
    314 }
    315 
    316 
    317 std::ostream& operator<<(std::ostream& os,
    318                          const PrintableParallelMove& printable) {
    319   const ParallelMove& pm = *printable.parallel_move_;
    320   bool first = true;
    321   for (auto move : pm) {
    322     if (move->IsEliminated()) continue;
    323     if (!first) os << " ";
    324     first = false;
    325     PrintableMoveOperands pmo = {printable.register_configuration_, move};
    326     os << pmo;
    327   }
    328   return os;
    329 }
    330 
    331 
    332 void ReferenceMap::RecordReference(const AllocatedOperand& op) {
    333   // Do not record arguments as pointers.
    334   if (op.IsStackSlot() && LocationOperand::cast(op).index() < 0) return;
    335   DCHECK(!op.IsDoubleRegister() && !op.IsDoubleStackSlot());
    336   reference_operands_.push_back(op);
    337 }
    338 
    339 
    340 std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm) {
    341   os << "{";
    342   bool first = true;
    343   PrintableInstructionOperand poi = {
    344       RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN),
    345       InstructionOperand()};
    346   for (auto& op : pm.reference_operands_) {
    347     if (!first) {
    348       os << ";";
    349     } else {
    350       first = false;
    351     }
    352     poi.op_ = op;
    353     os << poi;
    354   }
    355   return os << "}";
    356 }
    357 
    358 
    359 std::ostream& operator<<(std::ostream& os, const ArchOpcode& ao) {
    360   switch (ao) {
    361 #define CASE(Name) \
    362   case k##Name:    \
    363     return os << #Name;
    364     ARCH_OPCODE_LIST(CASE)
    365 #undef CASE
    366   }
    367   UNREACHABLE();
    368   return os;
    369 }
    370 
    371 
    372 std::ostream& operator<<(std::ostream& os, const AddressingMode& am) {
    373   switch (am) {
    374     case kMode_None:
    375       return os;
    376 #define CASE(Name)   \
    377   case kMode_##Name: \
    378     return os << #Name;
    379       TARGET_ADDRESSING_MODE_LIST(CASE)
    380 #undef CASE
    381   }
    382   UNREACHABLE();
    383   return os;
    384 }
    385 
    386 
    387 std::ostream& operator<<(std::ostream& os, const FlagsMode& fm) {
    388   switch (fm) {
    389     case kFlags_none:
    390       return os;
    391     case kFlags_branch:
    392       return os << "branch";
    393     case kFlags_set:
    394       return os << "set";
    395   }
    396   UNREACHABLE();
    397   return os;
    398 }
    399 
    400 
    401 std::ostream& operator<<(std::ostream& os, const FlagsCondition& fc) {
    402   switch (fc) {
    403     case kEqual:
    404       return os << "equal";
    405     case kNotEqual:
    406       return os << "not equal";
    407     case kSignedLessThan:
    408       return os << "signed less than";
    409     case kSignedGreaterThanOrEqual:
    410       return os << "signed greater than or equal";
    411     case kSignedLessThanOrEqual:
    412       return os << "signed less than or equal";
    413     case kSignedGreaterThan:
    414       return os << "signed greater than";
    415     case kUnsignedLessThan:
    416       return os << "unsigned less than";
    417     case kUnsignedGreaterThanOrEqual:
    418       return os << "unsigned greater than or equal";
    419     case kUnsignedLessThanOrEqual:
    420       return os << "unsigned less than or equal";
    421     case kUnsignedGreaterThan:
    422       return os << "unsigned greater than";
    423     case kFloatLessThanOrUnordered:
    424       return os << "less than or unordered (FP)";
    425     case kFloatGreaterThanOrEqual:
    426       return os << "greater than or equal (FP)";
    427     case kFloatLessThanOrEqual:
    428       return os << "less than or equal (FP)";
    429     case kFloatGreaterThanOrUnordered:
    430       return os << "greater than or unordered (FP)";
    431     case kFloatLessThan:
    432       return os << "less than (FP)";
    433     case kFloatGreaterThanOrEqualOrUnordered:
    434       return os << "greater than, equal or unordered (FP)";
    435     case kFloatLessThanOrEqualOrUnordered:
    436       return os << "less than, equal or unordered (FP)";
    437     case kFloatGreaterThan:
    438       return os << "greater than (FP)";
    439     case kUnorderedEqual:
    440       return os << "unordered equal";
    441     case kUnorderedNotEqual:
    442       return os << "unordered not equal";
    443     case kOverflow:
    444       return os << "overflow";
    445     case kNotOverflow:
    446       return os << "not overflow";
    447   }
    448   UNREACHABLE();
    449   return os;
    450 }
    451 
    452 
    453 std::ostream& operator<<(std::ostream& os,
    454                          const PrintableInstruction& printable) {
    455   const Instruction& instr = *printable.instr_;
    456   PrintableInstructionOperand printable_op = {printable.register_configuration_,
    457                                               InstructionOperand()};
    458   os << "gap ";
    459   for (int i = Instruction::FIRST_GAP_POSITION;
    460        i <= Instruction::LAST_GAP_POSITION; i++) {
    461     os << "(";
    462     if (instr.parallel_moves()[i] != nullptr) {
    463       PrintableParallelMove ppm = {printable.register_configuration_,
    464                                    instr.parallel_moves()[i]};
    465       os << ppm;
    466     }
    467     os << ") ";
    468   }
    469   os << "\n          ";
    470 
    471   if (instr.OutputCount() > 1) os << "(";
    472   for (size_t i = 0; i < instr.OutputCount(); i++) {
    473     if (i > 0) os << ", ";
    474     printable_op.op_ = *instr.OutputAt(i);
    475     os << printable_op;
    476   }
    477 
    478   if (instr.OutputCount() > 1) os << ") = ";
    479   if (instr.OutputCount() == 1) os << " = ";
    480 
    481   os << ArchOpcodeField::decode(instr.opcode());
    482   AddressingMode am = AddressingModeField::decode(instr.opcode());
    483   if (am != kMode_None) {
    484     os << " : " << AddressingModeField::decode(instr.opcode());
    485   }
    486   FlagsMode fm = FlagsModeField::decode(instr.opcode());
    487   if (fm != kFlags_none) {
    488     os << " && " << fm << " if " << FlagsConditionField::decode(instr.opcode());
    489   }
    490   if (instr.InputCount() > 0) {
    491     for (size_t i = 0; i < instr.InputCount(); i++) {
    492       printable_op.op_ = *instr.InputAt(i);
    493       os << " " << printable_op;
    494     }
    495   }
    496   return os;
    497 }
    498 
    499 
    500 Constant::Constant(int32_t v) : type_(kInt32), value_(v) {}
    501 
    502 
    503 std::ostream& operator<<(std::ostream& os, const Constant& constant) {
    504   switch (constant.type()) {
    505     case Constant::kInt32:
    506       return os << constant.ToInt32();
    507     case Constant::kInt64:
    508       return os << constant.ToInt64() << "l";
    509     case Constant::kFloat32:
    510       return os << constant.ToFloat32() << "f";
    511     case Constant::kFloat64:
    512       return os << constant.ToFloat64();
    513     case Constant::kExternalReference:
    514       return os << static_cast<const void*>(
    515                        constant.ToExternalReference().address());
    516     case Constant::kHeapObject:
    517       return os << Brief(*constant.ToHeapObject());
    518     case Constant::kRpoNumber:
    519       return os << "RPO" << constant.ToRpoNumber().ToInt();
    520   }
    521   UNREACHABLE();
    522   return os;
    523 }
    524 
    525 
    526 PhiInstruction::PhiInstruction(Zone* zone, int virtual_register,
    527                                size_t input_count)
    528     : virtual_register_(virtual_register),
    529       output_(UnallocatedOperand(UnallocatedOperand::NONE, virtual_register)),
    530       operands_(input_count, InstructionOperand::kInvalidVirtualRegister,
    531                 zone) {}
    532 
    533 
    534 void PhiInstruction::SetInput(size_t offset, int virtual_register) {
    535   DCHECK_EQ(InstructionOperand::kInvalidVirtualRegister, operands_[offset]);
    536   operands_[offset] = virtual_register;
    537 }
    538 
    539 
    540 InstructionBlock::InstructionBlock(Zone* zone, RpoNumber rpo_number,
    541                                    RpoNumber loop_header, RpoNumber loop_end,
    542                                    bool deferred, bool handler)
    543     : successors_(zone),
    544       predecessors_(zone),
    545       phis_(zone),
    546       ao_number_(rpo_number),
    547       rpo_number_(rpo_number),
    548       loop_header_(loop_header),
    549       loop_end_(loop_end),
    550       code_start_(-1),
    551       code_end_(-1),
    552       deferred_(deferred),
    553       handler_(handler),
    554       needs_frame_(false),
    555       must_construct_frame_(false),
    556       must_deconstruct_frame_(false),
    557       last_deferred_(RpoNumber::Invalid()) {}
    558 
    559 
    560 size_t InstructionBlock::PredecessorIndexOf(RpoNumber rpo_number) const {
    561   size_t j = 0;
    562   for (InstructionBlock::Predecessors::const_iterator i = predecessors_.begin();
    563        i != predecessors_.end(); ++i, ++j) {
    564     if (*i == rpo_number) break;
    565   }
    566   return j;
    567 }
    568 
    569 
    570 static RpoNumber GetRpo(const BasicBlock* block) {
    571   if (block == nullptr) return RpoNumber::Invalid();
    572   return RpoNumber::FromInt(block->rpo_number());
    573 }
    574 
    575 
    576 static RpoNumber GetLoopEndRpo(const BasicBlock* block) {
    577   if (!block->IsLoopHeader()) return RpoNumber::Invalid();
    578   return RpoNumber::FromInt(block->loop_end()->rpo_number());
    579 }
    580 
    581 
    582 static InstructionBlock* InstructionBlockFor(Zone* zone,
    583                                              const BasicBlock* block) {
    584   bool is_handler =
    585       !block->empty() && block->front()->opcode() == IrOpcode::kIfException;
    586   InstructionBlock* instr_block = new (zone)
    587       InstructionBlock(zone, GetRpo(block), GetRpo(block->loop_header()),
    588                        GetLoopEndRpo(block), block->deferred(), is_handler);
    589   // Map successors and precessors
    590   instr_block->successors().reserve(block->SuccessorCount());
    591   for (BasicBlock* successor : block->successors()) {
    592     instr_block->successors().push_back(GetRpo(successor));
    593   }
    594   instr_block->predecessors().reserve(block->PredecessorCount());
    595   for (BasicBlock* predecessor : block->predecessors()) {
    596     instr_block->predecessors().push_back(GetRpo(predecessor));
    597   }
    598   return instr_block;
    599 }
    600 
    601 
    602 InstructionBlocks* InstructionSequence::InstructionBlocksFor(
    603     Zone* zone, const Schedule* schedule) {
    604   InstructionBlocks* blocks = zone->NewArray<InstructionBlocks>(1);
    605   new (blocks) InstructionBlocks(
    606       static_cast<int>(schedule->rpo_order()->size()), nullptr, zone);
    607   size_t rpo_number = 0;
    608   for (BasicBlockVector::const_iterator it = schedule->rpo_order()->begin();
    609        it != schedule->rpo_order()->end(); ++it, ++rpo_number) {
    610     DCHECK(!(*blocks)[rpo_number]);
    611     DCHECK(GetRpo(*it).ToSize() == rpo_number);
    612     (*blocks)[rpo_number] = InstructionBlockFor(zone, *it);
    613   }
    614   ComputeAssemblyOrder(blocks);
    615   return blocks;
    616 }
    617 
    618 
    619 void InstructionSequence::ComputeAssemblyOrder(InstructionBlocks* blocks) {
    620   int ao = 0;
    621   for (auto const block : *blocks) {
    622     if (!block->IsDeferred()) {
    623       block->set_ao_number(RpoNumber::FromInt(ao++));
    624     }
    625   }
    626   for (auto const block : *blocks) {
    627     if (block->IsDeferred()) {
    628       block->set_ao_number(RpoNumber::FromInt(ao++));
    629     }
    630   }
    631 }
    632 
    633 
    634 InstructionSequence::InstructionSequence(Isolate* isolate,
    635                                          Zone* instruction_zone,
    636                                          InstructionBlocks* instruction_blocks)
    637     : isolate_(isolate),
    638       zone_(instruction_zone),
    639       instruction_blocks_(instruction_blocks),
    640       source_positions_(zone()),
    641       block_starts_(zone()),
    642       constants_(ConstantMap::key_compare(),
    643                  ConstantMap::allocator_type(zone())),
    644       immediates_(zone()),
    645       instructions_(zone()),
    646       next_virtual_register_(0),
    647       reference_maps_(zone()),
    648       representations_(zone()),
    649       deoptimization_entries_(zone()) {
    650   block_starts_.reserve(instruction_blocks_->size());
    651 }
    652 
    653 
    654 int InstructionSequence::NextVirtualRegister() {
    655   int virtual_register = next_virtual_register_++;
    656   CHECK_NE(virtual_register, InstructionOperand::kInvalidVirtualRegister);
    657   return virtual_register;
    658 }
    659 
    660 
    661 Instruction* InstructionSequence::GetBlockStart(RpoNumber rpo) const {
    662   const InstructionBlock* block = InstructionBlockAt(rpo);
    663   return InstructionAt(block->code_start());
    664 }
    665 
    666 
    667 void InstructionSequence::StartBlock(RpoNumber rpo) {
    668   DCHECK(block_starts_.size() == rpo.ToSize());
    669   InstructionBlock* block = InstructionBlockAt(rpo);
    670   int code_start = static_cast<int>(instructions_.size());
    671   block->set_code_start(code_start);
    672   block_starts_.push_back(code_start);
    673 }
    674 
    675 
    676 void InstructionSequence::EndBlock(RpoNumber rpo) {
    677   int end = static_cast<int>(instructions_.size());
    678   InstructionBlock* block = InstructionBlockAt(rpo);
    679   if (block->code_start() == end) {  // Empty block.  Insert a nop.
    680     AddInstruction(Instruction::New(zone(), kArchNop));
    681     end = static_cast<int>(instructions_.size());
    682   }
    683   DCHECK(block->code_start() >= 0 && block->code_start() < end);
    684   block->set_code_end(end);
    685 }
    686 
    687 
    688 int InstructionSequence::AddInstruction(Instruction* instr) {
    689   int index = static_cast<int>(instructions_.size());
    690   instructions_.push_back(instr);
    691   if (instr->NeedsReferenceMap()) {
    692     DCHECK(instr->reference_map() == nullptr);
    693     ReferenceMap* reference_map = new (zone()) ReferenceMap(zone());
    694     reference_map->set_instruction_position(index);
    695     instr->set_reference_map(reference_map);
    696     reference_maps_.push_back(reference_map);
    697   }
    698   return index;
    699 }
    700 
    701 
    702 InstructionBlock* InstructionSequence::GetInstructionBlock(
    703     int instruction_index) const {
    704   DCHECK(instruction_blocks_->size() == block_starts_.size());
    705   auto begin = block_starts_.begin();
    706   auto end = std::lower_bound(begin, block_starts_.end(), instruction_index);
    707   // Post condition of std::lower_bound:
    708   DCHECK(end == block_starts_.end() || *end >= instruction_index);
    709   if (end == block_starts_.end() || *end > instruction_index) --end;
    710   DCHECK(*end <= instruction_index);
    711   size_t index = std::distance(begin, end);
    712   auto block = instruction_blocks_->at(index);
    713   DCHECK(block->code_start() <= instruction_index &&
    714          instruction_index < block->code_end());
    715   return block;
    716 }
    717 
    718 
    719 static MachineRepresentation FilterRepresentation(MachineRepresentation rep) {
    720   switch (rep) {
    721     case MachineRepresentation::kBit:
    722     case MachineRepresentation::kWord8:
    723     case MachineRepresentation::kWord16:
    724       return InstructionSequence::DefaultRepresentation();
    725     case MachineRepresentation::kWord32:
    726     case MachineRepresentation::kWord64:
    727     case MachineRepresentation::kFloat32:
    728     case MachineRepresentation::kFloat64:
    729     case MachineRepresentation::kTagged:
    730       return rep;
    731     case MachineRepresentation::kNone:
    732       break;
    733   }
    734   UNREACHABLE();
    735   return MachineRepresentation::kNone;
    736 }
    737 
    738 
    739 MachineRepresentation InstructionSequence::GetRepresentation(
    740     int virtual_register) const {
    741   DCHECK_LE(0, virtual_register);
    742   DCHECK_LT(virtual_register, VirtualRegisterCount());
    743   if (virtual_register >= static_cast<int>(representations_.size())) {
    744     return DefaultRepresentation();
    745   }
    746   return representations_[virtual_register];
    747 }
    748 
    749 
    750 void InstructionSequence::MarkAsRepresentation(MachineRepresentation rep,
    751                                                int virtual_register) {
    752   DCHECK_LE(0, virtual_register);
    753   DCHECK_LT(virtual_register, VirtualRegisterCount());
    754   if (virtual_register >= static_cast<int>(representations_.size())) {
    755     representations_.resize(VirtualRegisterCount(), DefaultRepresentation());
    756   }
    757   rep = FilterRepresentation(rep);
    758   DCHECK_IMPLIES(representations_[virtual_register] != rep,
    759                  representations_[virtual_register] == DefaultRepresentation());
    760   representations_[virtual_register] = rep;
    761 }
    762 
    763 
    764 InstructionSequence::StateId InstructionSequence::AddFrameStateDescriptor(
    765     FrameStateDescriptor* descriptor) {
    766   int deoptimization_id = static_cast<int>(deoptimization_entries_.size());
    767   deoptimization_entries_.push_back(descriptor);
    768   return StateId::FromInt(deoptimization_id);
    769 }
    770 
    771 FrameStateDescriptor* InstructionSequence::GetFrameStateDescriptor(
    772     InstructionSequence::StateId state_id) {
    773   return deoptimization_entries_[state_id.ToInt()];
    774 }
    775 
    776 
    777 int InstructionSequence::GetFrameStateDescriptorCount() {
    778   return static_cast<int>(deoptimization_entries_.size());
    779 }
    780 
    781 
    782 RpoNumber InstructionSequence::InputRpo(Instruction* instr, size_t index) {
    783   InstructionOperand* operand = instr->InputAt(index);
    784   Constant constant =
    785       operand->IsImmediate()
    786           ? GetImmediate(ImmediateOperand::cast(operand))
    787           : GetConstant(ConstantOperand::cast(operand)->virtual_register());
    788   return constant.ToRpoNumber();
    789 }
    790 
    791 
    792 bool InstructionSequence::GetSourcePosition(const Instruction* instr,
    793                                             SourcePosition* result) const {
    794   auto it = source_positions_.find(instr);
    795   if (it == source_positions_.end()) return false;
    796   *result = it->second;
    797   return true;
    798 }
    799 
    800 
    801 void InstructionSequence::SetSourcePosition(const Instruction* instr,
    802                                             SourcePosition value) {
    803   source_positions_.insert(std::make_pair(instr, value));
    804 }
    805 
    806 
    807 void InstructionSequence::Print(const RegisterConfiguration* config) const {
    808   OFStream os(stdout);
    809   PrintableInstructionSequence wrapper;
    810   wrapper.register_configuration_ = config;
    811   wrapper.sequence_ = this;
    812   os << wrapper << std::endl;
    813 }
    814 
    815 
    816 void InstructionSequence::Print() const {
    817   const RegisterConfiguration* config =
    818       RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN);
    819   Print(config);
    820 }
    821 
    822 
    823 FrameStateDescriptor::FrameStateDescriptor(
    824     Zone* zone, FrameStateType type, BailoutId bailout_id,
    825     OutputFrameStateCombine state_combine, size_t parameters_count,
    826     size_t locals_count, size_t stack_count,
    827     MaybeHandle<SharedFunctionInfo> shared_info,
    828     FrameStateDescriptor* outer_state)
    829     : type_(type),
    830       bailout_id_(bailout_id),
    831       frame_state_combine_(state_combine),
    832       parameters_count_(parameters_count),
    833       locals_count_(locals_count),
    834       stack_count_(stack_count),
    835       values_(zone),
    836       shared_info_(shared_info),
    837       outer_state_(outer_state) {}
    838 
    839 
    840 size_t FrameStateDescriptor::GetSize(OutputFrameStateCombine combine) const {
    841   size_t size = 1 + parameters_count() + locals_count() + stack_count() +
    842                 (HasContext() ? 1 : 0);
    843   switch (combine.kind()) {
    844     case OutputFrameStateCombine::kPushOutput:
    845       size += combine.GetPushCount();
    846       break;
    847     case OutputFrameStateCombine::kPokeAt:
    848       break;
    849   }
    850   return size;
    851 }
    852 
    853 
    854 size_t FrameStateDescriptor::GetTotalSize() const {
    855   size_t total_size = 0;
    856   for (const FrameStateDescriptor* iter = this; iter != nullptr;
    857        iter = iter->outer_state_) {
    858     total_size += iter->GetSize();
    859   }
    860   return total_size;
    861 }
    862 
    863 
    864 size_t FrameStateDescriptor::GetFrameCount() const {
    865   size_t count = 0;
    866   for (const FrameStateDescriptor* iter = this; iter != nullptr;
    867        iter = iter->outer_state_) {
    868     ++count;
    869   }
    870   return count;
    871 }
    872 
    873 
    874 size_t FrameStateDescriptor::GetJSFrameCount() const {
    875   size_t count = 0;
    876   for (const FrameStateDescriptor* iter = this; iter != nullptr;
    877        iter = iter->outer_state_) {
    878     if (FrameStateFunctionInfo::IsJSFunctionType(iter->type_)) {
    879       ++count;
    880     }
    881   }
    882   return count;
    883 }
    884 
    885 
    886 std::ostream& operator<<(std::ostream& os, const RpoNumber& rpo) {
    887   return os << rpo.ToSize();
    888 }
    889 
    890 
    891 std::ostream& operator<<(std::ostream& os,
    892                          const PrintableInstructionSequence& printable) {
    893   const InstructionSequence& code = *printable.sequence_;
    894   for (size_t i = 0; i < code.immediates_.size(); ++i) {
    895     Constant constant = code.immediates_[i];
    896     os << "IMM#" << i << ": " << constant << "\n";
    897   }
    898   int i = 0;
    899   for (ConstantMap::const_iterator it = code.constants_.begin();
    900        it != code.constants_.end(); ++i, ++it) {
    901     os << "CST#" << i << ": v" << it->first << " = " << it->second << "\n";
    902   }
    903   for (int i = 0; i < code.InstructionBlockCount(); i++) {
    904     RpoNumber rpo = RpoNumber::FromInt(i);
    905     const InstructionBlock* block = code.InstructionBlockAt(rpo);
    906     CHECK(block->rpo_number() == rpo);
    907 
    908     os << "B" << block->rpo_number();
    909     os << ": AO#" << block->ao_number();
    910     if (block->IsDeferred()) os << " (deferred)";
    911     if (!block->needs_frame()) os << " (no frame)";
    912     if (block->must_construct_frame()) os << " (construct frame)";
    913     if (block->must_deconstruct_frame()) os << " (deconstruct frame)";
    914     if (block->IsLoopHeader()) {
    915       os << " loop blocks: [" << block->rpo_number() << ", "
    916          << block->loop_end() << ")";
    917     }
    918     os << "  instructions: [" << block->code_start() << ", "
    919        << block->code_end() << ")\n  predecessors:";
    920 
    921     for (auto pred : block->predecessors()) {
    922       os << " B" << pred.ToInt();
    923     }
    924     os << "\n";
    925 
    926     for (auto phi : block->phis()) {
    927       PrintableInstructionOperand printable_op = {
    928           printable.register_configuration_, phi->output()};
    929       os << "     phi: " << printable_op << " =";
    930       for (auto input : phi->operands()) {
    931         os << " v" << input;
    932       }
    933       os << "\n";
    934     }
    935 
    936     ScopedVector<char> buf(32);
    937     PrintableInstruction printable_instr;
    938     printable_instr.register_configuration_ = printable.register_configuration_;
    939     for (int j = block->first_instruction_index();
    940          j <= block->last_instruction_index(); j++) {
    941       // TODO(svenpanne) Add some basic formatting to our streams.
    942       SNPrintF(buf, "%5d", j);
    943       printable_instr.instr_ = code.InstructionAt(j);
    944       os << "   " << buf.start() << ": " << printable_instr << "\n";
    945     }
    946 
    947     for (auto succ : block->successors()) {
    948       os << " B" << succ.ToInt();
    949     }
    950     os << "\n";
    951   }
    952   return os;
    953 }
    954 
    955 }  // namespace compiler
    956 }  // namespace internal
    957 }  // namespace v8
    958