Greedy reg alloc - better splitting

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 50b89ede055b78db461794d25578b67625ba5685..ced34aadde2512fdc806423ddbd0fb645a730bc7 100644
--- a/src/compiler/register-allocator.h
+++ b/src/compiler/register-allocator.h
@@ -6,8 +6,10 @@
 #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 {
@@ -100,6 +102,16 @@ class LifetimePosition final {
     return LifetimePosition(Start().value_ - kHalfStep);
   }
 
+  LifetimePosition Next() const {
+    DCHECK(IsValid());
+    return LifetimePosition(value_ + 1);
+  }
+
+  LifetimePosition Prev() const {
+    DCHECK(IsValid());
+    return LifetimePosition(value_ - 1);
+  }
+
   // Constructs the lifetime position which does not correspond to any
   // instruction.
   LifetimePosition() : value_(-1) {}
@@ -153,6 +165,9 @@ class LifetimePosition final {
 };
 
 
+std::ostream& operator<<(std::ostream& os, const LifetimePosition pos);
+
+
 // Representation of the non-empty interval [start,end[.
 class UseInterval final : public ZoneObject {
  public:
@@ -465,6 +480,13 @@ class LiveRange final : public ZoneObject {
   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:
@@ -572,6 +594,29 @@ class RegisterAllocationData final : public ZoneObject {
                                 PhiInstruction* phi);
   PhiMapValue* GetPhiMapValueFor(int virtual_register);
 
+  PrintableInstruction ToPrintable(Instruction* ins) const {
+    return {config_, ins};
+  }
+
+  PrintableInstructionOperand ToPrintable(InstructionOperand op) const {
+    return {config_, op};
+  }
+
+  PrintableInstructionSequence ToPrintable(InstructionSequence* seq) const {
+    return {config_, seq};
+  }
+
+  PrintableLiveRange ToPrintable(LiveRange* range) const {
+    return {config_, range};
+  }
+
+  void Print(Instruction* ins);
+  void Print(InstructionOperand op);
+  void Print(InstructionSequence* seq);
+  void Print(LiveRange* range);
+
+  std::ostream& dbgs() { return dbgs_; }
+
  private:
   Zone* const allocation_zone_;
   Frame* const frame_;
@@ -586,6 +631,7 @@ class RegisterAllocationData final : public ZoneObject {
   ZoneVector<SpillRange*> spill_ranges_;
   BitVector* assigned_registers_;
   BitVector* assigned_double_registers_;
+  OFStream dbgs_;

[dcarney, 2015/04/30 06:01:32]

this is not done anywhere in v8 and seems anyway a little odd.  like i said,
these Print things are the kinds of things we locally hack when necessary but do
not put in the codebase

can you tear out all the debugging stuff for now, except for the 2 operator <<
functions
so we can land this patch. it's anyway unrelated

 
   DISALLOW_COPY_AND_ASSIGN(RegisterAllocationData);
 };
@@ -819,6 +865,8 @@ class GreedyAllocator final : public RegisterAllocator {
 
  private:
   const RegisterConfiguration* config() const { return data()->config(); }
+  bool TryReuseSpillForPhi(LiveRange* range);
+  int GetHintedRegister(LiveRange* range);
 
   typedef ZonePriorityQueue<std::pair<unsigned, LiveRange*>> PQueue;
 
@@ -834,12 +882,16 @@ class GreedyAllocator final : public RegisterAllocator {
   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);
 
+  LifetimePosition FindProgressingSplitPosition(LiveRange* range,
+                                                bool* is_spill_pos);
+
   ZoneVector<CoallescedLiveRanges*> allocations_;
   PQueue queue_;
   DISALLOW_COPY_AND_ASSIGN(GreedyAllocator);
@@ -909,6 +961,7 @@ class LiveRangeConnector final : public ZoneObject {
   DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector);
 };
 
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8