Register allocation

428: 655: 675:: the properties of this intermediate representation simplify the allocation algorithm and allow lifetime holes to be computed directly. First, the time spent in data-flow graph analysis, aimed at building the lifetime intervals, is reduced, namely because variables are unique. It consequently produces shorter live intervals, because each new assignment corresponds to a new live interval. To avoid modeling intervals and liveness holes, Rogers showed a simplification called future-active sets that successfully removed intervals for 80% of instructions. 3494: 488:, to decide which variables are spilled. Finding a minimal coloring graph is indeed an NP-complete problem. 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. 228:. This process is called "spilling" the registers. Over the lifetime of a program, a variable can be both spilled and stored in registers: this variable is then considered as "split". Accessing RAM is significantly slower than accessing registers and so a compiled program runs slower. Therefore, an optimizing compiler aims to assign as many variables to registers as possible. A high " 500:

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

302: 1841:

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

794:

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

761:

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

748:

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. In this approach, the choice between one or the other solution is

704:

Doing coalescing might have both positive and negative impacts on the colorability of the interference graph. 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

700:

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

496:

in the number of live ranges. 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

491:

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. Finally, graph coloring is an aggressive technique

770:

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

509:

Linear scan is another global register allocation approach. It was first proposed by Poletto et al. in 1999. 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

1797:

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,

662:

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. In this approach, spilled variables get the opportunity to be stored later in a register by

356:

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

263:

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

790:

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

715:

it was first introduced by Chaitin original register allocator. This heuristic aims at coalescing any non-interfering, copy-related nodes. From the perspective of copy elimination, this heuristic has the best results. On the other hand, aggressive coalescing could impact the colorability of the

753:

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

208:

runs faster when more variables can be in the CPU's registers. 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

705:

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

650:

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". Besides, a spilled variable will stay spilled for its entire lifetime.

374:

merge points in register allocation reveals itself a time-consuming operation. 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).

667:

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.

510:

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.

501:

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.

293:

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

513:

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

401:, 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 771:

online. In the same fashion, B. Diouf et al. proposed an allocation technique relying both on offline and online behaviors, namely static and dynamic compilation. During the offline stage, an optimal spill set is first gathered using

791:

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.

274:

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

819:, 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. 325:

architecture has four general purpose 32-bit registers that can also be used as 16-bit or 8-bit registers. In this case, assigning a 32-bit value to the eax register will affect the value of the al register.

1879:

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

1007: 267:

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:

779:

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.

370:

of code: it is said to be "local", and was first mentioned by Horwitz et al. As basic blocks do not contain branches, the allocation process is thought to be fast, because the management of

224:

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

314:

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:

782:

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.

232:" 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". 1725:

Barik, Rajkishore; Grothoff, Christian; Gupta, Rahul; Pandit, Vinayaka; Udupa, Raghavendra (2007). "Optimal Bitwise Register Allocation Using Integer Linear Programming".

983: 2408:

Proceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools - PPPJ '16

722:

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.

518:, the used graph coloring algorithm having a quadratic cost. Owing to this feature, linear scan is the approach currently used in several JIT compilers, like the 220:(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 3391: 2146:

Chaitin, Gregory J.; Auslander, Marc A.; Chandra, Ashok K.; Cocke, John; Hopkins, Martin E.; Markstein, Peter W. (1981). "Register allocation via coloring".

389:

Graph-coloring allocation is the predominant approach to solve register allocation. It was first proposed by Chaitin et al. In this approach, nodes in the

2325:

Diouf, Boubacar; Cohen, Albert; Rastello, Fabrice; Cavazos, John (2010). "Split Register Allocation: Linear Complexity Without the Performance Penalty".

3262: 2405:

Eisl, Josef; Grimmer, Matthias; Simon, Doug; Würthinger, Thomas; Mössenböck, Hanspeter (2016). "Trace-based Register Allocation in a JIT Compiler".

3994: 4141: 3386: 492:

for allocating registers, but is computationally expensive due to its use of the interference graph, which can have a worst-case size that is

757:

Trace register allocation is a recent approach developed by Eisl et al. This technique handles the allocation locally: it relies on dynamic

2770:

Mössenböck, Hanspeter; Pfeiffer, Michael (2002). "Linear Scan Register Allocation in the Context of SSA Form and Register Constraints".

734:

it is based on aggressive coalescing, but if the inference graph colorability is compromised, then it gives up as few moves as possible.

1800:

Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications - OOPSLA '06

1762:

Bergner, Peter; Dahl, Peter; Engebretsen, David; O'Keefe, Matthew (1997). "Spill code minimization via interference region spilling".

457:: compute the spill cost of each variable. This assesses the impact of mapping a variable to memory on the speed of the final program. 405:

problem in which colors (registers) are assigned to the nodes such that two nodes connected by an edge do not receive the same color.

239:

frequently-accessed registers. So, programs can be further optimized by assigning the same register to a source and destination of a

2372:

Proceedings of the first international symposium on Architectural support for programming languages and operating systems - ASPLOS-I

321:

In some architectures, assigning a value to one register can affect the value of another: this is called aliasing. For example, the

2245:

Cohen, Albert; Rohou, Erven (2010). "Processor virtualization and split compilation for heterogeneous multicore embedded systems".

2210:

Chen, Wei-Yu; Lueh, Guei-Yuan; Ashar, Pratik; Chen, Kaiyu; Cheng, Buqi (2018). "Register allocation for Intel processor graphics".

4175: 3880: 3400: 1610:

Ahn, Minwook; Paek, Yunheung (2009). "Register coalescing techniques for heterogeneous register architecture with copy sifting".

213:

is translating code to machine-language, it must decide how to allocate variables to the limited number of registers in the CPU.

990: 2111:

Cavazos, John; Moss, J. Eliot B.; O’Boyle, Michael F. P. (2006). "Hybrid Optimizations: Which Optimization Algorithm to Use?".

555:

is the list, sorted in order of increasing end point, of live intervals overlapping the current point and placed in registers.

3255: 3007:

Smith, Michael D.; Ramsey, Norman; Holloway, Glenn (2004). "A generalized algorithm for graph-coloring register allocation".

2989: 2787: 2713: 2544: 2352: 2128: 2017: 1933: 1896: 1752: 762:

be considered as hybrid because it is possible to use different register allocation algorithms between the different traces.

2443: 413: 3987: 2292:

Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems - CASES '11

2962:

Runeson, Johan; Nyström, Sven-Olof (2003). "Retargetable Graph-Coloring Register Allocation for Irregular Architectures".

3961: 3423: 2696:

Johansson, Erik; Sagonas, Konstantinos (2002). "Linear Scan Register Allocation in a High-Performance Erlang Compiler".

416:

where the nodes are the program's variables, is used to model which variables cannot be allocated to the same register.

3475: 3336: 3112: 2752: 2387: 2192: 1823: 1779: 1707: 1670: 427: 357:

Graph Coloring is an NP-Hard problem and Register Allocation is in NP, this proves the NP-completeness of the problem.

4347: 3443: 3157: 3085:

Wimmer, Christian; Mössenböck, Hanspeter (2005). "Optimized interval splitting in a linear scan register allocator".

2571: 2513: 2472: 2424: 2307: 2272: 2227: 4224: 4125: 3554: 3248: 1951:

Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2007b). "On the complexity of spill everywhere under SSA form".

907: 758: 493: 3493: 4373: 4266: 3980: 3046:

Traub, Omri; Holloway, Glenn; Smith, Michael D. (1998). "Quality and speed in linear-scan register allocation".

2064:

Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1994). "Improvements to graph coloring register allocation".

3831: 2805:

Nickerson, Brian R. (1990). "Graph coloring register allocation for processors with multi-register operands".

4161: 3939: 3559: 3132:

Proceedings of the 8th annual IEEE/ ACM international symposium on Code generation and optimization - CGO '10

1990:

Braun, Matthias; Hack, Sebastian (2009). "Register Spilling and Live-Range Splitting for SSA-Form Programs".

695: 672: 248: 32: 2290:

Colombet, Quentin; Brandner, Florian; Darte, Alain (2011). "Studying optimal spilling in the light of SSA".

4245: 3875: 3843: 1764:

Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation - PLDI '97

1682:

Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation - PLDI '01

664: 390: 4296: 4261: 3924: 3549: 484:

The graph-coloring allocation has three major drawbacks. First, it relies on graph-coloring, which is an

394: 244: 193: 4185: 4060: 3870: 3826: 3719: 3448: 3428: 1906:

Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2007a). "On the Complexity of Register Coalescing".

816: 634:

333:

This problem is an act to force some variables to be assigned to particular registers. For example, in

3638: 3087:

Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments - VEE '05

2490:

Eisl, Josef; Leopoldseder, David; Mössenböck, Hanspeter (2018). "Parallel trace register allocation".

4040: 3609: 3271: 531: 519: 3794: 3240: 3212: 3140: 3095: 2844: 2335: 2255: 2000: 1916: 1624: 3656: 3060: 3021: 2914: 2867: 1735: 1690: 2972: 2078: 469:: insert spill instructions, i.e. loads and stores to commute values between registers and memory. 4045: 3838: 3737: 3453: 201: 83: 3225: 2563: 2555: 4193: 4170: 4146: 4075: 3929: 3914: 3804: 3682: 3331: 3308: 3275: 3135: 3090: 3055: 3016: 2967: 2909: 2862: 2839: 2834:

Paleczny, Michael; Vick, Christopher; Click, Cliff (2001). "The Java HotSpot Server Compiler".

2330: 2250: 2073: 1995: 1911: 1730: 1685: 1680:

Appel, Andrew W.; George, Lal (2001). "Optimal spilling for CISC machines with few registers".

1619: 409: 2212:

Proceedings of the 2018 International Symposium on Code Generation and Optimization - CGO 2018

1842:

Miller Raymond E. and Thatcher James W., Plenum Press, New York and London 1972, pp. 85–103".

251:(SSA). In particular, when SSA is not fully optimized it can artificially generate additional 4322: 4317: 4271: 4198: 4022: 4017: 3818: 3784: 3687: 3629: 3510: 3316: 3296: 2537:

Proceedings of the 12th International Workshop on Software and Compilers for Embedded Systems

298:

Many register allocation approaches optimize for one or more specific categories of actions.

94: 20: 2562:. SODA '98. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics. pp. 4352: 4276: 4120: 3865: 3692: 3604: 2493:

Proceedings of the 15th International Conference on Managed Languages & Runtimes - Man

515: 225: 210: 189: 701:

color and be allocated to the same register, once the copy operation becomes unnecessary.

8: 4332: 4095: 4003: 3934: 3799: 3752: 3742: 3594: 3582: 3395: 3378: 3283: 3130:

Wimmer, Christian; Franz, Michael (2010). "Linear scan register allocation on SSA form".

2452:

Proceedings of the 14th International Conference on Managed Languages and Runtimes - Man

772: 1881:

1798:

Rotem; Diwan, Amer; Feinberg, Daniel; Frampton, Daniel (2006). "The DaCapo benchmarks".

728:

it removes one particular move at the time, while keeping the colorability of the graph.

654: 243:

instruction whenever possible. This is especially important if the compiler is using an

4327: 4291: 4110: 4100: 4050: 3669: 3624: 3614: 3405: 3321: 3182: 3163: 3118: 2948: 2935: 2888: 2758: 2684: 2641: 2519: 2478: 2430: 2393: 2313: 2278: 2233: 2198: 2099: 1960: 1939: 1867: 1829: 1785: 1713: 1645: 810: 398: 371: 337: 197: 63: 36: 28: 4208: 4032: 3677: 3355: 3153: 3108: 3073: 3034: 2995: 2985: 2927: 2880: 2822: 2793: 2783: 2748: 2719: 2709: 2676: 2633: 2602: 2581: 2567: 2540: 2509: 2468: 2420: 2383: 2358: 2348: 2303: 2268: 2223: 2188: 2163: 2159: 2134: 2124: 2091: 2052: 2023: 2013: 1978: 1929: 1892: 1859: 1819: 1775: 1748: 1703: 1666: 1637: 684: 236: 229: 217: 2939: 2892: 2762: 2688: 2645: 2532: 2523: 2491: 2434: 2282: 2202: 1789: 1649: 4342: 4281: 4151: 4130: 4090: 4070: 3757: 3747: 3651: 3528: 3433: 3415: 3368: 3279: 3167: 3145: 3100: 3065: 3026: 2977: 2919: 2872: 2814: 2775: 2740: 2701: 2666: 2623: 2597: 2501: 2482: 2460: 2412: 2397: 2375: 2340: 2317: 2295: 2260: 2237: 2215: 2180: 2155: 2116: 2103: 2083: 2044: 2005: 1970: 1943: 1921: 1884: 1851: 1833: 1811: 1803: 1767: 1740: 1717: 1695: 1629: 750: 205: 98: 3122: 2588:(1979), "The number of registers required for evaluating arithmetic expressions", 451:: merge the live ranges of non-interfering variables related by copy instructions. 4337: 3773: 3219: 2981: 2836:

Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM01)

2732: 2450: 2406: 2009: 1888: 1744: 804: 485: 349: 3237:- documentation about x86 processor architecture and low-level code optimization 2900:

Poletto, Massimiliano; Sarkar, Vivek (1999). "Linear scan register allocation".

2344: 2177:

Proceedings of the 1982 SIGPLAN symposium on Compiler construction - SIGPLAN '82

2175:

Chaitin, G. J. (1982). "Register allocation & spilling via graph coloring".

1659: 340:, parameters are commonly passed in R3-R10 and the return value is passed in R3. 4312: 4286: 4085: 4080: 4065: 3761: 3646: 3533: 3467: 3438: 2585: 2035:

Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1992). "Rematerialization".

402: 384: 353: 2737:

24th ACM/IEEE conference proceedings on Design automation conference - DAC '87

1235: 984:"Intel® 64 and IA-32 Architectures Software Developer's Manual, Section 3.4.1" 264:

determine the duration for which a variable should stay at the same location.

4367: 3919: 3903: 3205: 3077: 3038: 2999: 2931: 2884: 2826: 2797: 2779: 2723: 2680: 2637: 2442:

Eisl, Josef; Marr, Stefan; Würthinger, Thomas; Mössenböck, Hanspeter (2017).

2362: 2167: 2138: 2095: 2056: 2027: 1982: 1863: 1641: 3149: 3104: 2876: 2705: 2505: 2464: 2416: 2299: 2264: 1974: 1807: 1633: 873: 871: 858: 856: 281:

This action consists of storing a variable into memory instead of registers.

3857: 3363: 3069: 3030: 2923: 2671: 2654: 2628: 2611: 2379: 2370:

Ditzel, David R.; McLellan, H. R. (1982). "Register allocation for free".

2184: 2087: 2048: 1771: 1699: 1575: 1479: 1050: 586:

424:

The main phases in a Chaitin-style graph-coloring register allocator are:

412:, an interference graph can be built. The interference graph, which is an 4055: 3972: 3944: 3326: 3230: 2560:

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

890: 888: 886: 868: 853: 542:

This describes the algorithm as first proposed by Poletto et al., where:

367: 43: 2818: 2744: 2120: 1925: 1657:

Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. (2006).

807:, the minimum number of registers needed to evaluate an expression tree. 4135: 3202:. An article about GCC's use of SSA and how it improves over older IRs. 2966:. Lecture Notes in Computer Science. Vol. 2826. pp. 240–254. 2853:

Park, Jinpyo; Moon, Soo-Mook (2004). "Optimistic register coalescing".

2774:. Lecture Notes in Computer Science. Vol. 2304. pp. 229–246. 2700:. Lecture Notes in Computer Science. Vol. 2257. pp. 101–119. 2115:. Lecture Notes in Computer Science. Vol. 3923. pp. 124–138. 1994:. Lecture Notes in Computer Science. Vol. 5501. pp. 174–189. 1871: 1729:. Lecture Notes in Computer Science. Vol. 4382. pp. 267–282. 1539: 1515: 1503: 1272: 1062: 1026: 51: 1815: 954: 952: 950: 948: 883: 795:

about register allocation uses especially the Dacapo benchmark suite.

104:

Different number of scalar registers in the most common architectures

4229: 3270: 3234: 2329:. Lecture Notes in Computer Science. Vol. 5952. pp. 66–80. 1491: 1081: 1079: 1077: 527: 523: 301: 67: 2219: 1908:

International Symposium on Code Generation and Optimization (CGO'07)

1883:. Lecture Notes in Computer Science. Vol. 4382. pp. 2–14. 1855: 1158: 1156: 1154: 3346: 3188: 2953: 1587: 964: 945: 671:

Linear scan allocation was also adapted to take advantage from the

79: 3199: 1965: 1551: 1443: 1139: 1127: 1074: 813:, the hint in C and C++ for a variable to be placed in a register. 431:

Chaitin et al.'s iterative graph coloring based register allocator

3666: 3193: 2653:

Horwitz, L. P.; Karp, R. M.; Miller, R. E.; Winograd, S. (1966).

2247:

Proceedings of the 47th Design Automation Conference on - DAC '10

1761: 1356: 1344: 1332: 1296: 1284: 1151: 1014: 334: 1563: 309: 1665:(second ed.). Addison-Wesley Longman Publishing Co., Inc. 1216: 1204: 1038: 1248: 785: 1168: 1103: 2947:

Rogers, Ian (2020). "Efficient global register allocation".

2441: 2145: 1485: 1308: 1260: 1192: 1180: 1091: 1056: 877: 841: 463:: construct an ordering of the nodes in the inferences graph 1796: 1581: 829: 622:

from active add register to pool of free registers

287:

This action consists of assigning a register to a variable.

58:), or across function boundaries traversed via call-graph ( 2489: 2404: 1509: 1455: 1320: 1278: 1068: 933: 894: 862: 2652: 2324: 1545: 1521: 1032: 322: 3189:

Integer Programming and Combinatorial Optimization, IPCO

1724: 439:: discover live range information in the source program. 2580: 1593: 1527: 1467: 1431: 1407: 1397: 1395: 1115: 921: 645: 2539:. SCOPES '09. New York, NY, USA: ACM. pp. 21–30. 2902:

ACM Transactions on Programming Languages and Systems

2855:

ACM Transactions on Programming Languages and Systems

2616:

ACM Transactions on Programming Languages and Systems

2327:

High Performance Embedded Architectures and Compilers

2289: 2066:

ACM Transactions on Programming Languages and Systems

1950: 1905: 1557: 1419: 1380: 1133: 970: 958: 479: 348:

Chaitin et al. showed that register allocation is an

3783: 1878: 1392: 1020: 258: 3006: 2735:(1987). "REAL: a program for REgister ALlocation". 2063: 2034: 1449: 1145: 1085: 708:There are several coalescing heuristics available: 3213:"The Development of Static Single Assignment Form" 3045: 2769: 2110: 1658: 1497: 1368: 1362: 1350: 1338: 1302: 1290: 1162: 66:may require insertion of save/restore around each 2833: 2209: 1656: 1254: 361: 4365: 3084: 2695: 2553: 2531:Koes, David Ryan; Goldstein, Seth Copen (2009). 1222: 1210: 1044: 908:"Latency Comparison Numbers in computer/network" 3194:The Aussois Combinatorial Optimization Workshop 4142:Induction variable recognition and elimination 2961: 2558:. Written at San Francisco, California, USA. 2369: 1727:Languages and Compilers for Parallel Computing 1612:ACM Transactions on Embedded Computing Systems 1174: 1109: 847: 835: 638:to active, sorted by increasing end point 3988: 3256: 3208:. Extensive catalogue of SSA research papers. 2899: 2730: 2554:Farach, Martin; Liberatore, Vincenzo (1998). 2530: 1569: 1314: 1266: 1198: 1186: 1097: 1008:"32-bit PowerPC function calling conventions" 939: 310:Common problems raised in register allocation 3817: 2838:. Monterey, California, USA. pp. 1–12. 1661:Compilers: Principles, Techniques, and Tools 775:. Then, live ranges are annotated using the 378: 3295: 3215:, December 2007 talk on the origins of SSA. 3129: 2964:Software and Compilers for Embedded Systems 2609: 1679: 1461: 1326: 786:Comparison between the different techniques 534:uses graph coloring for its superior code. 4002: 3995: 3981: 3263: 3249: 2698:Practical Aspects of Declarative Languages 2244: 1533: 590:to active, sorted by increasing end point 196:. The computer can quickly read and write 3509: 3139: 3094: 3059: 3020: 2971: 2952: 2913: 2866: 2843: 2804: 2670: 2627: 2601: 2334: 2254: 2077: 1999: 1989: 1964: 1915: 1734: 1689: 1623: 927: 604:active, in order of increasing end point 3497:Optimization computes maxima and minima. 2852: 1473: 1437: 1413: 1069:Eisl, Leopoldseder & Mössenböck 2018 653: 426: 300: 62:). When done per function/procedure the 16:Computer compiler optimization technique 4176:Sparse conditional constant propagation 3581: 2174: 1609: 1425: 1401: 1386: 192:, the programmer may use any number of 4366: 3198:Bosscher, Steven; and Novillo, Diego. 2946: 2610:George, Lal; Appel, Andrew W. (1996). 1374: 1244:. 25 May 2016. Event occurs at 3m47s. 1237:The Evolution of ART - Google I/O 2016 366:Register allocation can happen over a 42:Register allocation can happen over a 3976: 3901: 3717: 3693:Principal pivoting algorithm of Lemke 3580: 3508: 3294: 3244: 1594:Flajolet, Raoult & Vuillemin 1979 658:Shorter live ranges with SSA approach 570:, in order of increasing start point 549:is the number of available registers. 530:, and the Android Runtime (ART). The 475:: assign a register to each variable. 2444:"Trace Register Allocation Policies" 1840: 1121: 743: 678: 626:spill ← last interval in active 2533:"Register Allocation Deconstructed" 1558:Bouchez, Darte & Rastello 2007a 1134:Colombet, Brandner & Darte 2011 971:Colombet, Brandner & Darte 2011 959:Bouchez, Darte & Rastello 2007b 910:. blog.morizyun.com. 6 January 2018 765: 738: 235:In addition, some computer designs 60:interprocedural register allocation 13: 3902: 3492: 3337:Successive parabolic interpolation 3200:GCC gets a new Optimizer Framework 1021:Bouchez, Darte & Rastello 2006 646:Drawbacks and further improvements 480:Drawbacks and further improvements 27:is the process of assigning local 14: 4385: 3718: 3657:Projective algorithm of Karmarkar 3183:A Tutorial on Integer Programming 3176: 1450:Briggs, Cooper & Torczon 1994 1146:Smith, Ramsey & Holloway 2004 1086:Briggs, Cooper & Torczon 1992 989:. Intel. May 2019. Archived from 749:determined dynamically: first, a 259:Components of register allocation 4126:Common subexpression elimination 3652:Ellipsoid algorithm of Khachiyan 3555:Sequential quadratic programming 3392:Broyden–Fletcher–Goldfarb–Shanno 1498:Cavazos, Moss & O’Boyle 2006 1303:Traub, Holloway & Smith 1998 1291:Traub, Holloway & Smith 1998 1163:Cavazos, Moss & O’Boyle 2006 4267:Compile-time function execution 1255:Paleczny, Vick & Click 2001 1228: 1000: 976: 445:: build the interference graph. 35:results to a limited number of 3610:Reduced gradient (Frank–Wolfe) 2612:"Iterated register coalescing" 2556:"On Local Register Allocation" 1363:Mössenböck & Pfeiffer 2002 1351:Mössenböck & Pfeiffer 2002 1339:Mössenböck & Pfeiffer 2002 900: 642:location ← new stack location 574:ExpireOldIntervals(i) 504: 419: 362:Register allocation techniques 1: 3940:Spiral optimization algorithm 3560:Successive linear programming 1844:The Journal of Symbolic Logic 823: 696:Coalescing (computer science) 689: 537: 249:static single-assignment form 4246:Interprocedural optimization 3678:Simplex algorithm of Dantzig 3550:Augmented Lagrangian methods 2982:10.1007/978-3-540-39920-9_17 2603:10.1016/0304-3975(79)90009-4 2590:Theoretical Computer Science 2535:. Written at Nice, France. 2160:10.1016/0096-0551(81)90048-5 2010:10.1007/978-3-642-00722-4_13 1889:10.1007/978-3-540-72521-3_21 1745:10.1007/978-3-540-72521-3_20 1223:Johansson & Sagonas 2002 1211:Wimmer & Mössenböck 2005 1045:Farach & Liberatore 1998 560:LinearScanRegisterAllocation 88: 7: 4297:Profile-guided optimization 4262:Bounds-checking elimination 3220:"SSA-based Compiler Design" 2655:"Index Register Allocation" 2345:10.1007/978-3-642-11515-8_7 798: 582:SpillAtInterval(i) 245:intermediate representation 10: 4390: 4061:Loop-invariant code motion 1602: 1175:Runeson & Nyström 2003 1110:Runeson & Nyström 2003 848:Runeson & Nyström 2003 836:Ditzel & McLellan 1982 773:Integer Linear Programming 693: 682: 382: 92: 77: 73: 56:global register allocation 4305: 4254: 4238: 4217: 4184: 4160: 4109: 4041:Automatic parallelization 4031: 4010: 3957: 3910: 3897: 3881:Push–relabel maximum flow 3856: 3772: 3730: 3726: 3713: 3683:Revised simplex algorithm 3665: 3637: 3623: 3593: 3589: 3576: 3542: 3521: 3517: 3504: 3490: 3466: 3414: 3377: 3354: 3345: 3307: 3303: 3290: 1570:Poletto & Sarkar 1999 1315:Poletto & Sarkar 1999 1267:Poletto & Sarkar 1999 1199:Poletto & Sarkar 1999 1187:Poletto & Sarkar 1999 1098:Poletto & Sarkar 1999 940:Koes & Goldstein 2009 379:Graph-coloring allocation 352:problem. They reduce the 174: 163: 152: 141: 130: 119: 114: 111: 50:), over a whole function/ 48:local register allocation 3406:Symmetric rank-one (SR1) 3387:Berndt–Hall–Hall–Hausman 2780:10.1007/3-540-45937-5_17 4046:Automatic vectorization 3930:Parallel metaheuristics 3738:Approximation algorithm 3449:Powell's dog leg method 3401:Davidon–Fletcher–Powell 3297:Unconstrained nonlinear 3226:Citations from CiteSeer 3150:10.1145/1772954.1772979 3105:10.1145/1064979.1064998 2877:10.1145/1011508.1011512 2706:10.1007/3-540-45587-6_8 2506:10.1145/3237009.3237010 2465:10.1145/3132190.3132209 2417:10.1145/2972206.2972211 2300:10.1145/2038698.2038706 2265:10.1145/1837274.1837303 1975:10.1145/1273444.1254782 1808:10.1145/1167473.1167488 1634:10.1145/1457255.1457263 1462:George & Appel 1996 1327:Wimmer & Franz 2010 719:Conservative Coalescing 630:endpoint > endpoint 532:Hotspot server compiler 520:Hotspot client compiler 393:represent live ranges ( 84:Interpreter (computing) 4374:Compiler optimizations 4194:Instruction scheduling 4171:Global value numbering 4147:Live-variable analysis 4076:Loop nest optimization 4004:Compiler optimizations 3915:Evolutionary algorithm 3498: 1534:Cohen & Rohou 2010 817:Sethi–Ullman algorithm 659: 611:endpoint ≥ startpoint 432: 306: 216:Not all variables are 4323:Control-flow analysis 4318:Array-access analysis 4272:Dead-code elimination 4230:Tail-call elimination 4199:Instruction selection 4023:Local value numbering 4018:Peephole optimization 3688:Criss-cross algorithm 3511:Constrained nonlinear 3496: 3317:Golden-section search 3070:10.1145/277652.277714 3031:10.1145/996893.996875 2924:10.1145/330249.330250 2772:Compiler Construction 2672:10.1145/321312.321317 2629:10.1145/229542.229546 2380:10.1145/800050.801825 2185:10.1145/800230.806984 2113:Compiler Construction 2088:10.1145/177492.177575 2049:10.1145/143103.143143 1992:Compiler Construction 1772:10.1145/258915.258941 1700:10.1145/378795.378854 1582:Blackburn et al. 2006 928:Braun & Hack 2009 731:Optimistic coalescing 712:Aggressive coalescing 657: 592:ExpireOldIntervals(i) 430: 304: 190:programming languages 95:Computer data storage 21:compiler optimization 4353:Value range analysis 4277:Expression templates 4121:Available expression 3605:Cutting-plane method 3231:Optimization manuals 3211:Zadeck, F. Kenneth. 3206:The SSA Bibliography 2739:. pp. 210–215. 2214:. pp. 352–364. 1910:. pp. 102–114. 1766:. pp. 287–295. 1684:. pp. 243–253. 1474:Park & Moon 2004 1438:Park & Moon 2004 1414:Park & Moon 2004 4333:Dependence analysis 4204:Register allocation 4096:Software pipelining 3935:Simulated annealing 3753:Integer programming 3743:Dynamic programming 3583:Convex optimization 3444:Levenberg–Marquardt 3048:ACM SIGPLAN Notices 3009:ACM SIGPLAN Notices 2819:10.1145/93548.93552 2807:ACM SIGPLAN Notices 2745:10.1145/37888.37920 2459:. pp. 92–104. 2179:. pp. 98–101. 2121:10.1007/11688839_12 2037:ACM SIGPLAN Notices 1953:ACM SIGPLAN Notices 1926:10.1109/CGO.2007.26 1402:Ahn & Paek 2009 1033:Horwitz et al. 1966 878:Chaitin et al. 1981 725:Iterated coalescing 578:length(active) = R 486:NP-complete problem 338:calling conventions 305:Intel 386 registers 105: 37:processor registers 29:automatic variables 25:register allocation 4328:Data-flow analysis 4292:Partial evaluation 4101:Strength reduction 4051:Induction variable 3615:Subgradient method 3499: 3424:Conjugate gradient 3332:Nelder–Mead method 2659:Journal of the ACM 2374:. pp. 48–56. 2148:Computer Languages 1572:, p. 901-910. 1500:, p. 124-127. 1124:, p. 618–619. 811:Register (keyword) 777:compressAnnotation 663:using a different 660: 624:SpillAtInterval(i) 433: 372:control-flow graph 307: 103: 64:calling convention 4361: 4360: 4209:Rematerialization 3970: 3969: 3953: 3952: 3893: 3892: 3889: 3888: 3852: 3851: 3813: 3812: 3709: 3708: 3705: 3704: 3701: 3700: 3572: 3571: 3568: 3567: 3488: 3487: 3484: 3483: 3462: 3461: 2991:978-3-540-20145-8 2789:978-3-540-43369-9 2715:978-3-540-43092-6 2584:; Raoult, J. C.; 2546:978-1-60558-696-0 2411:. pp. 1–11. 2354:978-3-642-11514-1 2130:978-3-540-33050-9 2019:978-3-642-00721-7 1935:978-0-7695-2764-2 1898:978-3-540-72520-6 1754:978-3-540-72520-6 1546:Diouf et al. 2010 1522:Diouf et al. 2010 744:Hybrid allocation 685:Rematerialization 679:Rematerialization 410:liveness analysis 230:Register pressure 185: 184: 4381: 4343:Pointer analysis 4282:Inline expansion 4152:Use-define chain 4131:Constant folding 4091:Loop unswitching 4071:Loop interchange 3997: 3990: 3983: 3974: 3973: 3899: 3898: 3815: 3814: 3781: 3780: 3758:Branch and bound 3748:Greedy algorithm 3728: 3727: 3715: 3714: 3635: 3634: 3591: 3590: 3578: 3577: 3519: 3518: 3506: 3505: 3454:Truncated Newton 3369:Wolfe conditions 3352: 3351: 3305: 3304: 3292: 3291: 3265: 3258: 3251: 3242: 3241: 3171: 3143: 3126: 3098: 3081: 3063: 3042: 3024: 3003: 2975: 2958: 2956: 2943: 2917: 2896: 2870: 2849: 2847: 2830: 2801: 2766: 2731:Kurdahi, F. J.; 2727: 2692: 2674: 2649: 2631: 2606: 2605: 2577: 2550: 2527: 2500:. pp. 1–7. 2486: 2448: 2438: 2401: 2366: 2338: 2321: 2286: 2258: 2241: 2206: 2171: 2142: 2107: 2081: 2060: 2031: 2003: 1986: 1968: 1947: 1919: 1902: 1875: 1837: 1793: 1758: 1738: 1721: 1693: 1676: 1664: 1653: 1627: 1597: 1591: 1585: 1579: 1573: 1567: 1561: 1555: 1549: 1543: 1537: 1531: 1525: 1519: 1513: 1510:Eisl et al. 2016 1507: 1501: 1495: 1489: 1486:Eisl et al. 2017 1483: 1477: 1471: 1465: 1459: 1453: 1447: 1441: 1435: 1429: 1423: 1417: 1411: 1405: 1399: 1390: 1384: 1378: 1372: 1366: 1360: 1354: 1348: 1342: 1336: 1330: 1324: 1318: 1312: 1306: 1300: 1294: 1288: 1282: 1279:Eisl et al. 2016 1276: 1270: 1264: 1258: 1252: 1246: 1245: 1232: 1226: 1220: 1214: 1208: 1202: 1196: 1190: 1184: 1178: 1172: 1166: 1160: 1149: 1143: 1137: 1131: 1125: 1119: 1113: 1107: 1101: 1095: 1089: 1083: 1072: 1066: 1060: 1057:Eisl et al. 2017 1054: 1048: 1042: 1036: 1030: 1024: 1018: 1012: 1011: 1004: 998: 997: 995: 988: 980: 974: 968: 962: 956: 943: 937: 931: 925: 919: 918: 916: 915: 904: 898: 895:Eisl et al. 2016 892: 881: 875: 866: 863:Eisl et al. 2016 860: 851: 845: 839: 833: 778: 766:Split allocation 751:machine learning 739:Mixed approaches 716:inference graph. 562:active ← {} 497:register banks. 414:undirected graph 254: 242: 206:computer program 106: 102: 99:Memory hierarchy 4389: 4388: 4384: 4383: 4382: 4380: 4379: 4378: 4364: 4363: 4362: 4357: 4338:Escape analysis 4306:Static analysis 4301: 4250: 4234: 4213: 4186:Code generation 4180: 4156: 4112: 4105: 4027: 4006: 4001: 3971: 3966: 3949: 3906: 3885: 3848: 3809: 3786: 3775: 3768: 3722: 3697: 3661: 3628: 3619: 3596: 3585: 3564: 3538: 3534:Penalty methods 3529:Barrier methods 3513: 3500: 3480: 3476:Newton's method 3458: 3410: 3373: 3341: 3322:Powell's method 3299: 3286: 3269: 3179: 3174: 3160: 3141:10.1.1.162.2590 3134:. p. 170. 3115: 3096:10.1.1.394.4054 3089:. p. 132. 2992: 2845:10.1.1.106.1919 2790: 2755: 2716: 2574: 2547: 2516: 2475: 2446: 2427: 2390: 2355: 2336:10.1.1.229.3988 2310: 2275: 2256:10.1.1.470.9701 2249:. p. 102. 2230: 2220:10.1145/3168806 2195: 2131: 2020: 2001:10.1.1.219.5318 1936: 1917:10.1.1.101.6801 1899: 1856:10.2307/2271828 1826: 1802:. p. 169. 1782: 1755: 1710: 1673: 1625:10.1.1.615.5767 1605: 1600: 1592: 1588: 1580: 1576: 1568: 1564: 1556: 1552: 1544: 1540: 1532: 1528: 1520: 1516: 1508: 1504: 1496: 1492: 1484: 1480: 1472: 1468: 1460: 1456: 1448: 1444: 1436: 1432: 1424: 1420: 1412: 1408: 1400: 1393: 1385: 1381: 1373: 1369: 1361: 1357: 1349: 1345: 1337: 1333: 1325: 1321: 1313: 1309: 1301: 1297: 1289: 1285: 1277: 1273: 1265: 1261: 1253: 1249: 1234: 1233: 1229: 1221: 1217: 1209: 1205: 1197: 1193: 1185: 1181: 1173: 1169: 1161: 1152: 1144: 1140: 1132: 1128: 1120: 1116: 1108: 1104: 1096: 1092: 1084: 1075: 1067: 1063: 1055: 1051: 1043: 1039: 1031: 1027: 1019: 1015: 1006: 1005: 1001: 993: 986: 982: 981: 977: 969: 965: 957: 946: 938: 934: 926: 922: 913: 911: 906: 905: 901: 893: 884: 876: 869: 865:, p. 14:1. 861: 854: 846: 842: 834: 830: 826: 805:Strahler number 801: 788: 776: 768: 746: 741: 698: 692: 687: 681: 648: 643: 540: 507: 482: 422: 387: 381: 364: 312: 261: 252: 240: 187: 101: 91: 86: 76: 17: 12: 11: 5: 4387: 4377: 4376: 4359: 4358: 4356: 4355: 4350: 4348:Shape analysis 4345: 4340: 4335: 4330: 4325: 4320: 4315: 4313:Alias analysis 4309: 4307: 4303: 4302: 4300: 4299: 4294: 4289: 4287:Jump threading 4284: 4279: 4274: 4269: 4264: 4258: 4256: 4252: 4251: 4249: 4248: 4242: 4240: 4236: 4235: 4233: 4232: 4227: 4221: 4219: 4215: 4214: 4212: 4211: 4206: 4201: 4196: 4190: 4188: 4182: 4181: 4179: 4178: 4173: 4167: 4165: 4158: 4157: 4155: 4154: 4149: 4144: 4139: 4133: 4128: 4123: 4117: 4115: 4107: 4106: 4104: 4103: 4098: 4093: 4088: 4086:Loop unrolling 4083: 4081:Loop splitting 4078: 4073: 4068: 4066:Loop inversion 4063: 4058: 4053: 4048: 4043: 4037: 4035: 4029: 4028: 4026: 4025: 4020: 4014: 4012: 4008: 4007: 4000: 3999: 3992: 3985: 3977: 3968: 3967: 3965: 3964: 3958: 3955: 3954: 3951: 3950: 3948: 3947: 3942: 3937: 3932: 3927: 3922: 3917: 3911: 3908: 3907: 3904:Metaheuristics 3895: 3894: 3891: 3890: 3887: 3886: 3884: 3883: 3878: 3876:Ford–Fulkerson 3873: 3868: 3862: 3860: 3854: 3853: 3850: 3849: 3847: 3846: 3844:Floyd–Warshall 3841: 3836: 3835: 3834: 3823: 3821: 3811: 3810: 3808: 3807: 3802: 3797: 3791: 3789: 3778: 3770: 3769: 3767: 3766: 3765: 3764: 3750: 3745: 3740: 3734: 3732: 3724: 3723: 3711: 3710: 3707: 3706: 3703: 3702: 3699: 3698: 3696: 3695: 3690: 3685: 3680: 3674: 3672: 3663: 3662: 3660: 3659: 3654: 3649: 3647:Affine scaling 3643: 3641: 3639:Interior point 3632: 3621: 3620: 3618: 3617: 3612: 3607: 3601: 3599: 3587: 3586: 3574: 3573: 3570: 3569: 3566: 3565: 3563: 3562: 3557: 3552: 3546: 3544: 3543:Differentiable 3540: 3539: 3537: 3536: 3531: 3525: 3523: 3515: 3514: 3502: 3501: 3491: 3489: 3486: 3485: 3482: 3481: 3479: 3478: 3472: 3470: 3464: 3463: 3460: 3459: 3457: 3456: 3451: 3446: 3441: 3436: 3431: 3426: 3420: 3418: 3412: 3411: 3409: 3408: 3403: 3398: 3389: 3383: 3381: 3375: 3374: 3372: 3371: 3366: 3360: 3358: 3349: 3343: 3342: 3340: 3339: 3334: 3329: 3324: 3319: 3313: 3311: 3301: 3300: 3288: 3287: 3268: 3267: 3260: 3253: 3245: 3239: 3238: 3228: 3223: 3216: 3209: 3203: 3196: 3191: 3185: 3178: 3177:External links 3175: 3173: 3172: 3158: 3127: 3114:978-1595930477 3113: 3082: 3061:10.1.1.52.8730 3054:(5): 142–151. 3043: 3022:10.1.1.71.9532 3004: 2990: 2959: 2944: 2915:10.1.1.27.2462 2908:(5): 895–913. 2897: 2868:10.1.1.33.9438 2861:(4): 735–765. 2850: 2831: 2802: 2788: 2767: 2754:978-0818607813 2753: 2728: 2714: 2693: 2650: 2622:(3): 300–324. 2607: 2578: 2572: 2551: 2545: 2528: 2514: 2487: 2473: 2439: 2425: 2402: 2389:978-0897910668 2388: 2367: 2353: 2322: 2308: 2294:. p. 25. 2287: 2273: 2242: 2228: 2207: 2194:978-0897910743 2193: 2172: 2143: 2129: 2108: 2072:(3): 428–455. 2061: 2043:(7): 311–321. 2032: 2018: 1987: 1959:(7): 103–114. 1948: 1934: 1903: 1897: 1876: 1850:(4): 618–619. 1838: 1825:978-1595933485 1824: 1794: 1781:978-0897919074 1780: 1759: 1753: 1736:10.1.1.75.6911 1722: 1709:978-1581134148 1708: 1691:10.1.1.37.8978 1677: 1672:978-0321486813 1671: 1654: 1606: 1604: 1601: 1599: 1598: 1586: 1584:, p. 169. 1574: 1562: 1550: 1538: 1526: 1514: 1502: 1490: 1478: 1476:, p. 741. 1466: 1464:, p. 212. 1454: 1452:, p. 433. 1442: 1440:, p. 738. 1430: 1418: 1416:, p. 736. 1406: 1391: 1379: 1367: 1365:, p. 229. 1355: 1353:, p. 233. 1343: 1341:, p. 234. 1331: 1329:, p. 170. 1319: 1317:, p. 897. 1307: 1305:, p. 141. 1295: 1293:, p. 143. 1283: 1271: 1269:, p. 899. 1259: 1247: 1227: 1225:, p. 102. 1215: 1213:, p. 132. 1203: 1201:, p. 902. 1191: 1189:, p. 895. 1179: 1177:, p. 240. 1167: 1165:, p. 124. 1150: 1148:, p. 277. 1138: 1126: 1114: 1112:, p. 241. 1102: 1100:, p. 896. 1090: 1088:, p. 316. 1073: 1061: 1049: 1047:, p. 566. 1037: 1025: 1013: 999: 996:on 2019-05-25. 975: 963: 961:, p. 103. 944: 932: 930:, p. 174. 920: 899: 882: 867: 852: 850:, p. 242. 840: 827: 825: 822: 821: 820: 814: 808: 800: 797: 787: 784: 767: 764: 745: 742: 740: 737: 736: 735: 732: 729: 726: 723: 720: 717: 713: 691: 688: 680: 677: 647: 644: 566:live interval 558: 557: 556: 550: 539: 536: 506: 503: 481: 478: 477: 476: 470: 464: 458: 452: 446: 440: 421: 418: 403:graph coloring 385:Graph coloring 380: 377: 363: 360: 359: 358: 354:graph coloring 346: 342: 341: 331: 327: 326: 319: 311: 308: 296: 295: 291: 288: 285: 282: 279: 276: 272: 271:Move insertion 260: 257: 255:instructions. 183: 182: 179: 176: 172: 171: 168: 165: 161: 160: 157: 154: 153:POWER/PowerPC 150: 149: 146: 143: 139: 138: 135: 132: 128: 127: 124: 121: 117: 116: 113: 110: 90: 87: 75: 72: 15: 9: 6: 4: 3: 2: 4386: 4375: 4372: 4371: 4369: 4354: 4351: 4349: 4346: 4344: 4341: 4339: 4336: 4334: 4331: 4329: 4326: 4324: 4321: 4319: 4316: 4314: 4311: 4310: 4308: 4304: 4298: 4295: 4293: 4290: 4288: 4285: 4283: 4280: 4278: 4275: 4273: 4270: 4268: 4265: 4263: 4260: 4259: 4257: 4253: 4247: 4244: 4243: 4241: 4237: 4231: 4228: 4226: 4225:Deforestation 4223: 4222: 4220: 4216: 4210: 4207: 4205: 4202: 4200: 4197: 4195: 4192: 4191: 4189: 4187: 4183: 4177: 4174: 4172: 4169: 4168: 4166: 4163: 4159: 4153: 4150: 4148: 4145: 4143: 4140: 4137: 4134: 4132: 4129: 4127: 4124: 4122: 4119: 4118: 4116: 4114: 4108: 4102: 4099: 4097: 4094: 4092: 4089: 4087: 4084: 4082: 4079: 4077: 4074: 4072: 4069: 4067: 4064: 4062: 4059: 4057: 4054: 4052: 4049: 4047: 4044: 4042: 4039: 4038: 4036: 4034: 4030: 4024: 4021: 4019: 4016: 4015: 4013: 4009: 4005: 3998: 3993: 3991: 3986: 3984: 3979: 3978: 3975: 3963: 3960: 3959: 3956: 3946: 3943: 3941: 3938: 3936: 3933: 3931: 3928: 3926: 3923: 3921: 3920:Hill climbing 3918: 3916: 3913: 3912: 3909: 3905: 3900: 3896: 3882: 3879: 3877: 3874: 3872: 3869: 3867: 3864: 3863: 3861: 3859: 3858:Network flows 3855: 3845: 3842: 3840: 3837: 3833: 3830: 3829: 3828: 3825: 3824: 3822: 3820: 3819:Shortest path 3816: 3806: 3803: 3801: 3798: 3796: 3793: 3792: 3790: 3788: 3787:spanning tree 3782: 3779: 3777: 3771: 3763: 3759: 3756: 3755: 3754: 3751: 3749: 3746: 3744: 3741: 3739: 3736: 3735: 3733: 3729: 3725: 3721: 3720:Combinatorial 3716: 3712: 3694: 3691: 3689: 3686: 3684: 3681: 3679: 3676: 3675: 3673: 3671: 3668: 3664: 3658: 3655: 3653: 3650: 3648: 3645: 3644: 3642: 3640: 3636: 3633: 3631: 3626: 3622: 3616: 3613: 3611: 3608: 3606: 3603: 3602: 3600: 3598: 3592: 3588: 3584: 3579: 3575: 3561: 3558: 3556: 3553: 3551: 3548: 3547: 3545: 3541: 3535: 3532: 3530: 3527: 3526: 3524: 3520: 3516: 3512: 3507: 3503: 3495: 3477: 3474: 3473: 3471: 3469: 3465: 3455: 3452: 3450: 3447: 3445: 3442: 3440: 3437: 3435: 3432: 3430: 3427: 3425: 3422: 3421: 3419: 3417: 3416:Other methods 3413: 3407: 3404: 3402: 3399: 3397: 3393: 3390: 3388: 3385: 3384: 3382: 3380: 3376: 3370: 3367: 3365: 3362: 3361: 3359: 3357: 3353: 3350: 3348: 3344: 3338: 3335: 3333: 3330: 3328: 3325: 3323: 3320: 3318: 3315: 3314: 3312: 3310: 3306: 3302: 3298: 3293: 3289: 3285: 3281: 3277: 3273: 3266: 3261: 3259: 3254: 3252: 3247: 3246: 3243: 3236: 3232: 3229: 3227: 3224: 3221: 3217: 3214: 3210: 3207: 3204: 3201: 3197: 3195: 3192: 3190: 3186: 3184: 3181: 3180: 3169: 3165: 3161: 3159:9781605586359 3155: 3151: 3147: 3142: 3137: 3133: 3128: 3124: 3120: 3116: 3110: 3106: 3102: 3097: 3092: 3088: 3083: 3079: 3075: 3071: 3067: 3062: 3057: 3053: 3049: 3044: 3040: 3036: 3032: 3028: 3023: 3018: 3014: 3010: 3005: 3001: 2997: 2993: 2987: 2983: 2979: 2974: 2973:10.1.1.6.6186 2969: 2965: 2960: 2955: 2950: 2945: 2941: 2937: 2933: 2929: 2925: 2921: 2916: 2911: 2907: 2903: 2898: 2894: 2890: 2886: 2882: 2878: 2874: 2869: 2864: 2860: 2856: 2851: 2846: 2841: 2837: 2832: 2828: 2824: 2820: 2816: 2812: 2808: 2803: 2799: 2795: 2791: 2785: 2781: 2777: 2773: 2768: 2764: 2760: 2756: 2750: 2746: 2742: 2738: 2734: 2733:Parker, A. C. 2729: 2725: 2721: 2717: 2711: 2707: 2703: 2699: 2694: 2690: 2686: 2682: 2678: 2673: 2668: 2664: 2660: 2656: 2651: 2647: 2643: 2639: 2635: 2630: 2625: 2621: 2617: 2613: 2608: 2604: 2599: 2596:(1): 99–125, 2595: 2591: 2587: 2586:Vuillemin, J. 2583: 2579: 2575: 2573:0-89871-410-9 2569: 2565: 2561: 2557: 2552: 2548: 2542: 2538: 2534: 2529: 2525: 2521: 2517: 2515:9781450364249 2511: 2507: 2503: 2499: 2498: 2494: 2488: 2484: 2480: 2476: 2474:9781450353403 2470: 2466: 2462: 2458: 2457: 2453: 2445: 2440: 2436: 2432: 2428: 2426:9781450341356 2422: 2418: 2414: 2410: 2409: 2403: 2399: 2395: 2391: 2385: 2381: 2377: 2373: 2368: 2364: 2360: 2356: 2350: 2346: 2342: 2337: 2332: 2328: 2323: 2319: 2315: 2311: 2309:9781450307130 2305: 2301: 2297: 2293: 2288: 2284: 2280: 2276: 2274:9781450300025 2270: 2266: 2262: 2257: 2252: 2248: 2243: 2239: 2235: 2231: 2229:9781450356176 2225: 2221: 2217: 2213: 2208: 2204: 2200: 2196: 2190: 2186: 2182: 2178: 2173: 2169: 2165: 2161: 2157: 2153: 2149: 2144: 2140: 2136: 2132: 2126: 2122: 2118: 2114: 2109: 2105: 2101: 2097: 2093: 2089: 2085: 2080: 2079:10.1.1.23.253 2075: 2071: 2067: 2062: 2058: 2054: 2050: 2046: 2042: 2038: 2033: 2029: 2025: 2021: 2015: 2011: 2007: 2002: 1997: 1993: 1988: 1984: 1980: 1976: 1972: 1967: 1962: 1958: 1954: 1949: 1945: 1941: 1937: 1931: 1927: 1923: 1918: 1913: 1909: 1904: 1900: 1894: 1890: 1886: 1882: 1877: 1873: 1869: 1865: 1861: 1857: 1853: 1849: 1845: 1839: 1835: 1831: 1827: 1821: 1817: 1813: 1809: 1805: 1801: 1795: 1791: 1787: 1783: 1777: 1773: 1769: 1765: 1760: 1756: 1750: 1746: 1742: 1737: 1732: 1728: 1723: 1719: 1715: 1711: 1705: 1701: 1697: 1692: 1687: 1683: 1678: 1674: 1668: 1663: 1662: 1655: 1651: 1647: 1643: 1639: 1635: 1631: 1626: 1621: 1617: 1613: 1608: 1607: 1595: 1590: 1583: 1578: 1571: 1566: 1559: 1554: 1548:, p. 72. 1547: 1542: 1535: 1530: 1524:, p. 66. 1523: 1518: 1511: 1506: 1499: 1494: 1488:, p. 11. 1487: 1482: 1475: 1470: 1463: 1458: 1451: 1446: 1439: 1434: 1428:, p. 99. 1427: 1422: 1415: 1410: 1403: 1398: 1396: 1389:, p. 90. 1388: 1383: 1376: 1371: 1364: 1359: 1352: 1347: 1340: 1335: 1328: 1323: 1316: 1311: 1304: 1299: 1292: 1287: 1280: 1275: 1268: 1263: 1256: 1251: 1243: 1239: 1238: 1231: 1224: 1219: 1212: 1207: 1200: 1195: 1188: 1183: 1176: 1171: 1164: 1159: 1157: 1155: 1147: 1142: 1135: 1130: 1123: 1118: 1111: 1106: 1099: 1094: 1087: 1082: 1080: 1078: 1070: 1065: 1059:, p. 92. 1058: 1053: 1046: 1041: 1035:, p. 43. 1034: 1029: 1022: 1017: 1009: 1003: 992: 985: 979: 973:, p. 26. 972: 967: 960: 955: 953: 951: 949: 942:, p. 21. 941: 936: 929: 924: 909: 903: 896: 891: 889: 887: 880:, p. 47. 879: 874: 872: 864: 859: 857: 849: 844: 838:, p. 48. 837: 832: 828: 818: 815: 812: 809: 806: 803: 802: 796: 792: 783: 780: 774: 763: 760: 755: 752: 733: 730: 727: 724: 721: 718: 714: 711: 710: 709: 706: 702: 697: 686: 676: 674: 669: 666: 656: 652: 641: 637: 633: 629: 625: 621: 617: 614: 610: 607: 603: 600: 596: 593: 589: 585: 581: 577: 573: 569: 565: 561: 554: 551: 548: 545: 544: 543: 535: 533: 529: 525: 521: 517: 511: 502: 498: 495: 489: 487: 474: 471: 468: 465: 462: 459: 456: 453: 450: 447: 444: 441: 438: 435: 434: 429: 425: 417: 415: 411: 406: 404: 400: 396: 392: 386: 376: 373: 369: 355: 351: 347: 344: 343: 339: 336: 332: 329: 328: 324: 320: 317: 316: 315: 303: 299: 292: 289: 286: 283: 280: 277: 273: 270: 269: 268: 265: 256: 250: 246: 238: 233: 231: 227: 223: 219: 214: 212: 207: 203: 199: 195: 191: 180: 177: 173: 169: 166: 162: 158: 155: 151: 147: 144: 140: 136: 133: 129: 125: 122: 118: 109:Architecture 108: 107: 100: 96: 85: 81: 71: 69: 65: 61: 57: 53: 49: 45: 40: 38: 34: 30: 26: 22: 4203: 3925:Local search 3871:Edmonds–Karp 3827:Bellman–Ford 3597:minimization 3429:Gauss–Newton 3379:Quasi–Newton 3364:Trust region 3272:Optimization 3131: 3086: 3051: 3047: 3012: 3008: 2963: 2905: 2901: 2858: 2854: 2835: 2813:(6): 40–52. 2810: 2806: 2771: 2736: 2697: 2665:(1): 43–61. 2662: 2658: 2619: 2615: 2593: 2589: 2582:Flajolet, P. 2559: 2536: 2496: 2492: 2455: 2451: 2407: 2371: 2326: 2291: 2246: 2211: 2176: 2154:(1): 47–57. 2151: 2147: 2112: 2069: 2065: 2040: 2036: 1991: 1956: 1952: 1907: 1880: 1847: 1843: 1799: 1763: 1726: 1681: 1660: 1615: 1611: 1589: 1577: 1565: 1560:, p. 1. 1553: 1541: 1536:, p. 1. 1529: 1517: 1512:, p. 4. 1505: 1493: 1481: 1469: 1457: 1445: 1433: 1426:Chaitin 1982 1421: 1409: 1404:, p. 7. 1387:Chaitin 1982 1382: 1370: 1358: 1346: 1334: 1322: 1310: 1298: 1286: 1281:, p. 2. 1274: 1262: 1257:, p. 1. 1250: 1241: 1236: 1230: 1218: 1206: 1194: 1182: 1170: 1141: 1136:, p. 1. 1129: 1117: 1105: 1093: 1071:, p. 1. 1064: 1052: 1040: 1028: 1023:, p. 4. 1016: 1002: 991:the original 978: 966: 935: 923: 912:. Retrieved 902: 897:, p. 1. 843: 831: 793: 789: 781: 769: 756: 754:algorithms. 747: 707: 703: 699: 670: 661: 649: 639: 635: 631: 627: 623: 619: 615: 612: 608: 605: 601: 598: 594: 591: 587: 583: 579: 575: 571: 567: 563: 559: 552: 546: 541: 512: 508: 499: 490: 483: 472: 466: 460: 454: 448: 442: 436: 423: 407: 388: 365: 330:Pre-coloring 313: 297: 266: 262: 234: 221: 215: 186: 59: 55: 47: 41: 24: 18: 4138:elimination 4056:Loop fusion 4011:Basic block 3945:Tabu search 3356:Convergence 3327:Line search 3187:Conference 1618:(2): 1–37. 1375:Rogers 2020 505:Linear scan 399:temporaries 368:basic block 350:NP-complete 44:basic block 4218:Functional 4136:Dead store 3776:algorithms 3284:heuristics 3276:Algorithms 3015:(6): 277. 2954:2011.05608 1816:1885/33723 914:2019-01-08 824:References 694:See also: 690:Coalescing 683:See also: 538:Pseudocode 467:Spill Code 455:Spill cost 383:See also: 345:NP-Problem 290:Coalescing 284:Assignment 131:Intel x86 93:See also: 78:See also: 33:expression 4111:Data-flow 3731:Paradigms 3630:quadratic 3347:Gradients 3309:Functions 3235:Agner Fog 3136:CiteSeerX 3091:CiteSeerX 3078:0362-1340 3056:CiteSeerX 3039:0362-1340 3017:CiteSeerX 3000:0302-9743 2968:CiteSeerX 2932:0164-0925 2910:CiteSeerX 2885:0164-0925 2863:CiteSeerX 2840:CiteSeerX 2827:0362-1340 2798:0302-9743 2724:0302-9743 2681:0004-5411 2638:0164-0925 2363:0302-9743 2331:CiteSeerX 2251:CiteSeerX 2168:0096-0551 2139:0302-9743 2096:0164-0925 2074:CiteSeerX 2057:0362-1340 2028:0302-9743 1996:CiteSeerX 1983:0362-1340 1966:0710.3642 1912:CiteSeerX 1864:0022-4812 1731:CiteSeerX 1686:CiteSeerX 1642:1539-9087 1620:CiteSeerX 1122:Book 1975 759:profiling 665:heuristic 597:interval 528:Jikes RVM 494:quadratic 420:Principle 395:variables 294:lifetime. 275:approach. 204:, so the 198:registers 194:variables 89:Principle 68:call-site 52:procedure 4368:Category 4113:analysis 3962:Software 3839:Dijkstra 3670:exchange 3468:Hessians 3434:Gradient 2940:18180752 2893:15969885 2763:17598675 2689:14560597 2646:12281734 2524:52137887 2435:31845919 2283:14314078 2203:16872867 1790:16952747 1650:14143277 799:See also 673:SSA form 595:for each 564:for each 516:overhead 461:Simplify 449:Coalesce 437:Renumber 318:Aliasing 278:Spilling 247:such as 211:compiler 188:In many 80:Compiler 3805:Kruskal 3795:Borůvka 3785:Minimum 3522:General 3280:methods 3218:VV.AA. 3168:1820765 2564:564–573 2483:1195601 2398:2812379 2318:8296742 2238:3367270 2104:6571479 1944:7683867 1872:2271828 1834:9255051 1718:1380545 1603:Sources 618:remove 335:PowerPC 200:in the 164:RISC-V 115:64 bit 112:32 bit 74:Context 4239:Global 4164:-based 3667:Basis- 3625:Linear 3595:Convex 3439:Mirror 3396:L-BFGS 3282:, and 3222:(2014) 3166: 3156: 3138: 3123:494490 3121: 3111: 3093: 3076: 3058: 3037: 3019: 2998: 2988: 2970: 2938: 2930: 2912: 2891: 2883: 2865: 2842: 2825: 2796: 2786: 2761: 2751: 2722: 2712: 2687: 2679: 2644: 2636: 2570: 2543: 2522: 2512: 2481: 2471: 2433: 2423: 2396: 2386: 2361: 2351: 2333: 2316: 2306: 2281: 2271: 2253: 2236: 2226: 2201: 2191: 2166: 2137: 2127: 2102: 2094: 2076: 2055: 2026: 2016: 1998: 1981: 1942: 1932: 1914: 1895: 1870: 1862: 1832: 1822: 1788: 1778: 1751: 1733: 1716: 1706: 1688: 1669: 1648: 1640: 1622: 1242:Google 616:return 553:active 473:Select 408:Using 218:in use 175:SPARC 167:16/32 4255:Other 3866:Dinic 3774:Graph 3164:S2CID 3119:S2CID 2949:arXiv 2936:S2CID 2889:S2CID 2759:S2CID 2685:S2CID 2642:S2CID 2520:S2CID 2479:S2CID 2447:(PDF) 2431:S2CID 2394:S2CID 2314:S2CID 2279:S2CID 2234:S2CID 2199:S2CID 2100:S2CID 1961:arXiv 1940:S2CID 1868:JSTOR 1830:S2CID 1786:S2CID 1714:S2CID 1646:S2CID 994:(PDF) 987:(PDF) 443:Build 391:graph 237:cache 142:MIPS 4033:Loop 3832:SPFA 3800:Prim 3394:and 3154:ISBN 3109:ISBN 3074:ISSN 3035:ISSN 2996:ISSN 2986:ISBN 2928:ISSN 2881:ISSN 2823:ISSN 2794:ISSN 2784:ISBN 2749:ISBN 2720:ISSN 2710:ISBN 2677:ISSN 2634:ISSN 2568:ISBN 2541:ISBN 2510:ISBN 2495:Lang 2469:ISBN 2456:2017 2454:Lang 2421:ISBN 2384:ISBN 2359:ISSN 2349:ISBN 2304:ISBN 2269:ISBN 2224:ISBN 2189:ISBN 2164:ISSN 2135:ISSN 2125:ISBN 2092:ISSN 2053:ISSN 2024:ISSN 2014:ISBN 1979:ISSN 1930:ISBN 1893:ISBN 1860:ISSN 1820:ISBN 1776:ISBN 1749:ISBN 1704:ISBN 1667:ISBN 1638:ISSN 640:else 632:then 613:then 584:else 580:then 253:move 241:move 222:same 120:ARM 97:and 82:and 31:and 4162:SSA 3762:cut 3627:and 3233:by 3146:doi 3101:doi 3066:doi 3027:doi 2978:doi 2920:doi 2873:doi 2815:doi 2776:doi 2741:doi 2702:doi 2667:doi 2624:doi 2598:doi 2502:doi 2497:'18 2461:doi 2413:doi 2376:doi 2341:doi 2296:doi 2261:doi 2216:doi 2181:doi 2156:doi 2117:doi 2084:doi 2045:doi 2006:doi 1971:doi 1922:doi 1885:doi 1852:doi 1812:hdl 1804:doi 1768:doi 1741:doi 1696:doi 1630:doi 323:x86 226:RAM 202:CPU 181:31 178:31 170:32 159:32 156:32 148:32 145:32 137:16 126:31 123:15 19:In 4370:: 3278:, 3274:: 3162:. 3152:. 3144:. 3117:. 3107:. 3099:. 3072:. 3064:. 3052:33 3050:. 3033:. 3025:. 3013:39 3011:. 2994:. 2984:. 2976:. 2934:. 2926:. 2918:. 2906:21 2904:. 2887:. 2879:. 2871:. 2859:26 2857:. 2821:. 2811:25 2809:. 2792:. 2782:. 2757:. 2747:. 2718:. 2708:. 2683:. 2675:. 2663:13 2661:. 2657:. 2640:. 2632:. 2620:18 2618:. 2614:. 2592:, 2566:. 2518:. 2508:. 2477:. 2467:. 2449:. 2429:. 2419:. 2392:. 2382:. 2357:. 2347:. 2339:. 2312:. 2302:. 2277:. 2267:. 2259:. 2232:. 2222:. 2197:. 2187:. 2162:. 2150:. 2133:. 2123:. 2098:. 2090:. 2082:. 2070:16 2068:. 2051:. 2041:27 2039:. 2022:. 2012:. 2004:. 1977:. 1969:. 1957:42 1955:. 1938:. 1928:. 1920:. 1891:. 1866:. 1858:. 1848:40 1846:. 1828:. 1818:. 1810:. 1784:. 1774:. 1747:. 1739:. 1712:. 1702:. 1694:. 1644:. 1636:. 1628:. 1614:. 1394:^ 1240:. 1153:^ 1076:^ 947:^ 885:^ 870:^ 855:^ 628:if 609:if 606:do 602:in 576:if 572:do 526:, 524:V8 522:, 397:, 134:8 70:. 39:. 23:, 3996:e 3989:t 3982:v 3760:/ 3264:e 3257:t 3250:v 3170:. 3148:: 3125:. 3103:: 3080:. 3068:: 3041:. 3029:: 3002:. 2980:: 2957:. 2951:: 2942:. 2922:: 2895:. 2875:: 2848:. 2829:. 2817:: 2800:. 2778:: 2765:. 2743:: 2726:. 2704:: 2691:. 2669:: 2648:. 2626:: 2600:: 2594:9 2576:. 2549:. 2526:. 2504:: 2485:. 2463:: 2437:. 2415:: 2400:. 2378:: 2365:. 2343:: 2320:. 2298:: 2285:. 2263:: 2240:. 2218:: 2205:. 2183:: 2170:. 2158:: 2152:6 2141:. 2119:: 2106:. 2086:: 2059:. 2047:: 2030:. 2008:: 1985:. 1973:: 1963:: 1946:. 1924:: 1901:. 1887:: 1874:. 1854:: 1836:. 1814:: 1806:: 1792:. 1770:: 1757:. 1743:: 1720:. 1698:: 1675:. 1652:. 1632:: 1616:8 1596:. 1377:. 1010:. 917:. 636:i 620:j 599:j 588:i 568:i 547:R 54:( 46:(

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.