Precise complexity guarantees for pointer analysis via Datalog with extensions

DOI10.1017/S1471068416000405MaRDI QIDQ4593068zbMATH OpenOpenAlexFDO

Authors K. Tuncay Tekle, Yanhong A. Liu

Publication date 9 November 2017

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.01594

zbMATH Keywords

alias analysiscomputational complexityDatalogfunction symbolspointer analysisstatic program analysisuniversal quantification

Mathematics Subject Classification ID

Logic programming (68N17) Analysis of algorithms and problem complexity (68Q25)

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. This paper is under consideration for acceptance in TPLP.

Recommendations

• On the complexity analysis of static analyses
• Semi-sparse flow-sensitive pointer analysis
• Programming Languages and Systems
• On the complexity of dataflow analysis of logic programs
• Why Use Datalog to Analyze Programs?

Cites work

• Pick your contexts well, understanding object-sensitivity
• Precise complexity guarantees for pointer analysis via Datalog with extensions
• Termination of logic programs: the never-ending story
• The Complexity of Andersen’s Analysis in Practice
• Transformational derivation of an improved alias analysis algorithm

Cited in

(6)

• A decompositional approach for computing least fixed-points of datalog programs with \(\mathcal Z\)-counters
• New results on the computability and complexity of points-to analysis
• Designing programming languages for the analyzability of pointer data structures
• On the complexity analysis of static analyses
• Precise complexity guarantees for pointer analysis via Datalog with extensions
• Why Use Datalog to Analyze Programs?

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: Precise complexity guarantees for pointer analysis via Datalog with extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4593068)