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