{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,8]],"date-time":"2025-11-08T22:33:39Z","timestamp":1762641219646,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T00:00:00Z","timestamp":1188604800000},"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. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2007,9]]},"abstract":"<jats:p>This paper presents a novel method to construct a dynamic single assignment (DSA) form of array intensive, pointer free C programs. A program in DSA form does not perform any destructive update of scalars and array elements; that is, each element is written at most once. As DSA makes the dependencies between variable references explicit, it facilitates complex analyses and optimizations of programs. Existing transformations into DSA perform a complex data flow analysis with exponential analysis time, and they work only for a limited class of input programs. Our method removes irregularities from the data flow by adding copy assignments to the program, so that it can use simple data flow analyses. The presented DSA transformation scales very well with growing program sizes and overcomes a number of important limitations of existing methods. We have implemented the method and it is being used in the context of memory optimization and verification of those optimizations. Experiments show that in practice, the method scales well indeed, and that added copy operations can be removed in case they are unwanted.<\/jats:p>","DOI":"10.1145\/1278349.1278353","type":"journal-article","created":{"date-parts":[[2007,10,14]],"date-time":"2007-10-14T12:41:11Z","timestamp":1192365671000},"page":"40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["A practical dynamic single assignment transformation"],"prefix":"10.1145","volume":"12","author":[{"given":"Peter","family":"Vanbroekhoven","sequence":"first","affiliation":[{"name":"K. U. Leuven, Belgium"}]},{"given":"Gerda","family":"Janssens","sequence":"additional","affiliation":[{"name":"K. U. Leuven, Belgium"}]},{"given":"Maurice","family":"Bruynooghe","sequence":"additional","affiliation":[{"name":"K. U. Leuven, Belgium"}]},{"given":"Francky","family":"Catthoor","sequence":"additional","affiliation":[{"name":"Interuniversity Micro-Electronics Center, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2007,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/6448"},{"key":"e_1_2_1_2_1","unstructured":"Alias C. 2003. f2sare. http:\/\/www.prism.uvsq.fr\/users\/ca\/progs\/f2sare.tgz.  Alias C. 2003. f2sare. http:\/\/www.prism.uvsq.fr\/users\/ca\/progs\/f2sare.tgz."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/93542.93578"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/335043.335044"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of ICASSP'88","author":"Bu J.","year":"2025","unstructured":"Bu , J. and Deprettere , E . 1988. Converting sequential interative algorithms to recurrent equations for automatic design of systolic arrays . In Proceedings of ICASSP'88 . vol IV. IEEE Press , 2025 --2028. Bu, J. and Deprettere, E. 1988. Converting sequential interative algorithms to recurrent equations for automatic design of systolic arrays. In Proceedings of ICASSP'88. vol IV. IEEE Press, 2025--2028."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Catthoor F. Wuytack S. De Greef E. Balasa F. Nachtergaele L. and Vandecappelle A. 1998. Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design. Kluwer Academic Publishers.   Catthoor F. Wuytack S. De Greef E. Balasa F. Nachtergaele L. and Vandecappelle A. 1998. Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design. Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4757-2849-1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.1261"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of Dagstuhl Seminar on Loop Parallelization.","author":"De Greef E.","year":"1996","unstructured":"De Greef , E. , Catthoor , F. , and De Man , H. 1996 . Reducing storage size for static control programs mapped onto parallel architectures . In Proceedings of Dagstuhl Seminar on Loop Parallelization. De Greef, E., Catthoor, F., and De Man, H. 1996. Reducing storage size for static control programs mapped onto parallel architectures. In Proceedings of Dagstuhl Seminar on Loop Parallelization."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/55364.55406"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_1_12_1","unstructured":"Genin D. and Hilfinger P. 1989. Silage Reference Manual Draft 1.0. Silvar-Lisco Leuven.  Genin D. and Hilfinger P. 1989. Silage Reference Manual Draft 1.0. Silvar-Lisco Leuven."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/321406.321418"},{"key":"e_1_2_1_14_1","volume-title":"Matparser: An array dataflow analysis compiler. Tech. rep.","author":"Kienhuis B.","year":"2000","unstructured":"Kienhuis , B. 2000 . Matparser: An array dataflow analysis compiler. Tech. rep. , University of California , Berkeley. Kienhuis, B. 2000. Matparser: An array dataflow analysis compiler. Tech. rep., University of California, Berkeley."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/334012.334015"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/268946.268956"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/143369.143426"},{"key":"e_1_2_1_18_1","unstructured":"Offner C. and Knobe K. 2003. Weak dynamic single assignment form. Tech. rep. HPL-2003-169 HP Labs.  Offner C. and Knobe K. 2003. Weak dynamic single assignment form. Tech. rep. HPL-2003-169 HP Labs."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/375977.375978"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/125826.125848"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/800015.808184"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 6th International Workshop on Implementation of Functional Languages (IFL'94)","author":"Scholz S.-B.","year":"1994","unstructured":"Scholz , S.-B. 1994 . Single assignment C---functional programming using imperative style . In Proceedings of the 6th International Workshop on Implementation of Functional Languages (IFL'94) . 21.1--21.13. Scholz, S.-B. 1994. Single assignment C---functional programming using imperative style. In Proceedings of the 6th International Workshop on Implementation of Functional Languages (IFL'94). 21.1--21.13."},{"key":"e_1_2_1_23_1","first-page":"248","article-title":"An automatic verification technique for loop and data reuse transformations based on geometric modeling of programs","volume":"9","author":"Shashidhar K. C.","year":"2003","unstructured":"Shashidhar , K. C. , Bruynooghe , M. , Catthoor , F. , and Janssens , G. 2003 . An automatic verification technique for loop and data reuse transformations based on geometric modeling of programs . J. Univer. Comput. Sci. 9 , 3, 248 -- 269 . Shashidhar, K. C., Bruynooghe, M., Catthoor, F., and Janssens, G. 2003. An automatic verification technique for loop and data reuse transformations based on geometric modeling of programs. J. Univer. Comput. Sci. 9, 3, 248--269.","journal-title":"J. Univer. Comput. Sci."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31985-6_15"},{"key":"e_1_2_1_25_1","volume-title":"Lecture Notes in Computer Science","volume":"2294","author":"Tron\u00e7on R.","unstructured":"Tron\u00e7on , R. , Bruynooghe , M. , Janssens , G. , and Catthoor , F . 2002. Storage size reduction by in-place mapping of arrays. In Verification, Model Checking and Abstract Interpretation (VMCAI'02) Revised Papers . Lecture Notes in Computer Science , vol. 2294 . 167--181. Tron\u00e7on, R., Bruynooghe, M., Janssens, G., and Catthoor, F. 2002. Storage size reduction by in-place mapping of arrays. In Verification, Model Checking and Abstract Interpretation (VMCAI'02) Revised Papers. Lecture Notes in Computer Science, vol. 2294. 167--181."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575467_22"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/780732.780736"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1278349.1278353","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1278349.1278353","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:29Z","timestamp":1750258049000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1278349.1278353"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,9]]}},"alternative-id":["10.1145\/1278349.1278353"],"URL":"https:\/\/doi.org\/10.1145\/1278349.1278353","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2007,9]]},"assertion":[{"value":"2007-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}