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): #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".
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
computeKnownBitsandDemandedBits.What they do
KnownBits - forward analysis (definition -> use). For each integer value, tracks two masks: bits known to be
0and bits known to be1(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)
x % 8→x & 7; foldx % 8 == 0when low 3 bits are known 0.(p + 7) & ~7→pwhenpis known 8-aligned;(x >> 3) << 3→x.(x & 1)branch when evenness is known;x | FLAGmakes(x & FLAG) != 0→true.x & C→xwhen bits outsideCare already 0; dropmovzx/& 0xFFFFwhen upper bits known 0.(x & 0x10) == 0x20→false(a range can't see this).x & C→0,x | C→Cwhen known bits don't overlap.abs, fold sign tests.Examples - DemandedBits folds (backward)
t = x << 8; r = t & 0xFF→r = 0, andx << 8is dead.(long)p * (long)qconsumed as(int)→ 32-bit multiply (drops upper half).y = x | 1; z = y & 0xFE→z = x & 0xFE(the| 1is dead).(int)((long)(int)x + 1)→x + 1when upper 32 bits unused.add→or: when no demanded bit position carries.zextaroundi1values when only bit 0 is read.I think
KnownBitspart is fairly straighforward to implement, my initial attempt (doesn't cover many operators intentionally to be less complex in an initial PR): #129082I'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".