{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T15:12:10Z","timestamp":1791299530742,"version":"4.1.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T00:00:00Z","timestamp":1338508800000},"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. Embed. Comput. Syst."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>The static single information (SSI) form is an extension of the static single assignment (SSA) form, a well-established compiler intermediate representation that has been successfully used for numerous compiler analysis and optimizations. Several interesting results have also been shown for SSI form concerning liveness analysis and the representation of live-ranges of variables, which could make SSI form appealing for just-in-time compilation. Unfortunately, we have uncovered several mistakes in the previous literature on SSI form, which, admittedly, is already quite sparse. This article corrects the mistakes that are most germane to SSI form. We first explain why the two definitions of SSI form proposed in past literature, first by C. S. Ananian, then by J. Singer, are not equivalent. Our main result is then to prove that basic blocks, and thus program points, can be totally ordered so that live-ranges of variables correspond to intervals on a line, a result that holds for both variants of SSI form. In other words, in SSI form, the intersection graph defined by live-ranges is an interval graph, a stronger structural property than for SSA form for which the intersection graph of live-ranges is chordal. Finally, we show how this structure of live-ranges can be used to simplify liveness analysis.<\/jats:p>","DOI":"10.1145\/2180887.2180898","type":"journal-article","created":{"date-parts":[[2012,6,11]],"date-time":"2012-06-11T13:03:21Z","timestamp":1339419801000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["SSI Properties Revisited"],"prefix":"10.1145","volume":"11S","author":[{"given":"Benoit","family":"Boissinot","sequence":"first","affiliation":[{"name":"ENS-Lyon"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philip","family":"Brisk","sequence":"additional","affiliation":[{"name":"University of California, Riverside"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alain","family":"Darte","sequence":"additional","affiliation":[{"name":"CNRS"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabrice","family":"Rastello","sequence":"additional","affiliation":[{"name":"Inria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73561"},{"key":"e_1_2_1_2_1","volume-title":"Laboratory for Computer Science","author":"Ananian C. S.","unstructured":"Ananian , C. S. 1999. The static single information form. Tech. rep. MIT-LCS-TR-801 , Laboratory for Computer Science , Massachusetts Institute of Technology . Ananian, C. S. 1999. The static single information form. Tech. rep. MIT-LCS-TR-801, Laboratory for Computer Science, Massachusetts Institute of Technology."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Appel A. W. and Palsberg J. 2002. Modern Compiler Implementation in Java 2nd Ed. Cambridge University Press. Appel A. W. and Palsberg J. 2002. Modern Compiler Implementation in Java 2nd Ed. Cambridge University Press.","DOI":"10.1017\/CBO9780511811432"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2009.19"},{"key":"e_1_2_1_5_1","volume-title":"RR2005-33","author":"Bouchez F.","unstructured":"Bouchez , F. , Darte , A. , Guillon , C. , and Rastello , F . 2005. Register allocation and spill complexity under SSA. Tech. rep . RR2005-33 , LIP, ENS Lyon, France. Bouchez, F., Darte, A., Guillon, C., and Rastello, F. 2005. Register allocation and spill complexity under SSA. Tech. rep. RR2005-33, LIP, ENS Lyon, France."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1757112.1757141"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(19980710)28:8%3C859::AID-SPE188%3E3.0.CO;2-8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1269843.1269858"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.870409"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512534"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800230.806984"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-0551(81)90048-5"},{"key":"e_1_2_1_13_1","unstructured":"Cooper K. D. and Torczon L. 2004. Engineering a Compiler. Morgan Kaufmann. Cooper K. D. and Torczon L. 2004. Engineering a Compiler . Morgan Kaufmann."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/984029"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_20"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/262004.262005"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/773473.178258"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575467_21"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/330249.330250"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/570886.570887"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73562"},{"key":"e_1_2_1_23_1","volume-title":"Computer Laboratory","author":"Singer J.","unstructured":"Singer , J. 2006. Static program analysis based on virtual register renaming. Tech. rep. UCAM-CL-TR-660 , Computer Laboratory , University of Cambridge . Singer, J. 2006. Static program analysis based on virtual register renaming. Tech. rep. UCAM-CL-TR-660, Computer Laboratory, University of Cambridge."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/236114.236115"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 6th International Symposium on Static Analysis (SAS\u201999)","author":"Sreedhar V. C.","unstructured":"Sreedhar , V. C. , Ju , R. D.-C. , Gillies , D. M. , and Santhanam , V . 1999. Translating out of static single assignment form . In Proceedings of the 6th International Symposium on Static Analysis (SAS\u201999) . Springer, 194--210. Sreedhar, V. C., Ju, R. D.-C., Gillies, D. M., and Santhanam, V. 1999. Translating out of static single assignment form. In Proceedings of the 6th International Symposium on Static Analysis (SAS\u201999). Springer, 194--210."},{"key":"e_1_2_1_26_1","volume-title":"Sequentializing program dependence graphs for irreducible programs. Tech. rep. MSR-TR-93-14","author":"Steensgaard B.","unstructured":"Steensgaard , B. 1993. Sequentializing program dependence graphs for irreducible programs. Tech. rep. MSR-TR-93-14 , Microsoft Research , Redmond, WA . Steensgaard, B. 1993. Sequentializing program dependence graphs for irreducible programs. Tech. rep. MSR-TR-93-14, Microsoft Research, Redmond, WA."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/103135.103136"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90107-4"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2180887.2180898","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2180887.2180898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:22Z","timestamp":1750240462000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2180887.2180898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.1145\/2180887.2180898"],"URL":"https:\/\/doi.org\/10.1145\/2180887.2180898","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6]]},"assertion":[{"value":"2009-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}