[turbofan] Greedy allocator refactoring.

src/compiler/greedy-allocator.h

 // Copyright 2015 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_GREEDY_ALLOCATOR_H_
 #define V8_GREEDY_ALLOCATOR_H_
 
+#include "src/compiler/coalesced-live-ranges.h"
 #include "src/compiler/register-allocator.h"
 #include "src/zone-containers.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
-class CoalescedLiveRanges;
+
+// The object of allocation scheduling. At minimum, this is a LiveRange, but
+// we may extend this to groups of LiveRanges. It has to be comparable.
+// TODO(mtrofin): size calculation may happen redundantly for a range, consider
+// making size a member of LiveRange.
+struct AllocationCandidate {
+  explicit AllocationCandidate(LiveRange* range);
+  bool operator<(const AllocationCandidate& other) const {
+    return size_ < other.size_;
+  }

[Benedikt Meurer, 2015/06/25 04:41:06]

Nit: Please add an appropriate operator> if you decide to overload operator<,
even if it's currently unused.

[Mircea Trofin, 2015/06/25 23:06:22]

Done.

+  LiveRange* live_range() const { return range_; }
+  unsigned size() const { return size_; }
+
+ private:
+  LiveRange* range_;
+  unsigned size_;
+};
+
+
+// Schedule processing (allocating) of AllocationCandidates.
+class AllocationScheduler final : ZoneObject {
+ public:
+  explicit AllocationScheduler(Zone* zone) : storage_(zone) {}
+  void Schedule(LiveRange* range) { storage_.push(AllocationCandidate(range)); }
+  AllocationCandidate GetNext();
+  bool empty() const { return storage_.empty(); }
+
+ private:
+  typedef ZonePriorityQueue<AllocationCandidate> ScheduleStorage;
+  ScheduleStorage storage_;
+
+  DISALLOW_COPY_AND_ASSIGN(AllocationScheduler);
+};
 
 
 // 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(); }
+  AllocationScheduler& scheduler() { return scheduler_; }
+  CoalescedLiveRanges* current_allocations(unsigned i) {
+    return allocations_[i];
+  }
   Zone* local_zone() const { return local_zone_; }
 
-  int GetHintedRegister(LiveRange* range);
+  // Insert fixed ranges.
+  void InitializeAllocations();

[titzer, 2015/06/24 23:05:44]

Why not just name the method after what it does? InsertFixedRanges()?

[Mircea Trofin, 2015/06/25 23:06:23]

Good suggestion. I'm proposing PreallocateFixedRanges.

 
-  typedef ZonePriorityQueue<std::pair<unsigned, LiveRange*>> PQueue;
+  // Schedule unassigned live ranges for allocation.
+  // TODO(mtrofin): groups.
+  void InitializeScheduler();

[titzer, 2015/06/24 23:05:44]

Same here.

[Mircea Trofin, 2015/06/25 23:06:23]

Done.

 
-  unsigned GetLiveRangeSize(LiveRange* range);
-  void Enqueue(LiveRange* range);
+  // Find the optimal split for ranges defined by a memory operand, e.g.
+  // constants or function parameters passed on the stack.
+  void HandleRangesDefinedByMemoryOperand();

[titzer, 2015/06/24 23:05:44]

"handle" is too general. Please name the method after what it does. This doesn't
return anything, so it obviously has some side effects.

 
-  void Evict(LiveRange* range);
-  float CalculateSpillWeight(LiveRange* range);
-  float CalculateMaxSpillWeight(const ZoneSet<LiveRange*>& ranges);
+  void ProcessCandidate(const AllocationCandidate& candidate);

[titzer, 2015/06/24 23:05:44]

What does Process mean?

[Mircea Trofin, 2015/06/25 23:06:23]

Done.

+  void ProcessLiveRange(LiveRange* range, unsigned size);
 
+  bool CanProcessRange(LiveRange* range) const {
+    return range != nullptr && !range->IsEmpty() && range->kind() == mode();
+  }
 
-  bool TryAllocate(LiveRange* current, ZoneSet<LiveRange*>* conflicting);
-  bool TryAllocatePhysicalRegister(unsigned reg_id, LiveRange* range,
-                                   ZoneSet<LiveRange*>* conflicting);
+  // Calculate the weight of a candidate for allocation.
+  float GetCandidateRangeWeight(LiveRange* range, unsigned size);

[titzer, 2015/06/24 23:05:44]

Even though this is camel case (and thus CouldPerformCalculations), it might be
better to avoid naming things with the Get prefix if they compute something.

[Mircea Trofin, 2015/06/25 23:06:23]

Done by virtue of having had changed a bit more on the API. 

+
+  // Calculate the new weight of a range that is about to be allocated.
+  float GetAllocatedRangeWeight(float candidate_weight);
+
+  // TODO(mtrofin): HandleSpillOperands feel like belonging to
+  // a preceding phase, rather than here.
   bool HandleSpillOperands(LiveRange* range);

[titzer, 2015/06/24 23:05:44]

Again, no idea what "Handle" means here.

[Mircea Trofin, 2015/06/25 23:06:23]

Done.

-  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);
+  // This is the extension point for splitting heuristics.
+  void HandleBlockedRange(LiveRange* range);
 
-  LifetimePosition FindProgressingSplitPosition(LiveRange* range,
-                                                bool* is_spill_pos);
+  // Necessary heuristic: spill when all else failed.
+  void SpillRangeAsLastResort(LiveRange* range);
+
+  void AssignRangeToRegister(int reg_id, LiveRange* range, float weight);
 
   Zone* local_zone_;
   ZoneVector<CoalescedLiveRanges*> allocations_;
-  PQueue queue_;
+  AllocationScheduler scheduler_;
   DISALLOW_COPY_AND_ASSIGN(GreedyAllocator);
 };
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 #endif  // V8_GREEDY_ALLOCATOR_H_