Jeremy G. Siek - Essentials of Compilation: An Incremental Approach in Racket

Essentials of Compilation

An Incremental Approach in Racket

Jeremy G. Siek

The MIT Press
Cambridge, Massachusetts
London, England

2023 Massachusetts Institute of Technology

This work is subject to a Creative Commons CC-BY-ND-NC license.

Subject to such license, all rights are reserved.

The MIT Press would like to thank the anonymous peer reviewers who provided comments on drafts of this book. The generous work of academic experts is essential for establishing the authority and quality of our publications. We acknowledge with gratitude the contributions of these otherwise uncredited readers.

Library of Congress Cataloging-in-Publication Data

Names: Siek, Jeremy, author.

Title: Essentials of compilation: an incremental approach in Racket / Jeremy G. Siek.

Description: Cambridge, Massachusetts: The MIT Press, [2023] | Includes bibliographical references and index.

Identifiers: LCCN 2022015399 (print) | LCCN 2022015400 (ebook) | ISBN 9780262047760 (hardcover) | ISBN 9780262373272 (epub) | ISBN 9780262373289 (pdf)

Subjects: LCSH: Racket (Computer program language) | Compilers (Computer programs)

Classification: LCC QA76.73.R33 S54 2023 (print) | LCC QA76.73.R33 (ebook) | DDC 005.13/3dc23/eng/20220705

LC record available at https://lccn.loc.gov/2022015399

LC ebook record available at https://lccn.loc.gov/2022015400

d_r0

This book is dedicated to Katie, my partner in everything, my children, who grew up during the writing of this book, and the programming language students at Indiana University, whose thoughtful questions made this a better book.

List of Illustrations

Diagram of chapter dependencies.

The concrete syntax of Int.

The abstract syntax of Int.

Example of recursive functions for Int. These functions recognize whether an AST is in Int.

Interpreter for the Int language.

A partial evaluator for Int.

The concrete syntax of Var.

The abstract syntax of Var.

Interpreter for Int as a class.

Interpreter for the Var language.

Association lists implement the dictionary interface.

The syntax of the x86Int assembly language (AT&T syntax).

An x86 program that computes (+ 10 32).

An x86 program that computes (+ 52 (- 10)).

Memory layout of a frame.

The abstract syntax of x86Int assembly.

Diagram of the passes for compiling Var.

The concrete syntax of the Var intermediate language.

The abstract syntax of the Var intermediate language.

Skeleton for the uniquify pass.

is Var with operands restricted to atomic expressions.

Skeleton for the explicate_control pass.

A running example for register allocation.

An example with function calls.

The set data structure.

Example output of liveness analysis on a short example.

The running example annotated with live-after sets.

The Racket graph package.

Interference results for the running example.

The interference graph of the example program.

A sudoku game board and the corresponding colored graph.

The saturation-based greedy graph coloring algorithm.

The priority queue data structure.

Diagram of the passes for Var with register allocation.

The x86 output from the running example (figure 3.1), limiting allocation to just rbx and rcx.

The concrete syntax of If, extending Var (figure 2.1) with Booleans and conditionals.

The abstract syntax of If.

Interpreter for the If language. (See figure 4.4 for interp-op.)

Interpreter for the primitive operators in the If language.

Type checker for the Var language.

Type checker for the If language.

The concrete syntax of the If intermediate language, an extension of Var (figure 2.12).

The abstract syntax of If, an extension of Var (figure 2.13).

The concrete syntax of x86If (extends x86Int of figure 2.6).

The abstract syntax of x86If (extends x86Int shown in figure 2.10).

is If in monadic normal form (extends in figure 2.15).

Translation from If to If via the explicate_control.

Skeleton for the explicate_pred auxiliary function.

Example compilation of an if expression to x86, showing the results of explicate_control, select_instructions, and the final x86 assembly code.

Diagram of the passes for If, a language with conditionals.

Translation from If to If via the improved explicate_control.

Merging basic blocks by removing unnecessary jumps.

The concrete syntax of While, extending If (figure 4.1).

The abstract syntax of While, extending If (figure 4.2).

Interpreter for While.

Type checker for the While language.

Generic work list algorithm for dataflow analysis.

is While in monadic normal form.

The abstract syntax of , extending If (figure 4.8).

Diagram of the passes for While.

The concrete syntax of Tup, extending While (figure 5.1).

The abstract syntax of Tup.

Interpreter for the Tup language.

Type checker for the Tup language.

A copying collector in action.

Depiction of the Cheney algorithm copying the live tuples.

Maintaining a root stack to facilitate garbage collection.

Representation of tuples in the heap.

The compilers interface to the garbage collector.

Output of the expose_allocation pass.

is Alloc in monadic normal form.

The abstract syntax of Tup, extending (figure 5.7).

The concrete syntax of x86Global (extends x86If shown in figure 4.9).

The abstract syntax of x86Global (extends x86If shown in figure 4.10).

Output of the explicate_control (left) and select_instructions (right) passes on the running example.

The prelude and conclusion generated by the prelude_and_conclusion pass for the running example.

Diagram of the passes for Tup, a language with tuples.

The concrete syntax of Struct, extending Tup (figure 6.1).

The abstract syntax of Struct, extending Tup (figure 6.2).

The concrete syntax of Array, extending Tup (figure 6.1).

The abstract syntax of Array, extending Tup (figure 6.2).

Example program that computes the inner product.

Type checker for the Array language.

Interpreter for Array.

The concrete syntax of Fun, extending Tup (figure 6.1).

The abstract syntax of Fun, extending Tup (figure 6.2).

Example of using functions in Fun.

Interpreter for the Fun language.

Type checker for the Fun language.

Memory layout of caller and callee frames.

is FunRef in monadic normal form.

The abstract syntax of Fun, extending Tup (figure 6.12).

The concrete syntax of (extends x86Global of figure 6.13).

The abstract syntax of x86Def callq* (extends x86Global of figure 6.14).

Example compilation of a simple function to x86.