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..76f566bfa3292817ece22f0cc0497b922927b2e2 100644
--- a/src/compiler/register-allocator.h
+++ b/src/compiler/register-allocator.h
@@ -8,6 +8,10 @@
 #include "src/compiler/instruction.h"
 #include "src/zone-containers.h"
 
+#ifdef DEBUG
+#include <iostream>

[dcarney, 2015/04/29 17:24:13]

this is not allowed - adds static initializers

[Mircea Trofin, 2015/04/29 17:35:33]

OK. 

As a note, weird that it shows up in the bot test for static initializers, I
thought that one validates release builds only, or?

+#endif
+
 namespace v8 {
 namespace internal {
 namespace compiler {
@@ -100,6 +104,16 @@ class LifetimePosition final {
     return LifetimePosition(Start().value_ - kHalfStep);
   }
 
+  LifetimePosition Next() const {

[dcarney, 2015/04/29 17:24:13]

are these really useful?  they seem unusual...

[Mircea Trofin, 2015/04/29 17:35:33]

Yes, see the way we pick split points. 

+    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 +167,25 @@ class LifetimePosition final {
 };
 
 
+#ifdef DEBUG
+static inline std::ostream& operator<<(std::ostream& os,

[dcarney, 2015/04/29 17:24:13]

this should not be DEBUG and should not be inline but in the impl file

+                                       const LifetimePosition& pos) {
+  os << '@' << pos.ToInstructionIndex();
+  if (pos.IsGapPosition()) {
+    os << 'g';
+  } else {
+    os << 'i';
+  }
+  if (pos.IsStart()) {
+    os << 's';
+  } else {
+    os << 'e';
+  }
+  return os;
+}
+#endif
+
+
 // Representation of the non-empty interval [start,end[.
 class UseInterval final : public ZoneObject {
  public:
@@ -572,6 +605,16 @@ class RegisterAllocationData final : public ZoneObject {
                                 PhiInstruction* phi);
   PhiMapValue* GetPhiMapValueFor(int virtual_register);
 
+#ifdef DEBUG
+  void Print(LiveRange* range);

[dcarney, 2015/04/29 17:24:13]

these we don't do in v8.  you'll need  a local patch if you want them.  you can
add  the ostream operator<< thing for LiveRange, though

[Mircea Trofin, 2015/04/29 17:35:33]

I see. So do we have an ostream available in gdb, akin LLVM's dbgs()? (I tried
to find something of the sort and unfortunately didn't)

I could add something like that and expose it here, so that the config is
available and we avoid asking the dev to construct Printable{...} while in the
debugger. 

I'd still have that stream available under DEBUG only, though.

+  void Print(ZoneSet<LiveRange*>& conflicts);
+  void Print(InstructionSequence* code);
+  void Print(Instruction* instr);
+  void Print(InstructionSequence* code, InstructionBlock* block);
+  void PrintOperators(LiveRange* range);
+  void Print(LifetimePosition pos);
+#endif
+
  private:
   Zone* const allocation_zone_;
   Frame* const frame_;
@@ -819,6 +862,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 +879,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 +958,7 @@ class LiveRangeConnector final : public ZoneObject {
   DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector);
 };
 
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8