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