diff --git a/llvm/include/llvm/Analysis/IRSimilarityIdentifier.h b/llvm/include/llvm/Analysis/IRSimilarityIdentifier.h
--- a/llvm/include/llvm/Analysis/IRSimilarityIdentifier.h
+++ b/llvm/include/llvm/Analysis/IRSimilarityIdentifier.h
@@ -110,7 +110,8 @@
 /// by \ref isSameOperationAs.
 /// TODO: Handle GetElementPtrInsts, as some of the operands have to be the
 /// exact same, and some do not.
-struct IRInstructionData : ilist_node<IRInstructionData> {
+struct IRInstructionData
+    : ilist_node<IRInstructionData, ilist_sentinel_tracking<true>> {
 
   /// The source Instruction that is being wrapped.
   Instruction *Inst = nullptr;
@@ -127,12 +128,41 @@
   /// to a less than form.  It is None otherwise.
   Optional<CmpInst::Predicate> RevisedPredicate;
 
+  /// This structure holds the distances of how far "ahead of" or "behind" the
+  /// target blocks of a branch, or the incoming blocks of a phi nodes are.
+  /// If the value is negative, it means that the block was registered before
+  /// the block of this instruction in terms of blocks in the function.
+  /// Code Example:
+  /// \code
+  /// block_1:
+  ///   br i1 %0, label %block_2, label %block_3
+  /// block_2:
+  ///   br i1 %1, label %block_1, label %block_2
+  /// block_3:
+  ///   br i1 %2, label %block_2, label %block_1
+  /// ; Replacing the labels with relative values, this becomes:
+  /// block_1:
+  ///   br i1 %0, distance 1, distance 2
+  /// block_2:
+  ///   br i1 %1, distance -1, distance 0
+  /// block_3:
+  ///   br i1 %2, distance -1, distance -2
+  /// \endcode
+  /// Taking block_2 as our example, block_1 is "behind" block_2, and block_2 is
+  /// "ahead" of block_2.
+  SmallVector<int, 4> RelativeBlockLocations;
+
   /// Gather the information that is difficult to gather for an Instruction, or
   /// is changed. i.e. the operands of an Instruction and the Types of those
   /// operands. This extra information allows for similarity matching to make
   /// assertions that allow for more flexibility when checking for whether an
   /// Instruction performs the same operation.
   IRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL);
+  IRInstructionData(IRInstructionDataList &IDL);
+
+  /// Fills data stuctures for IRInstructionData when it is constructed from a
+  // reference or a pointer.
+  void initializeInstruction();
 
   /// Get the predicate that the compare instruction is using for hashing the
   /// instruction. the IRInstructionData must be wrapping a CmpInst.
@@ -145,6 +175,16 @@
   /// \return the consistent comparison predicate. 
   static CmpInst::Predicate predicateForConsistency(CmpInst *CI);
 
+  /// For an IRInstructionData containing a branch, finds the
+  /// relative distances from the source basic block to the target by taking
+  /// the difference of the number assigned to the current basic block and the
+  /// target basic block of the branch.
+  ///
+  /// \param BasicBlockToInteger - The mapping of basic blocks to their location
+  /// in the module.
+  void
+  setBranchSuccessors(DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger);
+
   /// Hashes \p Value based on its opcode, types, and operand types.
   /// Two IRInstructionData instances produce the same hash when they perform
   /// the same operation.
@@ -198,7 +238,8 @@
   IRInstructionDataList *IDL = nullptr;
 };
 
-struct IRInstructionDataList : simple_ilist<IRInstructionData> {};
+struct IRInstructionDataList
+    : simple_ilist<IRInstructionData, ilist_sentinel_tracking<true>> {};
 
 /// Compare one IRInstructionData class to another IRInstructionData class for
 /// whether they are performing a the same operation, and can mapped to the
@@ -288,6 +329,10 @@
   DenseMap<IRInstructionData *, unsigned, IRInstructionDataTraits>
       InstructionIntegerMap;
 
+  /// A mapping for a basic block in a module to its assigned number/location
+  /// in the module.
+  DenseMap<BasicBlock *, unsigned> BasicBlockToInteger;
+
   /// Set if we added an illegal number in the previous step.
   /// Since each illegal number is unique, we only need one of them between
   /// each range of legal numbers. This lets us make sure we don't add more
@@ -322,6 +367,14 @@
   IRInstructionData *allocateIRInstructionData(Instruction &I, bool Legality,
                                                IRInstructionDataList &IDL);
 
+  /// Get an empty allocated IRInstructionData struct using the
+  /// InstDataAllocator.
+  ///
+  /// \param IDL - The InstructionDataList that the IRInstructionData is
+  /// inserted into.
+  /// \returns An allocated IRInstructionData struct.
+  IRInstructionData *allocateIRInstructionData(IRInstructionDataList &IDL);
+
   /// Get an allocated IRInstructionDataList object using the IDLAllocator.
   ///
   /// \returns An allocated IRInstructionDataList object.
@@ -329,6 +382,24 @@
 
   IRInstructionDataList *IDL = nullptr;
 
+  /// Assigns values to all the basic blocks in function \p F starting from
+  /// integer \p BBNumber.
+  ///
+  /// \param F - The function containing the basic blocks to assign numbers to.
+  /// \param BBNumber - The number to start from.
+  void initializeForBBs(Function &F, unsigned &BBNumber) {
+    for (BasicBlock &BB : F)
+      BasicBlockToInteger.insert(std::make_pair(&BB, BBNumber++));
+  }
+
+  /// Assigns values to all the basic blocks in Module \p M.
+  /// \param M - The module containing the basic blocks to assign numbers to.
+  void initializeForBBs(Module &M) {
+    unsigned BBNumber = 0;
+    for (Function &F : M)
+      initializeForBBs(F, BBNumber);
+  }
+
   /// Maps the Instructions in a BasicBlock \p BB to legal or illegal integers
   /// determined by \p InstrType. Two Instructions are mapped to the same value
   /// if they are close as defined by the InstructionData class above.
@@ -386,7 +457,11 @@
     InstructionClassification() {}
 
     // TODO: Determine a scheme to resolve when the label is similar enough.
-    InstrType visitBranchInst(BranchInst &BI) { return Illegal; }
+    InstrType visitBranchInst(BranchInst &BI) {
+      if (EnableBranches)
+        return Legal;
+      return Illegal;
+    }
     // TODO: Determine a scheme to resolve when the labels are similar enough.
     InstrType visitPHINode(PHINode &PN) { return Illegal; }
     // TODO: Handle allocas.
@@ -419,6 +494,10 @@
     // TODO: Handle interblock similarity.
     InstrType visitTerminator(Instruction &I) { return Illegal; }
     InstrType visitInstruction(Instruction &I) { return Legal; }
+
+    // The flag variable that lets the classifier know whether we should
+    // allow branches to be checked for similarity.
+    bool EnableBranches = false;
   };
 
   /// Maps an Instruction to a member of InstrType.
@@ -546,6 +625,21 @@
     DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMapping;
   };
 
+  /// A helper struct to hold the candidate, for a branch instruction, the
+  /// relative location of a label, and the label itself.  This is mostly to
+  /// group the values together before passing them as a bundle to a function.
+  struct RelativeLocMapping {
+    /// The IRSimilarityCandidate that holds the instruction the relative
+    /// location was pulled from.
+    const IRSimilarityCandidate &IRSC;
+
+    /// The relative location to be analyzed.
+    int RelativeLocation;
+
+    /// The corresponding value.
+    Value *OperVal;
+  };
+
   /// Compare the operands in \p A and \p B and check that the current mapping
   /// of global value numbers from \p A to \p B and \p B to \A is consistent.
   ///
@@ -569,6 +663,44 @@
   static bool compareCommutativeOperandMapping(OperandMapping A,
                                                OperandMapping B);
 
+  /// Compare the relative locations in \p A and \p B and check that the
+  /// distances match if both locations are contained in the region, and that
+  /// the branches both point outside the region if they do not.
+  /// Example Region:
+  /// \code
+  /// entry:
+  ///   br i1 %0, label %block_1, label %block_3
+  /// block_0:
+  ///   br i1 %0, label %block_1, label %block_2
+  /// block_1:
+  ///   br i1 %0, label %block_2, label %block_3
+  /// block_2:
+  ///   br i1 %1, label %block_1, label %block_4
+  /// block_3:
+  ///   br i1 %2, label %block_2, label %block_5
+  /// \endcode
+  /// If we compare the branches in block_0 and block_1 the relative values are
+  /// 1 and 2 for both, so we consider this a match.
+  ///
+  /// If we compare the branches in entry and block_0 the relative values are
+  /// 2 and 3, and 1 and 2 respectively.  Since these are not the same we do not
+  /// consider them a match.
+  ///
+  /// If we compare the branches in block_1 and block_2 the relative values are
+  /// 1 and 2, and -1 and None respectively.  As a result we do not consider
+  /// these to be the same
+  ///
+  /// If we compare the branches in block_2 and block_3 the relative values are
+  /// -1 and None for both.  We do consider these to be a match.
+  ///
+  /// \param A - The first IRInstructionCandidate, relative location value,
+  /// and incoming block.
+  /// \param B - The second IRInstructionCandidate, relative location value,
+  /// and incoming block.
+  /// \returns true if the relative locations match.
+  static bool checkRelativeLocations(RelativeLocMapping A,
+                                     RelativeLocMapping B);
+
   /// Create a mapping from the value numbering to a different separate set of
   /// numbers. This will serve as a guide for relating one candidate to another.
   /// The canonical number gives use the ability identify which global value
@@ -596,6 +728,31 @@
       DenseMap<unsigned, DenseSet<unsigned>> &ToSourceMapping,
       DenseMap<unsigned, DenseSet<unsigned>> &FromSourceMapping);
 
+  /// \param [in,out] BBSet - The set to track the basic blocks.
+  /// \returns The BasicBlock the IRSimilarityCandidate ends in.
+  void getBasicBlocks(DenseSet<BasicBlock *> &BBSet) const {
+    for (IRInstructionData &ID : *this) {
+      BasicBlock *BB = ID.Inst->getParent();
+      if (BBSet.contains(BB))
+        continue;
+      BBSet.insert(BB);
+    }
+  }
+
+  /// \param [in,out] BBSet - The set to track the basic blocks.
+  /// \param [in,out] BBList - A list in order of use to track the basic blocks.
+  /// \returns The BasicBlock the IRSimilarityCandidate ends in.
+  void getBasicBlocks(DenseSet<BasicBlock *> &BBSet,
+                      std::vector<BasicBlock *> &BBList) const {
+    for (IRInstructionData &ID : *this) {
+      BasicBlock *BB = ID.Inst->getParent();
+      if (BBSet.contains(BB))
+        continue;
+      BBSet.insert(BB);
+      BBList.push_back(BB);
+    }
+  }
+
   /// Compare the start and end indices of the two IRSimilarityCandidates for
   /// whether they overlap. If the start instruction of one
   /// IRSimilarityCandidate is less than the end instruction of the other, and
@@ -727,8 +884,9 @@
 /// analyzing the module.
 class IRSimilarityIdentifier {
 public:
-  IRSimilarityIdentifier()
-      : Mapper(&InstDataAllocator, &InstDataListAllocator) {}
+  IRSimilarityIdentifier(bool MatchBranches = true)
+      : Mapper(&InstDataAllocator, &InstDataListAllocator),
+        EnableBranches(MatchBranches) {}
 
 private:
   /// Map the instructions in the module to unsigned integers, using mapping
@@ -804,6 +962,10 @@
   /// instance of IRInstructionData.
   IRInstructionMapper Mapper;
 
+  /// The flag variable that marks whether we should check branches for
+  /// similarity, or only look within basic blocks.
+  bool EnableBranches = true;
+
   /// The SimilarityGroups found with the most recent run of \ref
   /// findSimilarity. None if there is no recent run.
   Optional<SimilarityGroupList> SimilarityCandidates;
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
@@ -23,13 +23,23 @@
 using namespace llvm;
 using namespace IRSimilarity;
 
+cl::opt<bool>
+    DisableBranches("no-ir-sim-branch-matching", cl::init(false),
+                    cl::ReallyHidden,
+                    cl::desc("disable similarity matching, and outlining, "
+                             "across branches for debugging purposes."));
+
 IRInstructionData::IRInstructionData(Instruction &I, bool Legality,
                                      IRInstructionDataList &IDList)
     : Inst(&I), Legal(Legality), IDL(&IDList) {
+  initializeInstruction();
+}
+
+void IRInstructionData::initializeInstruction() {
   // We check for whether we have a comparison instruction.  If it is, we
   // find the "less than" version of the predicate for consistency for
   // comparison instructions throught the program.
-  if (CmpInst *C = dyn_cast<CmpInst>(&I)) {
+  if (CmpInst *C = dyn_cast<CmpInst>(Inst)) {
     CmpInst::Predicate Predicate = predicateForConsistency(C);
     if (Predicate != C->getPredicate())
       RevisedPredicate = Predicate;
@@ -37,8 +47,8 @@
 
   // Here we collect the operands and their types for determining whether
   // the structure of the operand use matches between two different candidates.
-  for (Use &OI : I.operands()) {
-    if (isa<CmpInst>(I) && RevisedPredicate.hasValue()) {
+  for (Use &OI : Inst->operands()) {
+    if (isa<CmpInst>(Inst) && RevisedPredicate.hasValue()) {
       // If we have a CmpInst where the predicate is reversed, it means the
       // operands must be reversed as well.
       OperVals.insert(OperVals.begin(), OI.get());
@@ -49,6 +59,33 @@
   }
 }
 
+IRInstructionData::IRInstructionData(IRInstructionDataList &IDList)
+    : Inst(nullptr), Legal(false), IDL(&IDList) {}
+
+void IRInstructionData::setBranchSuccessors(
+    DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger) {
+  assert(isa<BranchInst>(Inst) && "Instruction must be branch");
+
+  BranchInst *BI = cast<BranchInst>(Inst);
+  DenseMap<BasicBlock *, unsigned>::iterator BBNumIt;
+
+  BBNumIt = BasicBlockToInteger.find(BI->getParent());
+  assert(BBNumIt != BasicBlockToInteger.end() &&
+         "Could not find location for BasicBlock!");
+
+  int CurrentBlockNumber = static_cast<int>(BBNumIt->second);
+
+  for (BasicBlock *Successor : BI->successors()) {
+    BBNumIt = BasicBlockToInteger.find(Successor);
+    assert(BBNumIt != BasicBlockToInteger.end() &&
+           "Could not find number for BasicBlock!");
+    int OtherBlockNumber = static_cast<int>(BBNumIt->second);
+
+    int Relative = OtherBlockNumber - CurrentBlockNumber;
+    RelativeBlockLocations.push_back(Relative);
+  }
+}
+
 CmpInst::Predicate IRInstructionData::predicateForConsistency(CmpInst *CI) {
   switch (CI->getPredicate()) {
   case CmpInst::FCMP_OGT:
@@ -143,6 +180,10 @@
       return false;
   }
 
+  if (isa<BranchInst>(A.Inst) && isa<BranchInst>(B.Inst) &&
+      A.RelativeBlockLocations.size() != B.RelativeBlockLocations.size())
+    return false;
+
   return true;
 }
 
@@ -156,10 +197,6 @@
   std::vector<unsigned> IntegerMappingForBB;
   std::vector<IRInstructionData *> InstrListForBB;
 
-  HaveLegalRange = false;
-  CanCombineWithPrevInstr = false;
-  AddedIllegalLastTime = true;
-
   for (BasicBlock::iterator Et = BB.end(); It != Et; ++It) {
     switch (InstClassifier.visit(*It)) {
     case InstrType::Legal:
@@ -175,7 +212,8 @@
   }
 
   if (HaveLegalRange) {
-    mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB, true);
+    if (AddedIllegalLastTime)
+      mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB, true);
     for (IRInstructionData *ID : InstrListForBB)
       this->IDL->push_back(*ID);
     llvm::append_range(InstrList, InstrListForBB);
@@ -203,6 +241,9 @@
   IRInstructionData *ID = allocateIRInstructionData(*It, true, *IDL);
   InstrListForBB.push_back(ID);
 
+  if (isa<BranchInst>(*It))
+    ID->setBranchSuccessors(BasicBlockToInteger);
+
   // Add to the instruction list
   bool WasInserted;
   DenseMap<IRInstructionData *, unsigned, IRInstructionDataTraits>::iterator
@@ -235,6 +276,11 @@
   return new (InstDataAllocator->Allocate()) IRInstructionData(I, Legality, IDL);
 }
 
+IRInstructionData *
+IRInstructionMapper::allocateIRInstructionData(IRInstructionDataList &IDL) {
+  return new (InstDataAllocator->Allocate()) IRInstructionData(IDL);
+}
+
 IRInstructionDataList *
 IRInstructionMapper::allocateIRInstructionDataList() {
   return new (IDLAllocator->Allocate()) IRInstructionDataList();
@@ -255,6 +301,8 @@
   IRInstructionData *ID = nullptr;
   if (!End)
     ID = allocateIRInstructionData(*It, false, *IDL);
+  else
+    ID = allocateIRInstructionData(*IDL);
   InstrListForBB.push_back(ID);
 
   // Remember that we added an illegal number last time.
@@ -563,6 +611,34 @@
   return true;
 }
 
+bool IRSimilarityCandidate::checkRelativeLocations(RelativeLocMapping A,
+                                                   RelativeLocMapping B) {
+  // Get the basic blocks the label refers to.
+  BasicBlock *ABB = static_cast<BasicBlock *>(A.OperVal);
+  BasicBlock *BBB = static_cast<BasicBlock *>(B.OperVal);
+
+  // Get the basic blocks contained in each region.
+  DenseSet<BasicBlock *> BasicBlockA;
+  DenseSet<BasicBlock *> BasicBlockB;
+  A.IRSC.getBasicBlocks(BasicBlockA);
+  B.IRSC.getBasicBlocks(BasicBlockB);
+  
+  // Determine if the block is contained in the region.
+  bool AContained = BasicBlockA.find(ABB) != BasicBlockA.end();
+  bool BContained = BasicBlockB.find(BBB) != BasicBlockB.end();
+
+  // Both blocks need to be contained in the region, or both need to be outside
+  // the reigon.
+  if (AContained != BContained)
+    return false;
+  
+  // If both are contained, then we need to make sure that the relative
+  // distance to the target blocks are the same.
+  if (AContained)
+    return A.RelativeLocation == B.RelativeLocation;
+  return true;
+}
+
 bool IRSimilarityCandidate::compareStructure(const IRSimilarityCandidate &A,
                                              const IRSimilarityCandidate &B) {
   DenseMap<unsigned, DenseSet<unsigned>> MappingA;
@@ -570,6 +646,11 @@
   return IRSimilarityCandidate::compareStructure(A, B, MappingA, MappingB);
 }
 
+typedef detail::zippy<detail::zip_shortest, SmallVector<int, 4> &,
+                      SmallVector<int, 4> &, ArrayRef<Value *> &,
+                      ArrayRef<Value *> &>
+    ZippedRelativeLocationsT;
+
 bool IRSimilarityCandidate::compareStructure(
     const IRSimilarityCandidate &A, const IRSimilarityCandidate &B,
     DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingA,
@@ -639,6 +720,37 @@
             {A, OperValsA, ValueNumberMappingA},
             {B, OperValsB, ValueNumberMappingB}))
       return false;
+
+    // Here we check that between two corresponding instructions,
+    // when referring to a basic block in the same region, the
+    // relative locations are the same. And, that the instructions refer to
+    // basic blocks outside the region in the same corresponding locations.
+
+    // We are able to make the assumption about blocks outside of the region
+    // since the target block labels are considered values and will follow the
+    // same number matching that we defined for the other instructions in the
+    // region.  So, at this point, in each location we target a specific block
+    // outside the region, we are targeting a corresponding block in each
+    // analagous location in the region we are comparing to.
+    if (!(isa<BranchInst>(IA) && isa<BranchInst>(IB)) &&
+        !(isa<PHINode>(IA) && isa<PHINode>(IB)))
+      continue;
+
+    SmallVector<int, 4> &RelBlockLocsA = ItA->RelativeBlockLocations;
+    SmallVector<int, 4> &RelBlockLocsB = ItB->RelativeBlockLocations;
+    if (RelBlockLocsA.size() != RelBlockLocsB.size() &&
+        OperValsA.size() != OperValsB.size())
+      return false;
+
+    ZippedRelativeLocationsT ZippedRelativeLocations =
+        zip(RelBlockLocsA, RelBlockLocsB, OperValsA, OperValsB);
+    if (any_of(ZippedRelativeLocations,
+               [&A, &B](std::tuple<int, int, Value *, Value *> R) {
+                 return !checkRelativeLocations(
+                     {A, std::get<0>(R), std::get<2>(R)},
+                     {B, std::get<1>(R), std::get<3>(R)});
+               }))
+      return false;
   }
   return true;
 }
@@ -664,6 +776,8 @@
   std::vector<unsigned> IntegerMappingForModule;
   // Iterate over the functions in the module to map each Instruction in each
   // BasicBlock to an unsigned integer.
+  Mapper.initializeForBBs(M);
+
   for (Function &F : M) {
 
     if (F.empty())
@@ -671,15 +785,18 @@
 
     for (BasicBlock &BB : F) {
 
-      if (BB.sizeWithoutDebug() < 2)
-        continue;
-
       // BB has potential to have similarity since it has a size greater than 2
       // and can therefore match other regions greater than 2. Map it to a list
       // of unsigned integers.
       Mapper.convertToUnsignedVec(BB, InstrListForModule,
                                   IntegerMappingForModule);
     }
+
+    BasicBlock::iterator It = F.begin()->end();
+    Mapper.mapToIllegalUnsigned(It, IntegerMappingForModule, InstrListForModule,
+                                true);
+    if (InstrListForModule.size() > 0)
+      Mapper.IDL->push_back(*InstrListForModule.back());
   }
 
   // Insert the InstrListForModule at the end of the overall InstrList so that
@@ -714,6 +831,8 @@
     std::vector<IRSimilarityCandidate> &CandsForRepSubstring) {
 
   unsigned StringLen = RS.Length;
+  if (StringLen < 2)
+    return;
 
   // Create an IRSimilarityCandidate for instance of this subsequence \p RS.
   for (const unsigned &StartIdx : RS.StartIndices) {
@@ -955,6 +1074,7 @@
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> IntegerMapping;
+  Mapper.InstClassifier.EnableBranches = this->EnableBranches;
 
   populateMapper(Modules, InstrList, IntegerMapping);
   findCandidates(InstrList, IntegerMapping);
@@ -964,6 +1084,7 @@
 
 SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(Module &M) {
   resetSimilarityCandidates();
+  Mapper.InstClassifier.EnableBranches = this->EnableBranches;
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> IntegerMapping;
@@ -984,7 +1105,7 @@
 }
 
 bool IRSimilarityIdentifierWrapperPass::doInitialization(Module &M) {
-  IRSI.reset(new IRSimilarityIdentifier());
+  IRSI.reset(new IRSimilarityIdentifier(!DisableBranches));
   return false;
 }
 
@@ -1000,9 +1121,9 @@
 
 AnalysisKey IRSimilarityAnalysis::Key;
 IRSimilarityIdentifier IRSimilarityAnalysis::run(Module &M,
-                                               ModuleAnalysisManager &) {
+                                                 ModuleAnalysisManager &) {
 
-  auto IRSI = IRSimilarityIdentifier();
+  auto IRSI = IRSimilarityIdentifier(!DisableBranches);
   IRSI.findSimilarity(M);
   return IRSI;
 }
diff --git a/llvm/lib/Transforms/IPO/IROutliner.cpp b/llvm/lib/Transforms/IPO/IROutliner.cpp
--- a/llvm/lib/Transforms/IPO/IROutliner.cpp
+++ b/llvm/lib/Transforms/IPO/IROutliner.cpp
@@ -1342,6 +1342,35 @@
   OutlinedFunctionNum++;
 }
 
+/// Checks that the next instruction in the InstructionDataList matches the
+/// next instruction in the module.  If they do not, there could be the
+/// possibility that extra code has been inserted, and we must ignore it.
+///
+/// \param ID - The IRInstructionData to check the next instruction of.
+/// \returns true if the InstructionDataList and actual instruction match.
+static bool nextIRInstructionDataMatchesNextInst(IRInstructionData &ID) {
+  // We check if there is a discrepancy between the InstructionDataList
+  // and the actual next instruction in the module.  If there is, it means
+  // that an extra instruction was added, likely by the CodeExtractor.
+
+  // Since we do not have any similarity data about this particular
+  // instruction, we cannot confidently outline it, and must discard this
+  // candidate.
+  IRInstructionDataList::iterator NextIDIt = std::next(ID.getIterator());
+  Instruction *NextIDLInst = NextIDIt->Inst;
+  Instruction *NextModuleInst = nullptr;
+  if (!ID.Inst->isTerminator())
+    NextModuleInst = ID.Inst->getNextNonDebugInstruction();
+  else if (NextIDLInst != nullptr)
+    NextModuleInst =
+        &*NextIDIt->Inst->getParent()->instructionsWithoutDebug().begin();
+
+  if (NextIDLInst && NextIDLInst != NextModuleInst)
+    return false;
+
+  return true;
+}
+
 bool IROutliner::isCompatibleWithAlreadyOutlinedCode(
     const OutlinableRegion &Region) {
   IRSimilarityCandidate *IRSC = Region.Candidate;
@@ -1373,17 +1402,10 @@
   }
 
   return none_of(*IRSC, [this](IRInstructionData &ID) {
-    // We check if there is a discrepancy between the InstructionDataList
-    // and the actual next instruction in the module.  If there is, it means
-    // that an extra instruction was added, likely by the CodeExtractor.
-
-    // Since we do not have any similarity data about this particular
-    // instruction, we cannot confidently outline it, and must discard this
-    // candidate.
-    if (std::next(ID.getIterator())->Inst !=
-        ID.Inst->getNextNonDebugInstruction())
+    if (!nextIRInstructionDataMatchesNextInst(ID))
       return true;
-    return !InstructionClassifier.visit(ID.Inst);
+
+    return !this->InstructionClassifier.visit(ID.Inst);
   });
 }
 
@@ -1428,16 +1450,9 @@
       continue;
 
     bool BadInst = any_of(IRSC, [this](IRInstructionData &ID) {
-      // We check if there is a discrepancy between the InstructionDataList
-      // and the actual next instruction in the module.  If there is, it means
-      // that an extra instruction was added, likely by the CodeExtractor.
-
-      // Since we do not have any similarity data about this particular
-      // instruction, we cannot confidently outline it, and must discard this
-      // candidate.
-      if (std::next(ID.getIterator())->Inst !=
-          ID.Inst->getNextNonDebugInstruction())
+      if (!nextIRInstructionDataMatchesNextInst(ID))
         return true;
+
       return !this->InstructionClassifier.visit(ID.Inst);
     });
 
diff --git a/llvm/test/Analysis/IRSimilarityIdentifier/basic.ll b/llvm/test/Analysis/IRSimilarityIdentifier/basic.ll
--- a/llvm/test/Analysis/IRSimilarityIdentifier/basic.ll
+++ b/llvm/test/Analysis/IRSimilarityIdentifier/basic.ll
@@ -5,6 +5,9 @@
 ; IRSimilarityPrinterPass is working.
 
 ; CHECK: 4 candidates of length 2.  Found in:
+; CHECK-NEXT:  Function: turtle, Basic Block: (unnamed)
+; CHECK-NEXT:    Start Instruction:   store i32 5, i32* %5, align 4
+; CHECK-NEXT:      End Instruction:   store i32 6, i32* %6, align 4
 ; CHECK-NEXT:  Function: cat, Basic Block: entry
 ; CHECK-NEXT:    Start Instruction:   store i32 4, i32* %4, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 5, i32* %5, align 4
@@ -14,10 +17,10 @@
 ; CHECK-NEXT:  Function: dog, Basic Block: entry
 ; CHECK-NEXT:    Start Instruction:   store i32 4, i32* %4, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 5, i32* %5, align 4
+; CHECK-NEXT:4 candidates of length 3.  Found in:
 ; CHECK-NEXT:  Function: turtle, Basic Block: (unnamed)
-; CHECK-NEXT:    Start Instruction:   store i32 5, i32* %5, align 4
+; CHECK-NEXT:    Start Instruction:   store i32 4, i32* %4, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 6, i32* %6, align 4
-; CHECK-NEXT:4 candidates of length 3.  Found in:
 ; CHECK-NEXT:  Function: cat, Basic Block: entry
 ; CHECK-NEXT:    Start Instruction:   store i32 3, i32* %3, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 5, i32* %5, align 4
@@ -27,10 +30,10 @@
 ; CHECK-NEXT:  Function: dog, Basic Block: entry
 ; CHECK-NEXT:    Start Instruction:   store i32 3, i32* %3, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 5, i32* %5, align 4
+; CHECK-NEXT:4 candidates of length 4.  Found in:
 ; CHECK-NEXT:  Function: turtle, Basic Block: (unnamed)
-; CHECK-NEXT:    Start Instruction:   store i32 4, i32* %4, align 4
+; CHECK-NEXT:    Start Instruction:   store i32 3, i32* %3, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 6, i32* %6, align 4
-; CHECK-NEXT:4 candidates of length 4.  Found in:
 ; CHECK-NEXT:  Function: cat, Basic Block: entry
 ; CHECK-NEXT:    Start Instruction:   store i32 2, i32* %2, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 5, i32* %5, align 4
@@ -40,10 +43,10 @@
 ; CHECK-NEXT:  Function: dog, Basic Block: entry
 ; CHECK-NEXT:    Start Instruction:   store i32 2, i32* %2, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 5, i32* %5, align 4
+; CHECK-NEXT:4 candidates of length 5.  Found in:
 ; CHECK-NEXT:  Function: turtle, Basic Block: (unnamed)
-; CHECK-NEXT:    Start Instruction:   store i32 3, i32* %3, align 4
+; CHECK-NEXT:    Start Instruction:   store i32 2, i32* %2, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 6, i32* %6, align 4
-; CHECK-NEXT:4 candidates of length 5.  Found in:
 ; CHECK-NEXT:  Function: cat, Basic Block: entry
 ; CHECK-NEXT:    Start Instruction:   store i32 1, i32* %1, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 5, i32* %5, align 4
@@ -53,10 +56,10 @@
 ; CHECK-NEXT:  Function: dog, Basic Block: entry
 ; CHECK-NEXT:    Start Instruction:   store i32 1, i32* %1, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 5, i32* %5, align 4
+; CHECK-NEXT:4 candidates of length 6.  Found in:
 ; CHECK-NEXT:  Function: turtle, Basic Block: (unnamed)
-; CHECK-NEXT:    Start Instruction:   store i32 2, i32* %2, align 4
+; CHECK-NEXT:    Start Instruction:   store i32 1, i32* %1, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 6, i32* %6, align 4
-; CHECK-NEXT:4 candidates of length 6.  Found in:
 ; CHECK-NEXT:  Function: cat, Basic Block: entry
 ; CHECK-NEXT:    Start Instruction:   store i32 6, i32* %0, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 5, i32* %5, align 4
@@ -66,9 +69,6 @@
 ; CHECK-NEXT:  Function: dog, Basic Block: entry
 ; CHECK-NEXT:    Start Instruction:   store i32 6, i32* %0, align 4
 ; CHECK-NEXT:      End Instruction:   store i32 5, i32* %5, align 4
-; CHECK-NEXT:  Function: turtle, Basic Block: (unnamed)
-; CHECK-NEXT:    Start Instruction:   store i32 1, i32* %1, align 4
-; CHECK-NEXT:      End Instruction:   store i32 6, i32* %6, align 4
 
 define linkonce_odr void @fish() {
 entry:
diff --git a/llvm/test/Analysis/IRSimilarityIdentifier/different.ll b/llvm/test/Analysis/IRSimilarityIdentifier/different.ll
--- a/llvm/test/Analysis/IRSimilarityIdentifier/different.ll
+++ b/llvm/test/Analysis/IRSimilarityIdentifier/different.ll
@@ -7,11 +7,11 @@
 
 ; CHECK: 2 candidates of length 3.  Found in:
 ; CHECK-NEXT:   Function: turtle, Basic Block: (unnamed)
-; CHECK-NEXT:     Start Instruction:   %a = load i32, i32* %0, align 4
-; CHECK-NEXT:       End Instruction:   %c = load i32, i32* %2, align 4
-; CHECK-NEXT:   Function: turtle, Basic Block: (unnamed)
 ; CHECK-NEXT:     Start Instruction:   %b = load i32, i32* %1, align 4
 ; CHECK-NEXT:       End Instruction:   %d = load i32, i32* %3, align 4
+; CHECK-NEXT:   Function: turtle, Basic Block: (unnamed)
+; CHECK-NEXT:     Start Instruction:   %a = load i32, i32* %0, align 4
+; CHECK-NEXT:       End Instruction:   %c = load i32, i32* %2, align 4
 ; CHECK-NEXT: 2 candidates of length 5.  Found in:
 ; CHECK-NEXT:   Function: fish, Basic Block: entry
 ; CHECK-NEXT:     Start Instruction:   store i32 6, i32* %0, align 4
diff --git a/llvm/test/Transforms/IROutliner/illegal-branches.ll b/llvm/test/Transforms/IROutliner/illegal-branches.ll
--- a/llvm/test/Transforms/IROutliner/illegal-branches.ll
+++ b/llvm/test/Transforms/IROutliner/illegal-branches.ll
@@ -1,5 +1,5 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s
+; RUN: opt -S -verify -iroutliner -no-ir-sim-branch-matching -ir-outlining-no-cost < %s | FileCheck %s
 
 ; Show that we do not extract sections with branches as it would require extra
 ; label and control flow checking.
diff --git a/llvm/test/Transforms/IROutliner/illegal-catchpad.ll b/llvm/test/Transforms/IROutliner/illegal-catchpad.ll
--- a/llvm/test/Transforms/IROutliner/illegal-catchpad.ll
+++ b/llvm/test/Transforms/IROutliner/illegal-catchpad.ll
@@ -1,5 +1,5 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s
+; RUN: opt -S -verify -iroutliner -no-ir-sim-branch-matching -ir-outlining-no-cost < %s | FileCheck %s
 
 ; This test checks that catchpad instructions are not outlined even if they
 ; in a similar section.  Dealing with exception handling inside of an outlined
diff --git a/llvm/test/Transforms/IROutliner/illegal-cleanup.ll b/llvm/test/Transforms/IROutliner/illegal-cleanup.ll
--- a/llvm/test/Transforms/IROutliner/illegal-cleanup.ll
+++ b/llvm/test/Transforms/IROutliner/illegal-cleanup.ll
@@ -1,5 +1,5 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s
+; RUN: opt -S -verify -iroutliner -no-ir-sim-branch-matching -ir-outlining-no-cost < %s | FileCheck %s
 
 ; This test checks that cleanuppad instructions are not outlined even if they
 ; in a similar section.  Dealing with exception handling inside of an outlined
diff --git a/llvm/test/Transforms/IROutliner/illegal-landingpad.ll b/llvm/test/Transforms/IROutliner/illegal-landingpad.ll
--- a/llvm/test/Transforms/IROutliner/illegal-landingpad.ll
+++ b/llvm/test/Transforms/IROutliner/illegal-landingpad.ll
@@ -1,5 +1,5 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s
+; RUN: opt -S -verify -iroutliner -no-ir-sim-branch-matching -ir-outlining-no-cost < %s | FileCheck %s
 
 ; This test checks that landingpad instructions are not outlined even if they
 ; in a similar section.  Dealing with exception handling inside of an outlined
diff --git a/llvm/test/Transforms/IROutliner/region-end-of-module.ll b/llvm/test/Transforms/IROutliner/region-end-of-module.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/IROutliner/region-end-of-module.ll
@@ -0,0 +1,69 @@
+; 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
+
+; This test checks that we do not fail when there is a similarity group with
+; an ending instruction that is also the end of the module.
+
+@a = global i8* null
+
+define void @foo() {
+entry:
+  br label %for.cond1
+
+for.cond1:
+  br label %for.body
+
+for.body:
+  %inc = add nsw i32 2, 1
+  br label %for.cond1
+
+for.end:
+  %inc3 = add nsw i32 2, 1
+  br label %for.cond1
+}
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND1:%.*]]
+; CHECK:       for.cond1:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INC:%.*]] = add nsw i32 2, 1
+; CHECK-NEXT:    br label [[FOR_COND1]]
+; CHECK:       for.end:
+; CHECK-NEXT:    [[INC3:%.*]] = add nsw i32 2, 1
+; CHECK-NEXT:    br label [[FOR_COND1]]
+;
+
+; These are for testing if return instructions or unreachable instructions are
+; matched for similarity.
+define void @foo1() {
+entry:
+  br label %for.cond1
+
+for.cond1:
+  br label %for.body
+
+for.body:
+  %inc = add nsw i32 2, 1
+  ret void
+
+for.end:
+  %inc3 = add nsw i32 2, 1
+  ret void
+}
+
+define void @foo2() {
+entry:
+  br label %for.cond1
+
+for.cond1:
+  br label %for.body
+
+for.body:
+  %inc = add nsw i32 2, 1
+  unreachable
+
+for.end:
+  %inc3 = add nsw i32 2, 1
+  unreachable
+}
diff --git a/llvm/test/tools/llvm-sim/single-sim-file.test b/llvm/test/tools/llvm-sim/single-sim-file.test
--- a/llvm/test/tools/llvm-sim/single-sim-file.test
+++ b/llvm/test/tools/llvm-sim/single-sim-file.test
@@ -4,54 +4,54 @@
 # Checking the output of a single module test.
 
 # CHECK: {
-# CHECK-NEXT:  "1": [
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 8,
-# CHECK-NEXT:    "end": 9
-# CHECK-NEXT:   },
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 18,
-# CHECK-NEXT:    "end": 19
-# CHECK-NEXT:   }
-# CHECK-NEXT:  ],
-# CHECK-NEXT:  "2": [
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 7,
-# CHECK-NEXT:    "end": 9
-# CHECK-NEXT:   },
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 17,
-# CHECK-NEXT:    "end": 19
-# CHECK-NEXT:   }
-# CHECK-NEXT:  ],
-# CHECK-NEXT:  "3": [
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 6,
-# CHECK-NEXT:    "end": 9
-# CHECK-NEXT:   },
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 16,
-# CHECK-NEXT:    "end": 19
-# CHECK-NEXT:   }
-# CHECK-NEXT:  ],
-# CHECK-NEXT:  "4": [
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 5,
-# CHECK-NEXT:    "end": 9
-# CHECK-NEXT:   },
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 15,
-# CHECK-NEXT:    "end": 19
-# CHECK-NEXT:   }
-# CHECK-NEXT:  ],
-# CHECK-NEXT:  "5": [
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 4,
-# CHECK-NEXT:    "end": 9
-# CHECK-NEXT:   },
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 14,
-# CHECK-NEXT:    "end": 19
-# CHECK-NEXT:   }
-# CHECK-NEXT:  ]
-# CHECK-NEXT: }
+# CHECK-NEXT: "1": [
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 18,
+# CHECK-NEXT:   "end": 19
+# CHECK-NEXT:  },
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 8,
+# CHECK-NEXT:   "end": 9
+# CHECK-NEXT:  }
+# CHECK-NEXT: ],
+# CHECK-NEXT: "2": [
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 17,
+# CHECK-NEXT:   "end": 19
+# CHECK-NEXT:  },
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 7,
+# CHECK-NEXT:   "end": 9
+# CHECK-NEXT:  }
+# CHECK-NEXT: ],
+# CHECK-NEXT: "3": [
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 16,
+# CHECK-NEXT:   "end": 19
+# CHECK-NEXT:  },
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 6,
+# CHECK-NEXT:   "end": 9
+# CHECK-NEXT:  }
+# CHECK-NEXT: ],
+# CHECK-NEXT: "4": [
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 15,
+# CHECK-NEXT:   "end": 19
+# CHECK-NEXT:  },
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 5,
+# CHECK-NEXT:   "end": 9
+# CHECK-NEXT:  }
+# CHECK-NEXT: ],
+# CHECK-NEXT: "5": [
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 14,
+# CHECK-NEXT:   "end": 19
+# CHECK-NEXT:  },
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 4,
+# CHECK-NEXT:   "end": 9
+# CHECK-NEXT:  }
+# CHECK-NEXT: ]
+# CHECK-NEXT:}
diff --git a/llvm/test/tools/llvm-sim/single-sim.test b/llvm/test/tools/llvm-sim/single-sim.test
--- a/llvm/test/tools/llvm-sim/single-sim.test
+++ b/llvm/test/tools/llvm-sim/single-sim.test
@@ -3,54 +3,54 @@
 # Checking the output of a single module test.
 
 # CHECK: {
-# CHECK-NEXT:  "1": [
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 8,
-# CHECK-NEXT:    "end": 9
-# CHECK-NEXT:   },
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 18,
-# CHECK-NEXT:    "end": 19
-# CHECK-NEXT:   }
-# CHECK-NEXT:  ],
-# CHECK-NEXT:  "2": [
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 7,
-# CHECK-NEXT:    "end": 9
-# CHECK-NEXT:   },
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 17,
-# CHECK-NEXT:    "end": 19
-# CHECK-NEXT:   }
-# CHECK-NEXT:  ],
-# CHECK-NEXT:  "3": [
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 6,
-# CHECK-NEXT:    "end": 9
-# CHECK-NEXT:   },
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 16,
-# CHECK-NEXT:    "end": 19
-# CHECK-NEXT:   }
-# CHECK-NEXT:  ],
-# CHECK-NEXT:  "4": [
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 5,
-# CHECK-NEXT:    "end": 9
-# CHECK-NEXT:   },
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 15,
-# CHECK-NEXT:    "end": 19
-# CHECK-NEXT:   }
-# CHECK-NEXT:  ],
-# CHECK-NEXT:  "5": [
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 4,
-# CHECK-NEXT:    "end": 9
-# CHECK-NEXT:   },
-# CHECK-NEXT:   {
-# CHECK-NEXT:    "start": 14,
-# CHECK-NEXT:    "end": 19
-# CHECK-NEXT:   }
-# CHECK-NEXT:  ]
-# CHECK-NEXT: }
+# CHECK-NEXT: "1": [
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 18,
+# CHECK-NEXT:   "end": 19
+# CHECK-NEXT:  },
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 8,
+# CHECK-NEXT:   "end": 9
+# CHECK-NEXT:  }
+# CHECK-NEXT: ],
+# CHECK-NEXT: "2": [
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 17,
+# CHECK-NEXT:   "end": 19
+# CHECK-NEXT:  },
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 7,
+# CHECK-NEXT:   "end": 9
+# CHECK-NEXT:  }
+# CHECK-NEXT: ],
+# CHECK-NEXT: "3": [
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 16,
+# CHECK-NEXT:   "end": 19
+# CHECK-NEXT:  },
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 6,
+# CHECK-NEXT:   "end": 9
+# CHECK-NEXT:  }
+# CHECK-NEXT: ],
+# CHECK-NEXT: "4": [
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 15,
+# CHECK-NEXT:   "end": 19
+# CHECK-NEXT:  },
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 5,
+# CHECK-NEXT:   "end": 9
+# CHECK-NEXT:  }
+# CHECK-NEXT: ],
+# CHECK-NEXT: "5": [
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 14,
+# CHECK-NEXT:   "end": 19
+# CHECK-NEXT:  },
+# CHECK-NEXT:  {
+# CHECK-NEXT:   "start": 4,
+# CHECK-NEXT:   "end": 9
+# CHECK-NEXT:  }
+# CHECK-NEXT: ]
+# CHECK-NEXT:}
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
@@ -41,7 +41,9 @@
 void getSimilarities(
     Module &M,
     std::vector<std::vector<IRSimilarityCandidate>> &SimilarityCandidates) {
-  IRSimilarityIdentifier Identifier;
+  // In order to keep the size of the tests from becoming too large, we do not
+  // recognize similarity for branches unless explicitly needed.
+  IRSimilarityIdentifier Identifier(/*EnableBranchMatching = */false);
   SimilarityCandidates = Identifier.findSimilarity(M);
 }
 
@@ -726,22 +728,8 @@
   ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
 }
 
-// In most cases, the illegal instructions we are collecting don't require any
-// sort of setup.  In these cases, we can just only have illegal instructions,
-// and the mapper will create 0 length vectors, and we can check that.
-
-// In cases where we have legal instructions needed to set up the illegal
-// instruction, to check illegal instructions are assigned unsigned integers
-// from the maximum value decreasing to 0, it will be greater than a legal
-// instruction that comes after.  So to check that we have an illegal
-// instruction, we place a legal instruction after an illegal instruction, and
-// check that the illegal unsigned integer is greater than the unsigned integer
-// of the legal instruction.
-
-// Checks that the branch is mapped to be illegal since there is extra checking
-// needed to ensure that a branch in one region is branching to an isomorphic
-// location in a different region.
-TEST(IRInstructionMapper, BranchIllegal) {
+// Checks that the branch is mapped to legal when the option is set.
+TEST(IRInstructionMapper, BranchLegal) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
@@ -759,12 +747,28 @@
   SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
   SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
   IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
+  Mapper.InstClassifier.EnableBranches = true;
+  Mapper.initializeForBBs(*M);
   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_TRUE(UnsignedVec[1] > UnsignedVec[0]);
+  ASSERT_TRUE(UnsignedVec[1] < UnsignedVec[2]);
 }
 
+// In most cases, the illegal instructions we are collecting don't require any
+// sort of setup.  In these cases, we can just only have illegal instructions,
+// and the mapper will create 0 length vectors, and we can check that.
+
+// In cases where we have legal instructions needed to set up the illegal
+// instruction, to check illegal instructions are assigned unsigned integers
+// from the maximum value decreasing to 0, it will be greater than a legal
+// instruction that comes after.  So to check that we have an illegal
+// instruction, we place a legal instruction after an illegal instruction, and
+// check that the illegal unsigned integer is greater than the unsigned integer
+// of the legal instruction.
+
 // Checks that a PHINode is mapped to be illegal since there is extra checking
 // needed to ensure that a branch in one region is bin an isomorphic
 // location in a different region.
@@ -1445,8 +1449,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(6));
-  ASSERT_TRUE(UnsignedVec[2] < UnsignedVec[1]);
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(7));
+  ASSERT_TRUE(UnsignedVec[2] < UnsignedVec[0]);
 }
 
 // Checks that a memcpy instruction is mapped to an illegal value.
@@ -1476,8 +1480,9 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(6));
-  ASSERT_TRUE(UnsignedVec[2] < UnsignedVec[1]);
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(7));
+  ASSERT_GT(UnsignedVec[2], UnsignedVec[3]);
+  ASSERT_LT(UnsignedVec[2], UnsignedVec[0]);
 }
 
 // Checks that a memmove instruction is mapped to an illegal value.
@@ -1507,8 +1512,8 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(6));
-  ASSERT_TRUE(UnsignedVec[2] < UnsignedVec[1]);
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(7));
+  ASSERT_LT(UnsignedVec[2], UnsignedVec[0]);
 }
 
 // Checks that a variable argument instructions are mapped to an illegal value.
@@ -1555,11 +1560,10 @@
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(16));
-  ASSERT_TRUE(UnsignedVec[4] < UnsignedVec[3]);
-  ASSERT_TRUE(UnsignedVec[7] < UnsignedVec[6]);
-  ASSERT_TRUE(UnsignedVec[10] < UnsignedVec[9]);
-  ASSERT_TRUE(UnsignedVec[13] < UnsignedVec[12]);
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(17));
+  ASSERT_TRUE(UnsignedVec[7] < UnsignedVec[0]);
+  ASSERT_TRUE(UnsignedVec[13] < UnsignedVec[10]);
+  ASSERT_TRUE(UnsignedVec[16] < UnsignedVec[13]);
 }
 
 // Check the length of adding two illegal instructions one after th other.  We
@@ -1599,21 +1603,23 @@
 // two blocks of two legal instructions and terminator, and checks them for
 // instruction similarity.
 static bool longSimCandCompare(std::vector<IRInstructionData *> &InstrList,
-                               bool Structure = false) {
+                               bool Structure = false, unsigned Length = 2,
+                               unsigned StartIdxOne = 0,
+                               unsigned StartIdxTwo = 3) {
   std::vector<IRInstructionData *>::iterator Start, End;
 
   Start = InstrList.begin();
   End = InstrList.begin();
 
-  std::advance(End, 1);
-  IRSimilarityCandidate Cand1(0, 2, *Start, *End);
+  std::advance(End, StartIdxOne + Length - 1);
+  IRSimilarityCandidate Cand1(StartIdxOne, Length, *Start, *End);
 
   Start = InstrList.begin();
   End = InstrList.begin();
 
-  std::advance(Start, 3);
-  std::advance(End, 4);
-  IRSimilarityCandidate Cand2(3, 2, *Start, *End);
+  std::advance(Start, StartIdxTwo);
+  std::advance(End, StartIdxTwo + Length - 1);
+  IRSimilarityCandidate Cand2(StartIdxTwo, Length, *Start, *End);
   if (Structure)
     return IRSimilarityCandidate::compareStructure(Cand1, Cand2);
   return IRSimilarityCandidate::isSimilar(Cand1, Cand2);
@@ -2083,6 +2089,206 @@
   ASSERT_TRUE(longSimCandCompare(InstrList, true));
 }
 
+// Checks that the same structure is recognized between two candidates when
+// the branches target other blocks inside the same region, the relative
+// distance between the blocks must be the same.
+TEST(IRSimilarityCandidate, SameBranchStructureInternal) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = add i32 %b, %a
+                             br label %bb1
+                          bb1:
+                             %2 = add i32 %b, %a
+                             %3 = add i32 %a, %b
+                             ret i32 0
+                          }
+                          
+                          define i32 @f2(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = add i32 %b, %a
+                             br label %bb1
+                          bb1:
+                             %2 = add i32 %b, %a
+                             %3 = add i32 %a, %b
+                             ret i32 0
+                          })";
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  std::vector<IRInstructionData *> InstrList;
+  std::vector<unsigned> UnsignedVec;
+
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
+  Mapper.InstClassifier.EnableBranches = true;
+  Mapper.initializeForBBs(*M);
+  getVectors(*M, Mapper, InstrList, UnsignedVec);
+
+  // Check to make sure that we have a long enough region.
+  ASSERT_EQ(InstrList.size(), static_cast<unsigned>(12));
+  // Check that the instructions were added correctly to both vectors.
+  ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
+
+  ASSERT_TRUE(longSimCandCompare(InstrList, true, 5, 0, 6));
+}
+
+// Checks that the different structure is recognized between two candidates,
+// when the branches target other blocks inside the same region, the relative
+// distance between the blocks must be the same.
+TEST(IRSimilarityCandidate, DifferentBranchStructureInternal) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = add i32 %b, %a
+                             br label %bb2
+                          bb1:
+                             %2 = add i32 %b, %a
+                             %3 = add i32 %a, %b
+                             br label %bb2
+                          bb2:
+                             %4 = add i32 %b, %a
+                             %5 = add i32 %a, %b
+                             ret i32 0
+                          }
+                          
+                          define i32 @f2(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = add i32 %b, %a
+                             br label %bb1
+                          bb1:
+                             %2 = add i32 %b, %a
+                             %3 = add i32 %a, %b
+                             br label %bb2
+                          bb2:
+                             %4 = add i32 %b, %a
+                             %5 = add i32 %a, %b
+                             ret i32 0
+                          })";
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  std::vector<IRInstructionData *> InstrList;
+  std::vector<unsigned> UnsignedVec;
+
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
+  Mapper.InstClassifier.EnableBranches = true;
+  Mapper.initializeForBBs(*M);
+  getVectors(*M, Mapper, InstrList, UnsignedVec);
+
+  // Check to make sure that we have a long enough region.
+  ASSERT_EQ(InstrList.size(), static_cast<unsigned>(18));
+  // Check that the instructions were added correctly to both vectors.
+  ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
+
+  ASSERT_FALSE(longSimCandCompare(InstrList, true, 6, 0, 9));
+}
+
+// Checks that the same structure is recognized between two candidates, when
+// the branches target other blocks outside region, the relative distance
+// does not need to be the same.
+TEST(IRSimilarityCandidate, SameBranchStructureOutside) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = add i32 %b, %a
+                             br label %bb1
+                          bb1:
+                             %2 = add i32 %b, %a
+                             %3 = add i32 %a, %b
+                             ret i32 0
+                          }
+                          
+                          define i32 @f2(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = add i32 %b, %a
+                             br label %bb1
+                          bb1:
+                             %2 = add i32 %b, %a
+                             %3 = add i32 %a, %b
+                             ret i32 0
+                          })";
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  std::vector<IRInstructionData *> InstrList;
+  std::vector<unsigned> UnsignedVec;
+
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
+  Mapper.InstClassifier.EnableBranches = true;
+  Mapper.initializeForBBs(*M);
+  getVectors(*M, Mapper, InstrList, UnsignedVec);
+
+  // Check to make sure that we have a long enough region.
+  ASSERT_EQ(InstrList.size(), static_cast<unsigned>(12));
+  // Check that the instructions were added correctly to both vectors.
+  ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
+
+  ASSERT_TRUE(longSimCandCompare(InstrList, true, 3, 0, 6));
+}
+
+// Checks that the same structure is recognized between two candidates, when
+// the branches target other blocks outside region, the relative distance
+// does not need to be the same.
+TEST(IRSimilarityCandidate, DifferentBranchStructureOutside) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = add i32 %b, %a
+                             br label %bb1
+                          bb1:
+                             %2 = add i32 %b, %a
+                             %3 = add i32 %a, %b
+                             ret i32 0
+                          }
+                          
+                          define i32 @f2(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = add i32 %b, %a
+                             br label %bb2
+                          bb1:
+                             %2 = add i32 %b, %a
+                             %3 = add i32 %a, %b
+                             br label %bb2
+                          bb2:
+                             %4 = add i32 %b, %a
+                             %5 = add i32 %a, %b
+                             ret i32 0
+                          })";
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  std::vector<IRInstructionData *> InstrList;
+  std::vector<unsigned> UnsignedVec;
+
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
+  Mapper.InstClassifier.EnableBranches = true;
+  Mapper.initializeForBBs(*M);
+  getVectors(*M, Mapper, InstrList, UnsignedVec);
+
+  // Check to make sure that we have a long enough region.
+  ASSERT_EQ(InstrList.size(), static_cast<unsigned>(15));
+  // Check that the instructions were added correctly to both vectors.
+  ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
+
+  ASSERT_TRUE(longSimCandCompare(InstrList, true, 3, 0, 6));
+}
+
 // Checks that two sets of identical instructions are found to be the same.
 // Both sequences of adds have the same operand ordering, and the same
 // instructions, making them strcturally equivalent.