llvm dev - Feb 2013 - [LLVMdev] Passes for object memory footprint / data-direction

Hi,

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.


Best regards,
Sebastian

----- Original Message -----
> From: "Sebastian Dreßler" <dressler at zib.de>
> To: llvmdev at cs.uiuc.edu
> Sent: Monday, February 18, 2013 7:49:39 AM
> Subject: [LLVMdev] Passes for object memory footprint / data-direction
> 
> Hi,
> 
> 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?

 -Hal
> 
> 
> Best regards,
> Sebastian
> 
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

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/