<div style="line-height:1.7;color:#000000;font-size:14px;font-family:arial">Hello all,<div><br></div><div>I have done some basic experiments about Polly canonicalization passes and I found the SCEV canonicalization has significant impact on both compile-time and execution-time performance.</div><div><span style="font-size: 14px; line-height: 1.7;"><br></span></div><div><span style="font-size: 14px; line-height: 1.7;">Detailed results for SCEV and default canonicalization can be viewed on:</span><span style="font-size: 14px; line-height: 1.7;"> </span>http://188.40.87.11:8000/db_default/v4/nts/32 (or 33, 34)</div><div> *pNoGen with SCEV canonicalization (run 32): -O3 <span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;">-Xclang -load -Xclang LLVMPolly.so -mllvm -polly -mllvm -polly-optimizer=none -mllvm -polly-code-generator=none -mllvm -polly-codegen-scev</span></div><!
div> *pNoGen with default canonicalization (run 33): -O3 <span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;">-Xclang -load -Xclang LLVMPolly.so -mllvm -polly -mllvm -polly-optimizer=none -mllvm -polly-code-generator=none</span></div><div> *pBasic without any canonicalization (run 34): -O3 <span style="font-size: 14px; color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px;">-Xclang -load -Xclang LLVMPolly.so</span></div><div><span style="font-size: 14px; color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px;"><br></span></div><div><span style="font-size: 14px; color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px;">Impact of SCEV canonicalization:</span></div><div><font color="#333333" face="Helv!
etica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20
px;"> </span></font>http://188.40.87.11:8000/db_default/v4/nts/32?compare_to=34&baseline=34</div><div><span style="font-size: 14px; color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px;">Impact of default canonicalization: </span></div><div><span style="font-size: 14px; color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px;"> </span><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif" style="font-size: 14px; line-height: 1.7;"><span style="line-height: 20px;"> </span></font><span style="font-size: 14px; line-height: 1.7;">http://188.40.87.11:8000/db_default/v4/nts/33?compare_to=34&baseline=34</span></div><div><span style="font-size: 14px; color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px;">Comparison of SCEV </span><span style="color: rgb(51, 51, 51); f!
ont-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px;">canonicalization </span><span style="font-size: 14px; color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px;">with default </span><span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;">canonicalization: </span></div><div><span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;"> </span><span style="font-size: 14px; color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px;"> </span><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif" style="font-size: 14px; line-height: 1.7;"><span style="line-height: 20px;"> </span></font><span style="font-size: 14px; line-height: 1.7;">http://188.40.87.11:80!
00/db_default/v4/nts/32?compare_to=33&baseline=33</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 we expected, </span><span style="font-size: 14px; line-height: 1.7;">both SCEV canonicalization and default </span><span style="font-size: 14px; line-height: 1.7;">canonicalization</span><span style="font-size: 14px; line-height: 1.7;"> will slightly increase the compile-time overhead (at most 30% extra compile-time). They also lead to some execution-time regressions and improvements.</span></div><div><span style="font-size: 14px; line-height: 1.7;"><br></span></div><div>The only difference between SCEV canonicalization and default canonicalization is the "IndVarSimplify" pass as shown in the code RegisterPasses.cpp:212:</div><div><div> if (!SCEVCodegen)</div><div> PM.add(polly::createIndVarSimplifyPass());</div></div><div>However, I find it is interesting to look into the comparison between !
<span style="font-size: 14px; line-height: 1.7;">SCEV canonicalization and default canonicalization (</span><span style="font-size: 14px; line-height: 1.7;">http://188.40.87.11:8000/db_default/v4/nts/32?compare_to=33&baseline=33):</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;">First of all, we can expect SCEV </span><span style="font-size: 14px; line-height: 1.7;">canonicalization</span><span style="font-size: 14px; line-height: 1.7;"> has better compile-time performance since it avoids the "IndVarSimplify" pass. Actually, it can gain more than 5% compile-time performance improvement for 32 benchmarks, especially for the following benchmarks:</span></div><div><div><span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;"> </span><span style="color: rgb(51, 51, 51); font-!
family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 2
0px; font-size: 14px;"> </span>MultiSource/Applications/lemon/lemon<span class="Apple-tab-span" style="white-space: pre;"> </span>-11.02%</div><div><span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;"> </span><span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;"> </span>SingleSource/Benchmarks/Misc/oourafft<span class="Apple-tab-span" style="white-space:pre"> </span>-10.53%</div><div><span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;"> </span><span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;"> </span>SingleSource/Benchmarks/Linpack/linpack-pc<span class="Apple-tab-span" style="white-sp!
ace:pre"> </span>-10.00%</div><div><span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;"> </span><span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;"> </span>MultiSource/Benchmarks/MiBench/automotive-susan/automotive-susan<span class="Apple-tab-span" style="white-space:pre"> </span>-8.31%</div><div><span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;"> </span><span style="color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; line-height: 20px; font-size: 14px;"> </span>MultiSource/Benchmarks/TSVC/LinearDependence-flt/LinearDependence-flt<span class="Apple-tab-span" style="white-space:pre"> </span>-8.18%</div><div><br></div></div><div>Second, w!
e find that SCEV canonicalization has both regression and improvement
of execution performance compared with default canonicalization. Actually, there are <span style="font-size: 14px; line-height: 20px; color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif;">many execution-time regressions such as:</span></div><div><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;"> SingleSource/Benchmarks/Shootout/nestedloop<span class="Apple-tab-span" style="white-space:pre"> </span>+16363.64%</span></font></div><div><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;"> SingleSource/Benchmarks/Shootout-C++/nestedloop<span class="Apple-tab-span" style="white-space:pre"> </span>+16200.00%</span></font></div><div><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;"> SingleSource/UnitTe!
sts/Vectorizer/gcc-loops<span class="Apple-tab-span" style="white-space:pre"> </span>+107.35%</span></font></div><div><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;"> SingleSource/Benchmarks/Polybench/medley/reg_detect/reg_detect<span class="Apple-tab-span" style="white-space:pre"> </span>+75.00</span></font></div><div><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;"> SingleSource/Benchmarks/Misc/flops-6<span class="Apple-tab-span" style="white-space:pre"> </span>+40.03%</span></font></div><div><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;"> SingleSource/Benchmarks/Misc/flops-5<span class="Apple-tab-span" style="white-space:pre"> </span>+40.00%</span></font></div><div><font color="#333333" face="Helvetica Neue, Helvetica!
, Arial, sans-serif"><span style="line-height: 20px;"> &n
bsp; MultiSource/Benchmarks/MiBench/automotive-susan/automotive-susan<span class="Apple-tab-span" style="white-space: pre;"> </span>30.00%</span></font></div><div><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;">as well as many execution-time improvements such as:</span></font></div><div><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;"><div> SingleSource/Benchmarks/Shootout/ary3<span class="Apple-tab-span" style="white-space: pre;"> </span>-28.98%</div></span></font><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;"><div><span style="font-size: 14px;"> </span>SingleSource/Benchmarks/Polybench/linear-algebra/solvers/dynprog/dynprog<span class="Apple-tab-span" style="white-space:pre"> </span>-26.97%</div></span></font><font color="#333333" face="Helv!
etica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;"><div><span style="font-size: 14px;"> </span>SingleSource/Benchmarks/CoyoteBench/lpbench<span class="Apple-tab-span" style="white-space:pre"> </span>-25.84%</div></span></font><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;"><div><span style="font-size: 14px;"> </span>MultiSource/Benchmarks/BitBench/drop3/drop3<span class="Apple-tab-span" style="white-space:pre"> </span>-16.58%</div></span></font><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;"><div><span style="font-size: 14px;"> </span>MultiSource/Benchmarks/Ptrdist/yacr2/yacr2<span class="Apple-tab-span" style="white-space:pre"> </span>-16.46%</div></span></font><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-heigh!
t: 20px;"><div><span style="font-size: 14px;"> &nb
sp;</span>MultiSource/Benchmarks/TSVC/Symbolics-flt/Symbolics-flt<span class="Apple-tab-span" style="white-space:pre"> </span>-14.96%</div></span></font></div><div><br></div><div><font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="line-height: 20px;">I think the execution-time performance regression is mainly because of the unexpected performance improvements from non-SCEV canonicalization as shown int eh following bug: </span></font><a href="http://llvm.org/bugs/show_bug.cgi?id=17153" style="font-size: 14px; line-height: 1.7;">http://llvm.org/bugs/show_bug.cgi?id=17153</a>. I will try to find out why "<span style="font-size: 14px; line-height: 1.7;">IndVarSimplify" can produce better code in the next step. If we can eliminate "IndVarSimplify" canonicalization but keep on producing high-quality code, then we can gain better compile-time performance without execution-time performance loss.</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;">Best,</span></div><div><span style="font-size: 14px; line-height: 1.7;">Star Tan</span></div><div><br></div></div>