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
9namespace v8 {
10namespace internal {
11namespace compiler {
12
13OStream& 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
60template <InstructionOperand::Kind kOperandKind, int kNumCachedOperands>
61SubKindOperand<kOperandKind, kNumCachedOperands>*
62    SubKindOperand<kOperandKind, kNumCachedOperands>::cache = NULL;
63
64
65template <InstructionOperand::Kind kOperandKind, int kNumCachedOperands>
66void 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
75template <InstructionOperand::Kind kOperandKind, int kNumCachedOperands>
76void SubKindOperand<kOperandKind, kNumCachedOperands>::TearDownCache() {
77  delete[] cache;
78  cache = NULL;
79}
80
81
82void 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
90void 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
98OStream& 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
105bool 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
113OStream& 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
126void 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
134void 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
147void 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
155OStream& 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
167OStream& 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
180OStream& 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
195OStream& 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
209OStream& 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
253OStream& 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
297OStream& 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
315Label* InstructionSequence::GetLabel(BasicBlock* block) {
316  return GetBlockStart(block)->label();
317}
318
319
320BlockStartInstruction* InstructionSequence::GetBlockStart(BasicBlock* block) {
321  return BlockStartInstruction::cast(InstructionAt(block->code_start_));
322}
323
324
325void 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
333void 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
340int 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
358BasicBlock* 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
370bool InstructionSequence::IsReference(int virtual_register) const {
371  return references_.find(virtual_register) != references_.end();
372}
373
374
375bool InstructionSequence::IsDouble(int virtual_register) const {
376  return doubles_.find(virtual_register) != doubles_.end();
377}
378
379
380void InstructionSequence::MarkAsReference(int virtual_register) {
381  references_.insert(virtual_register);
382}
383
384
385void InstructionSequence::MarkAsDouble(int virtual_register) {
386  doubles_.insert(virtual_register);
387}
388
389
390void InstructionSequence::AddGapMove(int index, InstructionOperand* from,
391                                     InstructionOperand* to) {
392  GapAt(index)->GetOrCreateParallelMove(GapInstruction::START, zone())->AddMove(
393      from, to, zone());
394}
395
396
397InstructionSequence::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
404FrameStateDescriptor* InstructionSequence::GetFrameStateDescriptor(
405    InstructionSequence::StateId state_id) {
406  return deoptimization_entries_[state_id.ToInt()];
407}
408
409
410int InstructionSequence::GetFrameStateDescriptorCount() {
411  return static_cast<int>(deoptimization_entries_.size());
412}
413
414
415OStream& 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