PRECISE CONCRETE TYPE INFERENCE FOR OBJECT-ORIENTED LANGUAGES

Concrete type information is invaluable for program optimization. The determination of concrete types in object-oriented languages is a flow sensitive global data flow problem. It is made difficult by dynamic d ispatch (virtual function invocation) and first class functions (and s electors) - the very program structures for whose optimization its res ults are most critical. Previous work has shown that constraint-based type inference systems can be used to safely approximate concrete type s [15], but their use can be expensive and their results imprecise. We present an incremental constraint-based type inference which produces precise concrete type information for a much larger class of programs at lower cost. Our algorithm extends the analysis in response to disc overed imprecisions, guiding the analysis' effort to where it is most productive. This produces precise information at a cost proportional t o the type complexity of the program. Many programs untypable by previ ous approaches or practically untypable due to computational expense, can be precisely analyzed by our new algorithm. Performance results, p recision, and running time, are reported for a number of concurrent ob ject-oriented programs. These results confirm the algorithm's precisio n and efficiency.