-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathcompiler-books.html
More file actions
245 lines (230 loc) · 15.8 KB
/
compiler-books.html
File metadata and controls
245 lines (230 loc) · 15.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />
<title>Compiler Books — Compiler Programming</title>
<link rel="stylesheet" type="text/css" href="_static/pygments.css" />
<link rel="stylesheet" type="text/css" href="_static/agogo.css" />
<script data-url_root="./" id="documentation_options" src="_static/documentation_options.js"></script>
<script src="_static/jquery.js"></script>
<script src="_static/underscore.js"></script>
<script src="_static/doctools.js"></script>
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="prev" title="Learning Resources" href="learning-resources.html" />
</head><body>
<div class="header-wrapper" role="banner">
<div class="header">
<div class="headertitle"><a
href="index.html">Compiler Programming</a></div>
<div class="rel" role="navigation" aria-label="related navigation">
<a href="learning-resources.html" title="Learning Resources"
accesskey="P">previous</a> |
<a href="genindex.html" title="General Index"
accesskey="I">index</a>
</div>
</div>
</div>
<div class="content-wrapper">
<div class="content">
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<section id="compiler-books">
<h1>Compiler Books<a class="headerlink" href="#compiler-books" title="Permalink to this headline">¶</a></h1>
<p>I own a bunch of compiler books that I have purchased over the years.</p>
<section id="dragon-books">
<h2>Dragon Books<a class="headerlink" href="#dragon-books" title="Permalink to this headline">¶</a></h2>
<p>I have 3 editions of these.</p>
<ul class="simple">
<li><p>Principles of Compiler Design. Aho & Ullman, 1977.</p></li>
<li><p>Compilers: Principles, Techniques and Tools. Aho, Sethi, Ullman, 1986.</p></li>
<li><p>Compilers: Principles, Techniques and Tools, 2nd Ed. Aho, Lam, Sethi, Ullman, 2006.</p></li>
</ul>
<p>These books are criticised today because of the excessive focus on lexical analysis and parsing techniques.
While this is true, they do cover various aspects of a compiler backend such as intermediate representations and
optimization techniques including peephole optimization, data flow analysis, register allocation etc.
I found the description of the lattice in a data flow analysis quite accessible.</p>
<p>The 2nd edition adopts a more mathematical presentation style, whereas the earlier editions present
algorithms using pseudo code. I think the 1986 edition is the best.</p>
<p>The dragon books are a bit dated in that newer techniques such as Static Single Assignment or Graph
Coloring Register Allocation etc. are not covered in any detail. I would even say that these books are not
useful if your goal is to work with SSA IR.</p>
<p>For a different take on 2nd edition see <a class="reference external" href="https://gcc.gnu.org/wiki/Review_of_the_second_addition_of_the_Dragon_Book.">Review of the second addition of the “Dragon Book”</a>.</p>
</section>
<section id="engineering-a-compiler-2nd-ed-cooper-torczon-2012">
<h2>Engineering a Compiler, 2nd Ed. Cooper & Torczon. 2012.<a class="headerlink" href="#engineering-a-compiler-2nd-ed-cooper-torczon-2012" title="Permalink to this headline">¶</a></h2>
<p>This is a more modern version of the Dragon book. It is less focused on the lexical analysis / parsing
phases, and covers the later phases of a compiler in more detail. Exposition is similar to the Dragon book, i.e. describes
techniques conceptually, and some algorithms are described in more detail using a form of pseudo code.</p>
<p>Defines an intermediate language called ILOC, but this IR does not have support for function calls.</p>
<p>In practice, I found this book helpful when implementing the Dominator algorithm and SSA transformation. However, it left out
important parts in its coverage of SSA which meant that the algorithms as described do not work. For instance:</p>
<ul class="simple">
<li><p>The SSA construction algorithm inserts Phis in blocks where the original variable is dead (semi-pruned SSA). This then
causes the renaming phase to fail as there is no available definition of the variable.</p></li>
<li><p>Liveness analysis does not cover SSA form and does not handle phis correctly.</p></li>
<li><p>Exiting out of SSA is described conceptually but the algorithms are not described in detail.</p></li>
</ul>
<p>In practice though it is easy to recommend Engineering a Compiler over the Dragon books.</p>
<p>Both this and the Dragon books describe ahead of time compilers and cover topics that are suited for procedural languages
such as C or traditional Pascal or Fortran. They cover both front-end and back-end techniques; however, on the front-end
side, interesting topics such as Object Orientation, Closures, Generics, Semantic analysis of more complex languages
such as Java are not covered.</p>
</section>
<section id="modern-compiler-implementation-in-c-appel-1998-tiger-book">
<h2>Modern Compiler Implementation in C. Appel. 1998. (Tiger book)<a class="headerlink" href="#modern-compiler-implementation-in-c-appel-1998-tiger-book" title="Permalink to this headline">¶</a></h2>
<p>This book takes a hands on tutorial like approach to describing how to implement both the front-end and back-end
of a compiler, using a toy language called Tiger as an example. Algorithms are described in pseudo code.
If I had to choose from the Dragon book, Engineering a compiler, and this book, I would pick this one and
Engineering a Compiler.</p>
<p>It covers a lot of techniques, and usually presents algorithms in pseudo code form. I consulted this book
when implementing SSA and SCCP, but the descriptions were not sufficiently comprehensive so that I had to
consult other material too.</p>
<p>This book covers functional languages, closures, as well as Object Oriented languages such as Java. Type inference is
covered too.</p>
</section>
<section id="crafting-a-compiler-fischer-leblanc-cytron-2010">
<h2>Crafting a Compiler. Fischer, LeBlanc, Cytron. 2010.<a class="headerlink" href="#crafting-a-compiler-fischer-leblanc-cytron-2010" title="Permalink to this headline">¶</a></h2>
<p>The last couple of chapters are the most interesting - these focus on code generation and program optimization.</p>
<p>The 2nd edition of the book (with Cytron as co author) has a description of Static Single assignment. However the
description is based on a statement level IR, rather than one that uses Basic Blocks. Also, the algorithm for exiting
SSA is not described.</p>
<p>The 1st edition describes data flow analysis in more detail, but does not cover SSA.</p>
<p>Apart from the final two chapters, the rest of the book is about parsing and semantic analysis.</p>
</section>
<section id="building-an-optimizing-compiler-bob-morgan-1998">
<h2>Building an Optimizing Compiler. Bob Morgan. 1998.<a class="headerlink" href="#building-an-optimizing-compiler-bob-morgan-1998" title="Permalink to this headline">¶</a></h2>
<p>I have the kindle edition which is very poor and hard to read. I wish I had a paper copy.</p>
<p>This book is almost completely about the backend of the compiler. I consulted the description of SCCP and
based my implementation at least in part on the descriptions. In particular I found some discussion about how to
exploit local knowledge in conditional branches to handle null checks, which was useful, and not discussed in
other books.</p>
</section>
<section id="advanced-compiler-design-implementation-muchnick-1997">
<h2>Advanced Compiler Design & Implementation. Muchnick. 1997.<a class="headerlink" href="#advanced-compiler-design-implementation-muchnick-1997" title="Permalink to this headline">¶</a></h2>
<p>I have the kindle edition, which is very poor quality and hard to read.</p>
<p>This book is mostly about the backend of a compiler, focusing on optimization.</p>
<p>My impression is that this book describes many algorithms in detail. But when I tried to implement one of the
simpler algorithms (18.1 Unreachable Code Elimination) I found that the description left out a
part (No_Path) of the algorithm.</p>
<p>Introduces the idea of multiple levels of intermediate representation, HIR, MIR and LIR.
I guess this has influenced many compiler implementations.</p>
<p>Its coverage of SSA is rudimentary - I guess it was written when SSA was still very new. Hence if you are
working with SSA IR then you will need to consult other material.</p>
<p>The Graph Coloring register allocation algorithm is presented in detail and is based on the paper by
Preston Briggs.</p>
<p>This book has a reputation of containing many errors, although I assume the latest printings have the errors
fixed.</p>
<p>Despite its faults, it is a must have book if you want to learn about compiler construction.</p>
</section>
<section id="retargetable-c-compiler-a-design-and-implementation-hanson-fraser-1995">
<h2>Retargetable C Compiler, A: Design and Implementation. Hanson & Fraser. 1995.<a class="headerlink" href="#retargetable-c-compiler-a-design-and-implementation-hanson-fraser-1995" title="Permalink to this headline">¶</a></h2>
<p>Describes a production C compiler. Contains detailed walkthrough of the actual compiler code.</p>
<p>Weak on theoretical aspects, and limited by features of the compiler being described. The compiler
implementation is a single pass code generator, hence its optimizing capabilities are limited.
There is no coverage of data flow analysis or SSA as these weren’t used by the implementation.</p>
<p>In short this describes an old school C compiler that generates code fast, but lacks optimizations.</p>
</section>
<section id="program-flow-analysis-theory-and-applications-editors-muchnick-jones-1981">
<h2>Program Flow Analysis: Theory and Applications. Editors Muchnick, Jones. 1981.<a class="headerlink" href="#program-flow-analysis-theory-and-applications-editors-muchnick-jones-1981" title="Permalink to this headline">¶</a></h2>
<p>Collection of essays on program analysis, by various authors. This is pre-SSA, hence a bit
dated.</p>
</section>
<section id="ssa-based-compiler-design-various-authors">
<h2>SSA-Based Compiler Design - various authors<a class="headerlink" href="#ssa-based-compiler-design-various-authors" title="Permalink to this headline">¶</a></h2>
<p>An online version of this book is available <a class="reference external" href="https://pfalcon.github.io/ssabook/latest/book-full.pdf">here</a>.
This book is a collection of articles on various topics related to SSA. As such it presents more
recent knowledge regarding SSA construction, optimizations based on SSA, and finally destruction and
register allocation. I will have more to say about this book as I use it.</p>
</section>
<section id="other-book-reviews">
<h2>Other Book Reviews<a class="headerlink" href="#other-book-reviews" title="Permalink to this headline">¶</a></h2>
<ul class="simple">
<li><p><a class="reference external" href="https://gcc.gnu.org/wiki/ListOfCompilerBooks">List of compiler books</a></p></li>
</ul>
</section>
</section>
<div class="clearer"></div>
</div>
</div>
</div>
</div>
<div class="sidebar">
<h3>Table of Contents</h3>
<p class="caption" role="heading"><span class="caption-text">Preliminaries</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="prelim-impl-lang.html">Compiler Implementation Language</a></li>
<li class="toctree-l1"><a class="reference internal" href="ez-lang.html">The EeZee Programming Language</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">Parsing Techniques</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="lexical-analysis.html">Lexical Analysis</a></li>
<li class="toctree-l1"><a class="reference internal" href="syntax-analysis.html">Syntax Analysis</a></li>
<li class="toctree-l1"><a class="reference internal" href="abstract-syntax-tree.html">Abstract Syntax Tree</a></li>
<li class="toctree-l1"><a class="reference internal" href="type-systems.html">Type Systems</a></li>
<li class="toctree-l1"><a class="reference internal" href="semantic-analysis.html">Semantic Analysis</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">Backend Basics</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="intermediate-representations.html">Intermediate Representations</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">Learning Resources</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="learning-resources.html">Learning Resources</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">Reviews</span></p>
<ul class="current">
<li class="toctree-l1 current"><a class="current reference internal" href="#">Compiler Books</a><ul>
<li class="toctree-l2"><a class="reference internal" href="#dragon-books">Dragon Books</a></li>
<li class="toctree-l2"><a class="reference internal" href="#engineering-a-compiler-2nd-ed-cooper-torczon-2012">Engineering a Compiler, 2nd Ed. Cooper & Torczon. 2012.</a></li>
<li class="toctree-l2"><a class="reference internal" href="#modern-compiler-implementation-in-c-appel-1998-tiger-book">Modern Compiler Implementation in C. Appel. 1998. (Tiger book)</a></li>
<li class="toctree-l2"><a class="reference internal" href="#crafting-a-compiler-fischer-leblanc-cytron-2010">Crafting a Compiler. Fischer, LeBlanc, Cytron. 2010.</a></li>
<li class="toctree-l2"><a class="reference internal" href="#building-an-optimizing-compiler-bob-morgan-1998">Building an Optimizing Compiler. Bob Morgan. 1998.</a></li>
<li class="toctree-l2"><a class="reference internal" href="#advanced-compiler-design-implementation-muchnick-1997">Advanced Compiler Design & Implementation. Muchnick. 1997.</a></li>
<li class="toctree-l2"><a class="reference internal" href="#retargetable-c-compiler-a-design-and-implementation-hanson-fraser-1995">Retargetable C Compiler, A: Design and Implementation. Hanson & Fraser. 1995.</a></li>
<li class="toctree-l2"><a class="reference internal" href="#program-flow-analysis-theory-and-applications-editors-muchnick-jones-1981">Program Flow Analysis: Theory and Applications. Editors Muchnick, Jones. 1981.</a></li>
<li class="toctree-l2"><a class="reference internal" href="#ssa-based-compiler-design-various-authors">SSA-Based Compiler Design - various authors</a></li>
<li class="toctree-l2"><a class="reference internal" href="#other-book-reviews">Other Book Reviews</a></li>
</ul>
</li>
</ul>
<div role="search">
<h3 style="margin-top: 1.5em;">Search</h3>
<form class="search" action="search.html" method="get">
<input type="text" name="q" />
<input type="submit" value="Go" />
</form>
</div>
</div>
<div class="clearer"></div>
</div>
</div>
<div class="footer-wrapper">
<div class="footer">
<div class="left">
<div role="navigation" aria-label="related navigaton">
<a href="learning-resources.html" title="Learning Resources"
>previous</a> |
<a href="genindex.html" title="General Index"
>index</a>
</div>
<div role="note" aria-label="source link">
<br/>
<a href="_sources/compiler-books.rst.txt"
rel="nofollow">Show Source</a>
</div>
</div>
<div class="right">
<div class="footer" role="contentinfo">
© Copyright 2024, Dibyendu Majumdar.
Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 4.3.2.
</div>
</div>
<div class="clearer"></div>
</div>
</div>
</body>
</html>