《工程化编译器》第二版——深入现代优化编译器构建

5星 · 超过95%的资源需积分: 9 15 浏览量更新于2024-07-28 收藏 8.27MB PDF 举报

"《Engineering a Compiler, 2nd Edition》是一本深入研究编译器的著作，由Cooper和Torczon合著，是初学者理解编译器原理与实践的宝贵指南。这本书在第二版中增加了清晰的教程和必要的细节，同时保持了对整体概念的把握。" 在计算机科学领域，编译器是一个集大成的研究方向，它将各种知识融合到一个精巧的系统中。《Engineering a Compiler, 2nd Edition》是这样一本能够引领读者进入这个领域的书籍。作者Cooper和Torczon凭借丰富的编译器构建经验，为读者提供了深入浅出的指导，帮助他们不仅理解基础理论，还能掌握优化编译器的关键细节。本书的亮点之一是对静态单赋值形式（Static Single Assignment Form, SSA）的出色介绍。SSA是一种在编译器优化中广泛使用的中间表示形式，它使得数据流分析和优化更为便捷。作者通过详尽的阐述，让读者能够理解和应用这一重要概念。在第二版中，作者针对现代优化编译器的构建提供了全面的介绍。他们引导学生逐步了解编译器的工作流程，包括词法分析、语法分析、语义分析、代码生成以及各种优化技术，如常量折叠、死代码消除、循环展开等。此外，书中还涵盖了如何处理重要的但往往被忽视的细节，这些细节对于构建一个高效优化的编译器至关重要。 Michael D. Smith，哈佛大学的工程与应用科学学院院长，称赞这本书为新学者提供了宝贵的陪伴。Jeffery von Ronne教授也认为这本书是学习现代优化编译器构造的优秀入门教材，特别强调了其在SSA形式讲解上的卓越表现。《Engineering a Compiler, 2nd Edition》是一本深入且实用的编译器工程教科书，适合大学课程、自学或者专业开发者参考，它能帮助读者建立起扎实的编译器理论基础，并掌握实际编译器设计和实现的技巧。通过阅读此书，读者不仅可以了解到编译器的核心概念，还能获得在实践中解决问题的能力。

“02-toc-ix-xviii-9780120884780” — 2011/1/13 — 15:55 — page xv — #7

Contents xv

9.6 Summary and Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533

Chapter Notes ...................................................... . . 534

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535

CHAPTER 10 Scalar Optimizations.... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ... 539

10.1 Introduction .. . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . 539

10.2 Eliminating Useless and Unreachable Code . . . . . .... . . . ..... . . . .... 544

10.2.1 Eliminating Useless Code .... . . . . .... . . . . .... . . . . .... . . . . .... 544

10.2.2 Eliminating Useless Control Flow .... . . . . .... . . . . .... . . . . .. 547

10.2.3 Eliminating Unreachable Code ..... . . . ..... . . . ..... . . . ..... . 550

10.3 Code Motion . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . 551

10.3.1 Lazy Code Motion .. . . . . .... . . . . ..... . . . ..... . . . ..... . . . .... . . 551

10.3.2 Code Hoisting . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . 559

10.4 Specialization . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . 560

10.4.1 Tail-Call Optimization . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . 561

10.4.2 Leaf-Call Optimization .. . . . ..... . . . ..... . . . ..... . . . ..... . . . .. 562

10.4.3 Parameter Promotion .... . . . ..... . . . ..... . . . ..... . . . ..... . . . .. 563

10.5 Redundancy Elimination . . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . .. 565

10.5.1 Value Identity versus Name Identity . . . . ..... . . . ..... . . . .... 565

10.5.2 Dominator-based Value Numbering . . ..... . . . ..... . . . ..... . . 566

10.6 Enabling Other Transformations . . . . ..... . . . ..... . . . ..... . . . ..... . . . . 569

10.6.1 Superblock Cloning . . . ..... . . . ..... . . . ..... . . . ..... . . . . .... . . . 570

10.6.2 Procedure Cloning . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . .... 571

10.6.3 Loop Unswitching . . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . 572

10.6.4 Renaming ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . 573

10.7 Advanced Topics . . . ..... . . . .... . . . . ..... . . . ..... . . . ..... . . . ..... . . . .... 575

10.7.1 Combining Optimizations .... . . . . .... . . . . .... . . . . .... . . . . .... 575

10.7.2 Strength Reduction . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . .. 580

10.7.3 Choosing an Optimization Sequence . ..... . . . ..... . . . ..... . . 591

10.8 Summary and Perspective . . . ..... . . . .... . . . . .... . . . . .... . . . . .... . . . . . 592

Chapter Notes .. . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... 593

Exercises . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . 594

CHAPTER 11 Instruction Selection . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . 597

11.1 Introduction .. . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . 597

11.2 Code Generation . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . 600

11.3 Extending the Simple Treewalk Scheme . .... . . . . .... . . . . .... . . . . ... 603

11.4 Instruction Selection via Tree-Pattern Matching . . ..... . . . ..... . . . . 610

11.4.1 Rewrite Rules . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . . 611

11.4.2 Finding a Tiling . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . 616

11.4.3 Tools . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . . 620

“02-toc-ix-xviii-9780120884780” — 2011/1/13 — 15:55 — page xvi — #8

xvi Contents

11.5 Instruction Selection via Peephole Optimization . ..... . . . ..... . . . .. 621

11.5.1 Peephole Optimization . ..... . . . ..... . . . ..... . . . ..... . . . ..... . 622

11.5.2 Peephole Transformers . ..... . . . ..... . . . ..... . . . ..... . . . ..... . 629

11.6 Advanced Topics . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . .... 632

11.6.1 Learning Peephole Patterns . . . ..... . . . ..... . . . .... . . . . .... . . . 632

11.6.2 Generating Instruction Sequences . . . ..... . . . ..... . . . .... . . . . 633

11.7 Summary and Perspective . . . ..... . . . ..... . . . .... . . . . .... . . . . .... . . . . . 634

Chapter Notes .. . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... 635

Exercises . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . 637

CHAPTER 12 Instruction Scheduling . . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .. 639

12.1 Introduction .. . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . 639

12.2 The Instruction-Scheduling Problem . . . . ..... . . . ..... . . . ..... . . . .... 643

12.2.1 Other Measures of Schedule Quality . .... . . . . .... . . . . ..... . . 648

12.2.2 What Makes Scheduling Hard? . . . ..... . . . ..... . . . ..... . . . ... 649

12.3 Local List Scheduling ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . . 651

12.3.1 The Algorithm . . . . .... . . . . ..... . . . ..... . . . .... . . . . .... . . . . .... . 651

12.3.2 Scheduling Operations with Variable Delays . . . ..... . . . ... 654

12.3.3 Extending the Algorithm . . . ..... . . . ..... . . . ..... . . . ..... . . . .. 655

12.3.4 Tie Breaking in the List-Scheduling

Algorithm .... . . . . .... . . . . .... . . . . ..... . . . ..... . . . ..... . . . ..... . 655

12.3.5 Forward versus Backward List Scheduling . ..... . . . ..... . . 656

12.3.6 Improving the Efficiency of List Scheduling . . .... . . . . .... 660

12.4 Regional Scheduling .. . . . .... . . . . .... . . . . ..... . . . .... . . . . .... . . . . .... . . 661

12.4.1 Scheduling Extended Basic Blocks . . . . ..... . . . ..... . . . ..... 661

12.4.2 Trace Scheduling . . . . ..... . . . ..... . . . ..... . . . .... . . . . ..... . . . .. 663

12.4.3 Cloning for Context . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . .. 664

12.5 Advanced Topics . . . ..... . . . .... . . . . ..... . . . ..... . . . ..... . . . ..... . . . .... 666

12.5.1 The Strategy of Software Pipelining . ..... . . . ..... . . . ..... . . 666

12.5.2 An Algorithm for Software Pipelining . . . . ..... . . . ..... . . . .. 670

12.6 Summary and Perspective . . . ..... . . . .... . . . . .... . . . . .... . . . . .... . . . . . 673

Chapter Notes .. . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... 673

Exercises . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . 675

CHAPTER 13 Register Allocation..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . .... 679

13.1 Introduction .. . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . 679

13.2 Background Issues . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ... 681

13.2.1 Memory versus Registers ..... . . . ..... . . . ..... . . . ..... . . . . ... 681

13.2.2 Allocation versus Assignment . . . . .... . . . . .... . . . . .... . . . . ... 682

13.2.3 Register Classes . . . . ..... . . . ..... . . . ..... . . . .... . . . . ..... . . . ... 683

13.3 Local Register Allocation and Assignment . . ..... . . . ..... . . . ..... . . 684

13.3.1 Top-Down Local Register Allocation . . ..... . . . ..... . . . ..... 685

“02-toc-ix-xviii-9780120884780” — 2011/1/13 — 15:55 — page xvii — #9

Contents xvii

13.3.2 Bottom-Up Local Register Allocation . . ..... . . . ..... . . . .... 686

13.3.3 Moving Beyond Single Blocks . . . ..... . . . ..... . . . ..... . . . ... 689

13.4 Global Register Allocation and Assignment . . ..... . . . ..... . . . ..... . 693

13.4.1 Discovering Global Live Ranges .. . . . ..... . . . ..... . . . ..... . . 696

13.4.2 Estimating Global Spill Costs . ..... . . . ..... . . . ..... . . . ..... . 697

13.4.3 Interferences and the Interference Graph . ..... . . . ..... . . . .. 699

13.4.4 Top-Down Coloring . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . . 702

13.4.5 Bottom-Up Coloring ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . .. 704

13.4.6 Coalescing Copies to Reduce Degree . ..... . . . ..... . . . ..... . 706

13.4.7 Comparing Top-Down and Bottom-Up

Global Allocators . . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . . 708

13.4.8 Encoding Machine Constraints in the

Interference Graph . .... . . . . .... . . . . .... . . . . ..... . . . ..... . . . ... 711

13.5 Advanced Topics . . . ..... . . . .... . . . . ..... . . . ..... . . . ..... . . . ..... . . . .... 713

13.5.1 Variations on Graph-Coloring Allocation . . . ..... . . . ..... . . 713

13.5.2 Global Register Allocation over SSA Form . ..... . . . ..... . . 717

13.6 Summary and Perspective . . . ..... . . . .... . . . . .... . . . . .... . . . . .... . . . . . 718

Chapter Notes .. . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... 719

Exercises . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . 720

APPENDIX A ILOC. . ..... . . . .... . . . . .... . . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . .... 725

A.1 Introduction . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . .... . . . . . 725

A.2 Naming Conventions ... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... 727

A.3 Individual Operations . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . 728

A.3.1 Arithmetic .... . . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . 728

A.3.2 Shifts . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . .... 729

A.3.3 Memory Operations . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ... 729

A.3.4 Register-to-Register Copy Operations .... . . . ..... . . . ..... . . . . 730

A.4 Control-Flow Operations . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . .... 731

A.4.1 Alternate Comparison and Branch Syntax . . . ..... . . . ..... . . . 732

A.4.2 Jumps ... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . 732

A.5 Representing SSA Form . . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ... 733

APPENDIX B Data Structures ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . .... . . . . 737

B.1 Introduction .... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . 737

B.2 Representing Sets .... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . ..... . . . 738

B.2.1 Representing Sets as Ordered Lists . . . . ..... . . . ..... . . . ..... . . 739

B.2.2 Representing Sets as Bit Vectors .. . . . ..... . . . ..... . . . ..... . . . . 741

B.2.3 Representing Sparse Sets ..... . . . ..... . . . ..... . . . ..... . . . ..... . . 741

B.3 Implementing Intermediate Representations . .... . . . . .... . . . . ..... . . . 743

B.3.1 Graphical Intermediate Representations . . . . ..... . . . ..... . . . .. 743

B.3.2 Linear Intermediate Forms . . ..... . . . ..... . . . ..... . . . ..... . . . ... 748

“03-pref-xix-xxiv-9780120884780” — 2011/1/13 — 15:49 — page xix — #1

Preface to the Second Edition

The practice of compiler construction changes continually, in part because the designs of

processors and systems change. For example, when we began to write Engineering a Com-

piler (eac) in 1998, some of our colleagues questioned the wisdom of including a chapter on

instruction scheduling because out-of-order execution threatened to make scheduling largely

irrelevant. Today, as the second edition goes to press, the rise of multicore processors and the

push for more cores has made in-order execution pipelines attractive again because their smaller

footprints allow the designer to place more cores on a chip. Instruction scheduling will remain

important for the near-term future.

At the same time, the compiler construction community continues to develop new insights and

algorithms, and to rediscover older techniques that were effective but largely forgotten. Recent

research has created excitement surrounding the use of chordal graphs in register allocation

(see Section 13.5.2). That work promises to simplify some aspects of graph-coloring allocators.

Brzozowski’s algorithm is a dfa minimization technique that dates to the early 1960s but has

not been taught in compiler courses for decades (see Section 2.6.2). It provides an easy path

from an implementation of the subset construction to one that minimizes dfas. A modern course

in compiler construction might include both of these ideas.

How, then, are we to structure a curriculum in compiler construction so that it prepares students

to enter this ever changing ﬁeld? We believe that the course should provide each student with

the set of base skills that they will need to build new compiler components and to modify

existing ones. Students need to understand both sweeping concepts, such as the collaboration

between the compiler, linker, loader, and operating system embodied in a linkage convention,

and minute detail, such as how the compiler writer might reduce the aggregate code space used

by the register-save code at each procedure call.

n CHANGES IN THE SECOND EDITION

The second edition of Engineering a Compiler (eac2e) presents both perspectives: big-picture

views of the problems in compiler construction and detailed discussions of algorithmic alterna-

tives. In preparing eac2e, we focused on the usability of the book, both as a textbook and as a

reference for professionals. Speciﬁcally, we

n Improved the ﬂow of ideas to help the student who reads the book sequentially. Chapter

introductions explain the purpose of the chapter, lay out the major concepts, and provide a

high-level overview of the chapter’s subject matter. Examples have been reworked to

provide continuity across chapters. In addition, each chapter begins with a summary and a

set of keywords to aid the user who treats eac2e as a reference book.

n Added section reviews and review questions at the end of each major section. The review

questions provide a quick check as to whether or not the reader has understood the major

points of the section.

xix

剩余824页未读，继续阅读

地针

粉丝: 0
资源: 12

《工程化编译器》第二版——深入现代优化编译器构建

Intel.C.Plus.Plus.Compiler.v9.1.022-lic

plexus-compiler--2.8.4.jar.rar

新建一个MAVEN项目，properties没有显示maven.compiler.source和maven.compiler.target

org.apache.jasper.JasperException:

):[c]和[/client/index.jsp]的TagLibraryValidator的验证错误消息

无法解析插件 org.apache.maven.plugins:maven-compiler-plugin:3.10.1

如何添加 Unresolved plugin: 'org.apache.maven.plugins:maven-compiler-plugin:3.1' 到pom.xml

无法解析插件 org.apache.maven.plugins:maven-compiler-plugin

nresolved plugin: 'org.apache.maven.plugins:maven-compiler-plugin:3.1'

最新资源