Register allocation

<h2 id="context">Context</h2>
See also: <a href="/facts/Compiler/WNfCDFJe">Compiler</a> and <a href="/facts/Interpreter_(computing)/JB85fbyb">Interpreter (computing)</a>
<h3>Principle</h3>
See also: <a href="/facts/Computer_data_storage/wPHKFpdx">Computer data storage</a> and <a href="/facts/Memory_hierarchy/ttwjvRyd">Memory hierarchy</a>
Different number of scalar registers in the most common architectures<table><tbody><tr><th>Architecture</th><th scope="col">32 bit</th><th scope="col">64 bit</th></tr><tr><th scope="row">ARM</th><td>15</td><td>31</td></tr><tr><th scope="row">Intel x86</th><td>8</td><td>16</td></tr><tr><th scope="row">MIPS</th><td>32</td><td>32</td></tr><tr><th scope="row">POWER/PowerPC</th><td>32</td><td>32</td></tr><tr><th scope="row">RISC-V</th><td>16/32</td><td>32</td></tr><tr><th scope="row">SPARC</th><td>31</td><td>31</td></tr></tbody></table>

In many <a href="/facts/Programming_language/cWTYbgWa">programming languages</a>, the programmer may use any number of <a href="/facts/Variable_(computer_science)/VoCKtwml">variables</a>. The computer can quickly read and write <a href="/facts/Processor_register/32RvbUdz">registers</a> in the <a href="/facts/Central_processing_unit/Jxp1bqMV">CPU</a>, so the <a href="/facts/Computer_program/e38jH9N9">computer program</a> runs faster when more variables can be in the CPU's registers.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> Also, sometimes code accessing registers is more compact, so the code is smaller, and can be fetched faster if it uses registers rather than memory. However, the number of registers is limited. Therefore, when the <a href="/facts/Compiler_(computing)/WNfCDFJe">compiler</a> is translating code to machine-language, it must decide how to allocate variables to the limited number of registers in the CPU.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
Not all variables are <a href="/facts/Liveness_analysis/GEHK3I2c">in use</a> (or "live") at the same time, so, over the lifetime of a program, a given register may be used to hold different variables. However, two variables in use at the same time cannot be assigned to the same register without corrupting one of the variables. If there are not enough registers to hold all the variables, some variables may be moved to and from <a href="/facts/Random_access_memory/DuD4bxh6">RAM</a>. This process is called "spilling" the registers.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> Over the lifetime of a program, a variable can be both spilled and stored in registers: this variable is then considered as "split".<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> Accessing RAM is significantly slower than accessing registers <a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> and so a compiled program runs slower. Therefore, an optimizing compiler aims to assign as many variables to registers as possible. A high "<a href="/facts/Register_pressure/8p8vwUeE">Register pressure</a>" is a technical term that means that more spills and reloads are needed; it is defined by Braun et al. as "the number of simultaneously live variables at an instruction".<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
In addition, some computer designs <a href="/facts/Cache_(computing)/gmJYN8wm">cache</a> frequently-accessed registers. So, programs can be further optimized by assigning the same register to a source and destination of a move instruction whenever possible. This is especially important if the compiler is using an <a href="/facts/Intermediate_representation/s0qRrbfh">intermediate representation</a> such as <a href="/facts/Static_single_assignment_form/HnDHfx6I">static single-assignment form</a> (SSA). In particular, when SSA is not fully optimized it can artificially generate additional move instructions.

<h3>Components of register allocation</h3>
Register allocation consists therefore of choosing where to store the variables at runtime, i.e. inside or outside registers. If the variable is to be stored in registers, then the allocator needs to determine in which register(s) this variable will be stored. Eventually, another challenge is to determine the duration for which a variable should stay at the same location.
A register allocator, disregarding the chosen allocation strategy, can rely on a set of core actions to address these challenges. These actions can be gathered in several different categories:<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

Move insertion
This action consists of increasing the number of move instructions between registers, i.e. make a variable live in different registers during its lifetime, instead of one. This occurs in the split live range approach.
Spilling
This action consists of storing a variable into memory instead of registers.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
Assignment
This action consists of assigning a register to a variable.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
Coalescing
This action consists of limiting the number of moves between registers, thus limiting the total number of instructions. For instance, by identifying a variable live across different methods, and storing it into one register during its whole lifetime.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
Many register allocation approaches optimize for one or more specific categories of actions.

<h3>Common problems raised in register allocation</h3>
Register allocation raises several problems that can be tackled (or avoided) by different register allocation approaches. Three of the most common problems are identified as follows:

Aliasing
In some architectures, assigning a value to one register can affect the value of another: this is called aliasing. For example, the <a href="/facts/X86/Kypq5fgu">x86</a> architecture has four general purpose 32-bit registers that can also be used as 16-bit or 8-bit registers.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> In this case, assigning a 32-bit value to the eax register will affect the value of the al register.
Pre-coloring
This problem is an act to force some variables to be assigned to particular registers. For example, in <a href="/facts/PowerPC/DqmM9y50">PowerPC</a> <a href="/facts/Calling_convention/FtzN2BKj">calling conventions</a>, parameters are commonly passed in R3-R10 and the return value is passed in R3.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
NP-Problem
Chaitin et al. showed that register allocation is an <a href="/facts/NP-completeness/NFPv56DU">NP-complete</a> problem. They reduce the <a href="/facts/Graph_coloring/J6HoBfP0">graph coloring</a> problem to the register allocation problem by showing that for an arbitrary graph, a program can be constructed such that the register allocation for the program (with registers representing nodes and machine registers representing available colors) would be a coloring for the original graph. As Graph Coloring is an NP-Hard problem and Register Allocation is in NP, this proves the NP-completeness of the problem.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>
<h2 id="register-allocation-techniques">Register allocation techniques</h2>
Register allocation can happen over a <a href="/facts/Basic_block/HPL1Nkvs">basic block</a> of code: it is said to be "local", and was first mentioned by Horwitz et al.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> As basic blocks do not contain branches, the allocation process is thought to be fast, because the management of <a href="/facts/Control-flow_graph/BLsvNzcP">control-flow graph</a> merge points in register allocation reveals itself a time-consuming operation.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> However, this approach is thought not to produce as optimized code as the "global" approach, which operates over the whole compilation unit (a method or procedure for instance).<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>

<h3>Graph-coloring allocation</h3>
See also: <a href="/facts/Graph_coloring/J6HoBfP0">Graph coloring</a>
Graph-coloring allocation is the predominant approach to solve register allocation.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a><a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> It was first proposed by Chaitin et al.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>
In this approach, nodes in the <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> represent live ranges (<a href="/facts/Variable_(computer_science)/VoCKtwml">variables</a>, <a href="/facts/Temporary_variable/sQaCQM3a">temporaries</a>, virtual/symbolic registers) that are candidates for register allocation. Edges connect live ranges that interfere, i.e., live ranges that are simultaneously live at at least one program point. Register allocation then reduces to the <a href="/facts/Graph_coloring/J6HoBfP0">graph coloring</a> problem in which colors (registers) are assigned to the nodes such that two nodes connected by an edge do not receive the same color.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>
Using <a href="/facts/Live_variable_analysis/GEHK3I2c">liveness analysis</a>, an interference graph can be built. The interference graph, which is an <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">undirected graph</a> where the nodes are the program's variables, is used to model which variables cannot be allocated to the same register.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>

<h4>Principle</h4>
The main phases in a Chaitin-style graph-coloring register allocator are:<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a>

<ol><li>Renumber: discover live range information in the source program.</li>
<li>Build: build the interference graph.</li>
<li>Coalesce: merge the live ranges of non-interfering variables related by copy instructions.</li>
<li>Spill cost: compute the spill cost of each variable. This assesses the impact of mapping a variable to memory on the speed of the final program.</li>
<li>Simplify: construct an ordering of the nodes in the inferences graph</li>
<li>Spill Code: insert spill instructions, i.e. loads and stores to commute values between registers and memory.</li>
<li>Select: assign a register to each variable.</li></ol>
<h4>Drawbacks and further improvements</h4>
The graph-coloring allocation has three major drawbacks. First, it relies on graph-coloring, which is an <a href="/facts/NP-completeness/NFPv56DU">NP-complete problem</a>, to decide which variables are spilled. Finding a minimal coloring graph is indeed an NP-complete problem.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a> Second, unless live-range splitting is used, evicted variables are spilled everywhere: store instructions are inserted as early as possible, i.e., just after variable definitions; load instructions are respectively inserted late, just before variable use. Third, a variable that is not spilled is kept in the same register throughout its whole lifetime.<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a>
On the other hand, a single register name may appear in multiple register classes, where a class is a set of register names that are interchangeable in a particular role. Then, multiple register names may be aliases for a single hardware register.<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a> 
Finally, graph coloring is an aggressive technique for allocating registers, but is computationally expensive due to its use of the interference graph, which can have a worst-case size that is <a href="/facts/Time_complexity/77T62gmf">quadratic</a> in the number of live ranges.<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a>
The traditional formulation of graph-coloring register allocation implicitly assumes a single bank of non-overlapping general-purpose registers and does not handle irregular architectural features like overlapping registers pairs, special purpose registers and multiple register banks.<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a>
One later improvement of Chaitin-style graph-coloring approach was found by Briggs et al.: it is called conservative coalescing. This improvement adds a criterion to decide when two live ranges can be merged. Mainly, in addition to the non-interfering requirements, two variables can only be coalesced if their merging will not cause further spilling. Briggs et al. introduces a second improvement to Chaitin's works which is biased coloring. Biased coloring tries to assign the same color in the graph-coloring to live range that are copy related.<a class="footnote-ref" id="fnref:29" href="#fn:29">29</a>

<h3>Linear scan</h3>
Linear scan is another global register allocation approach. It was first proposed by Poletto et al. in 1999.<a class="footnote-ref" id="fnref:30" href="#fn:30">30</a> 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.<a class="footnote-ref" id="fnref:31" href="#fn:31">31</a>
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 <a href="/facts/Overhead_(computing)/e2jgPrHr">overhead</a>,<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a><a class="footnote-ref" id="fnref:33" href="#fn:33">33</a> the used graph coloring algorithm having a quadratic cost.<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a> Owing to this feature, linear scan is the approach currently used in several JIT compilers, like the <a href="/facts/HotSpot_(virtual_machine)/m6vjRXvm">Hotspot client compiler</a>, <a href="/facts/Chrome_V8/0Fd3taMh">V8</a>, <a href="/facts/Jikes_RVM/IIwrVMDv">Jikes RVM</a>,<a class="footnote-ref" id="fnref:35" href="#fn:35">35</a> and the Android Runtime (ART).<a class="footnote-ref" id="fnref:36" href="#fn:36">36</a> The <a href="/facts/HotSpot_(virtual_machine)/m6vjRXvm">Hotspot server compiler</a> uses graph coloring for its superior code.<a class="footnote-ref" id="fnref:37" href="#fn:37">37</a>

<h4>Pseudocode</h4>
This describes the algorithm as first proposed by Poletto et al.,<a class="footnote-ref" id="fnref:38" href="#fn:38">38</a> where:

<ul><li>R is the number of available registers.</li>
<li>active is the list, sorted in order of increasing end point, of live intervals overlapping the current point and placed in registers.</li></ul>
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

<h4>Drawbacks and further improvements</h4>
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".<a class="footnote-ref" id="fnref:39" href="#fn:39">39</a><a class="footnote-ref" id="fnref:40" href="#fn:40">40</a> Besides, a spilled variable will stay spilled for its entire lifetime.

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.<a class="footnote-ref" id="fnref:41" href="#fn:41">41</a><a class="footnote-ref" id="fnref:42" href="#fn:42">42</a> In this approach, spilled variables get the opportunity to be stored later in a register by using a different <a href="/facts/Heuristic_(computer_science)/PM2qkoa2">heuristic</a> 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 <a href="/facts/Static_single_assignment_form/HnDHfx6I">SSA form</a>: the properties of this intermediate representation simplify the allocation algorithm and allow lifetime holes to be computed directly.<a class="footnote-ref" id="fnref:43" href="#fn:43">43</a> First, the time spent in data-flow graph analysis, aimed at building the lifetime intervals, is reduced, namely because variables are unique.<a class="footnote-ref" id="fnref:44" href="#fn:44">44</a> It consequently produces shorter live intervals, because each new assignment corresponds to a new live interval.<a class="footnote-ref" id="fnref:45" href="#fn:45">45</a><a class="footnote-ref" id="fnref:46" href="#fn:46">46</a> To avoid modeling intervals and liveness holes, Rogers showed a simplification called future-active sets that successfully removed intervals for 80% of instructions.<a class="footnote-ref" id="fnref:47" href="#fn:47">47</a>

<h3>Rematerialization</h3>
See also: <a href="/facts/Rematerialization/VBedEPpw">Rematerialization</a>
<h3>Coalescing</h3>
See also: <a href="/facts/Coalescing_(computer_science)/zpX2lMK1">Coalescing (computer science)</a>
In the context of register allocation, coalescing is the act of merging variable-to-variable move operations by allocating those two variables to the same location. The coalescing operation takes place after the interference graph is built. Once two nodes have been coalesced, they must get the same color and be allocated to the same register, once the copy operation becomes unnecessary.<a class="footnote-ref" id="fnref:48" href="#fn:48">48</a>
Doing coalescing might have both positive and negative impacts on the colorability of the interference graph.<a class="footnote-ref" id="fnref:49" href="#fn:49">49</a> For example, one negative impact that coalescing could have on graph inference colorability is when two nodes are coalesced, as the result node will have a union of the edges of those being coalesced.<a class="footnote-ref" id="fnref:50" href="#fn:50">50</a>
A positive impact of coalescing on inference graph colorability is, for example, when a node interferes with both nodes being coalesced, the degree of the node is reduced by one which leads to improving the overall colorability of the interference graph.<a class="footnote-ref" id="fnref:51" href="#fn:51">51</a>
There are several coalescing heuristics available:<a class="footnote-ref" id="fnref:52" href="#fn:52">52</a>

Aggressive coalescing
It was first introduced in Chaitin's original register allocator. This heuristic aims at coalescing any non-interfering, copy-related nodes.<a class="footnote-ref" id="fnref:53" href="#fn:53">53</a> From the perspective of copy elimination, this heuristic has the best results.<a class="footnote-ref" id="fnref:54" href="#fn:54">54</a> On the other hand, aggressive coalescing could impact the colorability of the inference graph.<a class="footnote-ref" id="fnref:55" href="#fn:55">55</a>
Conservative Coalescing
It mainly uses the same heuristic as aggressive coalescing but it merges moves if, and only if, it does not compromise the colorability of the interference graph.<a class="footnote-ref" id="fnref:56" href="#fn:56">56</a>
Iterated coalescing
It removes one particular move at the time, while keeping the colorability of the graph.<a class="footnote-ref" id="fnref:57" href="#fn:57">57</a>
Optimistic coalescing
It is based on aggressive coalescing, but if the inference graph colorability is compromised, then it gives up as few moves as possible.<a class="footnote-ref" id="fnref:58" href="#fn:58">58</a>
<h3>Mixed approaches</h3>
<h4>Hybrid allocation</h4>
Some other register allocation approaches do not limit to one technique to optimize register's use. Cavazos et al., for instance, proposed a solution where it is possible to use both the linear scan and the graph coloring algorithms.<a class="footnote-ref" id="fnref:59" href="#fn:59">59</a> In this approach, the choice between one or the other solution is determined dynamically: first, a <a href="/facts/Machine_learning/e0w0XJTu">machine learning</a> algorithm is used "offline", that is to say not at runtime, to build a heuristic function that determines which allocation algorithm needs to be used. The heuristic function is then used at runtime; in light of the code behavior, the allocator can then choose between one of the two available algorithms.<a class="footnote-ref" id="fnref:60" href="#fn:60">60</a>
Trace register allocation is a recent approach developed by Eisl et al.<a class="footnote-ref" id="fnref:61" href="#fn:61">61</a><a class="footnote-ref" id="fnref:62" href="#fn:62">62</a> This technique handles the allocation locally: it relies on dynamic <a href="/facts/Profiling_(computer_programming)/JbSlDHPP">profiling</a> data to determine which branches will be the most frequently used in a given control flow graph. It then infers a set of "traces" (i.e. code segments) in which the merge point is ignored in favor of the most used branch. Each trace is then independently processed by the allocator. This approach can be considered as hybrid because it is possible to use different register allocation algorithms between the different traces.<a class="footnote-ref" id="fnref:63" href="#fn:63">63</a>

<h4>Split allocation</h4>
Split allocation is another register allocation technique that combines different approaches, usually considered as opposite. For instance, the hybrid allocation technique can be considered as split because the first heuristic building stage is performed offline, and the heuristic use is performed online.<a class="footnote-ref" id="fnref:64" href="#fn:64">64</a> In the same fashion, B. Diouf et al. proposed an allocation technique relying both on offline and online behaviors, namely static and dynamic compilation.<a class="footnote-ref" id="fnref:65" href="#fn:65">65</a><a class="footnote-ref" id="fnref:66" href="#fn:66">66</a> During the offline stage, an optimal spill set is first gathered using <a href="/facts/Integer_programming/MDaaadoA">Integer Linear Programming</a>. Then, live ranges are annotated using the compressAnnotation algorithm which relies on the previously identified optimal spill set. Register allocation is performed afterwards during the online stage, based on the data collected in the offline phase.<a class="footnote-ref" id="fnref:67" href="#fn:67">67</a>
In 2007, Bouchez et al. suggested as well to split the register allocation in different stages, having one stage dedicated to spilling, and one dedicated to coloring and coalescing.<a class="footnote-ref" id="fnref:68" href="#fn:68">68</a>

<h2 id="comparison-between-the-different-techniques">Comparison between the different techniques</h2>
Several metrics have been used to assess the performance of one register allocation technique against the other. Register allocation has typically to deal with a trade-off between code quality, i.e. code that executes quickly, and analysis overhead, i.e. the time spent determining analyzing the source code to generate code with optimized register allocation. From this perspective, execution time of the generated code and time spent in liveness analysis are relevant metrics to compare the different techniques.<a class="footnote-ref" id="fnref:69" href="#fn:69">69</a>
Once relevant metrics have been chosen, the code on which the metrics will be applied should be available and relevant to the problem, either by reflecting the behavior of real-world application, or by being relevant to the particular problem the algorithm wants to address. The more recent articles about register allocation uses especially the Dacapo benchmark suite.<a class="footnote-ref" id="fnref:70" href="#fn:70">70</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Strahler_number/NvIPLc2u">Strahler number</a>, the minimum number of registers needed to evaluate an expression tree.<a class="footnote-ref" id="fnref:71" href="#fn:71">71</a></li>
<li><a href="/facts/Register_(keyword)/6XRABXvq">Register (keyword)</a>, the hint in C and C++ for a variable to be placed in a register.</li>
<li><a href="/facts/Sethi%E2%80%93Ullman_algorithm/L56k6Mh4">Sethi–Ullman algorithm</a>, an algorithm to produce the most efficient register allocation for evaluating a single expression when the number of registers required to evaluate the expression exceeds the number of available registers.</li></ul>

<h2 id="sources">Sources</h2>

<ul><li>Ahn, Minwook; Paek, Yunheung (2009). "Register coalescing techniques for heterogeneous register architecture with copy sifting". ACM Transactions on Embedded Computing Systems. 8 (2): 1–37. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.615.5767">10.1.1.615.5767</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1457255.1457263">10.1145/1457255.1457263</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/1539-9087">1539-9087</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:14143277">14143277</a>.</li>
<li>Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. (2006). <a href="https://archive.org/details/compilers00alfr_0">Compilers: Principles, Techniques, and Tools</a> (second ed.). Addison-Wesley Longman Publishing Co., Inc. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0321486813.</li>
<li>Appel, Andrew W.; George, Lal (2001). "Optimal spilling for CISC machines with few registers". Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation - PLDI '01. pp. 243–253. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.8978">10.1.1.37.8978</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F378795.378854">10.1145/378795.378854</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1581134148. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:1380545">1380545</a>.</li>
<li>Barik, Rajkishore; Grothoff, Christian; Gupta, Rahul; Pandit, Vinayaka; Udupa, Raghavendra (2007). "Optimal Bitwise Register Allocation Using Integer Linear Programming". Languages and Compilers for Parallel Computing. Lecture Notes in Computer Science. Vol. 4382. pp. 267–282. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.75.6911">10.1.1.75.6911</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-72521-3_20">10.1007/978-3-540-72521-3_20</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-72520-6.</li>
<li>Bergner, Peter; Dahl, Peter; Engebretsen, David; O'Keefe, Matthew (1997). "Spill code minimization via interference region spilling". Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation - PLDI '97. pp. 287–295. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F258915.258941">10.1145/258915.258941</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0897919074. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:16952747">16952747</a>.</li>
<li>Blackburn, Stephen M.; Guyer, Samuel Z.; Hirzel, Martin; Hosking, Antony; Jump, Maria; Lee, Han; Eliot, J.; Moss, B.; Phansalkar, Aashish; Stefanović, Darko; VanDrunen, Thomas; Garner, Robin; von Dincklage, Daniel; Wiedermann, Ben; Hoffmann, Chris; Khang, Asjad M.; McKinley, Kathryn S.; Bentzur, Rotem; Diwan, Amer; Feinberg, Daniel; Frampton, Daniel (2006). "The DaCapo benchmarks". Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications - OOPSLA '06. p. 169. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1167473.1167488">10.1145/1167473.1167488</a>. <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/1885%2F33723">1885/33723</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1595933485. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:9255051">9255051</a>.</li>
<li>Book, Ronald V. (December 1975). "Karp Richard M.. Reducibility among combinatorial problems. Complexity of computer computations, Proceedings of a Symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Center, Yorktown Heights, New York, edited by Miller Raymond E. and Thatcher James W., Plenum Press, New York and London 1972, pp. 85–103". The Journal of Symbolic Logic. 40 (4): 618–619. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2271828">10.2307/2271828</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0022-4812">0022-4812</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2271828">2271828</a>.</li>
<li>Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2006). "Register Allocation: What Does the NP-Completeness Proof of Chaitin et al. Really Prove? Or Revisiting Register Allocation: Why and How". Register allocation: what does the NP-Completeness proof of Chaitin et al. really prove?. Lecture Notes in Computer Science. Vol. 4382. pp. 2–14. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-72521-3_21">10.1007/978-3-540-72521-3_21</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-72520-6.</li>
<li>Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2007a). "On the Complexity of Register Coalescing". International Symposium on Code Generation and Optimization (CGO'07). pp. 102–114. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.6801">10.1.1.101.6801</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FCGO.2007.26">10.1109/CGO.2007.26</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-7695-2764-2. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:7683867">7683867</a>.</li>
<li>Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2007b). "On the complexity of spill everywhere under SSA form". ACM SIGPLAN Notices. 42 (7): 103–114. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/0710.3642">0710.3642</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1273444.1254782">10.1145/1273444.1254782</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0362-1340">0362-1340</a>.</li>
<li>Braun, Matthias; Hack, Sebastian (2009). "Register Spilling and Live-Range Splitting for SSA-Form Programs". Compiler Construction. Lecture Notes in Computer Science. Vol. 5501. pp. 174–189. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.219.5318">10.1.1.219.5318</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-642-00722-4_13">10.1007/978-3-642-00722-4_13</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-642-00721-7. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>.</li>
<li>Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1992). "Rematerialization". ACM SIGPLAN Notices. 27 (7): 311–321. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F143103.143143">10.1145/143103.143143</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0362-1340">0362-1340</a>.</li>
<li>Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1994). "Improvements to graph coloring register allocation". ACM Transactions on Programming Languages and Systems. 16 (3): 428–455. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.253">10.1.1.23.253</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F177492.177575">10.1145/177492.177575</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0164-0925">0164-0925</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6571479">6571479</a>.</li>
<li>Cavazos, John; Moss, J. Eliot B.; O’Boyle, Michael F. P. (2006). "Hybrid Optimizations: Which Optimization Algorithm to Use?". Compiler Construction. Lecture Notes in Computer Science. Vol. 3923. pp. 124–138. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F11688839_12">10.1007/11688839_12</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-33050-9. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>.</li>
<li>Chaitin, Gregory J.; Auslander, Marc A.; Chandra, Ashok K.; Cocke, John; Hopkins, Martin E.; Markstein, Peter W. (1981). "Register allocation via coloring". Computer Languages. 6 (1): 47–57. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0096-0551%2881%2990048-5">10.1016/0096-0551(81)90048-5</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0096-0551">0096-0551</a>.</li>
<li>Chaitin, G. J. (1982). "Register allocation & spilling via graph coloring". Proceedings of the 1982 SIGPLAN symposium on Compiler construction - SIGPLAN '82. pp. 98–101. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F800230.806984">10.1145/800230.806984</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0897910743. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:16872867">16872867</a>.</li>
<li>Chen, Wei-Yu; Lueh, Guei-Yuan; Ashar, Pratik; Chen, Kaiyu; Cheng, Buqi (2018). "Register allocation for Intel processor graphics". Proceedings of the 2018 International Symposium on Code Generation and Optimization - CGO 2018. pp. 352–364. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F3168806">10.1145/3168806</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781450356176. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:3367270">3367270</a>.</li>
<li>Cohen, Albert; Rohou, Erven (2010). "Processor virtualization and split compilation for heterogeneous multicore embedded systems". Proceedings of the 47th Design Automation Conference on - DAC '10. p. 102. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.470.9701">10.1.1.470.9701</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1837274.1837303">10.1145/1837274.1837303</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781450300025. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:14314078">14314078</a>.</li>
<li>Colombet, Quentin; Brandner, Florian; Darte, Alain (2011). "Studying optimal spilling in the light of SSA". Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems - CASES '11. p. 25. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F2038698.2038706">10.1145/2038698.2038706</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781450307130. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:8296742">8296742</a>.</li>
<li>Diouf, Boubacar; Cohen, Albert; Rastello, Fabrice; Cavazos, John (2010). "Split Register Allocation: Linear Complexity Without the Performance Penalty". High Performance Embedded Architectures and Compilers. Lecture Notes in Computer Science. Vol. 5952. pp. 66–80. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.229.3988">10.1.1.229.3988</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-642-11515-8_7">10.1007/978-3-642-11515-8_7</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-642-11514-1. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>.</li>
<li>Ditzel, David R.; McLellan, H. R. (1982). "Register allocation for free". Proceedings of the first international symposium on Architectural support for programming languages and operating systems - ASPLOS-I. pp. 48–56. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F800050.801825">10.1145/800050.801825</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0897910668. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:2812379">2812379</a>.</li>
<li>Eisl, Josef; Grimmer, Matthias; Simon, Doug; Würthinger, Thomas; Mössenböck, Hanspeter (2016). "Trace-based Register Allocation in a JIT Compiler". <a href="http://epub.jku.at/doi/10.1145/2972206.2972211">Proceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools - PPPJ '16</a>. pp. 1–11. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F2972206.2972211">10.1145/2972206.2972211</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781450341356. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:31845919">31845919</a>.</li>
<li>Eisl, Josef; Marr, Stefan; Würthinger, Thomas; Mössenböck, Hanspeter (2017). <a href="http://kar.kent.ac.uk/63807/1/manlang17-eisl-et-al-trace-register-allocation-policies.pdf">"Trace Register Allocation Policies"</a> (PDF). <a href="http://epub.jku.at/doi/10.1145/3132190.3132209">Proceedings of the 14th International Conference on Managed Languages and Runtimes - Man Lang 2017</a>. pp. 92–104. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F3132190.3132209">10.1145/3132190.3132209</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781450353403. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:1195601">1195601</a>.</li>
<li>Eisl, Josef; Leopoldseder, David; Mössenböck, Hanspeter (2018). "Parallel trace register allocation". <a href="https://resolver.obvsg.at/urn:nbn:at:at-ubl:3-271">Proceedings of the 15th International Conference on Managed Languages & Runtimes - Man Lang '18</a>. pp. 1–7. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F3237009.3237010">10.1145/3237009.3237010</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781450364249. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:52137887">52137887</a>.</li>
<li>Koes, David Ryan; Goldstein, Seth Copen (2009). <a href="http://dl.acm.org/citation.cfm?id=1543820.1543824">"Register Allocation Deconstructed"</a>. Written at Nice, France. Proceedings of the 12th International Workshop on Software and Compilers for Embedded Systems. SCOPES '09. New York, NY, USA: ACM. pp. 21–30. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-60558-696-0.</li>
<li>Farach, Martin; Liberatore, Vincenzo (1998). <a href="https://archive.org/details/proceedingsofnin0000acms/page/564">"On Local Register Allocation"</a>. Written at San Francisco, California, USA. Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '98. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics. pp. <a href="https://archive.org/details/proceedingsofnin0000acms/page/564">564–573</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-89871-410-9.</li>
<li><a href="/facts/Philippe_Flajolet/8C9NqUlD">Flajolet, P.</a>; Raoult, J. C.; <a href="/facts/Jean_Vuillemin/jUWCvsEA">Vuillemin, J.</a> (1979), "The number of registers required for evaluating arithmetic expressions", Theoretical Computer Science, 9 (1): 99–125, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0304-3975%2879%2990009-4">10.1016/0304-3975(79)90009-4</a></li>
<li>George, Lal; Appel, Andrew W. (1996). <a href="https://doi.org/10.1145%2F229542.229546">"Iterated register coalescing"</a>. ACM Transactions on Programming Languages and Systems. 18 (3): 300–324. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F229542.229546">10.1145/229542.229546</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0164-0925">0164-0925</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:12281734">12281734</a>.</li>
<li>Horwitz, L. P.; Karp, R. M.; Miller, R. E.; Winograd, S. (1966). <a href="https://doi.org/10.1145%2F321312.321317">"Index Register Allocation"</a>. Journal of the ACM. 13 (1): 43–61. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F321312.321317">10.1145/321312.321317</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:14560597">14560597</a>.</li>
<li>Johansson, Erik; Sagonas, Konstantinos (2002). "Linear Scan Register Allocation in a High-Performance Erlang Compiler". Practical Aspects of Declarative Languages. Lecture Notes in Computer Science. Vol. 2257. pp. 101–119. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-45587-6_8">10.1007/3-540-45587-6_8</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-43092-6. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>.</li>
<li>Kurdahi, F. J.; <a href="/facts/Alice_C._Parker/BrjIAeoW">Parker, A. C.</a> (1987). "REAL: a program for REgister ALlocation". 24th ACM/IEEE conference proceedings on Design automation conference - DAC '87. pp. 210–215. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F37888.37920">10.1145/37888.37920</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0818607813. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:17598675">17598675</a>.</li>
<li>Mössenböck, Hanspeter; Pfeiffer, Michael (2002). "Linear Scan Register Allocation in the Context of SSA Form and Register Constraints". Compiler Construction. Lecture Notes in Computer Science. Vol. 2304. pp. 229–246. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-45937-5_17">10.1007/3-540-45937-5_17</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-43369-9. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>.</li>
<li>Nickerson, Brian R. (1990). "Graph coloring register allocation for processors with multi-register operands". ACM SIGPLAN Notices. 25 (6): 40–52. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F93548.93552">10.1145/93548.93552</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0362-1340">0362-1340</a>.</li>
<li>Paleczny, Michael; Vick, Christopher; Click, Cliff (2001). "The Java HotSpot Server Compiler". Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM01). Monterey, California, USA. pp. 1–12. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.1919">10.1.1.106.1919</a>.</li>
<li>Park, Jinpyo; Moon, Soo-Mook (2004). "Optimistic register coalescing". ACM Transactions on Programming Languages and Systems. 26 (4): 735–765. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.9438">10.1.1.33.9438</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1011508.1011512">10.1145/1011508.1011512</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0164-0925">0164-0925</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:15969885">15969885</a>.</li>
<li>Poletto, Massimiliano; Sarkar, Vivek (1999). "Linear scan register allocation". ACM Transactions on Programming Languages and Systems. 21 (5): 895–913. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462">10.1.1.27.2462</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F330249.330250">10.1145/330249.330250</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0164-0925">0164-0925</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:18180752">18180752</a>.</li>
<li>Rogers, Ian (2020). "Efficient global register allocation". <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/2011.05608">2011.05608</a> [<a href="https://arxiv.org/archive/cs.PL">cs.PL</a>].</li>
<li>Runeson, Johan; Nyström, Sven-Olof (2003). "Retargetable Graph-Coloring Register Allocation for Irregular Architectures". Software and Compilers for Embedded Systems. Lecture Notes in Computer Science. Vol. 2826. pp. 240–254. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.6186">10.1.1.6.6186</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-39920-9_17">10.1007/978-3-540-39920-9_17</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-20145-8. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>.</li>
<li>Smith, Michael D.; Ramsey, Norman; Holloway, Glenn (2004). "A generalized algorithm for graph-coloring register allocation". ACM SIGPLAN Notices. 39 (6): 277. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.9532">10.1.1.71.9532</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F996893.996875">10.1145/996893.996875</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0362-1340">0362-1340</a>.</li>
<li>Traub, Omri; Holloway, Glenn; Smith, Michael D. (1998). "Quality and speed in linear-scan register allocation". ACM SIGPLAN Notices. 33 (5): 142–151. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.8730">10.1.1.52.8730</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F277652.277714">10.1145/277652.277714</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0362-1340">0362-1340</a>.</li>
<li>Wimmer, Christian; Mössenböck, Hanspeter (2005). "Optimized interval splitting in a linear scan register allocator". Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments - VEE '05. p. 132. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.394.4054">10.1.1.394.4054</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1064979.1064998">10.1145/1064979.1064998</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1595930477. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:494490">494490</a>.</li>
<li>Wimmer, Christian; Franz, Michael (2010). "Linear scan register allocation on SSA form". Proceedings of the 8th annual IEEE/ ACM international symposium on Code generation and optimization - CGO '10. p. 170. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.162.2590">10.1.1.162.2590</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1772954.1772979">10.1145/1772954.1772979</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781605586359. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:1820765">1820765</a>.</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://mat.gsia.cmu.edu/orclass/integer/integer.html">A Tutorial on Integer Programming</a></li>
<li>Conference <a href="http://www.mathopt.org/?nav=ipco">Integer Programming and Combinatorial Optimization, IPCO</a></li>
<li><a href="http://www.iasi.cnr.it/aussois">The Aussois Combinatorial Optimization Workshop</a></li>
<li>Bosscher, Steven; and Novillo, Diego. <a href="https://lwn.net/Articles/84888/">GCC gets a new Optimizer Framework</a>. An article about GCC's use of SSA and how it improves over older IRs.</li>
<li><a href="http://www.dcs.gla.ac.uk/~jsinger/ssa.html">The SSA Bibliography</a>. Extensive catalogue of SSA research papers.</li>
<li>Zadeck, F. Kenneth. <a href="http://webcast.rice.edu/webcast.php?action=details&event=1346">"The Development of Static Single Assignment Form"</a>, December 2007 talk on the origins of SSA.</li>
<li>VV.AA. <a href="http://ssabook.gforge.inria.fr/latest/book.pdf">"SSA-based Compiler Design"</a> (2014)</li>
<li><a href="http://citeseer.ist.psu.edu/Programming/CompilerOptimization/">Citations from CiteSeer</a></li>
<li><a href="http://www.agner.org/optimize/#manuals">Optimization manuals</a> by <a href="/facts/Agner_Fog/ya0BwejU">Agner Fog</a> - documentation about x86 processor architecture and low-level code optimization</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Ditzel & McLellan 1982, p. 48. - Ditzel, David R.; McLellan, H. R. (1982). "Register allocation for free". Proceedings of the first international symposium on Architectural support for programming languages and operating systems - ASPLOS-I. pp. 48–56. doi:10.1145/800050.801825. ISBN 978-0897910668. S2CID 2812379. <a href="https://doi.org/10.1145%2F800050.801825" target="_blank">https://doi.org/10.1145%2F800050.801825</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Runeson & Nyström 2003, p. 242. - Runeson, Johan; Nyström, Sven-Olof (2003). "Retargetable Graph-Coloring Register Allocation for Irregular Architectures". Software and Compilers for Embedded Systems. Lecture Notes in Computer Science. Vol. 2826. pp. 240–254. CiteSeerX 10.1.1.6.6186. doi:10.1007/978-3-540-39920-9_17. ISBN 978-3-540-20145-8. ISSN 0302-9743. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.6186" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.6186</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Eisl et al. 2016, p. 14:1. - Eisl, Josef; Grimmer, Matthias; Simon, Doug; Würthinger, Thomas; Mössenböck, Hanspeter (2016). "Trace-based Register Allocation in a JIT Compiler". Proceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools - PPPJ '16. pp. 1–11. doi:10.1145/2972206.2972211. ISBN 9781450341356. S2CID 31845919. <a href="http://epub.jku.at/doi/10.1145/2972206.2972211" target="_blank">http://epub.jku.at/doi/10.1145/2972206.2972211</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Chaitin et al. 1981, p. 47. - Chaitin, Gregory J.; Auslander, Marc A.; Chandra, Ashok K.; Cocke, John; Hopkins, Martin E.; Markstein, Peter W. (1981). "Register allocation via coloring". Computer Languages. 6 (1): 47–57. doi:10.1016/0096-0551(81)90048-5. ISSN 0096-0551. <a href="https://doi.org/10.1016%2F0096-0551%2881%2990048-5" target="_blank">https://doi.org/10.1016%2F0096-0551%2881%2990048-5</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Eisl et al. 2016, p. 1. - Eisl, Josef; Grimmer, Matthias; Simon, Doug; Würthinger, Thomas; Mössenböck, Hanspeter (2016). "Trace-based Register Allocation in a JIT Compiler". Proceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools - PPPJ '16. pp. 1–11. doi:10.1145/2972206.2972211. ISBN 9781450341356. S2CID 31845919. <a href="http://epub.jku.at/doi/10.1145/2972206.2972211" target="_blank">http://epub.jku.at/doi/10.1145/2972206.2972211</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">"Latency Comparison Numbers in computer/network". blog.morizyun.com. 6 January 2018. Retrieved 2019-01-08. <a href="https://blog.morizyun.com/computer-science/basic-latency-comparison-numbers.html" target="_blank">https://blog.morizyun.com/computer-science/basic-latency-comparison-numbers.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Braun & Hack 2009, p. 174. - Braun, Matthias; Hack, Sebastian (2009). "Register Spilling and Live-Range Splitting for SSA-Form Programs". Compiler Construction. Lecture Notes in Computer Science. Vol. 5501. pp. 174–189. CiteSeerX 10.1.1.219.5318. doi:10.1007/978-3-642-00722-4_13. ISBN 978-3-642-00721-7. ISSN 0302-9743. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.219.5318" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.219.5318</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Koes & Goldstein 2009, p. 21. - Koes, David Ryan; Goldstein, Seth Copen (2009). "Register Allocation Deconstructed". Written at Nice, France. Proceedings of the 12th International Workshop on Software and Compilers for Embedded Systems. SCOPES '09. New York, NY, USA: ACM. pp. 21–30. ISBN 978-1-60558-696-0. <a href="http://dl.acm.org/citation.cfm?id=1543820.1543824" target="_blank">http://dl.acm.org/citation.cfm?id=1543820.1543824</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Bouchez, Darte & Rastello 2007b, p. 103. - Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2007b). "On the complexity of spill everywhere under SSA form". ACM SIGPLAN Notices. 42 (7): 103–114. arXiv:0710.3642. doi:10.1145/1273444.1254782. ISSN 0362-1340. <a href="https://arxiv.org/abs/0710.3642" target="_blank">https://arxiv.org/abs/0710.3642</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Colombet, Brandner & Darte 2011, p. 26. - Colombet, Quentin; Brandner, Florian; Darte, Alain (2011). "Studying optimal spilling in the light of SSA". Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems - CASES '11. p. 25. doi:10.1145/2038698.2038706. ISBN 9781450307130. S2CID 8296742. <a href="https://doi.org/10.1145%2F2038698.2038706" target="_blank">https://doi.org/10.1145%2F2038698.2038706</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Bouchez, Darte & Rastello 2007b, p. 103. - Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2007b). "On the complexity of spill everywhere under SSA form". ACM SIGPLAN Notices. 42 (7): 103–114. arXiv:0710.3642. doi:10.1145/1273444.1254782. ISSN 0362-1340. <a href="https://arxiv.org/abs/0710.3642" target="_blank">https://arxiv.org/abs/0710.3642</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">"Intel® 64 and IA-32 Architectures Software Developer's Manual, Section 3.4.1" (PDF). Intel. May 2019. Archived from the original (PDF) on 2019-05-25. <a href="https://web.archive.org/web/20190525125151/https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf" target="_blank">https://web.archive.org/web/20190525125151/https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">"32-bit PowerPC function calling conventions". <a href="https://developer.apple.com/library/archive/documentation/DeveloperTools/Conceptual/LowLevelABI/100-32-bit_PowerPC_Function_Calling_Conventions/32bitPowerPC.html" target="_blank">https://developer.apple.com/library/archive/documentation/DeveloperTools/Conceptual/LowLevelABI/100-32-bit_PowerPC_Function_Calling_Conventions/32bitPowerPC.html</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Bouchez, Darte & Rastello 2006, p. 4. - Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2006). "Register Allocation: What Does the NP-Completeness Proof of Chaitin et al. Really Prove? Or Revisiting Register Allocation: Why and How". Register allocation: what does the NP-Completeness proof of Chaitin et al. really prove?. Lecture Notes in Computer Science. Vol. 4382. pp. 2–14. doi:10.1007/978-3-540-72521-3_21. ISBN 978-3-540-72520-6. <a href="https://doi.org/10.1007%2F978-3-540-72521-3_21" target="_blank">https://doi.org/10.1007%2F978-3-540-72521-3_21</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Horwitz et al. 1966, p. 43. - Horwitz, L. P.; Karp, R. M.; Miller, R. E.; Winograd, S. (1966). "Index Register Allocation". Journal of the ACM. 13 (1): 43–61. doi:10.1145/321312.321317. ISSN 0004-5411. S2CID 14560597. <a href="https://doi.org/10.1145%2F321312.321317" target="_blank">https://doi.org/10.1145%2F321312.321317</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Farach & Liberatore 1998, p. 566. - Farach, Martin; Liberatore, Vincenzo (1998). "On Local Register Allocation". Written at San Francisco, California, USA. Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '98. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics. pp. 564–573. ISBN 0-89871-410-9. <a href="https://archive.org/details/proceedingsofnin0000acms/page/564" target="_blank">https://archive.org/details/proceedingsofnin0000acms/page/564</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Eisl et al. 2017, p. 92. - Eisl, Josef; Marr, Stefan; Würthinger, Thomas; Mössenböck, Hanspeter (2017). "Trace Register Allocation Policies" (PDF). Proceedings of the 14th International Conference on Managed Languages and Runtimes - Man Lang 2017. pp. 92–104. doi:10.1145/3132190.3132209. ISBN 9781450353403. S2CID 1195601. <a href="http://kar.kent.ac.uk/63807/1/manlang17-eisl-et-al-trace-register-allocation-policies.pdf" target="_blank">http://kar.kent.ac.uk/63807/1/manlang17-eisl-et-al-trace-register-allocation-policies.pdf</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Eisl, Leopoldseder & Mössenböck 2018, p. 1. - Eisl, Josef; Leopoldseder, David; Mössenböck, Hanspeter (2018). "Parallel trace register allocation". Proceedings of the 15th International Conference on Managed Languages & Runtimes - Man Lang '18. pp. 1–7. doi:10.1145/3237009.3237010. ISBN 9781450364249. S2CID 52137887. <a href="https://resolver.obvsg.at/urn:nbn:at:at-ubl:3-271" target="_blank">https://resolver.obvsg.at/urn:nbn:at:at-ubl:3-271</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Briggs, Cooper & Torczon 1992, p. 316. - Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1992). "Rematerialization". ACM SIGPLAN Notices. 27 (7): 311–321. doi:10.1145/143103.143143. ISSN 0362-1340. <a href="https://doi.org/10.1145%2F143103.143143" target="_blank">https://doi.org/10.1145%2F143103.143143</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Chaitin et al. 1981, p. 47. - Chaitin, Gregory J.; Auslander, Marc A.; Chandra, Ashok K.; Cocke, John; Hopkins, Martin E.; Markstein, Peter W. (1981). "Register allocation via coloring". Computer Languages. 6 (1): 47–57. doi:10.1016/0096-0551(81)90048-5. ISSN 0096-0551. <a href="https://doi.org/10.1016%2F0096-0551%2881%2990048-5" target="_blank">https://doi.org/10.1016%2F0096-0551%2881%2990048-5</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Poletto & Sarkar 1999, p. 896. - Poletto, Massimiliano; Sarkar, Vivek (1999). "Linear scan register allocation". ACM Transactions on Programming Languages and Systems. 21 (5): 895–913. CiteSeerX 10.1.1.27.2462. doi:10.1145/330249.330250. ISSN 0164-0925. S2CID 18180752. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Runeson & Nyström 2003, p. 241. - Runeson, Johan; Nyström, Sven-Olof (2003). "Retargetable Graph-Coloring Register Allocation for Irregular Architectures". Software and Compilers for Embedded Systems. Lecture Notes in Computer Science. Vol. 2826. pp. 240–254. CiteSeerX 10.1.1.6.6186. doi:10.1007/978-3-540-39920-9_17. ISBN 978-3-540-20145-8. ISSN 0302-9743. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.6186" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.6186</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Briggs, Cooper & Torczon 1992, p. 316. - Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1992). "Rematerialization". ACM SIGPLAN Notices. 27 (7): 311–321. doi:10.1145/143103.143143. ISSN 0362-1340. <a href="https://doi.org/10.1145%2F143103.143143" target="_blank">https://doi.org/10.1145%2F143103.143143</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Book 1975, p. 618–619. - Book, Ronald V. (December 1975). "Karp Richard M.. Reducibility among combinatorial problems. Complexity of computer computations, Proceedings of a Symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Center, Yorktown Heights, New York, edited by Miller Raymond E. and Thatcher James W., Plenum Press, New York and London 1972, pp. 85–103". The Journal of Symbolic Logic. 40 (4): 618–619. doi:10.2307/2271828. ISSN 0022-4812. JSTOR 2271828. <a href="https://doi.org/10.2307%2F2271828" target="_blank">https://doi.org/10.2307%2F2271828</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Colombet, Brandner & Darte 2011, p. 1. - Colombet, Quentin; Brandner, Florian; Darte, Alain (2011). "Studying optimal spilling in the light of SSA". Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems - CASES '11. p. 25. doi:10.1145/2038698.2038706. ISBN 9781450307130. S2CID 8296742. <a href="https://doi.org/10.1145%2F2038698.2038706" target="_blank">https://doi.org/10.1145%2F2038698.2038706</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Smith, Ramsey & Holloway 2004, p. 277. - Smith, Michael D.; Ramsey, Norman; Holloway, Glenn (2004). "A generalized algorithm for graph-coloring register allocation". ACM SIGPLAN Notices. 39 (6): 277. CiteSeerX 10.1.1.71.9532. doi:10.1145/996893.996875. ISSN 0362-1340. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.9532" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.9532</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Cavazos, Moss & O’Boyle 2006, p. 124. - Cavazos, John; Moss, J. Eliot B.; O’Boyle, Michael F. P. (2006). "Hybrid Optimizations: Which Optimization Algorithm to Use?". Compiler Construction. Lecture Notes in Computer Science. Vol. 3923. pp. 124–138. doi:10.1007/11688839_12. ISBN 978-3-540-33050-9. ISSN 0302-9743. <a href="https://doi.org/10.1007%2F11688839_12" target="_blank">https://doi.org/10.1007%2F11688839_12</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Runeson & Nyström 2003, p. 240. - Runeson, Johan; Nyström, Sven-Olof (2003). "Retargetable Graph-Coloring Register Allocation for Irregular Architectures". Software and Compilers for Embedded Systems. Lecture Notes in Computer Science. Vol. 2826. pp. 240–254. CiteSeerX 10.1.1.6.6186. doi:10.1007/978-3-540-39920-9_17. ISBN 978-3-540-20145-8. ISSN 0302-9743. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.6186" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.6186</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Briggs, Cooper & Torczon 1992, p. 316. - Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1992). "Rematerialization". ACM SIGPLAN Notices. 27 (7): 311–321. doi:10.1145/143103.143143. ISSN 0362-1340. <a href="https://doi.org/10.1145%2F143103.143143" target="_blank">https://doi.org/10.1145%2F143103.143143</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Poletto & Sarkar 1999, p. 895. - Poletto, Massimiliano; Sarkar, Vivek (1999). "Linear scan register allocation". ACM Transactions on Programming Languages and Systems. 21 (5): 895–913. CiteSeerX 10.1.1.27.2462. doi:10.1145/330249.330250. ISSN 0164-0925. S2CID 18180752. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">Cavazos, Moss & O’Boyle 2006, p. 124. - Cavazos, John; Moss, J. Eliot B.; O’Boyle, Michael F. P. (2006). "Hybrid Optimizations: Which Optimization Algorithm to Use?". Compiler Construction. Lecture Notes in Computer Science. Vol. 3923. pp. 124–138. doi:10.1007/11688839_12. ISBN 978-3-540-33050-9. ISSN 0302-9743. <a href="https://doi.org/10.1007%2F11688839_12" target="_blank">https://doi.org/10.1007%2F11688839_12</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Poletto & Sarkar 1999, p. 902. - Poletto, Massimiliano; Sarkar, Vivek (1999). "Linear scan register allocation". ACM Transactions on Programming Languages and Systems. 21 (5): 895–913. CiteSeerX 10.1.1.27.2462. doi:10.1145/330249.330250. ISSN 0164-0925. S2CID 18180752. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Wimmer & Mössenböck 2005, p. 132. - Wimmer, Christian; Mössenböck, Hanspeter (2005). "Optimized interval splitting in a linear scan register allocator". Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments - VEE '05. p. 132. CiteSeerX 10.1.1.394.4054. doi:10.1145/1064979.1064998. ISBN 978-1595930477. S2CID 494490. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.394.4054" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.394.4054</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Johansson & Sagonas 2002, p. 102. - Johansson, Erik; Sagonas, Konstantinos (2002). "Linear Scan Register Allocation in a High-Performance Erlang Compiler". Practical Aspects of Declarative Languages. Lecture Notes in Computer Science. Vol. 2257. pp. 101–119. doi:10.1007/3-540-45587-6_8. ISBN 978-3-540-43092-6. ISSN 0302-9743. <a href="https://doi.org/10.1007%2F3-540-45587-6_8" target="_blank">https://doi.org/10.1007%2F3-540-45587-6_8</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">Eisl et al. 2016, p. 1. - Eisl, Josef; Grimmer, Matthias; Simon, Doug; Würthinger, Thomas; Mössenböck, Hanspeter (2016). "Trace-based Register Allocation in a JIT Compiler". Proceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools - PPPJ '16. pp. 1–11. doi:10.1145/2972206.2972211. ISBN 9781450341356. S2CID 31845919. <a href="http://epub.jku.at/doi/10.1145/2972206.2972211" target="_blank">http://epub.jku.at/doi/10.1145/2972206.2972211</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">The Evolution of ART - Google I/O 2016. Google. 25 May 2016. Event occurs at 3m47s. <a href="https://www.youtube.com/watch?v=fwMM6g7wpQ8" target="_blank">https://www.youtube.com/watch?v=fwMM6g7wpQ8</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Paleczny, Vick & Click 2001, p. 1. - Paleczny, Michael; Vick, Christopher; Click, Cliff (2001). "The Java HotSpot Server Compiler". Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM01). Monterey, California, USA. pp. 1–12. CiteSeerX 10.1.1.106.1919. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.1919" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.1919</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Poletto & Sarkar 1999, p. 899. - Poletto, Massimiliano; Sarkar, Vivek (1999). "Linear scan register allocation". ACM Transactions on Programming Languages and Systems. 21 (5): 895–913. CiteSeerX 10.1.1.27.2462. doi:10.1145/330249.330250. ISSN 0164-0925. S2CID 18180752. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
<li id="fn:39">Eisl et al. 2016, p. 2. - Eisl, Josef; Grimmer, Matthias; Simon, Doug; Würthinger, Thomas; Mössenböck, Hanspeter (2016). "Trace-based Register Allocation in a JIT Compiler". Proceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools - PPPJ '16. pp. 1–11. doi:10.1145/2972206.2972211. ISBN 9781450341356. S2CID 31845919. <a href="http://epub.jku.at/doi/10.1145/2972206.2972211" target="_blank">http://epub.jku.at/doi/10.1145/2972206.2972211</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></li>
<li id="fn:40">Traub, Holloway & Smith 1998, p. 143. - Traub, Omri; Holloway, Glenn; Smith, Michael D. (1998). "Quality and speed in linear-scan register allocation". ACM SIGPLAN Notices. 33 (5): 142–151. CiteSeerX 10.1.1.52.8730. doi:10.1145/277652.277714. ISSN 0362-1340. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.8730" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.8730</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></li>
<li id="fn:41">Traub, Holloway & Smith 1998, p. 141. - Traub, Omri; Holloway, Glenn; Smith, Michael D. (1998). "Quality and speed in linear-scan register allocation". ACM SIGPLAN Notices. 33 (5): 142–151. CiteSeerX 10.1.1.52.8730. doi:10.1145/277652.277714. ISSN 0362-1340. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.8730" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.8730</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></li>
<li id="fn:42">Poletto & Sarkar 1999, p. 897. - Poletto, Massimiliano; Sarkar, Vivek (1999). "Linear scan register allocation". ACM Transactions on Programming Languages and Systems. 21 (5): 895–913. CiteSeerX 10.1.1.27.2462. doi:10.1145/330249.330250. ISSN 0164-0925. S2CID 18180752. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></li>
<li id="fn:43">Wimmer & Franz 2010, p. 170. - Wimmer, Christian; Franz, Michael (2010). "Linear scan register allocation on SSA form". Proceedings of the 8th annual IEEE/ ACM international symposium on Code generation and optimization - CGO '10. p. 170. CiteSeerX 10.1.1.162.2590. doi:10.1145/1772954.1772979. ISBN 9781605586359. S2CID 1820765. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.162.2590" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.162.2590</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></li>
<li id="fn:44">Mössenböck & Pfeiffer 2002, p. 234. - Mössenböck, Hanspeter; Pfeiffer, Michael (2002). "Linear Scan Register Allocation in the Context of SSA Form and Register Constraints". Compiler Construction. Lecture Notes in Computer Science. Vol. 2304. pp. 229–246. doi:10.1007/3-540-45937-5_17. ISBN 978-3-540-43369-9. ISSN 0302-9743. <a href="https://doi.org/10.1007%2F3-540-45937-5_17" target="_blank">https://doi.org/10.1007%2F3-540-45937-5_17</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></li>
<li id="fn:45">Mössenböck & Pfeiffer 2002, p. 233. - Mössenböck, Hanspeter; Pfeiffer, Michael (2002). "Linear Scan Register Allocation in the Context of SSA Form and Register Constraints". Compiler Construction. Lecture Notes in Computer Science. Vol. 2304. pp. 229–246. doi:10.1007/3-540-45937-5_17. ISBN 978-3-540-43369-9. ISSN 0302-9743. <a href="https://doi.org/10.1007%2F3-540-45937-5_17" target="_blank">https://doi.org/10.1007%2F3-540-45937-5_17</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></li>
<li id="fn:46">Mössenböck & Pfeiffer 2002, p. 229. - Mössenböck, Hanspeter; Pfeiffer, Michael (2002). "Linear Scan Register Allocation in the Context of SSA Form and Register Constraints". Compiler Construction. Lecture Notes in Computer Science. Vol. 2304. pp. 229–246. doi:10.1007/3-540-45937-5_17. ISBN 978-3-540-43369-9. ISSN 0302-9743. <a href="https://doi.org/10.1007%2F3-540-45937-5_17" target="_blank">https://doi.org/10.1007%2F3-540-45937-5_17</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></li>
<li id="fn:47">Rogers 2020. - Rogers, Ian (2020). "Efficient global register allocation". arXiv:2011.05608 [cs.PL]. <a href="https://arxiv.org/abs/2011.05608" target="_blank">https://arxiv.org/abs/2011.05608</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></li>
<li id="fn:48">Chaitin 1982, p. 90. - Chaitin, G. J. (1982). "Register allocation & spilling via graph coloring". Proceedings of the 1982 SIGPLAN symposium on Compiler construction - SIGPLAN '82. pp. 98–101. doi:10.1145/800230.806984. ISBN 978-0897910743. S2CID 16872867. <a href="https://doi.org/10.1145%2F800230.806984" target="_blank">https://doi.org/10.1145%2F800230.806984</a> <a href="#fnref:48" class="footnote-back-ref">↩</a></li>
<li id="fn:49">Bouchez, Darte & Rastello 2007b, p. 103. - Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2007b). "On the complexity of spill everywhere under SSA form". ACM SIGPLAN Notices. 42 (7): 103–114. arXiv:0710.3642. doi:10.1145/1273444.1254782. ISSN 0362-1340. <a href="https://arxiv.org/abs/0710.3642" target="_blank">https://arxiv.org/abs/0710.3642</a> <a href="#fnref:49" class="footnote-back-ref">↩</a></li>
<li id="fn:50">Bouchez, Darte & Rastello 2007b, p. 103. - Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2007b). "On the complexity of spill everywhere under SSA form". ACM SIGPLAN Notices. 42 (7): 103–114. arXiv:0710.3642. doi:10.1145/1273444.1254782. ISSN 0362-1340. <a href="https://arxiv.org/abs/0710.3642" target="_blank">https://arxiv.org/abs/0710.3642</a> <a href="#fnref:50" class="footnote-back-ref">↩</a></li>
<li id="fn:51">Ahn & Paek 2009, p. 7. - Ahn, Minwook; Paek, Yunheung (2009). "Register coalescing techniques for heterogeneous register architecture with copy sifting". ACM Transactions on Embedded Computing Systems. 8 (2): 1–37. CiteSeerX 10.1.1.615.5767. doi:10.1145/1457255.1457263. ISSN 1539-9087. S2CID 14143277. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.615.5767" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.615.5767</a> <a href="#fnref:51" class="footnote-back-ref">↩</a></li>
<li id="fn:52">Park & Moon 2004, p. 736. - Park, Jinpyo; Moon, Soo-Mook (2004). "Optimistic register coalescing". ACM Transactions on Programming Languages and Systems. 26 (4): 735–765. CiteSeerX 10.1.1.33.9438. doi:10.1145/1011508.1011512. ISSN 0164-0925. S2CID 15969885. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.9438" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.9438</a> <a href="#fnref:52" class="footnote-back-ref">↩</a></li>
<li id="fn:53">Chaitin 1982, p. 99. - Chaitin, G. J. (1982). "Register allocation & spilling via graph coloring". Proceedings of the 1982 SIGPLAN symposium on Compiler construction - SIGPLAN '82. pp. 98–101. doi:10.1145/800230.806984. ISBN 978-0897910743. S2CID 16872867. <a href="https://doi.org/10.1145%2F800230.806984" target="_blank">https://doi.org/10.1145%2F800230.806984</a> <a href="#fnref:53" class="footnote-back-ref">↩</a></li>
<li id="fn:54">Park & Moon 2004, p. 738. - Park, Jinpyo; Moon, Soo-Mook (2004). "Optimistic register coalescing". ACM Transactions on Programming Languages and Systems. 26 (4): 735–765. CiteSeerX 10.1.1.33.9438. doi:10.1145/1011508.1011512. ISSN 0164-0925. S2CID 15969885. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.9438" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.9438</a> <a href="#fnref:54" class="footnote-back-ref">↩</a></li>
<li id="fn:55">Ahn & Paek 2009, p. 7. - Ahn, Minwook; Paek, Yunheung (2009). "Register coalescing techniques for heterogeneous register architecture with copy sifting". ACM Transactions on Embedded Computing Systems. 8 (2): 1–37. CiteSeerX 10.1.1.615.5767. doi:10.1145/1457255.1457263. ISSN 1539-9087. S2CID 14143277. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.615.5767" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.615.5767</a> <a href="#fnref:55" class="footnote-back-ref">↩</a></li>
<li id="fn:56">Briggs, Cooper & Torczon 1994, p. 433. - Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1994). "Improvements to graph coloring register allocation". ACM Transactions on Programming Languages and Systems. 16 (3): 428–455. CiteSeerX 10.1.1.23.253. doi:10.1145/177492.177575. ISSN 0164-0925. S2CID 6571479. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.253" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.253</a> <a href="#fnref:56" class="footnote-back-ref">↩</a></li>
<li id="fn:57">George & Appel 1996, p. 212. - George, Lal; Appel, Andrew W. (1996). "Iterated register coalescing". ACM Transactions on Programming Languages and Systems. 18 (3): 300–324. doi:10.1145/229542.229546. ISSN 0164-0925. S2CID 12281734. <a href="https://doi.org/10.1145%2F229542.229546" target="_blank">https://doi.org/10.1145%2F229542.229546</a> <a href="#fnref:57" class="footnote-back-ref">↩</a></li>
<li id="fn:58">Park & Moon 2004, p. 741. - Park, Jinpyo; Moon, Soo-Mook (2004). "Optimistic register coalescing". ACM Transactions on Programming Languages and Systems. 26 (4): 735–765. CiteSeerX 10.1.1.33.9438. doi:10.1145/1011508.1011512. ISSN 0164-0925. S2CID 15969885. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.9438" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.9438</a> <a href="#fnref:58" class="footnote-back-ref">↩</a></li>
<li id="fn:59">Eisl et al. 2017, p. 11. - Eisl, Josef; Marr, Stefan; Würthinger, Thomas; Mössenböck, Hanspeter (2017). "Trace Register Allocation Policies" (PDF). Proceedings of the 14th International Conference on Managed Languages and Runtimes - Man Lang 2017. pp. 92–104. doi:10.1145/3132190.3132209. ISBN 9781450353403. S2CID 1195601. <a href="http://kar.kent.ac.uk/63807/1/manlang17-eisl-et-al-trace-register-allocation-policies.pdf" target="_blank">http://kar.kent.ac.uk/63807/1/manlang17-eisl-et-al-trace-register-allocation-policies.pdf</a> <a href="#fnref:59" class="footnote-back-ref">↩</a></li>
<li id="fn:60">Cavazos, Moss & O’Boyle 2006, p. 124-127. - Cavazos, John; Moss, J. Eliot B.; O’Boyle, Michael F. P. (2006). "Hybrid Optimizations: Which Optimization Algorithm to Use?". Compiler Construction. Lecture Notes in Computer Science. Vol. 3923. pp. 124–138. doi:10.1007/11688839_12. ISBN 978-3-540-33050-9. ISSN 0302-9743. <a href="https://doi.org/10.1007%2F11688839_12" target="_blank">https://doi.org/10.1007%2F11688839_12</a> <a href="#fnref:60" class="footnote-back-ref">↩</a></li>
<li id="fn:61">Eisl et al. 2016, p. 14:1. - Eisl, Josef; Grimmer, Matthias; Simon, Doug; Würthinger, Thomas; Mössenböck, Hanspeter (2016). "Trace-based Register Allocation in a JIT Compiler". Proceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools - PPPJ '16. pp. 1–11. doi:10.1145/2972206.2972211. ISBN 9781450341356. S2CID 31845919. <a href="http://epub.jku.at/doi/10.1145/2972206.2972211" target="_blank">http://epub.jku.at/doi/10.1145/2972206.2972211</a> <a href="#fnref:61" class="footnote-back-ref">↩</a></li>
<li id="fn:62">Eisl et al. 2016, p. 1. - Eisl, Josef; Grimmer, Matthias; Simon, Doug; Würthinger, Thomas; Mössenböck, Hanspeter (2016). "Trace-based Register Allocation in a JIT Compiler". Proceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools - PPPJ '16. pp. 1–11. doi:10.1145/2972206.2972211. ISBN 9781450341356. S2CID 31845919. <a href="http://epub.jku.at/doi/10.1145/2972206.2972211" target="_blank">http://epub.jku.at/doi/10.1145/2972206.2972211</a> <a href="#fnref:62" class="footnote-back-ref">↩</a></li>
<li id="fn:63">Eisl et al. 2016, p. 4. - Eisl, Josef; Grimmer, Matthias; Simon, Doug; Würthinger, Thomas; Mössenböck, Hanspeter (2016). "Trace-based Register Allocation in a JIT Compiler". Proceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools - PPPJ '16. pp. 1–11. doi:10.1145/2972206.2972211. ISBN 9781450341356. S2CID 31845919. <a href="http://epub.jku.at/doi/10.1145/2972206.2972211" target="_blank">http://epub.jku.at/doi/10.1145/2972206.2972211</a> <a href="#fnref:63" class="footnote-back-ref">↩</a></li>
<li id="fn:64">Cavazos, Moss & O’Boyle 2006, p. 124. - Cavazos, John; Moss, J. Eliot B.; O’Boyle, Michael F. P. (2006). "Hybrid Optimizations: Which Optimization Algorithm to Use?". Compiler Construction. Lecture Notes in Computer Science. Vol. 3923. pp. 124–138. doi:10.1007/11688839_12. ISBN 978-3-540-33050-9. ISSN 0302-9743. <a href="https://doi.org/10.1007%2F11688839_12" target="_blank">https://doi.org/10.1007%2F11688839_12</a> <a href="#fnref:64" class="footnote-back-ref">↩</a></li>
<li id="fn:65">Diouf et al. 2010, p. 66. - Diouf, Boubacar; Cohen, Albert; Rastello, Fabrice; Cavazos, John (2010). "Split Register Allocation: Linear Complexity Without the Performance Penalty". High Performance Embedded Architectures and Compilers. Lecture Notes in Computer Science. Vol. 5952. pp. 66–80. CiteSeerX 10.1.1.229.3988. doi:10.1007/978-3-642-11515-8_7. ISBN 978-3-642-11514-1. ISSN 0302-9743. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.229.3988" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.229.3988</a> <a href="#fnref:65" class="footnote-back-ref">↩</a></li>
<li id="fn:66">Cohen & Rohou 2010, p. 1. - Cohen, Albert; Rohou, Erven (2010). "Processor virtualization and split compilation for heterogeneous multicore embedded systems". Proceedings of the 47th Design Automation Conference on - DAC '10. p. 102. CiteSeerX 10.1.1.470.9701. doi:10.1145/1837274.1837303. ISBN 9781450300025. S2CID 14314078. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.470.9701" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.470.9701</a> <a href="#fnref:66" class="footnote-back-ref">↩</a></li>
<li id="fn:67">Diouf et al. 2010, p. 72. - Diouf, Boubacar; Cohen, Albert; Rastello, Fabrice; Cavazos, John (2010). "Split Register Allocation: Linear Complexity Without the Performance Penalty". High Performance Embedded Architectures and Compilers. Lecture Notes in Computer Science. Vol. 5952. pp. 66–80. CiteSeerX 10.1.1.229.3988. doi:10.1007/978-3-642-11515-8_7. ISBN 978-3-642-11514-1. ISSN 0302-9743. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.229.3988" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.229.3988</a> <a href="#fnref:67" class="footnote-back-ref">↩</a></li>
<li id="fn:68">Bouchez, Darte & Rastello 2007a, p. 1. - Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2007a). "On the Complexity of Register Coalescing". International Symposium on Code Generation and Optimization (CGO'07). pp. 102–114. CiteSeerX 10.1.1.101.6801. doi:10.1109/CGO.2007.26. ISBN 978-0-7695-2764-2. S2CID 7683867. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.6801" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.6801</a> <a href="#fnref:68" class="footnote-back-ref">↩</a></li>
<li id="fn:69">Poletto & Sarkar 1999, p. 901-910. - Poletto, Massimiliano; Sarkar, Vivek (1999). "Linear scan register allocation". ACM Transactions on Programming Languages and Systems. 21 (5): 895–913. CiteSeerX 10.1.1.27.2462. doi:10.1145/330249.330250. ISSN 0164-0925. S2CID 18180752. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.2462</a> <a href="#fnref:69" class="footnote-back-ref">↩</a></li>
<li id="fn:70">Blackburn et al. 2006, p. 169. - Blackburn, Stephen M.; Guyer, Samuel Z.; Hirzel, Martin; Hosking, Antony; Jump, Maria; Lee, Han; Eliot, J.; Moss, B.; Phansalkar, Aashish; Stefanović, Darko; VanDrunen, Thomas; Garner, Robin; von Dincklage, Daniel; Wiedermann, Ben; Hoffmann, Chris; Khang, Asjad M.; McKinley, Kathryn S.; Bentzur, Rotem; Diwan, Amer; Feinberg, Daniel; Frampton, Daniel (2006). "The DaCapo benchmarks". Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications - OOPSLA '06. p. 169. doi:10.1145/1167473.1167488. hdl:1885/33723. ISBN 978-1595933485. S2CID 9255051. <a href="https://doi.org/10.1145%2F1167473.1167488" target="_blank">https://doi.org/10.1145%2F1167473.1167488</a> <a href="#fnref:70" class="footnote-back-ref">↩</a></li>
<li id="fn:71">Flajolet, Raoult & Vuillemin 1979. - Flajolet, P.; Raoult, J. C.; Vuillemin, J. (1979), "The number of registers required for evaluating arithmetic expressions", Theoretical Computer Science, 9 (1): 99–125, doi:10.1016/0304-3975(79)90009-4 <a href="https://doi.org/10.1016%2F0304-3975%2879%2990009-4" target="_blank">https://doi.org/10.1016%2F0304-3975%2879%2990009-4</a> <a href="#fnref:71" class="footnote-back-ref">↩</a></li>
</ol>

Register allocation open-in-new

Register allocation