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