title: Global context recovery: A new strategy for parser recovery from syntax errors

authors:
Ajit B. Pai
Richard B. Kieburtz

abstract: Methods for error recovery in parsing a deterministic, context-free language need not be derived by ad hoc means. When fixed, table-driven parsing algorithms are used the error recovery procedures can also make use of knowledge about the grammar for the language, derived from the parsing tables. However, at the point of detection of certain kinds of syntax errors, the knowledge of a sentential prefix already parsed, as reflected in the current state of the parsing stack, will be incorrect. Effective error recovery under such circumstances has proven to be difficult. We suggest the use of fiducial, or trustworthy symbols of a language as a key to recovery in these difficult cases. In this paper we give a characterization of such symbols in terms of properties of a grammar and give an algorithm that is capable of global context recovery under all circumstances. It has been implemented in conjunction with an LL(1) parser. We have compared it experimentally with the LR-parser recovery algorithm of Pennello and DeRemer on a test set of 126 small Pascal programs.


venue: pldi

title: Machine-independent PASCAL code optimization

authors:
Daniel R. Perkins
Richard L. Sites

abstract: A variant of PASCAL pseudo-code which is suitable for optimization is presented. This new language, Universal pseudo-code, is designed to be easily extended to meet the needs of a variety of target machines. The language is further designed such that only one optimizer need be written for it. This approach lends itself well to the portable software spirit of PASCAL. The problems and opportunities associated with optimization at this level are discussed.


title: The use of transition matrices in a recursive-descent compiler

abstract: Transition matrices are a well-known tool for the construction of bottom-up compilers. This paper discusses the use of transition matrices in the recursive-descent compiler for the structured assembly language PL/85. In this compiler, a transition matrix (TM) is a self-contained module which can recursively invoke other TMs. TM invocation and exit and state transitions are handled by a microcoded interpreter. It is shown that our use of TMs made the compiler easy to implement and maintain, considerably reduced the space requirements for the parser, and resulted in a reliable, efficient and flexible compiler with good error handling capabilities.


title: Dynamic allocation of space for attribute instances in multi-pass evaluators of attribute grammars

abstract: Attribute grammars [14] have proved useful as the basis of input languages for compiler-compilers. Many algorithms have evolved which can be used to automatically produce an evaluator for a given attribute grammar. The task of an evaluator is to compute the values of the attribute instances attached to a parse tree. From the compiler point of view, the evaluator takes care of the semantic analysis and in some cases also the code generation of the compiler. An overview of various evaluation algorithms is given in [6]. A bibliography can be found in [21].


title: Compiler design for efficient code generation and program optimization

authors:
Andres Rudmik
E. S. Lee

abstract: This paper describes the design of a compiler for an extended PASCAL with particular emphasis on code generation and optimization. The design objectives are: compiler reliability, code generator portability and object code efficiency.


title: Machine-independent register allocation

abstract: The context of this paper is a machine-independent Pascal optimizer that transforms an intermediate stack-machine pseudo-code program into a generally smaller and faster pseudo-code program. The emphasis of this current paper is on the approach taken for mapping registers and storage, using an abstract but practical definition of the target machine's storage hierarchy. A companion paper [7] describes the overall optimizer project. After starting on this project, additional input became available from a Fortran-to-Pcode compiler written at Stanford [2]. Our storage mapping design is sufficiently robust that the addition of Fortran EQUIVALENCE and COMMON statements required no changes.


title: Program checking

abstract: In languages such as Pascal, the programmer can arrange to have the compiler check such things as the range of the value of a variable only by defining a new type or sub-type. I have investigated how more powerful checking facilities might be provided if they were divorced from the type machinery, and also if the necessary language constructs were designed independent of what any particular compiler would check at compile-time.


title: An Overview of the PL.8 Compiler

authors:
Marc A. Auslander
Martin Hopkins

abstract: The PL.8 compiler accepts multiple source languages and produces high quality object code for several different machines. The strategy used is to first do a simple translation of the source program to a low level intermediate language. Global optimization and register allocation are then used to improve code rather than relying on special case code selection.


title: The Design of an Integrated Support Software System

authors:
Arra Avakian
Sam Haradhvala
Julian Horn
Bruce Knobe

abstract: This paper describes some of the interesting features of a large integrated support software system. The system was built to support the development, on an IBM 370, of an extremely large Pascal program to be run on a network of Intel 8086 microprocessors. The Pascal program was composed of over 1500 separately compiled components containing over 1,000,000 lines of source code. About 200 technical people were involved in this activity. In a project of this magnitude, integration issues are of overriding importance. There must be all the type checking and managerial control associated with standard Pascal programs, but the Pascal solution of compiling the whole application as one unit is clearly unacceptable. Various pieces must be separately compiled.


title: A Single-Pass Syntax-Directed Front End for Ada

abstract: This paper describes the front-end processor of an Ada compiler that is under development at Florida State University. The compiler is coded in Pascal, to execute on a CDC Cyber system, and is presently targeted to the Z8000 microprocessor architecture. Owing at least in part to the peculiar origins and changing goals of this project, the front end processor is rather unlike those of the other Ada compilers of which we know. Perhaps its most distinctive feature is that it operates in one pass.


title: An Implementation of a Code Generator Specification Language for Table Driven Code Generators

abstract: This paper discusses an implementation of Glanville's code generator generator for producing a code generator for a production Pascal compiler on an Amdahl 470.We successfully replaced the hand written code generator of an existing compiler with one which was produced automatically from a formal specification. This paper first outlines Glanville's original scheme, then describes extensions which were necessary for generating code for a production compiler.


title: Experience with an Experimental Compiler Generator Based on Denotational Semantics

authors:
James Bodwin
Laurette Bradley
Kohji Kanda
Diane Litle
Uwe F. Pleban

abstract: Compiler generation based on formal semantics has received considerable attention in recent years from a number of semanticists. Compiler writers, on the other hand, know relatively little about these efforts. This paper tries to remedy this situation by discussing our experimentation with the Semantics Implementation System (SIS) of Peter Mosses. SIS allows the user to generate a complete compiler from a formal specification of the syntax and semantics of a programming language. In particular, the translator component of a compiler is obtained by directly implementing a denotational semantics. Consequently, a compiler is expressed as a higher order function. A program is compiled by formally applying the compiler to a tree representation of the program and simplifying this application. The experimentation with SIS indicates that compiler generation based on denotational semantics is feasible, though not yet viable. We argue that SIS constitutes an important first step toward the automatic construction of provably correct, complete, and reasonably efficient compilers from formal syntactic and semantic specifications.


title: An Optimizing Compiler for Lexically Scoped LISP

authors:
Rodney A. Brooks
Richard P. Gabriel
Guy L. Steele Jr.

abstract: We are developing an optimizing compiler for a dialect of the LISP language. The current target architecture is the S-I, a multiprocessing supercomputer designed at Lawrence Livermore National Laboratory. While LISP is usually thought of as a language primarily for symbolic processing and list manipulation, this compiler is also intended to compete with the S-1 PASCAL and FORTRAN compilers for quality of compiled numerical code. The S-1 is designed for extremely high-speed signal processing as well as for symbolic computation; it provides primitive operations on vectors of floating-point and complex numbers. The LISP compiler is designed to exploit the architecture heavily.


title: A Practical Method for Syntactic Error Diagnosis and Recovery

authors:
Michael G. Burke
Gerald A. Fisher

abstract: Our goal is to develop a practical syntactic error recovery method applicable within the general framework of viable prefix parsing. Our method represents an attempt to accurately diagnose and report all syntax errors without reporting errors that are not actually present. Successful recovery depends upon accurate diagnosis of errors together with sensible “correction” or alteration of the text to put the parse back on track. The issuing of accurate and helpful diagnostics is achieved by indicating the nature of the recovery made for each error encountered. The error recovery is prior to and independent of any semantic analysis of the program. However, the method does not exclude the invocation of semantic actions while parsing or preclude the use of semantic information for error recovery.


title: Register Allocation & Spilling via Graph Coloring

abstract: In a previous paper we reported the successful use of graph coloring techniques for doing global register allocation in an experimental PL/I optimizing compiler. When the compiler cannot color the register conflict graph with a number of colors equal to the number of available machine registers, it must add code to spill and reload registers to and from storage. Previously the compiler produced spill code whose quality sometimes left much to be desired, and the ad hoe techniques used took considerable amounts of compile time. We have now discovered how to extend the graph coloring approach so that it naturally solves the spilling problem. Spill decisions are now made on the basis of the register conflict graph and cost estimates of the value of keeping the result of a computation in a register rather than in storage. This new approach produces better object code and takes much less compile time.


title: The Design of a Data Flow Analyzer

authors:
Anita L. Chow
Andres Rudmik

abstract: This paper presents an efficient inter-procedural data flow analysis algorithm for precisely determining aliases in programs that employ a rich set of parameter passing mechanisms and pointer data types. This approach handles the use of pointers bounded to a data type as in Pascal, as well as unbounded pointers that can point to the same locations to which variables map. In the last step of this approach, the alias information is used to compute data flow information that is required for optimization.


title: Engineering a Production Code Generator

abstract: This paper describes the structure of a code generator formed by merging the best aspects of three code generation techniques: Graham-Glanville parser-driven code generation [G] [GG] [GR] [HG], the register allocation/spill mechanism from the Portable C Compiler [J], and a code template expander [W]. The Graham-Glanville method was modified to use a standard LALR parser and table builder, and the register allocation method was extended in several significant ways in order to make optimal use of a machine with characterized registers.


title: An Attribute Grammar for Ada

authors:
Sophia Drossopoulou
James S. Uhl
Guido Persch
Gerhard Goos
Manfred Dausmann
Georg Winterstein

abstract: We describe the development of a formal specification of the static semantics of Ada in form of an attribute grammar. This specification is complete, and was tested extensively with automatically generated equivalent Pascal programs. From this specification we systematically developed the semantic analysis part of our Ada Compiler Front End. We outline the general proceeding when specifying semantic analysis with attribute grammars and then discuss to some extent examples about declaration elaboration and overloading resolution.


title: LINGUIST-86: Yet Another Translator Writing System Based On Attribute Grammars

abstract: LINGUIST-86 is a commercially-developed translator-writing-system based on attribute grammars [K]. From an input attribute grammar it generates a set of high-level language source modules that form an alternating-pass attribute evaluator [JW]. LINGUIST-86 generates attribute evaluators efficient enough to run on a microcomputer at speeds competitive with other translators on the system. The Attributed Program Tree is kept on secondary storage rather than in randomly-accessed memory, thus allowing non-trivial inputs to be evaluated on a microcomputer system. LINGUIST-86 also applies an optimization called static subsumption that eliminates many copy rules from the generated evaluators. LINGUIST-86 is itself written as an 1800 line attribute grammar and is self-generating.


title: A Truly Generative Semantics-Directed Compiler Generator

authors:
Harald Ganzinger
Robert Giegerich
Ulrich Möncke
Reinhard Wilhelm

abstract: This paper describes semantic processing in the compiler generating system MUG2. MUG2 accepts high-level descriptions of the semantics of a programming language including full runtime semantics, data flow analysis, and optimizing transformations. This distinguishes MUG2 from systems such as YACC [Joh75], HLP [HLP78], PQCC [PQC79], or its own former version [GRW77] with respect to expressive power and convenience. In this respect, MUG2 comes close to semantics-directed systems such as [Mos76], [JoS80], [Set81], [Pau82]. In contrast to these, MUG2 is not a universal translator system where program independent semantic properties have to be evaluated at compilation time. The description concepts of MUG2 allow a far reaching separation of language vs. program dependent semantics, thus constituting a truly generative approach to semantics-directed compiler generation.


title: An Experiment in Table Driven Code Generation

authors:
Susan L. Graham
Robert R. Henry
Robert A. Schulman

abstract: We have constructed a local code generator for the VAX-112 using a parser-like instruction pattern matcher. The code generator replaces the second pass of the UNIX3 Portable “Crdquo; compiler. This paper describes the design of the code generator and the special considerations imposed by the pattern matching process. We summarize the structure of the machine description grammar and its associated semantic actions, as well as the tools we developed to manipulate the large VAX description. In our experience, this approach makes the instruction selection phase of the compiler easier and faster to implement, and more likely to be correct than traditional techniques.


title: gprof: a Call Graph Execution Profiler

authors:
Susan L. Graham
Peter B. Kessler
Marshall K. McKusick

abstract: Large complex programs are composed of many small routines that implement abstractions for the routines that call them. To be useful, an execution profiler must attribute execution time in a way that is significant for the logical structure of a program as well as for its textual decomposition. This data must then be displayed to the user in a convenient and informative way. The gprof profiler accounts for the running time of called routines in the running time of the routines that call them. The design and use of this profiler is described.


title: Current Status of a Portable Lisp Compiler

authors:
Martin L. Griss
Eric Benson
Anthony C. Hearn

abstract: This report describes the current status of a Portable LISP Compiler used with great success to compile Standard LISP on a variety of machines. It has also been used to provide a portable implementation base for a new LISP (PSL) on the DECSystem 20 and VAX.


title: Semantic Errors - Diagnosis and Repair

authors:
C. W. Johnson
Colin Runciman

abstract: In compiler technology, semantic error handling has too often used ad hoc techniques and terse messages of fixed content. In contrast, we present general models of diagnosis and repair of semantic errors and illustrate their use in the York Ada Workbench Compiler. The diagnostic model focuses upon the problem of selecting suitable information from which the programmer can locate and correct an error; following a brief discussion of an approach in which filters are applied to reports, and we give a more extensive account of a new approach using an interactive diagnostic interpreter. The repair model is based upon the idea of plastic nodes which are introduced into the compiler's internal representation of a program to replace normal nodes which are missing or erroneous.


title: Experience with Porting Techniques on a COBOL 74 Compiler

abstract: The problems of compiler construction have largely been solved for COBOL '74, but a remaining fundamental consideration in a commercial environment is the cost of compiler development. This can be reduced by the use of portable software, but the cost of porting to a new system remains significant. In the microprocessor system market, two approaches have been followed. The first is to produce software for a virtual machine environment and simulate this on real hardware be means of an interpreter. Most software, including language processors and large parts of the operating system, can be transferred almost unchanged to a new processor. Nearly all commercial software for microprocessors has been developed on this basis. The alternative approach is to produce software which, by virtue of certain characteristics, can be made to be portable to new real machine environments, provided the appropriate high level language compiler is available.


title: Compiler Construction Using Attribute Grammars

authors:
Kai Koskimies
Kari-Jouko Räihä
Matti Sarjakoski

abstract: The adequacy of attribute grammars as a compiler writing tool is studied on the basis of the experiences on attribute grammars for Pascal and a subset of Euclid. A qualitative assessment of the grammars shows that the compiler oriented view in the design of an attribute grammar tends to make the grammar hard to understand. A design discipline is proposed to improve the comprehensibility of the grammar. Quantitative measurements of the automatically generated compilers suggest that an efficient compiler can be produced from an attribute grammar. To achieve this, a carefully optimized implementation of the compiler-compiler is required.


title: A Practical Method for Code Generation Based on Exhaustive Search

authors:
David W. Krumme
David H. Ackley

abstract: An original method for code generation has been developed in conjunction with the construction of a compiler for the C programming language on the DEC-10 computer. The method is comprehensive, determining evaluation order and doing register allocation and instruction selection simultaneously. It uses exhaustive search rather than heuristics, and is table-driven, with most machine-specific information isolated in the tables. Testing and evaluation have shown that the method is effective, that the search process is not too time consuming, and that the compiler is capable of producing code as good as that of other optimizing compilers.


title: A Flexible Compiler Structure That Allows Dynamic Phase Ordering

authors:
Wilf R. LaLonde
Jim des Rivières

abstract: Traditionally, compilers have been internally organized into separate phases that are invoked in a fixed, predetermined order. However, the optimal phase invocation order is usually different for different contexts, such as (1) large batch-oriented production environments, (2) small batch-oriented student environments, and (3) interactive programming environments.


title: Experience with an Automatic Code Generator Generator

authors:
Rudolf Landwehr
Hans-Stephan Jansohn
Gerhard Goos

abstract: We implemented an automatic code generator generator based on the approach of Glanville and Graham. We describe our experience with this system and compare the generated code with that of a conventional Pascal compiler.


title: Cray Pascal

authors:
Nazim H. Madhavji
I. R. Wilson

abstract: This paper presents an investigation of the design decisions taken in the implementation of a compiler for Pascal on the CRAY-1 computer. The structured nature of Pascal statements and data structures is contrasted with the 'powerful computing engine' nature of the CRAY-1 hardware. The accepted views of Pascal as a simple one-pass language and the CRAY-1 as a vector processor are laid aside in favour of a multi-pass approach, taking account of the machine's scalar capabilities. The project as a whole, aims to produce highly efficient run-time code for applications likely to be programmed in Pascal. Some statistics are given to indicate the nature of such applications.


title: Optimization of Range Checking

authors:
Victoria Markstein
John Cocke
Peter W. Markstein

abstract: An analysis is given for optimizing run-time range checks in regions of high execution frequency. These optimizations are accomplished using strength reduction, code motion and common subexpression elimination. Test programs, using the above optimizations, are used to illustrate run-time improvements.


title: The Linear Graph Package, a Compiler Building Environment

abstract: The Linear Graph package is a collection of software tools that provides a software development environment particularly well suited to compiler construction. More precisely, the Linear Graph (or “LG”) package is a generic specification of these tools. No specific implementation language or host computer system is presumed, and, in fact, LG packages have been built in several languages on a variety of computers.


title: A Forward Move Algorithm for LL and LR Parsers

authors:
Jon Mauney
Charles N. Fischer

abstract: A wide variety of algorithms have been suggested for the repair of syntactic errors in a computer program. Since there is usually more than one possible repair for any syntax error, many algorithms employ a cost function to guide the the repair, and some [1,3,4,6], guarantee that the repair chosen will be least-cost, according to some definition. (The others, although guided by costs, do not guarantee least-cost in all cases.) Fischer et al. [4,6,7] define a “locally least-cost” repair using insertions and deletions, and provide algorithms for LL and LR parsers. A locally least-cost repair is a least-cost sequence of deletions and insertions such that one more symbol in the original string will be accepted by the parser. Backhouse [2,3] uses a similar definition. In both cases, the repair algorithms operate by examining a single symbol in the input at any time.


title: An Applicative Compiler for a Parallel Machine

abstract: A compiler for the applicative language HOPE is described. The compiler is itself written in HOPE and generates a machine independent compiler target language, suitable for execution on the parallel reduction machine ALICE. The advantages of writing a compiler in a very high level applicative language are discussed, and the use of program transformation and other techniques to turn the initial 'runnable specification' into a more efficient (if less clear) program are outlined. Extensions to the HOPE language and the compiler which can exploit the parallelism and various execution modes of ALICE are described.


title: Analyzing Exotic Instructions for a Retargetable Code Generator

authors:
Thomas M. Morgan
Lawrence A. Rowe

abstract: Exotic instructions are complex instructions, such as block move, string search, and string edit, which are found on most conventional computers. Recent retargetable code generator and instruction set analysis systems have not dealt with exotic instructions. A method to analyze exotic instructions is presented which provides the information needed by a retargetable code generator. The analysis uses source-to-source transformations to prove the equivalence of high-level language operators to exotic instructions. Examples are presented which illustrate the analysis process.


title: Experience with the Normal Semantic Definition of HAL/S

authors:
Terrence W. Pratt
George D. Maydwell

abstract: HAL/S is a large general purpose real-time programming language somewhat similar to ADA. Its major applications are for embedded real-time systems, in particular for the Space Shuttle on-board computer software and similar applications within NASA. After the language had been in regular use for several years, we were requested by NASA to prepare a formal semantic definition of the language using the method of H-graph semantics. This paper reports on the method and structure of that definition and on experience with its use in finding and correcting errors in the language specification and in the design of implementations for the language.


title: Denotational Semantics as a Specification of Code Generators

abstract: We describe the automatic generation - from the formal denotational semantic specification - of an efficient compiler's code generation phase, producing efficient code for real machines. The method has been succesfully implemented and tested with languages as complex as GEDANKEN!


title: An Efficient Separate Compilation Strategy for Very Large Programs

authors:
Andres Rudmik
Barbara G. Moore

abstract: This paper describes the design of a compiling system that supports the efficient compilation of very large programs. The system consists of front ends for different languages, a common program database to store the intermediate code, and various back ends, optimizers, debuggers and other development tools. The compiling system achieves efficiency of use by minimizing the number of system components that must be invoked when a small change is made in a program.


title: Control Flow Aspects of Semantics Directed Compiling (Summary)

abstract: We focus on the part of a compiler between syntax analysis and code generation. A language is specified by adding semantic rules in a functional notation to the syntax of the language. Starting with a small sublanguage of while statements, the semantics of the statement constructs of C is built up incrementally. Using a small ad hoc code generator, a compiler has automatically been constructed from the semantics. The semantic description is analogous to a syntax directed construction of a flow diagram for a program. In analogy with grammars and parser generators, minimal knowledge of the underlying theory is required.For the control flow aspects of languages, efficient compilers can quickly be generated.


title: Tailoring Testing to a Specific Compiler - Experiences

abstract: The testing of the Univac UCS-Pascal compiler is described. Tests were acquired from various sources, converted from existing tests, and developed in house. Test development and execution using the Univac Test Controller System is illustrated with examples. The experiences gained from this and other compiler testing efforts are described.


title: A Facility for the Downward Execution of a High-Level Language

abstract: This paper presents a method whereby a high-level language can be extended to provide access to all the capabilities of the underlying hardware and operating system of a machine. In essence, it is a facility that allows a user to make special purpose extensions to a language without requiring the compiler to be modified for each extension. Extensions are specified in an assembler-like language that is used at compile time to produce executable code to be combined with compiler-generated code. This facility has been implemented in a systems-programming language and was designed to provide access to facilities not directly available in the language. The way in which the facility was implemented calls for a minimum of user-visible language changes and is well suited for generating code sequences for any language. The facility provides the extension writer access to information available in the high-level language during compilation, permits the selective generation of user-defined code sequences depending on the context in which they are being used, provides for the integration of this code with compiler-generated code, and provides for the generation of user-understandable error messages when an extension is used incorrectly.


title: Experience with a Graham-Glanville style code generator

authors:
Philippe Aigrain
Susan L. Graham
Robert R. Henry
Marshall K. McKusick
Eduardo Pelegrí-Llopart


title: Automatic loop interchange

authors:
John R. Allen
Ken Kennedy

abstract: Parallel and vector machines are becoming increasingly important to many computation intensive applications. Effectively utilizing such architectures, particularly from sequential languages such as Fortran, has demanded increasingly sophisticated compilers. In general, a compiler needs to significantly reorder a program in order to generate code optimal for a specific architecture.Because DO loops typically control the execution of a number of statements, the order in which loops are executed can dramatically affect the performance of a machine on a particular section of code. In particular, loop interchange can often be used to enhance the performance of code on parallel or vector machines.Determining when loops may be safely and profitably interchanged requires a study of the data dependences in the program. This work discusses specific applications of that theory to loop interchange. This theory is described as it has been implemented in PFC (Parallel Fortran Converter) -- a program which attempts to uncover operations in sequential Fortran code that may be safely rewritten as vector operations.


title: Static checking of interprocess communication in ECSP

authors:
Fabrizio Baiardi
Laura Ricci
Marco Vanneschi

abstract: The structure of a compiler for the ECSP language is described. ECSP is a concurrent language extending Hoare's CSP: it supports dynamic communication channels and nested processes. The compilation of ECPS programs is obtained by the composition of several tools of minimal functionalities.A set of static checks on interactions between concurrent processes is described. The checks verify the mutual consistency of the interfaces of processes: an interface is given by a set of input/output channels connecting a process to its partners. It is shown that the amount and the coverage of checks depend on the entities referred to in interprocess communication constructs and that both increase with the adoption of explicit naming.The checks on process interfaces are carried on in several tool of the compiler front-end to achieve machine independence. To support separate compilation, each tool can be applied to a subset of the processes of a program.


title: An efficient implementation of visibility in Ada

abstract: This paper discusses the efficient implementation of Ada's visibility requirements. A scope stack and an unstructured name space are used to facilitate separate compilation and ensure that each Ada declaration takes a constant unit of time. Visibility issues affect practically every aspect of semantic analysis in Ada: declarations, statements, expressions, and separate compilation. The design of the symbol table package is, thus, a critical one. In this paper, I discuss the design goals of the symbol table for the Ada Integrated Environment (AIE) bootstrap compiler front end, and how they were influenced by the Ada language. Since the compiler is being heavily used by the AIE project, we have ample data with which to measure symbol table performance.


title: Sharing code among instances of Ada generics

abstract: This paper describes the aspects of the Ada compiler for the Air Force Ada Integrated Environment (AIE) that are concerned with sharing code among generic instances. Sharing is achieved by forming equivalence classes of generic instances and sharing executable code among members of the class. This approach achieves the required efficiency for embedded applications while minimizing the storage consumed by the executable code of generic instances.


title: Register allocation by priority-based coloring

authors:
Fred C. Chow
John L. Hennessy

abstract: The classic problem of global register allocation is treated in a heuristic and practical manner by adopting the notion of priorities in node-coloring. The assignment of priorities is based on estimates of the benefits that can be derived from allocating individual quantities in registers. Using the priorities, the exponential coloring process can be made to run in linear time. Since the costs involved in register allocation are taken into account, the algorithm does not over-allocate. The algorithm can be parameterized to cater to different fetch characteristics and register configurations among machines. Measurements indicate that the register allocation scheme is effective on a number of target machines. The results confirm that, using priority-based coloring, global register allocation can be performed practically and efficiently.


title: Using dynamic programming to generate optimized code in a Graham-Glanville style code generator

authors:
Thomas W. Christopher
Philip J. Hatcher
Ronald C. Kukuk

abstract: We have performed an investigation of using a dynamic programming to generate optimized code in a Graham-Glanville style code generator We use Earley's algorithm rather than an IR algorithm for parsing in the code generator Not only does the use of Earley's algorithm make the construction of the code generator very easy it allows the selection of optimal code by dynamic programming (using a modification of the technique developed by Lvon) We compare two implementations of this technique to conventional hand-coded code generators using a subset of BASIC as the source language Further we discuss the use of this technique in an experimental C compiler.


authors:
Keith D. Cooper
Ken Kennedy

abstract: article Efficient computation of flow insensitive interprocedural summary information Share on Authors: Keith D. Cooper Rice University, Houston, Texas Rice University, Houston, TexasView Profile , Ken Kennedy Rice University, Houston, Texas Rice University, Houston, TexasView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 19Issue 6June 1984 pp 247–258https://doi.org/10.1145/502949.502898Online:01 June 1984Publication History 97citation347DownloadsMetricsTotal Citations97Total Downloads347Last 12 Months7Last 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 SiteGet Access


title: Automatic generation of peephole optimizations

authors:
Jack W. Davidson
Christopher W. Fraser

abstract: This paper describes a system that automatically generates peephole optimizations. A general peephole optimizer driven by a machine description produces optimizations at compile-compile time for a fast, pattern-directed, compile-time optimizer. They form part of a compiler that simplifies retargeting by substituting peephole optimization for case analysis.


title: Sub-protocol-evaluators for attribute grammars

abstract: This paper presents a new strategy for evaluating attribute grammars, sub-protocol attribute evaluation, and gives an algorithm for constructing sub-protocol-evaluators. Sub-protocol-evaluators can be built for any non-circular attribute grammar; this paper describes how to construct them for absolutely noncircular grammars [4]. Sub-protocol-evaluators are most easily understood as a simple optimization of another evaluator we call the protocol-evaluator. The protocol-evaluator has elements in common with the tree-walk evaluator of Kennedy-Warren [4] and with Nielson's direct evaluator [6]; it can be viewed as a refinement of each of these. Furthermore, the uniform AGs, proposed by Warren [9], and the ordered AGs, proposed by Kastens [3], are both subclasses of grammars for which especially efficient protocol-evaluators can be built.


title: Parallel processing: a smart compiler and a dumb machine

authors:
Joseph A. Fisher
John R. Ellis
John C. Ruttenberg
Alexandru Nicolau

abstract: Multiprocessors and vector machines, the only successful parallel architectures, have coarse-grained parallelism that is hard for compilers to take advantage of. We've developed a new fine-grained parallel architecture and a compiler that together offer order-of-magnitude speedups for ordinary scientific code.


title: Analyzing and compressing assembly code

authors:
Christopher W. Fraser
Eugene W. Myers
Alan L. Wendt

abstract: This paper describes the application of a general data compression algorithm to assembly code. The system is retargetable and generalizes cross-jumping and procedural abstraction. It can be used as a space optimizer that trades time for space, it can turn assembly code into interpretive code, and it can help formalize and automate the traditionally ad hoc design of both real and abstract machines.


title: Attribute coupled grammars

authors:
Harald Ganzinger
Robert Giegerich

abstract: In this paper, attribute grammars are viewed as specifying translations from source language terms into target language terms. The terms are constructed over a hierarchical signature consisting of a semantic and a syntactic part. Attribute grammars are redefined to become morphisms in the category of such signatures, called attribute coupled grammars, such that they come with an associative composition operation. The composition allows for a new kind of modularity in compiler specifications. The paper also discusses properties of the concept with respect to attribute evaluation and application as a tree transformation device.


title: Efficient compilation of lazy evaluation

abstract: This paper describes the principles underlying an efficient implementation of a lazy functional language, compiling to code for ordinary computers. It is based on combinator-like graph reduction: the user defined functions are used as rewrite rules in the graph. Each function is compiled into an instruction sequence for an abstract graph reduction machine, called the G-machine, the code reduces a function application graph to its value. The G-machine instructions are then translated into target code. Speed improvements by almost two orders of magnitude over previous lazy evaluators have been measured; we provide some performance figures.


title: Strongly non-circular attribute grammars and their recursive evaluation

abstract: This paper is devoted to the construction of recursive evaluators for strongly non-circular attribute grammars. This class of attribute grammars is very large and includes every practical example ; testing strong non-circularity can be done in polynomial time. To each synthesized attribute, a function is associated, which takes as parameters a derivation tree and the values of some inherited attributes, and returns the value of that attribute at the root of the tree. These functions are mutually recursive according to the structure of the full parse tree. This method implements a dynamic "evaluation by need", reducing the number of attributes computed to those necessary to get the "semantic value" of the full tree. A Lisp implementation allowing automatic efficient storage management is also presented, together with some applications. Our work is closely related to those of Kennedy and Warren, Saarinen and Katamaya, but our method is more efficient and has a better theoretical basis.


title: Regular right-part attribute grammars

authors:
Richard Jüllig
Frank DeRemer

abstract: article Free Access Share on Regular right-part attribute grammars Authors: Richard K. Jullig Kestrel Institute Kestrel InstituteView Profile , Frank DeRemer MetaWare Inc., University of California, Santa Cruz MetaWare Inc., University of California, Santa CruzView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 19Issue 6June 1984 pp 171–178https://doi.org/10.1145/502949.502891Online:01 June 1984Publication History 10citation259DownloadsMetricsTotal Citations10Total Downloads259Last 12 Months11Last 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: Code generation by coagulation

abstract: This paper describes a new approach to code-generation. The central tenet is that there must be a more intimate coupling between register allocation and instruction selection than exists in present-day technology. This is achieved by generating code in very small regions and gradually coalescing the part of the program that is "compiled".


title: Tree transformation techniques and experiences

authors:
Steven E. Keller
John A. Perkins
Teri F. Payton
S. P. Mardinly

abstract: A formal description technique for describing transformations from one well-defined language to another is introduced. A TT-grammar contains context-free grammars for describing the syntax of both languages. The transformation between the languages is described by a relationship of productions from the grammars. The TT-grammar is supported by an automated tool. SSAGS -- a translator writing system based on attribute grammars -- has been extended to support certain classes of TT-grammars. SSAGS analyzes TT-grammars and automatically generates Ada source programs implementing the transformation specified by the TT-grammar. Experience with two different restricted forms of TT-grammars is described with respect to their practical application. The experience demonstrates the readability, ease of development, and additional verification available through the use of TT-grammars.


title: Peep: an architectural description driven peephole optimizer

abstract: Peep is an architectural description driven peephole optimizer, that is being adapted for use in the Portable Standard Lisp compiler. Tables of optimizable instructions are generated prior to the creation of the compiler from the architectural description of the target machine. Peep then performs global flow analysis on the target machine code and optimizes instructions as defined in the table. This global flow analysis allows optimization across basic blocks of instructions, and the use of tables created at compiler-generation time minimizes the overhead of discovering optimizable instructions.


title: A specification language for one-pass semantic analysis

abstract: A new language is introduced for the specification of semantic analysis of programming languages. The language is based on the concept of one-pass attribute grammars. Various extensions of this basic formalism are incorporated in the language, including disciplined global variables, facilities for symbol processing, and features supporting semantic error detection and recovery. To encourage the writing of declarative specifications the language is nonterminal-oriented, in contrast to the production-oriented languages traditionally used in compiler writing systems.


title: Type checking, separate compilation and reusability

abstract: A strategy for performing type checking on programs built out of separately compiled parts is presented. This strategy is used in a programming environment that allows small components of a software system to be reconfigured in different ways. The strategy works by inferring type schemas for all of the undeclared functions used by a component and then unifying each schema with a program library when a configuration is built.


title: Inline routines in VAXELN Pascal

abstract: This paper describes the implementation of inline procedures and functions inthe VAXELN Pascal compiler. Inline expansion translates the reverse Polish text produced by the parser into an intermediate language like that used in the VAX-11 PL/I and C compilers. The paper gives detailed descriptions of the front end's organization as it relates to inline routines and of the symbol substitutions made during inline expansion. The paper also discusses global optimization and the compiler's treatment of dynamically sized data, which is based on parametric types.


title: Compiler prototyping using formal semantics

abstract: The descriptive techniques of formal semantics can be used for the generation of complete prototype compilers. First, we review the essential characteristics of such semantics implementation systems, and discuss our experience with two existing experimental systems. Then, we show how to derive a complete conventional compiler for a small language from its denotational semantics. The compiler is specified in three phases consisting of a front-end (parser, tree builder, and semantic checker), a translator from syntax trees to prefix code, and a code generator which converts the prefix code into IBM/370 style assembly code. The translator component is obtained by modifying the standard semantics of the language in two steps: first, the semantic domains and the equations are rewritten in a straight forward way to achieve a normal form, and then the auxiliary semantic functions are interpreted as instructions for a prefix code machine. The entire three part specification has been implemented with the help of Paulson's semantics processing system.


title: A portable optimizing compiler for Modula-2

abstract: A portable compiler for the Modula-2 programming language has been implemented with a simple, machine independent optimizer. The front end of the compiler generates a dialect of P-code, and the back end translates the P-code into machine language. The compiler fits well in the Unix environment.The design philosophy of the compiler "best simple". Whenever possible, design decisions were made to favor the simplest alternative that got us most of what we wanted. Benchmark results show that the code quality is comparable to or better than other good compilers.


title: An approach to incremental compilation

abstract: This paper describes an approach to incremental compilation that allows a complete incremental compiler to be generated from a simple language description. This description is in two parts. The first consists of an abstract syntax annotated with a powerful language for specifying the local semantics. The second consists of separate specifications detailing the uses of symbols, data types and expressions in the language. The approach operates in two stages. The first stage builds a local model of the semantics. The second propagates local changes into a global semantics. This approach has been used as part of the PECAN system for generating program development environments at Brown University.


abstract: article Free Access Share on Engineering a high-capacity Pascal compiler for high performance Author: David C. Robbins GTE Communication Systems, Inc., Phoenix, Arizona GTE Communication Systems, Inc., Phoenix, ArizonaView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 19Issue 6June 1984 pp 300–309https://doi.org/10.1145/502949.502904Published:01 June 1984Publication History 0citation185DownloadsMetricsTotal Citations0Total Downloads185Last 12 Months21Last 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 multi-language compiler system with automatically generated codegenerators

authors:
Uwe Schmidt
Reinhard Völler

abstract: The compiler system described in this paper may be regarded as a specialization of the classical UNCOL-problem [Con58].It has been developed at the University of Kiel and is currently being used by Norsk-Data-Oietz Computer Systems, M0Ihelm, FRG.The system results from the need to lower maintenance costs and to achieve a high degree of portability of the compilers for the languages supported.The source languages are compiled into the common intermediate language CAT [V5183], which is then translated by code generators into various machine languages [Sch83].The code generators are automatically generated from denotational specifications.The system has been designed to cover a wide range of PASCAL-and FORTRANlike languages and to generate code for von-Neumann-type processors.Up to now BASIC, FORTRAN-77, COBOL-74 and PASCAL have been considered as source languages with PASCAL and BASIC front ends fully implemented and a FORTRAN front end under construction, Codegenerators exist for the DIETZ-621/X3, a byte oriented minicomputer, for the National NS 16000 microprocessor and the Norsk-Data ND100.The system is used at Norsk-Data-Dietz for CAD and systems programming applications.


title: Incremental compilation in Magpie

authors:
Mayer D. Schwartz
Norman M. Delisle
Vimal S. Begwani

abstract: Magpie is an interactive, integrate programming environment that supports the development of Pascal programs a powerful, single-user workstation. Incremental compilation techniques are used to provide quick feedback on static errors and to ensure that a program is always ready for execution even while it is being edited. Magpie performs syntax and static semantic analysis with the unit of incrementality of a single character. Magpie uses incremental compilation to achieve performance levels that allow Pascal to be used interactively and as its own debugging language.


title: A Fortran compiler for the FPS-164 scientific computer


title: A semantic prototyping system

abstract: We have written a set of computer programs for testing and exercising programming language specifications given in the style of denotational semantics. The system is built largely in Scheme 84, a dialect of LISP that serves as an efficient lambda-calculus interpreter. The system consists of:• a syntax-directed transducer, which embodies the principle of compositionality,• a type checker, which is extremely useful in debugging semantic definitions, and• an interface to the yacc parser-generator, which allows the system to use concrete syntax rather than the often cumbersome abstract syntax for its programs.In this paper, we discuss the design of the system, its implementation, and discuss its use.


title: Incremental data flow analysis in a structured program editor

abstract: For many years, the generally accepted methods for solving global data flow analysis problems (GDFAPs) have relied on the bit vector paradigm [Alle 70] [Kenn 81]. In these algorithms, the information for each variable is represented as a position in a bit vector. These vectors are propagated from node to node during the analysis of the program.This paper investigates a different paradigm for solving GDFAPs. In this strategy, the data flow solution for each variable is computed independently. A new algorithm for solving some GDFAPs is presented here. While it is expected that this algorithm will run slower in the batch compiling environment, there are conditions under which this algorithm can be expected to be superior to those in the bit vector class.


title: A practical arbitrary look-ahead LR parsing technique

authors:
Manuel E. Bermudez
Karl M. Schimpf

abstract: We present a practical technique that provides an LR (0) parser with either fixed or arbitrary look-ahead. The construction algorithm is based on certain paths in the LR (0) state diagram, which must be restricted to a maximum length m. The technique determines the amount of look-ahead required, and the user is spared the task of guessing it. Instead, the user provides m. In situations where single symbol look-ahead is sufficient, the corresponding grammar class (called LAR (m )) is identical to the NQLALR (1) class. For practical grammars that require arbitrary look-ahead, the storage requirements typically do not exceed an amount linear in the size of the corresponding LR (0) parser. The technique is shown to work for a practical programming language grammar, and has been used to solve particular cases of the PL/1 keyword problem.


title: Optimal chaining in expression trees

authors:
David Bernstein
Haran Boral
Ron Y. Pinter

abstract: Chaining is the ability to pipeline two or more vector instructions on Cray-1 like machines. We show how to optimally use this feature to compute (vector) expression trees, in the context of automatic code-generation. We present a linear-time scheduling algorithm for finding an optimal order of evaluation for a machine with a bounded number of registers.


title: Implementing RUSSELL

authors:
Hans-Juergen Boehm
Alan J. Demers

abstract: We have completed an implementation of the Russell programming language [Don 85]. This effort has been very helpful in the evaluation of the original language design. It has also served to pinpoint the difficulties in implementing languages with type systems as general as that of Russell.


title: Interprocedural dependence analysis and parallelization

authors:
Michael G. Burke
Ron Cytron


title: Interprocedural constant propagation

authors:
David Callahan
Keith D. Cooper
Ken Kennedy
Linda Torczon

abstract: In a compiling system that attempts to improve code for a whole program by optimizing across procedures, the compiler can generate better code for a specific procedure if it knows which variables will have constant values, and what those values will be, when the procedure is invoked. This paper presents a general algorithm for determining for each procedure in a given program the set of inputs that will have known constant values at run time. The precision of the answers provided by this method are dependent on the precision of the local analysis of individual procedures in the program. Since the algorithm is intended for use in a sophisticated software development environment in which local analysis would be provided by the source editor, the quality of the answers will depend on the amount of work the editor performs. Several reasonable strategies for local analysis with different levels of complexity and precision are suggested and the results of a prototype implementation in a vectorizing Fortran compiler are presented.


title: Interprocedural optimization: eliminating unnecessary recompilation

authors:
Keith D. Cooper
Ken Kennedy
Linda Torczon

abstract: While efficient new algorithms for interprocedural data flow analysis have made these techniques practical for use in production compilation systems, a new problem has arisen: collecting and using interprocedural information in a compiler introduces subtle dependences among the procedures of a program. If the compiler depends on interprocedural information to optimize a given module, a subsequent editing change to another module in the program may change the interprocedural information and necessitate recompilation. To avoid having to recompile every module in a program in response to a single editing change to one module, we must develop techniques to more precisely determine which compilations have actually been invalidated by a change to the program's source. This paper presents a general recompilation test to determine which procedures must be compiled in response to a series of editing changes. Three different implementation strategies, which demonstrate the fundamental tradeoff between the cost of analysis and the precision of the resulting test, are also discussed.


title: A retargetable instruction reorganizer

abstract: Extant peephole optimizers can perform many optimizations that are handled by higher-level optimizers. This paper describes a retargetable instruction reorganizer that performs targeting and evaluation order determination by applying a well known algorithm for optimal code generation for expressions to object code. By applying the algorithm to object code after code generation and optimization, a phase ordering problem often encountered by higher-level optimizers is avoided. It minimizes the number of registers and temporaries required to compile expressions by rearranging machine instructions. For some machines, this can result in smaller and faster programs. By generalizing its operation, the reorganizer can also be used to reorder instructions to avoid delays in pipelined machines. For one pipelined machine, it has provided a 5 to 10 percent improvement in the execution speed of benchmark programs.


title: Automatic generation of fixed-point-finding evaluators for circular, but well-defined, attribute grammars

abstract: In the traditional formulation of attribute grammars (AGs) circularities are not allowed, that is, no attribute-instance in any derivation tree may be defined in terms of itself. Elsewhere in mathematics and computing, though, circular (or recursive) definitions are commonplace, and even essential. Given appropriate constraints, recursive definitions are well-founded, and the least fixed-points they denote are computable. This is also the case for circular AGs.


title: Integrating code generation and optimization

authors:
Christopher W. Fraser
Alan L. Wendt

abstract: This paper describes a compiler with a code generator and machine-directed peephole optimizer that are tightly integrated. Both functions are performed by a single rule-based rewriting system that matches and replaces patterns. This organization helps make the compiler simple, fast, and retargetable. It also corrects certain phase-ordering problems.


title: Efficient instruction scheduling for a pipelined architecture

authors:
Phillip B. Gibbons
Steven S. Muchnick

abstract: As part of an effort to develop an optimizing compiler for a pipelined architecture, a code reorganization algorithm has been developed that significantly reduces the number of runtime pipeline interlocks. In a pass after code generation, the algorithm uses a dag representation to heuristically schedule the instructions in each basic block.


title: Compilation for a high-performance systolic array

authors:
Thomas R. Gross
Monica S. Lam

abstract: We report on a compiler for Warp, a high-performance systolic array developed at Carnegie Mellon. This compiler enhances the usefulness of Warp significantly and allows application programmers to code substantial algorithms.


title: Efficient compilation of linear recursive functions into object level loops

authors:
Peter G. Harrison
Hessam Khoshnevisan

abstract: Whilst widely recognised as an excellent means for solving problems and for designing software, functional programming languages have suffered from their inefficient implementations on conventional computers. A route to improved runtime performance is to transform recursively defined functions into programs which execute more quickly and/or consume less space. We derive equivalent imperative programming language loops for a large class of linear recursive functions of which the tail-recursive functions form a very small subset. We first identify a small set of primitive function defining expressions for which we determine the corresponding loop-expressions. We then determine the loop-expressions for linear functions defined by any expressions which are formed from those primitives. In this way, a very general class of linear functions can be transformed automatically into loops in the parsing phase of a compiler, since the parser has in any case to determine the hierarchical structure of function definitions. Further transformation may involve specific properties of particular defining expressions, and adopt previous schemes. In addition, equivalent linear functions can be found for many non-linear ones which can therefore also be transformed into loops.


title: Efficient incremental evaluation of aggregate values in attribute grammars

authors:
Roger Hoover
Tim Teitelbaum

abstract: Aggregate valued attributes, which store collections of keyed elements, are required in attribute grammars to communicate information from multiple definition sites to multiple use locations. For syntax directed editors and incremental compilers, symbol tables are represented as aggregate values. We present efficient algorithms for incrementally maintaining these aggregate values and give an incremental evaluation algorithm that restricts attribute propagation to attributes dependent only upon information within the aggregate value that has changed.


title: Unifying view of recent LALR(1) lookahead set algorithms

abstract: Since the introduction of LALR parsing, several algorithms have been presented for the computation of the lookahead sets needed to produce an LALR parser. The algorithm in Aho and Ullman[1] has perhaps received the widest exposure. The recent algorithms by DeRemer and Pennello[2] and Park, Choe, and Chang[4] are the most efficient.


title: Data flow analysis for 'intractable' system software

abstract: We describe, and give experience with, a new method of intraprocedural data flow analysis on reducible flow-graphs[9]. The method is advantageous in imbedded applications where the added value of improved performance justifies substantial optimization effort, but extremely powerful data flow analysis is required due to the code profile.


title: Effectiveness of a machine-level, global optimizer

authors:
Mark Scott Johnson
Terrence C. Miller

abstract: We present an overview of the design of a machine-code-level, global (intraprocedural) optimizer that supports several front-ends producing code for the Hewlett-Packard Precision Architecture family of machines. The basic optimization strategy is described, including information about the division of responsibilities between various components of the compiler. Optimization algorithms are described, including a discussion of the dataflow information they require. Measurements showing the collective and individual effects of various optimizer components are presented.


title: Generation of run-time environments

abstract: Attribute grammars have been used for many years for automated compiler construction. Attribute grammars support the description of semantic analysis, code generation and some code optimization in a formal declarative style. Other tools support the automation of lexical analysis and parsing. However, there is one large part of compiler construction that is missing from our toolkit: run-time environments. This paper introduces an extension of attribute grammars that supports the generation of run-time environments. The extension also supports the generation of interpreters, symbolic debugging tools, and other execution-time facilities.


title: Discovering machine-specific code improvements

abstract: I have designed and built a compiler construction tool that automates much of the case analysis necessary to exploit special purpose instructions on a target machine. Given a suitable description of the target machine, my analysis identifies instruction sequences that are equivalent to single instructions. During code generation, these equivalences can be used to avoid inefficient instruction sequences in favor of more efficient instructions.I present a working prototype of the instruction set analyzer needed in the framework outlined by [Giegerich 83]. In contrast to the work presented in [Davidson and Fraser 80, 84], I analyze machine descriptions during compiler construction, rather than analyzing instruction sequences that occur during code generation. [R Kessler 84] describes a system which analyzes machine descriptions during compiler construction, but which which is limited to discovering instructions that are equivalent to instruction sequences of length 2. The techniques presented here can identify instruction sequences of arbitrary length that are equivalent to single instructions.I have applied this analysis to the descriptions of two machines, and used the results to replace hand-written case analysis routines in an otherwise table-driven code generator [Henry 84].


title: EPIC - a retargetable, highly optimizing Lisp compiler

authors:
Robert R. Kessler
John C. Peterson
Harold Carr
Gerald P. Duggan
J. Knell
Jed J. Krohnfeldt

abstract: The Experimental Portable Standard Lisp Compiler (EPIC) is a compiler testbed for experimentation with, and development of, Lisp compilation strategies. EPIC uses an architectural description of the target machine to increase portability, and performs extensive optimizations in the form of source-to-source transformations, register allocation, and peephole optimization. It introduces machine-specific instructions early to enable machine-specific optimizations in the initial passes. EPIC produces better code than the original Portable Standard Lisp compiler, has an improved portability model, and is easier to maintain.


title: ORBIT: an optimizing compiler for scheme

authors:
David A. Kranz
Richard Kelsey
Jonathan Rees
Paul Hudak
James Philbin

abstract: In this paper we describe an optimizing compiler for Scheme [3, 131 called Orbit that incorporates our experience with an earlier Scheme compiler called TC [IO, II], together with some ideas from Steele’s Rabbit compiler [14]. The three main design goals have been correctness, generating very efficient compiled code, and portability. In spirit, Orbit is similar to the Rabbit compiler in that it depends on a translation of source code into


title: Register allocation in the SPUR Lisp compiler

authors:
James R. Larus
Paul N. Hilfinger

abstract: Register allocation is an important component of most compilers, particularly those for RISC machines. The SPUR Lisp compiler uses a sophisticated, graph-coloring algorithm developed by Fredrick Chow [Chow84]. This paper describes the algorithm and the techniques used to implement it efficiently and evaluates its performance on several large programs. The allocator successfully assigned most temporaries and local variables to registers in a wide variety of functions. Its execution cost is moderate.


title: Static evaluation of functional programs

abstract: Static evaluation underlies essentially all techniques for a priori semantic program manipulation, i.e. those that stop short of fully general execution. Included are such activities as type checking, partial evaluation, and, ultimately, optimized compilation.


title: Very fast LR parsing

abstract: LR parsers can be made to run 6 to 10 times as fast as the best table-interpretive LR parsers. The resulting parse time is negligible compared to the time required by the remainder of a typical compiler containing the parser.


title: A globalizing transformation for attribute grammars

authors:
Kari-Jouko Räihä
Jorma Tarhio

abstract: A transformation is presented for replacing conventional local attribute references in attribute grammars by upward remote references. The purpose of the transformation is to enhance readability of the grammar and to facilitate easy storage optimization.


title: Transformations of denotational semantics in semantics directed compiler generation

abstract: In semantics-directed compiler generation one is faced with the problem of how to translate a source semantic definition of a programming language into on equivalent target semantics closer to an implementation. Most of the existing works solve this problem in a non constructive way : a target semantics is exhibited first and then only proved correct against the source. We try to show that target semantics can be derived from source semantics in a constructive way and so that some correctness ideas are automatically preserved. The framework is denotational semantics.


title: Compile-time partitioning and scheduling of parallel programs

authors:
Vivek Sarkar
John L. Hennessy

abstract: Partitioning and scheduling techniques are necessary to implement parallel languages on multiprocessors. Multiprocessor performance is maximized when parallelism between tasks is optimally traded off with communication and synchronization overhead. We present compile-time partitioning and scheduling techniques to achieve this trade-off.


title: Direct parallelization of call statements

authors:
Rémi Triolet
François Irigoin
Paul Feautrier

abstract: Asynchronous CALL statements are necessary in order to use more than one processor in current multiprocessors. Detecting CALL statements that may be executed in parallel is one way to fill this need. This approach requires accurate approximations of called procedure effects. This is achieved by using new objects called Region and Execution Context. An algorithm to find asynchronous CALL statements is given. It involves a new dependence test to compute data dependence graphs, which provides better results than previous ones even when no CALL statements are involved. This method has been implemented in Parafrase and preliminary results are encouraging.


title: Global register allocation at link time

abstract: In previous work in global register allocation, the compiler colors a conflict graph constructed from liveness dataflow information, in order to allocate the same register to many variables that are not simultaneously live. If two procedures are in separately compiled modules, however, the compiler must do this allocation separately for each procedure. As a result, the two procedures might use different registers for the same global, or the same register for different locals.


title: A generator for language-specific debugging systems

authors:
Rolf Bahlke
Bernhard Moritz
Gregor Snelting

abstract: We present a system which generates interactive high-level debugging systems from formal language definitions. The language definer has to specify a denotational semantics augmented with a formal description of the language specific debugging facilities. The generated debugger offers the traditional features such as tracing programs, setting breakpoints, displaying variables etc; interaction with the user is always on language level rather than on machine level. The concept has been implemented as part of the PSG-Programming System Generator, and has successfully been used to generate debuggers for Pascal and Modula-2. The core of the implementation consists of an interpreter for a functional language, which has been extended with the language-independent mechanisms needed in order to allow interaction with the user during program execution.


title: Efficient interpretation of Prolog programs

abstract: The paper focuses on three ideas for solving problems with writing interpreters for the logic programming language Prolog in Prolog and how to combine these ideas to an interpreter for Prolog which is both simple and efficient. The resulting interpreter system can be incorporated into a Prolog based on Warren's Abstract Machine and built mostly from existing parts of it. The interpreter has been implemented and is used in a Prolog system developed at Uppsala University.


title: Constructive real interpretation of numerical programs

abstract: We explore the feasibility of providing exact real arithmetic for use in conventional numerical programs. We have built a prototype interpreter which replaces floating point operations with operations on constructive real numbers in the execution of conventional Fortran programs. Such a facility makes it unnecessary to concern oneself with issues of numerical stability in the solution of small problems. It also provides a useful tool for the development of larger numerical programs.We discuss the computability and algorithmic issues involved in the design of the interpreter, as well as some preliminary experiences and performance measurements.


title: Selective interpretation as a technique for debugging computationally intensive programs

authors:
Benjamin B. Chase
Robert T. Hood

abstract: As part of Rice University's project to build a programming environment for scientific software, we have built a facility for program execution that solves some of the problems inherent in debugging large, computationally intensive programs. By their very nature such programs do not lend themselves to full-scale interpretation. In moderation however, interpretation can be extremely useful during the debugging process. In addition to discussing the particular benefits that we expect from interpretation, this paper addresses how interpretive techniques can be effectively used in conjunction with the execution of compiled code. The same implementation technique that permits interpretation to be incorporated as part of execution will also permit the execution facility to be used for debugging parallel programs running on a remote machine.


title: The JADE interpreter: a RISC interpreter for syntax directed editing

abstract: This paper describes key features of an interpreter for a language-based editor. The interpreter unites in a RISC framework features which have been used in other domains. The paper examines each feature's integration into the RISC framework.


title: Design of an interpretive environment for Turing

authors:
James R. Cordy
T. C. Nicholas Graham

abstract: This paper presents the design of an interpreter structure for modern programming languages such as Turing and Modula II that is modular and highly orthogonal while providing maximal flexibility and efficiency in implementation. At the outermost level, the structure consists of a front end, responsible for interaction with the user, and a back end, responsible for execution. The two are linked by a single database consisting of the tokenized statements of the user program. Interfaces between the major modules of each part are defined in such a way as to maximize reusability, and each interface can service a range of plug-compatible modules implementing radically different semantics. The design accommodates a wide spectrum of interpreter types ranging from batch-oriented compiler-simulators to statement-by-statement interactive execution, and provides for a range of program editing tools from simple line editors through to modern language-directed programming environments. It has served as the basis for several interpretive systems including the production Turing interpreter, the Turing Programming Environment, and the Turing Tool software maintenance tool.


title: Memory allocation and higher-order functions

abstract: This paper presents a constant-time marking-collecting algorithm to efficiently implement recursion with a general heap memory rather than with a vectorial stack, in a context of frequent captures of continuations. It has been seen to reduce the 80% garbage collection overhead to less than 5% on average.The algorithm has been built into a virtual machine to efficiently implement at the assembly level the Actor language PLASMA, an Actor-oriented version of PROLOG and a variant of SCHEME, currently in use on 8086, 68000 and Vax.The rationale to use the heap memory is that continuations are available via a single pointer in a unified memory and can be shared optimally when recurrently captured, which is simply impossible using a strategy based on stack recopy. Further, non-captured continuations can be incrementally garbage collected on the fly.Part I describes the elementary recursive instructions of the virtual machine. Part II presents and proves the marking-collecting strategy. Part III safely generalizes the transformation "call + return = branch" in a way compatible with the possible capture of the current continuation. An appendix relates its integration in the Virtual Scheme Machine supporting Scheme 84.


title: Cint: a RISC interpreter for the C programming language

authors:
Jack W. Davidson
Joseph V. Gresh

abstract: Cint is an interpretation system for the C programming language. Like most interpretation systems, it provides "load and go" type execution as well as enhanced debugging and performance analysis tools. Cint consists of two phases--a translator and an interpreter. The translator compiles the source program into code for a virtual machine. The interpreter then loads and executes this code. While providing services similar to traditional interpreters, Cint differs from them in two important ways. First, the virtual machine languages used by many interpreters are quite large; machines with 100 to 200 operations are common. In contrast, Cint's virtual machine has only 63 operations. Second, to achieve acceptable execution speeds, interpreters are often implemented in the assembly language of the host machine. Cint, however, is written entirely in C and is therefore portable. In fact, it has been transported to four machines without modification. Despite the compact size of the virtual machine language and the high-level language implementation, Cint's execution speed is comparable to that of other interpreters. This paper describes the design of the virtual machine, the implementation of the interpreter, and the performance of the system.


title: Distributed garbage collection

authors:
J. Dana Eckart
Richard J. LeBlanc

abstract: There are two basic approachs to the problem of storage reclamation, process- and processor-based, named for the view point used to recognize when a particular piece of storage can be reclaimed. Examples of the processor approach include mark/sweep and copying algorithms and their variants, while reference counting schemes use a process view of the collection. It is argued that the process approach is better suited for distributed computation where links between dynamically allocated objects may cross processor boundaries. In addition, the process approach allows the heap to be more conveniently shared with other processes in those cases when different processes might not have their own virtual address spaces. A new algorithm using the process approach is given. Its space requirement per object is better than that for reference counting. In addition, a restricted form of pointer replacement is supported which allows circular structures so constructed to be properly collected.


title: An eductive interpreter for Lucid

authors:
Antony A. Faustini
William W. Wadge


title: Parallelism, persistence and meta-cleanliness in the symmetric Lisp interpreter

authors:
David Gelernter
Suresh Jagannathan
Thomas London

abstract: Symmetric Lisp is a programming language designed around first-class environments, where an environment is a dictionary that associates names with definitions or values. In this paper we describe the logical structure of the Symmetric Lisp interpreter. In other interpreted languages, the interpreter is a virtual machine that evaluates user input on the basis of its own internal state. The Symmetric Lisp interpreter, on the other hand, is a simple finite-state machine with no internal state. Its role is to attach user input to whatever environment the user has specified; such environments are transparent objects created by, maintained by and fully accessible to the user. The interpreter's semantics are secondary to the semantics of environments in Symmetric Lisp: it is the environment-object to which an expression is attached, not the interpreter, that controls the evaluation of expressions.This arrangement has several consequences. Because environments in Symmetric Lisp are governed by a parallel evaluation rule, the Symmetric Lisp interpreter is a parallel interpreter. A Symmetric Lisp environment evaluates to another environment; a session with the interpreter therefore yields a well-defined environment object as its result. Users are free to write routines that manage these interpreter-created objects - routines that list the elements of a namespace, coalesce environments, maintain multiple name definitions and so on precisely because environment objects may be freely inspected and manipulated. Because a named environment may contain other named environments as elements, interpreter-created objects may be regarded as hierarchical file systems. Because of the parallel evaluation semantics of environments, the interpreter is well-suited as an interface to a concurrent, language-based computer system that uses Symmetric Lisp as its base language. We argue that - in short - a basic semantic simplification in Symmetric Lisp promises a correspondingly basic increase in power at the user-interpreter interface.


title: Interpreting ABF - a language for document construction

authors:
Henry Harr
Martha W. Evens
James Sprowl

abstract: This paper describes an interpreter for ABF, a language for constructing legal documents. The ABF language defines both commands to develop documents and commands to manipulate those documents. The language has typical programming constructs for sequence, selection, and repetition but also allows the user other capabilities to aid in document construction; the user can modify the program while it is running (change the document while it is being processed), type the variables during the initial processing of a document, and then change the type during later processing, enter commands that require a change of context during the processing of a document, output a document with variables still undefined. A document is constructed using conditional and repeat statements and incorporation of other documents by reference. Data types include documents, strings, numbers, dollar amounts and logical values. Arrays can be formed for all types except documents. There are three forms of subprograms: documents can be incorporated by reference in other documents at any point at which a variable name is permitted; rules (subprocedures) for computing values can be attached to any variable; and alternate questions can be attached to variables in a similar manner. The ABF system queries the user for any values needed to complete a document; questions are generated from variable names.


title: A block-and-actions generator as an alternative to a simulator for collecting architecture measurements

authors:
Miquel Huguet
Tomás Lang
Yuval Tamir

abstract: To design a new processor or to modify an existing one, designers need to gather data to estimate the influence of specific architecture features on the performance of the proposed machine (PM). To obtain this data, it is necessary to measure on an existing machine (EM) the dynamic behavior of typical programs. Traditionally, simulators have been used to obtain measurements for PMs. Since several hundred EM instructions are required to decode, interpret, and measure each simulated (PM) instruction, the simulation time of typical programs is prohibitively large. Thus, designers tend to simulate only small programs and the results obtained might not be representative of a real system behavior. In this paper we present an alternative tool for collecting architecture measurements: the Block-and-Actions Generator (BKGEN). BKGEN produces a version of the program being measured which is directly executable by the EM. This executable version is obtained directly with the EM compiler or with the PM compiler and a assembly-to-assembly translator. The choice between these alternatives depends on the EM and PM compiler technology and the type of measurements to be obtained. BKGEN also collects the PM events to be measured (called actions). Each EM block of instructions is associated with a PM block of actions so that when the program is executed, it collects the measurements associated with the PM. The main advantage of BKGEN is that the execution time is substantially reduced compared to the execution time of a simulator while collecting similar data. Thus, large typical programs (compilers, assemblers, word processors, ...) can be used by the designer to obtain meaningful measurements.


title: GL-a denotational testbed with continuations and partial continuations as first-class objects

abstract: In this paper we describe GL, a language designed to support interactive experimentation with denotational semantics of programming languages, and the novel features of its interpreter. GL is an expressional language that might best be described as an implementation of lambda calculus augmented with several useful basic data types including 1-values.A unique aspect of the GL environment is that it presents a visible, user-accessible implementation of the continuation semantics of GL. The user is expected to understand a denotational definition of GL, and to interact with the system in terms of that definition. In particular, if a computation is temporarily halted the expression continuation extant at that point can be interactively captured and later applied to other values and stores. The implementation of this feature is via a pair of routines called setjmpup and longjmpup that provide what might be called a partial continuation facility. A partial continuation is a function over stores or store/value pairs that represents execution of a partially executed program from its current state to some later state possibly before its half state. The semantics of partial continuations is interesting, and an extension of GL is presented that contains continuations and partial continuations as first-class objects.The GL environment is fairly complete; it has an experimental polymorphic type inference mechanism that supports self-application and report likely sources of user error in a robust manner, and it has a flexible breakpoint and trace facility that permits program execution to be observed and controlled at a variety of levels of granularity. Moreover, it has been used successfully to teach a graduate course in Theory of Programming Languages.


title: Incremental re-execution of programs

authors:
Raghu Karinthi
Mark D. Weiser


title: CCAL: An interpreted language for experimentation in concurrent control

authors:
Phil Kearns
Chris Cipriani
Mitzi Freeman

abstract: Concurrent Control Abstraction Language, CCAL, is an interpreted language which provides no particular control regime to the user. CCAL instead supports five primitive operations which manipulate an abstract model of inter-procedural control. This model is intrinsically concurrent, and the user is allowed to construct high-level concurrent control operations from the primitives (hence, control abstraction). The primary use of CCAL is as a vehicle by which rapid prototyping of application specific control forms may be done and as a tool for the construction and evaluation of novel control forms, especially control forms for highly concurrent and distributed systems. The CCAL interpreter is implemented as a distributed program on a network of Vaxen and Sun-3 workstations under 4.2bsd and 4.3bsd Unix1. CCAL programs appear as multi-process programs in a shared memory system. Both true and apparent concurrency are possible. This paper describes the control abstraction facilities offered by the CCAL interpreter, its use, and implementation strategies in the distributed environment.


title: TOOLS: a unifying approach to object-oriented language interpretation

authors:
Kai Koskimies
Jukka Paakki

abstract: The object-oriented paradigm is applied to the interpreting of programming languages. An intermediate representation of a program is created as a collection of objects representing various entities in the conceptual world of the source language. These objects cover both the static and the dynamic aspects of a program. As a major advantage of this approach, issues that are traditionally handled by very different techniques (like symbol table management and the generation and execution of intermediate code) can be treated in a unified manner. The specification language of an interpreter generator based on these principles is described.


title: Implementation of a high-speed Prolog interpreter


title: Incremental incrementally compacting garbage collection

authors:
Bernard Lang
Francis Dupont


title: Mimic: a fast system/370 simulator

abstract: Software simulation of one computer on another tends to be slow. Traditional simulators typically execute about 100 instructions on the host machine per instruction simulated. Newer simulators reduce the expansion factor to about 10, by saving and reusing translations of individual instructions. This paper describes an experimental simulator which takes the progression one step further, translating groups of instructions as a unit. This approach, combined with flow analysis, reduces the expansion factor to about 4. The new simulator simulates System/370 on a RISC, namely the IBM RT PC.


title: Managing stack frames in Smalltalk


title: Enhancement through extension: the extension interpreter

authors:
David Notkin
William G. Griswold

abstract: The ability to extend programs dynamically has clear advantages. However, providing efficient yet sufficiently flexible support for such capabilities system-wide presents significant challenges. We describe a design and implementation of an extension mechanism that depends heavily on interpretive techniques, including call arbitration, dynamic linking, and multilanguage extensions. We discuss these mechanisms in the context of our Extension Interpreter, which embodies our ideas and provides a framework for discussing the efficiency and generality of the implementation. Our current implementation runs under BSD UNIX 4.2 and 4.3 on VAXes and SUN workstations. Extensions can be written in both C and in Icon, demonstrating our ability to address problems both of compiled and interpreted languages.


title: A recursive interpreter for the Icon programming language

authors:
Janalee O'Bagy
Ralph E. Griswold

abstract: The implementation of the Icon programming language is more interesting and difficult than the implementation of many other programming languages because an expression in Icon can generate a sequence of results. The implementation therefore must support control backtracking in expression evaluation. There also are several novel control structures related to generators. Because expression evaluation is limited lexically, a full coroutine mechanism is not needed and expression evaluation can be handled in a stack-like fashion.The implementation of Icon consists of a virtual machine with a stack-based architecture and an interpreter that executes the virtual machine instructions. There have been several different interpreters for Icon's virtual machine. This paper describes a new approach in which the interpreter is called recursively whenever the context for expression evaluation changes. This recursive interpreter has the advantage of being conceptually clear and flexible without sacrificing efficiency.


title: A Fortran 77 interpreter for mutation analysis

authors:
A. Jefferson Offutt
K. N. King


title: Two-level hybrid interpreter/native code execution for combined space-time program efficiency

abstract: A two-level programming model permits the applications programmer to write programs that benefit both from the code density of interpreted virtual machines and from the speed of native code execution. A well-defined boundary between the native code and the virtual machine facilitates the development of translators to be used at both levels.


title: The Illinois functional programming interpreter


title: Automatic design and implementation of language data types

authors:
Stan Shebs
Robert R. Kessler


title: DI: an interactive debugging interpreter for applicative languages

authors:
Stephen K. Skedzielewski
Robert Kim Yates
R. R. Oldehoeft

abstract: The DI interpreter is both a debugger and interpreter of SISAL programs. Its use as a program interpreter is only a small part of its role; it is designed to be a tool for studying compilation techniques for applicative languages. DI interprets dataflow graphs expressed in the IF1 and IF2 languages, and is heavily instrumented to report the activity of dynamic storage activity, reference counting, copying and updating of structured data values. It also aids the SISAL language evaluation by providing an interim execution vehicle for SISAL programs. DI provides determinate, sequential interpretation of graph nodes for sequential and parallel operations in a canonical order. As a debugging aid, DI allows tracing, breakpointing, and interactive display of program data values. DI handles creation of SISAL and IF1 error values for each data type and propagates them according to a well-defined algebra. We have begun to implement IF1 optimizers and have measured the improvements with DI.


title: The type inference and coercion facilities in the scratchpad II interpreter

authors:
Robert S. Sutor
Richard D. Jenks

abstract: The Scratchpad II system is an abstract datatype programming language, a compiler for the language, a library of packages of polymorphic functions and parametrized abstract datatypes, and an interpreter that provides sophisticated type inference and coercion facilities. Although originally designed for the implementation of symbolic mathematical algorithms, Scratchpad II is a general purpose programming language. This paper discusses aspects of the implementation of the interpreter and how it attempts to provide a user friendly and relatively weakly typed front end for the strongly typed programming language.


title: Efficient interpretation of synchronizable series expressions

abstract: The benefits of programming in a functional style are well known. For example, algorithms which are expressed as compositions of functions operating on series/vectors/streams of data elements are much easier to understand and modify than equivalent algorithms expressed as loops. Unfortunately, many programmers hesitate to use series expressions because they are typically implemented very inefficiently-the prime source of inefficiency being the creation of intermediate series objects.A restricted class of series expressions, obviously synchronizable series expressions, is defined which can be evaluated very efficiently because they do not require the creation of any intermediate series objects. A Common Lisp macro package has been implemented which supports obviously synchronizable series expressions. Using this macro package, programmers can obtain the advantages of expressing computations as series expressions without incurring any runtime overhead. Obviously synchronizable series expressions could be straightforwardly supported in any programming language.


title: Optimal Loop Parallelization

authors:
Alexander Aiken
Alexandru Nicolau

abstract: Article Free Access Share on Optimal loop parallelization Authors: A. Aiken Cornell Univ., Itaca, NY Cornell Univ., Itaca, NYView Profile , A. Nicolau Cornell Univ., Ithaca, NY Cornell Univ., Ithaca, NYView Profile Authors Info & Claims PLDI '88: Proceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementationJune 1988Pages 308–317https://doi.org/10.1145/53990.54021Published:01 June 1988Publication History 190citation1,422DownloadsMetricsTotal Citations190Total Downloads1,422Last 12 Months97Last 6 weeks11 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 C for Vectorization, Parallelization, and Inline Expansion

authors:
Randy Allen
Steve Johnson

abstract: Practical implementations of real languages are often an excellent way of testing the applicability of theoretical principles. Many stresses and strains arise from fitting practicalities, such as performance and standard compatibility, to theoretical models and methods. These stresses and strains are valuable sources of new research and insight, as well as an oft-needed check on the egos of theoreticians.


title: Design and Implementation of the UW Illustrated Compiler

authors:
Kristy Andrews
Robert R. Henry
Wayne K. Yamamoto

abstract: We have implemented an illustrated compiler for a simple block structured language. The compiler graphically displays its control and data structures, and so gives its viewers an intuitive understanding of compiler organization and operation. The illustrations were planned by hand and display information naturally and concisely.


title: Real-Time Concurrent Collection on Stock Multiprocessors

authors:
Andrew W. Appel
John R. Ellis
Kai Li

abstract: We've designed and implemented a copying garbage-collection algorithm that is efficient, real-time, concurrent, runs on commercial uniprocessors and shared-memory multiprocessors, and requires no change to compilers. The algorithm uses standard virtual-memory hardware to detect references to “from space” objects and to synchronize the collector and mutator threads. We've implemented and measured a prototype running on SRC's 5-processor Firefly. It will be straightforward to merge our techniques with generational collection. An incremental, non-concurrent version could be implemented easily on many versions of Unix.