A common problem with preprocessors and compilers for high-level structured programming languages (those that have constructs such as if-then-else, while-do, and repeat-until) is that, for the sake of simplicity, they produce redundant code when translating nested instances of these constructs. For instance, multiple labels can be attached to the same statement, or jump instructions can branch to other branch instructions. The consequences of these redundancies include that the size of the generated code or text increases; the processing time of the subsequent phases (assembly or compiling) increases; if no optimizing phase is applied, the speed of the generated code decreases; and, for preprocessors, the generated program is more difficult to read and debug.

These problems are usually tackled by a separate optimization phase, such as the postpass (peephole) optimizer c2 invoked by most UNIX compilers when given the -0 option. Such optimizers can eliminate all of the above redundancies, though at the expense of added processing time and complexity; indeed, optimizing out redundant code is a global process because it involves control flow analysis, and it is usually performed in two or more passes.

Tsuji describes a new scheme that can be easily incorporated in most structured language processors and that enables them to directly produce optimized code (in the above sense). Basically, the idea is to keep track of when  multiple  labels actually designate the same place in the code or designate the same place modulo a chain of unconditional branches, so as to avoid the above redundancies. Of course, some forward-jump instructions need to be fixed after they have been generated, for instance when it is discovered that they target other jump instructions. These fixes are achieved by keeping track of the location of such jump instructions in the output file and rewriting their targets, if necessary, in a subsequent pass. Thus, although the author claims the scheme works in one pass, it actually needs one and a half passes.

Tsuji presents several versions of his scheme, in particular a source-language-driven scheme, which gives better results but is harder to apply to an existing processor, and an object-code–driven scheme that can be used as an “abstract package” in nearly all situations. Actual use of the scheme is exemplified by applying it to various structured FORTRAN preprocessors, a postpass FORTRAN optimizer, and a C compiler producing assembly code. The topic is covered in great detail (with actual source code in WESTRAN and in C). The explanations are clear and include enough redundancy, examples, and pictures to make sure the reader understands every difficulty, thus allowing her or him to easily incorporate Tsuji’s ideas in existing or new language processors. This book is directed mostly to language implementors, although anyone with a minimal background and interest in compiler construction and structured programming could find it valuable.

The basic idea is only of marginal value, however. The few experiments performed by Tsuji himself show that, in general, a complete compilation chain using his scheme is less than 10 percent faster than a classical compilation chain without an optimizer, and the programs generated using the optimizing scheme exhibit a negligible improvement over the original programs in terms of runtime speed (less than one percent). Furthermore, the scheme addresses only redundancies caused by nested high-level constructs and does not apply to other control-flow constructs such as Boolean expressions. In addition, the implementation of the scheme is falsely presented as one-pass, while it is actually an instance of the old technique known as “backpatching”; Tsuji is apparently not aware of this technique and never uses this word. Finally, although the index and bibliography are generally adequate (except for the absence of any reference to backpatching), the book is made hard to read by an unusual number of spelling and style errors.

I would recommend this book only to language implementors who really care about chains of jump instructions. Otherwise, an earlier paper by Tsuji and his colleagues [1] should be sufficient to explain the basic scheme and the main implementation details.