Article contents
Precise complexity guarantees for pointer analysis via Datalog with extensions*
Published online by Cambridge University Press: 14 October 2016
Abstract
Pointer analysis is a fundamental static program analysis for computing the set of objects that an expression can refer to. Decades of research has gone into developing methods of varying precision and efficiency for pointer analysis for programs that use different language features, but determining precisely how efficient a particular method is has been a challenge in itself.
For programs that use different language features, we consider methods for pointer analysis using Datalog and extensions to Datalog. When the rules are in Datalog, we present the calculation of precise time complexities from the rules using a new algorithm for decomposing rules for obtaining the best complexities. When extensions such as function symbols and universal quantification are used, we describe algorithms for efficiently implementing the extensions and the complexities of the algorithms.
Keywords
- Type
- Regular Papers
- Information
- Theory and Practice of Logic Programming , Volume 16 , Special Issue 5-6: 32nd International Conference on Logic Programming , September 2016 , pp. 916 - 932
- Copyright
- Copyright © Cambridge University Press 2016
Footnotes
This work was supported in part by NSF under grants CCF-1414078, IIS-1447549, CCF-1248184, CCF-0964196, and ONR under grant N000141512208.
References
- 1
- Cited by