Begin counting references to registers, both in the frame and out....

src/virtual-frame-ia32.cc

 // Copyright 2008 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 23 matching lines @@
 namespace v8 { namespace internal {
 
 #define __ masm_->
 
 // -------------------------------------------------------------------------
 // VirtualFrame implementation.
 
 // On entry to a function, the virtual frame already contains the receiver,
 // the parameters, and a return address.  All frame elements are in memory.
 VirtualFrame::VirtualFrame(CodeGenerator* cgen)
-    : masm_(cgen->masm()),
+    : cgen_(cgen),
+      masm_(cgen->masm()),
       elements_(0),
       parameter_count_(cgen->scope()->num_parameters()),
       local_count_(0),
       stack_pointer_(parameter_count_ + 1),  // 0-based index of TOS.
       frame_pointer_(kIllegalIndex) {
+  FrameElement memory_element;
   for (int i = 0; i < parameter_count_ + 2; i++) {
-    elements_.Add(FrameElement());
+    elements_.Add(memory_element);
   }
 }
 
 
 // When cloned, a frame is a deep copy of the original.
 VirtualFrame::VirtualFrame(VirtualFrame* original)
-    : masm_(original->masm_),
+    : cgen_(original->cgen_),
+      masm_(original->masm_),
       elements_(original->elements_.length()),
       parameter_count_(original->parameter_count_),
       local_count_(original->local_count_),
       stack_pointer_(original->stack_pointer_),
-      frame_pointer_(original->frame_pointer_) {
+      frame_pointer_(original->frame_pointer_),
+      frame_registers_(original->frame_registers_) {
   // Copy all the elements from the original.
   for (int i = 0; i < original->elements_.length(); i++) {
     elements_.Add(original->elements_[i]);
   }
 }
 
 
 // Modify the state of the virtual frame to match the actual frame by adding
 // extra in-memory elements to the top of the virtual frame.  The extra
 // elements will be externally materialized on the actual frame (eg, by
@@ skipping 13 matching lines @@
 // removing elements from the top of the virtual frame.  The elements will
 // be externally popped from the actual frame (eg, by a runtime call).  No
 // code is emitted.
 void VirtualFrame::Forget(int count) {
   ASSERT(count >= 0);
   ASSERT(stack_pointer_ == elements_.length() - 1);
   ASSERT(elements_.length() >= count);
 
   stack_pointer_ -= count;
   for (int i = 0; i < count; i++) {
-    elements_.RemoveLast();
+    FrameElement last = elements_.RemoveLast();
+    if (last.is_register()) {
+      Unuse(last.reg());
+    }
   }
 }
 
 
+void VirtualFrame::Use(Register reg) {
+  frame_registers_.Use(reg);
+  cgen_->allocator()->Use(reg);
+}
+
+
+void VirtualFrame::Unuse(Register reg) {
+  frame_registers_.Unuse(reg);
+  cgen_->allocator()->Unuse(reg);
+}
+
+
 // Clear the dirty bit for the element at a given index.  We can only
 // allocate space in the actual frame for the virtual element immediately
 // above the stack pointer.
 void VirtualFrame::SyncElementAt(int index) {
   FrameElement element = elements_[index];
 
-  if (element.is_dirty()) {
+  if (!element.is_synced()) {
     if (index <= stack_pointer_) {
       // Write elements below the stack pointer to their (already allocated)
       // actual frame location.
       if (element.is_constant()) {
         __ Set(Operand(ebp, fp_relative(index)), Immediate(element.handle()));
       } else {
         ASSERT(element.is_register());
         __ mov(Operand(ebp, fp_relative(index)), element.reg());
       }
     } else {
       // Push elements above the stack pointer to allocate space and sync
       // them.  Space should have already been allocated in the actual frame
       // for all the elements below this one.
       ASSERT(index == stack_pointer_ + 1);
       stack_pointer_++;
       if (element.is_constant()) {
         __ push(Immediate(element.handle()));
       } else {
         ASSERT(element.is_register());
         __ push(element.reg());
       }
     }
+
+    elements_[index].set_sync();
   }
 }
 
 
+// Spill any register if possible, making its reference count zero.
+Register VirtualFrame::SpillAnyRegister() {
+  // Find the leftmost (ordered by register code), least
+  // internally-referenced register whose internal reference count matches
+  // its external reference count (so that spilling it from the frame frees
+  // it for use).
+  int min_count = kMaxInt;
+  int best_register_code = no_reg.code();
+
+  for (int i = 0; i < RegisterFile::kNumRegisters; i++) {
+    int count = frame_registers_.count(i);
+    if (count < min_count && count == cgen_->allocator()->count(i)) {
+      min_count = count;
+      best_register_code = i;
+    }
+  }
+
+  if (best_register_code != no_reg.code()) {
+    // Spill all occurrences of the register.  There are min_count
+    // occurrences, stop when we've spilled them all to avoid syncing
+    // elements unnecessarily.
+    int i = 0;
+    while (min_count > 0) {
+      ASSERT(i < elements_.length());
+      if (elements_[i].is_register() &&
+          elements_[i].reg().code() == best_register_code) {
+        // Found an instance of the best_register being used in the frame.
+        // Spill it.
+        SpillElementAt(i);
+        min_count--;
+      } else {
+        if (i > stack_pointer_) {
+          // Make sure to materialize elements on the virtual frame in
+          // memory.  We rely on this to spill occurrences of the register
+          // lying above the current virtual stack pointer.
+          SyncElementAt(i);
+        }
+      }
+    }
+  }
+
+  Register result = { best_register_code };
+  return result;
+}
+
+
 // Make the type of the element at a given index be MEMORY.  We can only
 // allocate space in the actual frame for the virtual element immediately
 // above the stack pointer.
 void VirtualFrame::SpillElementAt(int index) {
   SyncElementAt(index);
   // The element is now in memory.
+  if (elements_[index].is_register()) {
+    Unuse(elements_[index].reg());
+  }
   elements_[index] = FrameElement();
 }
 
 
+// Clear the dirty bits for all elements.
+void VirtualFrame::SyncAll() {
+  for (int i = 0; i < elements_.length(); i++) {
+    SyncElementAt(i);
+  }
+}
+
+
 // Make the type of all elements be MEMORY.
 void VirtualFrame::SpillAll() {
   for (int i = 0; i < elements_.length(); i++) {
     SpillElementAt(i);
   }
 }
 
 
 void VirtualFrame::PrepareForCall(int frame_arg_count) {
   ASSERT(height() >= frame_arg_count);
@@ skipping 24 matching lines @@
   // We cannot merge to a frame that has constants as elements, because an
   // arbitrary frame might not have constants in those locations.
   //
   // We cannot merge to a frame that has registers as elements because we
   // haven't implemented merging for such frames yet.
   SpillAll();
 }
 
 
 void VirtualFrame::MergeTo(VirtualFrame* expected) {
+  ASSERT(cgen_ == expected->cgen_);
   ASSERT(masm_ == expected->masm_);
   ASSERT(elements_.length() == expected->elements_.length());
   ASSERT(parameter_count_ == expected->parameter_count_);
   ASSERT(local_count_ == expected->local_count_);
   ASSERT(frame_pointer_ == expected->frame_pointer_);
 
   // Mergable frames do not have constants and they do not (currently) have
   // registers.  They are always fully spilled, so the only thing needed to
   // make this frame match the expected one is to spill everything.
   //
   // TODO(): Implement a non-stupid way of merging frames.
   SpillAll();
 
   ASSERT(stack_pointer_ == expected->stack_pointer_);
 }
 
 
 void VirtualFrame::Enter() {
+  // Registers live on entry: esp, ebp, esi, edi.
   Comment cmnt(masm_, "[ Enter JS frame");
   EmitPush(ebp);
 
   frame_pointer_ = stack_pointer_;
   __ mov(ebp, Operand(esp));
 
   // Store the context and the function in the frame.
-  FrameElement context(esi);
-  context.clear_dirty();
-  elements_.Add(context);
-  stack_pointer_++;
-  __ push(esi);
+  Push(esi);
+  // The frame owns the register reference now.
+  cgen_->allocator()->Unuse(esi);
 
-  FrameElement function(edi);
-  function.clear_dirty();
-  elements_.Add(function);
-  stack_pointer_++;
-  __ push(edi);
-
-  // Clear the function slot when generating debug code.
-  if (FLAG_debug_code) {
-    SpillElementAt(stack_pointer_);
-    __ Set(edi, Immediate(reinterpret_cast<int>(kZapValue)));
-  }
+  Push(edi);
+  cgen_->allocator()->Unuse(edi);
 }
 
 
 void VirtualFrame::Exit() {
   Comment cmnt(masm_, "[ Exit JS frame");
   // Record the location of the JS exit code for patching when setting
   // break point.
   __ RecordJSReturn();
 
   // Avoid using the leave instruction here, because it is too
   // short. We need the return sequence to be a least the size of a
   // call instruction to support patching the exit code in the
   // debugger. See VisitReturnStatement for the full return sequence.
   __ mov(esp, Operand(ebp));
   stack_pointer_ = frame_pointer_;
   for (int i = elements_.length() - 1; i > stack_pointer_; i--) {
-    elements_.RemoveLast();
+    FrameElement last = elements_.RemoveLast();
+    if (last.is_register()) {
+      Unuse(last.reg());
+    }
   }
 
   frame_pointer_ = kIllegalIndex;
   EmitPop(ebp);
 }
 
 
 void VirtualFrame::AllocateStackSlots(int count) {
   ASSERT(height() == 0);
   local_count_ = count;
 
   if (count > 0) {
     Comment cmnt(masm_, "[ Allocate space for locals");
     // The locals are constants (the undefined value), but we sync them with
     // the actual frame to allocate space for spilling them.
-    FrameElement initial_value(Factory::undefined_value());
-    initial_value.clear_dirty();
-    __ Set(eax, Immediate(Factory::undefined_value()));
+    SyncAll();
+    Handle<Object> undefined = Factory::undefined_value();
+    FrameElement initial_value(undefined, FrameElement::SYNCED);
+    Register tmp = cgen_->allocator()->Allocate();
+    __ Set(tmp, Immediate(undefined));
     for (int i = 0; i < count; i++) {
       elements_.Add(initial_value);
       stack_pointer_++;
-      __ push(eax);
+      __ push(tmp);
     }
+    cgen_->allocator()->Unuse(tmp);
   }
 }
 
 
 void VirtualFrame::PushTryHandler(HandlerType type) {
   // Grow the expression stack by handler size less two (the return address
   // is already pushed by a call instruction, and PushTryHandler from the
   // macro assembler will leave the top of stack in the eax register to be
   // pushed separately).
   Adjust(kHandlerSize - 2);
@@ skipping 35 matching lines @@
   PrepareForCall(frame_arg_count);
   __ call(code, rmode);
 }
 
 
 void VirtualFrame::Drop(int count) {
   ASSERT(height() >= count);
 
   // Discard elements above the stack pointer.
   while (count > 0 && stack_pointer_ < elements_.length() - 1) {
-    elements_.RemoveLast();
+    FrameElement last = elements_.RemoveLast();
+    if (last.is_register()) {
+      Unuse(last.reg());
+    }
   }
 
   // Discard the rest of the elements and lower the stack pointer.
   Forget(count);
   if (count > 0) {
     __ add(Operand(esp), Immediate(count * kPointerSize));
   }
 }
 
 
@@ skipping 27 matching lines @@
 void VirtualFrame::EmitPush(Operand operand) {
   ASSERT(stack_pointer_ == elements_.length() - 1);
   elements_.Add(FrameElement());
   stack_pointer_++;
   __ push(operand);
 }
 
 
 void VirtualFrame::EmitPush(Immediate immediate) {
   ASSERT(stack_pointer_ == elements_.length() - 1);
-  elements_.Add(FrameElement());
+  FrameElement memory_element;
+  elements_.Add(memory_element);
   stack_pointer_++;
   __ push(immediate);
 }
 
 
+void VirtualFrame::Push(Register reg) {
+  FrameElement register_element(reg, FrameElement::NOT_SYNCED);
+  Use(reg);
+  elements_.Add(register_element);
+}
+
+
+void VirtualFrame::Push(Handle<Object> value) {
+  FrameElement constant_element(value, FrameElement::NOT_SYNCED);
+  elements_.Add(constant_element);
+}
+
+
 #undef __
 
 } }  // namespace v8::internal