[IRSim] Finding Branch Similarity

[AndrewLitteken]

Summary

The current IRSimilarityIdentifier does not try to find similarity across blocks, this patch provides a mechanism to compare two branches against one another, to find similarity across basic blocks, rather than just within them.

This adds a step in the similarity identification process that labels all of the basic blocks so that we can identify the relative branching locations. Within an IRSimilarityCandidate we use these relative locations to determine whether if the branching to other relative locations in the same region is the same between branches. If they are, we consider them similar.

We do not consider the relative location of the branch if the target branch is outside of the region. In this case, both branches must exit to a location outside the region, but the exact relative location does not matter.

[AndrewLitteken]

Adding comments to the code, and adjusting tests.

[yroux]

I found an issue with the IROutliner while testing this patch which I don't easily catch, when pruning icompatible regions there is an assert violation at llvm/include/llvm/ADT/ilist_iterator.h:138
The problem can be reproduce with this reduce testcase:

opt -S -iroutliner ~/test.ll -o -

test.ll:

@a = global i8* null

define void @foo() {
entry:
  br label %for.cond

for.cond:
  %c.0 = phi i32 [ undef, %entry ], [ %inc3, %for.end ]
  %d.0 = phi i32 [ undef, %entry ], [ %d.1, %for.end ]
  %conv = trunc i32 %c.0 to i8
  br label %for.cond1

for.cond1:
  %d.1 = phi i32 [ %d.0, %for.cond ], [ %inc, %for.body ]
  %cmp = icmp slt i32 %d.1, 0
  br i1 %cmp, label %for.body, label %for.end

for.body:
  %0 = load i8*, i8** @a
  %arrayidx = getelementptr inbounds i8, i8* %0, i32 %d.1
  store i8 %conv, i8* %arrayidx
  %inc = add nsw i32 %d.1, 1
  br label %for.cond1

for.end:
  %inc3 = add nsw i32 %c.0, 1
  br label %for.cond
}

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

754

Maybe use ASSERT_GT and ASSERT_LT here and in the rest of the testcase

[AndrewLitteken]

Updating to fix bug pointed out by Yvan, and adding test to catch it.

[paquette]

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

130

Why int?

150

remove fluff

303

359

461

comment?

461

comment on this variable?

860

doxygen comment on this variable?

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

26

Mention this is for debugging?

174

pull second if into this one?

175

pull if into the if above?

688

de morgan this and early return true to reduce indentation?

688

Cache ItA->Inst and ItB->Inst in variables?

also can you early return true or false using this condition? This if is pretty big.

703

this is a pretty dense statement. can you simplify this somehow? maybe it would be better as a helper function or something?

713

this could assign to AContained right?

bool AContained = BasicBloc A.find(...) != ...;

806

why is there a special case for 2? comment?

llvm/lib/Transforms/IPO/IROutliner.cpp

1392 ↗

(On Diff #368736)

I think that you should check for the end of the list in a different way. This seems like a workaround for a different bug? Nowhere else in the codebase uses isKnownSentinel directly.

[AndrewLitteken]

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

130

I'll add a comment for this variable, but it's because we could be targeting blocks that are "in front of" the other blocks in the function, or behind, so it needs to be able to be positive or negative.

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

806

This should probably get moved to the outliner side of things.

[AndrewLitteken]

Updating based on comments

[paquette]

Missing context for the patch?

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

131

Can you add an example of "ahead of" and "behind" in the comments here?

145

typo: IRInstrucitonData

613

Can you add a comment explaining the role of this struct?

621

Should this be a doxygen comment?

651

I think an example would be useful here?

657

I think it would be good to document what a relative location is somewhere in a comment in this patch.

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

187

De Morgan + return this value?

631

What does it mean if !AContained?

Maybe this function needs some comments?

713

run-on sentence is hard to read?

732

Merge this if in with the previous one?

741

use any_of and return !checkRelativeLocations?

llvm/lib/Transforms/IPO/IROutliner.cpp

1457 ↗

(On Diff #369520)

• Can you pull IDIt->Inst into variable?
• simpler:

if (blah && blah != NextInst)
   return true;

[AndrewLitteken]

Adding diff with context

[AndrewLitteken]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

187

Since it's possible this function will have more instruction types added to it, that may remain true, and for clarity I feel like it's better to keep it as is.

[AndrewLitteken]

Updating based on comments.

[paquette]

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

141

This is a function, so I think it should be documented more like "Fills data structures for IRInstructionData..."

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

59

Why would I ever be null?

llvm/lib/Transforms/IPO/IROutliner.cpp

1451 ↗

(On Diff #369565)

This is duplicated with the code above. Can this be a helper?

[AndrewLitteken]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

59

I changed things up so that at the end of a function, there is a nullptr used for the instruction of the IRInstructionData so that the end of the list can be detected rather than having to use the isKnownSentinel code from before.

[paquette]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

692

ItA->RelativeBlockLocations and ItB->RelativeBlockLocations into variables? Then you can reuse them in the zip below.

697

can you use a typedef for this?

like ZippedRelativeLocationsT or something?

[AndrewLitteken]

Updating based on comments

[paquette]

llvm/lib/Transforms/IPO/IROutliner.cpp

1361 ↗

(On Diff #370424)

This name is kind of confusing considering the other Instruction is named NextInst?

1363 ↗

(On Diff #370424)

Just use NextIDInst here?

1365 ↗

(On Diff #370424)

Same here?

llvm/test/Transforms/IROutliner/region-end-of-module.ll

4 ↗

(On Diff #370424)

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

44

Add comment saying what the false is describing?

Identifier(/*blah = */false);

[AndrewLitteken]

llvm/lib/Transforms/IPO/IROutliner.cpp

1363 ↗

(On Diff #370424)

That would be using the next instruction in the list, this is checking what the current instruction that was passed in.

1365 ↗

(On Diff #370424)

I'll change it for this one.

[paquette]

Can you fix the pre-merge checks?

[paquette]

llvm/lib/Transforms/IPO/IROutliner.cpp

1361 ↗

(On Diff #370647)

Can NextIDIt be the end/one past the end? Is this accessible in those cases?

llvm/test/Transforms/IROutliner/region-end-of-module.ll

3 ↗

(On Diff #370647)

each of the cases here end in a br.

What about unreachable and ret?

[AndrewLitteken]

llvm/lib/Transforms/IPO/IROutliner.cpp

1361 ↗

(On Diff #370647)

It shouldn’t be. This is looking from the start of the candidate to the end of the candidate, which should only ever include actual instructions. So it could be the end of the function, in which case there is a buffer IRInstructionData which is the nullptr, which is what we are checking here.

llvm/test/Transforms/IROutliner/region-end-of-module.ll

3 ↗

(On Diff #370647)

Those are into checked for similarity right now, and are excluded from the candidates as a result.

But I can add a function that ends in both for potential future developments.

[paquette]

LGTM

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

struct IRInstructionData : ilist_node<IRInstructionData> {
   /// considered similar.
   bool Legal;
 
   /// This is only relevant if we are wrapping a CmpInst where we needed to
   /// change the predicate of a compare instruction from a greater than form
   /// to a less than form.  It is None otherwise.
   Optional<CmpInst::Predicate> RevisedPredicate;
 
+  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);
 
   /// Get the predicate that the compare instruction is using for hashing the
   /// instruction. the IRInstructionData must be wrapping a CmpInst.
   CmpInst::Predicate getPredicate() const;
 
   /// A function that swaps the predicates to their less than form if they are
   /// in a greater than form. Otherwise, the predicate is unchanged.
   ///
   /// \param CI - The comparison operation to find a consistent preidcate for.
   /// \return the consistent comparison predicate. 
   static CmpInst::Predicate predicateForConsistency(CmpInst *CI);
 
+  /// A function that 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.
   ///
   /// As a simple example, consider the following instructions.
   ///
   /// \code
   /// %add1 = add i32 %x1, %y1
struct IRInstructionMapper {
 
   /// The next available integer to assign to a legal Instruction to.
   unsigned LegalInstrNumber = 0;
 
   /// Correspondence from IRInstructionData to unsigned integers.
   DenseMap<IRInstructionData *, unsigned, IRInstructionDataTraits>
       InstructionIntegerMap;
 
+  /// A mapping for a basic block in a module to it's 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
   /// than one illegal number per range.
   bool AddedIllegalLastTime = false;
 
   /// Marks whether we found a illegal instruction in the previous step.
   bool CanCombineWithPrevInstr = false;
struct IRInstructionMapper {
 
   /// Get an allocated IRInstructionDataList object using the IDLAllocator.
   ///
   /// \returns An allocated IRInstructionDataList object.
   IRInstructionDataList *allocateIRInstructionDataList();
 
   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 modules 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.
   ///
   /// \param [in] BB - The BasicBlock to be mapped to integers.
   /// \param [in,out] InstrList - Vector of IRInstructionData to append to.
   /// \param [in,out] IntegerMapping - Vector of unsigned integers to append to.
   void convertToUnsignedVec(BasicBlock &BB,
struct IRInstructionMapper {
 
   /// Custom InstVisitor to classify different instructions for whether it can
   /// be analyzed for similarity.
   struct InstructionClassification
       : public InstVisitor<InstructionClassification, InstrType> {
     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.
     InstrType visitAllocaInst(AllocaInst &AI) { return Illegal; }
     // We exclude variable argument instructions since variable arguments
     // requires extra checking of the argument list.
     InstrType visitVAArgInst(VAArgInst &VI) { return Illegal; }
     // We exclude all exception handling cases since they are so context
struct InstructionClassification
     }
     // TODO: We do not current handle similarity that changes the control flow.
     InstrType visitInvokeInst(InvokeInst &II) { return Illegal; }
     // TODO: We do not current handle similarity that changes the control flow.
     InstrType visitCallBrInst(CallBrInst &CBI) { return Illegal; }
     // TODO: Handle interblock similarity.
     InstrType visitTerminator(Instruction &I) { return Illegal; }
     InstrType visitInstruction(Instruction &I) { return Legal; }
+
+    bool EnableBranches = false;
   };
 
   /// Maps an Instruction to a member of InstrType.
   InstructionClassification InstClassifier;
 };
 
 /// This is a class that wraps a range of IRInstructionData from one point to
 /// another in the vector of IRInstructionData, which is a region of the
public:
   /// operand mappings to compare.
   /// \param B - The second IRInstructionCandidate, operand values, and current
   /// operand mappings to compare.
   /// \returns true if the IRSimilarityCandidates operands are compatible.
   static bool compareCommutativeOperandMapping(OperandMapping A,
                                                OperandMapping 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
   /// so that we can identify which global value number in on candidate
   /// relates to which number in the other.
   ///
   /// \param [in, out] A - The IRSimilarityCandidate to create a canonical
   /// numbering for.
   static void createCanonicalFor(IRSimilarityCandidate &A);
 
   /// Create a mapping for the value numbering of the calling
   /// IRSimilarityCandidate, to a different separate set of numbers, based on
   /// the canonical ordering in \A, and the found mappings in \p ToAMapping and
   /// \p FromAMapping.  Both of these relationships should have the same
   /// information, just in opposite directions.
   ///
   /// \param [in, out] A - The IRSimilarityCandidate to create a canonical
   /// numbering from.
   /// \param ToAMapping - The mapping of value numbers from this candidate to \p
   /// A.
   /// \param ToAMapping - The mapping of value numbers from \p A to this
   /// candidate.
   void createCanonicalRelationFrom(
       IRSimilarityCandidate &A,
       DenseMap<unsigned, DenseSet<unsigned>> &ToAMapping,
       DenseMap<unsigned, DenseSet<unsigned>> &FromAMapping);
 
+  /// \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
   /// the start instruction of one is greater than the start instruction of the
   /// other, they overlap.
   ///
   /// \returns true if the IRSimilarityCandidates do not have overlapping
   /// instructions.

 ///
 /// SimilarityGroup 1:  SimilarityGroup 2
 /// A, B, D             C
 ///
 /// A list of the different similarity groups is then returned after
 /// 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
   /// already present in the Mapper if possible.
   ///
   /// \param [in] M Module - To map to integers.
   /// \param [in,out] InstrList - The vector to append IRInstructionData to.
   /// \param [in,out] IntegerMapping - The vector to append integers to.
private:
 
   /// The allocator for IRInstructionDataLists.
   SpecificBumpPtrAllocator<IRInstructionDataList> InstDataListAllocator;
 
   /// Map Instructions to unsigned integers and wraps the Instruction in an
   /// instance of IRInstructionData.
   IRInstructionMapper Mapper;
 
+  bool EnableBranches = true;
+
   /// The SimilarityGroups found with the most recent run of \ref
   /// findSimilarity. None if there is no recent run.
   Optional<SimilarityGroupList> SimilarityCandidates;
 };
 
 } // end namespace IRSimilarity
 
 /// An analysis pass based on legacy pass manager that runs and returns

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

 #include "llvm/IR/Operator.h"
 #include "llvm/IR/User.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/SuffixTree.h"
 
 using namespace llvm;
 using namespace IRSimilarity;
 
+cl::opt<bool> DoNotEnableBranches(
+    "no-ir-sim-branch-matching", cl::init(false), cl::ReallyHidden,
+    cl::desc("disable similarity matching, and outlining, across branches."));
+
 IRInstructionData::IRInstructionData(Instruction &I, bool Legality,
                                      IRInstructionDataList &IDList)
     : Inst(&I), Legal(Legality), IDL(&IDList) {
   // 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)) {
     CmpInst::Predicate Predicate = predicateForConsistency(C);
if (isa<CmpInst>(I) && RevisedPredicate.hasValue()) {
       OperVals.insert(OperVals.begin(), OI.get());
       continue;
     }
 
     OperVals.push_back(OI.get());
   }
 }
 
+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:
   case CmpInst::FCMP_UGT:
   case CmpInst::FCMP_OGE:
   case CmpInst::FCMP_UGE:
   case CmpInst::ICMP_SGT:
   case CmpInst::ICMP_UGT:
bool IRSimilarity::isClose(const IRInstructionData &A,
   // true.
   if (isa<CallInst>(A.Inst) && isa<CallInst>(B.Inst)) {
     CallInst *CIA = cast<CallInst>(A.Inst);
     CallInst *CIB = cast<CallInst>(B.Inst);
     if (getCalledFunctionName(*CIA).compare(getCalledFunctionName(*CIB)) != 0)
       return false;
   }
 
+  if (isa<BranchInst>(A.Inst) && isa<BranchInst>(B.Inst)) {
+    if (A.RelativeBlockLocations.size() != B.RelativeBlockLocations.size())
+      return false;
+  }
+
   return true;
 }
 
 // TODO: This is the same as the MachineOutliner, and should be consolidated
 // into the same interface.
 void IRInstructionMapper::convertToUnsignedVec(
     BasicBlock &BB, std::vector<IRInstructionData *> &InstrList,
     std::vector<unsigned> &IntegerMapping) {
   BasicBlock::iterator It = BB.begin();
 
   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:
       mapToLegalUnsigned(It, IntegerMappingForBB, InstrListForBB);
       break;
     case InstrType::Illegal:
       mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB);
       break;
     case InstrType::Invisible:
       AddedIllegalLastTime = false;
       break;
     }
   }
 
   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);
   }
 }
 
 // TODO: This is the same as the MachineOutliner, and should be consolidated
if (CanCombineWithPrevInstr)
     HaveLegalRange = true;
   CanCombineWithPrevInstr = true;
 
   // Get the integer for this instruction or give it the current
   // LegalInstrNumber.
   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
       ResultIt;
   std::tie(ResultIt, WasInserted) =
       InstructionIntegerMap.insert(std::make_pair(ID, LegalInstrNumber));
   unsigned INumber = ResultIt->second;
 
bool IRSimilarityCandidate::compareStructure(
   // one element, and that same element maps to the original element in the
   // candidate we have a good mapping.
   DenseMap<unsigned, DenseSet<unsigned>>::iterator ValueMappingIt;
 
 
   // Iterate over the instructions contained in each candidate
   unsigned SectionLength = A.getStartIdx() + A.getLength();
   for (unsigned Loc = A.getStartIdx(); Loc < SectionLength;
        ItA++, ItB++, Loc++) {
     // Make sure the instructions are similar to one another.
     if (!isClose(*ItA, *ItB))
       return false;
 
     Instruction *IA = ItA->Inst;
     Instruction *IB = ItB->Inst;
 
     if (!ItA->Legal || !ItB->Legal)
if (IA->isCommutative() && !isa<FPMathOperator>(IA)) {
       continue;
     }
 
     // Handle the non-commutative cases.
     if (!compareNonCommutativeOperandMapping(
             {A, OperValsA, ValueNumberMappingA},
             {B, OperValsB, ValueNumberMappingB}))
       return false;
+
+    // Here we check that between two corresponding branch instructions,
+    // when the branch targets a basic block within the same region, the
+    // relative locations are the same, and otherwise, are targeting basic
+    // blocks outside the region at the same 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>(ItA->Inst) && isa<BranchInst>(ItB->Inst)) ||
+        (isa<PHINode>(ItA->Inst) && isa<PHINode>(ItB->Inst))) {
+      if (ItA->RelativeBlockLocations.size() !=
+          ItB->RelativeBlockLocations.size())
+        return false;
+
+      if (OperValsA.size() != OperValsB.size())
+        return false;
+
+      detail::zippy<detail::zip_shortest, SmallVector<int, 4> &,
+                    SmallVector<int, 4> &, ArrayRef<Value *> &,
+                    ArrayRef<Value *> &>
+          ZippedRelativeLocations =
+              zip(ItA->RelativeBlockLocations, ItB->RelativeBlockLocations,
+                  OperValsA, OperValsB);
+      if (!all_of(ZippedRelativeLocations,
+                  [&A, &B](std::tuple<int, int, Value *, Value *> R) {
+                    BasicBlock *ABB = static_cast<BasicBlock *>(std::get<2>(R));
+                    BasicBlock *BBB = static_cast<BasicBlock *>(std::get<3>(R));
+                    bool AContained = false;
+                    bool BContained = false;
+                    DenseSet<BasicBlock *> BasicBlockA;
+                    DenseSet<BasicBlock *> BasicBlockB;
+                    A.getBasicBlocks(BasicBlockA);
+                    B.getBasicBlocks(BasicBlockB);
+                    if (BasicBlockA.find(ABB) != BasicBlockA.end())
+                      AContained = true;
+                    if (BasicBlockB.find(BBB) != BasicBlockB.end())
+                      BContained = true;
+                    if (AContained != BContained)
+                      return false;
+                    if (AContained)
+                      return std::get<0>(R) == std::get<1>(R);
+                    return true;
+                  }))
+        return false;
+    }
   }
   return true;
 }
 
 bool IRSimilarityCandidate::overlap(const IRSimilarityCandidate &A,
                                     const IRSimilarityCandidate &B) {
   auto DoesOverlap = [](const IRSimilarityCandidate &X,
                         const IRSimilarityCandidate &Y) {
     // Check:
     // XXXXXX        X starts before Y ends
     //      YYYYYYY  Y starts after X starts
     return X.StartIdx <= Y.getEndIdx() && Y.StartIdx >= X.StartIdx;
   };
 
   return DoesOverlap(A, B) || DoesOverlap(B, A);
 }
 
 void IRSimilarityIdentifier::populateMapper(
     Module &M, std::vector<IRInstructionData *> &InstrList,
     std::vector<unsigned> &IntegerMapping) {
 
   std::vector<IRInstructionData *> InstrListForModule;
   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())
       continue;
 
     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);
   }
 
   // Insert the InstrListForModule at the end of the overall InstrList so that
   // we can have a long InstrList for the entire set of Modules being analyzed.
   llvm::append_range(InstrList, InstrListForModule);
   // Do the same as above, but for IntegerMapping.
   llvm::append_range(IntegerMapping, IntegerMappingForModule);
 }

 /// \param [out] CandsForRepSubstring - The vector to store the generated
 /// IRSimilarityCandidates.
 static void createCandidatesFromSuffixTree(
     const IRInstructionMapper& Mapper, std::vector<IRInstructionData *> &InstrList,
     std::vector<unsigned> &IntegerMapping, SuffixTree::RepeatedSubstring &RS,
     std::vector<IRSimilarityCandidate> &CandsForRepSubstring) {
 
   unsigned StringLen = RS.Length;
+  if (StringLen < 2)
+    return;
+  
+  if (StringLen == 2) {
+    const unsigned StartIdx = *RS.StartIndices.begin();
+    if (isa<CallInst>(InstrList[StartIdx]->Inst) &&
+        isa<BranchInst>(InstrList[StartIdx + 1]->Inst)) {
+      return;
+    }
+  }
 
   // Create an IRSimilarityCandidate for instance of this subsequence \p RS.
   for (const unsigned &StartIdx : RS.StartIndices) {
     unsigned EndIdx = StartIdx + StringLen - 1;
 
     // Check that this subsequence does not contain an illegal instruction.
     bool ContainsIllegal = false;
     for (unsigned CurrIdx = StartIdx; CurrIdx <= EndIdx; CurrIdx++) {

 }
 
 SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(
     ArrayRef<std::unique_ptr<Module>> Modules) {
   resetSimilarityCandidates();
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> IntegerMapping;
+  Mapper.InstClassifier.EnableBranches = this->EnableBranches;
 
   populateMapper(Modules, InstrList, IntegerMapping);
   findCandidates(InstrList, IntegerMapping);
 
   return SimilarityCandidates.getValue();
 }
 
 SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(Module &M) {
   resetSimilarityCandidates();
+  Mapper.InstClassifier.EnableBranches = this->EnableBranches;
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> IntegerMapping;
 
   populateMapper(M, InstrList, IntegerMapping);
   findCandidates(InstrList, IntegerMapping);
 
   return SimilarityCandidates.getValue();
 }
 
 INITIALIZE_PASS(IRSimilarityIdentifierWrapperPass, "ir-similarity-identifier",
                 "ir-similarity-identifier", false, true)
 
 IRSimilarityIdentifierWrapperPass::IRSimilarityIdentifierWrapperPass()
     : ModulePass(ID) {
   initializeIRSimilarityIdentifierWrapperPassPass(
       *PassRegistry::getPassRegistry());
 }
 
 bool IRSimilarityIdentifierWrapperPass::doInitialization(Module &M) {
-  IRSI.reset(new IRSimilarityIdentifier());
+  IRSI.reset(new IRSimilarityIdentifier(!DoNotEnableBranches));
   return false;
 }
 
 bool IRSimilarityIdentifierWrapperPass::doFinalization(Module &M) {
   IRSI.reset();
   return false;
 }
 
 bool IRSimilarityIdentifierWrapperPass::runOnModule(Module &M) {
   IRSI->findSimilarity(M);
   return false;
 }
 
 AnalysisKey IRSimilarityAnalysis::Key;
 IRSimilarityIdentifier IRSimilarityAnalysis::run(Module &M,
                                                  ModuleAnalysisManager &) {
 
-  auto IRSI = IRSimilarityIdentifier();
+  auto IRSI = IRSimilarityIdentifier(!DoNotEnableBranches);
   IRSI.findSimilarity(M);
   return IRSI;
 }
 
 PreservedAnalyses
 IRSimilarityAnalysisPrinterPass::run(Module &M, ModuleAnalysisManager &AM) {
   IRSimilarityIdentifier &IRSI = AM.getResult<IRSimilarityAnalysis>(M);
   Optional<SimilarityGroupList> &SimilarityCandidatesOpt = IRSI.getSimilarity();

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

void getVectors(Module &M, IRInstructionMapper &Mapper,
   for (Function &F : M)
     for (BasicBlock &BB : F)
       Mapper.convertToUnsignedVec(BB, InstrList, UnsignedVec);
 }
 
 void getSimilarities(
     Module &M,
     std::vector<std::vector<IRSimilarityCandidate>> &SimilarityCandidates) {
-  IRSimilarityIdentifier Identifier;
+  IRSimilarityIdentifier Identifier(false);
   SimilarityCandidates = Identifier.findSimilarity(M);
 }
 
 // Checks that different opcodes are mapped to different values
 TEST(IRInstructionMapper, OpcodeDifferentiation) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
TEST(IRInstructionMapper, StoreDifferentAtomic) {
   IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
   getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
   ASSERT_TRUE(UnsignedVec.size() == 3);
   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:
                              %0 = icmp slt i32 %a, %b
                              br i1 %0, label %bb0, label %bb1
                           bb1:
                              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);
 
   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.
 TEST(IRInstructionMapper, PhiIllegal) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = phi i1 [ 0, %bb0 ], [ %0, %bb1 ]
TEST(IRInstructionMapper, MemSetIllegal) {
   std::vector<unsigned> UnsignedVec;
 
   SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
   SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
   IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
   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.
 TEST(IRInstructionMapper, MemCpyIllegal) {
   StringRef ModuleString = R"(
   declare void @llvm.memcpy.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)
 
   define i64 @function(i64 %x, i64 %z, i64 %n) {
TEST(IRInstructionMapper, MemCpyIllegal) {
   std::vector<unsigned> UnsignedVec;
 
   SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
   SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
   IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
   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));
+  errs() << UnsignedVec[1] << " " << UnsignedVec[2] << " " << UnsignedVec[3] << "\n";
+  ASSERT_TRUE(UnsignedVec[2] > UnsignedVec[3]);
+  ASSERT_TRUE(UnsignedVec[2] < UnsignedVec[0]);
 }
 
 // Checks that a memmove instruction is mapped to an illegal value.
 TEST(IRInstructionMapper, MemMoveIllegal) {
   StringRef ModuleString = R"(
   declare void @llvm.memmove.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)
 
   define i64 @function(i64 %x, i64 %z, i64 %n) {
TEST(IRInstructionMapper, MemMoveIllegal) {
   std::vector<unsigned> UnsignedVec;
 
   SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
   SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
   IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
   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 variable argument instructions are mapped to an illegal value.
 // We exclude variable argument instructions since variable arguments
 // requires extra checking of the argument list.
 TEST(IRInstructionMapper, VarArgsIllegal) {
   StringRef ModuleString = R"(
   declare void @llvm.va_start(i8*)
TEST(IRInstructionMapper, VarArgsIllegal) {
   std::vector<unsigned> UnsignedVec;
 
   SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
   SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
   IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
   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
 // should find that only one element is added for each illegal range.
 TEST(IRInstructionMapper, RepeatedIllegalLength) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
TEST(IRInstructionMapper, RepeatedIllegalLength) {
   // Make sure that the unsigned vector is the expected size.
   ASSERT_TRUE(UnsignedVec.size() == 6);
 }
 
 // A helper function that accepts an instruction list from a module made up of
 // 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);
 }
 
 // Checks that two adds with commuted operands are considered to be the same
 // instructions.
 TEST(IRSimilarityCandidate, CheckIdenticalInstructions) {
TEST(IRSimilarityCandidate, DifferentNameSameStructure) {
   // Check to make sure that we have a long enough region.
   ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));
   // Check that the instructions were added correctly to both vectors.
   ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
 
   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.
 TEST(IRSimilarityIdentifier, IdentitySimilarity) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = add i32 %a, %b