Type-based alias analysis

This paper evaluates three alias analyses based on program-ming language types. The first analysis uses type compati-bility 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 analy-sis. Although other researchers suggests using types to dis-ambiguate memory references, none evaluates its effective-ness. 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 com-patibility 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 ef-fectiveness of the three alias algorithms in terms of the oppor-tunities 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 improve-ments 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 il-lustrate that to explore thoroughly the effectiveness of alias analyses, researchers need static, dynamic, and upper-bound analysis. In addition, we show that for type-safe languages like Modula-3 and Java, a fast and simple alias analysis may be sufficient for many applications.