Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

valgrind finds error in DSE using AliasAnalysis #1284

Closed
nlewycky opened this issue Sep 14, 2006 · 8 comments
Closed

valgrind finds error in DSE using AliasAnalysis #1284

nlewycky opened this issue Sep 14, 2006 · 8 comments
Labels
bugzilla Issues migrated from bugzilla

Comments

@nlewycky
Copy link
Contributor

Bugzilla Link 912
Resolution FIXED
Resolved on Feb 22, 2010 12:56
Version trunk
OS Linux
Attachments simplified testcase

Extended Description

The DSE seems to have some sort of hard to trigger memory error, caught by valgrind:

$ valgrind opt bugpoint-reduced-simplified.bc -dse
==13389== Memcheck, a memory error detector.
==13389== Copyright (C) 2002-2006, and GNU GPL'd, by Julian Seward et al.
==13389== Using LibVEX rev 1606, a library for dynamic binary translation.
==13389== Copyright (C) 2004-2006, and GNU GPL'd, by OpenWorks LLP.
==13389== Using valgrind-3.2.0-Debian, a dynamic binary instrumentation framework.
==13389== Copyright (C) 2000-2006, and GNU GPL'd, by Julian Seward et al.
==13389== For more details, rerun with: -v
==13389==
WARNING: You're attempting to print out a bytecode file.
This is inadvisable as it may cause display problems. If
you REALLY want to taste LLVM bytecode first-hand, you
can force output with the `-f' option.

==13389== Invalid read of size 4
==13389== at 0x8440A8F: std::equal_tollvm::Value*::operator()(llvm::Value*
const&, llvm::Value* const&) const (stl_function.h:200)
==13389== by 0x85E9319: __gnu_cxx::hashtable<std::pair<llvm::Value* const,
llvm::AliasSet::PointerRec>, llvm::Value*, __gnu_cxx::hashllvm::Value*,
std::_Select1st<std::pair<llvm::Value* const, llvm::AliasSet::PointerRec> >,
std::equal_tollvm::Value*, std::allocatorllvm::AliasSet::PointerRec

::erase(llvm::Value* const&) (hashtable.h:895)
==13389== by 0x85E937D: __gnu_cxx::hash_map<llvm::Value*,
llvm::AliasSet::PointerRec, __gnu_cxx::hashllvm::Value*,
std::equal_tollvm::Value*, std::allocatorllvm::AliasSet::PointerRec
::erase(llvm::Value* const&) (hash_map:249)
==13389== by 0x85E6A7E: llvm::AliasSetTracker::remove(llvm::AliasSet&)
(AliasSetTracker.cpp:377)
==13389== by 0x85E804A: llvm::AliasSetTracker::remove(llvm::LoadInst*)
(AliasSetTracker.cpp:397)
==13389== by 0x85E8087: llvm::AliasSetTracker::remove(llvm::Instruction*)
(AliasSetTracker.cpp:430)
==13389== by 0x850CA62: (anonymous
namespace)::DSE::runOnBasicBlock(llvm::BasicBlock&) (DeadStoreElimination.cpp:108)
==13389== by 0x850D408: (anonymous
namespace)::DSE::runOnFunction(llvm::Function&) (DeadStoreElimination.cpp:39)
==13389== by 0x86B9796:
llvm::FunctionPassManagerT::runPass(llvm::FunctionPass*, llvm::Function*)
(PassManagerT.h:804)
==13389== by 0x86CEF5F:
llvm::PassManagerTllvm::FTraits::runPasses(llvm::Function*,
std::map<llvm::Pass*, std::vector<llvm::Pass*, std::allocatorllvm::Pass* >,
std::lessllvm::Pass*, std::allocator<std::pair<llvm::Pass* const,
std::vector<llvm::Pass*, std::allocatorllvm::Pass* > > > >&) (PassManagerT.h:596)
==13389== by 0x86CF96F:
llvm::PassManagerTllvm::FTraits::runOnUnit(llvm::Function*) (PassManagerT.h:282)
==13389== by 0x86B9878:
llvm::FunctionPassManagerT::runOnFunction(llvm::Function&) (PassManagerT.h:896)
==13389== Address 0x73470FC is 4 bytes inside a block of size 24 free'd
==13389== at 0x53FC422: operator delete(void*) (vg_replace_malloc.c:244)
==13389== by 0x8417ABE:
__gnu_cxx::new_allocator<__gnu_cxx::_Hashtable_node<std::pair<llvm::Value*
const, llvm::AliasSet::PointerRec> >
::deallocate(__gnu_cxx::_Hashtable_node<std::pair<llvm::Value* const,
llvm::AliasSet::PointerRec> >, unsigned) (new_allocator.h:94)
==13389== by 0x8417AE3: __gnu_cxx::hashtable<std::pair<llvm::Value
const,
llvm::AliasSet::PointerRec>, llvm::Value*, __gnu_cxx::hashllvm::Value*,
std::_Select1st<std::pair<llvm::Value* const, llvm::AliasSet::PointerRec> >,
std::equal_tollvm::Value*, std::allocatorllvm::AliasSet::PointerRec
::_M_put_node(__gnu_cxx::_Hashtable_node<std::pair<llvm::Value* const,
llvm::AliasSet::PointerRec> >) (hashtable.h:301)
==13389== by 0x8417B33: __gnu_cxx::hashtable<std::pair<llvm::Value
const,
llvm::AliasSet::PointerRec>, llvm::Value*, __gnu_cxx::hashllvm::Value*,
std::_Select1st<std::pair<llvm::Value* const, llvm::AliasSet::PointerRec> >,
std::equal_tollvm::Value*, std::allocatorllvm::AliasSet::PointerRec
::_M_delete_node(__gnu_cxx::_Hashtable_node<std::pair<llvm::Value* const,
llvm::AliasSet::PointerRec> >) (hashtable.h:623)
==13389== by 0x85E92B2: __gnu_cxx::hashtable<std::pair<llvm::Value
const,
llvm::AliasSet::PointerRec>, llvm::Value*, __gnu_cxx::hashllvm::Value*,
std::_Select1st<std::pair<llvm::Value* const, llvm::AliasSet::PointerRec> >,
std::equal_tollvm::Value*, std::allocatorllvm::AliasSet::PointerRec
::erase(llvm::Value* const&) (hashtable.h:884)
==13389== by 0x85E937D: __gnu_cxx::hash_map<llvm::Value*,
llvm::AliasSet::PointerRec, __gnu_cxx::hashllvm::Value*,
std::equal_tollvm::Value*, std::allocatorllvm::AliasSet::PointerRec
::erase(llvm::Value* const&) (hash_map:249)
==13389== by 0x85E6A7E: llvm::AliasSetTracker::remove(llvm::AliasSet&)
(AliasSetTracker.cpp:377)
==13389== by 0x85E804A: llvm::AliasSetTracker::remove(llvm::LoadInst*)
(AliasSetTracker.cpp:397)
==13389== by 0x85E8087: llvm::AliasSetTracker::remove(llvm::Instruction*)
(AliasSetTracker.cpp:430)
==13389== by 0x850CA62: (anonymous
namespace)::DSE::runOnBasicBlock(llvm::BasicBlock&) (DeadStoreElimination.cpp:108)
==13389== by 0x850D408: (anonymous
namespace)::DSE::runOnFunction(llvm::Function&) (DeadStoreElimination.cpp:39)
==13389== by 0x86B9796:
llvm::FunctionPassManagerT::runPass(llvm::FunctionPass*, llvm::Function*)
(PassManagerT.h:804)
==13389==
==13389== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 27 from 1)
==13389== malloc/free: in use at exit: 99,867 bytes in 1,003 blocks.
==13389== malloc/free: 18,318 allocs, 17,315 frees, 614,957 bytes allocated.
==13389== For counts of detected errors, rerun with: -v
==13389== searching for pointers to 1,003 not-freed blocks.
==13389== checked 415,884 bytes.
==13389==
==13389== LEAK SUMMARY:
==13389== definitely lost: 99,608 bytes in 995 blocks.
==13389== possibly lost: 43 bytes in 1 blocks.
==13389== still reachable: 216 bytes in 7 blocks.
==13389== suppressed: 0 bytes in 0 blocks.
==13389== Use --leak-check=full to see details of leaked memory.

@lattner
Copy link
Collaborator

lattner commented Sep 16, 2006

I've been trying to figure this out, but I don't have valgrind, and don't really have much to go on. Any
ideas on what is happening?

-Chris

@nlewycky
Copy link
Contributor Author

further reduced by hand
I am absolutely stumped. Removing basic blocks with no predecessors removes the
failure. Removing unused instructions that don't use anything removes the
failure.

When reducing it, I found that it seems to be especially touchy with regards to
anything with the type of "sbyte". As such, I tried to switch as many
instructions over to a different type as possible in the hopes that this would
shed some light. It hasn't.

@nlewycky
Copy link
Contributor Author

debug output; operations done on KillLocs
I'm attaching a debug dump of the associated run. The valgrind error comes
right before the attempt to remove "%tmp22 = load sbyte* null", meaning that
this particular instruction is the one causing the error.

The trace lists every call to KillLocs.add, .remove and .clear (never called).
Because .add(I) is used three times in the code, they're numbered [1] [2] [3]
in the debug output, in order that they appear in DeadStoreElimination.cpp.

The AliasSetTracker API doesn't seem to be getting obviously misused (I was
hoping to see remove called with the same pointer twice, no such luck), so
perhaps the bug isn't in the DSE pass but the aliasing analysis?

@nlewycky
Copy link
Contributor Author

debug output including AliasSetTracker
I've added debugging statements to AliasSetTracker. What I see is that when
KillLocs.remove(%tmp22) is called, it calls to AliasSetTracker::remove(AliasSet
&) which does PointerMap.erase(%tmp66). %tmp66 is the dead [uses=#0] alloca
instruction at the top of the function.

The invalid read is std::equal_to(%tmp23, %tmp66), but I'm not sure whether
it's %tmp23 or %tmp66 is invalid. According to the debug output, both have been
inserted (into PointerMap) and neither has been removed yet.

Also, this debug output uses -no-aa. I've noticed that it, -basicaa and
-globalsmodref-aa produce the error, while -ds-aa -steens-aa and -anders-aa
mask it.

@nlewycky
Copy link
Contributor Author

The problem is that the hash_map is being given its own value as input:

AliasSet::HashNodePair *P = AS.PtrList;
PointerMap.erase(P->first);

Imagine that the hash_map is a multimap for a second. When you call
multimap::erase(key), it erases all of the elements which are equal to that key.
Of course, the key comes in as a reference; after it deletes the first one, it
then tries to compare it against the other members, but it can't because the key
it's using for comparison has just been deleted.

For this to work right, someone has to take a copy of P->first. The question is
whether LLVM is at fault or if the hash_map implementation is responsible for
handling this correctly. Making an explicit copy fixes (or works around) the
bug, anyways.

For reference, here's a copy of GCC's implementation of hashtable.erase, used to
implement erase for both hash_map and hash_multimap:

template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type
hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
erase(const key_type& __key)
{
const size_type __n = _M_bkt_num_key(__key);
_Node* __first = _M_buckets[__n];
size_type __erased = 0;

  if (__first)
    {
      _Node* __cur = __first;
      _Node* __next = __cur->_M_next;
      while (__next)
        {
          if (_M_equals(_M_get_key(__next->_M_val), __key))
            {
              __cur->_M_next = __next->_M_next;
              _M_delete_node(__next); // freeing __key
              __next = __cur->_M_next;
              ++__erased;
              --_M_num_elements;
            }
          else
            {
              __cur = __next;
              __next = __cur->_M_next;
            }
        }
      if (_M_equals(_M_get_key(__first->_M_val), __key)) // using __key

after free
{
_M_buckets[__n] = __first->_M_next;
_M_delete_node(__first);
++__erased;
--_M_num_elements;
}
}
return __erased;
}

@nlewycky
Copy link
Contributor Author

Fixed. No testcase because this is a memory management bug.

Patch here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060911/037931.html

@nlewycky
Copy link
Contributor Author

Just to be clear, it's uncertain whether this is was bug in LLVM or a defect in
the implementation, or even the standard:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25896

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#526

Regardless, we'll leave our workaround in as a resolution from vendors isn't
likely to come any time soon (and we don't want to lose correctness with current
compilers).

@lattner
Copy link
Collaborator

lattner commented Sep 21, 2006

I agree, the work-around is a great portability fix if nothing else.

-Chris

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 3, 2021
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugzilla Issues migrated from bugzilla
Projects
None yet
Development

No branches or pull requests

2 participants