Static Analysis by Elimination

Nytro · January 29, 2014

Pavle Subotic1 , Andrew E. Santosa2 , and

Bernhard Scholz

Uppsala University, Sweden

2 Oracle Labs, Australia

University of Sydney, Australia

Abstract.

In the past, elimination-based data flow analysis algorithms have been

proposed as an alternative to iterative algorithms for solving dataflow problems.

Elimination-based algorithms exhibit a better worst-case runtime performance

than iterative algorithms. However, the implementation of elimination-based al-

gorithms is more challenging and iterative algorithms have been sufficient for

solving standard data-flow problems in compilers. For more generic abstract in-

terpretation frameworks, it has not been explored whether elimination-based al-

gorithms are useful. In this paper we show that elimination-based algorithms

are useful for implementing abstract interpretation frameworks for low-level pro-

gramming languages. We demonstrate the feasibility of our approach by a range

analysis developed in the LLVM framework. We supplement this work by a range

of experiments conducted through several test suites.

Recommended Posts