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.
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 |
Archive Staff Only
View Item |