Compiler writers facea bleak future---soon everyone will be using Ada on the Nebula Architecture and there will be no further need for our services. Luckily, it appears to be possible to recycle compiler writers by encouraging them to build circuit design tools (Silicon Compilers). Many of the standard techniques used in compilers can be immediately applied in circuit design, especially for LSI circuits. In part, this paper attempts to serve as a tutorial, casting some of the problems of designing in nMOS with the Mead-Conway design rules into the vocabulary of the compiler writer. The paper also discusses experience with a Silicon compiler that has fabricated over two dozen different designs.

No abstract available.

A compiler for the C language has recently been constructed which is now compiling C for about half a dozen machines. The compiler was influenced in various ways by recent theoretical developments. This paper gives an overview of the compiler structure and algorithms, emphasizing those areas where theory was helpful, and discussing the approaches taken where theory was lacking.

Previous work on optimal code generation has usually assumed that the underlying machine has identical registers and that all operands fit in a single register or memory location. This paper considers the more realistic problem of generating optimal code for expressions involving single and double length operands, using several models of register-pair machines permitting both single and double word instructions. With register-pair machines a new phenomenom arises that is not present in optimal code generation for single register machines: In an optimal evaluation of an expression it may be necessary to oscillate back and forth between evaluating subexpressions of the expression.A linear-time optimal code generation algorithm is derived for a register-pair machine in which all registers are interchangeable. The algorithm is based on showing that for this model there is an optimal evaluation sequence with limited oscillation between the sub-trees dominated by the children of a given node. For other machine models including the familiar even-odd register-pair machine, optimal evaluation sequences can always require unlimited oscillation.

This paper shows the problem of generating optimal code for expressions containing common subexpressions is computationally difficult, even for simple expressions and simple machines. Some heuristics for code generation are given and their worst-case behavior is analyzed. For one register machines, an optimal code generation algorithm is given whose time complexity is linear in the size of an expression and exponential only in the amount of sharing.

Easy as the task may seem, many compilers generate rather inefficient code. Some of the difficulty of generating good code may arise from the lack of realistic models for programming language and machine semantics. In this paper we show that the computational complexity of generating efficient code in realistic situations may also be a major cause of difficulty in the design of good compilers.

This paper discusses algorithms which transform expression trees into code for register machines. A necessary and sufficient condition for optimality of such an algorithm is derived, which applies to a broad class of machines. A dynamic programming algorithm is then presented which produces optimal code for any machine in this class; this algorithm runs in time linearly proportional to the size of the input.

The problem of computing the deternunant of a matrix of polynomials IS considered; two algo. rithms (expansion by minors and expansion by Gaussian ehmmatmn) are compared; and each is examined under two models for polynomial computatmn (dense univanate and totally sparse). The results, while interesting in themselves, also serve to display two points: (1) Asymptotic results are sometimes misleading for noninfimte (e.g. practical) problems. (2) Models of computa-tion are by definition simplifications of reahty: algorithmic analysis should be carried out under several distract computatmnal models and should be supported by empirical data. Key Words and Phrases: symbohc algebraic computation, analysm of algorithms, determinants of polynomial matrices

We discuss the problem of generating code for a wide class of machines, restricting ourselves to the computation of expression trees. After defining a broad class of machines and discussing the properties of optimal programs on these machines, we derive a necessary and sufficient condition which can be used to prove the optimality of any code generation algorithm for expression trees on this class. We then present a dynamic programming algorithm which produces optimal code for any machine in the class; this algorithm runs in time which is linearly proportional to the number of vertices in an expression tree.

We consider methods of describing the syntax of programming languages in ways that are more flexible and natural than conventional BNF descriptions. These methods involve the use of ambiguous context-free grammars together with rules to resolve syntactic ambiguities. We show how efficient LL and LR parsers can be constructed directly from certain classes of these specifications.

We consider the problem of computing the determinant of a matrix of polynomials; we compare two algorithms (expansion by minors and Gaussian elimination), examining each under two models for polynomial computation (dense univariate and totally sparse). The results, while interesting in themselves, also serve to display two points:

The problem of recognizing when a complicated mathematical expression equals zero has great importance in symbolic mathematics.This paper gives two algorithms which can be applied to many such problems, and discusses a concrete example.The algorithms are based on the recognition that many interesting functions (such as exponentiation) are eigenvectors of well studied transformations (such as differentiation).