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