TYPE-BASED ALIAS ANALYSIS

This paper evaluates three alias analyses based on programming languag e types. The first analysis uses type compatibility to determine alias es. The second extends the first by using additional high-level inform ation such as held names. The third extends the second with a flow-ins ensitive analysis. Although other researchers suggests using types to disambiguate memory references, none evaluates its effectiveness. We p erform both static and dynamic evaluations of type-based alias analyse s for Modula-3, a statically-typed type-safe language. The static anal ysis reveals that type compatibility alone yields a very imprecise ali as analysis, but the other two analyses significantly improve alias pr ecision. We use redundant load elimination (RLE) to demonstrate the ef fectiveness of the three alias algorithms in terms of the opportunitie s for optimization, the impact on simulated execution times, and to co mpute an upper bound on what a perfect alias analysis would yield. We show modest dynamic improvements for (RLE), and more surprisingly, tha t on average our alias analysis is within 2.5% of a perfect alias anal ysis with respect to RLE on 8 Modula-3 programs. These results illustr ate that to explore thoroughly the effectiveness of alias analyses, re searchers need static, dynamic, and upper-bound analysis. In addition, we show that for type-safe languages like Modula-3 and Java, a fast a nd simple alias analysis may be sufficient for many applications.