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