{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T05:06:25Z","timestamp":1698037585350},"reference-count":36,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":6115,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1990,2]]},"abstract":"Abstract<\/jats:title>We extend the well\u2010known interval analysis method so that it can be used to gather global flow information for individual array elements. Data dependences between all array accesses in different basic blocks, different iterations of the same loop, and across different loops are computed and represented as labelled arcs in a program flow graph. This approach results in a uniform treatment of scalars and arrays in the compiler and builds a systematic basis from which the compiler can perform numerous global optimizations.<\/jats:p>This global dataflow analysis is performed as a separate phase in the compiler. This phase only gathers the global relationships between different accesses to a variable, yet the use of this information is left to the code generator. This organization substantially simplifies the engineering of an optimizing compiler and separates the back end of the compiler (e.g. code generator and register allocator) from the flow analysis part.<\/jats:p>The global dataflow analysis algorithm described in this paper has been implemented and used in an optimizing compiler for a processor with deep pipelines. This paper describes the algorithm and its compact implementation and evaluates it, both with respect to the accuracy of the information and to the compile\u2010time cost of obtaining and using it.<\/jats:p>","DOI":"10.1002\/spe.4380200203","type":"journal-article","created":{"date-parts":[[2006,11,18]],"date-time":"2006-11-18T05:22:43Z","timestamp":1163827363000},"page":"133-155","source":"Crossref","is-referenced-by-count":53,"title":["Structured dataflow analysis for arrays and its use in an optimizing compiler"],"prefix":"10.1002","volume":"20","author":[{"given":"Thomas","family":"Gross","sequence":"first","affiliation":[]},{"given":"Peter","family":"Steenkiste","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Compilers","author":"Aho A. V.","year":"1986"},{"issue":"7","key":"e_1_2_1_3_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/390013.808479","article-title":"\u2018Control flow analysis\u2019","volume":"5","author":"Allen F. E.","year":"1970","journal-title":"ACM SIGPLAN Notices"},{"key":"e_1_2_1_4_2","first-page":"1","volume-title":"Program Flow Analysis","author":"Kennedy K.","year":"1981"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/390013.808480"},{"key":"e_1_2_1_6_2","unstructured":"J. R.Allen \u2018Dependence analysis for subscripted variables and its application to program transformations\u2019 Ph.D. dissertation Rice University April1983."},{"key":"e_1_2_1_7_2","unstructured":"M. J.Wolfe \u2018Optimizing supercompilers for supercomputers\u2019 Ph.D. dissertation University of Illinois at Urbana\u2010Champaign October1982."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/360827.360844"},{"key":"e_1_2_1_9_2","first-page":"207","volume-title":"Conf. Record of the 8th Annual ACM Symposium on Principles of Programming Languages","author":"Kuck D. J.","year":"1981"},{"key":"e_1_2_1_10_2","unstructured":"U.Banerjee \u2018Data dependence in ordinary programs\u2019 Tech. report UIUCDCS\u2010R\u201076\u2013837 University of Illinois at Urbana\u2010Champaign Department of Computer Science November1976."},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1980.1675676"},{"key":"e_1_2_1_12_2","unstructured":"D.Kuck R.Kuhn B.LeasureandM.Wolfe \u2018The structure of an advanced vectorizer for pipelined processors\u2019 Proc. IEEE 4th International COMPSAC IEEE Chicago 1980 pp.709\u2013715."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/502874.502897"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1147\/rd.302.0163"},{"key":"e_1_2_1_15_2","first-page":"176","volume-title":"Proc. Third Int. Conf. on Supercomputing","author":"Allen Randy","year":"1988"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/502874.502878"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1080\/00207167108803048"},{"key":"e_1_2_1_18_2","series-title":"Programming Languages Series","volume-title":"Flow Analysis of Computer Programs","author":"Hecht M. S.","year":"1977"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289078"},{"key":"e_1_2_1_20_2","volume-title":"Tech. Report CS\u2010528","author":"Tarjan R. E.","year":"1975"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321939"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/360018.360025"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/12276.13329"},{"key":"e_1_2_1_24_2","first-page":"138","volume-title":"Proc. First Int. Conf. on Supercomputing","author":"Callahan D.","year":"1987"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.5009502"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/12276.13314"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/7902.7904"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675434"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/29873.29875"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.2247"},{"key":"e_1_2_1_31_2","first-page":"272","volume-title":"Proc. Compcon Spring 87","author":"Annaratone M.","year":"1987"},{"key":"e_1_2_1_32_2","doi-asserted-by":"crossref","unstructured":"M. S.Lam \u2018A systolic array optimizing compiler\u2019 Ph.D. dissertation Carnegie Mellon University May1987.","DOI":"10.1007\/978-1-4613-1705-0"},{"key":"e_1_2_1_33_2","doi-asserted-by":"crossref","unstructured":"M.Lam \u2018Software pipelining: an effective scheduling technique for VLIW machines\u2019 Proc. ACM SIGPLAN '88 Conf. on Programming Language Design and Implementation June1988 pp.318\u2013328.","DOI":"10.1145\/960116.54022"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/SUPERC.1988.44670"},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/70082.68183"},{"key":"e_1_2_1_36_2","unstructured":"H.Tamura S.Sakane F.Tomita N.Yokoya K.SakaueandN.Kaneko Joint System Development Corp. SPIDER Users' Manual Tokyo 1983."},{"key":"e_1_2_1_37_2","doi-asserted-by":"crossref","unstructured":"T.KanadeandJ.Webb \u2018End of year report for parallel vision algorithm design & implementation\u2019 Tech. Report CMU 1987.","DOI":"10.21236\/ADA199305"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380200203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380200203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T10:24:51Z","timestamp":1697970291000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380200203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,2]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1990,2]]}},"alternative-id":["10.1002\/spe.4380200203"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380200203","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,2]]}}}