jimmy wrote:
Steven Bosscher wrote:
Hi,
I found this old patch
(http://gcc.gnu.org/ml/gcc-patches/2003-06/msg01669.html) that refers
to pages 202-214 of Muchnick's "Advanced Compiler Design and
Implementation" book. That book still is not in my own compiler books
collection because of its price.
Since you've mentioned it, could you also suggest a few books worth
buying (for the benefit of the not-so-compiler-savvy-but-want-to-be
:). I think it would be very much appreciated!
This is my personal point of view about some not too old books about
compilers which I read and believe to worth to look at if you are
interested in compilers. Please, I don't want to argue if somebody
is not agree with me.
o Muchnik book is a fat one. Muchnick's book is rather encyclopedia
of optimizations and can be considered as collection of articles with
many details (sometimes too many). But some themes (like RA and
scheduling) are described not deep.
o Robert Morgan. Building an Optimizing compiler. Although the book
volume is small, this is not an appetizer. This is practically
description of Morgan's integral approach for building optimizing
compilers. The book contains very detail algorithms of all passes of
the proposed compiler back-end. A very interesting book to read about
RA but his proposed complicated approach (combined global/local/FAT
RA) is doubtful. I've tried it and found not working well for gcc.
Scheduling and software pipelining description is weak too.
o Cooper and Torczon. Engineering a compiler. It is close to their
course in Rice University. A good book to start study compiler from
parsing to code generation and basic optimizations. But if you are
familiar with the compilers, you probably don't find interesting
thoughts and approaches.
o Appel. Modern Compiler implementation in C/Java/ML. Another good
book to start to study compilers from parser to code generation and
basic optimizations. I especially like the version in ML (Modern
compiler implementation in ML).
o Aho/Lam/Sethi/Ulman. Compilers: Principles, Techniques, and
Tools. 2nd edition. Personally I don't like it because it is based on
outdated (although classical) book. I attached a review of this book
which I wrote more than year ago (when the book was not ready).
o Allen and Kennedy. Optimizing compilers for modern architectures.
It is book to study more advanced (not basic) optimizations like
dependence analysis, loop optimizations, inter-procedural
optimizations.
o I am waiting for Fischer's book (crafting compiler) which will be
published soon. I like his lectures but I am afraid using Java for
this book can hurt the book.
If you don't want to be compiler savvy but want to understand the
compiler, I'd recommend Appel's, Cooper's, Morgan's book in the same
priority.
There are a lot of other books about compilers but some of them are
too specialized or too trivial.
Review of the second addition of the Dragon Book.
Originally the book was to be called "21st century compilers". But
probably it is too ambitious name. Currently Amazon is selling the
1st edition plus online chapters from the 2nd edition. There is an
additional author Monica Lam, a professor of Standford University
(knowing her track of the researches I can guess that she probably
wrote the two best chapters about parallelism and locality). Chapters
5-11 were accessible starting Nov. 15 till Dec. 31 2005 online through
flash to prevent copying the book. It was hard to read it online and
flash permitted to print one page of very bad quality at a time.
Reading the chapters, I can guess that chapters prior 5 will be
without changes taken from the 1st edition of the Dragon book.
Chapter 5, Syntax directed translation, is pretty the same chapter
as in the 1st edition describing different attribute grammars to make
syntax trees, expression DAGs (with collapsed sub-expression) and
other translation. I did not find considerable changes in the
chapter. It is not the rocket science but probably it is the most
abstract and general description of the translation pass in compiler
books.
Chapter 6, Intermediate code generation, is actually more compact
and modern version of two chapters 6 (type checking) and 8
(intermediate code generation) from the 1st edition. Some obsolete
parts are removed and new concepts are added. It makes this chapter
is better than in the two ones in the 1st edition. Big drawback is
just mentioning SSA. IMHO It needs a deeper introduction in
algorithms of conversion to/from SSA. So Morgan's book (Building an
optimizing compiler) and Cooper's and Torczon's book (Engineering a
compiler) are much better description of SSA.
This is the first edition where GCC is mentioned (as an example of
compiler using the same IR for implementation of many languages).
Chapter 7, Runtime environment, is mainly more compact version of
the one in the 1st edition but it uses C++ and ML as example instead
of Pascal and Fortran in the 1st edition. Additionally the chapter
contains a big new part (40 pages) about garbage collection
algorithms:
o reference counting GC
o two mark-and-sweep GCs
o mark-and-compact GC
o copying GC
It also discusses several approaches to short-pause GCs and parallel
and concurrent GCs in details. In whole, the description of GC is a
bit better than another good description of GCs in Appel's book
(Modern Compiler Implementation in C/Java/ML).
Chapter 8, Code generation, is pretty the same chapter 9 (code
generation) from the 1st edition with small changes like mentioning
Java and Jit. It describes mainly target machines, storage layout and
allocation, code selection task (in a good and general way as pattern
matching algorithm), register allocation (a very brief and pathetic
description), peephole optimization in usual ad hoc way, and simple
local optimizations
There is some intersection with subsequent chapter (about CFG and
loop notions, etc).
Chapter 9, Machine-independent optimizations, is an improved version
of chapter 10 (code optimization) in the previous edition. Data flow
analysis is given in modern formalized way (lattice theory --
alternatively I would also recommend Copper's and Toczon's book as an
introduction in the theory). Also more detail description of PRE is
added to the chapter.
The last two chapters are absolutely new and they are very good.
o chapter 10. Instruction-level Parallelism
o chapter 11. Optimizing for Parallelism and Locality.
They are the best introduction in these fields what I saw in
Morgan's (Building an optimizing compiler), Muchnick's (Advanced
compiler design and implementation), Cooper's and Torczon's
(Engineering a compiler), and Allen's and Kennedy's (Optimizing
compilers for modern architectures) books. Although on my opinion
many issues in chapter "Optimizing for parallelism and locality" are
described deeper in Allen's and Kennedy's book.
Chapter about Instruction-Level parallelism mainly discusses insn
scheduling and software pipelining but mentions predication and
prefetching too. Insn scheduling and its conflict with the register
allocation is discussed on BB insn scheduling, dominator based
scheduling and region based scheduling. Software pipelining is
described in details on example of modulo scheduling including
variable expansion, if-reduction, register pressure decreasing, and
rotating register support.
A pretty big chapter (130 pages) about optimizing for parallelism is
devoted to improving data locality and parallelizing loops
(simultaneous execution of the loop on several CPU) with affine array
accesses. It needs data dependency analysis. The chapter describes
classical GCD test (greatest common division), heuristics to handle
large numbers of inequalities met in practice, and a specialized
linear integer programming solver. Data from the data dependencies
analysis is used for improving locality and parallelizing loops.
Locality can be improved by changing data layout and by blocking
(process arrays part by part or by *blocks* which can be fully placed
in cache). The chapter describes that in details. A half of the
chapter describes parallelizing loops (in other words execution of a
loop on several CPU) without and with synchronization through
pipelining (decomposing a task on stages executed on different
processors).
In general, 2nd edition is not the best description of all compiler
tasks and problems (some of them are pretty weak) but parts of them
(garbage collection, optimization for locality and using modern
processors parallelism) makes sense to have it on the bookshelf. But
personally I am not going to buy this book.
