llvm dev - Mar 2010 - [LLVMdev] Getting the DSNode from a Pool Descriptor?

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:
> 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:
>   
>> 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
>>     
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

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


On Mar 19, 2010, at 9:14 AM, Patrick Alexander Simmons wrote:
> 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:
>> 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:
>>  
>>> 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
>>>    
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>

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

On 03/19/10 04:10, 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
>
>
> On Mar 19, 2010, at 9:14 AM, Patrick Alexander Simmons wrote:
>
>    
>> 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:
>>      
>>> 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:
>>>
>>>        
>>>> 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
>>>>
>>>>          
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>>        
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>    

-- 
If I'm not here, I've gone out to find myself.  If I get back before I
return, please keep me here.

On Fri, Mar 19, 2010 at 5:10 AM, Harmen van der Spek <hvdspek at liacs.nl>
wrote:
> 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.
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