[LLVMdev] [Polly][GSOC2013] FastPolly -- SCOP Detection Pass

[Star Tan]

Hi all,



I have investigated the compile-time overhead of "Polly Scop Detection" pass based on LNT testing results. 
This mail is to share some results I have found.


(1) Analysis of "SCOP Detection Pass" for PolyBench (Attached file PolyBench_SCoPs.log)
Experimental results show that the "SCOP Detection pass" does not lead to significant extra compile-time overhead for compiling PolyBench. The percent of compile-time overhead caused by "SCOP Detection Pass" is usually less than 4% of total compile-time. Details for each benchmark can be seen in attached file SCoPs.tgz. I think this is because a lot of other Polly passes, such as "Cloog code generation" and "Induction Variable Simplification" are much more expensive than the "SCOP Detection Pass".


(2) Analysis of "SCOP Detection Pass for two hot benchmarks (tramp3d and oggenc)
“SCOP Detection Pass" would lead to significant compile-time overhead for these two benchmarks: tramp3d and oggenc, both of which are included in LLVM test-suite/MultiSource.


The top 5 passes in compiling tramp3d are: (Attached file tramp3d-SCoPs.log)
   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   6.0720 ( 21.7%)   0.0400 (  2.1%)   6.1120 ( 20.5%)   6.1986 ( 20.6%)  Polly - Detect static control parts (SCoPs)
   4.0600 ( 14.5%)   0.2000 ( 10.7%)   4.2600 ( 14.3%)   4.3655 ( 14.5%)  X86 DAG->DAG Instruction Selection
   1.9880 (  7.1%)   0.2080 ( 11.1%)   2.1960 (  7.4%)   2.2277 (  7.4%)  Function Integration/Inlining
   1.7520 (  6.3%)   0.0840 (  4.5%)   1.8360 (  6.2%)   1.8765 (  6.2%)  Global Value Numbering
   1.2440 (  4.4%)   0.1040 (  5.5%)   1.3480 (  4.5%)   1.2925 (  4.3%)  Combine redundant instructions


and the top 5 passes in compiling oggenc are: (Attached file oggenc-SCoPs.log)
   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   0.7760 ( 14.6%)   0.0280 ( 11.1%)   0.8040 ( 14.4%)   0.8207 ( 14.5%)  X86 DAG->DAG Instruction Selection
   0.7080 ( 13.3%)   0.0040 (  1.6%)   0.7120 ( 12.8%)   0.7317 ( 13.0%)  Polly - Detect static control parts (SCoPs)
   0.4200 (  7.9%)   0.0000 (  0.0%)   0.4200 (  7.5%)   0.4135 (  7.3%)  Polly - Calculate dependences
   0.3120 (  5.9%)   0.0200 (  7.9%)   0.3320 (  6.0%)   0.2947 (  5.2%)  Loop Strength Reduction
   0.1720 (  3.2%)   0.0080 (  3.2%)   0.1800 (  3.2%)   0.1992 (  3.5%)  Global Value Numbering


Results show that Polly spends a lot of time on detecting scops, but most of region scops are proved to be invalid at last. As a result, this pass waste a lot of compile-time.I think we should improve this pass by detect invalid scop early.


(3) About detecting scop regions in bottom-up order.
Detecting scop regions in bottom-up order can significantly speed up the scop detection pass. However, as I have discussed with Sebastian, detecting scops in bottom-up order and up-bottom order will lead to different results. As a result, we should not change the detection order. 


Do you have any other suggestions that may speed up the scop detection pass?


Best,
Star Tan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130630/c9f428d2/attachment.html>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: PolyBench_SCoPs.log
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130630/c9f428d2/attachment.ksh>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: SCoPs.tgz
Type: application/octet-stream
Size: 36590 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130630/c9f428d2/attachment.obj>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: tramp3d-SCoPs.log
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130630/c9f428d2/attachment-0001.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: oggenc-SCoPs.log
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130630/c9f428d2/attachment-0002.ksh>