[Support] Investigate making KnownBits::abdu optimal

[RKSimon]

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

Lines 386 to 391 in ffe4181

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

Investigate if we can make the implementation optimal (checkOptimalityBinary)

[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. In the comments of the issue, request for it to be assigned to you.
2. Fix the issue locally.
3. 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.
4. Create a Git commit.
5. Run git clang-format HEAD~1 to format your changes.
6. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation.

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/44be5a7fdc20a7f90d63dc18699a470e900bd3ba/llvm/unittests/Support/KnownBitsTest.cpp#L360-L367

Investigate if can make the implementation optimal (checkOptimalityBinary)

[aamod-wick]

HI @RKSimon can you please direct me to any reference material for this issue ??

[RKSimon]

There isn't any really :( You will need a good understanding of the typical bit twiddling patterns.

If you edit checkCorrectnessOnlyBinary -> checkOptimalityBinary, rebuild and run:

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

You will get an error dump of all the cases where the abdu knownbits aren't optimal e.g.:

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

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

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

Then its a lot of triage trying to work out why it failed.

[RKSimon]

CC @goldsteinn who may have some suggestions

[goldsteinn]

CC @goldsteinn who may have some suggestions

I think whats missing is we don't set nuw flag when comparing diff0/diff1.
What might work is pull the impl of computeForAddSub out to a helper that
does not reset conflicts/poison.
Then have something like:

  KnownBits Diff0 =
      computeForAddSubNoResolvePoison(/*Add=*/false, /*NSW=*/false, /*NUW=*/true, LHS, RHS);
  KnownBits Diff1 =
      computeForAddSubNoResolvePoison(/*Add=*/false, /*NSW=*/false, /*NUW=*/true, RHS, LHS);
  KnownBits SubDiff = Diff0;
  if(SubDiff.hasConflict())
    SubDiff = Diff1
  elif(!Diff1.hasConflict())
   SubDiff = SubDiff.intersectWith(Diff1)
  assert(!SubDiff.hasConflict());

Take the cases you have above.

In the LHS - RHS case, since we have NUW, we will deduce the signbit as leading 1s in RHS always imply zero (or poison).
In the RHS-LHS case, RHS.maxValue() - LHS.minValue() also underflows the signbit.

[aamod-wick]

Id like to try to fix it . Can this be assigned to me ?

[aamod-wick]

@goldsteinn i do have some doubts in this approach .if we do set NUW flag then how would we be resolving poison /conflicts. for the given test cases setting NUW flag in computeForAddSub with its current implementation should work right (though
it doesnt)?

[goldsteinn]

@goldsteinn i do have some doubts in this approach .if we do set NUW flag then how would we be resolving poison /conflicts. for the given test cases setting NUW flag in computeForAddSub with its current implementation should work right (though it doesnt)?

So with the NUW flag, poison inputs generate conflicts (same bitpos known zero/one). In computeForAddSub we currently handle conflicts by setting the output to zero.

How I would suggest proceeding is to move the core logic of computeForAddSub to a helper that does not resolve
conflicts to zero.

Then in computeForAddSub just call the helper and if the result has conflicts, set the result to zero.

In your code you can then check conflict to see if a result is usable.