DOC PREVIEW
CORNELL CS 612 - Precise Concrete Type Inference for Object-Oriented Languages

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Precise Concrete Type Inference for Object-Oriented Languages John Plevyak Andrew A. Chien Department of Computer Science 1304 W. Springfield Avenue Urbana, IL 61801 {jplevyak, a&en} @cs.uiuc. edu Abstract Concrete type information is invaluable for pro- gram optimization. The determination of concrete types in object-oriented languages is a flow sensi- tive global data flow problem. It is made difficult by dynamic dispatch (virtual function invocation) and first class functions (and selectors) - the very program structures for whose optimization its re- sults are most critical. Previous work has shown that constraint-based type inference systems can be used to safely approximate concrete types [15], but their use can be expensive and their results imprecise. We present an incremental constraint-based type inference which produces precise concrete type in- formation for a much larger class of programs at lower cost. Our algorithm extends the analysis in response to discovered imprecisions, guiding the analysis’ effort to where it is most productive. This produces precise information at a cost proportional to the type complexity of the program. Many pro- grams untypable by previous approaches or prac- tically untypable due to computational expense, can be precisely analyzed by our new algorithm. Performance results, precision, and running time, are reported for a number of concurrent object- oriented programs. These results confirm the algo- rithm’s precision and efficiency. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association of Computing Machinery. To copy otherwise, or to republish, requires a fee and/or soecific permission. OOPSLA 94- iO/94 Portland, Oregon USA 0 1994 ACM O-89791 -688-3/94/0010..$3.50 1 Introduction Type information is of central importance for en- abling efficient implementations of high-level lan- guages. It can be derived from explicit program- mer declarations or via type inference, analysis of program structure. It can be used to assist pro- grammers to detect errors, reason about program operation, and in some cases, to optimize the im- plementation. However, traditional type inference systems infer principal or most general types, en- suring that the program is a legal composition of data types and their operations. While a great deal of progress has been made with respect to the in- ference of this type information [13, 14, 41, more precise information is required for optimization of object-oriented languages. For example, the’most general type of a max function would take any two comparable objects and produce a comparable ob- ject result. Thus, a principal typing would ensure that the argument types matched each other and the return type. However, this level of information is inadequate for optimization since optimizing the maz operation for integers (32 bits), complex num- bers (64 bits), bignums (many bits), though they are all numbers, requires different transformations. Concrete types distinguish implementations of data types and discriminate the actual classes or physical data layouts which occur in a program. Thus concrete type inference can provide the lower level and more specific information which is essen- tial for program optimization. For example, in the case of max, concrete type information would dis- 324tinguish calls on the basis of the implementation types of the arguments, allowing each to be op- timized appropriately. Concrete type information enables optimizations which traditional type infor- mation cannot. While object-oriented languages can ease the task of programming, they make optimization more difficult. Increased use of polymorphism both in modern languages and programming practice de- crease the likelihood that type declarations com- bined with principal types will provide useful con- crete type information. This is primarily be- cause polymorphism leverages programming effort by sharing code over a number of uses, confounding concrete type information. Concrete type inference in object-oriented lan- guages is both especially critical for efficiency and especially difficult to obtain. Object-oriented lan- guages use type-dependent dispatch pervasively, so concrete type information is essential to deriving accurate control flow - a prerequisite to virtually all program analysis and optimization. However, the presence of type-dependent dispatch means that the control flow, type inference, and data flow prob- lems are coupled. Previous work [15] formulated the concrete type inference problem as a mono- tonic solution of a constraint network, solving all three problems simultaneously. However, it has drawbacks: 1) it does not type many common pro- gram structures, and 2) its logical extension to such structures has space and time complexity exponen- tial in program type structure. Our concrete type inference algorithm extends precision incrementally where needed, consequen- tially producing more precise type information while requiring less computation. Our algorithm exploits a shallow analysis of the type information to guide the extension of effort into program re- gions where imprecise results were obtained. The extension discriminates the control and data flow paths that caused imprecisions and reanalyzes the program. The process iterates until precise type information is obtained. The key to making the analysis efficient is the use of entry sets and con- tainer sets which collect similar flow histories to- gether, reducing the cost of flow-sensitive analy-


View Full Document

CORNELL CS 612 - Precise Concrete Type Inference for Object-Oriented Languages

Download Precise Concrete Type Inference for Object-Oriented Languages
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Precise Concrete Type Inference for Object-Oriented Languages and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Precise Concrete Type Inference for Object-Oriented Languages 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?