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 
      9 namespace v8 {
     10 namespace internal {
     11 namespace compiler {
     12 
     13 OStream& operator<<(OStream& os, const InstructionOperand& op) {
     14   switch (op.kind()) {
     15     case InstructionOperand::INVALID:
     16       return os << "(0)";
     17     case InstructionOperand::UNALLOCATED: {
     18       const UnallocatedOperand* unalloc = UnallocatedOperand::cast(&op);
     19       os << "v" << unalloc->virtual_register();
     20       if (unalloc->basic_policy() == UnallocatedOperand::FIXED_SLOT) {
     21         return os << "(=" << unalloc->fixed_slot_index() << "S)";
     22       }
     23       switch (unalloc->extended_policy()) {
     24         case UnallocatedOperand::NONE:
     25           return os;
     26         case UnallocatedOperand::FIXED_REGISTER:
     27           return os << "(=" << Register::AllocationIndexToString(
     28                                    unalloc->fixed_register_index()) << ")";
     29         case UnallocatedOperand::FIXED_DOUBLE_REGISTER:
     30           return os << "(=" << DoubleRegister::AllocationIndexToString(
     31                                    unalloc->fixed_register_index()) << ")";
     32         case UnallocatedOperand::MUST_HAVE_REGISTER:
     33           return os << "(R)";
     34         case UnallocatedOperand::SAME_AS_FIRST_INPUT:
     35           return os << "(1)";
     36         case UnallocatedOperand::ANY:
     37           return os << "(-)";
     38       }
     39     }
     40     case InstructionOperand::CONSTANT:
     41       return os << "[constant:" << op.index() << "]";
     42     case InstructionOperand::IMMEDIATE:
     43       return os << "[immediate:" << op.index() << "]";
     44     case InstructionOperand::STACK_SLOT:
     45       return os << "[stack:" << op.index() << "]";
     46     case InstructionOperand::DOUBLE_STACK_SLOT:
     47       return os << "[double_stack:" << op.index() << "]";
     48     case InstructionOperand::REGISTER:
     49       return os << "[" << Register::AllocationIndexToString(op.index())
     50                 << "|R]";
     51     case InstructionOperand::DOUBLE_REGISTER:
     52       return os << "[" << DoubleRegister::AllocationIndexToString(op.index())
     53                 << "|R]";
     54   }
     55   UNREACHABLE();
     56   return os;
     57 }
     58 
     59 
     60 template <InstructionOperand::Kind kOperandKind, int kNumCachedOperands>
     61 SubKindOperand<kOperandKind, kNumCachedOperands>*
     62     SubKindOperand<kOperandKind, kNumCachedOperands>::cache = NULL;
     63 
     64 
     65 template <InstructionOperand::Kind kOperandKind, int kNumCachedOperands>
     66 void SubKindOperand<kOperandKind, kNumCachedOperands>::SetUpCache() {
     67   if (cache) return;
     68   cache = new SubKindOperand[kNumCachedOperands];
     69   for (int i = 0; i < kNumCachedOperands; i++) {
     70     cache[i].ConvertTo(kOperandKind, i);
     71   }
     72 }
     73 
     74 
     75 template <InstructionOperand::Kind kOperandKind, int kNumCachedOperands>
     76 void SubKindOperand<kOperandKind, kNumCachedOperands>::TearDownCache() {
     77   delete[] cache;
     78   cache = NULL;
     79 }
     80 
     81 
     82 void InstructionOperand::SetUpCaches() {
     83 #define INSTRUCTION_OPERAND_SETUP(name, type, number) \
     84   name##Operand::SetUpCache();
     85   INSTRUCTION_OPERAND_LIST(INSTRUCTION_OPERAND_SETUP)
     86 #undef INSTRUCTION_OPERAND_SETUP
     87 }
     88 
     89 
     90 void InstructionOperand::TearDownCaches() {
     91 #define INSTRUCTION_OPERAND_TEARDOWN(name, type, number) \
     92   name##Operand::TearDownCache();
     93   INSTRUCTION_OPERAND_LIST(INSTRUCTION_OPERAND_TEARDOWN)
     94 #undef INSTRUCTION_OPERAND_TEARDOWN
     95 }
     96 
     97 
     98 OStream& operator<<(OStream& os, const MoveOperands& mo) {
     99   os << *mo.destination();
    100   if (!mo.source()->Equals(mo.destination())) os << " = " << *mo.source();
    101   return os << ";";
    102 }
    103 
    104 
    105 bool ParallelMove::IsRedundant() const {
    106   for (int i = 0; i < move_operands_.length(); ++i) {
    107     if (!move_operands_[i].IsRedundant()) return false;
    108   }
    109   return true;
    110 }
    111 
    112 
    113 OStream& operator<<(OStream& os, const ParallelMove& pm) {
    114   bool first = true;
    115   for (ZoneList<MoveOperands>::iterator move = pm.move_operands()->begin();
    116        move != pm.move_operands()->end(); ++move) {
    117     if (move->IsEliminated()) continue;
    118     if (!first) os << " ";
    119     first = false;
    120     os << *move;
    121   }
    122   return os;
    123 }
    124 
    125 
    126 void PointerMap::RecordPointer(InstructionOperand* op, Zone* zone) {
    127   // Do not record arguments as pointers.
    128   if (op->IsStackSlot() && op->index() < 0) return;
    129   DCHECK(!op->IsDoubleRegister() && !op->IsDoubleStackSlot());
    130   pointer_operands_.Add(op, zone);
    131 }
    132 
    133 
    134 void PointerMap::RemovePointer(InstructionOperand* op) {
    135   // Do not record arguments as pointers.
    136   if (op->IsStackSlot() && op->index() < 0) return;
    137   DCHECK(!op->IsDoubleRegister() && !op->IsDoubleStackSlot());
    138   for (int i = 0; i < pointer_operands_.length(); ++i) {
    139     if (pointer_operands_[i]->Equals(op)) {
    140       pointer_operands_.Remove(i);
    141       --i;
    142     }
    143   }
    144 }
    145 
    146 
    147 void PointerMap::RecordUntagged(InstructionOperand* op, Zone* zone) {
    148   // Do not record arguments as pointers.
    149   if (op->IsStackSlot() && op->index() < 0) return;
    150   DCHECK(!op->IsDoubleRegister() && !op->IsDoubleStackSlot());
    151   untagged_operands_.Add(op, zone);
    152 }
    153 
    154 
    155 OStream& operator<<(OStream& os, const PointerMap& pm) {
    156   os << "{";
    157   for (ZoneList<InstructionOperand*>::iterator op =
    158            pm.pointer_operands_.begin();
    159        op != pm.pointer_operands_.end(); ++op) {
    160     if (op != pm.pointer_operands_.begin()) os << ";";
    161     os << *op;
    162   }
    163   return os << "}";
    164 }
    165 
    166 
    167 OStream& operator<<(OStream& os, const ArchOpcode& ao) {
    168   switch (ao) {
    169 #define CASE(Name) \
    170   case k##Name:    \
    171     return os << #Name;
    172     ARCH_OPCODE_LIST(CASE)
    173 #undef CASE
    174   }
    175   UNREACHABLE();
    176   return os;
    177 }
    178 
    179 
    180 OStream& operator<<(OStream& os, const AddressingMode& am) {
    181   switch (am) {
    182     case kMode_None:
    183       return os;
    184 #define CASE(Name)   \
    185   case kMode_##Name: \
    186     return os << #Name;
    187       TARGET_ADDRESSING_MODE_LIST(CASE)
    188 #undef CASE
    189   }
    190   UNREACHABLE();
    191   return os;
    192 }
    193 
    194 
    195 OStream& operator<<(OStream& os, const FlagsMode& fm) {
    196   switch (fm) {
    197     case kFlags_none:
    198       return os;
    199     case kFlags_branch:
    200       return os << "branch";
    201     case kFlags_set:
    202       return os << "set";
    203   }
    204   UNREACHABLE();
    205   return os;
    206 }
    207 
    208 
    209 OStream& operator<<(OStream& os, const FlagsCondition& fc) {
    210   switch (fc) {
    211     case kEqual:
    212       return os << "equal";
    213     case kNotEqual:
    214       return os << "not equal";
    215     case kSignedLessThan:
    216       return os << "signed less than";
    217     case kSignedGreaterThanOrEqual:
    218       return os << "signed greater than or equal";
    219     case kSignedLessThanOrEqual:
    220       return os << "signed less than or equal";
    221     case kSignedGreaterThan:
    222       return os << "signed greater than";
    223     case kUnsignedLessThan:
    224       return os << "unsigned less than";
    225     case kUnsignedGreaterThanOrEqual:
    226       return os << "unsigned greater than or equal";
    227     case kUnsignedLessThanOrEqual:
    228       return os << "unsigned less than or equal";
    229     case kUnsignedGreaterThan:
    230       return os << "unsigned greater than";
    231     case kUnorderedEqual:
    232       return os << "unordered equal";
    233     case kUnorderedNotEqual:
    234       return os << "unordered not equal";
    235     case kUnorderedLessThan:
    236       return os << "unordered less than";
    237     case kUnorderedGreaterThanOrEqual:
    238       return os << "unordered greater than or equal";
    239     case kUnorderedLessThanOrEqual:
    240       return os << "unordered less than or equal";
    241     case kUnorderedGreaterThan:
    242       return os << "unordered greater than";
    243     case kOverflow:
    244       return os << "overflow";
    245     case kNotOverflow:
    246       return os << "not overflow";
    247   }
    248   UNREACHABLE();
    249   return os;
    250 }
    251 
    252 
    253 OStream& operator<<(OStream& os, const Instruction& instr) {
    254   if (instr.OutputCount() > 1) os << "(";
    255   for (size_t i = 0; i < instr.OutputCount(); i++) {
    256     if (i > 0) os << ", ";
    257     os << *instr.OutputAt(i);
    258   }
    259 
    260   if (instr.OutputCount() > 1) os << ") = ";
    261   if (instr.OutputCount() == 1) os << " = ";
    262 
    263   if (instr.IsGapMoves()) {
    264     const GapInstruction* gap = GapInstruction::cast(&instr);
    265     os << (instr.IsBlockStart() ? " block-start" : "gap ");
    266     for (int i = GapInstruction::FIRST_INNER_POSITION;
    267          i <= GapInstruction::LAST_INNER_POSITION; i++) {
    268       os << "(";
    269       if (gap->parallel_moves_[i] != NULL) os << *gap->parallel_moves_[i];
    270       os << ") ";
    271     }
    272   } else if (instr.IsSourcePosition()) {
    273     const SourcePositionInstruction* pos =
    274         SourcePositionInstruction::cast(&instr);
    275     os << "position (" << pos->source_position().raw() << ")";
    276   } else {
    277     os << ArchOpcodeField::decode(instr.opcode());
    278     AddressingMode am = AddressingModeField::decode(instr.opcode());
    279     if (am != kMode_None) {
    280       os << " : " << AddressingModeField::decode(instr.opcode());
    281     }
    282     FlagsMode fm = FlagsModeField::decode(instr.opcode());
    283     if (fm != kFlags_none) {
    284       os << " && " << fm << " if "
    285          << FlagsConditionField::decode(instr.opcode());
    286     }
    287   }
    288   if (instr.InputCount() > 0) {
    289     for (size_t i = 0; i < instr.InputCount(); i++) {
    290       os << " " << *instr.InputAt(i);
    291     }
    292   }
    293   return os << "\n";
    294 }
    295 
    296 
    297 OStream& operator<<(OStream& os, const Constant& constant) {
    298   switch (constant.type()) {
    299     case Constant::kInt32:
    300       return os << constant.ToInt32();
    301     case Constant::kInt64:
    302       return os << constant.ToInt64() << "l";
    303     case Constant::kFloat64:
    304       return os << constant.ToFloat64();
    305     case Constant::kExternalReference:
    306       return os << constant.ToExternalReference().address();
    307     case Constant::kHeapObject:
    308       return os << Brief(*constant.ToHeapObject());
    309   }
    310   UNREACHABLE();
    311   return os;
    312 }
    313 
    314 
    315 Label* InstructionSequence::GetLabel(BasicBlock* block) {
    316   return GetBlockStart(block)->label();
    317 }
    318 
    319 
    320 BlockStartInstruction* InstructionSequence::GetBlockStart(BasicBlock* block) {
    321   return BlockStartInstruction::cast(InstructionAt(block->code_start_));
    322 }
    323 
    324 
    325 void InstructionSequence::StartBlock(BasicBlock* block) {
    326   block->code_start_ = static_cast<int>(instructions_.size());
    327   BlockStartInstruction* block_start =
    328       BlockStartInstruction::New(zone(), block);
    329   AddInstruction(block_start, block);
    330 }
    331 
    332 
    333 void InstructionSequence::EndBlock(BasicBlock* block) {
    334   int end = static_cast<int>(instructions_.size());
    335   DCHECK(block->code_start_ >= 0 && block->code_start_ < end);
    336   block->code_end_ = end;
    337 }
    338 
    339 
    340 int InstructionSequence::AddInstruction(Instruction* instr, BasicBlock* block) {
    341   // TODO(titzer): the order of these gaps is a holdover from Lithium.
    342   GapInstruction* gap = GapInstruction::New(zone());
    343   if (instr->IsControl()) instructions_.push_back(gap);
    344   int index = static_cast<int>(instructions_.size());
    345   instructions_.push_back(instr);
    346   if (!instr->IsControl()) instructions_.push_back(gap);
    347   if (instr->NeedsPointerMap()) {
    348     DCHECK(instr->pointer_map() == NULL);
    349     PointerMap* pointer_map = new (zone()) PointerMap(zone());
    350     pointer_map->set_instruction_position(index);
    351     instr->set_pointer_map(pointer_map);
    352     pointer_maps_.push_back(pointer_map);
    353   }
    354   return index;
    355 }
    356 
    357 
    358 BasicBlock* InstructionSequence::GetBasicBlock(int instruction_index) {
    359   // TODO(turbofan): Optimize this.
    360   for (;;) {
    361     DCHECK_LE(0, instruction_index);
    362     Instruction* instruction = InstructionAt(instruction_index--);
    363     if (instruction->IsBlockStart()) {
    364       return BlockStartInstruction::cast(instruction)->block();
    365     }
    366   }
    367 }
    368 
    369 
    370 bool InstructionSequence::IsReference(int virtual_register) const {
    371   return references_.find(virtual_register) != references_.end();
    372 }
    373 
    374 
    375 bool InstructionSequence::IsDouble(int virtual_register) const {
    376   return doubles_.find(virtual_register) != doubles_.end();
    377 }
    378 
    379 
    380 void InstructionSequence::MarkAsReference(int virtual_register) {
    381   references_.insert(virtual_register);
    382 }
    383 
    384 
    385 void InstructionSequence::MarkAsDouble(int virtual_register) {
    386   doubles_.insert(virtual_register);
    387 }
    388 
    389 
    390 void InstructionSequence::AddGapMove(int index, InstructionOperand* from,
    391                                      InstructionOperand* to) {
    392   GapAt(index)->GetOrCreateParallelMove(GapInstruction::START, zone())->AddMove(
    393       from, to, zone());
    394 }
    395 
    396 
    397 InstructionSequence::StateId InstructionSequence::AddFrameStateDescriptor(
    398     FrameStateDescriptor* descriptor) {
    399   int deoptimization_id = static_cast<int>(deoptimization_entries_.size());
    400   deoptimization_entries_.push_back(descriptor);
    401   return StateId::FromInt(deoptimization_id);
    402 }
    403 
    404 FrameStateDescriptor* InstructionSequence::GetFrameStateDescriptor(
    405     InstructionSequence::StateId state_id) {
    406   return deoptimization_entries_[state_id.ToInt()];
    407 }
    408 
    409 
    410 int InstructionSequence::GetFrameStateDescriptorCount() {
    411   return static_cast<int>(deoptimization_entries_.size());
    412 }
    413 
    414 
    415 OStream& operator<<(OStream& os, const InstructionSequence& code) {
    416   for (size_t i = 0; i < code.immediates_.size(); ++i) {
    417     Constant constant = code.immediates_[i];
    418     os << "IMM#" << i << ": " << constant << "\n";
    419   }
    420   int i = 0;
    421   for (ConstantMap::const_iterator it = code.constants_.begin();
    422        it != code.constants_.end(); ++i, ++it) {
    423     os << "CST#" << i << ": v" << it->first << " = " << it->second << "\n";
    424   }
    425   for (int i = 0; i < code.BasicBlockCount(); i++) {
    426     BasicBlock* block = code.BlockAt(i);
    427 
    428     int bid = block->id();
    429     os << "RPO#" << block->rpo_number_ << ": B" << bid;
    430     CHECK(block->rpo_number_ == i);
    431     if (block->IsLoopHeader()) {
    432       os << " loop blocks: [" << block->rpo_number_ << ", " << block->loop_end_
    433          << ")";
    434     }
    435     os << "  instructions: [" << block->code_start_ << ", " << block->code_end_
    436        << ")\n  predecessors:";
    437 
    438     BasicBlock::Predecessors predecessors = block->predecessors();
    439     for (BasicBlock::Predecessors::iterator iter = predecessors.begin();
    440          iter != predecessors.end(); ++iter) {
    441       os << " B" << (*iter)->id();
    442     }
    443     os << "\n";
    444 
    445     for (BasicBlock::const_iterator j = block->begin(); j != block->end();
    446          ++j) {
    447       Node* phi = *j;
    448       if (phi->opcode() != IrOpcode::kPhi) continue;
    449       os << "     phi: v" << phi->id() << " =";
    450       Node::Inputs inputs = phi->inputs();
    451       for (Node::Inputs::iterator iter(inputs.begin()); iter != inputs.end();
    452            ++iter) {
    453         os << " v" << (*iter)->id();
    454       }
    455       os << "\n";
    456     }
    457 
    458     ScopedVector<char> buf(32);
    459     for (int j = block->first_instruction_index();
    460          j <= block->last_instruction_index(); j++) {
    461       // TODO(svenpanne) Add some basic formatting to our streams.
    462       SNPrintF(buf, "%5d", j);
    463       os << "   " << buf.start() << ": " << *code.InstructionAt(j);
    464     }
    465 
    466     os << "  " << block->control_;
    467 
    468     if (block->control_input_ != NULL) {
    469       os << " v" << block->control_input_->id();
    470     }
    471 
    472     BasicBlock::Successors successors = block->successors();
    473     for (BasicBlock::Successors::iterator iter = successors.begin();
    474          iter != successors.end(); ++iter) {
    475       os << " B" << (*iter)->id();
    476     }
    477     os << "\n";
    478   }
    479   return os;
    480 }
    481 
    482 }  // namespace compiler
    483 }  // namespace internal
    484 }  // namespace v8
    485