[turbofan] More aggressive reuse of spill slots in the register allocator.

src/compiler/register-allocator.h

 // Copyright 2014 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_REGISTER_ALLOCATOR_H_
 #define V8_REGISTER_ALLOCATOR_H_
 
 #include "src/compiler/instruction.h"
 #include "src/zone-containers.h"
 
@@ skipping 153 matching lines @@
   InstructionOperand* const hint_;
   LifetimePosition const pos_;
   UsePosition* next_;
   bool requires_reg_ : 1;
   bool register_beneficial_ : 1;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(UsePosition);
 };
 
+class SpillRange;
 
 // Representation of SSA values' live ranges as a collection of (continuous)
 // intervals over the instruction ordering.
 class LiveRange FINAL : public ZoneObject {
  public:
   static const int kInvalidAssignment = 0x7fffffff;
 
   LiveRange(int id, Zone* zone);
 
   UseInterval* first_interval() const { return first_interval_; }
@@ skipping 66 matching lines @@
 
   LifetimePosition End() const {
     DCHECK(!IsEmpty());
     return last_interval_->end();
   }
 
   bool HasAllocatedSpillOperand() const;
   InstructionOperand* GetSpillOperand() const { return spill_operand_; }
   void SetSpillOperand(InstructionOperand* operand);
 
+  void SetSpillRange(SpillRange* spill_range) { spill_range_ = spill_range; }
+  SpillRange* GetSpillRange() const { return spill_range_; }
+  void CommitSpillOperand(InstructionOperand* 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);
   void AddUsePosition(LifetimePosition pos, InstructionOperand* operand,
                       InstructionOperand* hint, 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);
+  void ConvertUsesToOperand(InstructionOperand* 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.
   InstructionOperand* current_hint_operand_;
   InstructionOperand* spill_operand_;
   int spill_start_index_;
+  SpillRange* spill_range_;
 
   friend class RegisterAllocator;  // Assigns to kind_.
 
   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 };
 
 
+class SpillRange : public ZoneObject {
+ public:
+  SpillRange(LiveRange* range, int id, Zone* zone);
+  bool TryMerge(SpillRange* other, Zone* zone);
+  void SetOperand(InstructionOperand* 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 RegisterAllocator FINAL : public ZoneObject {
  public:
   explicit RegisterAllocator(const RegisterConfiguration* config,
                              Zone* local_zone, Frame* frame,
                              InstructionSequence* code,
                              const char* debug_name = nullptr);
 
   bool AllocationOk() { return allocation_ok_; }
 
   const ZoneList<LiveRange*>& live_ranges() const { return live_ranges_; }
@@ skipping 11 matching lines @@
   void MeetRegisterConstraints();
 
   // Phase 2: compute liveness of all virtual register.
   void BuildLiveRanges();
   bool ExistsUseWithoutDefinition();
 
   // Phase 3: compute register assignments.
   void AllocateGeneralRegisters();
   void AllocateDoubleRegisters();
 
-  // Phase 4: compute values for pointer maps.
+  // Phase 4: reassign spill splots for maximal reuse.
+  void ReuseSpillSlots();
+
+  // Phase 5: compute values for pointer maps.
   void PopulatePointerMaps();  // TODO(titzer): rename to PopulateReferenceMaps.
 
-  // Phase 5: reconnect split ranges with moves.
+  // Phase 6: reconnect split ranges with moves.
   void ConnectRanges();
 
-  // Phase 6: insert moves to connect ranges across basic blocks.
+  // Phase 7: insert moves to connect ranges across basic blocks.
   void ResolveControlFlow();
 
  private:
   int GetVirtualRegister() {
     int vreg = code()->NextVirtualRegister();
     if (vreg >= UnallocatedOperand::kMaxVirtualRegisters) {
       allocation_ok_ = false;
       // Maintain the invariant that we return something below the maximum.
       return 0;
     }
@@ skipping 51 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);
-  InstructionOperand* TryReuseSpillSlot(LiveRange* range);
 
   // Helper methods for allocating registers.
   bool TryAllocateFreeReg(LiveRange* range);
   void AllocateBlockedReg(LiveRange* range);
+  SpillRange* AssignSpillRangeToLiveRange(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 76 matching lines @@
   // Liveness analysis results.
   ZoneList<LiveRange*> live_ranges_;
 
   // Lists of live ranges
   ZoneVector<LiveRange*> fixed_live_ranges_;
   ZoneVector<LiveRange*> 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_;
 
   RegisterKind mode_;
   int num_registers_;
 
   BitVector* assigned_registers_;
   BitVector* assigned_double_registers_;
 
   // Indicates success or failure during register allocation.
   bool allocation_ok_;
 
 #ifdef DEBUG
   LifetimePosition allocation_finger_;
 #endif
 
   DISALLOW_COPY_AND_ASSIGN(RegisterAllocator);
 };
 
 }
 }
 }  // namespace v8::internal::compiler
 
 #endif  // V8_REGISTER_ALLOCATOR_H_