[Support] Investigate making KnownBits::mul optimal

[RKSimon]

llvm-project/llvm/unittests/Support/KnownBitsTest.cpp

Lines 586 to 591 in ffe4181

	testBinaryOpExhaustive(
	[](const KnownBits &Known1, const KnownBits &Known2) {
	return KnownBits::mul(Known1, Known2);
	},
	[](const APInt &N1, const APInt &N2) { return N1 * N2; },
	checkCorrectnessOnlyBinary);

Investigate if we can make the implementation optimal (checkOptimalityBinary)

Similar to #84212 and #84213

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor has already been assigned to this issue. If you believe that no one is actually working on it despite an assignment, ping the person. After one week without a response, the assignee may be changed.
2. In the comments of this issue, request for it to be assigned to you, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Simon Pilgrim (RKSimon)

https://github.com/llvm/llvm-project/blob/ffe41819e58365dfbe85a22556c0d9d284e746b9/llvm/unittests/Support/KnownBitsTest.cpp#L586-L591

Investigate if we can make the implementation optimal (checkOptimalityBinary)

Similar to #84212 and #84213

[antoniofrighetto]

Do we currently fail if we check with checkOptimalityBinary?

[RKSimon]

yes, a lot :)

ninja\unittests\Support\SupportTests.exe --gtest_filter=KnownBitsTest.BinaryExhaustive

Note: Google Test filter = KnownBitsTest.BinaryExhaustive
[==========] Running 1 test from 1 test suite.
[----------] Global test environment set-up.
[----------] 1 test from KnownBitsTest
[ RUN      ] KnownBitsTest.BinaryExhaustive

E:\llvm\llvm-project\llvm\unittests\Support\KnownBitsTest.cpp(123): error: Value of: isOptimal(Exact, Computed, {Known1, Known2})
  Actual: false (Inputs = ??1?, ??01, Computed = ????, Exact = ??1?)
Expected: true

***** SEVERAL THOUSAND LINES LATER *****

E:\llvm\llvm-project\llvm\unittests\Support\KnownBitsTest.cpp(123): error: Value of: isOptimal(Exact, Computed, {Known1, Known2})
  Actual: false (Inputs = 0001, 010?, Computed = 0???, Exact = 010?)
Expected: true

E:\llvm\llvm-project\llvm\unittests\Support\KnownBitsTest.cpp(123): error: Value of: isOptimal(Exact, Computed, {Known1, Known2})
  Actual: false (Inputs = 0001, 001?, Computed = 00??, Exact = 001?)
Expected: true

[  FAILED  ] KnownBitsTest.BinaryExhaustive (240 ms)
[----------] 1 test from KnownBitsTest (240 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test suite ran. (241 ms total)
[  PASSED  ] 0 tests.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] KnownBitsTest.BinaryExhaustive

we don't even get the (mul X, 1) case correct.....

[RKSimon]

CC @goldsteinn who might have some insight on this

[goldsteinn]

CC @goldsteinn who might have some insight on this

I looked at this briefly but don't know how to make it optimal. @jayfoad is better at this stuff xD

I think cases like like 1/-1 and any pow2 aren't really that interesting to handle better (not that there is any cost),
but we will never really have a mul with any of those constants.

[jayfoad]

I looked at this briefly but don't know how to make it optimal. @jayfoad is better at this stuff xD

I don't know how to do it with a fixed-time algorithm. There are probably ways to do it if you don't mind iterating N times (for multiplying N-bit integers) but I always assumed that would not be acceptable.

[goldsteinn]

I looked at this briefly but don't know how to make it optimal. @jayfoad is better at this stuff xD

I don't know how to do it with a fixed-time algorithm. There are probably ways to do it if you don't mind iterating N times (for multiplying N-bit integers) but I always assumed that would not be acceptable.

We iterate N times for shifts. My guess is also we could get a lot of early outs if the result became fully unknown early.
A bit back I tried implementing it as N additions, but it wasn't optimal either (and missed some cases we currently cover).

[jayfoad]

I tried this implementation which tracks the lowest and highest possible value for each bit position of the result in turn, starting from bit 0:

KnownBits KnownBits::mul(const KnownBits &LHS, const KnownBits &RHS,
                         bool NoUndefSelfMultiply) {
  unsigned BitWidth = LHS.getBitWidth();
  KnownBits Res(BitWidth);

  unsigned MinVal = 0;
  unsigned MaxVal = 0;
  for (unsigned I = 0; I != BitWidth; ++I) {
    MinVal += (LHS.getMinValue().trunc(I + 1) & RHS.getMinValue().trunc(I + 1).reverseBits()).popcount();
    MaxVal += (LHS.getMaxValue().trunc(I + 1) & RHS.getMaxValue().trunc(I + 1).reverseBits()).popcount();
    if (MinVal == MaxVal) {
      if (MinVal & 1)
        Res.One.setBit(I);
      else
        Res.Zero.setBit(I);
    }
    MinVal >>= 1;
    MaxVal >>= 1;
  }

  return Res;
}

It is not optimal. The first case I found where it fails is:

Inputs = 1?1, 1?1, Computed = ??1, Exact = 0?1

(i.e. 5-or-7 times 5-or-7). The algorithm computes the range of bit 2 of the result as [2, 4] but it does not know that it is always 2 or 4, never 3.

[temyurchenko]

What are the requirements for the implementation wrt performance? Is there a benchmark for KnownBits?

[goldsteinn]

What are the requirements for the implementation wrt performance? Is there a benchmark for KnownBits?

@nikic has a compile time benchmark. If that doesn't regress any impl is fine

[temyurchenko]

What are the requirements for the implementation wrt performance? Is there a benchmark for KnownBits?

@nikic has a compile time benchmark. If that doesn't regress any impl is fine

Got it. Where do I find his benchmark?

I assume, it's https://github.com/nikic/llvm-compile-time-tracker?