Writing a C Compiler Early Access 1st Edition by Nora Sandler ISBN 9781718500433 1718500432

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!

Appendix 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

Appendix 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