Type analysis is the key for improving the efficiency of untyped object-oriented programs with dynamic method binding by replacing costly "late" by the more efficient "early" binding. The precision of type analysis and hence the runtime gain achievable depends above all on the treatment of method calls, program branches, and assignments. A monomorphic, monovariant, and non-destructive treatment of assignments are major sources introducing imprecision. In this article we present a new type analysis based on abstract interpretation, which systematically addresses and overcomes these problems. The new type analysis is unique for treating method calls polymorphically and polyvariantly, program branches and method sends almost deterministically, and assignments destructively. Above all, it is the almost deterministic treatment of program branches and method sends which makes our approach exceptional, and lets it improve on all previous related approches to type analysis.
Keywords
(Untyped) object-oriented languages, type analysis, abstract interpretation, data flow analysis, MOP-Solution, MFP-Solution, (Object-Oriented) Coincidence Theorem, Smaltalk, (classical) program optimization.
Ulrike Peiker, Martin Griebl