Article Generating machine specific optimizing compilers Share on Authors: Roger Hoover Computer Science Department, IBM TJ Watson Research Center, PO Box 704, Yorktown Heights, NY Computer Science Department, IBM TJ Watson Research Center, PO Box 704, Yorktown Heights, NYView Profile , Kenneth Zadeck Computer Science Department, IBM TJ Watson Research Center, PO Box 704, Yorktown Heights, NY Computer Science Department, IBM TJ Watson Research Center, PO Box 704, Yorktown Heights, NYView Profile Authors Info & Claims POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languagesJanuary 1996 Pages 219–229https://doi.org/10.1145/237721.237779Published:01 January 1996 6citation31DownloadsMetricsTotal Citations6Total Downloads31Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Elimination of partial redundancies is a powerful optimization that has been implemented in at least three important production compilers and has inspired several similar optimizations. The global data flow analysis that supports this family of optimizations includes some bidirectional problems. (A bidirectional problem is one in which the global information at each basic block depends on both control flow predecessors and control flow successors.) This paper contributes two ways to simplify and expedite the analysis, especially for large programs. For each global data flow question, we examine only the places in the program where the question might have an answer different from a trivial default answer. In a large program, we may examine only a small fraction of the places conventional algorithms would examine. We reduce the relevant bidirectional problems to simpler unidirectional problems. These bidirectional problems can be solved by applying a quick correction to a unidirectional approximation.

In optimizing compilers, data structure choices directly influence the power and efficiency of practical program optimization.A poor choice of data structure can inhibit optimization or slow compilation to the point that advanced optimization features become undesirable.Recently, static single assignment form and the control dependence graph have been proposed to represent data flow and control flow propertiee of programs.Each of these previously unrelated techniques lends efficiency and power to a useful class of program optimization.Although both of these structures are attractive, the difficulty of their construction and their potential size have discouraged their use.We present new algorithms that efficiently compute these data structures for arbitrary control flow graphs.The algorithms use dominance frontiers, a new concept that may have other applications.We also give analytical and experimental evidence that all of these data structures are usually linear in the size of the original program.This paper thus presents strong evidence that these structures can be of practical use in optimization.

Constant propagation is a well-known global flow analysis problem. The goal of constant propagation is to discover values that are constant on all possible executions of a program and to propagate these constant values as far foward through the program as possible. Expressions whose operands are all constants can be evaluated at compile time and the results propagated further. Using the algorithms presented in this paper can produce smaller and faster compiled programs. The same algorithms can be used for other kinds of analyses (e.g., type of determination). We present four algorithms in this paper, all conservitive in the sense that all constants may not be found, but each constant found is constant over all possible executions of the program. These algorithms are among the simplest, fastest, and most powerful global constant propagation algorithms known. We also present a new algorithm that performs a form of interprocedural data flow analysis in which aliasing information is gathered in conjunction with constant progagation. Several variants of this algorithm are considered.

article Free Access Share on Analysis of pointers and structures Authors: David R. Chase View Profile , Mark Wegman IBM T. J. Watson Research Center, P.O. Box 704, Yorktown, Heights, NY IBM T. J. Watson Research Center, P.O. Box 704, Yorktown, Heights, NYView Profile , F. Kenneth Zadeck Computer Science Dept., P.O. Box 1910, Brown University, Providence Computer Science Dept., P.O. Box 1910, Brown University, ProvidenceView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 25Issue 6Jun. 1990 pp 296–310https://doi.org/10.1145/93548.93585Online:01 June 1990Publication History 431citation2,454DownloadsMetricsTotal Citations431Total Downloads2,454Last 12 Months69Last 6 weeks21 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article An efficient method of computing static single assignment form Share on Authors: R. Cytron IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , J. Ferrante IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , B. K. Rosen IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , M. N. Wegman IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , F. K. Zadeck Computer Science Dept., Brown University, Providence, RI Computer Science Dept., Brown University, Providence, RIView Profile Authors Info & Claims POPL '89: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesJanuary 1989 Pages 25–35https://doi.org/10.1145/75277.75280Online:03 January 1989Publication History 308citation1,950DownloadsMetricsTotal Citations308Total Downloads1,950Last 12 Months119Last 6 weeks14 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Free Access Share on Detecting equality of variables in programs Authors: B. Alpern IBM Thomas J. Watson Research Center, Yorktown Heights, NY IBM Thomas J. Watson Research Center, Yorktown Heights, NYView Profile , M. N. Wegman IBM Thomas J. Watson Research Center, Yorktown Heights, NY IBM Thomas J. Watson Research Center, Yorktown Heights, NYView Profile , F. K. Zadeck Department of Computer Science, Brown University, Providence, RI Department of Computer Science, Brown University, Providence, RIView Profile Authors Info & Claims POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesJanuary 1988 Pages 1–11https://doi.org/10.1145/73560.73561Published:13 January 1988Publication History 264citation2,559DownloadsMetricsTotal Citations264Total Downloads2,559Last 12 Months137Last 6 weeks21 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Global value numbers and redundant computations Authors: B. K. Rosen IBM Thomas J. Watson Research Center, Yorktown Heights, NY IBM Thomas J. Watson Research Center, Yorktown Heights, NYView Profile , M. N. Wegman IBM Thomas J. Watson Research Center, Yorktown Heights, NY IBM Thomas J. Watson Research Center, Yorktown Heights, NYView Profile , F. K. Zadeck Department of Computer Science, Brown University, Providence, RI Department of Computer Science, Brown University, Providence, RIView Profile Authors Info & Claims POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesJanuary 1988 Pages 12–27https://doi.org/10.1145/73560.73562Published:13 January 1988Publication History 278citation1,997DownloadsMetricsTotal Citations278Total Downloads1,997Last 12 Months240Last 6 weeks26 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

One trend among programmers is the increased use of abstractions. Through encapsulation techniques, abstractions extend the repertory of data structures and their concomitant operations that are processed directly by a compiler. For example, a compiler might not offer sets or set operations in its base language, but abstractions allow a programmer to define sets in terms of constructs already recognized by the compiler. In particular, abstractions can allow new constructs to be defined in terms of other abstractions. Although significant power is gained through the use of layered abstractions, object code quality suffers as increasingly less of a program's data structures and operations are exposed to the optimization phase of a compiler. Multiple references to abstractions are also inefficient, since the interaction between abstractions is often complex yet hidden from a compiler. Abstractions are most flexible when they are cast in general terms; a specific invocation is then tailored by the abstraction to obtain the appropriate code. A sequence of references to such abstractions can be inefficient due to functional redundancy that cannot be detected at compile-time. By integrating the references, the offending segments of code can be moved to a more advantageous position. Although procedure integration materializes abstracted constructs, the abstractions can still be ineligible for optimization using current techniques; in particular, abstractions often involve loops and conditional branches that can obscure code that would otherwise be eligible for code motion.

Constant propagation is a well-known global flow analysis problem. The goal of constant propagation is to discover values that are constant on all possible executions of a program and to propagate these constant values as far forward through the program as possible. Expressions whose operands are all constants can be evaluated at compile time and the results propagated further. Using the algorithms presented in this paper can produce smaller and faster compiled programs. The same algorithms can be used for other kinds of analyses (e.g., type determina-tion). We present four algorithms in this paper, all conservative in the sense that all constants may not be found, but each constant found is constant over all possible executions of the program. These algorithms are among the simplest, fastest, and most powerful global constant propagation algorithms known. We also present a new algorithm that performs a form of interprocedural data flow analysis in which aliasing information is gathered in conjunction with constant propagation. Several variants of this algorithm are considered.