diff --git a/llvm/lib/Transforms/IPO/PartialInlining.cpp b/llvm/lib/Transforms/IPO/PartialInlining.cpp
--- a/llvm/lib/Transforms/IPO/PartialInlining.cpp
+++ b/llvm/lib/Transforms/IPO/PartialInlining.cpp
@@ -14,6 +14,7 @@
 #include "llvm/Transforms/IPO/PartialInlining.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
@@ -1178,14 +1179,14 @@
   ToExtract.push_back(ClonedOI->NonReturnBlock);
   OutlinedRegionCost += PartialInlinerImpl::computeBBInlineCost(
       ClonedOI->NonReturnBlock, ClonedFuncTTI);
-  for (BasicBlock &BB : *ClonedFunc)
-    if (!ToBeInlined(&BB) && &BB != ClonedOI->NonReturnBlock) {
-      ToExtract.push_back(&BB);
+  for (BasicBlock *BB : depth_first(&ClonedFunc->getEntryBlock()))
+    if (!ToBeInlined(BB) && BB != ClonedOI->NonReturnBlock) {
+      ToExtract.push_back(BB);
       // FIXME: the code extractor may hoist/sink more code
       // into the outlined function which may make the outlining
       // overhead (the difference of the outlined function cost
       // and OutliningRegionCost) look larger.
-      OutlinedRegionCost += computeBBInlineCost(&BB, ClonedFuncTTI);
+      OutlinedRegionCost += computeBBInlineCost(BB, ClonedFuncTTI);
     }
 
   // Extract the body of the if.
diff --git a/llvm/test/Transforms/PartialInlining/unreachable_basic_block.ll b/llvm/test/Transforms/PartialInlining/unreachable_basic_block.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/PartialInlining/unreachable_basic_block.ll
@@ -0,0 +1,29 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=partial-inliner -S < %s | FileCheck %s
+declare i1 @llvm.public.type.test(ptr, metadata)
+
+define void @dummy() {
+; CHECK-LABEL: @dummy(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 false, label [[WHILE_END:%.*]], label [[WHILE_BODY:%.*]]
+; CHECK:       while.body:
+; CHECK-NEXT:    call void @dummy.1.while.body()
+; CHECK-NEXT:    br label [[WHILE_END]]
+; CHECK:       while.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 false, label %while.end, label %while.body
+
+while.body:                                       ; preds = %entry
+  call void @dummy()
+  br label %while.end
+
+unreachable.block:               ; No predecessors!
+  %0 = tail call i1 @llvm.public.type.test(ptr null, metadata !"test-function")
+  %result = getelementptr ptr, ptr null, i64 1
+  br label %while.end
+
+while.end:                                        ; preds = %unreachable.block, %while.body, %entry
+  ret void
+}