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() const { return group_; }
+  void SetGroup(LiveRangeGroup* grp) { group_ = grp; }
+
+  float GetWeight() const {
+    DCHECK(weight_ >= 0.0f);
+    return weight_;
+  }
+
+  unsigned GetSize() {
+    if (size_ < 0) RecalculateSize();
+    DCHECK(size_ > 0);
+    return static_cast<unsigned>(size_);
+  }
+
+  void InvalidateWeightAndSize() {
+    weight_ = kInvalidWeight;
+    size_ = kInvalidSize;
+  }
+  void RecalculateWeight(InstructionSequence* code);
+  LifetimePosition GetFirstSplittablePosition();
+
+  static const float kMaxWeight;
+
  private:
+  static const float kUseInLoopWeightMultiplier;
+  static const float kPreferredRegisterWeightMultiplier;
+  static const float kInvalidWeight;
+  static const int kInvalidSize = -1;
+
+  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;
 
@@ skipping 19 matching lines @@
     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_;
 
+  // Used only by the greedy allocator.
+  float weight_;
+  int size_;
+  LiveRangeGroup* group_;
   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 };
 
 
+class LiveRangeGroup final : public ZoneObject {
+ public:
+  explicit LiveRangeGroup(Zone* zone) : ranges_(zone) {}
+  ZoneSet<LiveRange*>& ranges() { return ranges_; }
+  bool CanAdd(LiveRange* r);
+  void TryMerge(LiveRangeGroup* other);
+
+ 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() const { 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;
+    }
+  };
+};
+
+
 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 {
+  conflict_iterator() : storage_(nullptr) {}

[Jarin, 2015/06/12 04:09:12]

Initialize all fields here.

+  const LiveRange* operator->() const { return pos_->range; }
+
+  LiveRange* operator*() const { return pos_->range; }
+
+  conflict_iterator& operator++();
+  bool IsEnd() const {
+    DCHECK(storage_ != nullptr);
+    return pos_ == storage_->end();
+  }
+
+ private:
+  friend class CoalescedLiveRanges;
+  friend bool operator==(const conflict_iterator& first,
+                         const conflict_iterator& second);
+
+  typedef ZoneSet<AllocatedInterval, AllocatedInterval::Comparer> IntervalStore;
+  typedef IntervalStore::const_iterator interval_iterator;
+
+  void Invalidate() {
+    DCHECK(storage_ != nullptr);
+    pos_ = storage_->end();
+    query_ = nullptr;
+  }
+
+  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;

[Jarin, 2015/06/12 04:09:12]

Out of curiosity, cannot you just leave out the "if (a_start == b_start) return
true" line and replace "a_start < b_start" with "a_start <= b_start"?

This special casing for equality seems a bit funny.

Perhaps you can even expand the recursive call, so the body would be:

if (a_start <= b_start) return b_start < a_end;
return b_start <= a_start && a_start < b_end;

[Sven Panne, 2015/06/12 07:36:37]

Hmmm, this looks still too complicated, normally just a single line is needed:

   return a_start <= b_end && b_start <= a_end;

I'm not sure about the "open-ness" of our intervals, but I'm quite sure that
this condition can be tweaked to any convention.

+    return Intersects(b_start, b_end, a_start, a_end);
+  }
+
+  bool QueryIntersectsAllocatedInterval() {
+    DCHECK(query_ != nullptr);
+    return Intersects(query_->start(), query_->end(), pos_->start, pos_->end);
+  }
+
+  bool NextQueryIntersectsAllocatedInterval() {
+    DCHECK(query_->next() != nullptr);
+    return Intersects(query_->next()->start(), query_->next()->end(),
+                      pos_->start, pos_->end);
+  }
+
+  conflict_iterator(UseInterval* query, IntervalStore* storage)
+      : query_(query), storage_(storage) {
+    InitializeForNewQuery();
+  }
+
+  explicit conflict_iterator(IntervalStore* storage) : storage_(storage) {
+    Invalidate();
+  }
+
+  static conflict_iterator EndIteratorForStorage(IntervalStore* storage) {
+    conflict_iterator ret(storage);
+    return ret;
+  }
+
+  void InitializeForNewQuery();
+  void SkipMatchedQueries();
+
+  AllocatedInterval AsAllocatedInterval(LifetimePosition pos) {
+    return {pos, LifetimePosition::Invalid(), nullptr};
+  }
+
+  UseInterval* query_;
+  IntervalStore* storage_;
+  interval_iterator pos_;
+};
+
+bool operator==(const conflict_iterator& first,
+                const conflict_iterator& second);
+bool operator!=(const conflict_iterator& first,
+                const conflict_iterator& second);
+
+
 // 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 {

[Jarin, 2015/06/12 04:09:12]

PQueueElem -> QueueElement (or PriorityQueueElement).

I am actually wondering whether you could not include the priority field in the
struct, so that it is really the element. This would save you some std::pair
exercises.

+    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;

[Jarin, 2015/06/12 04:09:12]

The callers should (and do) always consult IsGroup, so it is safer to just do
"DCHECK(!IsGroup()); return storage_.range_;" here.

+      return storage_.range_;
+    }
+
+
+    LiveRangeGroup* get_group() {
+      if (is_grp_) return storage_.grp_;

[Jarin, 2015/06/12 04:09:12]

Similarly, "DCHECK(IsGroup()); return storage_.grp_;".

+      return nullptr;
+    }
+
+   private:
+    bool is_grp_;
+    union {
+      LiveRange* range_;
+      LiveRangeGroup* grp_;
+    } storage_;
+  };
+
+  void GroupAndEnqueue();

[Jarin, 2015/06/12 04:09:12]

GroupAndEnqueue -> EnqueuePhiGroups?

   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;

[Jarin, 2015/06/12 04:09:12]

PQueue -> PriorityQueue

+
   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);

[Jarin, 2015/06/12 04:09:12]

Static?

+
+  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_