llvm dev - Nov 2002 - [LLVMdev] Find mallocs from a DSNode

Chris Lattner wrote:
> > Is there some efficient way to find the malloc instructions which
point
> > to the memory represented by a DSNode?  Right now the only way I see
is
> > by iterating through the value map in the DSGraph object and finding
> > every value that points to my DSNode.
>
> You're right, you have to iterate over the program, looking to see what
> DSNodes the Malloc instructions point to.  This is intentional: keeping
> track of this information would cause a huge representational problem.
> Sorry :)
Fair enough.
> > A possibly related question: is there a way to tell that the node has
> > been merged, and if so, what types of nodes went into the merge?
>
> Yup, DSNode::NodeType contains flags for the node.  There are four flags
> that indicate the composition of the node: DSNode::AllocaNode, HeapNode,
> GlobalNode, UnknownNode.
>
> When two nodes are merged, their Flags are bitwise or'd together...
I realized that, but what if two nodes of the same type are merged?  Their
flags will not indicate that a merge has occurred.  I'm concerned about the
case where two malloc nodes are merged, because then if free is called on the
memory represented by that node, you cannot be certain of either malloc's
memory being freed.  I suppose after I iterate over the value map I'll see
that two malloc instructions point to the same DSNode, which will give me the
equivalent information.

Thanks,
Scott

> > When two nodes are merged, their Flags are bitwise or'd
together...
>
> I realized that, but what if two nodes of the same type are merged?  Their
> flags will not indicate that a merge has occurred.  I'm concerned about
the
> case where two malloc nodes are merged, because then if free is called on
the
> memory represented by that node, you cannot be certain of either
malloc's
> memory being freed.  I suppose after I iterate over the value map I'll
see
> that two malloc instructions point to the same DSNode, which will give me
the
> equivalent information.
Pretty much.  At some point, any representation has to merge together
information, because (in general) the program being represented may create
an unbounded number of objects dynamically, and we can obviously only
represent a finite number of them.  Looping through the program to see how
many scalars are pointing to the same node seems like a reasonable way to
get the information you need, but remember you also have this case:

for (...)
  X = malloc ...

where _1_ call site can create an unbounded number of objects, all of
which may be potentially merged together...

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

Scott (and the other Project 6 people),

I had given this some thought and, interestingly enough, there are cases
where you *can* be sure a node is freed even if 2 nodes have been merged
before the free.  E.g.,

	if (c)
	   p1 = malloc...
	else
	   p2 = malloc...
	endif
	p3 = phi(p1, p2)
	...
	free p3

The question is, can you distinguish the above case from the following one
where there is a potential leak:
      p1 = malloc...
	if (c)
	   p2 = malloc...
	endif
	p3 = phi(p1, p2)
	...
	free p3

Of course, some cases (like the loop Chris pointed out below) is obviously
difficult to detect.  The frees will usually happen in some other loop, and
it requires different technology to know if the free loop enumerates a
subset, superset, or identical set of array elements compared with the first
loop.

--Vikram

-------------------------------------------------------------------------
 VIKRAM S. ADVE
 Assistant Professor                            E-MAIL: vadve at cs.uiuc.edu
 Department of Computer Science                 PHONE:  (217) 244-2016
 Univ. of Illinois at Urbana-Champaign          FAX:    (217) 244-6869
 1304 W. Springfield Ave.              WWW: http://www.cs.uiuc.edu/~vadve
 Urbana IL 61801-2987.
-------------------------------------------------------------------------

> -----Original Message-----
> From: llvmdev-admin at cs.uiuc.edu [mailto:llvmdev-admin at cs.uiuc.edu]On
> Behalf Of Chris Lattner
> Sent: Sunday, November 10, 2002 11:02 PM
> To: Scott Mikula
> Cc: llvmdev at cs.uiuc.edu
> Subject: Re: [LLVMdev] Find mallocs from a DSNode
>
>
> > > When two nodes are merged, their Flags are bitwise or'd
together...
> >
> > I realized that, but what if two nodes of the same type are
> merged?  Their
> > flags will not indicate that a merge has occurred.  I'm
> concerned about the
> > case where two malloc nodes are merged, because then if free is
> called on the
> > memory represented by that node, you cannot be certain of
> either malloc's
> > memory being freed.  I suppose after I iterate over the value
> map I'll see
> > that two malloc instructions point to the same DSNode, which
> will give me the
> > equivalent information.
>
> Pretty much.  At some point, any representation has to merge together
> information, because (in general) the program being represented may create
> an unbounded number of objects dynamically, and we can obviously only
> represent a finite number of them.  Looping through the program to see how
> many scalars are pointing to the same node seems like a reasonable way to
> get the information you need, but remember you also have this case:
>
> for (...)
>   X = malloc ...
>
> where _1_ call site can create an unbounded number of objects, all of
> which may be potentially merged together...
>
> -Chris
>
> --
> http://llvm.cs.uiuc.edu/
> http://www.nondot.org/~sabre/Projects/
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://mail.cs.uiuc.edu/mailman/listinfo/llvmdev
>