Generating Abstract Operations with Hoist

toolchain bitwise domain

interval domain

The Problem

Many useful program analyses and transformations can be phrased in terms of abstract interpretation. A problem in developing an abstract interpreter, such as our stacktool, is that an abstract version of each concrete program operation must be constructed. For the stacktool, this means creating abstract machine instructions for the AVR architecture in the "bitwise" abstract domain. This is basically a big pain: these operations are boring to code and difficult to get right. Our experience, coupled with anecdotal evidence from other authors of abstract interpreters, suggests that creating operations that efficiently manipulate sets of values without losing too much information is inherently hard.

The Solution

Hoist sidesteps problems in creating tedious and error-prone code by automatically deriving maximally precise abstract operations for machine-level operations. We have shown that it works for the AVR architecture, and we believe that it generalizes to other architectures without too much difficulty. We have shows that it works for the bitwise and interval abstract domains, and we believe that it works for other domains that meet certain criteria.

The process, shown in the flowchart at the top of this page, is this:

Advantages of Hoist are that it requires almost no input from a human and it creates maximally precise operations. Its primary disadvantage comes from its brute-force strategy, which effectively limits it to 8-bit architectures.

Results

The Hoist system is described in detail in our ASPLOS paper. In a nutshell, it works and we have been using its results in day-to-day development of the stacktool for several months.

Ongoing Work

We are Hoisting more abstract domains and more architectures. Usit is making Hoist scale to 32- and 64-bit architectures.

People

Download

The bitwise abstract operations generated by Hoist are distributed as part of our stacktool. Look at the files in the bdd_ops subdirectory. Please contact us if you are interested in interval-domain operations for AVR.

Also let us know if you might be interested in porting Hoist to other architectures. Porting to 8-bit chips such as 8051 or PIC would be pretty straightforward. Porting Hoist to architectures with larger word sizes is a research problem that we are working on.


John Regehr, October 2004