[turbofan] Greedy: live range grouping.

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 {
 
 
 // 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.
 class AllocationCandidate {
  public:
-  explicit AllocationCandidate(LiveRange* range) : range_(range) {}
+  explicit AllocationCandidate(LiveRange* range)
+      : is_group_(false), size_(range->GetSize()) {
+    candidate_.range_ = range;
+  }
+
+  explicit AllocationCandidate(LiveRangeGroup* ranges)
+      : is_group_(true), size_(CalculateGroupSize(ranges)) {
+    candidate_.group_ = ranges;
+  }
 
   // Strict ordering operators
   bool operator<(const AllocationCandidate& other) const {
-    return range_->GetSize() < other.range_->GetSize();
+    return size() < other.size();
   }
 
   bool operator>(const AllocationCandidate& other) const {
-    return range_->GetSize() > other.range_->GetSize();
+    return size() > other.size();
   }
 
-  LiveRange* live_range() const { return range_; }
+  bool is_group() const { return is_group_; }
+  LiveRange* live_range() const { return candidate_.range_; }
+  LiveRangeGroup* group() const { return candidate_.group_; }
 
  private:
-  LiveRange* range_;
+  unsigned CalculateGroupSize(LiveRangeGroup* group) {
+    unsigned ret = 0;
+    for (LiveRange* range : group->ranges()) {
+      ret += range->GetSize();
+    }
+    return ret;
+  }
+
+  unsigned size() const { return size_; }
+  bool is_group_;
+  unsigned size_;
+  union {
+    LiveRange* range_;
+    LiveRangeGroup* group_;
+  } candidate_;
 };
 
 
 // Schedule processing (allocating) of AllocationCandidates.
 class AllocationScheduler final : ZoneObject {
  public:
   explicit AllocationScheduler(Zone* zone) : queue_(zone) {}
   void Schedule(LiveRange* range);
+  void Schedule(LiveRangeGroup* group);
   AllocationCandidate GetNext();
   bool empty() const { return queue_.empty(); }
 
  private:
   typedef ZonePriorityQueue<AllocationCandidate> ScheduleQueue;
   ScheduleQueue queue_;
 
   DISALLOW_COPY_AND_ASSIGN(AllocationScheduler);
 };
 
@@ skipping 24 matching lines @@
   AllocationScheduler& scheduler() { return scheduler_; }
   CoalescedLiveRanges* current_allocations(unsigned i) {
     return allocations_[i];
   }
 
   CoalescedLiveRanges* current_allocations(unsigned i) const {
     return allocations_[i];
   }
 
   Zone* local_zone() const { return local_zone_; }
+  ZoneVector<LiveRangeGroup*>& groups() { return groups_; }
+  const ZoneVector<LiveRangeGroup*>& groups() const { return groups_; }
 
   // Insert fixed ranges.
   void PreallocateFixedRanges();
 
+  void GroupLiveRanges();
+
   // Schedule unassigned live ranges for allocation.
-  // TODO(mtrofin): groups.
   void ScheduleAllocationCandidates();
 
   void AllocateRegisterToRange(unsigned reg_id, LiveRange* range) {
     UpdateWeightAtAllocation(range);
     current_allocations(reg_id)->AllocateRange(range);
   }
   // Evict and reschedule conflicts of a given range, at a given register.
   void EvictAndRescheduleConflicts(unsigned reg_id, const LiveRange* range);
 
   // Find the optimal split for ranges defined by a memory operand, e.g.
   // constants or function parameters passed on the stack.
   void SplitAndSpillRangesDefinedByMemoryOperand();
 
   void TryAllocateCandidate(const AllocationCandidate& candidate);
   void TryAllocateLiveRange(LiveRange* range);
+  void TryAllocateGroup(LiveRangeGroup* group);
 
   bool CanProcessRange(LiveRange* range) const {
     return range != nullptr && !range->IsEmpty() && range->kind() == mode();
   }
 
   // Calculate the weight of a candidate for allocation.
   void EnsureValidRangeWeight(LiveRange* range);
 
   // Calculate the new weight of a range that is about to be allocated.
   float GetAllocatedRangeWeight(float candidate_weight);
 
   // Returns kInvalidWeight if there are no conflicts, or the largest weight of
   // a range conflicting with the given range, at the given register.
   float GetMaximumConflictingWeight(unsigned reg_id,
                                     const LiveRange* range) const;
 
+  // Returns kInvalidWeight if there are no conflicts, or the largest weight of
+  // a range conflicting with the given range, at the given register.
+  float GetMaximumConflictingWeight(unsigned reg_id,
+                                    const LiveRangeGroup* group,
+                                    float group_weight) const;
+
   // This is the extension point for splitting heuristics.
   void SplitOrSpillBlockedRange(LiveRange* range);
 
   // Find a good position where to fill, after a range was spilled after a call.
   LifetimePosition FindSplitPositionAfterCall(const LiveRange* range,
                                               int call_index);
   // Split a range around all calls it passes over. Returns true if any changes
   // were made, or false if no calls were found.
   bool TrySplitAroundCalls(LiveRange* range);
 
@@ skipping 10 matching lines @@
   LiveRange* GetRemainderAfterSplittingAroundFirstCall(LiveRange* range);
 
   // Necessary heuristic: spill when all else failed.
   void SpillRangeAsLastResort(LiveRange* range);
 
   void AssignRangeToRegister(int reg_id, LiveRange* range);
 
   Zone* local_zone_;
   ZoneVector<CoalescedLiveRanges*> allocations_;
   AllocationScheduler scheduler_;
+  ZoneVector<LiveRangeGroup*> groups_;
+
   DISALLOW_COPY_AND_ASSIGN(GreedyAllocator);
 };
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 #endif  // V8_GREEDY_ALLOCATOR_H_