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 8ab37d19884034c88ff933342bbd2932d36d6e00..ebf28ac3c9fe15a20dd28d3d35ed1c5450c805d6 100644
--- a/src/compiler/register-allocator.h
+++ b/src/compiler/register-allocator.h
@@ -412,7 +412,7 @@ class SpillRange FINAL : public ZoneObject {
 };
 
 
-class RegisterAllocator FINAL : public ZoneObject {
+class RegisterAllocator : public ZoneObject {
  public:
   explicit RegisterAllocator(const RegisterConfiguration* config,
                              Zone* local_zone, Frame* frame,
@@ -442,8 +442,8 @@ class RegisterAllocator FINAL : public ZoneObject {
   bool ExistsUseWithoutDefinition();
 
   // Phase 4: compute register assignments.
-  void AllocateGeneralRegisters();
-  void AllocateDoubleRegisters();
+  virtual void AllocateGeneralRegisters() = 0;
+  virtual void AllocateDoubleRegisters() = 0;
 
   // Phase 5: assign spill splots.
   void AssignSpillSlots();
@@ -460,58 +460,163 @@ class RegisterAllocator FINAL : public ZoneObject {
   // Phase 9: insert moves to connect ranges across basic blocks.
   void ResolveControlFlow();
 
- private:
-  int GetVirtualRegister() { return code()->NextVirtualRegister(); }
+ protected:
+  virtual ~RegisterAllocator() {}
+  class PhiMapValue : public ZoneObject {
+   public:
+    PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone)
+        : phi(phi), block(block), incoming_moves(zone) {
+      incoming_moves.reserve(phi->operands().size());
+    }
+    PhiInstruction* const phi;
+    const InstructionBlock* const block;
+    ZoneVector<MoveOperands*> incoming_moves;
+  };
+  typedef ZoneMap<int, PhiMapValue*> PhiMap;
+  PhiMap& phi_map() { return phi_map_; }
 
-  // Checks whether the value of a given virtual register is a reference.
-  // TODO(titzer): rename this to IsReference.
-  bool HasTaggedValue(int virtual_register) const;
+  ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
+  ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; }
+  ZoneVector<LiveRange*>& fixed_double_live_ranges() {
+    return fixed_double_live_ranges_;
+  }
 
-  // Returns the register kind required by the given virtual register.
-  RegisterKind RequiredRegisterKind(int virtual_register) const;
+  BitVector* assigned_registers() const { return assigned_registers_; }
+  BitVector* assigned_double_registers() const {
+    return assigned_double_registers_;
+  }
 
-  // Creates a new live range.
-  LiveRange* NewLiveRange(int index);
+  Frame* frame() const { return frame_; }
+  const char* debug_name() const { return debug_name_; }
+  const RegisterConfiguration* config() const { return config_; }
+  ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; }
 
   // This zone is for InstructionOperands and moves that live beyond register
   // allocation.
   Zone* code_zone() const { return code()->zone(); }
+  Instruction* InstructionAt(int index) { return code()->InstructionAt(index); }
+  // Creates a new live range.
+  LiveRange* NewLiveRange(int index);
 
-  BitVector* assigned_registers() { return assigned_registers_; }
-  BitVector* assigned_double_registers() { return assigned_double_registers_; }
+  LiveRange* LiveRangeFor(int index);
+  LiveRange* LiveRangeFor(InstructionOperand* operand);
+  LiveRange* FixedLiveRangeFor(int index);
+  LiveRange* FixedDoubleLiveRangeFor(int index);
+  static int FixedLiveRangeID(int index) { return -index - 1; }
+  int FixedDoubleLiveRangeID(int index);
+  void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
 
-#ifdef DEBUG
-  void Verify() const;
-#endif
+  // Helper methods for building intervals.
+  InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos,
+                                    bool is_tagged);
 
-  void AllocateRegisters();
+  MoveOperands* AddGapMove(int index, Instruction::GapPosition position,
+                           const InstructionOperand& from,
+                           const InstructionOperand& to);
+  // Checks whether the value of a given virtual register is a reference.
+  // TODO(titzer): rename this to IsReference.
+  bool HasTaggedValue(int virtual_register) const;
+
+  bool IsBlockBoundary(LifetimePosition pos);
   bool CanEagerlyResolveControlFlow(const InstructionBlock* block) const;
-  bool SafePointsAreInOrder() const;
 
-  // Liveness analysis support.
-  BitVector* ComputeLiveOut(const InstructionBlock* block);
+  // Return the block which contains give lifetime position.
+  const InstructionBlock* GetInstructionBlock(LifetimePosition pos);
+  SpillRange* AssignSpillRangeToLiveRange(LiveRange* range);
+  void Spill(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);
+
+
+ private:
   void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out);
+  void AssignPhiInput(LiveRange* range, const InstructionOperand& assignment);
+  void ProcessInstructions(const InstructionBlock* block, BitVector* live);
+  Instruction* GetLastInstruction(const InstructionBlock* block);
+  void Define(LifetimePosition position, InstructionOperand* operand,
+              InstructionOperand* hint);
+  int GetVirtualRegister() { return code()->NextVirtualRegister(); }
+  void Use(LifetimePosition block_start, LifetimePosition position,
+           InstructionOperand* operand, InstructionOperand* hint);
+  // Returns the register kind required by the given virtual register.
+  RegisterKind RequiredRegisterKind(int virtual_register) const;
+
   bool IsOutputRegisterOf(Instruction* instr, int index);
   bool IsOutputDoubleRegisterOf(Instruction* instr, int index);
-  void ProcessInstructions(const InstructionBlock* block, BitVector* live);
+
+  void ResolvePhis(const InstructionBlock* block);
   void MeetRegisterConstraints(const InstructionBlock* block);
   void MeetConstraintsBefore(int index);
   void MeetConstraintsAfter(int index);
   void MeetRegisterConstraintsForLastInstructionInBlock(
       const InstructionBlock* block);
-  void ResolvePhis(const InstructionBlock* block);
 
-  // Helper methods for building intervals.
-  InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos,
-                                    bool is_tagged);
-  LiveRange* LiveRangeFor(InstructionOperand* operand);
-  void Define(LifetimePosition position, InstructionOperand* operand,
-              InstructionOperand* hint);
-  void Use(LifetimePosition block_start, LifetimePosition position,
-           InstructionOperand* operand, InstructionOperand* hint);
-  MoveOperands* AddGapMove(int index, Instruction::GapPosition position,
-                           const InstructionOperand& from,
-                           const InstructionOperand& to);
+  // Helper methods for resolving control flow.
+  void ResolveControlFlow(const InstructionBlock* block,
+                          const InstructionOperand& cur_op,
+                          const InstructionBlock* pred,
+                          const InstructionOperand& pred_op);
+  bool SafePointsAreInOrder() const;
+
+  // Liveness analysis support.
+  BitVector* ComputeLiveOut(const InstructionBlock* block);
+
+  Zone* const local_zone_;
+  Frame* const frame_;
+  InstructionSequence* const code_;
+  const char* const debug_name_;
+  const RegisterConfiguration* config_;
+  PhiMap phi_map_;
+
+  // Liveness analysis results.
+  ZoneVector<LiveRange*> live_ranges_;
+
+  // Lists of live ranges.
+  ZoneVector<LiveRange*> fixed_live_ranges_;
+  ZoneVector<LiveRange*> fixed_double_live_ranges_;
+  ZoneVector<SpillRange*> spill_ranges_;
+
+  // During liveness analysis keep a mapping from block id to live_in sets
+  // for blocks already analyzed.
+  ZoneVector<BitVector*> live_in_sets_;
+
+  BitVector* assigned_registers_;
+  BitVector* assigned_double_registers_;
+};
+
+
+class RegisterAllocatorLinear FINAL : public RegisterAllocator {
+ public:
+  explicit RegisterAllocatorLinear(const RegisterConfiguration* config,
+                                   Zone* local_zone, Frame* frame,
+                                   InstructionSequence* code,
+                                   const char* debug_name = nullptr);
+  void AllocateGeneralRegisters() override;
+  void AllocateDoubleRegisters() override;
+
+ private:
+#ifdef DEBUG
+  void Verify() const;
+#endif
+
+  void AllocateRegisters();
 
   // Helper methods for updating the life range lists.
   void AddToActive(LiveRange* range);
@@ -529,27 +634,6 @@ class RegisterAllocator FINAL : public ZoneObject {
   bool TryReuseSpillForPhi(LiveRange* range);
   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);
-
-  // 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);
@@ -570,42 +654,10 @@ class RegisterAllocator FINAL : public ZoneObject {
   LifetimePosition FindOptimalSpillingPos(LiveRange* range,
                                           LifetimePosition pos);
 
-  void Spill(LiveRange* range);
-  bool IsBlockBoundary(LifetimePosition pos);
-
-  // Helper methods for resolving control flow.
-  void ResolveControlFlow(const InstructionBlock* block,
-                          const InstructionOperand& cur_op,
-                          const InstructionBlock* pred,
-                          const InstructionOperand& pred_op);
-
-  void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
-
-  // Return the block which contains give lifetime position.
-  const InstructionBlock* GetInstructionBlock(LifetimePosition pos);
-
   // Helper methods for the fixed registers.
   int RegisterCount() const;
-  static int FixedLiveRangeID(int index) { return -index - 1; }
-  int FixedDoubleLiveRangeID(int index);
-  LiveRange* FixedLiveRangeFor(int index);
-  LiveRange* FixedDoubleLiveRangeFor(int index);
-  LiveRange* LiveRangeFor(int index);
-  Instruction* GetLastInstruction(const InstructionBlock* block);
 
   const char* RegisterName(int allocation_index);
-
-  Instruction* InstructionAt(int index) { return code()->InstructionAt(index); }
-  void AssignPhiInput(LiveRange* range, const InstructionOperand& assignment);
-
-  Frame* frame() const { return frame_; }
-  const char* debug_name() const { return debug_name_; }
-  const RegisterConfiguration* config() const { return config_; }
-  ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
-  ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; }
-  ZoneVector<LiveRange*>& fixed_double_live_ranges() {
-    return fixed_double_live_ranges_;
-  }
   ZoneVector<LiveRange*>& unhandled_live_ranges() {
     return unhandled_live_ranges_;
   }
@@ -613,54 +665,116 @@ class RegisterAllocator FINAL : public ZoneObject {
   ZoneVector<LiveRange*>& inactive_live_ranges() {
     return inactive_live_ranges_;
   }
-  ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; }
 
-  class PhiMapValue : public ZoneObject {
-   public:
-    PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone)
-        : phi(phi), block(block), incoming_moves(zone) {
-      incoming_moves.reserve(phi->operands().size());
-    }
-    PhiInstruction* const phi;
-    const InstructionBlock* const block;
-    ZoneVector<MoveOperands*> incoming_moves;
-  };
-  typedef ZoneMap<int, PhiMapValue*> PhiMap;
-
-  Zone* const local_zone_;
-  Frame* const frame_;
-  InstructionSequence* const code_;
-  const char* const debug_name_;
 
-  const RegisterConfiguration* config_;
-  PhiMap phi_map_;
-
-  // During liveness analysis keep a mapping from block id to live_in sets
-  // for blocks already analyzed.
-  ZoneVector<BitVector*> live_in_sets_;
-
-  // Liveness analysis results.
-  ZoneVector<LiveRange*> live_ranges_;
-
-  // Lists of live ranges
-  ZoneVector<LiveRange*> fixed_live_ranges_;
-  ZoneVector<LiveRange*> fixed_double_live_ranges_;
   ZoneVector<LiveRange*> unhandled_live_ranges_;
   ZoneVector<LiveRange*> active_live_ranges_;
   ZoneVector<LiveRange*> inactive_live_ranges_;
-  ZoneVector<SpillRange*> spill_ranges_;
 
   RegisterKind mode_;
   int num_registers_;
 
-  BitVector* assigned_registers_;
-  BitVector* assigned_double_registers_;
-
 #ifdef DEBUG
   LifetimePosition allocation_finger_;
 #endif
 
-  DISALLOW_COPY_AND_ASSIGN(RegisterAllocator);
+  DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorLinear);
+};
+
+class RegisterAllocatorGreedy FINAL : public RegisterAllocator {
+ public:
+  explicit RegisterAllocatorGreedy(const RegisterConfiguration* config,
+                                   Zone* local_zone, Frame* frame,
+                                   InstructionSequence* code,
+                                   const char* debug_name = nullptr);
+
+  void AllocateGeneralRegisters() override;
+  void AllocateDoubleRegisters() override;
+
+ private:
+  void AllocateRegisters(RegisterKind mode);
+  class RegisterAllocationInfo {

[dcarney, 2015/04/17 07:22:45]

make ZoneObject

[Mircea Trofin, 2015/04/17 19:23:33]

Done.

+   public:
+    explicit RegisterAllocationInfo(Zone* zone) : _storage(zone) {}

[dcarney, 2015/04/17 07:22:46]

this class doesn't need to be in the header.
also it's probably got to much inline code. we've been trying to reduce that. in
the implementation file it's obviously allowed though

[Mircea Trofin, 2015/04/17 19:23:34]

Done.

+
+    bool find(UseInterval* query, LiveRange*& result) {

[dcarney, 2015/04/17 07:22:46]

here and all over the place: functions in v8 start with capital letters except
for trivial getters and setters

[Mircea Trofin, 2015/04/17 19:23:34]

Done.

+      ZoneSplayTree<Config>::Locator locator;
+      bool ret = _storage.Find(GetKey(query), &locator);
+      if (ret) result = locator.value();
+      return ret;
+    }
+
+    bool insert(LiveRange* range) {
+      auto* interval = range->first_interval();
+      while (interval) {
+        if (!insert(interval, range)) return false;
+        interval = interval->next();
+      }
+      return true;
+    }
+
+    bool remove(UseInterval* key) { return _storage.Remove(GetKey(key)); }
+
+    bool remove(LiveRange* range) {
+      bool ret = false;
+      auto* segment = range->first_interval();
+      while (segment) {
+        ret |= remove(segment);
+        segment = segment->next();
+      }
+      return ret;
+    }
+    int isEmpty() { return _storage.is_empty(); }
+
+   private:
+    struct Config {
+      typedef std::pair<int, int> Key;
+      typedef LiveRange* Value;
+      static const Key kNoKey;
+      static Value NoValue() { return nullptr; }
+      static int Compare(const Key& a, const Key& b) {
+        if (a.second <= b.first) return -1;
+        if (a.first >= b.second) return 1;
+        return 0;
+      }
+    };
+
+    Config::Key GetKey(UseInterval* interval) {
+      if (!interval) return std::make_pair(0, 0);
+      return std::make_pair(interval->start().Value(), interval->end().Value());
+    }
+    bool insert(UseInterval* interval, LiveRange* range) {
+      ZoneSplayTree<Config>::Locator locator;
+      bool ret = _storage.Insert(GetKey(interval), &locator);
+      if (ret) locator.set_value(range);
+      return ret;
+    }
+
+    ZoneSplayTree<Config> _storage;

[dcarney, 2015/04/17 07:22:45]

in v8 this must be called storage_

[Mircea Trofin, 2015/04/17 19:23:34]

Done.

+  };

[dcarney, 2015/04/17 07:22:45]

the chromium style guide was DISALLOW_COPY_AND_ASSIGN on all classed that you
don't explicitly intend to be copied/assigned

[Mircea Trofin, 2015/04/17 19:23:33]

Done.

+
+  typedef std::priority_queue<std::pair<unsigned, LiveRange*>> PQueue;
+
+  unsigned GetLiveRangeSize(LiveRange* range);
+  void Enqueue(LiveRange* range);
+
+  void Evict(LiveRange* range);
+  float CalculateSpillWeight(LiveRange* range);
+  float CalculateMaxSpillWeight(ZoneSet<LiveRange*> ranges);

[dcarney, 2015/04/17 07:22:46]

you want ZoneSet<LiveRange*>* here to avoid epic levels of copying

[Mircea Trofin, 2015/04/17 19:23:34]

Good catch, thanks! It was meant to be ZoneSet<LiveRange*>&, but given the
guidance about refs only for constant parameters, moving to a pointer.

+
+
+  bool TryAllocate(LiveRange* current, ZoneSet<LiveRange*>& conflicting);

[dcarney, 2015/04/17 07:22:45]

ZoneSet<LiveRange*>* here as well, only const ref arguments allowed

[Mircea Trofin, 2015/04/17 19:23:34]

Done.

+  bool TryAllocatePhysicalRegister(unsigned regId, LiveRange* range,
+                                   ZoneSet<LiveRange*>& conflicting);
+  bool HandleSpillOperands(LiveRange* range);
+  bool AllocateBlockedRange(LiveRange*, ZoneSet<LiveRange*>&);
+
+  LiveRange* SpillBetweenUntil(LiveRange* range, LifetimePosition start,
+                               LifetimePosition until, LifetimePosition end);
+  void AssignRangeToRegister(unsigned regId, LiveRange* range);
+  PQueue queue_;
+  ZoneVector<RegisterAllocationInfo*> allocations_;
+  DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorGreedy);
 };
 
 }  // namespace compiler