title: Grammatical Abstraction and Incremental Syntax Analysis in a Language-Based Editor

authors:
Robert A. Ballance
Jacob Butcher
Susan L. Graham

abstract: Processors for programming languages and other formal languages typically use a concrete syntax to describe the user's view of a program and an abstract syntax to represent language structures internally. Grammatical abstraction is defined as a relationship between two context-free grammars. It formalizes the notion of one syntax being “more abstract” than another. Two variants of abstraction are presented. Weak grammatical abstraction supports (i) the construction during LR parsing of an internal representation that is closely related to the abstract syntax and (ii) incremental LR parsing using that internal representation as its base. Strong grammatical abstraction tightens the correspondence so that top-down construction of incrementally-parsable internal representations is possible. These results arise from an investigation into language-based editing systems, but apply to any program that transforms a linguistic object from a representation in its concrete syntax to a representation in its abstract syntax or vice versa.


venue: pldi

title: A Portable Global Optimizer and Linker

authors:
Manuel E. Benitez
Jack W. Davidson

abstract: To reduce complexity and simplify their implementation, most compilers are organized as a set of passes or phases. Each phase performs a particular piece of the compilation process. In an optimizing compiler, the assignment of function and order of application of the phases is a critical part of the design. A particularly difficult problem is the arrangement of the code generation and optimization phases so as to avoid phase ordering problems caused by the interaction of the phases. In this paper, we discuss the implementation of a compiler/linker that has been designed to avoid these problems. The key aspect of this design is that the synthesis phases of the compiler and the system linker share the same intermediate program representation. This results in two benefits. It permits the synthesis phases of the compiler to be performed in any order and repeatedly, thus eliminating potential phase ordering problems. Second, it permits code selection to be invoked at any point during the synthesis phases as well as at link time. The ability to perform code selection at link time presents many opportunities for additional optimizations. Measurements about the effectiveness of using this approach in a C compiler on two different machines are presented.


title: The Program Summary Graph and Flow-Sensitive InterproceduralData Flow Analysis

abstract: article Free Access Share on The program summary graph and flow-sensitive interprocedual data flow analysis Author: D. Callahan Rice Univ., Houston, TX Rice Univ., Houston, TXView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 23Issue 7July 1988 pp 47–56https://doi.org/10.1145/960116.53995Published:01 June 1988Publication History 108citation1,084DownloadsMetricsTotal Citations108Total Downloads1,084Last 12 Months81Last 6 weeks22 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


title: Safety Considerations for Storage Allocation Optimizations

abstract: Article Free Access Share on Safety consideration for storage allocation optimizations Author: D. R. Chase Olvetti Research Center, Menlo Park, CA Olvetti Research Center, Menlo Park, CAView Profile Authors Info & Claims PLDI '88: Proceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementationJune 1988 Pages 1–10https://doi.org/10.1145/53990.53991Published:01 June 1988Publication History 27citation666DownloadsMetricsTotal Citations27Total Downloads666Last 12 Months11Last 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 SiteeReaderPDF


title: Minimizing Register Usage Penalty at Procedure Calls

abstract: Inter-procedural register allocation can minimize the register usage penalty at procedure calls by reducing the saving and restoring of registers at procedure boundaries. A one-pass inter-procedural register allocation scheme based on processing the procedures in a depth-first traversal of the call graph is presented. This scheme can be overlaid on top of intra-procedural register allocation via a simple extension to the priority-based coloring algorithm. Using two different usage conventions for the registers, the scheme can distribute register saves/restores throughout the call graph even in the presence of recursion, indirect calls or separate compilation. A natural and efficient way to pass parameters emerges from this scheme. A separate technique uses data flow analysis to optimize the placement of the save/restore code for registers within individual procedures. The techniques described have been implemented in a production compiler suite. Measurements of the effects of these techniques on a set of practical programs are presented and the results analysed.


title: Interprocedural Side-Effect Analysis in Linear Time

authors:
Keith D. Cooper
Ken Kennedy

abstract: We present a new method for solving Banning's alias-free flow-insensitive side-effect analysis problem. The algorithm employs a new data structure, called the binding multi-graph, along with depth-first search to achieve a running time that is linear in the size of the call multi-graph of the program. This method can be extended to produce fast algorithms for data-flow problems with more complex lattice structures.


title: DOC: A Practical Approach to Source-Level Debugging of Globally Optimized Code

authors:
Deborah S. Coutant
Sue Meloy
Michelle Ruscetta

abstract: As optimizing compilers become more sophisticated, the problem of debugging the source code of an application becomes more difficult. In order to investigate this problem, we implemented DOC, a prototype solution for Debugging Optimized Code. DOC is a modification of the existing C compiler and source-level symbolic debugger for the HP9000 Series 800. This paper describes our experiences in this effort. We show in an actual implementation that source-level debugging of globally optimized code is viable.


title: Unfold/Fold Transformations and Loop Optimization of Logic Programs

abstract: Programs typically spend much of their execution time in loops. This makes the generation of efficient code for loops essential for good performance. Loop optimization of logic programming languages is complicated by the fact that such languages lack the iterative constructs of traditional languages, and instead use recursion to express loops. In this paper, we examine the application of unfold/fold transformations to three kinds of loop optimization for logic programming languages: recursion removal, loop fusion and code motion out of loops. We describe simple unfold/fold transformation sequences for these optimizations that can be automated relatively easily. In the process, we show that the properties of unification and logical variables can sometimes be used to generalize, from traditional languages, the conditions under which these optimizations may be carried out. Our experience suggests that such source-level transformations may be used as an effective tool for the optimization of logic programs.


title: Automatic Generation of Fast Optimizing Code Generators

authors:
Christopher W. Fraser
Alan L. Wendt

abstract: article Free Access Share on Automatic generation of fast optimizing code generators Authors: C. W. Fraser AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile , A. L. Wendt Univ. of Arizona, Tucson, AZ Univ. of Arizona, Tucson, AZView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 23Issue 7July 1988 pp 79–84https://doi.org/10.1145/960116.53998Online:01 June 1988Publication History 19citation463DownloadsMetricsTotal Citations19Total Downloads463Last 12 Months16Last 6 weeks4 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF


title: Interprocedural Slicing Using Dependence Graphs

authors:
Susan Horwitz
Thomas W. Reps
David W. Binkley


title: An Efficient Approach to Data Flow Analysis in a Multi Pass Global Optimizer

authors:
Suneel Jain
Carol L. Thompson


title: Anatomy of a Hardware Compiler

authors:
Kurt Keutzer
Wayne H. Wolf

abstract: Programming-language compilers generate code targeted to machines with fixed architectures, either parallel or serial. Compiler techniques can also be used to generate the hardware on which these programming languages are executed. In this paper we demonstrate that many compilation techniques developed for programming languages are applicable to compilation of register-transfer hardware designs. Our approach uses a typical syntax-directed translation → global optimization → local optimization → code generation → peephole optimization method. In this paper we will describe ways in which we have both followed and diverged from traditional compiler approaches to these problems and compare our approach to other compiler oriented approaches to hardware compilation.


title: Software Pipelining: An Effective Scheduling Technique for VLIW Machines

abstract: This paper shows that software pipelining is an effective and viable scheduling technique for VLIW processors. In software pipelining, iterations of a loop in the source program are continuously initiated at constant intervals, before the preceding iterations complete. The advantage of software pipelining is that optimal performance can be achieved with compact object code.


title: Detecting Conflicts Between Structure Accesses

authors:
James R. Larus
Paul N. Hilfinger

abstract: Two references to a record structure conflict if they access the same field and at least one modifies the location. Because structures can be connected by pointers, deciding if two statements conflict requires knowledge of the possible aliases for the locations that they access.


title: Promises: Linguistic Support for Efficient Asynchronous Procedure Calls in Distributed Systems

authors:
Barbara Liskov
Liuba Shrira

abstract: This paper deals with the integration of an efficient asynchronous remote procedure call mechanism into a programming language. It describes a new data type called a promise that was designed to support asynchronous calls. Promises allow a caller to run in parallel with a call and to pick up the results of the call, including any exceptions it raises, in a convenient and type-safe manner. The paper also discusses efficient composition of sequences of asynchronous calls to different locations in a network.


title: A Mechanism for Efficient Debugging of Parallel Programs

authors:
Barton P. Miller
Jong-Deok Choi

abstract: This paper addresses the design and implementation of an integrated debugging system for parallel programs running on shared memory multi-processors (SMMP). We describe the use of flowback analysis to provide information on causal relationships between events in a program's execution without re-executing the program for debugging. We introduce a mechanism called incremental tracing that, by using semantic analyses of the debugged program, makes the flowback analysis practical with only a small amount of trace generated during execution. We extend flowback analysis to apply to parallel programs and describe a method to detect race conditions in the interactions of the co-operating processes.


title: Multiprocessor Smalltalk: A Case Study of a Multiprocessor-Based Programming Environment

authors:
Joseph Pallas
David M. Ungar

abstract: We have adapted an interactive programming system (Smalltalk) to a multiprocessor (the Firefly). The task was not as difficult as might be expected, thanks to the application of three basic strategies: serialization, replication, and reorganization. Serialization of access to resources disallows concurrent access. Replication provides multiple instances of resources when they cannot or should not be serialized. Reorganization allows us to restructure part of the system when the other two strategies cannot be applied.


title: Higher-Order Abstract Syntax

authors:
Frank Pfenning
Conal Elliott

abstract: We describe motivation, design, use, and implementation of higher-order abstract syntax as a central representation for programs, formulas, rules, and other syntactic objects in program manipulation and other formal systems where matching and substitution or unification are central operations. Higher-order abstract syntax incorporates name binding information in a uniform and language generic way. Thus it acts as a powerful link integrating diverse tools in such formal environments. We have implemented higher-order abstract syntax, a supporting matching and unification algorithm, and some clients in Common Lisp in the framework of the Ergo project at Carnegie Mellon University.


title: An Automatically Generated, Realistic Compiler for an Imperative Programming Language

authors:
Uwe F. Pleban
Peter Lee

abstract: We describe the automatic generation of a complete, realistic compiler from formal specifications of the syntax and semantics of Sol/C, a nontrivial imperative language “sort of like C.” The compiler exhibits a three pass structure, is efficient, and produces object programs whose performance characteristics compare favorably with those produced by commercially available compilers. To our knowledge, this is the first time that this has been accomplished.


title: Synchronous Operations as First-Class Values

abstract: Synchronous message passing via channels is an interprocess communication (IPC) mechanism found in several concurrent languages, such as CSP, occam, and Amber. Such languages provide a powerful selective I/O operation, which plays a vital role in managing communication with multiple processes. Because the channel IPC mechanism is “operation-oriented,” only procedural abstraction techniques can be used in structuring the communication/synchronization aspects of a system. This has the unfortunate effect of restricting the use of selective I/O, which in turn limits the communication structure. We propose a new, “value-oriented” approach to channel-based synchronization. We make synchronous operations first-class values, called events, in much the same way that functions are first-class values in functional programming languages. Our approach allows the use of data abstraction techniques for structuring IPC. We have incorporated events into PML, a concurrent functional programming language, and have implemented run-time support for them as part of the Pegasus system.


title: Refined Types: Highly Differentiated Type Systems and Their Use in the Design of Intermediate Langages

abstract: Article Free Access Share on Refined types: highly differentiated type systems and their use in the design of intermediate languages Author: J. R. Rose Thinking Machines Corporation, Cambridge, MA Thinking Machines Corporation, Cambridge, MAView Profile Authors Info & Claims PLDI '88: Proceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementationJune 1988Pages 278–287https://doi.org/10.1145/53990.54018Published:01 June 1988Publication History 0citation312DownloadsMetricsTotal Citations0Total Downloads312Last 12 Months23Last 6 weeks2 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


title: An Optimizer for Ada - Design, Experiences and Results

authors:
Birgit Schwarz
Walter Kirchgässner
Rudolf Landwehr

abstract: In this paper we describe the design of a global machine independent low level optimizer for the Karlsruhe Ada Compiler. We give a short overview on the optimizations and data structures used in the optimizer as well as some experiences with the optimizer. Detailed measurements are provided for a collection of benchmarks. The average improvement of code speed is 40%.


title: Semantic Analysis in a Concurrent Compiler

authors:
V. Seshadri
David B. Wortman
Michael D. Junkin
S. Weber
C. P. Yu
I. Small

abstract: Traditional compilers are usually sequential programs that serially process source programs through lexical analysis, syntax analysis, semantic analysis and code generation. The availability of multiprocessor computers has made it feasible to consider alternatives to this serial compilation process. The authors are currently engaged in a project to devise ways of structuring compilers so that they can take advantage of modern multiprocessor hardware. This paper is about the most difficult aspect of concurrent compilation: concurrent semantic analysis.


title: Control-Flow Analysis in Scheme

abstract: Traditional flow analysis techniques, such as the ones typically employed by optimizing Fortran compilers, do not work for Scheme-like languages. This paper presents a flow analysis technique — control flow analysis — which is applicable to Scheme-like languages. As a demonstration application, the information gathered by control flow analysis is used to perform a traditional flow analysis problem, induction variable elimination. Extensions and limitations are discussed.


title: Debugging Concurrent Processes: A Case Study

abstract: We present a case study that illustrates a method of debugging concurrent processes in a parallel programming environment. It uses a new approach called speculative replay to reconstruct the behavior of a program from the histories of its individual processes. Known time dependencies between events in different processes are used to divide the histories into dependence blocks. A graphical representation called a concurrency map displays possibilities for concurrency among processes. The replay technique preserves the known dependencies and compares the process histories generated during replay with those that were logged during the original program execution. If a process generates a replay history that does not match its original history, replay backs up. An alternative ordering of events is created and tested to see if it produces process histories that match the original histories. Successively more controlled replay sequences are generated, by introducing additional dependencies. We describe ongoing work on tools that will control replay without reconstructing the entire space of possible event orderings.


title: Register Windows versus Register Allocation

abstract: A large register set can be exploited by keeping variables and constants in registers instead of in memory. Hardware register windows and compile-time or link-time global register allocation are ways to do this. A measure of the effectiveness of any of these register management schemes is how thoroughly they remove loads and stores. This measure must also count extra loads and stores executed because of window overflow or conflicts between procedures.


title: Incremental Evaluation for a General Class of Circular Attribute Grammars

authors:
Janet A. Walz
Gregory F. Johnson

abstract: article Free Access Share on Incremental evaluation for a general class of circular attribute grammars Authors: J. A. Walz Cornell Univ., Ithaca, NY Cornell Univ., Ithaca, NYView Profile , G. F. Johnson Univ. of Maryland, College Park, MD Univ. of Maryland, College Park, MDView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 23Issue 7July 1988 pp 209–221https://doi.org/10.1145/960116.54011Online:01 June 1988Publication History 6citation247DownloadsMetricsTotal Citations6Total Downloads247Last 12 Months4Last 6 weeks1 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


title: A Piggy-back Compiler For Prolog

authors:
J. L. Weiner
S. Ramakrishnan

abstract: Article A piggy-back compiler for Prolog Share on Authors: J. L. Weiner Univ. of New Hampshire Univ. of New HampshireView Profile , S. Ramakrishman Univ. of New Hampshire Univ. of New HampshireView Profile Authors Info & Claims PLDI '88: Proceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementationJune 1988 Pages 288–296https://doi.org/10.1145/53990.54019Published:01 June 1988 8citation271DownloadsMetricsTotal Citations8Total Downloads271Last 12 Months5Last 6 weeks1 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


title: INC: A Language for Incremental Computations

authors:
Daniel M. Yellin
Robert E. Strom

abstract: article INC: a language for incremental computations Share on Authors: D. Yellin IBM T. J. Watson Research Center, Yorktown Heights, NY IBM T. J. Watson Research Center, Yorktown Heights, NYView Profile , R. Strom IBM T. J. Watson Research Center, Yorktown Heights, NY IBM T. J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 23Issue 7July 1988 pp 115–124https://doi.org/10.1145/960116.54002Online:01 June 1988Publication History 16citation327DownloadsMetricsTotal Citations16Total Downloads327Last 12 Months4Last 6 weeks1 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


title: Experiences Creating a Portable Cedar

authors:
Russell R. Atkinson
Alan J. Demers
Carl Hauser
Christian Jacobi
Peter Kessler
Mark D. Weiser

abstract: Cedar is the name for both a language and an environment in use in the Computer Science Laboratory at Xerox PARC since 1980. The Cedar language is a superset of Mesa, the major additions being garbage collection and runtime types. Neither the language nor the environment was originally intended to be portable, and for many years ran only on D-machines at PARC and a few other locations in Xerox. We recently re-implemented the language to make it portable across many different architectures. Our strategy was, first, to use machine-dependent C code as an intermediate language, second, to create a language-independent layer known as the Portable Common Runtime, and third, to write a relatively large amount of Cedar-specific runtime code in a subset of Cedar itself. By treating C as an intermediate code we are able to achieve reasonably fast compilation, very good eventual machine code, and all with relatively small programmer effort. Because Cedar is a much richer language than C, there were numerous issues to resolve in performing an efficient translation and in providing reasonable debugging. These strategies will be of use to many other porters of high-level languages who may wish to use C as an assembler language without giving up either ease of debugging or high performance. We present a brief description of the Cedar language, our portability strategy for the compiler and runtime, our manner of making connections to other languages and the Unix* operating system, and some measures of the performance of our “Portable Cedar”.


title: A Technique for Summarizing Data Access and Its Use in Parallelism Enhancing Transformations

authors:
Vasanth Balasundaram
Ken Kennedy

abstract: article A technique for summarizing data access and its use in parallelism enhancing transformations Share on Authors: V. Balasundaram Dept. of Computer Science, Rice University Dept. of Computer Science, Rice UniversityView Profile , K. Kennedy Dept. of Computer Science, Rice University Dept. of Computer Science, Rice UniversityView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 24Issue 7July 1989 pp 41–53https://doi.org/10.1145/74818.74822Published:21 June 1989 104citation512DownloadsMetricsTotal Citations104Total Downloads512Last 12 Months15Last 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


title: Spill Code Minimization Techniques for Optimizing Compilers

authors:
David Bernstein
Dina Q. Goldin
Martin Charles Golumbic
Hugo Krawczyk
Yishay Mansour
Itai Nahshon
Ron Y. Pinter

abstract: Global register allocation and spilling is commonly performed by solving a graph coloring problem. In this paper we present a new coherent set of heuristic methods for reducing the amount of spill code generated. This results in more efficient (and shorter) compiled code. Our approach has been compared to both standard and priority-based coloring algorithms, universally outperforming them.


title: Type Inference in the Presence of Type Abstraction

abstract: A number of recent programming language designs incorporate a type checking system based on the Girard-Reynolds polymorphic λ-calculus. This allows the construction of general purpose, reusable software without sacrificing compile-time type checking. A major factor constraining the implementation of these languages is the difficulty of automatically inferring the lengthy type information that is otherwise required if full use is made of these languages. There is no known algorithm to solve any natural and fully general formulation of this “type inference” problem. One very reasonable formulation of the problem is known to be undecidable.


title: Coloring Heuristics for Register Allocation

authors:
Preston Briggs
Keith D. Cooper
Ken Kennedy
Linda Torczon

abstract: We describe an improvement to a heuristic introduced by Chaitin for use in graph coloring register allocation. Our modified heuristic produces better colorings, with less spill code. It has similar compile-time and implementation requirements. We present experimental data to compare the two methods.


title: The Semantics of Program Dependence

authors:
Robert Cartwright
Matthias Felleisen

abstract: Optimizing and parallelizing compilers for procedural languages rely on various forms of program dependence graphs (pdgs) to express the essential control and data dependencies among atomic program operations. In this paper, we provide a semantic justification for this practice by deriving two different forms of program dependence graph — the output pdg and the def-order pdg—and their semantic definitions from non-strict generalizations of the denotational semantics of the programming language. In the process, we demonstrate that both the output pdg and the def-order pdg (with minor technical modifications) are conventional data-flow programs. In addition, we show that the semantics of the def-order pdg dominates the semantics of the output pdg and that both of these semantics dominate—rather than preserve—the semantics of sequential execution.


title: Customization: Optimizing Compiler Technology for SELF, A Dynamically-Typed Object-Oriented Programming Language

authors:
Craig Chambers
David M. Ungar

abstract: Dynamically-typed object-oriented languages please programmers, but their lack of static type information penalizes performance. Our new implementation tech-niques extract static type information from declaration-free programs. Our system compiles several copies of a given procedure, each customized for one receiver type, so that the type of the receiver is bound at compile time. The compiler predicts types that are statically unknown but likely, and inserts run-time type tests to verify its predictions. It splits calls, compiling a copy on each control path, optimized to the specific types on that path. Coupling these new techniques with compile-time message lookup, aggressive procedure inlining, and traditional optimizations has doubled the performance of dynamically-typed object-oriented languages. 1.


title: Unified Management of Registers and Cache Using Liveness and Cache Bypass

authors:
Chi-Hung Chi
Henry G. Dietz

abstract: In current computer memory system hierarchy, registers and cache are both used to bridge the reference delay gap between the fast processor(s) and the slow main memory. While registers are managed by the compiler using program flow analysis, cache is mainly controlled by hardware without any program understanding. Due to the lack of coordination in managing these two memory structures, significant loss of system performance results because:


title: An LR Substring Parser for Noncorrecting Syntax Error Recovery

abstract: For a context-free grammar G, a construction is given to produce an LR parser that recognizes any substring of the language generated by G. The construction yields a conflict-free (deterministic) parser for the bounded context class of grammars (Floyd, 1964). The same construction yields either a left-to-right or right-to-left substring parser, as required to implement Non-correcting Syntax Error Recovery as proposed by Richter (1985). Experience in constructing a substring parser for Pascal is described.


title: Automatic Generation of DAG Parallelism

authors:
Ron Cytron
Michael Hind
Wilson C. Hsieh

abstract: Article Free Access Share on Automatic generation of DAG parallelism 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 , M. Hind Courant Institute, New York University, 251 Mercer St., New York, NY Courant Institute, New York University, 251 Mercer St., New York, NYView Profile , W. Hsieh Laboratory for Computer Science, Massachusetts Institute, Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute, Technology, Cambridge, MAView Profile Authors Info & Claims PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementationJune 1989 Pages 54–68https://doi.org/10.1145/73141.74823Published:21 June 1989Publication History 37citation653DownloadsMetricsTotal Citations37Total Downloads653Last 12 Months44Last 6 weeks4 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


title: BEG - A Generator for Efficient Back Ends

authors:
Helmut Emmelmann
Friedrich-Wilhelm Schröer
Rudolf Landwehr

abstract: This paper describes a system that generates compiler back ends from a strictly declarative specification of the code generation process. The generated back ends use tree pattern matching for code selection. Two methods for register allocation supporting a wide range of target architectures are provided. A general bottom-up pattern matching method avoids problems that occurred with previous systems using LR-parsing. The performance of compilers using generated back ends is comparable to very fast production compilers. Some figures are given about the results of using the system to generate the back end of a Modula-2 compiler.


title: A VHDL Compiler Based on Attribute Grammar Methodology

authors:
Rodney Farrow
Alec G. Stanculescu

abstract: This paper presents aspects of a compiler for a new hardware description language (VHDL) written using attribute grammar techniques. VHDL is introduced, along with the new compiler challenges brought by a language that extends an Ada subset for the purpose of describing hardware. Attribute grammar programming solutions are presented for some of the language challenges.


title: A Language for Writing Code Generators

abstract: Article Free Access Share on A language for writing code generators Author: C. W. Fraser AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile Authors Info & Claims PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementationJune 1989 Pages 238–245https://doi.org/10.1145/73141.74839Published:21 June 1989Publication History 26citation545DownloadsMetricsTotal Citations26Total Downloads545Last 12 Months34Last 6 weeks3 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


title: Generational Reference Counting: A Reduced-Communication Distributed Storage Reclamation Scheme

abstract: This paper describes generational reference counting, a new distributed storage reclamation scheme for loosely-coupled multiprocessors. It has a significantly lower communication overhead than distributed versions of conventional reference counting. Although generational reference counting has greater computational and space requirements than ordinary reference counting, it may provide a significant saving in overall execution time on machines in which message passing is expensive.


title: Parallel Compilation for a Parallel Machine

authors:
Thomas R. Gross
Angelika Zobel
Markus Zolg

abstract: An application for a parallel computer with multiple, independent processors often includes different programs (functions) for the individual processors; compilation of such functions can proceed independently. We implemented a compiler that exploits this parallelism by partitioning the input program for parallel translation. The host system for the parallel compiler is an Ethernet-based network of workstations, and different functions of the application program are compiled in parallel on different workstations. For typical programs in our environment, we observe a speedup ranging from 3 to 6 using not more than 9 processors. The paper includes detailed measurements for this parallel compiler; we report the system overhead, implementation overhead, as well as the speedup obtained when compared with sequential compilation.


title: Register Allocation via Clique Separators

authors:
Rajiv Gupta
Mary Lou Soffa
Tim Steele

abstract: Although graph coloring is widely recognized as an effective technique for global register allocation, the overhead can be quite high, not only in execution time but also in memory, as the size of the interference graph needed in coloring can become quite large. In this paper, we present an algorithm based upon a result by R. Tarjan regarding the colorability of graphs which are decomposable using clique separators, that improves on the overhead of coloring. The algorithm first partitions program code into code segments using the notion of clique separators. The interference graphs for the code partitions are next constructed one at a time and colored independently. The colorings for the partitions are combined to obtain a register allocation for the program code. The technique presented is both efficient in space and time because the graph for only a single code segment needs to be constructed and colored at any given point in time. The partitioning of a graph using clique separators increases the likelihood of obtaining a coloring without spilling and hence an efficient allocation of registers for the program. For straight line code an optimal allocation for the entire program code can be obtained from optimal allocations for individual code segments. In the presence of branches, optimal allocation along one execution path and a near optimal allocation along alternative paths can be potentially obtained. Since the algorithm is highly efficient, it eliminates the need for a local register allocation phase.


title: Incremental Generation of Parsers

authors:
Jan Heering
Paul Klint
J. Rekers

abstract: An LR-based parser generator for arbitrary context-free grammars is described, which generates parsers by need and processes grammar modifications by updating already existing parsers. We motivate the need for these techniques in the context of interactive language definition environments, present all required algorithms, and give measurements comparing their performance with that of conventional techniques.


title: Experience with CST: Programming and Implementation

authors:
Waldemar Horwat
Andrew A. Chien
William J. Dally

abstract: CST is a programming language based on Smalltalk-802 that supports concurrency using locks, asynchronous messages, and distributed objects. In this paper, we describe CST: the language and its implementation. Example programs and initial programming experience with CST are described. Our implementation of CST generates native code for the J-machine, a fine-grained concurrent computer. Some compiler optimizations developed in conjunction with that implementation are also described.


title: Dependence Analysis for Pointer Variables

authors:
Susan Horwitz
Phil Pfeiffer
Thomas W. Reps

abstract: Our concern is how to determine data dependencies between program constructs in programming languages with pointer variables. We are particularly interested in computing data dependencies for languages that manipulate heap-allocated storage, such as Lisp and Pascal. We have defined a family of algorithms that compute safe approximations to the flow, output, and anti-dependencies of a program written in such a language. Our algorithms account for destructive updates to fields of a structure and thus are not limited to the cases where all structures are trees or acyclic graphs; they are applicable to programs that build cyclic structures.


title: Inline Function Expansion for Compiling C Programs

authors:
Wen-mei W. Hwu
Pohua P. Chang

abstract: Inline function expansion replaces a function call with the function body. With automatic inline function expansion, programs can be constructed with many small functions to handle complexity and then rely on the compilation to eliminate most of the function calls. Therefore, inline expansion serves a tool for satisfying two conflicting goals: minizing the complexity of the program development and minimizing the function call overhead of program execution. A simple inline expansion procedure is presented which uses profile information to address three critical issues: code expansion, stack expansion, and unavailable function bodies. Experiments show that a large percentage of function calls/returns (about 59%) can be eliminated with a modest code expansion cost (about 17%) for twelve UNIX* programs.


title: Reasoning about Continuations with Control Effects

authors:
Pierre Jouvelot
David K. Gifford

abstract: We present a new static analysis method for first-class continuations that uses an effect system to classify the control domain behavior of expressions in a typed polymorphic language. We introduce two new control effects, goto and comefrom, that describe the control flow properties of expressions. An expression that does not have a goto effect is said to be continuation following because it will always call its passed return continuation. An expression that does not have a comefrom effect is said to be continuation discarding because it will never preserve its return continuation for later use. Unobservable control effects can be masked by the effect system. Control effect soundness theorems guarantee that the effects computed statically by the effect system are a conservative approximation of the dynamic behavior of an expression.


title: A Fresh Look at Combinator Graph Reduction

authors:
Philip J. Koopman Jr.
Peter Lee

abstract: We present a new abstract machine for graph reduction called TIGRE. Benchmark results show that TIGRE's execution speed compares quite favorably with previous combinator-graph reduction techniques on similar hardware. Furthermore, the mapping of TIGRE onto conventional hardware is simple and efficient. Mainframe implementations of TIGRE provide performance levels exceeding those previously available on custom graph reduction hardware.


title: Mul-T: A High-Performance Parallel Lisp

authors:
David A. Kranz
Robert H. Halstead Jr.
Eric Mohr

abstract: Mul-T is a parallel Lisp system, based on Multilisp's future construct, that has been developed to run on an Encore Multimax multiprocessor. Mul-T is an extended version of the Yale T system and uses the T system's ORBIT compiler to achieve “production quality” performance on stock hardware — about 100 times faster than Multilisp. Mul-T shows that futures can be implemented cheaply enough to be useful in a production-quality system. Mul-T is fully operational, including a user interface that supports managing groups of parallel tasks.


title: Type Reconstruction with First-Class Polymorphic Values

authors:
James W. O'Toole Jr.
David K. Gifford

abstract: We present the first type reconstruction system which combines the implicit typing of ML with the full power of the explicitly typed second-order polymorphic lambda calculus. The system will accept ML-style programs, explicitly typed programs, and programs that use explicit types for all first-class polymorphic values. We accomplish this flexibility by providing both generic and explicitly-quantified polymorphic types, as well as operators which convert between these two forms of polymorphism. This type reconstruction system is an integral part of the FX-89 programming language. We present a type reconstruction algorithm for the system. The type reconstruction algorithm is proven sound and complete with respect to the formal typing rules.


title: Process Decomposition Through Locality of Reference

authors:
Anne Rogers
Keshav Pingali

abstract: In the context of sequential computers, it is common practice to exploit temporal locality of reference through devices such as caches and virtual memory. In the context of multiprocessors, we believe that it is equally important to exploit spatial locality of reference. We are developing a system which, given a sequential program and its domain decomposition, performs process decomposition so as to enhance spatial locality of reference. We describe an application of this method - generating code from shared-memory programs for the (distributed memory) Intel iPSC/2.


title: Scannerless NSLR(1) Parsing of Programming Languages

authors:
Daniel J. Salomon
Gordon V. Cormack

abstract: The disadvantages of traditional two-phase parsing (a scanner phase preprocessing input for a parser phase) are discussed. We present metalanguage enhancements for context-free grammars that allow the syntax of programming languages to be completely described in a single grammar. The enhancements consist of two new grammar rules, the exclusion rule, and the adjacency-restriction rule. We also present parser construction techniques for building parsers from these enhanced grammars, that eliminate the need for a scanner phase.


title: Determining Average Program Execution Times and their Variance

abstract: This paper presents a general framework for determining average program execution times and their variance, based on the program's interval structure and control dependence graph. Average execution times and variance values are computed using frequency information from an optimized counter-based execution profile of the program.


title: On-The-Fly Detection of Access Anomalies

abstract: Access anomalies are a common class of bugs in shared-memory parallel programs. An access anomaly occurs when two concurrent execution threads both write (or one thread reads and the other writes) the same shared memory location without coordination. Approaches to the detection of access anomalies include static analysis, post-mortem trace analysis, and on-the-fly monitoring.A general on-the-fly algorithm for access anomaly detection is presented, which can be applied to programs with both nested fork-join and synchronization operations. The advantage of on-the-fly detection over post-mortem analysis is that the amount of storage used can be greatly reduced by data compression techniques and by discarding information as soon as it becomes obsolete. In the algorithm presented, the amount of storage required at any time depends only on the number V of shared variables being monitored and the number N of threads, not on the number of synchronizations. Data compression is achieved by the use of two techniques called merging and subtraction. Upper bounds on storage are shown to be V × N2 for merging and V × N for subtraction.


title: A Framework for Construction and Evaluation of High-Level Specifications for Program Analysis Techniques

abstract: Abstract interpretation introduced the notion of formal specification of program analyses. Denotational frameworks are convenient for reasoning about such specifications. However, implementation considerations make denotational specifications complex and hard to develop. We present a framework that facilitates the construction and understanding of denotational specifications for program analysis techniques. The framework is exemplified by specifications for program analysis techniques from the literature and from our own research. This approach allows program analysis techniques to be incorporated into automatically generated program synthesizers by including their specifications with the language definition.


title: Higher-Order Attribute Grammars

authors:
Harald Vogt
S. Doaitse Swierstra
Matthijs F. Kuiper

abstract: A new kind of attribute grammars, called higher order attribute grammars, is defined. In higher order attribute grammars the structure tree can be expanded as a result of attribute computation. A structure tree may be stored in an attribute. The term higher order is used because of the analogy with higher order functions, where a function can be the result or parameter of another function. A relatively simple method, using OAGs, is described to derive an evaluation order on the defining attribute occurrences which comprises all possible direct and indirect attribute dependencies. As in OAGs, visit-sequences are computed from which an efficient algorithm for attribute evaluation can be derived.


title: Demonic Memories for Process Histories

authors:
Paul R. Wilson
Thomas G. Moher

abstract: Demonic memory is a form of reconstructive memory for process histories. As a process executes, its states are regularly checkpointed, generating a history of the process at low time resolution. Following the initial generation, any prior state of the process can be reconstructed by starting from a checkpointed state and re-executing the process up through the desired state, thereby exploiting the redundancy between the states of a process and the description of that process (i.e., a computer program).


title: Dynamic Program Slicing

authors:
Hiralal Agrawal
Joseph Robert Horgan

abstract: Program slices are useful in debugging, testing, maintenance, and understanding of programs. The conventional notion of a program slice, the static slice, is the set of all statements that might affect the value of a given variable occurrence. In this paper, we investigate the concept of the dynamic slice consisting of all statements that actually affect the value of a variable occurrence for a given program input. The sensitivity of dynamic slicing to particular program inputs makes it more useful in program debugging and testing than static slicing. Several approaches for computing dynamic slices are examined. The notion of a Dynamic Dependence Graph and its use in computing dynamic slices is discussed. The Dynamic Dependence Graph may be unbounded in length; therefore, we introduce the economical concept of a Reduced Dynamic Dependence Graph, which is proportional in size to the number of dynamic slices arising during the program execution.


title: Automatic Recognition of Induction Variables and Recurrence Relations by Abstract Interpretation

authors:
Zahira Ammarguellat
Williams Ludwell Harrison III

abstract: The recognition of recurrence relations is important in several ways to the compilation of programs. Induction variables, the simplest form of recurrence, are pivotal in loop optimizations and dependence testing. Many recurrence relations, although expressed sequentially by the programmer, lend themselves to efficient vector or parallel computation. Despite the importance of recurrences, vectorizing and parallelizing compilers to date have recognized them only in an ad-hoc fashion. In this paper we put forth a systematic method for recognizing recurrence relations automatically. Our method has two parts. First, abstract interpretation [CC77, CC79] is used to construct a map that associates each variable assigned in a loop with a symbolic form (expression) of its value. Second, the elements of this map are matched with patterns that describe recurrence relations. The scheme is easily extensible by the addition of templates, and is able to recognize nested recurrences by the propagation of the closed forms of recurrences from inner loops. We present some applications of this method and a proof of its correctness.


title: Compilation of Haskell Array Comprehensions for Scientific Computing

authors:
Steven Anderson
Paul Hudak

abstract: Monolithic approaches to functional language arrays, such as Haskell array comprehensions, define elements all at once, at the time the array is created, instead of incrementally. Although monolithic arrays are elegant, a naive implementation can be very inefficient. For example, if a compiler does not know whether an element has zero or many definitions, it must compile runtime tests. If a compiler does not know inter-element data dependencies, it must resort to pessimistic strategies such as compiling elements as thunks, or making unnecessary copies when updating an array.


title: The Program Dependence Web: A Representation Supporting Control, Data, and Demand-Driven Interpretation of Imperative Languages

authors:
Robert A. Ballance
Arthur B. Maccabe
Karl J. Ottenstein

abstract: The Program Dependence Web (PDW) is a program representation that can be directly interpreted using control-, data-, or demand-driven models of execution. A PDW combines a single-assignment version of the program with explicit operators that manage the flow of data values. The PDW can be viewed as an augmented Program Dependence Graph. Translation to the PDW representation provides the basis for projects to compile Fortran onto dynamic dataflow architectures and simulators. A second application of the PDW is the construction of various compositional semantics for program dependence graphs.


title: Improving Register Allocation for Subscripted Variables

authors:
David Callahan
Steve Carr
Ken Kennedy

abstract: Most conventional compilers fail to allocate array elements to registers because standard data-flow analysis treats arrays like scalars, making it impossible to analyze the definitions and uses of individual array elements. This deficiency is particularly troublesome for floating-point registers, which are most often used as temporary repositories for subscripted variables.


title: Iterative Type Analysis and Extended Message Splitting: Optimizing Dynamically-Typed Object-Oriented Programs

authors:
Craig Chambers
David M. Ungar

abstract: Object-oriented languages have suffered from poor performance caused by frequent and slow dynamically-bound procedure calls. The best way to speed up a procedure call is to compile it out, but dynamic binding of object-oriented procedure calls without static receiver type information precludes inlining. Iterative type analysis and extended message splitting are new compilation techniques that extract much of the necessary type information and make it possible to hoist run-time type tests out of loops.


title: Analysis of Pointers and Structures

authors:
David R. Chase
Mark N. Wegman
F. Kenneth Zadeck

abstract: 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


title: How to Read Floating-Point Numbers Accurately

abstract: Consider the problem of converting decimal scientific notation for a number into the best binary floating point approximation to that number, for some fixed precision. This problem cannot be solved using arithmetic of any fixed precision. Hence the IEEE Standard for Binary Floating-Point Arithmetic does not require the result of such a conversion to be the best approximation.


title: Type-Dependent Parameter Inference

authors:
Gordon V. Cormack
Andrew K. Wright

abstract: An algorithm is presented to infer the type and operation parameters of polymorphic functions. Operation parameters are named and typed at the function definition, but are selected from the set of overloaded definitions available wherever the function is used. These parameters are always implicit, implying that the complexity of using a function does not increase with the generality of its type.


title: Compact Representations for Control Dependence

authors:
Ron Cytron
Jeanne Ferrante
Vivek Sarkar

abstract: article Free Access Share on Compact representations for control dependence Authors: Ron Cytron IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , Jeanne Ferrante IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , V. Sarkar IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 25Issue 6Jun. 1990 pp 337–351https://doi.org/10.1145/93548.93592Online:01 June 1990Publication History 33citation585DownloadsMetricsTotal Citations33Total Downloads585Last 12 Months14Last 6 weeks2 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


title: Task Granularity Analysis in Logic Programs

authors:
Saumya K. Debray
Nai-Wei Lin
Manuel V. Hermenegildo

abstract: While logic programming languages offer a great deal of scope for parallelism, there is usually some overhead associated with the execution of goals in parallel because of the work involved in task creation and scheduling. In practice, therefore, the “granularity” of a goal, i.e. an estimate of the work available under it, should be taken into account when deciding whether or not to execute a goal concurrently as a separate task. This paper describes a method for estimating the granularity of a goal at compile time. The runtime overhead associated with our approach is usually quite small, and the performance improvements resulting from the incorporation of grainsize control can be quite good. This is shown by means of experimental results.


title: On the Structure of Verifiable Code Generator Specifications


title: A Fresh Look at Optimizing Array Bound Checking

abstract: This paper describes techniques for optimizing range checks performed to detect array bound violations. In addition to the elimination of range checks, the optimizations discussed in this paper also reduce the overhead due to range checks that cannot be eliminated by compile-time analysis. The optimizations reduce the program execution time and the object code size through elimination of redundant checks, propagation of checks out of loops, and combination of multiple checks into a single check. A minimal control flow graph (MCFG) is constructed using which the minimal amount of data flow information required for range check optimizations is computed. The range check optimizations are performed using the MCFG rather the CFG for the entire program. This allows the global range check optimizations to be performed efficiently since the MCFG is significantly smaller than the CFG. Any array bound violation that is detected by a program with all range checks included, will also be detected by the program after range check optimization and vice versa. Even though the above optimizations may appear to be similar to traditional code optimizations, similar reduction in the number of range checks executed can not be achieved by a traditional code optimizer. Experimental results indicate that the number of range checks performed in executing a program is greatly reduced using the above techniques.


title: The University of Washington Illustrating Compiler

authors:
Robert R. Henry
Kenneth M. Whaley
Bruce Forstall

abstract: The University of Washington illustrating compiler (UWPI) automatically illustrates the data structures used in simple programs written in a subset of Pascal2. A UWPI user submits a program to UWPI, and can then watch a graphical display show time varying illustrations of the data structures and program source code. UWPI uses the information latent in the program to determine how to illustrate the program. UWPI infers the abstract data types directly from the declarations and operations used in the source program, and then lays out the illustration in a natural way by instantiating well-known layouts for the abstracts types. UWPI solves program illustration using compile-time pattern matching and type inferencing to link anticipated execution events to display events, rather than relying on user assistance or specialized programming techniques. UWPI has been used to automatically illustrate didactic sorting and searching examples, and can be used to help teach basic data structures, or to help when debugging programs.


title: Representing Control in the Presence of First-Class Continuations

authors:
Robert Hieb
R. Kent Dybvig
Carl Bruggeman

abstract: Languages such as Scheme and Smalltalk that provide continuations as first-class data objects present a challenge to efficient implementation. Allocating activation records in a heap has proven unsatisfactory because of increased frame linkage costs, increased garbage collection overhead, and decreased locality of reference. However, simply allocating activation records on a stack and copying them when a continuation is created results in unbounded copying overhead. This paper describes a new approach based on stack allocation that does not require the stack to be copied when a continuation is created and that allows us to place a small upper bound on the amount copied when a continuation is reinstated. This new approach is faster than the naive stack allocation approach, and it does not suffer from the problems associated with unbounded copying. For continuation-intensive programs, our approach is at worst a constant factor slower than the heap allocation approach, and for typical programs, it is significantly faster. An important additional benefit is that recovery from stack overflow is handled gracefully and efficiently.


title: Identifying the Semantic and Textual Differences Between Two Versions of a Program

abstract: Text-based file comparators (e.g., the Unix utility diff), are very general tools that can be applied to arbitrary files. However, using such tools to compare programs can be unsatisfactory because their only notion of change is based on program text rather than program behavior. This paper describes a technique for comparing two versions of a program, determining which program components represents changes, and classifying each changed component as representing either a semantic or a textual change.


title: Type Declarations as Subtype Constraints in Logic Programming

abstract: This paper presents a type system for logic programs that supports parametric polymorphism and subtypes. This system follows most knowledge representation and object-oriented schemes in that subtyping is name-based, i.e., τ1 is considered to be a subtype of τ2 iff it is declared as such. We take this as a fundamental principle in the sense that type declarations have the form of subtype constraints. Types are assigned meaning by viewing such constraints as Horn clauses that, together with a few basic axioms, define a subtype predicate. This technique provides a (least) model for types and, at the same time, a sound and complete proof system for deriving subtypes. Using this proof system, we define well-typedness conditions which ensure that a logic program/query respects a set of predicate types. We prove that these conditions are consistent in the sense that every atom of every resolvent produced during the execution of a well-typed program is consistent with its type.


title: Design, Implementation and Evaluation of the FNC-2 Attribute Grammar System

authors:
Martin Jourdan
Didier Parigot
Catherine Julié
Olivier Durin
Carole Le Bellec

abstract: FNC-2 is a new attribute grammar processing system aiming at expressive power, efficiency, ease of use and versatility. Its development at INRIA started in 1986, and a first running prototype is available since early 1989. Its most important features are: efficient exhaustive and incremental visit-sequence-based evaluation of strongly (absolutely) non-circular AGs; extensive space optimizations; a specially-designed AG-description language, with provisions for true modularity; portability and versatility of the generated evaluators; complete environment for application development. This paper briefly describes the design and implementation of FNC-2 and its peripherals. Then preliminary experience with the system is reported.


title: Fast Breakpoints: Design and Implementation


title: Optimizing Programs over the Constructive Reals

authors:
Vernon A. Lee Jr.
Hans-Juergen Boehm

abstract: The constructive reals provide programmers with a useful mechanism for prototyping numerical programs, and for experimenting with numerical algorithms. Unfortunately, the performance of current implementations is inadequate for some potential applications. In particular, these implementations tend to be space inefficient, in that they essentially require a complete computation history to be maintained.


title: Generators and the Replicator Control Structures in the Parallel Environment of ALLOY

authors:
Thanasis Mitsolides
Malcolm Harrison

abstract: The need for searching a space of solutions appears often. Many problems, such as iteration over a dynamically created domain, can be expressed most naturally using a generate-and-process style. Serial programming languages typically support solutions of these problems by providing some form of generators or backtracking.


title: Graph Coloring Register Allocation for Processors with Multi-Register Operands

abstract: Though graph coloring algorithms have been shown to work well when applied to register allocation problems, the technique has not been generalized for processor architectures in which some instructions refer to individual operands that are comprised of multiple registers. This paper presents a suitable generalization.


title: Profile Guided Code Positioning

authors:
Karl Pettis
Robert C. Hansen

abstract: This paper presents the results of our investigation of code positioning techniques using execution profile data as input into the compilation process. The primary objective of the positioning is to reduce the overhead of the instruction memory hierarchy.

awards: Most Influential PLDI Paper (awarded 2000)


title: Two-Directional Record Layout for Multiple Inheritance

authors:
William W. Pugh
Grant E. Weddell

abstract: Much recent work in polymorphic programming languages allows subtyping and multiple inheritance for records. In such systems, we would like to extract a field from a record with the same efficiency as if we were not making use of subtyping and multiple inheritance. Methods currently used make field extraction 3-5 times slower, which can produce a significant overall performance slowdown.


title: Register Allocation Across Procedure and Module Boundaries

authors:
Vatsa Santhanam
Daryl Odnert

abstract: This paper describes a method for compiling programs using interprocedural register allocation. A strategy for handling programs built from multiple modules is presented, as well as algorithms for global variable promotion and register spill code motion. These algorithms attempt to address some of the shortcomings of previous interprocedural register allocation strategies. Results are given for an implementation on a single register file RISC-based architecture.


title: Instruction Reordering for Fork-Join Parallelism

abstract: article Free Access Share on Instruction reordering for fork-join parallelism Author: V. Sarkar IBM Research, Thomas. J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY IBM Research, Thomas. J. Watson Research Center, P.O. Box 704, Yorktown Heights, NYView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 25Issue 6Jun. 1990 pp 322–336https://doi.org/10.1145/93548.93590Published:01 June 1990Publication History 12citation555DownloadsMetricsTotal Citations12Total Downloads555Last 12 Months30Last 6 weeks7 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


title: How to Print Floating-Point Numbers Accurately

authors:
Guy L. Steele Jr.
Jon L. White


title: Higher-Order Attribute Grammars and Editing Environments

authors:
Tim Teitelbaum
Richard Chapman

abstract: Article Free Access Share on Higher-order attribute grammars and editing environments Authors: Tim Teitelbaum Department of Computer Science, Cornell University, Ithaca, NY Department of Computer Science, Cornell University, Ithaca, NYView Profile , Richard Chapman Department of Computer Science, Cornell University, Ithaca, NY Department of Computer Science, Cornell University, Ithaca, NYView Profile Authors Info & Claims PLDI '90: Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementationJune 1990 Pages 197–208https://doi.org/10.1145/93542.93567Published:01 June 1990Publication History 17citation435DownloadsMetricsTotal Citations17Total Downloads435Last 12 Months20Last 6 weeks3 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


title: Compiling Programs for a Linear Systolic Array

abstract: This paper describes an AL compiler for the Warp systolic array. AL is a programming language in which the user programs a systolic array as if it were a sequential computer and relies on the compiler to generate parallel code. This paper introduces the notion of data relations in compiling programs for systolic arrays. Unlike dependence relations among statements of a program, data relations define compatibility relations among data objects of a program. The AL compiler uses data relations to compute data compatibility classes, determine data distribution, and distribute loop iterations. The AL compiler can generate efficient parallel code almost identical to what the user would have written by hand. For example, the AL compiler generates parallel code for the LINPACK LU decomposition (SGEFA) and QR decomposition (SQRDC) routines with a nearly 8-fold speedup on the 10-cell Warp array for matrices of size 180 × 180.


title: Fast Code Generation Using Automatically-Generated Decision Trees

abstract: article Free Access Share on Fast code generation using automatically-generated decision trees Author: Alan L. Wendt Department of Computer Science, Colorado State University, Fort Collins, Colorado Department of Computer Science, Colorado State University, Fort Collins, ColoradoView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 25Issue 6Jun. 1990 pp 9–15https://doi.org/10.1145/93548.93549Online:01 June 1990Publication History 1citation500DownloadsMetricsTotal Citations1Total Downloads500Last 12 Months8Last 6 weeks1 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


title: Global Instruction Scheduling for Superscalar Machines

authors:
David Bernstein
Michael Rodeh

abstract: To improve the utilization of machine resources in superscalar processors, the instructions have to be carefully scheduled by the compiler.As internal parallelism and pipelining increases, it becomes evident that scheduling should be done beyond the basic block level.A scheme for global (intra-loop) scheduling is proposed, which uses the control and data dependence information summarized in a


title: Occurences in Debugger Specifications

abstract: We describe formal manipulations of programming language semantics that permit execution animation for interpreters. We first study the use of occurrences in the -calculus and we describe an implementation of the notion of residuals. We then describe applications in the development of interpreters for the lazy -calculus and the parallel language Occam. 1. Introduction Formal descriptions of programming language semantics have already been shown to yield executable specifications of interpreters for these languages [Mini-ML], [Esterel]. However, while the obtained interpreters have the clear advantage of being "certified" implementations, they lack a nice user interface for the very reason that the definition only deals with semantic values. An interpreter can be tranformed into a debugging tool by adding tracing, profiling, or control of execution functionalities. For us, an execution trace is a list of basic instruction calls that describes a history of execution, a profile is a list...


title: Mostly Parallel Garbage Collection

authors:
Hans-Juergen Boehm
Alan J. Demers
Scott Shenker

abstract: We present a method for adapting garbage collectors designed to run sequentially with the client, so that they may run concurrently with it.We rely on virtual memory hardware to provide information about pages that have been updated or "dirtied" during a given period of time.This method has been used to construct a mostly parallel trace-and-sweep collector that exhibits very short pause times.Performance measurements are given.


title: The Marion System for Retargetable Instruction Scheduling

authors:
David G. Bradlee
Robert R. Henry
Susan J. Eggers

abstract: article Free Access Share on The Marion system for retargetable instruction scheduling Authors: David G. Bradlee Department of Computer Science and Engineering, FR-35, University of Washington, Seattle, Washington Department of Computer Science and Engineering, FR-35, University of Washington, Seattle, WashingtonView Profile , Robert R. Henry Tera Computer, 400 N 34th Street, Seattle, WA and Department of Computer Science and Engineering, FR-35, University of Washington, Seattle, Washington Tera Computer, 400 N 34th Street, Seattle, WA and Department of Computer Science and Engineering, FR-35, University of Washington, Seattle, WashingtonView Profile , Susan J. Eggers Department of Computer Science and Engineering, FR-35, University of Washington, Seattle, Washington Department of Computer Science and Engineering, FR-35, University of Washington, Seattle, WashingtonView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 26Issue 6June 1991 pp 229–240https://doi.org/10.1145/113446.113465Published:01 May 1991Publication History 36citation502DownloadsMetricsTotal Citations36Total Downloads502Last 12 Months28Last 6 weeks2 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


title: Fortran at Ten Gigaflops: The Connection Machine Convolution Compiler

authors:
Mark Bromley
Steven Heller
Timothy S. McNerney
Guy L. Steele Jr.

abstract: We have implemented a prototype of a specialized compiler module and associated run-time support that allows a Fortran user to achieve sustained floatingpoint performance of over 10 gigaflops on the Connection Machine Model CM-2.This improves substantially over the previous record of 5.6 gigaflops, which was achieved by means of hand-crafted low-level coding techniques (on which this work has been based).Indeed, the same code that ran at 5.6 gigaflops in 1989 now runs at over 14 gigaflops.The compiler module processes array assignment statements of a certain form the right-hand side must be a sum of products and the products must use the Fortran 90 array-shifting intrinsic in a certain stylized pattern.Such assignment statements are suitable for expressing array convolution (stencil) computations and can be executed efficiently by chained multiplyadd operations.Our implementation strategy divides responsibility for the computation into four parts.A run-time library provides the outer loop structure for strip-mining and for handling multidimensional arrays.Anew primitive speeds up nearest-neighbor grid communication.Hand-written CM-2 sequencer microcode directs the pipelined execution of the floating-point units.The compiler module performs a kind of loop unrolling in order to optimize the use of registers and determines, at compile time, the microcode to be used at run time.


title: Register Allocation via Hierarchical Graph Coloring

authors:
David Callahan
Brian D. Koblenz

abstract: We present a graph coloring register allocator de-signed to minimize the number of dynamic memory references. We cover the program with sets of blocks called tiles and group these tiles into a tree reflecting the program’s hierarchical control structure. Registers are allocated for each tile using standard graph coloring techniques and the local allocation and conflict information is passed around the tree in a two phase algorithm. This results in an allocation of reg-isters that is sensitive to local usage patterns while retaining a global perspective. Spill code is placed in less frequently executed portions of the program and the choice of variables to spill is based on usage pat-terns between the spills and the reloads rather than usage patterns over the entire program. 1


title: Soft Typing

authors:
Robert Cartwright
Mike Fagan

abstract: of programs than ML.We have also developed an algorithm for frugally inserting run-time checks in programs that do not type check.


title: Size and Access Inference for Data-Parallel Programs

authors:
Siddhartha Chatterjee
Guy E. Blelloch
Allan L. Fisher

abstract: Abstract: "Data-parallel programming languages have many desirable features, such as single-thread semantics and the ability to express fine-grained parallelism. However, it is challenging to implement such languages efficiently on conventional MIMD multiprocessors, because these machines incur a high overhead for small grain sizes. This paper presents compile-time analysis techniques for data-parallel program graphs that reduce these overheads in two ways: by stepping up the grain size, and by relaxing the synchronous nature of the computation without altering the program semantics.The algorithms partition the program graph into clusters of nodes such that all nodes in a cluster have the same loop structure, and futher refine these clusters into epochs based on generation and consumption patterns of data vectors. This converts the fine-grain parallelism in the original program to medium-grain loop parallelism, which is better suited to MIMD machines. A compiler has been implemented based on these ideas. We present performance results for data-parallel kernels analyzed by the compiler and converted to single-program multiple-data (SPMD) code running on an Encore Multimax."


title: Parameterized Partial Evaluation

authors:
Charles Consel
Siau-Cheng Khoo

abstract: article Free Access Share on Parameterized partial evaluation Authors: Charles Consel Yale University, Department of Computer Science, New Haven, CT Yale University, Department of Computer Science, New Haven, CTView Profile , Siau Cheng Khoo Yale University, Department of Computer Science, New Haven, CT Yale University, Department of Computer Science, New Haven, CTView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 26Issue 6June 1991 pp 92–106https://doi.org/10.1145/113446.113454Online:01 May 1991Publication History 7citation244DownloadsMetricsTotal Citations7Total Downloads244Last 12 Months6Last 6 weeks2 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF


title: Refinement Types for ML

authors:
Timothy S. Freeman
Frank Pfenning

abstract: T$'e describe a refinement of ML's type system allowing the specification of recursively defined subtypes of user-defined datatypes.The resulting system of rejirzemeni f,ypes preserves desirable properties of ML such as decidability of type inference, while at the same time allowing more errors to be detected at compile-time.The type system combines abstract interpretation with ideas from the intersection type discipline, but remains closely tied to ML in that refinement types are given only to programs which are already well-typed in ML.


title: Generalized Algorithmic Debugging and Testing

authors:
Peter Fritzson
Tibor Gyimóthy
Mariam Kamkar
Nahid Shahmehri

abstract: This paper presents a method for semi-automatic bug localization, generalized algorithmic debugging, which has been integrated with the category partition method for functional testing. In this way the efficiency of the algorithmic debugging method for bug localization can be improved by using test specifications and test results. The long-range goal of this work is a semi-automatic debugging and testing system which can be used during large-scale program development of nontrivial programs. The method is generally applicable to procedural languages and is not dependent on any ad hoc assumptions regarding the subject program. The original form of algorithmic debugging, introduced by Shapiro, was however limited to small Prolog programs without side-effects, but has later been generalized to concurrent logic programming languages. Another drawback of the original method is the large number of interactions with the user during bug localization. To our knowledge, this is the first method which uses category partition testing to improve the bug localization properties of algorithmic debugging. The method can avoid irrelevant questions to the programmer by categorizing input parameters and then match these against test cases in the test database. Additionally, we use program slicing, a data flow analysis technique, to


title: A Timed Petri-Net Model for Fine-Grain Loop Scheduling

authors:
Guang R. Gao
Yue-Bong Wong
Qi Ning

abstract: article Free Access Share on A timed Petri-net model for fine-grain loop scheduling Authors: Guang R. Gao School of Computer Science, McGill University, 3480 University, Montréal, Québec H3A 2A7 School of Computer Science, McGill University, 3480 University, Montréal, Québec H3A 2A7View Profile , Yue-Bong Wong School of Computer Science, McGill University, 3480 University, Montréal, Québec H3A 2A7 School of Computer Science, McGill University, 3480 University, Montréal, Québec H3A 2A7View Profile , Qi Ning School of Computer Science, McGill University, 3480 University, Montréal, Québec H3A 2A7 School of Computer Science, McGill University, 3480 University, Montréal, Québec H3A 2A7View Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 26Issue 6June 1991 pp 204–218https://doi.org/10.1145/113446.113463Published:01 May 1991Publication History 41citation490DownloadsMetricsTotal Citations41Total Downloads490Last 12 Months23Last 6 weeks5 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


title: Practical Dependence Testing

authors:
Gina Goff
Ken Kennedy
Chau-Wen Tseng

abstract: Precise and efficient dependence tests are essential to theeffectivermss ofaparallelizing compiler. This paper proposes a dependence testing scheme based on classi-fyingpairs ofsubscripted variable references. Exact yet fast dependence tests are presented for certain classes ofarray references, as well as empirical results showing that these references dominate scientific Fortran codes. These dependence tests are being implemented at Rice University in both PFC, aparallelizing compiler, and ParaScope, a parallel programming environment, 1


title: Tag-Free Garbage Collection for Strongly Typed Programming Languages

abstract: With the emergence of a number of strongly typed kmguages with very dynamic storage allocation, efficient methods of storage reclamation have become especially important, Even though no type tags are required for type checking programs written in these languages, current implementations douse tags to support run time garbage collection, This often inflicts a high time and space overhead on program execution. Since the early days of LISP (and Algo168 later on), there have been schemes for performing tag-free garbage collection, In this paper, we describe an improvement of existing methods that leads to more effective storage rechunation in the absence of tags. Garbage collection has also traditionally been viewed as being independent of the particular program being executed. This means that results of compile-time analyses which could increase the effectiveness of garbage collection cannot be incorporated easily into the garbage collection process. This paper describes a method for performing garbage collection 1) in the absence of tagged data, and 2) using compile-time information. This method relies on compiler-generated garbage collection routines specific to the program bekg executed and incurs no time overhead during execution other then the cost of the garbage collection process itself. We describe tag-free garbage collection methods for monomorphically typed and polymorphically typed languages, and suggest how they might be extended to support parallel languages.


title: A Methodology for Managing Hard Constraints in CLP Systems

authors:
Joxan Jaffar
Spiro Michaylov
Roland H. C. Yap

abstract: In constraint logic programming (CLP) systems, the standard technique for dealing with hard constraints is to delay solving them until additional constraints reduce them to a simpler form.For example, the CLP (7?) system delays the solving of nonlinear equations until they become linear, when certain variables become ground.In a naive implement ation, the overhead of delaying and awakening constraints could render a CLP system impractical.


title: Circular Scheduling: A New Technique to Perform Software Pipelining


title: Monitoring Semantics: A Formal Framework for Specifying, Implementing, and Reasoning about Execution Monitors

authors:
Amir Kishon
Paul Hudak
Charles Consel

abstract: We introduce monitoring semantics, a non-standard model


title: Strictness and Binding-Time Analyses: Two for the Price of One

abstract: article Free Access Share on Strictness and binding-time analyses: two for the price of one Author: John Launchbury University of Glasgow University of GlasgowView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 26Issue 6June 1991 pp 80–91https://doi.org/10.1145/113446.113453Online:01 May 1991Publication History 9citation234DownloadsMetricsTotal Citations9Total Downloads234Last 12 Months8Last 6 weeks2 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


title: Efficient and Exact Data Dependence Analysis

authors:
Dror E. Maydan
John L. Hennessy
Monica S. Lam

abstract: Data dependence testing is the basic step in detecting loop level parallelism in numerical programs. The problem is equivalent to integer linear programming and thus in general cannot be solved efficiently. Current methods in use employ inexact methods that sacrifice potential parallelism in order to improve compiler efficiency. This paper shows that in practice, data dependence can be computed exactly and efficiently. There are three major ideas that lead to this result. First, we have developed and assembled a small set of efficient algorithms, each one exact for special case inputs. Combined with a moderately expensive backup test, they are exact for all the cases we have seen in practice. Second, we introduce a memorization technique to save results of previous tests, thus avoiding calling the data dependence routines multiple times on the same input. Third, we show that this approach can both be extended to compute distance and direction vectors and to use unknown symbolic terms without any loss of accuracy or efficiency, We have implemented our algorithm in the SUIF system, a general purpose compiler system developed at Stanford. We ran the algorithm on the PERFECT Club Benchmarks and our data dependence analyzer gave an exact solution in all cases efficiently.


title: Procedure Merging with Instruction Caches

abstract: This paper describes a method of determining which procedures to merge for machines with instruction caches. The method uses profile information, the structure of the program, the cache size, and the cache miss penalty to guide the choice. Optimization for the cache is assumed to follow procedure merging. The method weighs the benefit of removing calls with the increase in the instruction cache miss rate. Better performance is achieved than previous schemes that do not consider the cache. Merging always results in a savings, unlike simpler schemes that can make programs slower once cache effects are considered. The new method also has better performance even when parameters to simpler algorithms are varied to get the best performance. This report is a preprint of a paper that will be presented at the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, Toronto, Ontario, Canada, June 26-28, 1991. Copyright 1990 ACM. i 1 Introduction This paper presents a ...


title: CCG: A Prototype Coagulating Code Generator

abstract: This paper describes the design and performance of CCG, a prototype code generator based on couguiation.Coagulation orders code generation using a run-time profile for the program being compiled.By treating busy parts of a program first and using the strategy of local optimality, CCG maximizes the benefit of careful instruction selection, register allocation and interprocedural optimization while avoiding unnecessary data movement in busy sections.Coagulation radically alters standard techniques for code generation, achieving highly efficient code without graph-coloring register allocation or peephole optimization.Experimental results showing an average 25% improvement over the GNU C compiler suggest, that compilation order is crucial and that coagulation can outperform current code generator technology.


title: Linear-Time, Optimal Code Scheduling for Delayed-Load Architectures

authors:
Todd A. Proebsting
Charles N. Fischer

abstract: Article Linear-time, optimal code scheduling for delayed-load architectures Share on Authors: Todd A. Proebsting University of Wisconsin-Madison, Dept. of Computer Sciences, 1210 W. Dayton St., Madison, WI University of Wisconsin-Madison, Dept. of Computer Sciences, 1210 W. Dayton St., Madison, WIView Profile , Charles N. Fischer University of Wisconsin-Madison, Dept. of Computer Sciences, 1210 W. Dayton St., Madison, WI University of Wisconsin-Madison, Dept. of Computer Sciences, 1210 W. Dayton St., Madison, WIView Profile Authors Info & Claims PLDI '91: Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementationMay 1991 Pages 256–267https://doi.org/10.1145/113445.113467Online:01 May 1991Publication History 28citation670DownloadsMetricsTotal Citations28Total Downloads670Last 12 Months11Last 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


title: Advice to Authors of Extended Abstracts


title: CML: A Higher-Order Concurrent Language

abstract: article Free Access Share on CML: A higher concurrent language Author: John H. Reppy Cornell University Cornell UniversityView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 26Issue 6June 1991pp 293–305https://doi.org/10.1145/113446.113470Published:01 May 1991Publication History 203citation1,330DownloadsMetricsTotal Citations203Total Downloads1,330Last 12 Months128Last 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


title: The Semantic Approach to Program Slicing

abstract: Program slicing is a source-to-source transformation


title: Predicting Program Behavior Using Real or Estimated Profiles

abstract: There is a growing interest in optimizations that depend on or benefit from an execution profile that tells where time is spent. How well does a profile from one run describe the behavior of a different run, and how does this compare with the behavior predicted statically by examining the program itself ? This paper defines two abstract measures of how well a profile predicts actual behavior. According to these measures, real profiles indeed do better than estimated profiles, usually. A perfect profile from an earlier run with the same data set, however, does better still, sometimes by a factor of two. Using such a profile is unrealistic, and can lead to inflated expectations of a profile-driven optimization. i 1. Introduction Many people have built or speculated on systems that use a run-time profile to guide code optimization. Applications include the selection of variables to promote to registers [7,8], placement of code sequences to improve cache behavior [3,6], and pre...


title: Automatic Generation of Global Optimizers

authors:
Deborah Whitfield
Mary Lou Soffa

abstract: article Free Access Share on Automatic generation of global optimizers Authors: Deborah Whitfield Department of Computer Science, University of Pittsburgh, Pittsburgh, PA Department of Computer Science, University of Pittsburgh, Pittsburgh, PAView Profile , Mary Lou Soffa Department of Computer Science, University of Pittsburgh, Pittsburgh, PA Department of Computer Science, University of Pittsburgh, Pittsburgh, PAView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 26Issue 6June 1991 pp 120–129https://doi.org/10.1145/113446.113456Published:01 May 1991Publication History 22citation315DownloadsMetricsTotal Citations22Total Downloads315Last 12 Months9Last 6 weeks2 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


title: Effective "Static-Graph" Reorganization to Improve Locality in Garbage-Collected Systems

authors:
Paul R. Wilson
Michael S. Lam
Thomas G. Moher

abstract: Article Free Access Share on Effective "static-graph" reorganization to improve locality in garbage-collected systems Authors: Paul R. Wilson Electrical Engineering and Computer Science Dept., University of Illinois at Chicago, Box 4348 (m/c 154) Chicago, Illinois Electrical Engineering and Computer Science Dept., University of Illinois at Chicago, Box 4348 (m/c 154) Chicago, IllinoisView Profile , Michael S. Lam Electrical Engineering and Computer Science Dept., University of Illinois at Chicago, Box 4348 (m/c 154) Chicago, Illinois Electrical Engineering and Computer Science Dept., University of Illinois at Chicago, Box 4348 (m/c 154) Chicago, IllinoisView Profile , Thomas G. Moher Electrical Engineering and Computer Science Dept., University of Illinois at Chicago, Box 4348 (m/c 154) Chicago, Illinois Electrical Engineering and Computer Science Dept., University of Illinois at Chicago, Box 4348 (m/c 154) Chicago, IllinoisView Profile Authors Info & Claims PLDI '91: Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementationMay 1991 Pages 177–191https://doi.org/10.1145/113445.113461Published:01 May 1991Publication History 83citation592DownloadsMetricsTotal Citations83Total Downloads592Last 12 Months39Last 6 weeks1 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


title: A Data Locality Optimizing Algorithm

authors:
Michael E. Wolf
Monica S. Lam

abstract: This paper proposes an algorithm that improves the locality of a loop nest by transforming the code via interchange, reversal, skewing and tiling.The loop transformation rrlgorithm is based on two concepts: a mathematical formulation of reuse and locality, and a loop transformation theory that unifies the various transforms as unimodular matrix tmnsfonnations.The algorithm haa been implemented in the SUIF (Stanford University Intermediate Format) compiler, and is successful in optimizing codes such as matrix multiplication, successive over-relaxation (SOR), LU decomposition without pivoting, and Givens QR factorization.Performance evaluation indicates that locatity optimization is especially crucial for scaling up the performance of parallel code.

awards: Most Influential PLDI Paper (awarded 2001)