Methods of profile information correction during compilation
https://doi.org/10.15514/ISPRAS-2015-27(6)-4
Abstract
Performed by compiler code optimizing transformations efficiency can be greatly increased by obtaining and using program profile information, such compiler work is called profile-guided optimization (PGO). After applying transformations, which change control flow graph, it is necessary to adjust the profile information in order to maintain its adequacy for the work of succeeding optimizations. This paper considers two ways of representing profile information and the transition between them, describes the possible causes of uprising additional information on optimized code control flow requiring profile updating. Most frequently encountered problems of profile information update are considered and following solutions are offered: algorithm of acyclic graph profile correction according to its end nodes values; algorithm of loop average iteration number correction; control flow with “controversial node” profile correction algorithm. It is proved that the suggested algorithms of acyclic region counters and the loop iterations counter correction allow to change the counters ratio with original graph counters minimally. With the use of proposed algorithms, the mechanism of correction profile and thin profile information after loop peeling is described. All described methods are implemented in optimizing compilers lcc, lccs, lfortran, lfortrans for Elbrus and Sparc architectures.
References
1. Chang P. P., Mahlke S. A., Hwu W. W. Using profile information to assist classic compiler code optimizations. Software Practice and Experience, V. 21, No12. -1991.-P. 1301-1321
2. W. Chen, R. Bringmann, S. Mahlke, S. Anik, T. Kiyohara, N. Warter, D. Lavery, W. -M. Hwu, R. Hank and J. Gyllenhaal., Using profile information to assist advanced compiler optimization and scheduling, 1993
3. Jan Hunicka, Profile driven optimisations in GCC, Proceedings of the GCC Developers’ Summit June 22nd-24th, 2005, Ottawa, Ontario Canada
4. Volkonskiy V.Y., Ermolitskii A.V., Rovinskii E.V. Razvitie metoda vektorizacii ciklov pri pomoshchi optimiziruyushchego kompilyatora. [Development of loops vectorization method using an optimizing compiler]. Vysokoproizvoditel'nye vychislitel'nye sistemy i mikroprocessory: sbornik trudov IMVS RAN [High-performance computing systems and microprocessors: a collection of IMVS RAS works], Vypusk N8, 2005 (in Russian)
5. Dmitry M Maslennikov, Vladimir Y Volkonsky: Compiler method and apparatus for elimination of redundant speculative computations from innermost loops. Elbrus International October 9, 2001: US06301706
6. Pengfei Yuan, Yao Guo , Xiangqun Chen, Experiences in profile-guided operating system kernel optimization, Proceedings of 5th Asia-Pacific Workshop on Systems, June 25-26, 2014, Beijing, China
7. Bo Wu, Mingzhou Zhou, Xipeng Shen, Yaoqing Gao, Raul Silvera, Graham Yiu, Simple profile rectifications go a long way, Proceedings of the 27th European conference on Object-Oriented Programming, July 01-05, 2013, Montpellier, France
8. Drozdov A.YU., Stepanenkov A.M. Tekhnologiya optimizacii ciklovyh uchastkov procedur v kompilyatorah dlya arhitektur s apparatnoj podderzhkoj konvejrizacii ciklov. [Procedures loop areas optimization technology for architectures with hardware loops pipelining] Informacionnye tekhnologii i vychislitenye sistemy.[Information Technology and computer systems] №3, M. 2004 (in Russian)
9. D.S. Ivanov, Register allocation with instruction scheduling for VLIW-architectures. Programming and Computer Software. November 2010, Volume 36, Issue 6, pp 363-367
10. Bo Wu, Zhijia Zhao, Xipeng Shen, Yunlian Jiang, Yaoqing Gao, Raul Silvera, Exploiting inter-sequence correlations for program behavior prediction, Proceedings of the ACM international conference on Object oriented programming systems languages and applications, October 19-26, 2012, Tucson, Arizona, USA [doi>10.1145/2384616.2384678]
11. Calin Cascaval , Luiz De Rose , David A. Padua , Daniel A. Reed, Compile-Time Based Performance Prediction, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.365-379, August 04-06, 1999
12. Jeremy Lau , Matthew Arnold , Michael Hind , Brad Calder, Online performance auditing: using hot optimizations without getting burned, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
13. Ananias V. Levitin . Algorithms : Introduction to the design and analysis [Algoritmy: vvedenie v razrabotku i analiz ] - M .: "Williams", 2006.— С. 220-224. — ISBN 5-8459-0987-2 (in Russian)
14. Steven S. Muchnick, Advanced Compiler Design & Implementation, 2003
15. Introduction to algorithms, Third Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, 2009
16. Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman "Compilers: Principles, Techniques, and Tools" Book, Pearson Education, ISBN 0-321-48681-1, 2006
Review
For citations:
Chetverina O.A. Methods of profile information correction during compilation. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2015;27(6):49-66. (In Russ.) https://doi.org/10.15514/ISPRAS-2015-27(6)-4
Email this article 