Editing Register allocation (section)

==== 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}}