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 
13 namespace v8 {
14 namespace internal {
15 namespace compiler {
16 
17 const RegisterConfiguration* (*GetRegConfig)() =
18     RegisterConfiguration::Turbofan;
19 
CommuteFlagsCondition(FlagsCondition condition)20 FlagsCondition 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 
InterferesWith(const InstructionOperand & other) const70 bool 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 
Print(const RegisterConfiguration * config) const101 void 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 
Print() const109 void InstructionOperand::Print() const { Print(GetRegConfig()); }
110 
operator <<(std::ostream & os,const PrintableInstructionOperand & printable)111 std::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 
Print(const RegisterConfiguration * config) const241 void 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 
Print() const251 void MoveOperands::Print() const { Print(GetRegConfig()); }
252 
operator <<(std::ostream & os,const PrintableMoveOperands & printable)253 std::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 
IsRedundant() const267 bool ParallelMove::IsRedundant() const {
268   for (MoveOperands* move : *this) {
269     if (!move->IsRedundant()) return false;
270   }
271   return true;
272 }
273 
PrepareInsertAfter(MoveOperands * move,ZoneVector<MoveOperands * > * to_eliminate) const274 void 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 
ExplicitOperand(LocationKind kind,MachineRepresentation rep,int index)299 ExplicitOperand::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 
Instruction(InstructionCode opcode)310 Instruction::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 
Instruction(InstructionCode opcode,size_t output_count,InstructionOperand * outputs,size_t input_count,InstructionOperand * inputs,size_t temp_count,InstructionOperand * temps)320 Instruction::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 
AreMovesRedundant() const349 bool 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 
Print(const RegisterConfiguration * config) const359 void 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 
Print() const367 void Instruction::Print() const { Print(GetRegConfig()); }
368 
operator <<(std::ostream & os,const PrintableParallelMove & printable)369 std::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 
RecordReference(const AllocatedOperand & op)384 void 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 
operator <<(std::ostream & os,const ReferenceMap & pm)392 std::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 
operator <<(std::ostream & os,const ArchOpcode & ao)409 std::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 
operator <<(std::ostream & os,const AddressingMode & am)422 std::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 
operator <<(std::ostream & os,const FlagsMode & fm)437 std::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 
operator <<(std::ostream & os,const FlagsCondition & fc)455 std::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 
operator <<(std::ostream & os,const PrintableInstruction & printable)511 std::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 
Constant(int32_t v)558 Constant::Constant(int32_t v) : type_(kInt32), value_(v) {}
559 
Constant(RelocatablePtrConstantInfo info)560 Constant::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 
ToHeapObject() const572 Handle<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 
operator <<(std::ostream & os,const Constant & constant)579 std::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 
PhiInstruction(Zone * zone,int virtual_register,size_t input_count)602 PhiInstruction::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 
SetInput(size_t offset,int virtual_register)610 void PhiInstruction::SetInput(size_t offset, int virtual_register) {
611   DCHECK_EQ(InstructionOperand::kInvalidVirtualRegister, operands_[offset]);
612   operands_[offset] = virtual_register;
613 }
614 
RenameInput(size_t offset,int virtual_register)615 void PhiInstruction::RenameInput(size_t offset, int virtual_register) {
616   DCHECK_NE(InstructionOperand::kInvalidVirtualRegister, operands_[offset]);
617   operands_[offset] = virtual_register;
618 }
619 
InstructionBlock(Zone * zone,RpoNumber rpo_number,RpoNumber loop_header,RpoNumber loop_end,bool deferred,bool handler)620 InstructionBlock::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 
PredecessorIndexOf(RpoNumber rpo_number) const638 size_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 
GetRpo(const BasicBlock * block)648 static RpoNumber GetRpo(const BasicBlock* block) {
649   if (block == nullptr) return RpoNumber::Invalid();
650   return RpoNumber::FromInt(block->rpo_number());
651 }
652 
653 
GetLoopEndRpo(const BasicBlock * block)654 static RpoNumber GetLoopEndRpo(const BasicBlock* block) {
655   if (!block->IsLoopHeader()) return RpoNumber::Invalid();
656   return RpoNumber::FromInt(block->loop_end()->rpo_number());
657 }
658 
659 
InstructionBlockFor(Zone * zone,const BasicBlock * block)660 static 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 
operator <<(std::ostream & os,PrintableInstructionBlock & printable_block)679 std::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 
InstructionBlocksFor(Zone * zone,const Schedule * schedule)731 InstructionBlocks* 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 
ValidateEdgeSplitForm() const747 void 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 
ValidateDeferredBlockExitPaths() const762 void 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 
ValidateDeferredBlockEntryPaths() const773 void 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 
ValidateSSA() const787 void 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 
ComputeAssemblyOrder(InstructionBlocks * blocks)802 void 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 
InstructionSequence(Isolate * isolate,Zone * instruction_zone,InstructionBlocks * instruction_blocks)816 InstructionSequence::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 
NextVirtualRegister()834 int InstructionSequence::NextVirtualRegister() {
835   int virtual_register = next_virtual_register_++;
836   CHECK_NE(virtual_register, InstructionOperand::kInvalidVirtualRegister);
837   return virtual_register;
838 }
839 
840 
GetBlockStart(RpoNumber rpo) const841 Instruction* InstructionSequence::GetBlockStart(RpoNumber rpo) const {
842   const InstructionBlock* block = InstructionBlockAt(rpo);
843   return InstructionAt(block->code_start());
844 }
845 
846 
StartBlock(RpoNumber rpo)847 void 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 
EndBlock(RpoNumber rpo)855 void 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 
AddInstruction(Instruction * instr)869 int 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 
GetInstructionBlock(int instruction_index) const885 InstructionBlock* InstructionSequence::GetInstructionBlock(
886     int instruction_index) const {
887   return instructions()[instruction_index]->block();
888 }
889 
890 
FilterRepresentation(MachineRepresentation rep)891 static 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 
GetRepresentation(int virtual_register) const917 MachineRepresentation 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 
MarkAsRepresentation(MachineRepresentation rep,int virtual_register)928 void 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 
AddDeoptimizationEntry(FrameStateDescriptor * descriptor,DeoptimizeKind kind,DeoptimizeReason reason)942 int 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 
GetDeoptimizationEntry(int state_id)951 DeoptimizationEntry const& InstructionSequence::GetDeoptimizationEntry(
952     int state_id) {
953   return deoptimization_entries_[state_id];
954 }
955 
956 
InputRpo(Instruction * instr,size_t index)957 RpoNumber 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 
GetSourcePosition(const Instruction * instr,SourcePosition * result) const967 bool 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 
SetSourcePosition(const Instruction * instr,SourcePosition value)976 void InstructionSequence::SetSourcePosition(const Instruction* instr,
977                                             SourcePosition value) {
978   source_positions_.insert(std::make_pair(instr, value));
979 }
980 
Print(const RegisterConfiguration * config) const981 void 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 
Print() const989 void InstructionSequence::Print() const { Print(GetRegConfig()); }
990 
PrintBlock(const RegisterConfiguration * config,int block_id) const991 void 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 
PrintBlock(int block_id) const1001 void InstructionSequence::PrintBlock(int block_id) const {
1002   PrintBlock(GetRegConfig(), block_id);
1003 }
1004 
1005 const RegisterConfiguration*
1006     InstructionSequence::registerConfigurationForTesting_ = nullptr;
1007 
1008 const RegisterConfiguration*
RegisterConfigurationForTesting()1009 InstructionSequence::RegisterConfigurationForTesting() {
1010   DCHECK(registerConfigurationForTesting_ != nullptr);
1011   return registerConfigurationForTesting_;
1012 }
1013 
SetRegisterConfigurationForTesting(const RegisterConfiguration * regConfig)1014 void InstructionSequence::SetRegisterConfigurationForTesting(
1015     const RegisterConfiguration* regConfig) {
1016   registerConfigurationForTesting_ = regConfig;
1017   GetRegConfig = InstructionSequence::RegisterConfigurationForTesting;
1018 }
1019 
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)1020 FrameStateDescriptor::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 
GetSize(OutputFrameStateCombine combine) const1037 size_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 
GetTotalSize() const1051 size_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 
GetFrameCount() const1061 size_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 
GetJSFrameCount() const1071 size_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 
operator <<(std::ostream & os,const RpoNumber & rpo)1083 std::ostream& operator<<(std::ostream& os, const RpoNumber& rpo) {
1084   return os << rpo.ToSize();
1085 }
1086 
1087 
operator <<(std::ostream & os,const PrintableInstructionSequence & printable)1088 std::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