More Web Proxy on the site http://driver.im/

article

Free access

A practical data flow framework for array reference analysis and its use in optimizations

Authors:

Evelyn Duesterwald,

Mary Lou SoffaAuthors Info & Claims

ACM SIGPLAN Notices, Volume 28, Issue 6

Pages 68 - 77

https://doi.org/10.1145/173262.155097

Published: 01 June 1993 Publication History

Abstract

Data flow analysis techniques have traditionally been restricted to the analysis of scalar variables. This retriction, however, imposes a limitation on the kinds of optimizations that can be performed in loops containing array references. We present a data flow framework for array reference analysis that provides the information needed in various optimizations targeted at sequential or fine-grained parallel architectures. The framework extends the traditional scalar framework by incorporating iteration distance values into the analysis to qualify the computed data flow solution during the fixed point iteration. Analyses phrased in this framework are capable of discovering recurrent access patterns among array references that evolve during the execution of a loop. Applications of our framework are discussed for register allocation, load/store optimizations, and controlled loop unrolling.

References

[1]

A.V. Aho, R. Sethi, and J. D. Ullman, in Compilers, principles, techniques, and tools, Addison-Wesley Publishing Company, Massachusetts, 1986.

Digital Library

[2]

T. Brandes, "The importance of direct dependences for automatic parallelism," Proc. of the '88 Int. Conf. on Supercomputing, pp. 407-424, 1988.

Digital Library

[3]

D. Callahan, S. Carr, and K. Kennedy, "Improving register allocation for subscripted variables," Proc. of the ACM SIGPLAN '90 Conf. Programming Language Design and Implementation, pp. 53-65, Jun. 1990.

Digital Library

[4]

G.J. Chaitin, "Register allocation and spilling via graph coloring," Proc. of the ACM SIGPLAN '82 Syrup. on Compiler Construction, pp. 201-207, Jun, 1982.

Digital Library

[5]

F. Chow and J. Hennessy, "Register allocation by priority-based coloring," ACM SIGPLAN Notices, vol. 19, no. 6, pp. 222-232, 1984,

Digital Library

[6]

P. Cousot and R. Cousot, "Abstract interpretation: a unified lattice model for static analysis of program,; by construction or approximation of fixpoints," Conf. Record of the 4th Annual ACM Syrup. on Principles of Programming Languages, pp. 238-252, Jan. 1977.

Digital Library

[7]

J.C. Dehnert, P.Y.-T. Hsu, and J.P. Bratt, "Overlapped loop support in the Cydra 5," Proc. of the 3rd Int. Conf. on Architectural Support for Programming Languages and Operating Systems., pp. 26-39, Apr. 1989.

Digital Library

[8]

J.j. Dongarra and A.R. Hinds, "Unrolling loops in FOR- TRAN," Software-Practice and Experience, vol. 9, no. 3, Mar. 1979.

[9]

E. Duesterwald, R. Gupta, amt M.L. Sofia, "Register pipeling: An integrated approach to register allocation for scalar and subscripted variables," Proc. of the 4th Int. Workshop on Compiler Construction, LNCS 641 Springer Verlag, pp. 192-206, Oct. 1992.

Digital Library

[10]

P. Feautrier, "Data flow analysis of array and scalar references," Int. Journal of Parallel Programming, vol. 20, no. 1, 1991.

[11]

E. Granston and A. Veidenbaum, "Detecting redundant accesses to array data," Proc. of Supercomputing '91, pp. 854-865, Nov. 1991.

Digital Library

[12]

T. Gross and P. Steenkiste, "Structured dataflow analysis for arrays and its use in an optimizing compiler," Software - Practice and Experience, vol. 20, no. 2, pp. 133-155, Feb. 1990.

Digital Library

[13]

R. Gupta and M.L. Sofia, "Region scheduling: an approach for detecting and redistributing parallelism," IEEE Trans. on Software Engineering, vol. 16, no. 4, pp. 421-431, Apr. 1990.

Digital Library

[14]

R. Hanxleden, K. Kennedy, C. Koelbel, R. Das, and J. Saltz, "Complier analysis for irregular problems in Fortran D," 5th Workshop on Languages and Compilers for Parallel Computing, pp. 65-77, Aug. 1992.

Digital Library

[15]

A.D. Kallis and D. Klappholz, "Reaching definitions analysis on code containing array references," Conf. Rec. of the 4th Workshop on Languages and Compilers for Parallel Computing, Aug. 1991.

Digital Library

[16]

j.B. Kam and J.D. Ullman, "Monotone data flow analysis frameworks," Acta Informatica, vol. 7, no. 3, pp. 305- 317, Jut. 1977.

Digital Library

[17]

D.J. Kuck, R.H. Kuhn, D. Padua, B.R, Leisure, and M. Wolfe, "Dependence graphs and compiler optimization," Proc. of the 8th ACM Syrup. on Principles of Programming Languages, pp. 207-218, Jan. 1981.

Digital Library

[18]

T.J. Marlowe and B.G. Ryder, "Properties of data flow frameworks, a unified model," Acta Informatica, vol. 28, no. 2, pp. 121-163, Dec. 1990.

Digital Library

[19]

D.E. Maydan, S.P, Amarasinghe, and M.S. Lain, "Array data-flow analysis and its use in array privatization," Proc. of the 20th ACM Syrup.on Principles of Programming Languages, pp. 2-15, Jan. 1993.

Digital Library

[20]

Q. Ning and G.R. Gao, "A novel framework of register allocation for software pipelining," Proc. of the 20th ACM Syrup. on Principles of Programming Languages, pp. 29-42, Jan. 1993.

Digital Library

[21]

W. Pugh and D. Wonnacott, "Eliminating false data dependences using the omega test," Proc. of the SIG- PLAN '92 Conf. on Programming Language Design and Implementation, pp. 140-151, Jun. 1992.

Digital Library

[22]

B.R. Rau, "Data flow and dependence analysis for instruction-level parallelism," Conf. Rec. of the 4th Workshop on Languages and Compilers for Parallel Computing, Aug. 1991.

Digital Library

[23]

H. Ribas, "Obtaining depedence vectors for nested-loop computations," Proc. of the 1990 Int. Conf. on Parallel Processing, pp. 212-219 0I), 1990.

[24]

C. Rosene, "Incremental dependence analysis," Ph.D. thesis, Rice University, March 1990.

Digital Library

[25]

M. Wolfe and U. Banerjee, "Data dependence and its application to parallel processing," Int. Journal of Parallel Programming, vol. 16, no. 2, pp. 137-178, 1987.

Digital Library

[26]

M. Wolfe, "Optimizing supercompilers for supercomputers," Pitman Publishing Company, London, MIT Press, Cambridge, Massachusets, 1989.

Digital Library

Cited By

Doerfert JSharma SHack SDubach CXue J(2018)Polyhedral expression propagationProceedings of the 27th International Conference on Compiler Construction10.1145/3178372.3179529(25-36)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3178372.3179529
Choudhary AKandemir M(2010)Compilation for Distributed Memory ArchitecturesThe Compiler Design Handbook10.1201/9781420040579.ch11Online publication date: 7-Mar-2010
https://doi.org/10.1201/9781420040579.ch11
Ferrante JGrunwald DSrinivasan H(2005)Computing communication sets for control parallel programsLanguages and Compilers for Parallel Computing10.1007/BFb0025887(316-330)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0025887
Show More Cited By

Index Terms

A practical data flow framework for array reference analysis and its use in optimizations

Recommendations

A practical data flow framework for array reference analysis and its use in optimizations
PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation

Data flow analysis techniques have traditionally been restricted to the analysis of scalar variables. This retriction, however, imposes a limitation on the kinds of optimizations that can be performed in loops containing array references. We present a ...
Array-data flow analysis and its use in array privatization
POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Data-flow analysis of scalar variables and data dependence analysis on array elements are two important program analyses used in optimizing and parallelizing compilers. Traditional data-flow analysis models accesses of array elements simply as accesses ...
Data-specific optimizations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 28, Issue 6

June 1993

313 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/173262

Editor:
Richard Wexelblat
IDA/CSED, Alexandria, VA

Issue’s Table of Contents

PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation
August 1993
313 pages
ISBN:0897915984
DOI:10.1145/155090
Editor:
Robert Cartwright
Rice Univ., Houston, TX

Copyright © 1993 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1993

Published in SIGPLAN Volume 28, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

101
Total Citations
View Citations
668
Total Downloads

Downloads (Last 12 months)106
Downloads (Last 6 weeks)22

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doerfert JSharma SHack SDubach CXue J(2018)Polyhedral expression propagationProceedings of the 27th International Conference on Compiler Construction10.1145/3178372.3179529(25-36)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3178372.3179529
Choudhary AKandemir M(2010)Compilation for Distributed Memory ArchitecturesThe Compiler Design Handbook10.1201/9781420040579.ch11Online publication date: 7-Mar-2010
https://doi.org/10.1201/9781420040579.ch11
Ferrante JGrunwald DSrinivasan H(2005)Computing communication sets for control parallel programsLanguages and Compilers for Parallel Computing10.1007/BFb0025887(316-330)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0025887
Lisper BCollard J(2005)Extent analysis of data fieldsStatic Analysis10.1007/3-540-58485-4_42(208-222)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-58485-4_42
Nieh JYang SNovik N(2003)Measuring thin-client performance using slow-motion benchmarkingACM Transactions on Computer Systems10.1145/592637.59264021:1(87-115)Online publication date: 1-Feb-2003
https://dl.acm.org/doi/10.1145/592637.592640
Arpaci-Dusseau R(2003)Run-time adaptation in riverACM Transactions on Computer Systems10.1145/592637.59263921:1(36-86)Online publication date: 1-Feb-2003
https://dl.acm.org/doi/10.1145/592637.592639
von Hanxleden RKennedy K(2000)A balanced code placement frameworkACM Transactions on Programming Languages and Systems10.1145/365151.36516122:5(816-860)Online publication date: 1-Sep-2000
https://dl.acm.org/doi/10.1145/365151.365161
Lee GGu J(1999)Program Control StructuresWiley Encyclopedia of Electrical and Electronics Engineering10.1002/047134608X.W6932Online publication date: 27-Dec-1999
https://doi.org/10.1002/047134608X.W6932
Barthou DCollard JFeautrier P(1997)Fuzzy Array Dataflow AnalysisJournal of Parallel and Distributed Computing10.1006/jpdc.1996.126140:2(210-226)Online publication date: 1-Feb-1997
https://dl.acm.org/doi/10.1006/jpdc.1996.1261
Forgács IRombach H(1996)An exact array reference analysis for data flow testingProceedings of the 18th international conference on Software engineering10.5555/227726.227844(565-574)Online publication date: 1-May-1996
https://dl.acm.org/doi/10.5555/227726.227844
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents