JIT: KnownBits & DemandedBits
- Dominant language
- C#
- Stars
- 18.3k
- Forks
- 5.6k
- PR merge metrics
- PR metrics pending
Description
RyuJIT currently reasons about integer values only as signed contiguous ranges `Range { int32 lo; int32 hi }`. That captures *magnitude* facts (bounds, overflow, comparison folding) but is blind to *bit-pattern* facts - alignment, parity, masks, set/clear bits. It is also will be painful to fully support 64-bit ranges.
This proposes adding two complementary, bit-granular analyses, mirroring LLVM's `computeKnownBits` and `DemandedBits`.
## What they do
**KnownBits** - forward analysis (definition -> use). For each integer value, tracks two masks: bits known to be `0` and bits known to be `1` (a bit can also be unknown). Answers: *"what does this value look like in binary at this point?"*
**DemandedBits** - backward analysis (use ->definition). For each value, tracks which bits any consumer actually reads (a "live-bit"/don't-care mask). Answers: *"which bits does anyone need down the line so we can simplify current operator"*
## Examples - KnownBits folds (forward)
- **Modulo/mask by power of two**: `x % 8` → `x & 7`; fold `x % 8 == 0` when low 3 bits are known 0.
- **Alignment fixups**: `(p + 7) & ~7` → `p` when `p` is known 8-aligned; `(x >> 3) << 3` → `x`.
- **Parity / single-bit tests**: fold `(x & 1)` branch when evenness is known; `x | FLAG` makes `(x & FLAG) != 0` → `true`.
- **Redundant masks / extensions**: `x & C` → `x` when bits outside `C` are already 0; drop `movzx`/`& 0xFFFF` when upper bits known 0.
- **Bit-pattern contradictions**: `(x & 0x10) == 0x20` → `false` (a range can't see this).
- **Disjoint bitwise ops**: `x & C` → `0`, `x | C` → `C` when known bits don't overlap.
- **Sign-bit known**: pick unsigned forms, simplify `abs`, fold sign tests.
## Examples - DemandedBits folds (backward)
- **Bit-level DCE**: `t = x << 8; r = t & 0xFF` → `r = 0`, and `x << 8` is dead.
- **Op narrowing**: 64-bit `(long)p * (long)q` consumed as `(int)` → 32-bit multiply (drops upper half).
- **Drop dead masks/sets**: `y = x | 1; z = y & 0xFE` → `z = x & 0xFE` (the `| 1` is dead).
- **Remove extensions**: `(int)((long)(int)x + 1)` → `x + 1` when upper 32 bits unused.
- **`add` → `or`**: when no demanded bit position carries.
- **Boolean widening cleanup**: drop masking/`zext` around `i1` values when only bit 0 is read.
I think `KnownBits` part is fairly straighforward to implement, my initial attempt (doesn't cover many operators intentionally to be less complex in an initial PR): https://github.com/dotnet/runtime/pull/129082
I'm not so sure about the `DemandedBits`. A few things that complicate the impl is the fact how small types are mostly typed as TYP_INT (32bit) + normalize on load/store things. Also, need to be careful with gc refs that may change their alignment when we do that "opportunistic align".
Contributor guide
Assessment
This issue has not been assessed yet.