|
|
|
|
|
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.
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.