[llvm-dev] [GSoC 2016] Implementation of the packing transformation

4lbert C0hen via llvm-dev llvm-dev at lists.llvm.org
Wed Jun 29 01:02:27 PDT 2016

On 06/28/2016 10:53 AM, Roman Gareev wrote:
> 2016-06-27 15:52 GMT+05:00 4lbert C0hen <4lbert.h.c0hen at gmail.com>:
>> Dear Roman and all,
>> Such features would be extremely useful to implement array expansion (scalar
>> and array renaming, privatization with new subscript expressions of higher
>> dimension) and storage mapping optimization (generalizing array
>> contraction). It would be interesting to have these future applications in
>> mind when working on the packing transformation.
> Thank you for the comment! Could you please advise me where I can find
> definitions of array expansion and storage mapping optimization?
> I've found the following papers that are probably related to this: [1]
> and [2]. However, maybe I missed something.
> Refs.:

> [1] - http://citeseerx.ist.psu.edu/viewdoc/download?doi=
Yes, this is one of the must-read papers for any polyhedral compilation 

The following is a generalization to approximate array dataflow (journal 
extension of a POPL 1998 paper)
Rather theoretical, and can be simplified to not make explicit usage of 
transitive closure computations. There is much research to be done in 
the area, with short term applications and implementation in production. 
E.g., on-demand expansion on top of the Live Range Reordering technique 
implemented in isl and PPCG (papers and slides below):

> [2] - https://hal.archives-ouvertes.fr/hal-01257316/document
That one is rather specific to parallel programs and also theoretical.

State of the art:

- POPL 2016

There is a tool available but it has received little publicity yet:
Yet the input is in for of polyhedral sets/maps, not code.

- CC 2016, Darte, Isoard, Yuki
Better heuristic. Currently limited to single-array SMO.

Again, much potential for research and implementation.

I'll be glad to discuss transfer of these results to Polly, as well as 
Alexandre, Uday and others on this list.


More information about the llvm-dev mailing list