More aggressive reuse of spill slots in the register allocator.

src/lithium-allocator.h

Index: src/lithium-allocator.h
diff --git a/src/lithium-allocator.h b/src/lithium-allocator.h
index 1d313a5a54825e890981cd0ddab90317fb2d37a4..194362d666f86417793669ac68bfc83be4dcc884 100644
--- a/src/lithium-allocator.h
+++ b/src/lithium-allocator.h
@@ -212,6 +212,8 @@ class UseInterval: public ZoneObject {
   LifetimePosition end_;
   UseInterval* next_;
 
+  friend class LAllocator;  // Assigns to next_.
+  friend class SpillRange;  // Assigns to next_.
   friend class LiveRange;  // Assigns to start_.
 };
 
@@ -326,6 +328,10 @@ class LiveRange: public ZoneObject {
   LOperand* GetSpillOperand() const { return spill_operand_; }
   void SetSpillOperand(LOperand* operand);
 
+  void SetSpillRangeId(int spill_index) { spill_range_id_ = spill_index; }
+  int GetSpillRangeId() { return spill_range_id_; }
+  void CommitSpillOperand(LOperand* operand);
+
   void SetSpillStartIndex(int start) {
     spill_start_index_ = Min(start, spill_start_index_);
   }
@@ -358,6 +364,7 @@ class LiveRange: public ZoneObject {
 
  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;
@@ -378,11 +385,37 @@ class LiveRange: public ZoneObject {
   LOperand* current_hint_operand_;
   LOperand* spill_operand_;
   int spill_start_index_;
+  int spill_range_id_;

[titzer, 2014/06/17 09:01:34]

Why not a direct pointer to the SpillRange?

[Jarin, 2014/06/24 21:49:58]

Done.

 
   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(); }
+
+  static const int INVALID_ID = -1;
+
+ private:
+  int id_;
+  ZoneList<LiveRange*> live_ranges_;
+  UseInterval* use_interval_;
+
+  static void Swap(UseInterval*& a, UseInterval*& b);
+
+  // 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);
@@ -449,6 +482,7 @@ class LAllocator BASE_EMBEDDED {
   void ResolveControlFlow();
   void PopulatePointerMaps();
   void AllocateRegisters();
+  void ReuseSpillSlots();
   bool CanEagerlyResolveControlFlow(HBasicBlock* block) const;
   inline bool SafePointsAreInOrder() const;
 
@@ -484,12 +518,12 @@ class LAllocator BASE_EMBEDDED {
   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.
 
@@ -589,6 +623,7 @@ class LAllocator BASE_EMBEDDED {
   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_;