, SSI: We use Ananian's Static Single Information form

, This live range splitting strategy generalizes the ABCD algorithm for array bounds checking elimination, ABCD: ({def, cond} ? ), vol.16

, This live range splitting strategy, which supports Wegman, CCP: ({def, cond e q } ? )

W. B. Ackerman, Efficient Implementation of Applicative Languages. PhD thesis, 1984.

A. V. Aho, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, 2006.

F. E. Allen and J. Cocke, A program data flow analysis procedure, Communications of the ACM, vol.19, issue.3, pp.137-146, 1976.

F. E. Allen, Control flow analysis, SIGPLAN Not, vol.5, pp.1-19, 1970.

M. N. Bowen-alpern, F. Wegman, and . Kenneth-zadeck, Detecting equality of variables in programs, 15th Symposium on Principles of Programming Languages (POPL'88), pp.1-11, 1988.

S. Ananian, The static single information form, 1999.

F. Pereira and J. Palsberg, Register allocation by puzzle solving, PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, pp.216-226, 2008.

A. W. Appel, Modern compiler implementation in ML, 1998.

A. W. Appel and L. George, Optimal spilling for CISC machines with few registers, ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'01), pp.243-253, 2001.

A. W. Appel and J. Palsberg, Modern Compiler Implementation in Java, 2002.

T. Ball and J. R. Larus, Branch prediction for free, SIGPLAN Notices, vol.28, pp.300-313, 1993.

R. Barik, Efficient optimization of memory accesses in parallel programs, 2009.

R. Barik, C. Grothoff, R. Gupta, V. Pandit, and R. Udupa, Optimal bitwise register allocation using integer linear programming, LCPC, vol.4382, pp.267-282, 2006.

M. Bender and M. Farach-colton, The LCA problem revisited, LATIN 2000: Theoretical Informatics, vol.1776, pp.88-94, 2000.

P. Biggar, Design and Implementation of an Ahead-of-Time Compiler for PHP, 2009.

R. Bodik, R. Gupta, and V. Sarkar, ABCD: eliminating array bounds checks on demand, PLDI, pp.321-333, 2000.

B. Boissinot, A. Darte, B. Dupont-de-dinechin, C. Guillon, and F. Rastello, Revisiting out-of-SSA translation for correctness, code quality, and efficiency, International Symposium on Code Generation and Optimization (CGO'09), pp.114-125, 2009.
URL : https://hal.archives-ouvertes.fr/inria-00349925

B. Boissinot, Towards an SSA-Based Compiler Back-End: Some Interesting Properties of SSA and its Extensions, 2010.

B. Boissinot, F. Brandner, A. Darte, B. Dupont-de-dinechin, and F. Rastello, A non-iterative data-flow algorithm for computing liveness sets in strict ssa programs, 9th Asian Symposium on Programming Languages and Systems (APLAS'11), 2011.

B. Boissinot, P. Brisk, A. Darte, and F. Rastello, SSI properties revisited. ACM Transactions on Embedded Computing Systems, 2010. Special Issue on Software and Compilers for Embedded Systems
URL : https://hal.archives-ouvertes.fr/hal-00761505

B. Boissinot, A. Darte, B. Dupont-de-dinechin, C. Guillon, and F. Rastello, Revisiting out-of-SSA translation for correctness, code quality, and efficiency, International Symposium on Code Generation and Optimization (CGO'09), pp.114-125, 2009.
URL : https://hal.archives-ouvertes.fr/inria-00349925

B. Boissinot, S. Hack, and D. Grund, Benoît Dupont de Dinechin, and Fabrice Rastello, CGO'08: proceedings of the sixth annual ieee/acm international symposium on code generation and optimization, pp.35-44, 2008.

F. Bouchez, A Study of Spilling and Coalescing in Register Allocation as Two Separate Phases, 2009.
URL : https://hal.archives-ouvertes.fr/tel-00403504

F. Bouchez, Q. Colombet, A. Darte, C. Guillon, and F. Rastello, Parallel copy motion, 13th International Workshop on Software & Compilers for Embedded Systems (SCOPES'10), pp.1-10, 2010.
URL : https://hal.archives-ouvertes.fr/inria-00435844

F. Bouchez, A. Darte, C. Guillon, and F. Rastello, Register allocation and spill complexity under SSA, 2005.
URL : https://hal.archives-ouvertes.fr/hal-02102197

F. Bouchez, A. Darte, C. Guillon, and F. Rastello, Register allocation: What does the NP-completeness proof of chaitin et al. really prove?, Workshop on Duplicating, Deconstructing and Debunking (WDDD'06), held in conjunction with the International Symposium on Computer Architecture (ISCA'33), 2006.

F. Bouchez, A. Darte, C. Guillon, and F. Rastello, Register allocation: What does the NP-completeness proof of Chaitin et al. really prove? or revisiting register allocation: Why and how, 19th International Workshop on Languages and Compilers for Parallel Computing (LCPC'06), vol.4382, pp.283-298, 2006.

F. Bouchez, A. Darte, and F. Rastello, On the complexity of register coalescing, International Symposium on Code Generation and Optimization (CGO'07), pp.102-114, 2007.
URL : https://hal.archives-ouvertes.fr/hal-02102282

F. Bouchez, A. Darte, and F. Rastello, On the complexity of spill everywhere under ssa form, Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'07), pp.103-112, 2007.
URL : https://hal.archives-ouvertes.fr/ensl-00180322

F. Bouchez, A. Darte, and F. Rastello, Advanced conservative and optimistic register coalescing, International Conference on Compilers, Architectures and Synthesis for Embedded Systems (CASES'08), pp.147-156, 2008.

F. Brandner and Q. Colombet, Copy elimination on data dependence graphs, Symposium on Applied Computing (SAC'12), 2012.
URL : https://hal.archives-ouvertes.fr/hal-00761499

M. Braun and S. Hack, Register Spilling and Live-Range Splitting for SSA-Form Programs, Compiler Construction, vol.5501, pp.174-189, 2009.

M. Braun, C. Mallon, and S. Hack, Preference-Guided Register Assignment, Compiler Construction, vol.6011, pp.205-223, 2010.

P. Briggs, K. D. Cooper, T. J. Harvey, and L. T. Simpson, Practical improvements to the construction and destruction of static single assignment form. Software-Practice and Experience, vol.28, pp.859-881, 1998.

P. Briggs, Register allocation via graph coloring. PhD thesis, Rice university, 1992.

P. Briggs, K. D. Cooper, and L. Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), vol.16, issue.3, pp.428-455, 1994.

P. Briggs and L. Torczon, An efficient representation for sparse sets, ACM Letters on Programming Languages and Systems (LOPLAS), vol.2, pp.59-69, 1993.

P. Brisk, F. Dabiri, J. Macbeth, and M. Sarrafzadeh, Polynomialtime graph coloring register allocation, 14th International Workshop on Logic and Synthesis, 2005.

Z. Budimlic, K. D. Cooper, T. J. Harvey, K. Kennedy, and T. S. ,

S. W. Oberg and . Reeves, Fast copy coalescing and live-range identification, PLDI, pp.25-32, 2002.

R. Cartwright and M. Felleisen, The semantics of program dependence, SIGPLAN Not, vol.24, issue.7, pp.13-27, 1989.

G. J. Chaitin, Register allocation and spilling via graph coloring, Symposium on Compiler Construction, vol.17, issue.6, pp.98-105, 1982.

G. J. Chaitin, M. A. Auslander, A. K. Chandra, and J. Cocke, Martin E. Hopkins, and Peter W. Markstein. Register allocation via coloring, Computer Languages, vol.6, pp.47-57, 1981.

C. Chambers and D. Ungar, Customization: optimizing compiler technology for self, a dynamically-typed object-oriented programming language, SIGPLAN Not, vol.24, issue.7, pp.146-160, 1989.

J. Choi, R. Cytron, and J. Ferrante, Automatic construction of sparse data flow evaluation graphs, POPL, pp.55-66, 1991.

F. C. Chow and J. L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), vol.12, issue.4, pp.501-536, 1990.

C. Click and M. Paleczny, A simple graph-based intermediate representation, ACM SIGPLAN Workshop on Intermediate Representations, pp.35-49, 1995.

J. Collard, Reasoning about Program Transformations, 2002.

Q. Colombet, B. Boissinot, P. Brisk, S. Hack, and F. Rastello, Graph coloring and treescan register allocation using repairing, International Conference on Compilers, Architectures, and Synthesis of Embedded Systems (CASES'11), 2011.

Q. Colombet, F. Brandner, and A. Darte, Studying optimal spilling in the light of ssa, International Conference on Compilers, Architectures, and Synthesis of Embedded Systems (CASES'11), 2011.
URL : https://hal.archives-ouvertes.fr/hal-01099016

K. D. Cooper and L. Torczon, Engineering a Compiler, 2004.

K. D. Cooper, T. J. Harvey, and K. Kennedy, An empirical study of iterative data-flow analysis, 15th International Conference on Computing (ICC'06), pp.266-276, 2006.

R. Cytron and J. Ferrante, What's in a name? Or the value of renaming for parallelism detection and storage allocation, Proceedings of the 1987 International Conference on Parallel Processing, pp.19-27, 1987.

R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. Kenneth-zadeck, An efficient method of computing static single assignment form, POPL, pp.25-35, 1989.

R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. Kenneth-zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), vol.13, issue.4, pp.451-490, 1991.

R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. Kenneth-zadeck, Efficiently computing static single assignment form and the control dependence graph, TOPLAS, vol.13, issue.4, pp.451-490, 1991.

L. Damas and R. Milner, Principal type-schemes for functional programs, POPL, pp.207-212, 1982.

B. Diouf, A. Cohen, and F. Rastello, A polynomial spilling heuristic: Layered allocation, International Symposium on Code Generation and Optimization (CGO'13), 2013.
URL : https://hal.archives-ouvertes.fr/hal-00713693

B. Diouf, A. Cohen, F. Rastello, and J. Cavazos, Split register allocation: Linear complexity without the performance penalty, International Conference on High-Performance Embedded Architectures and Compilers (HiPEAC'10), vol.5952, pp.66-80, 2010.
URL : https://hal.archives-ouvertes.fr/inria-00551513

C. Douglas-do, F. Teixeira, and . Pereira, The design and implementation of a non-iterative range analysis algorithm on a production compiler, SBLP, pp.45-59, 2011.

E. Duesterwald, R. Gupta, and M. L. Soffa, Reducing the cost of data flow analysis by congruence partitioning, Compiler Construction, 5th International Conference (CC'94), vol.786, pp.357-373, 1994.

B. Dupont-de-dinechin, F. Cois-de-ferrière, C. Guillon, and A. Stoutchinin, Code generator optimizations for the ST120 DSP-MCU core, International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES'00), pp.93-103, 2000.

B. Dupont-de-dinechin, C. Monat, and F. Rastello, Parallel execution of the saturated reductions, Workshop on Signal Processing Systems (SIPS'2001), pp.373-384, 2001.
URL : https://hal.archives-ouvertes.fr/hal-02101824

J. Fabri, Automatic storage optimization, Proceedings of the SIGPLAN symposium on Compiler construction (CC'79), pp.83-91, 1979.

P. Faraboschi, G. Brown, J. A. Fisher, G. Desoli, and F. Homewood, Lx: A technology platform for customizable VLIW embedded processing, Proceedings of the 27th International Symposium on Computer Architecture, pp.203-213, 2000.

M. Farach, -. Colton, and V. Liberatore, On local register allocation, Journal of Algorithms, vol.37, issue.1, pp.37-65, 2000.

P. Feautrier, Automatic parallelization in the polytope model, The Data Parallel Programming Model, pp.79-103, 1996.

T. Gawlitza, J. Leroux, J. Reineke, H. Seidl, G. Sutre et al., Polynomial precise interval analysis revisited, Efficient Algorithms, vol.1, pp.422-437, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00414750

L. George and A. W. Appel, TOPLAS, vol.18, issue.3, pp.300-324, 1996.

L. George and B. Matthias, Taming the ixp network processor, Proceedings of the ACM SIGPLAN 2003 conference on Programming Language Design and Implementation (PLDI'03), pp.26-37, 2003.

M. Gerlek, M. Wolfe, and E. Stoltz, A Reference Chain Approach for Live Variables, 1994.

C. Guillon, F. Rastello, T. Bidault, and F. Bouchez, Procedure placement using temporal-ordering information: Dealing with code size expansion, International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES'04), pp.268-295, 2004.

S. Hack, Register Allocation for Programs in SSA Form, 2007.

S. Hack and G. Goos, Copy coalescing by graph recoloring, ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'08), pp.227-237, 2008.

S. Hack, D. Grund, and G. Goos, Register allocation for programs in SSA-form, International Conference on Compiler Construction (CC'06), vol.3923, pp.247-262, 2006.

D. Harel and R. E. Tarjan, Fast algorithms for finding nearest common ancestors, SIAM J. Comput, vol.13, issue.2, pp.338-355, 1984.

P. Havlak, Nesting of reducible and irreducible loops, ACM Transactions on Programming Languages and Systems, vol.19, issue.4, pp.557-567, 1997.

M. S. Hecht and J. D. Ullman, Characterizations of reducible flow graphs, Journal of the ACM, vol.21, issue.3, pp.367-375, 1974.

M. S. Hecht, Flow Analysis of Computer Programs, 1977.

S. Matthew, J. D. Hecht, and . Ullman, Analysis of a simple algorithm for global data flow problems, 1st annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL'73), pp.207-217, 1973.

A. Jong-hoon-an, J. S. Chaudhuri, M. Foster, and . Hicks, Dynamic inference of static types for ruby, POPL, pp.459-472, 2011.

J. Janssen and H. Corporaal, Making graphs reducible with controlled node splitting, ACM Transactions on Programming Languages and Systems, vol.19, pp.1031-1052, 1997.

R. Johnson, D. Pearson, and K. Pingali, The program tree structure, PLDI, pp.171-185, 1994.

R. Johnson and K. Pingali, Dependence-based program analysis, PLDI, pp.78-89, 1993.

J. B. Kam and J. D. Ullman, Global data flow analysis and iterative algorithms, Journal of the ACM, vol.23, issue.1, pp.158-171, 1976.

K. W. Kennedy, Node listings applied to data flow analysis, 2nd ACM SIGACT-SIGPLAN symposium on Principles of Programming Languages (POPL'75), pp.10-21, 1975.

A. Gary and . Kildall, A unified approach to global program optimization, Symposium on Principles of Programming Languages (POPL'73), pp.194-206, 1973.

T. Kotzmann, C. Wimmer, H. Mössenböck, T. Rodriguez, K. Russell et al., Design of the Java HotSpot TM client compiler for Java 6, ACM Transactions on Architecture and Code Optimization, vol.5, pp.1-32, 2008.

C. Lattner, S. Vikram, and . Adve, LLVM: A compilation framework for lifelong program analysis & transformation, CGO, pp.75-88, 2004.

A. Leung and L. George, Static single assignment form for machine code, International Conference on Programming Language Design and Implementation (PLDI'99), pp.204-214, 1999.

L. Li, J. Xue, and J. Knoop, Scratchpad memory allocation for data aggregates via interval coloring in superperfect graphs, ACM Trans. Embedded Comput. Syst, vol.10, issue.2, p.28, 2010.

, LibFirm: A library that provides an intermediate representation and optimisations for compilers

, LLVM: The LLVM compiler infrastructure

R. Lo, F. Chow, R. Kennedy, S. Liu, and P. Tu, Register promotion by sparse partial redundancy elimination of loads and stores, Conference on Programming Language Design and Implementation (PLDI'(*), pp.26-37, 1998.

R. Lo, F. Chow, R. Kennedy, S. Liu, and P. Tu, Register promotion by sparse partial redundancy elimination of loads and stores, Proceedings of the ACM SIGPLAN 1998 conference on Programming Language Design and Implementation (PLDI'98), pp.26-37, 1998.

S. Mahlke, R. Ravindran, M. Schlansker, R. Schreiber, and T. Sherwood, Bitwidth cognizant architecture synthesis of custom hardware accelerators. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol.20, issue.11, pp.1355-1371, 2001.

C. May, The parallel assignment problem redefined, IEEE Trans. Software Eng, vol.15, issue.6, pp.821-824, 1989.

D. Mcallester, On the complexity analysis of static analyses, Journal of the ACM, vol.49, pp.512-537, 2002.

A. Miné, The octagon abstract domain, Higher Order Symbol. Comput, vol.19, pp.31-100, 2006.

M. Minoux, LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation, Information Processing Letters, vol.29, pp.1-12, 1988.

, Mono: Cross platform, open source .NET development framework

H. Mössenböck and M. Pfeiffer, Linear scan register allocation in the context of SSA form and register constraints, International Conference on Compiler Construction (CC'02), vol.2304, pp.229-246, 2002.

G. Mangala, S. Nanda, and . Sinha, Accurate interprocedural nulldereference analysis for java, ICSE, pp.133-143, 2009.

F. Nielson, Hanne Riis Nielson, and Chris Hankin. Principles of program analysis, 2005.

R. Odaira, T. Nakaike, T. Inagaki, H. Komatsu, and T. Nakatani, Coloring-based coalescing for graph coloring register allocation, Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization, CGO '10, pp.160-169, 2010.

D. A. Padua, Parallelization, automatic, Encyclopedia of Parallel Computing, pp.1442-1450, 2011.

J. Park and S. Moon, Optimistic register coalescing, Proceedings of the International Conference on Parallel Architecture and Compilation Techniques (PACT'98), pp.196-204, 1998.

J. Park and S. Moon, Optimistic register coalescing. ACM Transactions on Programming Languages and Systems, vol.26, issue.4, 2004.

F. M. Pereira and J. Palsberg, Register allocation via coloring of chordal graphs, Proceedings of Asian Symposium on Programming Languages and Systems (APLAS'05), vol.3780, pp.315-329, 2005.

F. Magno, Q. Pereira, and J. Palsberg, SSA elimination after register allocation, CC, pp.158-173, 2009.

K. Pingali and G. Bilardi, APT: A data structure for optimal control dependence computation, PLDI, pp.211-222, 1995.

K. Pingali and G. Bilardi, Optimal control dependence computation and the roman chariots problem, TOPLAS, pp.462-491, 1997.

J. Bradley and P. , Optimization of Object-Oriented and Concurrent Programs, 1996.

M. Poletto and V. Sarkar, Linear scan register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), vol.21, issue.5, pp.895-913, 1999.

R. T. Prosser, Applications of boolean matrices to the analysis of flow diagrams, Eastern joint IRE-AIEE-ACM computer conference, pp.133-138, 1959.

G. Ramalingam, Identifying loops in almost linear time, ACM Transactions on Programming Languages and Systems, vol.21, issue.2, pp.175-188, 1999.

G. Ramalingam, On loops, dominators, and dominance frontiers, ACM Transactions on Programming Languages and Systems, vol.24, issue.5, pp.455-490, 2002.

G. Ramalingam, On sparse evaluation representations, Theoretical Computer Science, vol.277, issue.1-2, pp.119-147, 2002.

F. Rastello, C. François-de-ferrière, and . Guillon, Optimizing translation out of SSA using renaming constraints, International Symposium on Code Generation and Optimization (CGO'04), pp.265-278, 2004.

U. Lakshminarayanan-renganarayana, S. Ramakrishna, and . Rajopadhye, Combined ilp and register tiling: Analytical model and optimization framework, Languages and Compilers for Parallel Computing, vol.4339, pp.244-258, 2006.

A. A. Rimsa, M. Amorim, and F. M. Pereira, Tainted flow analysis on e-SSA-form programs, CC, pp.124-143, 2011.

H. Rong, Tree Register Allocation, Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture, pp.67-77, 2009.

H. Rong, A. Douillet, and G. R. Gao, Register allocation for software pipelined multidimensional loops, ACM Trans. Program. Lang. Syst, vol.30, issue.4, 2008.

B. K. Rosen, F. K. Zadeck, and M. N. Wegman, Global value numbers and redundant computations, POPL, pp.12-27, 1988.

S. Roy and Y. N. Srikant, The hot path ssa form: Extending the static single assignment form for speculative optimizations, CC, pp.304-323, 2010.

G. Barbara, M. C. Ryder, and . Paull, Elimination algorithms for data flow analysis, ACM Computing Surveys, vol.18, issue.3, pp.277-316, 1986.

V. Sarkar and R. Barik, Extended linear scan: an alternate foundation for global register allocation, LCTES/CC, pp.141-155, 2007.

B. Scholz, C. Zhang, and C. Cifuentes, User-input dependence analysis via graph reachability, 2008.

J. Singer, Static Program Analysis Based on Virtual Register Renaming, 2006.

M. D. Smith, N. Ramsey, and G. Holloway, A generalized algorithm for graph-coloring register allocation, PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pp.277-288, 2004.

C. Vugranam, R. Sreedhar, D. M. Ju, V. Gillies, and . Santhanam, Translating out of static single assignment form, SAS, pp.194-210, 1999.

M. Stephenson, J. Babb, and S. Amarasinghe, Bidwidth analysis with application to silicon compilation, PLDI, pp.108-120, 2000.

Z. Su and D. Wagner, A class of polynomially solvable range constraints for interval analysis without widenings and narrowings, TACAS, pp.280-295, 2004.

Z. Su and D. Wagner, A class of polynomially solvable range constraints for interval analysis without widenings, Theoretical Computer Science, vol.345, issue.1, pp.122-138, 2005.

R. E. Tarjan, Testing flow graph reducibility, Journal of Computer and System Sciences, vol.9, issue.3, pp.355-365, 1974.

A. Tavares, Q. Colombet, M. Bigonha, C. Guillon, M. Q. Fernando et al., Decoupled graph-coloring register allocation with hierarchical aliasing, 14th International Workshop on Software and Compilers for Embedded Systems (SCOPES'11), pp.1-10, 2011.

S. Tobin, -. , and M. Felleisen, The design and implementation of typed scheme, pp.395-406, 2008.

O. Traub, G. H. Holloway, and M. D. Smith, Quality and speed in linear-scan register allocation, ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'98), pp.142-151, 1998.

W. T. Trotter, Combinatorics and Partially Ordered Sets: Dimension Theory, 1992.

N. Mark, F. Wegman, and . Kenneth-zadeck, Constant propagation with conditional branches, TOPLAS, vol.13, issue.2, 1991.

M. Weiss, The transitive closure of control dependence: the iterated join, TOPLAS, vol.1, issue.2, pp.178-190, 1992.

C. Wimmer and M. Franz, Linear scan register allocation on SSA form, IEEE/ACM International Symposium on Code Generation and Optimization (CGO'10), pp.170-179, 2010.

C. Wimmer and H. Mössenböck, Optimized interval splitting in a linear scan register allocator, 1st ACM/USENIX International Conference on Virtual Execution Environments (VEE), pp.132-141, 2005.

B. Yang, S. Moon, S. Park, J. Lee, S. Lee et al., Latte: A java vm just-in-time compiler with fast and efficient register allocation. Parallel Architectures and Compilation Techniques, p.128, 1999.

F. Kenneth-zadeck, Incremental Data Flow Analysis in a Structured Program Editor, 1984.