Precise complexity guarantees for pointer analysis via datalog with extensions*. Issue 5 (14th October 2016)

• Record Type: Journal Article
• Authors: TEKLE, K. TUNCAY; LIU, YANHONG A.
• Editors: Carro, Manuel; King, Andy
• Is Part Of: Theory and practice of logic programming. Volume 16:Issue 5/6(2016)
• Page Start: 916
• Page End: 932
• Publication Date: 2016-10-14
• Subjects: Datalog, -- function symbols, -- universal quantification, -- computational complexity, -- static program analysis, -- pointer analysis, -- alias analysis; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068416000405
• Languages: English
• ISSNs: 1471-0684

Abstract

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.