headers
Chris Lattner | 1 Dec 2002 13:15

How to get a Module DSGraph?

On Sat, 30 Nov 2002, Juan Nicolas Ruiz wrote:
> I've been trying to obtain a DSGraph for a complete module, but
> haven't succeeded. I tried

First off, there is no one way to get a DSGraph for a module.  What you do
to get it depends on what kind of information you are interested in...

> - getting the DSGraph for each function, and copying the nodes to a
> Module graph. But since there are no nodehandles, apparently there is
> no merging of nodes.

This works fine, you just have to merge the formal and actual arguments
(and the return value) of functions with their call sites.  This ends up
giving you a "steensgaard's" style IP DSGraph.  In fact, if you look in
the DataStructure directory, the Steensgaards.cpp file contains a
(partial) implementation of this.  It doesn't handle function pointers or
any of that fun stuff yet, but you should be able to get the main idea
from it...

> My main interest is in situations like
>
> void *M(int size) {
>   return malloc(size);
> }
> void F() {
>    void *p = M(....);
> }

> where I can identify that %p and the object returned by M() are the
> same.
(Continue reading)

Permalink | Reply | 0 comments |
headers
David Crowe | 1 Dec 2002 13:16
Picon

Shouldn't need a "Module Graph"

The way we are doing it, per Vikram's recommendation, is to provide a 
mapping between the callers nodes and the callees nodes at the time of the 
call.  Given that the only way they can communicate is through the 
parameters, globals, and return node, this is fairly easy.  You must take 
into account that the DSGraphs may be different shapes though.

Dave
Permalink | Reply | 2 comments |
headers
Juan Nicolas Ruiz | 1 Dec 2002 13:42
Picon

Shouldn't need a "Module Graph"

Thanks for the tip, but what do you mean by "DSGraphs may be different
shapes?

On Sun, 1 Dec 2002, David Crowe wrote:

> The way we are doing it, per Vikram's recommendation, is to provide a
> mapping between the callers nodes and the callees nodes at the time of the
> call.  Given that the only way they can communicate is through the
> parameters, globals, and return node, this is fairly easy.  You must take
> into account that the DSGraphs may be different shapes though.
Permalink | Reply | 1 comment |
headers
David Crowe | 1 Dec 2002 13:49
Picon

Shouldn't need a "Module Graph"

Ok, here is a trivial example:

In the Callee: A->(itself)

In the caller: B->C->itself

Your mapping should provide:

B->A
C->A
A->B  (not sure about this one, is there a better way?)

I don't know how this example could be manufactured in code, but I'm sure 
there are more complex cases which need the same principle...

Dave

On Sun, 1 Dec 2002, Juan Nicolas Ruiz wrote:

> Thanks for the tip, but what do you mean by "DSGraphs may be different
> shapes?
> 
> On Sun, 1 Dec 2002, David Crowe wrote:
> 
> > The way we are doing it, per Vikram's recommendation, is to provide a
> > mapping between the callers nodes and the callees nodes at the time of the
> > call.  Given that the only way they can communicate is through the
> > parameters, globals, and return node, this is fairly easy.  You must take
> > into account that the DSGraphs may be different shapes though.
>
(Continue reading)

Permalink | Reply | 0 comments |
headers
Aqeel Mahesri | 1 Dec 2002 21:41
Picon

PassManager error message hard to decipher

I cannot figure out a particular PassManager error for what seem to be
legal dependencies.

Here is the situation.  We have 5 passes, RegisterAllocator,
FunctionLiveVarInfo, CoalesceCopies, DominanceForest, and UnionSSAVars,
with dependencies as follows:

class RegisterAllocator : public FunctionPass {
  . . .
  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
	AU.addRequired<FunctionLiveVarInfo>();
	AU.addRequired<CoalesceCopies>();
  }
  . . .
};

class FunctionLiveVarInfo : public FunctionPass {
  . . .
  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
	AU.setPreservesAll();
  }
  . . .
};

class CoalesceCopies : public FunctionPass {
  . . .
  virtual void getAnalysisUsage(AnalysisUsage &AU) {
	AU.setPreservesAll();
	AU.addRequired<FunctionLiveVarInfo>();
	AU.addRequired<UnionSSAVars>();
(Continue reading)

Permalink | Reply | 1 comment |
headers
Chris Lattner | 2 Dec 2002 01:39

PassManager error message hard to decipher

> Here is the situation.  We have 5 passes, RegisterAllocator,
> FunctionLiveVarInfo, CoalesceCopies, DominanceForest, and UnionSSAVars,
> with dependencies as follows:

Wow, that is a crazy set of interdependences, I'm impressed :)

> class RegisterAllocator : public FunctionPass {
>   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
> class FunctionLiveVarInfo : public FunctionPass {
>   virtual void getAnalysisUsage(AnalysisUsage &AU) const {

These are ok...

> class CoalesceCopies : public FunctionPass {
>   virtual void getAnalysisUsage(AnalysisUsage &AU) {
> class UnionSSAVars : public FunctionPass {
>   virtual void getAnalysisUsage(AnalysisUsage &AU) {
> class DominanceForest : public FunctionPass {
>   virtual void getAnalysisUsage(AnalysisUsage &AU) {

These are not: notice the methods aren't const.  Let me know whether or
not this fixes the problem, you probably have the most complex web of
interdependences yet :)

-Chris

--

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/
(Continue reading)

Permalink | Reply | 0 comments |
headers
Juan Nicolas Ruiz | 2 Dec 2002 20:42
Picon

Function Formal parameters

can we assume that

  for(Function::aiterator I = F.abegin(); E = F.aend(); I!=E; ++I) {
   ....
  }

or

  Argument *FA = &F.afront();
  do {
    FA = FA->getNext();
    ....
  } while (FA != &F.aback());

would iterate over function "F" formal parameters in order? All the
tests I've run so far indicate so, but unless it is guaranteed, I
don't see how can I match formal and actual parameters for a function.
Permalink | Reply | 1 comment |
headers
Chris Lattner | 2 Dec 2002 20:46

Function Formal parameters

> can we assume that
>   for(Function::aiterator I = F.abegin(); E = F.aend(); I!=E; ++I) {

...

> would iterate over function "F" formal parameters in order? All the
> tests I've run so far indicate so, but unless it is guaranteed, I
> don't see how can I match formal and actual parameters for a function.

Yup, that's guaranteed.  Note that the first form is certainly more
idiomatic C++, so please don't do the second one...

-Chris

--

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/
Permalink | Reply | 0 comments |
headers
Xiaodong Li | 3 Dec 2002 00:32
Picon

DSnode type question

Hi, Chris,

I was wondering if you had a chance to look at this problem. Could
you let me know how to decide if this is a heap node in this case? It's
important because my code depends on this information.

Thanks,
Jerry

On Thu, 21 Nov 2002, Chris Lattner wrote:

> > When I use analyze to construct the DSGraph for the lists.c program in
> > test/Programs/SingleSource/Shootout directory. I found out the heap node
> > in the function test_list() all have type FOLDED:R. I was wondering why
> > it's not heapnode anymore? My pass need to use this type information to
> > determine whether a node is heap node. Is there any way I can know this is
> > a heap node in this case?
>
> Folded nodes are nodes where the type information in LLVM isn't good
> enough to distinguish fields, therefore we need to fold the nodes to be
> conservatively correct, even though doing so loses field sensitivity.
>
> Pointer/Alias analysis is an undecidable problem, so all [sound] analyses
> must have some way to represent conservativism.  This is one of the ways
> that the DSGraphs do it.  In this case, your pass should do something
> conservative.
>
> Despite this, we should not be tossing away the type of memory object it
> is (ie heap allocation).  I will look into this tommorow to see what is
> going on.
(Continue reading)

Permalink | Reply | 1 comment |
headers
Chris Lattner | 3 Dec 2002 14:03

DSnode type question

> I was wondering if you had a chance to look at this problem. Could
> you let me know how to decide if this is a heap node in this case? It's
> important because my code depends on this information.

Thanks for reminding me, I forgot.  I don't see any folded nodes for the
lists.c/test_list function.  Furthermore, I checked out
DSNode::foldNodeCompletely, and it doesn't remove any flags.  Can you give
me more details about when you see this problem?

-Chris

> On Thu, 21 Nov 2002, Chris Lattner wrote:
>
> > > When I use analyze to construct the DSGraph for the lists.c program in
> > > test/Programs/SingleSource/Shootout directory. I found out the heap node
> > > in the function test_list() all have type FOLDED:R. I was wondering why
> > > it's not heapnode anymore? My pass need to use this type information to
> > > determine whether a node is heap node. Is there any way I can know this is
> > > a heap node in this case?
> >
> > Folded nodes are nodes where the type information in LLVM isn't good
> > enough to distinguish fields, therefore we need to fold the nodes to be
> > conservatively correct, even though doing so loses field sensitivity.
> >
> > Pointer/Alias analysis is an undecidable problem, so all [sound] analyses
> > must have some way to represent conservativism.  This is one of the ways
> > that the DSGraphs do it.  In this case, your pass should do something
> > conservative.
> >
> > Despite this, we should not be tossing away the type of memory object it
(Continue reading)

Permalink | Reply | 0 comments |

Gmane