Aggressive Inlining for VLIW
https://doi.org/10.15514/ISPRAS-2015-27(6)-13
Abstract
Inline expansion is very important for high performance VLIW, especially for microprocessors with static scheduling. Optimizations in optimizing compilers for VLIW duplicate code aggressively and lead to long compile time. Our inlining algorithm is based on heuristics that takes into account compile time explicitly. This made optimization more balanced and significantly reduced code growth and compile time compared to common inlining approach based on minimization of runtime within constraints. Instead of using hard constraints we are trading run time for compilation time in some proportion. Our heuristics predicts several key optimizations in evaluation of runtime and compile time: code scheduling, global copy propagation, dead code elimination and different loop optimizations. Optimizations prediction reduces the need in profile information which is rarely available in practice. Our implementation of inlining includes cloning, partial inlining and inlining across compilation modules in whole program mode. All this factors make dramatic impact on performance: our inlining implementation in the Elbrus optimizing compiler boost SPEC CPU2006 benchmark performance by factor of 1.41 at the cost of 12% increase of compile time and 7.7% increase of code size on average.
About the Authors
A. . Ermolitckii
MCST
Russian Federation
Russian Federation
M. . Neiman-Zade
MCST
Russian Federation
Russian Federation
O. . Chetverina
MCST
Russian Federation
Russian Federation
A. . Markin
MCST
Russian Federation
Russian Federation
V. . Volkonskii
MCST
Russian Federation
Russian Federation
References
1. Robert W. Scheifler. An analysis of inline substitution for a structured programming language. Communications of the ACM, Sept. 1977, Volume 20, Issue 9, p. 647-654
2. P. C. Chang, Wen-mei W. Hwu. Inline function expansion for compiling C programs. ACM SIGPLAN Notices, 1989, vol. 24, no. 7, p. 246-257
3. Pohua P. Chang, Scott A. Mahlke, William Y. Chen, Wen-mei W. Hwu. Profile-guided automatic inline expansion for C programs. Software - Practice & Experience, May 1992, Volume 22, Issue 5, p. 349 - 369
4. Matthew Arnold, Stephen J. Fink, Vivek Sarkar, Peter F. Sweeney. A comparative study of static and profile-based heuristics for inlining. ACM SIGPLAN Notices, 2000, vol. 35, no. 7, p. 52-64
5. Peng Zhao, Jose Nelson Amaral. To inline or not to inline? Enhanced inlining decisions. Workshop on Languages and Compilers for Parallel Computing (LCPC) , Oct. 2003, p. 405-419
6. Andrew Ayers, Richard Schooler, Robert Gottlieb. Aggressive inlining. ACM SIGPLAN Notices, 1997, vol. 32, no. 5, p. 134-145
7. Robert Muth, Saumya Debray. Partial Inlining. Technical report, Department of Computer Science, University of Arizona, 1997
8. Tom Way, Ben Breech, Lori Pollock. Region Formation Analysis with Demand-Driven Inlining for Region-Based Optimization. Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, 2000
9. Tom Way, Lori L. Pollock. A Region-based Partial Inlining Algorithm for an ILP Optimizing Compiler. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 2002, Volume 2, p. 552-556
10. Dibyendu Das. Function inlining versus function cloning. ACM SIGPLAN Notices, June 2003, Volume 38, Issue 6, p. 23 - 29
11. Peng Zhao, Jose Nelson Amaral. Function outlining and partial inlining. Proceedings of the 17th International Symposium on Computer Architecture on High Performance Computing, 2005, p. 101 - 108
12. Jun-Pyo Lee, Jae-Jin Kim, Soo-Mook Moon, Suhyun Kim. Aggressive Function Splitting for Partial Inlining. Proceedings of the 2011 15th Workshop on Interaction between Compilers and Computer Architectures, 2011, p. 80-86
13. M.R. Garey, D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York.1979. 338 p.
14. Steven S. Muchnick. Advanced compiler design and implementation. Morgan Kaufmann Publishers, San Francisco. 1997. 888 p.
15. Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Pearson Education, Boston. 2006. 1000 p.
16. Kratkoe opisanie arkhitektury Elbrus [Short description of Elbrus architecture], http://www.elbrus.ru/arhitektura_elbrus (in Russian)
17. V.Volkonskii, A.Breger, A.Buchnev, A.Grabezhnoi, A.Ermolitckii, L.Mukhanov, M.Neiman-Zade, P.Stepanov, O.Chetverina. Metody rasparallelivaniia program v optimiziruiushchem kompiliatore [Program parallelization methods in optimizing compiler]. Voprosy radioelektroniki, seriia EVT, vypusk 3 [Questions of radioelectronics, Computer Technology series, Volume 3], 2012, p.63-88 (In Russian)
18. Standard Performance Evaluation Corporation. SPEC CPU Benchmarks, http://www.spec.org/
Review
For citations:
Ermolitckii A., Neiman-Zade M., Chetverina O., Markin A., Volkonskii V. Aggressive Inlining for VLIW. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2015;27(6):189-198. (In Russ.) https://doi.org/10.15514/ISPRAS-2015-27(6)-13
Email this article 