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/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 {
 
 enum RegisterKind {
   UNALLOCATED_REGISTERS,
   GENERAL_REGISTERS,
   DOUBLE_REGISTERS
 };
 
@@ skipping 72 matching lines @@
     return LifetimePosition(FullStart().value_ + kStep);
   }
 
   // Returns the lifetime position for the beginning of the previous START.
   LifetimePosition PrevStart() const {
     DCHECK(IsValid());
     DCHECK(value_ >= kHalfStep);
     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) {}
 
   // Returns true if this lifetime positions corrensponds to some
   // instruction.
   bool IsValid() const { return value_ != -1; }
 
   bool operator<(const LifetimePosition& that) const {
     return this->value_ < that.value_;
@@ skipping 33 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_;
 };
 
 
+#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:
   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 399 matching lines @@
 
   // Creates a new live range.
   LiveRange* NewLiveRange(int index);
 
   void MarkAllocated(RegisterKind kind, int index);
 
   PhiMapValue* InitializePhiMap(const InstructionBlock* block,
                                 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_;
   InstructionSequence* const code_;
   const char* const debug_name_;
   const RegisterConfiguration* const config_;
   PhiMap phi_map_;
   ZoneVector<BitVector*> live_in_sets_;
   ZoneVector<LiveRange*> live_ranges_;
   ZoneVector<LiveRange*> fixed_live_ranges_;
@@ skipping 227 matching lines @@
 // 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:
   const RegisterConfiguration* config() const { return data()->config(); }
+  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);
 
+  LifetimePosition FindProgressingSplitPosition(LiveRange* range,
+                                                bool* is_spill_pos);
+
   ZoneVector<CoallescedLiveRanges*> allocations_;
   PQueue queue_;
   DISALLOW_COPY_AND_ASSIGN(GreedyAllocator);
 };
 
 
 class OperandAssigner final : public ZoneObject {
  public:
   explicit OperandAssigner(RegisterAllocationData* data);
 
@@ skipping 49 matching lines @@
   void ResolveControlFlow(const InstructionBlock* block,
                           const InstructionOperand& cur_op,
                           const InstructionBlock* pred,
                           const InstructionOperand& pred_op);
 
   RegisterAllocationData* const data_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector);
 };
 
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_REGISTER_ALLOCATOR_H_