Merge 6006:6095 from bleeding_edge to experimental/gc branch.

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 278 matching lines @@
 }
 
 
 void LiveRange::SplitAt(LifetimePosition position, LiveRange* result) {
   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);
+
+  // If the split position coincides with the beginning of a use interval
+  // we need to split use positons in a special way.
+  bool split_at_start = false;
+
   while (current != NULL) {
     if (current->Contains(position)) {
       current->SplitAt(position);
       break;
     }
     UseInterval* next = current->next();
-    if (next->start().Value() >= position.Value()) break;
+    if (next->start().Value() >= position.Value()) {
+      split_at_start = (next->start().Value() == position.Value());
+      break;
+    }
     current = next;
   }
 
   // Partition original use intervals to the two live ranges.
   UseInterval* before = current;
   UseInterval* after = before->next();
   result->last_interval_ = (last_interval_ == before)
       ? after            // Only interval in the range after split.
       : last_interval_;  // Last interval of the original range.
   result->first_interval_ = after;
   last_interval_ = before;
 
   // Find the last use position before the split and the first use
   // position after it.
   UsePosition* use_after = first_pos_;
   UsePosition* use_before = NULL;
-  while (use_after != NULL && use_after->pos().Value() <= position.Value()) {
-    use_before = use_after;
-    use_after = use_after->next();
+  if (split_at_start) {
+    // The split position coincides with the beginning of a use interval (the
+    // end of a lifetime hole). Use at this position should be attributed to
+    // the split child because split child owns use interval covering it.
+    while (use_after != NULL && use_after->pos().Value() < position.Value()) {
+      use_before = use_after;
+      use_after = use_after->next();
+    }
+  } else {
+    while (use_after != NULL && use_after->pos().Value() <= position.Value()) {
+      use_before = use_after;
+      use_after = use_after->next();
+    }
   }
 
   // Partition original use positions to the two live ranges.
   if (use_before != NULL) {
     use_before->next_ = NULL;
   } else {
     first_pos_ = NULL;
   }
   result->first_pos_ = use_after;
 
@@ skipping 166 matching lines @@
   UseInterval* a = FirstSearchIntervalForPosition(b->start());
   while (a != NULL && b != NULL) {
     if (a->start().Value() > other->End().Value()) break;
     if (b->start().Value() > End().Value()) break;
     LifetimePosition cur_intersection = a->Intersect(b);
     if (cur_intersection.IsValid()) {
       return cur_intersection;
     }
     if (a->start().Value() < b->start().Value()) {
       a = a->next();
-      if (a == NULL && a->start().Value() > other->End().Value()) break;
+      if (a == NULL || a->start().Value() > other->End().Value()) break;
       AdvanceLastProcessedMarker(a, advance_last_processed_up_to);
     } else {
       b = b->next();
     }
   }
   return LifetimePosition::Invalid();
 }
 
 
 void LAllocator::InitializeLivenessAnalysis() {
@@ skipping 38 matching lines @@
 }
 
 
 void LAllocator::AddInitialIntervals(HBasicBlock* block,
                                      BitVector* live_out) {
   // Add an interval that includes the entire block to the live range for
   // each live_out value.
   LifetimePosition start = LifetimePosition::FromInstructionIndex(
       block->first_instruction_index());
   LifetimePosition end = LifetimePosition::FromInstructionIndex(
-      block->last_instruction_index());
+      block->last_instruction_index()).NextInstruction();
   BitVector::Iterator iterator(live_out);
   while (!iterator.Done()) {
     int operand_index = iterator.Current();
     LiveRange* range = LiveRangeFor(operand_index);
-    if (!range->IsEmpty() &&
-        range->Start().Value() == end.NextInstruction().Value()) {
-      range->AddUseInterval(start, end.NextInstruction());
-    } else {
-      range->AddUseInterval(start, end);
-    }
+    range->AddUseInterval(start, end);
     iterator.Advance();
   }
 }
 
 
 int LAllocator::FixedDoubleLiveRangeID(int index) {
   return -index - 1 - Register::kNumAllocatableRegisters;
 }
 
 
@@ skipping 362 matching lines @@
           LOperand* temp = summary->TempAt(i);
           if (summary->IsCall()) {
             if (temp->IsRegister()) continue;
             if (temp->IsUnallocated()) {
               LUnallocated* temp_unalloc = LUnallocated::cast(temp);
               if (temp_unalloc->HasFixedPolicy()) {
                 continue;
               }
             }
           }
-          Use(block_start_position, curr_position, temp, NULL);
-          Define(curr_position.PrevInstruction(), temp, NULL);
+          Use(block_start_position, curr_position.InstructionEnd(), temp, NULL);
+          Define(curr_position, temp, NULL);
         }
       }
     }
 
     index = index - 1;
   }
 }
 
 
 void LAllocator::ResolvePhis(HBasicBlock* block) {
@@ skipping 832 matching lines @@
     // 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 %s to live range %d\n",
+  TraceAlloc("Assigning free reg %s to live range %d\n",
              RegisterName(reg),
              current->id());
   current->set_assigned_register(reg, mode_);
 
   return true;
 }
 
 
 void LAllocator::AllocateBlockedReg(LiveRange* current) {
   UsePosition* register_use = current->NextRegisterPosition(current->Start());
@@ skipping 69 matching lines @@
     // Register becomes blocked before the 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 %s to live range %d\n",
+  TraceAlloc("Assigning blocked reg %s to live range %d\n",
              RegisterName(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);
 }
 
@@ skipping 176 matching lines @@
     LiveRange* current = live_ranges()->at(i);
     if (current != NULL) current->Verify();
   }
 }
 
 
 #endif
 
 
 } }  // namespace v8::internal