Donald Bren School of Information and Computer Sciences

Modem and likely future architectures require compilers to perform extensive restructuring of programs during optimization. We have been building a system in which JVM bytecode is compiled off-line into an alternative, enhanced mobile-code format. This alternative format is still fully target-machine independent but can be more easily verified and compiled into native code. In particular, our approach permits shifting of analyses and optimizations to the code producer that, because of the necessity to perform bytecode verification, could only occur on the code consumer if JVM byte-code were used. Our approach naturally encompasses irreducible control flow, which can result from the use of bytecode optimizers, obfuscators and compilers for source languages other than Java. Our techniques are applicable beyond JVM bytecode.

Although some optimizations can be moved to the code producer, we believe that it will still be unavoidable to perform some restructuring optimizations on the target machine. For example, loop transformations, code scheduling, and parallelization are vital to achieve high performance on EPIC and multithreaded architectures.

In this paper, we introduce the Augmented Dominator Tree (ADT) as a candidate mobile code format enabling efficient program analysis. The ADT may be quickly validated on the target machine; we give an O(E + V) algorithm for this. However, our algorithm not only verifies the validity of the data structure, but also reconstructs the control flow graph, and computes the dominance frontier. Furthermore, we show how to quickly compute the post-dominator tree, using a more efficient variant of Cooper, Harvey, and Kennedy's iterative dominator algorithm. We intend the ADT to form the basis of simple and efficient algorithms for performing sophisticated program analysis in a just-in-time compiler for high-performance architectures.