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

[4lbert C0hen via llvm-dev]

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=10.1.1.29.5704&rep=rep1&type=pdf
Yes, this is one of the must-read papers for any polyhedral compilation 
work!

The following is a generalization to approximate array dataflow (journal 
extension of a POPL 1998 paper)
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.26.6376&rep=rep1&type=pdf
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):
http://impact.gforge.inria.fr/impact2016

> [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
http://conf.researchr.org/event/POPL-2016/popl-2016-papers-smo-an-integrated-approach-to-intra-array-and-inter-array-storage-optimization
http://dl.acm.org/citation.cfm?id=2837636

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

- CC 2016, Darte, Isoard, Yuki
https://www.conference-publishing.com/list.php?Event=CC16
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.

Albert