编译原理 英文版 第2版PDF|Epub|txt|kindle电子书版本网盘下载

编译原理 英文版 第2版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1 Introduction1

1.1 Language Processors1

1.1.1 Exercises for Section 1.13

1.2 The Structure of a Compiler4

1.2.1 Lexical Analysis5

1.2.2 Syntax Analysis8

1.2.3 Semantic Analysis8

1.2.4 Intermediate Code Generation9

1.2.5 Code Optimization10

1.2.6 Code Generation10

1.2.7 Symbol-Table Management11

1.2.8 The Grouping of Phases into Passes11

1.2.9 Compiler-Construction Tools12

1.3 The Evolution of Programming Languages12

1.3.1 The Move to Higher-level Languages13

1.3.2 Impacts on Compilers14

1.3.3 Exercises for Section 1.314

1.4 The Science of Building a Compiler15

1.4.1 Modeling in Compiler Design and Implementation15

1.4.2 The Science of Code Optimization15

1.5 Applications of Compiler Technology17

1.5.1 Implementation of High-Level Programming Languages17

1.5.2 Optimizations for Computer Architectures19

1.5.3 Design of New Computer Architectures21

1.5.4 Program Translations22

1.5.5 Software Productivity Tools23

1.6 Programming Language Basics25

1.6.1 The Static/Dynamic Distinction25

1.6.2 Environments and States26

1.6.3 Static Scope and Block Structure28

1.6.4 Explicit Access Control31

1.6.5 Dynamic Scope31

1.6.6 Parameter Passing Mechanisms33

1.6.7 Aliasing35

1.6.8 Exercises for Section 1.635

1.7 Summary of Chapter 136

1.8 References for Chapter 138

2 A Simple Syntax-Directed Translator39

2.1 Introduction40

2.2 Syntax Definition42

2.2.1 Definition of Grammars42

2.2.2 Derivations44

2.2.3 Parse Trees45

2.2.4 Ambiguity47

2.2.5 Associativity of Operators48

2.2.6 Precedence of Operators48

2.2.7 Exercises for Section 2.251

2.3 Syntax-Directed Transiation52

2.3.1 Postfix Notation53

2.3.2 Synthesized Attributes54

2.3.3 Simple Syntax-Directed Definitions56

2.3.4 Tree Traversals56

2.3.5 Translation Schemes57

2.3.6 Exercises for Section 2.360

2.4 Parsing60

2.4.1 Top-Down Parsing61

2.4.2 Predictive Parsing64

2.4.3 When to Use 6-Productions65

2.4.4 Designing a Predictive Parser66

2.4.5 Left Recursion67

2.4.6 Exercises for Section 2.468

2.5 A Translator for Simple Expressions68

2.5.1 Abstract and Concrete Syntax69

2.5.2 Adapting the Translation Scheme70

2.5.3 Procedures for the Nonterminals72

2.5.4 Simplifying the Translator73

2.5.5 The Complete Program74

2.6 Lexical Analysis76

2.6.1 Removal of White Space and Comments77

2.6.2 Reading Ahead78

2.6.3 Constants78

2.6.4 Recognizing Keywords and Identifiers79

2.6.5 A Lexical Analyzer81

2.6.6 Exercises for Section 2.684

2.7 Symbol Tables85

2.7.1 Symbol Table Per Scope86

2.7.2 The Use of Symbol Tables89

2.8 Intermediate Code Generation91

2.8.1 Two Kinds of Intermediate Representations91

2.8.2 Construction of Syntax Trees92

2.8.3 Static Checking97

2.8.4 Three-Address Code99

2.8.5 Exercises for Section 2.8105

2.9 Summary of Chapter 2105

3 Lexical Analysis109

3.1 The Role of the Lexical Analyzer109

3.1.1 Lexical Analysis Versus Parsing110

3.1.2 Tokens,Patterns,and Lexemes111

3.1.3 Attributes for Tokens112

3.1.4 Lexical Errors113

3.1.5 Exercises for Section 3.1114

3.2 Input Buffering115

3.2.1 Buffer Pairs115

3.2.2 Sentinels116

3.3 Specification of Tokens116

3.3.1 Strings and Languages117

3.3.2 Operations on Languages119

3.3.3 Regular Expressions120

3.3.4 Regular Definitions123

3.3.5 Extensions of Regular Expressions124

3.3.6 Exercises for Section 3.3125

3.4 Recognition of Tokens128

3.4.1 Transition Diagrams130

3.4.2 Recognition of Reserved Words and Identifiers132

3.4.3 Completion of the Running Example133

3.4.4 Architecture of a Transition-Diagram-Based Lexical An-alyzer134

3.4.5 Exercises for Section 3.4136

3.5 The Lexical-Analyzer Generator Lex140

3.5.1 Use of Lex140

3.5.2 Structure of Lex Programs141

3.5.3 Conflict Resolution in Lex144

3.5.4 The Lookahead Operator144

3.5.5 Exercises for Section 3.5146

3.6 Finite Automata147

3.6.1 Nondeterministic Finite Automata147

3.6.2 Transition Tables148

3.6.3 Acceptance of Input Strings by Automata149

3.6.4 Deterministic Finite Automata149

3.6.5 Exercises for Section 3.6151

3.7 From Regular Expressions to Automata152

3.7.1 Conversion of an NFA to a DFA152

3.7.2 Simulation of an NFA156

3.7.3 Efficiency of NFA Simulation157

3.7.4 Construction of an NFA from a Regular Expression159

3.7.5 Efficiency of String-Processing Algorithms163

3.7.6 Exercises for Section 3.7166

3.8 Design of a Lexical-Analyzer Generator166

3.8.1 The Structure of the Generated Analyzer167

3.8.2 Pattern Matching Based on NFA's168

3.8.3 DFA's for Lexical Analyzers170

3.8.4 Implementing the Lookahead Operator171

3.8.5 Exercises for Section 3.8172

3.9 Optimization of DFA-Based Pattern Matchers173

3.9.1 Important States of an NFA173

3.9.2 Functions Computed From the Syntax Tree175

3.9.3 Computing nullable,firstpos,and lastpos176

3.9.4 Computing followpos177

3.9.5 Converting a Regular Expression Directly to a DFA179

3.9.6 Minimizing the Number of States of a DFA180

3.9.7 State Minimization in Lexical Analyzers184

3.9.8 Trading Time for Space in DFA Simulation185

3.9.9 Exercises for Section 3.9186

3.10 Summary of Chapter 3187

3.11 References for Chapter 3189

4 Syntax Analysis191

4.1 Introduction192

4.1.1 The Role of the Parser192

4.1.2 Representative Grammars193

4.1.3 Syntax Error Handling194

4.1.4 Error-Recovery Strategies195

4.2 Context-Free Grammars197

4.2.1 The Formal Definition of a Context-Free Grammar197

4.2.2 Notational Conventions198

4.2.3 Derivations199

4.2.4 Parse Trees and Derivations201

4.2.5 Ambiguity203

4.2.6 Verifying the Language Generated by a Grammar204

4.2.7 Context-Free Grammars Versus Regular Expressions205

4.2.8 Exercises for Section 4.2206

4.3 Writing a Grammar209

4.3.1 Lexical Versus Syntactic Analysis209

4.3.2 Eliminating Ambiguity210

4.3.3 Elimination of Left Recursion212

4.3.4 Left Factoring214

4.3.5 Non-Context-Free Language Constructs215

4.3.6 Exercises for Section 4.3216

4.4 Top-Down Parsing217

4.4.1 Recursive-Descent Parsing219

4.4.2 FIRST and FOLLOW220

4.4.3 LL（1） Grammars222

4.4.4 Nonrecursive Predictive Parsing226

4.4.5 Error Recovery in Predictive Parsing228

4.4.6 Exercises for Section 4.4231

4.5 Bottom-Up Parsing233

4.5.1 Reductions234

4.5.2 Handle Pruning235

4.5.3 Shift-Reduce Parsing236

4.5.4 Conflicts During Shift-Reduce Parsing238

4.5.5 Exercises for Section 4.5240

4.6 Introduction to LR Parsing:Simple LR241

4.6.1 Why LR Parsers?241

4.6.2 Items and the LR（0）Automaton242

4.6.3 The LR-Parsing Algorithm248

4.6.4 Constructing SLR-Parsing Tables252

4.6.5 Viable Prefixes256

4.6.6 Exercises for Section 4.6257

4.7 More Powerful LR Parsers259

4.7.1 Canonical LR（1）Items260

4.7.2 Constructing LR（1）Sets of Items261

4.7.3 Canonical LR（1）Parsing Tables265

4.7.4 Constructing LALR Parsing Tables266

4.7.5 Efficient Construction of LALR Parsing Tables270

4.7.6 Compaction of LR Parsing Tables275

4.7.7 Exercises for Section 4.7277

4.8 Using Ambiguous Grammars278

4.8.1 Precedence and Associativity to Resolve Conflicts279

4.8.2 The“Dangling-Else”Ambiguity281

4.8.3 Error Recovery in LR Parsing283

4.8.4 Exercises for Section 4.8285

4.9 Parser Generators287

4.9.1 The Parser Generator Yacc287

4.9.2 Using Yacc with Ambiguous Grammars291

4.9.3 Creating Yacc Lexical Analyzers with Lex294

4.9.4 Error Recovery in Yacc295

4.9.5 Exercises for Section 4.9297

4.10 Summary of Chapter 4297

4.11 References for Chapter 4300

5 Syntax-Directed Translation303

5.1 Syntax-Directed Definitions304

5.1.1 Inherited and Synthesized Attributes304

5.1.2 Evaluating an SDD at the Nodes of a Parse Tree306

5.1.3 Exercises for Section 5.1309

5.2 Evaluation Orders for SDD's310

5.2.1 Dependency Graphs310

5.2.2 Ordering the Evaluation of Attributes312

5.2.3 S-Attributed Definitions312

5.2.4 L-Attributed Definitions313

5.2.5 Semantic Rules with Controlled Side Effects314

5.2.6 Exercises for Section 5.2317

5.3 Applications of Syntax-Directed Translation318

5.3.1 Construction of Syntax Trees318

5.3.2 The Structure of a Type321

5.3.3 Exercises for Section 5.3323

5.4 Syntax-Directed Translation Schemes324

5.4.1 Postfix Translation Schemes324

5.4.2 Parser-Stack Implementation of Postfix SDT's325

5.4.3 SDT's With Actions Inside Productions327

5.4.4 Eliminating Left Recursion From SDT's328

5.4.5 SDT's for L-Attributed Definitions331

5.4.6 Exercises for Section 5.4336

5.5 Implementing L-Attributed SDD's337

5.5.1 Translation During Recursive-Descent Parsing338

5.5.2 On-The-Fly Code Generation340

5.5.3 L-Attributed SDD's and LL Parsing343

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

5.5.5 Exercises for Section 5.5352

5.6 Summary of Chapter 5353

5.7 References for Chapter 5354

6 Intermediate-Code Generation357

6.1 Variants of Syntax Trees358

6.1.1 Directed Acyclic Graphs for Expressions359

6.1.2 The Value-Number Method for Constructing DAG's360

6.1.3 Exercises for Section 6.1362

6.2 Three-Address Code363

6.2.1 Addresses and Instructions364

6.2.2 Quadruples366

6.2.3 Triples367

6.2.4 Static Single-Assignment Form369

6.2.5 Exercises for Section 6.2370

6.3 Types and Declarations370

6.3.1 Type Expressions371

6.3.2 Type Equivalence372

6.3.3 Declarations373

6.3.4 Storage Layout for Local Names373

6.3.5 Sequences of Declarations376

6.3.6 Fields in Records and Classes376

6.3.7 Exercises for Section 6.3378

6.4 Translation of Expressions378

6.4.1 Operations Within Expressions378

6.4.2 Incremental Translation380

6.4.3 Addressing Array Elements381

6.4.4 Translation of Array References383

6.4.5 Exercises for Section 6.4384

6.5 Type Checking386

6.5.1 Rules for Type Checking387

6.5.2 Type Conversions388

6.5.3 Overloading of Functions and Operators390

6.5.4 Type Inference and Polymorphic Functions391

6.5.5 An Algorithm for Unification395

6.5.6 Exercises for Section 6.5398

6.6 Control Flow399

6.6.1 Boolean Expressions399

6.6.2 Short-Circuit Code400

6.6.3 Flow-of-Control Statements401

6.6.4 Control-Flow Translation of Boolean Expressions403

6.6.5 Avoiding Redundant Gotos405

6.6.6 Boolean Values and Jumping Code408

6.6.7 Exercises for Section 6.6408

6.7 Backpatching410

6.7.1 One-Pass Code Generation Using Backpatching410

6.7.2 Backpatching for Boolean Expressions411

6.7.3 Flow-of-Control Statements413

6.7.4 Break-,Continue-,and Goto-Statements416

6.7.5 Exercises for Section 6.7417

6.8 Switch-Statements418

6.8.1 Translation of Switch-Statements419

6.8.2 Syntax-Directed Translation of Switch-Statements420

6.8.3 Exercises for Section 6.8421

6.9 Intermediate Code for Procedures422

6.10 Summary of Chapter 6424

6.11 References for Chapter 6425

7 Run-Time Environments427

7.1 Storage Organization427

7.1.1 Static Versus Dynamic Storage Allocation429

7.2 Stack Allocation of Space430

7.2.1 Activation Trees430

7.2.2 Activation Records433

7.2.3 Calling Sequences436

7.2.4 Variable-Length Data on the Stack438

7.2.5 Exercises for Section 7.2440

7.3 Access to Nonlocal Data on the Stack441

7.3.1 Data Access Without Nested Procedures442

7.3.2 Issues With Nested Procedures442

7.3.3 A Language With Nested Procedure Declarations443

7.3.4 Nesting Depth443

7.3.5 Access Links445

7.3.6 Manipulating Access Links447

7.3.7 Access Links for Procedure Parameters448

7.3.8 Displays449

7.3.9 Exercises for Section 7.3451

7.4 Heap Management452

7.4.1 The Memory Manager453

7.4.2 The Memory Hierarchy of a Computer454

7.4.3 Locality in Programs455

7.4.4 Reducing Fragmentation457

7.4.5 Manual Deallocation Requests460

7.4.6 Exercises for Section 7.4463

7.5 Introduction to Garbage Collection463

7.5.1 Design Goals for Garbage Collectors464

7.5.2 Reachability466

7.5.3 Reference Counting Garbage Collectors468

7.5.4 Exercises for Section 7.5470

7.6 Introduction to Trace-Based Collection470

7.6.1 A Basic Mark-and-Sweep Collector471

7.6.2 Basic Abstraction473

7.6.3 Optimizing Mark-and-Sweep475

7.6.4 Mark-and-Compact Garbage Collectors476

7.6.5 Copying collectors478

7.6.6 Comparing Costs482

7.6.7 Exercises for Section 7.6482

7.7 Short-Pause Garbage Collection483

7.7.1 Incremental Garbage Collection483

7.7.2 Incremental Reachability Analysis485

7.7.3 Partial-Collection Basics487

7.7.4 Generational Garbage Collection488

7.7.5 The Train Algorithm490

7.7.6 Exercises for Section 7.7493

7.8 Advanced Topics in Garbage Collection494

7.8.1 Parallel and Concurrent Garbage Collection495

7.8.2 Partial Object Relocation497

7.8.3 Conservative Collection for Unsafe Languages498

7.8.4 Weak References498

7.8.5 Exercises for Section 7.8499

7.9 Summary of Chapter 7500

7.10 References for Chapter 7502

8 Code Generation505

8.1 Issues in the Design of a Code Generator506

8.1.1 Input to the Code Generator507

8.1.2 The Target Program507

8.1.3 Instruction Selection508

8.1.4 Register Allocation510

8.1.5 Evaluation Order511

8.2 The Target Language512

8.2.1 A Simple Target Machine Model512

8.2.2 Program and Instruction Costs515

8.2.3 Exercises for Section 8.2516

8.3 Addresses in the Target Code518

8.3.1 Static Allocation518

8.3.2 Stack Allocation520

8.3.3 Run-Time Addresses for Names522

8.3.4 Exercises for Section 8.3524

8.4 Basic Blocks and Flow Graphs525

8.4.1 Basic Blocks526

8.4.2 Next-Use Information528

8.4.3 Flow Graphs529

8.4.4 Representation of Flow Graphs530

8.4.5 Loops531

8.4.6 Exercises for Section 8.4531

8.5 Optimization of Basic Blocks533

8.5.1 The DAG Representation of Basic Blocks533

8.5.2 Finding Local Common Subexpressions534

8.5.3 Dead Code Elimination535

8.5.4 The Use of Algebraic Identities536

8.5.5 Representation of Array References537

8.5.6 Pointer Assignments and Procedure Calls539

8.5.7 Reassembling Basic Blocks From DAG's539

8.5.8 Exercises for Section 8.5541

8.6 A Simple Code Generator542

8.6.1 Register and Address Descriptors543

8.6.2 The Code-Generation Algorithm544

8.6.3 Design of the Function getReg547

8.6.4 Exercises for Section 8.6548

8.7 Peephole Optimization549

8.7.1 Eliminating Redundant Loads and Stores550

8.7.2 Eliminating Unreachable Code550

8.7.3 Flow-of-Control Optimizations551

8.7.4 Algebraic Simplification and Reduction in Strength552

8.7.5 Use of Machine Idioms552

8.7.6 Exercises for Section 8.7553

8.8 Register Allocation and Assignment553

8.8.1 Global Register Allocation553

8.8.2 Usage Counts554

8.8.3 Register Assignment for Outer Loops556

8.8.4 Register Allocation by Graph Coloring556

8.8.5 Exercises for Section 8.8557

8.9 Instruction Selection by Tree Rewriting558

8.9.1 Tree-Translation Schemes558

8.9.2 Code Generation by Tiling an Input Tree560

8.9.3 Pattern Matching by Parsing563

8.9.4 Routines for Semantic Checking565

8.9.5 General Tree Matching565

8.9.6 Exercises for Section 8.9567

8.10 Optimal Code Generation for Expressions567

8.10.1 Ershov Numbers567

8.10.2 Generating Code From Labeled Expression Trees568

8.10.3 Evaluating Expressions with an Insufficient Supply of Registers570

8.10.4 Exercises for Section 8.10572

8.11 Dynamic Programming Code-Generation573

8.11.1 Contiguous Evaluation574

8.11.2 The Dynamic Programming Algorithm575

8.11.3 Exercises for Section 8.11577

8.12 Summary of Chapter 8578

8.13 References for Chapter 8579

9 Machine-Independent Optimizations583

9.1 The Principal Sources of Optimization584

9.1.1 Causes of Redundancy584

9.1.2 A Running Example:Quicksort585

9.1.3 Semantics-Preserving Transformations586

9.1.4 Global Common Subexpressions588

9.1.5 Copy Propagation590

9.1.6 Dead-Code Elimination591

9.1.7 Code Motion592

9.1.8 Induction Variables and Reduction in Strength592

9.1.9 Exercises for Section 9.1596

9.2 Introduction to Data-Flow Analysis597

9.2.1 The Data-Flow Abstraction597

9.2.2 The Data-Flow Analysis Schema599

9.2.3 Data-Flow Schemas on Basic Blocks600

9.2.4 Reaching Definitions601

9.2.5 Live-Variable Analysis608

9.2.6 Available Expressions610

9.2.7 Summary614

9.2.8 Exercises for Section 9.2615

9.3 Foundations of Data-Flow Analysis618

9.3.1 Semilattices618

9.3.2 Transfer Functions623

9.3.3 The Iterative Algorithm for General Frameworks626

9.3.4 Meaning of a Data-Flow Solution628

9.3.5 Exercises for Section 9.3631

9.4 Constant Propagation632

9.4.1 Data-Flow Values for the Constant-Propagation Framework633

9.4.2 The Meet for the Constant-Propagation Framework633

9.4.3 Transfer Functions for the Constant-Propagation Framwork634

9.4.4 Monotonicity of the Constant-Propagation Framework635

9.4.5 Nondistributivity of the Constant-Propagation Framework635

9.4.6 Interpretation of the Results637

9.4.7 Exercises for Section 9.4637

9.5 Partial-Redundancy Elimination639

9.5.1 The Sources of Redundancy639

9.5.2 Can All Redundancy Be Eliminated?642

9.5.3 The Lazy-Code-Motion Problem644

9.5.4 Anticipation of Expressions645

9.5.5 The Lazy-Code-Motion Algorithm646

9.5.6 Exercises for Section 9.5655

9.6 Loops in Flow Graphs655

9.6.1 Dominators656

9.6.2 Depth-First Ordering660

9.6.3 Edges in a Depth-First Spanning Tree661

9.6.4 Back Edges and Reducibility662

9.6.5 Depth of a Flow Graph665

9.6.6 Natural Loops665

9.6.7 Speed of Convergence of Iterative Data-Flow Algorithms667

9.6.8 Exercises for Section 9.6669

9.7 Region-Based Analysis672

9.7.1 Regions672

9.7.2 Region Hierarchies for Reducible Flow Graphs673

9.7.3 Overview of a Region-Based Analysis676

9.7.4 Necessary Assumptions About Transfer Functions678

9.7.5 An Algorithm for Region-Based Analysis680

9.7.6 Handling Nonreducible Flow Graphs684

9.7.7 Exercises for Section 9.7686

9.8 Symbolic Analysis686

9.8.1 Affine Expressions of Reference Variables687

9.8.2 Data-Flow Problem Formulation689

9.8.3 Region-Based Symbolic Analysis694

9.8.4 Exercises for Section 9.8699

9.9 Summary of Chapter 9700

9.10 References for Chapter 9703

10 Instruction-Level Parallelism707

10.1 Processor Architectures708

10.1.1 Instruction Pipelines and Branch Delays708

10.1.2 Pipelined Execution709

10.1.3 Multiple Instruction Issue710

10.2 Code-Scheduling Constraints710

10.2.1 Data Dependence711

10.2.2 Finding Dependences Among Memory Accesses712

10.2.3 Tradeoff Between Register Usage and Parallelism713

10.2.4 Phase Ordering Between Register Allocation and Code Scheduling716

10.2.5 Control Dependence716

10.2.6 Speculative Execution Support717

10.2.7 A Basic Machine Model719

10.2.8 Exercises for Section 10.2720

10.3 Basic-Block Scheduling721

10.3.1 Data-Dependence Graphs722

10.3.2 List Scheduling of Basic Blocks723

10.3.3 Prioritized Topological Orders725

10.3.4 Exercises for Section 10.3726

10.4 Global Code Scheduling727

10.4.1 Primitive Code Motion728

10.4.2 Upward Code Motion730

10.4.3 Downward Code Motion731

10.4.4 Updating Data Dependences732

10.4.5 Global Scheduling Algorithms732

10.4.6 Advanced Code Motion Techniques736

10.4.7 Interaction with Dynamic Schedulers737

10.4.8 Exercises for Section 10.4737

10.5 Software Pipelining738

10.5.1 Introduction738

10.5.2 Software Pipelining of Loops740

10.5.3 Register Allocation and Code Generation743

10.5.4 Do-Across Loops743

10.5.5 Goals and Constraints of Software Pipelining745

10.5.6 A Software-Pipelining Algorithm749

10.5.7 Scheduling Acyclic Data-Dependence Graphs749

10.5.8 Scheduling Cyclic Dependence Graphs751

10.5.9 Improvements to the Pipelining Algorithms758

10.5.10 Modular Variable Expansion758

10.5.11 Conditional Statements761

10.5.12 Hardware Support for Software Pipelining762

10.5.13 Exercises for Section 10.5763

10.6 Summary of Chapter 10765

10.7 References for Chapter 10766

11 Optimizing for Parallelism and Locality769

11.1 Basic Concepts771

11.1.1 Multiprocessors772

11.1.2 Parallelism in Applications773

11.1.3 Loop-Level Parallelism775

11.1.4 Data Locality777

11.1.5 Introduction to Affine Transform Theory778

11.2 Matrix Multiply:An In-Depth Example782

11.2.1 The Matrix-Multiplication Algorithm782

11.2.2 Optimizations785

11.2.3 Cache Interference788

11.2.4 Exercises for Section 11.2788

11.3 Iteration Spaces788

11.3.1 Constructing Iteration Spaces from Loop Nests788

11.3.2 Execution Order for Loop Nests791

11.3.3 Matrix Formulation of Inequalities791

11.3.4 Incorporating Symbolic Constants793

11.3.5 Controlling the Order of Execution793

11.3.6 Changing Axes798

11.3.7 Exercises for Section 11.3799

11.4 Affine Array Indexes801

11.4.1 Affine Accesses802

11.4.2 Affine and Nonaffine Accesses in Practice803

11.4.3 Exercises for Section 11.4804

11.5 Data Reuse804

11.5.1 Types of Reuse805

11.5.2 Self Reuse806

11.5.3 Self-Spatial Reuse809

11.5.4 Group Reuse811

11.5.5 Exercises for Section 11.5814

11.6 Array Data-Dependence Analysis815

11.6.1 Definition of Data Dependence of Array Accesses816

11.6.2 Integer Linear Programming817

11.6.3 The GCD Test818

11.6.4 Heuristics for Solving Integer Linear Programs820

11.6.5 Solving General Integer Linear Programs823

11.6.6 Summary825

11.6.7 Exercises for Section 11.6826

11.7 Finding Synchronization-Free Parallelism828

11.7.1 An Introductory Example828

11.7.2 Affine Space Partitions830

11.7.3 Space-Partition Constraints831

11.7.4 Solving Space-Partition Constraints835

11.7.5 A Simple Code-Generation Algorithm838

11.7.6 Eliminating Empty Iterations841

11.7.7 Eliminating Tests from Innermost Loops844

11.7.8 Source-Code Transforms846

11.7.9 Exercises for Section 11.7851

11.8 Synchronization Between Parallel Loops853

11.8.1 A Constant Number of Synchronizations853

11.8.2 Program-Dependence Graphs854

11.8.3 Hierarchical Time857

11.8.4 The Parallelization Algorithm859

11.8.5 Exercises for Section 11.8860

11.9 Pipelining861

11.9.1 What is Pipelining?861

11.9.2 Successive Over-Relaxation（SOR）:An Example863

11.9.3 Fully Permutable Loops864

11.9.4 Pipelining Fully Permutable Loops864

11.9.5 General Theory867

11.9.6 Time-Partition Constraints868

11.9.7 Solving Time-Partition Constraints by Farkas'Lemma872

11.9.8 Code Transformations875

11.9.9 Parallelism With Minimum Synchronization880

11.9.10 Exercises for Section 11.9882

11.10 Locality Optimizations884

11.10.1 Temporal Locality of Computed Data885

11.10.2 Array Contraction885

11.10.3 Partition Interleaving887

11.10.4 Putting it All Together890

11.10.5 Exercises for Section 11.10892

11.11 Other Uses of Affine Transforms893

11.11.1 Distributed memory machines894

11.11.2 Multi-Instruction-Issue Processors895

11.11.3 Vector and SIMD Instructions895

11.11.4 Prefetching896

11.12 Summary of Chapter 11897

11.13 References for Chapter 11899

12 Interprocedural Analysis903

12.1 Basic Concepts904

12.1.1 Call Graphs904

12.1.2 Context Sensitivity906

12.1.3 Call Strings908

12.1.4 Cloning-Based Context-Sensitive Analysis910

12.1.5 Summary-Based Context-Sensitive Analysis911

12.1.6 Exercises for Section 12.1914

12.2 Why Interprocedural Analysis?916

12.2.1 Virtual Method Invocation916

12.2.2 Pointer Alias Analysis917

12.2.3 Parallelization917

12.2.4 Detection of Software Errors and Vulnerabilities917

12.2.5 SQL Injection918

12.2.6 Buffer Overflow920

12.3 A Logical Representation of Data Flow921

12.3.1 Introduction to Datalog921

12.3.2 Datalog Rules922

12.3.3 Intensional and Extensional Predicates924

12.3.4 Execution of Datalog Programs927

12.3.5 Incremental Evaluation of Datalog Programs928

12.3.6 Problematic Datalog Rules930

12.3.7 Exercises for Section 12.3932

12.4 A Simple Pointer-Analysis Algorithm933

12.4.1 Why is Pointer Analysis Difficult934

12.4.2 A Model for Pointers and References935

12.4.3 Flow Insensitivity936

12.4.4 The Formulation in Datalog937

12.4.5 Using Type Information938

12.4.6 Exercises for Section 12.4939

12.5 Context-Insensitive Interprocedural Analysis941

12.5.1 Effects of a Method Invocation941

12.5.2 Call Graph Discovery in Datalog943

12.5.3 Dynamic Loading and Refection944

12.5.4 Exercises for Section 12.5945

12.6 Context-Sensitive Pointer Analysis945

12.6.1 Contexts and Call Strings946

12.6.2 Adding Context to Datalog Rules949

12.6.3 Additional Observations About Sensitivity949

12.6.4 Exercises for Section 12.6950

12.7 Datalog Implementation by BDD's951

12.7.1 Binary Decision Diagrams951

12.7.2 Transformations on BDD's953

12.7.3 Representing Relations by BDD's954

12.7.4 Relational Operations as BDD Operations954

12.7.5 Using BDD's for Points-to Analysis957

12.7.6 Exercises for Section 12.7958

12.8 Summary of Chapter 12958

12.9 References for Chapter 12961

A A Complete Front End965

A.1 The Source Language965

A.2 Main966

A.3 Lexical Analyzer967

A.4 Symbol Tables and Types970

A.5 Intermediate Code for Expressions971

A.6 Jumping Code for Boolean Expressions974

A.7 Intermediate Code for Statements978

A.8 Parser981

A.9 Creating the Front End986

B Finding Linearly Independent Solutions989

Index993