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.
5 #ifndef V8_LITHIUM_ALLOCATOR_H_
6 #define V8_LITHIUM_ALLOCATOR_H_
10 #include "src/allocation.h"
11 #include "src/lithium.h"
17 // Forward declarations.
34 // This class represents a single point of a LOperand's lifetime.
35 // For each lithium instruction there are exactly two lifetime positions:
36 // the beginning and the end of the instruction. Lifetime positions for
37 // different lithium instructions are disjoint.
38 class LifetimePosition {
40 // Return the lifetime position that corresponds to the beginning of
41 // the instruction with the given index.
42 static LifetimePosition FromInstructionIndex(int index) {
43 return LifetimePosition(index * kStep);
46 // Returns a numeric representation of this lifetime position.
51 // Returns the index of the instruction to which this lifetime position
53 int InstructionIndex() const {
55 return value_ / kStep;
58 // Returns true if this lifetime position corresponds to the instruction
60 bool IsInstructionStart() const {
61 return (value_ & (kStep - 1)) == 0;
64 // Returns the lifetime position for the start of the instruction which
65 // corresponds to this lifetime position.
66 LifetimePosition InstructionStart() const {
68 return LifetimePosition(value_ & ~(kStep - 1));
71 // Returns the lifetime position for the end of the instruction which
72 // corresponds to this lifetime position.
73 LifetimePosition InstructionEnd() const {
75 return LifetimePosition(InstructionStart().Value() + kStep/2);
78 // Returns the lifetime position for the beginning of the next instruction.
79 LifetimePosition NextInstruction() const {
81 return LifetimePosition(InstructionStart().Value() + kStep);
84 // Returns the lifetime position for the beginning of the previous
86 LifetimePosition PrevInstruction() const {
89 return LifetimePosition(InstructionStart().Value() - kStep);
92 // Constructs the lifetime position which does not correspond to any
94 LifetimePosition() : value_(-1) {}
96 // Returns true if this lifetime positions corrensponds to some
98 bool IsValid() const { return value_ != -1; }
100 static inline LifetimePosition Invalid() { return LifetimePosition(); }
102 static inline LifetimePosition MaxPosition() {
103 // We have to use this kind of getter instead of static member due to
105 return LifetimePosition(kMaxInt);
109 static const int kStep = 2;
111 // Code relies on kStep being a power of two.
112 STATIC_ASSERT(IS_POWER_OF_TWO(kStep));
114 explicit LifetimePosition(int value) : value_(value) { }
120 // Representation of the non-empty interval [start,end[.
121 class UseInterval: public ZoneObject {
123 UseInterval(LifetimePosition start, LifetimePosition end)
124 : start_(start), end_(end), next_(NULL) {
125 DCHECK(start.Value() < end.Value());
128 LifetimePosition start() const { return start_; }
129 LifetimePosition end() const { return end_; }
130 UseInterval* next() const { return next_; }
132 // Split this interval at the given position without effecting the
133 // live range that owns it. The interval must contain the position.
134 void SplitAt(LifetimePosition pos, Zone* zone);
136 // If this interval intersects with other return smallest position
137 // that belongs to both of them.
138 LifetimePosition Intersect(const UseInterval* other) const {
139 if (other->start().Value() < start_.Value()) return other->Intersect(this);
140 if (other->start().Value() < end_.Value()) return other->start();
141 return LifetimePosition::Invalid();
144 bool Contains(LifetimePosition point) const {
145 return start_.Value() <= point.Value() && point.Value() < end_.Value();
149 void set_start(LifetimePosition start) { start_ = start; }
150 void set_next(UseInterval* next) { next_ = next; }
152 LifetimePosition start_;
153 LifetimePosition end_;
156 friend class LiveRange; // Assigns to start_.
159 // Representation of a use position.
160 class UsePosition: public ZoneObject {
162 UsePosition(LifetimePosition pos, LOperand* operand, LOperand* hint);
164 LOperand* operand() const { return operand_; }
165 bool HasOperand() const { return operand_ != NULL; }
167 LOperand* hint() const { return hint_; }
168 bool HasHint() const;
169 bool RequiresRegister() const;
170 bool RegisterIsBeneficial() const;
172 LifetimePosition pos() const { return pos_; }
173 UsePosition* next() const { return next_; }
176 void set_next(UsePosition* next) { next_ = next; }
178 LOperand* const operand_;
179 LOperand* const hint_;
180 LifetimePosition const pos_;
183 bool register_beneficial_;
185 friend class LiveRange;
188 // Representation of SSA values' live ranges as a collection of (continuous)
189 // intervals over the instruction ordering.
190 class LiveRange: public ZoneObject {
192 static const int kInvalidAssignment = 0x7fffffff;
194 LiveRange(int id, Zone* zone);
196 UseInterval* first_interval() const { return first_interval_; }
197 UsePosition* first_pos() const { return first_pos_; }
198 LiveRange* parent() const { return parent_; }
199 LiveRange* TopLevel() { return (parent_ == NULL) ? this : parent_; }
200 LiveRange* next() const { return next_; }
201 bool IsChild() const { return parent() != NULL; }
202 int id() const { return id_; }
203 bool IsFixed() const { return id_ < 0; }
204 bool IsEmpty() const { return first_interval() == NULL; }
205 LOperand* CreateAssignedOperand(Zone* zone);
206 int assigned_register() const { return assigned_register_; }
207 int spill_start_index() const { return spill_start_index_; }
208 void set_assigned_register(int reg, Zone* zone);
209 void MakeSpilled(Zone* zone);
211 // Returns use position in this live range that follows both start
212 // and last processed use position.
213 // Modifies internal state of live range!
214 UsePosition* NextUsePosition(LifetimePosition start);
216 // Returns use position for which register is required in this live
217 // range and which follows both start and last processed use position
218 // Modifies internal state of live range!
219 UsePosition* NextRegisterPosition(LifetimePosition start);
221 // Returns use position for which register is beneficial in this live
222 // range and which follows both start and last processed use position
223 // Modifies internal state of live range!
224 UsePosition* NextUsePositionRegisterIsBeneficial(LifetimePosition start);
226 // Returns use position for which register is beneficial in this live
227 // range and which precedes start.
228 UsePosition* PreviousUsePositionRegisterIsBeneficial(LifetimePosition start);
230 // Can this live range be spilled at this position.
231 bool CanBeSpilled(LifetimePosition pos);
233 // Split this live range at the given position which must follow the start of
235 // All uses following the given position will be moved from this
236 // live range to the result live range.
237 void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone);
239 RegisterKind Kind() const { return kind_; }
240 bool HasRegisterAssigned() const {
241 return assigned_register_ != kInvalidAssignment;
243 bool IsSpilled() const { return spilled_; }
245 LOperand* current_hint_operand() const {
246 DCHECK(current_hint_operand_ == FirstHint());
247 return current_hint_operand_;
249 LOperand* FirstHint() const {
250 UsePosition* pos = first_pos_;
251 while (pos != NULL && !pos->HasHint()) pos = pos->next();
252 if (pos != NULL) return pos->hint();
256 LifetimePosition Start() const {
258 return first_interval()->start();
261 LifetimePosition End() const {
263 return last_interval_->end();
266 bool HasAllocatedSpillOperand() const;
267 LOperand* GetSpillOperand() const { return spill_operand_; }
268 void SetSpillOperand(LOperand* operand);
270 void SetSpillStartIndex(int start) {
271 spill_start_index_ = Min(start, spill_start_index_);
274 bool ShouldBeAllocatedBefore(const LiveRange* other) const;
275 bool CanCover(LifetimePosition position) const;
276 bool Covers(LifetimePosition position);
277 LifetimePosition FirstIntersection(LiveRange* other);
279 // Add a new interval or a new use position to this live range.
280 void EnsureInterval(LifetimePosition start,
281 LifetimePosition end,
283 void AddUseInterval(LifetimePosition start,
284 LifetimePosition end,
286 void AddUsePosition(LifetimePosition pos,
291 // Shorten the most recently added interval by setting a new start.
292 void ShortenTo(LifetimePosition start);
295 // True if target overlaps an existing interval.
296 bool HasOverlap(UseInterval* target) const;
301 void ConvertOperands(Zone* zone);
302 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const;
303 void AdvanceLastProcessedMarker(UseInterval* to_start_of,
304 LifetimePosition but_not_past) const;
309 int assigned_register_;
310 UseInterval* last_interval_;
311 UseInterval* first_interval_;
312 UsePosition* first_pos_;
315 // This is used as a cache, it doesn't affect correctness.
316 mutable UseInterval* current_interval_;
317 UsePosition* last_processed_use_;
318 // This is used as a cache, it's invalid outside of BuildLiveRanges.
319 LOperand* current_hint_operand_;
320 LOperand* spill_operand_;
321 int spill_start_index_;
323 friend class LAllocator; // Assigns to kind_.
327 class LAllocator BASE_EMBEDDED {
329 LAllocator(int first_virtual_register, HGraph* graph);
331 static void TraceAlloc(const char* msg, ...);
333 // Checks whether the value of a given virtual register is tagged.
334 bool HasTaggedValue(int virtual_register) const;
336 // Returns the register kind required by the given virtual register.
337 RegisterKind RequiredRegisterKind(int virtual_register) const;
339 bool Allocate(LChunk* chunk);
341 const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; }
342 const Vector<LiveRange*>* fixed_live_ranges() const {
343 return &fixed_live_ranges_;
345 const Vector<LiveRange*>* fixed_double_live_ranges() const {
346 return &fixed_double_live_ranges_;
349 LPlatformChunk* chunk() const { return chunk_; }
350 HGraph* graph() const { return graph_; }
351 Isolate* isolate() const { return graph_->isolate(); }
352 Zone* zone() { return &zone_; }
354 int GetVirtualRegister() {
355 if (next_virtual_register_ >= LUnallocated::kMaxVirtualRegisters) {
356 allocation_ok_ = false;
357 // Maintain the invariant that we return something below the maximum.
360 return next_virtual_register_++;
363 bool AllocationOk() { return allocation_ok_; }
365 void MarkAsOsrEntry() {
366 // There can be only one.
367 DCHECK(!has_osr_entry_);
368 // Simply set a flag to find and process instruction later.
369 has_osr_entry_ = true;
376 BitVector* assigned_registers() {
377 return assigned_registers_;
379 BitVector* assigned_double_registers() {
380 return assigned_double_registers_;
384 void MeetRegisterConstraints();
386 void BuildLiveRanges();
387 void AllocateGeneralRegisters();
388 void AllocateDoubleRegisters();
389 void ConnectRanges();
390 void ResolveControlFlow();
391 void PopulatePointerMaps();
392 void AllocateRegisters();
393 bool CanEagerlyResolveControlFlow(HBasicBlock* block) const;
394 inline bool SafePointsAreInOrder() const;
396 // Liveness analysis support.
397 void InitializeLivenessAnalysis();
398 BitVector* ComputeLiveOut(HBasicBlock* block);
399 void AddInitialIntervals(HBasicBlock* block, BitVector* live_out);
400 void ProcessInstructions(HBasicBlock* block, BitVector* live);
401 void MeetRegisterConstraints(HBasicBlock* block);
402 void MeetConstraintsBetween(LInstruction* first,
403 LInstruction* second,
405 void ResolvePhis(HBasicBlock* block);
407 // Helper methods for building intervals.
408 LOperand* AllocateFixed(LUnallocated* operand, int pos, bool is_tagged);
409 LiveRange* LiveRangeFor(LOperand* operand);
410 void Define(LifetimePosition position, LOperand* operand, LOperand* hint);
411 void Use(LifetimePosition block_start,
412 LifetimePosition position,
415 void AddConstraintsGapMove(int index, LOperand* from, LOperand* to);
417 // Helper methods for updating the life range lists.
418 void AddToActive(LiveRange* range);
419 void AddToInactive(LiveRange* range);
420 void AddToUnhandledSorted(LiveRange* range);
421 void AddToUnhandledUnsorted(LiveRange* range);
422 void SortUnhandled();
423 bool UnhandledIsSorted();
424 void ActiveToHandled(LiveRange* range);
425 void ActiveToInactive(LiveRange* range);
426 void InactiveToHandled(LiveRange* range);
427 void InactiveToActive(LiveRange* range);
428 void FreeSpillSlot(LiveRange* range);
429 LOperand* TryReuseSpillSlot(LiveRange* range);
431 // Helper methods for allocating registers.
432 bool TryAllocateFreeReg(LiveRange* range);
433 void AllocateBlockedReg(LiveRange* range);
435 // Live range splitting helpers.
437 // Split the given range at the given position.
438 // If range starts at or after the given position then the
439 // original range is returned.
440 // Otherwise returns the live range that starts at pos and contains
441 // all uses from the original range that follow pos. Uses at pos will
442 // still be owned by the original range after splitting.
443 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos);
445 // Split the given range in a position from the interval [start, end].
446 LiveRange* SplitBetween(LiveRange* range,
447 LifetimePosition start,
448 LifetimePosition end);
450 // Find a lifetime position in the interval [start, end] which
451 // is optimal for splitting: it is either header of the outermost
452 // loop covered by this interval or the latest possible position.
453 LifetimePosition FindOptimalSplitPos(LifetimePosition start,
454 LifetimePosition end);
456 // Spill the given life range after position pos.
457 void SpillAfter(LiveRange* range, LifetimePosition pos);
459 // Spill the given life range after position [start] and up to position [end].
460 void SpillBetween(LiveRange* range,
461 LifetimePosition start,
462 LifetimePosition end);
464 // Spill the given life range after position [start] and up to position [end].
465 // Range is guaranteed to be spilled at least until position [until].
466 void SpillBetweenUntil(LiveRange* range,
467 LifetimePosition start,
468 LifetimePosition until,
469 LifetimePosition end);
471 void SplitAndSpillIntersecting(LiveRange* range);
473 // If we are trying to spill a range inside the loop try to
474 // hoist spill position out to the point just before the loop.
475 LifetimePosition FindOptimalSpillingPos(LiveRange* range,
476 LifetimePosition pos);
478 void Spill(LiveRange* range);
479 bool IsBlockBoundary(LifetimePosition pos);
481 // Helper methods for resolving control flow.
482 void ResolveControlFlow(LiveRange* range,
486 inline void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
488 // Return parallel move that should be used to connect ranges split at the
490 LParallelMove* GetConnectingParallelMove(LifetimePosition pos);
492 // Return the block which contains give lifetime position.
493 HBasicBlock* GetBlock(LifetimePosition pos);
495 // Helper methods for the fixed registers.
496 int RegisterCount() const;
497 static int FixedLiveRangeID(int index) { return -index - 1; }
498 static int FixedDoubleLiveRangeID(int index);
499 LiveRange* FixedLiveRangeFor(int index);
500 LiveRange* FixedDoubleLiveRangeFor(int index);
501 LiveRange* LiveRangeFor(int index);
502 HPhi* LookupPhi(LOperand* operand) const;
503 LGap* GetLastGap(HBasicBlock* block);
505 const char* RegisterName(int allocation_index);
507 inline bool IsGapAt(int index);
509 inline LInstruction* InstructionAt(int index);
511 inline LGap* GapAt(int index);
515 LPlatformChunk* chunk_;
517 // During liveness analysis keep a mapping from block id to live_in sets
518 // for blocks already analyzed.
519 ZoneList<BitVector*> live_in_sets_;
521 // Liveness analysis results.
522 ZoneList<LiveRange*> live_ranges_;
524 // Lists of live ranges
525 EmbeddedVector<LiveRange*, Register::kMaxNumAllocatableRegisters>
527 EmbeddedVector<LiveRange*, DoubleRegister::kMaxNumAllocatableRegisters>
528 fixed_double_live_ranges_;
529 ZoneList<LiveRange*> unhandled_live_ranges_;
530 ZoneList<LiveRange*> active_live_ranges_;
531 ZoneList<LiveRange*> inactive_live_ranges_;
532 ZoneList<LiveRange*> reusable_slots_;
534 // Next virtual register number to be assigned to temporaries.
535 int next_virtual_register_;
536 int first_artificial_register_;
537 GrowableBitVector double_artificial_registers_;
542 BitVector* assigned_registers_;
543 BitVector* assigned_double_registers_;
549 // Indicates success or failure during register allocation.
553 LifetimePosition allocation_finger_;
556 DISALLOW_COPY_AND_ASSIGN(LAllocator);
560 class LAllocatorPhase : public CompilationPhase {
562 LAllocatorPhase(const char* name, LAllocator* allocator);
566 LAllocator* allocator_;
567 unsigned allocator_zone_start_allocation_size_;
569 DISALLOW_COPY_AND_ASSIGN(LAllocatorPhase);
573 } } // namespace v8::internal
575 #endif // V8_LITHIUM_ALLOCATOR_H_