SSA Bibliography SSA bibliography This is a bibliography of 106 papers relating to static single assignment form (SSA). I read most of these papers while studying for my PhD. Any comments below reflect my (perhaps immature) opinions at that time. This bibliography is also available and searchable via the computer science bibliography collection. I will endeavour to maintain this bibliography, and update it as new papers become available. Please contact me with details of relevant papers. Thanks to Dibyendu Das (IBM India), Kenneth Zadeck (NaturalBridge) and Keith D. Cooper (Rice University) for their helpful contributions. Note that there is a very useful introductory article about SSA on wikipedia. Compiler textbooks [1] Andrew W. Appel. Modern Compiler Implementation in {C,Java,ML}. Cambridge University Press, 1998. [ bib ] [2] Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997. [ bib ] [3] Randy Allen and Ken Kennedy. Optimizing Compilers for Modern Architectures: A Dependence-Based Approach. Morgan Kaufmann, 2002. [ bib ] [4] Flemming Nielson, Hanne Riis Nielson, and Chris Hankin. Principles of Program Analysis. Springer, 1999. [ bib ] [5] Keith D. Cooper and Linda Torczon. Engineering a Compiler. Morgan Kaufmann, 2004. [ bib ] plenty of information about SSA [6] Robert Morgan. Building an Optimizing Compiler. Digital Press, 1998. [ bib ] out of print SSA construction papers [1] Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451-490, Oct 1991. [ bib | http ] The most important paper in the field. Comprehensive yet readable. Note there was an earlier version at POPL 89. [2] Mark N. Wegman and F. Kenneth Zadeck. Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems, 13(2):181-210, Apr 1991. [ bib | http ] A fascinating account of constant propagation - different approaches. Clear application of SSA to good advantage. [3] B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Global value numbers and redundant computations. In Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 12-27, 1988. [ bib | http ] early paper from SSA authors [4] B. Alpern, M. N. Wegman, and F. K. Zadeck. Detecting equality of variables in programs. In Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 1-11, 1988. [ bib | http ] early paper from SSA authors [5] Preston Briggs, Keith D. Cooper, Timothy J. Harvey, and L. Taylor Simpson. Practical improvements to the construction and destruction of static single assignment form. Software-Practice and Experience, 28(8):859-881, Jul 1998. [ bib | .html ] describes semi-pruned SSA form, as used in Machine SUIF. Cheaper to compute than fully pruned form yet nearly as small. [6] John Aycock and Nigel Horspool. Simple generation of static single assignment form. In Proceedings of the 9th International Conference in Compiler Construction, volume 1781 of Lecture Notes in Computer Science, pages 110-125. Springer, 2000. [ bib | .html ] pessimistic construction of SSA - not v efficient idea but a really neat way of presenting it [7] Marc M. Brandis and Hanspeter Mössenböck. Single-pass generation of static single-assignment form for structured languages. ACM Transactions on Programming Languages and Systems, 16(6):1684-1698, Nov 1994. [ bib | http ] syntax directed SSA construction for Oberon, a high-level very well-structured language [8] J.-D. Choi, V. Sarkar, and E. Schonberg. Incremental computation of static single assignment form. In Sixth International Conference on Compiler Construction, volume 1060 of Lecture Notes in Computer Science, pages 223-237, Apr 1996. [ bib ] [9] Matthias Braun, Sebastian Buchwald, Sebastian Hack, Roland Leißa, Christoph Mallon, and Andreas Zwinkau. Simple and efficient construction of static single assignment form. In Proceedings of the International Conference on Compiler Construction, Lecture Notes in Computer Science, 2013. [ bib | .pdf ] Whereas Cytron et al.’s algorithm is an eager forwards approach, this new approach is lazy and backwards i.e. it searches backwards from uses to find reaching definitions, inserting φ functions at control flow join points along the way. Memoization avoids repeated lookups, on-the-fly optimization simplifies generated IR. Implemented in LLVM Pre-SSA Historical Papers [1] R. M. Shapiro and H. Saint. The representation of algorithms. Technical Report RADC-TR-69-313, Rome Air Development Center, September 1969. [ bib | .pdf ] early inspiration for SSA. Discusses variable names, data dependence, control flow, graphical notation, etc. [2] Thomas Lengauer and Robert E. Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM Transactions on Programming Languages and Systems, 1(1):121-141, Jul 1979. [ bib | http ] the classic paper on how to compute dominators quickly. [3] J. H. Reif and R. E. Tarjan. Symbolic program analysis in almost linear time. SIAM Journal on Computing, 11(1):81-93, Feb 1982. [ bib | http ] ***The date is wrong on the top of the paper.*** In this paper an "optimal" algorithm is given to compute simple join birthpoints. An earlier version appeared in POPL [4] J. H. Reif and H. R. Lewis. Symbolic evaluation and the global value graph. In Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pages 104-118, 1977. [ bib | http ] global value graph (pre-SSA IR) for linear time constant propagation [5] J. H. Reif and H. R. Lewis. Efficent symbolic analysis of programs. Journal of Computer and System Sciences, 32(3):280-313, Jun 1986. [ bib | http ] linear algorithm is given to perform constant propagation in time linear in the size of the use-definition chains. Updated version of Reif77 and Reif82 phi-function placement algorithms [1] Gianfranco Bilardi and Keshav Pingali. The static single assignment form and its computation. Technical report, Department of Computer Science, Cornell University, Jul 1999. [ bib | .html ] a linear φ-function placement algm [2] Gianfranco Bilardi and Keshav Pingali. Algorithms for computing the static single assignment form. Journal of the ACM, 50(3):375-425, May 2003. [ bib | http ] rather complicated expansion of above tech report. Theoretical framework for φ-fn placement algorithms, general enough to cope with most other placement algms! [3] Vugranam C. Sreedhar and Guang R. Gao. A linear time algorithm for placing φ-nodes. In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 62-73, 1995. [ bib | http ] title says it all - although this one doesn't go as fast as Bilardi and Pingali, according to BP's paper (a personal communication). However, this is the one that Microsoft use for their Marmot compiler - so it must be ok... uses data structures known as DJ-graphs. [4] Dibyendu Das and U. Ramakrishna. A practical and fast iterative algorithm for φ-function computation using DJ graphs. ACM Transactions on Programming Languages and Systems, 27(3):426-440, 2005. [ bib ] precomputes merge sets for each CFG node. The merge set is the set of locations where phi-fns will be needed for vars defined in n. Do not need to recompute if phi-fns are later placed in n. Apparently good for dense variable definitions, demonstrated on SPEC CPU 2000. SSA extensions [1] Kathleen Knobe and Vivek Sarkar. Array SSA form and its use in parallelization. In Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 107-120, 1998. [ bib | http ] extends SSA form to handle arrays more elegantly [2] Stephen Fink, Kathleen Knobe, and Vivek Sarkar. Unified analysis of array and object references in strongly typed languages. In Proceedings of the 7th International Static Analysis Symposium, volume 1824 of Lecture Notes in Computer Science, pages 155-174. Springer, 2000. [ bib | .html ] extends SSA to handle arrays and objects, in Java-like langs. Builds upon the original Array SSA - by splitting classes up into heap-arrays of appropriate fields, and indexing into these heap arrays by object references (quite clever!) Then just uses standard Array SSA transformation. three kinds of phi nodes - standard, then array defn phi, then array use phi. Rename arrays each time we do a lookup (cf SSU). Uses global value numbering instead of points-to analysis to determine when object references are same/different. Analysis enables scalar replacement - remove redundant loads, then redundant stores. Comments that transformation to SSA leads to flow-sensitivity property. Actually implemented in IBM Jalapeno JIT compiler. [3] Paul Feautrier. Dataflow analysis of array and scalar references. International Journal of Parallel Programming, 20(1):23-51, Feb 1991. [ bib | .html ] Introduces the concept of dynamic single assignment form (DSA). [4] Carl Offner and Kathleen Knobe. Weak dynamic single assignment form. Technical Report TR-HPL-2003-169, HP Labs, Nov 2003. [ bib | .html ] reviews array SSA, goes onto develop dynamic single assignment, which is similar to linear naming, only seems to be for arrays. Make it work by adding extra dimensions to arrays to cope with repeated assignments to same elements (probably due to loops) [5] B. Ramakrishna Rau. Iterative modulo scheduling. International Journal of Parallel Processing, 24(1):3-64, Feb 1996. [ bib | .html ] also available as a HP Labs technical report. Describes DSA and expanded virtual registers, the cloning support nec for DSA. Basically converts each scalar into an array [6] Peter Vanbroekhoven, Gerda Janssens, Maurice Bruynooghe, Henk Corporaal, and Francky Catthoor. A step towards a scalable dynamic single assignment conversion. Technical Report CW 360, Department of Computer Science, Katholieke Universiteit Leuven, Apr 2003. [ bib | .html ] gives some motivation for DSA in terms of memory hierarchy design for embedded systems. Then gives two diff methods for constructing DSA, one from SSA, one from CFG. Plenty of discussion, no results and not much analysis. [7] Ron Cytron and Reid Gershbein. Efficient accommodation of may-alias information in SSA form. In Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation, pages 36-45, 1993. [ bib | http ] really simple [8] Fred C. Chow, Sun Chan, Shin-Ming Liu, Raymond Lo, and Mark Streich. Effective representation of aliases and indirect memory operations in SSA form. In Proceedings of the International Conference on Compiler Construction, volume 1060 of Lecture Notes in Computer Science, pages 253-267. Springer, 1996. [ bib | .html ] rather complicated! [9] Christopher Lapkowski and Laurie J. Hendren. Extended SSA numbering: Introducing SSA properties to language with multi-level pointers. In Proceedings of the 7th International Conference on Compiler Construction, volume 1383 of Lecture Notes in Computer Science, pages 128-143. Springer, 1998. [ bib | .html ] SSA for pointers. No phi nodes, instead it just does global value numbering for scalar variables, and for single-indirect pointers. A ptr has two global value numbers, one for the var itself, and one for the location it points to. This allows us to detect symbolic equality, and to make assumptions about definition sets. No explicit phi nodes, they aren't deemed necessary. [10] Rebecca Hasti and Susan Horwitz. Using static single assignment form to improve flow-insensitive pointer analysis. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, pages 97-105, 1998. [ bib | http ] Claims that SSA turns flow-insensitive analysis into flow-sensitive analysis. Slightly suspect paper. But interesting claim, even if not backed up formally. [11] Lori Carter, Beth Simon, Brad Calder, Larry Carter, and Jeanne Ferrante. Predicated static single assignment. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, pages 245-255, 1999. [ bib | http ] a little like SSI, if you factor full-path-predicates into the variable names. Does SSA-like scheme for predicated ISAs, such as IA64. [12] J. Knoop and O. Rüthing. Constant propagation on predicated code. Journal of Universal Computer Science, 9(8):829-850, 2003. [ bib | http ] constant propagation analysis on a value graph, relies on a predicated form of SSA [13] Jin Lin, Tong Chen, Wei-Chung Hsu, Pen-Chung Yew, Roy Dz-Ching Ju, Tin-Fook Ngai, and Sun Chan. A compiler framework for speculative analysis and optimizations. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation, pages 289-299, 2003. [ bib | http ] quite involved, but enables data speculation in SSA form, with notion of likeliness of operations [14] Subhajit Roy and Y. N. Srikant. The hot path ssa form: Extending the static single assignment form for speculative optimizations. In Proceedings of the International Conference on Compiler Construction, volume 6011/2010 of Lecture Notes in Computer Science, pages 304-323, 2010. [ bib | http ] Does profiling to identify hot paths through a CFG, then introduces the tau-function, which allows us to discard variable definitions from non-hot paths, enabling speculative optimizations like constant propagation. Shows how speculative constant propagation works on real programs, with a hit-rate metric that shows how often speculation is correct. [15] Harini Srinivasan, James Hook, and Michael Wolfe. Static single assignment for explicitly parallel programs. In Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 260-272, 1993. [ bib | http ] early attempt at dealing with simple kind of parallelism, introduces extra pseudo-assignment for parallel merge points [16] Jaejin Lee, Samuel P. Midkiff, and David A. Padua. Concurrent static single assignment form and constant propagation for explicitly parallel programs. In Proceedings of the 10th International Workshop on Languages and Compilers for Parallel Computing, volume 1366 of Lecture Notes in Computer Science, pages 114-130. Springer, 1997. [ bib | .html ] caters for more complicated parallel programs, introduces an extra pseudo-assignment [17] Diego Novillo, Ronald C. Unrau, and Jonathan Schaeffer. Concurrent SSA form in the presence of mutual exclusion. In Proceedings of the International Conference on Parallel Processing, pages 356-364, 1998. [ bib | .html ] more complicated still. Extends CSSA with support for mutexes [18] Jaejin Lee, David A. Padua, and Samuel P. Midkiff. Basic compiler algorithms for parallel programs. In Proceedings of the 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 1-12, 1999. [ bib | http ] clearest description of concurrent CFGs and CSSA. With three diff kinds of pseudo-assignment now. [19] Rastislav Bodik, Rajiv Gupta, and Vivek Sarkar. ABCD: eliminating array bounds checks on demand. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, pages 321-333, 2000. [ bib | http ] similar to SSI, has phi functions, and also pi functions to rename at conditional branches and after array bounds checks [20] Eric James Stoltz. Intermediate Compiler Analysis via Reference Chaining. PhD thesis, Oregon Graduate Institute of Science and Technology, Jan 1995. [ bib | .ps.gz ] reference chaining - a generalization of SSA. For forwards or backwards data flow problems, but not both. Talks a lot about factored use and def chains. A student of Michael Wolfe's [21] Eric Stoltz, Michael P. Gerlek, and Michael Wolfe. Extended SSA with factored use-def chains to support optimization and parallelism. In Proceedings of the Hawaii International Conference on Systems Sciences, pages 43-52, 1994. [ bib | .html ] introduces concept of factored use-def chains, as a form of SSA [22] Michael P. Gerlek, Eric Stoltz, and Michael Wolfe. Beyond induction variables: detecting and classifying sequences using a demand-driven ssa form. ACM Transactions on Programming Languages and Systems, 17(1):85-122, 1995. [ bib | http ] haven't actually read this. It uses a variant of SSA to discover properties of variables. Mentions FUD chains. [23] Allen Leung and Lal George. Static single assignment form for machine code. In Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design and Implementation, pages 204-214, 1999. [ bib | http ] simple techniques so machine code can be properly represented as SSA, and optimised using SSA algms [24] Jeffery von Ronne, Ning Wang, and Michael Franz. Interpreting programs in static single assignment form. In Proceedings of the ACM SIGPLAN 2004 Workshop on Interpreters, Virtual Machines and Emulators, pages 23-30, 2004. [ bib | http ] interpretable SSA. Simple techniques to interpret phi fns, single-assignment arrays, etc. V similar to SafeTSA Interprocedural SSA [1] Shih-Wei Liao, Amer Diwan, Robert P. Bosch, Jr., Anwar Ghuloum, and Monica S. Lam. Suif explorer: an interactive and interprocedural parallelizer. In Proceedings of the 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 37-48, 1999. [ bib | .html ] describes interprocedural SSA - similar to supergraph. For program visualization and slicing, in order to do user-assisted parallelization in an interactive manner [2] Stefan Staiger, Gunther Vogel, Steffen Keul, and Eduard Wiebe. Interprocedural Static Single Assignment Form. In Proceedings of the 14th Working Conference on Reverse Engineering, pages 1-10, 2007. [ bib | http ] describes the concepts and implementation of the interprocedural SSA framework as implemented in Bauhaus. Can be used together with many different pointer analyses. Static Single Information [1] C. Scott Ananian. The static single information form. Technical Report MIT-LCS-TR-801, Laboratory for Computer Science, Massachusetts Institute of Technology, Sep 1999. [ bib | http ] First half is nice and hacky - all about why SSI is needed, contrasting it with SSA, etc., also a (slightly strange) way to construct it using SESE regions. Second half is wierd and wonderful theory, whcich hopefully we can largely ignore - gives an executable semantics to some variant of the standard SSI form. [2] Benoit Boissinot, Philip Brisk, Alain Darte, and Fabrice Rastello. Ssi properties revisited. ACM Trans. Embed. Comput. Syst., 11S(1):21:1-21:23, June 2012. [ bib | DOI | http ] Corrects mistakes in previous definitions of SSI. Considers properties of live ranges in SSI programs. SSI applications [1] Radu Rugina and Martin Rinard. Symbolic bounds analysis of pointers, array indices and accessed memory regions. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, pages 182-195, 2000. [ bib | http ] hard-going, but just a brief mention of the merits of SSI in the conclusions [2] Mark Stephenson, Jonathan Babb, and Saman Amarasinghe. Bitwidth analysis with application to silicon compilation. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, pages 108-120, 2000. [ bib | http ] fascinating stuff, quite simple to read. Quite early on they mention that SSI might be a possible alternative intermediate form, just a footnote [3] Ovidiu Gheorghioiu, Alexandru Salcianu, and Martin Rinard. Interprocedural compatibility analysis for static object preallocation. In Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium of Principles of Programming Languages, pages 273-284, 2003. [ bib | http ] [4] C. Scott Ananian and Martin Rinard. Data size optimizations for Java programs. In Proceedings of the 2003 ACM SIGPLAN Conference on Languages, Compilers and Tools for Embedded Systems, pages 59-68, 2003. [ bib | http ] [5] Wolfgang Mayer and Markus Stumptner. Debugging program exceptions. In Proceedings of the 14th International Workshop on Principles of Diagnosis, pages 119-124, 2003. [ bib | .pdf ] does debugging using model checking, for Java programs. Uses SSI in order to construct the model. Cites me as well as Ananian for SSI construction! [6] John Teifel and Rajit Manohar. Static tokens: Using dataflow to automate concurrent pipeline synthesis. In Proceedings of the 10th International Symposium on Asynchronous Circuits and Systems, pages 17-27, 2004. [ bib | http ] uses SSI for some kind of ECAD-like hardware synthesis Static Single Use [1] Raymond Lo, Fred Chow, Robert Kennedy, Shin-Ming Liu, and Peng Tu. Register promotion by sparse partial redundancy elimination of loads and stores. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, pages 26-37, 1998. [ bib | http ] presents static single use form, complete with lambda (inverse phi) nodes - uses it to do PRE for STORE instrs [2] Lal George and Matthias Blume. Taming the IXP network processor. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation, pages 26-37, 2003. [ bib | http ] A rather more informal SSU presentation - for register allocation in IXP processors - with no reference to other SSU work [3] John Bradley Plevyak. Optimization of Object-Oriented and Concurrent Programs. PhD thesis, University of Illinois at Urbana-Champaign, Aug 1996. [ bib | .ps ] defines static single use - BUT - really SSI - only rename at control flow split points, uses ψ-nodes instead of σ-nodes. Linear Naming [1] Alan Bawden. Implementing distributed systems using linear naming. Technical Report 1627, Massachusetts Institute of Technology Artificial Intelligence Laboratory, Mar 1993. [ bib | .html ] transforming programs so that they have linear names - a linear name is only used once (PhD thesis). [2] Henry G. Baker. `Use-once' variables and linear objects-storage management, reflection and multi-threading. ACM SIGPLAN Notices, 30(1):45-52, Jan 1995. [ bib | http ] introduction to use-once variables. Argues that they are needed in mainstream programming languages. Gives some examples from LISP world. SSA applications [1] Robert Kennedy, Sun Chan, Shin-Ming Liu, Raymond Lo, Peng Tu, and Fred Chow. Partial redundancy elimination in SSA form. ACM Transactions on Programming Languages and Systems, 21(3):627-676, May 1999. [ bib | http ] shows how to do PRE using SSA - derives factored redundancy graph from SSA and does forwards and backwards data flow analysis on this. Shows how to use SSA to do analysis/optimization for expressions, not just for vars. Also defines an interesting density function to measure sparseness. [2] Thomas VanDrunen and Antony L. Hosking. Value-based partial redundancy elimination. In 13th International Conference on Compiler Construction, volume 2985 of Lecture Notes in Computer Science, pages 167-184. Springer, 2004. [ bib | http ] a different approach to SSA-based PRE. Uses value numbering to identify redundant computation, rather than a more syntactic measure. This approach has been implemented in Jikes RVM and GCC. [3] Alexandre Lenart, Christopher Sadler, and Sandeep K. S. Gupta. SSA-based flow-sensitive type analysis: combining constant and type propagation. In Proceedings of the ACM Symposium on Applied Computing, pages 813-817, 2000. [ bib | http ] combines WZ91 sparse conditional constant propagation with type propagation for concrete types in Java programs. A poorly written, short, rather dodgy paper, but still quite an interesting find [4] Alan Mycroft. Type-based decompilation. In Proceedings of the 8th European Symposium on Programming, volume 1576 of Lecture Notes in Computer Science, pages 208-223. Springer, 1999. [ bib | .html ] uses SSA to undo register colouring, then infers types and transforms RTL back into C. All thoughts, and no real implementations here... [5] Hideki Saito and Constantine D. Polychronopoulos. sigma-SSA and its construction through symbolic interpretation. In Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, pages 585-587. Springer-Verlag, 1997. [ bib | http ] a variant of SSA that purports to be useful for symbolic analysis and interpretation. Uses a data flow like Value Flow Graph for optimization. Lack of detail for construction algorithm [6] Ranjit Jhala, Rupak Majumdar, and Ru-Gang Xu. Structural invariants. In Proceedings of the Static Analysis Symposium, volume 4134, pages 71-87, 2006. [ bib | http ] SSA for model checking. Using the dominance properties of SSA enables efficient generation of verification conditions [7] Benoit Boissinot, Sebastian Hack, Daniel Grund, Benoît Dupont de Dinechin, and Fabrice Rastello. Fast liveness checking for SSA-form programs. In Proceedings of the Sixth Annual IEEE/ACM International Symposium on Code Generation and Optimization, pages 35-44, 2008. [ bib | http ] liveness analysis based directly on SSA, rather than specialized data flow analysis SSA-based compilers [1] Robert Fitzgerald, Todd B. Knoblock, Erik Ruf, Bjarne Steensgaard, and David Tarditi. Marmot: an optimizing compiler for Java. Software-Practice and Experience, 30(3):199-232, 2000. [ bib | http ] describes design and implementation of Marmot - uses SSA, buth as some criticism for how hard it is to do transformations efficiently in SSA. [2] Java HotSpot, 1999. [ bib | .html ] Just a website with a link to a white paper, no real detail here. However it does mention that the HotSpot server VM uses an SSA-based IR. [3] Thomas Kotzmann, Christian Wimmer, Hanspeter Mössenböck, Thomas Rodriguez, Kenneth Russell, and David Cox. Design of the Java HotSpot client compiler for java 6. ACM Transactions on Architure and Code Optimization, 5(1):1-32, 2008. [ bib | DOI ] [4] Diego Novillo. TreeSSA a new optimization infrastructure for GCC. In Proceedings of the 2003 GCC Developers' Summit, pages 181-193, 2003. [ bib | .pdf ] [5] B. Alpern, C. R. Attanasio, J. J. Barton, M. G. Burke, P .Cheng, J.-D. Choi, A. Cocchi, S. J. Fink, D. Grove, M. Hind, S. F. Hummel, D. Lieber, V. Litvinov, M. F. Mergen, T. Ngo, J. R. Russell, V. Sarkar, M. J. Serrano, J. C. Shepherd, S. E. Smith, V. C. Sreedhar, H. Srinivasan, and J. Whaley. The Jalapeño virtual machine. IBM Systems Journal, 39(1), Feb 2000. [ bib | .html ] SSI-based compilers [1] The Flex compiler infrastructure, 1998. [ bib | http ] SUIF [1] Robert P. Wilson, Robert S. French, Christopher S. Wilson, Saman P. Amarasinghe, Jennifer M. Anderson, Steve W. K. Tjiang, Shih-Wei Liao, Chau-Wen Tseng, Mary W. Hall, Monica S. Lam, and John L. Hennessy. SUIF: An infrastructure for research on parallelizing and optimizing compilers, 1994. [ bib | .html ] overview document (rather outdated!) for SUIF v1 [2] Michael D. Smith. Extending SUIF for machine-dependent optimizations. In Proceedings of the First SUIF Compiler Workshop, pages 14-25, Jan 1996. [ bib | .html ] general introduction to machine suif [3] Glenn Holloway. The Machine-SUIF static single assignment library, 2001. [ bib | .html ] SSA docs for Machine SUIF [4] Laurent Rolaz. An implementation of sparse conditional constant propagation for Machine SUIF, 2003. [ bib | .pdf ] Translating SSA into functional programs [1] Andrew W. Appel. SSA is functional programming. ACM SIGPLAN Notices, 33(4):17-20, Apr 1998. [ bib | http ] [2] Richard A. Kelsey. A correspondence between continuation passing style and static single assignment form. ACM SIGPLAN Notices, 30(3):13-22, Mar 1995. [ bib | http ] [3] Manuel M.T. Chatravarty, Gabriele Keller, and Patryk Zadarnowski. A functional perspective on SSA optimisation algorithms. In Proceedings of the 2nd International Workshop on Compiler Optimization Meets Compiler Verification, 2003. [ bib | .html ] Gated single assignment form [1] Robert A. Ballance, Arthur B. Maccabe, and Karl J. Ottenstein. The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages. In Proceedings of the ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation, pages 257-271, 1990. [ bib | http ] PDW - fascinating data flow stuff - but switch nodes are just like SSI sigma nodes. [2] Peng Tu and David Padua. Efficient building and placing of gating functions. In Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation, pages 47-55, 1995. [ bib | http ] reintroduces gated single assignment, shows how to compute gating fns quicker than previously [3] Paul Havlak. Construction of thinned gated single-assignment form. In Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, volume 768 of Lecture Notes in Computer Science, pages 477-499. Springer, 1993. [ bib | .html ] TGSA is a simplified version of GSA SSA and Type Checking [1] Wolfram Amme, Niall Dalton, Jeffery von Ronne, and Michael Franz. SafeTSA: a type safe and referentially secure mobile-code representation based on static single assignment form. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, pages 137-147, 2001. [ bib | http ] SafeTSA is a replacement for Java bytecode - a VM-based intermediate form that encodes implicit type-safety. (effectively diff stacks for diff types) [2] Wolfram Amme, Jeffery von Ronne, and Michael Franz. Quantifying the benefits of ssa-based mobile code. Electronic Notes in Theoretical Computer Science, 141(2):103-119, 2005. [ bib | http ] another SafeTSA paper, integrating SafeTSA into Jikes RVM via a custom classloader and comparing performance with Java bytecode on simple benchmarks [3] Wolfram Amme, Jeffery von Ronne, and Michael Franz. Ssa-based mobile code: Implementation and empirical evaluation. ACM Transactions on Architure and Code Optimization, 4(2):13, 2007. [ bib | DOI ] [4] Vijay S. Menon, Neal Glew, Brian R. Murphy, Andrew McCreight, Tatiana Shpeisman, Ali-Reza Adl-Tabatabai, and Leaf Petersen. A verifiable ssa program representation for aggressive compiler optimization. In Proceedings of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 397-408, 2006. [ bib | http ] introduces a low-level IR based on SSA that encodes type info for type-safe compiler optimizations [5] Yutaka Matsuno and Atsushi Ohori. A type system equivalent to static single assignment. In Proceedings of the 8th ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming, pages 249-260, 2006. [ bib | http ] introduces a type system that works like SSA. Effectively type inference is SSA transformation. So we can encode SSA as type-based info, rather than in variable renaming. SSA and code generation [1] A. V. S. Sastry and Roy D. C. Ju. A new algorithm for scalar register promotion based on SSA form. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, pages 15-25, 1998. [ bib | http ] handles register spilling and rematerialization. Deals with a new algorithm for repairing SSA. [2] E. Eckstein, O. König, and B. Scholz. Code instruction selection based on SSA-graphs. In Proceedings of the International Workshop on Software and Compilers for Embedded Systems, volume 2826 of Lecture Notes in Computer Science, pages 49-65. Springer, 2003. [ bib | http ] uses some kind of boolean optimization techniques (maths!) to generate near-optimal instruction sequences for DSP programs in SSA form. [3] Sebastian Hack, Daniel Grund, and Gerhard Goos. Register allocation for programs in SSA-form. In 15th International Conference on Compiler Construction, volume 3923 of Lecture Notes in Computer Science, pages 247-262. Springer, 2006. [ bib | http ] an interesting read. Do register allocation directly in SSA, rather than translate out of SSA. Some graph theory here. [4] Philip Brisk and Majid Sarrafzadeh. Interference graphs for procedures in static single information form are interval graphs. In Proceedings of the 10th international workshop on Software & compilers for embedded systems, pages 101-110, 2007. [ bib | http ] shows how liveness analysis is O(1) for SSI programs, interesting graph-theoretic properties of SSI-based register interference graphs [5] Adam Kaplan, Philip Brisk, and Ryan Kastner. Data communication estimation and reduction for reconfigurable systems. In Proceedings of the 40th conference on Design automation, pages 616-621, 2003. [ bib | http ] uses SSA for hardware synthesis, shows how tweaks in φ-function placement affects hardware efficiency [6] F. Rastello, F. de Ferrière, and C. Guillon. Optimizing translation out of SSA using renaming constraints. In Proceedings of the International Symposium on Code Generation and Optimization, pages 265-278, 2004. [ bib | http ] Extends work of leung99, for reducing number of moves after eliminating phi-functions when converting out of SSA. Variable pinning coalescing technique. [7] F.M.Q. Pereira and J. Palsberg. Register allocation after classical SSA elimination is NP-complete. In Proceedings of Foundations of Software Science and Computation Structures, volume 3921 of Lecture Notes in Computer Science, pages 79-93, Mar 2006. [ bib | .pdf ] Despite work of Hack, showing that SSA programs are colourable in linear time, register allocation is still NP-complete [8] F.M. Pereira and J. Palsberg. SSA elimination after register allocation. In Proceedings of the International Conference on Compiler Construction, volume 5501 of Lecture Notes in Computer Science, pages 158-173. Springer, 2009. [ bib | http ] destroy SSA after register allocation, without increasing the number of spill variables [9] Sebastian Hack and Gerhard Goos. Copy coalescing by graph recoloring. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 227-237, 2008. [ bib | http ] A new coalescing algorithm for reg coloring after SSA-based register allocation [10] Fernando Magno Quintão Pereira and Jens Palsberg. Register allocation by puzzle solving. In Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 216-226, 2008. [ bib | http ] fun paper on register allocation for architectures like x86 with overlapping registers of different sizes. Does ultimate live range splitting, adds pseudo-assignments for live variables between every individual instruction. This is known as the elementary form. [11] Matthias Braun and Sebastian Hack. Register spilling and live-range splitting for ssa-form programs. In Proceedings of the International Conference on Compiler Construction, pages 174-189, 2009. [ bib | .pdf ] SSA-based register allocator reduces dynamic number of spill instructions in benchmark code, in relation to linear scan and graph coloring allocators [12] Benoit Boissinot, Alain Darte, Fabrice Rastello, Benoit Dupont de Dinechin, and Christophe Guillon. Revisiting out-of-SSA translation for correctness, code quality and efficiency. In Proceedings of the 2009 International Symposium on Code Generation and Optimization, pages 114-125, 2009. [ bib | http ] new algorithm for translating out of SSA, efficient enough to be implemented in JIT compilers [13] Vugranam C. Sreedhar, Roy Dz-Ching Ju, David M. Gillies, and Vatsa Santhanam. Translating out of static single assignment form. In Proceedings of the Static Analysis Symposium, volume 1694 of Lecture Notes in Computer Science, pages 194-210, 1999. [ bib | http ] another out-of-SSA algorithm, replacing phi-functions with copies where appropriate. Copies are eliminated with coalescing. [14] Masataka Sassa, Yo Ito, and Masaki Kohama. Comparison and evaluation of back-translation algorithms for static single assignment forms. Computer Languages, Systems & Structures, 35(2):173-195, 2009. [ bib | http ] Comparison of several classical out-of-SSA algorithms, Briggs, etc. SSA for Java programs [1] Andreas Gal, Christian W. Probst, and Michael Franz. Structural encoding of static single assignment form. Electronic Notes in Theoretical Computer Science, 141(2):85-102, 2005. [ bib | http ] interesting approach to embedding SSA info directly in standard Java bytecode, using local variables as SSA registers, neat encoding of phi functions and dominator tree. This file has been generated automatically with some help from bibtex2html 1.78
