Friday, June 14, 2013

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 -

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. -

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 -

"Global Code Motion Global Value Numbering" by Click -

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. -

Another paper on phi node elimination:
"Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency" by Boissinot, Darte, and Rastello -

And some of the papers they cite:
"Fast Copy Coalescing and Live-Range Identification" by  Budimlic et. al. -

"Fast liveness checking for SSA-form programs" by Bossinot et. al -

Liveness analysis (necessary for register allocation):

Good overview of the Chaitin graph coloring algorithm and extensions:

"Register Allocation via Graph Coloring" by Briggs -

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 -

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 -

Register allocation in SSA (really cool idea, but coalescing seems tough...):
"Register allocation for programs in SSA-form" by Hack, Grund, and Goos -

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 -

No comments:

Post a Comment