KnownBits: Multiplication when LSB is followed by known zeros
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
https://github.com/llvm/llvm-project/blob/main/llvm/lib/Support/KnownBits.cpp
`KnownBits::mul` calculates the known bits when multiplying integers X and Y.
Suppose both X and Y have no known trailing zeros.
Currently, if there are N least-significant known bits in X, and M least-significant known bits in Y, then we know `min(N, M)` least-significant bits of the result. This is explained here in `KnownBits::mul` https://github.com/llvm/llvm-project/blob/3e6d5937389ff34243b58b70af0282c6c9174021/llvm/lib/Support/KnownBits.cpp#L1093-L1134
However, it is possible infer more known bits if the LSB is followed by known zeros in one of the arguments:
- LSB is known set: `??0001 * ??ABC? = ??ABC?`
- LSB is unknown: `??000? * ??ABC? = ??abc?` (where `a` is `0` if `A` was `0`, and unknown otherwise)
- Squaring: `??A0B * ??A0B = ??00B`, `??A000B * ??A000B = ??0000B`
# LSB is known set
Requirements:
- bit [0] of X is set.
- bits [1, K] are known zeros for X
- bits [1, K] of Y contains at least one known bit.
```
??001 * ??AB? =
??001 * ??00? = ??00?
??001 * ??01? = ??01?
??001 * ??10? = ??10?
??001 * ??11? = ??11?
```
# LSB is unknown
Requirements:
- bits [1, K] are known zeros for X
- bits [1, K] of Y contains at least one known zero.
```
???0? * ???0? =
???00 * ???00 = ?0000
???00 * ???01 = ???00
???01 * ???00 = ???00
???01 * ???01 = ???01
---------------------------
= ???0?
```
More generally, known zeros will stay zero, but known ones will become unknown in the result.
```
??00? * ??AB? =
??00? * ??00? = ??00?
??00? * ??01? = ??0??
??00? * ??10? = ???0?
??00? * ??11? = ?????
```
# Squaring
If bits [1, K] are zeros in X, then bits [1, K + 1] will be zero in the result for X * X.
```
?A0B * ?A0B =
?000 * ?000 = ?0?000000
?001 * ?001 = ??????001
?100 * ?100 = ??0010000
?101 * ?101 = ??????001
---------------------------
= ??????00?
```
Proof that bit `K + 1` will be cleared when squaring:
For the example above, let `C = K + 1`, which is the bit position where A resides. It is trivial to show that bit `C` will be cleared if `A` or `B` is 0. That leaves the case where A and B are both 1. We can also express `A` as `2^C`. Therefore when we square the least significant bits `(A + B)^2`:
```
(A + B)^2 =
(A + 1)^2 =
A^2 + 2A + 1 =
(2^C)^2 + 2 * 2^C + 1 =
2^(2C) + 2^(C+1) + 2^0
```
If we take this simplified expression modulo `2^(C+1)`, the only remaining value is `2^0`, meaning that `2^C` will be cleared.
Fun fact: X * X already clears bit[1], so if you were to raise X to the power of 4 `(X * X) * (X * X)` we would then also be able to infer that both bit[1] and bit[2] are cleared. However, I believe this won't be inferred if multiplication is done in this order `((X * X) * X) * X`.
Contributor guide
Research direction
Start in llvm/lib/Support/KnownBits.cpp at KnownBits::mul and trace how trailing known bits are currently inferred. Use the issue’s LSB, unknown-LSB, and squaring examples as expected cases, then verify that multiplication reports every bit the stated rules prove known without losing existing results.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100