We describe a novel approach to performing data dependence analysis for Java in the presence of Java’s “non-traditional” language
features such as exceptions, synchronization, and memory consistency. We introduce new classes of edges in a dependence graph
to model code motion constraints arising from these language features. We present a linear-time algorithm for constructing
this augmented dependence graph for an extended basic block.
On sabbatical from the Dept. of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WA 98195-2350,
USA; chambers@cs.washington.edu.