[llvm] Add KnownBits implementations for avgFloor and avgCeil #86445

changkhothuychung · 2024-03-24T17:55:49Z

This PR is to address the issue #84640

llvmbot · 2024-03-24T17:56:17Z

@llvm/pr-subscribers-llvm-selectiondag

@llvm/pr-subscribers-llvm-support

Author: Nhat Nguyen (changkhothuychung)

Changes

This PR is to address the issue #84640

Full diff: https://github.com/llvm/llvm-project/pull/86445.diff

1 Files Affected:

(modified) llvm/lib/Support/KnownBits.cpp (+40)

diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp
index d72355dab6f1d3..07c7ad0882387a 100644
--- a/llvm/lib/Support/KnownBits.cpp
+++ b/llvm/lib/Support/KnownBits.cpp
@@ -762,6 +762,46 @@ KnownBits KnownBits::usub_sat(const KnownBits &LHS, const KnownBits &RHS) {
   return computeForSatAddSub(/*Add*/ false, /*Signed*/ false, LHS, RHS);
 }
 
+KnownBits KnownBits::avgFloorS(const KnownBits &LHS, const KnownBits &RHS) {
+  // (C1 & C2) + (C1 ^ C2).ashr(1)
+  KnownBits andResult = LHS & RHS;
+  KnownBits xorResult = LHS ^ RHS;
+  xorResult.Zero.ashrInPlace(1);
+  xorResult.One.ashrInPlace(1);
+  return computeForSatAddSub(/*Add*/ true, /*Signed*/ true, andResult,
+                             xorResult);
+}
+
+KnownBits KnownBits::avgFloorU(const KnownBits &LHS, const KnownBits &RHS) {
+  // (C1 & C2) + (C1 ^ C2).lshr(1)
+  KnownBits andResult = LHS & RHS;
+  KnownBits xorResult = LHS ^ RHS;
+  xorResult.Zero.lshrInPlace(1);
+  xorResult.One.lshrInPlace(1);
+  return computeForSatAddSub(/*Add*/ true, /*Signed*/ false, andResult,
+                             xorResult);
+}
+
+KnownBits KnownBits::avgCeilS(const KnownBits &LHS, const KnownBits &RHS) {
+  // (C1 | C2) - (C1 ^ C2).ashr(1)
+  KnownBits andResult = LHS & RHS;
+  KnownBits xorResult = LHS ^ RHS;
+  xorResult.Zero.ashrInPlace(1);
+  xorResult.One.ashrInPlace(1);
+  return computeForSatAddSub(/*Add*/ false, /*Signed*/ true, andResult,
+                             xorResult);
+}
+
+KnownBits KnownBits::avgCeilU(const KnownBits &LHS, const KnownBits &RHS) {
+  // (C1 | C2) - (C1 ^ C2).lshr(1)
+  KnownBits andResult = LHS & RHS;
+  KnownBits xorResult = LHS ^ RHS;
+  xorResult.Zero.lshrInPlace(1);
+  xorResult.One.lshrInPlace(1);
+  return computeForSatAddSub(/*Add*/ false, /*Signed*/ false, andResult,
+                             xorResult);
+}
+
 KnownBits KnownBits::mul(const KnownBits &LHS, const KnownBits &RHS,
                          bool NoUndefSelfMultiply) {
   unsigned BitWidth = LHS.getBitWidth();

github-actions · 2024-03-24T17:58:47Z

✅ With the latest revision this PR passed the Python code formatter.

github-actions · 2024-03-24T17:58:47Z

✅ With the latest revision this PR passed the C/C++ code formatter.

changkhothuychung · 2024-03-24T18:34:53Z

@RKSimon RkSim
What type of test should I add, should it be similar to this test ?

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

Lines 834 to 848 in ffe4181

    
           TEST(KnownBitsTest, CommonBitsSet) { 
        
             unsigned Bits = 4; 
        
             ForeachKnownBits(Bits, [&](const KnownBits &Known1) { 
        
               ForeachKnownBits(Bits, [&](const KnownBits &Known2) { 
        
                 bool HasCommonBitsSet = false; 
        
                 ForeachNumInKnownBits(Known1, [&](const APInt &N1) { 
        
                   ForeachNumInKnownBits(Known2, [&](const APInt &N2) { 
        
                     HasCommonBitsSet |= N1.intersects(N2); 
        
                   }); 
        
                 }); 
        
                 EXPECT_EQ(!HasCommonBitsSet, 
        
                           KnownBits::haveNoCommonBitsSet(Known1, Known2)); 
        
               }); 
        
             }); 
        
           }

changkhothuychung · 2024-03-30T18:15:59Z

@RKSimon Rkso
just following up on this!

goldsteinn · 2024-04-01T16:23:18Z

@RKSimon RkSim What type of test should I add, should it be similar to this test ?

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

Lines 834 to 848 in ffe4181

TEST(KnownBitsTest, CommonBitsSet) {

unsigned Bits = 4;

ForeachKnownBits(Bits, [&](const KnownBits &Known1) {

ForeachKnownBits(Bits, [&](const KnownBits &Known2) {

bool HasCommonBitsSet = false;

ForeachNumInKnownBits(Known1, [&](const APInt &N1) {

ForeachNumInKnownBits(Known2, [&](const APInt &N2) {

HasCommonBitsSet |= N1.intersects(N2);

});

});

EXPECT_EQ(!HasCommonBitsSet,

KnownBits::haveNoCommonBitsSet(Known1, Known2));

});

});

}

Your unit tests should look something like:

  testBinaryOpExhaustive(KnownBits::abds, APIntOps::abds,
                         checkCorrectnessOnlyBinary);

The first argument is a function pointer to the knownbits function we are testing.
The second argument is a function pointer to the reference implementation on an APInt.
edit: both of the function pointers can be lambda's i.e:

  testBinaryOpExhaustive(
      [](const KnownBits &Known1, const KnownBits &Known2) {
        return KnownBits::udiv(Known1, Known2);
      },
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
        if (N2.isZero())
          return std::nullopt;
        return N1.udiv(N2);
      },
      checkCorrectnessOnlyBinary);

The third is optional. If your implementation is complete (i.e proves all knowable bits) you can
drop it, otherwise just use what you see above. We like to strive for exhaustive, so if yours is not,
can you provide a few values that is fails for and explain a bit why its not really feasible?

llvm/lib/Support/KnownBits.cpp

llvm/include/llvm/Support/KnownBits.h

RKSimon

#86754 has now landed so please can you update the SelectionDAG::computeKnownBits AVG cases to use KnowBits implementations

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

llvm/lib/Support/KnownBits.cpp

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

llvm/unittests/Support/KnownBitsTest.cpp

RKSimon

Please address the KnownBitsTests failures

llvm/lib/Support/KnownBits.cpp

jayfoad · 2024-04-08T03:57:04Z

llvm/lib/Support/KnownBits.cpp

+
+KnownBits KnownBits::avgCeilS(const KnownBits &LHS, const KnownBits &RHS) {
+  // (C1 | C2) - (C1 ^ C2).ashr(1)
+  KnownBits andResult = LHS | RHS;


Change name to OrResult. Variable names should be capitalised throughout.

jayfoad · 2024-04-08T03:58:15Z

llvm/include/llvm/Support/KnownBits.h

+  /// Compute knownbits resulting from APIntOps::avgFloorU
+  static KnownBits avgFloorU(const KnownBits &LHS, const KnownBits &RHS);
+
+  /// Compute knownbits resulting from APIntOps::avgCelS


Typo "Cel" here and below

avgCel -> avgCeil

llvm/include/llvm/Support/KnownBits.h

llvm/lib/Support/KnownBits.cpp

llvm/unittests/Support/KnownBitsTest.cpp

jayfoad

This looks good to me now except for the remaining cosmetic issues.

llvm/lib/Support/KnownBits.cpp

goldsteinn · 2024-05-17T15:32:39Z

This LGTM, wait one 1 more approval to push.

jayfoad · 2024-05-17T15:48:06Z

llvm/lib/Support/KnownBits.cpp

@@ -475,7 +475,7 @@ KnownBits KnownBits::ashr(const KnownBits &LHS, const KnownBits &RHS,
  Known.Zero.setAllBits();
  Known.One.setAllBits();
  for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;
-      ++ShiftAmt) {
+       ++ShiftAmt) {


This looks like spurious reformatting.

changkhothuychung · 2024-05-17T16:01:23Z

@jayfoad f
looks like the BinaryExhaustive test fails when I remove the bool flag to enable Optimal check?

Link to failed CI: https://buildkite.com/llvm-project/github-pull-requests/builds/65024#018f86e0-35f7-4c66-bb68-14cd36220d70

jayfoad · 2024-05-17T16:06:15Z

looks like the BinaryExhaustive test fails when I remove the bool flag to enable Optimal check?

Oh, I thought this implementation was supposed to be optimal, but maybe I got that wrong.

Patch LGTM anyway.

jayfoad · 2024-05-17T16:18:32Z

looks like the BinaryExhaustive test fails when I remove the bool flag to enable Optimal check?

Oh, I thought this implementation was supposed to be optimal, but maybe I got that wrong.

Having looked into it, the unsigned functions are optimal. The signed ones are not because LHS/RHS.sext(BitWidth + 1) does not preserve the knowledge that the top two bits are the same.

We can look into improving that later. For now, it's fine to commit the patch with optimality checking removed.

changkhothuychung · 2024-05-18T22:05:37Z

looks like the BinaryExhaustive test fails when I remove the bool flag to enable Optimal check?

Oh, I thought this implementation was supposed to be optimal, but maybe I got that wrong.

Patch LGTM anyway.

I am assuming I need to put back the flag to disable optimality check ?

goldsteinn · 2024-05-19T00:48:01Z

looks like the BinaryExhaustive test fails when I remove the bool flag to enable Optimal check?

Oh, I thought this implementation was supposed to be optimal, but maybe I got that wrong.
Patch LGTM anyway.

I am assuming I need to put back the flag to disable optimality check ?

You already do. Its the bool argument.

jayfoad · 2024-05-19T07:31:14Z

looks like the BinaryExhaustive test fails when I remove the bool flag to enable Optimal check?

Oh, I thought this implementation was supposed to be optimal, but maybe I got that wrong.

Patch LGTM anyway.

I am assuming I need to put back the flag to disable optimality check ?

Yes (at least for the signed functions CeilS and FloorS) because you can't commit with failing tests.

RKSimon

LGTM

changkhothuychung · 2024-05-19T13:49:50Z

looks like the BinaryExhaustive test fails when I remove the bool flag to enable Optimal check?

Oh, I thought this implementation was supposed to be optimal, but maybe I got that wrong.
Patch LGTM anyway.

I am assuming I need to put back the flag to disable optimality check ?

You already do. Its the bool argument.

I made a push to put it back after I made that comment.

changkhothuychung · 2024-05-19T13:50:25Z

Thanks everyon! looks like I got 2 approves already, I will merge this PR shortly if there is no other concern.

changkhothuychung · 2024-05-19T20:12:23Z

@RKSimon RK
it looks like there is a failed build in later stages after the PR was merged - https://lab.llvm.org/buildbot/#/builders/185/builds/6813

Should we revert the changes?

RKSimon · 2024-05-19T20:32:42Z

wait until the current build has finished to see if it was an intermittent fail

initial attempt

e447f4c

llvmbot added the llvm:support label Mar 24, 2024

add definitions to header file

8b6e8bb

RKSimon requested review from jayfoad, RKSimon and goldsteinn April 1, 2024 09:48

goldsteinn reviewed Apr 1, 2024

View reviewed changes

llvm/lib/Support/KnownBits.cpp Show resolved Hide resolved

jayfoad reviewed Apr 2, 2024

View reviewed changes

llvm/include/llvm/Support/KnownBits.h Outdated Show resolved Hide resolved

RKSimon requested changes Apr 2, 2024

View reviewed changes

changkhothuychung added 2 commits April 4, 2024 18:09

Merge branch 'main' into knownbits_impl

f7eff4e

fix comments

b0d8100

llvmbot added the llvm:SelectionDAG SelectionDAGISel as well label Apr 5, 2024

goldsteinn reviewed Apr 5, 2024

View reviewed changes

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp Outdated Show resolved Hide resolved

goldsteinn reviewed Apr 5, 2024

View reviewed changes

llvm/lib/Support/KnownBits.cpp Outdated Show resolved Hide resolved

changkhothuychung added 2 commits April 4, 2024 21:19

add tests

ba43d22

remove opcode check

af3a08c

jayfoad reviewed Apr 5, 2024

View reviewed changes

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp Outdated Show resolved Hide resolved

RKSimon reviewed Apr 5, 2024

View reviewed changes

llvm/unittests/Support/KnownBitsTest.cpp Outdated Show resolved Hide resolved

fix test

d5ded0e

RKSimon requested changes Apr 7, 2024

View reviewed changes

fix or operation

e9c8c6c

RKSimon reviewed Apr 8, 2024

View reviewed changes

llvm/lib/Support/KnownBits.cpp Outdated Show resolved Hide resolved

llvm/lib/Support/KnownBits.cpp Outdated Show resolved Hide resolved

fix variable name

529ebe7

jayfoad reviewed Apr 8, 2024

View reviewed changes

changkhothuychung added 4 commits May 17, 2024 00:01

syntax fix

10de0a1

syntax fix

69c1a37

syntax fix

99e179a

some fix

ab00768

jayfoad reviewed May 17, 2024

View reviewed changes

changkhothuychung added 3 commits May 17, 2024 09:02

some fix

d230997

revert

eca6944

make test optimal

2cd048c

jayfoad reviewed May 17, 2024

View reviewed changes

llvm/lib/Support/KnownBits.cpp Show resolved Hide resolved

llvm/lib/Support/KnownBits.cpp Outdated Show resolved Hide resolved

add avgCeilU back

3ae62ff

jayfoad reviewed May 17, 2024

View reviewed changes

changkhothuychung added 2 commits May 17, 2024 12:03

remove spurious reformat

667c7af

remove spurious reformat

44c0b92

jayfoad approved these changes May 17, 2024

View reviewed changes

disable optimality check

22b2aa9

RKSimon approved these changes May 19, 2024

View reviewed changes

changkhothuychung merged commit eab92cb into llvm:main May 19, 2024
4 checks passed

PeddleSpam mentioned this pull request May 20, 2024

[AMDGPU] Fix error in #88512. #92770

Merged

RKSimon mentioned this pull request May 20, 2024

[Support] Add KnownBits implementations for avgFloor and avgCeil #84640

Open

3 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[llvm] Add KnownBits implementations for avgFloor and avgCeil #86445

[llvm] Add KnownBits implementations for avgFloor and avgCeil #86445

changkhothuychung commented Mar 24, 2024

llvmbot commented Mar 24, 2024 •

edited

github-actions bot commented Mar 24, 2024

github-actions bot commented Mar 24, 2024 •

edited

changkhothuychung commented Mar 24, 2024

changkhothuychung commented Mar 30, 2024

goldsteinn commented Apr 1, 2024 •

edited

RKSimon left a comment

RKSimon left a comment

jayfoad Apr 8, 2024

jayfoad Apr 8, 2024

RKSimon May 13, 2024

jayfoad left a comment

goldsteinn commented May 17, 2024

jayfoad May 17, 2024

changkhothuychung commented May 17, 2024 •

edited

jayfoad commented May 17, 2024

jayfoad commented May 17, 2024

changkhothuychung commented May 18, 2024

goldsteinn commented May 19, 2024

jayfoad commented May 19, 2024

RKSimon left a comment

changkhothuychung commented May 19, 2024

changkhothuychung commented May 19, 2024

changkhothuychung commented May 19, 2024

RKSimon commented May 19, 2024

[llvm] Add KnownBits implementations for avgFloor and avgCeil #86445

[llvm] Add KnownBits implementations for avgFloor and avgCeil #86445

Conversation

changkhothuychung commented Mar 24, 2024

llvmbot commented Mar 24, 2024 • edited

github-actions bot commented Mar 24, 2024

github-actions bot commented Mar 24, 2024 • edited

changkhothuychung commented Mar 24, 2024

changkhothuychung commented Mar 30, 2024

goldsteinn commented Apr 1, 2024 • edited

RKSimon left a comment

Choose a reason for hiding this comment

RKSimon left a comment

Choose a reason for hiding this comment

jayfoad Apr 8, 2024

Choose a reason for hiding this comment

jayfoad Apr 8, 2024

Choose a reason for hiding this comment

RKSimon May 13, 2024

Choose a reason for hiding this comment

jayfoad left a comment

Choose a reason for hiding this comment

goldsteinn commented May 17, 2024

jayfoad May 17, 2024

Choose a reason for hiding this comment

changkhothuychung commented May 17, 2024 • edited

jayfoad commented May 17, 2024

jayfoad commented May 17, 2024

changkhothuychung commented May 18, 2024

goldsteinn commented May 19, 2024

jayfoad commented May 19, 2024

RKSimon left a comment

Choose a reason for hiding this comment

changkhothuychung commented May 19, 2024

changkhothuychung commented May 19, 2024

changkhothuychung commented May 19, 2024

RKSimon commented May 19, 2024

llvmbot commented Mar 24, 2024 •

edited

github-actions bot commented Mar 24, 2024 •

edited

goldsteinn commented Apr 1, 2024 •

edited

changkhothuychung commented May 17, 2024 •

edited