More Web Proxy on the site http://driver.im/

article

Open access

SSA-based mobile code: Implementation and empirical evaluation

Authors:

Jeffery von Ronne,

Michael FranzAuthors Info & Claims

ACM Transactions on Architecture and Code Optimization (TACO), Volume 4, Issue 2

Pages 13 - es

https://doi.org/10.1145/1250727.1250733

Published: 01 June 2007 Publication History

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]

Alpern, B., Wegman, M. N., and Zadeck, F. K. 1988. Detecting equality of variables in programs. In POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, New York. 1--11.

Digital Library

[2]

Alpern, B., Attanasio, D., Barton, J. J., Burke, M. G., Cheng, P., Choi, J.-D., Cocchi, C., Fink, S. J., Grove, D., Hind, H., Hummel, S. F., Lieber, D., Litvinov, L., Mergen, M., Ngo, T., Russell, J. R., Sarkar, V., Serrano, M. J., Shepherd, S., Smith, S., Sreedhar, V. C., Srinivasan, S., and Whaley, J. 2000. The Jalapeño virtual machine. IBM Systems Journal 39, 1 (Feb.), 211--238.

Digital Library

[3]

Amme, W. 2004. Effiziente und sichere Codegenerierung für mobilen Code. Habilitation, Friedrich-Schiller-University, Jena, Germany.

[4]

Amme, W., Dalton, N., Franz, M., and von Ronne, J. 2001a. SafeTSA: A type safe and referentially secure mobile-code representation based on static single assignment form. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI'2001a). ACM SIGPLAN Notices, vol. 36. ACM Press, New York. 137--147.

Digital Library

[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]

Appel, A. W. 1998. Ssa is functional programming. SIGPLAN Not. 33, 4, 17--20.

Digital Library

[8]

Arnold, M., Fink, S., Grove, D., Hind, M., and Sweeney, P. F. 2000a. Adaptive optimization in the Jalapeño JVM. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages and Application (OOPSLA'2000). ACM SIGPLAN Notices, vol. 35. ACM Press, New York. 47--65.

Digital Library

[9]

Arnold, M., Fink, S., Sarkar, V., and Sweeney, P. F. 2000b. A comparative study of static and profile-based heuristics for inlining. In DYNAMO '00: Proceedings of the ACM SIGPLAN workshop on Dynamic and adaptive compilation and optimization. ACM Press, New York. 52--64.

Digital Library

[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]

Breazu-Tannen, V., Coquand, T., Gunter, C. A., and Scedrov, A. 1991. Inheritance as implicit coercion. Information and Computation 93, 1 (July), 172--221.

Digital Library

[12]

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

Digital Library

[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]

Burke, M., Choi, J.-D., Fink, S., Grove, D., Hind, M., Sarkar, V., Serrano, M., Sreedhar, V. C., and Srinivasan, H. 1999. The jalapeño dynamic optimizing compiler for java. In ACM Java Grande Conference. ACM Press, New York. 129--141.

Digital Library

[15]

Chaitin, G. J. 1982. Register allocation and spilling via graph coloring. In Proceedings of the Symposium on Compiler Construction (CC'1982). ACM Press, New York. 98--105.

Digital Library

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

Digital Library

[17]

Click, C. 1995. Global code motion/global value numbering. In PLDI '95: Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation. ACM Press, New York. 246--257.

Digital Library

[18]

Cooper, K. and Torczon, L. 2003. Engineering a Compiler. Morgan Kaufman, San Francisco, CA.

Digital Library

[19]

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

Digital Library

[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]

Fink, S. J., Knobe, K., and Sarkar, V. 2000. Unified analysis of array and object references in strongly typed languages. In Static Analysis, 7th International Symposium, SAS 2000, Santa Barbara, CA, June 29--July 1, 2000, Proceedings, J. Palsberg, Ed. Lecture Notes in Computer Science, vol. 1824. Springer, Heidelberg. 155--174.

Digital Library

[23]

Franz, M. and Kistler, T. 1997. Slim Binaries. Communications of the ACM 40, 12 (Dec.), 87--94.

Digital Library

[24]

Fraser, C. W. and Hanson, D. R. 1992. Simple register spilling in a retargetable compiler. Software---Practice and Experience 22, 1 (Jan.), 85--99.

Digital Library

[25]

Gupta, R. and Bodik, R. 1999. Register pressure sensitive redundancy elimination. Lecture Notes in Computer Science 1575, 107--121.

Digital Library

[26]

Hecht, M. S. and Ullman, J. D. 1974. Characteristics of reducible flow graphs. Journal of the ACM 21, 3 (July), 367--375.

Digital Library

[27]

Joy, B., Steele, G., Gosling, J., and Bracha, G. 2000. Java Language Specification, 2nd ed. Addison-Wesley, Boston, MA.

Digital Library

[28]

Kistler, T. and Franz, M. 1999. A Tree-Based alternative to Java byte-codes. International Journal of Parallel Programming 27, 1 (Feb.), 21--34.

Digital Library

[29]

Knobe, K. and Sarkar, V. 1998. Array ssa form and its use in parallelization. In POPL '98: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM Press, New York. 107--120.

Digital Library

[30]

Lattner, C. and Adve, V. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO'04). IEEE Computer Society, Palo Alto, CA.

Digital Library

[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]

Menon, V. S., Glew, N., Murphy, B. R., McCreight, A., Shpeisman, T., Adl-Tabatabai, A.-R., and Petersen, L. 2006. A verifiable ssa program representation for aggressive compiler optimization. In POPL '06: Conference Record of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, New York. 397--408.

Digital Library

[33]

Motwani, R., Palem, K. V., Sarkar, V., and Reyen, S. 1995. Combining register allocation and instruction scheduling. Technical Note CS-TN-95-22 (Aug.). Stanford University, Department of Computer Science. Stanford CA.

Digital Library

[34]

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

Digital Library

[35]

Stork, C. H. 2006. WELL: A language-agnostic foundation for compact and inherently safe mobile code. Ph.D. thesis, University of California, Irvine, CA.

Digital Library

[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]

von Ronne, J. 2005. A safe and efficient machine-independent code transportation format based on static signle assignment form and applied to just-in-time compilation. Ph.D. thesis, University of California, Irvine.

Digital Library

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

Cited By

Gampe Avon Ronne JNiedzielski DVasek JPsarris K(2010)Safe, multiphase bounds check elimination in JavaSoftware: Practice and Experience10.1002/spe.102841:7(753-788)Online publication date: 25-Nov-2010
https://doi.org/10.1002/spe.1028
Adler PAmme W(2009)Type-Separated Bytecode --- Its Construction and EvaluationRuntime Verification10.1007/978-3-642-04694-0_3(26-39)Online publication date: 30-Sep-2009
https://dl.acm.org/doi/10.1007/978-3-642-04694-0_3
Niedzielski DRonne JGampe APsarris K(2009)A Verifiable, Control Flow Aware Constraint Analyzer for Bounds Check EliminationProceedings of the 16th International Symposium on Static Analysis10.1007/978-3-642-03237-0_11(137-153)Online publication date: 12-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-03237-0_11
Show More Cited By

Index Terms

SSA-based mobile code: Implementation and empirical evaluation
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments
      2. Source code generation

Recommendations

Quantifying the Benefits of SSA-Based Mobile Code

High-performance just-in-time compilers for Java need to invest considerable effort before actual code generation can commence. This is in part due to the very nature of the Java Virtual Machine, which is not well matched to the requirements of ...
The effectiveness of producer-side machine-independent optimizations for mobile code

Portable mobile code is often executed by a host virtual machine using just-in-time compilation. In this context, the compilation time in the host virtual machine is critical. This compilation time can be reduced if optimizations are performed ahead-of-...
Analyzing the performance of code-copying virtual machines
OOPSLA '08: Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications

Many popular programming languages use interpreter-based execution for portability, supporting dynamic or reflective properties, and ease of implementation. Code-copying is an optimization technique for interpreters that reduces the performance gap ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Architecture and Code Optimization

ACM Transactions on Architecture and Code Optimization Volume 4, Issue 2

June 2007

193 pages

ISSN:1544-3566

EISSN:1544-3973

DOI:10.1145/1250727

Issue’s Table of Contents

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2007

Published in TACO Volume 4, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
794
Total Downloads

Downloads (Last 12 months)102
Downloads (Last 6 weeks)18

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gampe Avon Ronne JNiedzielski DVasek JPsarris K(2010)Safe, multiphase bounds check elimination in JavaSoftware: Practice and Experience10.1002/spe.102841:7(753-788)Online publication date: 25-Nov-2010
https://doi.org/10.1002/spe.1028
Adler PAmme W(2009)Type-Separated Bytecode --- Its Construction and EvaluationRuntime Verification10.1007/978-3-642-04694-0_3(26-39)Online publication date: 30-Sep-2009
https://dl.acm.org/doi/10.1007/978-3-642-04694-0_3
Niedzielski DRonne JGampe APsarris K(2009)A Verifiable, Control Flow Aware Constraint Analyzer for Bounds Check EliminationProceedings of the 16th International Symposium on Static Analysis10.1007/978-3-642-03237-0_11(137-153)Online publication date: 12-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-03237-0_11
Amme Wvon Ronne JAdler PFranz M(2009)The effectiveness of producer‐side machine‐independent optimizations for mobile codeSoftware: Practice and Experience10.1002/spe.92139:10(923-946)Online publication date: 15-Apr-2009
https://doi.org/10.1002/spe.921

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents