Home  |  About Journal  |  Editorial Board  |  For Authors  |  For Referees  |  For Readers  |  Subscription  |  Contract Us
International Journal of Automation and Computing 2018, Vol. 15 Issue (2) :228-238    DOI: 10.1007/s11633-017-1100-0
Research Articles Current Issue | Next Issue | Archive | Adv Search << Previous Articles | Next Articles >>
Improving on Linear Scan Register Allocation
Shahrzad Kananizadeh1, Kirill Kononenko2
1 Department of Computer Science, Saarland University, Saarbrücken, Germany;
2 École Normale Supérieure/French Institute for Research in Computer Science and Automation(INRIA), Paris, France
Download: [PDF 2134KB] HTML()   Export: BibTeX or EndNote (RIS)      Supporting Info
Abstract Register allocation is a major step for all compilers. Various register allocation algorithms have been developed over the decades. This work describes a new class of rapid register allocation algorithms and presents experimental data on their behavior. Our research encourages the avoidance of graphing and graph-coloring based on the fact that precise graph-coloring is nondeterministic polynomial time-complete (NP-complete), which is not suitable for real-time tasks. In addition, practical graph-coloring algorithms tend to use polynomial-time heuristics. In dynamic compilation environments, their super linear complexity makes them unsuitable for register allocation and code generation. Existing tools for code generation and register allocation do not completely fulfill the requirements of fast compilation. Existing approaches either do not allow for the optimization of register allocation to be achieved comprehensively with a sufficient degree of performance or they require an unjustifiable amount of time and/or resources. Therefore, we propose a new class of register allocation and code generation algorithms that can be performed in linear time. These algorithms are based on the mathematical foundations of abstract interpretation and the computation of the level of abstraction. They have been implemented in a specialized library for just-in-time compilation. The specialization of this library involves the execution of common intermediate language (CIL) and low level virtual machine (LLVM) with a focus on embedded systems.
Email this article
Add to my bookshelf
Add to citation manager
Email Alert
Articles by authors
KeywordsRegister allocation   just-in-time compilation   code generation   static analysis   dynamic analysis     
Received: 2016-11-07; Revised: 2017-08-02; published: 2017-08-16
Corresponding Authors: Kirill Kononenko     Email: kirill.kononenko@acm.org
About author: Shahrzad Kananizadeh received the B.Sc. degree in cyber security from University of Tubingen, Germany. She is currently a researcher at Saarland University, Germany and works in Robert Bosch, Germany.E-mail:kananiz_sh@hotmail.com;Kirill Kononenko is a mathematician who is interested in the theoretical and mathematical foundations of computer science.E-mail:kirill.kononenko@acm.org
Cite this article:   
Shahrzad Kananizadeh, Kirill Kononenko. Improving on Linear Scan Register Allocation[J]. International Journal of Automation and Computing , vol. 15, no. 2, pp. 228-238, 2018.
http://www.ijac.net/EN/10.1007/s11633-017-1100-0      或     http://www.ijac.net/EN/Y2018/V15/I2/228
[1] Cocke J. and Markstein P., Measurement of code improvement algorithms, S. Lavington, editor, Proceedings of the IFIP Congress, 1980, Tokyo, Japan, 1980, 221-228.
[2] Ershov A., The Alpha automatic programming system, Academic Press, New York, NY, USA, 1971.
[3] Schwartz J., On Programming:An interim report on the SETL project, Courant Institute of Mathematical Sciences, New York, NY, USA, 1973.
[4] Chaitin G., Auslander M., Chandra A., Cocke J., Hopkins M., and Markstein P., Register allocation via coloring, Journal of Computer Languages, 1981, 47-57.
[5] Chaitin G., Register allocation & spilling via graph coloring, Proceedings of the 1982 ACM SIGPLAN Symposium on Compiler Construction, ACM Press, New York, NY, USA, 1982, 98-101.
[6] Chow F. and Hennessy J., The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems, New York, NY, USA, 1990, 501-536.
[7] Vivek S. and Rajkishore B.. 2007. Extended linear scan:an alternate foundation for global register allocation. In Proceedings of the 16th international conference on Compiler construction (CC'07), Shriram Krishnamurthi and Martin Odersky. Springer-Verlag, Berlin, Heidelberg, 141-155.
[8] Traub O., Holloway G., and Smith M., Quality and speed in linear scan register allocation, in proceedings of the 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation, New York, NY, USA, 1998, 142-151.
[9] Gruia C. and Minming L.. 2015. Register Loading via Linear Programming. Algorithmica 72, 4(August 2015), 1011-1032. DOI=http://dx.doi.org/10.1007/s00453-014-9888-2
[10] Pereira F. M. Q. and Palsberg J.. 2008. Register allocation by puzzle solving. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'08). ACM, New York, NY, USA, 216-226. DOI=http://dx.doi.org/10.1145/1375581.1375609
[11] Callahan D. and Koblenz B., Register Allocation via hierarchical graph coloring, Proceedings of the 1991 ACM SIGPLAN Conference on Programming Language Design and Implementation, 1991, New York, NY, USA, 192-203.
[12] Mohr M., Grudnitsky A., Modschiedler T., Bauer L., Hack S., and Henkel J.. 2013. Hardware acceleration for programs in SSA form. In Proceedings of the 2013 International Conference on Compilers, Architectures and Synthesis for Embedded Systems(CASES'13). IEEE Press, Piscataway, NJ, USA,, Article 14, 10 pages.
[13] Cousot P., Cousot R., Static determination of dynamic properties of programs, B. Robinet, editor, Proceedings of the 2nd International Symposium of Programming, Paris, France, Dunod, Paris, april 13-15, 1976, 106-130.
[14] Cousot P. and Cousot R. 2014. Abstract interpretation:past, present and future. In Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (CSL-LICS'14). ACM, New York, NY, USA, Article 2, 10 pages.
[15] Cousot P., Cousot R., and Laurent Mauborgne. 2013. Theories, solvers and static analysis by abstract interpretation. J. ACM 59, 6, Article 31(January 2013), 56 pages.
[16] Wimmer C., and Franz M., 2010. Linear scan register allocation on SSA form. In Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization (CGO'10). ACM, New York, NY, USA, 170-179. DOI=http://dx.doi.org/10.1145/1772954.1772979
[17] Barik R., Zhao J., Sarkar V.. 2013. A decoupled non-SSA global register allocation using bipartite liveness graphs. ACM Trans. Archit. Code Optim. 10, 4, Article 63(December 2013), 24 pages. DOI=http://dx.doi.org/10.1145/2544101
[18] Calinescu G., Li M., 2015. Register Loading via Linear Programming. Algorithmica 72, 4(August 2015), 1011-1032.
[19] Cooper K. D., Dasgupta A., Eckhardt J., 2005. Revisiting graph coloring register allocation:a study of the chaitin-briggs and callahan-koblenz algorithms. In Proceedings of the 18th international conference on Languages and Compilers for Parallel Computing (LCPC'05), Eduard Ayguadé, Gerald Baumgartner, J. Ramanujam, and P.Sadayappan (Eds.). Springer-Verlag, Berlin, Heidelberg, 1-16.
[20] Hongbo R. 2009. Tree register allocation. In Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO 42). ACM, New York, NY, USA, 67-77.
[21] Rastello F., Diouf B., Cohen A.. 2013. A polynomial spilling heuristic:Layered allocation. In Proceedings of the 2013 IEEE. ACM International Symposium on Code Generation and Optimization (CGO) (CGO'13). IEEE Computer Society, Washington, DC, USA, 1-10.
[22] Kononenko, K. Libjit linear scan:a model for fast and efficient compilation. In International Review on Modelling and Simulations (October 2010), vol. 3 N.5, pp. 1035-1044.
[23] Kononenko, K. A unified approach to identifying and healing vulnerabilities in x86 machine code. In Proceedings of the 18th Annual International Conference on Mobile Computing and Networking (New York, NY, USA, 2012), Mobicom'12, ACM, pp. 397-398.
[24] Dang-Dang Niu, Lei Liu, Xin Zhang, Shuai Lü, Zhuang Li. Security Analysis Model, System Architecture and Relational Model of Enterprise Cloud Services. International Journal of Automation and Computing, vol. 13, no. 6, pp. 574-584, 2016.
[25] Miller F. P., Vandome A. F., and McBrewster J. 2009. Mono (Software):Monodevelop, Software Patents and Free Software, Novell, Comparison of Application Virtual Machines, Dotgnu, Portable.Net,.NET Framework,... Free and Open Source Software, Ximian. Alpha Press.
[26] Pandey M., and Sarda S. LLVM Cookbook. Packt Publishing, 2015.
[27] Zhao J., Nagarakatte S., Milo M.K. Martin, and Zdancewic S. 2013. Formal verification of SSA-based optimizations for LLVM. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'13). ACM, New York, NY, USA, 175-186.
[28] Colombet Q., Brandner F., and Darte A. 2015. Studying Optimal Spilling in the Light of SSA. ACM Trans. Archit. Code Optim. 11, 4, Article 47(January 2015), 26 pages.
[29] Jiang I. H., Gi-Joon N., Chang H., Nassif S. R., and Hayes J. 2014. Smart grid load balancing techniques via simultaneous switch/tie-line/wire configurations. In Proceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design (ICCAD'14). IEEE Press, Piscataway, NJ, USA, 382-388.
[30] Eisl J.. 2015. Trace register allocation. In Companion Proceedings of the 2015 ACM SIGPLAN International Conference on Systems, Programming, Languages and Applications:Software for Humanity (SPLASH Companion 2015). ACM, New York, NY, USA, 21-23.
[31] Krause P. K. 2014. The complexity of register allocation. Discrete Appl. Math. 168(May 2014), 51-59.
[32] Lozano R. C., Carlsson M., Drejhammar F., and Schulte Ch.. 2012. Constraint-Based register allocation and instruction scheduling. In Proceedings of the 18th international conference on Principles and Practice of Constraint Programming (CP'12), Michela Milano (Ed.). Springer-Verlag, Berlin, Heidelberg, 750-766.
[33] Krause P. K. 2013. Optimal register allocation in polynomial time. In Proceedings of the 22nd international conference on Compiler Construction (CC'13), Ranjit Jhala and Koen Bosschere (Eds.). Springer-Verlag, Berlin, Heidelberg, 1-20.
[34] Colombet Q., Boissinot B., Brisk P., Hack S., and Rastello F. 2011. Graph-coloring and treescan register allocation using repairing. In Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems (CASES'11).
[35] Davis T., Karlsson C., Liu H., Ding C., and Chen Z. High performance linpack benchmark:A fault tolerant implementation without checkpointing. In Proceedings of the International Conference on Supercomputing (New York, NY, USA, 2011), ICS'11, ACM, pp. 162-171.
[36] Dick J. R., Kent K. B., and Libby J. C. A quantitative analysis of the.net common language runtime. J. Syst. Archit. 54, 7(July 2008), 679-696.
[37] Krause P. K. 2015. Bytewise Register Allocation. In Proceedings of the 18th International Workshop on Software and Compilers for Embedded Systems (SCOPES'15). ACM, New York, NY, USA, 22-27. DOI=http://dx.doi.org/10.1145/2764967.2764971
[38] Bouchez F. A Study of Spilling and Coalescing in Register Allocation as Two Separate Phases. PhD thesis, ENS Lyon, France, apr 2009.
[39] Hack S. Register Allocation for Programs in SSA Form. PhD thesis, Universität Karlsruhe, October 2007.
[40] Boissinot B., Brandner F., Darte A., Dupont de Dinechin B., and Rastello F. 2011. A non-iterative data-flow algorithm for computing liveness sets in strict SSA programs. In Proceedings of the 9th Asian conference on Programming Languages and Systems(APLAS'11), Hongseok Yang (Ed.). Springer-Verlag, Berlin, Heidelberg, 137-154. DOI=http://dx.doi.org/10.1007/978-3-642-25318-8_13
[41] Boissinot B., Brisk Ph., Darte A., and Rastello F. 2012. SSI Properties Revisited. ACM Trans. Embed. Comput. Syst. 11S, 1, Article 21(June 2012), 23 pages.DOI=http://dx.doi.org/10.1145/2180887.2180898
[42] Brisk Ph., Sarrafzadeh M. 2007. Interference graphs for procedures in static single information form are interval graphs. In Proceedings of the 10th international workshop on Software & compilers for embedded systems (SCOPES'07), Heiko Falk and Peter Marwedel (Eds.). ACM, New York, NY, USA, 101-110. DOI=http://dx.doi.org/10.1145/1269843.1269858
[43] Knuth, D.E., 1997. Art of Computer Programming, Volume 2:Seminumerical Algorithms. 3rd Ed. Addison-Wesley, ISBN:0201896842, pp:784
[44] A. F. Deon and Y. A. Menyaev. The Complete Set Simulation of Stochastic Sequences without Repeated and Skipped Elements, Journal of Universal Computer Science, vol.22(8), pp.1023-1047, 2016
[45] A. F. Deon and Y. A. Menyaev. Parametrical Tuning of Twisting Generators, Journal of Computer Science, vol.12(8), pp.363-378, 2016.
[46] Odaira R., Nakaike T, Inagaki T, Komatsu H., and Nakatani T. 2010. Coloring-based coalescing for graph coloring register allocation. In Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization (CGO'10). ACM, New York, NY, USA, 160-169. DOI=http://dx.doi.org/10.1145/1772954.1772978
[47] Pereira, F. M. Q.:Register Allocation by Puzzle Solving. PhD thesis, University of California, Los Angeles (2008)
[48] Smith M. D., Ramsey N., and Holloway G. 2004. A generalized algorithm for graphcoloring register allocation. SIGPLAN Not. 39, 6(June 2004), 277-288. DOI=http://dx.doi.org/10.1145/996893.996875.
[49] Quan Liang, Yuan-Zhuo Wang, Yong-Hui Zhang. Resource Virtualization Model Using Hybrid-graph Representation and Converging Algorithm for Cloud Computing. International Journal of Automation and Computing, vol. 10, no. 6, pp. 597-606, 2013.
No similar article found!
Copyright 2010 by International Journal of Automation and Computing