{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:09:26Z","timestamp":1763467766966,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2006,3]]},"abstract":"<jats:p>\n            Architectures with a register stack can implement efficient calling conventions. Using the overlapping of callers' and callees' registers, callers are able to pass parameters to callees without a memory stack. The most recent instance of a register stack can be found in the Intel Itanium architecture. A hardware component called the register stack engine (RSE) provides an illusion of an infinite-length register stack using a memory-backed process to handle overflow and underflow for a physically limited number of registers. Despite such hardware support, some applications suffer from the overhead required to handle register stack overflow and underflow. The memory latency associated with the overflow and underflow of a register stack can be reduced by generating multiple register allocation instructions within a procedure [Settle et al. 2003]. Live analysis is utilized to find a set of registers that are not required to keep their values across procedure boundaries. However, among those dead registers, only the registers that are consecutively located in a certain part of the register stack frame can be removed. We propose a compiler-supported register reassignment technique that reduces RSE overflow\/underflow further. By reassigning registers based on live analysis, our technique forces as many dead registers to be removed as possible. We define the problem of optimal register reassignment, which minimizes interprocedural register stack heights considering multiple call sites within a procedure. We present how this problem is related to a\n            <jats:italic>path-finding problem<\/jats:italic>\n            in a graph called a\n            <jats:italic>sequence graph<\/jats:italic>\n            . We also propose an efficient heuristic algorithm for the problem. Finally, we present the measurement of effects of the proposed techniques on SPEC CINT2000 benchmark suite and the analysis of the results. The result shows that our approach reduces the RSE cycles by 6.4% and total cpu cycles by 1.7% on average.\n          <\/jats:p>","DOI":"10.1145\/1132462.1132467","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"90-114","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimal register reassignment for register stack overflow minimization"],"prefix":"10.1145","volume":"3","author":[{"given":"Yoonseo","family":"Choi","sequence":"first","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Daejeon, Korea"}]},{"given":"Hwansoo","family":"Han","sequence":"additional","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Daejeon, Korea"}]}],"member":"320","published-online":{"date-parts":[[2006,3]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/177492.177575"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the SIGPLAN'82 Symposium on Compiler Construction. 201--207","author":"Chaitin G.","year":"1982","unstructured":"Chaitin , G. 1982 . Register allocation and spilling via graph coloring . In Proceedings of the SIGPLAN'82 Symposium on Compiler Construction. 201--207 . 10.1145\/800230.806984 Chaitin, G. 1982. Register allocation and spilling via graph coloring. In Proceedings of the SIGPLAN'82 Symposium on Compiler Construction. 201--207. 10.1145\/800230.806984"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation. 85--94","author":"Chow F.","year":"1988","unstructured":"Chow , F. 1988 . Minimizing register usage penalty at procedure calls . In Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation. 85--94 . 10.1145\/53990.53999 Chow, F. 1988. Minimizing register usage penalty at procedure calls. In Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation. 85--94. 10.1145\/53990.53999"},{"volume-title":"Proceedings of the SIGPLAN'84 Symposium on Compiler Construction. 222--232","author":"Chow F.","unstructured":"Chow , F. and Hennessy , J . 1984. Register allocation by priority-based coloring . In Proceedings of the SIGPLAN'84 Symposium on Compiler Construction. 222--232 . 10.1145\/502874.502896 Chow, F. and Hennessy, J. 1984. Register allocation by priority-based coloring. In Proceedings of the SIGPLAN'84 Symposium on Compiler Construction. 222--232. 10.1145\/502874.502896","key":"e_1_2_1_4_1"},{"volume-title":"15th Workshop on Languages and Compilers for Parallel Computing. 10","author":"Douillet A.","unstructured":"Douillet , A. , Amaral , J. , and Gao , G . 2002. Fine-grained stacked register allocation for the itanium architecture . In 15th Workshop on Languages and Compilers for Parallel Computing. 10 .1007\/11596110_23 Douillet, A., Amaral, J., and Gao, G. 2002. Fine-grained stacked register allocation for the itanium architecture. In 15th Workshop on Languages and Compilers for Parallel Computing. 10.1007\/11596110_23","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 37th International Symposium on Microarchitecture. 294--303","author":"Hoflehner G.","year":"2004","unstructured":"Hoflehner , G. , Kirkegaard , K. , Skinner , R. , Lavery , D. , and Lee , Y . 2004. Compiler optimizations for transaction processing workloads on itanium linux systems . In Proceedings of the 37th International Symposium on Microarchitecture. 294--303 . 10.1109\/MICRO. 2004 .11 Hoflehner, G., Kirkegaard, K., Skinner, R., Lavery, D., and Lee, Y. 2004. Compiler optimizations for transaction processing workloads on itanium linux systems. In Proceedings of the 37th International Symposium on Microarchitecture. 294--303. 10.1109\/MICRO.2004.11"},{"volume-title":"Intel Itanium Architecture Software Developer's Manual","author":"Intel Corporation 2002.","unstructured":"Intel Corporation 2002. Intel Itanium Architecture Software Developer's Manual . Intel Corporation , Santa Clara, CA . Intel Corporation 2002. Intel Itanium Architecture Software Developer's Manual. Intel Corporation, Santa Clara, CA.","key":"e_1_2_1_7_1"},{"volume-title":"Open Research Compiler for Itanium Processor Family (ORC version 2.1)","author":"Intel Corporation and Chinese Academy of Sciences 2002.","unstructured":"Intel Corporation and Chinese Academy of Sciences 2002. Open Research Compiler for Itanium Processor Family (ORC version 2.1) . Intel Corporation and Chinese Academy of Sciences , http:\/\/ipf-orc.sourceforge.net. Intel Corporation and Chinese Academy of Sciences 2002. Open Research Compiler for Itanium Processor Family (ORC version 2.1). Intel Corporation and Chinese Academy of Sciences, http:\/\/ipf-orc.sourceforge.net.","key":"e_1_2_1_8_1"},{"volume-title":"Proceedings of the 23rd SIGPLAN-SIGACT Symposium on Principles of Programming Language. 230--241","author":"Kurlander S.","unstructured":"Kurlander , S. and Fisher , C . 1996. Minimum cost interprocedural register allocation . In Proceedings of the 23rd SIGPLAN-SIGACT Symposium on Principles of Programming Language. 230--241 . 10.1145\/237721.237780 Kurlander, S. and Fisher, C. 1996. Minimum cost interprocedural register allocation. In Proceedings of the 23rd SIGPLAN-SIGACT Symposium on Principles of Programming Language. 230--241. 10.1145\/237721.237780","key":"e_1_2_1_9_1"},{"volume-title":"Proceedings of the SIGPLAN'97 Conference on Programming Language Design and Implementation. 296--307","author":"Lueh G.","unstructured":"Lueh , G. and Gross , T . 1997. Call-cost directed register allocation . In Proceedings of the SIGPLAN'97 Conference on Programming Language Design and Implementation. 296--307 . 10.1145\/258915.258942 Lueh, G. and Gross, T. 1997. Call-cost directed register allocation. In Proceedings of the SIGPLAN'97 Conference on Programming Language Design and Implementation. 296--307. 10.1145\/258915.258942","key":"e_1_2_1_10_1"},{"volume-title":"Proceedings of the International Symposium on Code Generation and Optimization. 115--124","author":"Settle A.","unstructured":"Settle , A. , Connors , D. , Hoflehner , G. , and Lavery , D . 2003. Optimization for the intel itanium architecture register stack . In Proceedings of the International Symposium on Code Generation and Optimization. 115--124 . Settle, A., Connors, D., Hoflehner, G., and Lavery, D. 2003. Optimization for the intel itanium architecture register stack. In Proceedings of the International Symposium on Code Generation and Optimization. 115--124.","key":"e_1_2_1_11_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/59287.59289"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the SIGPLAN'86 Symposium on Compiler Construction. 264--275","author":"Wall D.","year":"1986","unstructured":"Wall , D. 1986 . Global register allocation at link time . In Proceedings of the SIGPLAN'86 Symposium on Compiler Construction. 264--275 . 10.1145\/12276.13338 Wall, D. 1986. Global register allocation at link time. In Proceedings of the SIGPLAN'86 Symposium on Compiler Construction. 264--275. 10.1145\/12276.13338"},{"unstructured":"Weaver D. and Germond T. 1994. The SPARC Architecture Manual. SPARC International Inc. Menlo Park CA.   Weaver D. and Germond T. 1994. The SPARC Architecture Manual. SPARC International Inc. Menlo Park CA.","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the Sixth Workshop on Interaction between Compilers and Computer Architectures","author":"Weldon R.","unstructured":"Weldon , R. , Chang , S. , Wang , H. , Hoflehner , G. , Wang , P. , Lavery , D. , and Shen , J . 2002. Quantitative evaluation of the register stack engine and optimization for future itanium processors . In Proceedings of the Sixth Workshop on Interaction between Compilers and Computer Architectures . Boston. Weldon, R., Chang, S., Wang, H., Hoflehner, G., Wang, P., Lavery, D., and Shen, J. 2002. Quantitative evaluation of the register stack engine and optimization for future itanium processors. In Proceedings of the Sixth Workshop on Interaction between Compilers and Computer Architectures. Boston.","key":"e_1_2_1_15_1"},{"volume-title":"Proceedings of the 17th International Conference on Supercomputing. 215--225","author":"Yang L.","unstructured":"Yang , L. , Chan , S. , Gao , G. , Ju , R. , Lueh , G. , and Zhang , Z . 2003. Inter-procedural stacked register allocation for itanium like architecture . In Proceedings of the 17th International Conference on Supercomputing. 215--225 . 10.1145\/782814.782844 Yang, L., Chan, S., Gao, G., Ju, R., Lueh, G., and Zhang, Z. 2003. Inter-procedural stacked register allocation for itanium like architecture. In Proceedings of the 17th International Conference on Supercomputing. 215--225. 10.1145\/782814.782844","key":"e_1_2_1_16_1"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132462.1132467","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132462.1132467","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:50Z","timestamp":1750263530000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132462.1132467"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1132462.1132467"],"URL":"https:\/\/doi.org\/10.1145\/1132462.1132467","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2006,3]]},"assertion":[{"value":"2006-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}