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 
CommuteFlagsCondition(FlagsCondition condition)16 FlagsCondition CommuteFlagsCondition(FlagsCondition condition) {
17   switch (condition) {
18     case kSignedLessThan:
19       return kSignedGreaterThan;
20     case kSignedGreaterThanOrEqual:
21       return kSignedLessThanOrEqual;
22     case kSignedLessThanOrEqual:
23       return kSignedGreaterThanOrEqual;
24     case kSignedGreaterThan:
25       return kSignedLessThan;
26     case kUnsignedLessThan:
27       return kUnsignedGreaterThan;
28     case kUnsignedGreaterThanOrEqual:
29       return kUnsignedLessThanOrEqual;
30     case kUnsignedLessThanOrEqual:
31       return kUnsignedGreaterThanOrEqual;
32     case kUnsignedGreaterThan:
33       return kUnsignedLessThan;
34     case kFloatLessThanOrUnordered:
35       return kFloatGreaterThanOrUnordered;
36     case kFloatGreaterThanOrEqual:
37       return kFloatLessThanOrEqual;
38     case kFloatLessThanOrEqual:
39       return kFloatGreaterThanOrEqual;
40     case kFloatGreaterThanOrUnordered:
41       return kFloatLessThanOrUnordered;
42     case kFloatLessThan:
43       return kFloatGreaterThan;
44     case kFloatGreaterThanOrEqualOrUnordered:
45       return kFloatLessThanOrEqualOrUnordered;
46     case kFloatLessThanOrEqualOrUnordered:
47       return kFloatGreaterThanOrEqualOrUnordered;
48     case kFloatGreaterThan:
49       return kFloatLessThan;
50     case kEqual:
51     case kNotEqual:
52     case kOverflow:
53     case kNotOverflow:
54     case kUnorderedEqual:
55     case kUnorderedNotEqual:
56       return condition;
57   }
58   UNREACHABLE();
59   return condition;
60 }
61 
62 
Print(const RegisterConfiguration * config) const63 void InstructionOperand::Print(const RegisterConfiguration* config) const {
64   OFStream os(stdout);
65   PrintableInstructionOperand wrapper;
66   wrapper.register_configuration_ = config;
67   wrapper.op_ = *this;
68   os << wrapper << std::endl;
69 }
70 
71 
Print() const72 void InstructionOperand::Print() const {
73   const RegisterConfiguration* config =
74       RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN);
75   Print(config);
76 }
77 
78 
operator <<(std::ostream & os,const PrintableInstructionOperand & printable)79 std::ostream& operator<<(std::ostream& os,
80                          const PrintableInstructionOperand& printable) {
81   const InstructionOperand& op = printable.op_;
82   const RegisterConfiguration* conf = printable.register_configuration_;
83   switch (op.kind()) {
84     case InstructionOperand::UNALLOCATED: {
85       const UnallocatedOperand* unalloc = UnallocatedOperand::cast(&op);
86       os << "v" << unalloc->virtual_register();
87       if (unalloc->basic_policy() == UnallocatedOperand::FIXED_SLOT) {
88         return os << "(=" << unalloc->fixed_slot_index() << "S)";
89       }
90       switch (unalloc->extended_policy()) {
91         case UnallocatedOperand::NONE:
92           return os;
93         case UnallocatedOperand::FIXED_REGISTER:
94           return os << "(="
95                     << conf->GetGeneralRegisterName(
96                            unalloc->fixed_register_index())
97                     << ")";
98         case UnallocatedOperand::FIXED_DOUBLE_REGISTER:
99           return os << "(="
100                     << conf->GetDoubleRegisterName(
101                            unalloc->fixed_register_index())
102                     << ")";
103         case UnallocatedOperand::MUST_HAVE_REGISTER:
104           return os << "(R)";
105         case UnallocatedOperand::MUST_HAVE_SLOT:
106           return os << "(S)";
107         case UnallocatedOperand::SAME_AS_FIRST_INPUT:
108           return os << "(1)";
109         case UnallocatedOperand::ANY:
110           return os << "(-)";
111       }
112     }
113     case InstructionOperand::CONSTANT:
114       return os << "[constant:" << ConstantOperand::cast(op).virtual_register()
115                 << "]";
116     case InstructionOperand::IMMEDIATE: {
117       auto imm = ImmediateOperand::cast(op);
118       switch (imm.type()) {
119         case ImmediateOperand::INLINE:
120           return os << "#" << imm.inline_value();
121         case ImmediateOperand::INDEXED:
122           return os << "[immediate:" << imm.indexed_value() << "]";
123       }
124     }
125     case InstructionOperand::EXPLICIT:
126     case InstructionOperand::ALLOCATED: {
127       auto allocated = LocationOperand::cast(op);
128       if (op.IsStackSlot()) {
129         os << "[stack:" << LocationOperand::cast(op).index();
130       } else if (op.IsDoubleStackSlot()) {
131         os << "[double_stack:" << LocationOperand::cast(op).index();
132       } else if (op.IsRegister()) {
133         os << "[" << LocationOperand::cast(op).GetRegister().ToString() << "|R";
134       } else {
135         DCHECK(op.IsDoubleRegister());
136         os << "[" << LocationOperand::cast(op).GetDoubleRegister().ToString()
137            << "|R";
138       }
139       if (allocated.IsExplicit()) {
140         os << "|E";
141       }
142       switch (allocated.representation()) {
143         case MachineRepresentation::kNone:
144           os << "|-";
145           break;
146         case MachineRepresentation::kBit:
147           os << "|b";
148           break;
149         case MachineRepresentation::kWord8:
150           os << "|w8";
151           break;
152         case MachineRepresentation::kWord16:
153           os << "|w16";
154           break;
155         case MachineRepresentation::kWord32:
156           os << "|w32";
157           break;
158         case MachineRepresentation::kWord64:
159           os << "|w64";
160           break;
161         case MachineRepresentation::kFloat32:
162           os << "|f32";
163           break;
164         case MachineRepresentation::kFloat64:
165           os << "|f64";
166           break;
167         case MachineRepresentation::kTagged:
168           os << "|t";
169           break;
170       }
171       return os << "]";
172     }
173     case InstructionOperand::INVALID:
174       return os << "(x)";
175   }
176   UNREACHABLE();
177   return os;
178 }
179 
180 
Print(const RegisterConfiguration * config) const181 void MoveOperands::Print(const RegisterConfiguration* config) const {
182   OFStream os(stdout);
183   PrintableInstructionOperand wrapper;
184   wrapper.register_configuration_ = config;
185   wrapper.op_ = destination();
186   os << wrapper << " = ";
187   wrapper.op_ = source();
188   os << wrapper << std::endl;
189 }
190 
191 
Print() const192 void MoveOperands::Print() const {
193   const RegisterConfiguration* config =
194       RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN);
195   Print(config);
196 }
197 
198 
operator <<(std::ostream & os,const PrintableMoveOperands & printable)199 std::ostream& operator<<(std::ostream& os,
200                          const PrintableMoveOperands& printable) {
201   const MoveOperands& mo = *printable.move_operands_;
202   PrintableInstructionOperand printable_op = {printable.register_configuration_,
203                                               mo.destination()};
204   os << printable_op;
205   if (!mo.source().Equals(mo.destination())) {
206     printable_op.op_ = mo.source();
207     os << " = " << printable_op;
208   }
209   return os << ";";
210 }
211 
212 
IsRedundant() const213 bool ParallelMove::IsRedundant() const {
214   for (auto move : *this) {
215     if (!move->IsRedundant()) return false;
216   }
217   return true;
218 }
219 
220 
PrepareInsertAfter(MoveOperands * move) const221 MoveOperands* ParallelMove::PrepareInsertAfter(MoveOperands* move) const {
222   MoveOperands* replacement = nullptr;
223   MoveOperands* to_eliminate = nullptr;
224   for (auto curr : *this) {
225     if (curr->IsEliminated()) continue;
226     if (curr->destination().EqualsCanonicalized(move->source())) {
227       DCHECK(!replacement);
228       replacement = curr;
229       if (to_eliminate != nullptr) break;
230     } else if (curr->destination().EqualsCanonicalized(move->destination())) {
231       DCHECK(!to_eliminate);
232       to_eliminate = curr;
233       if (replacement != nullptr) break;
234     }
235   }
236   DCHECK_IMPLIES(replacement == to_eliminate, replacement == nullptr);
237   if (replacement != nullptr) move->set_source(replacement->source());
238   return to_eliminate;
239 }
240 
241 
ExplicitOperand(LocationKind kind,MachineRepresentation rep,int index)242 ExplicitOperand::ExplicitOperand(LocationKind kind, MachineRepresentation rep,
243                                  int index)
244     : LocationOperand(EXPLICIT, kind, rep, index) {
245   DCHECK_IMPLIES(kind == REGISTER && !IsFloatingPoint(rep),
246                  Register::from_code(index).IsAllocatable());
247   DCHECK_IMPLIES(kind == REGISTER && IsFloatingPoint(rep),
248                  DoubleRegister::from_code(index).IsAllocatable());
249 }
250 
251 
Instruction(InstructionCode opcode)252 Instruction::Instruction(InstructionCode opcode)
253     : opcode_(opcode),
254       bit_field_(OutputCountField::encode(0) | InputCountField::encode(0) |
255                  TempCountField::encode(0) | IsCallField::encode(false)),
256       reference_map_(nullptr) {
257   parallel_moves_[0] = nullptr;
258   parallel_moves_[1] = nullptr;
259 }
260 
261 
Instruction(InstructionCode opcode,size_t output_count,InstructionOperand * outputs,size_t input_count,InstructionOperand * inputs,size_t temp_count,InstructionOperand * temps)262 Instruction::Instruction(InstructionCode opcode, size_t output_count,
263                          InstructionOperand* outputs, size_t input_count,
264                          InstructionOperand* inputs, size_t temp_count,
265                          InstructionOperand* temps)
266     : opcode_(opcode),
267       bit_field_(OutputCountField::encode(output_count) |
268                  InputCountField::encode(input_count) |
269                  TempCountField::encode(temp_count) |
270                  IsCallField::encode(false)),
271       reference_map_(nullptr) {
272   parallel_moves_[0] = nullptr;
273   parallel_moves_[1] = nullptr;
274   size_t offset = 0;
275   for (size_t i = 0; i < output_count; ++i) {
276     DCHECK(!outputs[i].IsInvalid());
277     operands_[offset++] = outputs[i];
278   }
279   for (size_t i = 0; i < input_count; ++i) {
280     DCHECK(!inputs[i].IsInvalid());
281     operands_[offset++] = inputs[i];
282   }
283   for (size_t i = 0; i < temp_count; ++i) {
284     DCHECK(!temps[i].IsInvalid());
285     operands_[offset++] = temps[i];
286   }
287 }
288 
289 
AreMovesRedundant() const290 bool Instruction::AreMovesRedundant() const {
291   for (int i = Instruction::FIRST_GAP_POSITION;
292        i <= Instruction::LAST_GAP_POSITION; i++) {
293     if (parallel_moves_[i] != nullptr && !parallel_moves_[i]->IsRedundant()) {
294       return false;
295     }
296   }
297   return true;
298 }
299 
300 
Print(const RegisterConfiguration * config) const301 void Instruction::Print(const RegisterConfiguration* config) const {
302   OFStream os(stdout);
303   PrintableInstruction wrapper;
304   wrapper.instr_ = this;
305   wrapper.register_configuration_ = config;
306   os << wrapper << std::endl;
307 }
308 
309 
Print() const310 void Instruction::Print() const {
311   const RegisterConfiguration* config =
312       RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN);
313   Print(config);
314 }
315 
316 
operator <<(std::ostream & os,const PrintableParallelMove & printable)317 std::ostream& operator<<(std::ostream& os,
318                          const PrintableParallelMove& printable) {
319   const ParallelMove& pm = *printable.parallel_move_;
320   bool first = true;
321   for (auto move : pm) {
322     if (move->IsEliminated()) continue;
323     if (!first) os << " ";
324     first = false;
325     PrintableMoveOperands pmo = {printable.register_configuration_, move};
326     os << pmo;
327   }
328   return os;
329 }
330 
331 
RecordReference(const AllocatedOperand & op)332 void ReferenceMap::RecordReference(const AllocatedOperand& op) {
333   // Do not record arguments as pointers.
334   if (op.IsStackSlot() && LocationOperand::cast(op).index() < 0) return;
335   DCHECK(!op.IsDoubleRegister() && !op.IsDoubleStackSlot());
336   reference_operands_.push_back(op);
337 }
338 
339 
operator <<(std::ostream & os,const ReferenceMap & pm)340 std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm) {
341   os << "{";
342   bool first = true;
343   PrintableInstructionOperand poi = {
344       RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN),
345       InstructionOperand()};
346   for (auto& op : pm.reference_operands_) {
347     if (!first) {
348       os << ";";
349     } else {
350       first = false;
351     }
352     poi.op_ = op;
353     os << poi;
354   }
355   return os << "}";
356 }
357 
358 
operator <<(std::ostream & os,const ArchOpcode & ao)359 std::ostream& operator<<(std::ostream& os, const ArchOpcode& ao) {
360   switch (ao) {
361 #define CASE(Name) \
362   case k##Name:    \
363     return os << #Name;
364     ARCH_OPCODE_LIST(CASE)
365 #undef CASE
366   }
367   UNREACHABLE();
368   return os;
369 }
370 
371 
operator <<(std::ostream & os,const AddressingMode & am)372 std::ostream& operator<<(std::ostream& os, const AddressingMode& am) {
373   switch (am) {
374     case kMode_None:
375       return os;
376 #define CASE(Name)   \
377   case kMode_##Name: \
378     return os << #Name;
379       TARGET_ADDRESSING_MODE_LIST(CASE)
380 #undef CASE
381   }
382   UNREACHABLE();
383   return os;
384 }
385 
386 
operator <<(std::ostream & os,const FlagsMode & fm)387 std::ostream& operator<<(std::ostream& os, const FlagsMode& fm) {
388   switch (fm) {
389     case kFlags_none:
390       return os;
391     case kFlags_branch:
392       return os << "branch";
393     case kFlags_set:
394       return os << "set";
395   }
396   UNREACHABLE();
397   return os;
398 }
399 
400 
operator <<(std::ostream & os,const FlagsCondition & fc)401 std::ostream& operator<<(std::ostream& os, const FlagsCondition& fc) {
402   switch (fc) {
403     case kEqual:
404       return os << "equal";
405     case kNotEqual:
406       return os << "not equal";
407     case kSignedLessThan:
408       return os << "signed less than";
409     case kSignedGreaterThanOrEqual:
410       return os << "signed greater than or equal";
411     case kSignedLessThanOrEqual:
412       return os << "signed less than or equal";
413     case kSignedGreaterThan:
414       return os << "signed greater than";
415     case kUnsignedLessThan:
416       return os << "unsigned less than";
417     case kUnsignedGreaterThanOrEqual:
418       return os << "unsigned greater than or equal";
419     case kUnsignedLessThanOrEqual:
420       return os << "unsigned less than or equal";
421     case kUnsignedGreaterThan:
422       return os << "unsigned greater than";
423     case kFloatLessThanOrUnordered:
424       return os << "less than or unordered (FP)";
425     case kFloatGreaterThanOrEqual:
426       return os << "greater than or equal (FP)";
427     case kFloatLessThanOrEqual:
428       return os << "less than or equal (FP)";
429     case kFloatGreaterThanOrUnordered:
430       return os << "greater than or unordered (FP)";
431     case kFloatLessThan:
432       return os << "less than (FP)";
433     case kFloatGreaterThanOrEqualOrUnordered:
434       return os << "greater than, equal or unordered (FP)";
435     case kFloatLessThanOrEqualOrUnordered:
436       return os << "less than, equal or unordered (FP)";
437     case kFloatGreaterThan:
438       return os << "greater than (FP)";
439     case kUnorderedEqual:
440       return os << "unordered equal";
441     case kUnorderedNotEqual:
442       return os << "unordered not equal";
443     case kOverflow:
444       return os << "overflow";
445     case kNotOverflow:
446       return os << "not overflow";
447   }
448   UNREACHABLE();
449   return os;
450 }
451 
452 
operator <<(std::ostream & os,const PrintableInstruction & printable)453 std::ostream& operator<<(std::ostream& os,
454                          const PrintableInstruction& printable) {
455   const Instruction& instr = *printable.instr_;
456   PrintableInstructionOperand printable_op = {printable.register_configuration_,
457                                               InstructionOperand()};
458   os << "gap ";
459   for (int i = Instruction::FIRST_GAP_POSITION;
460        i <= Instruction::LAST_GAP_POSITION; i++) {
461     os << "(";
462     if (instr.parallel_moves()[i] != nullptr) {
463       PrintableParallelMove ppm = {printable.register_configuration_,
464                                    instr.parallel_moves()[i]};
465       os << ppm;
466     }
467     os << ") ";
468   }
469   os << "\n          ";
470 
471   if (instr.OutputCount() > 1) os << "(";
472   for (size_t i = 0; i < instr.OutputCount(); i++) {
473     if (i > 0) os << ", ";
474     printable_op.op_ = *instr.OutputAt(i);
475     os << printable_op;
476   }
477 
478   if (instr.OutputCount() > 1) os << ") = ";
479   if (instr.OutputCount() == 1) os << " = ";
480 
481   os << ArchOpcodeField::decode(instr.opcode());
482   AddressingMode am = AddressingModeField::decode(instr.opcode());
483   if (am != kMode_None) {
484     os << " : " << AddressingModeField::decode(instr.opcode());
485   }
486   FlagsMode fm = FlagsModeField::decode(instr.opcode());
487   if (fm != kFlags_none) {
488     os << " && " << fm << " if " << FlagsConditionField::decode(instr.opcode());
489   }
490   if (instr.InputCount() > 0) {
491     for (size_t i = 0; i < instr.InputCount(); i++) {
492       printable_op.op_ = *instr.InputAt(i);
493       os << " " << printable_op;
494     }
495   }
496   return os;
497 }
498 
499 
Constant(int32_t v)500 Constant::Constant(int32_t v) : type_(kInt32), value_(v) {}
501 
502 
operator <<(std::ostream & os,const Constant & constant)503 std::ostream& operator<<(std::ostream& os, const Constant& constant) {
504   switch (constant.type()) {
505     case Constant::kInt32:
506       return os << constant.ToInt32();
507     case Constant::kInt64:
508       return os << constant.ToInt64() << "l";
509     case Constant::kFloat32:
510       return os << constant.ToFloat32() << "f";
511     case Constant::kFloat64:
512       return os << constant.ToFloat64();
513     case Constant::kExternalReference:
514       return os << static_cast<const void*>(
515                        constant.ToExternalReference().address());
516     case Constant::kHeapObject:
517       return os << Brief(*constant.ToHeapObject());
518     case Constant::kRpoNumber:
519       return os << "RPO" << constant.ToRpoNumber().ToInt();
520   }
521   UNREACHABLE();
522   return os;
523 }
524 
525 
PhiInstruction(Zone * zone,int virtual_register,size_t input_count)526 PhiInstruction::PhiInstruction(Zone* zone, int virtual_register,
527                                size_t input_count)
528     : virtual_register_(virtual_register),
529       output_(UnallocatedOperand(UnallocatedOperand::NONE, virtual_register)),
530       operands_(input_count, InstructionOperand::kInvalidVirtualRegister,
531                 zone) {}
532 
533 
SetInput(size_t offset,int virtual_register)534 void PhiInstruction::SetInput(size_t offset, int virtual_register) {
535   DCHECK_EQ(InstructionOperand::kInvalidVirtualRegister, operands_[offset]);
536   operands_[offset] = virtual_register;
537 }
538 
539 
InstructionBlock(Zone * zone,RpoNumber rpo_number,RpoNumber loop_header,RpoNumber loop_end,bool deferred,bool handler)540 InstructionBlock::InstructionBlock(Zone* zone, RpoNumber rpo_number,
541                                    RpoNumber loop_header, RpoNumber loop_end,
542                                    bool deferred, bool handler)
543     : successors_(zone),
544       predecessors_(zone),
545       phis_(zone),
546       ao_number_(rpo_number),
547       rpo_number_(rpo_number),
548       loop_header_(loop_header),
549       loop_end_(loop_end),
550       code_start_(-1),
551       code_end_(-1),
552       deferred_(deferred),
553       handler_(handler),
554       needs_frame_(false),
555       must_construct_frame_(false),
556       must_deconstruct_frame_(false),
557       last_deferred_(RpoNumber::Invalid()) {}
558 
559 
PredecessorIndexOf(RpoNumber rpo_number) const560 size_t InstructionBlock::PredecessorIndexOf(RpoNumber rpo_number) const {
561   size_t j = 0;
562   for (InstructionBlock::Predecessors::const_iterator i = predecessors_.begin();
563        i != predecessors_.end(); ++i, ++j) {
564     if (*i == rpo_number) break;
565   }
566   return j;
567 }
568 
569 
GetRpo(const BasicBlock * block)570 static RpoNumber GetRpo(const BasicBlock* block) {
571   if (block == nullptr) return RpoNumber::Invalid();
572   return RpoNumber::FromInt(block->rpo_number());
573 }
574 
575 
GetLoopEndRpo(const BasicBlock * block)576 static RpoNumber GetLoopEndRpo(const BasicBlock* block) {
577   if (!block->IsLoopHeader()) return RpoNumber::Invalid();
578   return RpoNumber::FromInt(block->loop_end()->rpo_number());
579 }
580 
581 
InstructionBlockFor(Zone * zone,const BasicBlock * block)582 static InstructionBlock* InstructionBlockFor(Zone* zone,
583                                              const BasicBlock* block) {
584   bool is_handler =
585       !block->empty() && block->front()->opcode() == IrOpcode::kIfException;
586   InstructionBlock* instr_block = new (zone)
587       InstructionBlock(zone, GetRpo(block), GetRpo(block->loop_header()),
588                        GetLoopEndRpo(block), block->deferred(), is_handler);
589   // Map successors and precessors
590   instr_block->successors().reserve(block->SuccessorCount());
591   for (BasicBlock* successor : block->successors()) {
592     instr_block->successors().push_back(GetRpo(successor));
593   }
594   instr_block->predecessors().reserve(block->PredecessorCount());
595   for (BasicBlock* predecessor : block->predecessors()) {
596     instr_block->predecessors().push_back(GetRpo(predecessor));
597   }
598   return instr_block;
599 }
600 
601 
InstructionBlocksFor(Zone * zone,const Schedule * schedule)602 InstructionBlocks* InstructionSequence::InstructionBlocksFor(
603     Zone* zone, const Schedule* schedule) {
604   InstructionBlocks* blocks = zone->NewArray<InstructionBlocks>(1);
605   new (blocks) InstructionBlocks(
606       static_cast<int>(schedule->rpo_order()->size()), nullptr, zone);
607   size_t rpo_number = 0;
608   for (BasicBlockVector::const_iterator it = schedule->rpo_order()->begin();
609        it != schedule->rpo_order()->end(); ++it, ++rpo_number) {
610     DCHECK(!(*blocks)[rpo_number]);
611     DCHECK(GetRpo(*it).ToSize() == rpo_number);
612     (*blocks)[rpo_number] = InstructionBlockFor(zone, *it);
613   }
614   ComputeAssemblyOrder(blocks);
615   return blocks;
616 }
617 
618 
ComputeAssemblyOrder(InstructionBlocks * blocks)619 void InstructionSequence::ComputeAssemblyOrder(InstructionBlocks* blocks) {
620   int ao = 0;
621   for (auto const block : *blocks) {
622     if (!block->IsDeferred()) {
623       block->set_ao_number(RpoNumber::FromInt(ao++));
624     }
625   }
626   for (auto const block : *blocks) {
627     if (block->IsDeferred()) {
628       block->set_ao_number(RpoNumber::FromInt(ao++));
629     }
630   }
631 }
632 
633 
InstructionSequence(Isolate * isolate,Zone * instruction_zone,InstructionBlocks * instruction_blocks)634 InstructionSequence::InstructionSequence(Isolate* isolate,
635                                          Zone* instruction_zone,
636                                          InstructionBlocks* instruction_blocks)
637     : isolate_(isolate),
638       zone_(instruction_zone),
639       instruction_blocks_(instruction_blocks),
640       source_positions_(zone()),
641       block_starts_(zone()),
642       constants_(ConstantMap::key_compare(),
643                  ConstantMap::allocator_type(zone())),
644       immediates_(zone()),
645       instructions_(zone()),
646       next_virtual_register_(0),
647       reference_maps_(zone()),
648       representations_(zone()),
649       deoptimization_entries_(zone()) {
650   block_starts_.reserve(instruction_blocks_->size());
651 }
652 
653 
NextVirtualRegister()654 int InstructionSequence::NextVirtualRegister() {
655   int virtual_register = next_virtual_register_++;
656   CHECK_NE(virtual_register, InstructionOperand::kInvalidVirtualRegister);
657   return virtual_register;
658 }
659 
660 
GetBlockStart(RpoNumber rpo) const661 Instruction* InstructionSequence::GetBlockStart(RpoNumber rpo) const {
662   const InstructionBlock* block = InstructionBlockAt(rpo);
663   return InstructionAt(block->code_start());
664 }
665 
666 
StartBlock(RpoNumber rpo)667 void InstructionSequence::StartBlock(RpoNumber rpo) {
668   DCHECK(block_starts_.size() == rpo.ToSize());
669   InstructionBlock* block = InstructionBlockAt(rpo);
670   int code_start = static_cast<int>(instructions_.size());
671   block->set_code_start(code_start);
672   block_starts_.push_back(code_start);
673 }
674 
675 
EndBlock(RpoNumber rpo)676 void InstructionSequence::EndBlock(RpoNumber rpo) {
677   int end = static_cast<int>(instructions_.size());
678   InstructionBlock* block = InstructionBlockAt(rpo);
679   if (block->code_start() == end) {  // Empty block.  Insert a nop.
680     AddInstruction(Instruction::New(zone(), kArchNop));
681     end = static_cast<int>(instructions_.size());
682   }
683   DCHECK(block->code_start() >= 0 && block->code_start() < end);
684   block->set_code_end(end);
685 }
686 
687 
AddInstruction(Instruction * instr)688 int InstructionSequence::AddInstruction(Instruction* instr) {
689   int index = static_cast<int>(instructions_.size());
690   instructions_.push_back(instr);
691   if (instr->NeedsReferenceMap()) {
692     DCHECK(instr->reference_map() == nullptr);
693     ReferenceMap* reference_map = new (zone()) ReferenceMap(zone());
694     reference_map->set_instruction_position(index);
695     instr->set_reference_map(reference_map);
696     reference_maps_.push_back(reference_map);
697   }
698   return index;
699 }
700 
701 
GetInstructionBlock(int instruction_index) const702 InstructionBlock* InstructionSequence::GetInstructionBlock(
703     int instruction_index) const {
704   DCHECK(instruction_blocks_->size() == block_starts_.size());
705   auto begin = block_starts_.begin();
706   auto end = std::lower_bound(begin, block_starts_.end(), instruction_index);
707   // Post condition of std::lower_bound:
708   DCHECK(end == block_starts_.end() || *end >= instruction_index);
709   if (end == block_starts_.end() || *end > instruction_index) --end;
710   DCHECK(*end <= instruction_index);
711   size_t index = std::distance(begin, end);
712   auto block = instruction_blocks_->at(index);
713   DCHECK(block->code_start() <= instruction_index &&
714          instruction_index < block->code_end());
715   return block;
716 }
717 
718 
FilterRepresentation(MachineRepresentation rep)719 static MachineRepresentation FilterRepresentation(MachineRepresentation rep) {
720   switch (rep) {
721     case MachineRepresentation::kBit:
722     case MachineRepresentation::kWord8:
723     case MachineRepresentation::kWord16:
724       return InstructionSequence::DefaultRepresentation();
725     case MachineRepresentation::kWord32:
726     case MachineRepresentation::kWord64:
727     case MachineRepresentation::kFloat32:
728     case MachineRepresentation::kFloat64:
729     case MachineRepresentation::kTagged:
730       return rep;
731     case MachineRepresentation::kNone:
732       break;
733   }
734   UNREACHABLE();
735   return MachineRepresentation::kNone;
736 }
737 
738 
GetRepresentation(int virtual_register) const739 MachineRepresentation InstructionSequence::GetRepresentation(
740     int virtual_register) const {
741   DCHECK_LE(0, virtual_register);
742   DCHECK_LT(virtual_register, VirtualRegisterCount());
743   if (virtual_register >= static_cast<int>(representations_.size())) {
744     return DefaultRepresentation();
745   }
746   return representations_[virtual_register];
747 }
748 
749 
MarkAsRepresentation(MachineRepresentation rep,int virtual_register)750 void InstructionSequence::MarkAsRepresentation(MachineRepresentation rep,
751                                                int virtual_register) {
752   DCHECK_LE(0, virtual_register);
753   DCHECK_LT(virtual_register, VirtualRegisterCount());
754   if (virtual_register >= static_cast<int>(representations_.size())) {
755     representations_.resize(VirtualRegisterCount(), DefaultRepresentation());
756   }
757   rep = FilterRepresentation(rep);
758   DCHECK_IMPLIES(representations_[virtual_register] != rep,
759                  representations_[virtual_register] == DefaultRepresentation());
760   representations_[virtual_register] = rep;
761 }
762 
763 
AddFrameStateDescriptor(FrameStateDescriptor * descriptor)764 InstructionSequence::StateId InstructionSequence::AddFrameStateDescriptor(
765     FrameStateDescriptor* descriptor) {
766   int deoptimization_id = static_cast<int>(deoptimization_entries_.size());
767   deoptimization_entries_.push_back(descriptor);
768   return StateId::FromInt(deoptimization_id);
769 }
770 
GetFrameStateDescriptor(InstructionSequence::StateId state_id)771 FrameStateDescriptor* InstructionSequence::GetFrameStateDescriptor(
772     InstructionSequence::StateId state_id) {
773   return deoptimization_entries_[state_id.ToInt()];
774 }
775 
776 
GetFrameStateDescriptorCount()777 int InstructionSequence::GetFrameStateDescriptorCount() {
778   return static_cast<int>(deoptimization_entries_.size());
779 }
780 
781 
InputRpo(Instruction * instr,size_t index)782 RpoNumber InstructionSequence::InputRpo(Instruction* instr, size_t index) {
783   InstructionOperand* operand = instr->InputAt(index);
784   Constant constant =
785       operand->IsImmediate()
786           ? GetImmediate(ImmediateOperand::cast(operand))
787           : GetConstant(ConstantOperand::cast(operand)->virtual_register());
788   return constant.ToRpoNumber();
789 }
790 
791 
GetSourcePosition(const Instruction * instr,SourcePosition * result) const792 bool InstructionSequence::GetSourcePosition(const Instruction* instr,
793                                             SourcePosition* result) const {
794   auto it = source_positions_.find(instr);
795   if (it == source_positions_.end()) return false;
796   *result = it->second;
797   return true;
798 }
799 
800 
SetSourcePosition(const Instruction * instr,SourcePosition value)801 void InstructionSequence::SetSourcePosition(const Instruction* instr,
802                                             SourcePosition value) {
803   source_positions_.insert(std::make_pair(instr, value));
804 }
805 
806 
Print(const RegisterConfiguration * config) const807 void InstructionSequence::Print(const RegisterConfiguration* config) const {
808   OFStream os(stdout);
809   PrintableInstructionSequence wrapper;
810   wrapper.register_configuration_ = config;
811   wrapper.sequence_ = this;
812   os << wrapper << std::endl;
813 }
814 
815 
Print() const816 void InstructionSequence::Print() const {
817   const RegisterConfiguration* config =
818       RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN);
819   Print(config);
820 }
821 
822 
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)823 FrameStateDescriptor::FrameStateDescriptor(
824     Zone* zone, FrameStateType type, BailoutId bailout_id,
825     OutputFrameStateCombine state_combine, size_t parameters_count,
826     size_t locals_count, size_t stack_count,
827     MaybeHandle<SharedFunctionInfo> shared_info,
828     FrameStateDescriptor* outer_state)
829     : type_(type),
830       bailout_id_(bailout_id),
831       frame_state_combine_(state_combine),
832       parameters_count_(parameters_count),
833       locals_count_(locals_count),
834       stack_count_(stack_count),
835       values_(zone),
836       shared_info_(shared_info),
837       outer_state_(outer_state) {}
838 
839 
GetSize(OutputFrameStateCombine combine) const840 size_t FrameStateDescriptor::GetSize(OutputFrameStateCombine combine) const {
841   size_t size = 1 + parameters_count() + locals_count() + stack_count() +
842                 (HasContext() ? 1 : 0);
843   switch (combine.kind()) {
844     case OutputFrameStateCombine::kPushOutput:
845       size += combine.GetPushCount();
846       break;
847     case OutputFrameStateCombine::kPokeAt:
848       break;
849   }
850   return size;
851 }
852 
853 
GetTotalSize() const854 size_t FrameStateDescriptor::GetTotalSize() const {
855   size_t total_size = 0;
856   for (const FrameStateDescriptor* iter = this; iter != nullptr;
857        iter = iter->outer_state_) {
858     total_size += iter->GetSize();
859   }
860   return total_size;
861 }
862 
863 
GetFrameCount() const864 size_t FrameStateDescriptor::GetFrameCount() const {
865   size_t count = 0;
866   for (const FrameStateDescriptor* iter = this; iter != nullptr;
867        iter = iter->outer_state_) {
868     ++count;
869   }
870   return count;
871 }
872 
873 
GetJSFrameCount() const874 size_t FrameStateDescriptor::GetJSFrameCount() const {
875   size_t count = 0;
876   for (const FrameStateDescriptor* iter = this; iter != nullptr;
877        iter = iter->outer_state_) {
878     if (FrameStateFunctionInfo::IsJSFunctionType(iter->type_)) {
879       ++count;
880     }
881   }
882   return count;
883 }
884 
885 
operator <<(std::ostream & os,const RpoNumber & rpo)886 std::ostream& operator<<(std::ostream& os, const RpoNumber& rpo) {
887   return os << rpo.ToSize();
888 }
889 
890 
operator <<(std::ostream & os,const PrintableInstructionSequence & printable)891 std::ostream& operator<<(std::ostream& os,
892                          const PrintableInstructionSequence& printable) {
893   const InstructionSequence& code = *printable.sequence_;
894   for (size_t i = 0; i < code.immediates_.size(); ++i) {
895     Constant constant = code.immediates_[i];
896     os << "IMM#" << i << ": " << constant << "\n";
897   }
898   int i = 0;
899   for (ConstantMap::const_iterator it = code.constants_.begin();
900        it != code.constants_.end(); ++i, ++it) {
901     os << "CST#" << i << ": v" << it->first << " = " << it->second << "\n";
902   }
903   for (int i = 0; i < code.InstructionBlockCount(); i++) {
904     RpoNumber rpo = RpoNumber::FromInt(i);
905     const InstructionBlock* block = code.InstructionBlockAt(rpo);
906     CHECK(block->rpo_number() == rpo);
907 
908     os << "B" << block->rpo_number();
909     os << ": AO#" << block->ao_number();
910     if (block->IsDeferred()) os << " (deferred)";
911     if (!block->needs_frame()) os << " (no frame)";
912     if (block->must_construct_frame()) os << " (construct frame)";
913     if (block->must_deconstruct_frame()) os << " (deconstruct frame)";
914     if (block->IsLoopHeader()) {
915       os << " loop blocks: [" << block->rpo_number() << ", "
916          << block->loop_end() << ")";
917     }
918     os << "  instructions: [" << block->code_start() << ", "
919        << block->code_end() << ")\n  predecessors:";
920 
921     for (auto pred : block->predecessors()) {
922       os << " B" << pred.ToInt();
923     }
924     os << "\n";
925 
926     for (auto phi : block->phis()) {
927       PrintableInstructionOperand printable_op = {
928           printable.register_configuration_, phi->output()};
929       os << "     phi: " << printable_op << " =";
930       for (auto input : phi->operands()) {
931         os << " v" << input;
932       }
933       os << "\n";
934     }
935 
936     ScopedVector<char> buf(32);
937     PrintableInstruction printable_instr;
938     printable_instr.register_configuration_ = printable.register_configuration_;
939     for (int j = block->first_instruction_index();
940          j <= block->last_instruction_index(); j++) {
941       // TODO(svenpanne) Add some basic formatting to our streams.
942       SNPrintF(buf, "%5d", j);
943       printable_instr.instr_ = code.InstructionAt(j);
944       os << "   " << buf.start() << ": " << printable_instr << "\n";
945     }
946 
947     for (auto succ : block->successors()) {
948       os << " B" << succ.ToInt();
949     }
950     os << "\n";
951   }
952   return os;
953 }
954 
955 }  // namespace compiler
956 }  // namespace internal
957 }  // namespace v8
958