[turbofan] Greedy: Unset hints at eviction.

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 {
 
 
 #define TRACE(...)                             \
   do {                                         \
     if (FLAG_trace_alloc) PrintF(__VA_ARGS__); \
   } while (false)
 
 
 const float GreedyAllocator::kAllocatedRangeMultiplier = 10.0;
 
 
 namespace {
 
-
-void UpdateOperands(TopLevelLiveRange* range, RegisterAllocationData* data) {
+void UpdateOperands(LiveRange* range, RegisterAllocationData* data) {
   int reg_id = range->assigned_register();
   range->SetUseHints(reg_id);
-  if (range->is_phi()) {
-    data->GetPhiMapValueFor(range)->set_assigned_register(reg_id);
+  if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
+    data->GetPhiMapValueFor(range->TopLevel())->set_assigned_register(reg_id);
   }
 }
 
+
+void UnsetOperands(LiveRange* range, RegisterAllocationData* data) {
+  range->UnsetUseHints();
+  if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
+    data->GetPhiMapValueFor(range->TopLevel())->UnsetAssignedRegister();
+  }
+}
+
 
 LiveRange* Split(LiveRange* range, RegisterAllocationData* data,
                  LifetimePosition pos) {
   DCHECK(range->Start() < pos && pos < range->End());
   DCHECK(pos.IsStart() || pos.IsGapPosition() ||
          (data->code()
               ->GetInstructionBlock(pos.ToInstructionIndex())
               ->last_instruction_index() != pos.ToInstructionIndex()));
   LiveRange* result = range->SplitAt(pos, data->allocation_zone());
   return result;
 }
 
 
 // TODO(mtrofin): explain why splitting in gap START is always OK.
 LifetimePosition GetSplitPositionForInstruction(const LiveRange* range,
-                                                const InstructionSequence* code,
                                                 int instruction_index) {
   LifetimePosition ret = LifetimePosition::Invalid();
 
   ret = LifetimePosition::GapFromInstructionIndex(instruction_index);
   if (range->Start() >= ret || ret >= range->End()) {
     return LifetimePosition::Invalid();
   }
   return ret;
 }
 
@@ skipping 22 matching lines @@
   UseInterval* interval = range->first_interval();
   int first = GetFirstGapIndex(interval);
   int last = GetLastGapIndex(interval);
   if (first == last) return LifetimePosition::Invalid();
 
   // TODO(mtrofin:) determine why we can't just split somewhere arbitrary
   // within the range, e.g. it's middle.
   for (UsePosition* pos = range->first_pos(); pos != nullptr;
        pos = pos->next()) {
     if (pos->type() != UsePositionType::kRequiresRegister) continue;
-    LifetimePosition before = GetSplitPositionForInstruction(
-        range, code, pos->pos().ToInstructionIndex());
+    LifetimePosition before =
+        GetSplitPositionForInstruction(range, pos->pos().ToInstructionIndex());
     if (before.IsValid()) return before;
     LifetimePosition after = GetSplitPositionForInstruction(
-        range, code, pos->pos().ToInstructionIndex() + 1);
+        range, pos->pos().ToInstructionIndex() + 1);
     if (after.IsValid()) return after;
   }
   return LifetimePosition::Invalid();
 }
 
 
 bool IsProgressPossible(const LiveRange* range,
                         const InstructionSequence* code) {
   return range->CanBeSpilled(range->Start()) ||
          GetLastResortSplitPosition(range, code).IsValid();
@@ skipping 27 matching lines @@
   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);
 
   TRACE("Assigning %s to range %d%d.\n", RegisterName(reg_id),
         range->TopLevel()->vreg(), range->relative_id());
   range->set_assigned_register(reg_id);
+  UpdateOperands(range, data());
 }
 
 
 void GreedyAllocator::PreallocateFixedRanges() {
   allocations_.resize(num_registers());
   for (int i = 0; i < num_registers(); i++) {
     allocations_[i] = new (local_zone()) CoalescedLiveRanges(local_zone());
   }
 
   for (LiveRange* fixed_range : GetFixedRegisters()) {
@@ skipping 29 matching lines @@
 }
 
 
 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);
   DCHECK(range->weight() != LiveRange::kInvalidWeight);
 
-  float smallest_weight = LiveRange::kMaxWeight;
-
-  // Seek either the first free register, or, from the set of registers
-  // where the maximum conflict is lower than the candidate's weight, the one
-  // with the smallest such weight.
-  for (int i = 0; i < num_registers(); i++) {
-    float max_conflict_weight = GetMaximumConflictingWeight(i, range);
+  // Can we allocate at the hinted register?
+  if (range->FirstHintPosition(&hinted_reg) != nullptr) {
+    DCHECK(hinted_reg >= 0);
+    float max_conflict_weight = GetMaximumConflictingWeight(hinted_reg, range);
     if (max_conflict_weight == LiveRange::kInvalidWeight) {
-      free_reg = i;
-      break;
-    }
-    if (max_conflict_weight < range->weight() &&
-        max_conflict_weight < smallest_weight) {
-      smallest_weight = max_conflict_weight;
-      evictable_reg = i;
+      free_reg = hinted_reg;
+    } else if (max_conflict_weight < range->weight()) {
+      evictable_reg = hinted_reg;
     }
   }
 
+  if (free_reg < 0 && evictable_reg < 0) {
+    // There was no hinted reg, or we cannot allocate there.
+    float smallest_weight = LiveRange::kMaxWeight;
+
+    // Seek either the first free register, or, from the set of registers
+    // where the maximum conflict is lower than the candidate's weight, the one
+    // with the smallest such weight.
+    for (int i = 0; i < num_registers(); i++) {
+      // Skip unnecessarily re-visiting the hinted register, if any.
+      if (i == hinted_reg) continue;
+      float max_conflict_weight = GetMaximumConflictingWeight(i, range);
+      if (max_conflict_weight == LiveRange::kInvalidWeight) {
+        free_reg = i;
+        break;
+      }
+      if (max_conflict_weight < range->weight() &&
+          max_conflict_weight < smallest_weight) {
+        smallest_weight = max_conflict_weight;
+        evictable_reg = i;
+      }
+    }
+  }
+
   // We have a free register, so we use it.
   if (free_reg >= 0) {
     TRACE("Found free register %s for live range %d:%d.\n",
           RegisterName(free_reg), range->TopLevel()->vreg(),
           range->relative_id());
     AssignRangeToRegister(free_reg, range);
     return;
   }
 
   // We found a register to perform evictions, so we evict and allocate our
@@ skipping 13 matching lines @@
 
 
 void GreedyAllocator::EvictAndRescheduleConflicts(unsigned reg_id,
                                                   const LiveRange* range) {
   auto conflicts = current_allocations(reg_id)->GetConflicts(range);
   for (LiveRange* conflict = conflicts.Current(); conflict != nullptr;
        conflict = conflicts.RemoveCurrentAndGetNext()) {
     DCHECK(conflict->HasRegisterAssigned());
     CHECK(!conflict->TopLevel()->IsFixed());
     conflict->UnsetAssignedRegister();
+    UnsetOperands(conflict, data());
     UpdateWeightAtEviction(conflict);
     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();
@@ skipping 11 matching lines @@
     }
     auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos);
     // If the range already has a spill operand and it doesn't need a
     // register immediately, split it and spill the first part of the range.
     if (pos == nullptr) {
       Spill(range);
     } else if (pos->pos() > range->Start().NextStart()) {
       // Do not spill live range eagerly if use position that can benefit from
       // the register is too close to the start of live range.
       auto split_pos = GetSplitPositionForInstruction(
-          range, data()->code(), pos->pos().ToInstructionIndex());
+          range, pos->pos().ToInstructionIndex());
       // There is no place to split, so we can't split and spill.
       if (!split_pos.IsValid()) continue;
 
       split_pos =
           FindOptimalSplitPos(range->Start().NextFullStart(), split_pos);
 
       Split(range, data(), split_pos);
       Spill(range);
     }
   }
 }
 
 
 void GreedyAllocator::AllocateRegisters() {
   CHECK(scheduler().empty());
   CHECK(allocations_.empty());
 
   TRACE("Begin allocating function %s with the Greedy Allocator\n",
         data()->debug_name());
 
   SplitAndSpillRangesDefinedByMemoryOperand();
   PreallocateFixedRanges();
   ScheduleAllocationCandidates();
 
   while (!scheduler().empty()) {
     AllocationCandidate candidate = scheduler().GetNext();
     TryAllocateCandidate(candidate);
   }
 
-
-  // We do not rely on the hint mechanism used by LinearScan, so no need to
-  // actively update/reset operands until the end.
-  for (auto range : data()->live_ranges()) {
-    if (CanProcessRange(range) && range->HasRegisterAssigned()) {
-      UpdateOperands(range, data());
-    }
-  }
-
   for (size_t i = 0; i < allocations_.size(); ++i) {
     if (!allocations_[i]->empty()) {
       data()->MarkAllocated(mode(), static_cast<int>(i));
     }
   }
   allocations_.clear();
 
   TRACE("End allocating function %s with the Greedy Allocator\n",
         data()->debug_name());
 }
@@ skipping 58 matching lines @@
     scheduler().Schedule(range);
     return;
   }
   SpillRangeAsLastResort(range);
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8