Incremental Inference of Concrete Types

Concrete type information is invaluable for program optimization. The determination of concrete types is, in general, a flow sensitive global data flow problem. As a result, its solution is hampered by the very program structures for whose optimization its results are most critical: dynamic dispatch (as in object-oriented programs) and first class functions (including function pointers). Constraint based type inference systems are an effective way of safely approximating concrete types, but their use can be expensive and their results imprecise. We present an incremental constraint based type inference technique for extending the analysis in response to discovered imprecisions. This technique infers concrete types to high precision with a cost proportional to the information obtained. Performance results, precision and running time, are reported for a number of concurrent object-oriented programs. 1 Introduction Strongly typed languages with type declarations and/or type inference sys..