diff --git a/src/asm_support.h b/src/asm_support.h
index b2f8126..0a8489c 100644
--- a/src/asm_support.h
+++ b/src/asm_support.h
@@ -27,7 +27,6 @@
 #if defined(__arm__)
 #define rSUSPEND r4
 #define rSELF r9
-#define rLR r14
 // Offset of field Thread::suspend_count_ verified in InitCpu
 #define THREAD_FLAGS_OFFSET 0
 // Offset of field Thread::exception_ verified in InitCpu
diff --git a/src/debugger.cc b/src/debugger.cc
index a75cd8c..77a9252 100644
--- a/src/debugger.cc
+++ b/src/debugger.cc
@@ -1558,7 +1558,7 @@
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
   struct CountStackDepthVisitor : public StackVisitor {
     CountStackDepthVisitor(const ManagedStack* stack,
-                           const std::vector<InstrumentationStackFrame>* instrumentation_stack)
+                           const std::deque<InstrumentationStackFrame>* instrumentation_stack)
         : StackVisitor(stack, instrumentation_stack, NULL), depth(0) {}
 
     bool VisitFrame() {
@@ -1585,10 +1585,12 @@
   return GetStackDepth(DecodeThread(soa, threadId));
 }
 
-JDWP::JdwpError Dbg::GetThreadFrames(JDWP::ObjectId thread_id, size_t start_frame, size_t frame_count, JDWP::ExpandBuf* buf) {
+JDWP::JdwpError Dbg::GetThreadFrames(JDWP::ObjectId thread_id, size_t start_frame,
+                                     size_t frame_count, JDWP::ExpandBuf* buf) {
   class GetFrameVisitor : public StackVisitor {
    public:
-    GetFrameVisitor(const ManagedStack* stack, const std::vector<InstrumentationStackFrame>* instrumentation_stack,
+    GetFrameVisitor(const ManagedStack* stack,
+                    const std::deque<InstrumentationStackFrame>* instrumentation_stack,
                     size_t start_frame, size_t frame_count, JDWP::ExpandBuf* buf)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
         : StackVisitor(stack, instrumentation_stack, NULL), depth_(0),
@@ -1627,7 +1629,8 @@
   ScopedObjectAccessUnchecked soa(Thread::Current());
   MutexLock mu(soa.Self(), *Locks::thread_list_lock_);
   Thread* thread = DecodeThread(soa, thread_id);  // Caller already checked thread is suspended.
-  GetFrameVisitor visitor(thread->GetManagedStack(), thread->GetInstrumentationStack(), start_frame, frame_count, buf);
+  GetFrameVisitor visitor(thread->GetManagedStack(), thread->GetInstrumentationStack(),
+                          start_frame, frame_count, buf);
   visitor.WalkStack();
   return JDWP::ERR_NONE;
 }
@@ -1695,7 +1698,8 @@
 }
 
 struct GetThisVisitor : public StackVisitor {
-  GetThisVisitor(const ManagedStack* stack, const std::vector<InstrumentationStackFrame>* instrumentation_stack,
+  GetThisVisitor(const ManagedStack* stack,
+                 const std::deque<InstrumentationStackFrame>* instrumentation_stack,
                  Context* context, JDWP::FrameId frameId)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
       : StackVisitor(stack, instrumentation_stack, context), this_object(NULL), frame_id(frameId) {}
@@ -1758,7 +1762,8 @@
 void Dbg::GetLocalValue(JDWP::ObjectId threadId, JDWP::FrameId frameId, int slot, JDWP::JdwpTag tag,
                         uint8_t* buf, size_t width) {
   struct GetLocalVisitor : public StackVisitor {
-    GetLocalVisitor(const ManagedStack* stack, const std::vector<InstrumentationStackFrame>* instrumentation_stack,
+    GetLocalVisitor(const ManagedStack* stack,
+                    const std::deque<InstrumentationStackFrame>* instrumentation_stack,
                     Context* context, JDWP::FrameId frameId, int slot, JDWP::JdwpTag tag,
                     uint8_t* buf, size_t width)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
@@ -1894,7 +1899,7 @@
 void Dbg::SetLocalValue(JDWP::ObjectId threadId, JDWP::FrameId frameId, int slot, JDWP::JdwpTag tag,
                         uint64_t value, size_t width) {
   struct SetLocalVisitor : public StackVisitor {
-    SetLocalVisitor(const ManagedStack* stack, const std::vector<InstrumentationStackFrame>* instrumentation_stack, Context* context,
+    SetLocalVisitor(const ManagedStack* stack, const std::deque<InstrumentationStackFrame>* instrumentation_stack, Context* context,
                     JDWP::FrameId frame_id, int slot, JDWP::JdwpTag tag, uint64_t value,
                     size_t width)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
@@ -2193,7 +2198,7 @@
 
   struct SingleStepStackVisitor : public StackVisitor {
     SingleStepStackVisitor(const ManagedStack* stack,
-                           const std::vector<InstrumentationStackFrame>* instrumentation_stack)
+                           const std::deque<InstrumentationStackFrame>* instrumentation_stack)
         EXCLUSIVE_LOCKS_REQUIRED(Locks::breakpoint_lock_)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
         : StackVisitor(stack, instrumentation_stack, NULL) {
@@ -3179,7 +3184,8 @@
 
 struct AllocRecordStackVisitor : public StackVisitor {
   AllocRecordStackVisitor(const ManagedStack* stack,
-                          const std::vector<InstrumentationStackFrame>* instrumentation_stack, AllocRecord* record)
+                          const std::deque<InstrumentationStackFrame>* instrumentation_stack,
+                          AllocRecord* record)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
       : StackVisitor(stack, instrumentation_stack, NULL), record(record), depth(0) {}
 
diff --git a/src/instrumentation.cc b/src/instrumentation.cc
index 28f8cb2..bcf7c5d 100644
--- a/src/instrumentation.cc
+++ b/src/instrumentation.cc
@@ -72,28 +72,83 @@
   return true;
 }
 
-static void InstrumentationRestoreStack(Thread* self, void*) NO_THREAD_SAFETY_ANALYSIS {
-  struct RestoreStackVisitor : public StackVisitor {
-    RestoreStackVisitor(Thread* self)
-        : StackVisitor(self->GetManagedStack(), self->GetInstrumentationStack(), NULL), self_(self) {}
+void InstrumentationInstallStack(Thread* self, void* arg)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  struct InstallStackVisitor : public StackVisitor {
+    InstallStackVisitor(Thread* self, uintptr_t instrumentation_exit_pc)
+        : StackVisitor(self->GetManagedStack(), self->GetInstrumentationStack(), NULL),
+          self_(self), instrumentation_exit_pc_(instrumentation_exit_pc) {}
 
-    virtual bool VisitFrame() {
+    virtual bool VisitFrame() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+      if (GetCurrentQuickFrame() == NULL) {
+        return true;  // Ignore shadow frames.
+      }
+      AbstractMethod* m = GetMethod();
+      if (m == NULL) {
+        return true; // Ignore upcalls.
+      }
+      if (m->GetDexMethodIndex() == DexFile::kDexNoIndex16) {
+        return true;  // Ignore unresolved methods since they will be instrumented after resolution.
+      }
+      uintptr_t pc = GetReturnPc();
+      InstrumentationStackFrame instrumentation_frame(m, pc, GetFrameId());
+      self_->PushBackInstrumentationStackFrame(instrumentation_frame);
+      SetReturnPc(instrumentation_exit_pc_);
+      return true;  // Continue.
+    }
+    Thread* const self_;
+    const uintptr_t instrumentation_exit_pc_;
+  };
+  uintptr_t instrumentation_exit_pc = GetInstrumentationExitPc();
+  InstallStackVisitor visitor(self, instrumentation_exit_pc);
+  visitor.WalkStack(true);
+  Trace* trace = reinterpret_cast<Trace*>(arg);
+  if (trace != NULL) {
+    std::deque<InstrumentationStackFrame>::const_reverse_iterator it =
+        self->GetInstrumentationStack()->rbegin();
+    std::deque<InstrumentationStackFrame>::const_reverse_iterator end =
+        self->GetInstrumentationStack()->rend();
+    for (; it != end; ++it) {
+      trace->LogMethodTraceEvent(self, (*it).method_, Trace::kMethodTraceEnter);
+    }
+  }
+}
+
+static void InstrumentationRestoreStack(Thread* self, void*)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  struct RestoreStackVisitor : public StackVisitor {
+    RestoreStackVisitor(Thread* self, uintptr_t instrumentation_exit_pc)
+        : StackVisitor(self->GetManagedStack(), self->GetInstrumentationStack(), NULL),
+          self_(self), instrumentation_exit_pc_(instrumentation_exit_pc) {}
+
+    virtual bool VisitFrame() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
       if (self_->IsInstrumentationStackEmpty()) {
         return false;  // Stop.
       }
+      AbstractMethod* m = GetMethod();
+      if (m == NULL) {
+        return true;  // Ignore upcalls.
+      }
       uintptr_t pc = GetReturnPc();
-      if (IsInstrumentationExitPc(pc)) {
+      if (pc == instrumentation_exit_pc_) {
         InstrumentationStackFrame instrumentation_frame = self_->PopInstrumentationStackFrame();
         SetReturnPc(instrumentation_frame.return_pc_);
-        CHECK(GetMethod() == instrumentation_frame.method_);
+        CHECK(m == instrumentation_frame.method_);
+        CHECK_EQ(GetFrameId(), instrumentation_frame.frame_id_);
+        Runtime* runtime = Runtime::Current();
+        if (runtime->IsMethodTracingActive()) {
+          Trace* trace = runtime->GetInstrumentation()->GetTrace();
+          trace->LogMethodTraceEvent(self_, m, Trace::kMethodTraceExit);
+        }
       }
       return true;  // Continue.
     }
-
-    Thread* self_;
+    Thread* const self_;
+    const uintptr_t instrumentation_exit_pc_;
   };
-  RestoreStackVisitor visitor(self);
-  visitor.WalkStack();
+  uintptr_t instrumentation_exit_pc = GetInstrumentationExitPc();
+  RestoreStackVisitor visitor(self, instrumentation_exit_pc);
+  visitor.WalkStack(true);
 }
 
 Instrumentation::~Instrumentation() {
@@ -101,7 +156,11 @@
 }
 
 void Instrumentation::InstallStubs() {
+  Thread* self = Thread::Current();
+  Locks::thread_list_lock_->AssertNotHeld(self);
   Runtime::Current()->GetClassLinker()->VisitClasses(InstallStubsClassVisitor, NULL);
+  MutexLock mu(self, *Locks::thread_list_lock_);
+  Runtime::Current()->GetThreadList()->ForEach(InstrumentationInstallStack, GetTrace());
 }
 
 void Instrumentation::UninstallStubs() {
diff --git a/src/instrumentation.h b/src/instrumentation.h
index b17e020..00060ce 100644
--- a/src/instrumentation.h
+++ b/src/instrumentation.h
@@ -35,12 +35,13 @@
 uint32_t InstrumentationMethodUnwindFromCode(Thread* self);
 
 struct InstrumentationStackFrame {
-  InstrumentationStackFrame(AbstractMethod* method, uintptr_t return_pc)
-      : method_(method), return_pc_(return_pc) {
+  InstrumentationStackFrame() : method_(NULL), return_pc_(0), frame_id_(0) {}
+  InstrumentationStackFrame(AbstractMethod* method, uintptr_t return_pc, size_t frame_id)
+      : method_(method), return_pc_(return_pc), frame_id_(frame_id) {
   }
-
   AbstractMethod* method_;
   uintptr_t return_pc_;
+  size_t frame_id_;
 };
 
 class Instrumentation {
@@ -49,7 +50,7 @@
   ~Instrumentation();
 
   // Replaces code of each method with a pointer to a stub for method tracing.
-  void InstallStubs();
+  void InstallStubs() LOCKS_EXCLUDED(Locks::thread_list_lock_);
 
   // Restores original code for each method and fixes the return values of each thread's stack.
   void UninstallStubs() LOCKS_EXCLUDED(Locks::thread_list_lock_);
diff --git a/src/interpreter/interpreter.cc b/src/interpreter/interpreter.cc
index e425ee8..bff9f37 100644
--- a/src/interpreter/interpreter.cc
+++ b/src/interpreter/interpreter.cc
@@ -546,11 +546,11 @@
 }
 
 static JValue Execute(Thread* self, MethodHelper& mh, const DexFile::CodeItem* code_item,
-                      ShadowFrame& shadow_frame) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+                      ShadowFrame& shadow_frame, JValue result_register)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
   const uint16_t* insns = code_item->insns_;
   const Instruction* inst = Instruction::At(insns + shadow_frame.GetDexPC());
   bool entry = (inst->GetDexPc(insns) == 0);
-  JValue result_register;
   while (true) {
     CheckSuspend(self);
     uint32_t dex_pc = inst->GetDexPc(insns);
@@ -1846,7 +1846,7 @@
     }
   }
   if (LIKELY(!method->IsNative())) {
-    JValue r = Execute(self, mh, code_item, *shadow_frame.get());
+    JValue r = Execute(self, mh, code_item, *shadow_frame.get(), JValue());
     if (result != NULL) {
       *result = r;
     }
@@ -1862,5 +1862,12 @@
   self->PopShadowFrame();
 }
 
+JValue EnterInterpreterFromDeoptimize(Thread* self, ShadowFrame& shadow_frame, JValue ret_val)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  MethodHelper mh(shadow_frame.GetMethod());
+  const DexFile::CodeItem* code_item = mh.GetCodeItem();
+  return Execute(self, mh, code_item, shadow_frame, ret_val);
+}
+
 }  // namespace interpreter
 }  // namespace art
diff --git a/src/interpreter/interpreter.h b/src/interpreter/interpreter.h
index ea07ce8..ec6832d 100644
--- a/src/interpreter/interpreter.h
+++ b/src/interpreter/interpreter.h
@@ -24,6 +24,7 @@
 class AbstractMethod;
 union JValue;
 class Object;
+class ShadowFrame;
 class Thread;
 
 namespace interpreter {
@@ -32,6 +33,10 @@
                                        JValue* args, JValue* result)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
+extern JValue EnterInterpreterFromDeoptimize(Thread* self, ShadowFrame& shadow_frame,
+                                             JValue ret_val)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
 }  // namespace interpreter
 }  // namespace art
 
diff --git a/src/jvalue.h b/src/jvalue.h
new file mode 100644
index 0000000..a7a1795
--- /dev/null
+++ b/src/jvalue.h
@@ -0,0 +1,75 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_SRC_JVALUE_H_
+#define ART_SRC_JVALUE_H_
+
+#include "base/macros.h"
+
+namespace art {
+
+class Object;
+
+union PACKED(4) JValue {
+  // We default initialize JValue instances to all-zeros.
+  JValue() : j(0) {}
+
+  int8_t GetB() const { return b; }
+  void SetB(int8_t new_b) {
+    i = ((static_cast<int32_t>(new_b) << 24) >> 24); // Sign-extend.
+  }
+
+  uint16_t GetC() const { return c; }
+  void SetC(uint16_t new_c) { c = new_c; }
+
+  double GetD() const { return d; }
+  void SetD(double new_d) { d = new_d; }
+
+  float GetF() const { return f; }
+  void SetF(float new_f) { f = new_f; }
+
+  int32_t GetI() const { return i; }
+  void SetI(int32_t new_i) { i = new_i; }
+
+  int64_t GetJ() const { return j; }
+  void SetJ(int64_t new_j) { j = new_j; }
+
+  Object* GetL() const { return l; }
+  void SetL(Object* new_l) { l = new_l; }
+
+  int16_t GetS() const { return s; }
+  void SetS(int16_t new_s) {
+    i = ((static_cast<int32_t>(new_s) << 16) >> 16); // Sign-extend.
+  }
+
+  uint8_t GetZ() const { return z; }
+  void SetZ(uint8_t new_z) { z = new_z; }
+
+ private:
+  uint8_t z;
+  int8_t b;
+  uint16_t c;
+  int16_t s;
+  int32_t i;
+  int64_t j;
+  float f;
+  double d;
+  Object* l;
+};
+
+}  // namespace art
+
+#endif  // ART_SRC_JVALUE_H_
diff --git a/src/native/dalvik_system_VMStack.cc b/src/native/dalvik_system_VMStack.cc
index 0e6e675..8ce022d 100644
--- a/src/native/dalvik_system_VMStack.cc
+++ b/src/native/dalvik_system_VMStack.cc
@@ -51,7 +51,8 @@
   }
 }
 
-static jint VMStack_fillStackTraceElements(JNIEnv* env, jclass, jobject javaThread, jobjectArray javaSteArray) {
+static jint VMStack_fillStackTraceElements(JNIEnv* env, jclass, jobject javaThread,
+                                           jobjectArray javaSteArray) {
   jobject trace = GetThreadStack(env, javaThread);
   if (trace == NULL) {
     return 0;
@@ -69,10 +70,11 @@
   return soa.AddLocalReference<jobject>(visitor.caller->GetDeclaringClass()->GetClassLoader());
 }
 
-static jobject VMStack_getClosestUserClassLoader(JNIEnv* env, jclass, jobject javaBootstrap, jobject javaSystem) {
+static jobject VMStack_getClosestUserClassLoader(JNIEnv* env, jclass, jobject javaBootstrap,
+                                                 jobject javaSystem) {
   struct ClosestUserClassLoaderVisitor : public StackVisitor {
     ClosestUserClassLoaderVisitor(const ManagedStack* stack,
-                                  const std::vector<InstrumentationStackFrame>* instrumentation_stack,
+                                  const std::deque<InstrumentationStackFrame>* instrumentation_stack,
                                   Object* bootstrap, Object* system)
       : StackVisitor(stack, instrumentation_stack, NULL),
         bootstrap(bootstrap), system(system), class_loader(NULL) {}
diff --git a/src/nth_caller_visitor.h b/src/nth_caller_visitor.h
index 3c1f2e0..15e62e2 100644
--- a/src/nth_caller_visitor.h
+++ b/src/nth_caller_visitor.h
@@ -24,7 +24,7 @@
 
 // Walks up the stack 'n' callers, when used with Thread::WalkStack.
 struct NthCallerVisitor : public StackVisitor {
-  NthCallerVisitor(const ManagedStack* stack, const std::vector<InstrumentationStackFrame>* instrumentation_stack, size_t n)
+  NthCallerVisitor(const ManagedStack* stack, const std::deque<InstrumentationStackFrame>* instrumentation_stack, size_t n)
       : StackVisitor(stack, instrumentation_stack, NULL), n(n), count(0), caller(NULL) {}
 
   bool VisitFrame() {
diff --git a/src/oat/runtime/arm/oat_support_entrypoints_arm.cc b/src/oat/runtime/arm/oat_support_entrypoints_arm.cc
index f30ce24..041e12b 100644
--- a/src/oat/runtime/arm/oat_support_entrypoints_arm.cc
+++ b/src/oat/runtime/arm/oat_support_entrypoints_arm.cc
@@ -138,6 +138,7 @@
 // Instrumentation entrypoints.
 extern "C" void art_instrumentation_entry_from_code(void*);
 extern "C" void art_instrumentation_exit_from_code();
+extern "C" void art_deoptimize();
 
 void InitEntryPoints(EntryPoints* points) {
   // Alloc
@@ -251,9 +252,12 @@
   points->pUpdateDebuggerFromCode = (enabled ? art_update_debugger : NULL);
 }
 
-bool IsInstrumentationExitPc(uintptr_t pc) {
-  uintptr_t trace_exit = reinterpret_cast<uintptr_t>(art_instrumentation_exit_from_code);
-  return pc == trace_exit;
+uintptr_t GetInstrumentationExitPc() {
+  return reinterpret_cast<uintptr_t>(art_instrumentation_exit_from_code);
+}
+
+uintptr_t GetDeoptimizationEntryPoint() {
+  return reinterpret_cast<uintptr_t>(art_deoptimize);
 }
 
 void* GetInstrumentationEntryPoint() {
diff --git a/src/oat/runtime/arm/runtime_support_arm.S b/src/oat/runtime/arm/runtime_support_arm.S
index 34caeac..7901c5f 100644
--- a/src/oat/runtime/arm/runtime_support_arm.S
+++ b/src/oat/runtime/arm/runtime_support_arm.S
@@ -743,7 +743,7 @@
     ldrh    r0, [rSELF, #THREAD_FLAGS_OFFSET]
     mov    rSUSPEND, #SUSPEND_CHECK_INTERVAL  @ reset rSUSPEND to SUSPEND_CHECK_INTERVAL
     cmp    r0, #0                             @ check Thread::Current()->suspend_count_ == 0
-    bxeq   rLR                                @ return if suspend_count_ == 0
+    bxeq   lr                                 @ return if suspend_count_ == 0
     mov    r0, rSELF
     SETUP_REF_ONLY_CALLEE_SAVE_FRAME          @ save callee saves for stack crawl
     mov    r1, sp
@@ -780,19 +780,54 @@
      */
     ALIGN_FUNCTION_ENTRY
 art_instrumentation_entry_from_code:
+    mov   r12, sp        @ remember bottom of caller's frame
     push  {r0-r3}        @ save arguments (4 words)
     mov   r1, r9         @ pass Thread::Current
-    mov   r2, lr         @ pass LR
-    blx   artInstrumentationMethodEntryFromCode  @ (Method*, Thread*, LR)
+    mov   r2, r12        @ pass SP
+    mov   r3, lr         @ pass LR
+    blx   artInstrumentationMethodEntryFromCode  @ (Method*, Thread*, SP, LR)
     mov   r12, r0        @ r12 holds reference to code
     pop   {r0-r3}        @ restore arguments
     blx   r12            @ call method
 art_instrumentation_exit_from_code:
+    mov   r12, sp        @ remember bottom of caller's frame
     push  {r0-r1}        @ save return value
-    blx   artInstrumentationMethodExitFromCode  @ ()
-    mov   lr, r0         @ restore link register
+    sub   sp, #8         @ align stack
+    mov   r0, r9         @ pass Thread::Current
+    mov   r1, r12        @ pass SP
+    blx   artInstrumentationMethodExitFromCode  @ (Thread*, SP)
+    add   sp, #8
+    mov   r2, r0         @ link register saved by instrumentation
+    mov   lr, r1         @ r1 is holding link register if we're to bounce to deoptimize
     pop   {r0, r1}       @ restore return value
-    bx    lr             @ return
+    bx    r2             @ return
+
+    .global art_deoptimize
+    .extern artDeoptimize
+    .extern artEnterInterpreterFromDeoptimize
+    /*
+     * The thread's enter interpreter flag is set and so we should transition to the interpreter
+     * rather than allow execution to continue in the frame below. There may be live results in
+     * registers depending on how complete the operation is when we safepoint - for example, a
+     * set operation may have completed while a get operation needs writing back into the vregs.
+     */
+    ALIGN_FUNCTION_ENTRY
+art_deoptimize:
+    SETUP_REF_ONLY_CALLEE_SAVE_FRAME
+    mov    r2, r9         @ Set up args.
+    mov    r3, sp
+    blx    artDeoptimize  @ artDeoptimize(return value, Thread*, SP)
+                          @ Returns caller method's frame size.
+    RESTORE_REF_ONLY_CALLEE_SAVE_FRAME
+    cmp    r0, #0         @ Was the caller an upcall?
+    bxeq   lr             @ Return if caller was upcall.
+    add    r12, sp, r0    @ r12 == bottom of caller's frame.
+    ldr    lr, [r12, #-4] @ Restore lr.
+    mov    sp, r12        @ Remove frame.
+    SETUP_REF_ONLY_CALLEE_SAVE_FRAME
+    blx     artEnterInterpreterFromDeoptimize  @ Enter interpreter, callee-save ends stack fragment.
+    RESTORE_REF_ONLY_CALLEE_SAVE_FRAME
+    bx lr                 @ Return to caller.
 
     .global art_mul_long
     /*
diff --git a/src/oat/runtime/oat_support_entrypoints.h b/src/oat/runtime/oat_support_entrypoints.h
index 284fc0b..285105d 100644
--- a/src/oat/runtime/oat_support_entrypoints.h
+++ b/src/oat/runtime/oat_support_entrypoints.h
@@ -146,8 +146,11 @@
 // Change the debugger entry point in the data structure.
 void ChangeDebuggerEntryPoint(EntryPoints* points, bool enabled);
 
-// Is the given return_pc the instrumentation exit return pc?
-bool IsInstrumentationExitPc(uintptr_t pc);
+// The return_pc of instrumentation exit stub.
+uintptr_t GetInstrumentationExitPc();
+
+// Entry point for deoptimization.
+uintptr_t GetDeoptimizationEntryPoint();
 
 // Return address of instrumentation stub.
 void* GetInstrumentationEntryPoint();
diff --git a/src/oat/runtime/support_deoptimize.cc b/src/oat/runtime/support_deoptimize.cc
new file mode 100644
index 0000000..13fd3ae
--- /dev/null
+++ b/src/oat/runtime/support_deoptimize.cc
@@ -0,0 +1,99 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "callee_save_frame.h"
+#include "interpreter/interpreter.h"
+#include "object.h"  // for JValue
+#include "object_utils.h"
+#include "stack.h"
+#include "thread.h"
+#include "verifier/method_verifier.h"
+
+namespace art {
+
+extern "C" uint64_t artDeoptimize(JValue ret_val, Thread* self, AbstractMethod** sp)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  FinishCalleeSaveFrameSetup(self, sp, Runtime::kRefsOnly);
+  // Return value may hold Object* so avoid suspension.
+  const char* old_cause = self->StartAssertNoThreadSuspension("Deoptimizing stack frame");
+  CHECK(old_cause == NULL);
+  class DeoptimizationVisitor : public StackVisitor {
+   public:
+    DeoptimizationVisitor(const ManagedStack* stack,
+                          const std::deque<InstrumentationStackFrame>* instrumentation_stack,
+                          Context* context)
+        : StackVisitor(stack, instrumentation_stack, context), shadow_frame_(NULL),
+          runtime_frames_(0) { }
+
+    virtual bool VisitFrame() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+      AbstractMethod* m = GetMethod();
+      if (m->IsRuntimeMethod()) {
+        if (runtime_frames_ == 0) {
+          runtime_frames_++;
+          return true;  // Skip the callee save frame.
+        } else {
+          return false;  // Caller was an upcall.
+        }
+      }
+      MethodHelper mh(m);
+      const DexFile::CodeItem* code_item = mh.GetCodeItem();
+      CHECK(code_item != NULL);
+      uint16_t num_regs =  code_item->registers_size_;
+      shadow_frame_ = ShadowFrame::Create(num_regs, NULL, m, GetDexPc());
+      std::vector<int32_t> kinds =
+          verifier::MethodVerifier::DescribeVRegs(m->GetDexMethodIndex(), &mh.GetDexFile(),
+                                                  mh.GetDexCache(), mh.GetClassLoader(),
+                                                  mh.GetClassDefIndex(), code_item, m,
+                                                  m->GetAccessFlags(), GetDexPc());
+      for(uint16_t reg = 0; reg < num_regs; reg++) {
+        VRegKind kind = static_cast<VRegKind>(kinds.at(reg * 2));
+        switch (kind) {
+          case kUndefined:
+            shadow_frame_->SetVReg(reg, 0xEBADDE09);
+            break;
+          case kConstant:
+            shadow_frame_->SetVReg(reg, kinds.at((reg * 2) + 1));
+            break;
+          default:
+            shadow_frame_->SetVReg(reg, GetVReg(m, reg, kind));
+            break;
+        }
+      }
+      return false;  // Stop now we have built the shadow frame.
+    }
+    ShadowFrame* shadow_frame_;
+    uint32_t runtime_frames_;
+  } visitor(self->GetManagedStack(), self->GetInstrumentationStack(), self->GetLongJumpContext());
+  visitor.WalkStack(false);
+  if (visitor.shadow_frame_ != NULL) {
+    self->SetDeoptimizationShadowFrame(visitor.shadow_frame_, ret_val);
+    return (*sp)->GetFrameSizeInBytes();
+  } else {
+    return 0;  // Caller was an upcall.
+  }
+}
+
+
+extern "C" JValue artEnterInterpreterFromDeoptimize(Thread* self, AbstractMethod** sp)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  FinishCalleeSaveFrameSetup(self, sp, Runtime::kRefsOnly);
+  JValue return_value;
+  UniquePtr<ShadowFrame> shadow_frame(self->GetAndClearDeoptimizationShadowFrame(&return_value));
+  self->EndAssertNoThreadSuspension(NULL);
+  return interpreter::EnterInterpreterFromDeoptimize(self, *shadow_frame.get(), return_value);
+}
+
+}  // namespace art
diff --git a/src/oat/runtime/support_instrumentation.cc b/src/oat/runtime/support_instrumentation.cc
index 8c5e442..339c11a 100644
--- a/src/oat/runtime/support_instrumentation.cc
+++ b/src/oat/runtime/support_instrumentation.cc
@@ -14,6 +14,7 @@
  * limitations under the License.
  */
 
+#include "base/logging.h"
 #include "instrumentation.h"
 #include "runtime.h"
 #include "thread.h"
@@ -22,26 +23,61 @@
 namespace art {
 
 extern "C" const void* artInstrumentationMethodEntryFromCode(AbstractMethod* method, Thread* self,
-                                                             uintptr_t lr) {
+                                                             AbstractMethod** sp, uintptr_t lr)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  if (*sp != NULL) {
+    self->SetTopOfStack(sp, lr);
+  }
+  self->VerifyStack();
   Instrumentation* instrumentation = Runtime::Current()->GetInstrumentation();
-  Trace* trace = instrumentation->GetTrace();
-  InstrumentationStackFrame instrumentation_frame = InstrumentationStackFrame(method, lr);
+  // +1 as frame id's start at 1, +1 as we haven't yet built this method's frame.
+  const size_t kFrameIdAdjust = 2;
+  size_t frame_id = StackVisitor::ComputeNumFrames(self->GetManagedStack(),
+                                                   self->GetInstrumentationStack()) + kFrameIdAdjust;
+  InstrumentationStackFrame instrumentation_frame(method, lr, frame_id);
   self->PushInstrumentationStackFrame(instrumentation_frame);
 
-  trace->LogMethodTraceEvent(self, method, Trace::kMethodTraceEnter);
+  Trace* trace = instrumentation->GetTrace();
+  if (trace != NULL) {
+    trace->LogMethodTraceEvent(self, method, Trace::kMethodTraceEnter);
+  }
 
   return instrumentation->GetSavedCodeFromMap(method);
 }
 
-extern "C" uintptr_t artInstrumentationMethodExitFromCode() {
-  Trace* trace = Runtime::Current()->GetInstrumentation()->GetTrace();
-  InstrumentationStackFrame instrumentation_frame = Thread::Current()->PopInstrumentationStackFrame();
-  AbstractMethod* method = instrumentation_frame.method_;
-  uintptr_t lr = instrumentation_frame.return_pc_;
+extern "C" uint64_t artInstrumentationMethodExitFromCode(Thread* self, AbstractMethod** sp)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  if (*sp != NULL) {
+    self->SetTopOfStack(sp, 0);
+  }
+  self->VerifyStack();
 
-  trace->LogMethodTraceEvent(Thread::Current(), method, Trace::kMethodTraceExit);
-
-  return lr;
+  /*
+  // TODO: ComputeNumFrames currently fails here, so it's disabled.
+  // +1 as frame id's start at 1, +1 as we want the called frame not the frame being returned into.
+  const size_t kFrameIdAdjust = 2;
+  size_t frame_id = StackVisitor::ComputeNumFrames(self->GetManagedStack(),
+                                                   self->GetInstrumentationStack()) + kFrameIdAdjust;
+  */
+  InstrumentationStackFrame instrumentation_frame;
+  instrumentation_frame = self->PopInstrumentationStackFrame();
+  /*
+  if (frame_id != instrumentation_frame.frame_id_) {
+    LOG(ERROR) << "Expected frame_id=" << frame_id << " but found " << instrumentation_frame.frame_id_;
+    StackVisitor::DescribeStack(self->GetManagedStack(), self->GetInstrumentationStack());
+  }
+  */
+  Runtime* runtime = Runtime::Current();
+  if (runtime->IsMethodTracingActive()) {
+    Trace* trace = runtime->GetInstrumentation()->GetTrace();
+    trace->LogMethodTraceEvent(self, instrumentation_frame.method_, Trace::kMethodTraceExit);
+  }
+  if (self->ReadFlag(kEnterInterpreter)) {
+    return static_cast<uint64_t>(GetDeoptimizationEntryPoint()) |
+        (static_cast<uint64_t>(instrumentation_frame.return_pc_) << 32);
+  } else {
+    return instrumentation_frame.return_pc_;
+  }
 }
 
 }  // namespace art
diff --git a/src/oat/runtime/x86/oat_support_entrypoints_x86.cc b/src/oat/runtime/x86/oat_support_entrypoints_x86.cc
index 9b32b8b..a3c845e 100644
--- a/src/oat/runtime/x86/oat_support_entrypoints_x86.cc
+++ b/src/oat/runtime/x86/oat_support_entrypoints_x86.cc
@@ -233,8 +233,12 @@
   UNIMPLEMENTED(FATAL);
 }
 
-bool IsInstrumentationExitPc(uintptr_t) {
-  return false;
+uintptr_t GetInstrumentationExitPc() {
+  return 0;
+}
+
+uintptr_t GetDeoptimizationEntryPoint() {
+  return 0;
 }
 
 void* GetInstrumentationEntryPoint() {
diff --git a/src/object.cc b/src/object.cc
index 8565c38..c3c4e13 100644
--- a/src/object.cc
+++ b/src/object.cc
@@ -591,8 +591,8 @@
       return mapping_table[i + 1];
     }
   }
-  LOG(FATAL) << "Failed to find Dex offset for PC offset 0x" << std::hex << sought_offset
-             << " in " << PrettyMethod(this);
+  LOG(ERROR) << "Failed to find Dex offset for PC offset " << reinterpret_cast<void*>(sought_offset)
+             << "(PC " << reinterpret_cast<void*>(pc) << ") in " << PrettyMethod(this);
   return DexFile::kDexNoIndex;
 #else
   // Compiler LLVM doesn't use the machine pc, we just use dex pc instead.
diff --git a/src/object.h b/src/object.h
index 0eea8c3..60e45c3 100644
--- a/src/object.h
+++ b/src/object.h
@@ -61,53 +61,7 @@
 typedef PrimitiveArray<int32_t> IntArray;
 typedef PrimitiveArray<int64_t> LongArray;
 typedef PrimitiveArray<int16_t> ShortArray;
-
-union JValue {
-  // We default initialize JValue instances to all-zeros.
-  JValue() : j(0) {}
-
-  int8_t GetB() const { return b; }
-  void SetB(int8_t new_b) {
-    i = ((static_cast<int32_t>(new_b) << 24) >> 24); // Sign-extend.
-  }
-
-  uint16_t GetC() const { return c; }
-  void SetC(uint16_t new_c) { c = new_c; }
-
-  double GetD() const { return d; }
-  void SetD(double new_d) { d = new_d; }
-
-  float GetF() const { return f; }
-  void SetF(float new_f) { f = new_f; }
-
-  int32_t GetI() const { return i; }
-  void SetI(int32_t new_i) { i = new_i; }
-
-  int64_t GetJ() const { return j; }
-  void SetJ(int64_t new_j) { j = new_j; }
-
-  Object* GetL() const { return l; }
-  void SetL(Object* new_l) { l = new_l; }
-
-  int16_t GetS() const { return s; }
-  void SetS(int16_t new_s) {
-    i = ((static_cast<int32_t>(new_s) << 16) >> 16); // Sign-extend.
-  }
-
-  uint8_t GetZ() const { return z; }
-  void SetZ(uint8_t new_z) { z = new_z; }
-
- private:
-  uint8_t z;
-  int8_t b;
-  uint16_t c;
-  int16_t s;
-  int32_t i;
-  int64_t j;
-  float f;
-  double d;
-  Object* l;
-};
+union JValue;
 
 #if defined(ART_USE_LLVM_COMPILER)
 namespace compiler_llvm {
diff --git a/src/stack.cc b/src/stack.cc
index ed44df9..e962dec 100644
--- a/src/stack.cc
+++ b/src/stack.cc
@@ -142,10 +142,11 @@
   *reinterpret_cast<uintptr_t*>(pc_addr) = new_ret_pc;
 }
 
-size_t StackVisitor::ComputeNumFrames() const {
+size_t StackVisitor::ComputeNumFrames(const ManagedStack* stack,
+                                      const std::deque<InstrumentationStackFrame>* instr_stack) {
   struct NumFramesVisitor : public StackVisitor {
     explicit NumFramesVisitor(const ManagedStack* stack,
-                              const std::vector<InstrumentationStackFrame>* instrumentation_stack)
+                              const std::deque<InstrumentationStackFrame>* instrumentation_stack)
         : StackVisitor(stack, instrumentation_stack, NULL), frames(0) {}
 
     virtual bool VisitFrame() {
@@ -155,15 +156,35 @@
 
     size_t frames;
   };
-
-  NumFramesVisitor visitor(stack_start_, instrumentation_stack_);
+  UNUSED(instr_stack);  // We don't use the instrumentation stack as we don't require dex pcs...
+  NumFramesVisitor visitor(stack, NULL);
   visitor.WalkStack(true);
   return visitor.frames;
 }
 
+void StackVisitor::DescribeStack(const ManagedStack* stack,
+                                 const std::deque<InstrumentationStackFrame>* instr_stack) {
+  struct DescribeStackVisitor : public StackVisitor {
+    explicit DescribeStackVisitor(const ManagedStack* stack,
+                              const std::deque<InstrumentationStackFrame>* instrumentation_stack)
+        : StackVisitor(stack, instrumentation_stack, NULL) {}
+
+    virtual bool VisitFrame() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+      LOG(INFO) << "Frame Id=" << GetFrameId() << " " << DescribeLocation();
+      return true;
+    }
+  };
+  DescribeStackVisitor visitor(stack, instr_stack);
+  visitor.WalkStack(true);
+}
+
 std::string StackVisitor::DescribeLocation() const {
   std::string result("Visiting method '");
-  result += PrettyMethod(GetMethod());
+  AbstractMethod* m = GetMethod();
+  if (m == NULL) {
+    return "upcall";
+  }
+  result += PrettyMethod(m);
   result += StringPrintf("' at dex PC 0x%04zx", GetDexPc());
   if (!IsShadowFrame()) {
     result += StringPrintf(" (native PC %p)", reinterpret_cast<void*>(GetCurrentQuickFramePc()));
@@ -189,7 +210,7 @@
 }
 
 void StackVisitor::WalkStack(bool include_transitions) {
-  bool method_tracing_active = Runtime::Current()->IsMethodTracingActive();
+  bool method_tracing_active = instrumentation_stack_ != NULL;
   uint32_t instrumentation_stack_depth = 0;
   for (const ManagedStack* current_fragment = stack_start_; current_fragment != NULL;
        current_fragment = current_fragment->GetLink()) {
@@ -218,7 +239,7 @@
           // While profiling, the return pc is restored from the side stack, except when walking
           // the stack for an exception where the side stack will be unwound in VisitFrame.
           // TODO: stop using include_transitions as a proxy for is this the catch block visitor.
-          if (IsInstrumentationExitPc(return_pc) && !include_transitions) {
+          if (GetInstrumentationExitPc() == return_pc && !include_transitions) {
             // TODO: unify trace and managed stack.
             InstrumentationStackFrame instrumentation_frame = GetInstrumentationStackFrame(instrumentation_stack_depth);
             instrumentation_stack_depth++;
diff --git a/src/stack.h b/src/stack.h
index 30de26d..c3b837f 100644
--- a/src/stack.h
+++ b/src/stack.h
@@ -331,7 +331,8 @@
 
 class StackVisitor {
  protected:
-  StackVisitor(const ManagedStack* stack, const std::vector<InstrumentationStackFrame>* instrumentation_stack,
+  StackVisitor(const ManagedStack* stack,
+               const std::deque<InstrumentationStackFrame>* instrumentation_stack,
                Context* context)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
       : stack_start_(stack), instrumentation_stack_(instrumentation_stack), cur_shadow_frame_(NULL),
@@ -388,7 +389,7 @@
 
   size_t GetNumFrames() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     if (num_frames_ == 0) {
-      num_frames_ = ComputeNumFrames();
+      num_frames_ = ComputeNumFrames(stack_start_, instrumentation_stack_);
     }
     return num_frames_;
   }
@@ -492,17 +493,24 @@
 
   std::string DescribeLocation() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
+  static size_t ComputeNumFrames(const ManagedStack* stack,
+                                 const std::deque<InstrumentationStackFrame>* instr_stack)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  static void DescribeStack(const ManagedStack* stack,
+                            const std::deque<InstrumentationStackFrame>* instr_stack)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
  private:
-  size_t ComputeNumFrames() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   InstrumentationStackFrame GetInstrumentationStackFrame(uint32_t depth) const {
-    return instrumentation_stack_->at(instrumentation_stack_->size() - depth - 1);
+    return instrumentation_stack_->at(depth);
   }
 
   void SanityCheckFrame() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   const ManagedStack* const stack_start_;
-  const std::vector<InstrumentationStackFrame>* const instrumentation_stack_;
+  const std::deque<InstrumentationStackFrame>* const instrumentation_stack_;
   ShadowFrame* cur_shadow_frame_;
   AbstractMethod** cur_quick_frame_;
   uintptr_t cur_quick_frame_pc_;
diff --git a/src/thread.cc b/src/thread.cc
index aa13ad2..484806e 100644
--- a/src/thread.cc
+++ b/src/thread.cc
@@ -93,6 +93,21 @@
 #endif
 }
 
+
+void Thread::SetDeoptimizationShadowFrame(ShadowFrame* sf, const JValue& ret_val) {
+  CHECK(sf != NULL);
+  deoptimization_shadow_frame_ = sf;
+  deoptimization_return_value_.SetJ(ret_val.GetJ());
+}
+
+ShadowFrame* Thread::GetAndClearDeoptimizationShadowFrame(JValue* ret_val) {
+  ShadowFrame* sf = deoptimization_shadow_frame_;
+  DCHECK(sf != NULL);
+  deoptimization_shadow_frame_ = NULL;
+  ret_val->SetJ(deoptimization_return_value_.GetJ());
+  return sf;
+}
+
 void Thread::InitTid() {
   tid_ = ::art::GetTid();
 }
@@ -965,7 +980,7 @@
       throwing_OutOfMemoryError_(false),
       debug_suspend_count_(0),
       debug_invoke_req_(new DebugInvokeReq),
-      instrumentation_stack_(new std::vector<InstrumentationStackFrame>),
+      instrumentation_stack_(new std::deque<InstrumentationStackFrame>),
       name_(new std::string(kThreadNameDuringStartup)),
       daemon_(daemon),
       pthread_self_(0),
@@ -1240,7 +1255,7 @@
 class CountStackDepthVisitor : public StackVisitor {
  public:
   CountStackDepthVisitor(const ManagedStack* stack,
-                         const std::vector<InstrumentationStackFrame>* instrumentation_stack)
+                         const std::deque<InstrumentationStackFrame>* instrumentation_stack)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
       : StackVisitor(stack, instrumentation_stack, NULL),
         depth_(0), skip_depth_(0), skipping_(true) {}
@@ -1281,7 +1296,7 @@
 class BuildInternalStackTraceVisitor : public StackVisitor {
  public:
   explicit BuildInternalStackTraceVisitor(Thread* self, const ManagedStack* stack,
-                                          const std::vector<InstrumentationStackFrame>* instrumentation_stack,
+                                          const std::deque<InstrumentationStackFrame>* instrumentation_stack,
                                           int skip_depth)
       : StackVisitor(stack, instrumentation_stack, NULL), self_(self),
         skip_depth_(skip_depth), count_(0), dex_pc_trace_(NULL), method_trace_(NULL) {}
@@ -1360,8 +1375,8 @@
   int32_t skip_depth = count_visitor.GetSkipDepth();
 
   // Build internal stack trace.
-  BuildInternalStackTraceVisitor build_trace_visitor(soa.Self(), GetManagedStack(), GetInstrumentationStack(),
-                                                     skip_depth);
+  BuildInternalStackTraceVisitor build_trace_visitor(soa.Self(), GetManagedStack(),
+                                                     GetInstrumentationStack(), skip_depth);
   if (!build_trace_visitor.Init(depth)) {
     return NULL;  // Allocation failed.
   }
@@ -1703,7 +1718,8 @@
         native_method_count_++;
       } else {
         // Unwind stack when an exception occurs during instrumentation
-        if (UNLIKELY(method_tracing_active_ && IsInstrumentationExitPc(GetCurrentQuickFramePc()))) {
+        if (UNLIKELY(method_tracing_active_ &&
+                     GetInstrumentationExitPc() == GetCurrentQuickFramePc())) {
           uintptr_t pc = InstrumentationMethodUnwindFromCode(Thread::Current());
           dex_pc = method->ToDexPc(pc);
         } else {
@@ -1802,7 +1818,7 @@
 AbstractMethod* Thread::GetCurrentMethod(uint32_t* dex_pc, size_t* frame_id) const {
   struct CurrentMethodVisitor : public StackVisitor {
     CurrentMethodVisitor(const ManagedStack* stack,
-                         const std::vector<InstrumentationStackFrame>* instrumentation_stack)
+                         const std::deque<InstrumentationStackFrame>* instrumentation_stack)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
         : StackVisitor(stack, instrumentation_stack, NULL), method_(NULL), dex_pc_(0), frame_id_(0) {}
 
@@ -1844,7 +1860,8 @@
 template <typename RootVisitor>
 class ReferenceMapVisitor : public StackVisitor {
  public:
-  ReferenceMapVisitor(const ManagedStack* stack, const std::vector<InstrumentationStackFrame>* instrumentation_stack,
+  ReferenceMapVisitor(const ManagedStack* stack,
+                      const std::deque<InstrumentationStackFrame>* instrumentation_stack,
                       Context* context, const RootVisitor& visitor)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
       : StackVisitor(stack, instrumentation_stack, context), visitor_(visitor) {}
@@ -2013,8 +2030,8 @@
   // Visit roots on this thread's stack
   Context* context = GetLongJumpContext();
   VerifyCallbackVisitor visitorToCallback(visitor, arg);
-  ReferenceMapVisitor<VerifyCallbackVisitor> mapper(GetManagedStack(), GetInstrumentationStack(), context,
-                                                  visitorToCallback);
+  ReferenceMapVisitor<VerifyCallbackVisitor> mapper(GetManagedStack(), GetInstrumentationStack(),
+                                                    context, visitorToCallback);
   mapper.WalkStack();
   ReleaseLongJumpContext(context);
 }
diff --git a/src/thread.h b/src/thread.h
index 29ae7c1..e8f69db 100644
--- a/src/thread.h
+++ b/src/thread.h
@@ -20,15 +20,16 @@
 #include <pthread.h>
 
 #include <bitset>
+#include <deque>
 #include <iosfwd>
 #include <list>
 #include <string>
-#include <vector>
 
 #include "base/macros.h"
 #include "closure.h"
 #include "globals.h"
 #include "instrumentation.h"
+#include "jvalue.h"
 #include "oat/runtime/oat_support_entrypoints.h"
 #include "locks.h"
 #include "offsets.h"
@@ -566,7 +567,11 @@
 
   void SetDebuggerUpdatesEnabled(bool enabled);
 
-  const std::vector<InstrumentationStackFrame>* GetInstrumentationStack() const {
+  void SetDeoptimizationShadowFrame(ShadowFrame* sf, const JValue& ret_val);
+
+  ShadowFrame* GetAndClearDeoptimizationShadowFrame(JValue* ret_val);
+
+  const std::deque<InstrumentationStackFrame>* GetInstrumentationStack() const {
     return instrumentation_stack_;
   }
 
@@ -575,12 +580,16 @@
   }
 
   void PushInstrumentationStackFrame(const InstrumentationStackFrame& frame) {
+    instrumentation_stack_->push_front(frame);
+  }
+
+  void PushBackInstrumentationStackFrame(const InstrumentationStackFrame& frame) {
     instrumentation_stack_->push_back(frame);
   }
 
   InstrumentationStackFrame PopInstrumentationStackFrame() {
-    InstrumentationStackFrame frame = instrumentation_stack_->back();
-    instrumentation_stack_->pop_back();
+    InstrumentationStackFrame frame = instrumentation_stack_->front();
+    instrumentation_stack_->pop_front();
     return frame;
   }
 
@@ -767,9 +776,13 @@
   // JDWP invoke-during-breakpoint support.
   DebugInvokeReq* debug_invoke_req_;
 
+  // Shadow frame that is used temporarily during the deoptimization of a method.
+  ShadowFrame* deoptimization_shadow_frame_;
+  JValue deoptimization_return_value_;
+
   // Additional stack used by method instrumentation to store method and return pc values.
-  // Stored as a pointer since std::vector is not PACKED.
-  std::vector<InstrumentationStackFrame>* instrumentation_stack_;
+  // Stored as a pointer since std::deque is not PACKED.
+  std::deque<InstrumentationStackFrame>* instrumentation_stack_;
 
   // A cached copy of the java.lang.Thread's name.
   std::string* name_;