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 1100173 : FlagsCondition CommuteFlagsCondition(FlagsCondition condition) {
23 1100173 : switch (condition) {
24 : case kSignedLessThan:
25 : return kSignedGreaterThan;
26 : case kSignedGreaterThanOrEqual:
27 555 : return kSignedLessThanOrEqual;
28 : case kSignedLessThanOrEqual:
29 9728 : return kSignedGreaterThanOrEqual;
30 : case kSignedGreaterThan:
31 1024 : return kSignedLessThan;
32 : case kUnsignedLessThan:
33 917864 : return kUnsignedGreaterThan;
34 : case kUnsignedGreaterThanOrEqual:
35 15423 : return kUnsignedLessThanOrEqual;
36 : case kUnsignedLessThanOrEqual:
37 71470 : return kUnsignedGreaterThanOrEqual;
38 : case kUnsignedGreaterThan:
39 1377 : 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 700 : return condition;
67 : }
68 0 : UNREACHABLE();
69 : }
70 :
71 54480193 : 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 557 : std::ostream& operator<<(std::ostream& os, const InstructionOperand& op) {
127 557 : switch (op.kind()) {
128 : case InstructionOperand::UNALLOCATED: {
129 : const UnallocatedOperand* unalloc = UnallocatedOperand::cast(&op);
130 180 : os << "v" << unalloc->virtual_register();
131 180 : if (unalloc->basic_policy() == UnallocatedOperand::FIXED_SLOT) {
132 3 : return os << "(=" << unalloc->fixed_slot_index() << "S)";
133 : }
134 177 : switch (unalloc->extended_policy()) {
135 : case UnallocatedOperand::NONE:
136 : return os;
137 : case UnallocatedOperand::FIXED_REGISTER:
138 6 : return os << "(="
139 : << Register::from_code(unalloc->fixed_register_index())
140 6 : << ")";
141 : case UnallocatedOperand::FIXED_FP_REGISTER:
142 0 : 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 15 : return os << "(1)";
152 : case UnallocatedOperand::REGISTER_OR_SLOT:
153 59 : return os << "(-)";
154 : case UnallocatedOperand::REGISTER_OR_SLOT_OR_CONSTANT:
155 0 : return os << "(*)";
156 : }
157 : }
158 : case InstructionOperand::CONSTANT:
159 16 : return os << "[constant:" << ConstantOperand::cast(op).virtual_register()
160 16 : << "]";
161 : case InstructionOperand::IMMEDIATE: {
162 : ImmediateOperand imm = ImmediateOperand::cast(op);
163 152 : switch (imm.type()) {
164 : case ImmediateOperand::INLINE:
165 62 : return os << "#" << imm.inline_value();
166 : case ImmediateOperand::INDEXED:
167 90 : return os << "[immediate:" << imm.indexed_value() << "]";
168 : }
169 : }
170 : case InstructionOperand::EXPLICIT:
171 : case InstructionOperand::ALLOCATED: {
172 : LocationOperand allocated = LocationOperand::cast(op);
173 209 : if (op.IsStackSlot()) {
174 40 : os << "[stack:" << allocated.index();
175 169 : } else if (op.IsFPStackSlot()) {
176 3 : os << "[fp_stack:" << allocated.index();
177 166 : } else if (op.IsRegister()) {
178 : const char* name =
179 : allocated.register_code() < Register::kNumRegisters
180 : ? RegisterName(Register::from_code(allocated.register_code()))
181 149 : : Register::GetSpecialRegisterName(allocated.register_code());
182 149 : os << "[" << name << "|R";
183 17 : } else if (op.IsDoubleRegister()) {
184 17 : os << "[" << DoubleRegister::from_code(allocated.register_code())
185 17 : << "|R";
186 0 : } else if (op.IsFloatRegister()) {
187 0 : os << "[" << FloatRegister::from_code(allocated.register_code())
188 0 : << "|R";
189 : } else {
190 : DCHECK(op.IsSimd128Register());
191 0 : os << "[" << Simd128Register::from_code(allocated.register_code())
192 0 : << "|R";
193 : }
194 209 : if (allocated.IsExplicit()) {
195 0 : os << "|E";
196 : }
197 209 : 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 24 : os << "|w32";
212 24 : break;
213 : case MachineRepresentation::kWord64:
214 44 : os << "|w64";
215 44 : break;
216 : case MachineRepresentation::kFloat32:
217 0 : os << "|f32";
218 0 : break;
219 : case MachineRepresentation::kFloat64:
220 20 : os << "|f64";
221 20 : 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 121 : os << "|t";
233 121 : break;
234 : }
235 209 : return os << "]";
236 : }
237 : case InstructionOperand::INVALID:
238 0 : return os << "(x)";
239 : }
240 0 : UNREACHABLE();
241 : }
242 :
243 0 : void MoveOperands::Print() const {
244 0 : StdoutStream{} << destination() << " = " << source() << std::endl;
245 0 : }
246 :
247 71 : std::ostream& operator<<(std::ostream& os, const MoveOperands& mo) {
248 71 : os << mo.destination();
249 71 : if (!mo.source().Equals(mo.destination())) {
250 71 : os << " = " << mo.source();
251 : }
252 71 : return os << ";";
253 : }
254 :
255 23857105 : bool ParallelMove::IsRedundant() const {
256 62174896 : for (MoveOperands* move : *this) {
257 21404110 : if (!move->IsRedundant()) return false;
258 : }
259 : return true;
260 : }
261 :
262 13215519 : void ParallelMove::PrepareInsertAfter(
263 : MoveOperands* move, ZoneVector<MoveOperands*>* to_eliminate) const {
264 : bool no_aliasing =
265 : kSimpleFPAliasing || !move->destination().IsFPLocationOperand();
266 : MoveOperands* replacement = nullptr;
267 : MoveOperands* eliminated = nullptr;
268 46780676 : for (MoveOperands* curr : *this) {
269 20364016 : if (curr->IsEliminated()) continue;
270 40163646 : if (curr->destination().EqualsCanonicalized(move->source())) {
271 : // We must replace move's source with curr's destination in order to
272 : // insert it into this ParallelMove.
273 : DCHECK(!replacement);
274 : replacement = curr;
275 1355338 : if (no_aliasing && eliminated != nullptr) break;
276 37452995 : } else if (curr->destination().InterferesWith(move->destination())) {
277 : // We can eliminate curr, since move overwrites at least a part of its
278 : // destination, implying its value is no longer live.
279 : eliminated = curr;
280 207445 : to_eliminate->push_back(curr);
281 207445 : if (no_aliasing && replacement != nullptr) break;
282 : }
283 : }
284 13215544 : if (replacement != nullptr) move->set_source(replacement->source());
285 13215544 : }
286 :
287 712158 : ExplicitOperand::ExplicitOperand(LocationKind kind, MachineRepresentation rep,
288 : int index)
289 : : LocationOperand(EXPLICIT, kind, rep, index) {
290 : DCHECK_IMPLIES(kind == REGISTER && !IsFloatingPoint(rep),
291 : GetRegConfig()->IsAllocatableGeneralCode(index));
292 : DCHECK_IMPLIES(kind == REGISTER && rep == MachineRepresentation::kFloat32,
293 : GetRegConfig()->IsAllocatableFloatCode(index));
294 : DCHECK_IMPLIES(kind == REGISTER && (rep == MachineRepresentation::kFloat64),
295 : GetRegConfig()->IsAllocatableDoubleCode(index));
296 712158 : }
297 :
298 0 : Instruction::Instruction(InstructionCode opcode)
299 : : opcode_(opcode),
300 : bit_field_(OutputCountField::encode(0) | InputCountField::encode(0) |
301 : TempCountField::encode(0) | IsCallField::encode(false)),
302 : reference_map_(nullptr),
303 0 : block_(nullptr) {
304 0 : parallel_moves_[0] = nullptr;
305 0 : parallel_moves_[1] = nullptr;
306 0 : }
307 :
308 63182510 : Instruction::Instruction(InstructionCode opcode, size_t output_count,
309 : InstructionOperand* outputs, size_t input_count,
310 : InstructionOperand* inputs, size_t temp_count,
311 : InstructionOperand* temps)
312 : : opcode_(opcode),
313 63182510 : bit_field_(OutputCountField::encode(output_count) |
314 63182510 : InputCountField::encode(input_count) |
315 : TempCountField::encode(temp_count) |
316 : IsCallField::encode(false)),
317 : reference_map_(nullptr),
318 189547392 : block_(nullptr) {
319 63182510 : parallel_moves_[0] = nullptr;
320 63182510 : parallel_moves_[1] = nullptr;
321 : size_t offset = 0;
322 98145309 : for (size_t i = 0; i < output_count; ++i) {
323 : DCHECK(!outputs[i].IsInvalid());
324 34962799 : operands_[offset++] = outputs[i];
325 : }
326 132769877 : for (size_t i = 0; i < input_count; ++i) {
327 : DCHECK(!inputs[i].IsInvalid());
328 132769877 : operands_[offset++] = inputs[i];
329 : }
330 753856 : for (size_t i = 0; i < temp_count; ++i) {
331 : DCHECK(!temps[i].IsInvalid());
332 753856 : operands_[offset++] = temps[i];
333 : }
334 63182510 : }
335 :
336 55805087 : bool Instruction::AreMovesRedundant() const {
337 153527046 : for (int i = Instruction::FIRST_GAP_POSITION;
338 : i <= Instruction::LAST_GAP_POSITION; i++) {
339 104666029 : if (parallel_moves_[i] != nullptr && !parallel_moves_[i]->IsRedundant()) {
340 : return false;
341 : }
342 : }
343 : return true;
344 : }
345 :
346 0 : void Instruction::Print() const { StdoutStream{} << *this << std::endl; }
347 :
348 89 : std::ostream& operator<<(std::ostream& os, const ParallelMove& pm) {
349 : const char* space = "";
350 263 : for (MoveOperands* move : pm) {
351 85 : if (move->IsEliminated()) continue;
352 71 : os << space << *move;
353 : space = " ";
354 : }
355 89 : return os;
356 : }
357 :
358 38625987 : void ReferenceMap::RecordReference(const AllocatedOperand& op) {
359 : // Do not record arguments as pointers.
360 101024134 : if (op.IsStackSlot() && LocationOperand::cast(op).index() < 0) return;
361 : DCHECK(!op.IsFPRegister() && !op.IsFPStackSlot());
362 30927372 : reference_operands_.push_back(op);
363 : }
364 :
365 0 : std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm) {
366 0 : os << "{";
367 : const char* separator = "";
368 0 : for (const InstructionOperand& op : pm.reference_operands_) {
369 0 : os << separator << op;
370 : separator = ";";
371 : }
372 0 : return os << "}";
373 : }
374 :
375 272 : std::ostream& operator<<(std::ostream& os, const ArchOpcode& ao) {
376 272 : switch (ao) {
377 : #define CASE(Name) \
378 : case k##Name: \
379 : return os << #Name;
380 13 : ARCH_OPCODE_LIST(CASE)
381 : #undef CASE
382 : }
383 0 : UNREACHABLE();
384 : }
385 :
386 64 : std::ostream& operator<<(std::ostream& os, const AddressingMode& am) {
387 64 : switch (am) {
388 : case kMode_None:
389 : return os;
390 : #define CASE(Name) \
391 : case kMode_##Name: \
392 : return os << #Name;
393 8 : TARGET_ADDRESSING_MODE_LIST(CASE)
394 : #undef CASE
395 : }
396 0 : UNREACHABLE();
397 : }
398 :
399 36 : std::ostream& operator<<(std::ostream& os, const FlagsMode& fm) {
400 36 : switch (fm) {
401 : case kFlags_none:
402 : return os;
403 : case kFlags_branch:
404 21 : return os << "branch";
405 : case kFlags_branch_and_poison:
406 0 : return os << "branch_and_poison";
407 : case kFlags_deoptimize:
408 15 : return os << "deoptimize";
409 : case kFlags_deoptimize_and_poison:
410 0 : return os << "deoptimize_and_poison";
411 : case kFlags_set:
412 0 : return os << "set";
413 : case kFlags_trap:
414 0 : return os << "trap";
415 : }
416 0 : UNREACHABLE();
417 : }
418 :
419 36 : std::ostream& operator<<(std::ostream& os, const FlagsCondition& fc) {
420 36 : switch (fc) {
421 : case kEqual:
422 8 : return os << "equal";
423 : case kNotEqual:
424 18 : return os << "not equal";
425 : case kSignedLessThan:
426 0 : return os << "signed less than";
427 : case kSignedGreaterThanOrEqual:
428 0 : return os << "signed greater than or equal";
429 : case kSignedLessThanOrEqual:
430 0 : return os << "signed less than or equal";
431 : case kSignedGreaterThan:
432 0 : return os << "signed greater than";
433 : case kUnsignedLessThan:
434 0 : return os << "unsigned less than";
435 : case kUnsignedGreaterThanOrEqual:
436 0 : return os << "unsigned greater than or equal";
437 : case kUnsignedLessThanOrEqual:
438 0 : return os << "unsigned less than or equal";
439 : case kUnsignedGreaterThan:
440 5 : return os << "unsigned greater than";
441 : case kFloatLessThanOrUnordered:
442 0 : return os << "less than or unordered (FP)";
443 : case kFloatGreaterThanOrEqual:
444 0 : return os << "greater than or equal (FP)";
445 : case kFloatLessThanOrEqual:
446 0 : return os << "less than or equal (FP)";
447 : case kFloatGreaterThanOrUnordered:
448 0 : return os << "greater than or unordered (FP)";
449 : case kFloatLessThan:
450 0 : return os << "less than (FP)";
451 : case kFloatGreaterThanOrEqualOrUnordered:
452 0 : return os << "greater than, equal or unordered (FP)";
453 : case kFloatLessThanOrEqualOrUnordered:
454 0 : return os << "less than, equal or unordered (FP)";
455 : case kFloatGreaterThan:
456 0 : return os << "greater than (FP)";
457 : case kUnorderedEqual:
458 0 : return os << "unordered equal";
459 : case kUnorderedNotEqual:
460 0 : return os << "unordered not equal";
461 : case kOverflow:
462 5 : return os << "overflow";
463 : case kNotOverflow:
464 0 : return os << "not overflow";
465 : case kPositiveOrZero:
466 0 : return os << "positive or zero";
467 : case kNegative:
468 0 : return os << "negative";
469 : }
470 0 : UNREACHABLE();
471 : }
472 :
473 1186 : std::ostream& operator<<(std::ostream& os, const Instruction& instr) {
474 146 : os << "gap ";
475 438 : for (int i = Instruction::FIRST_GAP_POSITION;
476 : i <= Instruction::LAST_GAP_POSITION; i++) {
477 292 : os << "(";
478 292 : if (instr.parallel_moves()[i] != nullptr) {
479 89 : os << *instr.parallel_moves()[i];
480 : }
481 292 : os << ") ";
482 : }
483 146 : os << "\n ";
484 :
485 146 : if (instr.OutputCount() == 1) {
486 97 : os << *instr.OutputAt(0) << " = ";
487 49 : } else if (instr.OutputCount() > 1) {
488 0 : os << "(" << *instr.OutputAt(0);
489 0 : for (size_t i = 1; i < instr.OutputCount(); i++) {
490 0 : os << ", " << *instr.OutputAt(i);
491 : }
492 0 : os << ") = ";
493 : }
494 :
495 292 : os << ArchOpcodeField::decode(instr.opcode());
496 146 : AddressingMode am = AddressingModeField::decode(instr.opcode());
497 146 : if (am != kMode_None) {
498 32 : os << " : " << AddressingModeField::decode(instr.opcode());
499 : }
500 292 : FlagsMode fm = FlagsModeField::decode(instr.opcode());
501 146 : if (fm != kFlags_none) {
502 20 : os << " && " << fm << " if " << FlagsConditionField::decode(instr.opcode());
503 : }
504 766 : for (size_t i = 0; i < instr.InputCount(); i++) {
505 310 : os << " " << *instr.InputAt(i);
506 : }
507 146 : return os;
508 : }
509 :
510 38809932 : Constant::Constant(int32_t v) : type_(kInt32), value_(v) {}
511 :
512 80791 : Constant::Constant(RelocatablePtrConstantInfo info) {
513 80791 : if (info.type() == RelocatablePtrConstantInfo::kInt32) {
514 0 : type_ = kInt32;
515 80791 : } else if (info.type() == RelocatablePtrConstantInfo::kInt64) {
516 80791 : type_ = kInt64;
517 : } else {
518 0 : UNREACHABLE();
519 : }
520 80791 : value_ = info.value();
521 80791 : rmode_ = info.rmode();
522 80791 : }
523 :
524 14347945 : Handle<HeapObject> Constant::ToHeapObject() const {
525 : DCHECK_EQ(kHeapObject, type());
526 : Handle<HeapObject> value(
527 14347978 : reinterpret_cast<Address*>(static_cast<intptr_t>(value_)));
528 14347945 : return value;
529 : }
530 :
531 4732661 : Handle<Code> Constant::ToCode() const {
532 : DCHECK_EQ(kHeapObject, type());
533 4732661 : Handle<Code> value(reinterpret_cast<Address*>(static_cast<intptr_t>(value_)));
534 4732661 : return value;
535 : }
536 :
537 4578 : const StringConstantBase* Constant::ToDelayedStringConstant() const {
538 : DCHECK_EQ(kDelayedStringConstant, type());
539 : const StringConstantBase* value =
540 4578 : bit_cast<StringConstantBase*>(static_cast<intptr_t>(value_));
541 4578 : return value;
542 : }
543 :
544 283 : std::ostream& operator<<(std::ostream& os, const Constant& constant) {
545 177 : switch (constant.type()) {
546 : case Constant::kInt32:
547 5 : return os << constant.ToInt32();
548 : case Constant::kInt64:
549 32 : return os << constant.ToInt64() << "l";
550 : case Constant::kFloat32:
551 0 : return os << constant.ToFloat32() << "f";
552 : case Constant::kFloat64:
553 : return os << constant.ToFloat64().value();
554 : case Constant::kExternalReference:
555 : return os << constant.ToExternalReference().address();
556 : case Constant::kHeapObject:
557 33 : return os << Brief(*constant.ToHeapObject());
558 : case Constant::kRpoNumber:
559 96 : return os << "RPO" << constant.ToRpoNumber().ToInt();
560 : case Constant::kDelayedStringConstant:
561 0 : return os << "DelayedStringConstant: "
562 0 : << constant.ToDelayedStringConstant();
563 : }
564 0 : UNREACHABLE();
565 : }
566 :
567 2098901 : PhiInstruction::PhiInstruction(Zone* zone, int virtual_register,
568 : size_t input_count)
569 : : virtual_register_(virtual_register),
570 : output_(UnallocatedOperand(UnallocatedOperand::NONE, virtual_register)),
571 : operands_(input_count, InstructionOperand::kInvalidVirtualRegister,
572 6296705 : zone) {}
573 :
574 5080726 : void PhiInstruction::SetInput(size_t offset, int virtual_register) {
575 : DCHECK_EQ(InstructionOperand::kInvalidVirtualRegister, operands_[offset]);
576 10161452 : operands_[offset] = virtual_register;
577 5080726 : }
578 :
579 301954 : void PhiInstruction::RenameInput(size_t offset, int virtual_register) {
580 : DCHECK_NE(InstructionOperand::kInvalidVirtualRegister, operands_[offset]);
581 603908 : operands_[offset] = virtual_register;
582 301954 : }
583 :
584 7395 : InstructionBlock::InstructionBlock(Zone* zone, RpoNumber rpo_number,
585 : RpoNumber loop_header, RpoNumber loop_end,
586 : bool deferred, bool handler)
587 : : successors_(zone),
588 : predecessors_(zone),
589 : phis_(zone),
590 : ao_number_(RpoNumber::Invalid()),
591 : rpo_number_(rpo_number),
592 : loop_header_(loop_header),
593 : loop_end_(loop_end),
594 : deferred_(deferred),
595 19449740 : handler_(handler) {}
596 :
597 23035214 : size_t InstructionBlock::PredecessorIndexOf(RpoNumber rpo_number) const {
598 : size_t j = 0;
599 958962092 : for (InstructionBlock::Predecessors::const_iterator i = predecessors_.begin();
600 : i != predecessors_.end(); ++i, ++j) {
601 958784489 : if (*i == rpo_number) break;
602 : }
603 23035214 : return j;
604 : }
605 :
606 69029697 : static RpoNumber GetRpo(const BasicBlock* block) {
607 85447931 : if (block == nullptr) return RpoNumber::Invalid();
608 : return RpoNumber::FromInt(block->rpo_number());
609 : }
610 :
611 19442236 : static RpoNumber GetLoopEndRpo(const BasicBlock* block) {
612 19442236 : if (!block->IsLoopHeader()) return RpoNumber::Invalid();
613 243534 : return RpoNumber::FromInt(block->loop_end()->rpo_number());
614 : }
615 :
616 19442236 : static InstructionBlock* InstructionBlockFor(Zone* zone,
617 38884472 : const BasicBlock* block) {
618 : bool is_handler =
619 38693048 : !block->empty() && block->front()->opcode() == IrOpcode::kIfException;
620 : InstructionBlock* instr_block = new (zone)
621 : InstructionBlock(zone, GetRpo(block), GetRpo(block->loop_header()),
622 : GetLoopEndRpo(block), block->deferred(), is_handler);
623 : // Map successors and precessors
624 19442345 : instr_block->successors().reserve(block->SuccessorCount());
625 62166237 : for (BasicBlock* successor : block->successors()) {
626 46563487 : instr_block->successors().push_back(GetRpo(successor));
627 : }
628 19442324 : instr_block->predecessors().reserve(block->PredecessorCount());
629 62166307 : for (BasicBlock* predecessor : block->predecessors()) {
630 46563572 : instr_block->predecessors().push_back(GetRpo(predecessor));
631 : }
632 32999868 : if (block->PredecessorCount() == 1 &&
633 13557579 : block->predecessors()[0]->control() == BasicBlock::Control::kSwitch) {
634 : instr_block->set_switch_target(true);
635 : }
636 19442289 : return instr_block;
637 : }
638 :
639 38 : std::ostream& operator<<(std::ostream& os,
640 : const PrintableInstructionBlock& printable_block) {
641 430 : const InstructionBlock* block = printable_block.block_;
642 38 : const InstructionSequence* code = printable_block.code_;
643 :
644 38 : os << "B" << block->rpo_number();
645 38 : os << ": AO#" << block->ao_number();
646 38 : if (block->IsDeferred()) os << " (deferred)";
647 38 : if (!block->needs_frame()) os << " (no frame)";
648 38 : if (block->must_construct_frame()) os << " (construct frame)";
649 38 : if (block->must_deconstruct_frame()) os << " (deconstruct frame)";
650 38 : if (block->IsLoopHeader()) {
651 0 : os << " loop blocks: [" << block->rpo_number() << ", " << block->loop_end()
652 0 : << ")";
653 : }
654 38 : os << " instructions: [" << block->code_start() << ", " << block->code_end()
655 38 : << ")" << std::endl
656 38 : << " predecessors:";
657 :
658 120 : for (RpoNumber pred : block->predecessors()) {
659 44 : os << " B" << pred.ToInt();
660 : }
661 : os << std::endl;
662 :
663 84 : for (const PhiInstruction* phi : block->phis()) {
664 8 : os << " phi: " << phi->output() << " =";
665 32 : for (int input : phi->operands()) {
666 16 : os << " v" << input;
667 : }
668 : os << std::endl;
669 : }
670 :
671 328 : for (int j = block->first_instruction_index();
672 : j <= block->last_instruction_index(); j++) {
673 252 : os << " " << std::setw(5) << j << ": " << *code->InstructionAt(j)
674 : << std::endl;
675 : }
676 :
677 38 : os << " successors:";
678 120 : for (RpoNumber succ : block->successors()) {
679 44 : os << " B" << succ.ToInt();
680 : }
681 : os << std::endl;
682 38 : return os;
683 : }
684 :
685 2141539 : InstructionBlocks* InstructionSequence::InstructionBlocksFor(
686 : Zone* zone, const Schedule* schedule) {
687 : InstructionBlocks* blocks = zone->NewArray<InstructionBlocks>(1);
688 : new (blocks) InstructionBlocks(
689 4283696 : static_cast<int>(schedule->rpo_order()->size()), nullptr, zone);
690 : size_t rpo_number = 0;
691 43168104 : for (BasicBlockVector::const_iterator it = schedule->rpo_order()->begin();
692 21584052 : it != schedule->rpo_order()->end(); ++it, ++rpo_number) {
693 : DCHECK(!(*blocks)[rpo_number]);
694 : DCHECK(GetRpo(*it).ToSize() == rpo_number);
695 38884482 : (*blocks)[rpo_number] = InstructionBlockFor(zone, *it);
696 : }
697 2141811 : return blocks;
698 : }
699 :
700 0 : void InstructionSequence::ValidateEdgeSplitForm() const {
701 : // Validate blocks are in edge-split form: no block with multiple successors
702 : // has an edge to a block (== a successor) with more than one predecessors.
703 0 : for (const InstructionBlock* block : instruction_blocks()) {
704 0 : if (block->SuccessorCount() > 1) {
705 0 : for (const RpoNumber& successor_id : block->successors()) {
706 0 : const InstructionBlock* successor = InstructionBlockAt(successor_id);
707 : // Expect precisely one predecessor: "block".
708 0 : CHECK(successor->PredecessorCount() == 1 &&
709 : successor->predecessors()[0] == block->rpo_number());
710 : }
711 : }
712 : }
713 0 : }
714 :
715 0 : void InstructionSequence::ValidateDeferredBlockExitPaths() const {
716 : // A deferred block with more than one successor must have all its successors
717 : // deferred.
718 0 : for (const InstructionBlock* block : instruction_blocks()) {
719 0 : if (!block->IsDeferred() || block->SuccessorCount() <= 1) continue;
720 0 : for (RpoNumber successor_id : block->successors()) {
721 0 : CHECK(InstructionBlockAt(successor_id)->IsDeferred());
722 : }
723 : }
724 0 : }
725 :
726 0 : void InstructionSequence::ValidateDeferredBlockEntryPaths() const {
727 : // If a deferred block has multiple predecessors, they have to
728 : // all be deferred. Otherwise, we can run into a situation where a range
729 : // that spills only in deferred blocks inserts its spill in the block, but
730 : // other ranges need moves inserted by ResolveControlFlow in the predecessors,
731 : // which may clobber the register of this range.
732 0 : for (const InstructionBlock* block : instruction_blocks()) {
733 0 : if (!block->IsDeferred() || block->PredecessorCount() <= 1) continue;
734 0 : for (RpoNumber predecessor_id : block->predecessors()) {
735 0 : CHECK(InstructionBlockAt(predecessor_id)->IsDeferred());
736 : }
737 : }
738 0 : }
739 :
740 0 : void InstructionSequence::ValidateSSA() const {
741 : // TODO(mtrofin): We could use a local zone here instead.
742 0 : BitVector definitions(VirtualRegisterCount(), zone());
743 0 : for (const Instruction* instruction : *this) {
744 0 : for (size_t i = 0; i < instruction->OutputCount(); ++i) {
745 0 : const InstructionOperand* output = instruction->OutputAt(i);
746 : int vreg = (output->IsConstant())
747 : ? ConstantOperand::cast(output)->virtual_register()
748 0 : : UnallocatedOperand::cast(output)->virtual_register();
749 0 : CHECK(!definitions.Contains(vreg));
750 : definitions.Add(vreg);
751 : }
752 : }
753 0 : }
754 :
755 4285721 : void InstructionSequence::ComputeAssemblyOrder() {
756 : int ao = 0;
757 : RpoNumber invalid = RpoNumber::Invalid();
758 :
759 2142917 : ao_blocks_ = zone()->NewArray<InstructionBlocks>(1);
760 2142917 : new (ao_blocks_) InstructionBlocks(zone());
761 4285834 : ao_blocks_->reserve(instruction_blocks_->size());
762 :
763 : // Place non-deferred blocks.
764 25870562 : for (InstructionBlock* const block : *instruction_blocks_) {
765 : DCHECK_NOT_NULL(block);
766 21539331 : if (block->IsDeferred()) continue; // skip deferred blocks.
767 14866784 : if (block->ao_number() != invalid) continue; // loop rotated.
768 14661977 : if (block->IsLoopHeader()) {
769 : bool header_align = true;
770 214604 : if (FLAG_turbo_loop_rotation) {
771 : // Perform loop rotation for non-deferred loops.
772 : InstructionBlock* loop_end =
773 429210 : instruction_blocks_->at(block->loop_end().ToSize() - 1);
774 214605 : if (loop_end->SuccessorCount() == 1 && /* ends with goto */
775 : loop_end != block /* not a degenerate infinite loop */) {
776 : // If the last block has an unconditional jump back to the header,
777 : // then move it to be in front of the header in the assembly order.
778 : DCHECK_EQ(block->rpo_number(), loop_end->successors()[0]);
779 214585 : loop_end->set_ao_number(RpoNumber::FromInt(ao++));
780 214585 : ao_blocks_->push_back(loop_end);
781 : // This block will be the new machine-level loop header, so align
782 : // this block instead of the loop header block.
783 214585 : loop_end->set_alignment(true);
784 : header_align = false;
785 : }
786 : }
787 214604 : block->set_alignment(header_align);
788 : }
789 16759222 : if (block->loop_header().IsValid() && block->IsSwitchTarget()) {
790 : block->set_alignment(true);
791 : }
792 14661977 : block->set_ao_number(RpoNumber::FromInt(ao++));
793 14661977 : ao_blocks_->push_back(block);
794 : }
795 : // Add all leftover (deferred) blocks.
796 25871417 : for (InstructionBlock* const block : *instruction_blocks_) {
797 19442336 : if (block->ao_number() == invalid) {
798 4565631 : block->set_ao_number(RpoNumber::FromInt(ao++));
799 4565631 : ao_blocks_->push_back(block);
800 : }
801 : }
802 : DCHECK_EQ(instruction_blocks_->size(), ao);
803 2143013 : }
804 :
805 35 : void InstructionSequence::RecomputeAssemblyOrderForTesting() {
806 : RpoNumber invalid = RpoNumber::Invalid();
807 260 : for (InstructionBlock* block : *instruction_blocks_) {
808 : block->set_ao_number(invalid);
809 : }
810 35 : ComputeAssemblyOrder();
811 35 : }
812 :
813 2142737 : InstructionSequence::InstructionSequence(Isolate* isolate,
814 : Zone* instruction_zone,
815 4285836 : InstructionBlocks* instruction_blocks)
816 : : isolate_(isolate),
817 : zone_(instruction_zone),
818 : instruction_blocks_(instruction_blocks),
819 : ao_blocks_(nullptr),
820 : source_positions_(zone()),
821 : constants_(ConstantMap::key_compare(),
822 : ConstantMap::allocator_type(zone())),
823 : immediates_(zone()),
824 : instructions_(zone()),
825 : next_virtual_register_(0),
826 : reference_maps_(zone()),
827 : representations_(zone()),
828 : representation_mask_(0),
829 : deoptimization_entries_(zone()),
830 8571535 : current_block_(nullptr) {
831 2142962 : ComputeAssemblyOrder();
832 2142992 : }
833 :
834 40947345 : int InstructionSequence::NextVirtualRegister() {
835 40947345 : int virtual_register = next_virtual_register_++;
836 40947345 : CHECK_NE(virtual_register, InstructionOperand::kInvalidVirtualRegister);
837 40947345 : return virtual_register;
838 : }
839 :
840 0 : Instruction* InstructionSequence::GetBlockStart(RpoNumber rpo) const {
841 0 : const InstructionBlock* block = InstructionBlockAt(rpo);
842 0 : return InstructionAt(block->code_start());
843 : }
844 :
845 19449157 : void InstructionSequence::StartBlock(RpoNumber rpo) {
846 : DCHECK_NULL(current_block_);
847 19449157 : current_block_ = InstructionBlockAt(rpo);
848 19449291 : int code_start = static_cast<int>(instructions_.size());
849 : current_block_->set_code_start(code_start);
850 19449291 : }
851 :
852 19449438 : void InstructionSequence::EndBlock(RpoNumber rpo) {
853 19449438 : int end = static_cast<int>(instructions_.size());
854 : DCHECK_EQ(current_block_->rpo_number(), rpo);
855 19449438 : CHECK(current_block_->code_start() >= 0 &&
856 : current_block_->code_start() < end);
857 : current_block_->set_code_end(end);
858 19449438 : current_block_ = nullptr;
859 19449438 : }
860 :
861 68906741 : int InstructionSequence::AddInstruction(Instruction* instr) {
862 : DCHECK_NOT_NULL(current_block_);
863 63182769 : int index = static_cast<int>(instructions_.size());
864 63182769 : instr->set_block(current_block_);
865 63182769 : instructions_.push_back(instr);
866 126365558 : if (instr->NeedsReferenceMap()) {
867 : DCHECK_NULL(instr->reference_map());
868 5723976 : ReferenceMap* reference_map = new (zone()) ReferenceMap(zone());
869 : reference_map->set_instruction_position(index);
870 5723976 : instr->set_reference_map(reference_map);
871 5723976 : reference_maps_.push_back(reference_map);
872 : }
873 63182784 : return index;
874 : }
875 :
876 154577457 : InstructionBlock* InstructionSequence::GetInstructionBlock(
877 : int instruction_index) const {
878 154578524 : return instructions()[instruction_index]->block();
879 : }
880 :
881 31127830 : static MachineRepresentation FilterRepresentation(MachineRepresentation rep) {
882 31127830 : switch (rep) {
883 : case MachineRepresentation::kBit:
884 : case MachineRepresentation::kWord8:
885 : case MachineRepresentation::kWord16:
886 : return InstructionSequence::DefaultRepresentation();
887 : case MachineRepresentation::kWord32:
888 : case MachineRepresentation::kWord64:
889 : case MachineRepresentation::kTaggedSigned:
890 : case MachineRepresentation::kTaggedPointer:
891 : case MachineRepresentation::kTagged:
892 : case MachineRepresentation::kFloat32:
893 : case MachineRepresentation::kFloat64:
894 : case MachineRepresentation::kSimd128:
895 30674259 : return rep;
896 : case MachineRepresentation::kNone:
897 : break;
898 : }
899 :
900 0 : UNREACHABLE();
901 : }
902 :
903 154823906 : MachineRepresentation InstructionSequence::GetRepresentation(
904 : int virtual_register) const {
905 : DCHECK_LE(0, virtual_register);
906 : DCHECK_LT(virtual_register, VirtualRegisterCount());
907 309647812 : if (virtual_register >= static_cast<int>(representations_.size())) {
908 : return DefaultRepresentation();
909 : }
910 296962220 : return representations_[virtual_register];
911 : }
912 :
913 31127586 : void InstructionSequence::MarkAsRepresentation(MachineRepresentation rep,
914 18040365 : int virtual_register) {
915 : DCHECK_LE(0, virtual_register);
916 : DCHECK_LT(virtual_register, VirtualRegisterCount());
917 93383091 : if (virtual_register >= static_cast<int>(representations_.size())) {
918 36080730 : representations_.resize(VirtualRegisterCount(), DefaultRepresentation());
919 : }
920 31127741 : rep = FilterRepresentation(rep);
921 : DCHECK_IMPLIES(representations_[virtual_register] != rep,
922 : representations_[virtual_register] == DefaultRepresentation());
923 62255838 : representations_[virtual_register] = rep;
924 31127919 : representation_mask_ |= RepresentationBit(rep);
925 31127919 : }
926 :
927 3569045 : int InstructionSequence::AddDeoptimizationEntry(
928 : FrameStateDescriptor* descriptor, DeoptimizeKind kind,
929 : DeoptimizeReason reason, VectorSlotPair const& feedback) {
930 7138090 : int deoptimization_id = static_cast<int>(deoptimization_entries_.size());
931 : deoptimization_entries_.push_back(
932 7138099 : DeoptimizationEntry(descriptor, kind, reason, feedback));
933 3569054 : return deoptimization_id;
934 : }
935 :
936 6759219 : DeoptimizationEntry const& InstructionSequence::GetDeoptimizationEntry(
937 : int state_id) {
938 13518438 : return deoptimization_entries_[state_id];
939 : }
940 :
941 6817125 : RpoNumber InstructionSequence::InputRpo(Instruction* instr, size_t index) {
942 6817125 : InstructionOperand* operand = instr->InputAt(index);
943 : Constant constant =
944 : operand->IsImmediate()
945 : ? GetImmediate(ImmediateOperand::cast(operand))
946 6817125 : : GetConstant(ConstantOperand::cast(operand)->virtual_register());
947 6817144 : return constant.ToRpoNumber();
948 : }
949 :
950 40309659 : bool InstructionSequence::GetSourcePosition(const Instruction* instr,
951 : SourcePosition* result) const {
952 : auto it = source_positions_.find(instr);
953 40309800 : if (it == source_positions_.end()) return false;
954 4648530 : *result = it->second;
955 4648530 : return true;
956 : }
957 :
958 4790836 : void InstructionSequence::SetSourcePosition(const Instruction* instr,
959 : SourcePosition value) {
960 9581736 : source_positions_.insert(std::make_pair(instr, value));
961 4790900 : }
962 :
963 0 : void InstructionSequence::Print() const {
964 0 : StdoutStream{} << *this << std::endl;
965 0 : }
966 :
967 0 : void InstructionSequence::PrintBlock(int block_id) const {
968 : RpoNumber rpo = RpoNumber::FromInt(block_id);
969 0 : const InstructionBlock* block = InstructionBlockAt(rpo);
970 0 : CHECK(block->rpo_number() == rpo);
971 0 : StdoutStream{} << PrintableInstructionBlock{block, this} << std::endl;
972 0 : }
973 :
974 : const RegisterConfiguration*
975 : InstructionSequence::registerConfigurationForTesting_ = nullptr;
976 :
977 : const RegisterConfiguration*
978 0 : InstructionSequence::RegisterConfigurationForTesting() {
979 : DCHECK_NOT_NULL(registerConfigurationForTesting_);
980 0 : return registerConfigurationForTesting_;
981 : }
982 :
983 52 : void InstructionSequence::SetRegisterConfigurationForTesting(
984 : const RegisterConfiguration* regConfig) {
985 52 : registerConfigurationForTesting_ = regConfig;
986 52 : GetRegConfig = InstructionSequence::RegisterConfigurationForTesting;
987 52 : }
988 :
989 3946977 : FrameStateDescriptor::FrameStateDescriptor(
990 : Zone* zone, FrameStateType type, BailoutId bailout_id,
991 : OutputFrameStateCombine state_combine, size_t parameters_count,
992 : size_t locals_count, size_t stack_count,
993 : MaybeHandle<SharedFunctionInfo> shared_info,
994 : FrameStateDescriptor* outer_state)
995 : : type_(type),
996 : bailout_id_(bailout_id),
997 : frame_state_combine_(state_combine),
998 : parameters_count_(parameters_count),
999 : locals_count_(locals_count),
1000 : stack_count_(stack_count),
1001 : values_(zone),
1002 : shared_info_(shared_info),
1003 7893954 : outer_state_(outer_state) {}
1004 :
1005 21851769 : size_t FrameStateDescriptor::GetSize() const {
1006 21851769 : return 1 + parameters_count() + locals_count() + stack_count() +
1007 7283923 : (HasContext() ? 1 : 0);
1008 : }
1009 :
1010 3190196 : size_t FrameStateDescriptor::GetTotalSize() const {
1011 : size_t total_size = 0;
1012 6527168 : for (const FrameStateDescriptor* iter = this; iter != nullptr;
1013 : iter = iter->outer_state_) {
1014 3336972 : total_size += iter->GetSize();
1015 : }
1016 3190196 : return total_size;
1017 : }
1018 :
1019 3569036 : size_t FrameStateDescriptor::GetFrameCount() const {
1020 : size_t count = 0;
1021 7515987 : for (const FrameStateDescriptor* iter = this; iter != nullptr;
1022 : iter = iter->outer_state_) {
1023 3946951 : ++count;
1024 : }
1025 3569036 : return count;
1026 : }
1027 :
1028 3569029 : size_t FrameStateDescriptor::GetJSFrameCount() const {
1029 : size_t count = 0;
1030 7515982 : for (const FrameStateDescriptor* iter = this; iter != nullptr;
1031 : iter = iter->outer_state_) {
1032 7893906 : if (FrameStateFunctionInfo::IsJSFunctionType(iter->type_)) {
1033 3834975 : ++count;
1034 : }
1035 : }
1036 3569029 : return count;
1037 : }
1038 :
1039 57 : std::ostream& operator<<(std::ostream& os, const RpoNumber& rpo) {
1040 57 : return os << rpo.ToSize();
1041 : }
1042 :
1043 46 : std::ostream& operator<<(std::ostream& os, const InstructionSequence& code) {
1044 164 : for (size_t i = 0; i < code.immediates_.size(); ++i) {
1045 160 : Constant constant = code.immediates_[i];
1046 156 : os << "IMM#" << i << ": " << constant << "\n";
1047 : }
1048 : int i = 0;
1049 24 : for (ConstantMap::const_iterator it = code.constants_.begin();
1050 : it != code.constants_.end(); ++i, ++it) {
1051 8 : os << "CST#" << i << ": v" << it->first << " = " << it->second << "\n";
1052 : }
1053 80 : for (int i = 0; i < code.InstructionBlockCount(); i++) {
1054 38 : auto* block = code.InstructionBlockAt(RpoNumber::FromInt(i));
1055 38 : os << PrintableInstructionBlock{block, &code};
1056 : }
1057 4 : return os;
1058 : }
1059 :
1060 : } // namespace compiler
1061 : } // namespace internal
1062 178779 : } // namespace v8
|
