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 {
   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 {
+    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_;
 };
 
 
+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 292 matching lines @@
   // This is used as a cache, it doesn't affect correctness.
   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:
   SpillRange(LiveRange* range, Zone* zone);
 
   UseInterval* interval() const { return use_interval_; }
   RegisterKind kind() const { return live_ranges_[0]->kind(); }
   bool IsEmpty() const { return live_ranges_.empty(); }
   bool TryMerge(SpillRange* other);
   void SetOperand(AllocatedOperand* op);
@@ skipping 87 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);
 
+  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_;
   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_;
   ZoneVector<LiveRange*> fixed_double_live_ranges_;
   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);
 };
 
 
 class ConstraintBuilder final : public ZoneObject {
  public:
   explicit ConstraintBuilder(RegisterAllocationData* data);
 
   // Phase 1 : insert moves to account for fixed register operands.
@@ skipping 213 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_