Flow-Sensitive Type Analysis for C++

Static determination of run-time types is a key analysis step for compile-time optimizations of object-oriented languages with dynamic dispatch of functions. Type information is fundamental for determining the virtual functions that can be invoked and enables a number of interprocedural analyses and transformations. For example, knowledge of the types of objects at virtual function call sites opens opportunities for inlining, which in turn facilitates a number of intraprocedural compiler optimizations. The results of type analysis may also aid function cloning based on the types of function parameters. In this paper, we show how an existing flow-sensitive pointer alias analysis that uses a compact representation can be adapted to provide a type analysis algorithm which computes type information in a lazy fashion, thereby incurring minimal additional overhead. We show that use of the type information as soon as it becomes available can, in turn, improve the precision of the pointer alias analysis. We demonstrate that incorporating knowledge of the class hierarchy into our algorithm improves its precision, and show that our flow-sensitive method is more precise than flow-insensitive methods.

By: Paul R. Carini, Michael Hind, and Harini Srinvasan

Published in: RC20267 in 1995

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

7899.ps.gz

Questions about this service can be mailed to reports@us.ibm.com .