[IRSim] Adding IRSimilarityCandidate that contains a region of IRInstructionData

[AndrewLitteken]

Summary

The IRSimilarityCandidate is a container to hold a region of IRInstructions and offer interfaces for the starting instruction, ending instruction, parent function, length. It also assigns a global value number for each unique instance of a value in the region.

It also contains an interface to compare two IRSimilarity as to whether they have the same sequence of similar instructions.

Tests for whether the instructions are similar are found in unittests/Analysis/IRSimilarityIdentifierTest.cpp.

[AndrewLitteken]

Updating for clang-format

[jroelofs]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

201

I think you can avoid the expensive vector copy by writing this as:

for (Value *Arg : ID->OperVals) {

212

Could do:

ValueToNumber.emplace_back(ID->Inst, LocalValNumber);

237

A and B point at the same thing. Maybe you meant std::get<1>(R) for the latter?

240

isClose(A, B), since there are names for them already?

[paquette]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

245

Can reduce code duplication here using a lambda:

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 >= B.StartIdx
};
return DoesOverlap(A, B) || DoesOverlap(B, A);

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

1426

This sentence is a little hard to parse. Split it into two?

E.g.

Check that debug instructions do not impact similarity. They are marked as invisible.

1439

Can you add an extra basic block in this test which does not contain a debug value?

e.g.

bb3:
  %0 = add i32 %a, %b
  %1 = add i32 %b, %a
  ret i32 0

1463

Can you clarify which instruction is illegal in this comment?

[AndrewLitteken]

Updating utility functions.

[jroelofs]

LGTM

[aeubanks]

I believe this is causing issues in Windows builds, e.g. http://lab.llvm.org:8011/builders/llvm-clang-x86_64-expensive-checks-win/builds/25705 and hangs in http://45.33.8.238/win/summary.html.
I'm seeing a hang locally:
$ ./build/debug/obj/llvm/unittests/Analysis/AnalysisTests.exe --gtest_filter='*IRSimilarityCandidate.IdenticalWithDebug*'
Note: Google Test filter = *IRSimilarityCandidate.IdenticalWithDebug*
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from IRSimilarityCandidate
[ RUN ] IRSimilarityCandidate.IdenticalWithDebug
warning: ignoring debug info with an invalid version (0) in <string>

and then it hangs

[AndrewLitteken]

In D86970#2289145, @aeubanks wrote:

I believe this is causing issues in Windows builds, e.g. http://lab.llvm.org:8011/builders/llvm-clang-x86_64-expensive-checks-win/builds/25705 and hangs in http://45.33.8.238/win/summary.html.
I'm seeing a hang locally:
$ ./build/debug/obj/llvm/unittests/Analysis/AnalysisTests.exe --gtest_filter='*IRSimilarityCandidate.IdenticalWithDebug*'
Note: Google Test filter = *IRSimilarityCandidate.IdenticalWithDebug*
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from IRSimilarityCandidate
[ RUN ] IRSimilarityCandidate.IdenticalWithDebug
warning: ignoring debug info with an invalid version (0) in <string>

and then it hangs

Thanks for letting me know, I just noticed my email is wrong as the author so I didn't get the notification. Reverting the commit.

[aeubanks]

ASan to the rescue:

==2082251==ERROR: AddressSanitizer: heap-use-after-free on address 0x62100022ed08 at pc 0x0000014c1377 bp 0x7fff7aa4a020 sp 0x7fff7aa4a018
READ of size 8 at 0x62100022ed08 thread T0
    #0 0x14c1376 in llvm::ilist_node_base<true>::getNext() const /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/ADT/ilist_node_base.h:43:45
    #1 0x1d9ff47 in llvm::ilist_node_impl<llvm::ilist_detail::node_options<llvm::IRSimilarity::IRInstructionData, true, false, void> >::getNext() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/ADT/ilist_node.h:66:59
    #2 0x1d9fe8c in llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::IRSimilarity::IRInstructionData, true, false, void>, false, false>::operator++() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/ADT/ilist_iterator.h:157:57
    #3 0x1db6254 in std::iterator_traits<llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::IRSimilarity::IRInstructionData, true, false, void>, false, false> >::difference_type std::__distance<llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::IRSimilarity::IRInstructionData, true, false, void>, false, false> >(llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::IRSimilarity::IRInstructionData, true, false, void>, false, false>, llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::IRSimilarity::IRInstructionData, true, false, void>, false, false>, std::input_iterator_tag) /usr/lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_iterator_base_funcs.h:89:4
    #4 0x1d9d543 in std::iterator_traits<llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::IRSimilarity::IRInstructionData, true, false, void>, false, false> >::difference_type std::distance<llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::IRSimilarity::IRInstructionData, true, false, void>, false, false> >(llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::IRSimilarity::IRInstructionData, true, false, void>, false, false>, llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::IRSimilarity::IRInstructionData, true, false, void>, false, false>) /usr/lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_iterator_base_funcs.h:141:14
    #5 0x1d98ba1 in llvm::IRSimilarity::IRSimilarityCandidate::IRSimilarityCandidate(unsigned int, unsigned int, llvm::IRSimilarity::IRInstructionData*, llvm::IRSimilarity::IRInstructionData*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/lib/Analysis/IRSimilarityIdentifier.cpp:176:3
    #6 0x16d05f2 in IRSimilarityCandidate_CheckIdenticalInstructions_Test::TestBody() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp:1228:25
    #7 0x37739d7 in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2402:10
    #8 0x3742810 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2455:12
    #9 0x3713c54 in testing::Test::Run() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2474:5
    #10 0x37154c3 in testing::TestInfo::Run() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2656:11
    #11 0x37163e8 in testing::TestCase::Run() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2774:28
    #12 0x3724166 in testing::internal::UnitTestImpl::RunAllTests() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:4649:43
    #13 0x377c7b7 in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2402:10
    #14 0x3747430 in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2455:12
    #15 0x3723750 in testing::UnitTest::Run() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:4257:10
    #16 0x19f21e0 in RUN_ALL_TESTS() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/include/gtest/gtest.h:2233:46
    #17 0x19f20b1 in main /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/UnitTestMain/TestMain.cpp:50:10
    #18 0x7fe68f49ccc9 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x26cc9)
    #19 0x14022f9 in _start (/usr/local/google/home/aeubanks/repos/llvm-project/build/asan/obj/llvm/unittests/Analysis/AnalysisTests+0x14022f9)

0x62100022ed08 is located 8 bytes inside of 4096-byte region [0x62100022ed00,0x62100022fd00)
freed by thread T0 here:
    #0 0x14add0d in operator delete(void*) /b/s/w/ir/cache/builder/src/third_party/llvm/compiler-rt/lib/asan/asan_new_delete.cpp:160:3
    #1 0x306c2ec in llvm::deallocate_buffer(void*, unsigned long, unsigned long) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/lib/Support/MemAlloc.cpp:24:3
    #2 0x15df8e8 in llvm::MallocAllocator::Deallocate(void const*, unsigned long, unsigned long) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/Support/AllocatorBase.h:92:5
    #3 0x15df4fe in llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul, 128ul>::DeallocateSlabs(void**, void**) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/Support/Allocator.h:352:17
    #4 0x15dd3bc in llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul, 128ul>::~BumpPtrAllocatorImpl() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/Support/Allocator.h:99:5
    #5 0x16dcdd4 in llvm::SpecificBumpPtrAllocator<llvm::IRSimilarity::IRInstructionData>::~SpecificBumpPtrAllocator() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/Support/Allocator.h:388:47
    #6 0x16b13fd in getVectors(llvm::Module&, std::vector<llvm::IRSimilarity::IRInstructionData*, std::allocator<llvm::IRSimilarity::IRInstructionData*> >&, std::vector<unsigned int, std::allocator<unsigned int> >&) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp:42:1
    #7 0x16d006e in IRSimilarityCandidate_CheckIdenticalInstructions_Test::TestBody() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp:1217:3
    #8 0x37739d7 in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2402:10
    #9 0x3742810 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2455:12
    #10 0x3713c54 in testing::Test::Run() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2474:5
    #11 0x37154c3 in testing::TestInfo::Run() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2656:11
    #12 0x37163e8 in testing::TestCase::Run() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2774:28
    #13 0x3724166 in testing::internal::UnitTestImpl::RunAllTests() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:4649:43
    #14 0x377c7b7 in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2402:10
    #15 0x3747430 in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2455:12
    #16 0x3723750 in testing::UnitTest::Run() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:4257:10
    #17 0x19f21e0 in RUN_ALL_TESTS() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/include/gtest/gtest.h:2233:46
    #18 0x19f20b1 in main /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/UnitTestMain/TestMain.cpp:50:10
    #19 0x7fe68f49ccc9 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x26cc9)

previously allocated by thread T0 here:
    #0 0x14ad4ad in operator new(unsigned long) /b/s/w/ir/cache/builder/src/third_party/llvm/compiler-rt/lib/asan/asan_new_delete.cpp:99:3
    #1 0x306c2c8 in llvm::allocate_buffer(unsigned long, unsigned long) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/lib/Support/MemAlloc.cpp:15:10
    #2 0x16e1070 in llvm::MallocAllocator::Allocate(unsigned long, unsigned long) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/Support/AllocatorBase.h:85:12
    #3 0x16e13cc in llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul, 128ul>::StartNewSlab() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/Support/Allocator.h:336:19
    #4 0x16e0bf4 in llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul, 128ul>::Allocate(unsigned long, llvm::Align) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/Support/Allocator.h:188:5
    #5 0x16e029b in llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul, 128ul>::Allocate(unsigned long, unsigned long) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/Support/Allocator.h:202:12
    #6 0x16e00f7 in llvm::AllocatorBase<llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul, 128ul> >::Allocate(unsigned long, unsigned long) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/Support/AllocatorBase.h:46:43
    #7 0x1db4bc5 in llvm::IRSimilarity::IRInstructionData* llvm::AllocatorBase<llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul, 128ul> >::Allocate<llvm::IRSimilarity::IRInstructionData>(unsigned long) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/Support/AllocatorBase.h:69:29
    #8 0x1d9d26f in llvm::SpecificBumpPtrAllocator<llvm::IRSimilarity::IRInstructionData>::Allocate(unsigned long) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/include/llvm/Support/Allocator.h:427:50
    #9 0x1d98445 in llvm::IRSimilarity::IRInstructionMapper::allocateIRInstructionData(llvm::Instruction&, bool, llvm::IRSimilarity::IRInstructionDataList&) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/lib/Analysis/IRSimilarityIdentifier.cpp:125:34
    #10 0x1d97210 in llvm::IRSimilarity::IRInstructionMapper::mapToLegalUnsigned(llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, true, false, void>, false, false>&, std::vector<unsigned int, std::allocator<unsigned int> >&, std::vector<llvm::IRSimilarity::IRInstructionData*, std::allocator<llvm::IRSimilarity::IRInstructionData*> >&) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/lib/Analysis/IRSimilarityIdentifier.cpp:93:27
    #11 0x1d967dc in llvm::IRSimilarity::IRInstructionMapper::convertToUnsignedVec(llvm::BasicBlock&, std::vector<llvm::IRSimilarity::IRInstructionData*, std::allocator<llvm::IRSimilarity::IRInstructionData*> >&, std::vector<unsigned int, std::allocator<unsigned int> >&) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/lib/Analysis/IRSimilarityIdentifier.cpp:54:7
    #12 0x16b138e in getVectors(llvm::Module&, std::vector<llvm::IRSimilarity::IRInstructionData*, std::allocator<llvm::IRSimilarity::IRInstructionData*> >&, std::vector<unsigned int, std::allocator<unsigned int> >&) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp:41:14
    #13 0x16d006e in IRSimilarityCandidate_CheckIdenticalInstructions_Test::TestBody() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp:1217:3
    #14 0x37739d7 in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2402:10
    #15 0x3742810 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2455:12
    #16 0x3713c54 in testing::Test::Run() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2474:5
    #17 0x37154c3 in testing::TestInfo::Run() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2656:11
    #18 0x37163e8 in testing::TestCase::Run() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2774:28
    #19 0x3724166 in testing::internal::UnitTestImpl::RunAllTests() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:4649:43
    #20 0x377c7b7 in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2402:10
    #21 0x3747430 in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:2455:12
    #22 0x3723750 in testing::UnitTest::Run() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/src/gtest.cc:4257:10
    #23 0x19f21e0 in RUN_ALL_TESTS() /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/googletest/include/gtest/gtest.h:2233:46
    #24 0x19f20b1 in main /usr/local/google/home/aeubanks/repos/llvm-project/build/asan/../../llvm/utils/unittest/UnitTestMain/TestMain.cpp:50:10
    #25 0x7fe68f49ccc9 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x26cc9)

[AndrewLitteken]

Updating diff to fix memory issues.

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

 // slightly different.
 //
 // For instructions, we do not worry about operands that do not have fixed
 // semantic meaning to the program.  We consider the opcode that the instruction
 // has, the types, parameters, and extra information such as the function name,
 // or comparison predicate.  These are used to create a hash to map instructions
 // to integers to be used in similarity matching in sequences of instructions
 //
+// Terminology:
+// An IRSimilarityCandidate is a region of IRInstructionData (wrapped
+// Instructions), usually used to denote a region of similarity has been found.
+//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H
 #define LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H
 
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
struct InstructionClassification
     InstrType visitTerminator(Instruction &I) { return Illegal; }
     InstrType visitInstruction(Instruction &I) { return Legal; }
   };
 
   /// 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
+/// program.  It is also responsible for defining the structure within this
+/// region of instructions.
+///
+/// The structure of a region is defined through a value numbering system
+/// assigned to each unique value in a region at the creation of the
+/// IRSimilarityCandidate.
+///
+/// For example, for each Instruction we add a mapping for each new
+/// value seen in that Instruction.
+/// IR:                    Mapping Added:
+/// %add1 = add i32 %a, c1    %add1 -> 3, %a -> 1, c1 -> 2
+/// %add2 = add i32 %a, %1    %add2 -> 4
+/// %add3 = add i32 c2, c1    %add3 -> 6, c2 -> 5
+///
+/// We can compare IRSimilarityCandidates against one another.
+/// The \ref isSimilar function compares each IRInstructionData against one
+/// another and if we have the same sequences of IRInstructionData that would
+/// create the same hash, we have similar IRSimilarityCandidates.
+class IRSimilarityCandidate {
+private:
+  /// The start index of this IRSimilarityCandidate in the instruction list.
+  unsigned StartIdx = 0;
+
+  /// The number of instructions in this IRSimilarityCandidate.
+  unsigned Len = 0;
+
+  /// The first instruction in this IRSimilarityCandidate.
+  IRInstructionData *FirstInst = nullptr;
+
+  /// The last instruction in this IRSimilarityCandidate.
+  IRInstructionData *LastInst = nullptr;
+
+  /// Global Value Numbering structures
+  /// @{
+  /// Stores the mapping of the value to the number assigned to it in the
+  /// IRSimilarityCandidate.
+  DenseMap<Value *, unsigned> ValueToNumber;
+  /// Stores the mapping of the number to the value assigned this number.
+  DenseMap<unsigned, Value *> NumberToValue;
+  /// @}
+
+public:
+  /// \param StartIdx - The starting location of the region.
+  /// \param StartIdx - The length of the region.
+  /// \param FirstInstIt - The starting IRInstructionData of the region.
+  /// \param LastInstIt - The ending IRInstructionData of the region.
+  IRSimilarityCandidate(unsigned StartIdx, unsigned Len,
+                        IRInstructionData *FirstInstIt,
+                        IRInstructionData *LastInstIt);
+
+  /// \param A - The first IRInstructionCandidate to compare.
+  /// \param B - The second IRInstructionCandidate to compare.
+  /// \returns True when every IRInstructionData in \p A is similar to every
+  /// IRInstructionData in \p B.
+  static bool isSimilar(const IRSimilarityCandidate &A,
+                        const IRSimilarityCandidate &B);
+  /// 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.
+  static bool overlap(const IRSimilarityCandidate &A,
+                      const IRSimilarityCandidate &B);
+
+  /// \returns the number of instructions in this Candidate.
+  unsigned getLength() const { return Len; }
+
+  /// \returns the start index of this IRSimilarityCandidate.
+  unsigned getStartIdx() const { return StartIdx; }
+
+  /// \returns the end index of this IRSimilarityCandidate.
+  unsigned getEndIdx() const { return StartIdx + Len - 1; }
+
+  /// \returns The first IRInstructionData.
+  IRInstructionData *front() const { return FirstInst; }
+  /// \returns The last IRInstructionData.
+  IRInstructionData *back() const { return LastInst; }
+
+  /// \returns The first Instruction.
+  Instruction *frontInstruction() { return FirstInst->Inst; }
+  /// \returns The last Instruction
+  Instruction *backInstruction() { return LastInst->Inst; }
+
+  /// \returns The BasicBlock the IRSimilarityCandidate starts in.
+  BasicBlock *getStartBB() { return FirstInst->Inst->getParent(); }
+  /// \returns The BasicBlock the IRSimilarityCandidate ends in.
+  BasicBlock *getEndBB() { return LastInst->Inst->getParent(); }
+
+  /// \returns The Function that the IRSimilarityCandidate is located in.
+  Function *getFunction() { return getStartBB()->getParent(); }
+
+  /// Finds the positive number associated with \p V if it has been mapped.
+  /// \param [in] V - the Value to find.
+  /// \returns The positive number corresponding to the value.
+  /// \returns None if not present.
+  Optional<unsigned> getGVN(Value *V) {
+    assert(V != nullptr && "Value is a nullptr?");
+    DenseMap<Value *, unsigned>::iterator VNIt = ValueToNumber.find(V);
+    if (VNIt == ValueToNumber.end())
+      return None;
+    return VNIt->second;
+  }
+
+  /// Finds the Value associate with \p Num if it exists.
+  /// \param [in] Num - the number to find.
+  /// \returns The Value associated with the number.
+  /// \returns None if not present.
+  Optional<Value *> fromGVN(unsigned Num) {
+    DenseMap<unsigned, Value *>::iterator VNIt = NumberToValue.find(Num);
+    if (VNIt == NumberToValue.end())
+      return None;
+    assert(VNIt->second != nullptr && "Found value is a nullptr!");
+    return VNIt->second;
+  }
+
+  /// \param RHS -The IRSimilarityCandidate to compare against
+  /// \returns true if the IRSimilarityCandidate is occurs after the
+  /// IRSimilarityCandidate in the program.
+  bool operator<(const IRSimilarityCandidate &RHS) const {
+    return getStartIdx() > RHS.getStartIdx();
+  }
+
+  using iterator = IRInstructionDataList::iterator;
+  iterator begin() const { return iterator(front()); }
+  iterator end() const { return std::next(iterator(back())); }
+};
 } // end namespace IRSimilarity
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

unsigned IRInstructionMapper::mapToIllegalUnsigned(
   assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
          "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
 
   assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
          "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
 
   return INumber;
 }
+
+IRSimilarityCandidate::IRSimilarityCandidate(unsigned StartIdx, unsigned Len,
+                                             IRInstructionData *FirstInstIt,
+                                             IRInstructionData *LastInstIt)
+    : StartIdx(StartIdx), Len(Len) {
+
+  assert(FirstInstIt != nullptr && "Instruction is nullptr!");
+  assert(LastInstIt != nullptr && "Instruction is nullptr!");
+  assert(StartIdx + Len > StartIdx &&
+         "Overflow for IRSimilarityCandidate range?");
+  assert(Len - 1 ==
+             std::distance(iterator(FirstInstIt), iterator(LastInstIt)) &&
+         "Length of the first and last IRInstructionData do not match the "
+         "given length");
+
+  // We iterate over the given instructions, and map each unique value
+  // to a unique number in the IRSimilarityCandidate ValueToNumber and
+  // NumberToValue maps.  A constant get its own value globally, the individual
+  // uses of the constants are not considered to be unique.
+  //
+  // IR:                    Mapping Added:
+  // %add1 = add i32 %a, c1    %add1 -> 3, %a -> 1, c1 -> 2
+  // %add2 = add i32 %a, %1    %add2 -> 4
+  // %add3 = add i32 c2, c1    %add3 -> 6, c2 -> 5
+  //
+  // when replace with global values, starting from 1, would be
+  //
+  // 3 = add i32 1, 2
+  // 4 = add i32 1, 3
+  // 6 = add i32 5, 2
+  unsigned LocalValNumber = 1;
+  IRInstructionDataList::iterator ID = iterator(*FirstInstIt);
+  for (unsigned Loc = StartIdx; Loc < StartIdx + Len; Loc++, ID++) {
+    // Map the operand values to an unsigned integer if it does not already
+    // have an unsigned integer assigned to it.
+    for (Value *Arg : ID->OperVals)
+      if (ValueToNumber.find(Arg) == ValueToNumber.end()) {
+        ValueToNumber.try_emplace(Arg, LocalValNumber);
+        NumberToValue.try_emplace(LocalValNumber, Arg);
+        LocalValNumber++;
+      }
+
+    // Mapping the instructions to an unsigned integer if it is not already
+    // exist in the mapping.
+    if (ValueToNumber.find(ID->Inst) == ValueToNumber.end()) {
+      ValueToNumber.try_emplace(ID->Inst, LocalValNumber);
+      NumberToValue.try_emplace(LocalValNumber, ID->Inst);
+      LocalValNumber++;
+    }
+  }
+
+  // Setting the first and last instruction data pointers for the candidate.  If
+  // we got through the entire for loop without hitting an assert, we know
+  // that both of these instructions are not nullptrs.
+  FirstInst = FirstInstIt;
+  LastInst = LastInstIt;
+}
+
+bool IRSimilarityCandidate::isSimilar(const IRSimilarityCandidate &A,
+                                      const IRSimilarityCandidate &B) {
+  if (A.getLength() != B.getLength())
+    return false;
+
+  auto InstrDataForBoth =
+      zip(make_range(A.begin(), A.end()), make_range(B.begin(), B.end()));
+
+  return all_of(InstrDataForBoth,
+                [](std::tuple<IRInstructionData &, IRInstructionData &> R) {
+                  IRInstructionData &A = std::get<0>(R);
+                  IRInstructionData &B = std::get<1>(R);
+                  if (!A.Legal || !B.Legal)
+                    return false;
+                  return isClose(A, B);
+                });
+}
+
+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);
+}

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

 //===- IRSimilarityIdentifierTest.cpp - IRSimilarityIdentifier unit tests -===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Tests for components for finding similarity such as the instruction mapper,
 // suffix tree usage, and structural analysis.
 //
 //===----------------------------------------------------------------------===//
 
+#include "gtest/gtest.h"
 #include "llvm/Analysis/IRSimilarityIdentifier.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/SourceMgr.h"
-#include "gtest/gtest.h"
 
 using namespace llvm;
 using namespace IRSimilarity;
 
 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
                                               StringRef ModuleStr) {
   SMDiagnostic Err;
   std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
   assert(M && "Bad LLVM IR?");
   return M;
 }
 
-void getVectors(Module &M, std::vector<IRInstructionData *> &InstrList,
+void getVectors(Module &M, IRInstructionMapper &Mapper,
+                std::vector<IRInstructionData *> &InstrList,
                 std::vector<unsigned> &UnsignedVec) {
-  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
-  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
-  IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
-
   for (Function &F : M)
     for (BasicBlock &BB : F)
       Mapper.convertToUnsignedVec(BB, InstrList, UnsignedVec);
 }
 
 // Checks that different opcodes are mapped to different values.
 TEST(IRInstructionMapper, OpcodeDifferentiation) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = add i32 %a, %b
                              %1 = mul i32 %a, %b
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
+  getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   // Check that the size of the unsigned vector and the instruction list are the
   // same as a safety check.
   ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
 
   // Make sure that the unsigned vector is the expected size.
   ASSERT_TRUE(UnsignedVec.size() == 3);
 
StringRef ModuleString = R"(
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
+  getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
   ASSERT_TRUE(UnsignedVec.size() == 3);
 
   // Check whether the instructions are mapped to the same value.
   ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
 }
 
 // Checks that the same opcode and different types are mapped to different
 // values.
 TEST(IRInstructionMapper, TypeDifferentiation) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b, i64 %c, i64 %d) {
                           bb0:
                              %0 = add i32 %a, %b
                              %1 = add i64 %c, %d
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that different predicates map to different values.
 TEST(IRInstructionMapper, PredicateDifferentiation) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = icmp sge i32 %b, %a
                              %1 = icmp slt i32 %a, %b
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that predicates with the same swapped predicate map to different
 // values.
 TEST(IRInstructionMapper, PredicateIsomorphism) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = icmp sgt i32 %a, %b
                              %1 = icmp slt i32 %b, %a
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that the same predicate maps to the same value.
 TEST(IRInstructionMapper, PredicateSimilarity) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = icmp slt i32 %a, %b
                              %1 = icmp slt i32 %b, %a
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that the same predicate maps to the same value for floating point
 // CmpInsts.
 TEST(IRInstructionMapper, FPPredicateSimilarity) {
   StringRef ModuleString = R"(
                           define i32 @f(double %a, double %b) {
                           bb0:
                              %0 = fcmp olt double %a, %b
                              %1 = fcmp olt double %b, %a
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that the different predicate maps to a different value for floating
 // point CmpInsts.
 TEST(IRInstructionMapper, FPPredicatDifference) {
   StringRef ModuleString = R"(
                           define i32 @f(double %a, double %b) {
                           bb0:
                              %0 = fcmp olt double %a, %b
                              %1 = fcmp oge double %b, %a
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that the zexts that have the same type parameters map to the same
 // unsigned integer.
 TEST(IRInstructionMapper, ZextTypeSimilarity) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a) {
                           bb0:
                              %0 = zext i32  %a to i64
                              %1 = zext i32  %a to i64
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that the sexts that have the same type parameters map to the same
 // unsigned integer.
 TEST(IRInstructionMapper, SextTypeSimilarity) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a) {
                           bb0:
                              %0 = sext i32  %a to i64
                              %1 = sext i32  %a to i64
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that the zexts that have the different type parameters map to the
 // different unsigned integers.
 TEST(IRInstructionMapper, ZextTypeDifference) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i8 %b) {
                           bb0:
                              %0 = zext i32 %a to i64
                              %1 = zext i8 %b to i32
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that the sexts that have the different type parameters map to the
 // different unsigned integers.
 TEST(IRInstructionMapper, SextTypeDifference) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i8 %b) {
                           bb0:
                              %0 = sext i32 %a to i64
                              %1 = sext i8 %b to i32
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that loads that have the same type are mapped to the same unsigned
 // integer.
 TEST(IRInstructionMapper, LoadSimilarType) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i32* %b) {
                           bb0:
                              %0 = load i32, i32* %a
                              %1 = load i32, i32* %b
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that loads that have the different types are mapped to
 // different unsigned integers.
 TEST(IRInstructionMapper, LoadDifferentType) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i64* %b) {
                           bb0:
                              %0 = load i32, i32* %a
                              %1 = load i64, i64* %b
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that loads that have the different aligns are mapped to different
 // unsigned integers.
 TEST(IRInstructionMapper, LoadDifferentAlign) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i32* %b) {
                           bb0:
                              %0 = load i32, i32* %a, align 4
                              %1 = load i32, i32* %b, align 8
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that loads that have the different volatile settings are mapped to
 // different unsigned integers.
 TEST(IRInstructionMapper, LoadDifferentVolatile) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i32* %b) {
                           bb0:
                              %0 = load volatile i32, i32* %a
                              %1 = load i32, i32* %b
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that loads that have the same volatile settings are mapped to
 // different unsigned integers.
 TEST(IRInstructionMapper, LoadSameVolatile) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i32* %b) {
                           bb0:
                              %0 = load volatile i32, i32* %a
                              %1 = load volatile i32, i32* %b
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that loads that have the different atomicity settings are mapped to
 // different unsigned integers.
 TEST(IRInstructionMapper, LoadDifferentAtomic) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i32* %b) {
                           bb0:
                              %0 = load atomic i32, i32* %a unordered, align 4
                              %1 = load atomic i32, i32* %b monotonic, align 4
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that loads that have the same atomicity settings are mapped to
 // different unsigned integers.
 TEST(IRInstructionMapper, LoadSameAtomic) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i32* %b) {
                           bb0:
                              %0 = load atomic i32, i32* %a unordered, align 4
                              %1 = load atomic i32, i32* %b unordered, align 4
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that stores that have the same type are mapped to the same unsigned
 // integer.
 TEST(IRInstructionMapper, StoreSimilarType) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i32* %b) {
                           bb0:
                              store i32 1, i32* %a
                              store i32 2, i32* %a
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that stores that have the different types are mapped to
 // different unsigned integers.
 TEST(IRInstructionMapper, StoreDifferentType) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i64* %b) {
                           bb0:
                              store i32 1, i32* %a
                              store i64 1, i64* %b
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that stores that have the different aligns are mapped to different
 // unsigned integers.
 TEST(IRInstructionMapper, StoreDifferentAlign) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i32* %b) {
                           bb0:
                              store i32 1, i32* %a, align 4
                              store i32 1, i32* %b, align 8
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that stores that have the different volatile settings are mapped to
 // different unsigned integers.
 TEST(IRInstructionMapper, StoreDifferentVolatile) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i32* %b) {
                           bb0:
                              store volatile i32 1, i32* %a
                              store i32 1, i32* %b
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that stores that have the same volatile settings are mapped to
 // different unsigned integers.
 TEST(IRInstructionMapper, StoreSameVolatile) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i32* %b) {
                           bb0:
                              store volatile i32 1, i32* %a
                              store volatile i32 1, i32* %b
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that loads that have the same atomicity settings are mapped to
 // different unsigned integers.
 TEST(IRInstructionMapper, StoreSameAtomic) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i32* %b) {
                           bb0:
                              store atomic i32 1, i32* %a unordered, align 4
                              store atomic i32 1, i32* %b unordered, align 4
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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]);
 }
 
 // Checks that loads that have the different atomicity settings are mapped to
 // different unsigned integers.
 TEST(IRInstructionMapper, StoreDifferentAtomic) {
   StringRef ModuleString = R"(
                           define i32 @f(i32* %a, i32* %b) {
                           bb0:
                              store atomic i32 1, i32* %a unordered, align 4
                              store atomic i32 1, i32* %b monotonic, align 4
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  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,
StringRef ModuleString = R"(
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // 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 ]
                              ret i32 0
                           bb1:
                              ret i32 1
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // Checks that an alloca instruction is mapped to be illegal.
 TEST(IRInstructionMapper, AllocaIllegal) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = alloca i32
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // Checks that an getelementptr instruction is mapped to be illegal.  There is
 // extra checking required for the parameters if a getelementptr has more than
 // two operands.
 TEST(IRInstructionMapper, GetElementPtrIllegal) {
   StringRef ModuleString = R"(
     %struct.RT = type { i8, [10 x [20 x i32]], i8 }
     %struct.ST = type { i32, double, %struct.RT }
     define i32 @f(%struct.ST* %s, i32 %a, i32 %b) {
     bb0:
        %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 1
        ret i32 0
     })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // Checks that a call instruction is mapped to be illegal.  We have to perform
 // extra checks to ensure that both the name and function type are the same.
 TEST(IRInstructionMapper, CallIllegal) {
   StringRef ModuleString = R"(
                           declare i32 @f1(i32, i32)
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = call i32 @f1(i32 %a, i32 %b)
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // Checks that an invoke instruction is mapped to be illegal. Invoke
 // instructions are considered to be illegal because of the change in the
 // control flow that is currently not recognized.
StringRef ModuleString = R"(
                             unreachable
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // Checks that an callbr instructions are considered to be illegal.  Callbr
 // instructions are considered to be illegal because of the change in the
 // control flow that is currently not recognized.
define i32 @f(i32 %a, i32 %b) {
         ret i32 0
   })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // Checks that an debuginfo intrinsics are mapped to be invisible.  Since they
 // do not semantically change the program, they can be recognized as similar.
 TEST(IRInstructionMapper, DebugInfoInvisible) {
StringRef ModuleString = R"(
                           declare void @llvm.dbg.value(metadata)
                           !0 = distinct !{!"test\00", i32 10})";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(3));
 }
 
 // The following are all exception handling intrinsics.  We do not currently
 // handle these instruction because they are very context dependent.
 
StringRef ModuleString = R"(
 
     declare i32 @llvm.eh.typeid.for(i8*))";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // Checks that an eh.exceptioncode intrinsic is mapped to be illegal.
 TEST(IRInstructionMapper, ExceptionHandlingExceptionCodeIllegal) {
   StringRef ModuleString = R"(
StringRef ModuleString = R"(
 
     declare i32 @llvm.eh.exceptioncode(token))";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // Checks that an eh.unwind intrinsic is mapped to be illegal.
 TEST(IRInstructionMapper, ExceptionHandlingUnwindIllegal) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           entry:
                             call void @llvm.eh.unwind.init()
                             ret i32 0
                           }
 
                           declare void @llvm.eh.unwind.init())";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // Checks that an eh.exceptionpointer intrinsic is mapped to be illegal.
 TEST(IRInstructionMapper, ExceptionHandlingExceptionPointerIllegal) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           entry:
                             %0 = call i8* @llvm.eh.exceptionpointer.p0i8(i32 0)
                             ret i32 0
                           }
 
                           declare i8* @llvm.eh.exceptionpointer.p0i8(i32))";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // Checks that a catchpad instruction is mapped to an illegal value.
 TEST(IRInstructionMapper, CatchpadIllegal) {
   StringRef ModuleString = R"(
define void @function() personality i8 3 {
         ret void
   })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // Checks that a cleanuppad instruction is mapped to an illegal value.
 TEST(IRInstructionMapper, CleanuppadIllegal) {
   StringRef ModuleString = R"(
define void @function() personality i8 3 {
         ret void
   })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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>(0));
 }
 
 // The following three instructions are memory transfer and setting based, which
 // are considered illegal since is extra checking needed to handle the address
 // space checking.
entry:
     ret i64 0
   })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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]);
 }
 
 // Checks that a memcpy instruction is mapped to an illegal value.
 TEST(IRInstructionMapper, MemCpyIllegal) {
entry:
     ret i64 0
   })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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]);
 }
 
 // Checks that a memmove instruction is mapped to an illegal value.
 TEST(IRInstructionMapper, MemMoveIllegal) {
entry:
     ret i64 0
   })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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]);
 }
 
 // Checks that a variable argument instructions are mapped to an illegal value.
 // We exclude variable argument instructions since variable arguments
entry:
     ret i32 %tmp
   })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, 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]);
 }
StringRef ModuleString = R"(
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
-  getVectors(*M, InstrList, UnsignedVec);
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
+  getVectors(*M, Mapper, InstrList, UnsignedVec);
 
   // Check that the size of the unsigned vector and the instruction list are the
   // same as a safety check.
   ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
 
   // 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) {
+  std::vector<IRInstructionData *>::iterator Start, End;
+
+  Start = InstrList.begin();
+  End = InstrList.begin();
+
+  std::advance(End, 1);
+  IRSimilarityCandidate Cand1(0, 2, *Start, *End);
+
+  Start = InstrList.begin();
+  End = InstrList.begin();
+
+  std::advance(Start, 3);
+  std::advance(End, 4);
+  IRSimilarityCandidate Cand2(3, 2, *Start, *End);
+  return IRSimilarityCandidate::isSimilar(Cand1, Cand2);
+}
+
+// Checks that two adds with commuted operands are considered to be the same
+// instructions.
+TEST(IRSimilarityCandidate, CheckIdenticalInstructions) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = add i32 %b, %a
+                             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);
+  getVectors(*M, Mapper, InstrList, UnsignedVec);
+
+  // Check to make sure that we have a long enough region.
+  ASSERT_EQ(InstrList.size(), static_cast<unsigned>(3));
+  // Check that the instructions were added correctly to both vectors.
+  ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
+
+  std::vector<IRInstructionData *>::iterator Start, End;
+  Start = InstrList.begin();
+  End = InstrList.begin();
+  std::advance(End, 1);
+  IRSimilarityCandidate Cand1(0, 2, *Start, *End);
+  IRSimilarityCandidate Cand2(0, 2, *Start, *End);
+
+  ASSERT_TRUE(IRSimilarityCandidate::isSimilar(Cand1, Cand2));
+}
+
+// Checks that IRSimilarityCandidates wrapping these two regions of instructions
+// are able to differentiate between instructions that have different opcodes.
+TEST(IRSimilarityCandidate, CheckRegionsDifferentInstruction) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = add i32 %b, %a
+                             ret i32 0
+                          bb1:
+                             %2 = sub i32 %a, %b
+                             %3 = add i32 %b, %a
+                             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);
+  getVectors(*M, Mapper, InstrList, UnsignedVec);
+
+  // 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_FALSE(longSimCandCompare(InstrList));
+}
+
+// Checks that IRSimilarityCandidates wrapping these two regions of instructions
+// are able to differentiate between instructions that have different types.
+TEST(IRSimilarityCandidate, CheckRegionsDifferentTypes) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b, i64 %c, i64 %d) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = add i32 %b, %a
+                             ret i32 0
+                          bb1:
+                             %2 = add i64 %c, %d
+                             %3 = add i64 %d, %c
+                             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);
+  getVectors(*M, Mapper, InstrList, UnsignedVec);
+
+  // 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_FALSE(longSimCandCompare(InstrList));
+}
+
+// Check that debug instructions do not impact similarity. They are marked as
+// invisible.
+TEST(IRSimilarityCandidate, IdenticalWithDebug) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             call void @llvm.dbg.value(metadata !0)
+                             %1 = add i32 %b, %a
+                             ret i32 0
+                          bb1:
+                             %2 = add i32 %a, %b
+                             call void @llvm.dbg.value(metadata !1)
+                             %3 = add i32 %b, %a
+                             ret i32 0
+                          bb2:
+                             %4 = add i32 %a, %b
+                             %5 = add i32 %b, %a
+                             ret i32 0       
+                          }
+
+                          declare void @llvm.dbg.value(metadata)
+                          !0 = distinct !{!"test\00", i32 10}
+                          !1 = distinct !{!"test\00", i32 11})";
+  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);
+  getVectors(*M, Mapper, InstrList, UnsignedVec);
+
+  // Check to make sure that we have a long enough region.
+  ASSERT_EQ(InstrList.size(), static_cast<unsigned>(9));
+  // Check that the instructions were added correctly to both vectors.
+  ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
+
+  ASSERT_TRUE(longSimCandCompare(InstrList));
+}
+
+// Checks that IRSimilarityCandidates that include illegal instructions, are not
+// considered to be the same set of instructions.  In these sets of instructions
+// the allocas are illegal.
+TEST(IRSimilarityCandidate, IllegalInCandidate) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = add i32 %a, %b
+                             %2 = alloca i32
+                             ret i32 0
+                          bb1:
+                             %3 = add i32 %a, %b
+                             %4 = add i32 %a, %b
+                             %5 = alloca i32
+                             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);
+  getVectors(*M, Mapper, InstrList, UnsignedVec);
+
+  // 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());
+
+  std::vector<IRInstructionData *>::iterator Start, End;
+
+  Start = InstrList.begin();
+  End = InstrList.begin();
+
+  std::advance(End, 2);
+  IRSimilarityCandidate Cand1(0, 3, *Start, *End);
+
+  Start = InstrList.begin();
+  End = InstrList.begin();
+
+  std::advance(Start, 3);
+  std::advance(End, 5);
+  IRSimilarityCandidate Cand2(3, 3, *Start, *End);
+  ASSERT_FALSE(IRSimilarityCandidate::isSimilar(Cand1, Cand2));
+}