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

From: "Sebastian Dre├čler" <dressler@zib.de>
To: llvmdev@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

Hal,

[...]

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

Hi Sebastian,

Hi Duncan,

Duncan Sands wrote

I think there's an old bug report requesting per-parameter
readonly/readnone
attributes. This would be pretty useful. It sounds like you've
implemented a
pass that determines them. Maybe you could integrate it into the existing
FunctionAttrs pass, and have it generate such per parameter attributes.

I'll have a look on this pass and port my implementation. Is there a bug ID?
A quick search over Bugzilla did not reveal anything.

Best regards,
Sebastian