[turbofan] remove non-linearity in PopulateReferenceMaps

src/compiler/register-allocator.cc

Index: src/compiler/register-allocator.cc
diff --git a/src/compiler/register-allocator.cc b/src/compiler/register-allocator.cc
index 05bc8ba795c1b46fd59b35f1463b5b999fbb12c0..2072f679c9e9936b9e54fcae6a7c59173071cb07 100644
--- a/src/compiler/register-allocator.cc
+++ b/src/compiler/register-allocator.cc
@@ -3107,6 +3107,7 @@ void ReferenceMapPopulator::PopulateReferenceMaps() {
                 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;
@@ -3119,11 +3120,30 @@ void ReferenceMapPopulator::PopulateReferenceMaps() {
       // 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);

[Jarin, 2015/12/17 08:51:37]

I am wondering whether we could nopt do some sanity check for safepoint
ordering. Could not we DCHECK safe_point_pos >= cur->Start() here? (Actually we
might have to handle the first range separately, i.e. something like
DCHECK(safe_point_pos >= cur->Start() || range == cur).) What do you think?

[Mircea Trofin, 2015/12/17 16:50:57]

Done.

+      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 (!found) {
+        continue;
       }
-      if (cur == nullptr) continue;
 
       // Check if the live range is spilled and the safe point is after
       // the spill position.