diff --git a/runtime/debugger.cc b/runtime/debugger.cc
index e1aca2f..a131e32 100644
--- a/runtime/debugger.cc
+++ b/runtime/debugger.cc
@@ -3490,6 +3490,62 @@
   return instrumentation->IsDeoptimized(m);
 }
 
+struct NeedsDeoptimizationVisitor : public StackVisitor {
+ public:
+  explicit NeedsDeoptimizationVisitor(Thread* self)
+      SHARED_REQUIRES(Locks::mutator_lock_)
+    : StackVisitor(self, nullptr, StackVisitor::StackWalkKind::kIncludeInlinedFrames),
+      needs_deoptimization_(false) {}
+
+  bool VisitFrame() OVERRIDE SHARED_REQUIRES(Locks::mutator_lock_) {
+    // The visitor is meant to be used when handling exception from compiled code only.
+    CHECK(!IsShadowFrame()) << "We only expect to visit compiled frame: " << PrettyMethod(GetMethod());
+    ArtMethod* method = GetMethod();
+    if (method == nullptr) {
+      // We reach an upcall and don't need to deoptimize this part of the stack (ManagedFragment)
+      // so we can stop the visit.
+      DCHECK(!needs_deoptimization_);
+      return false;
+    }
+    if (Runtime::Current()->GetInstrumentation()->InterpretOnly()) {
+      // We found a compiled frame in the stack but instrumentation is set to interpret
+      // everything: we need to deoptimize.
+      needs_deoptimization_ = true;
+      return false;
+    }
+    if (Runtime::Current()->GetInstrumentation()->IsDeoptimized(method)) {
+      // We found a deoptimized method in the stack.
+      needs_deoptimization_ = true;
+      return false;
+    }
+    return true;
+  }
+
+  bool NeedsDeoptimization() const {
+    return needs_deoptimization_;
+  }
+
+ private:
+  // Do we need to deoptimize the stack?
+  bool needs_deoptimization_;
+
+  DISALLOW_COPY_AND_ASSIGN(NeedsDeoptimizationVisitor);
+};
+
+// Do we need to deoptimize the stack to handle an exception?
+bool Dbg::IsForcedInterpreterNeededForExceptionImpl(Thread* thread) {
+  const SingleStepControl* const ssc = thread->GetSingleStepControl();
+  if (ssc != nullptr) {
+    // We deopt to step into the catch handler.
+    return true;
+  }
+  // Deoptimization is required if at least one method in the stack needs it. However we
+  // skip frames that will be unwound (thus not executed).
+  NeedsDeoptimizationVisitor visitor(thread);
+  visitor.WalkStack(true);  // includes upcall.
+  return visitor.NeedsDeoptimization();
+}
+
 // Scoped utility class to suspend a thread so that we may do tasks such as walk its stack. Doesn't
 // cause suspension if the thread is the current thread.
 class ScopedDebuggerThreadSuspension {
diff --git a/runtime/debugger.h b/runtime/debugger.h
index a9fa6ce..8278fc6 100644
--- a/runtime/debugger.h
+++ b/runtime/debugger.h
@@ -576,6 +576,19 @@
     return IsForcedInterpreterNeededForUpcallImpl(thread, m);
   }
 
+  // Indicates whether we need to force the use of interpreter when handling an
+  // exception. This allows to deoptimize the stack and continue execution with
+  // the interpreter.
+  // Note: the interpreter will start by handling the exception when executing
+  // the deoptimized frames.
+  static bool IsForcedInterpreterNeededForException(Thread* thread)
+      SHARED_REQUIRES(Locks::mutator_lock_) {
+    if (!IsDebuggerActive()) {
+      return false;
+    }
+    return IsForcedInterpreterNeededForExceptionImpl(thread);
+  }
+
   // Single-stepping.
   static JDWP::JdwpError ConfigureStep(JDWP::ObjectId thread_id, JDWP::JdwpStepSize size,
                                        JDWP::JdwpStepDepth depth)
@@ -734,6 +747,9 @@
   static bool IsForcedInterpreterNeededForUpcallImpl(Thread* thread, ArtMethod* m)
       SHARED_REQUIRES(Locks::mutator_lock_);
 
+  static bool IsForcedInterpreterNeededForExceptionImpl(Thread* thread)
+      SHARED_REQUIRES(Locks::mutator_lock_);
+
   // Indicates whether the debugger is making requests.
   static bool gDebuggerActive;
 
diff --git a/runtime/interpreter/interpreter.cc b/runtime/interpreter/interpreter.cc
index 6c6232c..3ac80c6 100644
--- a/runtime/interpreter/interpreter.cc
+++ b/runtime/interpreter/interpreter.cc
@@ -399,14 +399,19 @@
   JValue value;
   // Set value to last known result in case the shadow frame chain is empty.
   value.SetJ(ret_val->GetJ());
+  // Are we executing the first shadow frame?
+  bool first = true;
   while (shadow_frame != nullptr) {
     self->SetTopOfShadowStack(shadow_frame);
     const DexFile::CodeItem* code_item = shadow_frame->GetMethod()->GetCodeItem();
     const uint32_t dex_pc = shadow_frame->GetDexPC();
     uint32_t new_dex_pc;
     if (UNLIKELY(self->IsExceptionPending())) {
+      // If we deoptimize from the QuickExceptionHandler, we already reported the exception to
+      // the instrumentation. To prevent from reporting it a second time, we simply pass a
+      // null Instrumentation*.
       const instrumentation::Instrumentation* const instrumentation =
-          Runtime::Current()->GetInstrumentation();
+          first ? nullptr : Runtime::Current()->GetInstrumentation();
       uint32_t found_dex_pc = FindNextInstructionFollowingException(self, *shadow_frame, dex_pc,
                                                                     instrumentation);
       new_dex_pc = found_dex_pc;  // the dex pc of a matching catch handler
@@ -424,6 +429,7 @@
     ShadowFrame* old_frame = shadow_frame;
     shadow_frame = shadow_frame->GetLink();
     ShadowFrame::DeleteDeoptimizedFrame(old_frame);
+    first = false;
   }
   ret_val->SetJ(value.GetJ());
 }
diff --git a/runtime/interpreter/interpreter_common.cc b/runtime/interpreter/interpreter_common.cc
index af67379..6602840 100644
--- a/runtime/interpreter/interpreter_common.cc
+++ b/runtime/interpreter/interpreter_common.cc
@@ -414,20 +414,21 @@
 #undef EXPLICIT_DO_IPUT_QUICK_ALL_TEMPLATE_DECL
 #undef EXPLICIT_DO_IPUT_QUICK_TEMPLATE_DECL
 
+// We accept a null Instrumentation* meaning we must not report anything to the instrumentation.
 uint32_t FindNextInstructionFollowingException(
     Thread* self, ShadowFrame& shadow_frame, uint32_t dex_pc,
     const instrumentation::Instrumentation* instrumentation) {
   self->VerifyStack();
   StackHandleScope<2> hs(self);
   Handle<mirror::Throwable> exception(hs.NewHandle(self->GetException()));
-  if (instrumentation->HasExceptionCaughtListeners()
+  if (instrumentation != nullptr && instrumentation->HasExceptionCaughtListeners()
       && self->IsExceptionThrownByCurrentMethod(exception.Get())) {
     instrumentation->ExceptionCaughtEvent(self, exception.Get());
   }
   bool clear_exception = false;
   uint32_t found_dex_pc = shadow_frame.GetMethod()->FindCatchBlock(
       hs.NewHandle(exception->GetClass()), dex_pc, &clear_exception);
-  if (found_dex_pc == DexFile::kDexNoIndex) {
+  if (found_dex_pc == DexFile::kDexNoIndex && instrumentation != nullptr) {
     // Exception is not caught by the current method. We will unwind to the
     // caller. Notify any instrumentation listener.
     instrumentation->MethodUnwindEvent(self, shadow_frame.GetThisObject(),
diff --git a/runtime/quick_exception_handler.cc b/runtime/quick_exception_handler.cc
index 9d5ce9f..60defba 100644
--- a/runtime/quick_exception_handler.cc
+++ b/runtime/quick_exception_handler.cc
@@ -40,7 +40,7 @@
     handler_dex_pc_(0), clear_exception_(false), handler_frame_depth_(kInvalidFrameDepth) {
 }
 
-// Finds catch handler or prepares for deoptimization.
+// Finds catch handler.
 class CatchBlockStackVisitor FINAL : public StackVisitor {
  public:
   CatchBlockStackVisitor(Thread* self, Context* context, Handle<mirror::Throwable>* exception,
@@ -125,7 +125,7 @@
   StackHandleScope<1> hs(self_);
   Handle<mirror::Throwable> exception_ref(hs.NewHandle(exception));
 
-  // Walk the stack to find catch handler or prepare for deoptimization.
+  // Walk the stack to find catch handler.
   CatchBlockStackVisitor visitor(self_, context_, &exception_ref, this);
   visitor.WalkStack(true);
 
@@ -146,16 +146,6 @@
     // Put exception back in root set with clear throw location.
     self_->SetException(exception_ref.Get());
   }
-  // The debugger may suspend this thread and walk its stack. Let's do this before popping
-  // instrumentation frames.
-  instrumentation::Instrumentation* instrumentation = Runtime::Current()->GetInstrumentation();
-  if (instrumentation->HasExceptionCaughtListeners()
-      && self_->IsExceptionThrownByCurrentMethod(exception)) {
-    instrumentation->ExceptionCaughtEvent(self_, exception_ref.Get());
-    // Instrumentation may have been updated.
-    method_tracing_active_ = is_deoptimization_ ||
-        Runtime::Current()->GetInstrumentation()->AreExitStubsInstalled();
-  }
 }
 
 // Prepares deoptimization.
@@ -189,6 +179,12 @@
       // Ignore callee save method.
       DCHECK(method->IsCalleeSaveMethod());
       return true;
+    } else if (method->IsNative()) {
+      // If we return from JNI with a pending exception and want to deoptimize, we need to skip
+      // the native method.
+      // The top method is a runtime method, the native method comes next.
+      CHECK_EQ(GetFrameDepth(), 1U);
+      return true;
     } else {
       return HandleDeoptimization(method);
     }
@@ -201,7 +197,7 @@
 
   bool HandleDeoptimization(ArtMethod* m) SHARED_REQUIRES(Locks::mutator_lock_) {
     const DexFile::CodeItem* code_item = m->GetCodeItem();
-    CHECK(code_item != nullptr);
+    CHECK(code_item != nullptr) << "No code item for " << PrettyMethod(m);
     uint16_t num_regs = code_item->registers_size_;
     uint32_t dex_pc = GetDexPc();
     StackHandleScope<2> hs(self_);  // Dex cache, class loader and method.
diff --git a/runtime/quick_exception_handler.h b/runtime/quick_exception_handler.h
index e934834..4db95a8 100644
--- a/runtime/quick_exception_handler.h
+++ b/runtime/quick_exception_handler.h
@@ -43,9 +43,18 @@
     UNREACHABLE();
   }
 
+  // Find the catch handler for the given exception.
   void FindCatch(mirror::Throwable* exception) SHARED_REQUIRES(Locks::mutator_lock_);
+
+  // Deoptimize the stack to the upcall. For every compiled frame, we create a "copy"
+  // shadow frame that will be executed with the interpreter.
   void DeoptimizeStack() SHARED_REQUIRES(Locks::mutator_lock_);
+
+  // Update the instrumentation stack by removing all methods that will be unwound
+  // by the exception being thrown.
   void UpdateInstrumentationStack() SHARED_REQUIRES(Locks::mutator_lock_);
+
+  // Long jump either to a catch handler or to the upcall.
   NO_RETURN void DoLongJump() SHARED_REQUIRES(Locks::mutator_lock_);
 
   void SetHandlerQuickFrame(ArtMethod** handler_quick_frame) {
@@ -83,9 +92,10 @@
  private:
   Thread* const self_;
   Context* const context_;
+  // Should we deoptimize the stack?
   const bool is_deoptimization_;
   // Is method tracing active?
-  bool method_tracing_active_;
+  const bool method_tracing_active_;
   // Quick frame with found handler or last frame if no handler found.
   ArtMethod** handler_quick_frame_;
   // PC to branch to for the handler.
diff --git a/runtime/thread.cc b/runtime/thread.cc
index af5830a..86ac140 100644
--- a/runtime/thread.cc
+++ b/runtime/thread.cc
@@ -2344,10 +2344,31 @@
   // Get exception from thread.
   mirror::Throwable* exception = GetException();
   CHECK(exception != nullptr);
+  bool is_deoptimization = (exception == GetDeoptimizationException());
+  if (!is_deoptimization) {
+    // This is a real exception: let the instrumentation know about it.
+    instrumentation::Instrumentation* instrumentation = Runtime::Current()->GetInstrumentation();
+    if (instrumentation->HasExceptionCaughtListeners() &&
+        IsExceptionThrownByCurrentMethod(exception)) {
+      // Instrumentation may cause GC so keep the exception object safe.
+      StackHandleScope<1> hs(this);
+      HandleWrapper<mirror::Throwable> h_exception(hs.NewHandleWrapper(&exception));
+      instrumentation->ExceptionCaughtEvent(this, exception);
+    }
+    // Does instrumentation need to deoptimize the stack?
+    // Note: we do this *after* reporting the exception to instrumentation in case it
+    // now requires deoptimization. It may happen if a debugger is attached and requests
+    // new events (single-step, breakpoint, ...) when the exception is reported.
+    is_deoptimization = Dbg::IsForcedInterpreterNeededForException(this);
+    if (is_deoptimization) {
+      // Save the exception into the deoptimization context so it can be restored
+      // before entering the interpreter.
+      PushDeoptimizationContext(JValue(), false, exception);
+    }
+  }
   // Don't leave exception visible while we try to find the handler, which may cause class
   // resolution.
   ClearException();
-  bool is_deoptimization = (exception == GetDeoptimizationException());
   QuickExceptionHandler exception_handler(this, is_deoptimization);
   if (is_deoptimization) {
     exception_handler.DeoptimizeStack();