Compilers Principles, Techniques, and Tools

, by Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D.

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9780321486813 | 0321486811
Cover: Hardcover
Copyright: 8/31/2006

Buy New

Currently Available, Usually Ships in 24-48 Hours

$203.56
eBook

Available Instantly

Online: 180 Days

Downloadable: 180 Days

$50.61

"This new edition of the classic "Dragon" book has been completely revised to include the most recent developments to compiling. The book provides a thorough introduction to compiler design and continues to emphasize the applicability of compiler technology to a broad range of problems in software design and development. The first hall of the book is designed for use in an undergraduate compilers course while the second half can be used in a graduate course stressing code optimization."--BOOK JACKET.

1 Introduction

(38)

1.1 Language Processors

(3)

1.1.1 Exercises for Section 1.1

(1)

1.2 The Structure of a Compiler

(8)

1.2.1 Lexical Analysis

(3)

1.2.2 Syntax Analysis

(1)

1.2.3 Semantic Analysis

(1)

1.2.4 Intermediate Code Generation

(1)

1.2.5 Code Optimization

(1)

1.2.6 Code Generation

(1)

1.2.7 Symbol-Table Management

(1)

1.2.8 The Grouping of Phases into Passes

(1)

1.2.9 Compiler-Construction Tools

(1)

1.3 Evolution of Programming Languages

(3)

1.3.1 The Move to Higher-level Languages

(1)

1.3.2 Impacts on Compilers

(1)

1.3.3 Exercises for Section 1.3

(1)

1.4 The Science of Building a Compiler

(2)

1.4.1 Modeling in Compiler Design and Implementation

(1)

1.4.2 The Science of Code Optimization

(2)

1.5 Applications of Compiler Technology

(8)

1.5.1 Implementation of High-Level Programming Languages

(2)

1.5.2 Optimizations for Computer Architectures

(2)

1.5.3 Design of New Computer Architectures

(1)

1.5.4 Program Translations

(1)

1.5.5 Software Productivity Tools

(2)

1.6 Language Basics

(11)

1.6.1 The Static/Dynamic Distinction

(1)

1.6.2 Environments and States

(2)

1.6.3 Static Scope and Block Structure

(3)

1.6.4. Explicit Access Control

(1)

1.6.5 Dynamic Scope

(2)

1.6.6 Parameter Passing Mechanisms

(2)

1.6.7 Aliasing

(1)

1.6.8 Exercises for Section 1.6

(1)

1.7 Summary of Chapter 1

(2)

1.8 References for Chapter 1

(1)

2 A Simple Syntax-Directed Translator

(70)

2.1 Introduction

(2)

2.2 Syntax Definition

(10)

2.2.1 Definition of Grammars

(2)

2.2.2 Derivations

(1)

2.2.3 Parse Trees

(2)

2.2.4 Ambiguity

(1)

2.2.5 Associativity of Operators

(1)

2.2.6 Precedence of Operators

(3)

2.2.7 Exercises for Section 2.2

(1)

2.3 Syntax-Directed Translation

(8)

2.3.1 Postfix Notation

(1)

2.3.2 Synthesized Attributes

(2)

2.3.3 Simple Syntax-Directed Definitions

(1)

2.3.4 Tree Traversals

(1)

2.3.5 Translation Schemes

(3)

2.3.6 Exercises for Section 2.3

(1)

2.4 Parsing

(8)

2.4.1 Top-Down Parsing

(3)

2.4.2 Predictive Parsing

(1)

2.4.3 When to Use E-Productions

(1)

2.4.4 Designing a Predictive Parser

(1)

2.4.5 Left Recursion

(1)

2.4.6 Exercises for Section 2.4

(1)

2.5 A Translator for Simple Expressions

(8)

2.5.1 Abstract and Concrete Syntax

(1)

2.5.2 Adapting the Translation Scheme

(2)

2.5.3 Procedures for the Nonterminals

(1)

2.5.4 Simplifying the Translator

(1)

2.5.5 The Complete Program

(2)

2.6 Lexical Analysis

(9)

2.6.1 Removal of White Space and Comments

(1)

2.6.2 Reading Ahead

(1)

2.6.3 Constants

(1)

2.6.4 Recognizing Keywords and Identifiers

(2)

2.6.5 A Lexical Analyzer

(3)

2.6.6 Exercises for Section 2.6

(1)

2.7 Symbol Tables

(6)

2.7.1 Symbol Table Per Scope

(3)

2.7.2 The Use of Symbol Tables

(2)

2.8 Intermediate Code Generation

(14)

2.8.1 Two Kinds of Intermediate Representations

(1)

2.8.2 Construction of Syntax Trees

(5)

2.8.3 Static Checking

(2)

2.8.4 Three-Address Code

(6)

2.8.5 Exercises for Section 2.8

105

(1)

2.9 Summary of Chapter 2

105

(4)

3 Lexical Analysis

109

(82)

3.1 The Role of the Lexical Analyzer

109

(6)

3.1.1 Lexical Analysis Versus Parsing

110

(1)

3.1.2 Tokens, Patterns, and Lexemes

111

(1)

3.1.3 Attributes for Tokens

112

(1)

3.1.4 Lexical Errors

113

(1)

3.1.5 Exercises for Section 3.1

114

(1)

3.2 Input Buffering

115

(1)

3.2.1 Buffer Pairs

115

(1)

3.2.2 Sentinels

116

(1)

3.3 Specification of Tokens

116

(12)

3.3.1 Strings and Languages

117

(2)

3.3.2 Operations on Languages

119

(1)

3.3.3 Regular Expressions

120

(3)

3.3.4 Regular Definitions

123

(1)

3.3.5 Extensions of Regular Expressions

124

(1)

3.3.6 Exercises for Section 3.3

125

(3)

3.4 Recognition of Tokens

128

(12)

3.4.1 Transition Diagrams

130

(2)

3.4.2 Recognition of Reserved Words and Identifiers

132

(1)

3.4.3 Completion of the Running Example

133

(1)

3.4.4 Architecture of a Transition-Diagram-Based Lexical Analyzer

134

(2)

3.4.5 Exercises for Section 3.4

136

(4)

3.5 The Lexical-Analyzer Generator Lex

140

(7)

3.5.1 Use of Lex

140

(1)

3.5.2 Structure of Lex Programs

141

(3)

3.5.3 Conflict Resolution in Lex

144

(1)

3.5.4 The Lookahead Operator

144

(2)

3.5.5 Exercises for Section 3.5

146

(1)

3.6 Finite Automata

147

(5)

3.6.1 Nondeterministic Finite Automata

147

(1)

3.6.2 Transition Tables

148

(1)

3.6.3 Acceptance of Input Strings by Automata

149

(1)

3.6.4 Deterministic Finite Automata

149

(2)

3.6.5 Exercises for Section 3.6

151

(1)

3.7 From Regular Expressions to Automata

152

(14)

3.7.1 Conversion of an NFA to a DFA

152

(4)

3.7.2 Simulation of an NFA

156

(1)

3.7.3 Efficiency of NFA Simulation

157

(2)

3.7.4 Construction of an NFA from a Regular Expression

159

(4)

3.7.5 Efficiency of String-Processing Algorithms

163

(3)

3.7.6 Exercises for Section 3.7

166

(1)

3.8 Design of a Lexical-Analyzer Generator

166

(7)

3.8.1 The Structure of the Generated Analyzer

167

(1)

3.8.2 Pattern Matching Based on NFA's

168

(2)

3.8.3 DFA's for Lexical Analyzers

170

(1)

3.8.4 Implementing the Lookahead Operator

171

(1)

3.8.5 Exercises for Section 3.8

172

(1)

3.9 Optimization of DFA-Based Pattern Matchers

173

(14)

3.9.1 Important States of an NFA

173

(2)

3.9.2 Functions Computed From the Syntax Tree

175

(1)

3.9.3 Computing nullable, firstpos, and lastpos

176

(1)

3.9.4 Computing followpos

177

(2)

3.9.5 Converting a Regular Expression Directly to a DFA

179

(1)

3.9.6 Minimizing the Number of States of a DFA

180

(4)

3.9.7 State Minimization in Lexical Analyzers

184

(1)

3.9.8 Trading Time for Space in DFA Simulation

185

(1)

3.9.9 Exercises for Section 3.9

186

(1)

3.10 Summary of Chapter 3

187

(2)

3.11 References for Chapter 3

189

(2)

4 Syntax Analysis

191

(112)

4.1 Introduction

192

(5)

4.1.1 The Role of the Parser

192

(1)

4.1.2 Representative Grammars

193

(1)

4.1.3 Syntax Error Handling

194

(1)

4.1.4 Error-Recovery Strategies

195

(2)

4.2 Context-Free Grammars

197

(12)

4.2.1 The Formal Definition of a Context-Free Grammar

197

(1)

4.2.2 Notational Conventions

198

(1)

4.2.3 Derivations

199

(2)

4.2.4 Parse Trees and Derivations

201

(2)

4.2.5 Ambiguity

203

(1)

4.2.6 Verifying the Language Generated by a Grammar

204

(1)

4.2.7 Context-Free Grammars Versus Regular Expressions

205

(1)

4.2.8 Exercises for Section 4.2

206

(3)

4.3 Writing a Grammar

209

(8)

4.3.1 Lexical Versus Syntactic Analysis

209

(1)

4.3.2 Eliminating Ambiguity

210

(2)

4.3.3 Elimination of Left Recursion

212

(2)

4.3.4 Left Factoring

214

(1)

4.3.5 Non-Context-Free Language Constructs

215

(1)

4.3.6 Exercises for Section 4.3

216

(1)

4.4 Top-Down Parsing

217

(16)

4.4.1 Recursive-Descent Parsing

219

(1)

4.4.2 FIRST and FOLLOW

220

(2)

4.4.3 LL(1) Grammars

222

(4)

4.4.4 Nonrecursive Predictive Parsing

226

(2)

4.4.5 Error Recovery in Predictive Parsing

228

(3)

4.4.6 Exercises for Section 4.4

231

(2)

4.5 Bottom-Up Parsing

233

(8)

4.5.1 Reductions

234

(1)

4.5.2 Handle Pruning

235

(1)

4.5.3 Shift-Reduce Parsing

236

(2)

4.5.4 Conflicts During Shift-Reduce Parsing

238

(2)

4.5.5 Exercises for Section 4.5

240

(1)

4.6 Introduction to LR Parsing: Simple LR

241

(18)

4.6.1 Why LR Parsers?

241

(1)

4.6.2 Items and the LR(0) Automaton

242

(6)

4.6.3 The LR-Parsing Algorithm

248

(4)

4.6.4 Constructing SLR-Parsing Tables

252

(4)

4.6.5 Viable Prefixes

256

(1)

4.6.6 Exercises for Section 4.6

257

(2)

4.7 More Powerful LR Parsers

259

(19)

4.7.1 Canonical LR(1) Items

260

(1)

4.7.2 Constructing LR(1) Sets of Items

261

(4)

4.7.3 Canonical LR(1) Parsing Tables

265

(1)

4.7.4 Constructing LALR Parsing Tables

266

(4)

4.7.5 Efficient Construction of LALR Parsing Tables

270

(5)

4.7.6 Compaction of LR Parsing Tables

275

(2)

4.7.7 Exercises for Section 4.7

277

(1)

4.8 Using Ambiguous Grammars

278

(9)

4.8.1 Precedence and Associativity to Resolve Conflicts

279

(2)

4.8.2 The "Dangling-Else" Ambiguity

281

(2)

4.8.3 Error Recovery in LR Parsing

283

(2)

4.8.4 Exercises for Section 4.8

285

(2)

4.9 Parser Generators

287

(10)

4.9.1 The Parser Generator Yacc

287

(4)

4.9.2 Using Yacc with Ambiguous Grammars

291

(3)

4.9.3 Creating Yacc Lexical Analyzers with Lex

294

(1)

4.9.4 Error Recovery in Yacc

295

(2)

4.9.5 Exercises for Section 4.9

297

(1)

4.10 Summary of Chapter 4

297

(3)

4.11 References for Chapter 4

300

(3)

5 Syntax-Directed Translation

303

(54)

5.1 Syntax-Directed Definitions

304

(6)

5.1.1 Inherited and Synthesized Attributes

304

(2)

5.1.2 Evaluating an SDD at the Nodes of a Parse Tree

306

(3)

5.1.3 Exercises for Section 5.1

309

(1)

5.2 Evaluation Orders for SDD's

310

(8)

5.2.1 Dependency Graphs

310

(2)

5.2.2 Ordering the Evaluation of Attributes

312

(1)

5.2.3 S-Attributed Definitions

312

(1)

5.2.4 L-Attributed Definitions

313

(1)

5.2.5 Semantic Rules with Controlled Side Effects

314

(3)

5.2.6 Exercises for Section 5.2

317

(1)

5.3 Applications of Syntax-Directed Translation

318

(6)

5.3.1 Construction of Syntax Trees

318

(3)

5.3.2 The Structure of a Type

321

(2)

5.3.3 Exercises for Section 5.3

323

(1)

5.4 Syntax-Directed Translation Schemes

324

(13)

5.4.1 Postfix Translation Schemes

324

(1)

5.4.2 Parser-Stack Implementation of Postfix SDT's

325

(2)

5.4.3 SDT's With Actions Inside Productions

327

(1)

5.4.4 Eliminating Left Recursion From SDT's

328

(3)

5.4.5 SDT's for L-Attributed Definitions

331

(5)

5.4.6 Exercises for Section 5.4

336

(1)

5.5 Implementing L-Attributed SDD's

337

(16)

5.5.1 Translation During Recursive-Descent Parsing

338

(2)

5.5.2 On-The-Fly Code Generation

340

(3)

5.5.3 L-Attributed SDD's and LL Parsing

343

(5)

5.5.4 Bottom-Up Parsing of L-Attributed SDD's

348

(4)

5.5.5 Exercises for Section 5.5

352

(1)

5.6 Summary of Chapter 5

353

(1)

5.7 References for Chapter 5

354

(3)

6 Intermediate-Code Generation

357

(70)

6.1 Variants of Syntax Trees

358

(5)

6.1.1 Directed Acyclic Graphs for Expressions

359

(1)

6.1.2 The Value-Number Method for Constructing DAG's

360

(2)

6.1.3 Exercises for Section 6.1

362

(1)

6.2 Three-Address Code

363

(7)

6.2.1 Addresses and Instructions

364

(2)

6.2.2 Quadruples

366

(1)

6.2.3 Triples

367

(2)

6.2.4 Static Single-Assignment Form

369

(1)

6.2.5 Exercises for Section 6.2

370

(1)

6.3 Types and Declarations

370

(8)

6.3.1 Type Expressions

371

(1)

6.3.2 Type Equivalence

372

(1)

6.3.3 Declarations

373

(1)

6.3.4 Storage Layout for Local Names

373

(3)

6.3.5 Sequences of Declarations

376

(1)

6.3.6 Fields in Records and Classes

376

(2)

6.3.7 Exercises for Section 6.3

378

(1)

6.4 Translation of Expressions

378

(8)

6.4.1 Operations Within Expressions

378

(2)

6.4.2 Incremental Translation

380

(1)

6.4.3 Addressing Array Elements

381

(2)

6.4.4 Translation of Array References

383

(1)

6.4.5 Exercises for Section 6.4

384

(2)

6.5 Type Checking

386

(13)

6.5.1 Rules for Type Checking

387

(1)

6.5.2 Type Conversions

388

(2)

6.5.3 Overloading of Functions and Operators

390

(1)

6.5.4 Type Inference and Polymorphic Functions

391

(4)

6.5.5 An Algorithm for Unification

395

(3)

6.5.6 Exercises for Section 6.5

398

(1)

6.6 Control Flow

399

(11)

6.6.1 Boolean Expressions

399

(1)

6.6.2 Short-Circuit Code

400

(1)

6.6.3 Flow-of-Control Statements

401

(2)

6.6.4 Control-Flow Translation of Boolean Expressions

403

(2)

6.6.5 Avoiding Redundant Gotos

405

(3)

6.6.6 Boolean Values and Jumping Code

408

(1)

6.6.7 Exercises for Section 6.6

408

(2)

6.7 Backpatching

410

(8)

6.7.1 One-Pass Code Generation Using Backpatching

410

(1)

6.7.2 Backpatching for Boolean Expressions

411

(2)

6.7.3 Flow-of-Control Statements

413

(3)

6.7.4 Break-, Continue-, and Goto-Statements

416

(1)

6.7.5 Exercises for Section 6.7

417

(1)

6.8 Switch-Statements

418

(4)

6.8.1 Translation of Switch-Statements

419

(1)

6.8.2 Syntax-Directed Translation of Switch-Statements

420

(1)

6.8.3 Exercises for Section 6.8

421

(1)

6.9 Intermediate Code for Procedures

422

(2)

6.10 Summary of Chapter 6

424

(1)

6.11 References for Chapter 6

425

(2)

7 Run-Time Environments

427

(78)

7.1 Storage Organization

427

(3)

7.1.1 Static Versus Dynamic Storage Allocation

429

(1)

7.2 Stack Allocation of Space

430

(11)

7.2.1 Activation Trees

430

(3)

7.2.2 Activation Records

433

(3)

7.2.3 Calling Sequences

436

(2)

7.2.4 Variable-Length Data on the Stack

438

(2)

7.2.5 Exercises for Section 7.2

440

(1)

7.3 Access to Nonlocal Data on the Stack

441

(11)

7.3.1 Data Access Without Nested Procedures

442

(1)

7.3.2 Issues With Nested Procedures

442

(1)

7.3.3 A Language With Nested Procedure Declarations

443

(1)

7.3.4 Nesting Depth

443

(2)

7.3.5 Access Links

445

(2)

7.3.6 Manipulating Access Links

447

(1)

7.3.7 Access Links for Procedure Parameters

448

(1)

7.3.8 Displays

449

(2)

7.3.9 Exercises for Section 7.3

451

(1)

7.4 Heap Management

452

(11)

7.4.1 The Memory Manager

453

(1)

7.4.2 The Memory Hierarchy of a Computer

454

(1)

7.4.3 Locality in Programs

455

(2)

7.4.4 Reducing Fragmentation

457

(3)

7.4.5 Manual Deallocation Requests

460

(3)

7.4.6 Exercises for Section 7.4

463

(1)

7.5 Introduction to Garbage Collection

463

(7)

7.5.1 Design Goals for Garbage Collectors

464

(2)

7.5.2 Reachability

466

(2)

7.5.3 Reference Counting Garbage Collectors

468

(2)

7.5.4 Exercises for Section 7.5

470

(1)

7.6 Introduction to Trace-Based Collection

470

(13)

7.6.1 A Basic Mark-and-Sweep Collector

471

(2)

7.6.2 Basic Abstraction

473

(2)

7.6.3 Optimizing Mark-and-Sweep

475

(1)

7.6.4 Mark-and-Compact Garbage Collectors

476

(2)

7.6.5 Copying collectors

478

(4)

7.6.6 Comparing Costs

482

(1)

7.6.7 Exercises for Section 7.6

482

(1)

7.7 Short-Pause Garbage Collection

483

(11)

7.7.1 Incremental Garbage Collection

483

(2)

7.7.2 Incremental Reachability Analysis

485

(2)

7.7.3 Partial-Collection Basics

487

(1)

7.7.4 Generational Garbage Collection

488

(2)

7.7.5 The Train Algorithm

490

(3)

7.7.6 Exercises for Section 7.7

493

(1)

7.8 Advanced Topics in Garbage Collection

494

(6)

7.8.1 Parallel and Concurrent Garbage Collection

495

(2)

7.8.2 Partial Object Relocation

497

(1)

7.8.3 Conservative Collection for Unsafe Languages

498

(1)

7.8.4 Weak References

498

(1)

7.8.5 Exercises for Section 7.8

499

(1)

7.9 Summary of Chapter 7

500

(2)

7.10 References for Chapter 7

502

(3)

8 Code Generation

505

(78)

8.1 Issues in the Design of a Code Generator

506

(6)

8.1.1 Input to the Code Generator

507

(1)

8.1.2 The Target Program

507

(1)

8.1.3 Instruction Selection

508

(2)

8.1.4 Register Allocation

510

(1)

8.1.5 Evaluation Order

511

(1)

8.2 The Target Language

512

(6)

8.2.1 A Simple Target Machine Model

512

(3)

8.2.2 Program and Instruction Costs

515

(1)

8.2.3 Exercises for Section 8.2

516

(2)

8.3 Addresses in the Target Code

518

(7)

8.3.1 Static Allocation

518

(2)

8.3.2 Stack Allocation

520

(2)

8.3.3 Run-Time Addresses for Names

522

(2)

8.3.4 Exercises for Section 8.3

524

(1)

8.4 Basic Blocks and Flow Graphs

525

(8)

8.4.1 Basic Blocks

526

(2)

8.4.2 Next-Use Information

528

(1)

8.4.3 Flow Graphs

529

(1)

8.4.4 Representation of Flow Graphs

530

(1)

8.4.5 Loops

531

(1)

8.4.6 Exercises for Section 8.4

531

(2)

8.5 Optimization of Basic Blocks

533

(9)

8.5.1 The DAG Representation of Basic Blocks

533

(1)

8.5.2 Finding Local Common Subexpressions

534

(1)

8.5.3 Dead Code Elimination

535

(1)

8.5.4 The Use of Algebraic Identities

536

(1)

8.5.5 Representation of Array References

537

(2)

8.5.6 Pointer Assignments and Procedure Calls

539

(1)

8.5.7 Reassembling Basic Blocks From DAG's

539

(2)

8.5.8 Exercises for Section 8.5

541

(1)

8.6 A Simple Code Generator

542

(7)

8.6.1 Register and Address Descriptors

543

(1)

8.6.2 The Code-Generation Algorithm

544

(3)

8.6.3 Design of the Function getReg

547

(1)

8.6.4 Exercises for Section 8.6

548

(1)

8.7 Peephole Optimization

549

(4)

8.7.1 Eliminating Redundant Loads and Stores

550

(1)

8.7.2 Eliminating Unreachable Code

550

(1)

8.7.3 Flow-of-Control Optimizations

551

(1)

8.7.4 Algebraic Simplification and Reduction in Strength

552

(1)

8.7.5 Use of Machine Idioms

552

(1)

8.7.6 Exercises for Section 8.7

553

(1)

8.8 Register Allocation and Assignment

553

(5)

8.8.1 Global Register Allocation

553

(1)

8.8.2 Usage Counts

554

(2)

8.8.3 Register Assignment for Outer Loops

556

(1)

8.8.4 Register Allocation by Graph Coloring

556

(1)

8.8.5 Exercises for Section 8.8

557

(1)

8.9 Instruction Selection by Tree Rewriting

558

(9)

8.9.1 Tree-Translation Schemes

558

(2)

8.9.2 Code Generation by Tiling an Input Tree

560

(3)

8.9.3 Pattern Matching by Parsing

563

(2)

8.9.4 Routines for Semantic Checking

565

(1)

8.9.5 General Tree Matching

565

(2)

8.9.6 Exercises for Section 8.9

567

(1)

8.10 Optimal Code Generation for Expressions

567

(6)

8.10.1 Ershov Numbers

567

(1)

8.10.2 Generating Code From Labeled Expression Trees

568

(2)

8.10.3 Evaluating Expressions with an Insufficient Supply of Registers

570

(2)

8.10.4 Exercises for Section 8.10

572

(1)

8.11 Dynamic Programming Code-Generation

573

(5)

8.11.1 Contiguous Evaluation

574

(1)

8.11.2 The Dynamic Programming Algorithm

575

(2)

8.11.3 Exercises for Section 8.11

577

(1)

8.12 Summary of Chapter 8

578

(1)

8.13 References for Chapter 8

579

(4)

9 Machine-Independent Optimizations

583

(124)

9.1 The Principal Sources of Optimization

584

(13)

9.1.1 Causes of Redundancy

584

(1)

9.1.2 A Running Example: Quicksort

585

(1)

9.1.3 Semantics-Preserving Transformations

586

(2)

9.1.4 Global Common Subexpressions

588

(2)

9.1.5 Copy Propagation

590

(1)

9.1.6 Dead-Code Elimination

591

(1)

9.1.7 Code Motion

592

(1)

9.1.8 Induction Variables and Reduction in Strength

592

(4)

9.1.9 Exercises for Section 9.1

596

(1)

9.2 Introduction to Data-Flow Analysis

597

(21)

9.2.1 The Data-Flow Abstraction

597

(2)

9.2.2 The Data-Flow Analysis Schema

599

(1)

9.2.3 Data-Flow Schemas on Basic Blocks

600

(1)

9.2.4 Reaching Definitions

601

(7)

9.2.5 Live-Variable Analysis

608

(2)

9.2.6 Available Expressions

610

(4)

9.2.7 Summary

614

(1)

9.2.8 Exercises for Section 9.2

615

(3)

9.3 Foundations of Data-Flow Analysis

618

(14)

9.3.1 Semilattices

618

(5)

9.3.2 Transfer Functions

623

(3)

9.3.3 The Iterative Algorithm for General Frameworks

626

(2)

9.3.4 Meaning of a Data-Flow Solution

628

(3)

9.3.5 Exercises for Section 9.3

631

(1)

9.4 Constant Propagation

632

(7)

9.4.1 Data-Flow Values for the Constant-Propagation Frame-work

633

(1)

9.4.2 The Meet for the Constant-Propagation Framework

633

(1)

9.4.3 Transfer Functions for the Constant-Propagation Frame-work

634

(1)

9.4.4 Monotonicity of the Constant-Propagation Framework

635

(1)

9.4.5 Nondistributivity of the Constant-Propagation Framework

635

(2)

9.4.6 Interpretation of the Results

637

(1)

9.4.7 Exercises for Section 9.4

637

(2)

9.5 Partial-Redundancy Elimination

639

(16)

9.5.1 The Sources of Redundancy

639

(3)

9.5.2 Can All Redundancy Be Eliminated?

642

(2)

9.5.3 The Lazy-Code-Motion Problem

644

(1)

9.5.4 Anticipation of Expressions

645

(1)

9.5.5 The Lazy-Code-Motion Algorithm

646

(9)

9.5.6 Exercises for Section 9.5

655

(1)

9.6 Loops in Flow Graphs

655

(17)

9.6.1 Dominators

656

(4)

9.6.2 Depth-First Ordering

660

(1)

9.6.3 Edges in a Depth-First Spanning Tree

661

(1)

9.6.4 Back Edges and Reducibility

662

(3)

9.6.5 Depth of a Flow Graph

665

(1)

9.6.6 Natural Loops

665

(2)

9.6.7 Speed of Convergence of Iterative Data-Flow Algorithms

667

(2)

9.6.8 Exercises for Section 9.6

669

(3)

9.7 Region-Based Analysis

672

(14)

9.7.1 Regions

672

(1)

9.7.2 Region Hierarchies for Reducible Flow Graphs

673

(3)

9.7.3 Overview of a Region-Based Analysis

676

(2)

9.7.4 Necessary Assumptions About Transfer Functions

678

(2)

9.7.5 An Algorithm for Region-Based Analysis

680

(4)

9.7.6 Handling Nonreducible Flow Graphs

684

(2)

9.7.7 Exercises for Section 9.7

686

(1)

9.8 Symbolic Analysis

686

(14)

9.8.1 Affine Expressions of Reference Variables

687

(2)

9.8.2 Data-Flow Problem Formulation

689

(5)

9.8.3 Region-Based Symbolic Analysis

694

(5)

9.8.4 Exercises for Section 9.8

699

(1)

9.9 Summary of Chapter 9

700

(3)

9.10 References for Chapter 9

703

(4)

10 Instruction-Level Parallelism

707

(62)

10.1 Processor Architectures

708

(2)

10.1.1 Instruction Pipelines and Branch Delays

708

(1)

10.1.2 Pipelined Execution

709

(1)

10.1.3 Multiple Instruction Issue

710

(1)

10.2 Code-Scheduling Constraints

710

(11)

10.2.1 Data Dependence

711

(1)

10.2.2 Finding Dependences Among Memory Accesses

712

(1)

10.2.3 Tradeoff Between Register Usage and Parallelism

713

(3)

10.2.4 Phase Ordering Between Register Allocation and Code Scheduling

716

(1)

10.2.5 Control Dependence

716

(1)

10.2.6 Speculative Execution Support

717

(2)

10.2.7 A Basic Machine Model

719

(1)

10.2.8 Exercises for Section 10.2

720

(1)

10.3 Basic-Block Scheduling

721

(6)

10.3.1 Data-Dependence Graphs

722

(1)

10.3.2 List Scheduling of Basic Blocks

723

(2)

10.3.3 Prioritized Topological Orders

725

(1)

10.3.4 Exercises for Section 10.3

726

(1)

10.4 Global Code Scheduling

727

(11)

10.4.1 Primitive Code Motion

728

(2)

10.4.2 Upward Code Motion

730

(1)

10.4.3 Downward Code Motion

731

(1)

10.4.4 Updating Data Dependences

732

(1)

10.4.5 Global Scheduling Algorithms

732

(4)

10.4.6 Advanced Code Motion Techniques

736

(1)

10.4.7 Interaction with Dynamic Schedulers

737

(1)

10.4.8 Exercises for Section 10.4

737

(1)

10.5 Software Pipelining

738

(27)

10.5.1 Introduction

738

(2)

10.5.2 Software Pipelining of Loops

740

(3)

10.5.3 Register Allocation and Code Generation

743

(1)

10.5.4 Do-Across Loops

743

(2)

10.5.5 Goals and Constraints of Software Pipelining

745

(4)

10.5.6 A Software-Pipelining Algorithm

749

(1)

10.5.7 Scheduling Acyclic Data-Dependence Graphs

749

(2)

10.5.8 Scheduling Cyclic Dependence Graphs

751

(7)

10.5.9 Improvements to the Pipelining Algorithms

758

(1)

10.5.10 Modular Variable Expansion

758

(3)

10.5.11 Conditional Statements

761

(1)

10.5.12 Hardware Support for Software Pipelining

762

(1)

10.5.13 Exercises for Section 10.5

763

(2)

10.6 Summary of Chapter 10

765

(1)

10.7 References for Chapter 10

766

(3)

11 Optimizing for Parallelism and Locality

769

(134)

11.1 Basic Concepts

771

(11)

11.1.1 Multiprocessors

772

(1)

11.1.2 Parallelism in Applications

773

(2)

11.1.3 Loop-Level Parallelism

775

(2)

11.1.4 Data Locality

777

(1)

11.1.5 Introduction to Affine Transform Theory

778

(4)

11.2 Matrix Multiply: An In-Depth Example

782

(6)

11.2.1 The Matrix-Multiplication Algorithm

782

(3)

11.2.2 Optimizations

785

(3)

11.2.3 Cache Interference

788

(1)

11.2.4 Exercises for Section 11.2

788

(1)

11.3 Iteration Spaces

788

(13)

11.3.1 Constructing Iteration Spaces from Loop Nests

788

(3)

11.3.2 Execution Order for Loop Nests

791

(1)

11.3.3 Matrix Formulation of Inequalities

791

(2)

11.3.4 Incorporating Symbolic Constants

793

(1)

11.3.5 Controlling the Order of Execution

793

(5)

11.3.6 Changing Axes

798

(1)

11.3.7 Exercises for Section 11.3

799

(2)

11.4 Affine Array Indexes

801

(3)

11.4.1 Affine Accesses

802

(1)

11.4.2 Affine and Nonaffine Accesses in Practice

803

(1)

11.4.3 Exercises for Section 11.4

804

(1)

11.5 Data Reuse

804

(11)

11.5.1 Types of Reuse

805

(1)

11.5.2 Self Reuse

806

(3)

11.5.3 Self-Spatial Reuse

809

(2)

11.5.4 Group Reuse

811

(3)

11.5.5 Exercises for Section 11.5

814

(1)

11.6 Array Data-Dependence Analysis

815

(13)

11.6.1 Definition of Data Dependence of Array Accesses

816

(1)

11.6.2 Integer Linear Programming

817

(1)

11.6.3 The GCD Test

818

(2)

11.6.4 Heuristics for Solving Integer Linear Programs

820

(3)

11.6.5 Solving General Integer Linear Programs

823

(2)

11.6.6 Summary

825

(1)

11.6.7 Exercises for Section 11.6

826

(2)

11.7 Finding Synchronization-Free Parallelism

828

(25)

11.7.1 An Introductory Example

828

(2)

11.7.2 Affine Space Partitions

830

(1)

11.7.3 Space-Partition Constraints

831

(4)

11.7.4 Solving Space-Partition Constraints

835

(3)

11.7.5 A Simple Code-Generation Algorithm

838

(3)

11.7.6 Eliminating Empty Iterations

841

(3)

11.7.7 Eliminating Tests from Innermost Loops

844

(2)

11.7.8 Source-Code Transforms

846

(5)

11.7.9 Exercises for Section 11.7

851

(2)

11.8 Synchronization Between Parallel Loops

853

(8)

11.8.1 A Constant Number of Synchronizations

853

(1)

11.8.2 Program-Dependence Graphs

854

(3)

11.8.3 Hierarchical Time

857

(2)

11.8.4 The Parallelization Algorithm

859

(1)

11.8.5 Exercises for Section 11.8

860

(1)

11.9 Pipelining

861

(23)

11.9.1 What is Pipelining'?

861

(2)

11.9.2 Successive Over-Relaxation (SOR): An Example

863

(1)

11.9.3 Fully Permutable Loops

864

(1)

11.9.4 Pipelining Fully Permutable Loops

864

(3)

11.9.5 General Theory

867

(1)

11.9.6 Time-Partition Constraints

868

(4)

11.9.7 Solving Time-Partition Constraints by Farkas' Lemma

872

(3)

11.9.8 Code Transformations

875

(5)

11.9.9 Parallelism With Minimum Synchronization

880

(2)

11.9.10 Exercises for Section 11.9

882

(2)

11.10 Locality Optimizations

884

(9)

11.10.1 Temporal Locality of Computed Data

885

(1)

11.10.2 Array Contraction

885

(2)

11.10.3 Partition Interleaving

887

(3)

11.10.4 Putting it All Together

890

(2)

11.10.5 Exercises for Section 11.10

892

(1)

11.11 Other Uses of Affine Transforms

893

(4)

11.11.1 Distributed memory machines

894

(1)

11.11.2 Multi-Instruction-Issue Processors

895

(1)

11.11.3 Vector and SIMD Instructions

895

(1)

11.11.4 Prefetching

896

(1)

11.12 Summary of Chapter 11

897

(2)

11.13 References for Chapter 11

899

(4)

12 Interprocedural Analysis

903

(62)

12.1 Basic Concepts

904

(12)

12.1.1 Call Graphs

904

(2)

12.1.2 Context Sensitivity

906

(2)

12.1.3 Call Strings

908

(2)

12.1.4 Cloning-Based Context-Sensitive Analysis

910

(1)

12.1.5 Summary-Based Context-Sensitive Analysis

911

(3)

12.1.6 Exercises for Section 12.1

914

(2)

12.2 Why Interprocedural Analysis?

916

(5)

12.2.1 Virtual Method Invocation

916

(1)

12.2.2 Pointer Alias Analysis

917

(1)

12.2.3 Parallelization

917

(1)

12.2.4 Detection of Software Errors and Vulnerabilities

917

(1)

12.2.5 SQL Injection

918

(2)

12.2.6 Buffer Overflow

920

(1)

12.3 A Logical Representation of Data Flow

921

(12)

12.3.1 Introduction to Datalog

921

(1)

12.3.2 Datalog Rules

922

(2)

12.3.3 Intensional and Extensional Predicates

924

(3)

12.3.4 Execution of Datalog Programs

927

(1)

12.3.5 Incremental Evaluation of Datalog Programs

928

(2)

12.3.6 Problematic Datalog Rules

930

(2)

12.3.7 Exercises for Section 12.3

932

(1)

12.4 A Simple Pointer-Analysis Algorithm

933

(8)

12.4.1 Why is Pointer Analysis Difficult

934

(1)

12.4.2 A Model for Pointers and References

935

(1)

12.4.3 Flow Insensitivity

936

(1)

12.4.4 The Formulation in Datalog

937

(1)

12.4.5 Using Type Information

938

(1)

12.4.6 Exercises for Section 12.4

939

(2)

12.5 Context-Insensitive Interprocedural Analysis

941

(4)

12.5.1 Effects of a Method Invocation

941

(2)

12.5.2 Call Graph Discovery in Datalog

943

(1)

12.5.3 Dynamic Loading and Reflection

944

(1)

12.5.4 Exercises for Section 12.5

945

(1)

12.6 Context-Sensitive Pointer Analysis

945

(6)

12.6.1 Contexts and Call Strings

946

(3)

12.6.2 Adding Context to Datalog Rules

949

(1)

12.6.3 Additional Observations About Sensitivity

949

(1)

12.6.4 Exercises for Section 12.6

950

(1)

12.7 Datalog Implementation by BDD's

951

(7)

12.7.1 Binary Decision Diagrams

951

(2)

12.7.2 Transformations on BDD's

953

(1)

12.7.3 Representing Relations by BDD's

954

(1)

12.7.4 Relational Operations as BDD Operations

954

(3)

12.7.5 Using BDD's for Points-to Analysis

957

(1)

12.7.6 Exercises for Section 12.7

958

(1)

12.8 Summary of Chapter 12

958

(3)

12.9 References for Chapter 12

961

(4)

A A Complete Front End

965

(24)

A.1 The Source Language

965

(1)

A.2 Main

966

(1)

A.3 Lexical Analyzer

967

(3)

A.4 Symbol Tables and Types

970

(1)

A.5 Intermediate Code for Expressions

971

(3)

A.6 Jumping Code for Boolean Expressions

974

(4)

A.7 Intermediate Code for Statements

978

(3)

A.8 Parser

981

(5)

A.9 Creating the Front End

986

(3)

B Finding Linearly Independent Solutions

989

(4)

Index

993

Please wait while the item is added to your bag...

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Compilers Principles, Techniques, and Tools

Summary

Author Biography

Table of Contents

Supplemental Materials