Partial redundancy elimination for access path expressions

Pointer traversals pose significant overhead to the execution of object-ori ented programs, since every access to an object's state requires a pointer dereference. Eliminating redundant pointer traversals reduces both instruct ions executed as well as redundant memory accesses to relieve pressure on t he memory subsystem. We describe an approach to elimination of redundant ac cess expressions that combines partial redundancy elimination (PRE) with ty pe-based alias analysis (TBAA), To explore the potential of this approach w e have implemented an optimization framework for Java class files incorpora ting TBAA-based PRE over pointer access expressions. The framework is imple mented as a class-file-to-class-file transformer; optimized classes can the n be run in any standard Java execution environment. Our experiments demons trate improvements in the execution of optimized code for several Java benc hmarks running in diverse execution environments: the standard interpreted JDK virtual machine, a virtual machine using 'just-in-time' compilation, an d native binaries compiled off-line ('way-ahead-of-time'). Overall, however , our experience is of mixed success with the optimizations, mainly because of the isolation between our optimizer and the underlying execution enviro nments which prevents more effective cooperation between them. We isolate t he impact of access path PRE using TBAA, and demonstrate that Java's requir ement of precise exceptions can noticeably impact code-motion optimizations like PRE, Copyright (C) 2001 John Wiley & Sons, Ltd.