Escape analysis is an optimization for identifying objects which do not escape the dynamic extent of a function; such objects can be stack-allocated, or 'flattened' so that usages of them are replaced with a series of local variables (the latter optimization is known as "scalar replacement").
An overview of the escape analysis algorithm used in Factor's Optimizing compiler: http://factor-language.blogspot.com/2008/08/algorithm-for-escape-analysis.html http://en.wikipedia.org/wiki/Escape_analysis
Linear scan: The linear scan algorithm sacrifices code quality for compilation speed; it only needs to make one or two passes over the intermediate representation to assign registers, and therefore runs in O(n) time; therefore it is much faster than graph coloring, which runs in O(n2) time.
Linear Scan Register Allocation, Massimiliano Poletto and Vivek Sarkar, http://www.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf
Linear Scan Register Allocation for the Java HotSpot Client Compiler, by Christian Wimmer, http://www.ssw.uni-linz.ac.at/Research/Papers/Wimmer04Master/
Quality and Speed in Linear-scan Register Allocation, by Omri Traub, Glenn Holloway, Michael D. Smith, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.8435
Graph coloring
Instruction Selection: Principles, Methods, & Applications: Gabriel Hjort Blindell (2016)
Universal Instruction Selection: 2018 PhD Dissertation; Gabriel Hjort Blindell Github and also here
Notes on Graph Algorithms Used in Optimizing Compilers - Carl Offner
Last modified 07 October 2024