Must-have for compiler writers and processor designers

Allen and Kennedy (A&K) haven't written your first compiler book. There's nothing about syntax analysis, code generation, instruction scheduling, or intermediate representations. You already know all that part, or you won't get very far in this book. Once you have the basics down, A&K is an irreplaceable reference.

It centers heavily on Fortran - even today, a mainstay of scientific computing and an active area of language development. Today, just as 50 years ago, the language's straightforward structure makes detailed behavioral analysis relatively easy. That's especially true in handling the array computations that soak up so many dozens (as of this writing) of CPU-hours per second on todays largest machines. There's far too much to summarize here, but A&K cover a huge range of processor features, including caches, multiple ALUs, vector units, chaining, and more. C code gets some attention as well, much needed because of the cultural weirdness around array handling in C. In every case, the focus is on the real-world kernels that need the help and on explicit ways of identifying and manipulating those code structures. As a result, the authors disregard the unreal situations that sometimes arise, e.g. in
"while (--n) *a++ = *b++ * *c++;"
Yes, the arrays pointed to by a, b, and c can overlap. But the pointer a can also point to a, b, c, or n, somewhere in its range - and likewise for pointers b and c, or all three. There is essentially no limit to how bad this can get, e.g when n is an alias for a, b, or c. Yes these are rare situations and generally errors - but I've seen on-the-fly code generation in production environments, so even the A&K example isn't as bad as it gets. I admit these to be pathological cases, though, better suited to an 'Obfuscated C' contest than to a compiler textbook.

The real disappointment comes from the section on compilation for Verilog and VHDL, and that disappointment may be a matter of emphasis only. The authors focus heavily on the strangeness of four-valued bits, which exist in Verilog and VHDL simulation, but not in synthesis. I.e., not in what really matters to a deployed application. The real challenge lies in compilation of C or Fortran into gates, a topic that the authors barely skim. That, however, is still a field of research exotica. It should be mentioned in a general book on compilation, as it is here, but awaits a text of its own.

All you processor designers out there should read the title a little differently. You should read this as "Modern Architectures for Optimizing Compilers," but you probably worked that out for yourself. If you have the luxury to define your own memory structure, all that analysis of memory access will give you plenty of ideas for your next ASIP. It will certainly give you lots of ways to quantify the behavior of your target applications, so you'll know just how to get the most MIPS per Mgate, including hard limits on how much hardware paralellism can actually do you any good.

All architects of performance computing systems, hardware or software, need this book. Even application developers can learn better ways to cooperate with the compilers and tools that run their codes. It has my very highest recommendation.

//wiredweird

Other Reviews

• An very innovative book
• Must-have for compiler writers and processor designers
• Very readable, very specific
• An excellent book on loop based optimization
• Finally, everything in one place.