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 | #ifndef V8_COMPILER_BACKEND_REGISTER_ALLOCATOR_H_ |
6 | #define V8_COMPILER_BACKEND_REGISTER_ALLOCATOR_H_ |
7 | |
8 | #include "src/base/bits.h" |
9 | #include "src/base/compiler-specific.h" |
10 | #include "src/compiler/backend/instruction.h" |
11 | #include "src/flags.h" |
12 | #include "src/globals.h" |
13 | #include "src/ostreams.h" |
14 | #include "src/register-configuration.h" |
15 | #include "src/zone/zone-containers.h" |
16 | |
17 | namespace v8 { |
18 | namespace internal { |
19 | namespace compiler { |
20 | |
21 | static const int32_t kUnassignedRegister = RegisterConfiguration::kMaxRegisters; |
22 | |
23 | enum RegisterKind { GENERAL_REGISTERS, FP_REGISTERS }; |
24 | |
25 | // This class represents a single point of a InstructionOperand's lifetime. For |
26 | // each instruction there are four lifetime positions: |
27 | // |
28 | // [[START, END], [START, END]] |
29 | // |
30 | // Where the first half position corresponds to |
31 | // |
32 | // [GapPosition::START, GapPosition::END] |
33 | // |
34 | // and the second half position corresponds to |
35 | // |
36 | // [Lifetime::USED_AT_START, Lifetime::USED_AT_END] |
37 | // |
38 | class LifetimePosition final { |
39 | public: |
40 | // Return the lifetime position that corresponds to the beginning of |
41 | // the gap with the given index. |
42 | static LifetimePosition GapFromInstructionIndex(int index) { |
43 | return LifetimePosition(index * kStep); |
44 | } |
45 | // Return the lifetime position that corresponds to the beginning of |
46 | // the instruction with the given index. |
47 | static LifetimePosition InstructionFromInstructionIndex(int index) { |
48 | return LifetimePosition(index * kStep + kHalfStep); |
49 | } |
50 | |
51 | static bool ExistsGapPositionBetween(LifetimePosition pos1, |
52 | LifetimePosition pos2) { |
53 | if (pos1 > pos2) std::swap(pos1, pos2); |
54 | LifetimePosition next(pos1.value_ + 1); |
55 | if (next.IsGapPosition()) return next < pos2; |
56 | return next.NextFullStart() < pos2; |
57 | } |
58 | |
59 | // Returns a numeric representation of this lifetime position. |
60 | int value() const { return value_; } |
61 | |
62 | // Returns the index of the instruction to which this lifetime position |
63 | // corresponds. |
64 | int ToInstructionIndex() const { |
65 | DCHECK(IsValid()); |
66 | return value_ / kStep; |
67 | } |
68 | |
69 | // Returns true if this lifetime position corresponds to a START value |
70 | bool IsStart() const { return (value_ & (kHalfStep - 1)) == 0; } |
71 | // Returns true if this lifetime position corresponds to an END value |
72 | bool IsEnd() const { return (value_ & (kHalfStep - 1)) == 1; } |
73 | // Returns true if this lifetime position corresponds to a gap START value |
74 | bool IsFullStart() const { return (value_ & (kStep - 1)) == 0; } |
75 | |
76 | bool IsGapPosition() const { return (value_ & 0x2) == 0; } |
77 | bool IsInstructionPosition() const { return !IsGapPosition(); } |
78 | |
79 | // Returns the lifetime position for the current START. |
80 | LifetimePosition Start() const { |
81 | DCHECK(IsValid()); |
82 | return LifetimePosition(value_ & ~(kHalfStep - 1)); |
83 | } |
84 | |
85 | // Returns the lifetime position for the current gap START. |
86 | LifetimePosition FullStart() const { |
87 | DCHECK(IsValid()); |
88 | return LifetimePosition(value_ & ~(kStep - 1)); |
89 | } |
90 | |
91 | // Returns the lifetime position for the current END. |
92 | LifetimePosition End() const { |
93 | DCHECK(IsValid()); |
94 | return LifetimePosition(Start().value_ + kHalfStep / 2); |
95 | } |
96 | |
97 | // Returns the lifetime position for the beginning of the next START. |
98 | LifetimePosition NextStart() const { |
99 | DCHECK(IsValid()); |
100 | return LifetimePosition(Start().value_ + kHalfStep); |
101 | } |
102 | |
103 | // Returns the lifetime position for the beginning of the next gap START. |
104 | LifetimePosition NextFullStart() const { |
105 | DCHECK(IsValid()); |
106 | return LifetimePosition(FullStart().value_ + kStep); |
107 | } |
108 | |
109 | // Returns the lifetime position for the beginning of the previous START. |
110 | LifetimePosition PrevStart() const { |
111 | DCHECK(IsValid()); |
112 | DCHECK_LE(kHalfStep, value_); |
113 | return LifetimePosition(Start().value_ - kHalfStep); |
114 | } |
115 | |
116 | // Constructs the lifetime position which does not correspond to any |
117 | // instruction. |
118 | LifetimePosition() : value_(-1) {} |
119 | |
120 | // Returns true if this lifetime positions corrensponds to some |
121 | // instruction. |
122 | bool IsValid() const { return value_ != -1; } |
123 | |
124 | bool operator<(const LifetimePosition& that) const { |
125 | return this->value_ < that.value_; |
126 | } |
127 | |
128 | bool operator<=(const LifetimePosition& that) const { |
129 | return this->value_ <= that.value_; |
130 | } |
131 | |
132 | bool operator==(const LifetimePosition& that) const { |
133 | return this->value_ == that.value_; |
134 | } |
135 | |
136 | bool operator!=(const LifetimePosition& that) const { |
137 | return this->value_ != that.value_; |
138 | } |
139 | |
140 | bool operator>(const LifetimePosition& that) const { |
141 | return this->value_ > that.value_; |
142 | } |
143 | |
144 | bool operator>=(const LifetimePosition& that) const { |
145 | return this->value_ >= that.value_; |
146 | } |
147 | |
148 | void Print() const; |
149 | |
150 | static inline LifetimePosition Invalid() { return LifetimePosition(); } |
151 | |
152 | static inline LifetimePosition MaxPosition() { |
153 | // We have to use this kind of getter instead of static member due to |
154 | // crash bug in GDB. |
155 | return LifetimePosition(kMaxInt); |
156 | } |
157 | |
158 | static inline LifetimePosition FromInt(int value) { |
159 | return LifetimePosition(value); |
160 | } |
161 | |
162 | private: |
163 | static const int kHalfStep = 2; |
164 | static const int kStep = 2 * kHalfStep; |
165 | |
166 | static_assert(base::bits::IsPowerOfTwo(kHalfStep), |
167 | "Code relies on kStep and kHalfStep being a power of two" ); |
168 | |
169 | explicit LifetimePosition(int value) : value_(value) {} |
170 | |
171 | int value_; |
172 | }; |
173 | |
174 | std::ostream& operator<<(std::ostream& os, const LifetimePosition pos); |
175 | |
176 | enum class RegisterAllocationFlag : unsigned { |
177 | kTurboControlFlowAwareAllocation = 1 << 0, |
178 | kTurboPreprocessRanges = 1 << 1 |
179 | }; |
180 | |
181 | using RegisterAllocationFlags = base::Flags<RegisterAllocationFlag>; |
182 | |
183 | class SpillRange; |
184 | class LiveRange; |
185 | class TopLevelLiveRange; |
186 | |
187 | class RegisterAllocationData final : public ZoneObject { |
188 | public: |
189 | // Encodes whether a spill happens in deferred code (kSpillDeferred) or |
190 | // regular code (kSpillAtDefinition). |
191 | enum SpillMode { kSpillAtDefinition, kSpillDeferred }; |
192 | |
193 | bool is_turbo_control_flow_aware_allocation() const { |
194 | return flags_ & RegisterAllocationFlag::kTurboControlFlowAwareAllocation; |
195 | } |
196 | |
197 | bool is_turbo_preprocess_ranges() const { |
198 | return flags_ & RegisterAllocationFlag::kTurboPreprocessRanges; |
199 | } |
200 | |
201 | static constexpr int kNumberOfFixedRangesPerRegister = 2; |
202 | |
203 | class PhiMapValue : public ZoneObject { |
204 | public: |
205 | PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone); |
206 | |
207 | const PhiInstruction* phi() const { return phi_; } |
208 | const InstructionBlock* block() const { return block_; } |
209 | |
210 | // For hinting. |
211 | int assigned_register() const { return assigned_register_; } |
212 | void set_assigned_register(int register_code) { |
213 | DCHECK_EQ(assigned_register_, kUnassignedRegister); |
214 | assigned_register_ = register_code; |
215 | } |
216 | void UnsetAssignedRegister() { assigned_register_ = kUnassignedRegister; } |
217 | |
218 | void AddOperand(InstructionOperand* operand); |
219 | void CommitAssignment(const InstructionOperand& operand); |
220 | |
221 | private: |
222 | PhiInstruction* const phi_; |
223 | const InstructionBlock* const block_; |
224 | ZoneVector<InstructionOperand*> incoming_operands_; |
225 | int assigned_register_; |
226 | }; |
227 | using PhiMap = ZoneMap<int, PhiMapValue*>; |
228 | |
229 | struct DelayedReference { |
230 | ReferenceMap* map; |
231 | InstructionOperand* operand; |
232 | }; |
233 | using DelayedReferences = ZoneVector<DelayedReference>; |
234 | using RangesWithPreassignedSlots = |
235 | ZoneVector<std::pair<TopLevelLiveRange*, int>>; |
236 | |
237 | RegisterAllocationData(const RegisterConfiguration* config, |
238 | Zone* allocation_zone, Frame* frame, |
239 | InstructionSequence* code, |
240 | RegisterAllocationFlags flags, |
241 | const char* debug_name = nullptr); |
242 | |
243 | const ZoneVector<TopLevelLiveRange*>& live_ranges() const { |
244 | return live_ranges_; |
245 | } |
246 | ZoneVector<TopLevelLiveRange*>& live_ranges() { return live_ranges_; } |
247 | const ZoneVector<TopLevelLiveRange*>& fixed_live_ranges() const { |
248 | return fixed_live_ranges_; |
249 | } |
250 | ZoneVector<TopLevelLiveRange*>& fixed_live_ranges() { |
251 | return fixed_live_ranges_; |
252 | } |
253 | ZoneVector<TopLevelLiveRange*>& fixed_float_live_ranges() { |
254 | return fixed_float_live_ranges_; |
255 | } |
256 | const ZoneVector<TopLevelLiveRange*>& fixed_float_live_ranges() const { |
257 | return fixed_float_live_ranges_; |
258 | } |
259 | ZoneVector<TopLevelLiveRange*>& fixed_double_live_ranges() { |
260 | return fixed_double_live_ranges_; |
261 | } |
262 | const ZoneVector<TopLevelLiveRange*>& fixed_double_live_ranges() const { |
263 | return fixed_double_live_ranges_; |
264 | } |
265 | ZoneVector<TopLevelLiveRange*>& fixed_simd128_live_ranges() { |
266 | return fixed_simd128_live_ranges_; |
267 | } |
268 | const ZoneVector<TopLevelLiveRange*>& fixed_simd128_live_ranges() const { |
269 | return fixed_simd128_live_ranges_; |
270 | } |
271 | ZoneVector<BitVector*>& live_in_sets() { return live_in_sets_; } |
272 | ZoneVector<BitVector*>& live_out_sets() { return live_out_sets_; } |
273 | ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; } |
274 | DelayedReferences& delayed_references() { return delayed_references_; } |
275 | InstructionSequence* code() const { return code_; } |
276 | // This zone is for data structures only needed during register allocation |
277 | // phases. |
278 | Zone* allocation_zone() const { return allocation_zone_; } |
279 | // This zone is for InstructionOperands and moves that live beyond register |
280 | // allocation. |
281 | Zone* code_zone() const { return code()->zone(); } |
282 | Frame* frame() const { return frame_; } |
283 | const char* debug_name() const { return debug_name_; } |
284 | const RegisterConfiguration* config() const { return config_; } |
285 | |
286 | MachineRepresentation RepresentationFor(int virtual_register); |
287 | |
288 | TopLevelLiveRange* GetOrCreateLiveRangeFor(int index); |
289 | // Creates a new live range. |
290 | TopLevelLiveRange* NewLiveRange(int index, MachineRepresentation rep); |
291 | TopLevelLiveRange* NextLiveRange(MachineRepresentation rep); |
292 | |
293 | SpillRange* AssignSpillRangeToLiveRange(TopLevelLiveRange* range, |
294 | SpillMode spill_mode); |
295 | SpillRange* CreateSpillRangeForLiveRange(TopLevelLiveRange* range); |
296 | |
297 | MoveOperands* AddGapMove(int index, Instruction::GapPosition position, |
298 | const InstructionOperand& from, |
299 | const InstructionOperand& to); |
300 | |
301 | bool ExistsUseWithoutDefinition(); |
302 | bool RangesDefinedInDeferredStayInDeferred(); |
303 | |
304 | void MarkFixedUse(MachineRepresentation rep, int index); |
305 | bool HasFixedUse(MachineRepresentation rep, int index); |
306 | |
307 | void MarkAllocated(MachineRepresentation rep, int index); |
308 | |
309 | PhiMapValue* InitializePhiMap(const InstructionBlock* block, |
310 | PhiInstruction* phi); |
311 | PhiMapValue* GetPhiMapValueFor(TopLevelLiveRange* top_range); |
312 | PhiMapValue* GetPhiMapValueFor(int virtual_register); |
313 | bool IsBlockBoundary(LifetimePosition pos) const; |
314 | |
315 | RangesWithPreassignedSlots& preassigned_slot_ranges() { |
316 | return preassigned_slot_ranges_; |
317 | } |
318 | |
319 | void RememberSpillState(RpoNumber block, |
320 | const ZoneVector<LiveRange*>& state) { |
321 | spill_state_[block.ToSize()] = state; |
322 | } |
323 | |
324 | ZoneVector<LiveRange*>& GetSpillState(RpoNumber block) { |
325 | auto& result = spill_state_[block.ToSize()]; |
326 | return result; |
327 | } |
328 | |
329 | void ResetSpillState() { spill_state_.clear(); } |
330 | |
331 | private: |
332 | int GetNextLiveRangeId(); |
333 | |
334 | Zone* const allocation_zone_; |
335 | Frame* const frame_; |
336 | InstructionSequence* const code_; |
337 | const char* const debug_name_; |
338 | const RegisterConfiguration* const config_; |
339 | PhiMap phi_map_; |
340 | ZoneVector<BitVector*> live_in_sets_; |
341 | ZoneVector<BitVector*> live_out_sets_; |
342 | ZoneVector<TopLevelLiveRange*> live_ranges_; |
343 | ZoneVector<TopLevelLiveRange*> fixed_live_ranges_; |
344 | ZoneVector<TopLevelLiveRange*> fixed_float_live_ranges_; |
345 | ZoneVector<TopLevelLiveRange*> fixed_double_live_ranges_; |
346 | ZoneVector<TopLevelLiveRange*> fixed_simd128_live_ranges_; |
347 | ZoneVector<SpillRange*> spill_ranges_; |
348 | DelayedReferences delayed_references_; |
349 | BitVector* assigned_registers_; |
350 | BitVector* assigned_double_registers_; |
351 | BitVector* fixed_register_use_; |
352 | BitVector* fixed_fp_register_use_; |
353 | int virtual_register_count_; |
354 | RangesWithPreassignedSlots preassigned_slot_ranges_; |
355 | ZoneVector<ZoneVector<LiveRange*>> spill_state_; |
356 | RegisterAllocationFlags flags_; |
357 | |
358 | DISALLOW_COPY_AND_ASSIGN(RegisterAllocationData); |
359 | }; |
360 | |
361 | // Representation of the non-empty interval [start,end[. |
362 | class UseInterval final : public ZoneObject { |
363 | public: |
364 | UseInterval(LifetimePosition start, LifetimePosition end) |
365 | : start_(start), end_(end), next_(nullptr) { |
366 | DCHECK(start < end); |
367 | } |
368 | |
369 | LifetimePosition start() const { return start_; } |
370 | void set_start(LifetimePosition start) { start_ = start; } |
371 | LifetimePosition end() const { return end_; } |
372 | void set_end(LifetimePosition end) { end_ = end; } |
373 | UseInterval* next() const { return next_; } |
374 | void set_next(UseInterval* next) { next_ = next; } |
375 | |
376 | // Split this interval at the given position without effecting the |
377 | // live range that owns it. The interval must contain the position. |
378 | UseInterval* SplitAt(LifetimePosition pos, Zone* zone); |
379 | |
380 | // If this interval intersects with other return smallest position |
381 | // that belongs to both of them. |
382 | LifetimePosition Intersect(const UseInterval* other) const { |
383 | if (other->start() < start_) return other->Intersect(this); |
384 | if (other->start() < end_) return other->start(); |
385 | return LifetimePosition::Invalid(); |
386 | } |
387 | |
388 | bool Contains(LifetimePosition point) const { |
389 | return start_ <= point && point < end_; |
390 | } |
391 | |
392 | // Returns the index of the first gap covered by this interval. |
393 | int FirstGapIndex() const { |
394 | int ret = start_.ToInstructionIndex(); |
395 | if (start_.IsInstructionPosition()) { |
396 | ++ret; |
397 | } |
398 | return ret; |
399 | } |
400 | |
401 | // Returns the index of the last gap covered by this interval. |
402 | int LastGapIndex() const { |
403 | int ret = end_.ToInstructionIndex(); |
404 | if (end_.IsGapPosition() && end_.IsStart()) { |
405 | --ret; |
406 | } |
407 | return ret; |
408 | } |
409 | |
410 | private: |
411 | LifetimePosition start_; |
412 | LifetimePosition end_; |
413 | UseInterval* next_; |
414 | |
415 | DISALLOW_COPY_AND_ASSIGN(UseInterval); |
416 | }; |
417 | |
418 | enum class UsePositionType : uint8_t { |
419 | kRegisterOrSlot, |
420 | kRegisterOrSlotOrConstant, |
421 | kRequiresRegister, |
422 | kRequiresSlot |
423 | }; |
424 | |
425 | enum class UsePositionHintType : uint8_t { |
426 | kNone, |
427 | kOperand, |
428 | kUsePos, |
429 | kPhi, |
430 | kUnresolved |
431 | }; |
432 | |
433 | // Representation of a use position. |
434 | class V8_EXPORT_PRIVATE UsePosition final |
435 | : public NON_EXPORTED_BASE(ZoneObject) { |
436 | public: |
437 | UsePosition(LifetimePosition pos, InstructionOperand* operand, void* hint, |
438 | UsePositionHintType hint_type); |
439 | |
440 | InstructionOperand* operand() const { return operand_; } |
441 | bool HasOperand() const { return operand_ != nullptr; } |
442 | |
443 | bool RegisterIsBeneficial() const { |
444 | return RegisterBeneficialField::decode(flags_); |
445 | } |
446 | UsePositionType type() const { return TypeField::decode(flags_); } |
447 | void set_type(UsePositionType type, bool register_beneficial); |
448 | |
449 | LifetimePosition pos() const { return pos_; } |
450 | |
451 | UsePosition* next() const { return next_; } |
452 | void set_next(UsePosition* next) { next_ = next; } |
453 | |
454 | // For hinting only. |
455 | void set_assigned_register(int register_code) { |
456 | flags_ = AssignedRegisterField::update(flags_, register_code); |
457 | } |
458 | |
459 | UsePositionHintType hint_type() const { |
460 | return HintTypeField::decode(flags_); |
461 | } |
462 | bool HasHint() const; |
463 | bool HintRegister(int* register_code) const; |
464 | void SetHint(UsePosition* use_pos); |
465 | void ResolveHint(UsePosition* use_pos); |
466 | bool IsResolved() const { |
467 | return hint_type() != UsePositionHintType::kUnresolved; |
468 | } |
469 | static UsePositionHintType HintTypeForOperand(const InstructionOperand& op); |
470 | |
471 | private: |
472 | using TypeField = BitField<UsePositionType, 0, 2>; |
473 | using HintTypeField = BitField<UsePositionHintType, 2, 3>; |
474 | using RegisterBeneficialField = BitField<bool, 5, 1>; |
475 | using AssignedRegisterField = BitField<int32_t, 6, 6>; |
476 | |
477 | InstructionOperand* const operand_; |
478 | void* hint_; |
479 | UsePosition* next_; |
480 | LifetimePosition const pos_; |
481 | uint32_t flags_; |
482 | |
483 | DISALLOW_COPY_AND_ASSIGN(UsePosition); |
484 | }; |
485 | |
486 | class SpillRange; |
487 | class RegisterAllocationData; |
488 | class TopLevelLiveRange; |
489 | class LiveRangeBundle; |
490 | |
491 | // Representation of SSA values' live ranges as a collection of (continuous) |
492 | // intervals over the instruction ordering. |
493 | class V8_EXPORT_PRIVATE LiveRange : public NON_EXPORTED_BASE(ZoneObject) { |
494 | public: |
495 | UseInterval* first_interval() const { return first_interval_; } |
496 | UsePosition* first_pos() const { return first_pos_; } |
497 | TopLevelLiveRange* TopLevel() { return top_level_; } |
498 | const TopLevelLiveRange* TopLevel() const { return top_level_; } |
499 | |
500 | bool IsTopLevel() const; |
501 | |
502 | LiveRange* next() const { return next_; } |
503 | |
504 | int relative_id() const { return relative_id_; } |
505 | |
506 | bool IsEmpty() const { return first_interval() == nullptr; } |
507 | |
508 | InstructionOperand GetAssignedOperand() const; |
509 | |
510 | MachineRepresentation representation() const { |
511 | return RepresentationField::decode(bits_); |
512 | } |
513 | |
514 | int assigned_register() const { return AssignedRegisterField::decode(bits_); } |
515 | bool HasRegisterAssigned() const { |
516 | return assigned_register() != kUnassignedRegister; |
517 | } |
518 | void set_assigned_register(int reg); |
519 | void UnsetAssignedRegister(); |
520 | |
521 | bool ShouldRecombine() const { return RecombineField::decode(bits_); } |
522 | |
523 | void SetRecombine() { bits_ = RecombineField::update(bits_, true); } |
524 | void set_controlflow_hint(int reg) { |
525 | bits_ = ControlFlowRegisterHint::update(bits_, reg); |
526 | } |
527 | int controlflow_hint() const { |
528 | return ControlFlowRegisterHint::decode(bits_); |
529 | } |
530 | bool RegisterFromControlFlow(int* reg) { |
531 | int hint = controlflow_hint(); |
532 | if (hint != kUnassignedRegister) { |
533 | *reg = hint; |
534 | return true; |
535 | } |
536 | return false; |
537 | } |
538 | bool spilled() const { return SpilledField::decode(bits_); } |
539 | void AttachToNext(); |
540 | void Unspill(); |
541 | void Spill(); |
542 | |
543 | RegisterKind kind() const; |
544 | |
545 | // Returns use position in this live range that follows both start |
546 | // and last processed use position. |
547 | UsePosition* NextUsePosition(LifetimePosition start) const; |
548 | |
549 | // Returns use position for which register is required in this live |
550 | // range and which follows both start and last processed use position |
551 | UsePosition* NextRegisterPosition(LifetimePosition start) const; |
552 | |
553 | // Returns the first use position requiring stack slot, or nullptr. |
554 | UsePosition* NextSlotPosition(LifetimePosition start) const; |
555 | |
556 | // Returns use position for which register is beneficial in this live |
557 | // range and which follows both start and last processed use position |
558 | UsePosition* NextUsePositionRegisterIsBeneficial( |
559 | LifetimePosition start) const; |
560 | |
561 | // Returns lifetime position for which register is beneficial in this live |
562 | // range and which follows both start and last processed use position. |
563 | LifetimePosition NextLifetimePositionRegisterIsBeneficial( |
564 | const LifetimePosition& start) const; |
565 | |
566 | // Returns use position for which register is beneficial in this live |
567 | // range and which precedes start. |
568 | UsePosition* PreviousUsePositionRegisterIsBeneficial( |
569 | LifetimePosition start) const; |
570 | |
571 | // Can this live range be spilled at this position. |
572 | bool CanBeSpilled(LifetimePosition pos) const; |
573 | |
574 | // Splitting primitive used by both splitting and splintering members. |
575 | // Performs the split, but does not link the resulting ranges. |
576 | // The given position must follow the start of the range. |
577 | // All uses following the given position will be moved from this |
578 | // live range to the result live range. |
579 | // The current range will terminate at position, while result will start from |
580 | // position. |
581 | enum HintConnectionOption : bool { |
582 | DoNotConnectHints = false, |
583 | ConnectHints = true |
584 | }; |
585 | UsePosition* DetachAt(LifetimePosition position, LiveRange* result, |
586 | Zone* zone, HintConnectionOption connect_hints); |
587 | |
588 | // Detaches at position, and then links the resulting ranges. Returns the |
589 | // child, which starts at position. |
590 | LiveRange* SplitAt(LifetimePosition position, Zone* zone); |
591 | |
592 | // Returns nullptr when no register is hinted, otherwise sets register_index. |
593 | UsePosition* FirstHintPosition(int* register_index) const; |
594 | UsePosition* FirstHintPosition() const { |
595 | int register_index; |
596 | return FirstHintPosition(®ister_index); |
597 | } |
598 | |
599 | UsePosition* current_hint_position() const { |
600 | DCHECK(current_hint_position_ == FirstHintPosition()); |
601 | return current_hint_position_; |
602 | } |
603 | |
604 | LifetimePosition Start() const { |
605 | DCHECK(!IsEmpty()); |
606 | return first_interval()->start(); |
607 | } |
608 | |
609 | LifetimePosition End() const { |
610 | DCHECK(!IsEmpty()); |
611 | return last_interval_->end(); |
612 | } |
613 | |
614 | bool ShouldBeAllocatedBefore(const LiveRange* other) const; |
615 | bool CanCover(LifetimePosition position) const; |
616 | bool Covers(LifetimePosition position) const; |
617 | LifetimePosition NextStartAfter(LifetimePosition position) const; |
618 | LifetimePosition NextEndAfter(LifetimePosition position) const; |
619 | LifetimePosition FirstIntersection(LiveRange* other) const; |
620 | |
621 | void VerifyChildStructure() const { |
622 | VerifyIntervals(); |
623 | VerifyPositions(); |
624 | } |
625 | |
626 | void ConvertUsesToOperand(const InstructionOperand& op, |
627 | const InstructionOperand& spill_op); |
628 | void SetUseHints(int register_index); |
629 | void UnsetUseHints() { SetUseHints(kUnassignedRegister); } |
630 | |
631 | void Print(const RegisterConfiguration* config, bool with_children) const; |
632 | void Print(bool with_children) const; |
633 | |
634 | void set_bundle(LiveRangeBundle* bundle) { bundle_ = bundle; } |
635 | LiveRangeBundle* get_bundle() const { return bundle_; } |
636 | bool RegisterFromBundle(int* hint) const; |
637 | void UpdateBundleRegister(int reg) const; |
638 | |
639 | private: |
640 | friend class TopLevelLiveRange; |
641 | explicit LiveRange(int relative_id, MachineRepresentation rep, |
642 | TopLevelLiveRange* top_level); |
643 | |
644 | void UpdateParentForAllChildren(TopLevelLiveRange* new_top_level); |
645 | |
646 | void set_spilled(bool value) { bits_ = SpilledField::update(bits_, value); } |
647 | |
648 | UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; |
649 | void AdvanceLastProcessedMarker(UseInterval* to_start_of, |
650 | LifetimePosition but_not_past) const; |
651 | |
652 | void VerifyPositions() const; |
653 | void VerifyIntervals() const; |
654 | |
655 | using SpilledField = BitField<bool, 0, 1>; |
656 | // Bits (1,7[ are used by TopLevelLiveRange. |
657 | using AssignedRegisterField = BitField<int32_t, 7, 6>; |
658 | using RepresentationField = BitField<MachineRepresentation, 13, 8>; |
659 | using RecombineField = BitField<bool, 21, 1>; |
660 | using ControlFlowRegisterHint = BitField<uint8_t, 22, 6>; |
661 | // Bit 28 is used by TopLevelLiveRange. |
662 | |
663 | // Unique among children and splinters of the same virtual register. |
664 | int relative_id_; |
665 | uint32_t bits_; |
666 | UseInterval* last_interval_; |
667 | UseInterval* first_interval_; |
668 | UsePosition* first_pos_; |
669 | TopLevelLiveRange* top_level_; |
670 | LiveRange* next_; |
671 | // This is used as a cache, it doesn't affect correctness. |
672 | mutable UseInterval* current_interval_; |
673 | // This is used as a cache, it doesn't affect correctness. |
674 | mutable UsePosition* last_processed_use_; |
675 | // This is used as a cache, it's invalid outside of BuildLiveRanges. |
676 | mutable UsePosition* current_hint_position_; |
677 | // Cache the last position splintering stopped at. |
678 | mutable UsePosition* splitting_pointer_; |
679 | LiveRangeBundle* bundle_ = nullptr; |
680 | |
681 | DISALLOW_COPY_AND_ASSIGN(LiveRange); |
682 | }; |
683 | |
684 | struct LiveRangeOrdering { |
685 | bool operator()(const LiveRange* left, const LiveRange* right) const { |
686 | return left->Start() < right->Start(); |
687 | } |
688 | }; |
689 | class LiveRangeBundle : public ZoneObject { |
690 | public: |
691 | void MergeSpillRanges(); |
692 | |
693 | int id() { return id_; } |
694 | |
695 | int reg() { return reg_; } |
696 | |
697 | void set_reg(int reg) { |
698 | DCHECK_EQ(reg_, kUnassignedRegister); |
699 | reg_ = reg; |
700 | } |
701 | |
702 | private: |
703 | friend class BundleBuilder; |
704 | |
705 | class Range { |
706 | public: |
707 | Range(int s, int e) : start(s), end(e) {} |
708 | Range(LifetimePosition s, LifetimePosition e) |
709 | : start(s.value()), end(e.value()) {} |
710 | int start; |
711 | int end; |
712 | }; |
713 | |
714 | struct RangeOrdering { |
715 | bool operator()(const Range left, const Range right) const { |
716 | return left.start < right.start; |
717 | } |
718 | }; |
719 | bool UsesOverlap(UseInterval* interval) { |
720 | auto use = uses_.begin(); |
721 | while (interval != nullptr && use != uses_.end()) { |
722 | if (use->end <= interval->start().value()) { |
723 | ++use; |
724 | } else if (interval->end().value() <= use->start) { |
725 | interval = interval->next(); |
726 | } else { |
727 | return true; |
728 | } |
729 | } |
730 | return false; |
731 | } |
732 | void InsertUses(UseInterval* interval) { |
733 | while (interval != nullptr) { |
734 | auto done = uses_.insert({interval->start(), interval->end()}); |
735 | USE(done); |
736 | DCHECK_EQ(done.second, 1); |
737 | interval = interval->next(); |
738 | } |
739 | } |
740 | explicit LiveRangeBundle(Zone* zone, int id) |
741 | : ranges_(zone), uses_(zone), id_(id) {} |
742 | |
743 | bool TryAddRange(LiveRange* range); |
744 | bool TryMerge(LiveRangeBundle* other); |
745 | |
746 | ZoneSet<LiveRange*, LiveRangeOrdering> ranges_; |
747 | ZoneSet<Range, RangeOrdering> uses_; |
748 | int id_; |
749 | int reg_ = kUnassignedRegister; |
750 | }; |
751 | |
752 | class V8_EXPORT_PRIVATE TopLevelLiveRange final : public LiveRange { |
753 | public: |
754 | explicit TopLevelLiveRange(int vreg, MachineRepresentation rep); |
755 | int spill_start_index() const { return spill_start_index_; } |
756 | |
757 | bool IsFixed() const { return vreg_ < 0; } |
758 | |
759 | bool IsDeferredFixed() const { return DeferredFixedField::decode(bits_); } |
760 | void set_deferred_fixed() { bits_ = DeferredFixedField::update(bits_, true); } |
761 | bool is_phi() const { return IsPhiField::decode(bits_); } |
762 | void set_is_phi(bool value) { bits_ = IsPhiField::update(bits_, value); } |
763 | |
764 | bool is_non_loop_phi() const { return IsNonLoopPhiField::decode(bits_); } |
765 | void set_is_non_loop_phi(bool value) { |
766 | bits_ = IsNonLoopPhiField::update(bits_, value); |
767 | } |
768 | |
769 | enum SlotUseKind { kNoSlotUse, kDeferredSlotUse, kGeneralSlotUse }; |
770 | |
771 | bool has_slot_use() const { |
772 | return slot_use_kind() > SlotUseKind::kNoSlotUse; |
773 | } |
774 | |
775 | bool has_non_deferred_slot_use() const { |
776 | return slot_use_kind() == SlotUseKind::kGeneralSlotUse; |
777 | } |
778 | |
779 | void reset_slot_use() { |
780 | bits_ = HasSlotUseField::update(bits_, SlotUseKind::kNoSlotUse); |
781 | } |
782 | void register_slot_use(SlotUseKind value) { |
783 | bits_ = HasSlotUseField::update(bits_, Max(slot_use_kind(), value)); |
784 | } |
785 | SlotUseKind slot_use_kind() const { return HasSlotUseField::decode(bits_); } |
786 | |
787 | // Add a new interval or a new use position to this live range. |
788 | void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); |
789 | void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); |
790 | void AddUsePosition(UsePosition* pos); |
791 | |
792 | // Shorten the most recently added interval by setting a new start. |
793 | void ShortenTo(LifetimePosition start); |
794 | |
795 | // Detaches between start and end, and attributes the resulting range to |
796 | // result. |
797 | // The current range is pointed to as "splintered_from". No parent/child |
798 | // relationship is established between this and result. |
799 | void Splinter(LifetimePosition start, LifetimePosition end, Zone* zone); |
800 | |
801 | // Assuming other was splintered from this range, embeds other and its |
802 | // children as part of the children sequence of this range. |
803 | void Merge(TopLevelLiveRange* other, Zone* zone); |
804 | |
805 | // Spill range management. |
806 | void SetSpillRange(SpillRange* spill_range); |
807 | |
808 | // Encodes whether a range is also available from a memory localtion: |
809 | // kNoSpillType: not availble in memory location. |
810 | // kSpillOperand: computed in a memory location at range start. |
811 | // kSpillRange: copied (spilled) to memory location at range start. |
812 | // kDeferredSpillRange: copied (spilled) to memory location at entry |
813 | // to deferred blocks that have a use from memory. |
814 | // |
815 | // Ranges either start out at kSpillOperand, which is also their final |
816 | // state, or kNoSpillType. When spilled only in deferred code, a range |
817 | // ends up with kDeferredSpillRange, while when spilled in regular code, |
818 | // a range will be tagged as kSpillRange. |
819 | enum class SpillType { |
820 | kNoSpillType, |
821 | kSpillOperand, |
822 | kSpillRange, |
823 | kDeferredSpillRange |
824 | }; |
825 | void set_spill_type(SpillType value) { |
826 | bits_ = SpillTypeField::update(bits_, value); |
827 | } |
828 | SpillType spill_type() const { return SpillTypeField::decode(bits_); } |
829 | InstructionOperand* GetSpillOperand() const { |
830 | DCHECK_EQ(SpillType::kSpillOperand, spill_type()); |
831 | return spill_operand_; |
832 | } |
833 | |
834 | SpillRange* GetAllocatedSpillRange() const { |
835 | DCHECK_NE(SpillType::kSpillOperand, spill_type()); |
836 | return spill_range_; |
837 | } |
838 | |
839 | SpillRange* GetSpillRange() const { |
840 | DCHECK_GE(spill_type(), SpillType::kSpillRange); |
841 | return spill_range_; |
842 | } |
843 | bool HasNoSpillType() const { |
844 | return spill_type() == SpillType::kNoSpillType; |
845 | } |
846 | bool HasSpillOperand() const { |
847 | return spill_type() == SpillType::kSpillOperand; |
848 | } |
849 | bool HasSpillRange() const { return spill_type() >= SpillType::kSpillRange; } |
850 | bool HasGeneralSpillRange() const { |
851 | return spill_type() == SpillType::kSpillRange; |
852 | } |
853 | AllocatedOperand GetSpillRangeOperand() const; |
854 | |
855 | void RecordSpillLocation(Zone* zone, int gap_index, |
856 | InstructionOperand* operand); |
857 | void SetSpillOperand(InstructionOperand* operand); |
858 | void SetSpillStartIndex(int start) { |
859 | spill_start_index_ = Min(start, spill_start_index_); |
860 | } |
861 | |
862 | void CommitSpillMoves(RegisterAllocationData* data, |
863 | const InstructionOperand& operand, |
864 | bool might_be_duplicated); |
865 | |
866 | // If all the children of this range are spilled in deferred blocks, and if |
867 | // for any non-spilled child with a use position requiring a slot, that range |
868 | // is contained in a deferred block, mark the range as |
869 | // IsSpilledOnlyInDeferredBlocks, so that we avoid spilling at definition, |
870 | // and instead let the LiveRangeConnector perform the spills within the |
871 | // deferred blocks. If so, we insert here spills for non-spilled ranges |
872 | // with slot use positions. |
873 | void TreatAsSpilledInDeferredBlock(Zone* zone, int total_block_count) { |
874 | spill_start_index_ = -1; |
875 | spilled_in_deferred_blocks_ = true; |
876 | spill_move_insertion_locations_ = nullptr; |
877 | list_of_blocks_requiring_spill_operands_ = |
878 | new (zone) BitVector(total_block_count, zone); |
879 | } |
880 | |
881 | // Updates internal data structures to reflect that this range is not |
882 | // spilled at definition but instead spilled in some blocks only. |
883 | void TransitionRangeToDeferredSpill(Zone* zone, int total_block_count) { |
884 | spill_start_index_ = -1; |
885 | spill_move_insertion_locations_ = nullptr; |
886 | list_of_blocks_requiring_spill_operands_ = |
887 | new (zone) BitVector(total_block_count, zone); |
888 | } |
889 | |
890 | // Promotes this range to spill at definition if it was marked for spilling |
891 | // in deferred blocks before. |
892 | void TransitionRangeToSpillAtDefinition() { |
893 | DCHECK_NOT_NULL(spill_move_insertion_locations_); |
894 | if (spill_type() == SpillType::kDeferredSpillRange) { |
895 | set_spill_type(SpillType::kSpillRange); |
896 | } |
897 | } |
898 | |
899 | TopLevelLiveRange* splintered_from() const { return splintered_from_; } |
900 | bool IsSplinter() const { return splintered_from_ != nullptr; } |
901 | bool MayRequireSpillRange() const { |
902 | DCHECK(!IsSplinter()); |
903 | return !HasSpillOperand() && spill_range_ == nullptr; |
904 | } |
905 | void UpdateSpillRangePostMerge(TopLevelLiveRange* merged); |
906 | int vreg() const { return vreg_; } |
907 | |
908 | #if DEBUG |
909 | int debug_virt_reg() const; |
910 | #endif |
911 | |
912 | void Verify() const; |
913 | void VerifyChildrenInOrder() const; |
914 | LiveRange* GetChildCovers(LifetimePosition pos); |
915 | int GetNextChildId() { |
916 | return IsSplinter() ? splintered_from()->GetNextChildId() |
917 | : ++last_child_id_; |
918 | } |
919 | |
920 | int GetMaxChildCount() const { return last_child_id_ + 1; } |
921 | |
922 | bool IsSpilledOnlyInDeferredBlocks(const RegisterAllocationData* data) const { |
923 | if (data->is_turbo_control_flow_aware_allocation()) { |
924 | return spill_type() == SpillType::kDeferredSpillRange; |
925 | } |
926 | return spilled_in_deferred_blocks_; |
927 | } |
928 | |
929 | struct SpillMoveInsertionList; |
930 | |
931 | SpillMoveInsertionList* GetSpillMoveInsertionLocations( |
932 | const RegisterAllocationData* data) const { |
933 | DCHECK(!IsSpilledOnlyInDeferredBlocks(data)); |
934 | return spill_move_insertion_locations_; |
935 | } |
936 | TopLevelLiveRange* splinter() const { return splinter_; } |
937 | void SetSplinter(TopLevelLiveRange* splinter) { |
938 | DCHECK_NULL(splinter_); |
939 | DCHECK_NOT_NULL(splinter); |
940 | |
941 | splinter_ = splinter; |
942 | splinter->relative_id_ = GetNextChildId(); |
943 | splinter->set_spill_type(spill_type()); |
944 | splinter->SetSplinteredFrom(this); |
945 | if (bundle_ != nullptr) splinter->set_bundle(bundle_); |
946 | } |
947 | |
948 | void MarkHasPreassignedSlot() { has_preassigned_slot_ = true; } |
949 | bool has_preassigned_slot() const { return has_preassigned_slot_; } |
950 | |
951 | void AddBlockRequiringSpillOperand(RpoNumber block_id, |
952 | const RegisterAllocationData* data) { |
953 | DCHECK(IsSpilledOnlyInDeferredBlocks(data)); |
954 | GetListOfBlocksRequiringSpillOperands(data)->Add(block_id.ToInt()); |
955 | } |
956 | |
957 | BitVector* GetListOfBlocksRequiringSpillOperands( |
958 | const RegisterAllocationData* data) const { |
959 | DCHECK(IsSpilledOnlyInDeferredBlocks(data)); |
960 | return list_of_blocks_requiring_spill_operands_; |
961 | } |
962 | |
963 | private: |
964 | friend class LiveRange; |
965 | void SetSplinteredFrom(TopLevelLiveRange* splinter_parent); |
966 | |
967 | using HasSlotUseField = BitField<SlotUseKind, 1, 2>; |
968 | using IsPhiField = BitField<bool, 3, 1>; |
969 | using IsNonLoopPhiField = BitField<bool, 4, 1>; |
970 | using SpillTypeField = BitField<SpillType, 5, 2>; |
971 | using DeferredFixedField = BitField<bool, 28, 1>; |
972 | |
973 | int vreg_; |
974 | int last_child_id_; |
975 | TopLevelLiveRange* splintered_from_; |
976 | union { |
977 | // Correct value determined by spill_type() |
978 | InstructionOperand* spill_operand_; |
979 | SpillRange* spill_range_; |
980 | }; |
981 | |
982 | union { |
983 | SpillMoveInsertionList* spill_move_insertion_locations_; |
984 | BitVector* list_of_blocks_requiring_spill_operands_; |
985 | }; |
986 | |
987 | // TODO(mtrofin): generalize spilling after definition, currently specialized |
988 | // just for spill in a single deferred block. |
989 | bool spilled_in_deferred_blocks_; |
990 | int spill_start_index_; |
991 | UsePosition* last_pos_; |
992 | LiveRange* last_child_covers_; |
993 | TopLevelLiveRange* splinter_; |
994 | bool has_preassigned_slot_; |
995 | |
996 | DISALLOW_COPY_AND_ASSIGN(TopLevelLiveRange); |
997 | }; |
998 | |
999 | struct PrintableLiveRange { |
1000 | const RegisterConfiguration* register_configuration_; |
1001 | const LiveRange* range_; |
1002 | }; |
1003 | |
1004 | std::ostream& operator<<(std::ostream& os, |
1005 | const PrintableLiveRange& printable_range); |
1006 | |
1007 | class SpillRange final : public ZoneObject { |
1008 | public: |
1009 | static const int kUnassignedSlot = -1; |
1010 | SpillRange(TopLevelLiveRange* range, Zone* zone); |
1011 | |
1012 | UseInterval* interval() const { return use_interval_; } |
1013 | |
1014 | bool IsEmpty() const { return live_ranges_.empty(); } |
1015 | bool TryMerge(SpillRange* other); |
1016 | bool HasSlot() const { return assigned_slot_ != kUnassignedSlot; } |
1017 | |
1018 | void set_assigned_slot(int index) { |
1019 | DCHECK_EQ(kUnassignedSlot, assigned_slot_); |
1020 | assigned_slot_ = index; |
1021 | } |
1022 | int assigned_slot() { |
1023 | DCHECK_NE(kUnassignedSlot, assigned_slot_); |
1024 | return assigned_slot_; |
1025 | } |
1026 | const ZoneVector<TopLevelLiveRange*>& live_ranges() const { |
1027 | return live_ranges_; |
1028 | } |
1029 | ZoneVector<TopLevelLiveRange*>& live_ranges() { return live_ranges_; } |
1030 | // Spill slots can be 4, 8, or 16 bytes wide. |
1031 | int byte_width() const { return byte_width_; } |
1032 | void Print() const; |
1033 | |
1034 | private: |
1035 | LifetimePosition End() const { return end_position_; } |
1036 | bool IsIntersectingWith(SpillRange* other) const; |
1037 | // Merge intervals, making sure the use intervals are sorted |
1038 | void MergeDisjointIntervals(UseInterval* other); |
1039 | |
1040 | ZoneVector<TopLevelLiveRange*> live_ranges_; |
1041 | UseInterval* use_interval_; |
1042 | LifetimePosition end_position_; |
1043 | int assigned_slot_; |
1044 | int byte_width_; |
1045 | |
1046 | DISALLOW_COPY_AND_ASSIGN(SpillRange); |
1047 | }; |
1048 | |
1049 | class ConstraintBuilder final : public ZoneObject { |
1050 | public: |
1051 | explicit ConstraintBuilder(RegisterAllocationData* data); |
1052 | |
1053 | // Phase 1 : insert moves to account for fixed register operands. |
1054 | void MeetRegisterConstraints(); |
1055 | |
1056 | // Phase 2: deconstruct SSA by inserting moves in successors and the headers |
1057 | // of blocks containing phis. |
1058 | void ResolvePhis(); |
1059 | |
1060 | private: |
1061 | RegisterAllocationData* data() const { return data_; } |
1062 | InstructionSequence* code() const { return data()->code(); } |
1063 | Zone* allocation_zone() const { return data()->allocation_zone(); } |
1064 | |
1065 | InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos, |
1066 | bool is_tagged, bool is_input); |
1067 | void MeetRegisterConstraints(const InstructionBlock* block); |
1068 | void MeetConstraintsBefore(int index); |
1069 | void MeetConstraintsAfter(int index); |
1070 | void MeetRegisterConstraintsForLastInstructionInBlock( |
1071 | const InstructionBlock* block); |
1072 | void ResolvePhis(const InstructionBlock* block); |
1073 | |
1074 | RegisterAllocationData* const data_; |
1075 | |
1076 | DISALLOW_COPY_AND_ASSIGN(ConstraintBuilder); |
1077 | }; |
1078 | |
1079 | class LiveRangeBuilder final : public ZoneObject { |
1080 | public: |
1081 | explicit LiveRangeBuilder(RegisterAllocationData* data, Zone* local_zone); |
1082 | |
1083 | // Phase 3: compute liveness of all virtual register. |
1084 | void BuildLiveRanges(); |
1085 | static BitVector* ComputeLiveOut(const InstructionBlock* block, |
1086 | RegisterAllocationData* data); |
1087 | |
1088 | private: |
1089 | using SpillMode = RegisterAllocationData::SpillMode; |
1090 | static constexpr int kNumberOfFixedRangesPerRegister = |
1091 | RegisterAllocationData::kNumberOfFixedRangesPerRegister; |
1092 | |
1093 | RegisterAllocationData* data() const { return data_; } |
1094 | InstructionSequence* code() const { return data()->code(); } |
1095 | Zone* allocation_zone() const { return data()->allocation_zone(); } |
1096 | Zone* code_zone() const { return code()->zone(); } |
1097 | const RegisterConfiguration* config() const { return data()->config(); } |
1098 | ZoneVector<BitVector*>& live_in_sets() const { |
1099 | return data()->live_in_sets(); |
1100 | } |
1101 | |
1102 | // Verification. |
1103 | void Verify() const; |
1104 | bool IntervalStartsAtBlockBoundary(const UseInterval* interval) const; |
1105 | bool IntervalPredecessorsCoveredByRange(const UseInterval* interval, |
1106 | const TopLevelLiveRange* range) const; |
1107 | bool NextIntervalStartsInDifferentBlocks(const UseInterval* interval) const; |
1108 | |
1109 | // Liveness analysis support. |
1110 | void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out); |
1111 | void ProcessInstructions(const InstructionBlock* block, BitVector* live); |
1112 | void ProcessPhis(const InstructionBlock* block, BitVector* live); |
1113 | void (const InstructionBlock* block, BitVector* live); |
1114 | |
1115 | static int FixedLiveRangeID(int index) { return -index - 1; } |
1116 | int FixedFPLiveRangeID(int index, MachineRepresentation rep); |
1117 | TopLevelLiveRange* FixedLiveRangeFor(int index, SpillMode spill_mode); |
1118 | TopLevelLiveRange* FixedFPLiveRangeFor(int index, MachineRepresentation rep, |
1119 | SpillMode spill_mode); |
1120 | |
1121 | void MapPhiHint(InstructionOperand* operand, UsePosition* use_pos); |
1122 | void ResolvePhiHint(InstructionOperand* operand, UsePosition* use_pos); |
1123 | |
1124 | UsePosition* NewUsePosition(LifetimePosition pos, InstructionOperand* operand, |
1125 | void* hint, UsePositionHintType hint_type); |
1126 | UsePosition* NewUsePosition(LifetimePosition pos) { |
1127 | return NewUsePosition(pos, nullptr, nullptr, UsePositionHintType::kNone); |
1128 | } |
1129 | TopLevelLiveRange* LiveRangeFor(InstructionOperand* operand, |
1130 | SpillMode spill_mode); |
1131 | // Helper methods for building intervals. |
1132 | UsePosition* Define(LifetimePosition position, InstructionOperand* operand, |
1133 | void* hint, UsePositionHintType hint_type, |
1134 | SpillMode spill_mode); |
1135 | void Define(LifetimePosition position, InstructionOperand* operand, |
1136 | SpillMode spill_mode) { |
1137 | Define(position, operand, nullptr, UsePositionHintType::kNone, spill_mode); |
1138 | } |
1139 | UsePosition* Use(LifetimePosition block_start, LifetimePosition position, |
1140 | InstructionOperand* operand, void* hint, |
1141 | UsePositionHintType hint_type, SpillMode spill_mode); |
1142 | void Use(LifetimePosition block_start, LifetimePosition position, |
1143 | InstructionOperand* operand, SpillMode spill_mode) { |
1144 | Use(block_start, position, operand, nullptr, UsePositionHintType::kNone, |
1145 | spill_mode); |
1146 | } |
1147 | SpillMode SpillModeForBlock(const InstructionBlock* block) const { |
1148 | if (data()->is_turbo_control_flow_aware_allocation()) { |
1149 | return block->IsDeferred() ? SpillMode::kSpillDeferred |
1150 | : SpillMode::kSpillAtDefinition; |
1151 | } |
1152 | return SpillMode::kSpillAtDefinition; |
1153 | } |
1154 | RegisterAllocationData* const data_; |
1155 | ZoneMap<InstructionOperand*, UsePosition*> phi_hints_; |
1156 | |
1157 | DISALLOW_COPY_AND_ASSIGN(LiveRangeBuilder); |
1158 | }; |
1159 | |
1160 | class BundleBuilder final : public ZoneObject { |
1161 | public: |
1162 | explicit BundleBuilder(RegisterAllocationData* data) : data_(data) {} |
1163 | |
1164 | void BuildBundles(); |
1165 | |
1166 | private: |
1167 | RegisterAllocationData* data() const { return data_; } |
1168 | InstructionSequence* code() const { return data_->code(); } |
1169 | RegisterAllocationData* data_; |
1170 | int next_bundle_id_ = 0; |
1171 | }; |
1172 | |
1173 | class RegisterAllocator : public ZoneObject { |
1174 | public: |
1175 | RegisterAllocator(RegisterAllocationData* data, RegisterKind kind); |
1176 | |
1177 | protected: |
1178 | using SpillMode = RegisterAllocationData::SpillMode; |
1179 | RegisterAllocationData* data() const { return data_; } |
1180 | InstructionSequence* code() const { return data()->code(); } |
1181 | RegisterKind mode() const { return mode_; } |
1182 | int num_registers() const { return num_registers_; } |
1183 | int num_allocatable_registers() const { return num_allocatable_registers_; } |
1184 | const int* allocatable_register_codes() const { |
1185 | return allocatable_register_codes_; |
1186 | } |
1187 | // Returns true iff. we must check float register aliasing. |
1188 | bool check_fp_aliasing() const { return check_fp_aliasing_; } |
1189 | |
1190 | // TODO(mtrofin): explain why splitting in gap START is always OK. |
1191 | LifetimePosition GetSplitPositionForInstruction(const LiveRange* range, |
1192 | int instruction_index); |
1193 | |
1194 | Zone* allocation_zone() const { return data()->allocation_zone(); } |
1195 | |
1196 | // Find the optimal split for ranges defined by a memory operand, e.g. |
1197 | // constants or function parameters passed on the stack. |
1198 | void SplitAndSpillRangesDefinedByMemoryOperand(); |
1199 | |
1200 | // Split the given range at the given position. |
1201 | // If range starts at or after the given position then the |
1202 | // original range is returned. |
1203 | // Otherwise returns the live range that starts at pos and contains |
1204 | // all uses from the original range that follow pos. Uses at pos will |
1205 | // still be owned by the original range after splitting. |
1206 | LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); |
1207 | |
1208 | bool CanProcessRange(LiveRange* range) const { |
1209 | return range != nullptr && !range->IsEmpty() && range->kind() == mode(); |
1210 | } |
1211 | |
1212 | // Split the given range in a position from the interval [start, end]. |
1213 | LiveRange* SplitBetween(LiveRange* range, LifetimePosition start, |
1214 | LifetimePosition end); |
1215 | |
1216 | // Find a lifetime position in the interval [start, end] which |
1217 | // is optimal for splitting: it is either header of the outermost |
1218 | // loop covered by this interval or the latest possible position. |
1219 | LifetimePosition FindOptimalSplitPos(LifetimePosition start, |
1220 | LifetimePosition end); |
1221 | |
1222 | void Spill(LiveRange* range, SpillMode spill_mode); |
1223 | |
1224 | // If we are trying to spill a range inside the loop try to |
1225 | // hoist spill position out to the point just before the loop. |
1226 | LifetimePosition FindOptimalSpillingPos(LiveRange* range, |
1227 | LifetimePosition pos); |
1228 | |
1229 | const ZoneVector<TopLevelLiveRange*>& GetFixedRegisters() const; |
1230 | const char* RegisterName(int allocation_index) const; |
1231 | |
1232 | private: |
1233 | RegisterAllocationData* const data_; |
1234 | const RegisterKind mode_; |
1235 | const int num_registers_; |
1236 | int num_allocatable_registers_; |
1237 | const int* allocatable_register_codes_; |
1238 | bool check_fp_aliasing_; |
1239 | |
1240 | private: |
1241 | bool no_combining_; |
1242 | |
1243 | DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); |
1244 | }; |
1245 | |
1246 | class LinearScanAllocator final : public RegisterAllocator { |
1247 | public: |
1248 | LinearScanAllocator(RegisterAllocationData* data, RegisterKind kind, |
1249 | Zone* local_zone); |
1250 | |
1251 | // Phase 4: compute register assignments. |
1252 | void AllocateRegisters(); |
1253 | |
1254 | private: |
1255 | struct RangeWithRegister { |
1256 | TopLevelLiveRange* range; |
1257 | int expected_register; |
1258 | struct Hash { |
1259 | size_t operator()(const RangeWithRegister item) const { |
1260 | return item.range->vreg(); |
1261 | } |
1262 | }; |
1263 | struct Equals { |
1264 | bool operator()(const RangeWithRegister one, |
1265 | const RangeWithRegister two) const { |
1266 | return one.range == two.range; |
1267 | } |
1268 | }; |
1269 | |
1270 | explicit RangeWithRegister(LiveRange* a_range) |
1271 | : range(a_range->TopLevel()), |
1272 | expected_register(a_range->assigned_register()) {} |
1273 | RangeWithRegister(TopLevelLiveRange* toplevel, int reg) |
1274 | : range(toplevel), expected_register(reg) {} |
1275 | }; |
1276 | |
1277 | using RangeWithRegisterSet = |
1278 | ZoneUnorderedSet<RangeWithRegister, RangeWithRegister::Hash, |
1279 | RangeWithRegister::Equals>; |
1280 | |
1281 | void MaybeUndoPreviousSplit(LiveRange* range); |
1282 | void SpillNotLiveRanges(RangeWithRegisterSet& to_be_live, |
1283 | LifetimePosition position, SpillMode spill_mode); |
1284 | LiveRange* AssignRegisterOnReload(LiveRange* range, int reg); |
1285 | void ReloadLiveRanges(RangeWithRegisterSet& to_be_live, |
1286 | LifetimePosition position); |
1287 | |
1288 | void UpdateDeferredFixedRanges(SpillMode spill_mode, InstructionBlock* block); |
1289 | bool BlockIsDeferredOrImmediatePredecessorIsNotDeferred( |
1290 | const InstructionBlock* block); |
1291 | bool HasNonDeferredPredecessor(InstructionBlock* block); |
1292 | |
1293 | struct LiveRangeOrdering { |
1294 | bool operator()(const LiveRange* a, const LiveRange* b) const { |
1295 | return a->ShouldBeAllocatedBefore(b); |
1296 | } |
1297 | }; |
1298 | using LiveRangeQueue = ZoneMultiset<LiveRange*, LiveRangeOrdering>; |
1299 | LiveRangeQueue& unhandled_live_ranges() { return unhandled_live_ranges_; } |
1300 | ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; } |
1301 | ZoneVector<LiveRange*>& inactive_live_ranges() { |
1302 | return inactive_live_ranges_; |
1303 | } |
1304 | |
1305 | void SetLiveRangeAssignedRegister(LiveRange* range, int reg); |
1306 | |
1307 | // Helper methods for updating the life range lists. |
1308 | void AddToActive(LiveRange* range); |
1309 | void AddToInactive(LiveRange* range); |
1310 | void AddToUnhandled(LiveRange* range); |
1311 | ZoneVector<LiveRange*>::iterator ActiveToHandled( |
1312 | ZoneVector<LiveRange*>::iterator it); |
1313 | ZoneVector<LiveRange*>::iterator ActiveToInactive( |
1314 | ZoneVector<LiveRange*>::iterator it, LifetimePosition position); |
1315 | ZoneVector<LiveRange*>::iterator InactiveToHandled( |
1316 | ZoneVector<LiveRange*>::iterator it); |
1317 | ZoneVector<LiveRange*>::iterator InactiveToActive( |
1318 | ZoneVector<LiveRange*>::iterator it, LifetimePosition position); |
1319 | |
1320 | void ForwardStateTo(LifetimePosition position); |
1321 | |
1322 | int LastDeferredInstructionIndex(InstructionBlock* start); |
1323 | |
1324 | // Helper methods for choosing state after control flow events. |
1325 | |
1326 | bool ConsiderBlockForControlFlow(InstructionBlock* current_block, |
1327 | RpoNumber predecessor); |
1328 | RpoNumber ChooseOneOfTwoPredecessorStates(InstructionBlock* current_block, |
1329 | LifetimePosition boundary); |
1330 | void ComputeStateFromManyPredecessors(InstructionBlock* current_block, |
1331 | RangeWithRegisterSet* to_be_live); |
1332 | |
1333 | // Helper methods for allocating registers. |
1334 | bool TryReuseSpillForPhi(TopLevelLiveRange* range); |
1335 | int PickRegisterThatIsAvailableLongest( |
1336 | LiveRange* current, int hint_reg, |
1337 | const Vector<LifetimePosition>& free_until_pos); |
1338 | bool TryAllocateFreeReg(LiveRange* range, |
1339 | const Vector<LifetimePosition>& free_until_pos); |
1340 | bool TryAllocatePreferredReg(LiveRange* range, |
1341 | const Vector<LifetimePosition>& free_until_pos); |
1342 | void GetFPRegisterSet(MachineRepresentation rep, int* num_regs, |
1343 | int* num_codes, const int** codes) const; |
1344 | void FindFreeRegistersForRange(LiveRange* range, |
1345 | Vector<LifetimePosition> free_until_pos); |
1346 | void ProcessCurrentRange(LiveRange* current, SpillMode spill_mode); |
1347 | void AllocateBlockedReg(LiveRange* range, SpillMode spill_mode); |
1348 | bool TrySplitAndSpillSplinter(LiveRange* range); |
1349 | |
1350 | // Spill the given life range after position pos. |
1351 | void SpillAfter(LiveRange* range, LifetimePosition pos, SpillMode spill_mode); |
1352 | |
1353 | // Spill the given life range after position [start] and up to position [end]. |
1354 | void SpillBetween(LiveRange* range, LifetimePosition start, |
1355 | LifetimePosition end, SpillMode spill_mode); |
1356 | |
1357 | // Spill the given life range after position [start] and up to position [end]. |
1358 | // Range is guaranteed to be spilled at least until position [until]. |
1359 | void SpillBetweenUntil(LiveRange* range, LifetimePosition start, |
1360 | LifetimePosition until, LifetimePosition end, |
1361 | SpillMode spill_mode); |
1362 | void SplitAndSpillIntersecting(LiveRange* range, SpillMode spill_mode); |
1363 | |
1364 | void PrintRangeRow(std::ostream& os, const TopLevelLiveRange* toplevel); |
1365 | |
1366 | void PrintRangeOverview(std::ostream& os); |
1367 | |
1368 | LiveRangeQueue unhandled_live_ranges_; |
1369 | ZoneVector<LiveRange*> active_live_ranges_; |
1370 | ZoneVector<LiveRange*> inactive_live_ranges_; |
1371 | |
1372 | // Approximate at what position the set of ranges will change next. |
1373 | // Used to avoid scanning for updates even if none are present. |
1374 | LifetimePosition next_active_ranges_change_; |
1375 | LifetimePosition next_inactive_ranges_change_; |
1376 | |
1377 | #ifdef DEBUG |
1378 | LifetimePosition allocation_finger_; |
1379 | #endif |
1380 | |
1381 | DISALLOW_COPY_AND_ASSIGN(LinearScanAllocator); |
1382 | }; |
1383 | |
1384 | class SpillSlotLocator final : public ZoneObject { |
1385 | public: |
1386 | explicit SpillSlotLocator(RegisterAllocationData* data); |
1387 | |
1388 | void LocateSpillSlots(); |
1389 | |
1390 | private: |
1391 | RegisterAllocationData* data() const { return data_; } |
1392 | |
1393 | RegisterAllocationData* const data_; |
1394 | |
1395 | DISALLOW_COPY_AND_ASSIGN(SpillSlotLocator); |
1396 | }; |
1397 | |
1398 | class OperandAssigner final : public ZoneObject { |
1399 | public: |
1400 | explicit OperandAssigner(RegisterAllocationData* data); |
1401 | |
1402 | // Phase 5: final decision on spilling mode. |
1403 | void DecideSpillingMode(); |
1404 | |
1405 | // Phase 6: assign spill splots. |
1406 | void AssignSpillSlots(); |
1407 | |
1408 | // Phase 7: commit assignment. |
1409 | void CommitAssignment(); |
1410 | |
1411 | private: |
1412 | RegisterAllocationData* data() const { return data_; } |
1413 | |
1414 | RegisterAllocationData* const data_; |
1415 | |
1416 | DISALLOW_COPY_AND_ASSIGN(OperandAssigner); |
1417 | }; |
1418 | |
1419 | class ReferenceMapPopulator final : public ZoneObject { |
1420 | public: |
1421 | explicit ReferenceMapPopulator(RegisterAllocationData* data); |
1422 | |
1423 | // Phase 8: compute values for pointer maps. |
1424 | void PopulateReferenceMaps(); |
1425 | |
1426 | private: |
1427 | RegisterAllocationData* data() const { return data_; } |
1428 | |
1429 | bool SafePointsAreInOrder() const; |
1430 | |
1431 | RegisterAllocationData* const data_; |
1432 | |
1433 | DISALLOW_COPY_AND_ASSIGN(ReferenceMapPopulator); |
1434 | }; |
1435 | |
1436 | class LiveRangeBoundArray; |
1437 | // Insert moves of the form |
1438 | // |
1439 | // Operand(child_(k+1)) = Operand(child_k) |
1440 | // |
1441 | // where child_k and child_(k+1) are consecutive children of a range (so |
1442 | // child_k->next() == child_(k+1)), and Operand(...) refers to the |
1443 | // assigned operand, be it a register or a slot. |
1444 | class LiveRangeConnector final : public ZoneObject { |
1445 | public: |
1446 | explicit LiveRangeConnector(RegisterAllocationData* data); |
1447 | |
1448 | // Phase 9: reconnect split ranges with moves, when the control flow |
1449 | // between the ranges is trivial (no branches). |
1450 | void ConnectRanges(Zone* local_zone); |
1451 | |
1452 | // Phase 10: insert moves to connect ranges across basic blocks, when the |
1453 | // control flow between them cannot be trivially resolved, such as joining |
1454 | // branches. |
1455 | void ResolveControlFlow(Zone* local_zone); |
1456 | |
1457 | private: |
1458 | RegisterAllocationData* data() const { return data_; } |
1459 | InstructionSequence* code() const { return data()->code(); } |
1460 | Zone* code_zone() const { return code()->zone(); } |
1461 | |
1462 | bool CanEagerlyResolveControlFlow(const InstructionBlock* block) const; |
1463 | |
1464 | int ResolveControlFlow(const InstructionBlock* block, |
1465 | const InstructionOperand& cur_op, |
1466 | const InstructionBlock* pred, |
1467 | const InstructionOperand& pred_op); |
1468 | |
1469 | void CommitSpillsInDeferredBlocks(TopLevelLiveRange* range, |
1470 | LiveRangeBoundArray* array, |
1471 | Zone* temp_zone); |
1472 | |
1473 | RegisterAllocationData* const data_; |
1474 | |
1475 | DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector); |
1476 | }; |
1477 | |
1478 | } // namespace compiler |
1479 | } // namespace internal |
1480 | } // namespace v8 |
1481 | |
1482 | #endif // V8_COMPILER_BACKEND_REGISTER_ALLOCATOR_H_ |
1483 | |