Reland: Introducing the LLVM greedy register allocator.

src/compiler/register-allocator.h

Index: src/compiler/register-allocator.h
diff --git a/src/compiler/register-allocator.h b/src/compiler/register-allocator.h
index d968258ce725881be5e3366f253cdd0829a56cb9..db2b938221c2bb7e7099f0c129e912c1cff5be1c 100644
--- a/src/compiler/register-allocator.h
+++ b/src/compiler/register-allocator.h
@@ -489,6 +489,26 @@ class RegisterAllocationData final : public ZoneObject {
 
   // Creates a new live range.
   LiveRange* NewLiveRange(int index);
+  void Spill(LiveRange* range);
+  int GetVirtualRegister() { return code()->NextVirtualRegister(); }
+  // Live range splitting helpers.
+
+  // Split the given range in a position from the interval [start, end].
+  LiveRange* SplitBetween(LiveRange* range, LifetimePosition start,
+                          LifetimePosition end);
+
+  // 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);
+  // 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);
 
  private:
   Zone* const allocation_zone_;
@@ -603,8 +623,6 @@ class LinearScanAllocator final : public ZoneObject {
 
   Instruction* InstructionAt(int index) { return code()->InstructionAt(index); }
 
-  int GetVirtualRegister() { return code()->NextVirtualRegister(); }
-
   bool IsReference(int virtual_register) const {
     return data()->IsReference(virtual_register);
   }
@@ -628,26 +646,6 @@ class LinearScanAllocator final : public ZoneObject {
   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);
 
@@ -667,8 +665,6 @@ class LinearScanAllocator final : public ZoneObject {
   LifetimePosition FindOptimalSpillingPos(LiveRange* range,
                                           LifetimePosition pos);
 
-  void Spill(LiveRange* range);
-
   // Return the block which contains give lifetime position.
   const InstructionBlock* GetInstructionBlock(LifetimePosition pos) const {
     return data()->GetInstructionBlock(pos);
@@ -683,12 +679,6 @@ class LinearScanAllocator final : public ZoneObject {
   const char* RegisterName(int allocation_index);
 
   ZoneVector<LiveRange*>& live_ranges() { return data()->live_ranges(); }
-  ZoneVector<LiveRange*>& fixed_live_ranges() {
-    return data()->fixed_live_ranges();
-  }
-  ZoneVector<LiveRange*>& fixed_double_live_ranges() {
-    return data()->fixed_double_live_ranges();
-  }
   ZoneVector<LiveRange*>& unhandled_live_ranges() {
     return unhandled_live_ranges_;
   }
@@ -715,6 +705,50 @@ class LinearScanAllocator final : public ZoneObject {
 };
 
 
+class CoallescedLiveRanges;
+
+

[jvoung (off chromium), 2015/04/21 23:34:06]

I don't know if v8 style would say to include a comment or some sort of link to
describe where the algorithm comes from.

[Mircea Trofin, 2015/04/22 04:37:33]

Done.

+class GreedyAllocator final : public ZoneObject {
+ public:
+  explicit GreedyAllocator(RegisterAllocationData* data, RegisterKind kind);
+
+  void AllocateRegisters();
+
+ private:
+  RegisterAllocationData* data() const { return data_; }
+  InstructionSequence* code() const { return data()->code(); }
+  const RegisterConfiguration* config() const { return data()->config(); }
+
+  typedef ZonePriorityQueue<std::pair<unsigned, LiveRange*>> PQueue;
+
+  unsigned GetLiveRangeSize(LiveRange* range);
+  void Enqueue(LiveRange* range);
+
+  void Evict(LiveRange* range);
+  float CalculateSpillWeight(LiveRange* range);
+  float CalculateMaxSpillWeight(const ZoneSet<LiveRange*>& ranges);
+
+
+  bool TryAllocate(LiveRange* current, ZoneSet<LiveRange*>* conflicting);
+  bool TryAllocatePhysicalRegister(unsigned reg_id, LiveRange* range,
+                                   ZoneSet<LiveRange*>* conflicting);
+  bool HandleSpillOperands(LiveRange* range);
+  bool AllocateBlockedRange(LiveRange*, const ZoneSet<LiveRange*>&);
+
+  LiveRange* SpillBetweenUntil(LiveRange* range, LifetimePosition start,
+                               LifetimePosition until, LifetimePosition end);
+  void AssignRangeToRegister(int reg_id, LiveRange* range);
+
+  RegisterAllocationData* const data_;
+  const RegisterKind mode_;
+  const int num_registers_;
+
+  ZoneVector<CoallescedLiveRanges*> allocations_;
+  PQueue queue_;
+  DISALLOW_COPY_AND_ASSIGN(GreedyAllocator);
+};
+
+
 class OperandAssigner final : public ZoneObject {
  public:
   explicit OperandAssigner(RegisterAllocationData* data);