Memory leak in ETNode::setFather

[llvmbot]

Bugzilla Link	775
Resolution	FIXED
Resolved on	Feb 22, 2010 12:52
Version	1.7
OS	All
Attachments	BC test file for leak detection in ETNode
Reporter	LLVM Bugzilla Contributor
CC	@lattner

Extended Description

run

valgrind --tool=memcheck -leak-check=full --num-callers=20 analyze -etforest
hsat.bc 2> leak_report

[llvmbot]

assigned to @isanbard

[llvmbot]

I give on this one. I can't see the trees for the forest.

Actually, its more a matter of time. It will take me many hours to get a clear
comprehension of how the trees (ETNode and ETOccurrence) are interacting.

For the next person to tackle this, here is what Danny Berlin (author of
ETForest) wrote about the relationships in an email to me:

Reid Spencer wrote:

Hi Danny,

I'm working on LLVM llvm/llvm-bugzilla-archive#775 which is about a bug leak in
ETNode::setParent. The thing leaking is the ETOccurrence created as the
new father.

The new father should get linked into the occurrence splay tree, no?

I'm assuming its the previous incarnation of "father" that

gets leaked as the splay tree is built. My first idea was to simply:

ETOccurrence::~ETOccurrence { delete Left; delete Right; }

That lead to memory corruption, so obviously the correct thing is not
to delete the entire subtree when a parent is replaced.

It is not, because the subtree is only going to be updated, not destroyed.

Unfortunately, the documentation isn't quite complete enough for me to
understand how the ET-Forest and the Splay tree of ETOccurrences exactly
relate to each other.
The etnode tree is essentially a copy of the dominator tree.

The ETOccurrences splay-tree stores the dfs sequence that you would get
if you dfs'd the etnode tree. It is stored in a slightly modified splay
tree in a way that we can update and query it very quickly.

Thus, multiple etnodes may have the same etoccurrence as their father,
because multiple bb's may have the same immediate dominator.

This makes the lifetimes a bit hard for etoccurrences (etnodes are
easy). You'd probably need to refcount them, and then make sure all the
ops are done in the right order (IE sets before clears) so that the
refcount doesn't accidentally drop to 0 at the wrong time.

It is possible that what is happening here is that some part of the
dominator tree becomes completely disconnected, but we are still doing
setImmediateDominator calls on some part of the disconnected subtree, so
we end up creating etoccurrences that are completely disconnected from
the rest of the world because they don't occur in the dfs sequence.

This is a random guess. We wouldn't leak ETNodes in this case because
there is only one per basic block, and it would still go away at the
"right" time. I think.

Can you help my understanding a little or point me

in the right direction. I'm very familiar with binary and multi-way
trees, but there seem to be two trees enmeshed together or related in
some way and I'm not completely understanding the relationship between
the ETNode trees and the ETOccurrence tress.

You can conceptually view them as completely separate trees except that
nodes in one tree happen to be the data used in the other.

Past that, it just so happens that etnodes know their parent and
rightmost occurrences in the etoccurrence tree, because they can do so
in constant time. You could theoretically look it up all the time.

[isanbard]

I have a fix for this. It uses ye olde reference counting on ETOccurrence nodes to delete them when they're
no longer needed. I'll submit the fix after it's finished testing.

[lattner]

you add an ivar? I have a patch in my email that may help with this, I'll forward it to you.

[isanbard]

Cool! I'll take a look at it. Thanks!

[llvmbot]

Fixed.

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070219/044826.html