A framework for construction and evaluation of high-level specifications for program analysis techniques
Abstract interpretation introduced the notion of formal specification of program analyses. Denotational frameworks are convenient for reasoning about such specifications. However, implementation considerations make denotational specifications complex ...
The semantics of program dependence
Optimizing and parallelizing compilers for procedural languages rely on various forms of program dependence graphs (pdgs) to express the essential control and data dependencies among atomic program operations. In this paper, we provide a semantic ...
Dependence analysis for pointer variables
Our concern is how to determine data dependencies between program constructs in programming languages with pointer variables. We are particularly interested in computing data dependencies for languages that manipulate heap-allocated storage, such as ...
Process decomposition through locality of reference
In the context of sequential computers, it is common practice to exploit temporal locality of reference through devices such as caches and virtual memory. In the context of multiprocessors, we believe that it is equally important to exploit spatial ...
Mul-T: a high-performance parallel Lisp
Mul-T is a parallel Lisp system, based on Multilisp's future construct, that has been developed to run on an Encore Multimax multiprocessor. Mul-T is an extended version of the Yale T system and uses the T system's ORBIT compiler to achieve “production ...
Parallel compilation for a parallel machine
An application for a parallel computer with multiple, independent processors often includes different programs (functions) for the individual processors; compilation of such functions can proceed independently. We implemented a compiler that exploits ...
Experience with CST: programming and implementation
CST is a programming language based on Smalltalk-802 that supports concurrency using locks, asynchronous messages, and distributed objects. In this paper, we describe CST: the language and its implementation. Example programs and initial programming ...
A fresh look at combinator graph reduction
We present a new abstract machine for graph reduction called TIGRE. Benchmark results show that TIGRE's execution speed compares quite favorably with previous combinator-graph reduction techniques on similar hardware. Furthermore, the mapping of TIGRE ...
A VHDL compiler based on attribute grammar methodology
This paper presents aspects of a compiler for a new hardware description language (VHDL) written using attribute grammar techniques. VHDL is introduced, along with the new compiler challenges brought by a language that extends an Ada subset for the ...
Higher order attribute grammars
A new kind of attribute grammars, called higher order attribute grammars, is defined. In higher order attribute grammars the structure tree can be expanded as a result of attribute computation. A structure tree may be stored in an attribute. The term ...
Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language
Dynamically-typed object-oriented languages please programmers, but their lack of static type information penalizes performance. Our new implementation techniques extract static type information from declaration-free programs. Our system compiles ...
An LR substring parser for noncorrecting syntax error recovery
For a context-free grammar G, a construction is given to produce an LR parser that recognizes any substring of the language generated by G. The construction yields a conflict-free (deterministic) parser for the bounded context class of grammars (Floyd, ...
Scannerless NSLR(1) parsing of programming languages
The disadvantages of traditional two-phase parsing (a scanner phase preprocessing input for a parser phase) are discussed. We present metalanguage enhancements for context-free grammars that allow the syntax of programming languages to be completely ...
Incremental generation of parsers
An LR-based parser generator for arbitrary context-free grammars is described, which generates parsers by need and processes grammar modifications by updating already existing parsers. We motivate the need for these techniques in the context of ...
Type inference in the presence of type abstraction
A number of recent programming language designs incorporate a type checking system based on the Girard-Reynolds polymorphic λ-calculus. This allows the construction of general purpose, reusable software without sacrificing compile-time type checking. A ...
Type reconstruction with first-class polymorphic values
We present the first type reconstruction system which combines the implicit typing of ML with the full power of the explicitly typed second-order polymorphic lambda calculus. The system will accept ML-style programs, explicitly typed programs, and ...
Reasoning about continuations with control effects
We present a new static analysis method for first-class continuations that uses an effect system to classify the control domain behavior of expressions in a typed polymorphic language. We introduce two new control effects, goto and comefrom, that ...
BEG: a generator for efficient back ends
This paper describes a system that generates compiler back ends from a strictly declarative specification of the code generation process. The generated back ends use tree pattern matching for code selection. Two methods for register allocation ...
Inline function expansion for compiling C programs
Inline function expansion replaces a function call with the function body. With automatic inline function expansion, programs can be constructed with many small functions to handle complexity and then rely on the compilation to eliminate most of the ...
Spill code minimization techniques for optimizing compliers
Global register allocation and spilling is commonly performed by solving a graph coloring problem. In this paper we present a new coherent set of heuristic methods for reducing the amount of spill code generated. This results in more efficient (and ...
Register allocation via clique separators
Although graph coloring is widely recognized as an effective technique for global register allocation, the overhead can be quite high, not only in execution time but also in memory, as the size of the interference graph needed in coloring can become ...
Coloring heuristics for register allocation
We describe an improvement to a heuristic introduced by Chaitin for use in graph coloring register allocation. Our modified heuristic produces better colorings, with less spill code. It has similar compile-time and implementation requirements. We ...
On-the-fly detection of access anomalies
Access anomalies are a common class of bugs in shared-memory parallel programs. An access anomaly occurs when two concurrent execution threads both write (or one thread reads and the other writes) the same shared memory location without coordination. ...
Determining average program execution times and their variance
This paper presents a general framework for determining average program execution times and their variance, based on the program's interval structure and control dependence graph. Average execution times and variance values are computed using frequency ...
Generational reference counting: a reduced-communication distributed storage reclamation scheme
This paper describes generational reference counting, a new distributed storage reclamation scheme for loosely-coupled multiprocessors. It has a significantly lower communication overhead than distributed versions of conventional reference counting. ...
Experiences creating a portable cedar
Cedar is the name for both a language and an environment in use in the Computer Science Laboratory at Xerox PARC since 1980. The Cedar language is a superset of Mesa, the major additions being garbage collection and runtime types. Neither the language ...
Demonic memory for process histories
Demonic memory is a form of reconstructive memory for process histories. As a process executes, its states are regularly checkpointed, generating a history of the process at low time resolution. Following the initial generation, any prior state of the ...