SSA-based mobile code: Implementation and empirical evaluation

ABSTRACT

Although one might expect transportation formats based on static single-assignment form (SSA) to yield faster just-in-time compilation times than those based on stack-based virtual machines, this claim has not previously been validated, in practice. We attempt to quantify the effect of using an SSA-based mobile code representation by integrating support for a verifiable SSA-based IR into Jikes RVM. Performance results, measured with various optimizations and on both the IA32 and PowerPC, show improvements in both compilation time and code quality.

REFERENCES

• 1: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• 2: 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 , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 3: Amme, W. 2004. Effiziente und sichere Codegenerierung für mobilen Code. Habilitation, Friedrich-Schiller-University, Jena, Germany.
• 4: Wolfram Amme , Niall Dalton , Jeffery von Ronne , Michael Franz, SafeTSA: a type safe and referentially secure mobile-code representation based on static single assignment form, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.137-147, June 2001, Snowbird, Utah, United States
• 5: Amme, W., Dalton, N., Fröhlich, P., Haldar, V., Housel, P. S., von Ronne, J., Stork, C. H., Zhenochin, S., and Franz, M. 2001b. Project transprose: Reconciling mobile-code security with execution efficiency. In Proceedings of the Second DARPA Information Survivability Conference and Exposition. IEEE Computer Society, Los Alamitos, California. 196--210.
• 6: Amme, W., von Ronne, J., and Franz, M. 2005. Quantifying the benefits of ssa-based mobile code. In Proceedings of the 4th International Workshop on Compiler Optimization Meets Compiler Verification (COCV 2005), April 2005. Electronic Notes in Theoretical Computer Science Series (ENTCS), vol. 141. Elsevier Science, Amsterdam. 103--119.
• 7: Andrew W. Appel, SSA is functional programming, ACM SIGPLAN Notices, v.33 n.4, p.17-20, April 1998 [doi>10.1145/278283.278285]
• 8: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 9: Matthew Arnold , Stephen Fink , Vivek Sarkar , Peter F. Sweeney, A comparative study of static and profile-based heuristics for inlining, Proceedings of the ACM SIGPLAN workshop on Dynamic and adaptive compilation and optimization, p.52-64, January 2000
• 10: Belady, L. A. 1960. A study of replacement algorithms for virtual storage computers. IBM Journal of Research and Development 5, 2, 78--101.
• 11: Val Breazu-Tannen , Thierry Coquand , Carl A. Gunter , Andre Scedrov, Inheritance as implicit coercion, Information and Computation, v.93 n.1, p.172-221, July 1991 [doi>10.1016/0890-5401(91)90055-7]
• 12: Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994 [doi>10.1145/177492.177575]
• 13: Bull, J. M., Smith, L. A., Westhead, M. D., Henty, D. S., and Davey, R. A. 2000. A benchmark suite for high performance Java. Concurrency: Practice and Experience 12, 6 (May), 375--388.
• 14: Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304113]
• 15: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 16: Chaitin, G. J., Auslander, M. A., Chandra, A. K., Cocke, J., Hopkins, M. E., and Markstein, P. W. 1981. Register allocation via coloring. Computer Languages 6, 1, 47--57.
• 17: Cliff Click, Global code motion/global value numbering, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.246-257, June 18-21, 1995, La Jolla, California, United States
• 18: Cooper, K. and Torczon, L. 2003. Engineering a Compiler. Morgan Kaufman, San Francisco, CA.
• 19: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 20: de Bruijn, N. G. 1978. Lambda calculus with namefree formulas involving symbols that represent reference transforming mappings. Indagationes Mathematicae (Proceedings) 81, 3, 348--356.
• 21: ECMA. 2002. Common Language Infrastructure (CLI), Standard ECMA-335.
• 22: Stephen J. Fink , Kathleen Knobe , Vivek Sarkar, Unified Analysis of Array and Object References in Strongly Typed Languages, Proceedings of the 7th International Symposium on Static Analysis, p.155-174, June 29-July 01, 2000
• 23: Michael Franz , Thomas Kistler, Slim binaries, Communications of the ACM, v.40 n.12, p.87-94, Dec. 1997 [doi>10.1145/265563.265576]
• 24: Christopher W. Fraser , David R. Hanson, Simple register spilling in a retargetable compiler, Software—Practice & Experience, v.22 n.1, p.85-99, Jan. 1992 [doi>10.1002/spe.4380220105]
• 25: Rajiv Gupta , Rastislav Bodík, Register Pressure Sensitive Redundancy Elimination, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.107-121, March 22-28, 1999
• 26: M. S. Hecht , J. D. Ullman, Characterizations of Reducible Flow Graphs, Journal of the ACM (JACM), v.21 n.3, p.367-375, July 1974 [doi>10.1145/321832.321835]
• 27: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 28: Thomas Kistler , Michael Franz, A Tree-Based Alternative to Java Byte-Codes, International Journal of Parallel Programming, v.27 n.1, p.21-33, Feb. 1999 [doi>10.1023/A:1018740018601]
• 29: Kathleen Knobe , Vivek Sarkar, Array SSA form and its use in parallelization, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.107-120, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268956]
• 30: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 31: League, C., Trifonov, V., and Shao, Z. 2001. Functional Java bytecode. In Proceedings of the World Multiconference on Systemics, Cybernetics, and Informatics. International Institute of Informatics and Systemics, Orlando, FL.
• 32: Vijay S. Menon , Neal Glew , Brian R. Murphy , Andrew McCreight , Tatiana Shpeisman , Ali-Reza Adl-Tabatabai , Leaf Petersen, A verifiable SSA program representation for aggressive compiler optimization, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.397-408, January 11-13, 2006, Charleston, South Carolina, USA
• 33: Rajeev Motwani , Krishna V. Palem , Vivek Sarkar , Salem Reyen, Combining Register Allocation and Instruction Scheduling, Stanford University, Stanford, CA, 1995
• 34: Massimiliano Poletto , Vivek Sarkar, Linear scan register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.895-913, Sept. 1999 [doi>10.1145/330249.330250]
• 35: Christian H. Stork , Michael Franz, Well: a language-agnostic foundation for compact and inherently safe mobile code, California State University at Long Beach, Long Beach, CA, 2006
• 36: Stork, C. H., Haldar, V., and Franz, M. 2000. Generic adaptive syntax-directed compression for mobile code. Technical Report 00-42 (Nov.). Information and Computer Science, Univeristy of California, Irvine, CA.
• 37: Jeffery Von Ronne , Michael Franz, A safe and efficient machine-independent code transportation format based on static single assignment form and applied to just-in-time compilation, University of California at Irvine, Irvine, CA, 2005
• 38: von Ronne, J., Amme, W., and Franz, M. 2006. An inherently type-safe ssa-based code format. Tech. Rep. CS-TR-2006-004, Computer Science, The University of Texas at San Antonio, San Antonio.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments; Optimization; Compilers

General Terms:
Experimentation, Languages, Measurement, Performance

Keywords:
SafeTSA, Virtual machines, static single-assignment form