Search

SUMMARY This paper describes the management of register spills in a retargetable C compiler. Spills are rare, which means that testing is a bigger problem than performance. The trade-offs have been arranged so that the common case (no spills) generates respectable code quickly and the uncommon case (spills) is less efficient but as simple as possible. The technique has proven practical and is in production use on VAX, Motorola 68020, SPARC and MIPS machines.

SUMMARY lcc is a retargetable, production compiler for ANSI C; it has been ported to the VAX, Motorola 68020, SPARC, and MIPS R3000, and some versions have been in use for over a year and a half. It is smaller and faster than generally available alternatives, and its local code is comparable. This paper describes the interface between the target-independent front end and the target-dependent back ends. The interface consists of shared data structures, a few functions, and a dag language. While this approach couples the front and back ends tightly, it results in efficient, compact compilers. The interface is illustrated by detailing a code generator that emits naive VAX code.

SUMMARY Code generators based on bottom-up rewrite systems (BURS) are automatically generated from machinedescription grammars. They produce locally optimal code for expression trees, but their tables are large and require compile-time interpretation. This paper describes a program that compiles BURS tables into a combination of hard code and data. Hard-coding exposed important opportunities for compression that were previously hidden in the tables, so the hard-coded code generators are not just faster but also significantly smaller than their predecessors. A VAX code generator takes 21.4Kbytes and identifies optimal assembly code in about 50 VAX instructions per node.

Emerging peephole optimizers can relieve code generators of much case analysis, but delaying code generation decisions requires register allocation algorithms that accept object code instead of the more usual intermediate code. This paper describes two programs that implement such algorithms for a retargetable optimizing compiler. In a machine-independent fashion, they allocate and assign registers, eliminate common subexpressions (including often-missed machine-specific ones), identify dead variables, and define windows for the companion peephole optimizer. Their techniques for handling machine-specific data should generalize to other optimizations as well.

Linkers, although a well-established component of language translation, are typically machine-dependent, idiosyncratic, and hard for many users to understand. This paper describes a machine-independent linker and object language. The linker embodies those linking functions that are machine-independent and centralizes them in a single tool, simplifying compilers, assemblers, and loaders. Included are descriptions of its operation, implementation, and application.

Increasingly powerful machine instructions complicate abstract machine design for portability. Abstract machine instructions must be “larger” than the target machine instructions that they are to exploit, but they must not grow so large as to complicate the realization of the abstract machine on real machines. This paper presents related techniques for low-level yet machine-independent access to typical stack and string-processing instructions.

Peephole optimizers that are driven by machine descriptions are generally more thorough but less efficient than their classical rule-directed counterparts. This paper describes a system that addresses this shortcoming. It automatically infers rules by tracking the behaviour of a description-directed optimizer on a testbed, and it adapts a classical optimizer to interpret these rules efficiently. Experiments show that an easily constructed testbed can generate rules similar to those in a large hand-written rulebase. This software forms part of a compiler that simplifies retargeting by substituting peephole optimization for case analysis.

While operating system command languages have improved in recent years, the advances have not yet been widely applied to other command interpreters. This paper describes an editor that has been given two features popular in operating system command languages — i/o redirection and programmable command files. The result is suited both to editing and to some repetitive reformatting tasks often solved by one-shot, ad hoc programs. Examples display the utility of the extensions, and implications for still other command interpreters are discussed.

The special editing ability of display terminals is seldom exploited outside of display-based text editors. Tailoring a device driver in the operating system kernel to display terminals makes display editing available whenever the terminal is used and makes display editors simpler and terminal-independent. This paper describes such a device driver.

The proliferation of different versions of a program complicates maintenance: a change to the common ancestor of several versions requires a change to all versions. Some software distributors publish editor command scripts to automate these changes, but extensive modifications of the software by a remote installer can invalidate the scripts. This paper describes a program that alleviates this problem by merging editor scripts and shows how it has simplified a substantial version maintenance problem.

CRT-based text editors offer a better user interface than most teletype-based text editors but are more complex and less portable. Building a screen editor as a front end to a line editor exploits existing code, yields a more compact, portable result, and permits one computer to edit another's files. This paper describes such an editor.