llvm / llvm/llvm-project

KnownBits: Multiplication when LSB is followed by known zeros

Open
#211,387 2 comments 0 reactions 0 assignees View on GitHub
llvm:support
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.