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