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 710 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;
+
+  void reset() { *this = {0}; }
+};

[Jarin, 2015/05/13 13:12:57]

Could we have a proper constructor that sets everything to zero? Then reset
could be simply *this = AllocatorStats().

I also like to have a separate Print method and have the operator<< call the
Print method. This makes it easier to print from the gdb. Up to you.

+
+
+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 45 matching lines @@
 // 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);
+  bool FindGoodSplitPoint(LiveRange* range,
+                          const ZoneSet<LiveRange*>& conflicts);
+  LifetimePosition GetSplittablePos(UsePosition* use_pos, LiveRange* range);
+  LifetimePosition GetCorrectSplitPos(LifetimePosition pos);

[Jarin, 2015/05/13 13:12:57]

Nit: ...Pos -> ...Position)

   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;
 
+  unsigned GetLiveRangeSize(LiveRange* range, LifetimePosition start,
+                            LifetimePosition end);
   unsigned GetLiveRangeSize(LiveRange* range);
   void Enqueue(LiveRange* range);
 
   void Evict(LiveRange* range);
   float CalculateSpillWeight(LiveRange* range);
-  float CalculateMaxSpillWeight(const ZoneSet<LiveRange*>& ranges);
-
+  float CalculateSpillWeight(LiveRange* range, LifetimePosition start,
+                             LifetimePosition end);
 
   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);
+  void AllocateBlockedRange(LiveRange* current,
+                            const ZoneSet<LiveRange*>& conflicts);
 
   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);
+  bool RangeHasSplitOrSpillPosition(LiveRange* range, LifetimePosition start,
+                                    LifetimePosition end);
 
   Zone* local_zone_;
   ZoneVector<CoalescedLiveRanges*> allocations_;
   PQueue queue_;
   DISALLOW_COPY_AND_ASSIGN(GreedyAllocator);
 };
 
 
 class SpillSlotLocator final : public ZoneObject {
  public:
@@ skipping 71 matching lines @@
   RegisterAllocationData* const data_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_REGISTER_ALLOCATOR_H_