Engineering a Compiler

Author： Cooper, Keith;Torczon, Linda

Publishers： Elsevier Science

Publishing year： 2011

ISBN： 9780080916613

Subject： [TP 自动化技术、计算机技术]

Language： ENG

Introduction

This entirely revised second edition of Engineering a Compiler is full of technical updates and new material covering the latest developments in compiler technology. In this comprehensive text you will learn important techniques for constructing a modern compiler. Leading educators and researchers Keith Cooper and Linda Torczon combine basic principles with pragmatic insights from their experience building state-of-the-art compilers. They will help you fully understand important techniques such as compilation of imperative and object-oriented languages, construction of static single assignment forms, instruction scheduling, and graph-coloring register allocation.

  • In-depth treatment of algorithms and techniques used in the front end of a modern compiler
  • Focus on code optimization and code generation, the primary areas of recent research and development
  • Improvements in presentation including conceptual overviews for each chapter, summaries and review questions for sections, and prominent placement of definitions for new terms
  • Examples drawn from several different programming languages

    • Chapter

  • Front Cover

  • About the Authors

  • Engineering a Compiler

  • Copyright

  • Dedication

  • About the Cover

  • Table of Contents

  • Preface to the Second Edition

  • Changes in the Second Edition

  • Organization

  • The Art and Science of Compilation

  • Approach

  • Philosophy

  • A Word About Programming Exercises

  • Additional Materials

  • Acknowledgments

  • Chapter 1. Overview of Compilation

  • 1.1 Introduction

  • Conceptual Roadmap

  • Overview

  • Why Study Compiler Construction?

  • The Fundamental Principles of Compilation

  • 1.2 Compiler Structure

  • May You Study in Interesting Times

  • 1.3 Overview of Translation

  • Notation

  • 1.3.1 The Front End

  • Checking Syntax

  • Intermediate Representations

  • Terminology

  • 1.3.2 The Optimizer

  • Analysis

  • Transformation

  • 1.3.3 The Back End

  • About ILOC

  • Instruction Selection

  • Register Allocation

  • Instruction Scheduling

  • Compiler Construction is Engineering

  • Interactions Among Code-Generation Components

  • 1.4 Summary and Perspective

  • Chapter Notes

  • Exercises

  • Chapter 2. Scanners

  • 2.1 Introduction

  • Conceptual Roadmap

  • Overview

  • 2.2 Recognizing Words

  • 2.2.1 A Formalism for Recognizers

  • 2.2.2 Recognizing More Complex Words

  • Section Review

  • 2.3 Regular Expressions

  • 2.3.1 Formalizing the Notation

  • Regular Expressions in Virtual Life

  • 2.3.2 Examples

  • 2.3.3 Closure Properties of REs

  • Programming Languages Versus Natural Languages

  • 2.4 From Regular Expression to Scanner

  • 2.4.1 Nondeterministic Finite Automata

  • Equivalence of NFAs and DFAs

  • 2.4.2 Regular Expression to NFA: Thompson's Construction

  • 2.4.3 NFA to DFA: The Subset Construction

  • Representing the Precedence of Operators

  • From Q to D

  • Example

  • Fixed-Point Computations

  • Computing Є-closure Offline

  • 2.4.4 DFA to Minimal DFA: Hopcroft's Algorithm

  • Examples

  • 2.4.5 Using a DFA as a Recognizer

  • Section Review

  • 2.5 Implementing Scanners

  • 2.5.1 Table-Driven Scanners

  • Avoiding Excess Roll Back

  • Generating the Transition and Classifier Tables

  • Changing Languages

  • 2.5.2 Direct-Coded Scanners

  • Representing Strings

  • Overhead of Table Lookup

  • Replacing the Table-Driven Scanner's While Loop

  • Classifying Characters

  • 2.5.3 Hand-Coded Scanners

  • Buffering the Input Stream

  • Generating Lexemes

  • 2.5.4 Handling Keywords

  • Section Review

  • 2.6 Advanced Topics

  • 2.6.1 DFA to Regular Expression

  • 2.6.2 Another Approach to DFA Minimization: Brzozowski's Algorithm

  • 2.6.3 Closure-Free Regular Expressions

  • 2.7 Chapter Summary and Perspective

  • Chapter Notes

  • Exercises

  • Chapter 3. Parsers

  • 3.1 Introduction

  • Conceptual Roadmap

  • Overview

  • 3.2 Expressing Syntax

  • 3.2.1 Why Not Regular Expressions?

  • 3.2.2 Context-Free Grammars

  • Backus-Naur Form

  • Context-Free Grammars

  • 3.2.3 More Complex Examples

  • 3.2.4 Encoding Meaning into Structure

  • Classes of Context-Free Grammars and Their Parsers

  • 3.2.5 Discovering a Derivation for an Input String

  • 3.3 Top-Down Parsing

  • 3.3.1 Transforming a Grammar for Top-Down Parsing

  • A Top-Down Parser with Oracular Choice

  • Eliminating Left Recursion

  • Backtrack-Free Parsing

  • Left-Factoring to Eliminate Backtracking

  • 3.3.2 Top-Down Recursive-Descent Parsers

  • Predictive Parsers Versus DFAs

  • 3.3.3 Table-Driven LL(1) Parsers

  • Section Review

  • 3.4 Bottom-Up Parsing

  • 3.4.1 The LR(1) Parsing Algorithm

  • Handle Finding

  • Parsing an Erroneous Input String

  • Using LR Parsers

  • Using More Lookahead

  • 3.4.2 Building LR(1) Tables

  • LR(1) Items

  • Constructing the Canonical Collection

  • The closure Procedure

  • The goto Procedure

  • The Algorithm

  • The Canonical Collection for the Parentheses Grammar

  • Filling in the Tables

  • Handle Finding, Revisited

  • 3.4.3 Errors in the Table Construction

  • Section Review

  • 3.5 Practical Issues

  • 3.5.1 Error Recovery

  • 3.5.2 Unary Operators

  • 3.5.3 Handling Context-Sensitive Ambiguity

  • 3.5.4 Left versus Right Recursion

  • Stack Depth

  • Associativity

  • Section Review

  • 3.6 Advanced Topics

  • 3.6.1 Optimizing a Grammar

  • 3.6.2 Reducing the Size of LR(1) Tables

  • Combining Rows or Columns

  • Shrinking the Grammar

  • Directly Encoding the Table

  • Using Other Construction Algorithms

  • 3.7 Summary and Perspective

  • Chapter Notes

  • Exercises

  • Chapter 4. Context-Sensitive Analysis

  • 4.1 Introduction

  • Conceptual Roadmap

  • Overview

  • 4.2 An Introduction to Type Systems

  • 4.2.1 The Purpose of Type Systems

  • Ensuring Runtime Safety

  • Improving Expressiveness

  • Generating Better Code

  • Type Checking

  • 4.2.2 Components of a Type System

  • Base Types

  • Numbers

  • Characters

  • Booleans

  • Compound and Constructed Types

  • Arrays

  • Strings

  • Enumerated Types

  • Structures and Variants

  • An Alternative View of Structures

  • Pointers

  • Type Equivalence

  • Representing Types

  • Inference Rules

  • Declarations and Inference

  • Classifying Type Systems

  • Inferring Types for Expressions

  • Interprocedural Aspects of Type Inference

  • Section Review

  • 4.3 The Attribute-Grammar Framework

  • 4.3.1 Evaluation Methods

  • 4.3.2 Circularity

  • 4.3.3 Extended Examples

  • Inferring Expression Types

  • A Simple Execution-Time Estimator

  • Improving the Execution-Cost Estimator

  • Back to Inferring Expression Types

  • A Final Improvement to the Execution-Cost Estimator

  • 4.3.4 Problems with the Attribute-Grammar Approach

  • Handling Nonlocal Information

  • Storage Management

  • Instantiating the Parse Tree

  • Locating the Answers

  • Breakdown of the Functional Paradigm

  • Section Review

  • 4.4 Ad Hoc Syntax-Directed Translation

  • 4.4.1 Implementing Ad Hoc Syntax-Directed Translation

  • Communicating between Actions

  • Naming Values

  • Actions at Other Points in the Parse

  • 4.4.2 Examples

  • Load Tracking, Revisited

  • Type Inference for Expressions, Revisited

  • Building an Abstract Syntax Tree

  • Generating ILOC for Expressions

  • Processing Declarations

  • What about Context-Sensitive Grammars?

  • Section Review

  • 4.5 Advanced Topics

  • 4.5.1 Harder Problems in Type Inference

  • Type-Consistent Uses and Constant Function Types

  • Type-Consistent Uses and Unknown Function Types

  • Dynamic Changes in Type

  • 4.5.2 Changing Associativity

  • 4.6 Summary and Perspective

  • Chapter Notes

  • Exercises

  • Chapter 5. Intermediate Representations

  • 5.1 Introduction

  • Conceptual Roadmap

  • Overview

  • 5.1.1 A Taxonomy of Intermediate Representations

  • 5.2 Graphical IRs

  • 5.2.1 Syntax-Related Trees

  • Parse Trees

  • Abstract Syntax Trees

  • Storage Efficiency and Graphical Representations

  • Directed Acyclic Graphs

  • Level of Abstraction

  • 5.2.2 Graphs

  • Control-Flow Graph

  • Dependence Graph

  • Call Graph

  • Section Review

  • 5.3 Linear IRs

  • 5.3.1 Stack-Machine Code

  • 5.3.2 Three-Address Code

  • 5.3.3 Representing Linear Codes

  • 5.3.4 Building a Control-Flow Graph from a Linear Code

  • 5.4 Mapping Values to Names

  • 5.4.1 Naming Temporary Values

  • 5.4.2 Static Single-Assignment Form

  • 5.4.3 Memory Models

  • 5.5 Symbol Tables

  • 5.5.1 Hash Tables

  • 5.5.2 Building a Symbol Table

  • An Alternative to Hashing

  • 5.5.3 Handling Nested Scopes

  • The Concept

  • The Details

  • 5.5.4 The Many Uses for Symbol Tables

  • Structure Table

  • Linked Tables for Name Resolution in an Object-Oriented Language

  • 5.5.5 Other Uses for Symbol Table Technology

  • Section Review

  • 5.6 Summary and Perspective

  • Chapter Notes

  • Exercises

  • Chapter 6. The Procedure Abstraction

  • 6.1 Introduction

  • Conceptual Roadmap

  • Overview

  • A Word About Time

  • 6.2 Procedure Calls

  • Control Flow in Object-Oriented Languages

  • More Complex Control Flow

  • Section Review

  • 6.3 Name Spaces

  • 6.3.1 Name Spaces of Algol-like Languages

  • Nested Lexical Scopes

  • Dynamic Scoping

  • Scope Rules across Various Languages

  • 6.3.2 Runtime Structures to Support Algol-like Languages

  • Local Storage

  • Reserving Space for Local Data

  • Initializing Variables

  • Space for Saved Register Values

  • Allocating Activation Records

  • Stack Allocation of Activation Records

  • Heap Allocation of Activation Records

  • Static Allocation of Activation Records

  • Coalescing Activation Records

  • 6.3.3 Name Spaces of Object-Oriented Languages

  • Terminology for Object-Oriented Languages

  • Visibility

  • Naming in the Class Hierarchy

  • Translating Java

  • 6.3.4 Runtime Structures to Support Object-Oriented Languages

  • Method Invocation

  • Object-Record Layout

  • Static versus Dynamic Dispatch

  • Method Caches

  • Multiple Inheritance

  • Section Review

  • 6.4 Communicating Values Between Procedures

  • 6.4.1 Passing Parameters

  • Call by Value

  • Call-by-Name Parameter Binding

  • Call by Reference

  • Space for Parameters

  • 6.4.2 Returning Values

  • 6.4.3 Establishing Addressability

  • Variables with Static Base Addresses

  • Variables with Dynamic Base Addresses

  • Local Variable of the Current Procedure

  • Local Variables of Other Procedures

  • Access Links

  • Global Display

  • Section Review

  • 6.5 Standardized Linkages

  • More about Time

  • Saving Registers

  • Allocating the Activation Record

  • Managing Displays and Access Links

  • Section Review

  • 6.6 Advanced Topics

  • 6.6.1 Explicit Heap Management

  • First-Fit Allocation

  • Arena-Based Allocation

  • Multipool Allocators

  • Debugging Help

  • 6.6.2 Implicit Deallocation

  • Reference Counting

  • Batch Collectors

  • Identifying Live Data

  • Mark-Sweep Collectors

  • Copying Collectors

  • Comparing the Techniques

  • 6.7 Summary and Perspective

  • Chapter Notes

  • Exercises

  • Chapter 7. Code Shape

  • 7.1 Introduction

  • Conceptual Roadmap

  • Overview

  • 7.2 Assigning Storage Locations

  • 7.2.1 Placing Runtime Data Structures

  • 7.2.2 Layout for Data Areas

  • A Primer on Cache Memories

  • Assigning Offsets

  • Relative Offsets and Cache Performance

  • 7.2.3 Keeping Values in Registers

  • Section Review

  • 7.3 Arithmetic Operators

  • 7.3.1 Reducing Demand for Registers

  • 7.3.2 Accessing Parameter Values

  • Generating Load Address Immediate

  • Commutativity, Associativity, and Number Systems

  • 7.3.3 Function Calls in an Expression

  • 7.3.4 Other Arithmetic Operators

  • 7.3.5 Mixed-Type Expressions

  • 7.3.6 Assignment as an Operator

  • Section Review

  • 7.4 Boolean and Relational Operators

  • 7.4.1 Representations

  • Numerical Encoding

  • Positional Encoding

  • 7.4.2 Hardware Support for Relational Operations

  • Short-Circuit Evaluation

  • Straight Condition Codes

  • Short-Circuit Evaluation as an Optimization

  • Conditional Move

  • Boolean-Valued Comparisons

  • Predicated Execution

  • Section Review

  • 7.5 Storing and Accessing Arrays

  • 7.5.1 Referencing a Vector Element

  • 7.5.2 Array Storage Layout

  • 7.5.3 Referencing an Array Element

  • Row-Major Order

  • Indirection Vectors

  • Accessing Array-Valued Parameters

  • 7.5.4 Range Checking

  • Section Review

  • 7.6 Character Strings

  • 7.6.1 String Representations

  • 7.6.2 String Assignment

  • 7.6.3 String Concatenation

  • 7.6.4 String Length

  • Section Review

  • 7.7 Structure References

  • 7.7.1 Understanding Structure Layouts

  • 7.7.2 Arrays of Structures

  • 7.7.3 Unions and Runtime Tags

  • 7.7.4 Pointers and Anonymous Values

  • Section Review

  • 7.8 Control-Flow Constructs

  • 7.8.1 Conditional Execution

  • Branch Prediction by Users

  • 7.8.2 Loops and Iteration

  • For Loops

  • FORTRAN's do Loop

  • While Loops

  • Until Loops

  • Expressing Iteration as Tail Recursion

  • Break Statements

  • 7.8.3 Case Statements

  • Linear Search

  • Directly Computing the Address

  • Binary Search

  • Section Review

  • 7.9 Procedure Calls

  • 7.9.1 Evaluating Actual Parameters

  • 7.9.2 Saving and Restoring Registers

  • Section Review

  • 7.10 Summary and Perspective

  • Chapter Notes

  • Exercises

  • Chapter 8. Introduction to Optimization

  • 8.1 Introduction

  • Conceptual Roadmap

  • Overview

  • 8.2 Background

  • 8.2.1 Examples

  • Improving an Array-Address Calculation

  • Improving a Loop Nest in LINPACK

  • 8.2.2 Considerations for Optimization

  • Safety

  • Defining Safety

  • Profitability

  • Risk

  • 8.2.3 Opportunities for Optimization

  • Section Review

  • 8.3 Scope of Optimization

  • Local Methods

  • Regional Methods

  • Global Methods

  • Intraprocedural Versus Interprocedural

  • Interprocedural Methods

  • Section Review

  • 8.4 Local Optimization

  • 8.4.1 Local Value Numbering

  • The Algorithm

  • The Importance of Order

  • Extending the Algorithm

  • The Role of Naming

  • The Impact of Indirect Assignments

  • Runtime Exceptions and Optimization

  • 8.4.2 Tree-Height Balancing

  • Finding Candidate Trees

  • Rebuilding the Block in Balanced Form

  • Examples

  • Section Review

  • 8.5 Regional Optimization

  • 8.5.1 Superlocal Value Numbering

  • 8.5.2 Loop Unrolling

  • Sources of Improvement and Degradation

  • Section Review

  • 8.6 Global Optimization

  • 8.6.1 Finding Uninitialized Variables with Live Information

  • Defining the Data-Flow Problem

  • Solving the Data-Flow Problem

  • Gathering Initial Information

  • Solving the Equations for LIVEOUT

  • Finding Uninitialized Variables

  • Other Uses for Live Variables

  • 8.6.2 Global Code Placement

  • Gathering Profile Data

  • Obtaining Profile Data

  • Constructing Chains as Hot Paths in the CFG

  • Performing Code Layout

  • A Final Example

  • Section Review

  • 8.7 Interprocedural Optimization

  • 8.7.1 Inline Substitution

  • The Transformation

  • The Decision Procedure

  • 8.7.2 Procedure Placement

  • Example

  • 8.7.3 Compiler Organization for Interprocedural Optimization

  • Section Review

  • 8.8 Summary and Perspective

  • Chapter Notes

  • Exercises

  • Chapter 9. Data-Flow Analysis

  • 9.1 Introduction

  • Conceptual Roadmap

  • Overview

  • 9.2 Iterative Data-Flow Analysis

  • 9.2.1 Dominance

  • Termination

  • Correctness

  • Efficiency

  • 9.2.2 Live-Variable Analysis

  • Naming Sets in Data-Flow Equations

  • Termination

  • Correctness

  • Static Analysis Versus Dynamic Analysis

  • Efficiency

  • 9.2.3 Limitations on Data-Flow Analysis

  • 9.2.4 Other Data-Flow Problems

  • Available Expressions

  • Reaching Definitions

  • Anticipable Expressions

  • Implementing Data-Flow Frameworks

  • Interprocedural Summary Problems

  • Section Review

  • 9.3 Static Single-Assignment Form

  • 9.3.1 A Simple Method for Building SSA Form

  • 9.3.2 Dominance Frontiers

  • Dominator Trees

  • Computing Dominance Frontiers

  • 9.3.3 Placing φ-Functions

  • Example

  • The Different Flavors of SSA Form

  • Efficiency Improvements

  • 9.3.4 Renaming

  • Example

  • A Final Improvement

  • 9.3.5 Translation Out of SSA Form

  • The Lost-Copy Problem

  • The Swap Problem

  • 9.3.6 Using SSA Form

  • Complexity

  • Optimism: The Role of Top

  • The Value of SSA Form

  • Section Review

  • 9.4 Interprocedural Analysis

  • 9.4.1 Call-Graph Construction

  • Procedure-Valued Variables

  • Contextually-Resolved Names

  • Other Language Issues

  • 9.4.2 Interprocedural Constant Propagation

  • Discovering an Initial Set of Constants

  • Propagating Known Constant Values around the Call Graph

  • Modeling Transmission of Values through Procedures

  • The Algorithm

  • Jump Function Implementation

  • Extending the Algorithm

  • Section Review

  • 9.5 Advanced Topics

  • 9.5.1 Structural Data-Flow Algorithms and Reducibility

  • 9.5.2 Speeding up the Iterative Dominance Framework

  • 9.6 Summary and Perspective

  • Chapter Notes

  • Exercises

  • Chapter 10. Scalar Optimizations

  • 10.1 Introduction

  • Conceptual Roadmap

  • Overview

  • Optimization Sequences

  • Optimization as Software Engineering

  • 10.2 Eliminating Useless and Unreachable Code

  • 10.2.1 Eliminating Useless Code

  • 10.2.2 Eliminating Useless Control Flow

  • 10.2.3 Eliminating Unreachable Code

  • Section Review

  • 10.3 Code Motion

  • 10.3.1 Lazy Code Motion

  • Code Shape

  • Available Expressions

  • Anticipable Expressions

  • Earliest Placement

  • Later Placement

  • Rewriting the Code

  • 10.3.2 Code Hoisting

  • Section Review

  • 10.4 Specialization

  • 10.4.1 Tail-Call Optimization

  • 10.4.2 Leaf-Call Optimization

  • 10.4.3 Parameter Promotion

  • Section Review

  • 10.5 Redundancy Elimination

  • 10.5.1 Value Identity versus Name Identity

  • 10.5.2 Dominator-based Value Numbering

  • Process the φ-Functions in B

  • Process the Assignments in B

  • Propagate Information to B’s Successors

  • Section Review

  • 10.6 Enabling Other Transformations

  • 10.6.1 Superblock Cloning

  • 10.6.2 Procedure Cloning

  • 10.6.3 Loop Unswitching

  • 10.6.4 Renaming

  • Section Review

  • The SSA Graph

  • 10.7 Advanced Topics

  • 10.7.1 Combining Optimizations

  • Subtleties in Evaluating and Rewriting Operations

  • Effectiveness

  • 10.7.2 Strength Reduction

  • Background

  • The Algorithm

  • Rewriting the Code

  • Back to the Example

  • Linear-Function Test Replacement

  • 10.7.3 Choosing an Optimization Sequence

  • 10.8 Summary and Perspective

  • Chapter Notes

  • Exercises

  • Chapter 11. Instruction Selection

  • 11.1 Introduction

  • Conceptual Roadmap

  • Overview

  • Selection, Scheduling, and Allocation

  • 11.2 Code Generation

  • 11.3 Extending the Simple Treewalk Scheme

  • Code Layout

  • Optimal Code Generation

  • Section Review

  • 11.4 Instruction Selection via Tree-Pattern Matching

  • 11.4.1 Rewrite Rules

  • 11.4.2 Finding a Tiling

  • Finding the Low-Cost Matches

  • 11.4.3 Tools

  • Section Review

  • 11.5 Instruction Selection via Peephole Optimization

  • 11.5.1 Peephole Optimization

  • Tree-Pattern Matching on Quads?

  • Recognizing Dead Values

  • Control-Flow Operations

  • Physical versus Logical Windows

  • 11.5.2 Peephole Transformers

  • RISC, CISC, and Instruction Selection

  • Section Review

  • 11.6 Advanced Topics

  • 11.6.1 Learning Peephole Patterns

  • 11.6.2 Generating Instruction Sequences

  • 11.7 Summary and Perspective

  • Chapter Notes

  • Exercises

  • Chapter 12. Instruction Scheduling

  • 12.1 Introduction

  • Conceptual Roadmap

  • Overview

  • Measuring Runtime Performance

  • 12.2 The Instruction-Scheduling Problem

  • Limitations to Scheduling

  • 12.2.1 Other Measures of Schedule Quality

  • Interactions between Scheduling and Allocation

  • 12.2.2 What Makes Scheduling Hard?

  • Section Review

  • 12.3 Local List Scheduling

  • 12.3.1 The Algorithm

  • 12.3.2 Scheduling Operations with Variable Delays

  • 12.3.3 Extending the Algorithm

  • 12.3.4 Tie Breaking in the List-Scheduling Algorithm

  • 12.3.5 Forward versus Backward List Scheduling

  • What about Out-of-Order Execution?

  • 12.3.6 Improving the Efficiency of List Scheduling

  • Section Review

  • 12.4 Regional Scheduling

  • 12.4.1 Scheduling Extended Basic Blocks

  • 12.4.2 Trace Scheduling

  • 12.4.3 Cloning for Context

  • Section Review

  • 12.5 Advanced Topics

  • 12.5.1 The Strategy of Software Pipelining

  • 12.5.2 An Algorithm for Software Pipelining

  • Estimating Kernel Size

  • Scheduling the Kernel

  • Generating Prologue and Epilogue Code

  • 12.6 Summary and Perspective

  • Chapter Notes

  • Exercises

  • Chapter 13. Register Allocation

  • 13.1 Introduction

  • Conceptual Roadmap

  • Overview

  • 13.2 Background Issues

  • 13.2.1 Memory versus Registers

  • 13.2.2 Allocation versus Assignment

  • 13.2.3 Register Classes

  • 13.3 Local Register Allocation and Assignment

  • 13.3.1 Top-Down Local Register Allocation

  • 13.3.2 Bottom-Up Local Register Allocation

  • 13.3.3 Moving Beyond Single Blocks

  • Liveness and Live Ranges

  • Complications at Block Boundaries

  • Section Review

  • 13.4 Global Register Allocation and Assignment

  • Graph Coloring

  • 13.4.1 Discovering Global Live Ranges

  • 13.4.2 Estimating Global Spill Costs

  • Accounting for Execution Frequencies

  • Negative Spill Costs

  • Infinite Spill Costs

  • 13.4.3 Interferences and the Interference Graph

  • Building the Interference Graph

  • Building an Allocator

  • 13.4.4 Top-Down Coloring

  • Handling Spills

  • Live-Range Splitting

  • 13.4.5 Bottom-Up Coloring

  • Why Does This Work?

  • 13.4.6 Coalescing Copies to Reduce Degree

  • 13.4.7 Comparing Top-Down and Bottom-Up Global Allocators

  • Linear Scan Allocation

  • 13.4.8 Encoding Machine Constraints in the Interference Graph

  • Multiregister Values

  • Specific Register Placement

  • Section Review

  • 13.5 Advanced Topics

  • 13.5.1 Variations on Graph-Coloring Allocation

  • Imprecise Interference Graphs

  • Breaking the Graph into Smaller Pieces

  • Conservative Coalescing

  • Spilling Partial Live Ranges

  • Live-Range Splitting

  • Rematerialization

  • Ambiguous Values

  • 13.5.2 Global Register Allocation over SSA Form

  • 13.6 Summary and Perspective

  • Chapter Notes

  • Exercises

  • Appendix A: ILOC

  • A.1 Introduction

  • A.2 Naming Conventions

  • A.3 Individual Operations

  • A.3.1 Arithmetic

  • A.3.2 Shifts

  • A.3.3 Memory Operations

  • A.3.4 Register-to-Register Copy Operations

  • A.4 Control-Flow Operations

  • A.4.1 Alternate Comparison and Branch Syntax

  • A.4.2 Jumps

  • A.5 Representing SSA Form

  • Appendix B: Data Structures

  • B.1 Introduction

  • B.2 Representing Sets

  • B.2.1 Representing Sets as Ordered Lists

  • B.2.2 Representing Sets as Bit Vectors

  • B.2.3 Representing Sparse Sets

  • B.3 Implementing Intermediate Representations

  • B.3.1 Graphical Intermediate Representations

  • Representing Trees

  • Mapping Trees to Binary Trees

  • Representing Arbitrary Graphs

  • B.3.2 Linear Intermediate Forms

  • Fortran-Style Array

  • List of Structures

  • B.4 Implementing Hash Tables

  • B.4.1 Choosing a Hash Function

  • Multiplicative Hash Functions

  • Organizing a Symbol Table

  • Universal Hash Functions

  • B.4.2 Open Hashing

  • The Perils of Poor Hash Functions

  • B.4.3 Open Addressing

  • B.4.4 Storing Symbol Records

  • B.4.5 Adding Nested Lexical Scopes

  • Adding Lexical Scopes to Open Hashing

  • Adding Lexical Scopes to Open Addressing

  • B.5 A Flexible Symbol-Table Design

  • Appendix Notes

  • Bibliography

  • Index

  • A

  • B

  • C

  • D

  • E

  • F

  • G

  • H

  • I

  • J

  • K

  • L

  • M

  • N

  • O

  • P

  • R

  • S

  • T

  • U

  • V

  • W

  • Z

    • 服务邮箱： whx@cnpiec.com.cn

    联系电话：010-65063046；65001305

    京ICP备09090397号-16 京公网安备 11010502049547号