logo

SCIENTIA SINICA Informationis, Volume 49 , Issue 10 : 1267-1282(2019) https://doi.org/10.1360/N112019-00050

Selection of compiler-optimization sequences

More info
  • ReceivedMar 2, 2019
  • AcceptedJun 6, 2019
  • PublishedOct 16, 2019

Abstract

In recent decades, compiler developers have designed and implemented many compiler-optimization options for a variety of complex optimization requirements; however, it is difficult to effectively adapt existing standard compiler-optimization sequences comprising several optimization options to complex compilation requirements. Because programs have different semantics and compilation goals, it is difficult to achieve desirable optimization results by directly employing standard compiler-optimization sequences. Additionally, the evolution of hardware architectures has increased the complexity of compilation environments, requiring compiler-optimization sequences to be adjusted accordingly. Therefore, selection of good optimization sequences for programs remains challenging. To address this, we reviewed 55 studies related to the selection of compiler-optimization sequences and summarized the research status of this area from several perspectives, including algorithmic approaches, research focuses, target compilers, and target benchmarks. The most popular algorithms used in this research area include heuristic search algorithms (e.g., genetic algorithms) and machine-learning algorithms (e.g., support vector machines). Over 80% of the existing studies focused on novel solutions or validation research. Furthermore, the most popular compiler and benchmark suites used for these experiments are GCC and miBench, respectively. This review offers insight into research trends associated with compiler optimization-sequence selection and provides possible directions for future studies in this field.


Funded by

国家重点研发计划(2018YFB1003900)

国家自然科学基金(61722202,61772107)


References

[1] Hoste K, Eeckhout L. Cole: compiler optimization level exploration. In: Proceedings of the 6th Annual IEEE/ACM International Symposium on Code Generation and Optimization, 2008. 165--174. Google Scholar

[2] Petersen K, Feldt R, Mujtaba S, et al. Systematic mapping studies in software engineering. In: Proceedings of International Conference on Evaluation & Assessment in Software Engineering, 2008. 68--77. Google Scholar

[3] Chen Y Y, Zhang Y. Compiler Principle. 3rd ed. Beijing: Higher Education Press, 2014. Google Scholar

[4] Garousi V, Mesbah A, Betin-Can A. A systematic mapping study of web application testing. Inf Software Tech, 2013, 55: 1374-1396 CrossRef Google Scholar

[5] Neto C R L, Neto P A M S, Almeida E S D, et al. A Mapping Study on Software Product Lines Testing Tools. In: Proceedings of 24th International Conference on Software Engineering and Knowledge Engineering, 2012. 628--634. Google Scholar

[6] Ouhbi S, Idri A, Fernández-Alemán J L, et al. Software quality requirements: a systematic mapping study. In: Proceedings of the 20th Asia-Pacific Software Engineering Conference, 2013. 231--238. Google Scholar

[7] Cosentino V, Canovas Izquierdo J L, Cabot J. A Systematic Mapping Study of Software Development With GitHub. IEEE Access, 2017, 5: 7173-7192 CrossRef Google Scholar

[8] de Lima E D, Silva A F D, Herrera C. A case-based reasoning approach to find good compiler optimization sequences. In: Proceedings of the 32nd International Conference of the Chilean Computer Science Society (SCCC), Temuco, 2013. 8--10. Google Scholar

[9] Yi Q, Wang Q, Cui H M. Specializing compiler optimizations through programmable composition for dense matrix computations. In: Proceedings of IEEE/ACM International Symposium on Microarchitecture, 2014. 596--608. Google Scholar

[10] Cooper K D, Grosul A, Harvey T J. Exploring the structure of the space of compilation sequences using randomized search algorithms. J Supercomput, 2006, 36: 135-151 CrossRef Google Scholar

[11] Kulkarni P, Zhao W, Moon H, et al. Finding effective optimization phase sequences. In: Proceedings of ACM Sigplan Conference on Language, Compiler, and Tool for Embedded Systems, 2003. 12--23. Google Scholar

[12] Jantz M R, Kulkarni P A. Performance potential of optimization phase selection during dynamic JIT compilation. SIGPLAN Not, 2013, 48: 131 CrossRef Google Scholar

[13] Ansel J, Kamil S, Veeramachaneni K, et al. Opentuner: an extensible framework for program autotuning. In: Proceedings of the 23rd International Conference on Parallel Architectures and Compilation, 2014. 303--316. Google Scholar

[14] Boussaa M, Barais O, Baudry B, et al. NOTICE: a framework for non-functional testing of compilers. In: Proceedings of IEEE International Conference on Software Quality, Reliability and Security, 2016. 335--346. Google Scholar

[15] Lokuciejewski P, Plazar S, Falk H, et al. Multi-objective exploration of compiler optimizations for real-time systems. In: Proceedings of IEEE International Symposium on Object/component/service-Oriented Real-Time Distributed Computing, 2010. 115--122. Google Scholar

[16] Lokuciejewski P, Plazar S, Falk H. Approximating Pareto optimal compiler optimization sequences-a trade-off between WCET, ACET and code size. Softw-Pract Exper, 2011, 41: 1437-1458 CrossRef Google Scholar

[17] Chebolu N A B S, Wankar R. Multi-objective exploration for compiler optimizations and parameters. In: Proceedings of International Workshop on Multi-disciplinary Trends in Artificial Intelligence, 2014. 23--34. Google Scholar

[18] Cavazos J, Fursin G, Agakov F, et al. Rapidly selecting good compiler optimizations using performance counters. In: Proceedings of the International Symposium on Code Generation and Optimization, 2007. 185--197. Google Scholar

[19] Fursin G, Kashnikov Y, Memon A W. Milepost GCC: Machine Learning Enabled Self-tuning Compiler. Int J Parallel Prog, 2011, 39: 296-327 CrossRef Google Scholar

[20] Nobre R, Martins L G A. Use of previously acquired positioning of optimizations for phase ordering exploration. In: Proceedings of International Workshop on Software and Compilers for Embedded Systems, 2015. 58--67. Google Scholar

[21] Purini S, Jain L. Finding good optimization sequences covering program space. ACM Trans Archit Code Optim, 2013, 9: 1-23 CrossRef Google Scholar

[22] Park E, Cavazos J, Alvarez M A. Using graph-based program characterization for predictive modeling. In: Proceedings of the 10th International Symposium on Code Generation and Optimization, 2012. 196--206. Google Scholar

[23] Ashouri A H, Bignoli A, Palermo G. MiCOMP. ACM Trans Archit Code Optim, 2017, 14: 1-28 CrossRef Google Scholar

[24] Park E, Kartsaklis C, Cavazos J. HERCULES: strong patterns towards more intelligent predictive modeling. In: Proceedings of International Conference on Parallel Processing, 2014. 172--181. Google Scholar

[25] Martins L G A, Nobre R, Cardoso J M P. Clustering-Based Selection for the Exploration of Compiler Optimization Sequences. ACM Trans Archit Code Optim, 2016, 13: 1-28 CrossRef Google Scholar

[26] Ashouri A H, Mariani G, Palermo G. COBAYN. ACM Trans Archit Code Optim, 2016, 13: 1-25 CrossRef Google Scholar

[27] Foleiss J H, Faustino d S A, Ruiz L B. The Effect of Combining Compiler Optimizations on Code Size. In: Proceedings of the 30th International Conference of the Chilean Computer Science Society, 2011. 187--194. Google Scholar

[28] Plotnikov D, Melnik D, Vardanyan M, et al. An Automatic tool for tuning compiler optimizations. In: Proceedings of the 9th International Conference on Computer Science and Information Technologies Revised Selected Papers, Yerevan, 2014. 1--7. Google Scholar

[29] Lima E D D, Xavier T C D S, Silva A F D, et al. Compiling for performance and power efficiency. In: Proceedings of International Workshop on Power and Timing Modeling, Optimization and Simulation, 2013. 142--149. Google Scholar

[30] Narayanamurthy N, Pattabiraman K, Ripeanu M. Finding resilience-friendly compiler optimizations using meta-heuristic search techniques. In: Proceedings of the 12th European Dependable Computing Conference (EDCC), 2016. 1--12. Google Scholar

[31] Sangchoolie B, Ayatolahi F, Johansson R, et al. A study of the impact of Bit-Flip errors on programs compiled with different optimization levels. In: Proceedings of Dependable Computing Conference, 2014. 146--157. Google Scholar

[32] Li F Q, Tang F L, Shen Y. Feature Mining for Machine Learning Based Compilation Optimization. In: Proceedings of the 8th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, 2014. 207--214. Google Scholar

[33] Nazarian G, Strydis C, Gaydadjiev G. Compatibility study of compile-time optimizations for power and reliability. In: Proceedings of 2011 14th Euromicro Conference on Digital System Design, 2011. 809--813. Google Scholar

[34] Touati S A A, Barthou D. On the decidability of phase ordering problem in optimizing compilation. In: Proceedings of the 3rd Conference on Computing Frontiers, 2006. 147--156. Google Scholar

[35] Jantz M R, Kulkarni P A. Analyzing and addressing false interactions during compiler optimization phase ordering. Softw Pract Exper, 2014, 44: 643-679 CrossRef Google Scholar

[36] Chebolu N A B S, Wankar R. A novel scheme for Compiler Optimization Framework. In: Proceedings of International Conference on Advances in Computing, Communications and Informatics, 2015. 2374--2380. Google Scholar

[37] Nobre R, Martins L G A, Cardoso J M P. A graph-based iterative compiler pass selection and phase ordering approach. SIGPLAN Not, 2016, 51: 21-30 CrossRef Google Scholar

[38] Ashouri A H, Bignoli A, Palermo G, et al. Predictive modeling methodology for compiler phase-ordering. In: Proceedings of the 7th Workshop on Parallel Programming and Run-Time Management Techniques for Many-core Architectures and the 5th Workshop on Design Tools and Architectures For Multicore Embedded Computing Platforms, 2016. 7--12. Google Scholar

[39] Chen Y, Fang S, Huang Y. Deconstructing iterative optimization. ACM Trans Archit Code Optim, 2012, 9: 1-30 CrossRef Google Scholar

[40] Lu P J, Che Y G, Wang Z H. An Effective Iterative Compilation Search Algorithm for High Performance Computing Applications. In: Proceedings of IEEE International Conference on High PERFORMANCE Computing and Communications, 2008. 368--373. Google Scholar

[41] Xuan J, Jiang H, Ren Z. Solving the Large Scale Next Release Problem with a Backbone-Based Multilevel Algorithm. IIEEE Trans Software Eng, 2012, 38: 1195-1212 CrossRef Google Scholar

[42] Ren Z, Jiang H, Xuan J. Hyper-heuristics with low level parameter adaptation.. Evolary Computation, 2012, 20: 189-227 CrossRef PubMed Google Scholar

[43] Chen X, Jiang H, Chen Z. Automatic test report augmentation to assist crowdsourced testing. Front Comput Sci, 2019, 13: 943-959 CrossRef Google Scholar

[44] Li X C, Jiang H, Kamei Y, et al. Bridging semantic gaps between natural languages and APIs with word embedding. IEEE Trans Softw Eng, 2018. doi: 10.1109/TSE.2018.2876006. Google Scholar

[45] Li X C, Jiang H, Liu D, et al. Unsupervised Deep Bug Report Summarization. In: Proceedings of IEEE/ACM International Conference on Program Comprehension, 2018. 144--155. Google Scholar

[46] Mou L L, Li G, Zhang L, et al. Convolutional Neural Networks over Tree Structures for Programming Language Processing. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence, 2016. 1287--1293. Google Scholar

  • Figure 1

    The structure of compiler

  • Figure 2

    Procedure of publication analysis

  • Figure 3

    (Color online) The number of publications per year

  • Figure 4

    (Color online) Venues of publications

  • Figure 5

    (Color online) Heuristic search algorithms and objectives

  • Figure 6

    (Color online) Machine learning algorithms and objectives

  • Figure 7

    (Color online) Statistical results of research types

  • Figure 8

    (Color online) Statistical results of target compilers

  • Figure 9

    (Color online) Statistical results of target benchmarks

  • Table 1   Full names of publication venues
    Abbreviation Full name of journals/conferences
    LCTES ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems
    TACO ACM Transactions on Architecture and Code Optimization
    CGO IEEE/ACM International Symposium on Code Generation and Optimization
    SCCC International Conference of the Chilean Computer Science Society
    EDCC European Dependable Computing Conference
    CASES International Conference on Compilers, Architecture, and Synthesis for Embedded Systems
    TJSC The Journal of Supercomputing
    IJPP International Journal of Parallel Programming
  • Table 2   The comparison between heuristic search and machine learning
    Heuristic algorithms Machine learning
    Input Encode Feature representation
    Output Compiler optimization sequence Compiler optimization sequence
    Training set Unnecessary Necessary
    Time consuming Long Short
  • Table 3   Authors and their publication frequencies
    ID Author Frequency
    1 John Cavazos 9
    2 Prasad A. Kulkarni 7
    3 David Whalley 6
    4 Amir Hossein Ashouri 5
    5 Cristina Silvano 5
    6 Eunjung Park 5
    7 Gianluca Palermo 5
    8 Jack Davidson 5
    9 Joao M. P. Cardoso 5
    10 Keith D. Cooper 5
    11 Ricardo Nobre 5

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备17057255号       京公网安备11010102003388号