Control Flow Graphs for Java Bytecode


Neal Glew, Cornell University

About Myself

I was born in New Zealand and earned a BSc in Mathematics and Computer Science in 1992 and a BSc(Hons) first class in Computer Science in 1993, both from Victoria University of Wellington. In 1994 I travelled to the US for the first time and began my PhD program in computer science at Cornell University. My Cornell advisor is Dexter Kozen whose interests are mainly in theory: algorithms, decidability & complexity of various logics. I also work with Greg Morrisett whose interests are in language theory and implementation. I work on low level type systems. The goal is to produce a language that is close to the machine but probably machine independent yet strongly statically typed with a type safety theorem. This language would be used as the target for translation of a number of high level source languages. This is motivated by the desire to build type-directed compilers and to build secure code download systems. I choose SRC for an internship because of its strength and research interests as well as its West Coast location.

SRC Research

The original project was to look at register allocation in Sanjay's Ghamawat's Java JIT. Unfortunately there wasn't enough infrastructure in place to dive into this project so we started to build one and found it to be interesting in itself. I ended up looking at control flow graphs for Java bytecodes and their uses. This forms a part of improving the overall quality of code generated by jrun. The main problems were how to deal with exceptions and subroutines. We also looked at how to get larger blocks over which a local allocator can work and devised the idea of a superblock. We looked at register allocation and had some ideas. However, time constraints prevented us from exploring further. We did however implement a simple change, that of not saving dead variables at basic block boundaries. The final problem we looked at was how to encode the CFG as a hint in a Java classfile so that a JIT can quickly build and verify the CFG. We managed to devise a scheme that is quick but which is not verifiable and understand some of this tradeoff.

Specifics

I implemented or helped with: A procedure to compute control flow graphs; a procedure to compute superblocks; a procedure to compute live variables; a new code generation infrastructure to support new register allocation schemes; a simple improvement to the present allocator; an experiment with another register allocation idea; and a procedure to compute the sizes of a CFG hint in java class files. This was implemented in C as part of Sanjay's jruntime. I also used DCPI to successfully investigate some performance problems.

Other

I found my project fun and challenging, in particular thinking about how to do register allocation, and the difficulties in making CFGs.

I learnt a lot about Digital, about SRC, and about industrial research labs. I also learnt alot about the research done at SRC in the past through reading many of the SRC research reports. My project taught me a lot about how to measure performance and think about how to improve code quality and measure such improvements.