Merge 6800:7180 from the bleeding edge branch to the 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 460 matching lines @@
     if (use_pos->HasOperand()) {
       ASSERT(op->IsRegister() || op->IsDoubleRegister() ||
              !use_pos->RequiresRegister());
       use_pos->operand()->ConvertTo(op->kind(), op->index());
     }
     use_pos = use_pos->next();
   }
 }
 
 
-UsePosition* LiveRange::AddUsePosition(LifetimePosition pos) {
-  return AddUsePosition(pos, CreateAssignedOperand());
-}
-
-
 bool LiveRange::CanCover(LifetimePosition position) const {
   if (IsEmpty()) return false;
   return Start().Value() <= position.Value() &&
          position.Value() < End().Value();
 }
 
 
 bool LiveRange::Covers(LifetimePosition position) {
   if (!CanCover(position)) return false;
   UseInterval* start_search = FirstSearchIntervalForPosition(position);
@@ skipping 27 matching lines @@
       if (a == NULL || a->start().Value() > other->End().Value()) break;
       AdvanceLastProcessedMarker(a, advance_last_processed_up_to);
     } else {
       b = b->next();
     }
   }
   return LifetimePosition::Invalid();
 }
 
 
+LAllocator::LAllocator(int num_values, HGraph* graph)
+    : chunk_(NULL),
+      live_in_sets_(graph->blocks()->length()),
+      live_ranges_(num_values * 2),
+      fixed_live_ranges_(NULL),
+      fixed_double_live_ranges_(NULL),
+      unhandled_live_ranges_(num_values * 2),
+      active_live_ranges_(8),
+      inactive_live_ranges_(8),
+      reusable_slots_(8),
+      next_virtual_register_(num_values),
+      first_artificial_register_(num_values),
+      mode_(NONE),
+      num_registers_(-1),
+      graph_(graph),
+      has_osr_entry_(false) {}
+
+
 void LAllocator::InitializeLivenessAnalysis() {
   // Initialize the live_in sets for each block to NULL.
   int block_count = graph_->blocks()->length();
   live_in_sets_.Initialize(block_count);
   live_in_sets_.AddBlock(NULL, block_count);
 }
 
 
 BitVector* LAllocator::ComputeLiveOut(HBasicBlock* block) {
   // Compute live out for the given block, except not including backward
@@ skipping 73 matching lines @@
     LInstruction* instr = InstructionAt(pos);
     if (instr->HasPointerMap()) {
       instr->pointer_map()->RecordPointer(operand);
     }
   }
   return operand;
 }
 
 
 LiveRange* LAllocator::FixedLiveRangeFor(int index) {
-  if (index >= fixed_live_ranges_.length()) {
-    fixed_live_ranges_.AddBlock(NULL,
-                                index - fixed_live_ranges_.length() + 1);
-  }
-
+  ASSERT(index < Register::kNumAllocatableRegisters);
   LiveRange* result = fixed_live_ranges_[index];
   if (result == NULL) {
     result = new LiveRange(FixedLiveRangeID(index));
     ASSERT(result->IsFixed());
     result->set_assigned_register(index, GENERAL_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);
-  }
-
+  ASSERT(index < DoubleRegister::kNumAllocatableRegisters);
   LiveRange* result = fixed_double_live_ranges_[index];
   if (result == NULL) {
     result = new LiveRange(FixedDoubleLiveRangeID(index));
     ASSERT(result->IsFixed());
     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];
   if (result == NULL) {
     result = new LiveRange(index);
     live_ranges_[index] = result;
   }
   return result;
@@ skipping 424 matching lines @@
     LOperand* pred_op = pred_cover->CreateAssignedOperand();
     LOperand* cur_op = cur_cover->CreateAssignedOperand();
     if (!pred_op->Equals(cur_op)) {
       LGap* gap = NULL;
       if (block->predecessors()->length() == 1) {
         gap = GapAt(block->first_instruction_index());
       } else {
         ASSERT(pred->end()->SecondSuccessor() == NULL);
         gap = GetLastGap(pred);
 
+        // We are going to insert a move before the branch instruction.
+        // Some branch instructions (e.g. loops' back edges)
+        // can potentially cause a GC so they have a pointer map.
+        // By insterting a move we essentially create a copy of a
+        // value which is invisible to PopulatePointerMaps(), because we store
+        // it into a location different from the operand of a live range
+        // covering a branch instruction.
+        // Thus we need to manually record a pointer.
         if (HasTaggedValue(range->id())) {
           LInstruction* branch = InstructionAt(pred->last_instruction_index());
           if (branch->HasPointerMap()) {
             branch->pointer_map()->RecordPointer(cur_op);
           }
         }
       }
       gap->GetOrCreateParallelMove(LGap::START)->AddMove(pred_op, cur_op);
     }
   }
@@ skipping 152 matching lines @@
     }
 
 #ifdef DEBUG
     if (block_id == 0) {
       BitVector::Iterator iterator(live);
       bool found = false;
       while (!iterator.Done()) {
         found = true;
         int operand_index = iterator.Current();
         PrintF("Function: %s\n",
-               *graph_->info()->function()->debug_name()->ToCString());
+               *chunk_->info()->function()->debug_name()->ToCString());
         PrintF("Value %d used before first definition!\n", operand_index);
         LiveRange* range = LiveRangeFor(operand_index);
         PrintF("First use is at %d\n", range->first_pos()->pos().Value());
         iterator.Advance();
       }
       ASSERT(!found);
     }
 #endif
   }
 }
@@ skipping 141 matching lines @@
 void LAllocator::AllocateDoubleRegisters() {
   HPhase phase("Allocate double registers", this);
   num_registers_ = DoubleRegister::kNumAllocatableRegisters;
   mode_ = DOUBLE_REGISTERS;
   AllocateRegisters();
 }
 
 
 void LAllocator::AllocateRegisters() {
   ASSERT(mode_ != NONE);
-  reusable_slots_.Clear();
+  ASSERT(unhandled_live_ranges_.is_empty());
 
   for (int i = 0; i < live_ranges_.length(); ++i) {
     if (live_ranges_[i] != NULL) {
       if (RequiredRegisterKind(live_ranges_[i]->id()) == mode_) {
         AddToUnhandledUnsorted(live_ranges_[i]);
       }
     }
   }
   SortUnhandled();
   ASSERT(UnhandledIsSorted());
 
+  ASSERT(reusable_slots_.is_empty());
   ASSERT(active_live_ranges_.is_empty());
   ASSERT(inactive_live_ranges_.is_empty());
 
   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);
       }
     }
@@ skipping 64 matching lines @@
     bool result = TryAllocateFreeReg(current);
     if (!result) {
       AllocateBlockedReg(current);
     }
 
     if (current->HasRegisterAssigned()) {
       AddToActive(current);
     }
   }
 
-  active_live_ranges_.Clear();
-  inactive_live_ranges_.Clear();
+  reusable_slots_.Rewind(0);
+  active_live_ranges_.Rewind(0);
+  inactive_live_ranges_.Rewind(0);
 }
 
 
 void LAllocator::Setup() {
   LConstantOperand::SetupCache();
   LStackSlot::SetupCache();
   LDoubleStackSlot::SetupCache();
   LRegister::SetupCache();
   LDoubleRegister::SetupCache();
 }
@@ skipping 537 matching lines @@
     LiveRange* current = live_ranges()->at(i);
     if (current != NULL) current->Verify();
   }
 }
 
 
 #endif
 
 
 } }  // namespace v8::internal