[turbofan] Greedy allocator refactoring.

src/compiler/register-allocator.cc

 // Copyright 2014 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/base/adapters.h"
 #include "src/compiler/linkage.h"
 #include "src/compiler/register-allocator.h"
 #include "src/string-stream.h"
 
 namespace v8 {
@@ skipping 219 matching lines @@
 struct LiveRange::SpillAtDefinitionList : ZoneObject {
   SpillAtDefinitionList(int gap_index, InstructionOperand* operand,
                         SpillAtDefinitionList* next)
       : gap_index(gap_index), operand(operand), next(next) {}
   const int gap_index;
   InstructionOperand* const operand;
   SpillAtDefinitionList* const next;
 };
 
 
+const float LiveRange::kInvalidWeight = -1;
+const float LiveRange::kMaxWeight = std::numeric_limits<float>::max();
+
+
 LiveRange::LiveRange(int id, MachineType machine_type)
     : id_(id),
       spill_start_index_(kMaxInt),
       bits_(0),
       last_interval_(nullptr),
       first_interval_(nullptr),
       first_pos_(nullptr),
       parent_(nullptr),
       next_(nullptr),
       spill_operand_(nullptr),
       spills_at_definition_(nullptr),
       current_interval_(nullptr),
       last_processed_use_(nullptr),
-      current_hint_position_(nullptr) {
+      current_hint_position_(nullptr),
+      size_(kInvalidSize),
+      weight_(kInvalidWeight) {
   DCHECK(AllocatedOperand::IsSupportedMachineType(machine_type));
   bits_ = SpillTypeField::encode(SpillType::kNoSpillType) |
           AssignedRegisterField::encode(kUnassignedRegister) |
           MachineTypeField::encode(machine_type);
 }
 
 
 void LiveRange::Verify() const {
   // Walk the positions, verifying that each is in an interval.
   auto interval = first_interval_;
@@ skipping 288 matching lines @@
   // to the use that no longer belongs to this live range.
   last_processed_use_ = nullptr;
   current_interval_ = nullptr;
 
   // Link the new live range in the chain before any of the other
   // ranges linked from the range before the split.
   result->parent_ = (parent_ == nullptr) ? this : parent_;
   result->next_ = next_;
   next_ = result;
 
+  // Invalidate size and weight of this range. The child range has them
+  // invalid at construction.
+  size_ = kInvalidSize;
+  weight_ = kInvalidWeight;
 #ifdef DEBUG
   Verify();
   result->Verify();
 #endif
 }
 
 
 // This implements an ordering on live ranges so that they are ordered by their
 // start positions.  This is needed for the correctness of the register
 // allocation algorithm.  If two live ranges start at the same offset then there
@@ skipping 170 matching lines @@
       if (a == nullptr || a->start() > other->End()) break;
       AdvanceLastProcessedMarker(a, advance_last_processed_up_to);
     } else {
       b = b->next();
     }
   }
   return LifetimePosition::Invalid();
 }
 
 
+unsigned LiveRange::GetSize() {
+  if (size_ == kInvalidSize) {
+    size_ = 0;
+    for (auto interval = first_interval(); interval != nullptr;
+         interval = interval->next()) {
+      size_ += (interval->end().value() - interval->start().value());
+    }
+  }
+
+  return static_cast<unsigned>(size_);
+}
+
+
 static bool AreUseIntervalsIntersecting(UseInterval* interval1,
                                         UseInterval* interval2) {
   while (interval1 != nullptr && interval2 != nullptr) {
     if (interval1->start() < interval2->start()) {
       if (interval1->end() > interval2->start()) {
         return true;
       }
       interval1 = interval1->next();
     } else {
       if (interval2->end() > interval1->start()) {
@@ skipping 1083 matching lines @@
   range->Spill();
 }
 
 
 const ZoneVector<LiveRange*>& RegisterAllocator::GetFixedRegisters() const {
   return mode() == DOUBLE_REGISTERS ? data()->fixed_double_live_ranges()
                                     : data()->fixed_live_ranges();
 }
 
 
+const char* RegisterAllocator::RegisterName(int allocation_index) const {
+  if (mode() == GENERAL_REGISTERS) {
+    return data()->config()->general_register_name(allocation_index);
+  } else {
+    return data()->config()->double_register_name(allocation_index);
+  }
+}
+
+
 LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data,
                                          RegisterKind kind, Zone* local_zone)
     : RegisterAllocator(data, kind),
       unhandled_live_ranges_(local_zone),
       active_live_ranges_(local_zone),
       inactive_live_ranges_(local_zone) {
   unhandled_live_ranges().reserve(
       static_cast<size_t>(code()->VirtualRegisterCount() * 2));
   active_live_ranges().reserve(8);
   inactive_live_ranges().reserve(8);
@@ skipping 86 matching lines @@
 
     bool result = TryAllocateFreeReg(current);
     if (!result) AllocateBlockedReg(current);
     if (current->HasRegisterAssigned()) {
       AddToActive(current);
     }
   }
 }
 
 
-const char* LinearScanAllocator::RegisterName(int allocation_index) const {
-  if (mode() == GENERAL_REGISTERS) {
-    return data()->config()->general_register_name(allocation_index);
-  } else {
-    return data()->config()->double_register_name(allocation_index);
-  }
-}
-
-
 void LinearScanAllocator::SetLiveRangeAssignedRegister(LiveRange* range,
                                                        int reg) {
   data()->MarkAllocated(range->kind(), reg);
   range->set_assigned_register(reg);
   range->SetUseHints(reg);
   if (range->is_phi()) {
     data()->GetPhiMapValueFor(range->id())->set_assigned_register(reg);
   }
 }
 
@@ skipping 881 matching lines @@
     auto eliminate = moves->PrepareInsertAfter(move);
     to_insert.push_back(move);
     if (eliminate != nullptr) to_eliminate.push_back(eliminate);
   }
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8