A new instruction adapts LZ77 compression for use inside running programs. The instruction economically references and reuses code fragments that are too small to package as conventional subroutines. The compressed code is interpreted directly, with neither prior nor on-the-fly decompression. Hardware implementations seem plausible and could benefit both memory-constrained and more conventional systems. The method is extremely simple. It has been added to a pre-existing, bytecoded instruction set, and it added only 10 lines of C to the bytecode interpreter. It typically cuts code size by a third; that is, typical compression ratios are roughly 0.67×. More ambitious compressors are available, but they are more complex, which retards adoption. The current method offers a useful trade-off to these more complex systems. Copyright © 2005 John Wiley & Sons, Ltd.

This paper describes the design and implementation of a method for producing compact, bytecoded instruction sets and interpreters for them. It accepts a grammar for programs written using a simple bytecoded stack-based instruction set, as well as a training set of sample programs. The system transforms the grammar, creating an expanded grammar that represents the same language as the original grammar, but permits a shorter derivation of the sample programs and others like them. A program's derivation under the expanded grammar forms the compressed bytecode representation of the program. The interpreter for this bytecode is automatically generated from the original bytecode interpreter and the expanded grammar. Programs expressed using compressed bytecode can be substantially smaller than their original bytecode representation and even their machine code representation. For example, compression cuts the bytecode for lcc from 199KB to 58KB but increases the size of the interpreter by just over 11KB. Categories and Subject Descriptors D.3.3 [Programming Languages]: Processors---optimization, run-time environments. General Terms Algorithms, Performance, Design, Economics, Experimentation, Languages, Theory. Keywords Program compression, bytecode interpretation, variable-to-fixed length codes, context-free grammars. 1.

This paper describes experiments that apply machine learning to compress computer programs, formalizing and automating decisions about instruction encoding that have traditionally been made by humans in a more ad hoc manner. A program accepts a large training set of program material in a conventional compiler intermediate representation (IR) and automatically infers a decision tree that separates IR code into streams that compress much better than the undifferentiated whole. Driving a conventional arithmetic compressor with this model yields code 30% smaller than the previous record for IR code compression, and 24% smaller than an ambitious optimizing compiler feeding an ambitious general-purpose data compressor.

This paper describes gburg, which generates tiny, fast code generators based on finite-state machine pattern matching. The code generators translate postfix intermediate code into machine instructions in one pass (except, of course, for backpatching addresses) . A stack-based virtual machine---known as the Lean Virtual Machine (LVM)---tuned for fast code generation is also described. Gburg translates the two-page LVM-to-x86 specification into a code generator that fits entirely in an 8 KB I-cache and that emits x86 code at 3.6 MB/sec on a 266-MHz P6. Our just-in-time code generator translates and executes small benchmarks at speeds within a factor of two of executables derived from the conventional compile-time code generator on which it is based. 1 Introduction To execute virtual machine (VM) code on a client processor typically requires either a VM interpreter or a just-in-time (JIT) translator. Conventional wisdom dictates that the space/time tradeo# favors the interpreter approac...

Current research in compiler optimization counts mainly CPU time and perhaps the first cache level or two. This view has been important but is becoming myopic, at least from a system-wide viewpoint, as the ratio of network and disk speeds to CPU speeds grows exponentially.For example, we have seen the CPU idle for most of the time during paging, so compressing pages can increase total performance even though the CPU must decompress or interpret the page contents. Another profile shows that many functions are called just once, so reduced paging could pay for their interpretation overhead.This paper describes:• Measurements that show how code compression can save space and total time in some important real-world scenarios.• A compressed executable representation that is roughly the same size as gzipped x86 programs and can be interpreted without decompression. It can also be compiled to high-quality machine code at 2.5 megabytes per second on a 120MHz Pentium processor• A compressed "wire" representation that must be decompressed before execution but is, for example, roughly 21% the size of SPARC code when compressing gcc.

This paper describes a method for detecting structural hazards 5--80 times faster than its predecessors, which generally have simulated the pipeline at compile time. It accepts a compact specification of the pipeline and creates a finitestate automaton that can detect structural hazards in one table lookup per instruction. The automaton maintains an integer state that encodes all potential structural hazards for all instructions in the pipe. It accepts an instruction type and a state and either reports a hazard or produces the state that folds in the new instruction and advances the pipeline by one cy-

Abstract 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.

Abstract Code generators based on bottom‐up rewrite systems (BURS) are automatically generated from machine‐description 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.

Abstract 1cc 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.

Abstract This paper describes software that allows the user to edit the output of several common software tools and to cause the changes to be written back to the input files. For example, it is possible to edit the output of a spelling checker and have the changes propagated back to the source files. This technique makes some corrections simpler and more direct. A trial implementation is embedded in Emacs.

Article Free Access Share on A language for writing code generators Author: C. W. Fraser AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile Authors Info & Claims PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementationJune 1989 Pages 238–245https://doi.org/10.1145/73141.74839Published:21 June 1989Publication History 26citation545DownloadsMetricsTotal Citations26Total Downloads545Last 12 Months34Last 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

article Free Access Share on Automatic generation of fast optimizing code generators Authors: C. W. Fraser AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile , A. L. Wendt Univ. of Arizona, Tucson, AZ Univ. of Arizona, Tucson, AZView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 23Issue 7July 1988 pp 79–84https://doi.org/10.1145/960116.53998Online:01 June 1988Publication History 19citation463DownloadsMetricsTotal Citations19Total Downloads463Last 12 Months16Last 6 weeks4 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract 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.

Programming environments support revision control in several guises. Explicitly, revision control software manages the trees of revisions that grow as software is modified. Implicitly, editors retain past versions by automatically saving backup copies and by allowing users to undo commands. This paper describes an editor that offers a uniform solution to these problems by never destroying the old version of the file being edited. It represents files using a generalization of AVL trees called “AVL dags,” which makes it affordable to automatically retain past versions of files. Automatic retention makes revision maintenance transparent to users. The editor also uses the same command language to edit both text and revision trees.

EZ is a language-based programming environment that offers the services provided separately by programming languages and operating systems in traditional environments. These services are provided as facilities of a high-level string processing language with a 'persistent' memory in which values exist indefinitely or until changed. In EZ, strings and associative tables provide traditional file and directory services. This paper concentrates on the use of EZ procedures and their activations, which, like other values, have indefinite lifetimes. In EZ, the low-level aspects of procedure execution, such as activation record creation, references to local variables, and access to state information, are accessible via high-level language constructs. As a result, traditionally distinct services can be provided by a single service in the EZ environment. Furthermore, such services can be written in EZ itself. An editor/debugger that illustrates the details of this approach is described.

Abstract 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.

This paper shows how thorough object code optimization has simplified a compiler and made it easy to retarget.The code generator forgoes case analysis and emits naive code that is improved by a retargetable object code optimizer.With this technique, cross-compilers have been built for seven machines, some in as few as three person days.These cross-compilers emit code comparable to hostspecific compilers.

Compilers usually eliminate common subexpressions in intermediate code, not object code. This reduces machine-dependence but misses the machine-dependent common subexpressions introduced by the last phases of code expansion. This paper describes a machine-independent procedure for eliminating machine-specific common subexpressions. It also identifies dead variables, defines windows for a companion peephole optimizer, and forms the basis of a retargetable register allocator. Its techniques for handling machine-specific data should generalize to other optimizations as well.

Abstract 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.

Abstract 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.

Abstract 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.

Text is not the only data that needs editing.For example, interactive debuggers edit data structures internal to running programs.This paper describes eds, a generalized editor that allows users to edit arbitrary data structures.Examples show eds maintaining simple databases, editing LISP S-expressions, debugging SNOBOL4 programs, and creating and modifying data structures for a computer graphics system.

Abstract 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.

Abstract 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.

Peephole optimizers improve object code by replacing certain sequences of instructions with better sequences. This paper describes PO, a peephole optimizer that uses a symbolic machine description to simulate pairs of adjacent instructions, replacing them, where possible, with an equivalent single instruction. As a result of this organization, PO is machine independent and can be described formally and concisely: when PO is finished, no instruction, and no pair of adjacent instructions, can be replaced with a cheaper single instruction that has the same effect. This thoroughness allows PO to relieve code generators of much case analysis; for example, they might produce only load/add-register sequences and rely on PO to, where possible, discard them in favor or add-memory, add-immediate, or increment instructions. Experiments indicate that naive code generators can give good code if used with PO.

Object code optimizers pay dividends but are usually ad hoc and machine-dependent. They would be easier to understand if, instead of performing many ad hoc optimizations, they performed a few general optimizations that give the same effect. They would be easier to implement if they were machine-independent and parametrized by symbolic machine descriptions. This paper describes such a compact, machine-independent peephole optimizer.

Abstract 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.