𝔖 Bobbio Scriptorium
✦   LIBER   ✦

[ACM Press the 38th annual ACM SIGPLAN-SIGACT symposium - Austin, Texas, USA (2011.01.26-2011.01.28)] Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '11 - Pick your contexts well

✍ Scribed by Smaragdakis, Yannis; Bravenboer, Martin; Lhoták, Ondrej


Book ID
120707715
Publisher
ACM Press
Year
2011
Weight
466 KB
Category
Article
ISBN
1450304907

No coin nor oath required. For personal study only.

✦ Synopsis


Object-sensitivity has emerged as an excellent context abstraction for points-to analysis in object-oriented languages. Despite its practical success, however, object-sensitivity is poorly understood. For instance, for a context depth of 2 or higher, past scalable implementations deviate significantly from the original definition of an object-sensitive analysis. The reason is that the analysis has many degrees of freedom, relating to which context elements are picked at every method call and object creation. We offer a clean model for the analysis design space, and discuss a formal and informal understanding of object-sensitivity and of how to create good objectsensitive analyses. The results are surprising in their extent. We find that past implementations have made a sub-optimal choice of contexts, to the severe detriment of precision and performance. We define a "full-object-sensitive" analysis that results in significantly higher precision, and often performance, for the exact same context depth. We also introduce "type-sensitivity" as an explicit approximation of object-sensitivity that preserves high context quality at substantially reduced cost. A type-sensitive points-to analysis makes an unconventional use of types as context: the context types are not dynamic types of objects involved in the analysis, but instead upper bounds on the dynamic types of their allocator objects. Our results expose the influence of context choice on the quality of points-to analysis and demonstrate type-sensitivity to be an idea with major impact: It decisively advances the state-of-the-art with a spectrum of analyses that simultaneously enjoy speed (several times faster than an analogous object-sensitive analysis), scalability (comparable to analyses with much less context-sensitivity), and precision (comparable to the best object-sensitive analysis with the same context depth).


📜 SIMILAR VOLUMES


[ACM Press the 38th annual ACM SIGPLAN-S
✍ Weirich, Stephanie; Vytiniotis, Dimitrios; Peyton Jones, Simon; Zdancewic, Steve 📂 Article 📅 2011 🏛 ACM Press ⚖ 569 KB

Modular languages support generative type abstraction, ensuring that an abstract type is distinct from its representation, except inside the implementation where the two are synonymous. We show that this well-established feature is in tension with the non-parametric features of newer type systems, s