This is an archive of the discontinued LLVM Phabricator instance.

[IRSim] Adding IRSimilarityCandidate that contains a region of IRInstructionData
ClosedPublic

Authored by AndrewLitteken on Sep 1 2020, 1:14 PM.

Details

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.

Diff Detail

Event Timeline

AndrewLitteken created this revision.Sep 1 2020, 1:14 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 1 2020, 1:14 PM
AndrewLitteken added a reviewer: paquette.

Updating for clang-format

jroelofs added inline comments.
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 added inline comments.Sep 15 2020, 9:44 AM
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?

Updating utility functions.

This revision is now accepted and ready to land.Sep 16 2020, 8:19 AM

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

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.

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)

Updating diff to fix memory issues.