| // Copyright 2012 the V8 project authors. All rights reserved. |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions are |
| // met: |
| // |
| // * Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // * Redistributions in binary form must reproduce the above |
| // copyright notice, this list of conditions and the following |
| // disclaimer in the documentation and/or other materials provided |
| // with the distribution. |
| // * Neither the name of Google Inc. nor the names of its |
| // contributors may be used to endorse or promote products derived |
| // from this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| #ifndef V8_LITHIUM_ALLOCATOR_H_ |
| #define V8_LITHIUM_ALLOCATOR_H_ |
| |
| #include "v8.h" |
| |
| #include "allocation.h" |
| #include "lithium.h" |
| #include "zone.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| // Forward declarations. |
| class HBasicBlock; |
| class HGraph; |
| class HInstruction; |
| class HPhi; |
| class HTracer; |
| class HValue; |
| class BitVector; |
| class StringStream; |
| |
| class LArgument; |
| class LPlatformChunk; |
| class LOperand; |
| class LUnallocated; |
| class LConstantOperand; |
| class LGap; |
| class LParallelMove; |
| class LPointerMap; |
| class LStackSlot; |
| class LRegister; |
| |
| |
| // This class represents a single point of a LOperand's lifetime. |
| // For each lithium instruction there are exactly two lifetime positions: |
| // the beginning and the end of the instruction. Lifetime positions for |
| // different lithium instructions are disjoint. |
| class LifetimePosition { |
| public: |
| // Return the lifetime position that corresponds to the beginning of |
| // the instruction with the given index. |
| static LifetimePosition FromInstructionIndex(int index) { |
| return LifetimePosition(index * kStep); |
| } |
| |
| // Returns a numeric representation of this lifetime position. |
| int Value() const { |
| return value_; |
| } |
| |
| // Returns the index of the instruction to which this lifetime position |
| // corresponds. |
| int InstructionIndex() const { |
| ASSERT(IsValid()); |
| return value_ / kStep; |
| } |
| |
| // Returns true if this lifetime position corresponds to the instruction |
| // start. |
| bool IsInstructionStart() const { |
| return (value_ & (kStep - 1)) == 0; |
| } |
| |
| // Returns the lifetime position for the start of the instruction which |
| // corresponds to this lifetime position. |
| LifetimePosition InstructionStart() const { |
| ASSERT(IsValid()); |
| return LifetimePosition(value_ & ~(kStep - 1)); |
| } |
| |
| // Returns the lifetime position for the end of the instruction which |
| // corresponds to this lifetime position. |
| LifetimePosition InstructionEnd() const { |
| ASSERT(IsValid()); |
| return LifetimePosition(InstructionStart().Value() + kStep/2); |
| } |
| |
| // Returns the lifetime position for the beginning of the next instruction. |
| LifetimePosition NextInstruction() const { |
| ASSERT(IsValid()); |
| return LifetimePosition(InstructionStart().Value() + kStep); |
| } |
| |
| // Returns the lifetime position for the beginning of the previous |
| // instruction. |
| LifetimePosition PrevInstruction() const { |
| ASSERT(IsValid()); |
| ASSERT(value_ > 1); |
| return LifetimePosition(InstructionStart().Value() - kStep); |
| } |
| |
| // Constructs the lifetime position which does not correspond to any |
| // instruction. |
| LifetimePosition() : value_(-1) {} |
| |
| // Returns true if this lifetime positions corrensponds to some |
| // instruction. |
| bool IsValid() const { return value_ != -1; } |
| |
| static inline LifetimePosition Invalid() { return LifetimePosition(); } |
| |
| static inline LifetimePosition MaxPosition() { |
| // We have to use this kind of getter instead of static member due to |
| // crash bug in GDB. |
| return LifetimePosition(kMaxInt); |
| } |
| |
| private: |
| static const int kStep = 2; |
| |
| // Code relies on kStep being a power of two. |
| STATIC_ASSERT(IS_POWER_OF_TWO(kStep)); |
| |
| explicit LifetimePosition(int value) : value_(value) { } |
| |
| int value_; |
| }; |
| |
| |
| enum RegisterKind { |
| GENERAL_REGISTERS, |
| DOUBLE_REGISTERS |
| }; |
| |
| |
| // A register-allocator view of a Lithium instruction. It contains the id of |
| // the output operand and a list of input operand uses. |
| |
| class LInstruction; |
| class LEnvironment; |
| |
| // Iterator for non-null temp operands. |
| class TempIterator BASE_EMBEDDED { |
| public: |
| inline explicit TempIterator(LInstruction* instr); |
| inline bool Done(); |
| inline LOperand* Current(); |
| inline void Advance(); |
| |
| private: |
| inline void SkipUninteresting(); |
| LInstruction* instr_; |
| int limit_; |
| int current_; |
| }; |
| |
| |
| // Iterator for non-constant input operands. |
| class InputIterator BASE_EMBEDDED { |
| public: |
| inline explicit InputIterator(LInstruction* instr); |
| inline bool Done(); |
| inline LOperand* Current(); |
| inline void Advance(); |
| |
| private: |
| inline void SkipUninteresting(); |
| LInstruction* instr_; |
| int limit_; |
| int current_; |
| }; |
| |
| |
| class UseIterator BASE_EMBEDDED { |
| public: |
| inline explicit UseIterator(LInstruction* instr); |
| inline bool Done(); |
| inline LOperand* Current(); |
| inline void Advance(); |
| |
| private: |
| InputIterator input_iterator_; |
| DeepIterator env_iterator_; |
| }; |
| |
| |
| // Representation of the non-empty interval [start,end[. |
| class UseInterval: public ZoneObject { |
| public: |
| UseInterval(LifetimePosition start, LifetimePosition end) |
| : start_(start), end_(end), next_(NULL) { |
| ASSERT(start.Value() < end.Value()); |
| } |
| |
| LifetimePosition start() const { return start_; } |
| LifetimePosition end() const { return end_; } |
| UseInterval* next() const { return next_; } |
| |
| // Split this interval at the given position without effecting the |
| // live range that owns it. The interval must contain the position. |
| void SplitAt(LifetimePosition pos, Zone* zone); |
| |
| // If this interval intersects with other return smallest position |
| // that belongs to both of them. |
| LifetimePosition Intersect(const UseInterval* other) const { |
| if (other->start().Value() < start_.Value()) return other->Intersect(this); |
| if (other->start().Value() < end_.Value()) return other->start(); |
| return LifetimePosition::Invalid(); |
| } |
| |
| bool Contains(LifetimePosition point) const { |
| return start_.Value() <= point.Value() && point.Value() < end_.Value(); |
| } |
| |
| private: |
| void set_start(LifetimePosition start) { start_ = start; } |
| void set_next(UseInterval* next) { next_ = next; } |
| |
| LifetimePosition start_; |
| LifetimePosition end_; |
| UseInterval* next_; |
| |
| friend class LiveRange; // Assigns to start_. |
| }; |
| |
| // Representation of a use position. |
| class UsePosition: public ZoneObject { |
| public: |
| UsePosition(LifetimePosition pos, LOperand* operand); |
| |
| LOperand* operand() const { return operand_; } |
| bool HasOperand() const { return operand_ != NULL; } |
| |
| LOperand* hint() const { return hint_; } |
| void set_hint(LOperand* hint) { hint_ = hint; } |
| bool HasHint() const; |
| bool RequiresRegister() const; |
| bool RegisterIsBeneficial() const; |
| |
| LifetimePosition pos() const { return pos_; } |
| UsePosition* next() const { return next_; } |
| |
| private: |
| void set_next(UsePosition* next) { next_ = next; } |
| |
| LOperand* operand_; |
| LOperand* hint_; |
| LifetimePosition pos_; |
| UsePosition* next_; |
| bool requires_reg_; |
| bool register_beneficial_; |
| |
| friend class LiveRange; |
| }; |
| |
| // Representation of SSA values' live ranges as a collection of (continuous) |
| // intervals over the instruction ordering. |
| class LiveRange: public ZoneObject { |
| public: |
| static const int kInvalidAssignment = 0x7fffffff; |
| |
| LiveRange(int id, Zone* zone); |
| |
| UseInterval* first_interval() const { return first_interval_; } |
| UsePosition* first_pos() const { return first_pos_; } |
| LiveRange* parent() const { return parent_; } |
| LiveRange* TopLevel() { return (parent_ == NULL) ? this : parent_; } |
| LiveRange* next() const { return next_; } |
| bool IsChild() const { return parent() != NULL; } |
| int id() const { return id_; } |
| bool IsFixed() const { return id_ < 0; } |
| bool IsEmpty() const { return first_interval() == NULL; } |
| LOperand* CreateAssignedOperand(Zone* zone); |
| int assigned_register() const { return assigned_register_; } |
| int spill_start_index() const { return spill_start_index_; } |
| void set_assigned_register(int reg, |
| RegisterKind register_kind, |
| Zone* zone); |
| void MakeSpilled(Zone* zone); |
| |
| // Returns use position in this live range that follows both start |
| // and last processed use position. |
| // Modifies internal state of live range! |
| UsePosition* NextUsePosition(LifetimePosition start); |
| |
| // Returns use position for which register is required in this live |
| // range and which follows both start and last processed use position |
| // Modifies internal state of live range! |
| UsePosition* NextRegisterPosition(LifetimePosition start); |
| |
| // Returns use position for which register is beneficial in this live |
| // range and which follows both start and last processed use position |
| // Modifies internal state of live range! |
| UsePosition* NextUsePositionRegisterIsBeneficial(LifetimePosition start); |
| |
| // Can this live range be spilled at this position. |
| bool CanBeSpilled(LifetimePosition pos); |
| |
| // Split this live range at the given position which must follow the start of |
| // the range. |
| // All uses following the given position will be moved from this |
| // live range to the result live range. |
| void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone); |
| |
| bool IsDouble() const { return is_double_; } |
| bool HasRegisterAssigned() const { |
| return assigned_register_ != kInvalidAssignment; |
| } |
| bool IsSpilled() const { return spilled_; } |
| UsePosition* FirstPosWithHint() const; |
| |
| LOperand* FirstHint() const { |
| UsePosition* pos = FirstPosWithHint(); |
| if (pos != NULL) return pos->hint(); |
| return NULL; |
| } |
| |
| LifetimePosition Start() const { |
| ASSERT(!IsEmpty()); |
| return first_interval()->start(); |
| } |
| |
| LifetimePosition End() const { |
| ASSERT(!IsEmpty()); |
| return last_interval_->end(); |
| } |
| |
| bool HasAllocatedSpillOperand() const; |
| LOperand* GetSpillOperand() const { return spill_operand_; } |
| void SetSpillOperand(LOperand* operand); |
| |
| void SetSpillStartIndex(int start) { |
| spill_start_index_ = Min(start, spill_start_index_); |
| } |
| |
| bool ShouldBeAllocatedBefore(const LiveRange* other) const; |
| bool CanCover(LifetimePosition position) const; |
| bool Covers(LifetimePosition position); |
| LifetimePosition FirstIntersection(LiveRange* other); |
| |
| // Add a new interval or a new use position to this live range. |
| void EnsureInterval(LifetimePosition start, |
| LifetimePosition end, |
| Zone* zone); |
| void AddUseInterval(LifetimePosition start, |
| LifetimePosition end, |
| Zone* zone); |
| UsePosition* AddUsePosition(LifetimePosition pos, |
| LOperand* operand, |
| Zone* zone); |
| |
| // Shorten the most recently added interval by setting a new start. |
| void ShortenTo(LifetimePosition start); |
| |
| #ifdef DEBUG |
| // True if target overlaps an existing interval. |
| bool HasOverlap(UseInterval* target) const; |
| void Verify() const; |
| #endif |
| |
| private: |
| void ConvertOperands(Zone* zone); |
| UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; |
| void AdvanceLastProcessedMarker(UseInterval* to_start_of, |
| LifetimePosition but_not_past) const; |
| |
| int id_; |
| bool spilled_; |
| bool is_double_; |
| int assigned_register_; |
| UseInterval* last_interval_; |
| UseInterval* first_interval_; |
| UsePosition* first_pos_; |
| LiveRange* parent_; |
| LiveRange* next_; |
| // This is used as a cache, it doesn't affect correctness. |
| mutable UseInterval* current_interval_; |
| UsePosition* last_processed_use_; |
| LOperand* spill_operand_; |
| int spill_start_index_; |
| }; |
| |
| |
| class LAllocator BASE_EMBEDDED { |
| public: |
| LAllocator(int first_virtual_register, HGraph* graph); |
| |
| static void TraceAlloc(const char* msg, ...); |
| |
| // Checks whether the value of a given virtual register is tagged. |
| bool HasTaggedValue(int virtual_register) const; |
| |
| // Returns the register kind required by the given virtual register. |
| RegisterKind RequiredRegisterKind(int virtual_register) const; |
| |
| bool Allocate(LChunk* chunk); |
| |
| const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; } |
| const Vector<LiveRange*>* fixed_live_ranges() const { |
| return &fixed_live_ranges_; |
| } |
| const Vector<LiveRange*>* fixed_double_live_ranges() const { |
| return &fixed_double_live_ranges_; |
| } |
| |
| LPlatformChunk* chunk() const { return chunk_; } |
| HGraph* graph() const { return graph_; } |
| Zone* zone() const { return zone_; } |
| |
| int GetVirtualRegister() { |
| if (next_virtual_register_ > LUnallocated::kMaxVirtualRegisters) { |
| allocation_ok_ = false; |
| } |
| return next_virtual_register_++; |
| } |
| |
| bool AllocationOk() { return allocation_ok_; } |
| |
| void MarkAsOsrEntry() { |
| // There can be only one. |
| ASSERT(!has_osr_entry_); |
| // Simply set a flag to find and process instruction later. |
| has_osr_entry_ = true; |
| } |
| |
| #ifdef DEBUG |
| void Verify() const; |
| #endif |
| |
| private: |
| void MeetRegisterConstraints(); |
| void ResolvePhis(); |
| void BuildLiveRanges(); |
| void AllocateGeneralRegisters(); |
| void AllocateDoubleRegisters(); |
| void ConnectRanges(); |
| void ResolveControlFlow(); |
| void PopulatePointerMaps(); |
| void ProcessOsrEntry(); |
| void AllocateRegisters(); |
| bool CanEagerlyResolveControlFlow(HBasicBlock* block) const; |
| inline bool SafePointsAreInOrder() const; |
| |
| // Liveness analysis support. |
| void InitializeLivenessAnalysis(); |
| BitVector* ComputeLiveOut(HBasicBlock* block); |
| void AddInitialIntervals(HBasicBlock* block, BitVector* live_out); |
| void ProcessInstructions(HBasicBlock* block, BitVector* live); |
| void MeetRegisterConstraints(HBasicBlock* block); |
| void MeetConstraintsBetween(LInstruction* first, |
| LInstruction* second, |
| int gap_index); |
| void ResolvePhis(HBasicBlock* block); |
| |
| // Helper methods for building intervals. |
| LOperand* AllocateFixed(LUnallocated* operand, int pos, bool is_tagged); |
| LiveRange* LiveRangeFor(LOperand* operand); |
| void Define(LifetimePosition position, LOperand* operand, LOperand* hint); |
| void Use(LifetimePosition block_start, |
| LifetimePosition position, |
| LOperand* operand, |
| LOperand* hint); |
| void AddConstraintsGapMove(int index, LOperand* from, LOperand* to); |
| |
| // Helper methods for updating the life range lists. |
| void AddToActive(LiveRange* range); |
| void AddToInactive(LiveRange* range); |
| void AddToUnhandledSorted(LiveRange* range); |
| void AddToUnhandledUnsorted(LiveRange* range); |
| void SortUnhandled(); |
| bool UnhandledIsSorted(); |
| void ActiveToHandled(LiveRange* range); |
| void ActiveToInactive(LiveRange* range); |
| void InactiveToHandled(LiveRange* range); |
| void InactiveToActive(LiveRange* range); |
| void FreeSpillSlot(LiveRange* range); |
| LOperand* TryReuseSpillSlot(LiveRange* range); |
| |
| // Helper methods for allocating registers. |
| bool TryAllocateFreeReg(LiveRange* range); |
| void AllocateBlockedReg(LiveRange* range); |
| |
| // Live range splitting helpers. |
| |
| // Split the given range at the given position. |
| // If range starts at or after the given position then the |
| // original range is returned. |
| // Otherwise returns the live range that starts at pos and contains |
| // all uses from the original range that follow pos. Uses at pos will |
| // still be owned by the original range after splitting. |
| LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); |
| |
| // Split the given range in a position from the interval [start, end]. |
| LiveRange* SplitBetween(LiveRange* range, |
| LifetimePosition start, |
| LifetimePosition end); |
| |
| // Find a lifetime position in the interval [start, end] which |
| // is optimal for splitting: it is either header of the outermost |
| // loop covered by this interval or the latest possible position. |
| LifetimePosition FindOptimalSplitPos(LifetimePosition start, |
| LifetimePosition end); |
| |
| // Spill the given life range after position pos. |
| void SpillAfter(LiveRange* range, LifetimePosition pos); |
| |
| // Spill the given life range after position start and up to position end. |
| void SpillBetween(LiveRange* range, |
| LifetimePosition start, |
| LifetimePosition end); |
| |
| void SplitAndSpillIntersecting(LiveRange* range); |
| |
| void Spill(LiveRange* range); |
| bool IsBlockBoundary(LifetimePosition pos); |
| |
| // Helper methods for resolving control flow. |
| void ResolveControlFlow(LiveRange* range, |
| HBasicBlock* block, |
| HBasicBlock* pred); |
| |
| // Return parallel move that should be used to connect ranges split at the |
| // given position. |
| LParallelMove* GetConnectingParallelMove(LifetimePosition pos); |
| |
| // Return the block which contains give lifetime position. |
| HBasicBlock* GetBlock(LifetimePosition pos); |
| |
| // Helper methods for the fixed registers. |
| int RegisterCount() const; |
| static int FixedLiveRangeID(int index) { return -index - 1; } |
| static int FixedDoubleLiveRangeID(int index); |
| LiveRange* FixedLiveRangeFor(int index); |
| LiveRange* FixedDoubleLiveRangeFor(int index); |
| LiveRange* LiveRangeFor(int index); |
| HPhi* LookupPhi(LOperand* operand) const; |
| LGap* GetLastGap(HBasicBlock* block); |
| |
| const char* RegisterName(int allocation_index); |
| |
| inline bool IsGapAt(int index); |
| |
| inline LInstruction* InstructionAt(int index); |
| |
| inline LGap* GapAt(int index); |
| |
| Zone* zone_; |
| |
| LPlatformChunk* chunk_; |
| |
| // During liveness analysis keep a mapping from block id to live_in sets |
| // for blocks already analyzed. |
| ZoneList<BitVector*> live_in_sets_; |
| |
| // Liveness analysis results. |
| ZoneList<LiveRange*> live_ranges_; |
| |
| // Lists of live ranges |
| EmbeddedVector<LiveRange*, Register::kMaxNumAllocatableRegisters> |
| fixed_live_ranges_; |
| EmbeddedVector<LiveRange*, DoubleRegister::kMaxNumAllocatableRegisters> |
| fixed_double_live_ranges_; |
| ZoneList<LiveRange*> unhandled_live_ranges_; |
| ZoneList<LiveRange*> active_live_ranges_; |
| ZoneList<LiveRange*> inactive_live_ranges_; |
| ZoneList<LiveRange*> reusable_slots_; |
| |
| // Next virtual register number to be assigned to temporaries. |
| int next_virtual_register_; |
| int first_artificial_register_; |
| GrowableBitVector double_artificial_registers_; |
| |
| RegisterKind mode_; |
| int num_registers_; |
| |
| HGraph* graph_; |
| |
| bool has_osr_entry_; |
| |
| // Indicates success or failure during register allocation. |
| bool allocation_ok_; |
| |
| DISALLOW_COPY_AND_ASSIGN(LAllocator); |
| }; |
| |
| |
| } } // namespace v8::internal |
| |
| #endif // V8_LITHIUM_ALLOCATOR_H_ |