Pointer analysis is a widely used compiler analysis used as a base for different kinds of analyses and compiler optimizations. Designing a scalable pointer analysis with acceptable precision for use in production compilers is still an open question. Modern object oriented languages like Java and Scala promote abstractions and code reuse, both of which make it difficult to achieve precision. Collection data structures (such as HashMap and ArrayList in Java) are an example of a pervasively used component in such languages. But analyzing collection implementations with full context sensitivity (which is required for analysis precision) leads to prohibitively long analysis times.
In this talk, I will present a way to enable fast and precise analysis of collection data structures by the use of semantic models. A semantic model is a heavily simplified implementation of a collection data structure, specialized and used only for pointer analysis. The model encapsulates only the relevant behavior of the data structure while stripping away irrelevant details. Analyzing the model with context sensitivity leads to precise results with only a modest increase in analysis time. The models must be written manually, which is feasible because a model method usually consists of only a few statements. Our implementation in a production Java compiler shows a rise in useful precision with a manageable performance cost.
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.
Zoom Participation. See announcement.