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