Simple register allocation for ARM. Only top of expression...

src/arm/virtual-frame-arm.cc

 // Copyright 2009 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 19 matching lines @@
 #include "codegen-inl.h"
 #include "register-allocator-inl.h"
 #include "scopes.h"
 #include "virtual-frame-inl.h"
 
 namespace v8 {
 namespace internal {
 
 #define __ ACCESS_MASM(masm())
 
-void VirtualFrame::SyncElementBelowStackPointer(int index) {
-  UNREACHABLE();
+void VirtualFrame::PopToR1R0() {
+  VirtualFrame where_to_go = *this;
+  where_to_go.top_of_stack_state_ = R1_R0_TOS;
+  MergeTo(&where_to_go);

[Søren Thygesen Gjesse, 2010/04/07 10:46:51]

Maybe add a comment here saying the r0/r1 TOS state is now "detached" from the
frame.

[Erik Corry, 2010/04/07 12:49:17]

Done.

+  element_count_ -= 2;
+  top_of_stack_state_ = NO_TOS_REGISTERS;
 }
 
 
-void VirtualFrame::SyncElementByPushing(int index) {
-  UNREACHABLE();
+void VirtualFrame::PopToR1() {
+  VirtualFrame where_to_go = *this;
+  where_to_go.top_of_stack_state_ = R1_TOS;
+  MergeTo(&where_to_go);
+  element_count_ -= 1;
+  top_of_stack_state_ = NO_TOS_REGISTERS;
+}
+
+
+void VirtualFrame::PopToR0() {
+  VirtualFrame where_to_go = *this;
+  where_to_go.top_of_stack_state_ = R0_TOS;
+  MergeTo(&where_to_go);
+  element_count_ -= 1;
+  top_of_stack_state_ = NO_TOS_REGISTERS;
 }
 
 
 void VirtualFrame::MergeTo(VirtualFrame* expected) {

[Kasper Lund, 2010/04/07 08:09:50]

Do you have good tests of this function? Full coverage?

[Erik Corry, 2010/04/07 12:49:17]

No.  The coverage tool for covering code generated by a given line isn't working
right now.  I read it through once more and found a bug in it.  In the slightly
longer term this needs to be done differently anyway and this code will go away.

-  // ARM frames are currently always in memory.
-  ASSERT(Equals(expected));
-}
-
-
-void VirtualFrame::MergeMoveRegistersToMemory(VirtualFrame* expected) {
-  UNREACHABLE();
-}
-
-
-void VirtualFrame::MergeMoveRegistersToRegisters(VirtualFrame* expected) {
-  UNREACHABLE();
-}
-
-
-void VirtualFrame::MergeMoveMemoryToRegisters(VirtualFrame* expected) {
-  UNREACHABLE();
+  if (Equals(expected)) return;
+  switch (top_of_stack_state_ * 5 + expected->top_of_stack_state_) {

[Søren Thygesen Gjesse, 2010/04/07 10:46:51]

Maybe add a macro for (one_state * 5 + another_state) and use the actual
constant instead of 5. Maybe use shift of 3 instead.

[Erik Corry, 2010/04/07 12:49:17]

On ARM multiplying by 5 should be the same speed as shifting by 3 (it's a
shifted add instruction) and it keeps the table dense.  Created a macro.

+    case NO_TOS_REGISTERS * 5 + NO_TOS_REGISTERS:
+      break;
+    case NO_TOS_REGISTERS * 5 + R0_TOS:
+      __ pop(r0);
+      break;
+    case NO_TOS_REGISTERS * 5 + R1_TOS:
+      __ pop(r1);
+      break;
+    case NO_TOS_REGISTERS * 5 + R1_R0_TOS:
+      __ pop(r0);
+      __ pop(r1);
+      break;
+    case NO_TOS_REGISTERS * 5 + R0_R1_TOS:
+      __ pop(r0);
+      __ pop(r1);
+      break;
+    case R0_TOS * 5 + NO_TOS_REGISTERS:
+      __ push(r0);
+      break;
+    case R0_TOS * 5 + R0_TOS:
+      break;
+    case R0_TOS * 5 + R1_TOS:
+      __ mov(r1, r0);
+      break;
+    case R0_TOS * 5 + R1_R0_TOS:
+      __ pop(r1);
+      break;
+    case R0_TOS * 5 + R0_R1_TOS:
+      __ mov(r1, r0);
+      __ pop(r0);
+      break;
+    case R1_TOS * 5 + NO_TOS_REGISTERS:
+      __ push(r1);
+      break;
+    case R1_TOS * 5 + R0_TOS:
+      __ mov(r0, r1);
+      break;
+    case R1_TOS * 5 + R1_TOS:
+      break;
+    case R1_TOS * 5 + R1_R0_TOS:
+      __ mov(r0, r1);
+      __ pop(r1);
+      break;
+    case R1_TOS * 5 + R0_R1_TOS:
+      __ pop(r0);
+      break;
+    case R1_R0_TOS * 5 + NO_TOS_REGISTERS:
+      __ push(r1);
+      __ push(r0);
+      break;
+    case R1_R0_TOS * 5 + R0_TOS:
+      __ push(r1);
+      break;
+    case R1_R0_TOS * 5 + R1_TOS:
+      __ push(r1);
+      __ mov(r1, r0);
+      break;
+    case R1_R0_TOS * 5 + R1_R0_TOS:
+      break;
+    case R1_R0_TOS * 5 + R0_R1_TOS:

[Søren Thygesen Gjesse, 2010/04/07 07:53:37]

MacroAssembler::Swap?

[Erik Corry, 2010/04/07 12:49:17]

Done.

+      __ eor(r0, r0, Operand(r1));
+      __ eor(r1, r1, Operand(r0));
+      __ eor(r0, r0, Operand(r1));
+      break;
+    case R0_R1_TOS * 5 + NO_TOS_REGISTERS:
+      __ push(r0);
+      __ push(r1);
+      break;
+    case R0_R1_TOS * 5 + R0_TOS:
+      __ push(r0);
+      __ mov(r0, r1);
+      break;
+    case R0_R1_TOS * 5 + R1_TOS:
+      __ push(r0);
+      break;
+    case R0_R1_TOS * 5 + R1_R0_TOS:
+      __ eor(r0, r0, Operand(r1));

[Kasper Lund, 2010/04/07 08:09:50]

Swap again.

[Erik Corry, 2010/04/07 12:49:17]

Done.

+      __ eor(r1, r1, Operand(r0));
+      __ eor(r0, r0, Operand(r1));
+      break;
+    case R0_R1_TOS * 5 + R0_R1_TOS:
+      break;

[Søren Thygesen Gjesse, 2010/04/07 10:46:51]

default with UNREACHABLE()?

[Erik Corry, 2010/04/07 12:49:17]

Done.

+  }
+  ASSERT(register_allocation_map_ == expected->register_allocation_map_);
 }
 
 
 void VirtualFrame::Enter() {
   Comment cmnt(masm(), "[ Enter JS frame");
 
 #ifdef DEBUG
   // Verify that r1 contains a JS function.  The following code relies
   // on r2 being available for use.
   if (FLAG_debug_code) {
     Label map_check, done;
     __ tst(r1, Operand(kSmiTagMask));
     __ b(ne, &map_check);
     __ stop("VirtualFrame::Enter - r1 is not a function (smi check).");
     __ bind(&map_check);
     __ CompareObjectType(r1, r2, r2, JS_FUNCTION_TYPE);
     __ b(eq, &done);
     __ stop("VirtualFrame::Enter - r1 is not a function (map check).");
     __ bind(&done);
   }
 #endif  // DEBUG
 
   // We are about to push four values to the frame.
   Adjust(4);
   __ stm(db_w, sp, r1.bit() | cp.bit() | fp.bit() | lr.bit());
   // Adjust FP to point to saved FP.
   __ add(fp, sp, Operand(2 * kPointerSize));
-  cgen()->allocator()->Unuse(r1);
-  cgen()->allocator()->Unuse(lr);
 }
 
 
 void VirtualFrame::Exit() {
   Comment cmnt(masm(), "[ Exit JS frame");
   // Record the location of the JS exit code for patching when setting
   // break point.
   __ RecordJSReturn();
 
   // Drop the execution stack down to the frame pointer and restore the caller
@@ skipping 38 matching lines @@
   // Call the stub if lower.
   masm()->mov(pc,
               Operand(reinterpret_cast<intptr_t>(stub.GetCode().location()),
                       RelocInfo::CODE_TARGET),
               LeaveCC,
               lo);
 }
 
 
 
-void VirtualFrame::SaveContextRegister() {
-  UNIMPLEMENTED();
-}
-
-
-void VirtualFrame::RestoreContextRegister() {
-  UNIMPLEMENTED();
-}
-
-
 void VirtualFrame::PushReceiverSlotAddress() {
   UNIMPLEMENTED();
 }
 
 
-int VirtualFrame::InvalidateFrameSlotAt(int index) {
-  UNIMPLEMENTED();
-  return kIllegalIndex;
-}
-
-
-void VirtualFrame::TakeFrameSlotAt(int index) {
-  UNIMPLEMENTED();
-}
-
-
-void VirtualFrame::StoreToFrameSlotAt(int index) {
-  UNIMPLEMENTED();
-}
-
-
 void VirtualFrame::PushTryHandler(HandlerType type) {
   // Grow the expression stack by handler size less one (the return
   // address in lr is already counted by a call instruction).
   Adjust(kHandlerSize - 1);
   __ PushTryHandler(IN_JAVASCRIPT, type);
 }
 
 
 void VirtualFrame::CallRuntime(Runtime::Function* f, int arg_count) {
   Forget(arg_count);
@@ skipping 43 matching lines @@
       break;
     default:
       UNREACHABLE();
       break;
   }
   Forget(dropped_args);
   ASSERT(cgen()->HasValidEntryRegisters());
   __ Call(code, rmode);
 }
 
 

[Søren Thygesen Gjesse, 2010/04/07 10:46:51]

Lining up the states in a comment here could be helpful.

  NO_TOS_REGISTERS
  R0_TOS
  R1_TOS
  R0_R1_TOS
  R1_R0_TOS

[Erik Corry, 2010/04/07 12:49:17]

Done.

+const bool VirtualFrame::kR0InUse[TOS_STATES] =
+    { false, true, false, true, true };
+const bool VirtualFrame::kR1InUse[TOS_STATES] =
+    { false, false, true, true, true };
+const int VirtualFrame::kVirtualElements[TOS_STATES] = { 0, 1, 1, 2, 2 };
+const VirtualFrame::TopOfStack VirtualFrame::kPopState[TOS_STATES] =
+    { NO_TOS_REGISTERS, NO_TOS_REGISTERS, NO_TOS_REGISTERS, R0_TOS, R1_TOS };
+const VirtualFrame::TopOfStack VirtualFrame::kPushState[TOS_STATES] =
+    { R0_TOS, R0_R1_TOS, R1_R0_TOS, R1_R0_TOS, R0_R1_TOS };
+const Register VirtualFrame::kTopRegister[TOS_STATES] = { r0, r0, r1, r1, r0 };
+const Register VirtualFrame::kBottomRegister[TOS_STATES] =
+    { r0, r0, r1, r0, r1 };
+const Register VirtualFrame::kAllocatedRegisters[
+    VirtualFrame::kNumberOfAllocatedRegisters] = { r2, r3, r4, r5, r6 };
+
+
+bool VirtualFrame::SpilledScope::is_spilled_ = false;
+
+
 void VirtualFrame::Drop(int count) {
   ASSERT(count >= 0);
   ASSERT(height() >= count);
-  int num_virtual_elements = (element_count() - 1) - stack_pointer_;
-
-  // Emit code to lower the stack pointer if necessary.
-  if (num_virtual_elements < count) {
-    int num_dropped = count - num_virtual_elements;
-    stack_pointer_ -= num_dropped;
-    __ add(sp, sp, Operand(num_dropped * kPointerSize));
+  // Discard elements from the virtual frame and free any registers.
+  int num_virtual_elements = kVirtualElements[top_of_stack_state_];
+  while (num_virtual_elements > 0) {
+    Pop();
+    num_virtual_elements--;
+    count--;
+    if (count == 0) return;
   }
-
-  // Discard elements from the virtual frame and free any registers.
+  if (count == 0) return;
+  __ add(sp, sp, Operand(count * kPointerSize));
   element_count_ -= count;
 }
 
 
-Result VirtualFrame::Pop() {
-  UNIMPLEMENTED();
-  return Result();
+void VirtualFrame::Pop() {
+  if (top_of_stack_state_ == NO_TOS_REGISTERS) {
+    __ add(sp, sp, Operand(kPointerSize));
+  } else {
+    top_of_stack_state_ = kPopState[top_of_stack_state_];
+  }
+  element_count_--;
 }
 
 
 void VirtualFrame::EmitPop(Register reg) {
-  ASSERT(stack_pointer_ == element_count() - 1);
-  stack_pointer_--;
+  ASSERT(!is_used(reg));
+  if (top_of_stack_state_ == NO_TOS_REGISTERS) {
+    __ pop(reg);
+  } else {
+    __ mov(reg, kTopRegister[top_of_stack_state_]);
+    top_of_stack_state_ = kPopState[top_of_stack_state_];
+  }
   element_count_--;
-  __ pop(reg);
+}
+
+
+Register VirtualFrame::Peek() {
+  AssertIsNotSpilled();
+  if (top_of_stack_state_ == NO_TOS_REGISTERS) {
+    top_of_stack_state_ = kPushState[top_of_stack_state_];
+    Register answer = kTopRegister[top_of_stack_state_];
+    __ pop(answer);
+    return answer;
+  } else {
+    return kTopRegister[top_of_stack_state_];
+  }
+}
+
+
+Register VirtualFrame::PopToRegister(Register but_not_to_this_one) {

[Søren Thygesen Gjesse, 2010/04/07 10:46:51]

Maybe assert that but_not_to_this_one is one of the tos registers (otherwise it
does not make much sense, and is probably a mistake).

[Erik Corry, 2010/04/07 12:49:17]

Done.

+  AssertIsNotSpilled();
+  element_count_--;
+  if (top_of_stack_state_ == NO_TOS_REGISTERS) {
+    if (but_not_to_this_one.is(r0)) {
+      __ pop(r1);
+      return r1;
+    } else {
+      __ pop(r0);
+      return r0;
+    }
+  } else {

[Søren Thygesen Gjesse, 2010/04/07 10:46:51]

Isn't but_not_to_this_one ignored in the else part?

[Erik Corry, 2010/04/07 12:49:17]

Yes, because it never happens.

+    Register answer = kTopRegister[top_of_stack_state_];
+    top_of_stack_state_ = kPopState[top_of_stack_state_];

[Søren Thygesen Gjesse, 2010/04/07 10:46:51]

ASSERT(!answer.is(but_not_to_this_one));

[Erik Corry, 2010/04/07 12:49:17]

Done.

+    return answer;
+  }
 }
 
 
 void VirtualFrame::EmitPush(Register reg) {
-  ASSERT(stack_pointer_ == element_count() - 1);
   element_count_++;
-  stack_pointer_++;
-  __ push(reg);
+  if (SpilledScope::is_spilled()) {
+    __ push(reg);
+    return;
+  }
+  if (top_of_stack_state_ == NO_TOS_REGISTERS) {
+    if (reg.is(r0)) {
+      top_of_stack_state_ = R0_TOS;
+      return;
+    }
+    if (reg.is(r1)) {
+      top_of_stack_state_ = R1_TOS;
+      return;
+    }
+  }

[Søren Thygesen Gjesse, 2010/04/07 10:46:51]

Maybe add some kind of helper function "EnsureOneFreeTOSRegister", as kind of
the same code used here is also used in a couple of places below.

[Erik Corry, 2010/04/07 12:49:17]

Done.

+  if (kVirtualElements[top_of_stack_state_] == kMaxTOSRegisters) {
+    __ push(kBottomRegister[top_of_stack_state_]);
+  }
+  top_of_stack_state_ = kPushState[top_of_stack_state_];
+  Register dest = kTopRegister[top_of_stack_state_];
+  if (!dest.is(reg)) {
+    __ mov(dest, reg);
+  }
+}
+
+
+Register VirtualFrame::GetTOSRegister() {
+  if (SpilledScope::is_spilled()) return r0;
+
+  if (kVirtualElements[top_of_stack_state_] == kMaxTOSRegisters) {
+    Register answer = kBottomRegister[top_of_stack_state_];
+    __ push(answer);
+    top_of_stack_state_ = kPushState[top_of_stack_state_];
+    top_of_stack_state_ = kPopState[top_of_stack_state_];
+    return answer;
+  }
+
+  return kTopRegister[kPushState[top_of_stack_state_]];
+}
+
+
+void VirtualFrame::EmitPush(MemOperand operand) {
+  element_count_++;
+  if (SpilledScope::is_spilled()) {
+    __ ldr(r0, operand);
+    __ push(r0);
+    return;
+  }
+  if (kVirtualElements[top_of_stack_state_] == kMaxTOSRegisters) {
+    __ push(kBottomRegister[top_of_stack_state_]);
+  }
+  top_of_stack_state_ = kPushState[top_of_stack_state_];
+  __ ldr(kTopRegister[top_of_stack_state_], operand);
 }
 
 
 void VirtualFrame::EmitPushMultiple(int count, int src_regs) {
-  ASSERT(stack_pointer_ == element_count() - 1);
+  ASSERT(SpilledScope::is_spilled());
   Adjust(count);
   __ stm(db_w, sp, src_regs);
 }
 
 
 #undef __
 
 } }  // namespace v8::internal