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_to<llvm::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::hash<llvm::Value*>, std::_Select1st<std::pair<llvm::Value* const, llvm::AliasSet::PointerRec> >, std::equal_to<llvm::Value*>, std::allocator<llvm::AliasSet::PointerRec> >::erase(llvm::Value* const&) (hashtable.h:895) ==13389== by 0x85E937D: __gnu_cxx::hash_map<llvm::Value*, llvm::AliasSet::PointerRec, __gnu_cxx::hash<llvm::Value*>, std::equal_to<llvm::Value*>, std::allocator<llvm::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::PassManagerT<llvm::FTraits>::runPasses(llvm::Function*, std::map<llvm::Pass*, std::vector<llvm::Pass*, std::allocator<llvm::Pass*> >, std::less<llvm::Pass*>, std::allocator<std::pair<llvm::Pass* const, std::vector<llvm::Pass*, std::allocator<llvm::Pass*> > > > >&) (PassManagerT.h:596) ==13389== by 0x86CF96F: llvm::PassManagerT<llvm::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::hash<llvm::Value*>, std::_Select1st<std::pair<llvm::Value* const, llvm::AliasSet::PointerRec> >, std::equal_to<llvm::Value*>, std::allocator<llvm::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::hash<llvm::Value*>, std::_Select1st<std::pair<llvm::Value* const, llvm::AliasSet::PointerRec> >, std::equal_to<llvm::Value*>, std::allocator<llvm::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::hash<llvm::Value*>, std::_Select1st<std::pair<llvm::Value* const, llvm::AliasSet::PointerRec> >, std::equal_to<llvm::Value*>, std::allocator<llvm::AliasSet::PointerRec> >::erase(llvm::Value* const&) (hashtable.h:884) ==13389== by 0x85E937D: __gnu_cxx::hash_map<llvm::Value*, llvm::AliasSet::PointerRec, __gnu_cxx::hash<llvm::Value*>, std::equal_to<llvm::Value*>, std::allocator<llvm::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.
Created attachment 387 [details] simplified testcase
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
Created attachment 391 [details] 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.
Created attachment 392 [details] 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?
Created attachment 394 [details] 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.
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; }
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
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).
I agree, the work-around is a great portability fix if nothing else. -Chris