[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-10-10 Thread Simon Pilgrim via cfe-commits 


@@ -332,6 +332,10 @@ struct KnownBits {
   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits ,
 KnownBits RHS);
 
+  /// Compute known bits results from subtracting RHS from LHS.

RKSimon wrote:

Add to comment "and a 1-bit borrow"

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-10-10 Thread Christian Kissig via cfe-commits 


@@ -3764,14 +3768,11 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 if (Opcode == ISD::ADDE)
   // Can't track carry from glue, set carry to unknown.
   Carry.resetAll();
-else if (Opcode == ISD::UADDO_CARRY || Opcode == ISD::SADDO_CARRY)
-  // TODO: Compute known bits for the carry operand. Not sure if it is 
worth
-  // the trouble (how often will we find a known carry bit). And I haven't
-  // tested this very much yet, but something like this might work:
-  //   Carry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
-  //   Carry = Carry.zextOrTrunc(1, false);
-  Carry.resetAll();
-else
+else if (Opcode == ISD::UADDO_CARRY || Opcode == ISD::SADDO_CARRY) {
+  Carry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
+  // Carry has bit width 1
+  Carry = Carry.zextOrTrunc(1);
+} else

christiankissig wrote:

Done

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-10-10 Thread Christian Kissig via cfe-commits 


@@ -3764,14 +3768,11 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 if (Opcode == ISD::ADDE)
   // Can't track carry from glue, set carry to unknown.
   Carry.resetAll();
-else if (Opcode == ISD::UADDO_CARRY || Opcode == ISD::SADDO_CARRY)
-  // TODO: Compute known bits for the carry operand. Not sure if it is 
worth
-  // the trouble (how often will we find a known carry bit). And I haven't
-  // tested this very much yet, but something like this might work:
-  //   Carry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
-  //   Carry = Carry.zextOrTrunc(1, false);
-  Carry.resetAll();
-else
+else if (Opcode == ISD::UADDO_CARRY || Opcode == ISD::SADDO_CARRY) {
+  Carry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
+  // Carry has bit width 1
+  Carry = Carry.zextOrTrunc(1);

christiankissig wrote:

Done

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-10-09 Thread Christian Kissig via cfe-commits 

https://github.com/christiankissig updated 
https://github.com/llvm/llvm-project/pull/67788

>From 5d86936c3a48c613460983c980271fcab8128b75 Mon Sep 17 00:00:00 2001
From: Christian Kissig 
Date: Tue, 26 Sep 2023 12:18:59 +
Subject: [PATCH 1/6] [Support] Add KnownBits::computeForSubBorrow

* Implements computeForSubBorrow as alias for computeforAddCarry. Borrow
  is expected to be 1-bit wide.
* Adds exhaustive unit test.
---
 llvm/include/llvm/Support/KnownBits.h|  4 +++
 llvm/lib/Support/KnownBits.cpp   | 12 +
 llvm/unittests/Support/KnownBitsTest.cpp | 31 
 3 files changed, 47 insertions(+)

diff --git a/llvm/include/llvm/Support/KnownBits.h 
b/llvm/include/llvm/Support/KnownBits.h
index 8462aa11202d5d7..711ca8c12129a1b 100644
--- a/llvm/include/llvm/Support/KnownBits.h
+++ b/llvm/include/llvm/Support/KnownBits.h
@@ -332,6 +332,10 @@ struct KnownBits {
   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits ,
 KnownBits RHS);
 
+  /// Compute known bits results from subtracting RHS from LHS.
+  static KnownBits computeForSubBorrow(const KnownBits , KnownBits RHS,
+   const KnownBits );
+
   /// Compute knownbits resulting from llvm.sadd.sat(LHS, RHS)
   static KnownBits sadd_sat(const KnownBits , const KnownBits );
 
diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp
index 097c22d33dd12ba..99ac50a34666fce 100644
--- a/llvm/lib/Support/KnownBits.cpp
+++ b/llvm/lib/Support/KnownBits.cpp
@@ -85,6 +85,18 @@ KnownBits KnownBits::computeForAddSub(bool Add, bool NSW,
   return KnownOut;
 }
 
+KnownBits KnownBits::computeForSubBorrow(const KnownBits , KnownBits RHS,
+ const KnownBits ) {
+  assert(Borrow.getBitWidth() == 1 && "Borrow must be 1-bit");
+
+  // LHS - RHS = LHS + ~RHS + 1
+  // Carry 1 - Borrow in ::computeForAddCarry
+  std::swap(RHS.Zero, RHS.One);
+  return ::computeForAddCarry(LHS, RHS,
+  /*CarryZero*/ Borrow.One.getBoolValue(),
+  /*CarryOne*/ Borrow.Zero.getBoolValue());
+}
+
 KnownBits KnownBits::sextInReg(unsigned SrcBitWidth) const {
   unsigned BitWidth = getBitWidth();
   assert(0 < SrcBitWidth && SrcBitWidth <= BitWidth &&
diff --git a/llvm/unittests/Support/KnownBitsTest.cpp 
b/llvm/unittests/Support/KnownBitsTest.cpp
index 9d184beea3ba9e9..5597d69ab248d23 100644
--- a/llvm/unittests/Support/KnownBitsTest.cpp
+++ b/llvm/unittests/Support/KnownBitsTest.cpp
@@ -213,6 +213,37 @@ TEST(KnownBitsTest, AddSubExhaustive) {
   TestAddSubExhaustive(false);
 }
 
+TEST(KnownBitsTest, SubBorrowExhaustive) {
+  unsigned Bits = 4;
+  ForeachKnownBits(Bits, [&](const KnownBits ) {
+ForeachKnownBits(Bits, [&](const KnownBits ) {
+  ForeachKnownBits(1, [&](const KnownBits ) {
+// Explicitly compute known bits of the addition by trying all
+// possibilities.
+KnownBits Known(Bits);
+Known.Zero.setAllBits();
+Known.One.setAllBits();
+ForeachNumInKnownBits(Known1, [&](const APInt ) {
+  ForeachNumInKnownBits(Known2, [&](const APInt ) {
+ForeachNumInKnownBits(KnownBorrow, [&](const APInt ) {
+  APInt Sub = N1 - N2;
+  if (Borrow.getBoolValue())
+--Sub;
+
+  Known.One &= Sub;
+  Known.Zero &= ~Sub;
+});
+  });
+});
+
+KnownBits KnownComputed =
+KnownBits::computeForSubBorrow(Known1, Known2, KnownBorrow);
+EXPECT_EQ(Known, KnownComputed);
+  });
+});
+  });
+}
+
 TEST(KnownBitsTest, BinaryExhaustive) {
   testBinaryOpExhaustive(
   [](const KnownBits , const KnownBits ) {

>From f84c882cf429df238054d88ee07e41a08ae3fd6c Mon Sep 17 00:00:00 2001
From: Christian Kissig 
Date: Tue, 26 Sep 2023 18:02:49 +
Subject: [PATCH 2/6] [CodeGen] Implement USUBC, USUBO_CARRY, and SSUBO_CARRY
 with KnownBits::computeForSubBorrow

---
 .../lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 12 ++
 .../CodeGen/AArch64SelectionDAGTest.cpp   | 24 +++
 2 files changed, 32 insertions(+), 4 deletions(-)

diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp 
b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index cd21af770e1a4d9..ab3e9b4bdc67402 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -3732,14 +3732,18 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 assert(Op.getResNo() == 0 &&
"We only compute knownbits for the difference here.");
 
-// TODO: Compute influence of the carry operand.
+// With UADDO_CARRY and SSUBO_CARRY a borrow bit may be added in.
+KnownBits Borrow(1);
 if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY)
-  break;
+  // TODO: Compute known bits for the carry operand. Creates
+

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-10-09 Thread Christian Kissig via cfe-commits 

https://github.com/christiankissig updated 
https://github.com/llvm/llvm-project/pull/67788

>From 5d86936c3a48c613460983c980271fcab8128b75 Mon Sep 17 00:00:00 2001
From: Christian Kissig 
Date: Tue, 26 Sep 2023 12:18:59 +
Subject: [PATCH 1/5] [Support] Add KnownBits::computeForSubBorrow

* Implements computeForSubBorrow as alias for computeforAddCarry. Borrow
  is expected to be 1-bit wide.
* Adds exhaustive unit test.
---
 llvm/include/llvm/Support/KnownBits.h|  4 +++
 llvm/lib/Support/KnownBits.cpp   | 12 +
 llvm/unittests/Support/KnownBitsTest.cpp | 31 
 3 files changed, 47 insertions(+)

diff --git a/llvm/include/llvm/Support/KnownBits.h 
b/llvm/include/llvm/Support/KnownBits.h
index 8462aa11202d5d7..711ca8c12129a1b 100644
--- a/llvm/include/llvm/Support/KnownBits.h
+++ b/llvm/include/llvm/Support/KnownBits.h
@@ -332,6 +332,10 @@ struct KnownBits {
   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits ,
 KnownBits RHS);
 
+  /// Compute known bits results from subtracting RHS from LHS.
+  static KnownBits computeForSubBorrow(const KnownBits , KnownBits RHS,
+   const KnownBits );
+
   /// Compute knownbits resulting from llvm.sadd.sat(LHS, RHS)
   static KnownBits sadd_sat(const KnownBits , const KnownBits );
 
diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp
index 097c22d33dd12ba..99ac50a34666fce 100644
--- a/llvm/lib/Support/KnownBits.cpp
+++ b/llvm/lib/Support/KnownBits.cpp
@@ -85,6 +85,18 @@ KnownBits KnownBits::computeForAddSub(bool Add, bool NSW,
   return KnownOut;
 }
 
+KnownBits KnownBits::computeForSubBorrow(const KnownBits , KnownBits RHS,
+ const KnownBits ) {
+  assert(Borrow.getBitWidth() == 1 && "Borrow must be 1-bit");
+
+  // LHS - RHS = LHS + ~RHS + 1
+  // Carry 1 - Borrow in ::computeForAddCarry
+  std::swap(RHS.Zero, RHS.One);
+  return ::computeForAddCarry(LHS, RHS,
+  /*CarryZero*/ Borrow.One.getBoolValue(),
+  /*CarryOne*/ Borrow.Zero.getBoolValue());
+}
+
 KnownBits KnownBits::sextInReg(unsigned SrcBitWidth) const {
   unsigned BitWidth = getBitWidth();
   assert(0 < SrcBitWidth && SrcBitWidth <= BitWidth &&
diff --git a/llvm/unittests/Support/KnownBitsTest.cpp 
b/llvm/unittests/Support/KnownBitsTest.cpp
index 9d184beea3ba9e9..5597d69ab248d23 100644
--- a/llvm/unittests/Support/KnownBitsTest.cpp
+++ b/llvm/unittests/Support/KnownBitsTest.cpp
@@ -213,6 +213,37 @@ TEST(KnownBitsTest, AddSubExhaustive) {
   TestAddSubExhaustive(false);
 }
 
+TEST(KnownBitsTest, SubBorrowExhaustive) {
+  unsigned Bits = 4;
+  ForeachKnownBits(Bits, [&](const KnownBits ) {
+ForeachKnownBits(Bits, [&](const KnownBits ) {
+  ForeachKnownBits(1, [&](const KnownBits ) {
+// Explicitly compute known bits of the addition by trying all
+// possibilities.
+KnownBits Known(Bits);
+Known.Zero.setAllBits();
+Known.One.setAllBits();
+ForeachNumInKnownBits(Known1, [&](const APInt ) {
+  ForeachNumInKnownBits(Known2, [&](const APInt ) {
+ForeachNumInKnownBits(KnownBorrow, [&](const APInt ) {
+  APInt Sub = N1 - N2;
+  if (Borrow.getBoolValue())
+--Sub;
+
+  Known.One &= Sub;
+  Known.Zero &= ~Sub;
+});
+  });
+});
+
+KnownBits KnownComputed =
+KnownBits::computeForSubBorrow(Known1, Known2, KnownBorrow);
+EXPECT_EQ(Known, KnownComputed);
+  });
+});
+  });
+}
+
 TEST(KnownBitsTest, BinaryExhaustive) {
   testBinaryOpExhaustive(
   [](const KnownBits , const KnownBits ) {

>From f84c882cf429df238054d88ee07e41a08ae3fd6c Mon Sep 17 00:00:00 2001
From: Christian Kissig 
Date: Tue, 26 Sep 2023 18:02:49 +
Subject: [PATCH 2/5] [CodeGen] Implement USUBC, USUBO_CARRY, and SSUBO_CARRY
 with KnownBits::computeForSubBorrow

---
 .../lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 12 ++
 .../CodeGen/AArch64SelectionDAGTest.cpp   | 24 +++
 2 files changed, 32 insertions(+), 4 deletions(-)

diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp 
b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index cd21af770e1a4d9..ab3e9b4bdc67402 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -3732,14 +3732,18 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 assert(Op.getResNo() == 0 &&
"We only compute knownbits for the difference here.");
 
-// TODO: Compute influence of the carry operand.
+// With UADDO_CARRY and SSUBO_CARRY a borrow bit may be added in.
+KnownBits Borrow(1);
 if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY)
-  break;
+  // TODO: Compute known bits for the carry operand. Creates
+

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-10-09 Thread Denali Lumma via cfe-commits 

dlumma wrote:

It seems like this PR is ready to land. Any reason why it has not been 
integrated @christiankissig ?

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-10-05 Thread Christian Kissig via cfe-commits 

https://github.com/christiankissig updated 
https://github.com/llvm/llvm-project/pull/67788

>From 5d86936c3a48c613460983c980271fcab8128b75 Mon Sep 17 00:00:00 2001
From: Christian Kissig 
Date: Tue, 26 Sep 2023 12:18:59 +
Subject: [PATCH 1/5] [Support] Add KnownBits::computeForSubBorrow

* Implements computeForSubBorrow as alias for computeforAddCarry. Borrow
  is expected to be 1-bit wide.
* Adds exhaustive unit test.
---
 llvm/include/llvm/Support/KnownBits.h|  4 +++
 llvm/lib/Support/KnownBits.cpp   | 12 +
 llvm/unittests/Support/KnownBitsTest.cpp | 31 
 3 files changed, 47 insertions(+)

diff --git a/llvm/include/llvm/Support/KnownBits.h 
b/llvm/include/llvm/Support/KnownBits.h
index 8462aa11202d5d7..711ca8c12129a1b 100644
--- a/llvm/include/llvm/Support/KnownBits.h
+++ b/llvm/include/llvm/Support/KnownBits.h
@@ -332,6 +332,10 @@ struct KnownBits {
   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits ,
 KnownBits RHS);
 
+  /// Compute known bits results from subtracting RHS from LHS.
+  static KnownBits computeForSubBorrow(const KnownBits , KnownBits RHS,
+   const KnownBits );
+
   /// Compute knownbits resulting from llvm.sadd.sat(LHS, RHS)
   static KnownBits sadd_sat(const KnownBits , const KnownBits );
 
diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp
index 097c22d33dd12ba..99ac50a34666fce 100644
--- a/llvm/lib/Support/KnownBits.cpp
+++ b/llvm/lib/Support/KnownBits.cpp
@@ -85,6 +85,18 @@ KnownBits KnownBits::computeForAddSub(bool Add, bool NSW,
   return KnownOut;
 }
 
+KnownBits KnownBits::computeForSubBorrow(const KnownBits , KnownBits RHS,
+ const KnownBits ) {
+  assert(Borrow.getBitWidth() == 1 && "Borrow must be 1-bit");
+
+  // LHS - RHS = LHS + ~RHS + 1
+  // Carry 1 - Borrow in ::computeForAddCarry
+  std::swap(RHS.Zero, RHS.One);
+  return ::computeForAddCarry(LHS, RHS,
+  /*CarryZero*/ Borrow.One.getBoolValue(),
+  /*CarryOne*/ Borrow.Zero.getBoolValue());
+}
+
 KnownBits KnownBits::sextInReg(unsigned SrcBitWidth) const {
   unsigned BitWidth = getBitWidth();
   assert(0 < SrcBitWidth && SrcBitWidth <= BitWidth &&
diff --git a/llvm/unittests/Support/KnownBitsTest.cpp 
b/llvm/unittests/Support/KnownBitsTest.cpp
index 9d184beea3ba9e9..5597d69ab248d23 100644
--- a/llvm/unittests/Support/KnownBitsTest.cpp
+++ b/llvm/unittests/Support/KnownBitsTest.cpp
@@ -213,6 +213,37 @@ TEST(KnownBitsTest, AddSubExhaustive) {
   TestAddSubExhaustive(false);
 }
 
+TEST(KnownBitsTest, SubBorrowExhaustive) {
+  unsigned Bits = 4;
+  ForeachKnownBits(Bits, [&](const KnownBits ) {
+ForeachKnownBits(Bits, [&](const KnownBits ) {
+  ForeachKnownBits(1, [&](const KnownBits ) {
+// Explicitly compute known bits of the addition by trying all
+// possibilities.
+KnownBits Known(Bits);
+Known.Zero.setAllBits();
+Known.One.setAllBits();
+ForeachNumInKnownBits(Known1, [&](const APInt ) {
+  ForeachNumInKnownBits(Known2, [&](const APInt ) {
+ForeachNumInKnownBits(KnownBorrow, [&](const APInt ) {
+  APInt Sub = N1 - N2;
+  if (Borrow.getBoolValue())
+--Sub;
+
+  Known.One &= Sub;
+  Known.Zero &= ~Sub;
+});
+  });
+});
+
+KnownBits KnownComputed =
+KnownBits::computeForSubBorrow(Known1, Known2, KnownBorrow);
+EXPECT_EQ(Known, KnownComputed);
+  });
+});
+  });
+}
+
 TEST(KnownBitsTest, BinaryExhaustive) {
   testBinaryOpExhaustive(
   [](const KnownBits , const KnownBits ) {

>From f84c882cf429df238054d88ee07e41a08ae3fd6c Mon Sep 17 00:00:00 2001
From: Christian Kissig 
Date: Tue, 26 Sep 2023 18:02:49 +
Subject: [PATCH 2/5] [CodeGen] Implement USUBC, USUBO_CARRY, and SSUBO_CARRY
 with KnownBits::computeForSubBorrow

---
 .../lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 12 ++
 .../CodeGen/AArch64SelectionDAGTest.cpp   | 24 +++
 2 files changed, 32 insertions(+), 4 deletions(-)

diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp 
b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index cd21af770e1a4d9..ab3e9b4bdc67402 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -3732,14 +3732,18 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 assert(Op.getResNo() == 0 &&
"We only compute knownbits for the difference here.");
 
-// TODO: Compute influence of the carry operand.
+// With UADDO_CARRY and SSUBO_CARRY a borrow bit may be added in.
+KnownBits Borrow(1);
 if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY)
-  break;
+  // TODO: Compute known bits for the carry operand. Creates
+

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-10-01 Thread Shafik Yaghmour via cfe-commits 

https://github.com/shafik edited https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-10-01 Thread Nikita Popov via cfe-commits 


@@ -3732,14 +3732,18 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 assert(Op.getResNo() == 0 &&
"We only compute knownbits for the difference here.");
 
-// TODO: Compute influence of the carry operand.
-if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY)
-  break;
+// With UADDO_CARRY and SSUBO_CARRY a borrow bit may be added in.
+KnownBits Borrow(1);
+if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY) {
+  Borrow = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
+  // Borrow has bit width 1
+  Borrow = Borrow.zextOrTrunc(1);

nikic wrote:

There are no zero-bit integers in SDAG (or IR). The use of zextOrTrunc in the 
comment probably dates back to the time when APInt did not allow 
zext/sext/trunc to the original bit width.

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-10-01 Thread Christian Kissig via cfe-commits 

https://github.com/christiankissig updated 
https://github.com/llvm/llvm-project/pull/67788

>From 5d86936c3a48c613460983c980271fcab8128b75 Mon Sep 17 00:00:00 2001
From: Christian Kissig 
Date: Tue, 26 Sep 2023 12:18:59 +
Subject: [PATCH 1/5] [Support] Add KnownBits::computeForSubBorrow

* Implements computeForSubBorrow as alias for computeforAddCarry. Borrow
  is expected to be 1-bit wide.
* Adds exhaustive unit test.
---
 llvm/include/llvm/Support/KnownBits.h|  4 +++
 llvm/lib/Support/KnownBits.cpp   | 12 +
 llvm/unittests/Support/KnownBitsTest.cpp | 31 
 3 files changed, 47 insertions(+)

diff --git a/llvm/include/llvm/Support/KnownBits.h 
b/llvm/include/llvm/Support/KnownBits.h
index 8462aa11202d5d7..711ca8c12129a1b 100644
--- a/llvm/include/llvm/Support/KnownBits.h
+++ b/llvm/include/llvm/Support/KnownBits.h
@@ -332,6 +332,10 @@ struct KnownBits {
   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits ,
 KnownBits RHS);
 
+  /// Compute known bits results from subtracting RHS from LHS.
+  static KnownBits computeForSubBorrow(const KnownBits , KnownBits RHS,
+   const KnownBits );
+
   /// Compute knownbits resulting from llvm.sadd.sat(LHS, RHS)
   static KnownBits sadd_sat(const KnownBits , const KnownBits );
 
diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp
index 097c22d33dd12ba..99ac50a34666fce 100644
--- a/llvm/lib/Support/KnownBits.cpp
+++ b/llvm/lib/Support/KnownBits.cpp
@@ -85,6 +85,18 @@ KnownBits KnownBits::computeForAddSub(bool Add, bool NSW,
   return KnownOut;
 }
 
+KnownBits KnownBits::computeForSubBorrow(const KnownBits , KnownBits RHS,
+ const KnownBits ) {
+  assert(Borrow.getBitWidth() == 1 && "Borrow must be 1-bit");
+
+  // LHS - RHS = LHS + ~RHS + 1
+  // Carry 1 - Borrow in ::computeForAddCarry
+  std::swap(RHS.Zero, RHS.One);
+  return ::computeForAddCarry(LHS, RHS,
+  /*CarryZero*/ Borrow.One.getBoolValue(),
+  /*CarryOne*/ Borrow.Zero.getBoolValue());
+}
+
 KnownBits KnownBits::sextInReg(unsigned SrcBitWidth) const {
   unsigned BitWidth = getBitWidth();
   assert(0 < SrcBitWidth && SrcBitWidth <= BitWidth &&
diff --git a/llvm/unittests/Support/KnownBitsTest.cpp 
b/llvm/unittests/Support/KnownBitsTest.cpp
index 9d184beea3ba9e9..5597d69ab248d23 100644
--- a/llvm/unittests/Support/KnownBitsTest.cpp
+++ b/llvm/unittests/Support/KnownBitsTest.cpp
@@ -213,6 +213,37 @@ TEST(KnownBitsTest, AddSubExhaustive) {
   TestAddSubExhaustive(false);
 }
 
+TEST(KnownBitsTest, SubBorrowExhaustive) {
+  unsigned Bits = 4;
+  ForeachKnownBits(Bits, [&](const KnownBits ) {
+ForeachKnownBits(Bits, [&](const KnownBits ) {
+  ForeachKnownBits(1, [&](const KnownBits ) {
+// Explicitly compute known bits of the addition by trying all
+// possibilities.
+KnownBits Known(Bits);
+Known.Zero.setAllBits();
+Known.One.setAllBits();
+ForeachNumInKnownBits(Known1, [&](const APInt ) {
+  ForeachNumInKnownBits(Known2, [&](const APInt ) {
+ForeachNumInKnownBits(KnownBorrow, [&](const APInt ) {
+  APInt Sub = N1 - N2;
+  if (Borrow.getBoolValue())
+--Sub;
+
+  Known.One &= Sub;
+  Known.Zero &= ~Sub;
+});
+  });
+});
+
+KnownBits KnownComputed =
+KnownBits::computeForSubBorrow(Known1, Known2, KnownBorrow);
+EXPECT_EQ(Known, KnownComputed);
+  });
+});
+  });
+}
+
 TEST(KnownBitsTest, BinaryExhaustive) {
   testBinaryOpExhaustive(
   [](const KnownBits , const KnownBits ) {

>From f84c882cf429df238054d88ee07e41a08ae3fd6c Mon Sep 17 00:00:00 2001
From: Christian Kissig 
Date: Tue, 26 Sep 2023 18:02:49 +
Subject: [PATCH 2/5] [CodeGen] Implement USUBC, USUBO_CARRY, and SSUBO_CARRY
 with KnownBits::computeForSubBorrow

---
 .../lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 12 ++
 .../CodeGen/AArch64SelectionDAGTest.cpp   | 24 +++
 2 files changed, 32 insertions(+), 4 deletions(-)

diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp 
b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index cd21af770e1a4d9..ab3e9b4bdc67402 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -3732,14 +3732,18 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 assert(Op.getResNo() == 0 &&
"We only compute knownbits for the difference here.");
 
-// TODO: Compute influence of the carry operand.
+// With UADDO_CARRY and SSUBO_CARRY a borrow bit may be added in.
+KnownBits Borrow(1);
 if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY)
-  break;
+  // TODO: Compute known bits for the carry operand. Creates
+

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-09-29 Thread Christian Kissig via cfe-commits 

christiankissig wrote:

> Might be nice to add a test where this actually shows up in CodeGen.

+1 Will look to add it with this change.

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-09-29 Thread Christian Kissig via cfe-commits 


@@ -3732,14 +3732,18 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 assert(Op.getResNo() == 0 &&
"We only compute knownbits for the difference here.");
 
-// TODO: Compute influence of the carry operand.
-if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY)
-  break;
+// With UADDO_CARRY and SSUBO_CARRY a borrow bit may be added in.
+KnownBits Borrow(1);
+if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY) {
+  Borrow = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
+  // Borrow has bit width 1
+  Borrow = Borrow.zextOrTrunc(1);

christiankissig wrote:

@nikic and @goldsteinn Probably just hypothetical, but I couldn't work out 
whether Operand 2 is always of non-zero bit width, so went with the original 
suggestion for ADD ops to use zextOrTrunc(). Will change to trunc() on both of 
your recommendation here.

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-09-29 Thread via cfe-commits 

goldsteinn wrote:

Might be nice to add a test where this actually shows up in CodeGen.

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-09-29 Thread via cfe-commits 


@@ -3764,14 +3768,11 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 if (Opcode == ISD::ADDE)
   // Can't track carry from glue, set carry to unknown.
   Carry.resetAll();
-else if (Opcode == ISD::UADDO_CARRY || Opcode == ISD::SADDO_CARRY)
-  // TODO: Compute known bits for the carry operand. Not sure if it is 
worth
-  // the trouble (how often will we find a known carry bit). And I haven't
-  // tested this very much yet, but something like this might work:
-  //   Carry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
-  //   Carry = Carry.zextOrTrunc(1, false);
-  Carry.resetAll();
-else
+else if (Opcode == ISD::UADDO_CARRY || Opcode == ISD::SADDO_CARRY) {
+  Carry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
+  // Carry has bit width 1
+  Carry = Carry.zextOrTrunc(1);
+} else

goldsteinn wrote:

likewise else style.

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-09-29 Thread via cfe-commits 


@@ -3764,14 +3768,11 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 if (Opcode == ISD::ADDE)
   // Can't track carry from glue, set carry to unknown.
   Carry.resetAll();
-else if (Opcode == ISD::UADDO_CARRY || Opcode == ISD::SADDO_CARRY)
-  // TODO: Compute known bits for the carry operand. Not sure if it is 
worth
-  // the trouble (how often will we find a known carry bit). And I haven't
-  // tested this very much yet, but something like this might work:
-  //   Carry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
-  //   Carry = Carry.zextOrTrunc(1, false);
-  Carry.resetAll();
-else
+else if (Opcode == ISD::UADDO_CARRY || Opcode == ISD::SADDO_CARRY) {
+  Carry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
+  // Carry has bit width 1
+  Carry = Carry.zextOrTrunc(1);

goldsteinn wrote:

Likewise just `trunc` here.

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-09-29 Thread via cfe-commits 


@@ -3732,14 +3732,18 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 assert(Op.getResNo() == 0 &&
"We only compute knownbits for the difference here.");
 
-// TODO: Compute influence of the carry operand.
-if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY)
-  break;
+// With UADDO_CARRY and SSUBO_CARRY a borrow bit may be added in.
+KnownBits Borrow(1);
+if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY) {
+  Borrow = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
+  // Borrow has bit width 1
+  Borrow = Borrow.zextOrTrunc(1);
+} else
+  Borrow.setAllZero();

goldsteinn wrote:

nit: braces around else block if braces around if block.

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-09-29 Thread Nikita Popov via cfe-commits 

https://github.com/nikic edited https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-09-29 Thread Nikita Popov via cfe-commits 


@@ -3732,14 +3732,18 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 assert(Op.getResNo() == 0 &&
"We only compute knownbits for the difference here.");
 
-// TODO: Compute influence of the carry operand.
-if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY)
-  break;
+// With UADDO_CARRY and SSUBO_CARRY a borrow bit may be added in.
+KnownBits Borrow(1);
+if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY) {
+  Borrow = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
+  // Borrow has bit width 1
+  Borrow = Borrow.zextOrTrunc(1);

nikic wrote:

Should be just trunc.

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-09-29 Thread Simon Pilgrim via cfe-commits 


@@ -213,6 +213,37 @@ TEST(KnownBitsTest, AddSubExhaustive) {
   TestAddSubExhaustive(false);
 }
 
+TEST(KnownBitsTest, SubBorrowExhaustive) {
+  unsigned Bits = 4;
+  ForeachKnownBits(Bits, [&](const KnownBits ) {
+ForeachKnownBits(Bits, [&](const KnownBits ) {
+  ForeachKnownBits(1, [&](const KnownBits ) {
+// Explicitly compute known bits of the addition by trying all

RKSimon wrote:

addition -> subtraction

https://github.com/llvm/llvm-project/pull/67788
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] [Support] Add KnownBits::computeForSubBorrow (PR #67788)

2023-09-29 Thread Christian Kissig via cfe-commits 

https://github.com/christiankissig created 
https://github.com/llvm/llvm-project/pull/67788

- [Support] Add KnownBits::computeForSubBorrow
- [CodeGen] Implement USUBC, USUBO_CARRY, and SSUBO_CARRY with 
KnownBits::computeForSubBorrow
- [CodeGen] Compute unknown bits for Carry/Borrow for ADD/SUB
- [CodeGen] Compute known bits of Carry/Borrow for UADDO, SADDO, USUBO, and 
SSUBO


>From 5d86936c3a48c613460983c980271fcab8128b75 Mon Sep 17 00:00:00 2001
From: Christian Kissig 
Date: Tue, 26 Sep 2023 12:18:59 +
Subject: [PATCH 1/4] [Support] Add KnownBits::computeForSubBorrow

* Implements computeForSubBorrow as alias for computeforAddCarry. Borrow
  is expected to be 1-bit wide.
* Adds exhaustive unit test.
---
 llvm/include/llvm/Support/KnownBits.h|  4 +++
 llvm/lib/Support/KnownBits.cpp   | 12 +
 llvm/unittests/Support/KnownBitsTest.cpp | 31 
 3 files changed, 47 insertions(+)

diff --git a/llvm/include/llvm/Support/KnownBits.h 
b/llvm/include/llvm/Support/KnownBits.h
index 8462aa11202d5d7..711ca8c12129a1b 100644
--- a/llvm/include/llvm/Support/KnownBits.h
+++ b/llvm/include/llvm/Support/KnownBits.h
@@ -332,6 +332,10 @@ struct KnownBits {
   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits ,
 KnownBits RHS);
 
+  /// Compute known bits results from subtracting RHS from LHS.
+  static KnownBits computeForSubBorrow(const KnownBits , KnownBits RHS,
+   const KnownBits );
+
   /// Compute knownbits resulting from llvm.sadd.sat(LHS, RHS)
   static KnownBits sadd_sat(const KnownBits , const KnownBits );
 
diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp
index 097c22d33dd12ba..99ac50a34666fce 100644
--- a/llvm/lib/Support/KnownBits.cpp
+++ b/llvm/lib/Support/KnownBits.cpp
@@ -85,6 +85,18 @@ KnownBits KnownBits::computeForAddSub(bool Add, bool NSW,
   return KnownOut;
 }
 
+KnownBits KnownBits::computeForSubBorrow(const KnownBits , KnownBits RHS,
+ const KnownBits ) {
+  assert(Borrow.getBitWidth() == 1 && "Borrow must be 1-bit");
+
+  // LHS - RHS = LHS + ~RHS + 1
+  // Carry 1 - Borrow in ::computeForAddCarry
+  std::swap(RHS.Zero, RHS.One);
+  return ::computeForAddCarry(LHS, RHS,
+  /*CarryZero*/ Borrow.One.getBoolValue(),
+  /*CarryOne*/ Borrow.Zero.getBoolValue());
+}
+
 KnownBits KnownBits::sextInReg(unsigned SrcBitWidth) const {
   unsigned BitWidth = getBitWidth();
   assert(0 < SrcBitWidth && SrcBitWidth <= BitWidth &&
diff --git a/llvm/unittests/Support/KnownBitsTest.cpp 
b/llvm/unittests/Support/KnownBitsTest.cpp
index 9d184beea3ba9e9..5597d69ab248d23 100644
--- a/llvm/unittests/Support/KnownBitsTest.cpp
+++ b/llvm/unittests/Support/KnownBitsTest.cpp
@@ -213,6 +213,37 @@ TEST(KnownBitsTest, AddSubExhaustive) {
   TestAddSubExhaustive(false);
 }
 
+TEST(KnownBitsTest, SubBorrowExhaustive) {
+  unsigned Bits = 4;
+  ForeachKnownBits(Bits, [&](const KnownBits ) {
+ForeachKnownBits(Bits, [&](const KnownBits ) {
+  ForeachKnownBits(1, [&](const KnownBits ) {
+// Explicitly compute known bits of the addition by trying all
+// possibilities.
+KnownBits Known(Bits);
+Known.Zero.setAllBits();
+Known.One.setAllBits();
+ForeachNumInKnownBits(Known1, [&](const APInt ) {
+  ForeachNumInKnownBits(Known2, [&](const APInt ) {
+ForeachNumInKnownBits(KnownBorrow, [&](const APInt ) {
+  APInt Sub = N1 - N2;
+  if (Borrow.getBoolValue())
+--Sub;
+
+  Known.One &= Sub;
+  Known.Zero &= ~Sub;
+});
+  });
+});
+
+KnownBits KnownComputed =
+KnownBits::computeForSubBorrow(Known1, Known2, KnownBorrow);
+EXPECT_EQ(Known, KnownComputed);
+  });
+});
+  });
+}
+
 TEST(KnownBitsTest, BinaryExhaustive) {
   testBinaryOpExhaustive(
   [](const KnownBits , const KnownBits ) {

>From f84c882cf429df238054d88ee07e41a08ae3fd6c Mon Sep 17 00:00:00 2001
From: Christian Kissig 
Date: Tue, 26 Sep 2023 18:02:49 +
Subject: [PATCH 2/4] [CodeGen] Implement USUBC, USUBO_CARRY, and SSUBO_CARRY
 with KnownBits::computeForSubBorrow

---
 .../lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 12 ++
 .../CodeGen/AArch64SelectionDAGTest.cpp   | 24 +++
 2 files changed, 32 insertions(+), 4 deletions(-)

diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp 
b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index cd21af770e1a4d9..ab3e9b4bdc67402 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -3732,14 +3732,18 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, 
const APInt ,
 assert(Op.getResNo() == 0 &&
"We only compute knownbits for the difference here.");
 
-// TODO: