llvm dev - Oct 2011 - [LLVMdev] How to make Polly ignore some non-affine memory accesses

Hi Tobias,

thanks for the answer. I'll try to give a look to the code you pointed
me to , and I'll try to make the modification myself. I'm new to LLVM
and Polly, but the code of both seem clean and understandable, so I
hope to be able to do it myself. In case I'll ask here for support :)

Marcello

2011/10/1 Tobias Grosser <tobias at grosser.es>:
> On 10/01/2011 03:26 PM, Marcello Maggioni wrote:
>>
>> Hello everyone,
>>
>> I'm trying to use LLVM+Polly to obtain a polyhedral representation
of
>> some loops to use later for passes I want to implement, but seems like
>> Polly will stop when reaching any statement that has non-affine access
>> functions of the loop bounds discarding the whole SCoP entirely.
>>
>> What I would like to achieve is still getting some information for the
>> statements that , instead, have affine access functions, practically
>> "ignoring" the non-affine ones.
>>
>> There is a way to do such a thing?
>
> Hi Marcello,
>
> this is not yet integrated into Polly, but a very valuable extension which
I
> planned to integrate myself. In case you want to give it a try,
> I am very glad to help you.
>
> Basically, what you want is to adapt lib/Analysis/ScopDetection.cpp to
> not reject non-affine constructs. In lib/Analysis/ScopInfo.cpp we would
> need to adapt the translation into the polyhedral description. Instead of
> creating a map defining an affine must access (such as
> Stmt[i,j] -> A[2 * i + j]), we create a map that defines a may access to
all
> elements of the corresponding array. Something like 'Stmt[i,j] ->
A[x]'.
>
> Cheers
> Tobi
>
>

Hi, I'd like to ask another thing about Polly and SCoP discarding.

I've noticed that Polly discards quite simple loops like:

for (int i = 1; i < 1000; i++) {}

or

for (int i= 0; i < 1000; i+=2) {}

is this an intended behavior or there is some way to make it accept
these kind of loops ?

Thanks,
Marcello

2011/10/3 Marcello Maggioni <hayarms at
gmail.com>:
> Hi Tobias,
>
> thanks for the answer. I'll try to give a look to the code you pointed
> me to , and I'll try to make the modification myself. I'm new to
LLVM
> and Polly, but the code of both seem clean and understandable, so I
> hope to be able to do it myself. In case I'll ask here for support :)
>
> Marcello
>
> 2011/10/1 Tobias Grosser <tobias at grosser.es>:
>> On 10/01/2011 03:26 PM, Marcello Maggioni wrote:
>>>
>>> Hello everyone,
>>>
>>> I'm trying to use LLVM+Polly to obtain a polyhedral
representation of
>>> some loops to use later for passes I want to implement, but seems
like
>>> Polly will stop when reaching any statement that has non-affine
access
>>> functions of the loop bounds discarding the whole SCoP entirely.
>>>
>>> What I would like to achieve is still getting some information for
the
>>> statements that , instead, have affine access functions,
practically
>>> "ignoring" the non-affine ones.
>>>
>>> There is a way to do such a thing?
>>
>> Hi Marcello,
>>
>> this is not yet integrated into Polly, but a very valuable extension
which I
>> planned to integrate myself. In case you want to give it a try,
>> I am very glad to help you.
>>
>> Basically, what you want is to adapt lib/Analysis/ScopDetection.cpp to
>> not reject non-affine constructs. In lib/Analysis/ScopInfo.cpp we would
>> need to adapt the translation into the polyhedral description. Instead
of
>> creating a map defining an affine must access (such as
>> Stmt[i,j] -> A[2 * i + j]), we create a map that defines a may
access to all
>> elements of the corresponding array. Something like 'Stmt[i,j]
-> A[x]'.
>>
>> Cheers
>> Tobi
>>
>>
>

On 10/07/2011 03:25 PM, Marcello Maggioni wrote:
> Hi, I'd like to ask another thing about Polly and SCoP discarding.
>
> I've noticed that Polly discards quite simple loops like:
>
> for (int i = 1; i<  1000; i++) {}
>
> or
>
> for (int i= 0; i<  1000; i+=2) {}
>
> is this an intended behavior or there is some way to make it accept
> these kind of loops?
Hi Marcello,

can you provide complete test cases and explain how you run Polly. These 
loop constructs contain nothing Polly cannot handle, but other parts of 
your programs may block a detailed analysis. Furthermore, Polly relies 
on LLVM preparing passes to canonicalize the code. If they
are not run beforehand than Polly will hardly detect any loops.

In your case I propose you attach the complete C and LLVM-IR files and 
explain how you run Polly. I am sure I can help you with this.

Tobi

I add also the output of these commands:

[hades at artemis examples]$ ./compile_ex.sh super_simple_loop
Printing analysis 'Polly - Detect Scops in functions' for function
'main':

[hades at artemis examples]$

modifying it in :

 #include <stdio.h>

 int main()
 {
         int A[1024];
         int j, k=10;
         for (j = 0; j < 1024; j++)
                 A[j] = k;

       return 0;
}

gives:

[hades at artemis examples]$ ./compile_ex.sh super_simple_loop
Printing analysis 'Polly - Detect Scops in functions' for function
'main':
Valid Region for Scop: %1 => %5

[hades at artemis examples]$

2011/10/7 Marcello Maggioni <hayarms at
gmail.com>:
> Hi,
>
> for example this loop:
>
>  #include <stdio.h>
>
>  int main()
>  {
>          int A[1024];
>          int j, k=10;
>          for (j = 1; j < 1024; j++)
>                  A[j] = k;
>
>        return 0;
> }
>
> run with:
>
> #!/bin/bash
> source ../set_path.source
> clang -S -emit-llvm $1.c -o $1.s
> opt -S -mem2reg -loop-simplify -indvars $1.s > $1.preopt.ll
> opt -load ${PATH_TO_POLLY_LIB}/LLVMPolly.so -polly-detect -analyze
$1.preopt.ll
>
> Using the instructions found on the Polly website.
>
>
> 2011/10/7 Tobias Grosser <tobias at grosser.es>:
>> On 10/07/2011 03:25 PM, Marcello Maggioni wrote:
>>>
>>> Hi, I'd like to ask another thing about Polly and SCoP
discarding.
>>>
>>> I've noticed that Polly discards quite simple loops like:
>>>
>>> for (int i = 1; i<  1000; i++) {}
>>>
>>> or
>>>
>>> for (int i= 0; i<  1000; i+=2) {}
>>>
>>> is this an intended behavior or there is some way to make it accept
>>> these kind of loops?
>>
>> Hi Marcello,
>>
>> can you provide complete test cases and explain how you run Polly.
These
>> loop constructs contain nothing Polly cannot handle, but other parts of
your
>> programs may block a detailed analysis. Furthermore, Polly relies on
LLVM
>> preparing passes to canonicalize the code. If they
>> are not run beforehand than Polly will hardly detect any loops.
>>
>> In your case I propose you attach the complete C and LLVM-IR files and
>> explain how you run Polly. I am sure I can help you with this.
>>
>> Tobi
>>
>

On 10/07/2011 03:43 PM, Marcello Maggioni wrote:
> 2011/10/7 Marcello Maggioni<hayarms at gmail.com>:
>> Hi,
>>
>> for example this loop:
>>
>>   #include<stdio.h>
>>
>>   int main()
>>   {
>>           int A[1024];
>>           int j, k=10;
>>           for (j = 1; j<  1024; j++)
>>                   A[j] = k;
>>
>>         return 0;
>> }
>>
>> run with:
>>
>> #!/bin/bash
>> source ../set_path.source
>> clang -S -emit-llvm $1.c -o $1.s
>> opt -S -mem2reg -loop-simplify -indvars $1.s>  $1.preopt.ll
>> opt -load ${PATH_TO_POLLY_LIB}/LLVMPolly.so -polly-detect -analyze
$1.preopt.ll
>>
>> Using the instructions found on the Polly website.
There are two reasons why it does not work with these instructions

1. Not the right preoptimization passes

The instructions on the Polly website use a very short sequence of 
preoptimization passes that just matches the simple example presented. 
To optimize real world programs that are not 100% standard you need a 
larger sequence of prepasses. In your example the loop iv does not start 
at '0' so further canonicalication is required.

The minimal sequence of optimization passes for your example is:
opt -mem2reg -instcombine -simplifycfg -loop-rotate -indvars

2. -enable-iv-rewrite

LLVM recently disabled by default the induction variable rewrite. This 
feature is necessary for the Polly preoptimizations. Hence, you need to 
reenable it with the above flag during preoptimization.

-> opt -mem2reg -instcombine -simplifycfg -loop-rotate -indvars 
-enable-iv-rewrite test.s -S > test.preopt.ll



In general I use an even longer sequence of preoptimizations. This 
sequence is built directly into Polly and is defined in 
RegisterPasses.cpp. To get the corresponding opt flags you can load 
Polly into clang and use the following command (-O3 is important):

 > clang test.c -O3 -Xclang -load -Xclang lib/LLVMPolly.so -mllvm 
-debug-pass=Arguments
Pass Arguments: -targetdata -no-aa -targetlibinfo -tbaa -basicaa 
-preverify -domtree -verify -mem2reg -instcombine -simplifycfg 
-tailcallelim -simplifycfg -reassociate -domtree -loops -loop-simplify 
-lcssa -loop-rotate -instcombine -scalar-evolution -loop-simplify -lcssa 
-indvars -polly-prepare -postdomtree -domfrontier -regions 
-polly-region-simplify -scalar-evolution -loop-simplify -lcssa -indvars 
-postdomtree -domfrontier -regions -polly-detect -polly-independent 
-polly-analyze-ir -polly-scops -polly-dependences -polly-optimize-isl 
-polly-cloog -polly-codegen -simplifycfg -domtree -scalarrepl -early-cse 
-lower-expect

If you remove the first pass (-targetdata) and the passes after 
-polly-detect you get the list of preparing transformations (and the 
analysis they need).

Today I also further improved clang support. With the patch: 'Fix 
parsing of command line options for LLVM plugins' as posted today on 
cfe-commits, you can get the following new features:

1. Optimize a .c file automatically

Run: clang test.c -O3 -Xclang -load -Xclang lib/LLVMPolly.so -mllvm 
-enable-polly-viewer -mllvm -enable-iv-rewrite

Polly + all the preparing transformations are automatically scheduled.

2. Graphical SCoP viewer

Run: clang test.c -O3 -Xclang -load -Xclang lib/LLVMPolly.so -mllvm 
-enable-polly-viewer -mllvm -enable-iv-rewrite

Show for every function a graphviz graph that highlights the detected
SCoPs. Here we also show for every non-scop region, the reason why it
is not a SCoP. (This needs graphviz installed when run LLVM configure is 
run. You may also consider to install xdot.py [1] as a more convenient 
.dot file viewer. xdot.py will used automatically, if it is
in the PATH during 'configure' of LLVM)

3. OpenMP:

RUN: clang test.c -O3 -Xclang -load -Xclang lib/LLVMPolly.so -mllvm 
-enable-polly-openmp -lgomp

This will automatically OpenMP parallelize your code.

(Remember for all this LLVM/Clang/Polly need to be built together such
that they are in sync and .so loading works)

Cheers
Tobi

[1] http://code.google.com/p/jrfonseca/wiki/XDot