diff --git a/runtime/instrumentation.cc b/runtime/instrumentation.cc
index 1ddca87..d25893f 100644
--- a/runtime/instrumentation.cc
+++ b/runtime/instrumentation.cc
@@ -94,6 +94,56 @@
   Instrumentation* const instrumentation_;
 };
 
+InstrumentationStackPopper::InstrumentationStackPopper(Thread* self)
+      : self_(self),
+        instrumentation_(Runtime::Current()->GetInstrumentation()),
+        frames_to_remove_(0) {}
+
+InstrumentationStackPopper::~InstrumentationStackPopper() {
+  std::deque<instrumentation::InstrumentationStackFrame>* stack = self_->GetInstrumentationStack();
+  for (size_t i = 0; i < frames_to_remove_; i++) {
+    stack->pop_front();
+  }
+}
+
+bool InstrumentationStackPopper::PopFramesTo(uint32_t desired_pops,
+                                             MutableHandle<mirror::Throwable>& exception) {
+  std::deque<instrumentation::InstrumentationStackFrame>* stack = self_->GetInstrumentationStack();
+  DCHECK_LE(frames_to_remove_, desired_pops);
+  DCHECK_GE(stack->size(), desired_pops);
+  DCHECK(!self_->IsExceptionPending());
+  if (!instrumentation_->HasMethodUnwindListeners()) {
+    frames_to_remove_ = desired_pops;
+    return true;
+  }
+  if (kVerboseInstrumentation) {
+    LOG(INFO) << "Popping frames for exception " << exception->Dump();
+  }
+  // The instrumentation events expect the exception to be set.
+  self_->SetException(exception.Get());
+  bool new_exception_thrown = false;
+  for (; frames_to_remove_ < desired_pops && !new_exception_thrown; frames_to_remove_++) {
+    InstrumentationStackFrame frame = stack->at(frames_to_remove_);
+    ArtMethod* method = frame.method_;
+    // Notify listeners of method unwind.
+    // TODO: improve the dex_pc information here.
+    uint32_t dex_pc = dex::kDexNoIndex;
+    if (kVerboseInstrumentation) {
+      LOG(INFO) << "Popping for unwind " << method->PrettyMethod();
+    }
+    if (!method->IsRuntimeMethod() && !frame.interpreter_entry_) {
+      instrumentation_->MethodUnwindEvent(self_, frame.this_object_, method, dex_pc);
+      new_exception_thrown = self_->GetException() != exception.Get();
+    }
+  }
+  exception.Assign(self_->GetException());
+  self_->ClearException();
+  if (kVerboseInstrumentation && new_exception_thrown) {
+    LOG(INFO) << "Failed to pop " << (desired_pops - frames_to_remove_)
+              << " frames due to new exception";
+  }
+  return !new_exception_thrown;
+}
 
 Instrumentation::Instrumentation()
     : instrumentation_stubs_installed_(false),
@@ -1495,36 +1545,29 @@
   }
 }
 
-uintptr_t Instrumentation::PopMethodForUnwind(Thread* self, bool is_deoptimization) const {
-  // Do the pop.
+uintptr_t Instrumentation::PopFramesForDeoptimization(Thread* self, size_t nframes) const {
   std::deque<instrumentation::InstrumentationStackFrame>* stack = self->GetInstrumentationStack();
-  CHECK_GT(stack->size(), 0U);
-  size_t idx = stack->size();
-  InstrumentationStackFrame instrumentation_frame = stack->front();
-
-  ArtMethod* method = instrumentation_frame.method_;
-  if (is_deoptimization) {
-    if (kVerboseInstrumentation) {
-      LOG(INFO) << "Popping for deoptimization " << ArtMethod::PrettyMethod(method);
-    }
-  } else {
-    if (kVerboseInstrumentation) {
-      LOG(INFO) << "Popping for unwind " << ArtMethod::PrettyMethod(method);
-    }
-
-    // Notify listeners of method unwind.
-    // TODO: improve the dex pc information here, requires knowledge of current PC as opposed to
-    //       return_pc.
-    uint32_t dex_pc = dex::kDexNoIndex;
-    if (!method->IsRuntimeMethod()) {
-      MethodUnwindEvent(self, instrumentation_frame.this_object_, method, dex_pc);
+  CHECK_GE(stack->size(), nframes);
+  if (nframes == 0) {
+    return 0u;
+  }
+  // Only need to send instrumentation events if it's not for deopt (do give the log messages if we
+  // have verbose-instrumentation anyway though).
+  if (kVerboseInstrumentation) {
+    for (size_t i = 0; i < nframes; i++) {
+      LOG(INFO) << "Popping for deoptimization " << stack->at(i).method_->PrettyMethod();
     }
   }
-  // TODO: bring back CheckStackDepth(self, instrumentation_frame, 2);
-  CHECK_EQ(stack->size(), idx);
-  DCHECK(instrumentation_frame.method_ == stack->front().method_);
+  // Now that we've sent all the instrumentation events we can actually modify the
+  // instrumentation-stack. We cannot do this earlier since MethodUnwindEvent can re-enter java and
+  // do other things that require the instrumentation stack to be in a consistent state with the
+  // actual stack.
+  for (size_t i = 0; i < nframes - 1; i++) {
+    stack->pop_front();
+  }
+  uintptr_t return_pc = stack->front().return_pc_;
   stack->pop_front();
-  return instrumentation_frame.return_pc_;
+  return return_pc;
 }
 
 std::string InstrumentationStackFrame::Dump() const {
diff --git a/runtime/instrumentation.h b/runtime/instrumentation.h
index bc54ba2..0e366d3 100644
--- a/runtime/instrumentation.h
+++ b/runtime/instrumentation.h
@@ -37,6 +37,7 @@
 class ArtField;
 class ArtMethod;
 template <typename T> class Handle;
+template <typename T> class MutableHandle;
 union JValue;
 class ShadowFrame;
 class Thread;
@@ -158,6 +159,25 @@
       REQUIRES_SHARED(Locks::mutator_lock_) = 0;
 };
 
+class Instrumentation;
+// A helper to send instrumentation events while popping the stack in a safe way.
+class InstrumentationStackPopper {
+ public:
+  explicit InstrumentationStackPopper(Thread* self);
+  ~InstrumentationStackPopper() REQUIRES_SHARED(Locks::mutator_lock_);
+
+  // Increase the number of frames being popped to 'desired_pops' return true if the frames were
+  // popped without any exceptions, false otherwise. The exception that caused the pop is
+  // 'exception'.
+  bool PopFramesTo(uint32_t desired_pops, /*in-out*/MutableHandle<mirror::Throwable>& exception)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
+ private:
+  Thread* self_;
+  Instrumentation* instrumentation_;
+  uint32_t frames_to_remove_;
+};
+
 // Instrumentation is a catch-all for when extra information is required from the runtime. The
 // typical use for instrumentation is for profiling and debugging. Instrumentation may add stubs
 // to method entry and exit, it may also force execution to be switched to the interpreter and
@@ -498,9 +518,9 @@
                                              uint64_t* gpr_result, uint64_t* fpr_result)
       REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!deoptimized_methods_lock_);
 
-  // Pops an instrumentation frame from the current thread and generate an unwind event.
-  // Returns the return pc for the instrumentation frame that's popped.
-  uintptr_t PopMethodForUnwind(Thread* self, bool is_deoptimization) const
+  // Pops nframes instrumentation frames from the current thread. Returns the return pc for the last
+  // instrumentation frame that's popped.
+  uintptr_t PopFramesForDeoptimization(Thread* self, size_t nframes) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Call back for configure stubs.
@@ -717,6 +737,7 @@
   bool alloc_entrypoints_instrumented_;
 
   friend class InstrumentationTest;  // For GetCurrentInstrumentationLevel and ConfigureStubs.
+  friend class InstrumentationStackPopper;  // For popping instrumentation frames.
 
   DISALLOW_COPY_AND_ASSIGN(Instrumentation);
 };
diff --git a/runtime/quick_exception_handler.cc b/runtime/quick_exception_handler.cc
index e8d9658..7f5717f 100644
--- a/runtime/quick_exception_handler.cc
+++ b/runtime/quick_exception_handler.cc
@@ -60,18 +60,24 @@
 // Finds catch handler.
 class CatchBlockStackVisitor FINAL : public StackVisitor {
  public:
-  CatchBlockStackVisitor(Thread* self, Context* context, Handle<mirror::Throwable>* exception,
-                         QuickExceptionHandler* exception_handler)
+  CatchBlockStackVisitor(Thread* self,
+                         Context* context,
+                         Handle<mirror::Throwable>* exception,
+                         QuickExceptionHandler* exception_handler,
+                         uint32_t skip_frames)
       REQUIRES_SHARED(Locks::mutator_lock_)
       : StackVisitor(self, context, StackVisitor::StackWalkKind::kIncludeInlinedFrames),
         exception_(exception),
-        exception_handler_(exception_handler) {
+        exception_handler_(exception_handler),
+        skip_frames_(skip_frames) {
   }
 
   bool VisitFrame() OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_) {
     ArtMethod* method = GetMethod();
     exception_handler_->SetHandlerFrameDepth(GetFrameDepth());
     if (method == nullptr) {
+      DCHECK_EQ(skip_frames_, 0u)
+          << "We tried to skip an upcall! We should have returned to the upcall to finish delivery";
       // 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());
@@ -90,6 +96,10 @@
       }
       return false;  // End stack walk.
     }
+    if (skip_frames_ != 0) {
+      skip_frames_--;
+      return true;
+    }
     if (method->IsRuntimeMethod()) {
       // Ignore callee save method.
       DCHECK(method->IsCalleeSaveMethod());
@@ -138,48 +148,115 @@
   Handle<mirror::Throwable>* exception_;
   // The quick exception handler we're visiting for.
   QuickExceptionHandler* const exception_handler_;
+  // The number of frames to skip searching for catches in.
+  uint32_t skip_frames_;
 
   DISALLOW_COPY_AND_ASSIGN(CatchBlockStackVisitor);
 };
 
+// Counts instrumentation stack frame prior to catch handler or upcall.
+class InstrumentationStackVisitor : public StackVisitor {
+ public:
+  InstrumentationStackVisitor(Thread* self, size_t frame_depth)
+      REQUIRES_SHARED(Locks::mutator_lock_)
+      : StackVisitor(self, nullptr, StackVisitor::StackWalkKind::kIncludeInlinedFrames),
+        frame_depth_(frame_depth),
+        instrumentation_frames_to_pop_(0) {
+    CHECK_NE(frame_depth_, kInvalidFrameDepth);
+  }
+
+  bool VisitFrame() REQUIRES_SHARED(Locks::mutator_lock_) {
+    size_t current_frame_depth = GetFrameDepth();
+    if (current_frame_depth < frame_depth_) {
+      CHECK(GetMethod() != nullptr);
+      if (UNLIKELY(reinterpret_cast<uintptr_t>(GetQuickInstrumentationExitPc()) == GetReturnPc())) {
+        if (!IsInInlinedFrame()) {
+          // We do not count inlined frames, because we do not instrument them. The reason we
+          // include them in the stack walking is the check against `frame_depth_`, which is
+          // given to us by a visitor that visits inlined frames.
+          ++instrumentation_frames_to_pop_;
+        }
+      }
+      return true;
+    } else {
+      // We reached the frame of the catch handler or the upcall.
+      return false;
+    }
+  }
+
+  size_t GetInstrumentationFramesToPop() const {
+    return instrumentation_frames_to_pop_;
+  }
+
+ private:
+  const size_t frame_depth_;
+  size_t instrumentation_frames_to_pop_;
+
+  DISALLOW_COPY_AND_ASSIGN(InstrumentationStackVisitor);
+};
+
+// Finds the appropriate exception catch after calling all method exit instrumentation functions.
+// Note that this might change the exception being thrown.
 void QuickExceptionHandler::FindCatch(ObjPtr<mirror::Throwable> exception) {
   DCHECK(!is_deoptimization_);
+  instrumentation::InstrumentationStackPopper popper(self_);
+  // The number of total frames we have so far popped.
+  uint32_t already_popped = 0;
+  bool popped_to_top = true;
   StackHandleScope<1> hs(self_);
-  Handle<mirror::Throwable> exception_ref(hs.NewHandle(exception));
-  if (kDebugExceptionDelivery) {
-    ObjPtr<mirror::String> msg = exception_ref->GetDetailMessage();
-    std::string str_msg(msg != nullptr ? msg->ToModifiedUtf8() : "");
-    self_->DumpStack(LOG_STREAM(INFO) << "Delivering exception: " << exception_ref->PrettyTypeOf()
-                     << ": " << str_msg << "\n");
-  }
-
-  // Walk the stack to find catch handler.
-  CatchBlockStackVisitor visitor(self_, context_, &exception_ref, this);
-  visitor.WalkStack(true);
-
-  if (kDebugExceptionDelivery) {
-    if (*handler_quick_frame_ == nullptr) {
-      LOG(INFO) << "Handler is upcall";
+  MutableHandle<mirror::Throwable> exception_ref(hs.NewHandle(exception));
+  // Sending the instrumentation events (done by the InstrumentationStackPopper) can cause new
+  // exceptions to be thrown which will override the current exception. Therefore we need to perform
+  // the search for a catch in a loop until we have successfully popped all the way to a catch or
+  // the top of the stack.
+  do {
+    if (kDebugExceptionDelivery) {
+      ObjPtr<mirror::String> msg = exception_ref->GetDetailMessage();
+      std::string str_msg(msg != nullptr ? msg->ToModifiedUtf8() : "");
+      self_->DumpStack(LOG_STREAM(INFO) << "Delivering exception: " << exception_ref->PrettyTypeOf()
+                                        << ": " << str_msg << "\n");
     }
-    if (handler_method_ != nullptr) {
-      const DexFile* dex_file = handler_method_->GetDeclaringClass()->GetDexCache()->GetDexFile();
-      int line_number = annotations::GetLineNumFromPC(dex_file, handler_method_, handler_dex_pc_);
-      LOG(INFO) << "Handler: " << handler_method_->PrettyMethod() << " (line: "
-                << line_number << ")";
+
+    // Walk the stack to find catch handler.
+    CatchBlockStackVisitor visitor(self_, context_, &exception_ref, this, /*skip*/already_popped);
+    visitor.WalkStack(true);
+    uint32_t new_pop_count = handler_frame_depth_;
+    DCHECK_GE(new_pop_count, already_popped);
+    already_popped = new_pop_count;
+
+    // Figure out how many of those frames have instrumentation we need to remove (Should be the
+    // exact same as number of new_pop_count if there aren't inlined frames).
+    InstrumentationStackVisitor instrumentation_visitor(self_, handler_frame_depth_);
+    instrumentation_visitor.WalkStack(true);
+    size_t instrumentation_frames_to_pop = instrumentation_visitor.GetInstrumentationFramesToPop();
+
+    if (kDebugExceptionDelivery) {
+      if (*handler_quick_frame_ == nullptr) {
+        LOG(INFO) << "Handler is upcall";
+      }
+      if (handler_method_ != nullptr) {
+        const DexFile* dex_file = handler_method_->GetDeclaringClass()->GetDexCache()->GetDexFile();
+        int line_number = annotations::GetLineNumFromPC(dex_file, handler_method_, handler_dex_pc_);
+        LOG(INFO) << "Handler: " << handler_method_->PrettyMethod() << " (line: "
+                  << line_number << ")";
+      }
+      LOG(INFO) << "Will attempt to pop " << instrumentation_frames_to_pop
+                << " off of the instrumentation stack";
     }
-  }
-  // Exception was cleared as part of delivery.
-  DCHECK(!self_->IsExceptionPending());
+    // Exception was cleared as part of delivery.
+    DCHECK(!self_->IsExceptionPending());
+    // If the handler is in optimized code, we need to set the catch environment.
+    if (*handler_quick_frame_ != nullptr &&
+        handler_method_header_ != nullptr &&
+        handler_method_header_->IsOptimized()) {
+      SetCatchEnvironmentForOptimizedHandler(&visitor);
+    }
+    popped_to_top = popper.PopFramesTo(instrumentation_frames_to_pop, exception_ref);
+  } while (!popped_to_top);
   if (!clear_exception_) {
     // Put exception back in root set with clear throw location.
     self_->SetException(exception_ref.Get());
   }
-  // If the handler is in optimized code, we need to set the catch environment.
-  if (*handler_quick_frame_ != nullptr &&
-      handler_method_header_ != nullptr &&
-      handler_method_header_->IsOptimized()) {
-    SetCatchEnvironmentForOptimizedHandler(&visitor);
-  }
 }
 
 static VRegKind ToVRegKind(DexRegisterLocation::Kind kind) {
@@ -561,48 +638,8 @@
   }
 }
 
-// Unwinds all instrumentation stack frame prior to catch handler or upcall.
-class InstrumentationStackVisitor : public StackVisitor {
- public:
-  InstrumentationStackVisitor(Thread* self, size_t frame_depth)
-      REQUIRES_SHARED(Locks::mutator_lock_)
-      : StackVisitor(self, nullptr, StackVisitor::StackWalkKind::kIncludeInlinedFrames),
-        frame_depth_(frame_depth),
-        instrumentation_frames_to_pop_(0) {
-    CHECK_NE(frame_depth_, kInvalidFrameDepth);
-  }
-
-  bool VisitFrame() REQUIRES_SHARED(Locks::mutator_lock_) {
-    size_t current_frame_depth = GetFrameDepth();
-    if (current_frame_depth < frame_depth_) {
-      CHECK(GetMethod() != nullptr);
-      if (UNLIKELY(reinterpret_cast<uintptr_t>(GetQuickInstrumentationExitPc()) == GetReturnPc())) {
-        if (!IsInInlinedFrame()) {
-          // We do not count inlined frames, because we do not instrument them. The reason we
-          // include them in the stack walking is the check against `frame_depth_`, which is
-          // given to us by a visitor that visits inlined frames.
-          ++instrumentation_frames_to_pop_;
-        }
-      }
-      return true;
-    } else {
-      // We reached the frame of the catch handler or the upcall.
-      return false;
-    }
-  }
-
-  size_t GetInstrumentationFramesToPop() const {
-    return instrumentation_frames_to_pop_;
-  }
-
- private:
-  const size_t frame_depth_;
-  size_t instrumentation_frames_to_pop_;
-
-  DISALLOW_COPY_AND_ASSIGN(InstrumentationStackVisitor);
-};
-
 uintptr_t QuickExceptionHandler::UpdateInstrumentationStack() {
+  DCHECK(is_deoptimization_) << "Non-deoptimization handlers should use FindCatch";
   uintptr_t return_pc = 0;
   if (method_tracing_active_) {
     InstrumentationStackVisitor visitor(self_, handler_frame_depth_);
@@ -610,9 +647,7 @@
 
     size_t instrumentation_frames_to_pop = visitor.GetInstrumentationFramesToPop();
     instrumentation::Instrumentation* instrumentation = Runtime::Current()->GetInstrumentation();
-    for (size_t i = 0; i < instrumentation_frames_to_pop; ++i) {
-      return_pc = instrumentation->PopMethodForUnwind(self_, is_deoptimization_);
-    }
+    return_pc = instrumentation->PopFramesForDeoptimization(self_, instrumentation_frames_to_pop);
   }
   return return_pc;
 }
diff --git a/runtime/quick_exception_handler.h b/runtime/quick_exception_handler.h
index 1103dab..5579d36 100644
--- a/runtime/quick_exception_handler.h
+++ b/runtime/quick_exception_handler.h
@@ -47,7 +47,8 @@
     UNREACHABLE();
   }
 
-  // Find the catch handler for the given exception.
+  // Find the catch handler for the given exception and call all required Instrumentation methods.
+  // Note this might result in the exception being caught being different from 'exception'.
   void FindCatch(ObjPtr<mirror::Throwable> exception) REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Deoptimize the stack to the upcall/some code that's not deoptimizeable. For
diff --git a/runtime/thread.cc b/runtime/thread.cc
index 19d9485..5fb6e79 100644
--- a/runtime/thread.cc
+++ b/runtime/thread.cc
@@ -3368,7 +3368,6 @@
   ClearException();
   QuickExceptionHandler exception_handler(this, false);
   exception_handler.FindCatch(exception);
-  exception_handler.UpdateInstrumentationStack();
   if (exception_handler.GetClearException()) {
     // Exception was cleared as part of delivery.
     DCHECK(!IsExceptionPending());