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

I was trying the new feature you introduce about printing out the
graphs, so I updated my version of llvm/clang/polly synchronizing them
to the last version, but I get this error launching clang (also , I
recently switched to MacOS X for development):

$ clang not_so_simple_loop.c -O3 -Xclang -load -Xclang
${PATH_TO_POLLY_LIB}/LLVMPolly.dylib -mllvm -enable-polly-viewer
-mllvm -enable-iv-rewrite

error: unable to load plugin
'/Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib':
'dlopen(/Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib,
9): Symbol not found: __ZN4llvm10RegionInfo2IDE
  Referenced from:
/Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib
  Expected in: flat namespace
 in /Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib'
clang (LLVM option parsing): Unknown command line argument
'-enable-polly-viewer'.  Try: 'clang (LLVM option parsing)
-help'
clang (LLVM option parsing): Did you mean '-enable-ppc-preinc'?

$ clang -v
clang version 3.1 (trunk 142724)
Target: x86_64-apple-darwin11.2.0
Thread model: posix

Seems like it tries to load a symbol that it doesn't find ...
I have synchronized all clang/llvm/polly to the latest version and I
compiled them all together. Loading polly with "opt" works strangely
... :

opt -S -load ${PATH_TO_POLLY_LIB}/LLVMPolly.dylib -mem2reg -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  -loop-simplify -indvars  -enable-iv-rewrite
not_so_simple_loop.s

strange ...



2011/10/8 Tobias Grosser <tobias at grosser.es>:
> 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
>
>
>
>

On 10/22/2011 08:41 AM, Marcello Maggioni wrote:
> I was trying the new feature you introduce about printing out the
> graphs, so I updated my version of llvm/clang/polly synchronizing them
> to the last version, but I get this error launching clang (also , I
> recently switched to MacOS X for development):
>
> $ clang not_so_simple_loop.c -O3 -Xclang -load -Xclang
> ${PATH_TO_POLLY_LIB}/LLVMPolly.dylib -mllvm -enable-polly-viewer
> -mllvm -enable-iv-rewrite
I documented the use of Polly in clang on a new website:
http://polly.grosser.es/example_load_Polly_into_clang.html
> error: unable to load plugin
>
'/Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib':
>
'dlopen(/Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib,
> 9): Symbol not found: __ZN4llvm10RegionInfo2IDE
>    Referenced from:
> /Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib
>    Expected in: flat namespace
>   in
/Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib'
> clang (LLVM option parsing): Unknown command line argument
> '-enable-polly-viewer'.  Try: 'clang (LLVM option parsing)
-help'
> clang (LLVM option parsing): Did you mean '-enable-ppc-preinc'?
>
> $ clang -v
> clang version 3.1 (trunk 142724)
> Target: x86_64-apple-darwin11.2.0
> Thread model: posix
>
> Seems like it tries to load a symbol that it doesn't find ...
> I have synchronized all clang/llvm/polly to the latest version and I
> compiled them all together. Loading polly with "opt" works
strangely
> ... :
>
> opt -S -load ${PATH_TO_POLLY_LIB}/LLVMPolly.dylib -mem2reg -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  -loop-simplify -indvars  -enable-iv-rewrite
> not_so_simple_loop.s
>
> strange ...
Very strange. I have seen such problems previously and they were often
related to enabling rtti (runtime type info) or exceptions in Polly, but 
no clang or the other way around. I am not sure if this is the case her.

Another possibility is that clang does not use the RegionInfo stuff and
it gets dead code eliminated.

Can you run the following commands on the clang binary:

ldd /path/to/clang
objdump -xC /path/to/clang | grep RegionInfo

Can you also run them on the opt tool?

Are you building with cmake or autoconf? Do you use 
--enable-shared/BUILD_SHARED_LIBS. In case you do/don't it would be 
interesting to try to switch. Especially using shared libraries may help 
as it may block some dead code elimination.

Cheers
Tobi

On 10/23/2011 02:31 PM, Tobias Grosser wrote:
> On 10/22/2011 08:41 AM, Marcello Maggioni wrote:
[..]
>> Seems like it tries to load a symbol that it doesn't find ...
>> I have synchronized all clang/llvm/polly to the latest version and I
>> compiled them all together. Loading polly with "opt" works
strangely
>> ... :
>>
>> opt -S -load ${PATH_TO_POLLY_LIB}/LLVMPolly.dylib -mem2reg -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  -loop-simplify -indvars  -enable-iv-rewrite
>> not_so_simple_loop.s
>>
>> strange ...
> Very strange. I have seen such problems previously and they were often
> related to enabling rtti (runtime type info) or exceptions in Polly, but
> no clang or the other way around. I am not sure if this is the case her.
>
> Another possibility is that clang does not use the RegionInfo stuff and
> it gets dead code eliminated.
I am even more convinced this is the case. Can you try the attached 
patch and report if it works for you?

Cheers
Tobi
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Add-LinkAllPasses-to-clang.patch
Type: text/x-diff
Size: 901 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111023/bda7aa18/attachment.patch>

otool is equivalent to objtool on macosx

MacBook-Pro-di-Marcello:llvm-build Kariddi$ otool -tV
../git-prefix/bin/clang|grep RegionInfo
MacBook-Pro-di-Marcello:llvm-build Kariddi$

MacBook-Pro-di-Marcello:llvm-build Kariddi$ otool -tV
../git-prefix/bin/opt|grep RegionInfo
00000001000152d0	callq	__ZN4llvm20createRegionInfoPassEv
00000001002bc65c	callq	__ZN4llvm24initializeRegionInfoPassERNS_12PassRegistryE
__ZN4llvm6RegionC1EPNS_10BasicBlockES2_PNS_10RegionInfoEPNS_13DominatorTreeEPS0_:
000000010039e138	callq
__ZN4llvm6RegionC2EPNS_10BasicBlockES2_PNS_10RegionInfoEPNS_13DominatorTreeEPS0_
__ZN4llvm6RegionC2EPNS_10BasicBlockES2_PNS_10RegionInfoEPNS_13DominatorTreeEPS0_:
000000010039f3b3	callq	__ZNK4llvm10RegionInfo12getRegionForEPNS_10BasicBlockE
__ZNK4llvm10RegionInfo12getRegionForEPNS_10BasicBlockE:
000000010039fc34	callq
__ZN4llvm10RegionInfo12setRegionForEPNS_10BasicBlockEPNS_6RegionE
__ZN4llvm10RegionInfo12setRegionForEPNS_10BasicBlockEPNS_6RegionE:
00000001003a022e	callq	__ZNK4llvm10RegionInfo12getRegionForEPNS_10BasicBlockE
00000001003a02f7	callq
__ZN4llvm6RegionC1EPNS_10BasicBlockES2_PNS_10RegionInfoEPNS_13DominatorTreeEPS0_
00000001003a050e	callq
__ZN4llvm6RegionC1EPNS_10BasicBlockES2_PNS_10RegionInfoEPNS_13DominatorTreeEPS0_
__ZNK4llvm10RegionInfo19isCommonDomFrontierEPNS_10BasicBlockES2_S2_:
__ZNK4llvm10RegionInfo8isRegionEPNS_10BasicBlockES2_:
00000001003a0edf	callq
__ZNK4llvm10RegionInfo19isCommonDomFrontierEPNS_10BasicBlockES2_S2_
__ZNK4llvm10RegionInfo14insertShortCutEPNS_10BasicBlockES2_PNS_8DenseMapIS2_S2_NS_12DenseMapInfoIS2_EES5_EE:
__ZNK4llvm10RegionInfo14getNextPostDomEPNS_15DomTreeNodeBaseINS_10BasicBlockEEEPNS_8DenseMapIPS2_S6_NS_12DenseMapInfoIS6_EES8_EE:
__ZNK4llvm10RegionInfo15isTrivialRegionEPNS_10BasicBlockES2_:
__ZN4llvm10RegionInfo16updateStatisticsEPNS_6RegionE:
__ZN4llvm10RegionInfo12createRegionEPNS_10BasicBlockES2_:
00000001003a1437	callq
__ZNK4llvm10RegionInfo15isTrivialRegionEPNS_10BasicBlockES2_
00000001003a14a5	callq
__ZN4llvm6RegionC1EPNS_10BasicBlockES2_PNS_10RegionInfoEPNS_13DominatorTreeEPS0_
00000001003a1527	callq	__ZN4llvm10RegionInfo16updateStatisticsEPNS_6RegionE
__ZN4llvm10RegionInfo20findRegionsWithEntryEPNS_10BasicBlockEPNS_8DenseMapIS2_S2_NS_12DenseMapInfoIS2_EES5_EE:
00000001003a15e9	callq
__ZNK4llvm10RegionInfo14getNextPostDomEPNS_15DomTreeNodeBaseINS_10BasicBlockEEEPNS_8DenseMapIPS2_S6_NS_12DenseMapInfoIS6_EES8_EE
00000001003a162a	callq	__ZNK4llvm10RegionInfo8isRegionEPNS_10BasicBlockES2_
00000001003a1648	callq	__ZN4llvm10RegionInfo12createRegionEPNS_10BasicBlockES2_
00000001003a16c6	callq
__ZNK4llvm10RegionInfo14insertShortCutEPNS_10BasicBlockES2_PNS_8DenseMapIS2_S2_NS_12DenseMapInfoIS2_EES5_EE
__ZN4llvm10RegionInfo14scanForRegionsERNS_8FunctionEPNS_8DenseMapIPNS_10BasicBlockES5_NS_12DenseMapInfoIS5_EES7_EE:
00000001003a17d8	callq
__ZN4llvm10RegionInfo20findRegionsWithEntryEPNS_10BasicBlockEPNS_8DenseMapIS2_S2_NS_12DenseMapInfoIS2_EES5_EE
__ZN4llvm10RegionInfo16getTopMostParentEPNS_6RegionE:
__ZN4llvm10RegionInfo16buildRegionsTreeEPNS_15DomTreeNodeBaseINS_10BasicBlockEEEPNS_6RegionE:

.... lots of other stuff.

Now I'll try the patch you posted and report, thanks :)

2011/10/23 Tobias Grosser <tobias at grosser.es>:
> On 10/22/2011 08:41 AM, Marcello Maggioni wrote:
>>
>> I was trying the new feature you introduce about printing out the
>> graphs, so I updated my version of llvm/clang/polly synchronizing them
>> to the last version, but I get this error launching clang (also , I
>> recently switched to MacOS X for development):
>>
>> $ clang not_so_simple_loop.c -O3 -Xclang -load -Xclang
>> ${PATH_TO_POLLY_LIB}/LLVMPolly.dylib -mllvm -enable-polly-viewer
>> -mllvm -enable-iv-rewrite
>
> I documented the use of Polly in clang on a new website:
> http://polly.grosser.es/example_load_Polly_into_clang.html
>
>> error: unable to load plugin
>>
'/Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib':
>>
>>
'dlopen(/Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib,
>> 9): Symbol not found: __ZN4llvm10RegionInfo2IDE
>>   Referenced from:
>> /Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib
>>   Expected in: flat namespace
>>  in
>>
/Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib'
>> clang (LLVM option parsing): Unknown command line argument
>> '-enable-polly-viewer'.  Try: 'clang (LLVM option parsing)
-help'
>> clang (LLVM option parsing): Did you mean '-enable-ppc-preinc'?
>>
>> $ clang -v
>> clang version 3.1 (trunk 142724)
>> Target: x86_64-apple-darwin11.2.0
>> Thread model: posix
>>
>> Seems like it tries to load a symbol that it doesn't find ...
>> I have synchronized all clang/llvm/polly to the latest version and I
>> compiled them all together. Loading polly with "opt" works
strangely
>> ... :
>>
>> opt -S -load ${PATH_TO_POLLY_LIB}/LLVMPolly.dylib -mem2reg -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  -loop-simplify -indvars  -enable-iv-rewrite
>> not_so_simple_loop.s
>>
>> strange ...
>
> Very strange. I have seen such problems previously and they were often
> related to enabling rtti (runtime type info) or exceptions in Polly, but no
> clang or the other way around. I am not sure if this is the case her.
>
> Another possibility is that clang does not use the RegionInfo stuff and
> it gets dead code eliminated.
>
> Can you run the following commands on the clang binary:
>
> ldd /path/to/clang
> objdump -xC /path/to/clang | grep RegionInfo
>
> Can you also run them on the opt tool?
>
> Are you building with cmake or autoconf? Do you use
> --enable-shared/BUILD_SHARED_LIBS. In case you do/don't it would be
> interesting to try to switch. Especially using shared libraries may help as
> it may block some dead code elimination.
>
> Cheers
> Tobi
>

Strange , with --enable-shared (I use auto tool by the way ...) it gives:

MacBook-Pro-di-Marcello:examples Kariddi$ ./compile_ex.sh not_so_simple_loop
clang (LLVM option parsing): Unknown command line argument
'-enable-polly-viewer'.  Try: 'clang (LLVM option parsing)
-help'
clang (LLVM option parsing): Did you mean '-enable-polly-vector'?

Seems like it doesn't compile the viewer option ...

2011/10/24 Marcello Maggioni <hayarms at
gmail.com>:
> It works!! :)
>
> I'll try also enable-shared , to see if it's possible to use it
> without the patch and report
>
> 2011/10/24 Tobias Grosser <tobias at grosser.es>:
>> On 10/23/2011 02:31 PM, Tobias Grosser wrote:
>>>
>>> On 10/22/2011 08:41 AM, Marcello Maggioni wrote:
>>
>> [..]
>>>>
>>>> Seems like it tries to load a symbol that it doesn't find
...
>>>> I have synchronized all clang/llvm/polly to the latest version
and I
>>>> compiled them all together. Loading polly with "opt"
works strangely
>>>> ... :
>>>>
>>>> opt -S -load ${PATH_TO_POLLY_LIB}/LLVMPolly.dylib -mem2reg
-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  -loop-simplify -indvars
 -enable-iv-rewrite
>>>> not_so_simple_loop.s
>>>>
>>>> strange ...
>>>
>>> Very strange. I have seen such problems previously and they were
often
>>> related to enabling rtti (runtime type info) or exceptions in
Polly, but
>>> no clang or the other way around. I am not sure if this is the case
her.
>>>
>>> Another possibility is that clang does not use the RegionInfo stuff
and
>>> it gets dead code eliminated.
>>
>> I am even more convinced this is the case. Can you try the attached
patch
>> and report if it works for you?
>>
>> Cheers
>> Tobi
>>
>

On 10/24/2011 11:32 PM, Marcello Maggioni wrote:
> Strange , with --enable-shared (I use auto tool by the way ...) it gives:
>
> MacBook-Pro-di-Marcello:examples Kariddi$ ./compile_ex.sh
not_so_simple_loop
> clang (LLVM option parsing): Unknown command line argument
> '-enable-polly-viewer'.  Try: 'clang (LLVM option parsing)
-help'
> clang (LLVM option parsing): Did you mean '-enable-polly-vector'?
>
> Seems like it doesn't compile the viewer option ...
This error message is because the option name was changed. Try -polly-show.

Furthermore, I plan to commit the change to clang, that solves the 
failure when loading clang. Though it will probably take a day until it 
gets through review.

Cheers
Tobi