The post discusses the implementation of a knownbits abstract domain for optimizing integer operations in a toy optimizer. It closely follows the tristate abstract domain used in the Linux Kernel's eBPF verifier. The post covers the implementation details, including transfer functions for common operations, leveraging property-based testing with Hypothesis, and proving correctness using Z3. It culminates with examples of using the domain for generalized constant folding and conditional peephole optimizations.
Table of contents
Motivation ¶The Knownbits Abstract Domain ¶Transfer Functions ¶Property-based Tests with Hypothesis ¶When are Transfer Functions Correct? How do we test them? ¶Implementing Binary Transfer Functions ¶Addition and Subtraction ¶Proving correctness of the transfer functions with Z3 ¶Cases where this style of Z3 proof doesn't work ¶Making Statements about Precision ¶Using the Abstract Domain in the Toy Optimizer for Generalized Constant Folding ¶Using the KnownBits Domain for Conditional Peephole Rewrites ¶Conclusion ¶Sort: