[turbofan] round robin register picking

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/compiler/linkage.h"
 #include "src/compiler/register-allocator.h"
 #include "src/string-stream.h"
 
 namespace v8 {
 namespace internal {
@@ skipping 508 matching lines @@
       fixed_live_ranges_(this->config()->num_general_registers(), NULL,
                          local_zone()),
       fixed_double_live_ranges_(this->config()->num_double_registers(), NULL,
                                 local_zone()),
       unhandled_live_ranges_(code->VirtualRegisterCount() * 2, local_zone()),
       active_live_ranges_(8, local_zone()),
       inactive_live_ranges_(8, local_zone()),
       reusable_slots_(8, local_zone()),
       mode_(UNALLOCATED_REGISTERS),
       num_registers_(-1),
+      first_register_to_try_(0),
       allocation_ok_(true) {
   DCHECK(this->config()->num_general_registers() <=
          RegisterConfiguration::kMaxGeneralRegisters);
   DCHECK(this->config()->num_double_registers() <=
          RegisterConfiguration::kMaxDoubleRegisters);
   // TryAllocateFreeReg and AllocateBlockedReg assume this
   // when allocating local arrays.
   DCHECK(this->config()->num_double_registers() >=
          this->config()->num_general_registers());
   assigned_registers_ =
@@ skipping 1316 matching lines @@
 
 
 void RegisterAllocator::InactiveToActive(LiveRange* range) {
   DCHECK(inactive_live_ranges_.Contains(range));
   inactive_live_ranges_.RemoveElement(range);
   active_live_ranges_.Add(range, local_zone());
   TraceAlloc("Moving live range %d from inactive to active\n", range->id());
 }
 
 
+// Pick the index of the maximum position, starting at offset start.
+static int MaximalIndex(const LifetimePosition* positions, const uint8_t start,
+                        const int count) {
+  int reg = start % count;

[titzer, 2014/11/19 14:02:08]

On second thought, can we get rid of the modulus? Not the fastest CPU
instruction these days.

+  for (int i = 1; i < count; ++i) {
+    int index = (i + start) % count;
+    if (positions[index].Value() > positions[reg].Value()) {
+      reg = index;
+    }
+  }
+  return reg;
+}
+
+
 bool RegisterAllocator::TryAllocateFreeReg(LiveRange* current) {
   LifetimePosition free_until_pos[RegisterConfiguration::kMaxDoubleRegisters];
 
   for (int i = 0; i < num_registers_; i++) {
     free_until_pos[i] = LifetimePosition::MaxPosition();
   }
 
   for (int i = 0; i < active_live_ranges_.length(); ++i) {
     LiveRange* cur_active = active_live_ranges_.at(i);
     free_until_pos[cur_active->assigned_register()] =
@@ skipping 21 matching lines @@
     // The desired register is free until the end of the current live range.
     if (free_until_pos[register_index].Value() >= current->End().Value()) {
       TraceAlloc("Assigning preferred reg %s to live range %d\n",
                  RegisterName(register_index), current->id());
       SetLiveRangeAssignedRegister(current, register_index);
       return true;
     }
   }
 
   // Find the register which stays free for the longest time.
-  int reg = 0;
-  for (int i = 1; i < RegisterCount(); ++i) {
-    if (free_until_pos[i].Value() > free_until_pos[reg].Value()) {
-      reg = i;
-    }
-  }
-
+  int reg =
+      MaximalIndex(free_until_pos, first_register_to_try_++, RegisterCount());
   LifetimePosition pos = free_until_pos[reg];
 
   if (pos.Value() <= current->Start().Value()) {
     // All registers are blocked.
     return false;
   }
 
   if (pos.Value() < current->End().Value()) {
     // Register reg is available at the range start but becomes blocked before
     // the range end. Split current at position where it becomes blocked.
@@ skipping 54 matching lines @@
     if (!next_intersection.IsValid()) continue;
     int cur_reg = range->assigned_register();
     if (range->IsFixed()) {
       block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection);
       use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]);
     } else {
       use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection);
     }
   }
 
-  int reg = 0;
-  for (int i = 1; i < RegisterCount(); ++i) {
-    if (use_pos[i].Value() > use_pos[reg].Value()) {
-      reg = i;
-    }
-  }
-
+  int reg = MaximalIndex(use_pos, first_register_to_try_++, RegisterCount());
   LifetimePosition pos = use_pos[reg];
 
   if (pos.Value() < register_use->pos().Value()) {
     // All registers are blocked before the first use that requires a register.
     // Spill starting part of live range up to that use.
     SpillBetween(current, current->Start(), register_use->pos());
     return;
   }
 
   if (block_pos[reg].Value() < current->End().Value()) {
@@ skipping 272 matching lines @@
   } else {
     DCHECK(range->Kind() == GENERAL_REGISTERS);
     assigned_registers_->Add(reg);
   }
   range->set_assigned_register(reg, code_zone());
 }
 
 }
 }
 }  // namespace v8::internal::compiler