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