indvars pass creates dangling pointers in SCEV handles

[llvmbot]

Bugzilla Link	1487
Resolution	FIXED
Resolved on	Feb 22, 2010 12:44
Version	2.0
OS	Linux
Attachments	bugpoint-reduced-simplified.bc
Reporter	LLVM Bugzilla Contributor
CC	@nlewycky

Extended Description

laurov@laurov-desktop:~$ opt bugpoint-reduced-simplified.bc -indvars -o tmp.bc
opt((anonymous namespace)::PrintStackTrace()+0x1a)[0x86674fe]
opt((anonymous namespace)::SignalHandler(int)+0x112)[0x86677c4]
[0xffffe420]
opt(llvm::ETNode::DominatedBySlow(llvm::ETNode*)+0x18)[0x8419a4e]
opt(llvm::ETForestBase::dominates(llvm::BasicBlock*,
llvm::BasicBlock*)+0xba)[0x8419b0e]
opt[0x8629c2d]
opt[0x862a715]
opt(llvm::InstVisitor<(anonymous namespace)::Verifier,
void>::visitAdd(llvm::BinaryOperator&)+0x18)[0x862eea8]
opt(llvm::InstVisitor<(anonymous namespace)::Verifier,
void>::visit(llvm::Instruction&)+0xe6)[0x862f6d0]
opt(void llvm::InstVisitor<(anonymous namespace)::Verifier,
void>::visit<llvm::ilist_iteratorllvm::Instruction

(llvm::ilist_iteratorllvm::Instruction,
llvm::ilist_iteratorllvm::Instruction)+0x45)[0x862fae3]
opt(llvm::InstVisitor<(anonymous namespace)::Verifier,
void>::visit(llvm::BasicBlock&)+0x5e)[0x862fb5a]
opt(void llvm::InstVisitor<(anonymous namespace)::Verifier,
void>::visit<llvm::ilist_iteratorllvm::BasicBlock
(llvm::ilist_iteratorllvm::BasicBlock,
llvm::ilist_iteratorllvm::BasicBlock)+0x45)[0x862fba5]
opt(llvm::InstVisitor<(anonymous namespace)::Verifier,
void>::visit(llvm::Function&)+0x5e)[0x862fdc2]
opt[0x862fe11]
opt(llvm::FPPassManager::runOnFunction(llvm::Function&)+0x13a)[0x8601f1c]
opt(llvm::FPPassManager::runOnModule(llvm::Module&)+0x6e)[0x86020e4]
opt(llvm::MPPassManager::runOnModule(llvm::Module&)+0x11d)[0x8601bbd]
opt(llvm::PassManagerImpl::run(llvm::Module&)+0x6e)[0x8601d8a]
opt(llvm::PassManager::run(llvm::Module&)+0x1a)[0x8601ddc]
opt(main+0xa10)[0x83964e6]
/lib/tls/i686/cmov/libc.so.6(__libc_start_main+0xdc)[0xb7c6cebc]
opt(realloc+0x71)[0x8388711]
Segmentation fault (core dumped)

[llvmbot]

I'm not able to produce this crash on ppc32-darwin.

[nlewycky]

I can reproduce this on x86 linux. It's crashing in ETForest called from the
verifier. Valgrind catches the problem:

==30124== Invalid read of size 2
==30124== at 0x836445E: llvm::Value::getValueID() const (Value.h:193)
==30124== by 0x83644D2: bool llvm::isa_impl<llvm::Instruction,
llvm::Value>(llvm::Value const&) (Value.h:242)
==30124== by 0x8364E16: llvm::isa_impl_wrap<llvm::Instruction, llvm::Value
const, llvm::Value const>::doit(llvm::Value const&) (Casting.h:71)
==30124== by 0x8364E2C: bool
llvm::isa_impl_clllvm::Value::isallvm::Instruction(llvm::Value const&)
(Casting.h:83)
==30124== by 0x8364E42: bool
llvm::isa_impl_clllvm::Value*::isallvm::Instruction(llvm::Value*)
(Casting.h:101)
==30124== by 0x8364E5A: bool llvm::isa<llvm::Instruction,
llvm::Value*>(llvm::Value* const&) (Casting.h:116)
==30124== by 0x8365444: llvm::cast_retty<llvm::Instruction,
llvm::Value*>::ret_type llvm::dyn_cast<llvm::Instruction,
llvm::Value*>(llvm::Value*) (Casting.h:225)
==30124== by 0x852C061: llvm::SCEVUnknown::isLoopInvariant(llvm::Loop const*)
const (ScalarEvolution.cpp:373)
==30124== by 0x853F95D:
llvm::SCEVCommutativeExpr::hasComputableLoopEvolution(llvm::Loop const*) const
(ScalarEvolutionExpressions.h:210)
==30124== by 0x8406748: (anonymous
namespace)::IndVarSimplify::RewriteLoopExitValues(llvm::Loop*)
(IndVarSimplify.cpp:367)
==30124== by 0x8406B8B: (anonymous
namespace)::IndVarSimplify::runOnLoop(llvm::Loop*, llvm::LPPassManager&)
(IndVarSimplify.cpp:457)
==30124== by 0x851F399: llvm::LPPassManager::runOnFunction(llvm::Function&)
(LoopPass.cpp:204)
==30124== Address 0x61793DC is 4 bytes inside a block of size 44 free'd
==30124== at 0x43DADE1: operator delete(void*) (vg_replace_malloc.c:244)
==30124== by 0x85C2818: llvm::PHINode::~PHINode() (Instructions.cpp:72)
==30124== by 0x8389E3E: llvm::iplist<llvm::Instruction,
llvm::ilist_traitsllvm::Instruction

::erase(llvm::ilist_iteratorllvm::Instruction) (ilist:330)
==30124== by 0x85BC182: llvm::Instruction::eraseFromParent() (Instruction.cpp:68)
==30124== by 0x8406990: (anonymous
namespace)::IndVarSimplify::RewriteLoopExitValues(llvm::Loop*)
(IndVarSimplify.cpp:402)
==30124== by 0x8406B8B: (anonymous
namespace)::IndVarSimplify::runOnLoop(llvm::Loop*, llvm::LPPassManager&)
(IndVarSimplify.cpp:457)
==30124== by 0x851F399: llvm::LPPassManager::runOnFunction(llvm::Function&)
(LoopPass.cpp:204)
==30124== by 0x85DF0B5: llvm::FPPassManager::runOnFunction(llvm::Function&)
(PassManager.cpp:1140)
==30124== by 0x85DF27D: llvm::FPPassManager::runOnModule(llvm::Module&)
(PassManager.cpp:1159)
==30124== by 0x85DED56: llvm::MPPassManager::runOnModule(llvm::Module&)
(PassManager.cpp:1208)
==30124== by 0x85DEF23: llvm::PassManagerImpl::run(llvm::Module&)
(PassManager.cpp:1281)
==30124== by 0x85DEF75: llvm::PassManager::run(llvm::Module&)
(PassManager.cpp:1313)
==30124==

So IndVarSimplify.cpp:402 deleted a Value that ScalarEvolution.cpp:373 is trying
to read.

[nlewycky]

reduced by hand
I've further reduced the testcase.

My previous explanation of the valgrind reading were correct but not as
informative as they should have been. It's deleting it a PHINode
(%stream_ptr.132032.us.lcssa) at IndVarSimplify.cpp:402 and then trying to
access it at IndVarSimplify.cpp:367

Here's the indvars debug output:

INDVARS: RLEV: AfterLoopVal = %tmp. = add i32 %stream_ptr.142038.us.ph.ph1,
3; [#uses=0]
LoopVal = %stream_ptr.132032.us = add i32 %pixel_x.232031.us,
%stream_ptr.142038.us.ph.ph1 ; [#uses=1]

*** The problematic delete: %stream_ptr.132032.us.lcssa being replaced with
%tmp. = add i32 %stream_ptr.142038.us.ph.ph1, 3 ; [#uses=1]

INDVARS: Deleting: %stream_ptr.132032.us = add i32 %pixel_x.232031.us,
%stream_ptr.142038.us.ph.ph1 ; [#uses=0]
INDVARS: New CanIV: %indvar = phi i32 [ 0, %bb1326.us.outer ], [
%indvar.next, %bb1326.us ] ; [#uses=1]
INDVARS: LFTR: TripCount = 4 IndVar = %indvar.next = add i32 %indvar,
1 ; [#uses=1]

INDVARS: Rewrote IV '{ 0,+, 1}<bb1326.us>' %pixel_x.232031.us = phi i32 [
%tmp1341.us, %bb1326.us ], [ 0, %bb1326.us.outer ] ;
[#uses=1]
into = %indvar = phi i32 [ 0, %bb1326.us.outer ], [ %indvar.next,
%bb1326.us ] ; [#uses=1]

INDVARS: Deleting: phi i32 [ %tmp1341.us, %bb1326.us ], [ 0,
%bb1326.us.outer ] ; :0 [#uses=0]
INDVARS: Deleting: %tmp1344.us = icmp slt i32 %tmp1341.us, 4
; [#uses=0]
INDVARS: Deleting: %tmp1341.us = add i32 %pixel_x.232031.us, 1
; [#uses=0]

and then valgrind kicks in.

I tried fixing it with SE->deleteInstructionFromRecords(PN) right before PN is
removed, but that didn't remove the dangling pointer. That code at line 367
accesses the PHI indirectly because it's still a member of the Loop object.

[nlewycky]

cc'ing Owen because this may be related to his LCSSA work. Owen, feel free to
remove yourself from the cc once you exonerate yourself ;-)

[llvmbot]

I can't reproduce on darwin-x86 either.

[lattner]

lauro or nick, can you please try this patch? If it works (i.e. no crash and valgrind clean) let me know
and I'll commit it.

Thanks,

-Chris

RCS file: /var/cvs/llvm/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp,v
retrieving revision 1.119
diff -u -r1.119 IndVarSimplify.cpp
--- IndVarSimplify.cpp 6 May 2007 13:37:16 -0000 1.119
+++ IndVarSimplify.cpp 4 Jun 2007 23:06:50 -0000
@@ -398,6 +398,7 @@
// the PHI entirely. This is safe, because the NewVal won't be variant
// in the loop, so we don't need an LCSSA phi node anymore.
if (NumPreds == 1) {

•      SE->deleteInstructionFromRecords(PN);
       PN->replaceAllUsesWith(ExitVal);
       PN->eraseFromParent();
       break;
  

[llvmbot]

I can't produce the crash with the "reduced by hand" testcase.

Chris, the patch doesn't solve the problem.

[lattner]

Here is another related chunk:

--- IndVarSimplify.cpp 6 May 2007 13:37:16 -0000 1.119
+++ IndVarSimplify.cpp 5 Jun 2007 00:02:31 -0000
@@ -181,6 +181,7 @@
GetElementPtrInst *NGEPI = new GetElementPtrInst(
NCE, Constant::getNullValue(Type::Int32Ty), NewAdd,
GEPI->getName(), GEPI);

•          SE->deleteInstructionFromRecords(GEPI);
           GEPI->replaceAllUsesWith(NGEPI);
           GEPI->eraseFromParent();
           GEPI = NGEPI;
  

Nick, please see if these fix the valgrind output.

It is entirely possible that nick and lauro are hitting different issues here. Lauro, does the second fix it
for you? Nick, does the combination of the two patches fix all bad valgrind output?

-Chris

[nlewycky]

I had already written the same as Lauro's patch and found that it didn't work.
I'll look at Chris' patch in a minute.

[nlewycky]

With both patches applied, I get the same valgrind errors.

[lattner]

ok, well they should work. Perhaps SCEV isn't properly releasing all memory? I don't really know, and I
can't repro it. Can one of you guys plz investigate? Thanks,

[nlewycky]

The SCEVHandle for %tmp1339.us is "(%pixel_x.232031.us + undef)", except that
%pixel_x.232031.us was deleted by PN->replaceAllUsesWith(NewVal) around line 571.

How is a SCEVHandle supposed to be informed that an RAUW occured?

[lattner]

scevhandles can't be automatically updated. The client (e.g. indvars) needs to know to let go of these.

If this is internal to SCEV (i.e. it the value in the value map, then the existing calls should do it).

-Chris

[nlewycky]

I don't think the existing calls will do it.

getSCEV(%x) is called which caches the expression (%y + %z) in Scalars.
%y is deleted, SE->deleteInstructionFromRecords(%y) removes %y from Scalars, but
leaves %x as-is.
getSCEV(%x) is called against which returns the expression from the cache.
Unfortunately, it's invalid.

Is there supposed to be some mechanism to deal with this? The SCEV for %y
doesn't hold a pointer back to %x anywhere, does it?

[nlewycky]

patch fixes problem
Actually, it is fixable with the current API. The SCEV for %y may not hold a
pointer to the SCEV for %x, but %y itself still has a Uses list.

This patch changes deleteInstructionFromRecords to iterate through the uses and
finds other Instructions that have SCEVs and delete them too. Please review.

For bonus points when reviewing, prove that the while loop always terminates.