Reland: Introducing the LLVM greedy 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 567 matching lines @@
            InstructionOperand* operand, InstructionOperand* hint);
 
   RegisterAllocationData* const data_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeBuilder);
 };
 
 
 class RegisterAllocator : public ZoneObject {
  public:
-  explicit RegisterAllocator(RegisterAllocationData* data);
+  explicit RegisterAllocator(RegisterAllocationData* data, RegisterKind kind);
 
  protected:
   RegisterAllocationData* data() const { return data_; }
   InstructionSequence* code() const { return data()->code(); }
+  RegisterKind mode() const { return mode_; }
+  int num_registers() const { return num_registers_; }
+
   Zone* allocation_zone() const { return data()->allocation_zone(); }
 
   LiveRange* LiveRangeFor(int index) { return data()->LiveRangeFor(index); }
 
   // 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.
@@ skipping 11 matching lines @@
 
   void Spill(LiveRange* range);
 
   // If we are trying to spill a range inside the loop try to
   // hoist spill position out to the point just before the loop.
   LifetimePosition FindOptimalSpillingPos(LiveRange* range,
                                           LifetimePosition pos);
 
  private:
   RegisterAllocationData* const data_;
+  const RegisterKind mode_;
+  const int num_registers_;
 
   DISALLOW_COPY_AND_ASSIGN(RegisterAllocator);
 };
 
 
 class LinearScanAllocator final : public RegisterAllocator {
  public:
   LinearScanAllocator(RegisterAllocationData* data, RegisterKind kind,
                       Zone* local_zone);
 
   // Phase 4: compute register assignments.
   void AllocateRegisters();
 
  private:
-  int num_registers() const { return num_registers_; }
   const char* RegisterName(int allocation_index) const;
 
   ZoneVector<LiveRange*>& unhandled_live_ranges() {
     return unhandled_live_ranges_;
   }
   ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; }
   ZoneVector<LiveRange*>& inactive_live_ranges() {
     return inactive_live_ranges_;
   }
 
@@ skipping 21 matching lines @@
   void SpillBetween(LiveRange* range, LifetimePosition start,
                     LifetimePosition end);
 
   // Spill the given life range after position [start] and up to position [end].
   // Range is guaranteed to be spilled at least until position [until].
   void SpillBetweenUntil(LiveRange* range, LifetimePosition start,
                          LifetimePosition until, LifetimePosition end);
 
   void SplitAndSpillIntersecting(LiveRange* range);
 
-  const RegisterKind mode_;
-  const int num_registers_;
-
   ZoneVector<LiveRange*> unhandled_live_ranges_;
   ZoneVector<LiveRange*> active_live_ranges_;
   ZoneVector<LiveRange*> inactive_live_ranges_;
 
 #ifdef DEBUG
   LifetimePosition allocation_finger_;
 #endif
 
   DISALLOW_COPY_AND_ASSIGN(LinearScanAllocator);
 };
 
+class CoallescedLiveRanges;
+
+
+// A variant of the LLVM Greedy Register Allocator. See
+// http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
+class GreedyAllocator final : public RegisterAllocator {
+ public:
+  explicit GreedyAllocator(RegisterAllocationData* data, RegisterKind kind,
+                           Zone* local_zone);
+
+  void AllocateRegisters();
+
+ private:
+  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);
+
+  ZoneVector<CoallescedLiveRanges*> allocations_;
+  PQueue queue_;
+  DISALLOW_COPY_AND_ASSIGN(GreedyAllocator);
+};
+
 
 class OperandAssigner final : public ZoneObject {
  public:
   explicit OperandAssigner(RegisterAllocationData* data);
 
   // Phase 5: assign spill splots.
   void AssignSpillSlots();
 
   // Phase 6: commit assignment.
   void CommitAssignment();
@@ skipping 49 matching lines @@
   RegisterAllocationData* const data_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_REGISTER_ALLOCATOR_H_