Compiler Theory Links

I found these papers/links useful when writing the PP and GP compiler backends, so I'm saving them here. I'll try to list them front->back the way our compilers use them.

Computing dominance information (necessary for computing SSA form, among other things):

"A Simple, Fast Dominance Algorithm" by Cooper, Harvey, and Kennedy -

http://www.hipersoft.rice.edu/grads/publications/dom14.pdf

The classic paper on computing SSA form (they also present an algorithm for computing dominance, but the above one is much easier to implement, more elegant, and faster):

"Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" by Cytron et. al. -

http://grothoff.org/christian/teaching/2007/3353/papers/ssa.pdf

Now known as Sparse Conditional Constant Propagation (SCCP), this algorithm can also be extended relatively easily to do range analysis:

"Constant Propagation with Conditional Branches" by Wegman and Zadeck - http://dl.acm.org/ft_gateway.cfm?ftid=32613&id=103136

"Global Code Motion Global Value Numbering" by Click - https://courses.cs.washington.edu/courses/cse501/04wi/papers/click-pldi95.pdf

Coming out of SSA (right now, I'm only using their Method I and relying on copy propagation during register allocation to get rid of copies):

"Translating out of Single Static Assignment Form" by Sreedhar et. al. -

http://www.tjhsst.edu/~rlatimer/papers/sreedharTranslatingOutOfStaticSingleAssignmentForm.pdf

Another paper on phi node elimination:
"Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency" by Boissinot, Darte, and Rastello - hal.inria.fr/docs/00/34/99/25/PDF/OutSSA-RR.pdf

And some of the papers they cite:
"Fast Copy Coalescing and Live-Range Identification" by  Budimlic et. al. - http://cseweb.ucsd.edu/classes/sp02/cse231/kenpldi.pdf

"Fast liveness checking for SSA-form programs" by Bossinot et. al - http://rw4.cs.uni-saarland.de/~grund/papers/cgo08-liveness.pdf

Liveness analysis (necessary for register allocation):

http://en.wikipedia.org/wiki/Live_variable_analysis

Good overview of the Chaitin graph coloring algorithm and extensions:

"Register Allocation via Graph Coloring" by Briggs -

http://www.cs.utexas.edu/~mckinley/380C/lecs/briggs-thesis-1992.pdf

An extension to allocator described above which can guarantee that register coalescing never results in extra spilling - important to us since we only have a limited number of registers and spilling is expensive:

"Iterated Register Coalescing" by George and Appel -

http://www.cs.cmu.edu/afs/cs/academic/class/15745-s07/www/papers/george.pdf

Another extension to the classic Chaitin-Briggs allocator that can allow it to handle vector register allocation, also used by intel and r300g drivers:

"Retargetable Graph-Coloring Register Allocation for Irregular Architectures" by Runeson and Nystrom -

http://user.it.uu.se/~svenolof/wpo/AllocSCOPES2003.20030626b.pdf

Register allocation in SSA (really cool idea, but coalescing seems tough...):
"Register allocation for programs in SSA-form" by Hack, Grund, and Goos - http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.1578&rep=rep1&type=pdf

How to make coalescing easier, and solve a nasty problem with memory-to-memory copies, by using the classic out-of-SSA algorithm with SSA-based register allocation:

"SSA Elimination after Register Allocation" by Pereira and Palsberg - compilers.cs.ucla.edu/fernando/publications/drafts/ssaElimination.pdf