invalid use of iterators in gvn

[llvmbot]

Bugzilla Link	3358
Resolution	FIXED
Resolved on	Jan 22, 2009 01:40
Version	unspecified
OS	Linux
Attachments	testcase .ll
Reporter	LLVM Bugzilla Contributor
CC	@isanbard,@nlewycky

Extended Description

When built with ENABLE_EXPENSIVE_CHECKS=1, the attached testcase (reduced
from the llvm-gcc build) gives:

$ opt -gvn regexp.bc -disable-output
/usr/include/c++/4.3/bits/stl_algo.h:2180:error: elements in iterator range
[__first, __last) are not partitioned by the value __val.

Objects involved in the operation:
iterator "__first" @ 0x0x7fffe6d01ca0 {
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPSt4pairIPN4llvm10BasicBlockENS4_12MemDepResultEENSt6__norm6vectorIS8_SaIS8_EEEEENSt7__debug6vectorIS8_SC_EEEE (mutable iterator);
state = dereferenceable (start-of-sequence);
references sequence with type NSt7__debug6vectorISt4pairIPN4llvm10BasicBlockENS2_12MemDepResultEESaIS6_EEE' @ 0x0x7fffe6d01ca0 } iterator "__last" @ 0x0x7fffe6d01c40 { type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPSt4pairIPN4llvm10BasicBlockENS4_12MemDepResultEENSt6__norm6vectorIS8_SaIS8_EEEEENSt7__debug6vectorIS8_SC_EEEE (mutable iterator); state = dereferenceable; references sequence with type NSt7__debug6vectorISt4pairIPN4llvm10BasicBlockENS2_12MemDepResultEESaIS6_EEE' @ 0x0x7fffe6d01c40
}

[llvmbot]

Hi Duncan. Is it possible to match this back to code? Any idea where this is happening?

[lattner]

Duncan, can you get a stack trace of the failure? I would really really like to fix this for 2.5, it may explain some weirdness we're seeing lately

[llvmbot]

llvm::MemoryDependenceAnalysis::GetNonLocalInfoForBlock
MemoryDependenceAnalysis.cpp:515

510
511 // Do a binary search to see if we already have an entry for this block in
512 // the cache set. If so, find it.
513 NonLocalDepInfo::iterator Entry =
514 std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
515 std::make_pair(BB, MemDepResult()));
516 if (Entry != Cache->begin() && prior(Entry)->first == BB)
517 --Entry;
518

#​4 0x0000000000bac29b in llvm::MemoryDependenceAnalysis::GetNonLocalInfoForBlock (this=0x1fd09a0, Pointer=0x1fc8340,
PointeeSize=1, isLoad=true, BB=0x1fc5e20, Cache=0x1fd0ec0, NumSortedEntries=3)
at /home/duncan/LLVM/llvm.top/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp:515
#​5 0x0000000000bacbe3 in llvm::MemoryDependenceAnalysis::getNonLocalPointerDepFromBB (this=0x1fd09a0,
Pointer=0x1fc8340, PointeeSize=1, isLoad=true, StartBB=0x1fc5f10, Result=@0x7fffb8b87aa0,
Visited=@0x7fffb8b87820, SkipFirstBlock=false)
at /home/duncan/LLVM/llvm.top/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp:663
#​6 0x0000000000bacf04 in llvm::MemoryDependenceAnalysis::getNonLocalPointerDepFromBB (this=0x1fd09a0,
Pointer=0x1fc8340, PointeeSize=1, isLoad=true, StartBB=0x1fc5ec0, Result=@0x7fffb8b87aa0,
Visited=@0x7fffb8b87820, SkipFirstBlock=false)
at /home/duncan/LLVM/llvm.top/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp:734
#​7 0x0000000000bad569 in llvm::MemoryDependenceAnalysis::getNonLocalPointerDependency (this=0x1fd09a0,
Pointer=0x1fc8340, isLoad=true, FromBB=0x1fc5ec0, Result=@0x7fffb8b87aa0)
at /home/duncan/LLVM/llvm.top/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp:494
#​8 0x00000000009a5979 in processNonLocalLoad (this=0x1fc3760, LI=0x1fc8b78, toErase=@0x7fffb8b883f0)
---Type to continue, or q to quit---
at /home/duncan/LLVM/llvm.top/llvm/lib/Transforms/Scalar/GVN.cpp:940
#​9 0x00000000009a6855 in processLoad (this=0x1fc3760, L=0x1fc8b78, toErase=@0x7fffb8b883f0)
at /home/duncan/LLVM/llvm.top/llvm/lib/Transforms/Scalar/GVN.cpp:1161
#​10 0x00000000009a8a59 in processInstruction (this=0x1fc3760, I=0x1fc8b78, toErase=@0x7fffb8b883f0)
at /home/duncan/LLVM/llvm.top/llvm/lib/Transforms/Scalar/GVN.cpp:1284
#​11 0x00000000009a916e in processBlock (this=0x1fc3760, BB=0x1fc5ec0)
at /home/duncan/LLVM/llvm.top/llvm/lib/Transforms/Scalar/GVN.cpp:1422
#​12 0x00000000009a9449 in iterateOnFunction (this=0x1fc3760, F=@0x1fc48d0)
at /home/duncan/LLVM/llvm.top/llvm/lib/Transforms/Scalar/GVN.cpp:1620
#​13 0x00000000009a960f in runOnFunction (this=0x1fc3760, F=@0x1fc48d0)
at /home/duncan/LLVM/llvm.top/llvm/lib/Transforms/Scalar/GVN.cpp:1384
#​14 0x0000000000cba4b7 in llvm::FPPassManager::runOnFunction (this=0x1fc3850, F=@0x1fc48d0)
at /home/duncan/LLVM/llvm.top/llvm/lib/VMCore/PassManager.cpp:1323
#​15 0x0000000000cba61a in llvm::FPPassManager::runOnModule (this=0x1fc3850, M=@0x1fc3a70)
at /home/duncan/LLVM/llvm.top/llvm/lib/VMCore/PassManager.cpp:1346
#​16 0x0000000000cb992f in llvm::MPPassManager::runOnModule (this=0x1fc7dc0, M=@0x1fc3a70)
at /home/duncan/LLVM/llvm.top/llvm/lib/VMCore/PassManager.cpp:1393
#​17 0x0000000000cbaee6 in llvm::PassManagerImpl::run (this=0x1fc50a0, M=@0x1fc3a70)
at /home/duncan/LLVM/llvm.top/llvm/lib/VMCore/PassManager.cpp:1467
#​18 0x0000000000cbaf49 in llvm::PassManager::run (this=0x7fffb8b888b0, M=@0x1fc3a70)
at /home/duncan/LLVM/llvm.top/llvm/lib/VMCore/PassManager.cpp:1499
#​19 0x00000000008e1131 in main (argc=4, argv=0x7fffb8b88c68) at /home/duncan/LLVM/llvm.top/llvm/tools/opt/opt.cpp:588

[llvmbot]

I think this is saying that Cache is not ordered.

[llvmbot]

It could also mean that the comparator is broken.

[llvmbot]

Debugging patch
The attached patch shows the problem: the cache is not always
sorted when it is supposed to be.

[llvmbot]

Could you apply that patch with DEBUGs around the "isSorted()" calls? Similar to how "verifyRemoved" is done in GVN.cpp.

[lattner]

Investigating, this is very interesting. Thanks for the 'issorted' patch Bill, that is super-helpful.

[lattner]

Fixed:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20090119/072525.html

I will request this to be pulled into 2.5

[isanbard]

Investigating, this is very interesting. Thanks for the 'issorted' patch Bill,
that is super-helpful.

It was Duncan's patch. :-)