Greedy allocator: perf work

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/ostreams.h"
 #include "src/zone-containers.h"
@@ skipping 233 matching lines @@
   UsePositionHintType hint_type() const {
     return HintTypeField::decode(flags_);
   }
   bool HasHint() const;
   bool HintRegister(int* register_index) const;
   void ResolveHint(UsePosition* use_pos);
   bool IsResolved() const {
     return hint_type() != UsePositionHintType::kUnresolved;
   }
   static UsePositionHintType HintTypeForOperand(const InstructionOperand& op);
+  void dump_hint(std::ostream& os, const RegisterConfiguration* config);
 
  private:
   typedef BitField<UsePositionType, 0, 2> TypeField;
   typedef BitField<UsePositionHintType, 2, 3> HintTypeField;
   typedef BitField<bool, 5, 1> RegisterBeneficialField;
   typedef BitField<int32_t, 6, 6> AssignedRegisterField;
 
   InstructionOperand* const operand_;
   void* hint_;
   UsePosition* next_;
   LifetimePosition const pos_;
   uint32_t flags_;
 
   DISALLOW_COPY_AND_ASSIGN(UsePosition);
 };
 
 
 class SpillRange;
+class LiveRangeGroup;
 
 
 // Representation of SSA values' live ranges as a collection of (continuous)
 // intervals over the instruction ordering.
 class LiveRange final : public ZoneObject {
  public:
   explicit LiveRange(int id, MachineType machine_type);
 
   UseInterval* first_interval() const { return first_interval_; }
   UsePosition* first_pos() const { return first_pos_; }
@@ skipping 52 matching lines @@
   // range and which follows both start and last processed use position
   UsePosition* NextUsePositionRegisterIsBeneficial(
       LifetimePosition start) const;
 
   // Returns use position for which register is beneficial in this live
   // range and which precedes start.
   UsePosition* PreviousUsePositionRegisterIsBeneficial(
       LifetimePosition start) const;
 
   // Can this live range be spilled at this position.
-  bool CanBeSpilled(LifetimePosition pos) const;
+  bool CanBeSpilled(LifetimePosition pos) const { return CanBeSplit(pos); }
+
+  // Can this live range be split at this position.
+  bool CanBeSplit(LifetimePosition pos) const;
 
   // Split this live range at the given position which must follow the start of
   // the range.
   // All uses following the given position will be moved from this
   // live range to the result live range.
   void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone);
 
   // Returns nullptr when no register is hinted, otherwise sets register_index.
   UsePosition* FirstHintPosition(int* register_index) const;
   UsePosition* FirstHintPosition() const {
@@ skipping 66 matching lines @@
                             const InstructionOperand& spill_op);
   void SetUseHints(int register_index);
   void UnsetUseHints() { SetUseHints(kUnassignedRegister); }
 
   struct SpillAtDefinitionList;
 
   SpillAtDefinitionList* spills_at_definition() const {
     return spills_at_definition_;
   }
 
+  LiveRangeGroup* group() { return group_; }
+  void SetGroup(LiveRangeGroup* grp) { group_ = grp; }
+
+  float weight() const {
+    DCHECK(weight_ >= 0.0);
+    return weight_;
+  }
+
+  unsigned size() {
+    if (size_ < 0) RecalculateSize();
+    DCHECK(size_ > 0);
+    return static_cast<unsigned>(size_);
+  }
+
+  void InvalidateWeightAndSize() {
+    weight_ = -1.0;
+    size_ = -1;
+  }
+  void RecalculateWeight(InstructionSequence* code);
+  LifetimePosition GetFirstSplittablePosition();
+
  private:
+  void RecalculateSize();
   void set_spill_type(SpillType value) {
     bits_ = SpillTypeField::update(bits_, value);
   }
 
   void set_spilled(bool value) { bits_ = SpilledField::update(bits_, value); }
 
   UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const;
   void AdvanceLastProcessedMarker(UseInterval* to_start_of,
                                   LifetimePosition but_not_past) const;
 
   typedef BitField<bool, 0, 1> SpilledField;
   typedef BitField<bool, 1, 1> HasSlotUseField;
   typedef BitField<bool, 2, 1> IsPhiField;
   typedef BitField<bool, 3, 1> IsNonLoopPhiField;
   typedef BitField<SpillType, 4, 2> SpillTypeField;
   typedef BitField<int32_t, 6, 6> AssignedRegisterField;
   typedef BitField<MachineType, 12, 15> MachineTypeField;
 
   int id_;
   int spill_start_index_;
   uint32_t bits_;
   UseInterval* last_interval_;
   UseInterval* first_interval_;
   UsePosition* first_pos_;
   LiveRange* parent_;
   LiveRange* next_;
+  float weight_;

[Jarin, 2015/06/03 15:06:16]

Could you please split the fields into groups by their use in the allocator
(three groups: (1) used by linear scan only, (2) used by greedy only, (3) used
by both). I am worried that too much bloat might hurt performance of linear
scan, the split could help with experiments measuring impact of the bloat. It
would also be good for documentation purposes.

[Mircea Trofin, 2015/06/04 03:38:39]

Actually, the greedy introduces 3 fields only, the rest end up being used by
both. So there's no category 1, at least just yet.

+  int size_;
   union {
     // Correct value determined by spill_type()
     InstructionOperand* spill_operand_;
     SpillRange* spill_range_;
   };
   SpillAtDefinitionList* spills_at_definition_;
   // This is used as a cache, it doesn't affect correctness.
   mutable UseInterval* current_interval_;
   // This is used as a cache, it doesn't affect correctness.
   mutable UsePosition* last_processed_use_;
   // This is used as a cache, it's invalid outside of BuildLiveRanges.
   mutable UsePosition* current_hint_position_;
 
+  LiveRangeGroup* group_;
   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 };
 
 
+class LiveRangeGroup final : public ZoneObject {
+ public:
+  explicit LiveRangeGroup(Zone* zone) : ranges_(zone) {}
+  ZoneSet<LiveRange*>& ranges() { return ranges_; }
+
+ private:
+  ZoneSet<LiveRange*> ranges_;
+
+  DISALLOW_COPY_AND_ASSIGN(LiveRangeGroup);
+};
+
 struct PrintableLiveRange {
   const RegisterConfiguration* register_configuration_;
   const LiveRange* range_;
 };
 
 
 std::ostream& operator<<(std::ostream& os,
                          const PrintableLiveRange& printable_range);
 
 
 class SpillRange final : public ZoneObject {
  public:
   static const int kUnassignedSlot = -1;
   SpillRange(LiveRange* range, Zone* zone);
 
   UseInterval* interval() const { return use_interval_; }
   // Currently, only 4 or 8 byte slots are supported.
   int ByteWidth() const;
   bool IsEmpty() const { return live_ranges_.empty(); }
   bool TryMerge(SpillRange* other);
 
   void set_assigned_slot(int index) {
     DCHECK_EQ(kUnassignedSlot, assigned_slot_);
     assigned_slot_ = index;
   }
+  bool IsSlotAssigned() { return assigned_slot_ != kUnassignedSlot; }
   int assigned_slot() {
     DCHECK_NE(kUnassignedSlot, assigned_slot_);
     return assigned_slot_;
   }
 
  private:
   LifetimePosition End() const { return end_position_; }
   ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; }
   bool IsIntersectingWith(SpillRange* other) const;
   // Merge intervals, making sure the use intervals are sorted
   void MergeDisjointIntervals(UseInterval* other);
 
   ZoneVector<LiveRange*> live_ranges_;
   UseInterval* use_interval_;
   LifetimePosition end_position_;
   int assigned_slot_;
 
   DISALLOW_COPY_AND_ASSIGN(SpillRange);
 };
 
 
+std::ostream& operator<<(std::ostream& os, SpillRange* range);
+
+
 class RegisterAllocationData final : public ZoneObject {
  public:
   class PhiMapValue : public ZoneObject {
    public:
     PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone);
 
     const PhiInstruction* phi() const { return phi_; }
     const InstructionBlock* block() const { return block_; }
 
     // For hinting.
@@ skipping 190 matching lines @@
            InstructionOperand* operand) {
     Use(block_start, position, operand, nullptr, UsePositionHintType::kNone);
   }
 
   RegisterAllocationData* const data_;
   ZoneMap<InstructionOperand*, UsePosition*> phi_hints_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeBuilder);
 };
 
+struct AllocatorStats {
+  unsigned spills;
+  unsigned wins;
+  unsigned losses_no_eviction;
+  unsigned losses_after_eviction;
+  unsigned good_split_attempts;
+  unsigned good_split_successes;
+  unsigned good_split_smart_above;
+  unsigned good_split_smart_below;
+  unsigned good_split_above;
+  unsigned good_split_below;
+  unsigned groups_attempted;
+  unsigned groups_succeeded;
+  unsigned groups_allocated;
+  void reset() { *this = {0}; }
+};
+
+
+std::ostream& operator<<(std::ostream& os, const AllocatorStats& stats);
+
 
 class RegisterAllocator : public ZoneObject {
  public:
   explicit RegisterAllocator(RegisterAllocationData* data, RegisterKind kind);
 
  protected:
+  AllocatorStats stats_;
   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.
@@ skipping 13 matching lines @@
   // loop covered by this interval or the latest possible position.
   LifetimePosition FindOptimalSplitPos(LifetimePosition start,
                                        LifetimePosition end);
 
   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);
+  const char* RegisterName(int allocation_index) const;
 
  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:
-  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_;
   }
 
   void SetLiveRangeAssignedRegister(LiveRange* range, int reg);
 
@@ skipping 32 matching lines @@
   ZoneVector<LiveRange*> active_live_ranges_;
   ZoneVector<LiveRange*> inactive_live_ranges_;
 
 #ifdef DEBUG
   LifetimePosition allocation_finger_;
 #endif
 
   DISALLOW_COPY_AND_ASSIGN(LinearScanAllocator);
 };
 
+
+// Storage detail for CoalescedLiveRanges.
+struct AllocatedInterval {
+  LifetimePosition start;
+  LifetimePosition end;
+  LiveRange* range;
+  struct Comparer : public std::binary_function<AllocatedInterval,
+                                                AllocatedInterval, bool> {
+    bool operator()(const AllocatedInterval& x,
+                    const AllocatedInterval& y) const {
+      return x.start < y.start;
+    }
+  };
+};
+
+
+typedef ZoneSet<AllocatedInterval, AllocatedInterval::Comparer>::const_iterator
+    interval_iterator;
+
+
 class CoalescedLiveRanges;
 
 
+// Iterator over allocated live ranges (CoalescedLiveRanges) that conflict with
+// a given one. See CoalescedLiveRanges::first_conflict.
+// Note that iterating may produce non-consecutively repeating live ranges.
+struct conflict_iterator {
+  friend class CoalescedLiveRanges;
+  conflict_iterator() : query_(nullptr), storage_(nullptr) {}
+
+  LiveRange* operator->() { return pos_->range; }
+
+  LiveRange* operator*() { return pos_->range; }

[Jarin, 2015/06/03 15:06:16]

Should not the star operator return a reference rather than a pointer?

[Mircea Trofin, 2015/06/04 03:38:39]

It returns the item "pointed at" by the iterator, so LiveRange*.

[Jarin, 2015/06/08 13:32:49]

Normally, operator* for T::iterator returns T&; operator-> returns T*.

+
+  conflict_iterator& operator++();
+  bool IsValid() const { return storage_ != nullptr; }
+
+  bool operator==(const conflict_iterator& other) {
+    return IsValid() && other.IsValid() && query_ == other.query_ &&
+           pos_ == other.pos_ && storage_ == other.storage_;
+  }
+
+  bool operator!=(const conflict_iterator& other) {

[Jarin, 2015/06/03 15:06:16]

Why is not this is simply negation of the equality?

Even if there is reason to do it this way, please, do not use bitwise xor for
bools. You can use != instead.

[Mircea Trofin, 2015/06/04 03:38:39]

Done.

+    return IsValid() ^ other.IsValid() || query_ != other.query_ ||
+           storage_ != other.storage_ ||
+           (storage_ != nullptr && pos_ != other.pos_);
+  }
+
+ private:
+  static bool Intersects(LifetimePosition a_start, LifetimePosition a_end,
+                         LifetimePosition b_start, LifetimePosition b_end) {
+    if (a_start == b_start) return true;
+    if (a_start < b_start) return a_end > b_start;
+    return Intersects(b_start, b_end, a_start, a_end);
+  }
+
+  conflict_iterator(UseInterval* q,
+                    ZoneSet<AllocatedInterval, AllocatedInterval::Comparer>* s,
+                    interval_iterator& it)
+      : query_(nullptr), storage_(nullptr), pos_(it) {}
+
+  conflict_iterator(
+      UseInterval* query,
+      ZoneSet<AllocatedInterval, AllocatedInterval::Comparer>* storage)
+      : query_(query), storage_(storage) {
+    InitializeForNewQuery();
+  }
+
+  void MoveToEnd() {
+    query_ = nullptr;
+    storage_ = nullptr;
+  }
+
+  void InitializeForNewQuery();
+
+  AllocatedInterval AsAllocatedInterval(LifetimePosition pos) {
+    return {pos, LifetimePosition::Invalid(), nullptr};
+  }
+
+  UseInterval* query_;
+  ZoneSet<AllocatedInterval, AllocatedInterval::Comparer>* storage_;
+  interval_iterator pos_;
+};
+
+
 // 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:
-  LifetimePosition GetSplittablePos(LifetimePosition pos);
+  void AllocateRange(LiveRange* current);
+  void AllocateGroup(LiveRangeGroup* grp);
+  bool TryAllocateGroup(LiveRangeGroup* grp);
+  bool TryAllocateGroupAtRegister(unsigned reg, LiveRangeGroup* grp);
+
+  struct PQueueElem {
+    bool IsGroup() { return is_grp_; }
+    explicit PQueueElem(LiveRange* range) : is_grp_(false) {
+      storage_.range_ = range;
+    }
+
+    explicit PQueueElem(LiveRangeGroup* grp) : is_grp_(true) {
+      storage_.grp_ = grp;
+    }
+
+
+    LiveRange* get_range() {
+      if (is_grp_) return nullptr;
+      return storage_.range_;
+    }
+
+
+    LiveRangeGroup* get_group() {
+      if (is_grp_) return storage_.grp_;
+      return nullptr;
+    }
+
+   private:
+    bool is_grp_;
+    union {
+      LiveRange* range_;
+      LiveRangeGroup* grp_;
+    } storage_;
+  };
+
+  void GroupAndEnqueue();
   const RegisterConfiguration* config() const { return data()->config(); }
   Zone* local_zone() const { return local_zone_; }
-  bool TryReuseSpillForPhi(LiveRange* range);
-  int GetHintedRegister(LiveRange* range);
 
-  typedef ZonePriorityQueue<std::pair<unsigned, LiveRange*>> PQueue;
+  struct PQueueElemComparer
+      : public std::binary_function<std::pair<unsigned, PQueueElem>,
+                                    std::pair<unsigned, PQueueElem>, bool> {
+    bool operator()(const std::pair<unsigned, PQueueElem>& x,
+                    const std::pair<unsigned, PQueueElem>& y) const {
+      return x.first < y.first;
+    }
+  };
 
-  unsigned GetLiveRangeSize(LiveRange* range);
+  typedef ZonePriorityQueue<std::pair<unsigned, PQueueElem>, PQueueElemComparer>
+      PQueue;
+
   void Enqueue(LiveRange* range);
+  void Enqueue(LiveRangeGroup* group);
 
   void Evict(LiveRange* range);
-  float CalculateSpillWeight(LiveRange* range);
-  float CalculateMaxSpillWeight(const ZoneSet<LiveRange*>& ranges);
+  void EvictAll(int reg, const conflict_iterator& first_conflict);
 
+  // Find the register with the minimum spill weight. If that is still higher
+  // or equal to competing, return -1.
+  int FindRegisterToEvictForRange(
+      conflict_iterator
+          all_conflicts[RegisterConfiguration::kMaxDoubleRegisters],
+      float competing);
 
-  bool TryAllocate(LiveRange* current, ZoneSet<LiveRange*>* conflicting);
-  bool TryAllocatePhysicalRegister(unsigned reg_id, LiveRange* range,
-                                   ZoneSet<LiveRange*>* conflicting);
-  bool HandleSpillOperands(LiveRange* range);
-  void AllocateBlockedRange(LiveRange* current, LifetimePosition pos,
-                            bool spill);
+  // Same as above, for all the registers in a group.
+  int FindRegisterToEvictForGroup(LiveRangeGroup* grp, float competing);
+
+  template <typename TIter>
+  float CalculateMaxSpillWeight(const TIter& begin, const TIter& end);
+
+  bool HandleSpillOperands(LiveRange* range, LiveRange** remaining);
+  void HandleBlockedRange(LiveRange* current);
+  bool TrySplitBeforeLoops(LiveRange* current);
+  bool TrySplitAfterLoops(LiveRange* current);
+  bool TrySplitAroundCalls(LiveRange* range);
 
   LiveRange* SpillBetweenUntil(LiveRange* range, LifetimePosition start,
                                LifetimePosition until, LifetimePosition end);
   void AssignRangeToRegister(int reg_id, LiveRange* range);
 
-  LifetimePosition FindProgressingSplitPosition(LiveRange* range,
-                                                bool* is_spill_pos);
-
   Zone* local_zone_;
   ZoneVector<CoalescedLiveRanges*> allocations_;
   PQueue queue_;
   DISALLOW_COPY_AND_ASSIGN(GreedyAllocator);
 };
 
 
 class SpillSlotLocator final : public ZoneObject {
  public:
   explicit SpillSlotLocator(RegisterAllocationData* data);
@@ skipping 70 matching lines @@
   RegisterAllocationData* const data_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_REGISTER_ALLOCATOR_H_