{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:55:08Z","timestamp":1725544508514},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1977,1]]},"abstract":"This paper shows the problem of generating optimal code for expressions containing common subexpressions is computationally difficult, even for simple expressions and simple machines. Some heuristics for code generation are given and their worst-case behavior is analyzed. For one register machines, an optimal code generation algorithm is given whose time complexity is linear in the size of an expression and exponential only in the amount of sharing.<\/jats:p>","DOI":"10.1145\/321992.322001","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:13Z","timestamp":1027769173000},"page":"146-160","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":105,"title":["Code Generation for Expressions with Common Subexpressions"],"prefix":"10.1145","volume":"24","author":[{"given":"A. V.","family":"Aho","sequence":"first","affiliation":[{"name":"Bell Laboratories, Murray Hill, NJ"}]},{"given":"S. C.","family":"Johnson","sequence":"additional","affiliation":[{"name":"Bell Laboratories, Murray Hill, NJ"}]},{"given":"J. D.","family":"Ullman","sequence":"additional","affiliation":[{"name":"Dept. of EECS, Princeton University, Princeton, NJ"}]}],"member":"320","published-online":{"date-parts":[[1977,1]]},"reference":[{"key":"e_1_2_1_1_2","volume-title":"Reading, Mass","author":"AHO A V","year":"1974","unstructured":"AHO , A V , HOPCRO~ , J E , AND ULLMAN , J D The Design and Analysts of Computer Algorithms Addison Wesley , Reading, Mass , 1974 AHO, A V, HOPCRO~, J E, AND ULLMAN, J D The Design and Analysts of Computer Algorithms Addison Wesley, Reading, Mass, 1974"},{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321970"},{"key":"e_1_2_1_3_2","volume-title":"Vol H","author":"AHO A V","year":"1973","unstructured":"AHO , A V , AND ULLMAN , J D The Theory of Parsmg, Translation and Compthng , Vol H : Compthng Prentice-Hall , Englewood Chffs , N.J, 1973 AHO, A V, AND ULLMAN, J D The Theory of Parsmg, Translation and Compthng, Vol H: Compthng Prentice-Hall, Englewood Chffs, N.J, 1973"},{"key":"e_1_2_1_4_2","first-page":"1","volume":"18","author":"BEA' Y","year":"1974","unstructured":"BEA' r'r Y , j C A register assignment algorithm for generation of highly optimized object code. IBM J Res Develop. 18 , 1 ( Jan 1974 ), 20-39 BEA'r'rY, j C A register assignment algorithm for generation of highly optimized object code. IBM J Res Develop. 18, 1 (Jan 1974), 20-39","journal-title":"IBM J Res Develop."},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1147\/sj.52.0078","volume":"5","author":"BELADY","year":"1966","unstructured":"BELADY , L A A study of replacement algorithms for virtual storage computers. IBM Syst. J 5 , 2 ( 1966 ), 78-101 BELADY, L A A study of replacement algorithms for virtual storage computers. IBM Syst. J 5, 2 (1966), 78-101","journal-title":"IBM Syst. J"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/363011.363153"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/321892.321901"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321971"},{"key":"e_1_2_1_9_2","first-page":"37","volume":"5","author":"CHEN","year":"1975","unstructured":"CHEN , S On the Setht-Ullman algorithm int Z Comp. Math, A , 5 ( 1975 ), 37 - 55 CHEN, S On the Setht-Ullman algorithm int Z Comp. Math, A, 5 (1975), 37-55","journal-title":"Z Comp. Math, A"},{"key":"e_1_2_1_10_2","volume-title":"J AND SCHWARTZ J T Programming Languages and their. Compilers","author":"COCKE","year":"1970","unstructured":"COCKE , J AND SCHWARTZ J T Programming Languages and their. Compilers . Courant Institute , New York U, New York, second ed, 1970 COCKE, J AND SCHWARTZ J T Programming Languages and their. Compilers. Courant Institute, New York U, New York, second ed, 1970"},{"key":"e_1_2_1_11_2","unstructured":"DEMERS A Private commumcatlon DEMERS A Private commumcatlon"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/363626.363661"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361201"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/321312.321317"},{"key":"e_1_2_1_15_2","first-page":"3","volume":"4","author":"SET","year":"1975","unstructured":"SET m, R Complete register allocation problems SIAM J Computmg 4 , 3 ( Sept 1975 ), 226-248 SETm, R Complete register allocation problems SIAM J Computmg 4, 3 (Sept 1975), 226-248","journal-title":"SIAM J Computmg"},{"key":"e_1_2_1_16_2","unstructured":"SETHI R Private commumcatlon SETHI R Private commumcatlon"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/321607.321620"},{"key":"e_1_2_1_18_2","first-page":"549","volume-title":"F L Bauer and J. Elckel","author":"WAITE W M","year":"1974","unstructured":"WAITE , W M . Optimization In Compder Construcnon: An Advanced Course , F L Bauer and J. Elckel , Eds. Sprmger-Verlag , New York , 1974 , pp 549 - 602 WAITE, W M. Optimization In Compder Construcnon: An Advanced Course, F L Bauer and J. Elckel, Eds. Sprmger-Verlag, New York, 1974, pp 549-602"},{"key":"e_1_2_1_19_2","volume-title":"Northwestern U, Evanston, ii1","author":"WASILEW","year":"1971","unstructured":"WASILEW , S G A compiler writing system with opt~mtzation capabthttes for complex order structures Ph D Th , Northwestern U, Evanston, ii1 , 1971 WASILEW, S G A compiler writing system with opt~mtzation capabthttes for complex order structures Ph D Th, Northwestern U, Evanston, ii1, 1971"},{"key":"e_1_2_1_20_2","volume-title":"C M The Design of an Optimizing Compder American Elsevier","author":"WULF W A","year":"1975","unstructured":"WULF , W A , JOHNSSON , R.K , WEINSTOCK , C B , Hoaas, S O, AND GESCHKE , C M The Design of an Optimizing Compder American Elsevier , New York , 1975 WULF, W A, JOHNSSON, R.K, WEINSTOCK, C B, Hoaas, S O, AND GESCHKE, C M The Design of an Optimizing Compder American Elsevier, New York, 1975"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/321992.322001","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T19:40:22Z","timestamp":1672515622000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/321992.322001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977,1]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1977,1]]}},"alternative-id":["10.1145\/321992.322001"],"URL":"http:\/\/dx.doi.org\/10.1145\/321992.322001","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1977,1]]},"assertion":[{"value":"1977-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
