Advanced Compiler Design and Implementation
by Steven Muchnick
Preface
1 Introduction to Advanced Topics
1.1 Review of Compiler Structure
1.2 Advanced Issues in Elementary Topics
1.3 The Importance of Code Optimization
1.4 Structure of Optimizing Compilers
1.5 Placement of Optimizations in Aggressive Optimizing Compilers
1.6 Reading Flow Among the Chapters
1.7 Related Topics Not Covered in This Text
1.8 Target Machines Used in Examples
1.9 Number Notations and Data Sizes
1.10 Wrap-Up
1.11 Further Reading
1.12 Exercises
2 Informal Compiler Algorithm Notation (ICAN)
2.1 Extended Backus-Naur Form Syntax Notation
2.2 Introduction to ICAN
2.3 A Quick Overview of ICAN
2.4 Whole Programs
2.5 Type Definitions
2.6 Declarations
2.7 Data Types and Expressions
2.8 Statements
2.9 Wrap-Up
2.10 Further Reading
2.11 Exercises
3 Symbol-Table Structure
3.1 Storage Classes, Visibility, and Lifetimes
3.2 Symbol Attributes and Symbol-Table Entries
3.3 Local Symbol-Table Management
3.4 Global Symbol-Table Structure
3.5 Storage Binding and Symbolic Registers
3.6 Approaches to Generating Loads and Stores
3.7 Wrap-Up
3.8 Further Reading
3.9 Exercises
4 Intermediate Representations
4.1 Issues in Designing an Intermediate Language
4.2 High-Level Intermediate Languages
4.3 Medium-Level Intermediate Languages
4.4 Low-Level Intermediate Languages
4.5 Multi-Level Intermediate Languages
4.6 Our Intermediate Languages: MIR, HIR, and LIR
4.7 Representing MIR, HIR, and LIR in ICAN
4.8 ICAN Naming of Data Structures and Routines that Manipulate Intermediate Code
4.9 Other Intermediate-Language Forms
4.10 Wrap-Up
4.11 Further Reading
4.12 Exercises
5 Run-Time Support
5.1 Data Representations and Instructions
5.2 Register Usage
5.3 The Local Stack Frame
5.4 The Run-Time Stack
5.5 Parameter-Passing Disciplines
5.6 Procedure Prologues, Epilogues, Calls, and Returns
5.7 Code Sharing and Position-Independent Code
5.8 Symbolic and Polymorphic Language Support
5.9 Wrap-Up
5.10 Further Reading
5.11 Exercises
6 Producing Code Generators Automatically
6.1 Introduction to Automatic Generation of Code Generators
6.2 A Syntax-Directed Technique
6.3 Introduction to Semantics-Directed Parsing
6.4 Tree Pattern Matching and Dynamic Programming
6.5 Wrap-Up
6.6 Further Reading
6.7 Exercises
7 Control-Flow Analysis
7.1 Approaches to Control-Flow Analysis
7.2 Depth-First Search, Preorder Traversal, Postorder Traversal, and Breadth-First Search
7.3 Dominators
7.4 Loops and Strongly Connected Components
7.5 Reducibility
7.6 Interval Analysis and Control Trees
7.7 Structural Analysis
7.8 Wrap-Up
7.9 Further Reading
7.10 Exercises
8 Data-Flow Analysis
8.1 An Example: Reaching Definitions
8.2 Basic Concepts: Lattices, Flow Functions, and Fixed Points
8.3 Taxonomy of Data-Flow Problems and Solution Methods
8.4 Iterative Data-Flow Analysis
8.5 Lattices of Flow Functions
8.6 Control-Tree-Based Data-Flow Analysis
8.7 Structural Analysis
8.8 Interval Analysis
8.9 Other Approaches
8.10 Du-Chains, Ud-Chains, and Webs
8.11 Static Single-Assignment (SSA) Form
8.12 Dealing with Arrays, Structures, and Pointers
8.13 Automating Construction of Data-Flow Analyzers
8.14 More Ambitious Analyses
8.15 Wrap-Up
8.16 Further Reading
8.17 Exercises
9 Dependence Analysis and Dependence Graph
9.1 Dependence Relations
9.2 Basic-Block Dependence DAGs
9.3 Dependences in Loops
9.4 Dependence Testing
9.5 Program-Dependence Graphs
9.6 Dependences Between Dynamically Allocated Objects
9.7 Wrap-Up
9.8 Further Reading
9.9 Exercises
10 Alias Analysis
10.1 Aliases in Various Real Programming Languages
10.2 The Alias Gatherer
10.3 The Alias Propagator
10.4 Wrap-Up
10.5 Further Reading
10.6 Exercises
11 Introduction to Optimization
11.1 Global Optimizations Discussed in Chapters 12 Through 18
11.2 Flow Sensitivity and May vs. Must Information
11.3 Importance of Individual Optimizations
11.4 Order and Repetition of Optimizations
11.5 Further Reading
11.6 Exercises
12 Early Optimizations
12.1 Constant-Expression Evaluation (Constant Folding)
12.2 Scalar Replacement of Aggregates
12.3 Algebraic Simplifications and Reassociation
12.4 Value Numbering
12.5 Copy Propagation
12.6 Sparse Conditional Constant Propagation
12.7 Wrap-Up
12.8 Further Reading
12.9 Exercises
13 Redundancy Elimination
13.1 Common-Subexpression Elimination
13.2 Loop-Invariant Code Motion
13.3 Partial-Redundancy Elimination
13.4 Redundancy Elimination and Reassociation
13.5 Code Hoisting
13.6 Wrap-Up
13.7 Further Reading
13.8 Exercises
14 Loop Optimizations
14.1 Induction-Variable Optimizations
14.2 Unnecessary Bounds-Checking Elimination
14.3 Wrap-Up
14.4 Further Reading
14.5 Exercises
15 Procedure Optimizations
15.1 Tail-Call Optimization and Tail-Recursion Elimination
15.2 Procedure Integration
15.3 In-Line Expansion
15.4 Leaf-Routine Optimization and Shrink Wrapping
15.5 Wrap-Up
15.6 Further Reading
15.7 Exercises
16 Register Allocation
16.1 Register Allocation and Assignment
16.2 Local Methods
16.3 Graph Coloring
16.4 Priority-Based Graph Coloring
16.5 Other Approaches to Register Allocation
16.6 Wrap-Up
16.7 Further Reading
16.8 Exercises
17 Code Scheduling
17.1 Instruction Scheduling
17.2 Speculative Loads and Boosting
17.3 Speculative Scheduling
17.4 Software Pipelining
17.5 Trace Scheduling
17.6 Percolation Scheduling
17.7 Wrap-Up
17.8 Further Reading
17.9 Exercises
18 Control-Flow and Low-Level Optimizations
18.1 Unreachable-Code Elimination
18.2 Straightening
18.3 If Simplifications
18.4 Loop Simplifications
18.5 Loop Inversion
18.6 Unswitching
18.7 Branch Optimizations
18.8 Tail Merging or Cross Jumping
18.9 Conditional Moves
18.10 Dead-Code Elimination
18.11 Branch Prediction
18.12 Machine Idioms and Instruction Combining
18.13 Wrap-Up
18.14 Further Reading
18.15 Exercises
19 Interprocedural Analysis and Optimization
19.1 Interprocedural Control-Flow Analysis: The Call Graph
19.2 Interprocedural Data-Flow Analysis
19.3 Interprocedural Constant Propagation
19.4 Interprocedural Alias Analysis
19.5 Interprocedural Optimizations
19.6 Interprocedural Register Allocation
19.7 Aggregation of Global References
19.8 Other Issues in Interprocedural Program Management
19.9 Wrap-Up
19.10 Further Reading
19.11 Exercises
20 Optimization of the Memory Hierarchy
20.1 Impact of Data and Instruction Caches
20.2 Instruction-Cache Optimization
20.3 Scalar Replacement of Array Elements
20.4 Data-Cache Optimization
20.5 Scalar vs. Memory-Oriented Optimizations
20.6 Wrap-Up
20.7 Further Reading
20.8 Exercises
21 Case Studies of Compilers and Future Trends
21.1 the Sun Compilers for SPARC
21.2 The IBM XL Compilers for the POWER and PowerPC Architectures
21.3 Digital Equipment's Compilers for Alpha
21.4 The Intel Reference Compilers for the Intel 386 Architecture
21.5 Future Trends in Compiler Design and Implementation
21.6 Further Reading
A Guide to Assembly Languages Used in This Book
A.1 Sun SPARC Versions 8 and 9 Assembly Language
A.2 IBM POWER and PowerPC Assembly Language
A.3 DEC Alpha Assembly Language
A.4 Intel 386 Architecture Assembly Language
A.5 Hewlett-Packard's PA-RISC Assembly Language
B Representation of Sets, Sequences, Trees, DAGs, and Functions
B.1 Representation of Sets
B.2 Representation of Sequences
B.3 Representation of Trees and DAGs
B.4 Representation of Functions
B.5 Further Reading
C Software Resources
C.1 Finding and Accessing Software on the Internet
C.2 Machine Simulators
C.3 Compilers
C.4 Code-Generator Generators: BURG and IBURG
C.5 Profiling Tools
Society
Groupthink :
Two Party System
as Polyarchy :
Corruption of Regulators :
Bureaucracies :
Understanding Micromanagers
and Control Freaks : Toxic Managers :
Harvard Mafia :
Diplomatic Communication
: Surviving a Bad Performance
Review : Insufficient Retirement Funds as
Immanent Problem of Neoliberal Regime : PseudoScience :
Who Rules America :
Neoliberalism
: The Iron
Law of Oligarchy :
Libertarian Philosophy
Quotes
War and Peace
: Skeptical
Finance : John
Kenneth Galbraith :Talleyrand :
Oscar Wilde :
Otto Von Bismarck :
Keynes :
George Carlin :
Skeptics :
Propaganda : SE
quotes : Language Design and Programming Quotes :
Random IT-related quotes :
Somerset Maugham :
Marcus Aurelius :
Kurt Vonnegut :
Eric Hoffer :
Winston Churchill :
Napoleon Bonaparte :
Ambrose Bierce :
Bernard Shaw :
Mark Twain Quotes
Bulletin:
Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient
markets hypothesis :
Political Skeptic Bulletin, 2013 :
Unemployment Bulletin, 2010 :
Vol 23, No.10
(October, 2011) An observation about corporate security departments :
Slightly Skeptical Euromaydan Chronicles, June 2014 :
Greenspan legacy bulletin, 2008 :
Vol 25, No.10 (October, 2013) Cryptolocker Trojan
(Win32/Crilock.A) :
Vol 25, No.08 (August, 2013) Cloud providers
as intelligence collection hubs :
Financial Humor Bulletin, 2010 :
Inequality Bulletin, 2009 :
Financial Humor Bulletin, 2008 :
Copyleft Problems
Bulletin, 2004 :
Financial Humor Bulletin, 2011 :
Energy Bulletin, 2010 :
Malware Protection Bulletin, 2010 : Vol 26,
No.1 (January, 2013) Object-Oriented Cult :
Political Skeptic Bulletin, 2011 :
Vol 23, No.11 (November, 2011) Softpanorama classification
of sysadmin horror stories : Vol 25, No.05
(May, 2013) Corporate bullshit as a communication method :
Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law
History:
Fifty glorious years (1950-2000):
the triumph of the US computer engineering :
Donald Knuth : TAoCP
and its Influence of Computer Science : Richard Stallman
: Linus Torvalds :
Larry Wall :
John K. Ousterhout :
CTSS : Multix OS Unix
History : Unix shell history :
VI editor :
History of pipes concept :
Solaris : MS DOS
: Programming Languages History :
PL/1 : Simula 67 :
C :
History of GCC development :
Scripting Languages :
Perl history :
OS History : Mail :
DNS : SSH
: CPU Instruction Sets :
SPARC systems 1987-2006 :
Norton Commander :
Norton Utilities :
Norton Ghost :
Frontpage history :
Malware Defense History :
GNU Screen :
OSS early history
Classic books:
The Peter
Principle : Parkinson
Law : 1984 :
The Mythical Man-Month :
How to Solve It by George Polya :
The Art of Computer Programming :
The Elements of Programming Style :
The Unix Hater’s Handbook :
The Jargon file :
The True Believer :
Programming Pearls :
The Good Soldier Svejk :
The Power Elite
Most popular humor pages:
Manifest of the Softpanorama IT Slacker Society :
Ten Commandments
of the IT Slackers Society : Computer Humor Collection
: BSD Logo Story :
The Cuckoo's Egg :
IT Slang : C++ Humor
: ARE YOU A BBS ADDICT? :
The Perl Purity Test :
Object oriented programmers of all nations
: Financial Humor :
Financial Humor Bulletin,
2008 : Financial
Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related
Humor : Programming Language Humor :
Goldman Sachs related humor :
Greenspan humor : C Humor :
Scripting Humor :
Real Programmers Humor :
Web Humor : GPL-related Humor
: OFM Humor :
Politically Incorrect Humor :
IDS Humor :
"Linux Sucks" Humor : Russian
Musical Humor : Best Russian Programmer
Humor : Microsoft plans to buy Catholic Church
: Richard Stallman Related Humor :
Admin Humor : Perl-related
Humor : Linus Torvalds Related
humor : PseudoScience Related Humor :
Networking Humor :
Shell Humor :
Financial Humor Bulletin,
2011 : Financial
Humor Bulletin, 2012 :
Financial Humor Bulletin,
2013 : Java Humor : Software
Engineering Humor : Sun Solaris Related Humor :
Education Humor : IBM
Humor : Assembler-related Humor :
VIM Humor : Computer
Viruses Humor : Bright tomorrow is rescheduled
to a day after tomorrow : Classic Computer
Humor
The Last but not Least Technology is dominated by
two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt.
Ph.D
Copyright © 1996-2021 by Softpanorama Society. www.softpanorama.org
was initially created as a service to the (now defunct) UN Sustainable Development Networking Programme (SDNP)
without any remuneration. This document is an industrial compilation designed and created exclusively
for educational use and is distributed under the Softpanorama Content License.
Original materials copyright belong
to respective owners. Quotes are made for educational purposes only
in compliance with the fair use doctrine.
FAIR USE NOTICE This site contains
copyrighted material the use of which has not always been specifically
authorized by the copyright owner. We are making such material available
to advance understanding of computer science, IT technology, economic, scientific, and social
issues. We believe this constitutes a 'fair use' of any such
copyrighted material as provided by section 107 of the US Copyright Law according to which
such material can be distributed without profit exclusively for research and educational purposes.
This is a Spartan WHYFF (We Help You For Free)
site written by people for whom English is not a native language. Grammar and spelling errors should
be expected. The site contain some broken links as it develops like a living tree...
Disclaimer:
The statements, views and opinions presented on this web page are those of the author (or
referenced source) and are
not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness
of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be
tracked by Google please disable Javascript for this site. This site is perfectly usable without
Javascript.
Last modified: March 12, 2019
