This paper describes a programminglanguage for writing code generators. The language abbreviates repetitive constructs, simplifies encoding, and assumes responsibility for making the code generator small and fast. As...
详细信息
This paper describes a programminglanguage for writing code generators. The language abbreviates repetitive constructs, simplifies encoding, and assumes responsibility for making the code generator small and fast. As a result, a specification for the VAX takes 126 lines, one for the Motorola 68020 takes 156, and one for the MIPS R3000 takes 75. This project grew out of experience with a system that tracked the operation of a high-tech peephole optimizer and generated a hard-coded code generator from the trace. The current system generates similar code generators directly from a compact document that captures their entropy.
We present an algorithm for automatically generating a nested, fork-join parallel program from a sequential program represented in terms of control and data dependences. This algorithm embodies two techniques for deal...
详细信息
We present an algorithm for automatically generating a nested, fork-join parallel program from a sequential program represented in terms of control and data dependences. This algorithm embodies two techniques for dealing with data dependences: the first implicitly satisfies such dependences by reducing parallelism, and the second eliminates some dependences by introducing private variables. This algorithm has been implemented in the PTRAN system.
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 bounde...
详细信息
For a context-free grammar G, a construction is given to produce an LR parser that recognizes any substring of the language generated by G. The construction yields a conflict-free (deterministic) parser for the bounded context class of grammars (Floyd, 1964). The same construction yields either a left-to-right or right-to-left substring parser, as required to implement Non-correcting Syntax Error Recovery as proposed by Richter (1985). Experience in constructing a substring parser for Pascal is described.
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 progra...
详细信息
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 programminglanguages to be completely described in a single grammar. The enhancements consist of two new grammar rules, the exclusion rule, and the adjacency-restriction rule. We also present parser construction techniques for building parsers from these enhanced grammars, that eliminate the need for a scanner phase.
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 ...
详细信息
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 compliles several copies of a given procedure, each customized for one receiver type, so that the type of the receiver is bound at compile time. The compiler predicts types that are statically unknown but likely, and inserts run-time type tests to verify its predictions. It splits calls, compiling a copy on each control path, optimized to the specific types on that path. Coupling these new techniques with compile-time message lookup, aggressive procedure inlining, and traditional optimizations has doubled the performance of dynamically-typed object-oriented languages.
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 r...
详细信息
Cedar is the name for both a language and an environment in use in the Computer Science Laboratory at Xerox PARC since 1980. The Cedar language is a superset of Mesa, the major additions being garbage collection and runtime types. Neither the language nor the environment was originally intended to be portable, and for many years ran only on D-machines at PARC and a few other locations in Xerox. We recently re-implemented the language to make it portable across many different architectures. We present a brief description of the Cedar language, our portability strategy for the compiler and runtime, our manner of making connections to other languages and the Unix operating system, and some measures of the performance of our 'Portable Cedar'.
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 equal...
详细信息
In the context of sequential computers, it is common practice to exploit temporal locality of reference through devices such as caches and virtual memory. In the context of multiprocessors, we believe that it is equally important to exploit spatial locality of reference. We are developing a system which, given a sequential program and its domain decomposition, performs process decomposition so as to enhance spatial locality of reference. We describe an application of this method - generating code from shared-memory programs for the (distributed memory) Intel iPSC/2.
Our concern is how to determine data dependences between program constructs in programminglanguages with pointer variables. We are particularly interested in computing data dependences for languages that manipulate h...
详细信息
Our concern is how to determine data dependences between program constructs in programminglanguages with pointer variables. We are particularly interested in computing data dependences for languages that manipulate heap-allocated storage, such as Lisp and Pascal. We have defined a family of algorithms that compute safe approximations to the flow, output, and anti-dependences of a program written in such a language. Our algorithms account for destructive updates to fields of a structure and thus are not limited to the cases where all structures are trees or acyclic graphs;they are applicable to programs that build cyclic structures. For structured programming constructs, the technique can be extended to distinguish between loop-carried and loop-independent dependences, as well as to determine lower bounds on minimum distances for loop-carried dependences.
In this paper, we present a technique for summarizing the data accesses in a given region and show how this summary can be used to detect and enhance task parallelism in a program. For the sake of simplicity, we restr...
详细信息
In this paper, we present a technique for summarizing the data accesses in a given region and show how this summary can be used to detect and enhance task parallelism in a program. For the sake of simplicity, we restrict our discussion to Fortran programs that consist of a sequence of perfectly-nested loops in which all subroutine calls are expanded inline. However, the techniques presented here can easily be extended to the general case of programs with imperfectly nested loops and subroutine calls.
Optimizing and parallelizing compilers for procedural languages rely on various forms of program dependence graphs (pdgs) to express the essential control and data dependences among atomic program operations. In this ...
详细信息
Optimizing and parallelizing compilers for procedural languages rely on various forms of program dependence graphs (pdgs) to express the essential control and data dependences among atomic program operations. In this paper, we provide a semantic justification for this practice by deriving two different forms of program dependence graph - the output pdg and the def-order pdg - and their semantic definitions from non-strict generalizations of the denotational semantics of the programminglanguage. In the process, we demonstrate that both the output pdg and the def-order pdg (with minor technical modifications) are conventional data-flow programs. In addition, we show that the semantics of the def-order pdg dominates the semantics of the output pdg and that both of these semantics dominate - rather than preserve - the semantics of sequential execution.
暂无评论