{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:27:38Z","timestamp":1787340458504,"version":"build-2736575974"},"reference-count":11,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1976,3]]},"abstract":"<jats:p>The problem of determining the points in a program at which variables are \u201clive\u201d (will be used again) is introduced and discussed. Two solutions, one which uses a simple iterative algorithm and one which uses an algorithm based on \u201cCocke\u2013Allen interval\u201d analysis, are presented and analyzed. These algorithms are compared on \u201cself replicating\u201c families of reducible program flow graphs. The results are inconclusive in that the interval method requires fewer bit-vector steps on some graphs and more on others. If n is the number of nodes in a program flow graph and the number of edges is linearly proportional to n, then both algorithms require $O(n^2 )$ steps in the worst case.<\/jats:p>","DOI":"10.1137\/0205014","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T05:57:56Z","timestamp":1109224676000},"page":"158-180","source":"Crossref","is-referenced-by-count":16,"title":["A Comparison of Two Algorithms for Global Data Flow Analysis"],"prefix":"10.1137","volume":"5","author":[{"given":"Ken","family":"Kennedy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/390013.808479"},{"key":"R2","unstructured":"F. E. Allen,  A basis for program optimization,  Proc. IFIP Conf. 71, North-Holland, Amsterdam,  1971 0254.68007"},{"key":"R3","volume-title":"Graph theoretic constructs for program control flow analysis","author":"Allen F. E.","year":"1972"},{"key":"R4","volume-title":"Programming Languages and their Compilers","author":"Cocke J.","year":"1969"},{"key":"R5","volume-title":"The theory of parsing, translation, and compiling. Vol. II: Compiling","author":"Aho Alfred V.","year":"1973"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1080\/00207167108803048"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. S. Hecht, J. D. Ullman,  Analysis of a simple algorithm for global data flow problems,  Proc. ACM SIGACT\/SIGPLAN Symp. on Principles of Programming Languages, Boston, Mass.,  1973, Oct. 0309.68036","DOI":"10.1145\/512927.512946"},{"key":"R8","volume-title":"A mathematical theory of global program optimization","author":"Schaefer Marvin","year":"1973"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"G. A. Kildall,  A unified approach to global program optimization,  Proc. ACM SIGACT\/SIGPLAN Symp. on Principles of Programming Languages, Boston, Mass.,  1973, October 0309.68020","DOI":"10.1145\/512927.512945"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289078"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380010203"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0205014","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:35:35Z","timestamp":1787337335000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0205014"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1976,3]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1976,3]]}},"alternative-id":["10.1137\/0205014"],"URL":"https:\/\/doi.org\/10.1137\/0205014","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1976,3]]}}}