Greedy reg alloc - better splitting

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"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 enum RegisterKind {
   GENERAL_REGISTERS,
   DOUBLE_REGISTERS
 };
@@ skipping 126 matching lines @@
 
   // Code relies on kStep and kHalfStep being a power of two.
   STATIC_ASSERT(IS_POWER_OF_TWO(kHalfStep));
 
   explicit LifetimePosition(int value) : value_(value) {}
 
   int value_;
 };
 
 
+std::ostream& operator<<(std::ostream& os, const LifetimePosition pos);
+
+
 // Representation of the non-empty interval [start,end[.
 class UseInterval final : public ZoneObject {
  public:
   UseInterval(LifetimePosition start, LifetimePosition end)
       : start_(start), end_(end), next_(nullptr) {
     DCHECK(start < end);
   }
 
   LifetimePosition start() const { return start_; }
   void set_start(LifetimePosition start) { start_ = start; }
@@ skipping 296 matching lines @@
   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_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 };
 
 
+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);
@@ skipping 338 matching lines @@
   ZoneVector<LiveRange*> active_live_ranges_;
   ZoneVector<LiveRange*> inactive_live_ranges_;
 
 #ifdef DEBUG
   LifetimePosition allocation_finger_;
 #endif
 
   DISALLOW_COPY_AND_ASSIGN(LinearScanAllocator);
 };
 
-class CoallescedLiveRanges;
+class CoalescedLiveRanges;
 
 
 // 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);
   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);
   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*>&);
+  void AllocateBlockedRange(LiveRange* current, LifetimePosition pos,
+                            bool spill);
 
   LiveRange* SpillBetweenUntil(LiveRange* range, LifetimePosition start,
                                LifetimePosition until, LifetimePosition end);
   void AssignRangeToRegister(int reg_id, LiveRange* range);
 
-  ZoneVector<CoallescedLiveRanges*> allocations_;
+  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);
 
   void LocateSpillSlots();
@@ skipping 68 matching lines @@
   RegisterAllocationData* const data_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_REGISTER_ALLOCATOR_H_