Cooper_Engineering_a_Compiler(Second Edition) (1157546), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

. . . . . . . . . . . . .10.2.2 Eliminating Useless Control Flow . . . . . . . . . . . . . . . . . . . . . . . . . .10.2.3 Eliminating Unreachable Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.3 Code Motion . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.3.1 Lazy Code Motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.3.2 Code Hoisting . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.4 Specialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.4.1 Tail-Call Optimization . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.4.2 Leaf-Call Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.4.3 Parameter Promotion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.5 Redundancy Elimination . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.5.1 Value Identity versus Name Identity . . . . . . . . . . . . . . . . . . . . . . . .10.5.2 Dominator-based Value Numbering . . . . . . . . . . . . . . . . . . . . . . . . .10.6 Enabling Other Transformations .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.6.1 Superblock Cloning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.6.2 Procedure Cloning . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .10.6.3 Loop Unswitching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.6.4 Renaming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.7 Advanced Topics . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.7.1 Combining Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.7.2 Strength Reduction . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .10.7.3 Choosing an Optimization Sequence . . . . . . . . . . . . . . . . . . . . . . . .10.8 Summary and Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Chapter Notes . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .539544544547550551551559560561562563565565566569570571572573575575580591592593594CHAPTER 11 Instruction Selection . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59711.111.211.311.4Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Extending the Simple Treewalk Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . .Instruction Selection via Tree-Pattern Matching . . . . . . . . . . . . . . . . . .

.11.4.1 Rewrite Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.4.2 Finding a Tiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.4.3 Tools . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .597600603610611616620xvi Contents11.5 Instruction Selection via Peephole Optimization . . . . . . . . . . . . . . . . . . .11.5.1 Peephole Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.5.2 Peephole Transformers . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.6 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.6.1 Learning Peephole Patterns . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.6.2 Generating Instruction Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . .11.7 Summary and Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . .Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .621622629632632633634635637CHAPTER 12 Instruction Scheduling . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63912.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . .12.2 The Instruction-Scheduling Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12.2.1 Other Measures of Schedule Quality . . . . . . . . . . . . . . . . . . . . . . . .12.2.2 What Makes Scheduling Hard? . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .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-SchedulingAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12.3.5 Forward versus Backward List Scheduling . . . . . . .

. . . . . . . . .12.3.6 Improving the Efficiency of List Scheduling . . . . . . . . . . . . . .12.4 Regional Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12.4.1 Scheduling Extended Basic Blocks . . . . . .

. . . . . . . . . . . . . . . . . . .12.4.2 Trace Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12.4.3 Cloning for Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .12.5 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12.5.1 The Strategy of Software Pipelining . . . . . . . . . . . . . . . . . . . . . . . .12.5.2 An Algorithm for Software Pipelining . . . . . . . . . . . . . . . . . . . . . .12.6 Summary and Perspective . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .639643648649651651654655655656660661661663664666666670673673675CHAPTER 13 Register Allocation . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67913.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .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 . . . . . . . . . . . . . . . . . . . . . . .679681681682683684685Contents xvii13.3.2 Bottom-Up Local Register Allocation . . . . . . . . . . . . . .

. . . . . . . .13.3.3 Moving Beyond Single Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13.4 Global Register Allocation and Assignment . . . . . . . . . . . . . . . . . . . . . . . .13.4.1 Discovering Global Live Ranges . . . . . . . . . . . . . . . . . . . . . . . . . .

Характеристики

Список файлов учебной работы