[turbofan] Greedy: live range grouping.

src/compiler/greedy-allocator.cc

 // 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.
 
 #include "src/compiler/greedy-allocator.h"
 #include "src/compiler/register-allocator.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
@@ skipping 109 matching lines @@
   return ret;
 }
 
 
 void AllocationScheduler::Schedule(LiveRange* range) {
   TRACE("Scheduling live range %d:%d.\n", range->TopLevel()->vreg(),
         range->relative_id());
   queue_.push(AllocationCandidate(range));
 }
 
+
+void AllocationScheduler::Schedule(LiveRangeGroup* group) {
+  queue_.push(AllocationCandidate(group));
+}
+
 GreedyAllocator::GreedyAllocator(RegisterAllocationData* data,
                                  RegisterKind kind, Zone* local_zone)
     : RegisterAllocator(data, kind),
       local_zone_(local_zone),
       allocations_(local_zone),
-      scheduler_(local_zone) {}
+      scheduler_(local_zone),
+      groups_(local_zone) {}
 
 
 void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
   TRACE("Assigning register %s to live range %d:%d\n", RegisterName(reg_id),
         range->TopLevel()->vreg(), range->relative_id());
 
   DCHECK(!range->HasRegisterAssigned());
 
   AllocateRegisterToRange(reg_id, range);
 
@@ skipping 16 matching lines @@
       DCHECK(fixed_range->TopLevel()->IsFixed());
 
       int reg_nr = fixed_range->assigned_register();
       EnsureValidRangeWeight(fixed_range);
       AllocateRegisterToRange(reg_nr, fixed_range);
     }
   }
 }
 
 
+void GreedyAllocator::GroupLiveRanges() {
+  CoalescedLiveRanges groupper(local_zone());
+  for (TopLevelLiveRange* range : data()->live_ranges()) {
+    // Skip splinters, because we do not want to optimize for them, and moves
+    // due to assigning them to different registers occur in deferred blocks.
+    if (!CanProcessRange(range) || range->IsSplinter() || !range->is_phi()) {
+      continue;
+    }
+
+    // A phi can't be a memory operand, so it couldn't have been split.
+    DCHECK(!range->spilled());
+
+    // Maybe this phi range is itself an input to another phi which was already
+    // processed.
+    LiveRangeGroup* latest_grp = range->group() != nullptr
+                                     ? range->group()
+                                     : new (local_zone())
+                                           LiveRangeGroup(local_zone());
+
+    // Populate the groupper.
+    if (range->group() == nullptr) {
+      groupper.clear();
+      groupper.AllocateRange(range);
+    } else {
+      for (LiveRange* member : range->group()->ranges()) {
+        groupper.AllocateRange(member);
+      }
+    }
+    for (int j : data()->GetPhiMapValueFor(range)->phi()->operands()) {
+      // skip output also in input, which may happen for loops.
+      if (j == range->vreg()) continue;
+
+      TopLevelLiveRange* other_top = data()->live_ranges()[j];
+
+      if (other_top->IsSplinter()) continue;
+      // If the other was a memory operand, it might have been split.
+      // So get the unsplit part.
+      LiveRange* other =
+          other_top->next() == nullptr ? other_top : other_top->next();
+
+      if (other->spilled()) continue;
+
+      LiveRangeGroup* other_group = other->group();
+      if (other_group != nullptr) {
+        bool can_merge = true;
+        for (LiveRange* member : other_group->ranges()) {
+          if (groupper.GetConflicts(member).Current() != nullptr) {
+            can_merge = false;
+            break;
+          }
+        }
+        // If each member doesn't conflict with the current group, then since
+        // the members don't conflict with eachother either, we can merge them.
+        if (can_merge) {
+          latest_grp->ranges().insert(latest_grp->ranges().end(),
+                                      other_group->ranges().begin(),
+                                      other_group->ranges().end());
+          for (LiveRange* member : other_group->ranges()) {
+            groupper.AllocateRange(member);
+            member->set_group(latest_grp);
+          }
+          // Clear the other range, so we avoid scheduling it.
+          other_group->ranges().clear();
+        }
+      } else if (groupper.GetConflicts(other).Current() == nullptr) {
+        groupper.AllocateRange(other);
+        latest_grp->ranges().push_back(other);
+        other->set_group(latest_grp);
+      }
+    }
+
+    if (latest_grp->ranges().size() > 0 && range->group() == nullptr) {
+      latest_grp->ranges().push_back(range);
+      DCHECK(latest_grp->ranges().size() > 1);
+      groups().push_back(latest_grp);
+      range->set_group(latest_grp);
+    }
+  }
+}
+
+
 void GreedyAllocator::ScheduleAllocationCandidates() {
-  for (auto range : data()->live_ranges()) {
+  for (LiveRangeGroup* group : groups()) {
+    if (group->ranges().size() > 0) {
+      // We shouldn't have added single-range groups.
+      DCHECK(group->ranges().size() != 1);
+      scheduler().Schedule(group);
+    }
+  }
+  for (LiveRange* range : data()->live_ranges()) {
     if (CanProcessRange(range)) {
       for (LiveRange* child = range; child != nullptr; child = child->next()) {
-        if (!child->spilled()) {
+        if (!child->spilled() && child->group() == nullptr) {
           scheduler().Schedule(child);
         }
       }
     }
   }
 }
 
 
 void GreedyAllocator::TryAllocateCandidate(
     const AllocationCandidate& candidate) {
-  // At this point, this is just a live range. TODO: groups.
-  TryAllocateLiveRange(candidate.live_range());
+  if (candidate.is_group()) {
+    TryAllocateGroup(candidate.group());
+  } else {
+    TryAllocateLiveRange(candidate.live_range());
+  }
 }
 
 
+void GreedyAllocator::TryAllocateGroup(LiveRangeGroup* group) {
+  float group_weight = 0.0;
+  for (LiveRange* member : group->ranges()) {
+    EnsureValidRangeWeight(member);
+    group_weight = Max(group_weight, member->weight());
+  }
+
+  float eviction_weight = group_weight;
+  int eviction_reg = -1;
+  int free_reg = -1;
+  for (int reg = 0; reg < num_registers(); ++reg) {
+    float weight = GetMaximumConflictingWeight(reg, group, group_weight);
+    if (weight == LiveRange::kInvalidWeight) {
+      free_reg = reg;
+      break;
+    }
+    if (weight < eviction_weight) {
+      eviction_weight = weight;
+      eviction_reg = reg;
+    }
+  }
+  if (eviction_reg < 0 && free_reg < 0) {
+    for (LiveRange* member : group->ranges()) {
+      scheduler().Schedule(member);
+    }
+    return;
+  }
+  if (free_reg < 0) {
+    DCHECK(eviction_reg >= 0);
+    for (LiveRange* member : group->ranges()) {
+      EvictAndRescheduleConflicts(eviction_reg, member);
+    }
+    free_reg = eviction_reg;
+  }
+
+  DCHECK(free_reg >= 0);
+  for (LiveRange* member : group->ranges()) {
+    AssignRangeToRegister(free_reg, member);
+  }
+}
+
+
 void GreedyAllocator::TryAllocateLiveRange(LiveRange* range) {
   // TODO(mtrofin): once we introduce groups, we'll want to first try and
   // allocate at the preferred register.
   TRACE("Attempting to allocate live range %d:%d.\n", range->TopLevel()->vreg(),
         range->relative_id());
   int free_reg = -1;
   int evictable_reg = -1;
   int hinted_reg = -1;
 
   EnsureValidRangeWeight(range);
@@ skipping 71 matching lines @@
     scheduler().Schedule(conflict);
     TRACE("Evicted range %d%d.\n", conflict->TopLevel()->vreg(),
           conflict->relative_id());
   }
 }
 
 
 void GreedyAllocator::SplitAndSpillRangesDefinedByMemoryOperand() {
   size_t initial_range_count = data()->live_ranges().size();
   for (size_t i = 0; i < initial_range_count; ++i) {
-    auto range = data()->live_ranges()[i];
+    TopLevelLiveRange* range = data()->live_ranges()[i];
     if (!CanProcessRange(range)) continue;
     if (!range->HasSpillOperand()) continue;
 
     LifetimePosition start = range->Start();
     TRACE("Live range %d:%d is defined by a spill operand.\n",
           range->TopLevel()->vreg(), range->relative_id());
     auto next_pos = start;
     if (next_pos.IsGapPosition()) {
       next_pos = next_pos.NextStart();
     }
@@ skipping 21 matching lines @@
 
 
 void GreedyAllocator::AllocateRegisters() {
   CHECK(scheduler().empty());
   CHECK(allocations_.empty());
 
   TRACE("Begin allocating function %s with the Greedy Allocator\n",
         data()->debug_name());
 
   SplitAndSpillRangesDefinedByMemoryOperand();
+  GroupLiveRanges();
+  ScheduleAllocationCandidates();
   PreallocateFixedRanges();
-  ScheduleAllocationCandidates();
-
   while (!scheduler().empty()) {
     AllocationCandidate candidate = scheduler().GetNext();
     TryAllocateCandidate(candidate);
   }
 
   for (size_t i = 0; i < allocations_.size(); ++i) {
     if (!allocations_[i]->empty()) {
       data()->MarkAllocated(mode(), static_cast<int>(i));
     }
   }
@@ skipping 13 matching lines @@
        conflict = conflicts.GetNext()) {
     DCHECK_NE(conflict->weight(), LiveRange::kInvalidWeight);
     ret = Max(ret, conflict->weight());
     if (ret == LiveRange::kMaxWeight) return ret;
   }
 
   return ret;
 }
 
 
+float GreedyAllocator::GetMaximumConflictingWeight(unsigned reg_id,
+                                                   const LiveRangeGroup* group,
+                                                   float group_weight) const {
+  float ret = LiveRange::kInvalidWeight;
+
+  for (LiveRange* member : group->ranges()) {
+    float member_conflict_weight = GetMaximumConflictingWeight(reg_id, member);
+    if (member_conflict_weight == LiveRange::kMaxWeight) {
+      return LiveRange::kMaxWeight;
+    }
+    if (member_conflict_weight > group_weight) return LiveRange::kMaxWeight;
+    ret = Max(member_conflict_weight, ret);
+  }
+
+  return ret;
+}
+
+
 void GreedyAllocator::EnsureValidRangeWeight(LiveRange* range) {
   // The live range weight will be invalidated when ranges are created or split.
   // Otherwise, it is consistently updated when the range is allocated or
   // unallocated.
   if (range->weight() != LiveRange::kInvalidWeight) return;
 
   if (range->TopLevel()->IsFixed()) {
     range->set_weight(LiveRange::kMaxWeight);
     return;
   }
@@ skipping 131 matching lines @@
     scheduler().Schedule(range);
     return;
   }
   SpillRangeAsLastResort(range);
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8