Fix bug introduced by r13960.

src/lithium-allocator.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1528 matching lines @@
         AddToInactive(current);
       }
     }
   }
 
   while (!unhandled_live_ranges_.is_empty()) {
     ASSERT(UnhandledIsSorted());
     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());
 
     if (current->HasAllocatedSpillOperand()) {
       TraceAlloc("Live range %d already has a spill operand\n", current->id());
       LifetimePosition next_pos = position;
       if (IsGapAt(next_pos.InstructionIndex())) {
         next_pos = next_pos.NextInstruction();
       }
@@ skipping 104 matching lines @@
 
 void LAllocator::AddToInactive(LiveRange* range) {
   TraceAlloc("Add live range %d to inactive\n", range->id());
   inactive_live_ranges_.Add(range, zone());
 }
 
 
 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)) {
       TraceAlloc("Add live range %d to unhandled at %d\n", range->id(), i + 1);
       unhandled_live_ranges_.InsertAt(i + 1, range, zone());
       ASSERT(UnhandledIsSorted());
       return;
     }
   }
   TraceAlloc("Add live range %d to unhandled at start\n", range->id());
@@ skipping 310 matching lines @@
   int reg = current->assigned_register();
   LifetimePosition split_pos = current->Start();
   for (int i = 0; i < active_live_ranges_.length(); ++i) {
     LiveRange* range = active_live_ranges_[i];
     if (range->assigned_register() == reg) {
       UsePosition* next_pos = range->NextRegisterPosition(current->Start());
       LifetimePosition spill_pos = FindOptimalSpillingPos(range, split_pos);
       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);
       --i;
     }
   }
 
   for (int i = 0; i < inactive_live_ranges_.length(); ++i) {
     LiveRange* range = inactive_live_ranges_[i];
     ASSERT(range->End().Value() > current->Start().Value());
@@ skipping 93 matching lines @@
 void LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) {
   LiveRange* second_part = SplitRangeAt(range, pos);
   if (!AllocationOk()) return;
   Spill(second_part);
 }
 
 
 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;
 
   if (second_part->Start().Value() < end.Value()) {
     // The split result intersects with [start, end[.
     // Split it at position between ]start+1, end[, spill the middle part
     // 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;
 
     ASSERT(third_part != second_part);
 
     Spill(second_part);
     AddToUnhandledSorted(third_part);
   } else {
     // The split result does not intersect with [start, end[.
     // Nothing to spill. Just put it to unhandled as whole.
@@ skipping 29 matching lines @@
     LiveRange* current = live_ranges()->at(i);
     if (current != NULL) current->Verify();
   }
 }
 
 
 #endif
 
 
 } }  // namespace v8::internal