UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

On Fast Large-Scale Program Analysis in Datalog

Subotic, P; Scholz, B; Jordan, H; Westmann, T; (2016) On Fast Large-Scale Program Analysis in Datalog. In: Proceedings of the 25th International Conference on Compiler Construction. (pp. pp. 196-206). ACM: New York, NY, USA. Green open access

[thumbnail of main.pdf]
Preview
Text
main.pdf - Accepted Version

Download (469kB) | Preview

Abstract

Designing and crafting a static program analysis is challenging due to the complexity of the task at hand. Among the challenges are modelling the semantics of the input language, finding suitable abstractions for the analysis, and handwriting efficient code for the analysis in a traditional imperative language such as C++. Hence, the development of static program analysis tools is costly in terms of development time and resources for real world languages. To overcome, or at least alleviate the costs of developing a static program analysis, Datalog has been proposed as a domain specific language (DSL).With Datalog, a designer expresses a static program analysis in the form of a logical specification. While a domain specific language approach aids in the ease of development of program analyses, it is commonly accepted that such an approach has worse runtime performance than handcrafted static analysis tools. In this work, we introduce a new program synthesis methodology for Datalog specifications to produce highly efficient monolithic C++ analyzers. The synthesis technique requires the re-interpretation of the semi-naïve evaluation as a scaffolding for translation using partial evaluation. To achieve high-performance, we employ staged compilation techniques and specialize the underlying relational data structures for a given Datalog specification. Experimentation on benchmarks for large-scale program analysis validates the superior performance of our approach over available Datalog tools and demonstrates our competitiveness with state-of-the-art handcrafted tools.

Type: Proceedings paper
Title: On Fast Large-Scale Program Analysis in Datalog
Event: International Conference On Compiler Construction
Location: Barcelona, Spain
Dates: 17 March 2016 - 18 March 2016
ISBN-13: 978-1-4503-4241-4
Open access status: An open access version is available from UCL Discovery
DOI: 10.1145/2892208.2892226
Publisher version: http://dx.doi.org/10.1145/2892208.2892226
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Static Program Analysis, Synthesis, Datalog
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/1474713
Downloads since deposit
Loading...
990Downloads
Download activity - last month
Loading...
Download activity - last 12 months
Loading...
Downloads by country - last 12 months
Loading...

Archive Staff Only

View Item View Item