From 102c5170c2cd06db9b16c307bed4c483dbc1e2a4 Mon Sep 17 00:00:00 2001
From: "vegorov@chromium.org"
 <vegorov@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Tue, 16 Apr 2013 11:31:04 +0000
Subject: [PATCH] Fix bug introduced by r13960.

Allocator does not backtrack thus during allocation we must not create an unhandled live
range which starts before the start of the current live range.

If such range is added to the list of unhandled it might see an inconsistent state of active/inactive live-ranges as they are retired to handled as soon as start of the current live range is larger than their end.

Add assertion to catch this kind of bugs early.

TEST=NavierStokes does not fail on ARM

Review URL: https://codereview.chromium.org/14262005

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@14274 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/lithium-allocator.cc | 24 ++++++++++++++++++++++--
 src/lithium-allocator.h  | 13 ++++++++++++-
 2 files changed, 34 insertions(+), 3 deletions(-)

diff --git a/src/lithium-allocator.cc b/src/lithium-allocator.cc
index fa2aa24..7bddef7 100644
--- a/src/lithium-allocator.cc
+++ b/src/lithium-allocator.cc
@@ -1546,6 +1546,9 @@ void LAllocator::AllocateRegisters() {
     LiveRange* current = unhandled_live_ranges_.RemoveLast();
     ASSERT(UnhandledIsSorted());
     LifetimePosition position = current->Start();
+#ifdef DEBUG
+    allocation_finger_ = position;
+#endif
     TraceAlloc("Processing interval %d start=%d\n",
                current->id(),
                position.Value());
@@ -1670,6 +1673,7 @@ void LAllocator::AddToInactive(LiveRange* range) {
 void LAllocator::AddToUnhandledSorted(LiveRange* range) {
   if (range == NULL || range->IsEmpty()) return;
   ASSERT(!range->HasRegisterAssigned() && !range->IsSpilled());
+  ASSERT(allocation_finger_.Value() <= range->Start().Value());
   for (int i = unhandled_live_ranges_.length() - 1; i >= 0; --i) {
     LiveRange* cur_range = unhandled_live_ranges_.at(i);
     if (range->ShouldBeAllocatedBefore(cur_range)) {
@@ -2000,7 +2004,15 @@ void LAllocator::SplitAndSpillIntersecting(LiveRange* current) {
       if (next_pos == NULL) {
         SpillAfter(range, spill_pos);
       } else {
-        SpillBetween(range, spill_pos, next_pos->pos());
+        // When spilling between spill_pos and next_pos ensure that the range
+        // remains spilled at least until the start of the current live range.
+        // This guarantees that we will not introduce new unhandled ranges that
+        // start before the current range as this violates allocation invariant
+        // and will lead to an inconsistent state of active and inactive
+        // live-ranges: ranges are allocated in order of their start positions,
+        // ranges are retired from active/inactive when the start of the
+        // current live-range is larger than their end.
+        SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos());
       }
       if (!AllocationOk()) return;
       ActiveToHandled(range);
@@ -2114,6 +2126,14 @@ void LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) {
 void LAllocator::SpillBetween(LiveRange* range,
                               LifetimePosition start,
                               LifetimePosition end) {
+  SpillBetweenUntil(range, start, start, end);
+}
+
+
+void LAllocator::SpillBetweenUntil(LiveRange* range,
+                                   LifetimePosition start,
+                                   LifetimePosition until,
+                                   LifetimePosition end) {
   CHECK(start.Value() < end.Value());
   LiveRange* second_part = SplitRangeAt(range, start);
   if (!AllocationOk()) return;
@@ -2124,7 +2144,7 @@ void LAllocator::SpillBetween(LiveRange* range,
     // and put the rest to unhandled.
     LiveRange* third_part = SplitBetween(
         second_part,
-        second_part->Start().InstructionEnd(),
+        Max(second_part->Start().InstructionEnd(), until),
         end.PrevInstruction().InstructionEnd());
     if (!AllocationOk()) return;
 
diff --git a/src/lithium-allocator.h b/src/lithium-allocator.h
index 70f3182..8b45531 100644
--- a/src/lithium-allocator.h
+++ b/src/lithium-allocator.h
@@ -536,11 +536,18 @@ class LAllocator BASE_EMBEDDED {
   // Spill the given life range after position pos.
   void SpillAfter(LiveRange* range, LifetimePosition pos);
 
-  // Spill the given life range after position start and up to position end.
+  // Spill the given life range after position [start] and up to position [end].
   void SpillBetween(LiveRange* range,
                     LifetimePosition start,
                     LifetimePosition end);
 
+  // Spill the given life range after position [start] and up to position [end].
+  // Range is guaranteed to be spilled at least until position [until].
+  void SpillBetweenUntil(LiveRange* range,
+                         LifetimePosition start,
+                         LifetimePosition until,
+                         LifetimePosition end);
+
   void SplitAndSpillIntersecting(LiveRange* range);
 
   // If we are trying to spill a range inside the loop try to
@@ -625,6 +632,10 @@ class LAllocator BASE_EMBEDDED {
   // Indicates success or failure during register allocation.
   bool allocation_ok_;
 
+#ifdef DEBUG
+  LifetimePosition allocation_finger_;
+#endif
+
   DISALLOW_COPY_AND_ASSIGN(LAllocator);
 };
 
-- 
2.7.4