{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:44:26Z","timestamp":1750308266266,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2004,11,1]],"date-time":"2004-11-01T00:00:00Z","timestamp":1099267200000},"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. Program. Lang. Syst."],"published-print":{"date-parts":[[2004,11]]},"abstract":"<jats:p>In this work, we describe a \"just-in-time,\" &lt;i&gt;usage density-based register allocator&lt;\/i&gt; geared toward embedded systems with a limited general-purpose register set wherein speed, code size, and memory requirements are of equal concern. The main attraction of the allocator is that it does not make use of the traditional live range and interval analysis nor does it perform advanced optimizations based on range &lt;i&gt;splitting&lt;\/i&gt; but results in very good code quality. We circumvent the need for traditional analysis by using a measure of &lt;i&gt;usage density&lt;\/i&gt; of a variable. The usage density of a variable at a program point represents both the frequency and the density of the uses. We contend that by using this measure we can capture both &lt;i&gt;range&lt;\/i&gt; and &lt;i&gt;frequency&lt;\/i&gt; information which is essentially used by the good allocators based on &lt;i&gt;splitting&lt;\/i&gt;. We describe a framework based on this measure which has a linear complexity in terms of the program size. We perform comparisons with the static allocators based on graph coloring and the ones targeted toward just-in-time compilation systems like linear scan of live ranges. Through comparisons with graph coloring (Brigg's style) and live range-based (linear scan) allocators, we show that the memory footprint and the size of our allocator are smaller by 20% to 30%. The speed of allocation is comparable and the speed of the generated code is better and its size smaller. These attributes make the allocator an attractive candidate for performing a fast, memory-efficient register allocation for embedded devices with a small number of registers.<\/jats:p>","DOI":"10.1145\/1034774.1034776","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:35:53Z","timestamp":1106757353000},"page":"938-974","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A fast, memory-efficient register allocation framework for embedded systems"],"prefix":"10.1145","volume":"26","author":[{"given":"Sathyanarayanan","family":"Thammanur","sequence":"first","affiliation":[{"name":"University of Cincinnati, Cincinnati, OH"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Santosh","family":"Pande","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2004,11]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/349299.349303"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/73141.74841"},{"key":"e_1_2_1_3_1","volume-title":"Rematerialization. In Proceedings of PLDI 1992 (June). 311--321","author":"Briggs P.","year":"1992","unstructured":"Briggs , P. 1992 . Rematerialization. In Proceedings of PLDI 1992 (June). 311--321 . 10.1145\/143095.143143 Briggs, P. 1992. Rematerialization. In Proceedings of PLDI 1992 (June). 311--321. 10.1145\/143095.143143"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/73141.74843"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/177492.177575"},{"volume-title":"Proceedings of the ACM Java Grande Conference (June). 10","author":"Burke M. G.","unstructured":"Burke , M. G. , Choi , J. , Fink , S. , Grove , D. , Hind , M. , Sarkar , V. , Serrano , M. J. , Sreedhar , V. C. , and Srinivasan , H . 1999. The Jalapeno dynamic optimizing compiler for Java . In Proceedings of the ACM Java Grande Conference (June). 10 .1145\/304065.304113 Burke, M. G., Choi, J., Fink, S., Grove, D., Hind, M., Sarkar, V., Serrano, M. J., Sreedhar, V. C., and Srinivasan, H. 1999. The Jalapeno dynamic optimizing compiler for Java. In Proceedings of the ACM Java Grande Conference (June). 10.1145\/304065.304113","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the Symposium on Compiler Construction 1982 (June). 98--105","author":"Chaitin G.","year":"1982","unstructured":"Chaitin , G. 1982 . Register allocation and spilling via graph coloring . In Proceedings of the Symposium on Compiler Construction 1982 (June). 98--105 . 10.1145\/800230.806984 Chaitin, G. 1982. Register allocation and spilling via graph coloring. In Proceedings of the Symposium on Compiler Construction 1982 (June). 98--105. 10.1145\/800230.806984"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","article-title":"Register allocation via coloring","volume":"6","author":"Chaitin G.","year":"1981","unstructured":"Chaitin , G. , Auslander , M. , Chandra , A. , Cocke , J. , Hopkins , M. , and Markstein , P. 1981 . Register allocation via coloring . Comput. Lang. 6 , 47 -- 57 . Chaitin, G., Auslander, M., Chandra, A., Cocke, J., Hopkins, M., and Markstein, P. 1981. Register allocation via coloring. Comput. Lang. 6, 47--57.","journal-title":"Comput. Lang."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/88616.88621"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/237721.237767"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/237721.237765"},{"key":"e_1_2_1_12_1","first-page":"163","volume-title":"Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (June).","author":"Grant B.","unstructured":"Grant , B. , Mock , M. , Philipose , M. , Chambers , C. , and Eggers , S . 1997. Annotation-directed run-time specialization in c . In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (June). pp. 163 -- 178 . 10.1145\/258993.259016 Grant, B., Mock, M., Philipose, M., Chambers, C., and Eggers, S. 1997. Annotation-directed run-time specialization in c. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (June). pp. 163--178. 10.1145\/258993.259016"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/301618.301683"},{"key":"e_1_2_1_14_1","volume-title":"Dyc: An expressive annotation-directed dynamic compiler for c. Tech. rep. UW-CSE-97-03-03","author":"Grant B.","year":"1999","unstructured":"Grant , B. , Mock , M. , Philipose , M. , Chambers , C. , and Eggers , S . 1999 b. Dyc: An expressive annotation-directed dynamic compiler for c. Tech. rep. UW-CSE-97-03-03 . University of Washington , Seattle, WA . Grant, B., Mock, M., Philipose, M., Chambers, C., and Eggers, S. 1999b. Dyc: An expressive annotation-directed dynamic compiler for c. Tech. rep. UW-CSE-97-03-03. University of Washington, Seattle, WA."},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/177492.177499"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/73141.74842"},{"unstructured":"Leone M. and Lee P. 1995. Optimizing ml with run-time code generation. Tech. rep. CMU-CS-95-205. Carnegie Mellon University Pittsburgh PA.  Leone M. and Lee P. 1995. Optimizing ml with run-time code generation. Tech. rep. CMU-CS-95-205. Carnegie Mellon University Pittsburgh PA.","key":"e_1_2_1_17_1"},{"volume-title":"Advanced Compiler Design and Implementation","author":"Muchnick S.","unstructured":"Muchnick , S. 1997. Advanced Compiler Design and Implementation . Morgan Kaufmann Publishers , San Francisco, CA . Muchnick, S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, San Francisco, CA.","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the International Conference on Computer Languages (May).","author":"Noel F.","unstructured":"Noel , F. , Hornof , L. , Consel , C. , and Lawall , J . 1998. Automatic, template-based run-time specialization: Implementation and experimental study . In Proceedings of the International Conference on Computer Languages (May). Noel, F., Hornof, L., Consel, C., and Lawall, J. 1998. Automatic, template-based run-time specialization: Implementation and experimental study. In Proceedings of the International Conference on Computer Languages (May).","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/316686.316697"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/258915.258926"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1145\/330249.330250"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/277650.277714"},{"key":"e_1_2_1_24_1","volume-title":"2003 ACM SIGPLAN Conference on Languages, Compilers and Tools for Embedded Systems (LCTES 2003","author":"Zhang T.","year":"2003","unstructured":"Zhang , T. and Pande , S . 2003. Tamper resistant whole program partitioning . In 2003 ACM SIGPLAN Conference on Languages, Compilers and Tools for Embedded Systems (LCTES 2003 , June 2003 ). 209--219. 10.1145\/780732.780762 Zhang, T. and Pande, S. 2003. Tamper resistant whole program partitioning. In 2003 ACM SIGPLAN Conference on Languages, Compilers and Tools for Embedded Systems (LCTES 2003, June 2003). 209--219. 10.1145\/780732.780762"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1034774.1034776","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1034774.1034776","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:23:58Z","timestamp":1750267438000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1034774.1034776"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,11]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2004,11]]}},"alternative-id":["10.1145\/1034774.1034776"],"URL":"https:\/\/doi.org\/10.1145\/1034774.1034776","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2004,11]]},"assertion":[{"value":"2004-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}