[turbofan] split register allocator into little pieces

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..0d726de2613d4fefac1fb3c49bcf6126d2f27eb6 100644
--- a/src/compiler/register-allocator.h
+++ b/src/compiler/register-allocator.h
@@ -340,17 +340,18 @@ class LiveRange FINAL : public ZoneObject {
   // Shorten the most recently added interval by setting a new start.
   void ShortenTo(LifetimePosition start);
 
-#ifdef DEBUG
   // True if target overlaps an existing interval.
   bool HasOverlap(UseInterval* target) const;
   void Verify() const;
-#endif
+
+  void ConvertUsesToOperand(const InstructionOperand& op,
+                            InstructionOperand* spill_op);
+
+  void set_kind(RegisterKind kind) { kind_ = kind; }
 
  private:
   struct SpillAtDefinitionList;
 
-  void ConvertUsesToOperand(const InstructionOperand& op,
-                            InstructionOperand* spill_op);
   UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const;
   void AdvanceLastProcessedMarker(UseInterval* to_start_of,
                                   LifetimePosition but_not_past) const;
@@ -381,8 +382,6 @@ class LiveRange FINAL : public ZoneObject {
   };
   SpillAtDefinitionList* spills_at_definition_;
 
-  friend class RegisterAllocator;  // Assigns to kind_.
-
   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 };
 
@@ -412,23 +411,23 @@ class SpillRange FINAL : public ZoneObject {
 };
 
 
-class RegisterAllocator FINAL : public ZoneObject {
+class LiveRangeBuilder FINAL : public ZoneObject {
  public:
-  explicit RegisterAllocator(const RegisterConfiguration* config,
-                             Zone* local_zone, Frame* frame,
-                             InstructionSequence* code,
-                             const char* debug_name = nullptr);
+  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;
 
-  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_; }
+  LiveRangeBuilder(const RegisterConfiguration* config, Zone* local_zone,
+                   Frame* frame, InstructionSequence* code,
+                   const char* debug_name = nullptr);
 
   // Phase 1 : insert moves to account for fixed register operands.
   void MeetRegisterConstraints();
@@ -441,53 +440,58 @@ class RegisterAllocator FINAL : public ZoneObject {
   void BuildLiveRanges();
   bool ExistsUseWithoutDefinition();
 
-  // Phase 4: compute register assignments.
-  void AllocateGeneralRegisters();
-  void AllocateDoubleRegisters();
-
-  // 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(); }
+  const ZoneVector<LiveRange*>& live_ranges() const { return live_ranges_; }
+  ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
+  const ZoneVector<LiveRange*>& fixed_live_ranges() const {
+    return fixed_live_ranges_;
+  }
+  ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; }
+  ZoneVector<LiveRange*>& fixed_double_live_ranges() {
+    return fixed_double_live_ranges_;
+  }
+  const ZoneVector<LiveRange*>& fixed_double_live_ranges() const {
+    return fixed_double_live_ranges_;
+  }
+  const ZoneVector<BitVector*>& live_in_sets() const { return live_in_sets_; }
+  ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; }
+  const ZoneVector<SpillRange*>& spill_ranges() const { return spill_ranges_; }
+  InstructionSequence* code() const { return code_; }
+  // This zone is for datastructures only needed during register allocation
+  // phases.
+  Zone* local_zone() const { return local_zone_; }
+  // This zone is for InstructionOperands and moves that live beyond register
+  // allocation.
+  Zone* code_zone() const { return code()->zone(); }
+  const PhiMap& phi_map() const { return phi_map_; }
+  PhiMap& phi_map() { return phi_map_; }
+  Frame* frame() const { return frame_; }
+  const char* debug_name() const { return debug_name_; }
+  const RegisterConfiguration* config() const { return config_; }
 
-  // Checks whether the value of a given virtual register is a reference.
-  // TODO(titzer): rename this to IsReference.
-  bool HasTaggedValue(int virtual_register) const;
+  void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
+  LiveRange* LiveRangeFor(int index);
+  Instruction* InstructionAt(int index) { return code()->InstructionAt(index); }
 
-  // Returns the register kind required by the given virtual register.
-  RegisterKind RequiredRegisterKind(int virtual_register) const;
+  void AssignPhiInput(LiveRange* range, const InstructionOperand& assignment);
+  SpillRange* AssignSpillRangeToLiveRange(LiveRange* range);
 
-  // Creates a new live range.
-  LiveRange* NewLiveRange(int index);
+  MoveOperands* AddGapMove(int index, Instruction::GapPosition position,
+                           const InstructionOperand& from,
+                           const InstructionOperand& to);
 
-  // This zone is for InstructionOperands and moves that live beyond register
-  // allocation.
-  Zone* code_zone() const { return code()->zone(); }
+  bool IsBlockBoundary(LifetimePosition pos);
 
-  BitVector* assigned_registers() { return assigned_registers_; }
-  BitVector* assigned_double_registers() { return assigned_double_registers_; }
+  const InstructionBlock* GetInstructionBlock(LifetimePosition pos) const {
+    return code()->GetInstructionBlock(pos.ToInstructionIndex());
+  }
 
-#ifdef DEBUG
   void Verify() const;
-#endif
 
-  void AllocateRegisters();
-  bool CanEagerlyResolveControlFlow(const InstructionBlock* block) const;
-  bool SafePointsAreInOrder() const;
+  bool IsReference(int virtual_register) const {
+    return code()->IsReference(virtual_register);
+  }
 
+ private:
   // Liveness analysis support.
   BitVector* ComputeLiveOut(const InstructionBlock* block);
   void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out);
@@ -501,6 +505,18 @@ class RegisterAllocator FINAL : public ZoneObject {
       const InstructionBlock* block);
   void ResolvePhis(const InstructionBlock* block);
 
+  static int FixedLiveRangeID(int index) { return -index - 1; }
+  int FixedDoubleLiveRangeID(int index);
+  LiveRange* FixedLiveRangeFor(int index);
+  LiveRange* FixedDoubleLiveRangeFor(int index);
+  Instruction* GetLastInstruction(const InstructionBlock* block);
+
+  // 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);
+
   // Helper methods for building intervals.
   InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos,
                                     bool is_tagged);
@@ -509,9 +525,55 @@ class RegisterAllocator FINAL : public ZoneObject {
               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);
+
+  Zone* const local_zone_;
+  Frame* const frame_;
+  InstructionSequence* const code_;
+  const char* const debug_name_;
+  const RegisterConfiguration* const config_;

[titzer, 2015/04/20 13:33:53]

Can we split the output of the LiveRangeBuilder into a separate data-only class
(hopefully struct!) so that we can pass that around?

+  PhiMap phi_map_;
+  ZoneVector<BitVector*> live_in_sets_;
+  ZoneVector<LiveRange*> live_ranges_;
+  ZoneVector<LiveRange*> fixed_live_ranges_;
+  ZoneVector<LiveRange*> fixed_double_live_ranges_;
+  ZoneVector<SpillRange*> spill_ranges_;
+  BitVector* assigned_registers_;
+  BitVector* assigned_double_registers_;
+
+  DISALLOW_COPY_AND_ASSIGN(LiveRangeBuilder);
+};
+
+
+class LinearScanAllocator FINAL : public ZoneObject {
+ public:
+  explicit LinearScanAllocator(LiveRangeBuilder* live_range_builder,
+                               RegisterKind kind);
+
+  // Phase 4: compute register assignments.
+  void AllocateRegisters();
+
+ private:
+  LiveRangeBuilder* live_range_builder() const { return live_range_builder_; }
+
+  InstructionSequence* code() const { return live_range_builder()->code(); }
+  // This zone is for datastructures only needed during register allocation.
+  Zone* local_zone() const { return live_range_builder()->local_zone(); }
+
+  // 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); }
+
+  int GetVirtualRegister() { return code()->NextVirtualRegister(); }
+
+  bool IsReference(int virtual_register) const {
+    return live_range_builder()->IsReference(virtual_register);
+  }
+
+  LiveRange* LiveRangeFor(int index) {
+    return live_range_builder()->LiveRangeFor(index);
+  }
 
   // Helper methods for updating the life range lists.
   void AddToActive(LiveRange* range);
@@ -529,7 +591,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.
 
@@ -571,40 +632,31 @@ class RegisterAllocator FINAL : public ZoneObject {
                                           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);
+  const InstructionBlock* GetInstructionBlock(LifetimePosition pos) const {
+    return live_range_builder()->GetInstructionBlock(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);
+  void SetLiveRangeAssignedRegister(LiveRange* range, int reg) {
+    live_range_builder()->SetLiveRangeAssignedRegister(range, reg);
+  }
 
+  // Helper methods for the fixed registers.
+  int RegisterCount() const { return num_registers_; }
   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_; }
+  const RegisterConfiguration* config() const {
+    return live_range_builder()->config();
+  }
+  ZoneVector<LiveRange*>& live_ranges() {
+    return live_range_builder()->live_ranges();
+  }
+  ZoneVector<LiveRange*>& fixed_live_ranges() {
+    return live_range_builder()->fixed_live_ranges();
+  }
   ZoneVector<LiveRange*>& fixed_double_live_ranges() {
-    return fixed_double_live_ranges_;
+    return live_range_builder()->fixed_double_live_ranges();
   }
   ZoneVector<LiveRange*>& unhandled_live_ranges() {
     return unhandled_live_ranges_;
@@ -613,54 +665,96 @@ 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_;
+  ZoneVector<SpillRange*>& spill_ranges() {
+    return live_range_builder()->spill_ranges();
+  }
+  LiveRangeBuilder::PhiMap& phi_map() {
+    return live_range_builder()->phi_map();
+  }
 
-  // Liveness analysis results.
-  ZoneVector<LiveRange*> live_ranges_;
+  LiveRangeBuilder* const live_range_builder_;
+  const RegisterKind mode_;
+  const int num_registers_;
 
-  // 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(LinearScanAllocator);
+};
+
+
+class OperandAssigner : public ZoneObject {
+ public:
+  explicit OperandAssigner(LiveRangeBuilder* live_range_builder);
+
+  // Phase 5: assign spill splots.
+  void AssignSpillSlots();
+
+  // Phase 6: commit assignment.
+  void CommitAssignment();
+
+ private:
+  LiveRangeBuilder* live_range_builder() const { return live_range_builder_; }
+
+  LiveRangeBuilder* const live_range_builder_;
+
+  DISALLOW_COPY_AND_ASSIGN(OperandAssigner);
+};
+
+
+class ReferenceMapPopulator : public ZoneObject {
+ public:
+  explicit ReferenceMapPopulator(LiveRangeBuilder* live_range_builder);
+
+  // Phase 7: compute values for pointer maps.
+  void PopulateReferenceMaps();
+
+ private:
+  bool SafePointsAreInOrder() const;
+
+  bool IsReference(int virtual_register) const {
+    return live_range_builder()->IsReference(virtual_register);
+  }
+
+  LiveRangeBuilder* live_range_builder() const { return live_range_builder_; }
+
+  LiveRangeBuilder* const live_range_builder_;
+
+  DISALLOW_COPY_AND_ASSIGN(ReferenceMapPopulator);
+};
+
+
+class LiveRangeConnector : public ZoneObject {
+ public:
+  explicit LiveRangeConnector(LiveRangeBuilder* live_range_builder);
+
+  // Phase 8: reconnect split ranges with moves.
+  void ConnectRanges(Zone* temp_zone);
+
+  // Phase 9: insert moves to connect ranges across basic blocks.
+  void ResolveControlFlow();
+
+ private:
+  const InstructionBlock* GetInstructionBlock(LifetimePosition pos) const {
+    return live_range_builder()->GetInstructionBlock(pos);
+  }
+  bool CanEagerlyResolveControlFlow(const InstructionBlock* block) const;
+  void ResolveControlFlow(const InstructionBlock* block,
+                          const InstructionOperand& cur_op,
+                          const InstructionBlock* pred,
+                          const InstructionOperand& pred_op);
+  InstructionSequence* code() const { return live_range_builder()->code(); }
+  Zone* code_zone() const { return code()->zone(); }
+  LiveRangeBuilder* live_range_builder() const { return live_range_builder_; }
+
+  LiveRangeBuilder* const live_range_builder_;
+
+  DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector);
 };
 
 }  // namespace compiler