CSE 501 -- Implementation of Programming Languages -- Winter 2001
TERM PROJECT

Compiler Construction Within the SOOT Framework: Internal Representation and Optimizations

AUTHORS: Daniel Grossman, Bart Niswonger, and Dmitriy Portnov

 Abstract

Towards implementing several common compiler optimizations for our CSE 501 project, we make use of the SOOT Java bytecode optimization framework, constructed at McGill University (Montreal) [7]. SOOT provides a robust framework and a feature-rich API with which the user may modularly define and aggregate any number of analytical and transformational components in the process of building a complete optimizing compiler. Starting from SOOT's internal three-address representation, JIMPLE, we have defined a new intermediate representation for Java bytecode and the methods for translating to and from this IR.

In completing our term project we have constructed a generic dataflow analysis framework and we are able to accept a variety of input programs, convert them to graph forms appropriate to our DFA framework, conduct a number of standard intra- and interprocedural analyses and transformations, and output optimized JIMPLE code.

Keywords:
Java Bytecode, Optimizing Compiler, Internal Representation, Control Flow Graph, Data Flow Graph, Static Single Assignment, Def-Use, Lattice-Theoretic Analysis, DFA Framework.

Please download our paper here:    JavaCompiler.ps

NB: The paper contains a reference to Appendix A, which is not included in the above PostScript document. The following two documents constitute that Appendix: ClassHierarchies.java, ClassHierarchies.jimple.

References

  1. Andrew W. Appel. Modern Compiler Implementation. Cambridge University Press, Cambridge, UK, 1998.
  2. Cliff Click. "Global Code Motion -- Global Value Numbering." In Conference on Programming Languages Design and Implementation, June 1995.
  3. Ron Cytron, Jeanna 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, October 1991.
  4. Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. "The Program Dependence Graph and Its Use in Optimization." TOPLAS, 9(3):319--349, July 1987.
  5. Bjarne Steensgaard. "Points-To Analysis in Almost Linear Time." In Symposium on Principles of Programming Languages, 1996.
  6. Raja Vallée-Rai. SOOT API JavaDocumentation. http://www.sable.mcgill.ca/soot/doc/index.html.
  7. Raja Vallée-Rai. "SOOT: A Java Bytecode Optimization Framework." Master's thesis, McGill University, Montreal, 2000.
  8. Daniel Weise, Roger F. Crew, Michael Ernst, and Bjarne Steensgaard. "Value Dependence Graphs: Representation Without Taxation." Technical Report MSR-TR-94-03, Microsoft Research, April 1994. Revision of paper that appeared in POPL '94.
This page last updated: Saturday, March 10, 2001.
E-mail the authors: Daniel Grossman, Bart Niswonger, Dmitriy Portnov