llvm dev - Sep 2013 - [LLVMdev] [Polly] Move Polly's execution later

Hi Tobias,


I am trying to move Polly later.


LLVM provides some predefined ExtensionPointTy:
    EP_EarlyAsPossible,
    EP_ModuleOptimizerEarly,
    EP_LoopOptimizerEnd,
    EP_ScalarOptimizerLate,
    ...


Currently Polly uses "EP_EarlyAsPossible" to run as early as possible.
As what you suggested:
>Instead of removing canonicalization passes, I believe we may want to 
>move Polly to a later place in the pass manager. Possibly at the 
>beginning of the loop optimizer right before PM.add(createLoopRotatePass());
I want to move it to the point immediate after someone Loop optimization pass,
e.g. MPM.add(createLoopRotatePass()).  However no predefined ExtensionPointTy is
available for this purpose. Instead, the "EP_ModuleOptimizerEarly"
would move Polly before all loop optimization passes.


In my option, there are two solutions: one is to use
"EP_ModuleOptimizerEarly" (only modify the
tool/polly/lib/RegisterPasses.cpp) to move Polly before all loop optimization
passes; the other is to add a new ExtensionPointTy, e.g.
"EP_LoopRotateEnd" and move Polly exactly immediate after the
"LoopRotate" pass (need to modify tool/polly/lib/RegisterPasses.cpp,
include/llvm/Transforms/IPO/PassManagerBuilder.h and
lib/Transforms/IPO/PassManagerBuilder.cpp). We can use the second way to
investigate other points to start Polly.


Is my understanding correct? Do you have any further suggestion?


Thanks,
Star Tan 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130919/a3e2ba34/attachment.html>

On 09/19/2013 04:46 PM, Star Tan wrote:
> Hi Tobias,
>
>
> I am trying to move Polly later.
>
>
> LLVM provides some predefined ExtensionPointTy:
>      EP_EarlyAsPossible,
>      EP_ModuleOptimizerEarly,
>      EP_LoopOptimizerEnd,
>      EP_ScalarOptimizerLate,
>      ...
>
>
> Currently Polly uses "EP_EarlyAsPossible" to run as early as
possible.  As what you suggested:
>> Instead of removing canonicalization passes, I believe we may want to
>> move Polly to a later place in the pass manager. Possibly at the
>> beginning of the loop optimizer right before
PM.add(createLoopRotatePass());
> I want to move it to the point immediate after someone Loop optimization
pass, e.g. MPM.add(createLoopRotatePass()).  However no predefined
ExtensionPointTy is available for this purpose. Instead, the
"EP_ModuleOptimizerEarly" would move Polly before all loop
optimization passes.
>
>
> In my option, there are two solutions: one is to use
"EP_ModuleOptimizerEarly" (only modify the
tool/polly/lib/RegisterPasses.cpp) to move Polly before all loop optimization
passes; the other is to add a new ExtensionPointTy, e.g.
"EP_LoopRotateEnd" and move Polly exactly immediate after the
"LoopRotate" pass (need to modify tool/polly/lib/RegisterPasses.cpp,
include/llvm/Transforms/IPO/PassManagerBuilder.h and
lib/Transforms/IPO/PassManagerBuilder.cpp). We can use the second way to
investigate other points to start Polly.
>
>
> Is my understanding correct? Do you have any further suggestion?
Yes, fully correct. I would play with solution two. Why would you add 
Polly after the loop rotate pass?

I would possibly add it at the beginning of the loop optimizer (right 
before the loop rotation pass) possibly experimenting with a new 
extension point called EP_LoopOptimizerBegin.

Cheers,
Tobias

Hi Tobias,
At 2013-09-19 22:59:25,"Tobias Grosser" <tobias at grosser.es>
wrote:
>On 09/19/2013 04:46 PM, Star Tan wrote:
>> Hi Tobias,
>>
>>
>> I am trying to move Polly later.
>>
>>
>> LLVM provides some predefined ExtensionPointTy:
>>      EP_EarlyAsPossible,
>>      EP_ModuleOptimizerEarly,
>>      EP_LoopOptimizerEnd,
>>      EP_ScalarOptimizerLate,
>>      ...
>>
>>
>> Currently Polly uses "EP_EarlyAsPossible" to run as early as
possible.  As what you suggested:
>>> Instead of removing canonicalization passes, I believe we may want
to
>>> move Polly to a later place in the pass manager. Possibly at the
>>> beginning of the loop optimizer right before
PM.add(createLoopRotatePass());
>> I want to move it to the point immediate after someone Loop
optimization pass, e.g. MPM.add(createLoopRotatePass()).  However no predefined
ExtensionPointTy is available for this purpose. Instead, the
"EP_ModuleOptimizerEarly" would move Polly before all loop
optimization passes.
>>
>>
>> In my option, there are two solutions: one is to use
"EP_ModuleOptimizerEarly" (only modify the
tool/polly/lib/RegisterPasses.cpp) to move Polly before all loop optimization
passes; the other is to add a new ExtensionPointTy, e.g.
"EP_LoopRotateEnd" and move Polly exactly immediate after the
"LoopRotate" pass (need to modify tool/polly/lib/RegisterPasses.cpp,
include/llvm/Transforms/IPO/PassManagerBuilder.h and
lib/Transforms/IPO/PassManagerBuilder.cpp). We can use the second way to
investigate other points to start Polly.
>>
>> Is my understanding correct? Do you have any further suggestion?
>
>Yes, fully correct. I would play with solution two. Why would you add 
>Polly after the loop rotate pass?
Forgot it. I just wanted to give an immature example to show how to move Polly
to other points.
>I would possibly add it at the beginning of the loop optimizer (right 
>before the loop rotation pass) possibly experimenting with a new 
>extension point called EP_LoopOptimizerBegin.
>
Thanks for your advice. I have tried to move Polly immediately before the loop
rotation pass. The temporary patch file can be reached on
http://llvm.org/bugs/attachment.cgi?id=11262.
First of all, I evaluated Polly's canonicalization passes based on this
patch file. Results are posted on http://188.40.87.11:8000, which contains two
new runs:
PollyNoGen_loop (run 56): move polly later but keep all polly canonicalization
passes;
PollyNoGen_loop_nocan(run57): move polly later and delete all polly
canonicalization passes;
Comparison is shown on 
http://188.40.87.11:8000/db_default/v4/nts/57?compare_to=56&baseline=56. It
seems that even we move polly later, those canonicalization passes still have
significant impact on the final execution-time performance.
A very bad news is that Polly would produce wrong code if we move Polly right
immediately before the loop rotate pass. Many benchmarks in LLVM testsuite would
fail in execution. I constructed a relatively simple testcase for this bug as
shown on http://llvm.org/bugs/show_bug.cgi?id=17323. The key problem is Polly
would produce wrong basic blocks like this:
polly.loop_header27:                              ; preds = %vector.body,
%polly.loop_header27
  br label %polly.loop_header27
For your information, the source code is posted on
http://llvm.org/bugs/attachment.cgi?id=11263 and the LLVM IR code is posted on
http://llvm.org/bugs/attachment.cgi?id=11264
I have not yet found out why Polly produces such wrong code.  However, maybe I
should also investigate other points where we can move Polly. Do you have any
suggestion?
Best,
Star Tan
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130922/eda59b06/attachment.html>