In this work, we are investigating improving the performance of statically-typed object-oriented languages, such as Modula-3, and Java. These languages offer substantial software engineering benefits, but features like method invocations and pointer dereferencing often significantly degrade performance. To cut these costs, we investigate method invocation resolution and using alias analysis to disambiguate pointer references. We use limit analyses in each case which demonstrate that although our approaches are simple, they are very close to perfect for our program test suite.
Method Invocation Resolution. Frequent method invocations in object-oriented languages obscure control flow, and thus limit opportunities for optimization. We have investigated and evaluated a range of analysis techniques to convert method invocations into direct calls for statically-typed object-oriented languages, removing the overhead of method invocations and improving control-flow information for object-oriented languages. We present simple algorithms for type hierarchy analysis, aggregate analysis, and interprocedural and intraprocedural type propagation. These algorithms are fast, and thus practical for use in a compiler. When they fail, we use a new cause analysis to reveal the source of imprecision and suggest where more powerful algorithms may be warranted. We show that our simple analyses perform almost as well as an oracle that resolves all method invocations that invoke only a single procedure [DMM:96].
Alias Analysis. We investigate three alias analyses based on programming language types. The first analysis uses type compatibility to determine aliases. The second extends the first by using additional high-level information such as field names. The third extends the second with a flow-insensitive analysis. Although other researchers suggests using types to disambiguate memory references, none evaluates its effectiveness. We perform both static and dynamic evaluations of type-based alias analyses for Modula-3, a statically-typed type-safe language. The static analysis reveals that type compatibility alone yields a very imprecise alias analysis, but the other two analyses significantly improve alias precision. We use redundant load elimination (RLE) to demonstrate the effectiveness of the three alias algorithms in terms of the opportunities for optimization, the impact on simulated execution times, and to compute an upper bound on what a perfect alias analysis would yield. We show modest dynamic improvements for RLE, and more surprisingly, that on average our alias analysis is within 2.5% of a perfect alias analysis with respect to RLE on 8 Modula-3 programs. These results illustrate that to explore thoroughly the effectiveness of alias analyses, researchers need static, dynamic, and upper-bound analysis. In addition, our results suggest that for type-safe languages like Modula-3 and Java, a fast and simple alias analysis may be sufficient for many applications [DMM:98].