[turbofan] remove non-linearity in PopulateReferenceMaps

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 3079 matching lines @@
       if (range->HasSpillOperand()) {
         spill_operand = *range->GetSpillOperand();
       } else {
         spill_operand = range->GetSpillRangeOperand();
       }
       DCHECK(spill_operand.IsStackSlot());
       DCHECK_EQ(MachineRepresentation::kTagged,
                 AllocatedOperand::cast(spill_operand).representation());
     }
 
+    LiveRange* cur = range;
     // Step through the safe points to see whether they are in the range.
     for (auto it = first_it; it != reference_maps->end(); ++it) {
       auto map = *it;
       int safe_point = map->instruction_position();
 
       // The safe points are sorted so we can stop searching here.
       if (safe_point - 1 > end) break;
 
       // Advance to the next active range that covers the current
       // safe point position.
       auto safe_point_pos =
           LifetimePosition::InstructionFromInstructionIndex(safe_point);
-      LiveRange* cur = range;
-      while (cur != nullptr && !cur->Covers(safe_point_pos)) {
-        cur = cur->next();
+
+      // Search for the child range (cur) that covers safe_point_pos. If we
+      // don't find it before the children pass safe_point_pos, keep cur at
+      // the last child, because the next safe_point_pos may be covered by cur.
+      // This may happen if cur has more than one interval, and the current
+      // safe_point_pos is in between intervals.
+      // For that reason, cur may be at most the last child.
+      DCHECK_NOT_NULL(cur);
+      DCHECK(safe_point_pos >= cur->Start() || range == cur);
+      bool found = false;
+      while (!found) {
+        if (cur->Covers(safe_point_pos)) {
+          found = true;
+        } else {
+          LiveRange* next = cur->next();
+          if (next == nullptr || next->Start() > safe_point_pos) {
+            break;
+          }
+          cur = next;
+        }
       }
-      if (cur == nullptr) continue;
+
+      if (!found) {
+        continue;
+      }
 
       // Check if the live range is spilled and the safe point is after
       // the spill position.
       int spill_index = range->IsSpilledOnlyInDeferredBlocks()
                             ? cur->Start().ToInstructionIndex()
                             : range->spill_start_index();
 
       if (!spill_operand.IsInvalid() && safe_point >= spill_index) {
         TRACE("Pointer for range %d (spilled at %d) at safe point %d\n",
               range->vreg(), spill_index, safe_point);
@@ skipping 312 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