[turbofan] Separate LiveRange and TopLevelLiveRange concepts

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(LiveRange* range, RegisterAllocationData* data) {
+void UpdateOperands(TopLevelLiveRange* range, RegisterAllocationData* data) {
   int reg_id = range->assigned_register();
   range->SetUseHints(reg_id);
   if (range->is_phi()) {
-    data->GetPhiMapValueFor(range->id())->set_assigned_register(reg_id);
+    data->GetPhiMapValueFor(range)->set_assigned_register(reg_id);
   }
 }
 
 
 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 = data->NewChildRangeFor(range);
-  range->SplitAt(pos, result, data->allocation_zone());
+  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();
 
@@ skipping 57 matching lines @@
 
 AllocationCandidate AllocationScheduler::GetNext() {
   DCHECK(!queue_.empty());
   AllocationCandidate ret = queue_.top();
   queue_.pop();
   return ret;
 }
 
 
 void AllocationScheduler::Schedule(LiveRange* range) {
-  TRACE("Scheduling live range %d.\n", range->id());
+  TRACE("Scheduling live range %d:%d.\n", range->TopLevel()->vreg(),
+        range->relative_id());
   queue_.push(AllocationCandidate(range));
 }
 
 GreedyAllocator::GreedyAllocator(RegisterAllocationData* data,
                                  RegisterKind kind, Zone* local_zone)
     : RegisterAllocator(data, kind),
       local_zone_(local_zone),
       allocations_(local_zone),
       scheduler_(local_zone) {}
 
 
 void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
-  TRACE("Assigning register %s to live range %d\n", RegisterName(reg_id),
-        range->id());
+  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\n", RegisterName(reg_id), range->id());
+  TRACE("Assigning %s to range %d%d.\n", RegisterName(reg_id),
+        range->TopLevel()->vreg(), range->relative_id());
   range->set_assigned_register(reg_id);
 }
 
 
 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()) {
     if (fixed_range != nullptr) {
       DCHECK_EQ(mode(), fixed_range->kind());
-      DCHECK(fixed_range->IsFixed());
+      DCHECK(fixed_range->TopLevel()->IsFixed());
 
       int reg_nr = fixed_range->assigned_register();
       EnsureValidRangeWeight(fixed_range);
       AllocateRegisterToRange(reg_nr, fixed_range);
     }
   }
 }
 
 
 void GreedyAllocator::ScheduleAllocationCandidates() {
   for (auto range : data()->live_ranges()) {
     if (CanProcessRange(range) && !range->spilled()) {
       scheduler().Schedule(range);
     }
   }
 }
 
 
 void GreedyAllocator::TryAllocateCandidate(
     const AllocationCandidate& candidate) {
   // At this point, this is just a live range. TODO: groups.
   TryAllocateLiveRange(candidate.live_range());
 }
 
 
 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\n", range->id());
+  TRACE("Attempting to allocate live range %d:%d.\n", range->TopLevel()->vreg(),
+        range->relative_id());
   int free_reg = -1;
   int evictable_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);
     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\n", RegisterName(free_reg),
-          range->id());
+    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
   // candidate.
   if (evictable_reg >= 0) {
-    TRACE("Found evictable register %s for live range %d\n",
-          RegisterName(free_reg), range->id());
+    TRACE("Found evictable register %s for live range %d:%d.\n",
+          RegisterName(free_reg), range->TopLevel()->vreg(),
+          range->relative_id());
     EvictAndRescheduleConflicts(evictable_reg, range);
     AssignRangeToRegister(evictable_reg, range);
     return;
   }
 
   // The range needs to be split or spilled.
   SplitOrSpillBlockedRange(range);
 }
 
 
 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->IsFixed());
+    CHECK(!conflict->TopLevel()->IsFixed());
     conflict->UnsetAssignedRegister();
     UpdateWeightAtEviction(conflict);
     scheduler().Schedule(conflict);
-    TRACE("Evicted range %d.\n", conflict->id());
+    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];
     if (!CanProcessRange(range)) continue;
     if (range->HasNoSpillType()) continue;
 
     LifetimePosition start = range->Start();
-    TRACE("Live range %d is defined by a spill operand.\n", range->id());
+    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();
     }
     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()) {
@@ skipping 64 matching lines @@
   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->IsFixed()) {
+  if (range->TopLevel()->IsFixed()) {
     range->set_weight(LiveRange::kMaxWeight);
     return;
   }
   if (!IsProgressPossible(range, code())) {
     range->set_weight(LiveRange::kMaxWeight);
     return;
   }
 
   float use_count = 0.0;
   for (auto pos = range->first_pos(); pos != nullptr; pos = pos->next()) {
@@ skipping 23 matching lines @@
     scheduler().Schedule(range);
     return;
   }
   SpillRangeAsLastResort(range);
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8