Getting the DSNode from a Pool Descriptor?

I figure (hopefully correctly) that I can iterate over all pool descriptors in a program by iterating over all users of poolinit and looking at the first argument. However, once I have a pool descriptor, I need to get its corresponding DSNode in the function in which it is complete (or in the global graph if it is a global). How do I do this?

Thanks,
--Patrick

You might want to have a look at PoolAllocate.h.

Per function, a PA::FuncInfo structure keeps track of all DSNodes that should be pool allocated. ArgNodes contains pool arguments, NodesToPA
contains nodes that are locally pool allocated and thus initialized using poolinit.

PoolDescriptors contains a mapping from DSNodes to pool descriptors, and
you could easily invert this mapping.

Finding a corresponding DSNode which is complete is not uniquely determined. For example, if a function F uses a pool, but its DSNode
is incomplete, it might be called from two different function G and H,
which both have a complete DSNode that maps to the DSNode in F.

You can assume that if a function is cloned, so that its DSNodes
are pool allocated, those DSNodes originate from a complete DSNode
somewhere higher in the call chain.

Per function, a pool-allocated version can be generated. After that,
function calls are rewritten to call the pool allocated version. This is done in TransformFunctionBody.cpp. by calling TransformBody from PoolAllocate.cpp.

Harmen

Patrick Alexander Simmons wrote:

How is different than the function in which the poolinit appears (or
main if it is global)?

Andrew

Depending on the value of dsa_pass_to_use, either EquivBUDataStructures or EQTDDataStructures is used. In the case that the top-down DSA is used, information is pushed down to nodes in callees. However,
if bottom-up DSA is used, information has only been merged upwards and
the nodes are not necessarily equivalent.

Harmen

Andrew Lenharth wrote:

In BU, a node will not be complete if it it is reachable from an
argument. Poolalloc, originally, uses (c)BU. The TD based poolalloc
was for safecode. Patrick doesn't work on safecode, so I was assuming
he was using BU-poolalloc.

Harmen, your suggestion of inverting the mapping almost worked (and Andrew was correct that the function I need is the same as the one in which poolinit appears). Unfortunately, it appears that this mapping only considers the original function and not any of its clones. Since the pool descriptor in question may very well only exist in a clone, I can't use this. Is there another way?

Thanks,
--Patrick

Harmen van der Spek wrote:

Hi Patrick,

That's right. DSNodes are coupled to the original function. For function clones, you first need
to get the original function, and then use the DSNode from that function. FuncInfo
contains the information if a function is a clone and what the original function is.

If you want to find the corresponding DSNode for some instruction, you must call

PA::FuncInfo::MapValueToOriginal( value )

Then you can get the DSNode from the DSGraph:
  
    llvm::DSNodeHandle handle = _dsg->getNodeForValue(origVal);
    DSNode *node = handle.getNode();

origVal is obtained by calling MapValueToOriginal on a cloned Value.

All those mappings are quite confusing. I've been thinking about splitting Pool allocation in two phases,
one in which the clones are generated (which should be internal functions) and then, instead of maintaining all these mappings, just
rerun Top-Down DSA on that result. In that case, it would be much easier to find DSNodes. Anyway, this was just
a thought, I've not really tried anything like that.

Harmen

Thanks for all your help so far.

My problem is that what I have are the pool descriptors, which I by traversing the uses of poolinit and accessing the first argument of each call. I need to find the DSNode (in the original function) to which this pool descriptor corresponds. The rub is that this pool descriptor of course does not exist except in the clone.

If I call getFuncInfo(), I get a NULL pointer. getFuncInfoOrClone() returns the original function's FuncInfo structure, but this function's DSNode <-> PoolDescriptor mapping will not have my pool descriptor in it because my pool descriptor only existed in the clone. I'm fine with the DSNode being the original function's DSNode -- in fact, I need that -- but I'm really at a loss as to how to get out of this catch-22.

--Patrick

Thanks for all your help so far.

My problem is that what I have are the pool descriptors, which I by
traversing the uses of poolinit and accessing the first argument of each
call. I need to find the DSNode (in the original function) to which
this pool descriptor corresponds. The rub is that this pool descriptor
of course does not exist except in the clone.

If I call getFuncInfo(), I get a NULL pointer. getFuncInfoOrClone()
returns the original function's FuncInfo structure, but this function's
DSNode <-> PoolDescriptor mapping will not have my pool descriptor in it
because my pool descriptor only existed in the clone. I'm fine with the
DSNode being the original function's DSNode -- in fact, I need that --
but I'm really at a loss as to how to get out of this catch-22.

PoolDescriptors do not have DSNodes in any meaningful sense, so if
you are trying to lookup the PD pointer you will have problems. PA
adds the pointer to the DSGraph, but it doesn't corrospond to it's
logical contents at all. FuncInfo contains a map which should contain
all DSNode->PD mappings, which you can invert.

Andrew

You would have to rerun the entire DSA stack, not just TD (and a
number of PA clients don't want TD). Your problem is then the
PoolDescriptors will masquarade as normal pointers, so you already
have to maintain some mapping of Expected DSNode -> Expected PA and
hope it is stable (DSA didn't not use to be deterministic (I think
because the type merging code was not symetric)).

I would argue (and have partially implemented) that the main problem
is that PA clients must be DSA clients. PA should import and make
available a sane set of information about each pool such that going to
the DSNodes would not be useful. Then a PA client would never have to
manage that mapping. Further, PA is really 2 transforms in one: the
first associates PoolDescriptors with nodes creating a runtime
representation of the points-to graph; the second uses that mapping to
change heap structure (hijacking the PoolDescriptors to be allocation
pools (which is a fine thing to do with them)). I've split the two up
(well I haven't implemented the second over the first yet) and
currently have a pass that just does the transform and should, when it
is done, free clients from having to know about DSA.

Andrew

Patrick Simmons wrote:

Thanks for all your help so far.

My problem is that what I have are the pool descriptors, which I by traversing the uses of poolinit and accessing the first argument of each call. I need to find the DSNode (in the original function) to which this pool descriptor corresponds. The rub is that this pool descriptor of course does not exist except in the clone.
  
One way to do this might be to search for a use of the pool within the function (such as a poolalloc() or a function call that passes the pool). You can then find a pointer that belongs to the pool, map that pointer from the clone back to the original function, and then look up its DSNode.

However, before you do that, can you tell us why you need this functionality? Since things are getting complicated, it may be worthwhile to first understand if your approach of mapping Pools to the DSNodes from which they were created is the correct approach for what you are doing. If, for example, you need to know whether a pool is a type-homogeneous, then an easier method would be to modify poolinit() to pass an argument containing DSNode information (such as a flag indicating type-homogeneity).

-- John T.

I've thought of trying to do that, but that solution is really too ugly to live. I need this because NSPASS (my project) runs after DSA but before pool allocation and generates a list of DSNodes with a special property. Then, TPPA (still my project) needs to iterate over every pool, which it does by iterating over the uses of poolinit, and figure out whether that pool needs to be annotated in a special way based on whether the DSNode from whence it came had the special property. To do this, it needs to convert the pool descriptor it gets by taking the first argument of poolinit back into the DSNode it used to be and then check the information from NSPASS to see whether it needs a special annotation.

Is there a better way to do this?

Thanks,
--Patrick

Patrick Simmons wrote:

  

Patrick Simmons wrote:
    

Thanks for all your help so far.

My problem is that what I have are the pool descriptors, which I by traversing the uses of poolinit and accessing the first argument of each call. I need to find the DSNode (in the original function) to which this pool descriptor corresponds. The rub is that this pool descriptor of course does not exist except in the clone.
      

One way to do this might be to search for a use of the pool within the function (such as a poolalloc() or a function call that passes the pool). You can then find a pointer that belongs to the pool, map that pointer from the clone back to the original function, and then look up its DSNode.

However, before you do that, can you tell us why you need this functionality? Since things are getting complicated, it may be worthwhile to first understand if your approach of mapping Pools to the DSNodes from which they were created is the correct approach for what you are doing. If, for example, you need to know whether a pool is a type-homogeneous, then an easier method would be to modify poolinit() to pass an argument containing DSNode information (such as a flag indicating type-homogeneity).

-- John T.
    
I've thought of trying to do that, but that solution is really too ugly to live. I need this because NSPASS (my project) runs after DSA but before pool allocation and generates a list of DSNodes with a special property. Then, TPPA (still my project) needs to iterate over every pool, which it does by iterating over the uses of poolinit, and figure out whether that pool needs to be annotated in a special way based on whether the DSNode from whence it came had the special property. To do this, it needs to convert the pool descriptor it gets by taking the first argument of poolinit back into the DSNode it used to be and then check the information from NSPASS to see whether it needs a special annotation.

Is there a better way to do this?
  
The pool allocation passes already have a function called getPool() that should return the pool associated with a DSNode. Assuming that this function works for the Automatic Pool Allocation pass (and if it doesn't, we as a group can fix it), then you can do the following:

For every special DSNode
    Pool = getPool (special DSNode)
    Scan through uses of Pool to find the call to poolinit
    Modify the call to poolinit

This algorithm may not be as efficient as the one you described (because you'll be searching multiple use-def chains and, in some cases, will be searching them for a poolinit that doesn't exist). However, the algorithm should work, and the efficiency may still be good.

Another option would be to enhance the pool allocation passes to map a pool back to the DSNode for which it was created. I don't think this would be too difficult to do.

-- John T.