Fix nested deoptimization.

Handle nested deoptimization cases. Create a stacked shadow frame
records to keep track of deoptimization shadow frames. Shadow frames
under construction can be tracked in the same stack.

Bug: 20845490

(cherry picked from commit 1f2d3ba6af52cf6f566deb38b7e07735c9a08fb6)

Change-Id: I768285792c29e7c3cfcd21e7a2600802506024d8

10 files changed, 251 insertions, 141 deletions

diff --git a/runtime/art_method.cc b/runtime/art_method.cc
index fbaf0ae..478a87e 100644
--- a/runtime/art_method.cc
+++ b/runtime/art_method.cc
@@ -424,7 +424,8 @@ void ArtMethod::Invoke(Thread* self, uint32_t* args, uint32_t args_size, JValue*
         // exception was thrown to force the activations to be removed from the
         // stack. Continue execution in the interpreter.
         self->ClearException();
-        ShadowFrame* shadow_frame = self->GetAndClearDeoptimizationShadowFrame(result);
+        ShadowFrame* shadow_frame = self->PopStackedShadowFrame(kDeoptimizationShadowFrame);
+        result->SetJ(self->PopDeoptimizationReturnValue().GetJ());
         self->SetTopOfStack(nullptr);
         self->SetTopOfShadowStack(shadow_frame);
         interpreter::EnterInterpreterFromDeoptimize(self, shadow_frame, result);
diff --git a/runtime/entrypoints/quick/quick_deoptimization_entrypoints.cc b/runtime/entrypoints/quick/quick_deoptimization_entrypoints.cc
index 3eefeef..9860fb0 100644
--- a/runtime/entrypoints/quick/quick_deoptimization_entrypoints.cc
+++ b/runtime/entrypoints/quick/quick_deoptimization_entrypoints.cc
@@ -28,6 +28,7 @@ namespace art {
 
 extern "C" NO_RETURN void artDeoptimize(Thread* self) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
   ScopedQuickEntrypointChecks sqec(self);
+  self->PushAndClearDeoptimizationReturnValue();
   self->SetException(Thread::GetDeoptimizationException());
   self->QuickDeliverException();
 }
diff --git a/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc b/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc
index bc15cc7..2ea5cb0 100644
--- a/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc
+++ b/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc
@@ -647,7 +647,7 @@ extern "C" uint64_t artQuickToInterpreterBridge(ArtMethod* method, Thread* self,
     ArtMethod* caller = QuickArgumentVisitor::GetCallingMethod(sp);
     if (UNLIKELY(Dbg::IsForcedInterpreterNeededForUpcall(self, caller))) {
       self->SetException(Thread::GetDeoptimizationException());
-      self->SetDeoptimizationReturnValue(result);
+      self->SetDeoptimizationReturnValue(result, shorty[0] == 'L');
     }
 
     // No need to restore the args since the method has already been run by the interpreter.
diff --git a/runtime/entrypoints_order_test.cc b/runtime/entrypoints_order_test.cc
index 963dd02..0a5ebfa 100644
--- a/runtime/entrypoints_order_test.cc
+++ b/runtime/entrypoints_order_test.cc
@@ -72,6 +72,8 @@ class EntrypointsOrderTest : public CommonRuntimeTest {
     EXPECT_OFFSET_DIFFP(Thread, tls32_, throwing_OutOfMemoryError, no_thread_suspension, 4);
     EXPECT_OFFSET_DIFFP(Thread, tls32_, no_thread_suspension, thread_exit_check_count, 4);
     EXPECT_OFFSET_DIFFP(Thread, tls32_, thread_exit_check_count, handling_signal_, 4);
+    EXPECT_OFFSET_DIFFP(Thread, tls32_, handling_signal_,
+                        deoptimization_return_value_is_reference, 4);
 
     // TODO: Better connection. Take alignment into account.
     EXPECT_OFFSET_DIFF_GT3(Thread, tls32_.thread_exit_check_count, tls64_.trace_clock_base, 4,
@@ -103,11 +105,11 @@ class EntrypointsOrderTest : public CommonRuntimeTest {
     EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, long_jump_context, instrumentation_stack, sizeof(void*));
     EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, instrumentation_stack, debug_invoke_req, sizeof(void*));
     EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, debug_invoke_req, single_step_control, sizeof(void*));
-    EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, single_step_control, deoptimization_shadow_frame,
+    EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, single_step_control, stacked_shadow_frame_record,
                         sizeof(void*));
-    EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, deoptimization_shadow_frame,
-                        shadow_frame_under_construction, sizeof(void*));
-    EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, shadow_frame_under_construction, name, sizeof(void*));
+    EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, stacked_shadow_frame_record,
+                        deoptimization_return_value_stack, sizeof(void*));
+    EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, deoptimization_return_value_stack, name, sizeof(void*));
     EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, name, pthread_self, sizeof(void*));
     EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, pthread_self, last_no_thread_suspension_cause,
                         sizeof(void*));
diff --git a/runtime/instrumentation.cc b/runtime/instrumentation.cc
index 4ced23d..d37ddcb 100644
--- a/runtime/instrumentation.cc
+++ b/runtime/instrumentation.cc
@@ -1019,7 +1019,7 @@ TwoWordReturn Instrumentation::PopInstrumentationStackFrame(Thread* self, uintpt
                                 PrettyMethod(method).c_str(),
                                 return_value.GetJ()) << *self;
     }
-    self->SetDeoptimizationReturnValue(return_value);
+    self->SetDeoptimizationReturnValue(return_value, return_shorty == 'L');
     return GetTwoWordSuccessValue(*return_pc,
                                   reinterpret_cast<uintptr_t>(GetQuickDeoptimizationEntryPoint()));
   } else {
diff --git a/runtime/interpreter/interpreter_common.cc b/runtime/interpreter/interpreter_common.cc
index 1ed1a64..3f2e6db 100644
--- a/runtime/interpreter/interpreter_common.cc
+++ b/runtime/interpreter/interpreter_common.cc
@@ -517,7 +517,8 @@ bool DoCall(ArtMethod* called_method, Thread* self, ShadowFrame& shadow_frame,
     // Slow path.
     // We might need to do class loading, which incurs a thread state change to kNative. So
     // register the shadow frame as under construction and allow suspension again.
-    self->SetShadowFrameUnderConstruction(new_shadow_frame);
+    ScopedStackedShadowFramePusher pusher(
+        self, new_shadow_frame, kShadowFrameUnderConstruction);
     self->EndAssertNoThreadSuspension(old_cause);
 
     // We need to do runtime check on reference assignment. We need to load the shorty
@@ -590,8 +591,6 @@ bool DoCall(ArtMethod* called_method, Thread* self, ShadowFrame& shadow_frame,
           break;
       }
     }
-    // We're done with the construction.
-    self->ClearShadowFrameUnderConstruction();
   } else {
     // Fast path: no extra checks.
     if (is_range) {
diff --git a/runtime/jvalue.h b/runtime/jvalue.h
index b39567b..6a6d198 100644
--- a/runtime/jvalue.h
+++ b/runtime/jvalue.h
@@ -61,6 +61,8 @@ union PACKED(4) JValue {
   uint8_t GetZ() const { return z; }
   void SetZ(uint8_t new_z) { z = new_z; }
 
+  mirror::Object** GetGCRoot() { return &l; }
+
  private:
   uint8_t z;
   int8_t b;
diff --git a/runtime/quick_exception_handler.cc b/runtime/quick_exception_handler.cc
index 8c9782a..a10c5c8 100644
--- a/runtime/quick_exception_handler.cc
+++ b/runtime/quick_exception_handler.cc
@@ -163,8 +163,8 @@ class DeoptimizeStackVisitor FINAL : public StackVisitor {
       : StackVisitor(self, context, StackVisitor::StackWalkKind::kIncludeInlinedFrames),
         self_(self),
         exception_handler_(exception_handler),
-        prev_shadow_frame_(nullptr) {
-    CHECK(!self_->HasDeoptimizationShadowFrame());
+        prev_shadow_frame_(nullptr),
+        stacked_shadow_frame_pushed_(false) {
   }
 
   bool VisitFrame() OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
@@ -174,6 +174,13 @@ class DeoptimizeStackVisitor FINAL : public StackVisitor {
       // This is the upcall, we remember the frame and last pc so that we may long jump to them.
       exception_handler_->SetHandlerQuickFramePc(GetCurrentQuickFramePc());
       exception_handler_->SetHandlerQuickFrame(GetCurrentQuickFrame());
+      if (!stacked_shadow_frame_pushed_) {
+        // In case there is no deoptimized shadow frame for this upcall, we still
+        // need to push a nullptr to the stack since there is always a matching pop after
+        // the long jump.
+        self_->PushStackedShadowFrame(nullptr, kDeoptimizationShadowFrame);
+        stacked_shadow_frame_pushed_ = true;
+      }
       return false;  // End stack walk.
     } else if (method->IsRuntimeMethod()) {
       // Ignore callee save method.
@@ -204,111 +211,115 @@ class DeoptimizeStackVisitor FINAL : public StackVisitor {
     bool verifier_success = verifier.Verify();
     CHECK(verifier_success) << PrettyMethod(m);
     ShadowFrame* new_frame = ShadowFrame::CreateDeoptimizedFrame(num_regs, nullptr, m, dex_pc);
-    self_->SetShadowFrameUnderConstruction(new_frame);
-    const std::vector<int32_t> kinds(verifier.DescribeVRegs(dex_pc));
-
-    // Markers for dead values, used when the verifier knows a Dex register is undefined,
-    // or when the compiler knows the register has not been initialized, or is not used
-    // anymore in the method.
-    static constexpr uint32_t kDeadValue = 0xEBADDE09;
-    static constexpr uint64_t kLongDeadValue = 0xEBADDE09EBADDE09;
-    for (uint16_t reg = 0; reg < num_regs; ++reg) {
-      VRegKind kind = GetVRegKind(reg, kinds);
-      switch (kind) {
-        case kUndefined:
-          new_frame->SetVReg(reg, kDeadValue);
-          break;
-        case kConstant:
-          new_frame->SetVReg(reg, kinds.at((reg * 2) + 1));
-          break;
-        case kReferenceVReg: {
-          uint32_t value = 0;
-          // Check IsReferenceVReg in case the compiled GC map doesn't agree with the verifier.
-          // We don't want to copy a stale reference into the shadow frame as a reference.
-          // b/20736048
-          if (GetVReg(m, reg, kind, &value) && IsReferenceVReg(m, reg)) {
-            new_frame->SetVRegReference(reg, reinterpret_cast<mirror::Object*>(value));
-          } else {
+    {
+      ScopedStackedShadowFramePusher pusher(self_, new_frame, kShadowFrameUnderConstruction);
+      const std::vector<int32_t> kinds(verifier.DescribeVRegs(dex_pc));
+
+      // Markers for dead values, used when the verifier knows a Dex register is undefined,
+      // or when the compiler knows the register has not been initialized, or is not used
+      // anymore in the method.
+      static constexpr uint32_t kDeadValue = 0xEBADDE09;
+      static constexpr uint64_t kLongDeadValue = 0xEBADDE09EBADDE09;
+      for (uint16_t reg = 0; reg < num_regs; ++reg) {
+        VRegKind kind = GetVRegKind(reg, kinds);
+        switch (kind) {
+          case kUndefined:
             new_frame->SetVReg(reg, kDeadValue);
-          }
-          break;
-        }
-        case kLongLoVReg:
-          if (GetVRegKind(reg + 1, kinds) == kLongHiVReg) {
-            // Treat it as a "long" register pair.
-            uint64_t value = 0;
-            if (GetVRegPair(m, reg, kLongLoVReg, kLongHiVReg, &value)) {
-              new_frame->SetVRegLong(reg, value);
-            } else {
-              new_frame->SetVRegLong(reg, kLongDeadValue);
-            }
-          } else {
+            break;
+          case kConstant:
+            new_frame->SetVReg(reg, kinds.at((reg * 2) + 1));
+            break;
+          case kReferenceVReg: {
             uint32_t value = 0;
-            if (GetVReg(m, reg, kind, &value)) {
-              new_frame->SetVReg(reg, value);
+            // Check IsReferenceVReg in case the compiled GC map doesn't agree with the verifier.
+            // We don't want to copy a stale reference into the shadow frame as a reference.
+            // b/20736048
+            if (GetVReg(m, reg, kind, &value) && IsReferenceVReg(m, reg)) {
+              new_frame->SetVRegReference(reg, reinterpret_cast<mirror::Object*>(value));
             } else {
               new_frame->SetVReg(reg, kDeadValue);
             }
+            break;
           }
-          break;
-        case kLongHiVReg:
-          if (GetVRegKind(reg - 1, kinds) == kLongLoVReg) {
-            // Nothing to do: we treated it as a "long" register pair.
-          } else {
-            uint32_t value = 0;
-            if (GetVReg(m, reg, kind, &value)) {
-              new_frame->SetVReg(reg, value);
+          case kLongLoVReg:
+            if (GetVRegKind(reg + 1, kinds) == kLongHiVReg) {
+              // Treat it as a "long" register pair.
+              uint64_t value = 0;
+              if (GetVRegPair(m, reg, kLongLoVReg, kLongHiVReg, &value)) {
+                new_frame->SetVRegLong(reg, value);
+              } else {
+                new_frame->SetVRegLong(reg, kLongDeadValue);
+              }
             } else {
-              new_frame->SetVReg(reg, kDeadValue);
+              uint32_t value = 0;
+              if (GetVReg(m, reg, kind, &value)) {
+                new_frame->SetVReg(reg, value);
+              } else {
+                new_frame->SetVReg(reg, kDeadValue);
+              }
             }
-          }
-          break;
-        case kDoubleLoVReg:
-          if (GetVRegKind(reg + 1, kinds) == kDoubleHiVReg) {
-            uint64_t value = 0;
-            if (GetVRegPair(m, reg, kDoubleLoVReg, kDoubleHiVReg, &value)) {
-              // Treat it as a "double" register pair.
-              new_frame->SetVRegLong(reg, value);
+            break;
+          case kLongHiVReg:
+            if (GetVRegKind(reg - 1, kinds) == kLongLoVReg) {
+              // Nothing to do: we treated it as a "long" register pair.
             } else {
-              new_frame->SetVRegLong(reg, kLongDeadValue);
+              uint32_t value = 0;
+              if (GetVReg(m, reg, kind, &value)) {
+                new_frame->SetVReg(reg, value);
+              } else {
+                new_frame->SetVReg(reg, kDeadValue);
+              }
             }
-          } else {
-            uint32_t value = 0;
-            if (GetVReg(m, reg, kind, &value)) {
-              new_frame->SetVReg(reg, value);
+            break;
+          case kDoubleLoVReg:
+            if (GetVRegKind(reg + 1, kinds) == kDoubleHiVReg) {
+              uint64_t value = 0;
+              if (GetVRegPair(m, reg, kDoubleLoVReg, kDoubleHiVReg, &value)) {
+                // Treat it as a "double" register pair.
+                new_frame->SetVRegLong(reg, value);
+              } else {
+                new_frame->SetVRegLong(reg, kLongDeadValue);
+              }
             } else {
-              new_frame->SetVReg(reg, kDeadValue);
+              uint32_t value = 0;
+              if (GetVReg(m, reg, kind, &value)) {
+                new_frame->SetVReg(reg, value);
+              } else {
+                new_frame->SetVReg(reg, kDeadValue);
+              }
             }
-          }
-          break;
-        case kDoubleHiVReg:
-          if (GetVRegKind(reg - 1, kinds) == kDoubleLoVReg) {
-            // Nothing to do: we treated it as a "double" register pair.
-          } else {
+            break;
+          case kDoubleHiVReg:
+            if (GetVRegKind(reg - 1, kinds) == kDoubleLoVReg) {
+              // Nothing to do: we treated it as a "double" register pair.
+            } else {
+              uint32_t value = 0;
+              if (GetVReg(m, reg, kind, &value)) {
+                new_frame->SetVReg(reg, value);
+              } else {
+                new_frame->SetVReg(reg, kDeadValue);
+              }
+            }
+            break;
+          default:
             uint32_t value = 0;
             if (GetVReg(m, reg, kind, &value)) {
               new_frame->SetVReg(reg, value);
             } else {
               new_frame->SetVReg(reg, kDeadValue);
             }
-          }
-          break;
-        default:
-          uint32_t value = 0;
-          if (GetVReg(m, reg, kind, &value)) {
-            new_frame->SetVReg(reg, value);
-          } else {
-            new_frame->SetVReg(reg, kDeadValue);
-          }
-          break;
+            break;
+        }
       }
     }
     if (prev_shadow_frame_ != nullptr) {
       prev_shadow_frame_->SetLink(new_frame);
     } else {
-      self_->SetDeoptimizationShadowFrame(new_frame);
+      // Will be popped after the long jump after DeoptimizeStack(),
+      // right before interpreter::EnterInterpreterFromDeoptimize().
+      stacked_shadow_frame_pushed_ = true;
+      self_->PushStackedShadowFrame(new_frame, kDeoptimizationShadowFrame);
     }
-    self_->ClearShadowFrameUnderConstruction();
     prev_shadow_frame_ = new_frame;
     return true;
   }
@@ -316,6 +327,7 @@ class DeoptimizeStackVisitor FINAL : public StackVisitor {
   Thread* const self_;
   QuickExceptionHandler* const exception_handler_;
   ShadowFrame* prev_shadow_frame_;
+  bool stacked_shadow_frame_pushed_;
 
   DISALLOW_COPY_AND_ASSIGN(DeoptimizeStackVisitor);
 };
diff --git a/runtime/thread.cc b/runtime/thread.cc
index 29635a4..e79c5e6 100644
--- a/runtime/thread.cc
+++ b/runtime/thread.cc
@@ -147,29 +147,38 @@ void Thread::ResetQuickAllocEntryPointsForThread() {
   ResetQuickAllocEntryPoints(&tlsPtr_.quick_entrypoints);
 }
 
-void Thread::SetDeoptimizationShadowFrame(ShadowFrame* sf) {
-  tlsPtr_.deoptimization_shadow_frame = sf;
+void Thread::PushAndClearDeoptimizationReturnValue() {
+  DeoptimizationReturnValueRecord* record = new DeoptimizationReturnValueRecord(
+      tls64_.deoptimization_return_value,
+      tls32_.deoptimization_return_value_is_reference,
+      tlsPtr_.deoptimization_return_value_stack);
+  tlsPtr_.deoptimization_return_value_stack = record;
+  ClearDeoptimizationReturnValue();
 }
 
-void Thread::SetDeoptimizationReturnValue(const JValue& ret_val) {
-  tls64_.deoptimization_return_value.SetJ(ret_val.GetJ());
+JValue Thread::PopDeoptimizationReturnValue() {
+  DeoptimizationReturnValueRecord* record = tlsPtr_.deoptimization_return_value_stack;
+  DCHECK(record != nullptr);
+  tlsPtr_.deoptimization_return_value_stack = record->GetLink();
+  JValue ret_val(record->GetReturnValue());
+  delete record;
+  return ret_val;
 }
 
-ShadowFrame* Thread::GetAndClearDeoptimizationShadowFrame(JValue* ret_val) {
-  ShadowFrame* sf = tlsPtr_.deoptimization_shadow_frame;
-  tlsPtr_.deoptimization_shadow_frame = nullptr;
-  ret_val->SetJ(tls64_.deoptimization_return_value.GetJ());
-  return sf;
+void Thread::PushStackedShadowFrame(ShadowFrame* sf, StackedShadowFrameType type) {
+  StackedShadowFrameRecord* record = new StackedShadowFrameRecord(
+      sf, type, tlsPtr_.stacked_shadow_frame_record);
+  tlsPtr_.stacked_shadow_frame_record = record;
 }
 
-void Thread::SetShadowFrameUnderConstruction(ShadowFrame* sf) {
-  sf->SetLink(tlsPtr_.shadow_frame_under_construction);
-  tlsPtr_.shadow_frame_under_construction = sf;
-}
-
-void Thread::ClearShadowFrameUnderConstruction() {
-  CHECK_NE(static_cast<ShadowFrame*>(nullptr), tlsPtr_.shadow_frame_under_construction);
-  tlsPtr_.shadow_frame_under_construction = tlsPtr_.shadow_frame_under_construction->GetLink();
+ShadowFrame* Thread::PopStackedShadowFrame(StackedShadowFrameType type) {
+  StackedShadowFrameRecord* record = tlsPtr_.stacked_shadow_frame_record;
+  DCHECK(record != nullptr);
+  DCHECK(record->GetType() == type);
+  tlsPtr_.stacked_shadow_frame_record = record->GetLink();
+  ShadowFrame* shadow_frame = record->GetShadowFrame();
+  delete record;
+  return shadow_frame;
 }
 
 void Thread::InitTid() {
@@ -2385,21 +2394,27 @@ void Thread::VisitRoots(RootVisitor* visitor) {
   if (tlsPtr_.debug_invoke_req != nullptr) {
     tlsPtr_.debug_invoke_req->VisitRoots(visitor, RootInfo(kRootDebugger, thread_id));
   }
-  if (tlsPtr_.deoptimization_shadow_frame != nullptr) {
+  if (tlsPtr_.stacked_shadow_frame_record != nullptr) {
     RootCallbackVisitor visitor_to_callback(visitor, thread_id);
     ReferenceMapVisitor<RootCallbackVisitor> mapper(this, nullptr, visitor_to_callback);
-    for (ShadowFrame* shadow_frame = tlsPtr_.deoptimization_shadow_frame; shadow_frame != nullptr;
-        shadow_frame = shadow_frame->GetLink()) {
-      mapper.VisitShadowFrame(shadow_frame);
+    for (StackedShadowFrameRecord* record = tlsPtr_.stacked_shadow_frame_record;
+         record != nullptr;
+         record = record->GetLink()) {
+      for (ShadowFrame* shadow_frame = record->GetShadowFrame();
+           shadow_frame != nullptr;
+           shadow_frame = shadow_frame->GetLink()) {
+        mapper.VisitShadowFrame(shadow_frame);
+      }
     }
   }
-  if (tlsPtr_.shadow_frame_under_construction != nullptr) {
-    RootCallbackVisitor visitor_to_callback(visitor, thread_id);
-    ReferenceMapVisitor<RootCallbackVisitor> mapper(this, nullptr, visitor_to_callback);
-    for (ShadowFrame* shadow_frame = tlsPtr_.shadow_frame_under_construction;
-        shadow_frame != nullptr;
-        shadow_frame = shadow_frame->GetLink()) {
-      mapper.VisitShadowFrame(shadow_frame);
+  if (tlsPtr_.deoptimization_return_value_stack != nullptr) {
+    for (DeoptimizationReturnValueRecord* record = tlsPtr_.deoptimization_return_value_stack;
+         record != nullptr;
+         record = record->GetLink()) {
+      if (record->IsReference()) {
+        visitor->VisitRootIfNonNull(record->GetGCRoot(),
+            RootInfo(kRootThreadObject, thread_id));
+      }
     }
   }
   for (auto* verifier = tlsPtr_.method_verifier; verifier != nullptr; verifier = verifier->link_) {
diff --git a/runtime/thread.h b/runtime/thread.h
index 27f029e..8eb92bc 100644
--- a/runtime/thread.h
+++ b/runtime/thread.h
@@ -99,6 +99,55 @@ enum ThreadFlag {
   kCheckpointRequest = 2  // Request that the thread do some checkpoint work and then continue.
 };
 
+enum StackedShadowFrameType {
+  kShadowFrameUnderConstruction,
+  kDeoptimizationShadowFrame
+};
+
+class StackedShadowFrameRecord {
+ public:
+  StackedShadowFrameRecord(ShadowFrame* shadow_frame,
+                           StackedShadowFrameType type,
+                           StackedShadowFrameRecord* link)
+      : shadow_frame_(shadow_frame),
+        type_(type),
+        link_(link) {}
+
+  ShadowFrame* GetShadowFrame() const { return shadow_frame_; }
+  bool GetType() const { return type_; }
+  StackedShadowFrameRecord* GetLink() const { return link_; }
+
+ private:
+  ShadowFrame* const shadow_frame_;
+  const StackedShadowFrameType type_;
+  StackedShadowFrameRecord* const link_;
+
+  DISALLOW_COPY_AND_ASSIGN(StackedShadowFrameRecord);
+};
+
+class DeoptimizationReturnValueRecord {
+ public:
+  DeoptimizationReturnValueRecord(const JValue& ret_val,
+                                  bool is_reference,
+                                  DeoptimizationReturnValueRecord* link)
+      : ret_val_(ret_val), is_reference_(is_reference), link_(link) {}
+
+  JValue GetReturnValue() const { return ret_val_; }
+  bool IsReference() const { return is_reference_; }
+  DeoptimizationReturnValueRecord* GetLink() const { return link_; }
+  mirror::Object** GetGCRoot() {
+    DCHECK(is_reference_);
+    return ret_val_.GetGCRoot();
+  }
+
+ private:
+  JValue ret_val_;
+  const bool is_reference_;
+  DeoptimizationReturnValueRecord* const link_;
+
+  DISALLOW_COPY_AND_ASSIGN(DeoptimizationReturnValueRecord);
+};
+
 static constexpr size_t kNumRosAllocThreadLocalSizeBrackets = 34;
 
 // Thread's stack layout for implicit stack overflow checks:
@@ -789,21 +838,25 @@ class Thread {
     return reinterpret_cast<mirror::Throwable*>(-1);
   }
 
-  void SetDeoptimizationShadowFrame(ShadowFrame* sf);
-  void SetDeoptimizationReturnValue(const JValue& ret_val);
-
-  ShadowFrame* GetAndClearDeoptimizationShadowFrame(JValue* ret_val);
-
-  bool HasDeoptimizationShadowFrame() const {
-    return tlsPtr_.deoptimization_shadow_frame != nullptr;
+  // Currently deoptimization invokes verifier which can trigger class loading
+  // and execute Java code, so there might be nested deoptimizations happening.
+  // We need to save the ongoing deoptimization shadow frames and return
+  // values on stacks.
+  void SetDeoptimizationReturnValue(const JValue& ret_val, bool is_reference) {
+    tls64_.deoptimization_return_value.SetJ(ret_val.GetJ());
+    tls32_.deoptimization_return_value_is_reference = is_reference;
   }
-
-  void SetShadowFrameUnderConstruction(ShadowFrame* sf);
-  void ClearShadowFrameUnderConstruction();
-
-  bool HasShadowFrameUnderConstruction() const {
-    return tlsPtr_.shadow_frame_under_construction != nullptr;
+  bool IsDeoptimizationReturnValueReference() {
+    return tls32_.deoptimization_return_value_is_reference;
+  }
+  void ClearDeoptimizationReturnValue() {
+    tls64_.deoptimization_return_value.SetJ(0);
+    tls32_.deoptimization_return_value_is_reference = false;
   }
+  void PushAndClearDeoptimizationReturnValue();
+  JValue PopDeoptimizationReturnValue();
+  void PushStackedShadowFrame(ShadowFrame* sf, StackedShadowFrameType type);
+  ShadowFrame* PopStackedShadowFrame(StackedShadowFrameType type);
 
   std::deque<instrumentation::InstrumentationStackFrame>* GetInstrumentationStack() {
     return tlsPtr_.instrumentation_stack;
@@ -1047,7 +1100,8 @@ class Thread {
     explicit tls_32bit_sized_values(bool is_daemon) :
       suspend_count(0), debug_suspend_count(0), thin_lock_thread_id(0), tid(0),
       daemon(is_daemon), throwing_OutOfMemoryError(false), no_thread_suspension(0),
-      thread_exit_check_count(0), handling_signal_(false), suspended_at_suspend_check(false),
+      thread_exit_check_count(0), handling_signal_(false),
+      deoptimization_return_value_is_reference(false), suspended_at_suspend_check(false),
       ready_for_debug_invoke(false), debug_method_entry_(false) {
     }
 
@@ -1088,6 +1142,10 @@ class Thread {
     // True if signal is being handled by this thread.
     bool32_t handling_signal_;
 
+    // True if the return value for interpreter after deoptimization is a reference.
+    // For gc purpose.
+    bool32_t deoptimization_return_value_is_reference;
+
     // True if the thread is suspended in FullSuspendCheck(). This is
     // used to distinguish runnable threads that are suspended due to
     // a normal suspend check from other threads.
@@ -1123,8 +1181,9 @@ class Thread {
       stack_trace_sample(nullptr), wait_next(nullptr), monitor_enter_object(nullptr),
       top_handle_scope(nullptr), class_loader_override(nullptr), long_jump_context(nullptr),
       instrumentation_stack(nullptr), debug_invoke_req(nullptr), single_step_control(nullptr),
-      deoptimization_shadow_frame(nullptr), shadow_frame_under_construction(nullptr), name(nullptr),
-      pthread_self(0), last_no_thread_suspension_cause(nullptr), thread_local_start(nullptr),
+      stacked_shadow_frame_record(nullptr), deoptimization_return_value_stack(nullptr),
+      name(nullptr), pthread_self(0),
+      last_no_thread_suspension_cause(nullptr), thread_local_start(nullptr),
       thread_local_pos(nullptr), thread_local_end(nullptr), thread_local_objects(0),
       thread_local_alloc_stack_top(nullptr), thread_local_alloc_stack_end(nullptr),
       nested_signal_state(nullptr), flip_function(nullptr), method_verifier(nullptr) {
@@ -1200,11 +1259,13 @@ class Thread {
     // JDWP single-stepping support.
     SingleStepControl* single_step_control;
 
-    // Shadow frame stack that is used temporarily during the deoptimization of a method.
-    ShadowFrame* deoptimization_shadow_frame;
+    // For gc purpose, a shadow frame record stack that keeps track of:
+    // 1) shadow frames under construction.
+    // 2) deoptimization shadow frames.
+    StackedShadowFrameRecord* stacked_shadow_frame_record;
 
-    // Shadow frame stack that is currently under construction but not yet on the stack
-    ShadowFrame* shadow_frame_under_construction;
+    // Deoptimization return value record stack.
+    DeoptimizationReturnValueRecord* deoptimization_return_value_stack;
 
     // A cached copy of the java.lang.Thread's name.
     std::string* name;
@@ -1292,6 +1353,23 @@ class ScopedAssertNoThreadSuspension {
   const char* const old_cause_;
 };
 
+class ScopedStackedShadowFramePusher {
+ public:
+  ScopedStackedShadowFramePusher(Thread* self, ShadowFrame* sf, StackedShadowFrameType type)
+    : self_(self), type_(type) {
+    self_->PushStackedShadowFrame(sf, type);
+  }
+  ~ScopedStackedShadowFramePusher() {
+    self_->PopStackedShadowFrame(type_);
+  }
+
+ private:
+  Thread* const self_;
+  const StackedShadowFrameType type_;
+
+  DISALLOW_COPY_AND_ASSIGN(ScopedStackedShadowFramePusher);
+};
+
 std::ostream& operator<<(std::ostream& os, const Thread& thread);
 
 }  // namespace art