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/common-operator.h"
6 #include "src/compiler/graph.h"
7 #include "src/compiler/instruction.h"
8 #include "src/compiler/schedule.h"
9 #include "src/compiler/state-values-utils.h"
10 
11 namespace v8 {
12 namespace internal {
13 namespace compiler {
14 
15 const RegisterConfiguration* (*GetRegConfig)() =
16     RegisterConfiguration::Turbofan;
17 
CommuteFlagsCondition(FlagsCondition condition)18 FlagsCondition CommuteFlagsCondition(FlagsCondition condition) {
19   switch (condition) {
20     case kSignedLessThan:
21       return kSignedGreaterThan;
22     case kSignedGreaterThanOrEqual:
23       return kSignedLessThanOrEqual;
24     case kSignedLessThanOrEqual:
25       return kSignedGreaterThanOrEqual;
26     case kSignedGreaterThan:
27       return kSignedLessThan;
28     case kUnsignedLessThan:
29       return kUnsignedGreaterThan;
30     case kUnsignedGreaterThanOrEqual:
31       return kUnsignedLessThanOrEqual;
32     case kUnsignedLessThanOrEqual:
33       return kUnsignedGreaterThanOrEqual;
34     case kUnsignedGreaterThan:
35       return kUnsignedLessThan;
36     case kFloatLessThanOrUnordered:
37       return kFloatGreaterThanOrUnordered;
38     case kFloatGreaterThanOrEqual:
39       return kFloatLessThanOrEqual;
40     case kFloatLessThanOrEqual:
41       return kFloatGreaterThanOrEqual;
42     case kFloatGreaterThanOrUnordered:
43       return kFloatLessThanOrUnordered;
44     case kFloatLessThan:
45       return kFloatGreaterThan;
46     case kFloatGreaterThanOrEqualOrUnordered:
47       return kFloatLessThanOrEqualOrUnordered;
48     case kFloatLessThanOrEqualOrUnordered:
49       return kFloatGreaterThanOrEqualOrUnordered;
50     case kFloatGreaterThan:
51       return kFloatLessThan;
52     case kPositiveOrZero:
53     case kNegative:
54       UNREACHABLE();
55       break;
56     case kEqual:
57     case kNotEqual:
58     case kOverflow:
59     case kNotOverflow:
60     case kUnorderedEqual:
61     case kUnorderedNotEqual:
62       return condition;
63   }
64   UNREACHABLE();
65   return condition;
66 }
67 
InterferesWith(const InstructionOperand & other) const68 bool InstructionOperand::InterferesWith(const InstructionOperand& other) const {
69   if (kSimpleFPAliasing || !this->IsFPLocationOperand() ||
70       !other.IsFPLocationOperand())
71     return EqualsCanonicalized(other);
72   // Aliasing is complex and both operands are fp locations.
73   const LocationOperand& loc = *LocationOperand::cast(this);
74   const LocationOperand& other_loc = LocationOperand::cast(other);
75   LocationOperand::LocationKind kind = loc.location_kind();
76   LocationOperand::LocationKind other_kind = other_loc.location_kind();
77   if (kind != other_kind) return false;
78   MachineRepresentation rep = loc.representation();
79   MachineRepresentation other_rep = other_loc.representation();
80   if (rep == other_rep) return EqualsCanonicalized(other);
81   if (kind == LocationOperand::REGISTER) {
82     // FP register-register interference.
83     return GetRegConfig()->AreAliases(rep, loc.register_code(), other_rep,
84                                       other_loc.register_code());
85   } else {
86     // FP slot-slot interference. Slots of different FP reps can alias because
87     // the gap resolver may break a move into 2 or 4 equivalent smaller moves.
88     DCHECK_EQ(LocationOperand::STACK_SLOT, kind);
89     int index_hi = loc.index();
90     int index_lo = index_hi - (1 << ElementSizeLog2Of(rep)) / kPointerSize + 1;
91     int other_index_hi = other_loc.index();
92     int other_index_lo =
93         other_index_hi - (1 << ElementSizeLog2Of(other_rep)) / kPointerSize + 1;
94     return other_index_hi >= index_lo && index_hi >= other_index_lo;
95   }
96   return false;
97 }
98 
Print(const RegisterConfiguration * config) const99 void InstructionOperand::Print(const RegisterConfiguration* config) const {
100   OFStream os(stdout);
101   PrintableInstructionOperand wrapper;
102   wrapper.register_configuration_ = config;
103   wrapper.op_ = *this;
104   os << wrapper << std::endl;
105 }
106 
Print() const107 void InstructionOperand::Print() const { Print(GetRegConfig()); }
108 
operator <<(std::ostream & os,const PrintableInstructionOperand & printable)109 std::ostream& operator<<(std::ostream& os,
110                          const PrintableInstructionOperand& printable) {
111   const InstructionOperand& op = printable.op_;
112   const RegisterConfiguration* conf = printable.register_configuration_;
113   switch (op.kind()) {
114     case InstructionOperand::UNALLOCATED: {
115       const UnallocatedOperand* unalloc = UnallocatedOperand::cast(&op);
116       os << "v" << unalloc->virtual_register();
117       if (unalloc->basic_policy() == UnallocatedOperand::FIXED_SLOT) {
118         return os << "(=" << unalloc->fixed_slot_index() << "S)";
119       }
120       switch (unalloc->extended_policy()) {
121         case UnallocatedOperand::NONE:
122           return os;
123         case UnallocatedOperand::FIXED_REGISTER:
124           return os << "(="
125                     << conf->GetGeneralRegisterName(
126                            unalloc->fixed_register_index())
127                     << ")";
128         case UnallocatedOperand::FIXED_FP_REGISTER:
129           return os << "(="
130                     << conf->GetDoubleRegisterName(
131                            unalloc->fixed_register_index())
132                     << ")";
133         case UnallocatedOperand::MUST_HAVE_REGISTER:
134           return os << "(R)";
135         case UnallocatedOperand::MUST_HAVE_SLOT:
136           return os << "(S)";
137         case UnallocatedOperand::SAME_AS_FIRST_INPUT:
138           return os << "(1)";
139         case UnallocatedOperand::ANY:
140           return os << "(-)";
141       }
142     }
143     case InstructionOperand::CONSTANT:
144       return os << "[constant:" << ConstantOperand::cast(op).virtual_register()
145                 << "]";
146     case InstructionOperand::IMMEDIATE: {
147       ImmediateOperand imm = ImmediateOperand::cast(op);
148       switch (imm.type()) {
149         case ImmediateOperand::INLINE:
150           return os << "#" << imm.inline_value();
151         case ImmediateOperand::INDEXED:
152           return os << "[immediate:" << imm.indexed_value() << "]";
153       }
154     }
155     case InstructionOperand::EXPLICIT:
156     case InstructionOperand::ALLOCATED: {
157       LocationOperand allocated = LocationOperand::cast(op);
158       if (op.IsStackSlot()) {
159         os << "[stack:" << allocated.index();
160       } else if (op.IsFPStackSlot()) {
161         os << "[fp_stack:" << allocated.index();
162       } else if (op.IsRegister()) {
163         os << "["
164            << GetRegConfig()->GetGeneralRegisterName(allocated.register_code())
165            << "|R";
166       } else if (op.IsDoubleRegister()) {
167         os << "["
168            << GetRegConfig()->GetDoubleRegisterName(allocated.register_code())
169            << "|R";
170       } else if (op.IsFloatRegister()) {
171         os << "["
172            << GetRegConfig()->GetFloatRegisterName(allocated.register_code())
173            << "|R";
174       } else {
175         DCHECK(op.IsSimd128Register());
176         os << "["
177            << GetRegConfig()->GetSimd128RegisterName(allocated.register_code())
178            << "|R";
179       }
180       if (allocated.IsExplicit()) {
181         os << "|E";
182       }
183       switch (allocated.representation()) {
184         case MachineRepresentation::kNone:
185           os << "|-";
186           break;
187         case MachineRepresentation::kBit:
188           os << "|b";
189           break;
190         case MachineRepresentation::kWord8:
191           os << "|w8";
192           break;
193         case MachineRepresentation::kWord16:
194           os << "|w16";
195           break;
196         case MachineRepresentation::kWord32:
197           os << "|w32";
198           break;
199         case MachineRepresentation::kWord64:
200           os << "|w64";
201           break;
202         case MachineRepresentation::kFloat32:
203           os << "|f32";
204           break;
205         case MachineRepresentation::kFloat64:
206           os << "|f64";
207           break;
208         case MachineRepresentation::kSimd128:
209           os << "|s128";
210           break;
211         case MachineRepresentation::kTaggedSigned:
212           os << "|ts";
213           break;
214         case MachineRepresentation::kTaggedPointer:
215           os << "|tp";
216           break;
217         case MachineRepresentation::kTagged:
218           os << "|t";
219           break;
220       }
221       return os << "]";
222     }
223     case InstructionOperand::INVALID:
224       return os << "(x)";
225   }
226   UNREACHABLE();
227   return os;
228 }
229 
Print(const RegisterConfiguration * config) const230 void MoveOperands::Print(const RegisterConfiguration* config) const {
231   OFStream os(stdout);
232   PrintableInstructionOperand wrapper;
233   wrapper.register_configuration_ = config;
234   wrapper.op_ = destination();
235   os << wrapper << " = ";
236   wrapper.op_ = source();
237   os << wrapper << std::endl;
238 }
239 
Print() const240 void MoveOperands::Print() const { Print(GetRegConfig()); }
241 
operator <<(std::ostream & os,const PrintableMoveOperands & printable)242 std::ostream& operator<<(std::ostream& os,
243                          const PrintableMoveOperands& printable) {
244   const MoveOperands& mo = *printable.move_operands_;
245   PrintableInstructionOperand printable_op = {printable.register_configuration_,
246                                               mo.destination()};
247   os << printable_op;
248   if (!mo.source().Equals(mo.destination())) {
249     printable_op.op_ = mo.source();
250     os << " = " << printable_op;
251   }
252   return os << ";";
253 }
254 
255 
IsRedundant() const256 bool ParallelMove::IsRedundant() const {
257   for (MoveOperands* move : *this) {
258     if (!move->IsRedundant()) return false;
259   }
260   return true;
261 }
262 
PrepareInsertAfter(MoveOperands * move,ZoneVector<MoveOperands * > * to_eliminate) const263 void ParallelMove::PrepareInsertAfter(
264     MoveOperands* move, ZoneVector<MoveOperands*>* to_eliminate) const {
265   bool no_aliasing =
266       kSimpleFPAliasing || !move->destination().IsFPLocationOperand();
267   MoveOperands* replacement = nullptr;
268   MoveOperands* eliminated = nullptr;
269   for (MoveOperands* curr : *this) {
270     if (curr->IsEliminated()) continue;
271     if (curr->destination().EqualsCanonicalized(move->source())) {
272       // We must replace move's source with curr's destination in order to
273       // insert it into this ParallelMove.
274       DCHECK(!replacement);
275       replacement = curr;
276       if (no_aliasing && eliminated != nullptr) break;
277     } else if (curr->destination().InterferesWith(move->destination())) {
278       // We can eliminate curr, since move overwrites at least a part of its
279       // destination, implying its value is no longer live.
280       eliminated = curr;
281       to_eliminate->push_back(curr);
282       if (no_aliasing && replacement != nullptr) break;
283     }
284   }
285   if (replacement != nullptr) move->set_source(replacement->source());
286 }
287 
ExplicitOperand(LocationKind kind,MachineRepresentation rep,int index)288 ExplicitOperand::ExplicitOperand(LocationKind kind, MachineRepresentation rep,
289                                  int index)
290     : LocationOperand(EXPLICIT, kind, rep, index) {
291   DCHECK_IMPLIES(kind == REGISTER && !IsFloatingPoint(rep),
292                  GetRegConfig()->IsAllocatableGeneralCode(index));
293   DCHECK_IMPLIES(kind == REGISTER && rep == MachineRepresentation::kFloat32,
294                  GetRegConfig()->IsAllocatableFloatCode(index));
295   DCHECK_IMPLIES(kind == REGISTER && (rep == MachineRepresentation::kFloat64),
296                  GetRegConfig()->IsAllocatableDoubleCode(index));
297 }
298 
Instruction(InstructionCode opcode)299 Instruction::Instruction(InstructionCode opcode)
300     : opcode_(opcode),
301       bit_field_(OutputCountField::encode(0) | InputCountField::encode(0) |
302                  TempCountField::encode(0) | IsCallField::encode(false)),
303       reference_map_(nullptr),
304       block_(nullptr) {
305   parallel_moves_[0] = nullptr;
306   parallel_moves_[1] = nullptr;
307 }
308 
Instruction(InstructionCode opcode,size_t output_count,InstructionOperand * outputs,size_t input_count,InstructionOperand * inputs,size_t temp_count,InstructionOperand * temps)309 Instruction::Instruction(InstructionCode opcode, size_t output_count,
310                          InstructionOperand* outputs, size_t input_count,
311                          InstructionOperand* inputs, size_t temp_count,
312                          InstructionOperand* temps)
313     : opcode_(opcode),
314       bit_field_(OutputCountField::encode(output_count) |
315                  InputCountField::encode(input_count) |
316                  TempCountField::encode(temp_count) |
317                  IsCallField::encode(false)),
318       reference_map_(nullptr),
319       block_(nullptr) {
320   parallel_moves_[0] = nullptr;
321   parallel_moves_[1] = nullptr;
322   size_t offset = 0;
323   for (size_t i = 0; i < output_count; ++i) {
324     DCHECK(!outputs[i].IsInvalid());
325     operands_[offset++] = outputs[i];
326   }
327   for (size_t i = 0; i < input_count; ++i) {
328     DCHECK(!inputs[i].IsInvalid());
329     operands_[offset++] = inputs[i];
330   }
331   for (size_t i = 0; i < temp_count; ++i) {
332     DCHECK(!temps[i].IsInvalid());
333     operands_[offset++] = temps[i];
334   }
335 }
336 
337 
AreMovesRedundant() const338 bool Instruction::AreMovesRedundant() const {
339   for (int i = Instruction::FIRST_GAP_POSITION;
340        i <= Instruction::LAST_GAP_POSITION; i++) {
341     if (parallel_moves_[i] != nullptr && !parallel_moves_[i]->IsRedundant()) {
342       return false;
343     }
344   }
345   return true;
346 }
347 
Print(const RegisterConfiguration * config) const348 void Instruction::Print(const RegisterConfiguration* config) const {
349   OFStream os(stdout);
350   PrintableInstruction wrapper;
351   wrapper.instr_ = this;
352   wrapper.register_configuration_ = config;
353   os << wrapper << std::endl;
354 }
355 
Print() const356 void Instruction::Print() const { Print(GetRegConfig()); }
357 
operator <<(std::ostream & os,const PrintableParallelMove & printable)358 std::ostream& operator<<(std::ostream& os,
359                          const PrintableParallelMove& printable) {
360   const ParallelMove& pm = *printable.parallel_move_;
361   bool first = true;
362   for (MoveOperands* move : pm) {
363     if (move->IsEliminated()) continue;
364     if (!first) os << " ";
365     first = false;
366     PrintableMoveOperands pmo = {printable.register_configuration_, move};
367     os << pmo;
368   }
369   return os;
370 }
371 
372 
RecordReference(const AllocatedOperand & op)373 void ReferenceMap::RecordReference(const AllocatedOperand& op) {
374   // Do not record arguments as pointers.
375   if (op.IsStackSlot() && LocationOperand::cast(op).index() < 0) return;
376   DCHECK(!op.IsFPRegister() && !op.IsFPStackSlot());
377   reference_operands_.push_back(op);
378 }
379 
380 
operator <<(std::ostream & os,const ReferenceMap & pm)381 std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm) {
382   os << "{";
383   bool first = true;
384   PrintableInstructionOperand poi = {GetRegConfig(), InstructionOperand()};
385   for (const InstructionOperand& op : pm.reference_operands_) {
386     if (!first) {
387       os << ";";
388     } else {
389       first = false;
390     }
391     poi.op_ = op;
392     os << poi;
393   }
394   return os << "}";
395 }
396 
397 
operator <<(std::ostream & os,const ArchOpcode & ao)398 std::ostream& operator<<(std::ostream& os, const ArchOpcode& ao) {
399   switch (ao) {
400 #define CASE(Name) \
401   case k##Name:    \
402     return os << #Name;
403     ARCH_OPCODE_LIST(CASE)
404 #undef CASE
405   }
406   UNREACHABLE();
407   return os;
408 }
409 
410 
operator <<(std::ostream & os,const AddressingMode & am)411 std::ostream& operator<<(std::ostream& os, const AddressingMode& am) {
412   switch (am) {
413     case kMode_None:
414       return os;
415 #define CASE(Name)   \
416   case kMode_##Name: \
417     return os << #Name;
418       TARGET_ADDRESSING_MODE_LIST(CASE)
419 #undef CASE
420   }
421   UNREACHABLE();
422   return os;
423 }
424 
425 
operator <<(std::ostream & os,const FlagsMode & fm)426 std::ostream& operator<<(std::ostream& os, const FlagsMode& fm) {
427   switch (fm) {
428     case kFlags_none:
429       return os;
430     case kFlags_branch:
431       return os << "branch";
432     case kFlags_deoptimize:
433       return os << "deoptimize";
434     case kFlags_set:
435       return os << "set";
436   }
437   UNREACHABLE();
438   return os;
439 }
440 
441 
operator <<(std::ostream & os,const FlagsCondition & fc)442 std::ostream& operator<<(std::ostream& os, const FlagsCondition& fc) {
443   switch (fc) {
444     case kEqual:
445       return os << "equal";
446     case kNotEqual:
447       return os << "not equal";
448     case kSignedLessThan:
449       return os << "signed less than";
450     case kSignedGreaterThanOrEqual:
451       return os << "signed greater than or equal";
452     case kSignedLessThanOrEqual:
453       return os << "signed less than or equal";
454     case kSignedGreaterThan:
455       return os << "signed greater than";
456     case kUnsignedLessThan:
457       return os << "unsigned less than";
458     case kUnsignedGreaterThanOrEqual:
459       return os << "unsigned greater than or equal";
460     case kUnsignedLessThanOrEqual:
461       return os << "unsigned less than or equal";
462     case kUnsignedGreaterThan:
463       return os << "unsigned greater than";
464     case kFloatLessThanOrUnordered:
465       return os << "less than or unordered (FP)";
466     case kFloatGreaterThanOrEqual:
467       return os << "greater than or equal (FP)";
468     case kFloatLessThanOrEqual:
469       return os << "less than or equal (FP)";
470     case kFloatGreaterThanOrUnordered:
471       return os << "greater than or unordered (FP)";
472     case kFloatLessThan:
473       return os << "less than (FP)";
474     case kFloatGreaterThanOrEqualOrUnordered:
475       return os << "greater than, equal or unordered (FP)";
476     case kFloatLessThanOrEqualOrUnordered:
477       return os << "less than, equal or unordered (FP)";
478     case kFloatGreaterThan:
479       return os << "greater than (FP)";
480     case kUnorderedEqual:
481       return os << "unordered equal";
482     case kUnorderedNotEqual:
483       return os << "unordered not equal";
484     case kOverflow:
485       return os << "overflow";
486     case kNotOverflow:
487       return os << "not overflow";
488     case kPositiveOrZero:
489       return os << "positive or zero";
490     case kNegative:
491       return os << "negative";
492   }
493   UNREACHABLE();
494   return os;
495 }
496 
497 
operator <<(std::ostream & os,const PrintableInstruction & printable)498 std::ostream& operator<<(std::ostream& os,
499                          const PrintableInstruction& printable) {
500   const Instruction& instr = *printable.instr_;
501   PrintableInstructionOperand printable_op = {printable.register_configuration_,
502                                               InstructionOperand()};
503   os << "gap ";
504   for (int i = Instruction::FIRST_GAP_POSITION;
505        i <= Instruction::LAST_GAP_POSITION; i++) {
506     os << "(";
507     if (instr.parallel_moves()[i] != nullptr) {
508       PrintableParallelMove ppm = {printable.register_configuration_,
509                                    instr.parallel_moves()[i]};
510       os << ppm;
511     }
512     os << ") ";
513   }
514   os << "\n          ";
515 
516   if (instr.OutputCount() > 1) os << "(";
517   for (size_t i = 0; i < instr.OutputCount(); i++) {
518     if (i > 0) os << ", ";
519     printable_op.op_ = *instr.OutputAt(i);
520     os << printable_op;
521   }
522 
523   if (instr.OutputCount() > 1) os << ") = ";
524   if (instr.OutputCount() == 1) os << " = ";
525 
526   os << ArchOpcodeField::decode(instr.opcode());
527   AddressingMode am = AddressingModeField::decode(instr.opcode());
528   if (am != kMode_None) {
529     os << " : " << AddressingModeField::decode(instr.opcode());
530   }
531   FlagsMode fm = FlagsModeField::decode(instr.opcode());
532   if (fm != kFlags_none) {
533     os << " && " << fm << " if " << FlagsConditionField::decode(instr.opcode());
534   }
535   if (instr.InputCount() > 0) {
536     for (size_t i = 0; i < instr.InputCount(); i++) {
537       printable_op.op_ = *instr.InputAt(i);
538       os << " " << printable_op;
539     }
540   }
541   return os;
542 }
543 
544 
Constant(int32_t v)545 Constant::Constant(int32_t v) : type_(kInt32), value_(v) {}
546 
Constant(RelocatablePtrConstantInfo info)547 Constant::Constant(RelocatablePtrConstantInfo info) {
548   if (info.type() == RelocatablePtrConstantInfo::kInt32) {
549     type_ = kInt32;
550   } else if (info.type() == RelocatablePtrConstantInfo::kInt64) {
551     type_ = kInt64;
552   } else {
553     UNREACHABLE();
554   }
555   value_ = info.value();
556   rmode_ = info.rmode();
557 }
558 
ToHeapObject() const559 Handle<HeapObject> Constant::ToHeapObject() const {
560   DCHECK_EQ(kHeapObject, type());
561   Handle<HeapObject> value(
562       bit_cast<HeapObject**>(static_cast<intptr_t>(value_)));
563   return value;
564 }
565 
operator <<(std::ostream & os,const Constant & constant)566 std::ostream& operator<<(std::ostream& os, const Constant& constant) {
567   switch (constant.type()) {
568     case Constant::kInt32:
569       return os << constant.ToInt32();
570     case Constant::kInt64:
571       return os << constant.ToInt64() << "l";
572     case Constant::kFloat32:
573       return os << constant.ToFloat32() << "f";
574     case Constant::kFloat64:
575       return os << constant.ToFloat64();
576     case Constant::kExternalReference:
577       return os << static_cast<const void*>(
578                        constant.ToExternalReference().address());
579     case Constant::kHeapObject:
580       return os << Brief(*constant.ToHeapObject());
581     case Constant::kRpoNumber:
582       return os << "RPO" << constant.ToRpoNumber().ToInt();
583   }
584   UNREACHABLE();
585   return os;
586 }
587 
588 
PhiInstruction(Zone * zone,int virtual_register,size_t input_count)589 PhiInstruction::PhiInstruction(Zone* zone, int virtual_register,
590                                size_t input_count)
591     : virtual_register_(virtual_register),
592       output_(UnallocatedOperand(UnallocatedOperand::NONE, virtual_register)),
593       operands_(input_count, InstructionOperand::kInvalidVirtualRegister,
594                 zone) {}
595 
596 
SetInput(size_t offset,int virtual_register)597 void PhiInstruction::SetInput(size_t offset, int virtual_register) {
598   DCHECK_EQ(InstructionOperand::kInvalidVirtualRegister, operands_[offset]);
599   operands_[offset] = virtual_register;
600 }
601 
RenameInput(size_t offset,int virtual_register)602 void PhiInstruction::RenameInput(size_t offset, int virtual_register) {
603   DCHECK_NE(InstructionOperand::kInvalidVirtualRegister, operands_[offset]);
604   operands_[offset] = virtual_register;
605 }
606 
InstructionBlock(Zone * zone,RpoNumber rpo_number,RpoNumber loop_header,RpoNumber loop_end,bool deferred,bool handler)607 InstructionBlock::InstructionBlock(Zone* zone, RpoNumber rpo_number,
608                                    RpoNumber loop_header, RpoNumber loop_end,
609                                    bool deferred, bool handler)
610     : successors_(zone),
611       predecessors_(zone),
612       phis_(zone),
613       ao_number_(rpo_number),
614       rpo_number_(rpo_number),
615       loop_header_(loop_header),
616       loop_end_(loop_end),
617       code_start_(-1),
618       code_end_(-1),
619       deferred_(deferred),
620       handler_(handler),
621       needs_frame_(false),
622       must_construct_frame_(false),
623       must_deconstruct_frame_(false) {}
624 
PredecessorIndexOf(RpoNumber rpo_number) const625 size_t InstructionBlock::PredecessorIndexOf(RpoNumber rpo_number) const {
626   size_t j = 0;
627   for (InstructionBlock::Predecessors::const_iterator i = predecessors_.begin();
628        i != predecessors_.end(); ++i, ++j) {
629     if (*i == rpo_number) break;
630   }
631   return j;
632 }
633 
634 
GetRpo(const BasicBlock * block)635 static RpoNumber GetRpo(const BasicBlock* block) {
636   if (block == nullptr) return RpoNumber::Invalid();
637   return RpoNumber::FromInt(block->rpo_number());
638 }
639 
640 
GetLoopEndRpo(const BasicBlock * block)641 static RpoNumber GetLoopEndRpo(const BasicBlock* block) {
642   if (!block->IsLoopHeader()) return RpoNumber::Invalid();
643   return RpoNumber::FromInt(block->loop_end()->rpo_number());
644 }
645 
646 
InstructionBlockFor(Zone * zone,const BasicBlock * block)647 static InstructionBlock* InstructionBlockFor(Zone* zone,
648                                              const BasicBlock* block) {
649   bool is_handler =
650       !block->empty() && block->front()->opcode() == IrOpcode::kIfException;
651   InstructionBlock* instr_block = new (zone)
652       InstructionBlock(zone, GetRpo(block), GetRpo(block->loop_header()),
653                        GetLoopEndRpo(block), block->deferred(), is_handler);
654   // Map successors and precessors
655   instr_block->successors().reserve(block->SuccessorCount());
656   for (BasicBlock* successor : block->successors()) {
657     instr_block->successors().push_back(GetRpo(successor));
658   }
659   instr_block->predecessors().reserve(block->PredecessorCount());
660   for (BasicBlock* predecessor : block->predecessors()) {
661     instr_block->predecessors().push_back(GetRpo(predecessor));
662   }
663   return instr_block;
664 }
665 
operator <<(std::ostream & os,PrintableInstructionBlock & printable_block)666 std::ostream& operator<<(std::ostream& os,
667                          PrintableInstructionBlock& printable_block) {
668   const InstructionBlock* block = printable_block.block_;
669   const RegisterConfiguration* config = printable_block.register_configuration_;
670   const InstructionSequence* code = printable_block.code_;
671 
672   os << "B" << block->rpo_number();
673   os << ": AO#" << block->ao_number();
674   if (block->IsDeferred()) os << " (deferred)";
675   if (!block->needs_frame()) os << " (no frame)";
676   if (block->must_construct_frame()) os << " (construct frame)";
677   if (block->must_deconstruct_frame()) os << " (deconstruct frame)";
678   if (block->IsLoopHeader()) {
679     os << " loop blocks: [" << block->rpo_number() << ", " << block->loop_end()
680        << ")";
681   }
682   os << "  instructions: [" << block->code_start() << ", " << block->code_end()
683      << ")" << std::endl
684      << " predecessors:";
685 
686   for (RpoNumber pred : block->predecessors()) {
687     os << " B" << pred.ToInt();
688   }
689   os << std::endl;
690 
691   for (const PhiInstruction* phi : block->phis()) {
692     PrintableInstructionOperand printable_op = {config, phi->output()};
693     os << "     phi: " << printable_op << " =";
694     for (int input : phi->operands()) {
695       os << " v" << input;
696     }
697     os << std::endl;
698   }
699 
700   ScopedVector<char> buf(32);
701   PrintableInstruction printable_instr;
702   printable_instr.register_configuration_ = config;
703   for (int j = block->first_instruction_index();
704        j <= block->last_instruction_index(); j++) {
705     // TODO(svenpanne) Add some basic formatting to our streams.
706     SNPrintF(buf, "%5d", j);
707     printable_instr.instr_ = code->InstructionAt(j);
708     os << "   " << buf.start() << ": " << printable_instr << std::endl;
709   }
710 
711   for (RpoNumber succ : block->successors()) {
712     os << " B" << succ.ToInt();
713   }
714   os << std::endl;
715   return os;
716 }
717 
InstructionBlocksFor(Zone * zone,const Schedule * schedule)718 InstructionBlocks* InstructionSequence::InstructionBlocksFor(
719     Zone* zone, const Schedule* schedule) {
720   InstructionBlocks* blocks = zone->NewArray<InstructionBlocks>(1);
721   new (blocks) InstructionBlocks(
722       static_cast<int>(schedule->rpo_order()->size()), nullptr, zone);
723   size_t rpo_number = 0;
724   for (BasicBlockVector::const_iterator it = schedule->rpo_order()->begin();
725        it != schedule->rpo_order()->end(); ++it, ++rpo_number) {
726     DCHECK(!(*blocks)[rpo_number]);
727     DCHECK(GetRpo(*it).ToSize() == rpo_number);
728     (*blocks)[rpo_number] = InstructionBlockFor(zone, *it);
729   }
730   ComputeAssemblyOrder(blocks);
731   return blocks;
732 }
733 
ValidateEdgeSplitForm() const734 void InstructionSequence::ValidateEdgeSplitForm() const {
735   // Validate blocks are in edge-split form: no block with multiple successors
736   // has an edge to a block (== a successor) with more than one predecessors.
737   for (const InstructionBlock* block : instruction_blocks()) {
738     if (block->SuccessorCount() > 1) {
739       for (const RpoNumber& successor_id : block->successors()) {
740         const InstructionBlock* successor = InstructionBlockAt(successor_id);
741         // Expect precisely one predecessor: "block".
742         CHECK(successor->PredecessorCount() == 1 &&
743               successor->predecessors()[0] == block->rpo_number());
744       }
745     }
746   }
747 }
748 
ValidateDeferredBlockExitPaths() const749 void InstructionSequence::ValidateDeferredBlockExitPaths() const {
750   // A deferred block with more than one successor must have all its successors
751   // deferred.
752   for (const InstructionBlock* block : instruction_blocks()) {
753     if (!block->IsDeferred() || block->SuccessorCount() <= 1) continue;
754     for (RpoNumber successor_id : block->successors()) {
755       CHECK(InstructionBlockAt(successor_id)->IsDeferred());
756     }
757   }
758 }
759 
ValidateDeferredBlockEntryPaths() const760 void InstructionSequence::ValidateDeferredBlockEntryPaths() const {
761   // If a deferred block has multiple predecessors, they have to
762   // all be deferred. Otherwise, we can run into a situation where a range
763   // that spills only in deferred blocks inserts its spill in the block, but
764   // other ranges need moves inserted by ResolveControlFlow in the predecessors,
765   // which may clobber the register of this range.
766   for (const InstructionBlock* block : instruction_blocks()) {
767     if (!block->IsDeferred() || block->PredecessorCount() <= 1) continue;
768     for (RpoNumber predecessor_id : block->predecessors()) {
769       CHECK(InstructionBlockAt(predecessor_id)->IsDeferred());
770     }
771   }
772 }
773 
ValidateSSA() const774 void InstructionSequence::ValidateSSA() const {
775   // TODO(mtrofin): We could use a local zone here instead.
776   BitVector definitions(VirtualRegisterCount(), zone());
777   for (const Instruction* instruction : *this) {
778     for (size_t i = 0; i < instruction->OutputCount(); ++i) {
779       const InstructionOperand* output = instruction->OutputAt(i);
780       int vreg = (output->IsConstant())
781                      ? ConstantOperand::cast(output)->virtual_register()
782                      : UnallocatedOperand::cast(output)->virtual_register();
783       CHECK(!definitions.Contains(vreg));
784       definitions.Add(vreg);
785     }
786   }
787 }
788 
ComputeAssemblyOrder(InstructionBlocks * blocks)789 void InstructionSequence::ComputeAssemblyOrder(InstructionBlocks* blocks) {
790   int ao = 0;
791   for (InstructionBlock* const block : *blocks) {
792     if (!block->IsDeferred()) {
793       block->set_ao_number(RpoNumber::FromInt(ao++));
794     }
795   }
796   for (InstructionBlock* const block : *blocks) {
797     if (block->IsDeferred()) {
798       block->set_ao_number(RpoNumber::FromInt(ao++));
799     }
800   }
801 }
802 
InstructionSequence(Isolate * isolate,Zone * instruction_zone,InstructionBlocks * instruction_blocks)803 InstructionSequence::InstructionSequence(Isolate* isolate,
804                                          Zone* instruction_zone,
805                                          InstructionBlocks* instruction_blocks)
806     : isolate_(isolate),
807       zone_(instruction_zone),
808       instruction_blocks_(instruction_blocks),
809       source_positions_(zone()),
810       constants_(ConstantMap::key_compare(),
811                  ConstantMap::allocator_type(zone())),
812       immediates_(zone()),
813       instructions_(zone()),
814       next_virtual_register_(0),
815       reference_maps_(zone()),
816       representations_(zone()),
817       representation_mask_(0),
818       deoptimization_entries_(zone()),
819       current_block_(nullptr) {}
820 
NextVirtualRegister()821 int InstructionSequence::NextVirtualRegister() {
822   int virtual_register = next_virtual_register_++;
823   CHECK_NE(virtual_register, InstructionOperand::kInvalidVirtualRegister);
824   return virtual_register;
825 }
826 
827 
GetBlockStart(RpoNumber rpo) const828 Instruction* InstructionSequence::GetBlockStart(RpoNumber rpo) const {
829   const InstructionBlock* block = InstructionBlockAt(rpo);
830   return InstructionAt(block->code_start());
831 }
832 
833 
StartBlock(RpoNumber rpo)834 void InstructionSequence::StartBlock(RpoNumber rpo) {
835   DCHECK_NULL(current_block_);
836   current_block_ = InstructionBlockAt(rpo);
837   int code_start = static_cast<int>(instructions_.size());
838   current_block_->set_code_start(code_start);
839 }
840 
841 
EndBlock(RpoNumber rpo)842 void InstructionSequence::EndBlock(RpoNumber rpo) {
843   int end = static_cast<int>(instructions_.size());
844   DCHECK_EQ(current_block_->rpo_number(), rpo);
845   if (current_block_->code_start() == end) {  // Empty block.  Insert a nop.
846     AddInstruction(Instruction::New(zone(), kArchNop));
847     end = static_cast<int>(instructions_.size());
848   }
849   DCHECK(current_block_->code_start() >= 0 &&
850          current_block_->code_start() < end);
851   current_block_->set_code_end(end);
852   current_block_ = nullptr;
853 }
854 
855 
AddInstruction(Instruction * instr)856 int InstructionSequence::AddInstruction(Instruction* instr) {
857   DCHECK_NOT_NULL(current_block_);
858   int index = static_cast<int>(instructions_.size());
859   instr->set_block(current_block_);
860   instructions_.push_back(instr);
861   if (instr->NeedsReferenceMap()) {
862     DCHECK(instr->reference_map() == nullptr);
863     ReferenceMap* reference_map = new (zone()) ReferenceMap(zone());
864     reference_map->set_instruction_position(index);
865     instr->set_reference_map(reference_map);
866     reference_maps_.push_back(reference_map);
867   }
868   return index;
869 }
870 
871 
GetInstructionBlock(int instruction_index) const872 InstructionBlock* InstructionSequence::GetInstructionBlock(
873     int instruction_index) const {
874   return instructions()[instruction_index]->block();
875 }
876 
877 
FilterRepresentation(MachineRepresentation rep)878 static MachineRepresentation FilterRepresentation(MachineRepresentation rep) {
879   switch (rep) {
880     case MachineRepresentation::kBit:
881     case MachineRepresentation::kWord8:
882     case MachineRepresentation::kWord16:
883       return InstructionSequence::DefaultRepresentation();
884     case MachineRepresentation::kWord32:
885     case MachineRepresentation::kWord64:
886     case MachineRepresentation::kFloat32:
887     case MachineRepresentation::kFloat64:
888     case MachineRepresentation::kSimd128:
889     case MachineRepresentation::kTaggedSigned:
890     case MachineRepresentation::kTaggedPointer:
891     case MachineRepresentation::kTagged:
892       return rep;
893     case MachineRepresentation::kNone:
894       break;
895   }
896   UNREACHABLE();
897   return MachineRepresentation::kNone;
898 }
899 
900 
GetRepresentation(int virtual_register) const901 MachineRepresentation InstructionSequence::GetRepresentation(
902     int virtual_register) const {
903   DCHECK_LE(0, virtual_register);
904   DCHECK_LT(virtual_register, VirtualRegisterCount());
905   if (virtual_register >= static_cast<int>(representations_.size())) {
906     return DefaultRepresentation();
907   }
908   return representations_[virtual_register];
909 }
910 
911 
MarkAsRepresentation(MachineRepresentation rep,int virtual_register)912 void InstructionSequence::MarkAsRepresentation(MachineRepresentation rep,
913                                                int virtual_register) {
914   DCHECK_LE(0, virtual_register);
915   DCHECK_LT(virtual_register, VirtualRegisterCount());
916   if (virtual_register >= static_cast<int>(representations_.size())) {
917     representations_.resize(VirtualRegisterCount(), DefaultRepresentation());
918   }
919   rep = FilterRepresentation(rep);
920   DCHECK_IMPLIES(representations_[virtual_register] != rep,
921                  representations_[virtual_register] == DefaultRepresentation());
922   representations_[virtual_register] = rep;
923   representation_mask_ |= 1 << static_cast<int>(rep);
924 }
925 
AddDeoptimizationEntry(FrameStateDescriptor * descriptor,DeoptimizeReason reason)926 int InstructionSequence::AddDeoptimizationEntry(
927     FrameStateDescriptor* descriptor, DeoptimizeReason reason) {
928   int deoptimization_id = static_cast<int>(deoptimization_entries_.size());
929   deoptimization_entries_.push_back(DeoptimizationEntry(descriptor, reason));
930   return deoptimization_id;
931 }
932 
GetDeoptimizationEntry(int state_id)933 DeoptimizationEntry const& InstructionSequence::GetDeoptimizationEntry(
934     int state_id) {
935   return deoptimization_entries_[state_id];
936 }
937 
938 
InputRpo(Instruction * instr,size_t index)939 RpoNumber InstructionSequence::InputRpo(Instruction* instr, size_t index) {
940   InstructionOperand* operand = instr->InputAt(index);
941   Constant constant =
942       operand->IsImmediate()
943           ? GetImmediate(ImmediateOperand::cast(operand))
944           : GetConstant(ConstantOperand::cast(operand)->virtual_register());
945   return constant.ToRpoNumber();
946 }
947 
948 
GetSourcePosition(const Instruction * instr,SourcePosition * result) const949 bool InstructionSequence::GetSourcePosition(const Instruction* instr,
950                                             SourcePosition* result) const {
951   auto it = source_positions_.find(instr);
952   if (it == source_positions_.end()) return false;
953   *result = it->second;
954   return true;
955 }
956 
957 
SetSourcePosition(const Instruction * instr,SourcePosition value)958 void InstructionSequence::SetSourcePosition(const Instruction* instr,
959                                             SourcePosition value) {
960   source_positions_.insert(std::make_pair(instr, value));
961 }
962 
Print(const RegisterConfiguration * config) const963 void InstructionSequence::Print(const RegisterConfiguration* config) const {
964   OFStream os(stdout);
965   PrintableInstructionSequence wrapper;
966   wrapper.register_configuration_ = config;
967   wrapper.sequence_ = this;
968   os << wrapper << std::endl;
969 }
970 
Print() const971 void InstructionSequence::Print() const { Print(GetRegConfig()); }
972 
PrintBlock(const RegisterConfiguration * config,int block_id) const973 void InstructionSequence::PrintBlock(const RegisterConfiguration* config,
974                                      int block_id) const {
975   OFStream os(stdout);
976   RpoNumber rpo = RpoNumber::FromInt(block_id);
977   const InstructionBlock* block = InstructionBlockAt(rpo);
978   CHECK(block->rpo_number() == rpo);
979   PrintableInstructionBlock printable_block = {config, block, this};
980   os << printable_block << std::endl;
981 }
982 
PrintBlock(int block_id) const983 void InstructionSequence::PrintBlock(int block_id) const {
984   PrintBlock(GetRegConfig(), block_id);
985 }
986 
987 const RegisterConfiguration*
GetRegisterConfigurationForTesting()988 InstructionSequence::GetRegisterConfigurationForTesting() {
989   return GetRegConfig();
990 }
991 
FrameStateDescriptor(Zone * zone,FrameStateType type,BailoutId bailout_id,OutputFrameStateCombine state_combine,size_t parameters_count,size_t locals_count,size_t stack_count,MaybeHandle<SharedFunctionInfo> shared_info,FrameStateDescriptor * outer_state)992 FrameStateDescriptor::FrameStateDescriptor(
993     Zone* zone, FrameStateType type, BailoutId bailout_id,
994     OutputFrameStateCombine state_combine, size_t parameters_count,
995     size_t locals_count, size_t stack_count,
996     MaybeHandle<SharedFunctionInfo> shared_info,
997     FrameStateDescriptor* outer_state)
998     : type_(type),
999       bailout_id_(bailout_id),
1000       frame_state_combine_(state_combine),
1001       parameters_count_(parameters_count),
1002       locals_count_(locals_count),
1003       stack_count_(stack_count),
1004       values_(zone),
1005       shared_info_(shared_info),
1006       outer_state_(outer_state) {}
1007 
1008 
GetSize(OutputFrameStateCombine combine) const1009 size_t FrameStateDescriptor::GetSize(OutputFrameStateCombine combine) const {
1010   size_t size = 1 + parameters_count() + locals_count() + stack_count() +
1011                 (HasContext() ? 1 : 0);
1012   switch (combine.kind()) {
1013     case OutputFrameStateCombine::kPushOutput:
1014       size += combine.GetPushCount();
1015       break;
1016     case OutputFrameStateCombine::kPokeAt:
1017       break;
1018   }
1019   return size;
1020 }
1021 
1022 
GetTotalSize() const1023 size_t FrameStateDescriptor::GetTotalSize() const {
1024   size_t total_size = 0;
1025   for (const FrameStateDescriptor* iter = this; iter != nullptr;
1026        iter = iter->outer_state_) {
1027     total_size += iter->GetSize();
1028   }
1029   return total_size;
1030 }
1031 
1032 
GetFrameCount() const1033 size_t FrameStateDescriptor::GetFrameCount() const {
1034   size_t count = 0;
1035   for (const FrameStateDescriptor* iter = this; iter != nullptr;
1036        iter = iter->outer_state_) {
1037     ++count;
1038   }
1039   return count;
1040 }
1041 
1042 
GetJSFrameCount() const1043 size_t FrameStateDescriptor::GetJSFrameCount() const {
1044   size_t count = 0;
1045   for (const FrameStateDescriptor* iter = this; iter != nullptr;
1046        iter = iter->outer_state_) {
1047     if (FrameStateFunctionInfo::IsJSFunctionType(iter->type_)) {
1048       ++count;
1049     }
1050   }
1051   return count;
1052 }
1053 
1054 
operator <<(std::ostream & os,const RpoNumber & rpo)1055 std::ostream& operator<<(std::ostream& os, const RpoNumber& rpo) {
1056   return os << rpo.ToSize();
1057 }
1058 
1059 
operator <<(std::ostream & os,const PrintableInstructionSequence & printable)1060 std::ostream& operator<<(std::ostream& os,
1061                          const PrintableInstructionSequence& printable) {
1062   const InstructionSequence& code = *printable.sequence_;
1063   for (size_t i = 0; i < code.immediates_.size(); ++i) {
1064     Constant constant = code.immediates_[i];
1065     os << "IMM#" << i << ": " << constant << "\n";
1066   }
1067   int i = 0;
1068   for (ConstantMap::const_iterator it = code.constants_.begin();
1069        it != code.constants_.end(); ++i, ++it) {
1070     os << "CST#" << i << ": v" << it->first << " = " << it->second << "\n";
1071   }
1072   PrintableInstructionBlock printable_block = {
1073       printable.register_configuration_, nullptr, printable.sequence_};
1074   for (int i = 0; i < code.InstructionBlockCount(); i++) {
1075     printable_block.block_ = code.InstructionBlockAt(RpoNumber::FromInt(i));
1076     os << printable_block;
1077   }
1078   return os;
1079 }
1080 
1081 }  // namespace compiler
1082 }  // namespace internal
1083 }  // namespace v8
1084