--- title: The Shift of Theseus — Toy Bit Provenance Abstract Domain description: A new 'bit provenance' abstract domain tracks where each bit of an SSA value comes from, letting a toy optimizer collapse long chains of shifts, ands, ors and... canonical: https://daily.dev/posts/the-shift-of-theseus-toy-bit-provenance-abstract-domain-shrtb1gwj twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: The Shift of Theseus — Toy Bit Provenance Abstract Domain | daily.dev og:description: A new 'bit provenance' abstract domain tracks where each bit of an SSA value comes from, letting a toy optimizer collapse long chains of shifts, ands, ors and... og:url: https://daily.dev/posts/the-shift-of-theseus-toy-bit-provenance-abstract-domain-shrtb1gwj og:image: https://api.daily.dev/og/posts/ShRTb1GWJ.png og:image:alt: The Shift of Theseus — Toy Bit Provenance Abstract Domain og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # The Shift of Theseus — Toy Bit Provenance Abstract Domain **[Planet Python](https://daily.dev/sources/planetpython)** · 26 min read · 0 upvotes · 0 comments ## Summary A new 'bit provenance' abstract domain tracks where each bit of an SSA value comes from, letting a toy optimizer collapse long chains of shifts, ands, ors and xors into simpler operations. Unlike the earlier Knownbits domain, it can recognize when a bit in one variable is identical to a bit in another, enabling optimizations local peephole rules would miss. A 63-operation bit-reversal-then-shift-then-reversal test reduces to 3 operations. Tested on real PyPy JIT traces, the approach alone removes 44.59% of Pydrofoil's 1,484,985 integer operations and 4.71% of PyPy's 1,442,782, compared to 48.16% and 24.51% from RPython's existing integer optimizer. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### How much does bit provenance analysis reduce integer operations in PyPy JIT traces compared to existing RPython optimizations? Bit provenance optimization alone removes 4.71% of PyPy's 1,442,782 unoptimized integer operations, versus 24.51% removed by RPython's existing integer optimizer. Running RPython optimizations first and then provenance analysis removes the same 24.51%, meaning provenance found no additional reductions beyond what RPython already caught for this PyPy workload. _Developers tuning JIT compiler optimizations can track approaches like this through daily.dev._ ### What is a bit provenance abstract domain in compiler optimization? It is an abstract domain that tracks, for every bit of an SSA variable in a trace, which original source bit it comes from (possibly inverted) or whether it is a known constant 0 or 1. This lets an optimizer detect when a bit in one variable is identical to a bit in another variable at a different position, enabling rewrites that simple 'known bits' domains or local peephole rules would miss. _Those building or studying optimizer passes can follow deep dives like this on daily.dev._ ### How well does a bit provenance optimizer perform on RISC-V emulator JIT traces compared to a mature JIT optimizer? On Pydrofoil's RISC-V simulation traces, the standalone bit provenance optimizer removed 44.59% of 1,484,985 unoptimized integer operations, close to the 48.16% removed by RPython's well-tuned integer optimization passes. Combining both passes removed 55.79%, showing the small provenance-based approach nearly matches a mature optimizer's results with far simpler transfer function rules. _Engineers comparing optimizer designs can keep up with results like these via daily.dev._ ## Similar posts on daily.dev - [Too much Discussion of the XOR swap trick – Heather Cafe](https://daily.dev/posts/too-much-discussion-of-the-xor-swap-trick-heather-cafe-7zbqi1yr9) · Hacker News · 2 upvotes · 0 comments - [Computing efficiently in QLDPC codes](https://daily.dev/posts/computing-efficiently-in-qldpc-codes-xgfmydco4) · Nature · 0 upvotes · 0 comments --- Tags: [#python](https://daily.dev/tags/python), [#compiler-optimization](https://daily.dev/tags/compiler-optimization) [View this post on daily.dev](https://daily.dev/posts/the-shift-of-theseus-toy-bit-provenance-abstract-domain-shrtb1gwj) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"The Shift of Theseus — Toy Bit Provenance Abstract Domain","url":"https://daily.dev/posts/the-shift-of-theseus-toy-bit-provenance-abstract-domain-shrtb1gwj","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/the-shift-of-theseus-toy-bit-provenance-abstract-domain-shrtb1gwj"},"datePublished":"2026-10-27T10:49:09.151Z","dateModified":"2026-10-27T10:49:42.955Z","description":"A new 'bit provenance' abstract domain tracks where each bit of an SSA value comes from, letting a toy optimizer collapse long chains of shifts, ands, ors and...","image":"https://media.daily.dev/image/upload/s--OHB84bZF--/f_auto/v1722860399/public/Placeholder%2010","thumbnailUrl":"https://media.daily.dev/image/upload/s--OHB84bZF--/f_auto/v1722860399/public/Placeholder%2010","isAccessibleForFree":true,"articleSection":"Planet Python","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Planet Python","logo":"https://media.daily.dev/image/upload/t_logo,f_auto/v1/logos/eac3cc584cb043b5a242d13752bd3d0c","url":"https://daily.dev/sources/planetpython"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/the-shift-of-theseus-toy-bit-provenance-abstract-domain-shrtb1gwj","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":0},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"python,compiler-optimization","timeRequired":"PT26M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Planet Python","item":"https://daily.dev/sources/planetpython"},{"@type":"ListItem","position":3,"name":"The Shift of Theseus — Toy Bit Provenance Abstract Domain"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/the-shift-of-theseus-toy-bit-provenance-abstract-domain-shrtb1gwj#faq","mainEntity":[{"@type":"Question","name":"How much does bit provenance analysis reduce integer operations in PyPy JIT traces compared to existing RPython optimizations?","acceptedAnswer":{"@type":"Answer","text":"Bit provenance optimization alone removes 4.71% of PyPy's 1,442,782 unoptimized integer operations, versus 24.51% removed by RPython's existing integer optimizer. Running RPython optimizations first and then provenance analysis removes the same 24.51%, meaning provenance found no additional reductions beyond what RPython already caught for this PyPy workload. Developers tuning JIT compiler optimizations can track approaches like this through daily.dev."}},{"@type":"Question","name":"What is a bit provenance abstract domain in compiler optimization?","acceptedAnswer":{"@type":"Answer","text":"It is an abstract domain that tracks, for every bit of an SSA variable in a trace, which original source bit it comes from (possibly inverted) or whether it is a known constant 0 or 1. This lets an optimizer detect when a bit in one variable is identical to a bit in another variable at a different position, enabling rewrites that simple 'known bits' domains or local peephole rules would miss. Those building or studying optimizer passes can follow deep dives like this on daily.dev."}},{"@type":"Question","name":"How well does a bit provenance optimizer perform on RISC-V emulator JIT traces compared to a mature JIT optimizer?","acceptedAnswer":{"@type":"Answer","text":"On Pydrofoil's RISC-V simulation traces, the standalone bit provenance optimizer removed 44.59% of 1,484,985 unoptimized integer operations, close to the 48.16% removed by RPython's well-tuned integer optimization passes. Combining both passes removed 55.79%, showing the small provenance-based approach nearly matches a mature optimizer's results with far simpler transfer function rules. Engineers comparing optimizer designs can keep up with results like these via daily.dev."}}]} ```