diff --git a/libunwind/src/AddressSpace.hpp b/libunwind/src/AddressSpace.hpp
--- a/libunwind/src/AddressSpace.hpp
+++ b/libunwind/src/AddressSpace.hpp
@@ -462,29 +462,37 @@
 #endif
 
   Elf_Addr image_base = calculateImageBase(pinfo);
-  bool found_text = false;
-  bool found_unwind = false;
 
-  // Third phdr is usually the executable phdr.
-  if (pinfo->dlpi_phnum > 2)
-    found_text = checkAddrInSegment(&pinfo->dlpi_phdr[2], image_base, cbdata);
+  // Most shared objects seen in this callback function likely don't contain the
+  // target address, so optimize for that. Scan for a matching PT_LOAD segment
+  // first and bail when it isn't found.
+  bool found_text = false;
+  for (Elf_Half i = 0; i < pinfo->dlpi_phnum; ++i) {
+    if (checkAddrInSegment(&pinfo->dlpi_phdr[i], image_base, cbdata)) {
+      found_text = true;
+      break;
+    }
+  }
+  if (!found_text)
+    return 0;
 
   // PT_GNU_EH_FRAME and PT_ARM_EXIDX are usually near the end. Iterate
-  // backward. We already know that there is one or more phdrs.
+  // backward.
+  bool found_unwind = false;
   for (Elf_Half i = pinfo->dlpi_phnum; i > 0; i--) {
     const Elf_Phdr *phdr = &pinfo->dlpi_phdr[i - 1];
-    if (!found_unwind && checkForUnwindInfoSegment(phdr, image_base, cbdata))
+    if (checkForUnwindInfoSegment(phdr, image_base, cbdata)) {
       found_unwind = true;
-    else if (!found_text && checkAddrInSegment(phdr, image_base, cbdata))
-      found_text = true;
-    if (found_text && found_unwind) {
-#if defined(_LIBUNWIND_USE_FRAME_HEADER_CACHE)
-      TheFrameHeaderCache.add(cbdata->sects);
-#endif
-      return 1;
+      break;
     }
   }
-  return 0;
+  if (!found_unwind)
+    return 0;
+
+#if defined(_LIBUNWIND_USE_FRAME_HEADER_CACHE)
+  TheFrameHeaderCache.add(cbdata->sects);
+#endif
+  return 1;
 }
 
 #endif  // defined(_LIBUNWIND_USE_DL_ITERATE_PHDR)