Writing a C Compiler: Build a Real Programming Language from Scratch

Cover
Title Page
Copyright
Dedication
About the Author
About the Technical Reviewer
Brief Contents
Contents in Detail
Acknowledgments
Introduction
	Who This Book Is For
	Why Write a C Compiler?
	Compilation from 10,000 Feet
	What You’ll Build
	How to Use This Book
		The Test Suite
		Extra Credit Features
	Some Advice on Choosing an Implementation Language
	System Requirements
		Installing GCC and GDB on Linux
		Installing the Command Line Developer Tools on macOS
		Running on Apple Silicon
		Validating Your Setup
	Additional Resources
	Let’s Go!
Part I: The Basics
	1. A Minimal Compiler
		The Four Compiler Passes
		Hello, Assembly!
		The Compiler Driver
		The Lexer
		The Parser
			An Example Abstract Syntax Tree
			The AST Definition
			The Formal Grammar
			Recursive Descent Parsing
		Assembly Generation
		Code Emission
		Summary
		Additional Resources
	2. Unary Operators
		Negation and Bitwise Complement in Assembly
		The Stack
		The Lexer
		The Parser
		TACKY: A New Intermediate Representation
			Defining TACKY
			Generating TACKY
			Generating Names for Temporary Variables
			Updating the Compiler Driver
		Assembly Generation
			Converting TACKY to Assembly
			Replacing Pseudoregisters
			Fixing Up Instructions
		Code Emission
		Summary
		Additional Resources
	3. Binary Operators
		The Lexer
		The Parser
			The Trouble with Recursive Descent Parsing
			The Adequate Solution: Refactoring the Grammar
			The Better Solution: Precedence Climbing
			Precedence Climbing in Action
		TACKY Generation
		Assembly Generation
			Doing Arithmetic in Assembly
			Converting Binary Operations to Assembly
			Replacing Pseudoregisters
			Fixing Up the idiv, add, sub, and imul Instructions
		Code Emission
		Extra Credit: Bitwise Operators
		Summary
		Additional Resources
	4. Logical and Relational Operators
		Short-Circuiting Operators
		The Lexer
		The Parser
		TACKY Generation
			Adding Jumps, Copies, and Comparisons to the TACKY IR
			Converting Short-Circuiting Operators to TACKY
			Generating Labels
		Comparisons and Jumps in Assembly
			Comparisons and Status Flags
			Conditional Set Instructions
			Jump Instructions
		Assembly Generation
			Replacing Pseudoregisters
			Fixing Up the cmp Instruction
		Code Emission
		Summary
		Additional Resources
	5. Local Variables
		Variables, Declarations, and Assignment
		The Lexer
		The Parser
			The Updated AST and Grammar
			An Improved Precedence Climbing Algorithm
		Semantic Analysis
			Variable Resolution
			The --validate Option
		TACKY Generation
			Variable and Assignment Expressions
			Declarations, Statements, and Function Bodies
			Functions with No return Statement
		Extra Credit: Compound Assignment, Increment, and Decrement
		Summary
	6. If Statements and Conditional Expressions
		The Lexer
		The Parser
			Parsing if Statements
			Parsing Conditional Expressions
		Variable Resolution
		TACKY Generation
			Converting if Statements to TACKY
			Converting Conditional Expressions to TACKY
		Extra Credit: Labeled Statements and goto
		Summary
	7. Compound Statements
		The Scoop on Scopes
		The Parser
		Variable Resolution
			Resolving Variables in Multiple Scopes
			Updating the Variable Resolution Pseudocode
		TACKY Generation
		Summary
	8. Loops
		Loops and How to Escape Them
		The Lexer
		The Parser
		Semantic Analysis
			Extending Variable Resolution
			Loop Labeling
			Implementing Loop Labeling
		TACKY Generation
			break and continue Statements
			do Loops
			while Loops
			for Loops
		Extra Credit: switch Statements
		Summary
	9. Functions
		Declaring, Defining, and Calling Functions
			Declarations and Definitions
			Function Calls
			Identifier Linkage
		Compiling Libraries
		The Lexer
		The Parser
		Semantic Analysis
			Extending Identifier Resolution
			Writing the Type Checker
		TACKY Generation
		Assembly Generation
			Understanding Calling Conventions
			Calling Functions with the System V ABI
			Converting Function Calls and Definitions to Assembly
			Replacing Pseudoregisters
			Allocating Stack Space During Instruction Fix-Up
		Code Emission
		Calling Library Functions
		Summary
	10. File Scope Variable Declarations and Storage-Class Specifiers
		All About Declarations
			Scope
			Linkage
			Storage Duration
			Definitions vs. Declarations
			Error Cases
		Linkage and Storage Duration in Assembly
		The Lexer
		The Parser
			Parsing Type and Storage-Class Specifiers
			Distinguishing Between Function and Variable Declarations
		Semantic Analysis
			Identifier Resolution: Resolving External Variables
			Type Checking: Tracking Static Functions and Variables
		TACKY Generation
		Assembly Generation
			Generating Assembly for Variable Definitions
			Replacing Pseudoregisters According to Their Storage Duration
			Fixing Up Instructions
		Code Emission
		Summary
Part II: Types Beyond Int
	11. Long Integers
		Long Integers in Assembly
			Type Conversions
			Static Long Variables
		The Lexer
		The Parser
		Semantic Analysis
			Adding Type Information to the AST
			Type Checking Expressions
			Type Checking return Statements
			Type Checking Declarations and Updating the Symbol Table
		TACKY Generation
			Tracking the Types of Temporary Variables
			Generating Extra Return Instructions
		Assembly Generation
			Tracking Assembly Types in the Backend Symbol Table
			Replacing Longword and Quadword Pseudoregisters
			Fixing Up Instructions
		Code Emission
		Summary
	12. Unsigned Integers
		Type Conversions, Again
			Converting Between Signed and Unsigned Types of the Same Size
			Converting unsigned int to a Larger Type
			Converting signed int to a Larger Type
			Converting from Larger to Smaller Types
		The Lexer
		The Parser
		The Type Checker
		TACKY Generation
		Unsigned Integer Operations in Assembly
			Unsigned Comparisons
			Unsigned Division
			Zero Extension
		Assembly Generation
			Replacing Pseudoregisters
			Fixing Up the Div and MovZeroExtend Instructions
		Code Emission
		Summary
	13. Floating-Point Numbers
		IEEE 754, What Is It Good For?
		The IEEE 754 Double-Precision Format
		Rounding Behavior
			Rounding Modes
			Rounding Constants
			Rounding Type Conversions
			Rounding Arithmetic Operations
		Linking Shared Libraries
		The Lexer
			Recognizing Floating-Point Constant Tokens
			Matching the End of a Constant
		The Parser
		The Type Checker
		TACKY Generation
		Floating-Point Operations in Assembly
			Working with SSE Instructions
			Using Floating-Point Values in the System V Calling Convention
			Doing Arithmetic with SSE Instructions
			Comparing Floating-Point Numbers
			Converting Between Floating-Point and Integer Types
		Assembly Generation
			Floating-Point Constants
			Unary Instructions, Binary Instructions, and Conditional Jumps
			Type Conversions
			Function Calls
			Return Instructions
			The Complete Conversion from TACKY to Assembly
			Pseudoregister Replacement
			Instruction Fix-Up
		Code Emission
			Formatting Floating-Point Numbers
			Labeling Floating-Point Constants
			Storing Constants in the Read-Only Data Section
			Initializing Static Variables to 0.0 or –0.0
			Putting It All Together
		Extra Credit: NaN
		Summary
		Additional Resources
	14. Pointers
		Objects and Values
		Operations on Pointers
			Address and Dereference Operations
			Null Pointers and Type Conversions
			Pointer Comparisons
			& Operations on Dereferenced Pointers
		The Lexer
		The Parser
			Parsing Declarations
			Parsing Type Names
			Putting It All Together
		Semantic Analysis
			Type Checking Pointer Expressions
			Tracking Static Pointer Initializers in the Symbol Table
		TACKY Generation
			Pointer Operations in TACKY
			A Strategy for TACKY Conversion
		Assembly Generation
			Replacing Pseudoregisters with Memory Operands
			Fixing Up the lea and push Instructions
		Code Emission
		Summary
	15. Arrays and Pointer Arithmetic
		Arrays and Pointer Arithmetic
			Array Declarations and Initializers
			Memory Layout of Arrays
			Array-to-Pointer Decay
			Pointer Arithmetic to Access Array Elements
			Even More Pointer Arithmetic
			Array Types in Function Declarations
			Things We Aren’t Implementing
		The Lexer
		The Parser
			Parsing Array Declarators
			Parsing Abstract Array Declarators
			Parsing Compound Initializers
			Parsing Subscript Expressions
		The Type Checker
			Converting Arrays to Pointers
			Validating Lvalues
			Type Checking Pointer Arithmetic
			Type Checking Subscript Expressions
			Type Checking Cast Expressions
			Type Checking Function Declarations
			Type Checking Compound Initializers
			Initializing Static Arrays
			Initializing Scalar Variables with ZeroInit
		TACKY Generation
			Pointer Arithmetic
			Subscripting
			Compound Initializers
			Tentative Array Definitions
		Assembly Generation
			Converting TACKY to Assembly
			Replacing PseudoMem Operands
			Fixing Up Instructions
		Code Emission
		Summary
	16. Characters and Strings
		Character Traits
		String Literals
		Working with Strings in Assembly
		The Lexer
		The Parser
			Parsing Type Specifiers
			Parsing Character Constants
			Parsing String Literals
			Putting It All Together
		The Type Checker
			Characters
			String Literals in Expressions
			String Literals Initializing Non-static Variables
			String Literals Initializing Static Variables
		TACKY Generation
			String Literals as Array Initializers
			String Literals in Expressions
			Top-Level Constants in TACKY
		Assembly Generation
			Operations on Characters
			Top-Level Constants
			The Complete Conversion from TACKY to Assembly
			Pseudo-Operand Replacement
			Instruction Fix-Up
		Code Emission
		Hello Again, World!
		Summary
	17. Supporting Dynamic Memory Allocation
		The void Type
		Memory Management with void *
		Complete and Incomplete Types
		The sizeof Operator
		The Lexer
		The Parser
		The Type Checker
			Conversions to and from void *
			Functions with void Return Types
			Scalar and Non-scalar Types
			Restrictions on Incomplete Types
			Extra Restrictions on void
			Conditional Expressions with void Operands
			Existing Validation for Arithmetic Expressions and Comparisons
			sizeof Expressions
		TACKY Generation
			Functions with void Return Types
			Casts to void
			Conditional Expressions with void Operands
			sizeof Expressions
			The Latest and Greatest TACKY IR
		Assembly Generation
		Summary
	18. Structures
		Declaring Structure Types
			Structure Member Declarations
			Tag and Member Namespaces
			Structure Type Declarations We Aren’t Implementing
		Operating on Structures
		Structure Layout in Memory
		The Lexer
		The Parser
		Semantic Analysis
			Resolving Structure Tags
			Type Checking Structures
		TACKY Generation
			Implementing the Member Access Operators
			Converting Compound Initializers to TACKY
		Structures in the System V Calling Convention
			Classifying Structures
			Passing Parameters of Structure Type
			Returning Structures
		Assembly Generation
			Extending the Assembly AST
			Copying Structures
			Using Structures in Function Calls
			Putting It All Together
			Replacing Pseudo-operands
		Code Emission
		Extra Credit: Unions
		Summary
		Additional Resources
Part III: Optimizations
	19. Optimizing Tacky Programs
		Safety and Observable Behavior
		Four TACKY Optimizations
			Constant Folding
			Unreachable Code Elimination
			Copy Propagation
			Dead Store Elimination
			With Our Powers Combined
		Testing the Optimization Passes
		Wiring Up the Optimization Stage
		Constant Folding
			Constant Folding for Part I TACKY Programs
			Supporting Part II TACKY Programs
		Control-Flow Graphs
			Defining the Control-Flow Graph
			Creating Basic Blocks
			Adding Edges to the Control-Flow Graph
			Converting a Control-Flow Graph to a List of Instructions
			Making Your Control-Flow Graph Code Reusable
		Unreachable Code Elimination
			Eliminating Unreachable Blocks
			Removing Useless Jumps
			Removing Useless Labels
			Removing Empty Blocks
		A Little Bit About Data-Flow Analysis
		Copy Propagation
			Reaching Copies Analysis
			Rewriting TACKY Instructions
			Supporting Part II TACKY Programs
		Dead Store Elimination
			Liveness Analysis
			Removing Dead Stores
			Supporting Part II TACKY Programs
		Summary
		Additional Resources
	20. Register Allocation
		Register Allocation in Action
			Take One: Put Everything on the Stack
			Take Two: Register Allocation
			Take Three: Register Allocation with Coalescing
		Updating the Compiler Pipeline
		Extending the Assembly AST
		Converting TACKY to Assembly
		Register Allocation by Graph Coloring
			Detecting Interference
			Spilling Registers
		The Basic Register Allocator
			Handling Multiple Types During Register Allocation
			Defining the Interference Graph
			Building the Interference Graph
			Calculating Spill Costs
			Coloring the Interference Graph
			Building the Register Map and Rewriting the Function Body
		Instruction Fix-Up with Callee-Saved Registers
		Code Emission
		Register Coalescing
			Updating the Interference Graph
			Conservative Coalescing
			Implementing Register Coalescing
		Summary
		Additional Resources
	Next Steps
		Add Some Missing Features
		Handle Undefined Behavior Safely
		Write More TACKY Optimizations
		Support Another Target Architecture
		Contribute to an Open Source Programming Language Project
		That’s a Wrap!
	A. Debugging Assembly Code With GDB or LLDB
		The Program
		Debugging with GDB
			Configuring the GDB UI
			Starting and Stopping the Program
			Printing Expressions
			Examining Memory
			Setting Conditional Breakpoints
			Getting Help
		Debugging with LLDB
			Starting and Stopping the Program
			Displaying Assembly Code
			Printing Expressions
			Examining Memory
			Setting Conditional Breakpoints
			Getting Help
	B. Assembly Generation and Code Emission Tables
		Part I
			Converting TACKY to Assembly
			Code Emission
		Part II
			Converting TACKY to Assembly
			Code Emission
		Part III
References
Index