[LLVMdev] [Polly] Move Polly's execution later

Star Tan tanmx_star at yeah.net
Sat Sep 21 22:02:38 PDT 2013

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, 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 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?
Star Tan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130922/eda59b06/attachment.html>

More information about the llvm-dev mailing list