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
13namespace v8 {
14namespace internal {
15namespace compiler {
16
17const RegisterConfiguration* (*GetRegConfig)() =
18    RegisterConfiguration::Turbofan;
19
20FlagsCondition 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
70bool 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
101void 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
109void InstructionOperand::Print() const { Print(GetRegConfig()); }
110
111std::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
241void 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
251void MoveOperands::Print() const { Print(GetRegConfig()); }
252
253std::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
267bool ParallelMove::IsRedundant() const {
268  for (MoveOperands* move : *this) {
269    if (!move->IsRedundant()) return false;
270  }
271  return true;
272}
273
274void 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
299ExplicitOperand::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
310Instruction::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
320Instruction::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
349bool 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
359void 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
367void Instruction::Print() const { Print(GetRegConfig()); }
368
369std::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
384void 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
392std::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
409std::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
422std::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
437std::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
455std::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
511std::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
558Constant::Constant(int32_t v) : type_(kInt32), value_(v) {}
559
560Constant::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
572Handle<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
579std::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
602PhiInstruction::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
610void PhiInstruction::SetInput(size_t offset, int virtual_register) {
611  DCHECK_EQ(InstructionOperand::kInvalidVirtualRegister, operands_[offset]);
612  operands_[offset] = virtual_register;
613}
614
615void PhiInstruction::RenameInput(size_t offset, int virtual_register) {
616  DCHECK_NE(InstructionOperand::kInvalidVirtualRegister, operands_[offset]);
617  operands_[offset] = virtual_register;
618}
619
620InstructionBlock::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
638size_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
648static RpoNumber GetRpo(const BasicBlock* block) {
649  if (block == nullptr) return RpoNumber::Invalid();
650  return RpoNumber::FromInt(block->rpo_number());
651}
652
653
654static RpoNumber GetLoopEndRpo(const BasicBlock* block) {
655  if (!block->IsLoopHeader()) return RpoNumber::Invalid();
656  return RpoNumber::FromInt(block->loop_end()->rpo_number());
657}
658
659
660static 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
679std::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
731InstructionBlocks* 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
747void 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
762void 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
773void 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
787void 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
802void 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
816InstructionSequence::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
834int InstructionSequence::NextVirtualRegister() {
835  int virtual_register = next_virtual_register_++;
836  CHECK_NE(virtual_register, InstructionOperand::kInvalidVirtualRegister);
837  return virtual_register;
838}
839
840
841Instruction* InstructionSequence::GetBlockStart(RpoNumber rpo) const {
842  const InstructionBlock* block = InstructionBlockAt(rpo);
843  return InstructionAt(block->code_start());
844}
845
846
847void 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
855void 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
869int 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
885InstructionBlock* InstructionSequence::GetInstructionBlock(
886    int instruction_index) const {
887  return instructions()[instruction_index]->block();
888}
889
890
891static 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
917MachineRepresentation 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
928void 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
942int 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
951DeoptimizationEntry const& InstructionSequence::GetDeoptimizationEntry(
952    int state_id) {
953  return deoptimization_entries_[state_id];
954}
955
956
957RpoNumber 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
967bool 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
976void InstructionSequence::SetSourcePosition(const Instruction* instr,
977                                            SourcePosition value) {
978  source_positions_.insert(std::make_pair(instr, value));
979}
980
981void 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
989void InstructionSequence::Print() const { Print(GetRegConfig()); }
990
991void 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
1001void InstructionSequence::PrintBlock(int block_id) const {
1002  PrintBlock(GetRegConfig(), block_id);
1003}
1004
1005const RegisterConfiguration*
1006    InstructionSequence::registerConfigurationForTesting_ = nullptr;
1007
1008const RegisterConfiguration*
1009InstructionSequence::RegisterConfigurationForTesting() {
1010  DCHECK(registerConfigurationForTesting_ != nullptr);
1011  return registerConfigurationForTesting_;
1012}
1013
1014void InstructionSequence::SetRegisterConfigurationForTesting(
1015    const RegisterConfiguration* regConfig) {
1016  registerConfigurationForTesting_ = regConfig;
1017  GetRegConfig = InstructionSequence::RegisterConfigurationForTesting;
1018}
1019
1020FrameStateDescriptor::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
1037size_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
1051size_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
1061size_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
1071size_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
1083std::ostream& operator<<(std::ostream& os, const RpoNumber& rpo) {
1084  return os << rpo.ToSize();
1085}
1086
1087
1088std::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