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