<div style="line-height:1.7;color:#000000;font-size:14px;font-family:arial">Hello all,<div><br></div><div>I have evaluated the compile-time and execution-time performance of Polly canonicalization passes. Details can be referred to http://188.40.87.11:8000/db_default/v4/nts/recent_activity. There are four runs:</div><div>pollyBasic (run 45): clang -O3 <span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 20px;">-Xclang -load -Xclang LLVMPolly.so</span></div><div>pollyNoGenSCEV (run 44): clang -O3 <span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 20px;">-Xclang -load -Xclang LLVMPolly.so -mllvm -polly -mllvm -polly-codegen-scev</span></div><div>pollyNoGenSCEV_1comb (run 46): same option as pollyNoGenSCEV but remove the first "InstructionCombining" canonicalization pass when generate LLVMPolly.so</div><div><!
div></div><div id="divNeteaseMailCard"></div>pollyNoGenSCEV_nocan (run 47): <span style="font-size: 14px; line-height: 1.7;"> </span><span style="font-size: 14px; line-height: 1.7;">same option as pollyNoGenSCEV but remove all canonicalization passes (actually only keep "</span><span style="white-space: pre-wrap; font-size: 14px; line-height: 1.7;">createCodePreparationPass") </span><span style="font-size: 14px; line-height: 1.7;"> when generate LLVMPolly.so</span></div><div><span style="font-size: 14px; line-height: 1.7;"><br></span></div><div>Fist. let's see the results of removing the first "<span style="font-size: 14px; line-height: 1.7;">InstructionCombining" pass like this:</span></div><div><pre>static void registerCanonicalicationPasses(llvm::PassManagerBase &PM) {
PM.add(llvm::createPromoteMemoryToRegisterPass());
// PM.add(llvm::createInstructionCombiningPass()); //this is the most expensive canonicalization pass for flop benchmark
PM.add(llvm::createCFGSimplificationPass());
PM.add(llvm::createTailCallEliminationPass());
PM.add(llvm::createCFGSimplificationPass());
PM.add(llvm::createReassociatePass());
PM.add(llvm::createLoopRotatePass());
PM.add(llvm::createInstructionCombiningPass());</pre><pre> PM.add(polly::createCodePreparationPass());
}</pre></div><div><span style="font-size: 14px; line-height: 1.7;">Results are shown on </span><a href="http://188.40.87.11:8000/db_default/v4/nts/46?baseline=44&compare_to=44" style="font-size: 14px; line-height: 1.7;">http://188.40.87.11:8000/db_default/v4/nts/46?baseline=44&compare_to=44</a>. As shown in the results, 13 benchmarks have >5% compile-time performance improvements by simply removing the first "<span style="white-space: pre-wrap; font-size: 14px; line-height: 1.7;">createInstructionCombiningPass"</span><span style="font-size: 14px; line-height: 1.7;">. The top 5 benchmarks are listed as follows:</span></div><div><div><span class="Apple-tab-span" style="white-space:pre"> </span>SingleSource/Regression/C++/2003-09-29-NonPODsByValue<span class="Apple-tab-span" style="white-space:pre"> </span>-38.46%</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>SingleSource/Benchmarks/Misc/flops<span class="Apple-tab-span" style="white-spa!
ce:pre"> </span>-19.30%</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>SingleSource/Benchmarks/Misc/himenobmtxpa<span class="Apple-tab-span" style="white-space:pre"> </span>-12.94%</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>MultiSource/Benchmarks/VersaBench/ecbdes/ecbdes<span class="Apple-tab-span" style="white-space:pre"> </span>-12.68%</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>MultiSource/Benchmarks/ASCI_Purple/SMG2000/smg2000<span class="Apple-tab-span" style="white-space:pre"> </span>-10.68%</div></div><div>Unfortunately, there are also two serious execution-time performance regressions:</div><div><div><span class="Apple-tab-span" style="white-space:pre"> </span>SingleSource/Benchmarks/Adobe-C++/simple_types_constant_folding<span class="Apple-tab-span" style="white-space:pre"> </span>204.19%</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>SingleSource/Benchmarks/Polyb!
ench/linear-algebra/solvers/dynprog/dynprog<span class="Apple-tab-span
" style="white-space:pre"> </span>44.58%</div></div><div>By looking into the <span style="font-size: 14px; line-height: 1.7;">simple_types_constant_folding benchmark, I find it is mainly caused by the unexpected impact of the </span><span style="white-space: pre-wrap; font-size: 14px; line-height: 1.7;">createPromoteMemoryToRegisterPass(). Removing "</span><span style="white-space: pre-wrap; font-size: 14px; line-height: 1.7;">createPromoteMemoryToRegisterPass" would eliminate the execution-time performance regression for </span><span style="font-size: 14px; line-height: 1.7;">simple_types_constant_folding benchmark. Right now, I have no idea why </span><span style="white-space: pre-wrap; font-size: 14px; line-height: 1.7;">createPromoteMemoryToRegisterPass" would lead to such great execution-time performance regression.</span></div><div><span style="font-size: 14px; line-height: 1.7;"><br></span></div><div><a href="http://188.40.87.11:8000/db_default/v4/nts/!
46?baseline=45&compare_to=45" style="font-size: 14px; line-height: 1.7;">http://188.40.87.11:8000/db_default/v4/nts/46?baseline=45&compare_to=45</a> shows the extra compile-time overhead of Polly canonicalization passes without the first "<span style="font-size: 14px; line-height: 1.7;">InstructionCombining" pass.</span><span style="font-size: 14px; line-height: 1.7;"> By removing the </span><span style="font-size: 14px; line-height: 1.7;"> </span><span style="font-size: 14px; line-height: 1.7;">first "</span><span style="font-size: 14px; line-height: 1.7;">InstructionCombining" pass, we see the extra compile-time overhead of Polly canonicalization is at most 13.5%, which is much smaller than the original Polly canonicalization </span><span style="font-size: 14px; line-height: 1.7;">overhead </span><span style="font-size: 14px; line-height: 1.7;">(>20%).</span></div><div><span style="font-size: 14px; line-height: 1.7;"><br></span></d!
iv><div><span style="font-size: 14px; line-height: 1.7;">Second, let's
look into the total impact of those polly canonicalization passes by removing all </span><span style="font-size: 14px; line-height: 1.7;">optional canonicalization passes as follows:</span></div><div><pre>static void registerCanonicalicationPasses(llvm::PassManagerBase &PM) {
// PM.add(llvm::createPromoteMemoryToRegisterPass());
// PM.add(llvm::createInstructionCombiningPass()); //this is the most expensive canonicalization pass for flop benchmark
// PM.add(llvm::createCFGSimplificationPass());
// PM.add(llvm::createTailCallEliminationPass());
// PM.add(llvm::createCFGSimplificationPass());
// PM.add(llvm::createReassociatePass());
// PM.add(llvm::createLoopRotatePass());
// PM.add(llvm::createInstructionCombiningPass());</pre><pre> PM.add(polly::createCodePreparationPass());
}</pre></div><div>As shown on <a href="http://188.40.87.11:8000/db_default/v4/nts/47?baseline=45&compare_to=45">http://188.40.87.11:8000/db_default/v4/nts/47?baseline=45&compare_to=45</a>, the extra compile-time overhead is very small (5.04% at most) by removing all <span style="font-size: 14px; line-height: 1.7;">optional Polly canonicalization passes. However, I think it is not practical to remove all these canonicalizations for the sake of Polly optimization performance. I would further evaluate Polly's performance (with optimization and code generation) in the case all optional canonicalization passes are removed.</span></div><div><span style="font-size: 14px; line-height: 1.7;"><br></span></div><div><span style="font-size: 14px; line-height: 1.7;">As a simple informal conclusion, I think we should revise Polly's canonicalization passes. At least we should consider removing the first "InstructionCombining" pass! </span></div><div><span style=!
"font-size: 14px; line-height: 1.7;"><br></span></div><div>Best,</div><div>Star Tan</div><div><br></div><div>At 2013-09-13 12:46:33,"Star Tan" <tanmx_star@yeah.net> wrote:<br> <blockquote id="isReplyContent" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid"><div style="line-height:1.7;color:#000000;font-size:14px;font-family:arial"><span style="color: rgb(0, 0, 0); font-family: arial; font-size: 14px; line-height: 1.7; white-space: pre-wrap;">At 2013-09-09 13:07:07,"Tobias Grosser" <<a href="mailto:tobias@grosser.es">tobias@grosser.es</a>> wrote:</span><br><pre style="color: rgb(0, 0, 0); font-family: arial; font-size: 14px; line-height: 1.7;">>On 09/09/2013 05:18 AM, Star Tan wrote:
>>
>> At 2013-09-09 05:52:35,"Tobias Grosser" <<a href="mailto:tobias@grosser.es">tobias@grosser.es</a>> wrote:
>>
>>> On 09/08/2013 08:03 PM, Star Tan wrote:
>>> Also, I wonder if your runs include the dependence analysis. If this is
>>> the case, the numbers are very good. Otherwise, 30% overhead seems still
>>> to be a little bit much.
>> I think no Polly Dependence analysis is involved since our compiling command is:
>> clang -O3 -Xclang -load -Xclang LLVMPolly.so -mllvm -polly -mllvm -polly-optimizer=none -mllvm -polly-code-generator=none -mllvm -polly-codegen-scev
>> Fortunately, with the option "-polly-codegen-scev", only three benchmark shows >20% extra compile-time overhead:
>
>I believe so to, but please verify with -debug-pass=Structure</pre><pre style="color: rgb(0, 0, 0); font-family: arial; font-size: 14px; line-height: 1.7;">I have verified. It indeed does not involve Polly Dependence analysis. "Polly Dependence Pass" for flop is still high for some benchmarks as we have discussed before. </pre><pre style="color: rgb(0, 0, 0); font-family: arial; font-size: 14px; line-height: 1.7;">>> SingleSource/Benchmarks/Misc/flops 28.57%
>> MultiSource/Benchmarks/MiBench/security-sha/security-sha 22.22%
>> MultiSource/Benchmarks/VersaBench/ecbdes/ecbdes 21.05%
>> When I look into the compile-time for the flop benchmark using "-ftime-report", I find the extra compile-time overhead mainly comes from the "Combine redundant instructions" pass.
>> the top 5 passes when compiled with Polly canonicalization passes:
>> ---User Time--- --User+System-- ---Wall Time--- --- Name ---
>> 0.0160 ( 20.0%) 0.0160 ( 20.0%) 0.0164 ( 20.8%) Combine redundant instructions
>> 0.0120 ( 15.0%) 0.0120 ( 15.0%) 0.0138 ( 17.5%) X86 DAG->DAG Instruction Selection
>> 0.0040 ( 5.0%) 0.0040 ( 5.0%) 0.0045 ( 5.7%) Greedy Register Allocator
>> 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0029 ( 3.7%) Global Value Numbering
>> 0.0040 ( 5.0%) 0.0040 ( 5.0%) 0.0028 ( 3.6%) Polly - Create polyhedral description of Scops
>>
>> But the top 5 passes for clang is:
>> ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
>> 0.0120 ( 25.0%) 0.0000 ( 0.0%) 0.0120 ( 21.4%) 0.0141 ( 25.2%) X86 DAG->DAG Instruction Selection
>> 0.0040 ( 8.3%) 0.0000 ( 0.0%) 0.0040 ( 7.1%) 0.0047 ( 8.4%) Greedy Register Allocator
>> 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0034 ( 6.1%) Combine redundant instructions
>> 0.0000 ( 0.0%) 0.0040 ( 50.0%) 0.0040 ( 7.1%) 0.0029 ( 5.2%) Global Value Numbering
>> 0.0040 ( 8.3%) 0.0000 ( 0.0%) 0.0040 ( 7.1%) 0.0029 ( 5.2%) Combine redundant instructions
>> We can see the "Combine redundant instructions" are invoked many times and the extra invoke resulted by Polly's canonicalization is the most significant one. We have found this problem before and I need to look into the details of canonicalization passes related to "Combine redundant instructions".
>
>OK.
</pre><pre style="color: rgb(0, 0, 0); font-family: arial; font-size: 14px; line-height: 1.7;">By investigating the flop benchmark, I find the key is the first "<span style="font-size: 14px; line-height: 1.7;">InstructionCombining</span><span style="font-size: 14px; line-height: 1.7;">" pass in a serial of canonicalization passes listed as follows:</span></pre><pre>static void registerCanonicalicationPasses(llvm::PassManagerBase &PM) {
PM.add(llvm::createPromoteMemoryToRegisterPass());
PM.add(llvm::createInstructionCombiningPass()); //this is the most expensive canonicalization pass for flop benchmark
PM.add(llvm::createCFGSimplificationPass());
PM.add(llvm::createTailCallEliminationPass());
PM.add(llvm::createCFGSimplificationPass());
PM.add(llvm::createReassociatePass());
PM.add(llvm::createLoopRotatePass());
PM.add(llvm::createInstructionCombiningPass());</pre><pre> if (!SCEVCodegen)
PM.add(polly::createIndVarSimplifyPass());
PM.add(polly::createCodePreparationPass());
}</pre><pre>If we remove the first "<span style="font-size: 14px; line-height: 1.7;">InstructionCombining" pass, then the compile-time is reduced by more than 10% . The results reported by -ftime-report become very similar to the case without Polly canonicalization:</span></pre><pre> ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
0.0120 ( 23.1%) 0.0000 ( 0.0%) 0.0120 ( 21.4%) 0.0138 ( 21.5%) X86 DAG->DAG Instruction Selection
0.0040 ( 7.7%) 0.0000 ( 0.0%) 0.0040 ( 7.1%) 0.0045 ( 7.1%) Greedy Register Allocator
0.0040 ( 7.7%) 0.0000 ( 0.0%) 0.0040 ( 7.1%) 0.0042 ( 6.6%) Polly - Create polyhedral description of Scops
0.0040 ( 7.7%) 0.0000 ( 0.0%) 0.0040 ( 7.1%) 0.0038 ( 5.9%) Combine redundant instructions
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0029 ( 4.5%) Global Value Numbering
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0027 ( 4.2%) Combine redundant instructions
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0020 ( 3.2%) Combine redundant instructions
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0020 ( 3.1%) Combine redundant instructions</pre><pre><span style="font-size: 14px; line-height: 1.7;">Similar results have been found in the benchmark whetstone. I will have a full test using LLVM test-suite tonight to see whether it has similar effectiveness for other test-suite benchmarks.</span></pre><pre>@Tobias, do you have any idea about the performance impact and other consequences that if we remove such a canonicalization pass. In my option, it should not be important since we still run the "<span style="font-size: 14px; line-height: 1.7;">InstructionCombining" pass after "</span><span style="font-size: 14px; line-height: 1.7;">createLoopRotatePass" pass and in fact there are many more runs of "InstructionCombine" pass after this point.</span></pre><pre><span style="font-size: 14px; line-height: 1.7;">Best,</span></pre><pre style="color: rgb(0, 0, 0); font-family: arial; font-size: 14px; line-height: 1.7!
;">Star Tan</pre></div></blockquote></div></div>