The Shift of Theseus — Toy Bit Provenance Abstract Domain
The Knownbits Toy abstract domain that I wrote about earlier is great for all kinds of bit manipulation rewrites. However, it is not particularly good at recognizing where bits move around in a sequence of instructions. It has a notion of "this bit is `0` or `1` or unknown" but no notion of "this bit is the same as this other bit". This prevents it from optimizing something like this:
[](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aea0a36bfa794752a4a813c9227e54d9-1)x = ... [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aea0a36bfa794752a4a813c9227e54d9-2)a = x & 0x0f [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aea0a36bfa794752a4a813c9227e54d9-3)b = x << 60 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aea0a36bfa794752a4a813c9227e54d9-4)c = b >> 60 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aea0a36bfa794752a4a813c9227e54d9-5)result = a & c
Here `a` and `c` compute the same value, so it can be optimized to `result = a`. It is possible to do this optimization with local peephole rewrite rules too, but doing that requires adding a lot of these rules, and if one is missing we might miss collapsing a long sequence of operations.
In this post I want to talk about a more complicated abstract domain that is great at optimizing this kind of bit movement. It's a "bit provenance" domain. For every SSA variable in a trace, it computes where each bit from the variable comes from (or whether it's constant `0` or `1`). In particular it can track if a bit in one variable must be the same as the bit of another variable at another position.
For the example above, the domain would store the following provenance information. Nothing is known about `x`, so its bits refer to themselves. Using 64-bit integers and a logical right shift, we get this table (most significant bits first):
| operation | Bit 63 | Bit 62 | Bit 61 | Bit 60 | Bit 59 | ... | Bit 4 | Bit 3 | Bit 2 | Bit 1 | Bit 0 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | `x = ...` | x[63] | x[62] | x[61] | x[60] | x[59] | ... | x[4] | x[3] | x[2] | x[1] | x[0] | | `a = x & 0x0f` | 0 | 0 | 0 | 0 | 0 | ... | 0 | x[3] | x[2] | x[1] | x[0] | | `b = x << 60` | x[3] | x[2] | x[1] | x[0] | 0 | ... | 0 | 0 | 0 | 0 | 0 | | `c = b >> 60` | 0 | 0 | 0 | 0 | 0 | ... | 0 | x[3] | x[2] | x[1] | x[0] | | `result = a & c` | 0 | 0 | 0 | 0 | 0 | ... | 0 | x[3] | x[2] | x[1] | x[0] |
Then we can directly conclude that `result` is the same value as `a`.
In the rest of the post I'll describe how the domain values store this information, how the transfer functions work and how we can use the abstract domain to optimize.
- Implementing Transfer Functions
- Implementing Bitwise Binary Transfer Functions
- Extracting Simpler Operations
- Identity
- More Rewrites from the Same Rules
- Evaluation with Pydrofoil and PyPy
Implementing the Domain[¶](https://pypy.org/posts/2026/10/toy-bit-provenance.html#implementing-the-domain "Permalink to this heading")
We'll start with reusing the toy optimizer from the previous posts, in the fold for completeness’ sake.
toy infrastructure
[](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-1)from dataclasses import dataclass [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-2) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-3)INTEGER_WIDTH = 64 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-4)INT_MASK = 2 ** INTEGER_WIDTH - 1 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-5) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-6)class Value: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-7) def find(self): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-8) raise NotImplementedError("abstract") [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-9) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-10) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-11)@dataclass(eq=False) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-12)class Operation(Value): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-13) name : str [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-14) args : list[Value] [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-15) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-16) forwarded : Value | None = None [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-17) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-18) def find(self) -> Value: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-19) op = self [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-20) while isinstance(op, Operation): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-21) next = op.forwarded [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-22) if next is None: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-23) return op [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-24) op = next [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-25) return op [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-26) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-27) def arg(self, index): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-28) return self.args[index].find() [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-29) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-30) def make_equal_to(self, value : Value): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-31) self.find().forwarded = value [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-32) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-33) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-34)@dataclass(eq=False) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-35)class Constant(Value): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-36) value : object [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-37) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-38) def find(self): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-39) return self [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-40) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-41) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-42)class Block(list): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-43) def __getattr__ (self, opname): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-44) def wraparg(arg): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-45) if not isinstance(arg, Value): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-46) arg = Constant(arg) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-47) return arg [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-48) def make_op(*args): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-49) op = Operation(opname, [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-50) [wraparg(arg) for arg in args]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-51) self.append(op) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-52) return op [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-53) return make_op [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-54) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-55) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-56)def bb_to_str(l : Block, varprefix : str = "var"): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-57) def arg_to_str(arg : Value): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-58) if isinstance(arg, Constant): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-59) return str(arg.value) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-60) else: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-61) return varnames[arg] [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-62) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-63) varnames = {} [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-64) res = [] [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-65) for index, op in enumerate(l): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-66) # give the operation a name used while [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-67) # printing: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-68) var = f"{varprefix}{index}" [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-69) varnames[op] = var [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-70) arguments = ", ".join( [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-71) arg_to_str(op.arg(i)) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-72) for i in range(len(op.args)) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-73) ) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-74) strop = f"{var} = {op.name}({arguments})" [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-75) res.append(strop) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-76) return "\n".join(res) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-77) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-78)def dce(bb: Block) -> Block: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-79) pure = {"getarg", "int_and", "int_or", "int_xor", "int_invert", [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-80) "int_lshift", "int_rshift"} [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-81) used = set() [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-82) kept = [] [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-83) for op in reversed(bb): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-84) if op not in used and op.name in pure: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-85) continue [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-86) kept.append(op) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-87) for i in range(len(op.args)): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-88) arg = op.arg(i) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-89) if isinstance(arg, Operation): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-90) used.add(arg) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-91) return Block(reversed(kept)) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-92) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-93) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-94)def test_dce(): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-95) bb = Block() [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-96) x = bb.getarg(0) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-97) live = bb.int_or(x, 1) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-98) dead = bb.int_xor(live, 7) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-99) bb.int_and(dead, 15) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-100) forwarded = bb.int_and(x, 0) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-101) forwarded.make_equal_to(Constant(0)) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-102) bb.dummy(live) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-103) bb.dummy(forwarded) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-104) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-105) assert bb_to_str(dce(bb), "optvar") == """\ [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-106)optvar0 = getarg(0) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-107)optvar1 = int_or(optvar0, 1) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-108)optvar2 = dummy(optvar1) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_aef4c407cf194073b2eb51167457e7b7-109)optvar3 = dummy(0)"""
(The `dce` function was adapted from the Prospero blog post.)
Then we can start implementing the domain values like this:
[](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-1)@dataclass(frozen=True) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-2)class SourceBit: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-3) source: Operation [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-4) index: int [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-5) inverted: bool = False [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-6) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-7) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-8)@dataclass(frozen=True) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-9)class BitProvenance: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-10) # least significant bit first [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-11) bits: tuple[int | SourceBit, ...] [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-12) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-13) @staticmethod [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-14) def make(bits): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-15) bits = tuple(bits) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-16) if len(bits) < INTEGER_WIDTH: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-17) # zero-extend, mainly for tests [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-18) bits = bits + (0, ) * (INTEGER_WIDTH - len(bits)) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-19) assert len(bits) == INTEGER_WIDTH [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-20) return BitProvenance(bits) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-21) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-22) @staticmethod [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-23) def from_constant(value): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-24) return BitProvenance(tuple((value >> i) & 1 for i in range(INTEGER_WIDTH))) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-25) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-26) @staticmethod [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-27) def from_source(source: Operation): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-28) # nothing is known about this SSA value [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-29) return BitProvenance(tuple(SourceBit(source, i) for i in range(INTEGER_WIDTH))) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-30) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-31) def get_constant(self) -> int | None: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-32) res = 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-33) shift = 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-34) for bit in self.bits: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-35) if isinstance(bit, SourceBit): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-36) return None [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-37) res |= bit << shift [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-38) shift += 1 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_ba92c900ccb44ed68712c05929fc177e-39) return res
Every `SourceBit` refers to a bit of an SSA `Operation`. For an SSA value that we know nothing about, we use the `from_source` factory method, which returns something of the form:
[](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_b07dd51e54234d97a9511f29303155af-1)x = ... # x[63] x[62] x[61] x[60] x[59] ... x[ 3] x[ 2] x[ 1] x[0]
For a constant, the `from_constant` factory returns an abstract value where all the bits are concretely known values. Constants are simply `0` or `1` and need no source at all.
The `inverted` field of a `SourceBit` specifies whether the bit is a direct copy of the source bit, or whether the bit is flipped.
Let's make sure we got the bit twiddling in `from_constant` and `get_constant` right by writing a Hypothesis test:
[](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_afb964a25bdb421a8ad17ed6477633cb-1)from hypothesis import given, strategies [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_afb964a25bdb421a8ad17ed6477633cb-2) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_afb964a25bdb421a8ad17ed6477633cb-3)ints = strategies.integers(0, 2**64-1) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_afb964a25bdb421a8ad17ed6477633cb-4) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_afb964a25bdb421a8ad17ed6477633cb-5)@given(ints) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_afb964a25bdb421a8ad17ed6477633cb-6)def test_hypothesis_from_constant_get_constant_roundtrip(val): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_afb964a25bdb421a8ad17ed6477633cb-7) assert BitProvenance.from_constant(val).get_constant() == val
Implementing Transfer Functions[¶](https://pypy.org/posts/2026/10/toy-bit-provenance.html#implementing-transfer-functions "Permalink to this heading")
The simplest transfer function to implement for this domain is for `~`, bit invert. It inverts constant bits and flips the `inverted` field of any `SourceBit`. Here's a test:
[](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_a080c46ce4094ea2b2792f244ab845bc-1)def test_abstract_invert(): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_a080c46ce4094ea2b2792f244ab845bc-2) source = Operation("getarg", [Constant(0)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_a080c46ce4094ea2b2792f244ab845bc-3) x = BitProvenance.make([1, 0, SourceBit(source, 1, True), SourceBit(source, 0)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_a080c46ce4094ea2b2792f244ab845bc-4) res = x.abstract_invert() [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_a080c46ce4094ea2b2792f244ab845bc-5) assert res == BitProvenance.make((0, 1, SourceBit(source, 1), SourceBit(source, 0, True)) + (1, ) * 60)
The implementation looks like this (the reason for the `result` argument will become clear a bit further down):
[](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_b2254b4fa83d400ea86104c7d8716e07-1)def invert_bit(bit): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_b2254b4fa83d400ea86104c7d8716e07-2) if isinstance(bit, int): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_b2254b4fa83d400ea86104c7d8716e07-3) return bit ^ 1 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_b2254b4fa83d400ea86104c7d8716e07-4) return SourceBit(bit.source, bit.index, not bit.inverted) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_b2254b4fa83d400ea86104c7d8716e07-5) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_b2254b4fa83d400ea86104c7d8716e07-6) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_b2254b4fa83d400ea86104c7d8716e07-7)class BitProvenance: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_b2254b4fa83d400ea86104c7d8716e07-8) ... [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_b2254b4fa83d400ea86104c7d8716e07-9) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_b2254b4fa83d400ea86104c7d8716e07-10) def abstract_invert(self, result=None): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_b2254b4fa83d400ea86104c7d8716e07-11) return BitProvenance.make(tuple(invert_bit(bit) for bit in self.bits))
The shift implementations are also quite simple as long as the shift amounts are constant, they just move bits around. If the shifts aren't constant, we just know nothing about the result.
If we "know nothing", we want to use `BitProvenance.from_source` for the shift operation. Therefore the transfer functions need to get the shift `Operation` as an extra argument.
[](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-1)def test_lshift(): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-2) source = Operation("getarg", [Constant(0)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-3) x = BitProvenance.from_source(source) # no info [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-4) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-5) # x << 7, the seven high bits get cut off [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-6) seven = BitProvenance.from_constant(7) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-7) result = Operation("int_lshift", [source, Constant(7)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-8) assert x.abstract_lshift(seven, result).bits == (0, ) * 7 + x.bits[:-7] [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-9) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-10) # x << 65, constant 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-11) big = BitProvenance.from_constant(65) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-12) result = Operation("int_lshift", [source, Constant(65)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-13) assert x.abstract_lshift(big, result).get_constant() == 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-14) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-15) # x << y, we know nothing [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-16) amount = Operation("getarg", [Constant(1)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-17) result = Operation("int_lshift", [source, amount]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-18) assert x.abstract_lshift(BitProvenance.from_source(amount), result) == BitProvenance.from_source(result) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-19) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-20) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-21)@given(ints, strategies.integers(0, 100)) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-22)def test_hypothesis_lshift_on_constants(val, shift): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-23) absval = BitProvenance.from_constant(val) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-24) absshift = BitProvenance.from_constant(shift) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-25) result = Operation("int_lshift", [Constant(val), Constant(shift)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-26) assert absval.abstract_lshift(absshift, result).get_constant() == (val << shift) & INT_MASK [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-27) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-28) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-29)class BitProvenance: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-30) ... [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-31) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-32) def abstract_lshift(self, other, result: Operation): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-33) const = other.get_constant() [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-34) if const is None: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-35) return BitProvenance.from_source(result) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-36) if const >= INTEGER_WIDTH: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-37) # make oversized shift amounts return 0 for simplicity [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-38) return BitProvenance.from_constant(0) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-39) if const == 0: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-40) return self [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_552bc4be90814b43882a2481dba138c1-41) return BitProvenance.make((0, ) * const + self.bits[:-const])
Logical right shift is pretty similar, except we append the zeros at the other end:
[](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-1)def test_rshift(): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-2) source = Operation("getarg", [Constant(0)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-3) x = BitProvenance.from_source(source) # no info [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-4) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-5) # x >> 7, the seven low bits get cut off [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-6) seven = BitProvenance.from_constant(7) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-7) result = Operation("int_rshift", [source, Constant(7)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-8) assert x.abstract_rshift(seven, result).bits == x.bits[7:] + (0, ) * 7 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-9) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-10) # x >> 65, constant 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-11) big = BitProvenance.from_constant(65) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-12) result = Operation("int_rshift", [source, Constant(65)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-13) assert x.abstract_rshift(big, result).get_constant() == 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-14) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-15) # x >> y, we know nothing [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-16) amount = Operation("getarg", [Constant(1)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-17) result = Operation("int_rshift", [source, amount]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-18) assert x.abstract_rshift(BitProvenance.from_source(amount), result) == BitProvenance.from_source(result) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-19) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-20) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-21)@given(ints, strategies.integers(0, 100)) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-22)def test_hypothesis_rshift_on_constants(val, shift): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-23) absval = BitProvenance.from_constant(val) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-24) absshift = BitProvenance.from_constant(shift) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-25) result = Operation("int_rshift", [Constant(val), Constant(shift)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-26) assert absval.abstract_rshift(absshift, result).get_constant() == val >> shift [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-27) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-28) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-29)class BitProvenance: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-30) ... [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-31) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-32) def abstract_rshift(self, other, result: Operation): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-33) const = other.get_constant() [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-34) if const is None: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-35) return BitProvenance.from_source(result) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-36) if const >= INTEGER_WIDTH: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-37) return BitProvenance.from_constant(0) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-38) if const == 0: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-39) return self [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0e602e36e10d489dae187ef7d11a2c0f-40) return BitProvenance.make(self.bits[const:] + (0, ) * const)
Implementing Bitwise Binary Transfer Functions[¶](https://pypy.org/posts/2026/10/toy-bit-provenance.html#implementing-bitwise-binary-transfer-functions "Permalink to this heading")
Next are the abstract binary transfer functions `and`, `or`, `xor`. We can think about the behaviour on individual bits first. A few cases are simple (e.g. `a & 0 == 0`) but some need reasoning about sources.
[](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-1)def and_bits(a, b): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-2) # None means the result cannot be represented as a constant or source [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-3) # bit [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-4) if a == 0: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-5) return 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-6) if b == 0: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-7) return 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-8) if a == 1: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-9) return b [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-10) if b == 1: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-11) return a [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-12) assert isinstance(a, SourceBit) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-13) assert isinstance(b, SourceBit) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-14) if a == b: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-15) # a & a == a [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-16) return a [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-17) if a == invert_bit(b): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-18) # a & not a == 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-19) return 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-20) return None [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-21) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-22) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-23)def test_and_bits(): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-24) x = Operation("getarg", [Constant(0)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-25) y = Operation("getarg", [Constant(1)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-26) a = SourceBit(x, 3) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-27) assert and_bits(a, 0) == and_bits(0, a) == 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-28) assert and_bits(a, 1) == and_bits(1, a) == a [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-29) assert and_bits(a, a) == a [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-30) assert and_bits(a, invert_bit(a)) == 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-31) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-32) # positions disagree [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-33) assert and_bits(a, SourceBit(x, 4)) is None [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-34) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-35) # sources disagree [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-36) assert and_bits(a, SourceBit(y, 3)) is None [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_7229588c931e4b338101d2e4b2b0e18c-37) assert and_bits(a, SourceBit(y, 3, True)) is None
When `and_bits` returns `None` for output bit `i`, we can use `SourceBit(result, i)`: we don't know how that bit relates to the inputs. The other output bits keep their own provenance, even if they refer to different operations.
Now we can combine `and_bits` calls for all the bits of a `BitProvenance`.
[](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-1)def test_and(): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-2) x = Operation("getarg", [Constant(0)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-3) y = Operation("getarg", [Constant(1)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-4) absx = BitProvenance.from_source(x) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-5) absy = BitProvenance.from_source(y) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-6) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-7) # x & 0 == 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-8) result = Operation("int_and", [x, Constant(0)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-9) assert absx.abstract_and(BitProvenance.from_constant(0), result).get_constant() == 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-10) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-11) # x & -1 == x [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-12) result = Operation("int_and", [x, Constant(INT_MASK)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-13) assert absx.abstract_and(BitProvenance.from_constant(INT_MASK), result) == absx [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-14) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-15) # x & x == x [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-16) result = Operation("int_and", [x, x]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-17) assert absx.abstract_and(absx, result) == absx [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-18) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-19) # x & y: we can't usefully represent provenance, so we get fresh bits [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-20) result = Operation("int_and", [x, y]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-21) assert absx.abstract_and(absy, result) == BitProvenance.from_source(result) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-22) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-23) # x & ~x == 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-24) result = Operation("int_and", [x, Operation("int_invert", [x])]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-25) assert absx.abstract_and(absx.abstract_invert(), result).get_constant() == 0 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-26) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-27) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-28)@given(ints, ints) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-29)def test_hypothesis_and_on_constants(a, b): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-30) abs_a = BitProvenance.from_constant(a) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-31) abs_b = BitProvenance.from_constant(b) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-32) result = Operation("int_and", [Constant(a), Constant(b)]) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-33) assert abs_a.abstract_and(abs_b, result).get_constant() == a & b [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-34) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-35) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-36)class BitProvenance: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-37) ... [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-38) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-39) def abstract_and(self, other, result: Operation): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-40) bits = [] [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-41) for i, (bit_a, bit_b) in enumerate(zip(self.bits, other.bits)): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-42) bit_res = and_bits(bit_a, bit_b) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-43) if bit_res is None: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-44) # not representable, use fresh provenance [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-45) bit_res = SourceBit(result, i) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-46) bits.append(bit_res) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_40f944568e944841a29fb6e4e66468cd-47) return BitProvenance.make(bits)
`or` is very similar:
[](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-1)def or_bits(a, b): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-2) if a == 1: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-3) return 1 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-4) if b == 1: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-5) return 1 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-6) if a == 0: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-7) return b [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-8) if b == 0: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-9) return a [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-10) assert isinstance(a, SourceBit) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-11) assert isinstance(b, SourceBit) [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-12) if a == b: [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-13) # a | a == a [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-14) return a [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-15) if a == invert_bit(b): [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-16) # a | not a == 1 [](https://pypy.org/posts/2026/10/toy-bit-provenance.html#rest_code_0925c8892a2c48899b0409e410a69c97-17) return 1