diff --git a/llvm/lib/Analysis/IRSimilarityIdentifier.cpp b/llvm/lib/Analysis/IRSimilarityIdentifier.cpp
--- a/llvm/lib/Analysis/IRSimilarityIdentifier.cpp
+++ b/llvm/lib/Analysis/IRSimilarityIdentifier.cpp
@@ -289,14 +289,12 @@
     }
   }
 
-  if (HaveLegalRange) {
-    if (AddedIllegalLastTime)
-      mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB, true);
-    for (IRInstructionData *ID : InstrListForBB)
-      this->IDL->push_back(*ID);
-    llvm::append_range(InstrList, InstrListForBB);
-    llvm::append_range(IntegerMapping, IntegerMappingForBB);
-  }
+  if (AddedIllegalLastTime)
+    mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB, true);
+  for (IRInstructionData *ID : InstrListForBB)
+    this->IDL->push_back(*ID);
+  llvm::append_range(InstrList, InstrListForBB);
+  llvm::append_range(IntegerMapping, IntegerMappingForBB);
 }
 
 // TODO: This is the same as the MachineOutliner, and should be consolidated
diff --git a/llvm/test/Transforms/IROutliner/outlining-basic-branches.ll b/llvm/test/Transforms/IROutliner/outlining-basic-branches.ll
--- a/llvm/test/Transforms/IROutliner/outlining-basic-branches.ll
+++ b/llvm/test/Transforms/IROutliner/outlining-basic-branches.ll
@@ -10,12 +10,12 @@
 next:
   br label %next2
 next2:
-  br label %next
+  br label %next3
 next3:
   %a = alloca i32, align 4
   br label %next4
 next4:
-  br label %next3
+  br label %next5
 next5:
   br label %next6
 next6:
@@ -25,15 +25,11 @@
 
 ; CHECK-LABEL: @outline_outputs1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[NEXT:%.*]]
-; CHECK:       next:
 ; CHECK-NEXT:    call void @outlined_ir_func_0()
-; CHECK-NEXT:    br label [[NEXT]]
+; CHECK-NEXT:    br label [[NEXT3:%.*]]
 ; CHECK:       next3:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    call void @outlined_ir_func_0()
-; CHECK-NEXT:    br label [[NEXT3:%.*]]
-; CHECK:       next5:
 ; CHECK-NEXT:    br label [[NEXT6:%.*]]
 ; CHECK:       next6:
 ; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
@@ -41,12 +37,14 @@
 ;
 ;
 ; CHECK: define internal void @outlined_ir_func_0(
-; CHECK:  newFuncRoot:
-; CHECK-NEXT:    br label [[NEXT_TO_OUTLINE:%.*]]
-; CHECK:       next_to_outline:
+; CHECK-NEXT:  newFuncRoot:
+; CHECK-NEXT:    br label [[ENTRY_TO_OUTLINE:%.*]]
+; CHECK:       entry_to_outline:
+; CHECK-NEXT:    br label [[NEXT:%.*]]
+; CHECK:       next:
 ; CHECK-NEXT:    br label [[NEXT2:%.*]]
 ; CHECK:       next2:
-; CHECK-NEXT:    br label [[NEXT_EXITSTUB:%.*]]
-; CHECK:       next.exitStub:
+; CHECK-NEXT:    br label [[NEXT3_EXITSTUB:%.*]]
+; CHECK:       next3.exitStub:
 ; CHECK-NEXT:    ret void
 ;
diff --git a/llvm/test/Transforms/IROutliner/outlining-no-return-functions.ll b/llvm/test/Transforms/IROutliner/outlining-first-instruction.ll
copy from llvm/test/Transforms/IROutliner/outlining-no-return-functions.ll
copy to llvm/test/Transforms/IROutliner/outlining-first-instruction.ll
--- a/llvm/test/Transforms/IROutliner/outlining-no-return-functions.ll
+++ b/llvm/test/Transforms/IROutliner/outlining-first-instruction.ll
@@ -1,47 +1,57 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --include-generated-funcs
 ; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s
 
-; Make sure that we outline safely from functions with no return instructions.
-
-; The code extractor will insert return instructions in the outer function
-; due to assumptions about the contents of the outlined region.
+; Make sure that we outline from all three of these functions, and that
+; the first instruction in the module is included when it is the only
+; instruction in the first basic block.
 
 define void @f1() {
 bb:
   br label %bb1
 bb1:
-  br label %bb1
+  br label %bb2
+bb2:
+  ret void
 }
 
 define void @f2() {
 bb:
   br label %bb1
 bb1:
-  br label %bb1
+  br label %bb2
+bb2:
+  ret void
 }
 
 define void @f3() {
 bb:
   br label %bb1
 bb1:
-  br label %bb1
+  br label %bb2
+bb2:
+  ret void
 }
 ; CHECK-LABEL: @f1(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    br label [[BB1:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    br label [[BB1]]
+; CHECK-NEXT:    call void @outlined_ir_func_0()
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret void
 ;
 ;
 ; CHECK-LABEL: @f2(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    call void @outlined_ir_func_0()
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb2:
 ; CHECK-NEXT:    ret void
 ;
 ;
 ; CHECK-LABEL: @f3(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    call void @outlined_ir_func_0()
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb2:
 ; CHECK-NEXT:    ret void
 ;
 ;
@@ -51,5 +61,7 @@
 ; CHECK:       bb_to_outline:
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    br label [[BB1]]
+; CHECK-NEXT:    br label [[BB2_EXITSTUB:%.*]]
+; CHECK:       bb2.exitStub:
+; CHECK-NEXT:    ret void
 ;
diff --git a/llvm/test/Transforms/IROutliner/outlining-no-return-functions.ll b/llvm/test/Transforms/IROutliner/outlining-no-return-functions.ll
--- a/llvm/test/Transforms/IROutliner/outlining-no-return-functions.ll
+++ b/llvm/test/Transforms/IROutliner/outlining-no-return-functions.ll
@@ -28,9 +28,8 @@
 }
 ; CHECK-LABEL: @f1(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    br label [[BB1:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    br label [[BB1]]
+; CHECK-NEXT:    call void @outlined_ir_func_0()
+; CHECK-NEXT:    ret void
 ;
 ;
 ; CHECK-LABEL: @f2(
diff --git a/llvm/test/Transforms/IROutliner/phi-nodes-simple.ll b/llvm/test/Transforms/IROutliner/phi-nodes-simple.ll
--- a/llvm/test/Transforms/IROutliner/phi-nodes-simple.ll
+++ b/llvm/test/Transforms/IROutliner/phi-nodes-simple.ll
@@ -29,30 +29,28 @@
 }
 ; CHECK-LABEL: @function1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[TEST:%.*]]
-; CHECK:       test:
 ; CHECK-NEXT:    call void @outlined_ir_func_0(i32* [[A:%.*]], i32* [[B:%.*]])
 ; CHECK-NEXT:    ret void
 ;
 ;
 ; CHECK-LABEL: @function2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[TEST:%.*]]
-; CHECK:       test:
 ; CHECK-NEXT:    call void @outlined_ir_func_0(i32* [[A:%.*]], i32* [[B:%.*]])
 ; CHECK-NEXT:    ret void
 ;
 ;
 ; CHECK: define internal void @outlined_ir_func_0(
 ; CHECK-NEXT:  newFuncRoot:
-; CHECK-NEXT:    br label [[TEST_TO_OUTLINE:%.*]]
-; CHECK:       test_to_outline:
+; CHECK-NEXT:    br label [[ENTRY_TO_OUTLINE:%.*]]
+; CHECK:       entry_to_outline:
+; CHECK-NEXT:    br label [[TEST:%.*]]
+; CHECK:       test:
 ; CHECK-NEXT:    br label [[FIRST:%.*]]
 ; CHECK:       first:
-; CHECK-NEXT:    [[TMP2:%.*]] = phi i32 [ 0, [[TEST_TO_OUTLINE]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i32 [ 0, [[TEST]] ]
 ; CHECK-NEXT:    store i32 2, i32* [[TMP0:%.*]], align 4
 ; CHECK-NEXT:    store i32 3, i32* [[TMP1:%.*]], align 4
-; CHECK-NEXT:    br label [[TEST_AFTER_OUTLINE_EXITSTUB:%.*]]
-; CHECK:       test_after_outline.exitStub:
+; CHECK-NEXT:    br label [[ENTRY_AFTER_OUTLINE_EXITSTUB:%.*]]
+; CHECK:       entry_after_outline.exitStub:
 ; CHECK-NEXT:    ret void
 ;
diff --git a/llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp b/llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp
--- a/llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp
+++ b/llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp
@@ -809,7 +809,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
+  ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
 }
 
 // In most cases, the illegal instructions we are collecting don't require any
@@ -844,7 +845,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
+  ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
 }
 
 // Checks that an getelementptr instruction is mapped to be legal.  And that
@@ -983,7 +985,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
+  ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
 }
 
 // Checks that indirect call instructions are mapped to be legal when it is not
@@ -1265,7 +1268,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
+  ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
 }
 
 // Checks that an callbr instructions are considered to be illegal.  Callbr
@@ -1298,7 +1302,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
+  ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
 }
 
 // Checks that an debuginfo intrinsics are mapped to be invisible.  Since they
@@ -1356,7 +1361,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
+  ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
 }
 
 // Checks that an eh.exceptioncode intrinsic is mapped to be illegal.
@@ -1388,7 +1394,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
+  ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
 }
 
 // Checks that an eh.unwind intrinsic is mapped to be illegal.
@@ -1413,7 +1420,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
+  ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
 }
 
 // Checks that an eh.exceptionpointer intrinsic is mapped to be illegal.
@@ -1438,7 +1446,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
+  ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
 }
 
 // Checks that a catchpad instruction is mapped to an illegal value.
@@ -1469,7 +1478,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
+  ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
 }
 
 // Checks that a cleanuppad instruction is mapped to an illegal value.
@@ -1500,7 +1510,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
+  ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
 }
 
 // The following three instructions are memory transfer and setting based, which
@@ -2462,7 +2473,7 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   // Check to make sure that we have a long enough region.
-  ASSERT_EQ(InstrList.size(), static_cast<unsigned>(11));
+  ASSERT_EQ(InstrList.size(), static_cast<unsigned>(12));
   // Check that the instructions were added correctly to both vectors.
   ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
 
@@ -2515,7 +2526,7 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   // Check to make sure that we have a long enough region.
-  ASSERT_EQ(InstrList.size(), static_cast<unsigned>(13));
+  ASSERT_EQ(InstrList.size(), static_cast<unsigned>(14));
   // Check that the instructions were added correctly to both vectors.
   ASSERT_TRUE(InstrList.size() == UnsignedVec.size());