src/v8/src/compiler/instruction.cc

   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