dotnet / dotnet/runtime

JIT: KnownBits & DemandedBits

Open
#129,276 3 comments 4 reactions 1 assignee Claimed by @EgorBo View on GitHub
area-CodeGen-coreclr
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.