Editing Register allocation (section)

=== Linear scan ===

Linear scan is another global register allocation approach. It was first proposed by Poletto et al. in 1999.{{sfn|Poletto|Sarkar|1999|p=895}} In this approach, the code is not turned into a graph. Instead, all the variables are linearly scanned to determine their live range, represented as an interval. Once the live ranges of all variables have been figured out, the intervals  are traversed chronologically. Although this traversal could help identifying variables whose live ranges interfere, no interference graph is being built and the variables are allocated in a greedy way.{{sfn|Cavazos|Moss|O’Boyle|2006|p=124}}

The motivation for this approach is speed; not in terms of execution time of the generated code, but in terms of time spent in code generation. Typically, the standard graph coloring approaches produce quality code, but have a significant [[Overhead (computing)|overhead]],{{sfn|Poletto|Sarkar|1999|p=902}}{{sfn|Wimmer|Mössenböck|2005|p=132}} the used graph coloring algorithm having a quadratic cost.{{sfn|Johansson|Sagonas|2002|p=102}} Owing to this feature, linear scan is the approach currently used in several JIT compilers, like the [[HotSpot (virtual machine)|Hotspot client compiler]], [[Chrome V8|V8]], [[Jikes RVM]],{{sfn|Eisl|Grimmer|Simon|Würthinger|2016|p=1}} and the Android Runtime (ART).<ref>{{Cite video |url=https://www.youtube.com/watch?v=fwMM6g7wpQ8 |title=The Evolution of ART - Google I/O 2016  |date=25 May 2016 |time=3m47s |work=Google}}</ref> The [[HotSpot (virtual machine)|Hotspot server compiler]] uses graph coloring for its superior code.{{sfn|Paleczny|Vick|Click|2001|p=1}}

==== Pseudocode ====

This describes the algorithm as first proposed by Poletto et al.,{{sfn|Poletto|Sarkar|1999|p=899}} where:
* '''R''' is the number of available registers.
* '''active''' is the list, sorted in order of increasing end point, of live intervals overlapping the current point and placed in registers.

 '''LinearScanRegisterAllocation'''
     active ← {}
     '''for each''' live interval ''i'', in order of increasing start point '''do'''
         ExpireOldIntervals(i)
         '''if''' length(active) = R '''then'''
             SpillAtInterval(i)
         '''else'''
             register[i] ← a register removed from pool of free registers
             add ''i'' to active, sorted by increasing end point
 
 '''ExpireOldIntervals(i)'''
     '''for each''' interval ''j'' '''in''' active, in order of increasing end point '''do'''
         '''if''' endpoint[j] ≥ startpoint[i] '''then'''
             '''return''' 
         remove ''j'' from active
         add register[j] to pool of free registers
 
 '''SpillAtInterval(i)'''
     spill ← last interval in active
     '''if''' endpoint[spill] > endpoint[i] '''then'''
         register[i] ← register[spill]
         location[spill] ← new stack location
         remove spill from active
         add ''i'' to active, sorted by increasing end point
     '''else'''
         location[i] ← new stack location

==== Drawbacks and further improvements ====
However, the linear scan presents two major drawbacks. First, due to its greedy aspect, it does not take lifetime holes into account, i.e. "ranges where the value of the variable is not needed".{{sfn|Eisl|Grimmer|Simon|Würthinger|2016|p=2}}{{sfn|Traub|Holloway|Smith|1998|p=143}} Besides, a spilled variable will stay spilled for its entire lifetime.
[[File:Shorter live ranges with SSA approach.png|thumb|Shorter live ranges with SSA approach]]
Many other research works followed up on the Poletto's linear scan algorithm. Traub et al., for instance, proposed an algorithm called second-chance binpacking aiming at generating code of better quality.{{sfn|Traub|Holloway|Smith|1998|p=141}}{{sfn|Poletto|Sarkar|1999|p=897}} In this approach, spilled variables get the opportunity to be stored later in a register by using a different [[Heuristic (computer science)|heuristic]] from the one used in the standard linear scan algorithm. Instead of using live intervals, the algorithm relies on live ranges, meaning that if a range needs to be spilled, it is not necessary to spill all the other ranges corresponding to this variable.

Linear scan allocation was also adapted to take advantage from the [[Static single assignment form|SSA form]]: the properties of this intermediate representation simplify the allocation algorithm and allow lifetime holes to be computed directly.{{sfn|Wimmer|Franz|2010|p=170}} First, the time spent in data-flow graph analysis, aimed at building the lifetime intervals, is reduced, namely because variables are unique.{{sfn|Mössenböck|Pfeiffer|2002|p=234}} It consequently produces shorter live intervals, because each new assignment corresponds to a new live interval.{{sfn|Mössenböck|Pfeiffer|2002|p=233}}{{sfn|Mössenböck|Pfeiffer|2002|p=229}} To avoid modeling intervals and liveness holes, Rogers showed a simplification called future-active sets that successfully removed intervals for 80% of instructions.{{sfn|Rogers|2020}}