Bug Summary

File:out/../deps/v8/src/compiler/backend/register-allocator.cc
Warning:line 1199, column 19
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name register-allocator.cc -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/home/maurizio/node-v18.6.0/out -resource-dir /usr/local/lib/clang/16.0.0 -D _GLIBCXX_USE_CXX11_ABI=1 -D NODE_OPENSSL_CONF_NAME=nodejs_conf -D NODE_OPENSSL_HAS_QUIC -D V8_GYP_BUILD -D V8_TYPED_ARRAY_MAX_SIZE_IN_HEAP=64 -D __STDC_FORMAT_MACROS -D OPENSSL_NO_PINSHARED -D OPENSSL_THREADS -D V8_TARGET_ARCH_X64 -D V8_HAVE_TARGET_OS -D V8_TARGET_OS_LINUX -D V8_EMBEDDER_STRING="-node.8" -D ENABLE_DISASSEMBLER -D V8_PROMISE_INTERNAL_FIELD_COUNT=1 -D V8_SHORT_BUILTIN_CALLS -D OBJECT_PRINT -D V8_INTL_SUPPORT -D V8_ATOMIC_OBJECT_FIELD_WRITES -D V8_ENABLE_LAZY_SOURCE_POSITIONS -D V8_USE_SIPHASH -D V8_SHARED_RO_HEAP -D V8_WIN64_UNWINDING_INFO -D V8_ENABLE_REGEXP_INTERPRETER_THREADED_DISPATCH -D V8_SNAPSHOT_COMPRESSION -D V8_ENABLE_WEBASSEMBLY -D V8_ENABLE_JAVASCRIPT_PROMISE_HOOKS -D V8_ALLOCATION_FOLDING -D V8_ALLOCATION_SITE_TRACKING -D V8_SCRIPTORMODULE_LEGACY_LIFETIME -D V8_ADVANCED_BIGINT_ALGORITHMS -D UCONFIG_NO_SERVICE=1 -D U_ENABLE_DYLOAD=0 -D U_STATIC_IMPLEMENTATION=1 -D U_HAVE_STD_STRING=1 -D UCONFIG_NO_BREAK_ITERATION=0 -I ../deps/v8 -I ../deps/v8/include -I /home/maurizio/node-v18.6.0/out/Release/obj/gen/generate-bytecode-output-root -I /home/maurizio/node-v18.6.0/out/Release/obj/gen -I ../deps/icu-small/source/i18n -I ../deps/icu-small/source/common -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8/x86_64-redhat-linux -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8/backward -internal-isystem /usr/local/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../x86_64-redhat-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -Wno-unused-parameter -Wno-return-type -std=gnu++17 -fdeprecated-macro -fdebug-compilation-dir=/home/maurizio/node-v18.6.0/out -ferror-limit 19 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-08-22-142216-507842-1 -x c++ ../deps/v8/src/compiler/backend/register-allocator.cc

../deps/v8/src/compiler/backend/register-allocator.cc

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/register-allocator.h"
6
7#include <iomanip>
8
9#include "src/base/iterator.h"
10#include "src/base/small-vector.h"
11#include "src/base/vector.h"
12#include "src/codegen/assembler-inl.h"
13#include "src/codegen/tick-counter.h"
14#include "src/compiler/backend/spill-placer.h"
15#include "src/compiler/linkage.h"
16#include "src/strings/string-stream.h"
17
18namespace v8 {
19namespace internal {
20namespace compiler {
21
22#define TRACE_COND(cond, ...) \
23 do { \
24 if (cond) PrintF(__VA_ARGS__); \
25 } while (false)
26
27#define TRACE(...) TRACE_COND(data()->is_trace_alloc(), __VA_ARGS__)
28
29namespace {
30
31static constexpr int kFloat32Bit =
32 RepresentationBit(MachineRepresentation::kFloat32);
33static constexpr int kSimd128Bit =
34 RepresentationBit(MachineRepresentation::kSimd128);
35
36
37const InstructionBlock* GetContainingLoop(const InstructionSequence* sequence,
38 const InstructionBlock* block) {
39 RpoNumber index = block->loop_header();
40 if (!index.IsValid()) return nullptr;
41 return sequence->InstructionBlockAt(index);
42}
43
44const InstructionBlock* GetInstructionBlock(const InstructionSequence* code,
45 LifetimePosition pos) {
46 return code->GetInstructionBlock(pos.ToInstructionIndex());
47}
48
49Instruction* GetLastInstruction(InstructionSequence* code,
50 const InstructionBlock* block) {
51 return code->InstructionAt(block->last_instruction_index());
52}
53
54} // namespace
55
56void LiveRangeBoundArray::Initialize(Zone* zone, TopLevelLiveRange* range) {
57 size_t max_child_count = range->GetMaxChildCount();
58
59 start_ = zone->NewArray<LiveRangeBound>(max_child_count);
60 length_ = 0;
61 LiveRangeBound* curr = start_;
62 // The primary loop in ResolveControlFlow is not responsible for inserting
63 // connecting moves for spilled ranges.
64 for (LiveRange* i = range; i != nullptr; i = i->next(), ++curr, ++length_) {
65 new (curr) LiveRangeBound(i, i->spilled());
66 }
67}
68
69LiveRangeBound* LiveRangeBoundArray::Find(
70 const LifetimePosition position) const {
71 size_t left_index = 0;
72 size_t right_index = length_;
73 while (true) {
74 size_t current_index = left_index + (right_index - left_index) / 2;
75 DCHECK(right_index > current_index)((void) 0);
76 LiveRangeBound* bound = &start_[current_index];
77 if (bound->start_ <= position) {
78 if (position < bound->end_) return bound;
79 DCHECK(left_index < current_index)((void) 0);
80 left_index = current_index;
81 } else {
82 right_index = current_index;
83 }
84 }
85}
86
87LiveRangeBound* LiveRangeBoundArray::FindPred(const InstructionBlock* pred) {
88 LifetimePosition pred_end = LifetimePosition::InstructionFromInstructionIndex(
89 pred->last_instruction_index());
90 return Find(pred_end);
91}
92
93LiveRangeBound* LiveRangeBoundArray::FindSucc(const InstructionBlock* succ) {
94 LifetimePosition succ_start = LifetimePosition::GapFromInstructionIndex(
95 succ->first_instruction_index());
96 return Find(succ_start);
97}
98
99bool LiveRangeBoundArray::FindConnectableSubranges(
100 const InstructionBlock* block, const InstructionBlock* pred,
101 FindResult* result) const {
102 LifetimePosition pred_end = LifetimePosition::InstructionFromInstructionIndex(
103 pred->last_instruction_index());
104 LiveRangeBound* bound = Find(pred_end);
105 result->pred_cover_ = bound->range_;
106 LifetimePosition cur_start = LifetimePosition::GapFromInstructionIndex(
107 block->first_instruction_index());
108
109 if (bound->CanCover(cur_start)) {
110 // Both blocks are covered by the same range, so there is nothing to
111 // connect.
112 return false;
113 }
114 bound = Find(cur_start);
115 if (bound->skip_) {
116 return false;
117 }
118 result->cur_cover_ = bound->range_;
119 DCHECK(result->pred_cover_ != nullptr && result->cur_cover_ != nullptr)((void) 0);
120 return (result->cur_cover_ != result->pred_cover_);
121}
122
123LiveRangeFinder::LiveRangeFinder(const TopTierRegisterAllocationData* data,
124 Zone* zone)
125 : data_(data),
126 bounds_length_(static_cast<int>(data_->live_ranges().size())),
127 bounds_(zone->NewArray<LiveRangeBoundArray>(bounds_length_)),
128 zone_(zone) {
129 for (int i = 0; i < bounds_length_; ++i) {
130 new (&bounds_[i]) LiveRangeBoundArray();
131 }
132}
133
134LiveRangeBoundArray* LiveRangeFinder::ArrayFor(int operand_index) {
135 DCHECK(operand_index < bounds_length_)((void) 0);
136 TopLevelLiveRange* range = data_->live_ranges()[operand_index];
137 DCHECK(range != nullptr && !range->IsEmpty())((void) 0);
138 DCHECK_EQ(range->vreg(), operand_index)((void) 0);
139 LiveRangeBoundArray* array = &bounds_[operand_index];
140 if (array->ShouldInitialize()) {
141 array->Initialize(zone_, range);
142 }
143 return array;
144}
145
146using DelayedInsertionMapKey = std::pair<ParallelMove*, InstructionOperand>;
147
148struct DelayedInsertionMapCompare {
149 bool operator()(const DelayedInsertionMapKey& a,
150 const DelayedInsertionMapKey& b) const {
151 if (a.first == b.first) {
152 return a.second.Compare(b.second);
153 }
154 return a.first < b.first;
155 }
156};
157
158using DelayedInsertionMap = ZoneMap<DelayedInsertionMapKey, InstructionOperand,
159 DelayedInsertionMapCompare>;
160
161UsePosition::UsePosition(LifetimePosition pos, InstructionOperand* operand,
162 void* hint, UsePositionHintType hint_type)
163 : operand_(operand), hint_(hint), next_(nullptr), pos_(pos), flags_(0) {
164 DCHECK_IMPLIES(hint == nullptr, hint_type == UsePositionHintType::kNone)((void) 0);
165 bool register_beneficial = true;
166 UsePositionType type = UsePositionType::kRegisterOrSlot;
167 if (operand_ != nullptr && operand_->IsUnallocated()) {
168 const UnallocatedOperand* unalloc = UnallocatedOperand::cast(operand_);
169 if (unalloc->HasRegisterPolicy()) {
170 type = UsePositionType::kRequiresRegister;
171 } else if (unalloc->HasSlotPolicy()) {
172 type = UsePositionType::kRequiresSlot;
173 register_beneficial = false;
174 } else if (unalloc->HasRegisterOrSlotOrConstantPolicy()) {
175 type = UsePositionType::kRegisterOrSlotOrConstant;
176 register_beneficial = false;
177 } else {
178 register_beneficial = !unalloc->HasRegisterOrSlotPolicy();
179 }
180 }
181 flags_ = TypeField::encode(type) | HintTypeField::encode(hint_type) |
182 RegisterBeneficialField::encode(register_beneficial) |
183 AssignedRegisterField::encode(kUnassignedRegister);
184 DCHECK(pos_.IsValid())((void) 0);
185}
186
187bool UsePosition::HasHint() const {
188 int hint_register;
189 return HintRegister(&hint_register);
190}
191
192bool UsePosition::HintRegister(int* register_code) const {
193 if (hint_ == nullptr) return false;
194 switch (HintTypeField::decode(flags_)) {
195 case UsePositionHintType::kNone:
196 case UsePositionHintType::kUnresolved:
197 return false;
198 case UsePositionHintType::kUsePos: {
199 UsePosition* use_pos = reinterpret_cast<UsePosition*>(hint_);
200 int assigned_register = AssignedRegisterField::decode(use_pos->flags_);
201 if (assigned_register == kUnassignedRegister) return false;
202 *register_code = assigned_register;
203 return true;
204 }
205 case UsePositionHintType::kOperand: {
206 InstructionOperand* operand =
207 reinterpret_cast<InstructionOperand*>(hint_);
208 *register_code = LocationOperand::cast(operand)->register_code();
209 return true;
210 }
211 case UsePositionHintType::kPhi: {
212 TopTierRegisterAllocationData::PhiMapValue* phi =
213 reinterpret_cast<TopTierRegisterAllocationData::PhiMapValue*>(hint_);
214 int assigned_register = phi->assigned_register();
215 if (assigned_register == kUnassignedRegister) return false;
216 *register_code = assigned_register;
217 return true;
218 }
219 }
220 UNREACHABLE()V8_Fatal("unreachable code");
221}
222
223UsePositionHintType UsePosition::HintTypeForOperand(
224 const InstructionOperand& op) {
225 switch (op.kind()) {
226 case InstructionOperand::CONSTANT:
227 case InstructionOperand::IMMEDIATE:
228 return UsePositionHintType::kNone;
229 case InstructionOperand::UNALLOCATED:
230 return UsePositionHintType::kUnresolved;
231 case InstructionOperand::ALLOCATED:
232 if (op.IsRegister() || op.IsFPRegister()) {
233 return UsePositionHintType::kOperand;
234 } else {
235 DCHECK(op.IsStackSlot() || op.IsFPStackSlot())((void) 0);
236 return UsePositionHintType::kNone;
237 }
238 case InstructionOperand::PENDING:
239 case InstructionOperand::INVALID:
240 break;
241 }
242 UNREACHABLE()V8_Fatal("unreachable code");
243}
244
245void UsePosition::SetHint(UsePosition* use_pos) {
246 DCHECK_NOT_NULL(use_pos)((void) 0);
247 hint_ = use_pos;
248 flags_ = HintTypeField::update(flags_, UsePositionHintType::kUsePos);
249}
250
251void UsePosition::ResolveHint(UsePosition* use_pos) {
252 DCHECK_NOT_NULL(use_pos)((void) 0);
253 if (HintTypeField::decode(flags_) != UsePositionHintType::kUnresolved) return;
254 hint_ = use_pos;
255 flags_ = HintTypeField::update(flags_, UsePositionHintType::kUsePos);
256}
257
258void UsePosition::set_type(UsePositionType type, bool register_beneficial) {
259 DCHECK_IMPLIES(type == UsePositionType::kRequiresSlot, !register_beneficial)((void) 0);
260 DCHECK_EQ(kUnassignedRegister, AssignedRegisterField::decode(flags_))((void) 0);
261 flags_ = TypeField::encode(type) |
262 RegisterBeneficialField::encode(register_beneficial) |
263 HintTypeField::encode(HintTypeField::decode(flags_)) |
264 AssignedRegisterField::encode(kUnassignedRegister);
265}
266
267UseInterval* UseInterval::SplitAt(LifetimePosition pos, Zone* zone) {
268 DCHECK(Contains(pos) && pos != start())((void) 0);
269 UseInterval* after = zone->New<UseInterval>(pos, end_);
270 after->next_ = next_;
271 next_ = nullptr;
272 end_ = pos;
273 return after;
274}
275
276void LifetimePosition::Print() const { StdoutStream{} << *this << std::endl; }
277
278std::ostream& operator<<(std::ostream& os, const LifetimePosition pos) {
279 os << '@' << pos.ToInstructionIndex();
280 if (pos.IsGapPosition()) {
281 os << 'g';
282 } else {
283 os << 'i';
284 }
285 if (pos.IsStart()) {
286 os << 's';
287 } else {
288 os << 'e';
289 }
290 return os;
291}
292
293LiveRange::LiveRange(int relative_id, MachineRepresentation rep,
294 TopLevelLiveRange* top_level)
295 : relative_id_(relative_id),
296 bits_(0),
297 last_interval_(nullptr),
298 first_interval_(nullptr),
299 first_pos_(nullptr),
300 top_level_(top_level),
301 next_(nullptr),
302 current_interval_(nullptr),
303 last_processed_use_(nullptr),
304 current_hint_position_(nullptr) {
305 DCHECK(AllocatedOperand::IsSupportedRepresentation(rep))((void) 0);
306 bits_ = AssignedRegisterField::encode(kUnassignedRegister) |
307 RepresentationField::encode(rep) |
308 ControlFlowRegisterHint::encode(kUnassignedRegister);
309}
310
311void LiveRange::VerifyPositions() const {
312 // Walk the positions, verifying that each is in an interval.
313 UseInterval* interval = first_interval_;
314 for (UsePosition* pos = first_pos_; pos != nullptr; pos = pos->next()) {
315 CHECK(Start() <= pos->pos())do { if ((__builtin_expect(!!(!(Start() <= pos->pos()))
, 0))) { V8_Fatal("Check failed: %s.", "Start() <= pos->pos()"
); } } while (false)
;
316 CHECK(pos->pos() <= End())do { if ((__builtin_expect(!!(!(pos->pos() <= End())), 0
))) { V8_Fatal("Check failed: %s.", "pos->pos() <= End()"
); } } while (false)
;
317 CHECK_NOT_NULL(interval)do { if ((__builtin_expect(!!(!((interval) != nullptr)), 0)))
{ V8_Fatal("Check failed: %s.", "(interval) != nullptr"); } }
while (false)
;
318 while (!interval->Contains(pos->pos()) && interval->end() != pos->pos()) {
319 interval = interval->next();
320 CHECK_NOT_NULL(interval)do { if ((__builtin_expect(!!(!((interval) != nullptr)), 0)))
{ V8_Fatal("Check failed: %s.", "(interval) != nullptr"); } }
while (false)
;
321 }
322 }
323}
324
325void LiveRange::VerifyIntervals() const {
326 DCHECK(first_interval()->start() == Start())((void) 0);
327 LifetimePosition last_end = first_interval()->end();
328 for (UseInterval* interval = first_interval()->next(); interval != nullptr;
329 interval = interval->next()) {
330 DCHECK(last_end <= interval->start())((void) 0);
331 last_end = interval->end();
332 }
333 DCHECK(last_end == End())((void) 0);
334}
335
336void LiveRange::set_assigned_register(int reg) {
337 DCHECK(!HasRegisterAssigned() && !spilled())((void) 0);
338 bits_ = AssignedRegisterField::update(bits_, reg);
339}
340
341void LiveRange::UnsetAssignedRegister() {
342 DCHECK(HasRegisterAssigned() && !spilled())((void) 0);
343 bits_ = AssignedRegisterField::update(bits_, kUnassignedRegister);
344}
345
346void LiveRange::AttachToNext() {
347 DCHECK_NOT_NULL(next_)((void) 0);
348 DCHECK_NE(TopLevel()->last_child_covers_, next_)((void) 0);
349 last_interval_->set_next(next_->first_interval());
350 next_->first_interval_ = nullptr;
351 last_interval_ = next_->last_interval_;
352 next_->last_interval_ = nullptr;
353 if (first_pos() == nullptr) {
354 first_pos_ = next_->first_pos();
355 } else {
356 UsePosition* ptr = first_pos_;
357 while (ptr->next() != nullptr) {
358 ptr = ptr->next();
359 }
360 ptr->set_next(next_->first_pos());
361 }
362 next_->first_pos_ = nullptr;
363 LiveRange* old_next = next_;
364 next_ = next_->next_;
365 old_next->next_ = nullptr;
366}
367
368void LiveRange::Unspill() {
369 DCHECK(spilled())((void) 0);
370 set_spilled(false);
371 bits_ = AssignedRegisterField::update(bits_, kUnassignedRegister);
372}
373
374void LiveRange::Spill() {
375 DCHECK(!spilled())((void) 0);
376 DCHECK(!TopLevel()->HasNoSpillType())((void) 0);
377 set_spilled(true);
378 bits_ = AssignedRegisterField::update(bits_, kUnassignedRegister);
379}
380
381RegisterKind LiveRange::kind() const {
382 if (kFPAliasing == AliasingKind::kIndependent &&
383 IsSimd128(representation())) {
384 return RegisterKind::kSimd128;
385 } else {
386 return IsFloatingPoint(representation()) ? RegisterKind::kDouble
387 : RegisterKind::kGeneral;
388 }
389}
390
391UsePosition* LiveRange::FirstHintPosition(int* register_index) {
392 if (!first_pos_) return nullptr;
393 if (current_hint_position_) {
394 if (current_hint_position_->pos() < first_pos_->pos()) {
395 current_hint_position_ = first_pos_;
396 }
397 if (current_hint_position_->pos() > End()) {
398 current_hint_position_ = nullptr;
399 }
400 }
401 bool needs_revisit = false;
402 UsePosition* pos = current_hint_position_;
403 for (; pos != nullptr; pos = pos->next()) {
404 if (pos->HintRegister(register_index)) {
405 break;
406 }
407 // Phi and use position hints can be assigned during allocation which
408 // would invalidate the cached hint position. Make sure we revisit them.
409 needs_revisit = needs_revisit ||
410 pos->hint_type() == UsePositionHintType::kPhi ||
411 pos->hint_type() == UsePositionHintType::kUsePos;
412 }
413 if (!needs_revisit) {
414 current_hint_position_ = pos;
415 }
416#ifdef DEBUG
417 UsePosition* pos_check = first_pos_;
418 for (; pos_check != nullptr; pos_check = pos_check->next()) {
419 if (pos_check->HasHint()) {
420 break;
421 }
422 }
423 CHECK_EQ(pos, pos_check)do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(pos)>::type, typename ::v8
::base::pass_value_or_ref<decltype(pos_check)>::type>
((pos), (pos_check)); do { if ((__builtin_expect(!!(!(_cmp)),
0))) { V8_Fatal("Check failed: %s.", "pos" " " "==" " " "pos_check"
); } } while (false); } while (false)
;
424#endif
425 return pos;
426}
427
428UsePosition* LiveRange::NextUsePosition(LifetimePosition start) const {
429 UsePosition* use_pos = last_processed_use_;
430 if (use_pos == nullptr || use_pos->pos() > start) {
431 use_pos = first_pos();
432 }
433 while (use_pos != nullptr && use_pos->pos() < start) {
434 use_pos = use_pos->next();
435 }
436 last_processed_use_ = use_pos;
437 return use_pos;
438}
439
440UsePosition* LiveRange::NextUsePositionRegisterIsBeneficial(
441 LifetimePosition start) const {
442 UsePosition* pos = NextUsePosition(start);
443 while (pos != nullptr && !pos->RegisterIsBeneficial()) {
444 pos = pos->next();
445 }
446 return pos;
447}
448
449LifetimePosition LiveRange::NextLifetimePositionRegisterIsBeneficial(
450 const LifetimePosition& start) const {
451 UsePosition* next_use = NextUsePositionRegisterIsBeneficial(start);
452 if (next_use == nullptr) return End();
453 return next_use->pos();
454}
455
456UsePosition* LiveRange::PreviousUsePositionRegisterIsBeneficial(
457 LifetimePosition start) const {
458 UsePosition* pos = first_pos();
459 UsePosition* prev = nullptr;
460 while (pos != nullptr && pos->pos() < start) {
461 if (pos->RegisterIsBeneficial()) prev = pos;
462 pos = pos->next();
463 }
464 return prev;
465}
466
467UsePosition* LiveRange::NextUsePositionSpillDetrimental(
468 LifetimePosition start) const {
469 UsePosition* pos = NextUsePosition(start);
470 while (pos != nullptr && pos->type() != UsePositionType::kRequiresRegister &&
471 !pos->SpillDetrimental()) {
472 pos = pos->next();
473 }
474 return pos;
475}
476
477UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) const {
478 UsePosition* pos = NextUsePosition(start);
479 while (pos != nullptr && pos->type() != UsePositionType::kRequiresRegister) {
480 pos = pos->next();
481 }
482 return pos;
483}
484
485bool LiveRange::CanBeSpilled(LifetimePosition pos) const {
486 // We cannot spill a live range that has a use requiring a register
487 // at the current or the immediate next position.
488 UsePosition* use_pos = NextRegisterPosition(pos);
489 if (use_pos == nullptr) return true;
490 return use_pos->pos() > pos.NextStart().End();
491}
492
493bool LiveRange::IsTopLevel() const { return top_level_ == this; }
494
495InstructionOperand LiveRange::GetAssignedOperand() const {
496 DCHECK(!IsEmpty())((void) 0);
497 if (HasRegisterAssigned()) {
498 DCHECK(!spilled())((void) 0);
499 return AllocatedOperand(LocationOperand::REGISTER, representation(),
500 assigned_register());
501 }
502 DCHECK(spilled())((void) 0);
503 DCHECK(!HasRegisterAssigned())((void) 0);
504 if (TopLevel()->HasSpillOperand()) {
505 InstructionOperand* op = TopLevel()->GetSpillOperand();
506 DCHECK(!op->IsUnallocated())((void) 0);
507 return *op;
508 }
509 return TopLevel()->GetSpillRangeOperand();
510}
511
512UseInterval* LiveRange::FirstSearchIntervalForPosition(
513 LifetimePosition position) const {
514 if (current_interval_ == nullptr) return first_interval_;
515 if (current_interval_->start() > position) {
516 current_interval_ = nullptr;
517 return first_interval_;
518 }
519 return current_interval_;
520}
521
522void LiveRange::AdvanceLastProcessedMarker(
523 UseInterval* to_start_of, LifetimePosition but_not_past) const {
524 if (to_start_of == nullptr) return;
525 if (to_start_of->start() > but_not_past) return;
526 LifetimePosition start = current_interval_ == nullptr
527 ? LifetimePosition::Invalid()
528 : current_interval_->start();
529 if (to_start_of->start() > start) {
530 current_interval_ = to_start_of;
531 }
532}
533
534LiveRange* LiveRange::SplitAt(LifetimePosition position, Zone* zone) {
535 int new_id = TopLevel()->GetNextChildId();
536 LiveRange* child = zone->New<LiveRange>(new_id, representation(), TopLevel());
537 child->set_bundle(bundle_);
538 // If we split, we do so because we're about to switch registers or move
539 // to/from a slot, so there's no value in connecting hints.
540 DetachAt(position, child, zone, DoNotConnectHints);
541
542 child->top_level_ = TopLevel();
543 child->next_ = next_;
544 next_ = child;
545 return child;
546}
547
548UsePosition* LiveRange::DetachAt(LifetimePosition position, LiveRange* result,
549 Zone* zone,
550 HintConnectionOption connect_hints) {
551 DCHECK(Start() < position)((void) 0);
552 DCHECK(End() > position)((void) 0);
553 DCHECK(result->IsEmpty())((void) 0);
554 // Find the last interval that ends before the position. If the
555 // position is contained in one of the intervals in the chain, we
556 // split that interval and use the first part.
557 UseInterval* current = FirstSearchIntervalForPosition(position);
558
559 // If the split position coincides with the beginning of a use interval
560 // we need to split use positons in a special way.
561 bool split_at_start = false;
562
563 if (current->start() == position) {
564 // When splitting at start we need to locate the previous use interval.
565 current = first_interval_;
566 }
567
568 UseInterval* after = nullptr;
569 while (current != nullptr) {
570 if (current->Contains(position)) {
571 after = current->SplitAt(position, zone);
572 break;
573 }
574 UseInterval* next = current->next();
575 if (next->start() >= position) {
576 split_at_start = (next->start() == position);
577 after = next;
578 current->set_next(nullptr);
579 break;
580 }
581 current = next;
582 }
583 DCHECK_NOT_NULL(after)((void) 0);
584
585 // Partition original use intervals to the two live ranges.
586 UseInterval* before = current;
587 result->last_interval_ =
588 (last_interval_ == before)
589 ? after // Only interval in the range after split.
590 : last_interval_; // Last interval of the original range.
591 result->first_interval_ = after;
592 last_interval_ = before;
593
594 // Find the last use position before the split and the first use
595 // position after it.
596 UsePosition* use_after = first_pos();
597 UsePosition* use_before = nullptr;
598 if (split_at_start) {
599 // The split position coincides with the beginning of a use interval (the
600 // end of a lifetime hole). Use at this position should be attributed to
601 // the split child because split child owns use interval covering it.
602 while (use_after != nullptr && use_after->pos() < position) {
603 use_before = use_after;
604 use_after = use_after->next();
605 }
606 } else {
607 while (use_after != nullptr && use_after->pos() <= position) {
608 use_before = use_after;
609 use_after = use_after->next();
610 }
611 }
612
613 // Partition original use positions to the two live ranges.
614 if (use_before != nullptr) {
615 use_before->set_next(nullptr);
616 } else {
617 first_pos_ = nullptr;
618 }
619 result->first_pos_ = use_after;
620 result->current_hint_position_ = current_hint_position_;
621
622 // Discard cached iteration state. It might be pointing
623 // to the use that no longer belongs to this live range.
624 last_processed_use_ = nullptr;
625 current_interval_ = nullptr;
626
627 if (connect_hints == ConnectHints && use_before != nullptr &&
628 use_after != nullptr) {
629 use_after->SetHint(use_before);
630 result->current_hint_position_ = use_after;
631 }
632#ifdef DEBUG
633 VerifyChildStructure();
634 result->VerifyChildStructure();
635#endif
636 return use_before;
637}
638
639void LiveRange::UpdateParentForAllChildren(TopLevelLiveRange* new_top_level) {
640 LiveRange* child = this;
641 for (; child != nullptr; child = child->next()) {
642 child->top_level_ = new_top_level;
643 }
644}
645
646void LiveRange::ConvertUsesToOperand(const InstructionOperand& op,
647 const InstructionOperand& spill_op) {
648 for (UsePosition* pos = first_pos(); pos != nullptr; pos = pos->next()) {
649 DCHECK(Start() <= pos->pos() && pos->pos() <= End())((void) 0);
650 if (!pos->HasOperand()) continue;
651 switch (pos->type()) {
652 case UsePositionType::kRequiresSlot:
653 DCHECK(spill_op.IsStackSlot() || spill_op.IsFPStackSlot())((void) 0);
654 InstructionOperand::ReplaceWith(pos->operand(), &spill_op);
655 break;
656 case UsePositionType::kRequiresRegister:
657 DCHECK(op.IsRegister() || op.IsFPRegister())((void) 0);
658 V8_FALLTHROUGH[[clang::fallthrough]];
659 case UsePositionType::kRegisterOrSlot:
660 case UsePositionType::kRegisterOrSlotOrConstant:
661 InstructionOperand::ReplaceWith(pos->operand(), &op);
662 break;
663 }
664 }
665}
666
667// This implements an ordering on live ranges so that they are ordered by their
668// start positions. This is needed for the correctness of the register
669// allocation algorithm. If two live ranges start at the same offset then there
670// is a tie breaker based on where the value is first used. This part of the
671// ordering is merely a heuristic.
672bool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const {
673 LifetimePosition start = Start();
674 LifetimePosition other_start = other->Start();
675 if (start == other_start) {
676 // Prefer register that has a controlflow hint to make sure it gets
677 // allocated first. This allows the control flow aware alloction to
678 // just put ranges back into the queue without other ranges interfering.
679 if (controlflow_hint() < other->controlflow_hint()) {
680 return true;
681 }
682 // The other has a smaller hint.
683 if (controlflow_hint() > other->controlflow_hint()) {
684 return false;
685 }
686 // Both have the same hint or no hint at all. Use first use position.
687 UsePosition* pos = first_pos();
688 UsePosition* other_pos = other->first_pos();
689 // To make the order total, handle the case where both positions are null.
690 if (pos == other_pos) return TopLevel()->vreg() < other->TopLevel()->vreg();
691 if (pos == nullptr) return false;
692 if (other_pos == nullptr) return true;
693 // To make the order total, handle the case where both positions are equal.
694 if (pos->pos() == other_pos->pos())
695 return TopLevel()->vreg() < other->TopLevel()->vreg();
696 return pos->pos() < other_pos->pos();
697 }
698 return start < other_start;
699}
700
701void LiveRange::SetUseHints(int register_index) {
702 for (UsePosition* pos = first_pos(); pos != nullptr; pos = pos->next()) {
703 if (!pos->HasOperand()) continue;
704 switch (pos->type()) {
705 case UsePositionType::kRequiresSlot:
706 break;
707 case UsePositionType::kRequiresRegister:
708 case UsePositionType::kRegisterOrSlot:
709 case UsePositionType::kRegisterOrSlotOrConstant:
710 pos->set_assigned_register(register_index);
711 break;
712 }
713 }
714}
715
716bool LiveRange::CanCover(LifetimePosition position) const {
717 if (IsEmpty()) return false;
718 return Start() <= position && position < End();
719}
720
721bool LiveRange::Covers(LifetimePosition position) const {
722 if (!CanCover(position)) return false;
723 UseInterval* start_search = FirstSearchIntervalForPosition(position);
724 for (UseInterval* interval = start_search; interval != nullptr;
725 interval = interval->next()) {
726 DCHECK(interval->next() == nullptr ||((void) 0)
727 interval->next()->start() >= interval->start())((void) 0);
728 AdvanceLastProcessedMarker(interval, position);
729 if (interval->Contains(position)) return true;
730 if (interval->start() > position) return false;
731 }
732 return false;
733}
734
735LifetimePosition LiveRange::NextEndAfter(LifetimePosition position) const {
736 UseInterval* start_search = FirstSearchIntervalForPosition(position);
737 while (start_search->end() < position) {
738 start_search = start_search->next();
739 }
740 return start_search->end();
741}
742
743LifetimePosition LiveRange::NextStartAfter(LifetimePosition position) {
744 UseInterval* start_search = FirstSearchIntervalForPosition(position);
745 while (start_search->start() < position) {
746 start_search = start_search->next();
747 }
748 next_start_ = start_search->start();
749 return next_start_;
750}
751
752LifetimePosition LiveRange::FirstIntersection(LiveRange* other) const {
753 UseInterval* b = other->first_interval();
754 if (b == nullptr) return LifetimePosition::Invalid();
755 LifetimePosition advance_last_processed_up_to = b->start();
756 UseInterval* a = FirstSearchIntervalForPosition(b->start());
757 while (a != nullptr && b != nullptr) {
758 if (a->start() > other->End()) break;
759 if (b->start() > End()) break;
760 LifetimePosition cur_intersection = a->Intersect(b);
761 if (cur_intersection.IsValid()) {
762 return cur_intersection;
763 }
764 if (a->start() < b->start()) {
765 a = a->next();
766 if (a == nullptr || a->start() > other->End()) break;
767 AdvanceLastProcessedMarker(a, advance_last_processed_up_to);
768 } else {
769 b = b->next();
770 }
771 }
772 return LifetimePosition::Invalid();
773}
774
775void LiveRange::Print(const RegisterConfiguration* config,
776 bool with_children) const {
777 StdoutStream os;
778 PrintableLiveRange wrapper;
779 wrapper.register_configuration_ = config;
780 for (const LiveRange* i = this; i != nullptr; i = i->next()) {
781 wrapper.range_ = i;
782 os << wrapper << std::endl;
783 if (!with_children) break;
784 }
785}
786
787void LiveRange::Print(bool with_children) const {
788 Print(RegisterConfiguration::Default(), with_children);
789}
790
791bool LiveRange::RegisterFromBundle(int* hint) const {
792 if (bundle_ == nullptr || bundle_->reg() == kUnassignedRegister) return false;
793 *hint = bundle_->reg();
794 return true;
795}
796
797void LiveRange::UpdateBundleRegister(int reg) const {
798 if (bundle_ == nullptr || bundle_->reg() != kUnassignedRegister) return;
799 bundle_->set_reg(reg);
800}
801
802struct TopLevelLiveRange::SpillMoveInsertionList : ZoneObject {
803 SpillMoveInsertionList(int gap_index, InstructionOperand* operand,
804 SpillMoveInsertionList* next)
805 : gap_index(gap_index), operand(operand), next(next) {}
806 const int gap_index;
807 InstructionOperand* const operand;
808 SpillMoveInsertionList* next;
809};
810
811TopLevelLiveRange::TopLevelLiveRange(int vreg, MachineRepresentation rep)
812 : LiveRange(0, rep, this),
813 vreg_(vreg),
814 last_child_id_(0),
815 spill_operand_(nullptr),
816 spill_move_insertion_locations_(nullptr),
817 spilled_in_deferred_blocks_(false),
818 has_preassigned_slot_(false),
819 spill_start_index_(kMaxInt),
820 last_pos_(nullptr),
821 last_child_covers_(this) {
822 bits_ |= SpillTypeField::encode(SpillType::kNoSpillType);
823}
824
825void TopLevelLiveRange::RecordSpillLocation(Zone* zone, int gap_index,
826 InstructionOperand* operand) {
827 DCHECK(HasNoSpillType())((void) 0);
828 spill_move_insertion_locations_ = zone->New<SpillMoveInsertionList>(
829 gap_index, operand, spill_move_insertion_locations_);
830}
831
832void TopLevelLiveRange::CommitSpillMoves(TopTierRegisterAllocationData* data,
833 const InstructionOperand& op) {
834 DCHECK_IMPLIES(op.IsConstant(),((void) 0)
835 GetSpillMoveInsertionLocations(data) == nullptr)((void) 0);
836
837 if (HasGeneralSpillRange()) {
838 SetLateSpillingSelected(false);
839 }
840
841 InstructionSequence* sequence = data->code();
842 Zone* zone = sequence->zone();
843
844 for (SpillMoveInsertionList* to_spill = GetSpillMoveInsertionLocations(data);
845 to_spill != nullptr; to_spill = to_spill->next) {
846 Instruction* instr = sequence->InstructionAt(to_spill->gap_index);
847 ParallelMove* move =
848 instr->GetOrCreateParallelMove(Instruction::START, zone);
849 move->AddMove(*to_spill->operand, op);
850 instr->block()->mark_needs_frame();
851 }
852}
853
854void TopLevelLiveRange::FilterSpillMoves(TopTierRegisterAllocationData* data,
855 const InstructionOperand& op) {
856 DCHECK_IMPLIES(op.IsConstant(),((void) 0)
857 GetSpillMoveInsertionLocations(data) == nullptr)((void) 0);
858 bool might_be_duplicated = has_slot_use() || spilled();
859 InstructionSequence* sequence = data->code();
860
861 SpillMoveInsertionList* previous = nullptr;
862 for (SpillMoveInsertionList* to_spill = GetSpillMoveInsertionLocations(data);
863 to_spill != nullptr; previous = to_spill, to_spill = to_spill->next) {
864 Instruction* instr = sequence->InstructionAt(to_spill->gap_index);
865 ParallelMove* move = instr->GetParallelMove(Instruction::START);
866 // Skip insertion if it's possible that the move exists already as a
867 // constraint move from a fixed output register to a slot.
868 bool found = false;
869 if (move != nullptr && (might_be_duplicated || has_preassigned_slot())) {
870 for (MoveOperands* move_op : *move) {
871 if (move_op->IsEliminated()) continue;
872 if (move_op->source().Equals(*to_spill->operand) &&
873 move_op->destination().Equals(op)) {
874 found = true;
875 if (has_preassigned_slot()) move_op->Eliminate();
876 break;
877 }
878 }
879 }
880 if (found || has_preassigned_slot()) {
881 // Remove the item from the list.
882 if (previous == nullptr) {
883 spill_move_insertion_locations_ = to_spill->next;
884 } else {
885 previous->next = to_spill->next;
886 }
887 // Even though this location doesn't need a spill instruction, the
888 // block does require a frame.
889 instr->block()->mark_needs_frame();
890 }
891 }
892}
893
894void TopLevelLiveRange::SetSpillOperand(InstructionOperand* operand) {
895 DCHECK(HasNoSpillType())((void) 0);
896 DCHECK(!operand->IsUnallocated() && !operand->IsImmediate())((void) 0);
897 set_spill_type(SpillType::kSpillOperand);
898 spill_operand_ = operand;
899}
900
901void TopLevelLiveRange::SetSpillRange(SpillRange* spill_range) {
902 DCHECK(!HasSpillOperand())((void) 0);
903 DCHECK(spill_range)((void) 0);
904 spill_range_ = spill_range;
905}
906
907AllocatedOperand TopLevelLiveRange::GetSpillRangeOperand() const {
908 SpillRange* spill_range = GetSpillRange();
909 int index = spill_range->assigned_slot();
910 return AllocatedOperand(LocationOperand::STACK_SLOT, representation(), index);
911}
912
913void TopLevelLiveRange::VerifyChildrenInOrder() const {
914 LifetimePosition last_end = End();
915 for (const LiveRange* child = this->next(); child != nullptr;
916 child = child->next()) {
917 DCHECK(last_end <= child->Start())((void) 0);
918 last_end = child->End();
919 }
920}
921
922LiveRange* TopLevelLiveRange::GetChildCovers(LifetimePosition pos) {
923 LiveRange* child = last_child_covers_;
924 DCHECK_NE(child, nullptr)((void) 0);
925 if (pos < child->Start()) {
926 // Cached value has advanced too far; start from the top.
927 child = this;
928 }
929 LiveRange* previous_child = nullptr;
930 while (child != nullptr && child->End() <= pos) {
931 previous_child = child;
932 child = child->next();
933 }
934
935 // If we've walked past the end, cache the last child instead. This allows
936 // future calls that are also past the end to be fast, since they will know
937 // that there is no need to reset the search to the beginning.
938 last_child_covers_ = child == nullptr ? previous_child : child;
939
940 return !child || !child->Covers(pos) ? nullptr : child;
941}
942
943void TopLevelLiveRange::Verify() const {
944 VerifyChildrenInOrder();
945 for (const LiveRange* child = this; child != nullptr; child = child->next()) {
946 VerifyChildStructure();
947 }
948}
949
950void TopLevelLiveRange::ShortenTo(LifetimePosition start, bool trace_alloc) {
951 TRACE_COND(trace_alloc, "Shorten live range %d to [%d\n", vreg(),
952 start.value());
953 DCHECK_NOT_NULL(first_interval_)((void) 0);
954 DCHECK(first_interval_->start() <= start)((void) 0);
955 DCHECK(start < first_interval_->end())((void) 0);
956 first_interval_->set_start(start);
957}
958
959void TopLevelLiveRange::EnsureInterval(LifetimePosition start,
960 LifetimePosition end, Zone* zone,
961 bool trace_alloc) {
962 TRACE_COND(trace_alloc, "Ensure live range %d in interval [%d %d[\n", vreg(),
963 start.value(), end.value());
964 LifetimePosition new_end = end;
965 while (first_interval_ != nullptr && first_interval_->start() <= end) {
966 if (first_interval_->end() > end) {
967 new_end = first_interval_->end();
968 }
969 first_interval_ = first_interval_->next();
970 }
971
972 UseInterval* new_interval = zone->New<UseInterval>(start, new_end);
973 new_interval->set_next(first_interval_);
974 first_interval_ = new_interval;
975 if (new_interval->next() == nullptr) {
976 last_interval_ = new_interval;
977 }
978}
979
980void TopLevelLiveRange::AddUseInterval(LifetimePosition start,
981 LifetimePosition end, Zone* zone,
982 bool trace_alloc) {
983 TRACE_COND(trace_alloc, "Add to live range %d interval [%d %d[\n", vreg(),
984 start.value(), end.value());
985 if (first_interval_ == nullptr) {
986 UseInterval* interval = zone->New<UseInterval>(start, end);
987 first_interval_ = interval;
988 last_interval_ = interval;
989 } else {
990 if (end == first_interval_->start()) {
991 first_interval_->set_start(start);
992 } else if (end < first_interval_->start()) {
993 UseInterval* interval = zone->New<UseInterval>(start, end);
994 interval->set_next(first_interval_);
995 first_interval_ = interval;
996 } else {
997 // Order of instruction's processing (see ProcessInstructions) guarantees
998 // that each new use interval either precedes, intersects with or touches
999 // the last added interval.
1000 DCHECK(start <= first_interval_->end())((void) 0);
1001 first_interval_->set_start(std::min(start, first_interval_->start()));
1002 first_interval_->set_end(std::max(end, first_interval_->end()));
1003 }
1004 }
1005}
1006
1007void TopLevelLiveRange::AddUsePosition(UsePosition* use_pos, bool trace_alloc) {
1008 LifetimePosition pos = use_pos->pos();
1009 TRACE_COND(trace_alloc, "Add to live range %d use position %d\n", vreg(),
1010 pos.value());
1011 UsePosition* prev_hint = nullptr;
1012 UsePosition* prev = nullptr;
1013 UsePosition* current = first_pos_;
1014 while (current != nullptr && current->pos() < pos) {
1015 prev_hint = current->HasHint() ? current : prev_hint;
1016 prev = current;
1017 current = current->next();
1018 }
1019
1020 if (prev == nullptr) {
1021 use_pos->set_next(first_pos_);
1022 first_pos_ = use_pos;
1023 } else {
1024 use_pos->set_next(prev->next());
1025 prev->set_next(use_pos);
1026 }
1027
1028 if (prev_hint == nullptr && use_pos->HasHint()) {
1029 current_hint_position_ = use_pos;
1030 }
1031}
1032
1033static bool AreUseIntervalsIntersecting(UseInterval* interval1,
1034 UseInterval* interval2) {
1035 while (interval1 != nullptr && interval2 != nullptr) {
1036 if (interval1->start() < interval2->start()) {
1037 if (interval1->end() > interval2->start()) {
1038 return true;
1039 }
1040 interval1 = interval1->next();
1041 } else {
1042 if (interval2->end() > interval1->start()) {
1043 return true;
1044 }
1045 interval2 = interval2->next();
1046 }
1047 }
1048 return false;
1049}
1050
1051std::ostream& operator<<(std::ostream& os,
1052 const PrintableLiveRange& printable_range) {
1053 const LiveRange* range = printable_range.range_;
1054 os << "Range: " << range->TopLevel()->vreg() << ":" << range->relative_id()
1055 << " ";
1056 if (range->TopLevel()->is_phi()) os << "phi ";
1057 if (range->TopLevel()->is_non_loop_phi()) os << "nlphi ";
1058
1059 os << "{" << std::endl;
1060 UseInterval* interval = range->first_interval();
1061 UsePosition* use_pos = range->first_pos();
1062 while (use_pos != nullptr) {
1063 if (use_pos->HasOperand()) {
1064 os << *use_pos->operand() << use_pos->pos() << " ";
1065 }
1066 use_pos = use_pos->next();
1067 }
1068 os << std::endl;
1069
1070 while (interval != nullptr) {
1071 os << '[' << interval->start() << ", " << interval->end() << ')'
1072 << std::endl;
1073 interval = interval->next();
1074 }
1075 os << "}";
1076 return os;
1077}
1078
1079namespace {
1080void PrintBlockRow(std::ostream& os, const InstructionBlocks& blocks) {
1081 os << " ";
1082 for (auto block : blocks) {
1083 LifetimePosition start_pos = LifetimePosition::GapFromInstructionIndex(
1084 block->first_instruction_index());
1085 LifetimePosition end_pos = LifetimePosition::GapFromInstructionIndex(
1086 block->last_instruction_index())
1087 .NextFullStart();
1088 int length = end_pos.value() - start_pos.value();
1089 constexpr int kMaxPrefixLength = 32;
1090 char buffer[kMaxPrefixLength];
1091 int rpo_number = block->rpo_number().ToInt();
1092 const char* deferred_marker = block->IsDeferred() ? "(deferred)" : "";
1093 int max_prefix_length = std::min(length, kMaxPrefixLength);
1094 int prefix = snprintf(buffer, max_prefix_length, "[-B%d-%s", rpo_number,
1095 deferred_marker);
1096 os << buffer;
1097 int remaining = length - std::min(prefix, max_prefix_length) - 1;
1098 for (int i = 0; i < remaining; ++i) os << '-';
1099 os << ']';
1100 }
1101 os << '\n';
1102}
1103} // namespace
1104
1105void LinearScanAllocator::PrintRangeRow(std::ostream& os,
1106 const TopLevelLiveRange* toplevel) {
1107 int position = 0;
1108 os << std::setw(3) << toplevel->vreg() << ": ";
1109
1110 const char* kind_string;
1111 switch (toplevel->spill_type()) {
1112 case TopLevelLiveRange::SpillType::kSpillRange:
1113 kind_string = "ss";
1114 break;
1115 case TopLevelLiveRange::SpillType::kDeferredSpillRange:
1116 kind_string = "sd";
1117 break;
1118 case TopLevelLiveRange::SpillType::kSpillOperand:
1119 kind_string = "so";
1120 break;
1121 default:
1122 kind_string = "s?";
1123 }
1124
1125 for (const LiveRange* range = toplevel; range != nullptr;
1126 range = range->next()) {
1127 for (UseInterval* interval = range->first_interval(); interval != nullptr;
1128 interval = interval->next()) {
1129 LifetimePosition start = interval->start();
1130 LifetimePosition end = interval->end();
1131 CHECK_GE(start.value(), position)do { bool _cmp = ::v8::base::CmpGEImpl< typename ::v8::base
::pass_value_or_ref<decltype(start.value())>::type, typename
::v8::base::pass_value_or_ref<decltype(position)>::type
>((start.value()), (position)); do { if ((__builtin_expect
(!!(!(_cmp)), 0))) { V8_Fatal("Check failed: %s.", "start.value()"
" " ">=" " " "position"); } } while (false); } while (false
)
;
1132 for (; start.value() > position; position++) {
1133 os << ' ';
1134 }
1135 int length = end.value() - start.value();
1136 constexpr int kMaxPrefixLength = 32;
1137 char buffer[kMaxPrefixLength];
1138 int max_prefix_length = std::min(length + 1, kMaxPrefixLength);
1139 int prefix;
1140 if (range->spilled()) {
1141 prefix = snprintf(buffer, max_prefix_length, "|%s", kind_string);
1142 } else {
1143 prefix = snprintf(buffer, max_prefix_length, "|%s",
1144 RegisterName(range->assigned_register()));
1145 }
1146 os << buffer;
1147 position += std::min(prefix, max_prefix_length - 1);
1148 CHECK_GE(end.value(), position)do { bool _cmp = ::v8::base::CmpGEImpl< typename ::v8::base
::pass_value_or_ref<decltype(end.value())>::type, typename
::v8::base::pass_value_or_ref<decltype(position)>::type
>((end.value()), (position)); do { if ((__builtin_expect(!
!(!(_cmp)), 0))) { V8_Fatal("Check failed: %s.", "end.value()"
" " ">=" " " "position"); } } while (false); } while (false
)
;
1149 const char line_style = range->spilled() ? '-' : '=';
1150 for (; end.value() > position; position++) {
1151 os << line_style;
1152 }
1153 }
1154 }
1155 os << '\n';
1156}
1157
1158void LinearScanAllocator::PrintRangeOverview() {
1159 std::ostringstream os;
1160 PrintBlockRow(os, code()->instruction_blocks());
1161 for (auto const toplevel : data()->fixed_live_ranges()) {
1162 if (toplevel == nullptr) continue;
1163 PrintRangeRow(os, toplevel);
1164 }
1165 int rowcount = 0;
1166 for (auto toplevel : data()->live_ranges()) {
1167 if (!CanProcessRange(toplevel)) continue;
1168 if (rowcount++ % 10 == 0) PrintBlockRow(os, code()->instruction_blocks());
1169 PrintRangeRow(os, toplevel);
1170 }
1171 PrintF("%s\n", os.str().c_str());
1172}
1173
1174SpillRange::SpillRange(TopLevelLiveRange* parent, Zone* zone)
1175 : live_ranges_(zone),
1176 assigned_slot_(kUnassignedSlot),
1177 byte_width_(ByteWidthForStackSlot(parent->representation())) {
1178 // Spill ranges are created for top level. This is so that, when merging
1179 // decisions are made, we consider the full extent of the virtual register,
1180 // and avoid clobbering it.
1181 UseInterval* result = nullptr;
1182 UseInterval* node = nullptr;
9
'node' initialized to a null pointer value
1183 // Copy the intervals for all ranges.
1184 for (LiveRange* range = parent; range != nullptr; range = range->next()) {
10
Loop condition is true. Entering loop body
13
Assuming the condition is false
14
Loop condition is false. Execution continues on line 1197
1185 UseInterval* src = range->first_interval();
1186 while (src != nullptr) {
11
Assuming the condition is false
12
Loop condition is false. Execution continues on line 1184
1187 UseInterval* new_node = zone->New<UseInterval>(src->start(), src->end());
1188 if (result == nullptr) {
1189 result = new_node;
1190 } else {
1191 node->set_next(new_node);
1192 }
1193 node = new_node;
1194 src = src->next();
1195 }
1196 }
1197 use_interval_ = result;
1198 live_ranges().push_back(parent);
1199 end_position_ = node->end();
15
Called C++ object pointer is null
1200 parent->SetSpillRange(this);
1201}
1202
1203bool SpillRange::IsIntersectingWith(SpillRange* other) const {
1204 if (this->use_interval_ == nullptr || other->use_interval_ == nullptr ||
1205 this->End() <= other->use_interval_->start() ||
1206 other->End() <= this->use_interval_->start()) {
1207 return false;
1208 }
1209 return AreUseIntervalsIntersecting(use_interval_, other->use_interval_);
1210}
1211
1212bool SpillRange::TryMerge(SpillRange* other) {
1213 if (HasSlot() || other->HasSlot()) return false;
1214 if (byte_width() != other->byte_width() || IsIntersectingWith(other))
1215 return false;
1216
1217 LifetimePosition max = LifetimePosition::MaxPosition();
1218 if (End() < other->End() && other->End() != max) {
1219 end_position_ = other->End();
1220 }
1221 other->end_position_ = max;
1222
1223 MergeDisjointIntervals(other->use_interval_);
1224 other->use_interval_ = nullptr;
1225
1226 for (TopLevelLiveRange* range : other->live_ranges()) {
1227 DCHECK(range->GetSpillRange() == other)((void) 0);
1228 range->SetSpillRange(this);
1229 }
1230
1231 live_ranges().insert(live_ranges().end(), other->live_ranges().begin(),
1232 other->live_ranges().end());
1233 other->live_ranges().clear();
1234
1235 return true;
1236}
1237
1238void SpillRange::MergeDisjointIntervals(UseInterval* other) {
1239 UseInterval* tail = nullptr;
1240 UseInterval* current = use_interval_;
1241 while (other != nullptr) {
1242 // Make sure the 'current' list starts first
1243 if (current == nullptr || current->start() > other->start()) {
1244 std::swap(current, other);
1245 }
1246 // Check disjointness
1247 DCHECK(other == nullptr || current->end() <= other->start())((void) 0);
1248 // Append the 'current' node to the result accumulator and move forward
1249 if (tail == nullptr) {
1250 use_interval_ = current;
1251 } else {
1252 tail->set_next(current);
1253 }
1254 tail = current;
1255 current = current->next();
1256 }
1257 // Other list is empty => we are done
1258}
1259
1260void SpillRange::Print() const {
1261 StdoutStream os;
1262 os << "{" << std::endl;
1263 for (TopLevelLiveRange* range : live_ranges()) {
1264 os << range->vreg() << " ";
1265 }
1266 os << std::endl;
1267
1268 for (UseInterval* i = interval(); i != nullptr; i = i->next()) {
1269 os << '[' << i->start() << ", " << i->end() << ')' << std::endl;
1270 }
1271 os << "}" << std::endl;
1272}
1273
1274TopTierRegisterAllocationData::PhiMapValue::PhiMapValue(
1275 PhiInstruction* phi, const InstructionBlock* block, Zone* zone)
1276 : phi_(phi),
1277 block_(block),
1278 incoming_operands_(zone),
1279 assigned_register_(kUnassignedRegister) {
1280 incoming_operands_.reserve(phi->operands().size());
1281}
1282
1283void TopTierRegisterAllocationData::PhiMapValue::AddOperand(
1284 InstructionOperand* operand) {
1285 incoming_operands_.push_back(operand);
1286}
1287
1288void TopTierRegisterAllocationData::PhiMapValue::CommitAssignment(
1289 const InstructionOperand& assigned) {
1290 for (InstructionOperand* operand : incoming_operands_) {
1291 InstructionOperand::ReplaceWith(operand, &assigned);
1292 }
1293}
1294
1295TopTierRegisterAllocationData::TopTierRegisterAllocationData(
1296 const RegisterConfiguration* config, Zone* zone, Frame* frame,
1297 InstructionSequence* code, RegisterAllocationFlags flags,
1298 TickCounter* tick_counter, const char* debug_name)
1299 : RegisterAllocationData(Type::kTopTier),
1300 allocation_zone_(zone),
1301 frame_(frame),
1302 code_(code),
1303 debug_name_(debug_name),
1304 config_(config),
1305 phi_map_(allocation_zone()),
1306 live_in_sets_(code->InstructionBlockCount(), nullptr, allocation_zone()),
1307 live_out_sets_(code->InstructionBlockCount(), nullptr, allocation_zone()),
1308 live_ranges_(code->VirtualRegisterCount() * 2, nullptr,
1309 allocation_zone()),
1310 fixed_live_ranges_(kNumberOfFixedRangesPerRegister *
1311 this->config()->num_general_registers(),
1312 nullptr, allocation_zone()),
1313 fixed_float_live_ranges_(allocation_zone()),
1314 fixed_double_live_ranges_(kNumberOfFixedRangesPerRegister *
1315 this->config()->num_double_registers(),
1316 nullptr, allocation_zone()),
1317 fixed_simd128_live_ranges_(allocation_zone()),
1318 spill_ranges_(code->VirtualRegisterCount(), nullptr, allocation_zone()),
1319 delayed_references_(allocation_zone()),
1320 assigned_registers_(nullptr),
1321 assigned_double_registers_(nullptr),
1322 virtual_register_count_(code->VirtualRegisterCount()),
1323 preassigned_slot_ranges_(zone),
1324 spill_state_(code->InstructionBlockCount(), ZoneVector<LiveRange*>(zone),
1325 zone),
1326 flags_(flags),
1327 tick_counter_(tick_counter),
1328 slot_for_const_range_(zone) {
1329 if (kFPAliasing == AliasingKind::kCombine) {
1330 fixed_float_live_ranges_.resize(
1331 kNumberOfFixedRangesPerRegister * this->config()->num_float_registers(),
1332 nullptr);
1333 fixed_simd128_live_ranges_.resize(
1334 kNumberOfFixedRangesPerRegister *
1335 this->config()->num_simd128_registers(),
1336 nullptr);
1337 } else if (kFPAliasing == AliasingKind::kIndependent) {
1338 fixed_simd128_live_ranges_.resize(
1339 kNumberOfFixedRangesPerRegister *
1340 this->config()->num_simd128_registers(),
1341 nullptr);
1342 }
1343
1344 assigned_registers_ = code_zone()->New<BitVector>(
1345 this->config()->num_general_registers(), code_zone());
1346 assigned_double_registers_ = code_zone()->New<BitVector>(
1347 this->config()->num_double_registers(), code_zone());
1348 fixed_register_use_ = code_zone()->New<BitVector>(
1349 this->config()->num_general_registers(), code_zone());
1350 fixed_fp_register_use_ = code_zone()->New<BitVector>(
1351 this->config()->num_double_registers(), code_zone());
1352 if (kFPAliasing == AliasingKind::kIndependent) {
1353 assigned_simd128_registers_ = code_zone()->New<BitVector>(
1354 this->config()->num_simd128_registers(), code_zone());
1355 fixed_simd128_register_use_ = code_zone()->New<BitVector>(
1356 this->config()->num_simd128_registers(), code_zone());
1357 }
1358
1359 this->frame()->SetAllocatedRegisters(assigned_registers_);
1360 this->frame()->SetAllocatedDoubleRegisters(assigned_double_registers_);
1361}
1362
1363MoveOperands* TopTierRegisterAllocationData::AddGapMove(
1364 int index, Instruction::GapPosition position,
1365 const InstructionOperand& from, const InstructionOperand& to) {
1366 Instruction* instr = code()->InstructionAt(index);
1367 ParallelMove* moves = instr->GetOrCreateParallelMove(position, code_zone());
1368 return moves->AddMove(from, to);
1369}
1370
1371MachineRepresentation TopTierRegisterAllocationData::RepresentationFor(
1372 int virtual_register) {
1373 DCHECK_LT(virtual_register, code()->VirtualRegisterCount())((void) 0);
1374 return code()->GetRepresentation(virtual_register);
1375}
1376
1377TopLevelLiveRange* TopTierRegisterAllocationData::GetOrCreateLiveRangeFor(
1378 int index) {
1379 if (index >= static_cast<int>(live_ranges().size())) {
1380 live_ranges().resize(index + 1, nullptr);
1381 }
1382 TopLevelLiveRange* result = live_ranges()[index];
1383 if (result == nullptr) {
1384 result = NewLiveRange(index, RepresentationFor(index));
1385 live_ranges()[index] = result;
1386 }
1387 DCHECK_EQ(live_ranges()[index]->vreg(), index)((void) 0);
1388 return result;
1389}
1390
1391TopLevelLiveRange* TopTierRegisterAllocationData::NewLiveRange(
1392 int index, MachineRepresentation rep) {
1393 return allocation_zone()->New<TopLevelLiveRange>(index, rep);
1394}
1395
1396TopTierRegisterAllocationData::PhiMapValue*
1397TopTierRegisterAllocationData::InitializePhiMap(const InstructionBlock* block,
1398 PhiInstruction* phi) {
1399 TopTierRegisterAllocationData::PhiMapValue* map_value =
1400 allocation_zone()->New<TopTierRegisterAllocationData::PhiMapValue>(
1401 phi, block, allocation_zone());
1402 auto res =
1403 phi_map_.insert(std::make_pair(phi->virtual_register(), map_value));
1404 DCHECK(res.second)((void) 0);
1405 USE(res)do { ::v8::base::Use unused_tmp_array_for_use_macro[]{res}; (
void)unused_tmp_array_for_use_macro; } while (false)
;
1406 return map_value;
1407}
1408
1409TopTierRegisterAllocationData::PhiMapValue*
1410TopTierRegisterAllocationData::GetPhiMapValueFor(int virtual_register) {
1411 auto it = phi_map_.find(virtual_register);
1412 DCHECK(it != phi_map_.end())((void) 0);
1413 return it->second;
1414}
1415
1416TopTierRegisterAllocationData::PhiMapValue*
1417TopTierRegisterAllocationData::GetPhiMapValueFor(TopLevelLiveRange* top_range) {
1418 return GetPhiMapValueFor(top_range->vreg());
1419}
1420
1421bool TopTierRegisterAllocationData::ExistsUseWithoutDefinition() {
1422 bool found = false;
1423 for (int operand_index : *live_in_sets()[0]) {
1424 found = true;
1425 PrintF("Register allocator error: live v%d reached first block.\n",
1426 operand_index);
1427 LiveRange* range = GetOrCreateLiveRangeFor(operand_index);
1428 PrintF(" (first use is at %d)\n", range->first_pos()->pos().value());
1429 if (debug_name() == nullptr) {
1430 PrintF("\n");
1431 } else {
1432 PrintF(" (function: %s)\n", debug_name());
1433 }
1434 }
1435 return found;
1436}
1437
1438// If a range is defined in a deferred block, we can expect all the range
1439// to only cover positions in deferred blocks. Otherwise, a block on the
1440// hot path would be dominated by a deferred block, meaning it is unreachable
1441// without passing through the deferred block, which is contradictory.
1442// In particular, when such a range contributes a result back on the hot
1443// path, it will be as one of the inputs of a phi. In that case, the value
1444// will be transferred via a move in the Gap::END's of the last instruction
1445// of a deferred block.
1446bool TopTierRegisterAllocationData::RangesDefinedInDeferredStayInDeferred() {
1447 const size_t live_ranges_size = live_ranges().size();
1448 for (const TopLevelLiveRange* range : live_ranges()) {
1449 CHECK_EQ(live_ranges_size,do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(live_ranges().size
())>::type>((live_ranges_size), (live_ranges().size()))
; do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal("Check failed: %s."
, "live_ranges_size" " " "==" " " "live_ranges().size()"); } }
while (false); } while (false)
1450 live_ranges().size())do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(live_ranges().size
())>::type>((live_ranges_size), (live_ranges().size()))
; do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal("Check failed: %s."
, "live_ranges_size" " " "==" " " "live_ranges().size()"); } }
while (false); } while (false)
; // TODO(neis): crbug.com/831822
1451 if (range == nullptr || range->IsEmpty() ||
1452 !code()
1453 ->GetInstructionBlock(range->Start().ToInstructionIndex())
1454 ->IsDeferred()) {
1455 continue;
1456 }
1457 for (const UseInterval* i = range->first_interval(); i != nullptr;
1458 i = i->next()) {
1459 int first = i->FirstGapIndex();
1460 int last = i->LastGapIndex();
1461 for (int instr = first; instr <= last;) {
1462 const InstructionBlock* block = code()->GetInstructionBlock(instr);
1463 if (!block->IsDeferred()) return false;
1464 instr = block->last_instruction_index() + 1;
1465 }
1466 }
1467 }
1468 return true;
1469}
1470
1471SpillRange* TopTierRegisterAllocationData::AssignSpillRangeToLiveRange(
1472 TopLevelLiveRange* range, SpillMode spill_mode) {
1473 using SpillType = TopLevelLiveRange::SpillType;
1474 DCHECK(!range->HasSpillOperand())((void) 0);
1475
1476 SpillRange* spill_range = range->GetAllocatedSpillRange();
1477 if (spill_range == nullptr) {
5
Assuming the condition is true
6
Taking true branch
1478 spill_range = allocation_zone()->New<SpillRange>(range, allocation_zone());
7
Calling 'Zone::New'
1479 }
1480 if (spill_mode == SpillMode::kSpillDeferred &&
1481 (range->spill_type() != SpillType::kSpillRange)) {
1482 range->set_spill_type(SpillType::kDeferredSpillRange);
1483 } else {
1484 range->set_spill_type(SpillType::kSpillRange);
1485 }
1486
1487 spill_ranges()[range->vreg()] = spill_range;
1488 return spill_range;
1489}
1490
1491void TopTierRegisterAllocationData::MarkFixedUse(MachineRepresentation rep,
1492 int index) {
1493 switch (rep) {
1494 case MachineRepresentation::kFloat32:
1495 case MachineRepresentation::kSimd128:
1496 if (kFPAliasing == AliasingKind::kOverlap) {
1497 fixed_fp_register_use_->Add(index);
1498 } else if (kFPAliasing == AliasingKind::kIndependent) {
1499 if (rep == MachineRepresentation::kFloat32) {
1500 fixed_fp_register_use_->Add(index);
1501 } else {
1502 fixed_simd128_register_use_->Add(index);
1503 }
1504 } else {
1505 int alias_base_index = -1;
1506 int aliases = config()->GetAliases(
1507 rep, index, MachineRepresentation::kFloat64, &alias_base_index);
1508 DCHECK(aliases > 0 || (aliases == 0 && alias_base_index == -1))((void) 0);
1509 while (aliases--) {
1510 int aliased_reg = alias_base_index + aliases;
1511 fixed_fp_register_use_->Add(aliased_reg);
1512 }
1513 }
1514 break;
1515 case MachineRepresentation::kFloat64:
1516 fixed_fp_register_use_->Add(index);
1517 break;
1518 default:
1519 DCHECK(!IsFloatingPoint(rep))((void) 0);
1520 fixed_register_use_->Add(index);
1521 break;
1522 }
1523}
1524
1525bool TopTierRegisterAllocationData::HasFixedUse(MachineRepresentation rep,
1526 int index) {
1527 switch (rep) {
1528 case MachineRepresentation::kFloat32:
1529 case MachineRepresentation::kSimd128: {
1530 if (kFPAliasing == AliasingKind::kOverlap) {
1531 return fixed_fp_register_use_->Contains(index);
1532 } else if (kFPAliasing == AliasingKind::kIndependent) {
1533 if (rep == MachineRepresentation::kFloat32) {
1534 return fixed_fp_register_use_->Contains(index);
1535 } else {
1536 return fixed_simd128_register_use_->Contains(index);
1537 }
1538 } else {
1539 int alias_base_index = -1;
1540 int aliases = config()->GetAliases(
1541 rep, index, MachineRepresentation::kFloat64, &alias_base_index);
1542 DCHECK(aliases > 0 || (aliases == 0 && alias_base_index == -1))((void) 0);
1543 bool result = false;
1544 while (aliases-- && !result) {
1545 int aliased_reg = alias_base_index + aliases;
1546 result |= fixed_fp_register_use_->Contains(aliased_reg);
1547 }
1548 return result;
1549 }
1550 }
1551 case MachineRepresentation::kFloat64:
1552 return fixed_fp_register_use_->Contains(index);
1553 default:
1554 DCHECK(!IsFloatingPoint(rep))((void) 0);
1555 return fixed_register_use_->Contains(index);
1556 }
1557}
1558
1559void TopTierRegisterAllocationData::MarkAllocated(MachineRepresentation rep,
1560 int index) {
1561 switch (rep) {
1562 case MachineRepresentation::kFloat32:
1563 case MachineRepresentation::kSimd128:
1564 if (kFPAliasing == AliasingKind::kOverlap) {
1565 assigned_double_registers_->Add(index);
1566 } else if (kFPAliasing == AliasingKind::kIndependent) {
1567 if (rep == MachineRepresentation::kFloat32) {
1568 assigned_double_registers_->Add(index);
1569 } else {
1570 assigned_simd128_registers_->Add(index);
1571 }
1572 } else {
1573 int alias_base_index = -1;
1574 int aliases = config()->GetAliases(
1575 rep, index, MachineRepresentation::kFloat64, &alias_base_index);
1576 DCHECK(aliases > 0 || (aliases == 0 && alias_base_index == -1))((void) 0);
1577 while (aliases--) {
1578 int aliased_reg = alias_base_index + aliases;
1579 assigned_double_registers_->Add(aliased_reg);
1580 }
1581 }
1582 break;
1583 case MachineRepresentation::kFloat64:
1584 assigned_double_registers_->Add(index);
1585 break;
1586 default:
1587 DCHECK(!IsFloatingPoint(rep))((void) 0);
1588 assigned_registers_->Add(index);
1589 break;
1590 }
1591}
1592
1593bool TopTierRegisterAllocationData::IsBlockBoundary(
1594 LifetimePosition pos) const {
1595 return pos.IsFullStart() &&
1596 (static_cast<size_t>(pos.ToInstructionIndex()) ==
1597 code()->instructions().size() ||
1598 code()->GetInstructionBlock(pos.ToInstructionIndex())->code_start() ==
1599 pos.ToInstructionIndex());
1600}
1601
1602ConstraintBuilder::ConstraintBuilder(TopTierRegisterAllocationData* data)
1603 : data_(data) {}
1604
1605InstructionOperand* ConstraintBuilder::AllocateFixed(
1606 UnallocatedOperand* operand, int pos, bool is_tagged, bool is_input) {
1607 TRACE("Allocating fixed reg for op %d\n", operand->virtual_register());
1608 DCHECK(operand->HasFixedPolicy())((void) 0);
1609 InstructionOperand allocated;
1610 MachineRepresentation rep = InstructionSequence::DefaultRepresentation();
1611 int virtual_register = operand->virtual_register();
1612 if (virtual_register != InstructionOperand::kInvalidVirtualRegister) {
1613 rep = data()->RepresentationFor(virtual_register);
1614 }
1615 if (operand->HasFixedSlotPolicy()) {
1616 allocated = AllocatedOperand(AllocatedOperand::STACK_SLOT, rep,
1617 operand->fixed_slot_index());
1618 } else if (operand->HasFixedRegisterPolicy()) {
1619 DCHECK(!IsFloatingPoint(rep))((void) 0);
1620 DCHECK(data()->config()->IsAllocatableGeneralCode(((void) 0)
1621 operand->fixed_register_index()))((void) 0);
1622 allocated = AllocatedOperand(AllocatedOperand::REGISTER, rep,
1623 operand->fixed_register_index());
1624 } else if (operand->HasFixedFPRegisterPolicy()) {
1625 DCHECK(IsFloatingPoint(rep))((void) 0);
1626 DCHECK_NE(InstructionOperand::kInvalidVirtualRegister, virtual_register)((void) 0);
1627 allocated = AllocatedOperand(AllocatedOperand::REGISTER, rep,
1628 operand->fixed_register_index());
1629 } else {
1630 UNREACHABLE()V8_Fatal("unreachable code");
1631 }
1632 if (is_input && allocated.IsAnyRegister()) {
1633 data()->MarkFixedUse(rep, operand->fixed_register_index());
1634 }
1635 InstructionOperand::ReplaceWith(operand, &allocated);
1636 if (is_tagged) {
1637 TRACE("Fixed reg is tagged at %d\n", pos);
1638 Instruction* instr = code()->InstructionAt(pos);
1639 if (instr->HasReferenceMap()) {
1640 instr->reference_map()->RecordReference(*AllocatedOperand::cast(operand));
1641 }
1642 }
1643 return operand;
1644}
1645
1646void ConstraintBuilder::MeetRegisterConstraints() {
1647 for (InstructionBlock* block : code()->instruction_blocks()) {
1648 data_->tick_counter()->TickAndMaybeEnterSafepoint();
1649 MeetRegisterConstraints(block);
1650 }
1651}
1652
1653void ConstraintBuilder::MeetRegisterConstraints(const InstructionBlock* block) {
1654 int start = block->first_instruction_index();
1655 int end = block->last_instruction_index();
1656 DCHECK_NE(-1, start)((void) 0);
1657 for (int i = start; i <= end; ++i) {
1658 MeetConstraintsBefore(i);
1659 if (i != end) MeetConstraintsAfter(i);
1660 }
1661 // Meet register constraints for the instruction in the end.
1662 MeetRegisterConstraintsForLastInstructionInBlock(block);
1663}
1664
1665void ConstraintBuilder::MeetRegisterConstraintsForLastInstructionInBlock(
1666 const InstructionBlock* block) {
1667 int end = block->last_instruction_index();
1668 Instruction* last_instruction = code()->InstructionAt(end);
1669 for (size_t i = 0; i < last_instruction->OutputCount(); i++) {
1670 InstructionOperand* output_operand = last_instruction->OutputAt(i);
1671 DCHECK(!output_operand->IsConstant())((void) 0);
1672 UnallocatedOperand* output = UnallocatedOperand::cast(output_operand);
1673 int output_vreg = output->virtual_register();
1674 TopLevelLiveRange* range = data()->GetOrCreateLiveRangeFor(output_vreg);
1675 bool assigned = false;
1676 if (output->HasFixedPolicy()) {
1677 AllocateFixed(output, -1, false, false);
1678 // This value is produced on the stack, we never need to spill it.
1679 if (output->IsStackSlot()) {
1680 DCHECK(LocationOperand::cast(output)->index() <((void) 0)
1681 data()->frame()->GetSpillSlotCount())((void) 0);
1682 range->SetSpillOperand(LocationOperand::cast(output));
1683 range->SetSpillStartIndex(end);
1684 assigned = true;
1685 }
1686
1687 for (const RpoNumber& succ : block->successors()) {
1688 const InstructionBlock* successor = code()->InstructionBlockAt(succ);
1689 DCHECK_EQ(1, successor->PredecessorCount())((void) 0);
1690 int gap_index = successor->first_instruction_index();
1691 // Create an unconstrained operand for the same virtual register
1692 // and insert a gap move from the fixed output to the operand.
1693 UnallocatedOperand output_copy(UnallocatedOperand::REGISTER_OR_SLOT,
1694 output_vreg);
1695 data()->AddGapMove(gap_index, Instruction::START, *output, output_copy);
1696 }
1697 }
1698
1699 if (!assigned) {
1700 for (const RpoNumber& succ : block->successors()) {
1701 const InstructionBlock* successor = code()->InstructionBlockAt(succ);
1702 DCHECK_EQ(1, successor->PredecessorCount())((void) 0);
1703 int gap_index = successor->first_instruction_index();
1704 range->RecordSpillLocation(allocation_zone(), gap_index, output);
1705 range->SetSpillStartIndex(gap_index);
1706 }
1707 }
1708 }
1709}
1710
1711void ConstraintBuilder::MeetConstraintsAfter(int instr_index) {
1712 Instruction* first = code()->InstructionAt(instr_index);
1713 // Handle fixed temporaries.
1714 for (size_t i = 0; i < first->TempCount(); i++) {
1715 UnallocatedOperand* temp = UnallocatedOperand::cast(first->TempAt(i));
1716 if (temp->HasFixedPolicy()) AllocateFixed(temp, instr_index, false, false);
1717 }
1718 // Handle constant/fixed output operands.
1719 for (size_t i = 0; i < first->OutputCount(); i++) {
1720 InstructionOperand* output = first->OutputAt(i);
1721 if (output->IsConstant()) {
1722 int output_vreg = ConstantOperand::cast(output)->virtual_register();
1723 TopLevelLiveRange* range = data()->GetOrCreateLiveRangeFor(output_vreg);
1724 range->SetSpillStartIndex(instr_index + 1);
1725 range->SetSpillOperand(output);
1726 continue;
1727 }
1728 UnallocatedOperand* first_output = UnallocatedOperand::cast(output);
1729 TopLevelLiveRange* range =
1730 data()->GetOrCreateLiveRangeFor(first_output->virtual_register());
1731 bool assigned = false;
1732 if (first_output->HasFixedPolicy()) {
1733 int output_vreg = first_output->virtual_register();
1734 UnallocatedOperand output_copy(UnallocatedOperand::REGISTER_OR_SLOT,
1735 output_vreg);
1736 bool is_tagged = code()->IsReference(output_vreg);
1737 if (first_output->HasSecondaryStorage()) {
1738 range->MarkHasPreassignedSlot();
1739 data()->preassigned_slot_ranges().push_back(
1740 std::make_pair(range, first_output->GetSecondaryStorage()));
1741 }
1742 AllocateFixed(first_output, instr_index, is_tagged, false);
1743
1744 // This value is produced on the stack, we never need to spill it.
1745 if (first_output->IsStackSlot()) {
1746 DCHECK(LocationOperand::cast(first_output)->index() <((void) 0)
1747 data()->frame()->GetTotalFrameSlotCount())((void) 0);
1748 range->SetSpillOperand(LocationOperand::cast(first_output));
1749 range->SetSpillStartIndex(instr_index + 1);
1750 assigned = true;
1751 }
1752 data()->AddGapMove(instr_index + 1, Instruction::START, *first_output,
1753 output_copy);
1754 }
1755 // Make sure we add a gap move for spilling (if we have not done
1756 // so already).
1757 if (!assigned) {
1758 range->RecordSpillLocation(allocation_zone(), instr_index + 1,
1759 first_output);
1760 range->SetSpillStartIndex(instr_index + 1);
1761 }
1762 }
1763}
1764
1765void ConstraintBuilder::MeetConstraintsBefore(int instr_index) {
1766 Instruction* second = code()->InstructionAt(instr_index);
1767 // Handle fixed input operands of second instruction.
1768 ZoneVector<TopLevelLiveRange*>* spilled_consts = nullptr;
1769 for (size_t i = 0; i < second->InputCount(); i++) {
1770 InstructionOperand* input = second->InputAt(i);
1771 if (input->IsImmediate()) {
1772 continue; // Ignore immediates.
1773 }
1774 UnallocatedOperand* cur_input = UnallocatedOperand::cast(input);
1775 if (cur_input->HasSlotPolicy()) {
1776 TopLevelLiveRange* range =
1777 data()->GetOrCreateLiveRangeFor(cur_input->virtual_register());
1778 if (range->HasSpillOperand() && range->GetSpillOperand()->IsConstant()) {
1779 bool already_spilled = false;
1780 if (spilled_consts == nullptr) {
1781 spilled_consts =
1782 allocation_zone()->New<ZoneVector<TopLevelLiveRange*>>(
1783 allocation_zone());
1784 } else {
1785 auto it =
1786 std::find(spilled_consts->begin(), spilled_consts->end(), range);
1787 already_spilled = it != spilled_consts->end();
1788 }
1789 auto it = data()->slot_for_const_range().find(range);
1790 if (it == data()->slot_for_const_range().end()) {
1791 DCHECK(!already_spilled)((void) 0);
1792 int width = ByteWidthForStackSlot(range->representation());
1793 int index = data()->frame()->AllocateSpillSlot(width);
1794 auto* slot = AllocatedOperand::New(allocation_zone(),
1795 LocationOperand::STACK_SLOT,
1796 range->representation(), index);
1797 it = data()->slot_for_const_range().emplace(range, slot).first;
1798 }
1799 if (!already_spilled) {
1800 auto* slot = it->second;
1801 int input_vreg = cur_input->virtual_register();
1802 UnallocatedOperand input_copy(UnallocatedOperand::REGISTER_OR_SLOT,
1803 input_vreg);
1804 // Spill at every use position for simplicity, this case is very rare.
1805 data()->AddGapMove(instr_index, Instruction::END, input_copy, *slot);
1806 spilled_consts->push_back(range);
1807 }
1808 }
1809 }
1810 if (cur_input->HasFixedPolicy()) {
1811 int input_vreg = cur_input->virtual_register();
1812 UnallocatedOperand input_copy(UnallocatedOperand::REGISTER_OR_SLOT,
1813 input_vreg);
1814 bool is_tagged = code()->IsReference(input_vreg);
1815 AllocateFixed(cur_input, instr_index, is_tagged, true);
1816 data()->AddGapMove(instr_index, Instruction::END, input_copy, *cur_input);
1817 }
1818 }
1819 // Handle "output same as input" for second instruction.
1820 for (size_t i = 0; i < second->OutputCount(); i++) {
1821 InstructionOperand* output = second->OutputAt(i);
1822 if (!output->IsUnallocated()) continue;
1823 UnallocatedOperand* second_output = UnallocatedOperand::cast(output);
1824 if (!second_output->HasSameAsInputPolicy()) continue;
1825 DCHECK_EQ(0, i)((void) 0); // Only valid for first output.
1826 UnallocatedOperand* cur_input =
1827 UnallocatedOperand::cast(second->InputAt(second_output->input_index()));
1828 int output_vreg = second_output->virtual_register();
1829 int input_vreg = cur_input->virtual_register();
1830 UnallocatedOperand input_copy(UnallocatedOperand::REGISTER_OR_SLOT,
1831 input_vreg);
1832 *cur_input =
1833 UnallocatedOperand(*cur_input, second_output->virtual_register());
1834 MoveOperands* gap_move = data()->AddGapMove(instr_index, Instruction::END,
1835 input_copy, *cur_input);
1836 DCHECK_NOT_NULL(gap_move)((void) 0);
1837 if (code()->IsReference(input_vreg) && !code()->IsReference(output_vreg)) {
1838 if (second->HasReferenceMap()) {
1839 TopTierRegisterAllocationData::DelayedReference delayed_reference = {
1840 second->reference_map(), &gap_move->source()};
1841 data()->delayed_references().push_back(delayed_reference);
1842 }
1843 }
1844 }
1845}
1846
1847void ConstraintBuilder::ResolvePhis() {
1848 // Process the blocks in reverse order.
1849 for (InstructionBlock* block : base::Reversed(code()->instruction_blocks())) {
1850 data_->tick_counter()->TickAndMaybeEnterSafepoint();
1851 ResolvePhis(block);
1852 }
1853}
1854
1855void ConstraintBuilder::ResolvePhis(const InstructionBlock* block) {
1856 for (PhiInstruction* phi : block->phis()) {
1857 int phi_vreg = phi->virtual_register();
1858 TopTierRegisterAllocationData::PhiMapValue* map_value =
1859 data()->InitializePhiMap(block, phi);
1860 InstructionOperand& output = phi->output();
1861 // Map the destination operands, so the commitment phase can find them.
1862 for (size_t i = 0; i < phi->operands().size(); ++i) {
1863 InstructionBlock* cur_block =
1864 code()->InstructionBlockAt(block->predecessors()[i]);
1865 UnallocatedOperand input(UnallocatedOperand::REGISTER_OR_SLOT,
1866 phi->operands()[i]);
1867 MoveOperands* move = data()->AddGapMove(
1868 cur_block->last_instruction_index(), Instruction::END, input, output);
1869 map_value->AddOperand(&move->destination());
1870 DCHECK(!code()((void) 0)
1871 ->InstructionAt(cur_block->last_instruction_index())((void) 0)
1872 ->HasReferenceMap())((void) 0);
1873 }
1874 TopLevelLiveRange* live_range = data()->GetOrCreateLiveRangeFor(phi_vreg);
1875 int gap_index = block->first_instruction_index();
1876 live_range->RecordSpillLocation(allocation_zone(), gap_index, &output);
1877 live_range->SetSpillStartIndex(gap_index);
1878 // We use the phi-ness of some nodes in some later heuristics.
1879 live_range->set_is_phi(true);
1880 live_range->set_is_non_loop_phi(!block->IsLoopHeader());
1881 }
1882}
1883
1884LiveRangeBuilder::LiveRangeBuilder(TopTierRegisterAllocationData* data,
1885 Zone* local_zone)
1886 : data_(data), phi_hints_(local_zone) {}
1887
1888BitVector* LiveRangeBuilder::ComputeLiveOut(
1889 const InstructionBlock* block, TopTierRegisterAllocationData* data) {
1890 size_t block_index = block->rpo_number().ToSize();
1891 BitVector* live_out = data->live_out_sets()[block_index];
1892 if (live_out == nullptr) {
1893 // Compute live out for the given block, except not including backward
1894 // successor edges.
1895 Zone* zone = data->allocation_zone();
1896 const InstructionSequence* code = data->code();
1897
1898 live_out = zone->New<BitVector>(code->VirtualRegisterCount(), zone);
1899
1900 // Process all successor blocks.
1901 for (const RpoNumber& succ : block->successors()) {
1902 // Add values live on entry to the successor.
1903 if (succ <= block->rpo_number()) continue;
1904 BitVector* live_in = data->live_in_sets()[succ.ToSize()];
1905 if (live_in != nullptr) live_out->Union(*live_in);
1906
1907 // All phi input operands corresponding to this successor edge are live
1908 // out from this block.
1909 const InstructionBlock* successor = code->InstructionBlockAt(succ);
1910 size_t index = successor->PredecessorIndexOf(block->rpo_number());
1911 DCHECK(index < successor->PredecessorCount())((void) 0);
1912 for (PhiInstruction* phi : successor->phis()) {
1913 live_out->Add(phi->operands()[index]);
1914 }
1915 }
1916 data->live_out_sets()[block_index] = live_out;
1917 }
1918 return live_out;
1919}
1920
1921void LiveRangeBuilder::AddInitialIntervals(const InstructionBlock* block,
1922 BitVector* live_out) {
1923 // Add an interval that includes the entire block to the live range for
1924 // each live_out value.
1925 LifetimePosition start = LifetimePosition::GapFromInstructionIndex(
1926 block->first_instruction_index());
1927 LifetimePosition end = LifetimePosition::InstructionFromInstructionIndex(
1928 block->last_instruction_index())
1929 .NextStart();
1930 for (int operand_index : *live_out) {
1931 TopLevelLiveRange* range = data()->GetOrCreateLiveRangeFor(operand_index);
1932 range->AddUseInterval(start, end, allocation_zone(),
1933 data()->is_trace_alloc());
1934 }
1935}
1936
1937int LiveRangeBuilder::FixedFPLiveRangeID(int index, MachineRepresentation rep) {
1938 int result = -index - 1;
1939 switch (rep) {
1940 case MachineRepresentation::kSimd128:
1941 result -=
1942 kNumberOfFixedRangesPerRegister * config()->num_float_registers();
1943 V8_FALLTHROUGH[[clang::fallthrough]];
1944 case MachineRepresentation::kFloat32:
1945 result -=
1946 kNumberOfFixedRangesPerRegister * config()->num_double_registers();
1947 V8_FALLTHROUGH[[clang::fallthrough]];
1948 case MachineRepresentation::kFloat64:
1949 result -=
1950 kNumberOfFixedRangesPerRegister * config()->num_general_registers();
1951 break;
1952 default:
1953 UNREACHABLE()V8_Fatal("unreachable code");
1954 }
1955 return result;
1956}
1957
1958TopLevelLiveRange* LiveRangeBuilder::FixedLiveRangeFor(int index,
1959 SpillMode spill_mode) {
1960 int offset = spill_mode == SpillMode::kSpillAtDefinition
1961 ? 0
1962 : config()->num_general_registers();
1963 DCHECK(index < config()->num_general_registers())((void) 0);
1964 TopLevelLiveRange* result = data()->fixed_live_ranges()[offset + index];
1965 if (result == nullptr) {
1966 MachineRepresentation rep = InstructionSequence::DefaultRepresentation();
1967 result = data()->NewLiveRange(FixedLiveRangeID(offset + index), rep);
1968 DCHECK(result->IsFixed())((void) 0);
1969 result->set_assigned_register(index);
1970 data()->MarkAllocated(rep, index);
1971 if (spill_mode == SpillMode::kSpillDeferred) {
1972 result->set_deferred_fixed();
1973 }
1974 data()->fixed_live_ranges()[offset + index] = result;
1975 }
1976 return result;
1977}
1978
1979TopLevelLiveRange* LiveRangeBuilder::FixedFPLiveRangeFor(
1980 int index, MachineRepresentation rep, SpillMode spill_mode) {
1981 int num_regs = config()->num_double_registers();
1982 ZoneVector<TopLevelLiveRange*>* live_ranges =
1983 &data()->fixed_double_live_ranges();
1984 if (kFPAliasing == AliasingKind::kCombine) {
1985 switch (rep) {
1986 case MachineRepresentation::kFloat32:
1987 num_regs = config()->num_float_registers();
1988 live_ranges = &data()->fixed_float_live_ranges();
1989 break;
1990 case MachineRepresentation::kSimd128:
1991 num_regs = config()->num_simd128_registers();
1992 live_ranges = &data()->fixed_simd128_live_ranges();
1993 break;
1994 default:
1995 break;
1996 }
1997 }
1998
1999 int offset = spill_mode == SpillMode::kSpillAtDefinition ? 0 : num_regs;
2000
2001 DCHECK(index < num_regs)((void) 0);
2002 USE(num_regs)do { ::v8::base::Use unused_tmp_array_for_use_macro[]{num_regs
}; (void)unused_tmp_array_for_use_macro; } while (false)
;
2003 TopLevelLiveRange* result = (*live_ranges)[offset + index];
2004 if (result == nullptr) {
2005 result = data()->NewLiveRange(FixedFPLiveRangeID(offset + index, rep), rep);
2006 DCHECK(result->IsFixed())((void) 0);
2007 result->set_assigned_register(index);
2008 data()->MarkAllocated(rep, index);
2009 if (spill_mode == SpillMode::kSpillDeferred) {
2010 result->set_deferred_fixed();
2011 }
2012 (*live_ranges)[offset + index] = result;
2013 }
2014 return result;
2015}
2016
2017TopLevelLiveRange* LiveRangeBuilder::FixedSIMD128LiveRangeFor(
2018 int index, SpillMode spill_mode) {
2019 DCHECK_EQ(kFPAliasing, AliasingKind::kIndependent)((void) 0);
2020 int num_regs = config()->num_simd128_registers();
2021 ZoneVector<TopLevelLiveRange*>* live_ranges =
2022 &data()->fixed_simd128_live_ranges();
2023 int offset = spill_mode == SpillMode::kSpillAtDefinition ? 0 : num_regs;
2024
2025 DCHECK(index < num_regs)((void) 0);
2026 USE(num_regs)do { ::v8::base::Use unused_tmp_array_for_use_macro[]{num_regs
}; (void)unused_tmp_array_for_use_macro; } while (false)
;
2027 TopLevelLiveRange* result = (*live_ranges)[offset + index];
2028 if (result == nullptr) {
2029 result = data()->NewLiveRange(
2030 FixedFPLiveRangeID(offset + index, MachineRepresentation::kSimd128),
2031 MachineRepresentation::kSimd128);
2032 DCHECK(result->IsFixed())((void) 0);
2033 result->set_assigned_register(index);
2034 data()->MarkAllocated(MachineRepresentation::kSimd128, index);
2035 if (spill_mode == SpillMode::kSpillDeferred) {
2036 result->set_deferred_fixed();
2037 }
2038 (*live_ranges)[offset + index] = result;
2039 }
2040 return result;
2041}
2042
2043TopLevelLiveRange* LiveRangeBuilder::LiveRangeFor(InstructionOperand* operand,
2044 SpillMode spill_mode) {
2045 if (operand->IsUnallocated()) {
2046 return data()->GetOrCreateLiveRangeFor(
2047 UnallocatedOperand::cast(operand)->virtual_register());
2048 } else if (operand->IsConstant()) {
2049 return data()->GetOrCreateLiveRangeFor(
2050 ConstantOperand::cast(operand)->virtual_register());
2051 } else if (operand->IsRegister()) {
2052 return FixedLiveRangeFor(
2053 LocationOperand::cast(operand)->GetRegister().code(), spill_mode);
2054 } else if (operand->IsFPRegister()) {
2055 LocationOperand* op = LocationOperand::cast(operand);
2056 if (kFPAliasing == AliasingKind::kIndependent &&
2057 op->representation() == MachineRepresentation::kSimd128) {
2058 return FixedSIMD128LiveRangeFor(op->register_code(), spill_mode);
2059 }
2060 return FixedFPLiveRangeFor(op->register_code(), op->representation(),
2061 spill_mode);
2062 } else {
2063 return nullptr;
2064 }
2065}
2066
2067UsePosition* LiveRangeBuilder::NewUsePosition(LifetimePosition pos,
2068 InstructionOperand* operand,
2069 void* hint,
2070 UsePositionHintType hint_type) {
2071 return allocation_zone()->New<UsePosition>(pos, operand, hint, hint_type);
2072}
2073
2074UsePosition* LiveRangeBuilder::Define(LifetimePosition position,
2075 InstructionOperand* operand, void* hint,
2076 UsePositionHintType hint_type,
2077 SpillMode spill_mode) {
2078 TopLevelLiveRange* range = LiveRangeFor(operand, spill_mode);
2079 if (range == nullptr) return nullptr;
2080
2081 if (range->IsEmpty() || range->Start() > position) {
2082 // Can happen if there is a definition without use.
2083 range->AddUseInterval(position, position.NextStart(), allocation_zone(),
2084 data()->is_trace_alloc());
2085 range->AddUsePosition(NewUsePosition(position.NextStart()),
2086 data()->is_trace_alloc());
2087 } else {
2088 range->ShortenTo(position, data()->is_trace_alloc());
2089 }
2090 if (!operand->IsUnallocated()) return nullptr;
2091 UnallocatedOperand* unalloc_operand = UnallocatedOperand::cast(operand);
2092 UsePosition* use_pos =
2093 NewUsePosition(position, unalloc_operand, hint, hint_type);
2094 range->AddUsePosition(use_pos, data()->is_trace_alloc());
2095 return use_pos;
2096}
2097
2098UsePosition* LiveRangeBuilder::Use(LifetimePosition block_start,
2099 LifetimePosition position,
2100 InstructionOperand* operand, void* hint,
2101 UsePositionHintType hint_type,
2102 SpillMode spill_mode) {
2103 TopLevelLiveRange* range = LiveRangeFor(operand, spill_mode);
2104 if (range == nullptr) return nullptr;
2105 UsePosition* use_pos = nullptr;
2106 if (operand->IsUnallocated()) {
2107 UnallocatedOperand* unalloc_operand = UnallocatedOperand::cast(operand);
2108 use_pos = NewUsePosition(position, unalloc_operand, hint, hint_type);
2109 range->AddUsePosition(use_pos, data()->is_trace_alloc());
2110 }
2111 range->AddUseInterval(block_start, position, allocation_zone(),
2112 data()->is_trace_alloc());
2113 return use_pos;
2114}
2115
2116void LiveRangeBuilder::ProcessInstructions(const InstructionBlock* block,
2117 BitVector* live) {
2118 int block_start = block->first_instruction_index();
2119 LifetimePosition block_start_position =
2120 LifetimePosition::GapFromInstructionIndex(block_start);
2121 bool fixed_float_live_ranges = false;
2122 bool fixed_simd128_live_ranges = false;
2123 if (kFPAliasing == AliasingKind::kCombine) {
2124 int mask = data()->code()->representation_mask();
2125 fixed_float_live_ranges = (mask & kFloat32Bit) != 0;
2126 fixed_simd128_live_ranges = (mask & kSimd128Bit) != 0;
2127 } else if (kFPAliasing == AliasingKind::kIndependent) {
2128 int mask = data()->code()->representation_mask();
2129 fixed_simd128_live_ranges = (mask & kSimd128Bit) != 0;
2130 }
2131 SpillMode spill_mode = SpillModeForBlock(block);
2132
2133 for (int index = block->last_instruction_index(); index >= block_start;
2134 index--) {
2135 LifetimePosition curr_position =
2136 LifetimePosition::InstructionFromInstructionIndex(index);
2137 Instruction* instr = code()->InstructionAt(index);
2138 DCHECK_NOT_NULL(instr)((void) 0);
2139 DCHECK(curr_position.IsInstructionPosition())((void) 0);
2140 // Process output, inputs, and temps of this instruction.
2141 for (size_t i = 0; i < instr->OutputCount(); i++) {
2142 InstructionOperand* output = instr->OutputAt(i);
2143 if (output->IsUnallocated()) {
2144 // Unsupported.
2145 DCHECK(!UnallocatedOperand::cast(output)->HasSlotPolicy())((void) 0);
2146 int out_vreg = UnallocatedOperand::cast(output)->virtual_register();
2147 live->Remove(out_vreg);
2148 } else if (output->IsConstant()) {
2149 int out_vreg = ConstantOperand::cast(output)->virtual_register();
2150 live->Remove(out_vreg);
2151 }
2152 if (block->IsHandler() && index == block_start && output->IsAllocated() &&
2153 output->IsRegister() &&
2154 AllocatedOperand::cast(output)->GetRegister() ==
2155 v8::internal::kReturnRegister0) {
2156 // The register defined here is blocked from gap start - it is the
2157 // exception value.
2158 // TODO(mtrofin): should we explore an explicit opcode for
2159 // the first instruction in the handler?
2160 Define(LifetimePosition::GapFromInstructionIndex(index), output,
2161 spill_mode);
2162 } else {
2163 Define(curr_position, output, spill_mode);
2164 }
2165 }
2166
2167 if (instr->ClobbersRegisters()) {
2168 for (int i = 0; i < config()->num_allocatable_general_registers(); ++i) {
2169 // Create a UseInterval at this instruction for all fixed registers,
2170 // (including the instruction outputs). Adding another UseInterval here
2171 // is OK because AddUseInterval will just merge it with the existing
2172 // one at the end of the range.
2173 int code = config()->GetAllocatableGeneralCode(i);
2174 TopLevelLiveRange* range = FixedLiveRangeFor(code, spill_mode);
2175 range->AddUseInterval(curr_position, curr_position.End(),
2176 allocation_zone(), data()->is_trace_alloc());
2177 }
2178 }
2179
2180 if (instr->ClobbersDoubleRegisters()) {
2181 for (int i = 0; i < config()->num_allocatable_double_registers(); ++i) {
2182 // Add a UseInterval for all DoubleRegisters. See comment above for
2183 // general registers.
2184 int code = config()->GetAllocatableDoubleCode(i);
2185 TopLevelLiveRange* range = FixedFPLiveRangeFor(
2186 code, MachineRepresentation::kFloat64, spill_mode);
2187 range->AddUseInterval(curr_position, curr_position.End(),
2188 allocation_zone(), data()->is_trace_alloc());
2189 }
2190 // Clobber fixed float registers on archs with non-simple aliasing.
2191 if (kFPAliasing == AliasingKind::kCombine) {
2192 if (fixed_float_live_ranges) {
2193 for (int i = 0; i < config()->num_allocatable_float_registers();
2194 ++i) {
2195 // Add a UseInterval for all FloatRegisters. See comment above for
2196 // general registers.
2197 int code = config()->GetAllocatableFloatCode(i);
2198 TopLevelLiveRange* range = FixedFPLiveRangeFor(
2199 code, MachineRepresentation::kFloat32, spill_mode);
2200 range->AddUseInterval(curr_position, curr_position.End(),
2201 allocation_zone(), data()->is_trace_alloc());
2202 }
2203 }
2204 if (fixed_simd128_live_ranges) {
2205 for (int i = 0; i < config()->num_allocatable_simd128_registers();
2206 ++i) {
2207 int code = config()->GetAllocatableSimd128Code(i);
2208 TopLevelLiveRange* range = FixedFPLiveRangeFor(
2209 code, MachineRepresentation::kSimd128, spill_mode);
2210 range->AddUseInterval(curr_position, curr_position.End(),
2211 allocation_zone(), data()->is_trace_alloc());
2212 }
2213 }
2214 } else if (kFPAliasing == AliasingKind::kIndependent) {
2215 if (fixed_simd128_live_ranges) {
2216 for (int i = 0; i < config()->num_allocatable_simd128_registers();
2217 ++i) {
2218 int code = config()->GetAllocatableSimd128Code(i);
2219 TopLevelLiveRange* range =
2220 FixedSIMD128LiveRangeFor(code, spill_mode);
2221 range->AddUseInterval(curr_position, curr_position.End(),
2222 allocation_zone(), data()->is_trace_alloc());
2223 }
2224 }
2225 }
2226 }
2227
2228 for (size_t i = 0; i < instr->InputCount(); i++) {
2229 InstructionOperand* input = instr->InputAt(i);
2230 if (input->IsImmediate()) {
2231 continue; // Ignore immediates.
2232 }
2233 LifetimePosition use_pos;
2234 if (input->IsUnallocated() &&
2235 UnallocatedOperand::cast(input)->IsUsedAtStart()) {
2236 use_pos = curr_position;
2237 } else {
2238 use_pos = curr_position.End();
2239 }
2240
2241 if (input->IsUnallocated()) {
2242 UnallocatedOperand* unalloc = UnallocatedOperand::cast(input);
2243 int vreg = unalloc->virtual_register();
2244 live->Add(vreg);
2245 if (unalloc->HasSlotPolicy()) {
2246 data()->GetOrCreateLiveRangeFor(vreg)->register_slot_use(
2247 block->IsDeferred()
2248 ? TopLevelLiveRange::SlotUseKind::kDeferredSlotUse
2249 : TopLevelLiveRange::SlotUseKind::kGeneralSlotUse);
2250 }
2251 }
2252 Use(block_start_position, use_pos, input, spill_mode);
2253 }
2254
2255 for (size_t i = 0; i < instr->TempCount(); i++) {
2256 InstructionOperand* temp = instr->TempAt(i);
2257 // Unsupported.
2258 DCHECK_IMPLIES(temp->IsUnallocated(),((void) 0)
2259 !UnallocatedOperand::cast(temp)->HasSlotPolicy())((void) 0);
2260 if (instr->ClobbersTemps()) {
2261 if (temp->IsRegister()) continue;
2262 if (temp->IsUnallocated()) {
2263 UnallocatedOperand* temp_unalloc = UnallocatedOperand::cast(temp);
2264 if (temp_unalloc->HasFixedPolicy()) {
2265 continue;
2266 }
2267 }
2268 }
2269 Use(block_start_position, curr_position.End(), temp, spill_mode);
2270 Define(curr_position, temp, spill_mode);
2271 }
2272
2273 // Process the moves of the instruction's gaps, making their sources live.
2274 const Instruction::GapPosition kPositions[] = {Instruction::END,
2275 Instruction::START};
2276 curr_position = curr_position.PrevStart();
2277 DCHECK(curr_position.IsGapPosition())((void) 0);
2278 for (const Instruction::GapPosition& position : kPositions) {
2279 ParallelMove* move = instr->GetParallelMove(position);
2280 if (move == nullptr) continue;
2281 if (position == Instruction::END) {
2282 curr_position = curr_position.End();
2283 } else {
2284 curr_position = curr_position.Start();
2285 }
2286 for (MoveOperands* cur : *move) {
2287 InstructionOperand& from = cur->source();
2288 InstructionOperand& to = cur->destination();
2289 void* hint = &to;
2290 UsePositionHintType hint_type = UsePosition::HintTypeForOperand(to);
2291 UsePosition* to_use = nullptr;
2292 int phi_vreg = -1;
2293 if (to.IsUnallocated()) {
2294 int to_vreg = UnallocatedOperand::cast(to).virtual_register();
2295 TopLevelLiveRange* to_range =
2296 data()->GetOrCreateLiveRangeFor(to_vreg);
2297 if (to_range->is_phi()) {
2298 phi_vreg = to_vreg;
2299 if (to_range->is_non_loop_phi()) {
2300 hint = to_range->current_hint_position();
2301 hint_type = hint == nullptr ? UsePositionHintType::kNone
2302 : UsePositionHintType::kUsePos;
2303 } else {
2304 hint_type = UsePositionHintType::kPhi;
2305 hint = data()->GetPhiMapValueFor(to_vreg);
2306 }
2307 } else {
2308 if (live->Contains(to_vreg)) {
2309 to_use =
2310 Define(curr_position, &to, &from,
2311 UsePosition::HintTypeForOperand(from), spill_mode);
2312 live->Remove(to_vreg);
2313 } else {
2314 cur->Eliminate();
2315 continue;
2316 }
2317 }
2318 } else {
2319 Define(curr_position, &to, spill_mode);
2320 }
2321 UsePosition* from_use = Use(block_start_position, curr_position, &from,
2322 hint, hint_type, spill_mode);
2323 // Mark range live.
2324 if (from.IsUnallocated()) {
2325 live->Add(UnallocatedOperand::cast(from).virtual_register());
2326 }
2327 // When the value is moved to a register to meet input constraints,
2328 // we should consider this value use similar as a register use in the
2329 // backward spilling heuristics, even though this value use is not
2330 // register benefical at the AllocateBlockedReg stage.
2331 if (to.IsAnyRegister() ||
2332 (to.IsUnallocated() &&
2333 UnallocatedOperand::cast(&to)->HasRegisterPolicy())) {
2334 from_use->set_spill_detrimental();
2335 }
2336 // Resolve use position hints just created.
2337 if (to_use != nullptr && from_use != nullptr) {
2338 to_use->ResolveHint(from_use);
2339 from_use->ResolveHint(to_use);
2340 }
2341 DCHECK_IMPLIES(to_use != nullptr, to_use->IsResolved())((void) 0);
2342 DCHECK_IMPLIES(from_use != nullptr, from_use->IsResolved())((void) 0);
2343 // Potentially resolve phi hint.
2344 if (phi_vreg != -1) ResolvePhiHint(&from, from_use);
2345 }
2346 }
2347 }
2348}
2349
2350void LiveRangeBuilder::ProcessPhis(const InstructionBlock* block,
2351 BitVector* live) {
2352 for (PhiInstruction* phi : block->phis()) {
2353 // The live range interval already ends at the first instruction of the
2354 // block.
2355 int phi_vreg = phi->virtual_register();
2356 live->Remove(phi_vreg);
2357 // Select a hint from a predecessor block that precedes this block in the
2358 // rpo order. In order of priority:
2359 // - Avoid hints from deferred blocks.
2360 // - Prefer hints from allocated (or explicit) operands.
2361 // - Prefer hints from empty blocks (containing just parallel moves and a
2362 // jump). In these cases, if we can elide the moves, the jump threader
2363 // is likely to be able to elide the jump.
2364 // The enforcement of hinting in rpo order is required because hint
2365 // resolution that happens later in the compiler pipeline visits
2366 // instructions in reverse rpo order, relying on the fact that phis are
2367 // encountered before their hints.
2368 InstructionOperand* hint = nullptr;
2369 int hint_preference = 0;
2370
2371 // The cost of hinting increases with the number of predecessors. At the
2372 // same time, the typical benefit decreases, since this hinting only
2373 // optimises the execution path through one predecessor. A limit of 2 is
2374 // sufficient to hit the common if/else pattern.
2375 int predecessor_limit = 2;
2376
2377 for (RpoNumber predecessor : block->predecessors()) {
2378 const InstructionBlock* predecessor_block =
2379 code()->InstructionBlockAt(predecessor);
2380 DCHECK_EQ(predecessor_block->rpo_number(), predecessor)((void) 0);
2381
2382 // Only take hints from earlier rpo numbers.
2383 if (predecessor >= block->rpo_number()) continue;
2384
2385 // Look up the predecessor instruction.
2386 const Instruction* predecessor_instr =
2387 GetLastInstruction(code(), predecessor_block);
2388 InstructionOperand* predecessor_hint = nullptr;
2389 // Phis are assigned in the END position of the last instruction in each
2390 // predecessor block.
2391 for (MoveOperands* move :
2392 *predecessor_instr->GetParallelMove(Instruction::END)) {
2393 InstructionOperand& to = move->destination();
2394 if (to.IsUnallocated() &&
2395 UnallocatedOperand::cast(to).virtual_register() == phi_vreg) {
2396 predecessor_hint = &move->source();
2397 break;
2398 }
2399 }
2400 DCHECK_NOT_NULL(predecessor_hint)((void) 0);
2401
2402 // For each predecessor, generate a score according to the priorities
2403 // described above, and pick the best one. Flags in higher-order bits have
2404 // a higher priority than those in lower-order bits.
2405 int predecessor_hint_preference = 0;
2406 const int kNotDeferredBlockPreference = (1 << 2);
2407 const int kMoveIsAllocatedPreference = (1 << 1);
2408 const int kBlockIsEmptyPreference = (1 << 0);
2409
2410 // - Avoid hints from deferred blocks.
2411 if (!predecessor_block->IsDeferred()) {
2412 predecessor_hint_preference |= kNotDeferredBlockPreference;
2413 }
2414
2415 // - Prefer hints from allocated operands.
2416 //
2417 // Already-allocated operands are typically assigned using the parallel
2418 // moves on the last instruction. For example:
2419 //
2420 // gap (v101 = [x0|R|w32]) (v100 = v101)
2421 // ArchJmp
2422 // ...
2423 // phi: v100 = v101 v102
2424 //
2425 // We have already found the END move, so look for a matching START move
2426 // from an allocated operand.
2427 //
2428 // Note that we cannot simply look up data()->live_ranges()[vreg] here
2429 // because the live ranges are still being built when this function is
2430 // called.
2431 // TODO(v8): Find a way to separate hinting from live range analysis in
2432 // BuildLiveRanges so that we can use the O(1) live-range look-up.
2433 auto moves = predecessor_instr->GetParallelMove(Instruction::START);
2434 if (moves != nullptr) {
2435 for (MoveOperands* move : *moves) {
2436 InstructionOperand& to = move->destination();
2437 if (predecessor_hint->Equals(to)) {
2438 if (move->source().IsAllocated()) {
2439 predecessor_hint_preference |= kMoveIsAllocatedPreference;
2440 }
2441 break;
2442 }
2443 }
2444 }
2445
2446 // - Prefer hints from empty blocks.
2447 if (predecessor_block->last_instruction_index() ==
2448 predecessor_block->first_instruction_index()) {
2449 predecessor_hint_preference |= kBlockIsEmptyPreference;
2450 }
2451
2452 if ((hint == nullptr) ||
2453 (predecessor_hint_preference > hint_preference)) {
2454 // Take the hint from this predecessor.
2455 hint = predecessor_hint;
2456 hint_preference = predecessor_hint_preference;
2457 }
2458
2459 if (--predecessor_limit <= 0) break;
2460 }
2461 DCHECK_NOT_NULL(hint)((void) 0);
2462
2463 LifetimePosition block_start = LifetimePosition::GapFromInstructionIndex(
2464 block->first_instruction_index());
2465 UsePosition* use_pos = Define(block_start, &phi->output(), hint,
2466 UsePosition::HintTypeForOperand(*hint),
2467 SpillModeForBlock(block));
2468 MapPhiHint(hint, use_pos);
2469 }
2470}
2471
2472void LiveRangeBuilder::ProcessLoopHeader(const InstructionBlock* block,
2473 BitVector* live) {
2474 DCHECK(block->IsLoopHeader())((void) 0);
2475 // Add a live range stretching from the first loop instruction to the last
2476 // for each value live on entry to the header.
2477 LifetimePosition start = LifetimePosition::GapFromInstructionIndex(
2478 block->first_instruction_index());
2479 LifetimePosition end = LifetimePosition::GapFromInstructionIndex(
2480 code()->LastLoopInstructionIndex(block))
2481 .NextFullStart();
2482 for (int operand_index : *live) {
2483 TopLevelLiveRange* range = data()->GetOrCreateLiveRangeFor(operand_index);
2484 range->EnsureInterval(start, end, allocation_zone(),
2485 data()->is_trace_alloc());
2486 }
2487 // Insert all values into the live in sets of all blocks in the loop.
2488 for (int i = block->rpo_number().ToInt() + 1; i < block->loop_end().ToInt();
2489 ++i) {
2490 live_in_sets()[i]->Union(*live);
2491 }
2492}
2493
2494void LiveRangeBuilder::BuildLiveRanges() {
2495 // Process the blocks in reverse order.
2496 for (int block_id = code()->InstructionBlockCount() - 1; block_id >= 0;
1
Assuming 'block_id' is < 0
2
Loop condition is false. Execution continues on line 2516
2497 --block_id) {
2498 data_->tick_counter()->TickAndMaybeEnterSafepoint();
2499 InstructionBlock* block =
2500 code()->InstructionBlockAt(RpoNumber::FromInt(block_id));
2501 BitVector* live = ComputeLiveOut(block, data());
2502 // Initially consider all live_out values live for the entire block. We
2503 // will shorten these intervals if necessary.
2504 AddInitialIntervals(block, live);
2505 // Process the instructions in reverse order, generating and killing
2506 // live values.
2507 ProcessInstructions(block, live);
2508 // All phi output operands are killed by this block.
2509 ProcessPhis(block, live);
2510 // Now live is live_in for this block except not including values live
2511 // out on backward successor edges.
2512 if (block->IsLoopHeader()) ProcessLoopHeader(block, live);
2513 live_in_sets()[block_id] = live;
2514 }
2515 // Postprocess the ranges.
2516 const size_t live_ranges_size = data()->live_ranges().size();
2517 for (TopLevelLiveRange* range : data()->live_ranges()) {
2518 data_->tick_counter()->TickAndMaybeEnterSafepoint();
2519 CHECK_EQ(live_ranges_size,do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(data()->live_ranges
().size())>::type>((live_ranges_size), (data()->live_ranges
().size())); do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal
("Check failed: %s.", "live_ranges_size" " " "==" " " "data()->live_ranges().size()"
); } } while (false); } while (false)
2520 data()->live_ranges().size())do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(data()->live_ranges
().size())>::type>((live_ranges_size), (data()->live_ranges
().size())); do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal
("Check failed: %s.", "live_ranges_size" " " "==" " " "data()->live_ranges().size()"
); } } while (false); } while (false)
; // TODO(neis): crbug.com/831822
2521 if (range == nullptr) continue;
2522 // Give slots to all ranges with a non fixed slot use.
2523 if (range->has_slot_use() && range->HasNoSpillType()) {
2524 SpillMode spill_mode =
2525 range->slot_use_kind() ==
2526 TopLevelLiveRange::SlotUseKind::kDeferredSlotUse
2527 ? SpillMode::kSpillDeferred
2528 : SpillMode::kSpillAtDefinition;
2529 data()->AssignSpillRangeToLiveRange(range, spill_mode);
2530 }
2531 // TODO(bmeurer): This is a horrible hack to make sure that for constant
2532 // live ranges, every use requires the constant to be in a register.
2533 // Without this hack, all uses with "any" policy would get the constant
2534 // operand assigned.
2535 if (range->HasSpillOperand() && range->GetSpillOperand()->IsConstant()) {
2536 for (UsePosition* pos = range->first_pos(); pos != nullptr;
2537 pos = pos->next()) {
2538 if (pos->type() == UsePositionType::kRequiresSlot ||
2539 pos->type() == UsePositionType::kRegisterOrSlotOrConstant) {
2540 continue;
2541 }
2542 UsePositionType new_type = UsePositionType::kRegisterOrSlot;
2543 // Can't mark phis as needing a register.
2544 if (!pos->pos().IsGapPosition()) {
2545 new_type = UsePositionType::kRequiresRegister;
2546 }
2547 pos->set_type(new_type, true);
2548 }
2549 }
2550 range->ResetCurrentHintPosition();
2551 }
2552 for (auto preassigned : data()->preassigned_slot_ranges()) {
2553 TopLevelLiveRange* range = preassigned.first;
2554 int slot_id = preassigned.second;
2555 SpillRange* spill = range->HasSpillRange()
3
'?' condition is false
2556 ? range->GetSpillRange()
2557 : data()->AssignSpillRangeToLiveRange(
4
Calling 'TopTierRegisterAllocationData::AssignSpillRangeToLiveRange'
2558 range, SpillMode::kSpillAtDefinition);
2559 spill->set_assigned_slot(slot_id);
2560 }
2561#ifdef DEBUG
2562 Verify();
2563#endif
2564}
2565
2566void LiveRangeBuilder::MapPhiHint(InstructionOperand* operand,
2567 UsePosition* use_pos) {
2568 DCHECK(!use_pos->IsResolved())((void) 0);
2569 auto res = phi_hints_.insert(std::make_pair(operand, use_pos));
2570 DCHECK(res.second)((void) 0);
2571 USE(res)do { ::v8::base::Use unused_tmp_array_for_use_macro[]{res}; (
void)unused_tmp_array_for_use_macro; } while (false)
;
2572}
2573
2574void LiveRangeBuilder::ResolvePhiHint(InstructionOperand* operand,
2575 UsePosition* use_pos) {
2576 auto it = phi_hints_.find(operand);
2577 if (it == phi_hints_.end()) return;
2578 DCHECK(!it->second->IsResolved())((void) 0);
2579 it->second->ResolveHint(use_pos);
2580}
2581
2582void LiveRangeBuilder::Verify() const {
2583 for (auto& hint : phi_hints_) {
2584 CHECK(hint.second->IsResolved())do { if ((__builtin_expect(!!(!(hint.second->IsResolved())
), 0))) { V8_Fatal("Check failed: %s.", "hint.second->IsResolved()"
); } } while (false)
;
2585 }
2586 for (const TopLevelLiveRange* current : data()->live_ranges()) {
2587 if (current != nullptr && !current->IsEmpty()) {
2588 // New LiveRanges should not be split.
2589 CHECK_NULL(current->next())do { if ((__builtin_expect(!!(!((current->next()) == nullptr
)), 0))) { V8_Fatal("Check failed: %s.", "(current->next()) == nullptr"
); } } while (false)
;
2590 // General integrity check.
2591 current->Verify();
2592 const UseInterval* first = current->first_interval();
2593 if (first->next() == nullptr) continue;
2594
2595 // Consecutive intervals should not end and start in the same block,
2596 // otherwise the intervals should have been joined, because the
2597 // variable is live throughout that block.
2598 CHECK(NextIntervalStartsInDifferentBlocks(first))do { if ((__builtin_expect(!!(!(NextIntervalStartsInDifferentBlocks
(first))), 0))) { V8_Fatal("Check failed: %s.", "NextIntervalStartsInDifferentBlocks(first)"
); } } while (false)
;
2599
2600 for (const UseInterval* i = first->next(); i != nullptr; i = i->next()) {
2601 // Except for the first interval, the other intevals must start at
2602 // a block boundary, otherwise data wouldn't flow to them.
2603 CHECK(IntervalStartsAtBlockBoundary(i))do { if ((__builtin_expect(!!(!(IntervalStartsAtBlockBoundary
(i))), 0))) { V8_Fatal("Check failed: %s.", "IntervalStartsAtBlockBoundary(i)"
); } } while (false)
;
2604 // The last instruction of the predecessors of the block the interval
2605 // starts must be covered by the range.
2606 CHECK(IntervalPredecessorsCoveredByRange(i, current))do { if ((__builtin_expect(!!(!(IntervalPredecessorsCoveredByRange
(i, current))), 0))) { V8_Fatal("Check failed: %s.", "IntervalPredecessorsCoveredByRange(i, current)"
); } } while (false)
;
2607 if (i->next() != nullptr) {
2608 // Check the consecutive intervals property, except for the last
2609 // interval, where it doesn't apply.
2610 CHECK(NextIntervalStartsInDifferentBlocks(i))do { if ((__builtin_expect(!!(!(NextIntervalStartsInDifferentBlocks
(i))), 0))) { V8_Fatal("Check failed: %s.", "NextIntervalStartsInDifferentBlocks(i)"
); } } while (false)
;
2611 }
2612 }
2613 }
2614 }
2615}
2616
2617bool LiveRangeBuilder::IntervalStartsAtBlockBoundary(
2618 const UseInterval* interval) const {
2619 LifetimePosition start = interval->start();
2620 if (!start.IsFullStart()) return false;
2621 int instruction_index = start.ToInstructionIndex();
2622 const InstructionBlock* block =
2623 data()->code()->GetInstructionBlock(instruction_index);
2624 return block->first_instruction_index() == instruction_index;
2625}
2626
2627bool LiveRangeBuilder::IntervalPredecessorsCoveredByRange(
2628 const UseInterval* interval, const TopLevelLiveRange* range) const {
2629 LifetimePosition start = interval->start();
2630 int instruction_index = start.ToInstructionIndex();
2631 const InstructionBlock* block =
2632 data()->code()->GetInstructionBlock(instruction_index);
2633 for (RpoNumber pred_index : block->predecessors()) {
2634 const InstructionBlock* predecessor =
2635 data()->code()->InstructionBlockAt(pred_index);
2636 LifetimePosition last_pos = LifetimePosition::GapFromInstructionIndex(
2637 predecessor->last_instruction_index());
2638 last_pos = last_pos.NextStart().End();
2639 if (!range->Covers(last_pos)) return false;
2640 }
2641 return true;
2642}
2643
2644bool LiveRangeBuilder::NextIntervalStartsInDifferentBlocks(
2645 const UseInterval* interval) const {
2646 DCHECK_NOT_NULL(interval->next())((void) 0);
2647 LifetimePosition end = interval->end();
2648 LifetimePosition next_start = interval->next()->start();
2649 // Since end is not covered, but the previous position is, move back a
2650 // position
2651 end = end.IsStart() ? end.PrevStart().End() : end.Start();
2652 int last_covered_index = end.ToInstructionIndex();
2653 const InstructionBlock* block =
2654 data()->code()->GetInstructionBlock(last_covered_index);
2655 const InstructionBlock* next_block =
2656 data()->code()->GetInstructionBlock(next_start.ToInstructionIndex());
2657 return block->rpo_number() < next_block->rpo_number();
2658}
2659
2660void BundleBuilder::BuildBundles() {
2661 TRACE("Build bundles\n");
2662 // Process the blocks in reverse order.
2663 for (int block_id = code()->InstructionBlockCount() - 1; block_id >= 0;
2664 --block_id) {
2665 InstructionBlock* block =
2666 code()->InstructionBlockAt(RpoNumber::FromInt(block_id));
2667 TRACE("Block B%d\n", block_id);
2668 for (auto phi : block->phis()) {
2669 LiveRange* out_range =
2670 data()->GetOrCreateLiveRangeFor(phi->virtual_register());
2671 LiveRangeBundle* out = out_range->get_bundle();
2672 if (out == nullptr) {
2673 out = data()->allocation_zone()->New<LiveRangeBundle>(
2674 data()->allocation_zone(), next_bundle_id_++);
2675 out->TryAddRange(out_range);
2676 }
2677 TRACE("Processing phi for v%d with %d:%d\n", phi->virtual_register(),
2678 out_range->TopLevel()->vreg(), out_range->relative_id());
2679 bool phi_interferes_with_backedge_input = false;
2680 for (auto input : phi->operands()) {
2681 LiveRange* input_range = data()->GetOrCreateLiveRangeFor(input);
2682 TRACE("Input value v%d with range %d:%d\n", input,
2683 input_range->TopLevel()->vreg(), input_range->relative_id());
2684 LiveRangeBundle* input_bundle = input_range->get_bundle();
2685 if (input_bundle != nullptr) {
2686 TRACE("Merge\n");
2687 LiveRangeBundle* merged = LiveRangeBundle::TryMerge(
2688 out, input_bundle, data()->is_trace_alloc());
2689 if (merged != nullptr) {
2690 DCHECK_EQ(out_range->get_bundle(), merged)((void) 0);
2691 DCHECK_EQ(input_range->get_bundle(), merged)((void) 0);
2692 out = merged;
2693 TRACE("Merged %d and %d to %d\n", phi->virtual_register(), input,
2694 out->id());
2695 } else if (input_range->Start() > out_range->Start()) {
2696 // We are only interested in values defined after the phi, because
2697 // those are values that will go over a back-edge.
2698 phi_interferes_with_backedge_input = true;
2699 }
2700 } else {
2701 TRACE("Add\n");
2702 if (out->TryAddRange(input_range)) {
2703 TRACE("Added %d and %d to %d\n", phi->virtual_register(), input,
2704 out->id());
2705 } else if (input_range->Start() > out_range->Start()) {
2706 // We are only interested in values defined after the phi, because
2707 // those are values that will go over a back-edge.
2708 phi_interferes_with_backedge_input = true;
2709 }
2710 }
2711 }
2712 // Spilling the phi at the loop header is not beneficial if there is
2713 // a back-edge with an input for the phi that interferes with the phi's
2714 // value, because in case that input gets spilled it might introduce
2715 // a stack-to-stack move at the back-edge.
2716 if (phi_interferes_with_backedge_input)
2717 out_range->TopLevel()->set_spilling_at_loop_header_not_beneficial();
2718 }
2719 TRACE("Done block B%d\n", block_id);
2720 }
2721}
2722
2723bool LiveRangeBundle::TryAddRange(LiveRange* range) {
2724 DCHECK_NULL(range->get_bundle())((void) 0);
2725 // We may only add a new live range if its use intervals do not
2726 // overlap with existing intervals in the bundle.
2727 if (UsesOverlap(range->first_interval())) return false;
2728 ranges_.insert(range);
2729 range->set_bundle(this);
2730 InsertUses(range->first_interval());
2731 return true;
2732}
2733
2734LiveRangeBundle* LiveRangeBundle::TryMerge(LiveRangeBundle* lhs,
2735 LiveRangeBundle* rhs,
2736 bool trace_alloc) {
2737 if (rhs == lhs) return lhs;
2738
2739 auto iter1 = lhs->uses_.begin();
2740 auto iter2 = rhs->uses_.begin();
2741
2742 while (iter1 != lhs->uses_.end() && iter2 != rhs->uses_.end()) {
2743 if (iter1->start >= iter2->end) {
2744 ++iter2;
2745 } else if (iter2->start >= iter1->end) {
2746 ++iter1;
2747 } else {
2748 TRACE_COND(trace_alloc, "No merge %d:%d %d:%d\n", iter1->start,
2749 iter1->end, iter2->start, iter2->end);
2750 return nullptr;
2751 }
2752 }
2753 // Uses are disjoint, merging is possible.
2754 if (lhs->uses_.size() < rhs->uses_.size()) {
2755 // Merge the smallest bundle into the biggest.
2756 std::swap(lhs, rhs);
2757 }
2758 for (auto it = rhs->ranges_.begin(); it != rhs->ranges_.end(); ++it) {
2759 (*it)->set_bundle(lhs);
2760 lhs->InsertUses((*it)->first_interval());
2761 }
2762 lhs->ranges_.insert(rhs->ranges_.begin(), rhs->ranges_.end());
2763 rhs->ranges_.clear();
2764 return lhs;
2765}
2766
2767void LiveRangeBundle::MergeSpillRangesAndClear() {
2768 DCHECK_IMPLIES(ranges_.empty(), uses_.empty())((void) 0);
2769 SpillRange* target = nullptr;
2770 for (auto range : ranges_) {
2771 if (range->TopLevel()->HasSpillRange()) {
2772 SpillRange* current = range->TopLevel()->GetSpillRange();
2773 if (target == nullptr) {
2774 target = current;
2775 } else if (target != current) {
2776 target->TryMerge(current);
2777 }
2778 }
2779 }
2780 // Clear the fields so that we don't try to merge the spill ranges again when
2781 // we hit the same bundle from a different LiveRange in AssignSpillSlots.
2782 // LiveRangeBundles are not used after this.
2783 ranges_.clear();
2784 uses_.clear();
2785}
2786
2787RegisterAllocator::RegisterAllocator(TopTierRegisterAllocationData* data,
2788 RegisterKind kind)
2789 : data_(data),
2790 mode_(kind),
2791 num_registers_(GetRegisterCount(data->config(), kind)),
2792 num_allocatable_registers_(
2793 GetAllocatableRegisterCount(data->config(), kind)),
2794 allocatable_register_codes_(
2795 GetAllocatableRegisterCodes(data->config(), kind)),
2796 check_fp_aliasing_(false) {
2797 if (kFPAliasing == AliasingKind::kCombine && kind == RegisterKind::kDouble) {
2798 check_fp_aliasing_ = (data->code()->representation_mask() &
2799 (kFloat32Bit | kSimd128Bit)) != 0;
2800 }
2801}
2802
2803LifetimePosition RegisterAllocator::GetSplitPositionForInstruction(
2804 const LiveRange* range, int instruction_index) {
2805 LifetimePosition ret = LifetimePosition::Invalid();
2806
2807 ret = LifetimePosition::GapFromInstructionIndex(instruction_index);
2808 if (range->Start() >= ret || ret >= range->End()) {
2809 return LifetimePosition::Invalid();
2810 }
2811 return ret;
2812}
2813
2814void RegisterAllocator::SplitAndSpillRangesDefinedByMemoryOperand() {
2815 size_t initial_range_count = data()->live_ranges().size();
2816 for (size_t i = 0; i < initial_range_count; ++i) {
2817 CHECK_EQ(initial_range_count,do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(initial_range_count)>::type
, typename ::v8::base::pass_value_or_ref<decltype(data()->
live_ranges().size())>::type>((initial_range_count), (data
()->live_ranges().size())); do { if ((__builtin_expect(!!(
!(_cmp)), 0))) { V8_Fatal("Check failed: %s.", "initial_range_count"
" " "==" " " "data()->live_ranges().size()"); } } while (
false); } while (false)
2818 data()->live_ranges().size())do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(initial_range_count)>::type
, typename ::v8::base::pass_value_or_ref<decltype(data()->
live_ranges().size())>::type>((initial_range_count), (data
()->live_ranges().size())); do { if ((__builtin_expect(!!(
!(_cmp)), 0))) { V8_Fatal("Check failed: %s.", "initial_range_count"
" " "==" " " "data()->live_ranges().size()"); } } while (
false); } while (false)
; // TODO(neis): crbug.com/831822
2819 TopLevelLiveRange* range = data()->live_ranges()[i];
2820 if (!CanProcessRange(range)) continue;
2821 // Only assume defined by memory operand if we are guaranteed to spill it or
2822 // it has a spill operand.
2823 if (range->HasNoSpillType() ||
2824 (range->HasSpillRange() && !range->has_non_deferred_slot_use())) {
2825 continue;
2826 }
2827 LifetimePosition start = range->Start();
2828 TRACE("Live range %d:%d is defined by a spill operand.\n",
2829 range->TopLevel()->vreg(), range->relative_id());
2830 LifetimePosition next_pos = start;
2831 if (next_pos.IsGapPosition()) {
2832 next_pos = next_pos.NextStart();
2833 }
2834
2835 UsePosition* pos = range->NextUsePositionRegisterIsBeneficial(next_pos);
2836 // If the range already has a spill operand and it doesn't need a
2837 // register immediately, split it and spill the first part of the range.
2838 if (pos == nullptr) {
2839 Spill(range, SpillMode::kSpillAtDefinition);
2840 } else if (pos->pos() > range->Start().NextStart()) {
2841 // Do not spill live range eagerly if use position that can benefit from
2842 // the register is too close to the start of live range.
2843 LifetimePosition split_pos = GetSplitPositionForInstruction(
2844 range, pos->pos().ToInstructionIndex());
2845 // There is no place to split, so we can't split and spill.
2846 if (!split_pos.IsValid()) continue;
2847
2848 split_pos =
2849 FindOptimalSplitPos(range->Start().NextFullStart(), split_pos);
2850
2851 SplitRangeAt(range, split_pos);
2852 Spill(range, SpillMode::kSpillAtDefinition);
2853 }
2854 }
2855}
2856
2857LiveRange* RegisterAllocator::SplitRangeAt(LiveRange* range,
2858 LifetimePosition pos) {
2859 DCHECK(!range->TopLevel()->IsFixed())((void) 0);
2860 TRACE("Splitting live range %d:%d at %d\n", range->TopLevel()->vreg(),
2861 range->relative_id(), pos.value());
2862
2863 if (pos <= range->Start()) return range;
2864
2865 // We can't properly connect liveranges if splitting occurred at the end
2866 // a block.
2867 DCHECK(pos.IsStart() || pos.IsGapPosition() ||((void) 0)
2868 (GetInstructionBlock(code(), pos)->last_instruction_index() !=((void) 0)
2869 pos.ToInstructionIndex()))((void) 0);
2870
2871 LiveRange* result = range->SplitAt(pos, allocation_zone());
2872 return result;
2873}
2874
2875LiveRange* RegisterAllocator::SplitBetween(LiveRange* range,
2876 LifetimePosition start,
2877 LifetimePosition end) {
2878 DCHECK(!range->TopLevel()->IsFixed())((void) 0);
2879 TRACE("Splitting live range %d:%d in position between [%d, %d]\n",
2880 range->TopLevel()->vreg(), range->relative_id(), start.value(),
2881 end.value());
2882
2883 LifetimePosition split_pos = FindOptimalSplitPos(start, end);
2884 DCHECK(split_pos >= start)((void) 0);
2885 return SplitRangeAt(range, split_pos);
2886}
2887
2888LifetimePosition RegisterAllocator::FindOptimalSplitPos(LifetimePosition start,
2889 LifetimePosition end) {
2890 int start_instr = start.ToInstructionIndex();
2891 int end_instr = end.ToInstructionIndex();
2892 DCHECK_LE(start_instr, end_instr)((void) 0);
2893
2894 // We have no choice
2895 if (start_instr == end_instr) return end;
2896
2897 const InstructionBlock* start_block = GetInstructionBlock(code(), start);
2898 const InstructionBlock* end_block = GetInstructionBlock(code(), end);
2899
2900 if (end_block == start_block) {
2901 // The interval is split in the same basic block. Split at the latest
2902 // possible position.
2903 return end;
2904 }
2905
2906 const InstructionBlock* block = end_block;
2907 // Find header of outermost loop.
2908 do {
2909 const InstructionBlock* loop = GetContainingLoop(code(), block);
2910 if (loop == nullptr ||
2911 loop->rpo_number().ToInt() <= start_block->rpo_number().ToInt()) {
2912 // No more loops or loop starts before the lifetime start.
2913 break;
2914 }
2915 block = loop;
2916 } while (true);
2917
2918 // We did not find any suitable outer loop. Split at the latest possible
2919 // position unless end_block is a loop header itself.
2920 if (block == end_block && !end_block->IsLoopHeader()) return end;
2921
2922 return LifetimePosition::GapFromInstructionIndex(
2923 block->first_instruction_index());
2924}
2925
2926LifetimePosition RegisterAllocator::FindOptimalSpillingPos(
2927 LiveRange* range, LifetimePosition pos, SpillMode spill_mode,
2928 LiveRange** begin_spill_out) {
2929 *begin_spill_out = range;
2930 // TODO(herhut): Be more clever here as long as we do not move pos out of
2931 // deferred code.
2932 if (spill_mode == SpillMode::kSpillDeferred) return pos;
2933 const InstructionBlock* block = GetInstructionBlock(code(), pos.Start());
2934 const InstructionBlock* loop_header =
2935 block->IsLoopHeader() ? block : GetContainingLoop(code(), block);
2936 if (loop_header == nullptr) return pos;
2937
2938 while (loop_header != nullptr) {
2939 // We are going to spill live range inside the loop.
2940 // If possible try to move spilling position backwards to loop header.
2941 // This will reduce number of memory moves on the back edge.
2942 LifetimePosition loop_start = LifetimePosition::GapFromInstructionIndex(
2943 loop_header->first_instruction_index());
2944 // Stop if we moved to a loop header before the value is defined or
2945 // at the define position that is not beneficial to spill.
2946 if (range->TopLevel()->Start() > loop_start ||
2947 (range->TopLevel()->Start() == loop_start &&
2948 range->TopLevel()->SpillAtLoopHeaderNotBeneficial()))
2949 return pos;
2950
2951 LiveRange* live_at_header = range->TopLevel()->GetChildCovers(loop_start);
2952
2953 if (live_at_header != nullptr && !live_at_header->spilled()) {
2954 for (LiveRange* check_use = live_at_header;
2955 check_use != nullptr && check_use->Start() < pos;
2956 check_use = check_use->next()) {
2957 // If we find a use for which spilling is detrimental, don't spill
2958 // at the loop header
2959 UsePosition* next_use =
2960 check_use->NextUsePositionSpillDetrimental(loop_start);
2961 // UsePosition at the end of a UseInterval may
2962 // have the same value as the start of next range.
2963 if (next_use != nullptr && next_use->pos() <= pos) {
2964 return pos;
2965 }
2966 }
2967 // No register beneficial use inside the loop before the pos.
2968 *begin_spill_out = live_at_header;
2969 pos = loop_start;
2970 }
2971
2972 // Try hoisting out to an outer loop.
2973 loop_header = GetContainingLoop(code(), loop_header);
2974 }
2975 return pos;
2976}
2977
2978void RegisterAllocator::Spill(LiveRange* range, SpillMode spill_mode) {
2979 DCHECK(!range->spilled())((void) 0);
2980 DCHECK(spill_mode == SpillMode::kSpillAtDefinition ||((void) 0)
2981 GetInstructionBlock(code(), range->Start())->IsDeferred())((void) 0);
2982 TopLevelLiveRange* first = range->TopLevel();
2983 TRACE("Spilling live range %d:%d mode %d\n", first->vreg(),
2984 range->relative_id(), spill_mode);
2985
2986 TRACE("Starting spill type is %d\n", static_cast<int>(first->spill_type()));
2987 if (first->HasNoSpillType()) {
2988 TRACE("New spill range needed");
2989 data()->AssignSpillRangeToLiveRange(first, spill_mode);
2990 }
2991 // Upgrade the spillmode, in case this was only spilled in deferred code so
2992 // far.
2993 if ((spill_mode == SpillMode::kSpillAtDefinition) &&
2994 (first->spill_type() ==
2995 TopLevelLiveRange::SpillType::kDeferredSpillRange)) {
2996 TRACE("Upgrading\n");
2997 first->set_spill_type(TopLevelLiveRange::SpillType::kSpillRange);
2998 }
2999 TRACE("Final spill type is %d\n", static_cast<int>(first->spill_type()));
3000 range->Spill();
3001}
3002
3003const char* RegisterAllocator::RegisterName(int register_code) const {
3004 if (register_code == kUnassignedRegister) return "unassigned";
3005 switch (mode()) {
3006 case RegisterKind::kGeneral:
3007 return i::RegisterName(Register::from_code(register_code));
3008 case RegisterKind::kDouble:
3009 return i::RegisterName(DoubleRegister::from_code(register_code));
3010 case RegisterKind::kSimd128:
3011 return i::RegisterName(Simd128Register::from_code(register_code));
3012 }
3013}
3014
3015LinearScanAllocator::LinearScanAllocator(TopTierRegisterAllocationData* data,
3016 RegisterKind kind, Zone* local_zone)
3017 : RegisterAllocator(data, kind),
3018 unhandled_live_ranges_(local_zone),
3019 active_live_ranges_(local_zone),
3020 inactive_live_ranges_(num_registers(), InactiveLiveRangeQueue(local_zone),
3021 local_zone),
3022 next_active_ranges_change_(LifetimePosition::Invalid()),
3023 next_inactive_ranges_change_(LifetimePosition::Invalid()) {
3024 active_live_ranges().reserve(8);
3025}
3026
3027void LinearScanAllocator::MaybeSpillPreviousRanges(LiveRange* begin_range,
3028 LifetimePosition begin_pos,
3029 LiveRange* end_range) {
3030 // Spill begin_range after begin_pos, then spill every live range of this
3031 // virtual register until but excluding end_range.
3032 DCHECK(begin_range->Covers(begin_pos))((void) 0);
3033 DCHECK_EQ(begin_range->TopLevel(), end_range->TopLevel())((void) 0);
3034
3035 if (begin_range != end_range) {
3036 DCHECK_LE(begin_range->End(), end_range->Start())((void) 0);
3037 if (!begin_range->spilled()) {
3038 SpillAfter(begin_range, begin_pos, SpillMode::kSpillAtDefinition);
3039 }
3040 for (LiveRange* range = begin_range->next(); range != end_range;
3041 range = range->next()) {
3042 if (!range->spilled()) {
3043 range->Spill();
3044 }
3045 }
3046 }
3047}
3048
3049void LinearScanAllocator::MaybeUndoPreviousSplit(LiveRange* range) {
3050 if (range->next() != nullptr && range->next()->ShouldRecombine()) {
3051 LiveRange* to_remove = range->next();
3052 TRACE("Recombining %d:%d with %d\n", range->TopLevel()->vreg(),
3053 range->relative_id(), to_remove->relative_id());
3054
3055 // Remove the range from unhandled, as attaching it will change its
3056 // state and hence ordering in the unhandled set.
3057 auto removed_cnt = unhandled_live_ranges().erase(to_remove);
3058 DCHECK_EQ(removed_cnt, 1)((void) 0);
3059 USE(removed_cnt)do { ::v8::base::Use unused_tmp_array_for_use_macro[]{removed_cnt
}; (void)unused_tmp_array_for_use_macro; } while (false)
;
3060
3061 range->AttachToNext();
3062 } else if (range->next() != nullptr) {
3063 TRACE("No recombine for %d:%d to %d\n", range->TopLevel()->vreg(),
3064 range->relative_id(), range->next()->relative_id());
3065 }
3066}
3067
3068void LinearScanAllocator::SpillNotLiveRanges(RangeWithRegisterSet* to_be_live,
3069 LifetimePosition position,
3070 SpillMode spill_mode) {
3071 for (auto it = active_live_ranges().begin();
3072 it != active_live_ranges().end();) {
3073 LiveRange* active_range = *it;
3074 TopLevelLiveRange* toplevel = (*it)->TopLevel();
3075 auto found = to_be_live->find({toplevel, kUnassignedRegister});
3076 if (found == to_be_live->end()) {
3077 // Is not contained in {to_be_live}, spill it.
3078 // Fixed registers are exempt from this. They might have been
3079 // added from inactive at the block boundary but we know that
3080 // they cannot conflict as they are built before register
3081 // allocation starts. It would be algorithmically fine to split
3082 // them and reschedule but the code does not allow to do this.
3083 if (toplevel->IsFixed()) {
3084 TRACE("Keeping reactivated fixed range for %s\n",
3085 RegisterName(toplevel->assigned_register()));
3086 ++it;
3087 } else {
3088 // When spilling a previously spilled/reloaded range, we add back the
3089 // tail that we might have split off when we reloaded/spilled it
3090 // previously. Otherwise we might keep generating small split-offs.
3091 MaybeUndoPreviousSplit(active_range);
3092 TRACE("Putting back %d:%d\n", toplevel->vreg(),
3093 active_range->relative_id());
3094 LiveRange* split = SplitRangeAt(active_range, position);
3095 DCHECK_NE(split, active_range)((void) 0);
3096
3097 // Make sure we revisit this range once it has a use that requires
3098 // a register.
3099 UsePosition* next_use = split->NextRegisterPosition(position);
3100 if (next_use != nullptr) {
3101 // Move to the start of the gap before use so that we have a space
3102 // to perform the potential reload. Otherwise, do not spill but add
3103 // to unhandled for reallocation.
3104 LifetimePosition revisit_at = next_use->pos().FullStart();
3105 TRACE("Next use at %d\n", revisit_at.value());
3106 if (!data()->IsBlockBoundary(revisit_at)) {
3107 // Leave some space so we have enough gap room.
3108 revisit_at = revisit_at.PrevStart().FullStart();
3109 }
3110 // If this range became life right at the block boundary that we are
3111 // currently processing, we do not need to split it. Instead move it
3112 // to unhandled right away.
3113 if (position < revisit_at) {
3114 LiveRange* third_part = SplitRangeAt(split, revisit_at);
3115 DCHECK_NE(split, third_part)((void) 0);
3116 Spill(split, spill_mode);
3117 TRACE("Marking %d:%d to recombine\n", toplevel->vreg(),
3118 third_part->relative_id());
3119 third_part->SetRecombine();
3120 AddToUnhandled(third_part);
3121 } else {
3122 AddToUnhandled(split);
3123 }
3124 } else {
3125 Spill(split, spill_mode);
3126 }
3127 it = ActiveToHandled(it);
3128 }
3129 } else {
3130 // This range is contained in {to_be_live}, so we can keep it.
3131 int expected_register = (*found).expected_register;
3132 to_be_live->erase(found);
3133 if (expected_register == active_range->assigned_register()) {
3134 // Was life and in correct register, simply pass through.
3135 TRACE("Keeping %d:%d in %s\n", toplevel->vreg(),
3136 active_range->relative_id(),
3137 RegisterName(active_range->assigned_register()));
3138 ++it;
3139 } else {
3140 // Was life but wrong register. Split and schedule for
3141 // allocation.
3142 TRACE("Scheduling %d:%d\n", toplevel->vreg(),
3143 active_range->relative_id());
3144 LiveRange* split = SplitRangeAt(active_range, position);
3145 split->set_controlflow_hint(expected_register);
3146 AddToUnhandled(split);
3147 it = ActiveToHandled(it);
3148 }
3149 }
3150 }
3151}
3152
3153LiveRange* LinearScanAllocator::AssignRegisterOnReload(LiveRange* range,
3154 int reg) {
3155 // We know the register is currently free but it might be in
3156 // use by a currently inactive range. So we might not be able
3157 // to reload for the full distance. In such case, split here.
3158 // TODO(herhut):
3159 // It might be better if we could use the normal unhandled queue and
3160 // give reloading registers pecedence. That way we would compute the
3161 // intersection for the entire future.
3162 LifetimePosition new_end = range->End();
3163 for (int cur_reg = 0; cur_reg < num_registers(); ++cur_reg) {
3164 if ((kFPAliasing != AliasingKind::kCombine || !check_fp_aliasing()) &&
3165 cur_reg != reg) {
3166 continue;
3167 }
3168 for (const LiveRange* cur_inactive : inactive_live_ranges(cur_reg)) {
3169 if (kFPAliasing == AliasingKind::kCombine && check_fp_aliasing() &&
3170 !data()->config()->AreAliases(cur_inactive->representation(), cur_reg,
3171 range->representation(), reg)) {
3172 continue;
3173 }
3174 if (new_end <= cur_inactive->NextStart()) {
3175 // Inactive ranges are sorted by their next start, so the remaining
3176 // ranges cannot contribute to new_end.
3177 break;
3178 }
3179 auto next_intersection = cur_inactive->FirstIntersection(range);
3180 if (!next_intersection.IsValid()) continue;
3181 new_end = std::min(new_end, next_intersection);
3182 }
3183 }
3184 if (new_end != range->End()) {
3185 TRACE("Found new end for %d:%d at %d\n", range->TopLevel()->vreg(),
3186 range->relative_id(), new_end.value());
3187 LiveRange* tail = SplitRangeAt(range, new_end);
3188 AddToUnhandled(tail);
3189 }
3190 SetLiveRangeAssignedRegister(range, reg);
3191 return range;
3192}
3193
3194void LinearScanAllocator::ReloadLiveRanges(
3195 RangeWithRegisterSet const& to_be_live, LifetimePosition position) {
3196 // Assumption: All ranges in {to_be_live} are currently spilled and there are
3197 // no conflicting registers in the active ranges.
3198 // The former is ensured by SpillNotLiveRanges, the latter is by construction
3199 // of the to_be_live set.
3200 for (RangeWithRegister range_with_register : to_be_live) {
3201 TopLevelLiveRange* range = range_with_register.range;
3202 int reg = range_with_register.expected_register;
3203 LiveRange* to_resurrect = range->GetChildCovers(position);
3204 if (to_resurrect == nullptr) {
3205 // While the range was life until the end of the predecessor block, it is
3206 // not live in this block. Either there is a lifetime gap or the range
3207 // died.
3208 TRACE("No candidate for %d at %d\n", range->vreg(), position.value());
3209 } else {
3210 // We might be resurrecting a range that we spilled until its next use
3211 // before. In such cases, we have to unsplit it before processing as
3212 // otherwise we might get register changes from one range to the other
3213 // in the middle of blocks.
3214 // If there is a gap between this range and the next, we can just keep
3215 // it as a register change won't hurt.
3216 MaybeUndoPreviousSplit(to_resurrect);
3217 if (to_resurrect->Start() == position) {
3218 // This range already starts at this block. It might have been spilled,
3219 // so we have to unspill it. Otherwise, it is already in the unhandled
3220 // queue waiting for processing.
3221 DCHECK(!to_resurrect->HasRegisterAssigned())((void) 0);
3222 TRACE("Reload %d:%d starting at %d itself\n", range->vreg(),
3223 to_resurrect->relative_id(), position.value());
3224 if (to_resurrect->spilled()) {
3225 to_resurrect->Unspill();
3226 to_resurrect->set_controlflow_hint(reg);
3227 AddToUnhandled(to_resurrect);
3228 } else {
3229 // Assign the preassigned register if we know. Otherwise, nothing to
3230 // do as already in unhandeled.
3231 if (reg != kUnassignedRegister) {
3232 auto erased_cnt = unhandled_live_ranges().erase(to_resurrect);
3233 DCHECK_EQ(erased_cnt, 1)((void) 0);
3234 USE(erased_cnt)do { ::v8::base::Use unused_tmp_array_for_use_macro[]{erased_cnt
}; (void)unused_tmp_array_for_use_macro; } while (false)
;
3235 // We know that there is no conflict with active ranges, so just
3236 // assign the register to the range.
3237 to_resurrect = AssignRegisterOnReload(to_resurrect, reg);
3238 AddToActive(to_resurrect);
3239 }
3240 }
3241 } else {
3242 // This range was spilled before. We have to split it and schedule the
3243 // second part for allocation (or assign the register if we know).
3244 DCHECK(to_resurrect->spilled())((void) 0);
3245 LiveRange* split = SplitRangeAt(to_resurrect, position);
3246 TRACE("Reload %d:%d starting at %d as %d\n", range->vreg(),
3247 to_resurrect->relative_id(), split->Start().value(),
3248 split->relative_id());
3249 DCHECK_NE(split, to_resurrect)((void) 0);
3250 if (reg != kUnassignedRegister) {
3251 // We know that there is no conflict with active ranges, so just
3252 // assign the register to the range.
3253 split = AssignRegisterOnReload(split, reg);
3254 AddToActive(split);
3255 } else {
3256 // Let normal register assignment find a suitable register.
3257 split->set_controlflow_hint(reg);
3258 AddToUnhandled(split);
3259 }
3260 }
3261 }
3262 }
3263}
3264
3265RpoNumber LinearScanAllocator::ChooseOneOfTwoPredecessorStates(
3266 InstructionBlock* current_block, LifetimePosition boundary) {
3267 using SmallRangeVector =
3268 base::SmallVector<TopLevelLiveRange*,
3269 RegisterConfiguration::kMaxRegisters>;
3270 // Pick the state that would generate the least spill/reloads.
3271 // Compute vectors of ranges with imminent use for both sides.
3272 // As GetChildCovers is cached, it is cheaper to repeatedly
3273 // call is rather than compute a shared set first.
3274 auto& left = data()->GetSpillState(current_block->predecessors()[0]);
3275 auto& right = data()->GetSpillState(current_block->predecessors()[1]);
3276 SmallRangeVector left_used;
3277 for (const auto item : left) {
3278 LiveRange* at_next_block = item->TopLevel()->GetChildCovers(boundary);
3279 if (at_next_block != nullptr &&
3280 at_next_block->NextUsePositionRegisterIsBeneficial(boundary) !=
3281 nullptr) {
3282 left_used.emplace_back(item->TopLevel());
3283 }
3284 }
3285 SmallRangeVector right_used;
3286 for (const auto item : right) {
3287 LiveRange* at_next_block = item->TopLevel()->GetChildCovers(boundary);
3288 if (at_next_block != nullptr &&
3289 at_next_block->NextUsePositionRegisterIsBeneficial(boundary) !=
3290 nullptr) {
3291 right_used.emplace_back(item->TopLevel());
3292 }
3293 }
3294 if (left_used.empty() && right_used.empty()) {
3295 // There are no beneficial register uses. Look at any use at
3296 // all. We do not account for all uses, like flowing into a phi.
3297 // So we just look at ranges still being live.
3298 TRACE("Looking at only uses\n");
3299 for (const auto item : left) {
3300 LiveRange* at_next_block = item->TopLevel()->GetChildCovers(boundary);
3301 if (at_next_block != nullptr &&
3302 at_next_block->NextUsePosition(boundary) != nullptr) {
3303 left_used.emplace_back(item->TopLevel());
3304 }
3305 }
3306 for (const auto item : right) {
3307 LiveRange* at_next_block = item->TopLevel()->GetChildCovers(boundary);
3308 if (at_next_block != nullptr &&
3309 at_next_block->NextUsePosition(boundary) != nullptr) {
3310 right_used.emplace_back(item->TopLevel());
3311 }
3312 }
3313 }
3314 // Now left_used and right_used contains those ranges that matter.
3315 // Count which side matches this most.
3316 TRACE("Vote went %zu vs %zu\n", left_used.size(), right_used.size());
3317 return left_used.size() > right_used.size()
3318 ? current_block->predecessors()[0]
3319 : current_block->predecessors()[1];
3320}
3321
3322bool LinearScanAllocator::CheckConflict(MachineRepresentation rep, int reg,
3323 RangeWithRegisterSet* to_be_live) {
3324 for (RangeWithRegister range_with_reg : *to_be_live) {
3325 if (data()->config()->AreAliases(range_with_reg.range->representation(),
3326 range_with_reg.expected_register, rep,
3327 reg)) {
3328 return true;
3329 }
3330 }
3331 return false;
3332}
3333
3334void LinearScanAllocator::ComputeStateFromManyPredecessors(
3335 InstructionBlock* current_block, RangeWithRegisterSet* to_be_live) {
3336 struct Vote {
3337 size_t count;
3338 int used_registers[RegisterConfiguration::kMaxRegisters];
3339 };
3340 struct TopLevelLiveRangeComparator {
3341 bool operator()(const TopLevelLiveRange* lhs,
3342 const TopLevelLiveRange* rhs) const {
3343 return lhs->vreg() < rhs->vreg();
3344 }
3345 };
3346 ZoneMap<TopLevelLiveRange*, Vote, TopLevelLiveRangeComparator> counts(
3347 data()->allocation_zone());
3348 int deferred_blocks = 0;
3349 for (RpoNumber pred : current_block->predecessors()) {
3350 if (!ConsiderBlockForControlFlow(current_block, pred)) {
3351 // Back edges of a loop count as deferred here too.
3352 deferred_blocks++;
3353 continue;
3354 }
3355 const auto& pred_state = data()->GetSpillState(pred);
3356 for (LiveRange* range : pred_state) {
3357 // We might have spilled the register backwards, so the range we
3358 // stored might have lost its register. Ignore those.
3359 if (!range->HasRegisterAssigned()) continue;
3360 TopLevelLiveRange* toplevel = range->TopLevel();
3361 auto previous = counts.find(toplevel);
3362 if (previous == counts.end()) {
3363 auto result = counts.emplace(std::make_pair(toplevel, Vote{1, {0}}));
3364 CHECK(result.second)do { if ((__builtin_expect(!!(!(result.second)), 0))) { V8_Fatal
("Check failed: %s.", "result.second"); } } while (false)
;
3365 result.first->second.used_registers[range->assigned_register()]++;
3366 } else {
3367 previous->second.count++;
3368 previous->second.used_registers[range->assigned_register()]++;
3369 }
3370 }
3371 }
3372
3373 // Choose the live ranges from the majority.
3374 const size_t majority =
3375 (current_block->PredecessorCount() + 2 - deferred_blocks) / 2;
3376 bool taken_registers[RegisterConfiguration::kMaxRegisters] = {false};
3377 auto assign_to_live = [this, counts, majority](
3378 std::function<bool(TopLevelLiveRange*)> filter,
3379 RangeWithRegisterSet* to_be_live,
3380 bool* taken_registers) {
3381 bool check_aliasing =
3382 kFPAliasing == AliasingKind::kCombine && check_fp_aliasing();
3383 for (const auto& val : counts) {
3384 if (!filter(val.first)) continue;
3385 if (val.second.count >= majority) {
3386 int register_max = 0;
3387 int reg = kUnassignedRegister;
3388 bool conflict = false;
3389 int num_regs = num_registers();
3390 int num_codes = num_allocatable_registers();
3391 const int* codes = allocatable_register_codes();
3392 MachineRepresentation rep = val.first->representation();
3393 if (check_aliasing && (rep == MachineRepresentation::kFloat32 ||
3394 rep == MachineRepresentation::kSimd128))
3395 GetFPRegisterSet(rep, &num_regs, &num_codes, &codes);
3396 for (int idx = 0; idx < num_regs; idx++) {
3397 int uses = val.second.used_registers[idx];
3398 if (uses == 0) continue;
3399 if (uses > register_max || (conflict && uses == register_max)) {
3400 reg = idx;
3401 register_max = uses;
3402 conflict = check_aliasing ? CheckConflict(rep, reg, to_be_live)
3403 : taken_registers[reg];
3404 }
3405 }
3406 if (conflict) {
3407 reg = kUnassignedRegister;
3408 } else if (!check_aliasing) {
3409 taken_registers[reg] = true;
3410 }
3411 to_be_live->emplace(val.first, reg);
3412 TRACE("Reset %d as live due vote %zu in %s\n",
3413 val.first->TopLevel()->vreg(), val.second.count,
3414 RegisterName(reg));
3415 }
3416 }
3417 };
3418 // First round, process fixed registers, as these have precedence.
3419 // There is only one fixed range per register, so we cannot have
3420 // conflicts.
3421 assign_to_live([](TopLevelLiveRange* r) { return r->IsFixed(); }, to_be_live,
3422 taken_registers);
3423 // Second round, process the rest.
3424 assign_to_live([](TopLevelLiveRange* r) { return !r->IsFixed(); }, to_be_live,
3425 taken_registers);
3426}
3427
3428bool LinearScanAllocator::ConsiderBlockForControlFlow(
3429 InstructionBlock* current_block, RpoNumber predecessor) {
3430 // We ignore predecessors on back edges when looking for control flow effects,
3431 // as those lie in the future of allocation and we have no data yet. Also,
3432 // deferred bocks are ignored on deferred to non-deferred boundaries, as we do
3433 // not want them to influence allocation of non deferred code.
3434 return (predecessor < current_block->rpo_number()) &&
3435 (current_block->IsDeferred() ||
3436 !code()->InstructionBlockAt(predecessor)->IsDeferred());
3437}
3438
3439void LinearScanAllocator::UpdateDeferredFixedRanges(SpillMode spill_mode,
3440 InstructionBlock* block) {
3441 if (spill_mode == SpillMode::kSpillDeferred) {
3442 LifetimePosition max = LifetimePosition::InstructionFromInstructionIndex(
3443 LastDeferredInstructionIndex(block));
3444 // Adds range back to inactive, resolving resulting conflicts.
3445 auto add_to_inactive = [this, max](LiveRange* range) {
3446 AddToInactive(range);
3447 // Splits other if it conflicts with range. Other is placed in unhandled
3448 // for later reallocation.
3449 auto split_conflicting = [this, max](LiveRange* range, LiveRange* other,
3450 std::function<void(LiveRange*)>
3451 update_caches) {
3452 if (other->TopLevel()->IsFixed()) return;
3453 int reg = range->assigned_register();
3454 if (kFPAliasing != AliasingKind::kCombine || !check_fp_aliasing()) {
3455 if (other->assigned_register() != reg) {
3456 return;
3457 }
3458 } else {
3459 if (!data()->config()->AreAliases(range->representation(), reg,
3460 other->representation(),
3461 other->assigned_register())) {
3462 return;
3463 }
3464 }
3465 // The inactive range might conflict, so check whether we need to
3466 // split and spill. We can look for the first intersection, as there
3467 // cannot be any intersections in the past, as those would have been a
3468 // conflict then.
3469 LifetimePosition next_start = range->FirstIntersection(other);
3470 if (!next_start.IsValid() || (next_start > max)) {
3471 // There is no conflict or the conflict is outside of the current
3472 // stretch of deferred code. In either case we can ignore the
3473 // inactive range.
3474 return;
3475 }
3476 // They overlap. So we need to split active and reschedule it
3477 // for allocation.
3478 TRACE("Resolving conflict of %d with deferred fixed for register %s\n",
3479 other->TopLevel()->vreg(),
3480 RegisterName(other->assigned_register()));
3481 LiveRange* split_off =
3482 other->SplitAt(next_start, data()->allocation_zone());
3483 // Try to get the same register after the deferred block.
3484 split_off->set_controlflow_hint(other->assigned_register());
3485 DCHECK_NE(split_off, other)((void) 0);
3486 AddToUnhandled(split_off);
3487 update_caches(other);
3488 };
3489 // Now check for conflicts in active and inactive ranges. We might have
3490 // conflicts in inactive, as we do not do this check on every block
3491 // boundary but only on deferred/non-deferred changes but inactive
3492 // live ranges might become live on any block boundary.
3493 for (auto active : active_live_ranges()) {
3494 split_conflicting(range, active, [this](LiveRange* updated) {
3495 next_active_ranges_change_ =
3496 std::min(updated->End(), next_active_ranges_change_);
3497 });
3498 }
3499 for (int reg = 0; reg < num_registers(); ++reg) {
3500 if ((kFPAliasing != AliasingKind::kCombine || !check_fp_aliasing()) &&
3501 reg != range->assigned_register()) {
3502 continue;
3503 }
3504 for (auto inactive : inactive_live_ranges(reg)) {
3505 if (inactive->NextStart() > max) break;
3506 split_conflicting(range, inactive, [this](LiveRange* updated) {
3507 next_inactive_ranges_change_ =
3508 std::min(updated->End(), next_inactive_ranges_change_);
3509 });
3510 }
3511 }
3512 };
3513 if (mode() == RegisterKind::kGeneral) {
3514 for (TopLevelLiveRange* current : data()->fixed_live_ranges()) {
3515 if (current != nullptr) {
3516 if (current->IsDeferredFixed()) {
3517 add_to_inactive(current);
3518 }
3519 }
3520 }
3521 } else if (mode() == RegisterKind::kDouble) {
3522 for (TopLevelLiveRange* current : data()->fixed_double_live_ranges()) {
3523 if (current != nullptr) {
3524 if (current->IsDeferredFixed()) {
3525 add_to_inactive(current);
3526 }
3527 }
3528 }
3529 if (kFPAliasing == AliasingKind::kCombine && check_fp_aliasing()) {
3530 for (TopLevelLiveRange* current : data()->fixed_float_live_ranges()) {
3531 if (current != nullptr) {
3532 if (current->IsDeferredFixed()) {
3533 add_to_inactive(current);
3534 }
3535 }
3536 }
3537 for (TopLevelLiveRange* current : data()->fixed_simd128_live_ranges()) {
3538 if (current != nullptr) {
3539 if (current->IsDeferredFixed()) {
3540 add_to_inactive(current);
3541 }
3542 }
3543 }
3544 }
3545 } else {
3546 DCHECK_EQ(mode(), RegisterKind::kSimd128)((void) 0);
3547 for (TopLevelLiveRange* current : data()->fixed_simd128_live_ranges()) {
3548 if (current != nullptr) {
3549 if (current->IsDeferredFixed()) {
3550 add_to_inactive(current);
3551 }
3552 }
3553 }
3554 }
3555 } else {
3556 // Remove all ranges.
3557 for (int reg = 0; reg < num_registers(); ++reg) {
3558 for (auto it = inactive_live_ranges(reg).begin();
3559 it != inactive_live_ranges(reg).end();) {
3560 if ((*it)->TopLevel()->IsDeferredFixed()) {
3561 it = inactive_live_ranges(reg).erase(it);
3562 } else {
3563 ++it;
3564 }
3565 }
3566 }
3567 }
3568}
3569
3570bool LinearScanAllocator::BlockIsDeferredOrImmediatePredecessorIsNotDeferred(
3571 const InstructionBlock* block) {
3572 if (block->IsDeferred()) return true;
3573 if (block->PredecessorCount() == 0) return true;
3574 bool pred_is_deferred = false;
3575 for (auto pred : block->predecessors()) {
3576 if (pred.IsNext(block->rpo_number())) {
3577 pred_is_deferred = code()->InstructionBlockAt(pred)->IsDeferred();
3578 break;
3579 }
3580 }
3581 return !pred_is_deferred;
3582}
3583
3584bool LinearScanAllocator::HasNonDeferredPredecessor(InstructionBlock* block) {
3585 for (auto pred : block->predecessors()) {
3586 InstructionBlock* pred_block = code()->InstructionBlockAt(pred);
3587 if (!pred_block->IsDeferred()) return true;
3588 }
3589 return false;
3590}
3591
3592void LinearScanAllocator::AllocateRegisters() {
3593 DCHECK(unhandled_live_ranges().empty())((void) 0);
3594 DCHECK(active_live_ranges().empty())((void) 0);
3595 for (int reg = 0; reg < num_registers(); ++reg) {
3596 DCHECK(inactive_live_ranges(reg).empty())((void) 0);
3597 }
3598
3599 SplitAndSpillRangesDefinedByMemoryOperand();
3600 data()->ResetSpillState();
3601
3602 if (data()->is_trace_alloc()) {
3603 PrintRangeOverview();
3604 }
3605
3606 const size_t live_ranges_size = data()->live_ranges().size();
3607 for (TopLevelLiveRange* range : data()->live_ranges()) {
3608 CHECK_EQ(live_ranges_size,do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(data()->live_ranges
().size())>::type>((live_ranges_size), (data()->live_ranges
().size())); do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal
("Check failed: %s.", "live_ranges_size" " " "==" " " "data()->live_ranges().size()"
); } } while (false); } while (false)
3609 data()->live_ranges().size())do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(data()->live_ranges
().size())>::type>((live_ranges_size), (data()->live_ranges
().size())); do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal
("Check failed: %s.", "live_ranges_size" " " "==" " " "data()->live_ranges().size()"
); } } while (false); } while (false)
; // TODO(neis): crbug.com/831822
3610 if (!CanProcessRange(range)) continue;
3611 for (LiveRange* to_add = range; to_add != nullptr;
3612 to_add = to_add->next()) {
3613 if (!to_add->spilled()) {
3614 AddToUnhandled(to_add);
3615 }
3616 }
3617 }
3618
3619 if (mode() == RegisterKind::kGeneral) {
3620 for (TopLevelLiveRange* current : data()->fixed_live_ranges()) {
3621 if (current != nullptr) {
3622 if (current->IsDeferredFixed()) continue;
3623 AddToInactive(current);
3624 }
3625 }
3626 } else if (mode() == RegisterKind::kDouble) {
3627 for (TopLevelLiveRange* current : data()->fixed_double_live_ranges()) {
3628 if (current != nullptr) {
3629 if (current->IsDeferredFixed()) continue;
3630 AddToInactive(current);
3631 }
3632 }
3633 if (kFPAliasing == AliasingKind::kCombine && check_fp_aliasing()) {
3634 for (TopLevelLiveRange* current : data()->fixed_float_live_ranges()) {
3635 if (current != nullptr) {
3636 if (current->IsDeferredFixed()) continue;
3637 AddToInactive(current);
3638 }
3639 }
3640 for (TopLevelLiveRange* current : data()->fixed_simd128_live_ranges()) {
3641 if (current != nullptr) {
3642 if (current->IsDeferredFixed()) continue;
3643 AddToInactive(current);
3644 }
3645 }
3646 }
3647 } else {
3648 DCHECK(mode() == RegisterKind::kSimd128)((void) 0);
3649 for (TopLevelLiveRange* current : data()->fixed_simd128_live_ranges()) {
3650 if (current != nullptr) {
3651 if (current->IsDeferredFixed()) continue;
3652 AddToInactive(current);
3653 }
3654 }
3655 }
3656
3657 RpoNumber last_block = RpoNumber::FromInt(0);
3658 RpoNumber max_blocks =
3659 RpoNumber::FromInt(code()->InstructionBlockCount() - 1);
3660 LifetimePosition next_block_boundary =
3661 LifetimePosition::InstructionFromInstructionIndex(
3662 data()
3663 ->code()
3664 ->InstructionBlockAt(last_block)
3665 ->last_instruction_index())
3666 .NextFullStart();
3667 SpillMode spill_mode = SpillMode::kSpillAtDefinition;
3668
3669 // Process all ranges. We also need to ensure that we have seen all block
3670 // boundaries. Linear scan might have assigned and spilled ranges before
3671 // reaching the last block and hence we would ignore control flow effects for
3672 // those. Not only does this produce a potentially bad assignment, it also
3673 // breaks with the invariant that we undo spills that happen in deferred code
3674 // when crossing a deferred/non-deferred boundary.
3675 while (!unhandled_live_ranges().empty() || last_block < max_blocks) {
3676 data()->tick_counter()->TickAndMaybeEnterSafepoint();
3677 LiveRange* current = unhandled_live_ranges().empty()
3678 ? nullptr
3679 : *unhandled_live_ranges().begin();
3680 LifetimePosition position =
3681 current ? current->Start() : next_block_boundary;
3682#ifdef DEBUG
3683 allocation_finger_ = position;
3684#endif
3685 // Check whether we just moved across a block boundary. This will trigger
3686 // for the first range that is past the current boundary.
3687 if (position >= next_block_boundary) {
3688 TRACE("Processing boundary at %d leaving %d\n",
3689 next_block_boundary.value(), last_block.ToInt());
3690
3691 // Forward state to before block boundary
3692 LifetimePosition end_of_block = next_block_boundary.PrevStart().End();
3693 ForwardStateTo(end_of_block);
3694
3695 // Remember this state.
3696 InstructionBlock* current_block = data()->code()->GetInstructionBlock(
3697 next_block_boundary.ToInstructionIndex());
3698
3699 // Store current spill state (as the state at end of block). For
3700 // simplicity, we store the active ranges, e.g., the live ranges that
3701 // are not spilled.
3702 data()->RememberSpillState(last_block, active_live_ranges());
3703
3704 // Only reset the state if this was not a direct fallthrough. Otherwise
3705 // control flow resolution will get confused (it does not expect changes
3706 // across fallthrough edges.).
3707 bool fallthrough =
3708 (current_block->PredecessorCount() == 1) &&
3709 current_block->predecessors()[0].IsNext(current_block->rpo_number());
3710
3711 // When crossing a deferred/non-deferred boundary, we have to load or
3712 // remove the deferred fixed ranges from inactive.
3713 if ((spill_mode == SpillMode::kSpillDeferred) !=
3714 current_block->IsDeferred()) {
3715 // Update spill mode.
3716 spill_mode = current_block->IsDeferred()
3717 ? SpillMode::kSpillDeferred
3718 : SpillMode::kSpillAtDefinition;
3719
3720 ForwardStateTo(next_block_boundary);
3721
3722#ifdef DEBUG
3723 // Allow allocation at current position.
3724 allocation_finger_ = next_block_boundary;
3725#endif
3726 UpdateDeferredFixedRanges(spill_mode, current_block);
3727 }
3728
3729 // Allocation relies on the fact that each non-deferred block has at
3730 // least one non-deferred predecessor. Check this invariant here.
3731 DCHECK_IMPLIES(!current_block->IsDeferred(),((void) 0)
3732 HasNonDeferredPredecessor(current_block))((void) 0);
3733
3734 if (!fallthrough) {
3735#ifdef DEBUG
3736 // Allow allocation at current position.
3737 allocation_finger_ = next_block_boundary;
3738#endif
3739
3740 // We are currently at next_block_boundary - 1. Move the state to the
3741 // actual block boundary position. In particular, we have to
3742 // reactivate inactive ranges so that they get rescheduled for
3743 // allocation if they were not live at the predecessors.
3744 ForwardStateTo(next_block_boundary);
3745
3746 RangeWithRegisterSet to_be_live(data()->allocation_zone());
3747
3748 // If we end up deciding to use the state of the immediate
3749 // predecessor, it is better not to perform a change. It would lead to
3750 // the same outcome anyway.
3751 // This may never happen on boundaries between deferred and
3752 // non-deferred code, as we rely on explicit respill to ensure we
3753 // spill at definition.
3754 bool no_change_required = false;
3755
3756 auto pick_state_from = [this, current_block](
3757 RpoNumber pred,
3758 RangeWithRegisterSet* to_be_live) -> bool {
3759 TRACE("Using information from B%d\n", pred.ToInt());
3760 // If this is a fall-through that is not across a deferred
3761 // boundary, there is nothing to do.
3762 bool is_noop = pred.IsNext(current_block->rpo_number());
3763 if (!is_noop) {
3764 auto& spill_state = data()->GetSpillState(pred);
3765 TRACE("Not a fallthrough. Adding %zu elements...\n",
3766 spill_state.size());
3767 LifetimePosition pred_end =
3768 LifetimePosition::GapFromInstructionIndex(
3769 this->code()->InstructionBlockAt(pred)->code_end());
3770 for (const auto range : spill_state) {
3771 // Filter out ranges that were split or had their register
3772 // stolen by backwards working spill heuristics. These have
3773 // been spilled after the fact, so ignore them.
3774 if (range->End() < pred_end || !range->HasRegisterAssigned())
3775 continue;
3776 to_be_live->emplace(range);
3777 }
3778 }
3779 return is_noop;
3780 };
3781
3782 // Multiple cases here:
3783 // 1) We have a single predecessor => this is a control flow split, so
3784 // just restore the predecessor state.
3785 // 2) We have two predecessors => this is a conditional, so break ties
3786 // based on what to do based on forward uses, trying to benefit
3787 // the same branch if in doubt (make one path fast).
3788 // 3) We have many predecessors => this is a switch. Compute union
3789 // based on majority, break ties by looking forward.
3790 if (current_block->PredecessorCount() == 1) {
3791 TRACE("Single predecessor for B%d\n",
3792 current_block->rpo_number().ToInt());
3793 no_change_required =
3794 pick_state_from(current_block->predecessors()[0], &to_be_live);
3795 } else if (current_block->PredecessorCount() == 2) {
3796 TRACE("Two predecessors for B%d\n",
3797 current_block->rpo_number().ToInt());
3798 // If one of the branches does not contribute any information,
3799 // e.g. because it is deferred or a back edge, we can short cut
3800 // here right away.
3801 RpoNumber chosen_predecessor = RpoNumber::Invalid();
3802 if (!ConsiderBlockForControlFlow(current_block,
3803 current_block->predecessors()[0])) {
3804 chosen_predecessor = current_block->predecessors()[1];
3805 } else if (!ConsiderBlockForControlFlow(
3806 current_block, current_block->predecessors()[1])) {
3807 chosen_predecessor = current_block->predecessors()[0];
3808 } else {
3809 chosen_predecessor = ChooseOneOfTwoPredecessorStates(
3810 current_block, next_block_boundary);
3811 }
3812 no_change_required = pick_state_from(chosen_predecessor, &to_be_live);
3813
3814 } else {
3815 // Merge at the end of, e.g., a switch.
3816 ComputeStateFromManyPredecessors(current_block, &to_be_live);
3817 }
3818
3819 if (!no_change_required) {
3820 SpillNotLiveRanges(&to_be_live, next_block_boundary, spill_mode);
3821 ReloadLiveRanges(to_be_live, next_block_boundary);
3822 }
3823 }
3824 // Update block information
3825 last_block = current_block->rpo_number();
3826 next_block_boundary = LifetimePosition::InstructionFromInstructionIndex(
3827 current_block->last_instruction_index())
3828 .NextFullStart();
3829
3830 // We might have created new unhandled live ranges, so cycle around the
3831 // loop to make sure we pick the top most range in unhandled for
3832 // processing.
3833 continue;
3834 }
3835
3836 DCHECK_NOT_NULL(current)((void) 0);
3837
3838 TRACE("Processing interval %d:%d start=%d\n", current->TopLevel()->vreg(),
3839 current->relative_id(), position.value());
3840
3841 // Now we can erase current, as we are sure to process it.
3842 unhandled_live_ranges().erase(unhandled_live_ranges().begin());
3843
3844 if (current->IsTopLevel() && TryReuseSpillForPhi(current->TopLevel()))
3845 continue;
3846
3847 ForwardStateTo(position);
3848
3849 DCHECK(!current->HasRegisterAssigned() && !current->spilled())((void) 0);
3850
3851 ProcessCurrentRange(current, spill_mode);
3852 }
3853
3854 if (data()->is_trace_alloc()) {
3855 PrintRangeOverview();
3856 }
3857}
3858
3859void LinearScanAllocator::SetLiveRangeAssignedRegister(LiveRange* range,
3860 int reg) {
3861 data()->MarkAllocated(range->representation(), reg);
3862 range->set_assigned_register(reg);
3863 range->SetUseHints(reg);
3864 range->UpdateBundleRegister(reg);
3865 if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
3866 data()->GetPhiMapValueFor(range->TopLevel())->set_assigned_register(reg);
3867 }
3868}
3869
3870void LinearScanAllocator::AddToActive(LiveRange* range) {
3871 TRACE("Add live range %d:%d in %s to active\n", range->TopLevel()->vreg(),
3872 range->relative_id(), RegisterName(range->assigned_register()));
3873 active_live_ranges().push_back(range);
3874 next_active_ranges_change_ =
3875 std::min(next_active_ranges_change_, range->NextEndAfter(range->Start()));
3876}
3877
3878void LinearScanAllocator::AddToInactive(LiveRange* range) {
3879 TRACE("Add live range %d:%d to inactive\n", range->TopLevel()->vreg(),
3880 range->relative_id());
3881 next_inactive_ranges_change_ = std::min(
3882 next_inactive_ranges_change_, range->NextStartAfter(range->Start()));
3883 DCHECK(range->HasRegisterAssigned())((void) 0);
3884 inactive_live_ranges(range->assigned_register()).insert(range);
3885}
3886
3887void LinearScanAllocator::AddToUnhandled(LiveRange* range) {
3888 if (range == nullptr || range->IsEmpty()) return;
3889 DCHECK(!range->HasRegisterAssigned() && !range->spilled())((void) 0);
3890 DCHECK(allocation_finger_ <= range->Start())((void) 0);
3891
3892 TRACE("Add live range %d:%d to unhandled\n", range->TopLevel()->vreg(),
3893 range->relative_id());
3894 unhandled_live_ranges().insert(range);
3895}
3896
3897ZoneVector<LiveRange*>::iterator LinearScanAllocator::ActiveToHandled(
3898 const ZoneVector<LiveRange*>::iterator it) {
3899 TRACE("Moving live range %d:%d from active to handled\n",
3900 (*it)->TopLevel()->vreg(), (*it)->relative_id());
3901 return active_live_ranges().erase(it);
3902}
3903
3904ZoneVector<LiveRange*>::iterator LinearScanAllocator::ActiveToInactive(
3905 const ZoneVector<LiveRange*>::iterator it, LifetimePosition position) {
3906 LiveRange* range = *it;
3907 TRACE("Moving live range %d:%d from active to inactive\n",
3908 (range)->TopLevel()->vreg(), range->relative_id());
3909 LifetimePosition next_active = range->NextStartAfter(position);
3910 next_inactive_ranges_change_ =
3911 std::min(next_inactive_ranges_change_, next_active);
3912 DCHECK(range->HasRegisterAssigned())((void) 0);
3913 inactive_live_ranges(range->assigned_register()).insert(range);
3914 return active_live_ranges().erase(it);
3915}
3916
3917LinearScanAllocator::InactiveLiveRangeQueue::iterator
3918LinearScanAllocator::InactiveToHandled(InactiveLiveRangeQueue::iterator it) {
3919 LiveRange* range = *it;
3920 TRACE("Moving live range %d:%d from inactive to handled\n",
3921 range->TopLevel()->vreg(), range->relative_id());
3922 int reg = range->assigned_register();
3923 return inactive_live_ranges(reg).erase(it);
3924}
3925
3926LinearScanAllocator::InactiveLiveRangeQueue::iterator
3927LinearScanAllocator::InactiveToActive(InactiveLiveRangeQueue::iterator it,
3928 LifetimePosition position) {
3929 LiveRange* range = *it;
3930 active_live_ranges().push_back(range);
3931 TRACE("Moving live range %d:%d from inactive to active\n",
3932 range->TopLevel()->vreg(), range->relative_id());
3933 next_active_ranges_change_ =
3934 std::min(next_active_ranges_change_, range->NextEndAfter(position));
3935 int reg = range->assigned_register();
3936 return inactive_live_ranges(reg).erase(it);
3937}
3938
3939void LinearScanAllocator::ForwardStateTo(LifetimePosition position) {
3940 if (position >= next_active_ranges_change_) {
3941 next_active_ranges_change_ = LifetimePosition::MaxPosition();
3942 for (auto it = active_live_ranges().begin();
3943 it != active_live_ranges().end();) {
3944 LiveRange* cur_active = *it;
3945 if (cur_active->End() <= position) {
3946 it = ActiveToHandled(it);
3947 } else if (!cur_active->Covers(position)) {
3948 it = ActiveToInactive(it, position);
3949 } else {
3950 next_active_ranges_change_ = std::min(
3951 next_active_ranges_change_, cur_active->NextEndAfter(position));
3952 ++it;
3953 }
3954 }
3955 }
3956
3957 if (position >= next_inactive_ranges_change_) {
3958 next_inactive_ranges_change_ = LifetimePosition::MaxPosition();
3959 for (int reg = 0; reg < num_registers(); ++reg) {
3960 ZoneVector<LiveRange*> reorder(data()->allocation_zone());
3961 for (auto it = inactive_live_ranges(reg).begin();
3962 it != inactive_live_ranges(reg).end();) {
3963 LiveRange* cur_inactive = *it;
3964 if (cur_inactive->End() <= position) {
3965 it = InactiveToHandled(it);
3966 } else if (cur_inactive->Covers(position)) {
3967 it = InactiveToActive(it, position);
3968 } else {
3969 next_inactive_ranges_change_ =
3970 std::min(next_inactive_ranges_change_,
3971 cur_inactive->NextStartAfter(position));
3972 it = inactive_live_ranges(reg).erase(it);
3973 reorder.push_back(cur_inactive);
3974 }
3975 }
3976 for (LiveRange* range : reorder) {
3977 inactive_live_ranges(reg).insert(range);
3978 }
3979 }
3980 }
3981}
3982
3983int LinearScanAllocator::LastDeferredInstructionIndex(InstructionBlock* start) {
3984 DCHECK(start->IsDeferred())((void) 0);
3985 RpoNumber last_block =
3986 RpoNumber::FromInt(code()->InstructionBlockCount() - 1);
3987 while ((start->rpo_number() < last_block)) {
3988 InstructionBlock* next =
3989 code()->InstructionBlockAt(start->rpo_number().Next());
3990 if (!next->IsDeferred()) break;
3991 start = next;
3992 }
3993 return start->last_instruction_index();
3994}
3995
3996void LinearScanAllocator::GetFPRegisterSet(MachineRepresentation rep,
3997 int* num_regs, int* num_codes,
3998 const int** codes) const {
3999 DCHECK_EQ(kFPAliasing, AliasingKind::kCombine)((void) 0);
4000 if (rep == MachineRepresentation::kFloat32) {
4001 *num_regs = data()->config()->num_float_registers();
4002 *num_codes = data()->config()->num_allocatable_float_registers();
4003 *codes = data()->config()->allocatable_float_codes();
4004 } else if (rep == MachineRepresentation::kSimd128) {
4005 *num_regs = data()->config()->num_simd128_registers();
4006 *num_codes = data()->config()->num_allocatable_simd128_registers();
4007 *codes = data()->config()->allocatable_simd128_codes();
4008 } else {
4009 UNREACHABLE()V8_Fatal("unreachable code");
4010 }
4011}
4012
4013void LinearScanAllocator::GetSIMD128RegisterSet(int* num_regs, int* num_codes,
4014 const int** codes) const {
4015 DCHECK_EQ(kFPAliasing, AliasingKind::kIndependent)((void) 0);
4016
4017 *num_regs = data()->config()->num_simd128_registers();
4018 *num_codes = data()->config()->num_allocatable_simd128_registers();
4019 *codes = data()->config()->allocatable_simd128_codes();
4020}
4021
4022void LinearScanAllocator::FindFreeRegistersForRange(
4023 LiveRange* range, base::Vector<LifetimePosition> positions) {
4024 int num_regs = num_registers();
4025 int num_codes = num_allocatable_registers();
4026 const int* codes = allocatable_register_codes();
4027 MachineRepresentation rep = range->representation();
4028 if (kFPAliasing == AliasingKind::kCombine &&
4029 (rep == MachineRepresentation::kFloat32 ||
4030 rep == MachineRepresentation::kSimd128)) {
4031 GetFPRegisterSet(rep, &num_regs, &num_codes, &codes);
4032 } else if (kFPAliasing == AliasingKind::kIndependent &&
4033 (rep == MachineRepresentation::kSimd128)) {
4034 GetSIMD128RegisterSet(&num_regs, &num_codes, &codes);
4035 }
4036 DCHECK_GE(positions.length(), num_regs)((void) 0);
4037
4038 for (int i = 0; i < num_regs; ++i) {
4039 positions[i] = LifetimePosition::MaxPosition();
4040 }
4041
4042 for (LiveRange* cur_active : active_live_ranges()) {
4043 int cur_reg = cur_active->assigned_register();
4044 if (kFPAliasing != AliasingKind::kCombine || !check_fp_aliasing()) {
4045 positions[cur_reg] = LifetimePosition::GapFromInstructionIndex(0);
4046 TRACE("Register %s is free until pos %d (1) due to %d\n",
4047 RegisterName(cur_reg),
4048 LifetimePosition::GapFromInstructionIndex(0).value(),
4049 cur_active->TopLevel()->vreg());
4050 } else {
4051 int alias_base_index = -1;
4052 int aliases = data()->config()->GetAliases(
4053 cur_active->representation(), cur_reg, rep, &alias_base_index);
4054 DCHECK(aliases > 0 || (aliases == 0 && alias_base_index == -1))((void) 0);
4055 while (aliases--) {
4056 int aliased_reg = alias_base_index + aliases;
4057 positions[aliased_reg] = LifetimePosition::GapFromInstructionIndex(0);
4058 }
4059 }
4060 }
4061
4062 for (int cur_reg = 0; cur_reg < num_regs; ++cur_reg) {
4063 for (LiveRange* cur_inactive : inactive_live_ranges(cur_reg)) {
4064 DCHECK_GT(cur_inactive->End(), range->Start())((void) 0);
4065 CHECK_EQ(cur_inactive->assigned_register(), cur_reg)do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(cur_inactive->assigned_register
())>::type, typename ::v8::base::pass_value_or_ref<decltype
(cur_reg)>::type>((cur_inactive->assigned_register()
), (cur_reg)); do { if ((__builtin_expect(!!(!(_cmp)), 0))) {
V8_Fatal("Check failed: %s.", "cur_inactive->assigned_register()"
" " "==" " " "cur_reg"); } } while (false); } while (false)
;
4066 // No need to carry out intersections, when this register won't be
4067 // interesting to this range anyway.
4068 // TODO(mtrofin): extend to aliased ranges, too.
4069 if ((kFPAliasing != AliasingKind::kCombine || !check_fp_aliasing()) &&
4070 (positions[cur_reg] <= cur_inactive->NextStart() ||
4071 range->End() <= cur_inactive->NextStart())) {
4072 break;
4073 }
4074 LifetimePosition next_intersection =
4075 cur_inactive->FirstIntersection(range);
4076 if (!next_intersection.IsValid()) continue;
4077 if (kFPAliasing != AliasingKind::kCombine || !check_fp_aliasing()) {
4078 positions[cur_reg] = std::min(positions[cur_reg], next_intersection);
4079 TRACE("Register %s is free until pos %d (2)\n", RegisterName(cur_reg),
4080 positions[cur_reg].value());
4081 } else {
4082 int alias_base_index = -1;
4083 int aliases = data()->config()->GetAliases(
4084 cur_inactive->representation(), cur_reg, rep, &alias_base_index);
4085 DCHECK(aliases > 0 || (aliases == 0 && alias_base_index == -1))((void) 0);
4086 while (aliases--) {
4087 int aliased_reg = alias_base_index + aliases;
4088 positions[aliased_reg] =
4089 std::min(positions[aliased_reg], next_intersection);
4090 }
4091 }
4092 }
4093 }
4094}
4095
4096// High-level register allocation summary:
4097//
4098// We attempt to first allocate the preferred (hint) register. If that is not
4099// possible, we find a register that's free, and allocate that. If that's not
4100// possible, we search for a register to steal from a range that was allocated.
4101// The goal is to optimize for throughput by avoiding register-to-memory moves,
4102// which are expensive.
4103void LinearScanAllocator::ProcessCurrentRange(LiveRange* current,
4104 SpillMode spill_mode) {
4105 base::EmbeddedVector<LifetimePosition, RegisterConfiguration::kMaxRegisters>
4106 free_until_pos;
4107 FindFreeRegistersForRange(current, free_until_pos);
4108 if (!TryAllocatePreferredReg(current, free_until_pos)) {
4109 if (!TryAllocateFreeReg(current, free_until_pos)) {
4110 AllocateBlockedReg(current, spill_mode);
4111 }
4112 }
4113 if (current->HasRegisterAssigned()) {
4114 AddToActive(current);
4115 }
4116}
4117
4118bool LinearScanAllocator::TryAllocatePreferredReg(
4119 LiveRange* current, const base::Vector<LifetimePosition>& free_until_pos) {
4120 int hint_register;
4121 if (current->RegisterFromControlFlow(&hint_register) ||
4122 current->FirstHintPosition(&hint_register) != nullptr ||
4123 current->RegisterFromBundle(&hint_register)) {
4124 TRACE(
4125 "Found reg hint %s (free until [%d) for live range %d:%d (end %d[).\n",
4126 RegisterName(hint_register), free_until_pos[hint_register].value(),
4127 current->TopLevel()->vreg(), current->relative_id(),
4128 current->End().value());
4129
4130 // The desired register is free until the end of the current live range.
4131 if (free_until_pos[hint_register] >= current->End()) {
4132 TRACE("Assigning preferred reg %s to live range %d:%d\n",
4133 RegisterName(hint_register), current->TopLevel()->vreg(),
4134 current->relative_id());
4135 SetLiveRangeAssignedRegister(current, hint_register);
4136 return true;
4137 }
4138 }
4139 return false;
4140}
4141
4142int LinearScanAllocator::PickRegisterThatIsAvailableLongest(
4143 LiveRange* current, int hint_reg,
4144 const base::Vector<LifetimePosition>& free_until_pos) {
4145 int num_regs = 0; // used only for the call to GetFPRegisterSet.
4146 int num_codes = num_allocatable_registers();
4147 const int* codes = allocatable_register_codes();
4148 MachineRepresentation rep = current->representation();
4149 if (kFPAliasing == AliasingKind::kCombine &&
4150 (rep == MachineRepresentation::kFloat32 ||
4151 rep == MachineRepresentation::kSimd128)) {
4152 GetFPRegisterSet(rep, &num_regs, &num_codes, &codes);
4153 } else if (kFPAliasing == AliasingKind::kIndependent &&
4154 (rep == MachineRepresentation::kSimd128)) {
4155 GetSIMD128RegisterSet(&num_regs, &num_codes, &codes);
4156 }
4157
4158 DCHECK_GE(free_until_pos.length(), num_codes)((void) 0);
4159
4160 // Find the register which stays free for the longest time. Check for
4161 // the hinted register first, as we might want to use that one. Only
4162 // count full instructions for free ranges, as an instruction's internal
4163 // positions do not help but might shadow a hinted register. This is
4164 // typically the case for function calls, where all registered are
4165 // cloberred after the call except for the argument registers, which are
4166 // set before the call. Hence, the argument registers always get ignored,
4167 // as their available time is shorter.
4168 int reg = (hint_reg == kUnassignedRegister) ? codes[0] : hint_reg;
4169 int current_free = free_until_pos[reg].ToInstructionIndex();
4170 for (int i = 0; i < num_codes; ++i) {
4171 int code = codes[i];
4172 // Prefer registers that have no fixed uses to avoid blocking later hints.
4173 // We use the first register that has no fixed uses to ensure we use
4174 // byte addressable registers in ia32 first.
4175 int candidate_free = free_until_pos[code].ToInstructionIndex();
4176 TRACE("Register %s in free until %d\n", RegisterName(code), candidate_free);
4177 if ((candidate_free > current_free) ||
4178 (candidate_free == current_free && reg != hint_reg &&
4179 (data()->HasFixedUse(current->representation(), reg) &&
4180 !data()->HasFixedUse(current->representation(), code)))) {
4181 reg = code;
4182 current_free = candidate_free;
4183 }
4184 }
4185
4186 return reg;
4187}
4188
4189bool LinearScanAllocator::TryAllocateFreeReg(
4190 LiveRange* current, const base::Vector<LifetimePosition>& free_until_pos) {
4191 // Compute register hint, if such exists.
4192 int hint_reg = kUnassignedRegister;
4193 current->RegisterFromControlFlow(&hint_reg) ||
4194 current->FirstHintPosition(&hint_reg) != nullptr ||
4195 current->RegisterFromBundle(&hint_reg);
4196
4197 int reg =
4198 PickRegisterThatIsAvailableLongest(current, hint_reg, free_until_pos);
4199
4200 LifetimePosition pos = free_until_pos[reg];
4201
4202 if (pos <= current->Start()) {
4203 // All registers are blocked.
4204 return false;
4205 }
4206
4207 if (pos < current->End()) {
4208 // Register reg is available at the range start but becomes blocked before
4209 // the range end. Split current before the position where it becomes
4210 // blocked. Shift the split position to the last gap position. This is to
4211 // ensure that if a connecting move is needed, that move coincides with the
4212 // start of the range that it defines. See crbug.com/1182985.
4213 LifetimePosition gap_pos =
4214 pos.IsGapPosition() ? pos : pos.FullStart().End();
4215 if (gap_pos <= current->Start()) return false;
4216 LiveRange* tail = SplitRangeAt(current, gap_pos);
4217 AddToUnhandled(tail);
4218
4219 // Try to allocate preferred register once more.
4220 if (TryAllocatePreferredReg(current, free_until_pos)) return true;
4221 }
4222
4223 // Register reg is available at the range start and is free until the range
4224 // end.
4225 DCHECK_GE(pos, current->End())((void) 0);
4226 TRACE("Assigning free reg %s to live range %d:%d\n", RegisterName(reg),
4227 current->TopLevel()->vreg(), current->relative_id());
4228 SetLiveRangeAssignedRegister(current, reg);
4229
4230 return true;
4231}
4232
4233void LinearScanAllocator::AllocateBlockedReg(LiveRange* current,
4234 SpillMode spill_mode) {
4235 UsePosition* register_use = current->NextRegisterPosition(current->Start());
4236 if (register_use == nullptr) {
4237 // There is no use in the current live range that requires a register.
4238 // We can just spill it.
4239 LiveRange* begin_spill = nullptr;
4240 LifetimePosition spill_pos = FindOptimalSpillingPos(
4241 current, current->Start(), spill_mode, &begin_spill);
4242 MaybeSpillPreviousRanges(begin_spill, spill_pos, current);
4243 Spill(current, spill_mode);
4244 return;
4245 }
4246
4247 MachineRepresentation rep = current->representation();
4248
4249 // use_pos keeps track of positions a register/alias is used at.
4250 // block_pos keeps track of positions where a register/alias is blocked
4251 // from.
4252 base::EmbeddedVector<LifetimePosition, RegisterConfiguration::kMaxRegisters>
4253 use_pos(LifetimePosition::MaxPosition());
4254 base::EmbeddedVector<LifetimePosition, RegisterConfiguration::kMaxRegisters>
4255 block_pos(LifetimePosition::MaxPosition());
4256
4257 for (LiveRange* range : active_live_ranges()) {
4258 int cur_reg = range->assigned_register();
4259 bool is_fixed_or_cant_spill =
4260 range->TopLevel()->IsFixed() || !range->CanBeSpilled(current->Start());
4261 if (kFPAliasing != AliasingKind::kCombine || !check_fp_aliasing()) {
4262 if (is_fixed_or_cant_spill) {
4263 block_pos[cur_reg] = use_pos[cur_reg] =
4264 LifetimePosition::GapFromInstructionIndex(0);
4265 } else {
4266 DCHECK_NE(LifetimePosition::GapFromInstructionIndex(0),((void) 0)
4267 block_pos[cur_reg])((void) 0);
4268 use_pos[cur_reg] =
4269 range->NextLifetimePositionRegisterIsBeneficial(current->Start());
4270 }
4271 } else {
4272 int alias_base_index = -1;
4273 int aliases = data()->config()->GetAliases(
4274 range->representation(), cur_reg, rep, &alias_base_index);
4275 DCHECK(aliases > 0 || (aliases == 0 && alias_base_index == -1))((void) 0);
4276 while (aliases--) {
4277 int aliased_reg = alias_base_index + aliases;
4278 if (is_fixed_or_cant_spill) {
4279 block_pos[aliased_reg] = use_pos[aliased_reg] =
4280 LifetimePosition::GapFromInstructionIndex(0);
4281 } else {
4282 use_pos[aliased_reg] =
4283 std::min(block_pos[aliased_reg],
4284 range->NextLifetimePositionRegisterIsBeneficial(
4285 current->Start()));
4286 }
4287 }
4288 }
4289 }
4290
4291 for (int cur_reg = 0; cur_reg < num_registers(); ++cur_reg) {
4292 for (LiveRange* range : inactive_live_ranges(cur_reg)) {
4293 DCHECK(range->End() > current->Start())((void) 0);
4294 DCHECK_EQ(range->assigned_register(), cur_reg)((void) 0);
4295 bool is_fixed = range->TopLevel()->IsFixed();
4296
4297 // Don't perform costly intersections if they are guaranteed to not update
4298 // block_pos or use_pos.
4299 // TODO(mtrofin): extend to aliased ranges, too.
4300 if ((kFPAliasing != AliasingKind::kCombine || !check_fp_aliasing())) {
4301 DCHECK_LE(use_pos[cur_reg], block_pos[cur_reg])((void) 0);
4302 if (block_pos[cur_reg] <= range->NextStart()) break;
4303 if (!is_fixed && use_pos[cur_reg] <= range->NextStart()) continue;
4304 }
4305
4306 LifetimePosition next_intersection = range->FirstIntersection(current);
4307 if (!next_intersection.IsValid()) continue;
4308
4309 if (kFPAliasing != AliasingKind::kCombine || !check_fp_aliasing()) {
4310 if (is_fixed) {
4311 block_pos[cur_reg] = std::min(block_pos[cur_reg], next_intersection);
4312 use_pos[cur_reg] = std::min(block_pos[cur_reg], use_pos[cur_reg]);
4313 } else {
4314 use_pos[cur_reg] = std::min(use_pos[cur_reg], next_intersection);
4315 }
4316 } else {
4317 int alias_base_index = -1;
4318 int aliases = data()->config()->GetAliases(
4319 range->representation(), cur_reg, rep, &alias_base_index);
4320 DCHECK(aliases > 0 || (aliases == 0 && alias_base_index == -1))((void) 0);
4321 while (aliases--) {
4322 int aliased_reg = alias_base_index + aliases;
4323 if (is_fixed) {
4324 block_pos[aliased_reg] =
4325 std::min(block_pos[aliased_reg], next_intersection);
4326 use_pos[aliased_reg] =
4327 std::min(block_pos[aliased_reg], use_pos[aliased_reg]);
4328 } else {
4329 use_pos[aliased_reg] =
4330 std::min(use_pos[aliased_reg], next_intersection);
4331 }
4332 }
4333 }
4334 }
4335 }
4336
4337 // Compute register hint if it exists.
4338 int hint_reg = kUnassignedRegister;
4339 current->RegisterFromControlFlow(&hint_reg) ||
4340 register_use->HintRegister(&hint_reg) ||
4341 current->RegisterFromBundle(&hint_reg);
4342 int reg = PickRegisterThatIsAvailableLongest(current, hint_reg, use_pos);
4343
4344 if (use_pos[reg] < register_use->pos()) {
4345 // If there is a gap position before the next register use, we can
4346 // spill until there. The gap position will then fit the fill move.
4347 if (LifetimePosition::ExistsGapPositionBetween(current->Start(),
4348 register_use->pos())) {
4349 SpillBetween(current, current->Start(), register_use->pos(), spill_mode);
4350 return;
4351 }
4352 }
4353
4354 // When in deferred spilling mode avoid stealing registers beyond the current
4355 // deferred region. This is required as we otherwise might spill an inactive
4356 // range with a start outside of deferred code and that would not be reloaded.
4357 LifetimePosition new_end = current->End();
4358 if (spill_mode == SpillMode::kSpillDeferred) {
4359 InstructionBlock* deferred_block =
4360 code()->GetInstructionBlock(current->Start().ToInstructionIndex());
4361 new_end =
4362 std::min(new_end, LifetimePosition::GapFromInstructionIndex(
4363 LastDeferredInstructionIndex(deferred_block)));
4364 }
4365
4366 // We couldn't spill until the next register use. Split before the register
4367 // is blocked, if applicable.
4368 if (block_pos[reg] < new_end) {
4369 // Register becomes blocked before the current range end. Split before that
4370 // position.
4371 new_end = block_pos[reg].Start();
4372 }
4373
4374 // If there is no register available at all, we can only spill this range.
4375 // Happens for instance on entry to deferred code where registers might
4376 // become blocked yet we aim to reload ranges.
4377 if (new_end == current->Start()) {
4378 SpillBetween(current, new_end, register_use->pos(), spill_mode);
4379 return;
4380 }
4381
4382 // Split at the new end if we found one.
4383 if (new_end != current->End()) {
4384 LiveRange* tail = SplitBetween(current, current->Start(), new_end);
4385 AddToUnhandled(tail);
4386 }
4387
4388 // Register reg is not blocked for the whole range.
4389 DCHECK(block_pos[reg] >= current->End())((void) 0);
4390 TRACE("Assigning blocked reg %s to live range %d:%d\n", RegisterName(reg),
4391 current->TopLevel()->vreg(), current->relative_id());
4392 SetLiveRangeAssignedRegister(current, reg);
4393
4394 // This register was not free. Thus we need to find and spill
4395 // parts of active and inactive live regions that use the same register
4396 // at the same lifetime positions as current.
4397 SplitAndSpillIntersecting(current, spill_mode);
4398}
4399
4400void LinearScanAllocator::SplitAndSpillIntersecting(LiveRange* current,
4401 SpillMode spill_mode) {
4402 DCHECK(current->HasRegisterAssigned())((void) 0);
4403 int reg = current->assigned_register();
4404 LifetimePosition split_pos = current->Start();
4405 for (auto it = active_live_ranges().begin();
4406 it != active_live_ranges().end();) {
4407 LiveRange* range = *it;
4408 if (kFPAliasing != AliasingKind::kCombine || !check_fp_aliasing()) {
4409 if (range->assigned_register() != reg) {
4410 ++it;
4411 continue;
4412 }
4413 } else {
4414 if (!data()->config()->AreAliases(current->representation(), reg,
4415 range->representation(),
4416 range->assigned_register())) {
4417 ++it;
4418 continue;
4419 }
4420 }
4421
4422 UsePosition* next_pos = range->NextRegisterPosition(current->Start());
4423 LiveRange* begin_spill = nullptr;
4424 LifetimePosition spill_pos =
4425 FindOptimalSpillingPos(range, split_pos, spill_mode, &begin_spill);
4426 MaybeSpillPreviousRanges(begin_spill, spill_pos, range);
4427 if (next_pos == nullptr) {
4428 SpillAfter(range, spill_pos, spill_mode);
4429 } else {
4430 // When spilling between spill_pos and next_pos ensure that the range
4431 // remains spilled at least until the start of the current live range.
4432 // This guarantees that we will not introduce new unhandled ranges that
4433 // start before the current range as this violates allocation invariants
4434 // and will lead to an inconsistent state of active and inactive
4435 // live-ranges: ranges are allocated in order of their start positions,
4436 // ranges are retired from active/inactive when the start of the
4437 // current live-range is larger than their end.
4438 DCHECK(LifetimePosition::ExistsGapPositionBetween(current->Start(),((void) 0)
4439 next_pos->pos()))((void) 0);
4440 SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos(),
4441 spill_mode);
4442 }
4443 it = ActiveToHandled(it);
4444 }
4445
4446 for (int cur_reg = 0; cur_reg < num_registers(); ++cur_reg) {
4447 if (kFPAliasing != AliasingKind::kCombine || !check_fp_aliasing()) {
4448 if (cur_reg != reg) continue;
4449 }
4450 for (auto it = inactive_live_ranges(cur_reg).begin();
4451 it != inactive_live_ranges(cur_reg).end();) {
4452 LiveRange* range = *it;
4453 if (kFPAliasing == AliasingKind::kCombine && check_fp_aliasing() &&
4454 !data()->config()->AreAliases(current->representation(), reg,
4455 range->representation(), cur_reg)) {
4456 ++it;
4457 continue;
4458 }
4459 DCHECK(range->End() > current->Start())((void) 0);
4460 if (range->TopLevel()->IsFixed()) {
4461 ++it;
4462 continue;
4463 }
4464
4465 LifetimePosition next_intersection = range->FirstIntersection(current);
4466 if (next_intersection.IsValid()) {
4467 UsePosition* next_pos = range->NextRegisterPosition(current->Start());
4468 if (next_pos == nullptr) {
4469 SpillAfter(range, split_pos, spill_mode);
4470 } else {
4471 next_intersection = std::min(next_intersection, next_pos->pos());
4472 SpillBetween(range, split_pos, next_intersection, spill_mode);
4473 }
4474 it = InactiveToHandled(it);
4475 } else {
4476 ++it;
4477 }
4478 }
4479 }
4480}
4481
4482bool LinearScanAllocator::TryReuseSpillForPhi(TopLevelLiveRange* range) {
4483 if (!range->is_phi()) return false;
4484
4485 DCHECK(!range->HasSpillOperand())((void) 0);
4486 // Check how many operands belong to the same bundle as the output.
4487 LiveRangeBundle* out_bundle = range->get_bundle();
4488 TopTierRegisterAllocationData::PhiMapValue* phi_map_value =
4489 data()->GetPhiMapValueFor(range);
4490 const PhiInstruction* phi = phi_map_value->phi();
4491 const InstructionBlock* block = phi_map_value->block();
4492 // Count the number of spilled operands.
4493 size_t spilled_count = 0;
4494 for (size_t i = 0; i < phi->operands().size(); i++) {
4495 int op = phi->operands()[i];
4496 LiveRange* op_range = data()->GetOrCreateLiveRangeFor(op);
4497 if (!op_range->TopLevel()->HasSpillRange()) continue;
4498 const InstructionBlock* pred =
4499 code()->InstructionBlockAt(block->predecessors()[i]);
4500 LifetimePosition pred_end =
4501 LifetimePosition::InstructionFromInstructionIndex(
4502 pred->last_instruction_index());
4503 while (op_range != nullptr && !op_range->CanCover(pred_end)) {
4504 op_range = op_range->next();
4505 }
4506 if (op_range != nullptr && op_range->spilled() &&
4507 op_range->get_bundle() == out_bundle) {
4508 spilled_count++;
4509 }
4510 }
4511
4512 // Only continue if more than half of the operands are spilled to the same
4513 // slot (because part of same bundle).
4514 if (spilled_count * 2 <= phi->operands().size()) {
4515 return false;
4516 }
4517
4518 // If the range does not need register soon, spill it to the merged
4519 // spill range.
4520 LifetimePosition next_pos = range->Start();
4521 if (next_pos.IsGapPosition()) next_pos = next_pos.NextStart();
4522 UsePosition* pos = range->NextUsePositionRegisterIsBeneficial(next_pos);
4523 if (pos == nullptr) {
4524 Spill(range, SpillMode::kSpillAtDefinition);
4525 return true;
4526 } else if (pos->pos() > range->Start().NextStart()) {
4527 SpillBetween(range, range->Start(), pos->pos(),
4528 SpillMode::kSpillAtDefinition);
4529 return true;
4530 }
4531 return false;
4532}
4533
4534void LinearScanAllocator::SpillAfter(LiveRange* range, LifetimePosition pos,
4535 SpillMode spill_mode) {
4536 LiveRange* second_part = SplitRangeAt(range, pos);
4537 Spill(second_part, spill_mode);
4538}
4539
4540void LinearScanAllocator::SpillBetween(LiveRange* range, LifetimePosition start,
4541 LifetimePosition end,
4542 SpillMode spill_mode) {
4543 SpillBetweenUntil(range, start, start, end, spill_mode);
4544}
4545
4546void LinearScanAllocator::SpillBetweenUntil(LiveRange* range,
4547 LifetimePosition start,
4548 LifetimePosition until,
4549 LifetimePosition end,
4550 SpillMode spill_mode) {
4551 CHECK(start < end)do { if ((__builtin_expect(!!(!(start < end)), 0))) { V8_Fatal
("Check failed: %s.", "start < end"); } } while (false)
;
4552 LiveRange* second_part = SplitRangeAt(range, start);
4553
4554 if (second_part->Start() < end) {
4555 // The split result intersects with [start, end[.
4556 // Split it at position between ]start+1, end[, spill the middle part
4557 // and put the rest to unhandled.
4558
4559 // Make sure that the third part always starts after the start of the
4560 // second part, as that likely is the current position of the register
4561 // allocator and we cannot add ranges to unhandled that start before
4562 // the current position.
4563 LifetimePosition split_start = std::max(second_part->Start().End(), until);
4564
4565 // If end is an actual use (which it typically is) we have to split
4566 // so that there is a gap before so that we have space for moving the
4567 // value into its position.
4568 // However, if we have no choice, split right where asked.
4569 LifetimePosition third_part_end =
4570 std::max(split_start, end.PrevStart().End());
4571 // Instead of spliting right after or even before the block boundary,
4572 // split on the boumndary to avoid extra moves.
4573 if (data()->IsBlockBoundary(end.Start())) {
4574 third_part_end = std::max(split_start, end.Start());
4575 }
4576
4577 LiveRange* third_part =
4578 SplitBetween(second_part, split_start, third_part_end);
4579 if (GetInstructionBlock(data()->code(), second_part->Start())
4580 ->IsDeferred()) {
4581 // Try to use the same register as before.
4582 TRACE("Setting control flow hint for %d:%d to %s\n",
4583 third_part->TopLevel()->vreg(), third_part->relative_id(),
4584 RegisterName(range->controlflow_hint()));
4585 third_part->set_controlflow_hint(range->controlflow_hint());
4586 }
4587
4588 AddToUnhandled(third_part);
4589 // This can happen, even if we checked for start < end above, as we fiddle
4590 // with the end location. However, we are guaranteed to be after or at
4591 // until, so this is fine.
4592 if (third_part != second_part) {
4593 Spill(second_part, spill_mode);
4594 }
4595 } else {
4596 // The split result does not intersect with [start, end[.
4597 // Nothing to spill. Just put it to unhandled as whole.
4598 AddToUnhandled(second_part);
4599 }
4600}
4601
4602OperandAssigner::OperandAssigner(TopTierRegisterAllocationData* data)
4603 : data_(data) {}
4604
4605void OperandAssigner::DecideSpillingMode() {
4606 for (auto range : data()->live_ranges()) {
4607 data()->tick_counter()->TickAndMaybeEnterSafepoint();
4608 int max_blocks = data()->code()->InstructionBlockCount();
4609 if (range != nullptr && range->IsSpilledOnlyInDeferredBlocks(data())) {
4610 // If the range is spilled only in deferred blocks and starts in
4611 // a non-deferred block, we transition its representation here so
4612 // that the LiveRangeConnector processes them correctly. If,
4613 // however, they start in a deferred block, we uograde them to
4614 // spill at definition, as that definition is in a deferred block
4615 // anyway. While this is an optimization, the code in LiveRangeConnector
4616 // relies on it!
4617 if (GetInstructionBlock(data()->code(), range->Start())->IsDeferred()) {
4618 TRACE("Live range %d is spilled and alive in deferred code only\n",
4619 range->vreg());
4620 range->TransitionRangeToSpillAtDefinition();
4621 } else {
4622 TRACE("Live range %d is spilled deferred code only but alive outside\n",
4623 range->vreg());
4624 range->TransitionRangeToDeferredSpill(data()->allocation_zone(),
4625 max_blocks);
4626 }
4627 }
4628 }
4629}
4630
4631void OperandAssigner::AssignSpillSlots() {
4632 for (auto range : data()->live_ranges()) {
4633 data()->tick_counter()->TickAndMaybeEnterSafepoint();
4634 if (range != nullptr && range->get_bundle() != nullptr) {
4635 range->get_bundle()->MergeSpillRangesAndClear();
4636 }
4637 }
4638 ZoneVector<SpillRange*>& spill_ranges = data()->spill_ranges();
4639 // Merge disjoint spill ranges
4640 for (size_t i = 0; i < spill_ranges.size(); ++i) {
4641 data()->tick_counter()->TickAndMaybeEnterSafepoint();
4642 SpillRange* range = spill_ranges[i];
4643 if (range == nullptr) continue;
4644 if (range->IsEmpty()) continue;
4645 for (size_t j = i + 1; j < spill_ranges.size(); ++j) {
4646 SpillRange* other = spill_ranges[j];
4647 if (other != nullptr && !other->IsEmpty()) {
4648 range->TryMerge(other);
4649 }
4650 }
4651 }
4652 // Allocate slots for the merged spill ranges.
4653 for (SpillRange* range : spill_ranges) {
4654 data()->tick_counter()->TickAndMaybeEnterSafepoint();
4655 if (range == nullptr || range->IsEmpty()) continue;
4656 if (!range->HasSlot()) {
4657 // Allocate a new operand referring to the spill slot, aligned to the
4658 // operand size.
4659 int width = range->byte_width();
4660 int index = data()->frame()->AllocateSpillSlot(width, width);
4661 range->set_assigned_slot(index);
4662 }
4663 }
4664}
4665
4666void OperandAssigner::CommitAssignment() {
4667 const size_t live_ranges_size = data()->live_ranges().size();
4668 for (TopLevelLiveRange* top_range : data()->live_ranges()) {
4669 data()->tick_counter()->TickAndMaybeEnterSafepoint();
4670 CHECK_EQ(live_ranges_size,do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(data()->live_ranges
().size())>::type>((live_ranges_size), (data()->live_ranges
().size())); do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal
("Check failed: %s.", "live_ranges_size" " " "==" " " "data()->live_ranges().size()"
); } } while (false); } while (false)
4671 data()->live_ranges().size())do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(data()->live_ranges
().size())>::type>((live_ranges_size), (data()->live_ranges
().size())); do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal
("Check failed: %s.", "live_ranges_size" " " "==" " " "data()->live_ranges().size()"
); } } while (false); } while (false)
; // TODO(neis): crbug.com/831822
4672 if (top_range == nullptr || top_range->IsEmpty()) continue;
4673 InstructionOperand spill_operand;
4674 if (top_range->HasSpillOperand()) {
4675 auto it = data()->slot_for_const_range().find(top_range);
4676 if (it != data()->slot_for_const_range().end()) {
4677 spill_operand = *it->second;
4678 } else {
4679 spill_operand = *top_range->GetSpillOperand();
4680 }
4681 } else if (top_range->HasSpillRange()) {
4682 spill_operand = top_range->GetSpillRangeOperand();
4683 }
4684 if (top_range->is_phi()) {
4685 data()->GetPhiMapValueFor(top_range)->CommitAssignment(
4686 top_range->GetAssignedOperand());
4687 }
4688 for (LiveRange* range = top_range; range != nullptr;
4689 range = range->next()) {
4690 InstructionOperand assigned = range->GetAssignedOperand();
4691 DCHECK(!assigned.IsUnallocated())((void) 0);
4692 range->ConvertUsesToOperand(assigned, spill_operand);
4693 }
4694
4695 if (!spill_operand.IsInvalid()) {
4696 // If this top level range has a child spilled in a deferred block, we use
4697 // the range and control flow connection mechanism instead of spilling at
4698 // definition. Refer to the ConnectLiveRanges and ResolveControlFlow
4699 // phases. Normally, when we spill at definition, we do not insert a
4700 // connecting move when a successor child range is spilled - because the
4701 // spilled range picks up its value from the slot which was assigned at
4702 // definition. For ranges that are determined to spill only in deferred
4703 // blocks, we let ConnectLiveRanges and ResolveControlFlow find the blocks
4704 // where a spill operand is expected, and then finalize by inserting the
4705 // spills in the deferred blocks dominators.
4706 if (!top_range->IsSpilledOnlyInDeferredBlocks(data()) &&
4707 !top_range->HasGeneralSpillRange()) {
4708 // Spill at definition if the range isn't spilled in a way that will be
4709 // handled later.
4710 top_range->FilterSpillMoves(data(), spill_operand);
4711 top_range->CommitSpillMoves(data(), spill_operand);
4712 }
4713 }
4714 }
4715}
4716
4717ReferenceMapPopulator::ReferenceMapPopulator(
4718 TopTierRegisterAllocationData* data)
4719 : data_(data) {}
4720
4721bool ReferenceMapPopulator::SafePointsAreInOrder() const {
4722 int safe_point = 0;
4723 for (ReferenceMap* map : *data()->code()->reference_maps()) {
4724 if (safe_point > map->instruction_position()) return false;
4725 safe_point = map->instruction_position();
4726 }
4727 return true;
4728}
4729
4730void ReferenceMapPopulator::PopulateReferenceMaps() {
4731 DCHECK(SafePointsAreInOrder())((void) 0);
4732 // Map all delayed references.
4733 for (TopTierRegisterAllocationData::DelayedReference& delayed_reference :
4734 data()->delayed_references()) {
4735 delayed_reference.map->RecordReference(
4736 AllocatedOperand::cast(*delayed_reference.operand));
4737 }
4738 // Iterate over all safe point positions and record a pointer
4739 // for all spilled live ranges at this point.
4740 int last_range_start = 0;
4741 const ReferenceMapDeque* reference_maps = data()->code()->reference_maps();
4742 ReferenceMapDeque::const_iterator first_it = reference_maps->begin();
4743 const size_t live_ranges_size = data()->live_ranges().size();
4744 // We break the invariant that live ranges are indexed by their vregs here.
4745 // This is ok because we don't use that invariant here, and this is the last
4746 // phase.
4747 std::sort(data()->live_ranges().begin(), data()->live_ranges().end(),
4748 [](TopLevelLiveRange* a, TopLevelLiveRange* b) {
4749 if (!a || a->IsEmpty()) return false;
4750 if (!b || b->IsEmpty()) return true;
4751 return a->Start() < b->Start();
4752 });
4753 for (TopLevelLiveRange* range : data()->live_ranges()) {
4754 CHECK_EQ(live_ranges_size,do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(data()->live_ranges
().size())>::type>((live_ranges_size), (data()->live_ranges
().size())); do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal
("Check failed: %s.", "live_ranges_size" " " "==" " " "data()->live_ranges().size()"
); } } while (false); } while (false)
4755 data()->live_ranges().size())do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(data()->live_ranges
().size())>::type>((live_ranges_size), (data()->live_ranges
().size())); do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal
("Check failed: %s.", "live_ranges_size" " " "==" " " "data()->live_ranges().size()"
); } } while (false); } while (false)
; // TODO(neis): crbug.com/831822
4756 if (range == nullptr) continue;
4757 // Skip non-reference values.
4758 if (!data()->code()->IsReference(range->vreg())) continue;
4759 // Skip empty live ranges.
4760 if (range->IsEmpty()) continue;
4761 if (range->has_preassigned_slot()) continue;
4762
4763 // Find the extent of the range and its children.
4764 int start = range->Start().ToInstructionIndex();
4765 int end = 0;
4766 for (LiveRange* cur = range; cur != nullptr; cur = cur->next()) {
4767 LifetimePosition this_end = cur->End();
4768 if (this_end.ToInstructionIndex() > end)
4769 end = this_end.ToInstructionIndex();
4770 DCHECK(cur->Start().ToInstructionIndex() >= start)((void) 0);
4771 }
4772
4773 // Ranges should be sorted, so that the first reference map in the current
4774 // live range has to be after {first_it}.
4775 DCHECK_LE(last_range_start, start)((void) 0);
4776 last_range_start = start;
4777 USE(last_range_start)do { ::v8::base::Use unused_tmp_array_for_use_macro[]{last_range_start
}; (void)unused_tmp_array_for_use_macro; } while (false)
;
4778
4779 // Step across all the safe points that are before the start of this range,
4780 // recording how far we step in order to save doing this for the next range.
4781 for (; first_it != reference_maps->end(); ++first_it) {
4782 ReferenceMap* map = *first_it;
4783 if (map->instruction_position() >= start) break;
4784 }
4785
4786 InstructionOperand spill_operand;
4787 if (((range->HasSpillOperand() &&
4788 !range->GetSpillOperand()->IsConstant()) ||
4789 range->HasSpillRange())) {
4790 if (range->HasSpillOperand()) {
4791 spill_operand = *range->GetSpillOperand();
4792 } else {
4793 spill_operand = range->GetSpillRangeOperand();
4794 }
4795 DCHECK(spill_operand.IsStackSlot())((void) 0);
4796 DCHECK(CanBeTaggedOrCompressedPointer(((void) 0)
4797 AllocatedOperand::cast(spill_operand).representation()))((void) 0);
4798 }
4799
4800 LiveRange* cur = range;
4801 // Step through the safe points to see whether they are in the range.
4802 for (auto it = first_it; it != reference_maps->end(); ++it) {
4803 ReferenceMap* map = *it;
4804 int safe_point = map->instruction_position();
4805
4806 // The safe points are sorted so we can stop searching here.
4807 if (safe_point - 1 > end) break;
4808
4809 // Advance to the next active range that covers the current
4810 // safe point position.
4811 LifetimePosition safe_point_pos =
4812 LifetimePosition::InstructionFromInstructionIndex(safe_point);
4813
4814 // Search for the child range (cur) that covers safe_point_pos. If we
4815 // don't find it before the children pass safe_point_pos, keep cur at
4816 // the last child, because the next safe_point_pos may be covered by cur.
4817 // This may happen if cur has more than one interval, and the current
4818 // safe_point_pos is in between intervals.
4819 // For that reason, cur may be at most the last child.
4820 DCHECK_NOT_NULL(cur)((void) 0);
4821 DCHECK(safe_point_pos >= cur->Start() || range == cur)((void) 0);
4822 bool found = false;
4823 while (!found) {
4824 if (cur->Covers(safe_point_pos)) {
4825 found = true;
4826 } else {
4827 LiveRange* next = cur->next();
4828 if (next == nullptr || next->Start() > safe_point_pos) {
4829 break;
4830 }
4831 cur = next;
4832 }
4833 }
4834
4835 if (!found) {
4836 continue;
4837 }
4838
4839 // Check if the live range is spilled and the safe point is after
4840 // the spill position.
4841 int spill_index = range->IsSpilledOnlyInDeferredBlocks(data()) ||
4842 range->LateSpillingSelected()
4843 ? cur->Start().ToInstructionIndex()
4844 : range->spill_start_index();
4845
4846 if (!spill_operand.IsInvalid() && safe_point >= spill_index) {
4847 TRACE("Pointer for range %d (spilled at %d) at safe point %d\n",
4848 range->vreg(), spill_index, safe_point);
4849 map->RecordReference(AllocatedOperand::cast(spill_operand));
4850 }
4851
4852 if (!cur->spilled()) {
4853 TRACE(
4854 "Pointer in register for range %d:%d (start at %d) "
4855 "at safe point %d\n",
4856 range->vreg(), cur->relative_id(), cur->Start().value(),
4857 safe_point);
4858 InstructionOperand operand = cur->GetAssignedOperand();
4859 DCHECK(!operand.IsStackSlot())((void) 0);
4860 DCHECK(CanBeTaggedOrCompressedPointer(((void) 0)
4861 AllocatedOperand::cast(operand).representation()))((void) 0);
4862 map->RecordReference(AllocatedOperand::cast(operand));
4863 }
4864 }
4865 }
4866}
4867
4868LiveRangeConnector::LiveRangeConnector(TopTierRegisterAllocationData* data)
4869 : data_(data) {}
4870
4871bool LiveRangeConnector::CanEagerlyResolveControlFlow(
4872 const InstructionBlock* block) const {
4873 if (block->PredecessorCount() != 1) return false;
4874 return block->predecessors()[0].IsNext(block->rpo_number());
4875}
4876
4877void LiveRangeConnector::ResolveControlFlow(Zone* local_zone) {
4878 // Lazily linearize live ranges in memory for fast lookup.
4879 LiveRangeFinder finder(data(), local_zone);
4880 ZoneVector<BitVector*>& live_in_sets = data()->live_in_sets();
4881 for (const InstructionBlock* block : code()->instruction_blocks()) {
4882 if (CanEagerlyResolveControlFlow(block)) continue;
4883 BitVector* live = live_in_sets[block->rpo_number().ToInt()];
4884 auto it = live->begin();
4885 auto end = live->end();
4886 while (it != end) {
4887 data()->tick_counter()->TickAndMaybeEnterSafepoint();
4888 int vreg = *it;
4889 LiveRangeBoundArray* array = finder.ArrayFor(vreg);
4890 for (const RpoNumber& pred : block->predecessors()) {
4891 FindResult result;
4892 const InstructionBlock* pred_block = code()->InstructionBlockAt(pred);
4893 if (!array->FindConnectableSubranges(block, pred_block, &result)) {
4894 continue;
4895 }
4896 InstructionOperand pred_op = result.pred_cover_->GetAssignedOperand();
4897 InstructionOperand cur_op = result.cur_cover_->GetAssignedOperand();
4898 if (pred_op.Equals(cur_op)) continue;
4899 if (!pred_op.IsAnyRegister() && cur_op.IsAnyRegister()) {
4900 // We're doing a reload.
4901 // We don't need to, if:
4902 // 1) there's no register use in this block, and
4903 // 2) the range ends before the block does, and
4904 // 3) we don't have a successor, or the successor is spilled.
4905 LifetimePosition block_start =
4906 LifetimePosition::GapFromInstructionIndex(block->code_start());
4907 LifetimePosition block_end =
4908 LifetimePosition::GapFromInstructionIndex(block->code_end());
4909 const LiveRange* current = result.cur_cover_;
4910 // Note that this is not the successor if we have control flow!
4911 // However, in the following condition, we only refer to it if it
4912 // begins in the current block, in which case we can safely declare it
4913 // to be the successor.
4914 const LiveRange* successor = current->next();
4915 if (current->End() < block_end &&
4916 (successor == nullptr || successor->spilled())) {
4917 // verify point 1: no register use. We can go to the end of the
4918 // range, since it's all within the block.
4919
4920 bool uses_reg = false;
4921 for (const UsePosition* use = current->NextUsePosition(block_start);
4922 use != nullptr; use = use->next()) {
4923 if (use->operand()->IsAnyRegister()) {
4924 uses_reg = true;
4925 break;
4926 }
4927 }
4928 if (!uses_reg) continue;
4929 }
4930 if (current->TopLevel()->IsSpilledOnlyInDeferredBlocks(data()) &&
4931 pred_block->IsDeferred()) {
4932 // The spill location should be defined in pred_block, so add
4933 // pred_block to the list of blocks requiring a spill operand.
4934 TRACE("Adding B%d to list of spill blocks for %d\n",
4935 pred_block->rpo_number().ToInt(),
4936 current->TopLevel()->vreg());
4937 current->TopLevel()
4938 ->GetListOfBlocksRequiringSpillOperands(data())
4939 ->Add(pred_block->rpo_number().ToInt());
4940 }
4941 }
4942 int move_loc = ResolveControlFlow(block, cur_op, pred_block, pred_op);
4943 USE(move_loc)do { ::v8::base::Use unused_tmp_array_for_use_macro[]{move_loc
}; (void)unused_tmp_array_for_use_macro; } while (false)
;
4944 DCHECK_IMPLIES(((void) 0)
4945 result.cur_cover_->TopLevel()->IsSpilledOnlyInDeferredBlocks(((void) 0)
4946 data()) &&((void) 0)
4947 !(pred_op.IsAnyRegister() && cur_op.IsAnyRegister()) &&((void) 0)
4948 move_loc != -1,((void) 0)
4949 code()->GetInstructionBlock(move_loc)->IsDeferred())((void) 0);
4950 }
4951 ++it;
4952 }
4953 }
4954
4955 // At this stage, we collected blocks needing a spill operand due to reloads
4956 // from ConnectRanges and from ResolveControlFlow. Time to commit the spills
4957 // for deferred blocks. This is a convenient time to commit spills for general
4958 // spill ranges also, because they need to use the LiveRangeFinder.
4959 const size_t live_ranges_size = data()->live_ranges().size();
4960 SpillPlacer spill_placer(&finder, data(), local_zone);
4961 for (TopLevelLiveRange* top : data()->live_ranges()) {
4962 CHECK_EQ(live_ranges_size,do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(data()->live_ranges
().size())>::type>((live_ranges_size), (data()->live_ranges
().size())); do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal
("Check failed: %s.", "live_ranges_size" " " "==" " " "data()->live_ranges().size()"
); } } while (false); } while (false)
4963 data()->live_ranges().size())do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(data()->live_ranges
().size())>::type>((live_ranges_size), (data()->live_ranges
().size())); do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal
("Check failed: %s.", "live_ranges_size" " " "==" " " "data()->live_ranges().size()"
); } } while (false); } while (false)
; // TODO(neis): crbug.com/831822
4964 if (top == nullptr || top->IsEmpty()) continue;
4965 if (top->IsSpilledOnlyInDeferredBlocks(data())) {
4966 CommitSpillsInDeferredBlocks(top, finder.ArrayFor(top->vreg()),
4967 local_zone);
4968 } else if (top->HasGeneralSpillRange()) {
4969 spill_placer.Add(top);
4970 }
4971 }
4972}
4973
4974int LiveRangeConnector::ResolveControlFlow(const InstructionBlock* block,
4975 const InstructionOperand& cur_op,
4976 const InstructionBlock* pred,
4977 const InstructionOperand& pred_op) {
4978 DCHECK(!pred_op.Equals(cur_op))((void) 0);
4979 int gap_index;
4980 Instruction::GapPosition position;
4981 if (block->PredecessorCount() == 1) {
4982 gap_index = block->first_instruction_index();
4983 position = Instruction::START;
4984 } else {
4985 Instruction* last = code()->InstructionAt(pred->last_instruction_index());
4986 // The connecting move might invalidate uses of the destination operand in
4987 // the deoptimization call. See crbug.com/v8/12218. Omitting the move is
4988 // safe since the deopt call exits the current code.
4989 if (last->IsDeoptimizeCall()) {
4990 return -1;
4991 }
4992 // In every other case the last instruction should not participate in
4993 // register allocation, or it could interfere with the connecting move.
4994 for (size_t i = 0; i < last->InputCount(); ++i) {
4995 DCHECK(last->InputAt(i)->IsImmediate())((void) 0);
4996 }
4997 DCHECK_EQ(1, pred->SuccessorCount())((void) 0);
4998 DCHECK(!code()((void) 0)
4999 ->InstructionAt(pred->last_instruction_index())((void) 0)
5000 ->HasReferenceMap())((void) 0);
5001 gap_index = pred->last_instruction_index();
5002 position = Instruction::END;
5003 }
5004 data()->AddGapMove(gap_index, position, pred_op, cur_op);
5005 return gap_index;
5006}
5007
5008void LiveRangeConnector::ConnectRanges(Zone* local_zone) {
5009 DelayedInsertionMap delayed_insertion_map(local_zone);
5010 const size_t live_ranges_size = data()->live_ranges().size();
5011 for (TopLevelLiveRange* top_range : data()->live_ranges()) {
5012 CHECK_EQ(live_ranges_size,do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(data()->live_ranges
().size())>::type>((live_ranges_size), (data()->live_ranges
().size())); do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal
("Check failed: %s.", "live_ranges_size" " " "==" " " "data()->live_ranges().size()"
); } } while (false); } while (false)
5013 data()->live_ranges().size())do { bool _cmp = ::v8::base::CmpEQImpl< typename ::v8::base
::pass_value_or_ref<decltype(live_ranges_size)>::type, typename
::v8::base::pass_value_or_ref<decltype(data()->live_ranges
().size())>::type>((live_ranges_size), (data()->live_ranges
().size())); do { if ((__builtin_expect(!!(!(_cmp)), 0))) { V8_Fatal
("Check failed: %s.", "live_ranges_size" " " "==" " " "data()->live_ranges().size()"
); } } while (false); } while (false)
; // TODO(neis): crbug.com/831822
5014 if (top_range == nullptr) continue;
5015 bool connect_spilled = top_range->IsSpilledOnlyInDeferredBlocks(data());
5016 LiveRange* first_range = top_range;
5017 for (LiveRange *second_range = first_range->next(); second_range != nullptr;
5018 first_range = second_range, second_range = second_range->next()) {
5019 LifetimePosition pos = second_range->Start();
5020 // Add gap move if the two live ranges touch and there is no block
5021 // boundary.
5022 if (second_range->spilled()) continue;
5023 if (first_range->End() != pos) continue;
5024 if (data()->IsBlockBoundary(pos) &&
5025 !CanEagerlyResolveControlFlow(GetInstructionBlock(code(), pos))) {
5026 continue;
5027 }
5028 InstructionOperand prev_operand = first_range->GetAssignedOperand();
5029 InstructionOperand cur_operand = second_range->GetAssignedOperand();
5030 if (prev_operand.Equals(cur_operand)) continue;
5031 bool delay_insertion = false;
5032 Instruction::GapPosition gap_pos;
5033 int gap_index = pos.ToInstructionIndex();
5034 if (connect_spilled && !prev_operand.IsAnyRegister() &&
5035 cur_operand.IsAnyRegister()) {
5036 const InstructionBlock* block = code()->GetInstructionBlock(gap_index);
5037 DCHECK(block->IsDeferred())((void) 0);
5038 // Performing a reload in this block, meaning the spill operand must
5039 // be defined here.
5040 top_range->GetListOfBlocksRequiringSpillOperands(data())->Add(
5041 block->rpo_number().ToInt());
5042 }
5043
5044 if (pos.IsGapPosition()) {
5045 gap_pos = pos.IsStart() ? Instruction::START : Instruction::END;
5046 } else {
5047 if (pos.IsStart()) {
5048 delay_insertion = true;
5049 } else {
5050 gap_index++;
5051 }
5052 gap_pos = delay_insertion ? Instruction::END : Instruction::START;
5053 }
5054 // Reloads or spills for spilled in deferred blocks ranges must happen
5055 // only in deferred blocks.
5056 DCHECK_IMPLIES(connect_spilled && !(prev_operand.IsAnyRegister() &&((void) 0)
5057 cur_operand.IsAnyRegister()),((void) 0)
5058 code()->GetInstructionBlock(gap_index)->IsDeferred())((void) 0);
5059
5060 ParallelMove* move =
5061 code()->InstructionAt(gap_index)->GetOrCreateParallelMove(
5062 gap_pos, code_zone());
5063 if (!delay_insertion) {
5064 move->AddMove(prev_operand, cur_operand);
5065 } else {
5066 delayed_insertion_map.insert(
5067 std::make_pair(std::make_pair(move, prev_operand), cur_operand));
5068 }
5069 }
5070 }
5071 if (delayed_insertion_map.empty()) return;
5072 // Insert all the moves which should occur after the stored move.
5073 ZoneVector<MoveOperands*> to_insert(local_zone);
5074 ZoneVector<MoveOperands*> to_eliminate(local_zone);
5075 to_insert.reserve(4);
5076 to_eliminate.reserve(4);
5077 ParallelMove* moves = delayed_insertion_map.begin()->first.first;
5078 for (auto it = delayed_insertion_map.begin();; ++it) {
5079 bool done = it == delayed_insertion_map.end();
5080 if (done || it->first.first != moves) {
5081 // Commit the MoveOperands for current ParallelMove.
5082 for (MoveOperands* move : to_eliminate) {
5083 move->Eliminate();
5084 }
5085 for (MoveOperands* move : to_insert) {
5086 moves->push_back(move);
5087 }
5088 if (done) break;
5089 // Reset state.
5090 to_eliminate.clear();
5091 to_insert.clear();
5092 moves = it->first.first;
5093 }
5094 // Gather all MoveOperands for a single ParallelMove.
5095 MoveOperands* move =
5096 code_zone()->New<MoveOperands>(it->first.second, it->second);
5097 moves->PrepareInsertAfter(move, &to_eliminate);
5098 to_insert.push_back(move);
5099 }
5100}
5101
5102void LiveRangeConnector::CommitSpillsInDeferredBlocks(
5103 TopLevelLiveRange* range, LiveRangeBoundArray* array, Zone* temp_zone) {
5104 DCHECK(range->IsSpilledOnlyInDeferredBlocks(data()))((void) 0);
5105 DCHECK(!range->spilled())((void) 0);
5106
5107 InstructionSequence* code = data()->code();
5108 InstructionOperand spill_operand = range->GetSpillRangeOperand();
5109
5110 TRACE("Live Range %d will be spilled only in deferred blocks.\n",
5111 range->vreg());
5112 // If we have ranges that aren't spilled but require the operand on the stack,
5113 // make sure we insert the spill.
5114 for (const LiveRange* child = range; child != nullptr;
5115 child = child->next()) {
5116 for (const UsePosition* pos = child->first_pos(); pos != nullptr;
5117 pos = pos->next()) {
5118 if (pos->type() != UsePositionType::kRequiresSlot && !child->spilled())
5119 continue;
5120 range->AddBlockRequiringSpillOperand(
5121 code->GetInstructionBlock(pos->pos().ToInstructionIndex())
5122 ->rpo_number(),
5123 data());
5124 }
5125 }
5126
5127 ZoneQueue<int> worklist(temp_zone);
5128
5129 for (int block_id : *range->GetListOfBlocksRequiringSpillOperands(data())) {
5130 worklist.push(block_id);
5131 }
5132
5133 ZoneSet<std::pair<RpoNumber, int>> done_moves(temp_zone);
5134 // Seek the deferred blocks that dominate locations requiring spill operands,
5135 // and spill there. We only need to spill at the start of such blocks.
5136 BitVector done_blocks(
5137 range->GetListOfBlocksRequiringSpillOperands(data())->length(),
5138 temp_zone);
5139 while (!worklist.empty()) {
5140 int block_id = worklist.front();
5141 worklist.pop();
5142 if (done_blocks.Contains(block_id)) continue;
5143 done_blocks.Add(block_id);
5144 InstructionBlock* spill_block =
5145 code->InstructionBlockAt(RpoNumber::FromInt(block_id));
5146
5147 for (const RpoNumber& pred : spill_block->predecessors()) {
5148 const InstructionBlock* pred_block = code->InstructionBlockAt(pred);
5149
5150 if (pred_block->IsDeferred()) {
5151 worklist.push(pred_block->rpo_number().ToInt());
5152 } else {
5153 LifetimePosition pred_end =
5154 LifetimePosition::InstructionFromInstructionIndex(
5155 pred_block->last_instruction_index());
5156
5157 LiveRangeBound* bound = array->Find(pred_end);
5158
5159 InstructionOperand pred_op = bound->range_->GetAssignedOperand();
5160
5161 RpoNumber spill_block_number = spill_block->rpo_number();
5162 if (done_moves.find(std::make_pair(
5163 spill_block_number, range->vreg())) == done_moves.end()) {
5164 TRACE("Spilling deferred spill for range %d at B%d\n", range->vreg(),
5165 spill_block_number.ToInt());
5166 data()->AddGapMove(spill_block->first_instruction_index(),
5167 Instruction::GapPosition::START, pred_op,
5168 spill_operand);
5169 done_moves.insert(std::make_pair(spill_block_number, range->vreg()));
5170 spill_block->mark_needs_frame();
5171 }
5172 }
5173 }
5174 }
5175}
5176
5177#undef TRACE
5178#undef TRACE_COND
5179
5180} // namespace compiler
5181} // namespace internal
5182} // namespace v8

../deps/v8/src/zone/zone.h

1// Copyright 2012 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#ifndef V8_ZONE_ZONE_H_
6#define V8_ZONE_ZONE_H_
7
8#include <limits>
9
10#include "src/base/logging.h"
11#include "src/common/globals.h"
12#include "src/utils/utils.h"
13#include "src/zone/accounting-allocator.h"
14#include "src/zone/type-stats.h"
15#include "src/zone/zone-segment.h"
16#include "src/zone/zone-type-traits.h"
17
18#ifndef ZONE_NAME__func__
19#define ZONE_NAME__func__ __func__
20#endif
21
22namespace v8 {
23namespace internal {
24
25// The Zone supports very fast allocation of small chunks of
26// memory. The chunks cannot be deallocated individually, but instead
27// the Zone supports deallocating all chunks in one fast
28// operation. The Zone is used to hold temporary data structures like
29// the abstract syntax tree, which is deallocated after compilation.
30//
31// Note: There is no need to initialize the Zone; the first time an
32// allocation is attempted, a segment of memory will be requested
33// through the allocator.
34//
35// Note: The implementation is inherently not thread safe. Do not use
36// from multi-threaded code.
37
38class V8_EXPORT_PRIVATE Zone final {
39 public:
40 Zone(AccountingAllocator* allocator, const char* name,
41 bool support_compression = false);
42 ~Zone();
43
44 // Returns true if the zone supports zone pointer compression.
45 bool supports_compression() const {
46 return COMPRESS_ZONES_BOOLfalse && supports_compression_;
47 }
48
49 // Allocate 'size' bytes of uninitialized memory in the Zone; expands the Zone
50 // by allocating new segments of memory on demand using AccountingAllocator
51 // (see AccountingAllocator::AllocateSegment()).
52 //
53 // When V8_ENABLE_PRECISE_ZONE_STATS is defined, the allocated bytes are
54 // associated with the provided TypeTag type.
55 template <typename TypeTag>
56 void* Allocate(size_t size) {
57#ifdef V8_USE_ADDRESS_SANITIZER
58 return AsanNew(size);
59#else
60 size = RoundUp(size, kAlignmentInBytes);
61#ifdef V8_ENABLE_PRECISE_ZONE_STATS
62 if (V8_UNLIKELY(TracingFlags::is_zone_stats_enabled())(__builtin_expect(!!(TracingFlags::is_zone_stats_enabled()), 0
))
) {
63 type_stats_.AddAllocated<TypeTag>(size);
64 }
65 allocation_size_for_tracing_ += size;
66#endif
67 Address result = position_;
68 if (V8_UNLIKELY(size > limit_ - position_)(__builtin_expect(!!(size > limit_ - position_), 0))) {
69 result = NewExpand(size);
70 } else {
71 position_ += size;
72 }
73 return reinterpret_cast<void*>(result);
74#endif // V8_USE_ADDRESS_SANITIZER
75 }
76
77 // Return 'size' bytes of memory back to Zone. These bytes can be reused
78 // for following allocations.
79 //
80 // When V8_ENABLE_PRECISE_ZONE_STATS is defined, the deallocated bytes are
81 // associated with the provided TypeTag type.
82 template <typename TypeTag = void>
83 void Delete(void* pointer, size_t size) {
84 DCHECK_NOT_NULL(pointer)((void) 0);
85 DCHECK_NE(size, 0)((void) 0);
86 size = RoundUp(size, kAlignmentInBytes);
87#ifdef V8_ENABLE_PRECISE_ZONE_STATS
88 if (V8_UNLIKELY(TracingFlags::is_zone_stats_enabled())(__builtin_expect(!!(TracingFlags::is_zone_stats_enabled()), 0
))
) {
89 type_stats_.AddDeallocated<TypeTag>(size);
90 }
91 freed_size_for_tracing_ += size;
92#endif
93
94#ifdef DEBUG
95 static const unsigned char kZapDeadByte = 0xcd;
96 memset(pointer, kZapDeadByte, size);
97#endif
98 }
99
100 // Allocates memory for T instance and constructs object by calling respective
101 // Args... constructor.
102 //
103 // When V8_ENABLE_PRECISE_ZONE_STATS is defined, the allocated bytes are
104 // associated with the T type.
105 template <typename T, typename... Args>
106 T* New(Args&&... args) {
107 void* memory = Allocate<T>(sizeof(T));
108 return new (memory) T(std::forward<Args>(args)...);
8
Calling constructor for 'SpillRange'
109 }
110
111 // Allocates uninitialized memory for 'length' number of T instances.
112 //
113 // When V8_ENABLE_PRECISE_ZONE_STATS is defined, the allocated bytes are
114 // associated with the provided TypeTag type. It might be useful to tag
115 // buffer allocations with meaningful names to make buffer allocation sites
116 // distinguishable between each other.
117 template <typename T, typename TypeTag = T[]>
118 T* NewArray(size_t length) {
119 DCHECK_IMPLIES(is_compressed_pointer<T>::value, supports_compression())((void) 0);
120 DCHECK_LT(length, std::numeric_limits<size_t>::max() / sizeof(T))((void) 0);
121 return static_cast<T*>(Allocate<TypeTag>(length * sizeof(T)));
122 }
123
124 // Return array of 'length' elements back to Zone. These bytes can be reused
125 // for following allocations.
126 //
127 // When V8_ENABLE_PRECISE_ZONE_STATS is defined, the deallocated bytes are
128 // associated with the provided TypeTag type.
129 template <typename T, typename TypeTag = T[]>
130 void DeleteArray(T* pointer, size_t length) {
131 Delete<TypeTag>(pointer, length * sizeof(T));
132 }
133
134 // Seals the zone to prevent any further allocation.
135 void Seal() { sealed_ = true; }
136
137 // Allows the zone to be safely reused. Releases the memory except for the
138 // last page, and fires zone destruction and creation events for the
139 // accounting allocator.
140 void Reset();
141
142 size_t segment_bytes_allocated() const { return segment_bytes_allocated_; }
143
144 const char* name() const { return name_; }
145
146 // Returns precise value of used zone memory, allowed to be called only
147 // from thread owning the zone.
148 size_t allocation_size() const {
149 size_t extra = segment_head_ ? position_ - segment_head_->start() : 0;
150 return allocation_size_ + extra;
151 }
152
153 // When V8_ENABLE_PRECISE_ZONE_STATS is not defined, returns used zone memory
154 // not including the head segment.
155 // Can be called from threads not owning the zone.
156 size_t allocation_size_for_tracing() const {
157#ifdef V8_ENABLE_PRECISE_ZONE_STATS
158 return allocation_size_for_tracing_;
159#else
160 return allocation_size_;
161#endif
162 }
163
164 // Returns number of bytes freed in this zone via Delete<T>()/DeleteArray<T>()
165 // calls. Returns non-zero values only when V8_ENABLE_PRECISE_ZONE_STATS is
166 // defined.
167 size_t freed_size_for_tracing() const {
168#ifdef V8_ENABLE_PRECISE_ZONE_STATS
169 return freed_size_for_tracing_;
170#else
171 return 0;
172#endif
173 }
174
175 AccountingAllocator* allocator() const { return allocator_; }
176
177#ifdef V8_ENABLE_PRECISE_ZONE_STATS
178 const TypeStats& type_stats() const { return type_stats_; }
179#endif
180
181 private:
182 void* AsanNew(size_t size);
183
184 // Deletes all objects and free all memory allocated in the Zone.
185 void DeleteAll();
186
187 // Releases the current segment without performing any local bookkeeping
188 // (e.g. tracking allocated bytes, maintaining linked lists, etc).
189 void ReleaseSegment(Segment* segment);
190
191 // All pointers returned from New() are 8-byte aligned.
192 static const size_t kAlignmentInBytes = 8;
193
194 // Never allocate segments smaller than this size in bytes.
195 static const size_t kMinimumSegmentSize = 8 * KB;
196
197 // Never allocate segments larger than this size in bytes.
198 static const size_t kMaximumSegmentSize = 32 * KB;
199
200 // The number of bytes allocated in this zone so far.
201 std::atomic<size_t> allocation_size_ = {0};
202
203 // The number of bytes allocated in segments. Note that this number
204 // includes memory allocated from the OS but not yet allocated from
205 // the zone.
206 std::atomic<size_t> segment_bytes_allocated_ = {0};
207
208 // Expand the Zone to hold at least 'size' more bytes and allocate
209 // the bytes. Returns the address of the newly allocated chunk of
210 // memory in the Zone. Should only be called if there isn't enough
211 // room in the Zone already.
212 Address NewExpand(size_t size);
213
214 // The free region in the current (front) segment is represented as
215 // the half-open interval [position, limit). The 'position' variable
216 // is guaranteed to be aligned as dictated by kAlignment.
217 Address position_ = 0;
218 Address limit_ = 0;
219
220 AccountingAllocator* allocator_;
221
222 Segment* segment_head_ = nullptr;
223 const char* name_;
224 const bool supports_compression_;
225 bool sealed_ = false;
226
227#ifdef V8_ENABLE_PRECISE_ZONE_STATS
228 TypeStats type_stats_;
229 std::atomic<size_t> allocation_size_for_tracing_ = {0};
230
231 // The number of bytes freed in this zone so far.
232 stdd::atomic<size_t> freed_size_for_tracing_ = {0};
233#endif
234
235 friend class ZoneScope;
236};
237
238// Similar to the HandleScope, the ZoneScope defines a region of validity for
239// zone memory. All memory allocated in the given Zone during the scope's
240// lifetime is freed when the scope is destructed, i.e. the Zone is reset to
241// the state it was in when the scope was created.
242class ZoneScope final {
243 public:
244 explicit ZoneScope(Zone* zone);
245 ~ZoneScope();
246
247 private:
248 Zone* const zone_;
249#ifdef V8_ENABLE_PRECISE_ZONE_STATS
250 const size_t allocation_size_for_tracing_;
251 const size_t freed_size_for_tracing_;
252#endif
253 const size_t allocation_size_;
254 const size_t segment_bytes_allocated_;
255 const Address position_;
256 const Address limit_;
257 Segment* const segment_head_;
258};
259
260// ZoneObject is an abstraction that helps define classes of objects
261// allocated in the Zone. Use it as a base class; see ast.h.
262class ZoneObject {
263 public:
264 // The accidential old-style pattern
265 // new (zone) SomeObject(...)
266 // now produces compilation error. The proper way of allocating objects in
267 // Zones looks like this:
268 // zone->New<SomeObject>(...)
269 void* operator new(size_t, Zone*) = delete; // See explanation above.
270 // Allow non-allocating placement new.
271 void* operator new(size_t size, void* ptr) { // See explanation above.
272 return ptr;
273 }
274
275 // Ideally, the delete operator should be private instead of
276 // public, but unfortunately the compiler sometimes synthesizes
277 // (unused) destructors for classes derived from ZoneObject, which
278 // require the operator to be visible. MSVC requires the delete
279 // operator to be public.
280
281 // ZoneObjects should never be deleted individually; use
282 // Zone::DeleteAll() to delete all zone objects in one go.
283 // Note, that descructors will not be called.
284 void operator delete(void*, size_t) { UNREACHABLE()V8_Fatal("unreachable code"); }
285 void operator delete(void* pointer, Zone* zone) = delete;
286};
287
288// The ZoneAllocationPolicy is used to specialize generic data
289// structures to allocate themselves and their elements in the Zone.
290class ZoneAllocationPolicy {
291 public:
292 // Creates unusable allocation policy.
293 ZoneAllocationPolicy() : zone_(nullptr) {}
294 explicit ZoneAllocationPolicy(Zone* zone) : zone_(zone) {}
295
296 template <typename T, typename TypeTag = T[]>
297 V8_INLINEinline __attribute__((always_inline)) T* NewArray(size_t length) {
298 return zone()->NewArray<T, TypeTag>(length);
299 }
300 template <typename T, typename TypeTag = T[]>
301 V8_INLINEinline __attribute__((always_inline)) void DeleteArray(T* p, size_t length) {
302 zone()->DeleteArray<T, TypeTag>(p, length);
303 }
304
305 Zone* zone() const { return zone_; }
306
307 private:
308 Zone* zone_;
309};
310
311} // namespace internal
312} // namespace v8
313
314// The accidential old-style pattern
315// new (zone) SomeObject(...)
316// now produces compilation error. The proper way of allocating objects in
317// Zones looks like this:
318// zone->New<SomeObject>(...)
319void* operator new(size_t, v8::internal::Zone*) = delete; // See explanation.
320void operator delete(void*, v8::internal::Zone*) = delete; // See explanation.
321
322#endif // V8_ZONE_ZONE_H_