Essentials of Compilation: An Incremental Approach in Racket

Preface
1 Preliminaries
	1.1 Abstract Syntax Trees
	1.2 Grammars
	1.3 Pattern Matching
	1.4 Recursive Functions
	1.5 Interpreters
	1.6 Example Compiler: A Partial Evaluator
2 Integers and Variables
	2.1 The LVar Language
		2.1.1 Extensible Interpreters via Method Overriding
		2.1.2 Definitional Interpreter for LVar
	2.2 The x86Int Assembly Language
	2.3 Planning the Trip to x86
		2.3.1 The CVar Intermediate Language
	2.4 Uniquify Variables
	2.5 Remove Complex Operands
	2.6 Explicate Control
	2.7 Select Instructions
	2.8 Assign Homes
	2.9 Patch Instructions
	2.10 Generate Prelude and Conclusion
	2.11 Challenge: Partial Evaluator for LVar
3 Register Allocation
	3.1 Registers and Calling Conventions
	3.2 Liveness Analysis
	3.3 Build the Interference Graph
	3.4 Graph Coloring via Sudoku
	3.5 Patch Instructions
	3.6 Generate Prelude and Conclusion
	3.7 Challenge: Move Biasing
	3.8 Further Reading
4 Booleans and Conditionals
	4.1 The LIf Language
	4.2 Type Checking LIf Programs
	4.3 The CIf Intermediate Language
	4.4 The x86If Language
	4.5 Shrink the LIf Language
	4.6 Uniquify Variables
	4.7 Remove Complex Operands
	4.8 Explicate Control
		4.8.1 Explicate Tail and Assign
		4.8.2 Create Block
		4.8.3 Explicate Predicate
		4.8.4 Interactions between Explicate and Shrink
	4.9 Select Instructions
	4.10 Register Allocation
		4.10.1 Liveness Analysis
		4.10.2 Build the Interference Graph
	4.11 Patch Instructions
	4.12 Challenge: Optimize Blocks and Remove Jumps
		4.12.1 Optimize Blocks
		4.12.2 Remove Jumps
	4.13 Further Reading
5 Loops and Dataflow Analysis
	5.1 The LWhile Language
	5.2 Cyclic Control Flow and Dataflow Analysis
	5.3 Mutable Variables and Remove Complex Operands
	5.4 Uncover get!
	5.5 Remove Complex Operands
	5.6 Explicate Control and C
	5.7 Select Instructions
	5.8 Register Allocation
6 Tuples and Garbage Collection
	6.1 The LTup Language
	6.2 Garbage Collection
		6.2.1 Two-Space Copying Collector
		6.2.2 Graph Copying via Cheney\'s Algorithm
		6.2.3 Data Representation
		6.2.4 Implementation of the Garbage Collector
	6.3 Expose Allocation
	6.4 Remove Complex Operands
	6.5 Explicate Control and the CTup Language
	6.6 Select Instructions and the x86Global Language
	6.7 Register Allocation
	6.8 Generate Prelude and Conclusion
	6.9 Challenge: Simple Structures
	6.10 Challenge: Arrays
		6.10.1 Data Representation
		6.10.2 Overload Resolution
		6.10.3 Bounds Checking
		6.10.4 Expose Allocation
		6.10.5 Uncover get!
		6.10.6 Remove Complex Operands
		6.10.7 Explicate Control
		6.10.8 Select Instructions
	6.11 Challenge: Generational Collection
	6.12 Further Reading
7 Functions
	7.1 The LFun Language
	7.2 Functions in x86
		7.2.1 Calling Conventions
		7.2.2 Efficient Tail Calls
	7.3 Shrink LFun
	7.4 Reveal Functions and the LFunRef Language
	7.5 Limit Functions
	7.6 Remove Complex Operands
	7.7 Explicate Control and the CFun Language
	7.8 Select Instructions and the x86Defcallq* Language
	7.9 Register Allocation
		7.9.1 Liveness Analysis
		7.9.2 Build Interference Graph
		7.9.3 Allocate Registers
	7.10 Patch Instructions
	7.11 Generate Prelude and Conclusion
	7.12 An Example Translation
8 Lexically Scoped Functions
	8.1 The L Language
	8.2 Assignment and Lexically Scoped Functions
	8.3 Assignment Conversion
	8.4 Closure Conversion
		8.4.1 An Example Translation
	8.5 Expose Allocation
	8.6 Explicate Control and CClos
	8.7 Select Instructions
	8.8 Challenge: Optimize Closures
	8.9 Further Reading
9 Dynamic Typing
	9.1 The LDyn Language
	9.2 Representation of Tagged Values
	9.3 The LAny Language
	9.4 Cast Insertion: Compiling LDyn to LAny
	9.5 Reveal Casts
	9.6 Remove Complex Operands
	9.7 Explicate Control and CAny
	9.8 Select Instructions
	9.9 Register Allocation for LAny
10 Gradual Typing
	10.1 Type Checking L?
	10.2 Interpreting LCast
	10.3 Cast Insertion
	10.4 Lower Casts
	10.5 Differentiate Proxies
	10.6 Reveal Casts
	10.7 Closure Conversion
	10.8 Select Instructions
	10.9 Further Reading
11 Generics
	11.1 Compiling Generics
	11.2 Resolve Instantiation
	11.3 Erase Generic Types
A Appendix
	A.1 Interpreters
	A.2 Utility Functions
	A.3 x86 Instruction Set Quick Reference
References
Index