[LLVMdev] Passes for object memory footprint / data-direction

[Sebastian Dreßler]

Hal,

On 02/18/2013 06:33 PM, Hal Finkel wrote:
[...]

>> In the past months we were working on two LLVM passes which use
>> data objects of functions as input. One pass computes the 
>> "data-direction" (FORTRAN users know this as intent) of the
>> object, i.e. whether it is read-only, write-only or read-write. The
>> second pass injects code into the LLVM module that, when called at 
>> run-time, computes the memory footprint of the object. This also 
>> works for non-linear objects, e.g. linked lists or instances of 
>> std::map. Dynamic allocation is also supported, with some 
>> limitations.
>> 
>> Our original aim was to use these passes for a scheduler developed
>> in the project we are currently involved (ENHANCE, 
>> http://www.enhance-project.de). However, I'm curios to hear
>> whether these passes could also be useful for other LLVM developers
>> / users.
> 
> Sebastian,
> 
> These sounds quite interesting. Can you explain a little more about
> how they work? How they scale? Do they work with objects used across
> multiple modules? If so, does that require the use of LTO?
> 

Unfortunately I cannot provide too much details, because we've made a
conference submission and it is pending (not Euro-LLVM). However, I'll
try to answer your questions:

Both approaches first construct a graph containing the needed
information. This eases the following analysis a bit and we also want to
re-use them for other "problems".

Direction determination is completely static and basically works by
performing points-to analysis and counting *relevant* loads / stores.
Based on the load / store ratio we then assign a direction label to the
object.

Size determination works by gathering the structure of an object and
creating a function that returns the objects size at run-time. For
scalars it simply returns the bit-width. For classes it returns the sum
of all contained types. For STL containers we implemented iterators to
collect object sizes. Dynamic allocation works by searching for matching
malloc's and new's and extracting their arguments. Size estimation does
not extended the object with metadata but injects functions. There are
also some limitations, for instance re-allocs and overlapping pointers
are not supported at the moment.

We tested several data structures, e.g. sparse matrices, nested classes,
classes with recursion, classes with templates and inheritance and so
on. All these worked well. We have to make measurements regarding the
introduced overhead. If we have results, I'll post them.

Regarding scaling, I currently do not have any reliable information.
Because direction estimation uses points-to analysis, it could be
improved with Steensgaards algorithm or Horwitz-Shapiro to reduce
complexity to near-linear time.

I also never tested cross-module objects, but maybe you could provide a
small example and I'll figure out what happens.


-- Sebastian


-- 
Mit freundlichen Grüßen / Kind regards

Sebastian Dreßler

Zuse Institute Berlin (ZIB)
Takustraße 7
D-14195 Berlin-Dahlem
Germany

dressler at zib.de
Phone: +49 30 84185-261

http://www.zib.de/