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 RegisterAllocationInfo;
+
+
+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);
+  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(unsigned regId, LiveRange* range);
+
+  ZoneVector<RegisterAllocationInfo*> allocations_;
+  PQueue queue_;
+  DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorGreedy);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_REGISTER_ALLOCATOR_H_