More aggressive reuse of spill slots in the register allocator.

src/lithium-allocator.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_LITHIUM_ALLOCATOR_H_
 #define V8_LITHIUM_ALLOCATOR_H_
 
 #include "src/v8.h"
 
 #include "src/allocation.h"
@@ skipping 135 matching lines @@
   }
 
  private:
   void set_start(LifetimePosition start) { start_ = start; }
   void set_next(UseInterval* next) { next_ = next; }
 
   LifetimePosition start_;
   LifetimePosition end_;
   UseInterval* next_;
 
+  friend class LAllocator;  // Assigns to next_.
+  friend class SpillRange;  // Assigns to next_.
   friend class LiveRange;  // Assigns to start_.
 };
 
 // Representation of a use position.
 class UsePosition: public ZoneObject {
  public:
   UsePosition(LifetimePosition pos, LOperand* operand, LOperand* hint);
 
   LOperand* operand() const { return operand_; }
   bool HasOperand() const { return operand_ != NULL; }
@@ skipping 12 matching lines @@
   LOperand* const operand_;
   LOperand* const hint_;
   LifetimePosition const pos_;
   UsePosition* next_;
   bool requires_reg_;
   bool register_beneficial_;
 
   friend class LiveRange;
 };
 
+class SpillRange;
+
 // 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_; }
@@ skipping 62 matching lines @@
 
   LifetimePosition End() const {
     DCHECK(!IsEmpty());
     return last_interval_->end();
   }
 
   bool HasAllocatedSpillOperand() const;
   LOperand* GetSpillOperand() const { return spill_operand_; }
   void SetSpillOperand(LOperand* operand);
 
+  void SetSpillRange(SpillRange* spill_range) { spill_range_ = spill_range; }
+  SpillRange* GetSpillRange() const { return spill_range_; }
+  void CommitSpillOperand(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.
@@ skipping 12 matching lines @@
   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);
+  void ConvertUsesToOperand(LOperand* op);
   UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const;
   void AdvanceLastProcessedMarker(UseInterval* to_start_of,
                                   LifetimePosition but_not_past) const;
 
   int id_;
   bool spilled_;
   RegisterKind kind_;
   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_;
   // This is used as a cache, it's invalid outside of BuildLiveRanges.
   LOperand* current_hint_operand_;
   LOperand* spill_operand_;
   int spill_start_index_;
+  SpillRange* spill_range_;
 
   friend class LAllocator;  // Assigns to kind_.
 };
 
 
+class SpillRange : public ZoneObject {
+ public:
+  SpillRange(LiveRange* range, int id, Zone* zone);
+
+  bool TryMerge(SpillRange* other, Zone* zone);
+  void SetOperand(LOperand* op);
+  bool IsEmpty() { return live_ranges_.length() == 0; }
+  int id() const { return id_; }
+  UseInterval* interval() { return use_interval_; }
+  RegisterKind Kind() const { return live_ranges_.at(0)->Kind(); }
+  LifetimePosition End() const { return end_position_; }
+  bool IsIntersectingWith(SpillRange* other);
+
+ private:
+  int id_;
+  ZoneList<LiveRange*> live_ranges_;
+  UseInterval* use_interval_;
+  LifetimePosition end_position_;
+
+  // Merge intervals, making sure the use intervals are sorted
+  void MergeDisjointIntervals(UseInterval* other, Zone* zone);
+};
+
+
 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.
@@ skipping 46 matching lines @@
  private:
   void MeetRegisterConstraints();
   void ResolvePhis();
   void BuildLiveRanges();
   void AllocateGeneralRegisters();
   void AllocateDoubleRegisters();
   void ConnectRanges();
   void ResolveControlFlow();
   void PopulatePointerMaps();
   void AllocateRegisters();
+  void ReuseSpillSlots();
   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,
@@ skipping 15 matching lines @@
   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);
+  SpillRange* AssignSpillRangeToLiveRange(LiveRange* range);
 
   // Helper methods for allocating registers.
   bool TryAllocateFreeReg(LiveRange* range);
   void AllocateBlockedReg(LiveRange* range);
+  bool TryReuseSpillForPhi(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);
@@ skipping 79 matching lines @@
 
   // 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_;
+  ZoneList<SpillRange*> spill_ranges_;
 
   // 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_;
 
   BitVector* assigned_registers_;
@@ skipping 23 matching lines @@
   LAllocator* allocator_;
   unsigned allocator_zone_start_allocation_size_;
 
   DISALLOW_COPY_AND_ASSIGN(LAllocatorPhase);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_LITHIUM_ALLOCATOR_H_