The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combine

References

• Agakov, F., Bonilla, E., Cavazos, J., Franke, B., Fursin, G., O'Boyle, M. F. P., Thomson, J., Toussaint, M., & Williams, C. K. I. (2006). Using machine learning to focus on iterative optimization. International Symposium on Code Generation and Optimization (CGO’06). IEEE, 11-pp. https://doi.org/10.1109/CGO.2006.37
   Google Scholar
• Agakov, F., Bonilla, E., Cavazos, J., et al. (2006). Using machine learning to focus on iterative optimization. International Symposium on Code Generation and Optimization (CGO’06). IEEE, 11-pp. https://doi.org/10.1109/CGO.2006.37
   Google Scholar
• Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2007). Compilers: Principles, techniques, & tools. Pearson Education India.
   Google Scholar
• Almagor, L., Cooper, K. D., Grosul, A., Harvey, T. J., Reeves, S. W., Subramanian, D., Torczon, L., & Waterman, T. (2004). Finding effective compilation sequences. ACM SIGPLAN Notices, 39(7), 231–239. https://doi.org/10.1145/998300.997196
   Google Scholar
• Ammann, U. (1977). On code generation in a PASCAL compiler. Software: Practice and Experience, 7(3), 391–423. https://doi.org/10.1002/spe.4380070311
   Web of Science ®Google Scholar
• Asanović, K., & Patterson, D. A. (2014). Instruction sets should be free: The case for risc-v. EECS Department, University of California, Berkeley, Tech. Rep. UCB/ EECS-2014-146.
   Google Scholar
• Ashouri, A. H., Bignoli, A., Palermo, G., & Silvano, C. (2016). Predictive modeling methodology for compiler phase-ordering. 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, 7–12. https://doi.org/10.1145/2872421.2872424
   Google Scholar
• Ashouri, A. H., Bignoli, A., Palermo, G., Silvano, C., Kulkarni, S., & Cavazos, J. (2017). Micomp: Mitigating the compiler phase-ordering problem using optimization subsequences and machine learning. ACM Transactions on Architecture and Code Optimization (TACO), 14(3), 1–28. https://doi.org/10.1145/3124452
   Web of Science ®Google Scholar
• Aycock, J. (2003). A brief history of just-in-time. ACM Computing Surveys (CSUR), 35(2), 97–113. https://doi.org/10.1145/857076.857077
   Web of Science ®Google Scholar
• Batten, D., Jinturkar, S., Glossner, J., Schulte, M., & D’Arcy, P. (2000). A new approach to dsp intrinsic functions. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. IEEE, 10–pp. https://doi.org/10.1109/HICSS.2000.926967
   Google Scholar
• Beeler, M. (1972). Item 120 in m. beeler, r. w. gosper, and r. schroeppel, hakmem.
   Google Scholar
• Bornat, R. (1979). Understanding and writing compilers: A do-it-yourself guide. Macmillan International Higher Education.
   Google Scholar
• Consortium, E. M. B. (2018). Coremark: An eembc benchmark.
   Google Scholar
• Cooper, K. D., Grosul, A., Harvey, T. J., Reeves, S., Subramanian, D., Torczon, L., & Waterman, T. (2005). Acme: Adaptive compilation made efficient. ACM SIGPLAN Notices, 40(7), 69–77. https://doi.org/10.1145/1070891.1065921
   Google Scholar
• Ebner, D., Brandner, F., Scholz, B., Krall, A., Wiedermann, P., & Kadlec, A. (2008). Generalized instruction selection using ssa-graphs. Proceedings of the 2008 ACM SIGPLAN-SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems, 43(7), 31–40. https://doi.org/10.1145/1375657.1375663
   Google Scholar
• Engelfriet, A. (2009). Choosing an open source license. IEEE Software, 27(1), 48–49. https://doi.org/10.1109/MS.2010.5
   Web of Science ®Google Scholar
• Garciarena, U., & Santana, R. (2016). Evolutionary optimization of compiler flag selection by learning and exploiting flags interactions. Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion, 1159–1166. https://doi.org/10.1145/2908961.2931696
   Google Scholar
• Granlund, T., & Montgomery, P. L. (1994). Division by invariant integers using multiplication. Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation, 61–72. https://doi.org/10.1145/178243.178249
   Google Scholar
• Haj-Ali, A., Huang, Q. J., Xiang, J., Moses, W., Asanovic, K., Wawrzynek, J., & Stoica, I. (2020). Autophase: Juggling hls phase orderings in random forests with deep reinforcement learning. Proceedings of Machine Learning and Systems, 2, 70–81. https://doi.org/10.48550/arXiv.2003.00671
   Google Scholar
• Johnson, R. A., & Wichern, D. W. (2014). Applied multivariate statistical analysis. Pearson London, UK: 2014, vol. 6.
   Google Scholar
• Kane, G., & Heinrich, J. (1992). MIPS RISC architectures. Prentice-Hall, Inc.
   Google Scholar
• Kisuki, T., Knijnenburg, P. M., & O’Boyle, M. F. (2000). Combined selection of tile sizes and unroll factors using iterative compilation. Proceedings 2000 International Conference on Parallel Architectures and Compilation Techniques (Cat. No. PR00622) (pp. 237–246). IEEE. https://doi.org/10.1109/PACT.2000.888348
   Google Scholar
• Knoop, J., Rüthing, O., & Steffen, B. (1994). Partial dead code elimination. ACM Sigplan Notices, 29(6), 147–158. https://doi.org/10.1145/773473.178256
   Google Scholar
• Lattner, C., & Adve, V. (2004). LLVM: A compilation framework for lifelong program analysis & transformation. International Symposium on Code Generation and Optimization, 2004. CGO 2004 (pp. 75–86), IEEE. https://doi.org/10.1109/CGO.2004.1281665
   Google Scholar
• Lattner, C., contributors. (2022). LLVM test-suite repository. https://github.com/llvm/llvmtest-suite
   Google Scholar
• Li, S. S., Peeler, H., Sloss, A. N., Reid, K. N., & Banzhaf, W. (2022). Genetic improvement in the shackleton framework for optimizing LLVM pass sequences. GECCO ‘22: Proceedings of the Genetic and Evolutionary Computation Conference Companion, 1938–1939. GECCO. https://doi.org/10.1145/3520304.3534000
   Google Scholar
• Longbottom, R. (2005). Whetstone benchmark history and results.
   Google Scholar
• Mammadli, R., Jannesari, A., & Wolf, F. (2020). Static neural compiler optimization via deep reinforcement learning. 2020 IEEE/ACM 6th Workshop on the LLVM Compiler Infrastructure in HPC (LLVM-HPC) and Workshop on Hierarchical Parallelism for Exascale Computing (HiPar). IEEE, 1–11. https://doi.org/10.1109/LLVMHPCHiPar51896.2020.00006
   Google Scholar
• Muchnick, S. S. (1997). Advanced compiler design implementation. Morgan kaufmann.
   Google Scholar
• Park, E., Cavazos, J., Pouchet, L. N., Bastoul, C., Cohen, A., & Sadayappan, P. (2013). Predictive modeling in a polyhedral optimization space. International Journal of Parallel Programming, 41(5), 704–750. https://doi.org/10.1109/CGO.2011.5764680
   Web of Science ®Google Scholar
• Peeler, H., Li, S. S., Sloss, A. N., Reid, K. N., Yuan, Y., & Banzhaf, W. (2022). Optimizing LLVM pass sequences with shackleton: A linear genetic programming framework. GECCO ‘22: Proceedings of the Genetic and Evolutionary Computation Conference Companion (pp. 578–581). GECCO. https://doi.org/10.1145/3520304.3528945
   Google Scholar
• Rigger, M., Marr, S., Kell, S., Leopoldseder, D., & Mössenböck, H. (2018). An analysis of x86-64 inline assembly in c programs. Proceedings of the 14th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments. ACM SIGPLAN Notices, 53(3), 84–99. https://doi.org/10.1145/3296975.3186418
   Google Scholar
• Stallman, R. M. (1998). Using and porting GNU CC (Vol 675). Free Software Foundation.
   Google Scholar
• Wade, A. W., Kulkarni, P. A., & Jantz, M. R. (2017). AOT vs. JIT: Impact of profile data on code quality. Proceedings of the 18th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems, 52(5), 1–10. https://doi.org/10.1145/3140582.3081037
   Google Scholar
• Weicker, R. P. (1984). Dhrystone: A synthetic systems programming benchmark. Communications of the ACM, 27(10), 1013–1030. https://doi.org/10.1145/358274.358283
   Web of Science ®Google Scholar
• You, Y. P., & Su, Y. C. (2022). Reduced O3 subsequence labelling: A stepping stone towards optimisation sequence prediction. Connection Science, 34(1), 2860–2877. https://doi.org/10.1080/09540091.2022.2044761
   Web of Science ®Google Scholar