Fix issue 962.

src/lithium-allocator.cc

 // Copyright 2010 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 43 matching lines @@
   }
 
 DEFINE_OPERAND_CACHE(LConstantOperand, CONSTANT_OPERAND)
 DEFINE_OPERAND_CACHE(LStackSlot,       STACK_SLOT)
 DEFINE_OPERAND_CACHE(LDoubleStackSlot, DOUBLE_STACK_SLOT)
 DEFINE_OPERAND_CACHE(LRegister,        REGISTER)
 DEFINE_OPERAND_CACHE(LDoubleRegister,  DOUBLE_REGISTER)
 
 #undef DEFINE_OPERAND_CACHE
 
-
 static inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) {
   return a.Value() < b.Value() ? a : b;
 }
 
 
 static inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) {
   return a.Value() > b.Value() ? a : b;
 }
 
 
@@ skipping 165 matching lines @@
   UsePosition* pos = first_pos_;
   while (pos != NULL && !pos->HasHint()) pos = pos->next();
   return pos;
 }
 
 
 LOperand* LiveRange::CreateAssignedOperand() {
   LOperand* op = NULL;
   if (HasRegisterAssigned()) {
     ASSERT(!IsSpilled());
-    if (assigned_double_) {
+    if (assigned_register_class_ == DOUBLE_REGISTERS) {

[Kevin Millikin (Chromium), 2010/12/10 07:39:19]

Could use your IsDouble() predicate here.

[Vyacheslav Egorov (Chromium), 2010/12/10 14:18:27]

Done.

       op = LDoubleRegister::Create(assigned_register());
     } else {
       op = LRegister::Create(assigned_register());
     }
   } else if (IsSpilled()) {
     ASSERT(!HasRegisterAssigned());
     op = TopLevel()->GetSpillOperand();
     ASSERT(!op->IsUnallocated());
   } else {
     LUnallocated* unalloc = new LUnallocated(LUnallocated::NONE);
@@ skipping 22 matching lines @@
   LifetimePosition start =
       current_interval_ == NULL ? LifetimePosition::Invalid()
                                 : current_interval_->start();
   if (to_start_of->start().Value() > start.Value()) {
     current_interval_ = to_start_of;
   }
 }
 
 
 void LiveRange::SplitAt(LifetimePosition position, LiveRange* result) {
-  ASSERT(Start().Value() <= position.Value());
+  ASSERT(Start().Value() < position.Value());
   ASSERT(result->IsEmpty());
   // Find the last interval that ends before the position. If the
   // position is contained in one of the intervals in the chain, we
   // split that interval and use the first part.
   UseInterval* current = FirstSearchIntervalForPosition(position);
   while (current != NULL) {
     if (current->Contains(position)) {
       current->SplitAt(position);
       break;
     }
@@ skipping 314 matching lines @@
 LiveRange* LAllocator::FixedLiveRangeFor(int index) {
   if (index >= fixed_live_ranges_.length()) {
     fixed_live_ranges_.AddBlock(NULL,
                                 index - fixed_live_ranges_.length() + 1);
   }
 
   LiveRange* result = fixed_live_ranges_[index];
   if (result == NULL) {
     result = new LiveRange(FixedLiveRangeID(index));
     ASSERT(result->IsFixed());
-    result->set_assigned_register(index, false);
+    result->set_assigned_register(index, CPU_REGISTERS);
     fixed_live_ranges_[index] = result;
   }
   return result;
 }
 
 
 LiveRange* LAllocator::FixedDoubleLiveRangeFor(int index) {
   if (index >= fixed_double_live_ranges_.length()) {
     fixed_double_live_ranges_.AddBlock(NULL,
                                 index - fixed_double_live_ranges_.length() + 1);
   }
 
   LiveRange* result = fixed_double_live_ranges_[index];
   if (result == NULL) {
     result = new LiveRange(FixedDoubleLiveRangeID(index));
     ASSERT(result->IsFixed());
-    result->set_assigned_register(index, true);
+    result->set_assigned_register(index, DOUBLE_REGISTERS);
     fixed_double_live_ranges_[index] = result;
   }
   return result;
 }
 
 LiveRange* LAllocator::LiveRangeFor(int index) {
   if (index >= live_ranges_.length()) {
     live_ranges_.AddBlock(NULL, index - live_ranges_.length() + 1);
   }
   LiveRange* result = live_ranges_[index];
@@ skipping 595 matching lines @@
         PrintF("First use is at %d\n", range->first_pos()->pos().Value());
         iterator.Advance();
       }
       ASSERT(!found);
     }
 #endif
   }
 }
 
 
-void LAllocator::AllocateGeneralRegisters() {
-  HPhase phase("Allocate general registers", this);
-  num_registers_ = Register::kNumAllocatableRegisters;
-  mode_ = CPU_REGISTERS;
-  AllocateRegisters();
-}
-
-
 bool LAllocator::SafePointsAreInOrder() const {
   const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps();
   int safe_point = 0;
   for (int i = 0; i < pointer_maps->length(); ++i) {
     LPointerMap* map = pointer_maps->at(i);
     if (safe_point > map->lithium_position()) return false;
     safe_point = map->lithium_position();
   }
   return true;
 }
@@ skipping 111 matching lines @@
           instruction->MarkSpilledDoubleRegister(reg_index, spill_operand);
         } else {
           instruction->MarkSpilledRegister(reg_index, spill_operand);
         }
       }
     }
   }
 }
 
 
+void LAllocator::AllocateGeneralRegisters() {
+  HPhase phase("Allocate general registers", this);
+  num_registers_ = Register::kNumAllocatableRegisters;
+  mode_ = CPU_REGISTERS;
+  AllocateRegisters();
+}
+
+
 void LAllocator::AllocateDoubleRegisters() {
   HPhase phase("Allocate double registers", this);
   num_registers_ = DoubleRegister::kNumAllocatableRegisters;
-  mode_ = XMM_REGISTERS;
+  mode_ = DOUBLE_REGISTERS;
   AllocateRegisters();
 }
 
 
 void LAllocator::AllocateRegisters() {
   ASSERT(mode_ != NONE);
   reusable_slots_.Clear();
 
   for (int i = 0; i < live_ranges_.length(); ++i) {
     if (live_ranges_[i] != NULL) {
-      if (HasDoubleValue(live_ranges_[i]->id()) == (mode_ == XMM_REGISTERS)) {
+      if (RequiredRegisterClass(live_ranges_[i]->id()) == mode_) {
         AddToUnhandledUnsorted(live_ranges_[i]);
       }
     }
   }
   SortUnhandled();
   ASSERT(UnhandledIsSorted());
 
   ASSERT(active_live_ranges_.is_empty());
   ASSERT(inactive_live_ranges_.is_empty());
 
-  if (mode_ == XMM_REGISTERS) {
+  if (mode_ == DOUBLE_REGISTERS) {
     for (int i = 0; i < fixed_double_live_ranges_.length(); ++i) {
       LiveRange* current = fixed_double_live_ranges_.at(i);
       if (current != NULL) {
         AddToInactive(current);
       }
     }
   } else {
     for (int i = 0; i < fixed_live_ranges_.length(); ++i) {
       LiveRange* current = fixed_live_ranges_.at(i);
       if (current != NULL) {
@@ skipping 20 matching lines @@
       UsePosition* pos = current->NextUsePositionRegisterIsBeneficial(next_pos);
       // If the range already has a spill operand and it doesn't need a
       // register immediately, split it and spill the first part of the range.
       if (pos == NULL) {
         Spill(current);
         continue;
       } else if (pos->pos().Value() >
                  current->Start().NextInstruction().Value()) {
         // Do not spill live range eagerly if use position that can benefit from
         // the register is too close to the start of live range.
-        LiveRange* part = Split(current,
-                                current->Start().NextInstruction(),
-                                pos->pos());
-        Spill(current);
-        AddToUnhandledSorted(part);
+        SpillBetween(current, current->Start(), pos->pos());
         ASSERT(UnhandledIsSorted());
         continue;
       }
     }
 
     for (int i = 0; i < active_live_ranges_.length(); ++i) {
       LiveRange* cur_active = active_live_ranges_.at(i);
       if (cur_active->End().Value() <= position.Value()) {
         ActiveToHandled(cur_active);
         --i;  // The live range was removed from the list of active live ranges.
@@ skipping 56 matching lines @@
 }
 
 
 bool LAllocator::HasTaggedValue(int virtual_register) const {
   HValue* value = graph()->LookupValue(virtual_register);
   if (value == NULL) return false;
   return value->representation().IsTagged();
 }
 
 
-bool LAllocator::HasDoubleValue(int virtual_register) const {
+RegistersClass LAllocator::RequiredRegisterClass(int virtual_register) const {
   HValue* value = graph()->LookupValue(virtual_register);
-  if (value == NULL) return false;
-  return value->representation().IsDouble();
+  if (value != NULL && value->representation().IsDouble()) {
+    return DOUBLE_REGISTERS;
+  }
+  return CPU_REGISTERS;
 }
 
 
 void LAllocator::MarkAsCall() {
   current_summary()->MarkAsCall();
 }
 
 
 void LAllocator::RecordDefinition(HInstruction* instr, LUnallocated* operand) {
   operand->set_virtual_register(instr->id());
@@ skipping 160 matching lines @@
 
 
 void LAllocator::InactiveToActive(LiveRange* range) {
   ASSERT(inactive_live_ranges_.Contains(range));
   inactive_live_ranges_.RemoveElement(range);
   active_live_ranges_.Add(range);
   TraceAlloc("Moving live range %d from inactive to active\n", range->id());
 }
 
 
+// TryAllocateFreeReg and AllocateBlockedReg assume this
+// when allocating local arrays.
+STATIC_ASSERT(DoubleRegister::kNumAllocatableRegisters >=
+              Register::kNumAllocatableRegisters);
+
+
 bool LAllocator::TryAllocateFreeReg(LiveRange* current) {
-  LifetimePosition max_pos = LifetimePosition::FromInstructionIndex(
-      chunk_->instructions()->length() + 1);
-  ASSERT(DoubleRegister::kNumAllocatableRegisters >=
-         Register::kNumAllocatableRegisters);
-  EmbeddedVector<LifetimePosition, DoubleRegister::kNumAllocatableRegisters>
-      free_pos(max_pos);
+  LifetimePosition free_until_pos[DoubleRegister::kNumAllocatableRegisters];
+
+  for (int i = 0; i < DoubleRegister::kNumAllocatableRegisters; 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_pos[cur_active->assigned_register()] =
+    free_until_pos[cur_active->assigned_register()] =
         LifetimePosition::FromInstructionIndex(0);
   }
 
   for (int i = 0; i < inactive_live_ranges_.length(); ++i) {
     LiveRange* cur_inactive = inactive_live_ranges_.at(i);
     ASSERT(cur_inactive->End().Value() > current->Start().Value());
     LifetimePosition next_intersection =
         cur_inactive->FirstIntersection(current);
     if (!next_intersection.IsValid()) continue;
     int cur_reg = cur_inactive->assigned_register();
-    free_pos[cur_reg] = Min(free_pos[cur_reg], next_intersection);
+    free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection);
   }
 
-  UsePosition* pos = current->FirstPosWithHint();
-  if (pos != NULL) {
-    LOperand* hint = pos->hint();
+  UsePosition* hinted_use = current->FirstPosWithHint();
+  if (hinted_use != NULL) {
+    LOperand* hint = hinted_use->hint();
     if (hint->IsRegister() || hint->IsDoubleRegister()) {
       int register_index = hint->index();
-      TraceAlloc("Found reg hint %d for live range %d (free [%d, end %d[)\n",
-                 register_index,
-                 current->id(),
-                 free_pos[register_index].Value(),
-                 current->End().Value());
-      if (free_pos[register_index].Value() >= current->End().Value()) {
+      TraceAlloc(
+          "Found reg hint %d (free until [%d) for live range %d (end %d[).\n",
+          register_index,

[Kevin Millikin (Chromium), 2010/12/10 07:39:19]

Maybe it's not helpful here, but there's probably a function to convert the
register index to a string.

[Vyacheslav Egorov (Chromium), 2010/12/10 14:18:27]

Yes, I know. I was just lazy to introduce helper (which is required cause string
depends on mode_).

+          free_until_pos[register_index].Value(),
+          current->id(),
+          current->End().Value());
+
+      // Desired register is free until end of current live range.

[Kevin Millikin (Chromium), 2010/12/10 07:39:19]

The desired....until the end...

[Vyacheslav Egorov (Chromium), 2010/12/10 14:18:27]

Done.

+      if (free_until_pos[register_index].Value() >= current->End().Value()) {
         TraceAlloc("Assigning preferred reg %d to live range %d\n",
                    register_index,
                    current->id());
-        current->set_assigned_register(register_index, mode_ == XMM_REGISTERS);
+        current->set_assigned_register(register_index, mode_);
         return true;
       }
     }
   }
 
-  int max_reg = 0;
+  // Find register that stays free for the longest time.

[Kevin Millikin (Chromium), 2010/12/10 07:39:19]

Find the register

[Vyacheslav Egorov (Chromium), 2010/12/10 14:18:27]

Done.

+  int reg = 0;
   for (int i = 1; i < RegisterCount(); ++i) {
-    if (free_pos[i].Value() > free_pos[max_reg].Value()) {
-      max_reg = i;
+    if (free_until_pos[i].Value() > free_until_pos[reg].Value()) {
+      reg = i;
     }
   }
 
-  if (free_pos[max_reg].InstructionIndex() == 0) {
+  LifetimePosition pos = free_until_pos[reg];
+
+  if (pos.Value() <= current->Start().Value()) {
+    // All registers are blocked.
     return false;
-  } else if (free_pos[max_reg].Value() >= current->End().Value()) {
-    TraceAlloc("Assigning reg %d to live range %d\n", max_reg, current->id());
-    current->set_assigned_register(max_reg, mode_ == XMM_REGISTERS);
-  } else {
-    // Split the interval before first use position of max_reg and never split
-    // it interval at its start position.
-    LifetimePosition pos = free_pos[max_reg];
-    if (pos.Value() <= current->Start().Value()) return false;
-    LiveRange* second_range = Split(current, pos);
-    AddToUnhandledSorted(second_range);
-    current->set_assigned_register(max_reg, mode_ == XMM_REGISTERS);
   }
 
+  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.
+    LiveRange* tail = SplitAt(current, pos);
+    AddToUnhandledSorted(tail);
+  }
+
+
+  // Register reg is available at the range start and is free until
+  // the range end.
+  ASSERT(pos.Value() >= current->End().Value());
+  TraceAlloc("Assigning reg %d to live range %d\n", reg, current->id());
+  current->set_assigned_register(reg, mode_);
+
   return true;
 }
 
 
 void LAllocator::AllocateBlockedReg(LiveRange* current) {
-  LifetimePosition max_pos =
-      LifetimePosition::FromInstructionIndex(
-          chunk_->instructions()->length() + 1);
-  ASSERT(DoubleRegister::kNumAllocatableRegisters >=
-         Register::kNumAllocatableRegisters);
-  EmbeddedVector<LifetimePosition, DoubleRegister::kNumAllocatableRegisters>
-      use_pos(max_pos);
-  EmbeddedVector<LifetimePosition, DoubleRegister::kNumAllocatableRegisters>
-      block_pos(max_pos);
+  UsePosition* register_use = current->NextRegisterPosition(current->Start());
+  if (register_use == NULL) {
+    // There is no use in currect live range that requires register.

[Kevin Millikin (Chromium), 2010/12/10 07:39:19]

the current live range that requires a register

[Vyacheslav Egorov (Chromium), 2010/12/10 14:18:27]

Done.

+    // We can just spill it.
+    Spill(current);
+    return;
+  }
+
+
+  LifetimePosition use_pos[DoubleRegister::kNumAllocatableRegisters];
+  LifetimePosition block_pos[DoubleRegister::kNumAllocatableRegisters];
+
+  for (int i = 0; i < DoubleRegister::kNumAllocatableRegisters; i++) {
+    use_pos[i] = block_pos[i] = LifetimePosition::MaxPosition();
+  }
 
   for (int i = 0; i < active_live_ranges_.length(); ++i) {
     LiveRange* range = active_live_ranges_[i];
     int cur_reg = range->assigned_register();
     if (range->IsFixed() || !range->CanBeSpilled(current->Start())) {
       block_pos[cur_reg] = use_pos[cur_reg] =
           LifetimePosition::FromInstructionIndex(0);
     } else {
       UsePosition* next_use = range->NextUsePositionRegisterIsBeneficial(
           current->Start());
@@ skipping 12 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 max_reg = 0;
+  int reg = 0;
   for (int i = 1; i < RegisterCount(); ++i) {
-    if (use_pos[i].Value() > use_pos[max_reg].Value()) {
-      max_reg = i;
+    if (use_pos[i].Value() > use_pos[reg].Value()) {
+      reg = i;
     }
   }
 
-  UsePosition* first_usage = current->NextRegisterPosition(current->Start());
-  if (first_usage == NULL) {
-    Spill(current);
-  } else if (use_pos[max_reg].Value() < first_usage->pos().Value()) {
-    SplitAndSpill(current, current->Start(), first_usage->pos());
-  } else {
-    if (block_pos[max_reg].Value() < current->End().Value()) {
-      // Split current before blocked position.
-      LiveRange* second_range = Split(current,
-                                      current->Start(),
-                                      block_pos[max_reg]);
-      AddToUnhandledSorted(second_range);
-    }
+  LifetimePosition pos = use_pos[reg];
 
-    current->set_assigned_register(max_reg, mode_ == XMM_REGISTERS);
-    SplitAndSpillIntersecting(current);
+  if (pos.Value() < register_use->pos().Value()) {
+    // All registers are blocked before the first use that requires register.

[Kevin Millikin (Chromium), 2010/12/10 07:39:19]

that requires a register.  Spill the starting part of the 

[Vyacheslav Egorov (Chromium), 2010/12/10 14:18:27]

Done.

+    // Spill starting part of live range upto that use.
+    //
+    // Corner case: first use position is equal to start of range.

[Kevin Millikin (Chromium), 2010/12/10 07:39:19]

the first use...the start of the range

[Vyacheslav Egorov (Chromium), 2010/12/10 14:18:27]

Done.

+    // In this case we have nothing to spill and SpillBetween will just return
+    // this range to list unhandled ones. This means that we have unsatisfieable
+    // register constraints and we have to abort to avoid infinite loop.
+    CHECK(current->Start().Value() < register_use->pos().Value());

[Kevin Millikin (Chromium), 2010/12/10 07:39:19]

We should consider what to do here.  CHECK will crash (fail fast) in product
builds.  We probably don't actually want to do that, and instead bail out safely
and fall back to unoptimized code?

[Vyacheslav Egorov (Chromium), 2010/12/10 14:18:27]

I replaced check with assert.

Yes. Gracefully bailing out on unsatisfiable constraints is my desire.

+    SpillBetween(current, current->Start(), register_use->pos());
+    return;
   }
+
+  if (block_pos[reg].Value() < current->End().Value()) {
+    // Register becomes blocked before current range end. Split before that
+    // position.
+    LiveRange* tail = SplitBetween(current,
+                                   current->Start(),
+                                   block_pos[reg].InstructionStart());
+    AddToUnhandledSorted(tail);
+  }
+
+  // Register reg is not blocked for the whole range.
+  ASSERT(block_pos[reg].Value() >= current->End().Value());
+  TraceAlloc("Assigning reg %d to live range %d\n", reg, current->id());
+  current->set_assigned_register(reg, mode_);
+
+  // This register was not free. Thus we need to find and spill
+  // parts of active and inactive live regions that use the same register
+  // at the same lifetime positions as current.
+  SplitAndSpillIntersecting(current);
 }
 
 
 void LAllocator::SplitAndSpillIntersecting(LiveRange* current) {
   ASSERT(current->HasRegisterAssigned());
   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());
       if (next_pos == NULL) {
-        SplitAndSpill(range, split_pos);
+        SpillAfter(range, split_pos);
       } else {
-        SplitAndSpill(range, split_pos, next_pos->pos());
+        SpillBetween(range, split_pos, next_pos->pos());
       }
       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());
     if (range->assigned_register() == reg && !range->IsFixed()) {
       LifetimePosition next_intersection = range->FirstIntersection(current);
       if (next_intersection.IsValid()) {
         UsePosition* next_pos = range->NextRegisterPosition(current->Start());
         if (next_pos == NULL) {
-          SplitAndSpill(range, split_pos);
+          SpillAfter(range, split_pos);
         } else {
           next_intersection = Min(next_intersection, next_pos->pos());
-          SplitAndSpill(range, split_pos, next_intersection);
+          SpillBetween(range, split_pos, next_intersection);
         }
         InactiveToHandled(range);
         --i;
       }
     }
   }
 }
 
 
-LiveRange* LAllocator::Split(LiveRange* range,
-                             LifetimePosition start,
-                             LifetimePosition end) {
+bool LAllocator::IsBlockBoundary(LifetimePosition pos) {
+  return pos.IsInstructionStart() &&
+      chunk_->instructions()->at(pos.InstructionIndex())->IsLabel();
+}
+
+
+void LAllocator::AddGapMove(int pos, LiveRange* prev, LiveRange* next) {
+  UsePosition* prev_pos = prev->AddUsePosition(
+      LifetimePosition::FromInstructionIndex(pos));
+  UsePosition* next_pos = next->AddUsePosition(
+      LifetimePosition::FromInstructionIndex(pos));
+  LOperand* prev_operand = prev_pos->operand();
+  LOperand* next_operand = next_pos->operand();
+  LGap* gap = chunk_->GetGapAt(pos);
+  gap->GetOrCreateParallelMove(LGap::START)->
+      AddMove(prev_operand, next_operand);
+  next_pos->set_hint(prev_operand);
+}
+
+
+LiveRange* LAllocator::SplitAt(LiveRange* range, LifetimePosition pos) {
   ASSERT(!range->IsFixed());
-  TraceAlloc("Splitting live range %d in position between [%d, %d[\n",
+  TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value());
+
+  if (pos.Value() <= range->Start().Value()) return range;
+
+  LiveRange* result = LiveRangeFor(next_virtual_register_++);
+  range->SplitAt(pos, result);
+  return result;
+}
+
+
+LiveRange* LAllocator::SplitBetween(LiveRange* range,
+                                    LifetimePosition start,
+                                    LifetimePosition end) {
+  ASSERT(!range->IsFixed());
+  TraceAlloc("Splitting live range %d in position between [%d, %d]\n",
              range->id(),
              start.Value(),
              end.Value());
 
-  LifetimePosition split_pos = FindOptimalSplitPos(
-      start, end.PrevInstruction().InstructionEnd());
+  LifetimePosition split_pos = FindOptimalSplitPos(start, end);
   ASSERT(split_pos.Value() >= start.Value());
-  return Split(range, split_pos);
+  return SplitAt(range, split_pos);
 }
 
 
 LifetimePosition LAllocator::FindOptimalSplitPos(LifetimePosition start,
                                                  LifetimePosition end) {
   int start_instr = start.InstructionIndex();
   int end_instr = end.InstructionIndex();
   ASSERT(start_instr <= end_instr);
 
   // We have no choice
   if (start_instr == end_instr) return end;
 
   HBasicBlock* end_block = GetBlock(start);
   HBasicBlock* start_block = GetBlock(end);
 
   if (end_block == start_block) {
     // The interval is split in the same basic block. Split at latest possible
     // position.
     return end;
   }
 
   HBasicBlock* block = end_block;
-  // Move to the most outside loop header.
+  // Find header of outermost loop.
   while (block->parent_loop_header() != NULL &&
       block->parent_loop_header()->block_id() > start_block->block_id()) {
     block = block->parent_loop_header();
   }
 
-  if (block == end_block) {
-    return end;
-  }
+  if (block == end_block) return end;
 
   return LifetimePosition::FromInstructionIndex(
       block->first_instruction_index());
 }
 
 
-bool LAllocator::IsBlockBoundary(LifetimePosition pos) {
-  return pos.IsInstructionStart() &&
-      chunk_->instructions()->at(pos.InstructionIndex())->IsLabel();
+void LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) {
+  LiveRange* second_part = SplitAt(range, pos);
+  Spill(second_part);
 }
 
 
-void LAllocator::AddGapMove(int pos, LiveRange* prev, LiveRange* next) {
-  UsePosition* prev_pos = prev->AddUsePosition(
-      LifetimePosition::FromInstructionIndex(pos));
-  UsePosition* next_pos = next->AddUsePosition(
-      LifetimePosition::FromInstructionIndex(pos));
-  LOperand* prev_operand = prev_pos->operand();
-  LOperand* next_operand = next_pos->operand();
-  LGap* gap = chunk_->GetGapAt(pos);
-  gap->GetOrCreateParallelMove(LGap::START)->
-      AddMove(prev_operand, next_operand);
-  next_pos->set_hint(prev_operand);
-}
+void LAllocator::SpillBetween(LiveRange* range,
+                              LifetimePosition start,
+                              LifetimePosition end) {
+  ASSERT(start.Value() < end.Value());
+  LiveRange* second_part = SplitAt(range, start);
 
+  if (second_part->Start().Value() < end.Value()) {
+    // Split result intersects with [start, end[.
+    // Split it at position between ]start+1, end[, spill middle part
+    // and put the rest to unhandled.
+    LiveRange* third_part = SplitBetween(
+        second_part,
+        second_part->Start().InstructionEnd(),
+        end.PrevInstruction().InstructionEnd());
 
-LiveRange* LAllocator::Split(LiveRange* range, LifetimePosition pos) {
-  ASSERT(!range->IsFixed());
-  TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value());
-  if (pos.Value() <= range->Start().Value()) {
-    return range;
-  }
-  LiveRange* result = LiveRangeFor(next_virtual_register_++);
-  range->SplitAt(pos, result);
-  return result;
-}
+    ASSERT(third_part != second_part);
 
-
-void LAllocator::SplitAndSpill(LiveRange* range,
-                               LifetimePosition start,
-                               LifetimePosition end) {
-  // We have an interval range and want to make sure that it is
-  // spilled at start and at most spilled until end.
-  ASSERT(start.Value() < end.Value());
-  LiveRange* tail_part = Split(range, start);
-  if (tail_part->Start().Value() < end.Value()) {
-    LiveRange* third_part = Split(tail_part,
-                                  tail_part->Start().NextInstruction(),
-                                  end);
-    Spill(tail_part);
-    ASSERT(third_part != tail_part);
+    Spill(second_part);
     AddToUnhandledSorted(third_part);
   } else {
-    AddToUnhandledSorted(tail_part);
+    // Split result does not intersect with [start, end[.
+    // Nothing to spill. Just put split result to unhandled as whole.
+    AddToUnhandledSorted(second_part);
   }
 }
 
 
-void LAllocator::SplitAndSpill(LiveRange* range, LifetimePosition at) {
-  LiveRange* second_part = Split(range, at);
-  Spill(second_part);
-}
-
-
 void LAllocator::Spill(LiveRange* range) {
   ASSERT(!range->IsSpilled());
   TraceAlloc("Spilling live range %d\n", range->id());
   LiveRange* first = range->TopLevel();
 
   if (!first->HasAllocatedSpillOperand()) {
     LOperand* op = TryReuseSpillSlot(range);
-    if (op == NULL) op = chunk_->GetNextSpillSlot(mode_ == XMM_REGISTERS);
+    if (op == NULL) op = chunk_->GetNextSpillSlot(mode_ == DOUBLE_REGISTERS);
     first->SetSpillOperand(op);
   }
   range->MakeSpilled();
 }
 
 
 int LAllocator::RegisterCount() const {
   return num_registers_;
 }
 
 
 #ifdef DEBUG
 
 
 void LAllocator::Verify() const {
   for (int i = 0; i < live_ranges()->length(); ++i) {
     LiveRange* current = live_ranges()->at(i);
     if (current != NULL) current->Verify();
   }
 }
 
 
 #endif
 
 
 } }  // namespace v8::internal