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 394 matching lines @@
   void MergeDisjointIntervals(UseInterval* other);
 
   ZoneVector<LiveRange*> live_ranges_;
   UseInterval* use_interval_;
   LifetimePosition end_position_;
 
   DISALLOW_COPY_AND_ASSIGN(SpillRange);
 };
 
 
-class RegisterAllocator FINAL : public ZoneObject {
+class RegisterAllocator : public ZoneObject {
  public:
   explicit RegisterAllocator(const RegisterConfiguration* config,
                              Zone* local_zone, Frame* frame,
                              InstructionSequence* code,
                              const char* debug_name = nullptr);
 
   const ZoneVector<LiveRange*>& live_ranges() const { return live_ranges_; }
   const ZoneVector<LiveRange*>& fixed_live_ranges() const {
     return fixed_live_ranges_;
   }
   const ZoneVector<LiveRange*>& fixed_double_live_ranges() const {
     return fixed_double_live_ranges_;
   }
   InstructionSequence* code() const { return code_; }
   // This zone is for datastructures only needed during register allocation.
   Zone* local_zone() const { return local_zone_; }
 
   // Phase 1 : insert moves to account for fixed register operands.
   void MeetRegisterConstraints();
 
   // Phase 2: deconstruct SSA by inserting moves in successors and the headers
   // of blocks containing phis.
   void ResolvePhis();
 
   // Phase 3: compute liveness of all virtual register.
   void BuildLiveRanges();
   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();
 
   // Phase 6: commit assignment.
   void CommitAssignment();
 
   // Phase 7: compute values for pointer maps.
   void PopulateReferenceMaps();
 
   // Phase 8: reconnect split ranges with moves.
   void ConnectRanges();
 
   // 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_; }
 
+  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_;
+  }
+
+  BitVector* assigned_registers() const { return assigned_registers_; }
+  BitVector* assigned_double_registers() const {
+    return assigned_double_registers_;
+  }
+
+  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);
+
+  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);
+
+  // Helper methods for building intervals.
+  InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos,
+                                    bool is_tagged);
+
+  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;
+
+  // 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;
 
-  // Creates a new live range.
-  LiveRange* NewLiveRange(int index);
+  bool IsOutputRegisterOf(Instruction* instr, int index);
+  bool IsOutputDoubleRegisterOf(Instruction* instr, int index);
 
-  // This zone is for InstructionOperands and moves that live beyond register
-  // allocation.
-  Zone* code_zone() const { return code()->zone(); }
+  void ResolvePhis(const InstructionBlock* block);
+  void MeetRegisterConstraints(const InstructionBlock* block);
+  void MeetConstraintsBefore(int index);
+  void MeetConstraintsAfter(int index);
+  void MeetRegisterConstraintsForLastInstructionInBlock(
+      const InstructionBlock* block);
 
-  BitVector* assigned_registers() { return assigned_registers_; }
-  BitVector* assigned_double_registers() { return assigned_double_registers_; }
+  // 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();
-  bool CanEagerlyResolveControlFlow(const InstructionBlock* block) const;
-  bool SafePointsAreInOrder() const;
-
-  // Liveness analysis support.
-  BitVector* ComputeLiveOut(const InstructionBlock* block);
-  void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out);
-  bool IsOutputRegisterOf(Instruction* instr, int index);
-  bool IsOutputDoubleRegisterOf(Instruction* instr, int index);
-  void ProcessInstructions(const InstructionBlock* block, BitVector* live);
-  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 updating the life range lists.
   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);
 
   // Helper methods for allocating registers.
   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);
 
   // Spill the given life range after position [start] and up to position [end].
   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);
 
   // 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);
 
-  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_;
   }
   ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; }
   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
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_REGISTER_ALLOCATOR_H_