[clang] ae76eb3 - [NFC][Clang][Pragma] Remove unused variables
Author: Senran Zhang
Date: 2022-04-24T14:50:59+08:00
New Revision: ae76eb32a5988c1f4ebb07e7e5eb9de2b036e194
URL:
https://github.com/llvm/llvm-project/commit/ae76eb32a5988c1f4ebb07e7e5eb9de2b036e194
DIFF:
https://github.com/llvm/llvm-project/commit/ae76eb32a5988c1f4ebb07e7e5eb9de2b036e194.diff
LOG: [NFC][Clang][Pragma] Remove unused variables
Reviewed By: beanz
Differential Revision: https://reviews.llvm.org/D124339
Added:
Modified:
clang/lib/Lex/Pragma.cpp
Removed:
diff --git a/clang/lib/Lex/Pragma.cpp b/clang/lib/Lex/Pragma.cpp
index 5a1b999505426..fb4f2dc457581 100644
--- a/clang/lib/Lex/Pragma.cpp
+++ b/clang/lib/Lex/Pragma.cpp
@@ -1944,8 +1944,6 @@ struct PragmaRegionHandler : public PragmaHandler {
static IdentifierInfo *HandleMacroAnnotationPragma(Preprocessor &PP, Token
&Tok,
const char *Pragma,
std::string &MessageString)
{
- std::string Macro;
-
PP.Lex(Tok);
if (Tok.isNot(tok::l_paren)) {
PP.Diag(Tok, diag::err_expected) << "(";
@@ -2034,8 +2032,6 @@ struct PragmaFinalHandler : public PragmaHandler {
void HandlePragma(Preprocessor &PP, PragmaIntroducer Introducer,
Token &Tok) override {
-std::string Macro;
-
PP.Lex(Tok);
if (Tok.isNot(tok::l_paren)) {
PP.Diag(Tok, diag::err_expected) << "(";
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
https://github.com/zsrkmyn updated
https://github.com/llvm/llvm-project/pull/120352
>From 80ee70143f6754f53fc11d5d013bf571856c090c Mon Sep 17 00:00:00 2001
From: Senran Zhang
Date: Tue, 17 Dec 2024 16:15:25 +0800
Subject: [PATCH] [ConstantRange] Estimate tighter lower (upper) bounds for
masked binary and (or)
Co-author: Yingwei Zheng (@dtcxzyw)
---
clang/test/CodeGen/AArch64/fpm-helpers.c | 18 ++--
llvm/lib/IR/ConstantRange.cpp | 76 ++--
.../SCCP/range-and-or-bit-masked.ll | 88 +++
llvm/unittests/IR/ConstantRangeTest.cpp | 16
4 files changed, 183 insertions(+), 15 deletions(-)
create mode 100644 llvm/test/Transforms/SCCP/range-and-or-bit-masked.ll
diff --git a/clang/test/CodeGen/AArch64/fpm-helpers.c
b/clang/test/CodeGen/AArch64/fpm-helpers.c
index 4bced01d5c71fa..6264b5caeb4f50 100644
--- a/clang/test/CodeGen/AArch64/fpm-helpers.c
+++ b/clang/test/CodeGen/AArch64/fpm-helpers.c
@@ -35,7 +35,7 @@ extern "C" {
//
fpm_t test_init() { return __arm_fpm_init(); }
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -6) i64 @test_src1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -8
@@ -44,7 +44,7 @@ fpm_t test_src1_1() {
return __arm_set_fpm_src1_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -6) i64 @test_src1_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 1
@@ -53,7 +53,7 @@ fpm_t test_src1_2() {
return __arm_set_fpm_src1_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -48) i64 @test_src2_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -57
@@ -62,7 +62,7 @@ fpm_t test_src2_1() {
return __arm_set_fpm_src2_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -48) i64 @test_src2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 8
@@ -71,7 +71,7 @@ fpm_t test_src2_2() {
return __arm_set_fpm_src2_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -384) i64 @test_dst1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -449
@@ -80,7 +80,7 @@ fpm_t test_dst1_1() {
return __arm_set_fpm_dst_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -384) i64 @test_dst2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 64
@@ -139,21 +139,21 @@ fpm_t test_lscale() { return
__arm_set_fpm_lscale(INIT_ZERO, 127); }
//
fpm_t test_lscale2() { return __arm_set_fpm_lscale2(INIT_ZERO, 63); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2147483648
//
fpm_t test_nscale_1() { return __arm_set_fpm_nscale(INIT_ZERO, -128); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2130706432
//
fpm_t test_nscale_2() { return __arm_set_fpm_nscale(INIT_ZERO, 127); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_3(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_3(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 4278190080
diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index d81a292916fdea..8b36d72b7105b7 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -1520,15 +1520,72 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'00101'1, ; LLo
+/// 10'1'0] ; LHi
+/// RHS = [10'1'0, ; RLo
+/// 10'1'1] ; RHi
+///
+/// we know that the higher 2 bits of the
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
zsrkmyn wrote: Test updated. https://github.com/llvm/llvm-project/pull/120352 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -1520,15 +1520,72 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'00101'1, ; LLo
+/// 10'1'0] ; LHi
+/// RHS = [10'1'0, ; RLo
+/// 10'1'1] ; RHi
+///
+/// we know that the higher 2 bits of the result is always 10; and we also
+/// notice that RHS[1:6] are always 1, so the result[1:6] can no be less than
+/// LHS[1:6] (i.e., 00101). Thus, the lower bound is 10'00101'0.
+///
+/// The algorithm is as follows,
+/// 1. we first calculate a mask to find the higher common bits by
+/// Mask = ~((LLo ^ LHi) | (LLo ^ LHi) | (LLo ^ RLo));
+/// Mask = clear all non-leading-ones bits in Mask;
+///in the example, the Mask is set to 11'0'0;
+/// 2. calculate a new mask by setting all common leading bits to 1 in RHS, and
+///keeping the longest leading ones (i.e., 11'1'0 in the example).
+/// 3. return (LLo & new mask) as the lower bound;
+/// 4. repeat the step 2 and 3 with LHS and RHS swapped, and update the lower
+///bound with the larger one.
+static APInt estimateBitMaskedAndLowerBound(const ConstantRange &LHS,
+const ConstantRange &RHS) {
+ auto BitWidth = LHS.getBitWidth();
+ // If either is full set or unsigned wrapped, then the range must contain '0'
+ // which leads the lower bound to 0.
+ if ((LHS.isFullSet() || RHS.isFullSet()) ||
+ (LHS.isWrappedSet() || RHS.isWrappedSet()))
+return APInt::getZero(BitWidth);
+
+ auto LLo = LHS.getLower();
+ auto LHi = LHS.getUpper() - 1;
+ auto RLo = RHS.getLower();
+ auto RHi = RHS.getUpper() - 1;
+
+ // Calculate the mask for the higher common bits.
+ auto Mask = ~((LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo));
+ unsigned LeadingOnes = Mask.countLeadingOnes();
+ Mask.clearLowBits(BitWidth - LeadingOnes);
+
+ auto estimateBound = [BitWidth, &Mask](APInt ALo, const APInt &BLo,
+ const APInt &BHi) {
+unsigned LeadingOnes = ((BLo & BHi) | Mask).countLeadingOnes();
+unsigned StartBit = BitWidth - LeadingOnes;
+ALo.clearLowBits(StartBit);
zsrkmyn wrote:
Sorry, but can you elaborate it? I'm afraid they're not same.
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
zsrkmyn wrote: > > I'm thinking if I need to add a new test mode to test the optimal lower > > (upper) bound only for AND (OR). > > If you cannot make it optimal for all non-wrapped cases, please just add some > special cases (e.g., `[7, 14) & [-1, 0) = [7, 14)`) before > `TestBinaryOpExhaustive`. Ah, I mean, the lower bound by this patch is optimal, but the upper isn't, so tests failed. :-D But adding special cases should work. https://github.com/llvm/llvm-project/pull/120352 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
zsrkmyn wrote: I'd appreciate much if you can help me commit it. https://github.com/llvm/llvm-project/pull/120352 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -1520,15 +1520,72 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'00101'1, ; LLo
+/// 10'1'0] ; LHi
+/// RHS = [10'1'0, ; RLo
+/// 10'1'1] ; RHi
+///
+/// we know that the higher 2 bits of the result is always 10; and we also
+/// notice that RHS[1:6] are always 1, so the result[1:6] cannot be less than
+/// LHS[1:6] (i.e., 00101). Thus, the lower bound is 10'00101'0.
+///
+/// The algorithm is as follows,
+/// 1. we first calculate a mask to find the higher common bits by
+/// Mask = ~((LLo ^ LHi) | (LLo ^ LHi) | (LLo ^ RLo));
+/// Mask = clear all non-leading-ones bits in Mask;
+///in the example, the Mask is set to 11'0'0;
+/// 2. calculate a new mask by setting all common leading bits to 1 in RHS, and
+///keeping the longest leading ones (i.e., 11'1'0 in the example).
+/// 3. return (LLo & new mask) as the lower bound;
+/// 4. repeat the step 2 and 3 with LHS and RHS swapped, and update the lower
+///bound with the larger one.
+static APInt estimateBitMaskedAndLowerBound(const ConstantRange &LHS,
zsrkmyn wrote:
> I happened to analyze the problem in Oct and made a comment to
> https://stackoverflow.com/questions/2620388/bitwise-interval-arithmetic
>
> Do the two algorithms return the same result? If yes, my code seems simpler?
Aha, I saw your answer on SO before, but I don't think they are same. E.g.,
given
```
a.lo = 0b110101;
a.hi = 0b111000; // inclusive
b.lo = 0b11;
b.hi = 0b11;
```
your algorithm gives the lower bound as `0b11`, while mine gives `0b110101`.
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -2720,6 +2720,22 @@ TEST_F(ConstantRangeTest, binaryAnd) {
EXPECT_EQ(R16_32.binaryAnd(R0_99), R0_32);
EXPECT_EQ(R0_99.binaryAnd(R16_32), R0_32);
+ // 'And' with leading bits are masked (with common leading bits stripped)
zsrkmyn wrote:
'And' op is tricky, since it operates regardless of the signedness and all
ranges can be treated as unsigned. E.g., a range (with bitwidth=8) `[1, -10)`
can be treated as `[1, 246)` because of the nature of 2's complement;
similarly, range `[-3, -1)` can be treated as `[253, 255)`; and results won't
be affected. And I think it's how `ConstantRange` designed.
I'll add a test anyway.
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
https://github.com/zsrkmyn edited https://github.com/llvm/llvm-project/pull/120352 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -2720,6 +2720,22 @@ TEST_F(ConstantRangeTest, binaryAnd) {
EXPECT_EQ(R16_32.binaryAnd(R0_99), R0_32);
EXPECT_EQ(R0_99.binaryAnd(R16_32), R0_32);
+ // 'And' with leading bits are masked (with common leading bits stripped)
+ ConstantRange RMaskedL(APInt(8, 0b10'00101'1), APInt(8, 0b10'1'0 + 1));
+ ConstantRange RMaskedR(APInt(8, 0b10'1'0), APInt(8, 0b10'1'1 + 1));
+ EXPECT_EQ(RMaskedL.binaryAnd(RMaskedR).getLower(), APInt(8, 0b10'00101'0));
+ EXPECT_EQ(RMaskedR.binaryAnd(RMaskedL).getLower(), APInt(8, 0b10'00101'0));
+
+ ConstantRange RMaskedL1(APInt(8, 0b00'011'010), APInt(8, 0b00'100'100 + 1));
+ ConstantRange RMaskedR1(APInt(8, 0b00'111'010), APInt(8, 0b00'111'110 + 1));
+ EXPECT_EQ(RMaskedL1.binaryAnd(RMaskedR1).getLower(), APInt(8, 0b00'011'000));
+ EXPECT_EQ(RMaskedR1.binaryAnd(RMaskedL1).getLower(), APInt(8, 0b00'011'000));
+
+ ConstantRange RMaskedL2(APInt(8, 0b'0111u), APInt(8, 0b'1101u + 1u));
+ ConstantRange RMaskedR2(APInt(8, 0xff), APInt(8, 0));
+ EXPECT_EQ(RMaskedL2.binaryAnd(RMaskedR2), RMaskedL2);
+ EXPECT_EQ(RMaskedR2.binaryAnd(RMaskedL2), RMaskedL2);
zsrkmyn wrote:
So, should I `EXPECT_GE(lower, 0)` or `EXPECT_EQ(lower, 0)`? I prefer the
former, because tests won't fail if the algorithm is further optimized.
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -2720,6 +2720,22 @@ TEST_F(ConstantRangeTest, binaryAnd) {
EXPECT_EQ(R16_32.binaryAnd(R0_99), R0_32);
EXPECT_EQ(R0_99.binaryAnd(R16_32), R0_32);
+ // 'And' with leading bits are masked (with common leading bits stripped)
zsrkmyn wrote:
Oh, if you're asking wrapped set, e.g., `[254, 1)` (or `[-2, 1)`), the
algorithm bails out early at
[here](https://github.com/llvm/llvm-project/commit/9c49208195b25c6cf5bdbd0f6d85ed5f8348812d#diff-b4f991f8e64d4fd23608e9ac00520c91429ad1dca8ea91f8be3a2922ea465dbdR1553).
In such case, 0 is always in the range.
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
https://github.com/zsrkmyn updated
https://github.com/llvm/llvm-project/pull/120352
>From c585a24277ddbf828f19faa6a66c6dd3bae699e2 Mon Sep 17 00:00:00 2001
From: Senran Zhang
Date: Tue, 17 Dec 2024 16:15:25 +0800
Subject: [PATCH] [ConstantRange] Estimate tighter lower (upper) bounds for
masked binary and (or)
Co-author: Yingwei Zheng (@dtcxzyw)
---
clang/test/CodeGen/AArch64/fpm-helpers.c | 18 ++--
llvm/lib/IR/ConstantRange.cpp | 76 ++--
.../SCCP/range-and-or-bit-masked.ll | 88 +++
llvm/unittests/IR/ConstantRangeTest.cpp | 28 ++
4 files changed, 195 insertions(+), 15 deletions(-)
create mode 100644 llvm/test/Transforms/SCCP/range-and-or-bit-masked.ll
diff --git a/clang/test/CodeGen/AArch64/fpm-helpers.c
b/clang/test/CodeGen/AArch64/fpm-helpers.c
index 4bced01d5c71fa..6264b5caeb4f50 100644
--- a/clang/test/CodeGen/AArch64/fpm-helpers.c
+++ b/clang/test/CodeGen/AArch64/fpm-helpers.c
@@ -35,7 +35,7 @@ extern "C" {
//
fpm_t test_init() { return __arm_fpm_init(); }
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -6) i64 @test_src1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -8
@@ -44,7 +44,7 @@ fpm_t test_src1_1() {
return __arm_set_fpm_src1_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -6) i64 @test_src1_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 1
@@ -53,7 +53,7 @@ fpm_t test_src1_2() {
return __arm_set_fpm_src1_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -48) i64 @test_src2_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -57
@@ -62,7 +62,7 @@ fpm_t test_src2_1() {
return __arm_set_fpm_src2_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -48) i64 @test_src2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 8
@@ -71,7 +71,7 @@ fpm_t test_src2_2() {
return __arm_set_fpm_src2_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -384) i64 @test_dst1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -449
@@ -80,7 +80,7 @@ fpm_t test_dst1_1() {
return __arm_set_fpm_dst_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -384) i64 @test_dst2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 64
@@ -139,21 +139,21 @@ fpm_t test_lscale() { return
__arm_set_fpm_lscale(INIT_ZERO, 127); }
//
fpm_t test_lscale2() { return __arm_set_fpm_lscale2(INIT_ZERO, 63); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2147483648
//
fpm_t test_nscale_1() { return __arm_set_fpm_nscale(INIT_ZERO, -128); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2130706432
//
fpm_t test_nscale_2() { return __arm_set_fpm_nscale(INIT_ZERO, 127); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_3(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_3(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 4278190080
diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index d81a292916fdea..35664353989929 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -1520,15 +1520,72 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'00101'1, ; LLo
+/// 10'1'0] ; LHi
+/// RHS = [10'1'0, ; RLo
+/// 10'1'1] ; RHi
+///
+/// we know that the higher 2 bits of t
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -1520,15 +1520,72 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'00101'1, ; LLo
+/// 10'1'0] ; LHi
+/// RHS = [10'1'0, ; RLo
+/// 10'1'1] ; RHi
+///
+/// we know that the higher 2 bits of the result is always 10; and we also
+/// notice that RHS[1:6] are always 1, so the result[1:6] cannot be less than
+/// LHS[1:6] (i.e., 00101). Thus, the lower bound is 10'00101'0.
+///
+/// The algorithm is as follows,
+/// 1. we first calculate a mask to find the higher common bits by
+/// Mask = ~((LLo ^ LHi) | (LLo ^ LHi) | (LLo ^ RLo));
zsrkmyn wrote:
Fixed; thanks!
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -2720,6 +2720,22 @@ TEST_F(ConstantRangeTest, binaryAnd) {
EXPECT_EQ(R16_32.binaryAnd(R0_99), R0_32);
EXPECT_EQ(R0_99.binaryAnd(R16_32), R0_32);
+ // 'And' with leading bits are masked (with common leading bits stripped)
zsrkmyn wrote:
Test added.
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -2720,6 +2720,22 @@ TEST_F(ConstantRangeTest, binaryAnd) {
EXPECT_EQ(R16_32.binaryAnd(R0_99), R0_32);
EXPECT_EQ(R0_99.binaryAnd(R16_32), R0_32);
+ // 'And' with leading bits are masked (with common leading bits stripped)
+ ConstantRange RMaskedL(APInt(8, 0b10'00101'1), APInt(8, 0b10'1'0 + 1));
+ ConstantRange RMaskedR(APInt(8, 0b10'1'0), APInt(8, 0b10'1'1 + 1));
+ EXPECT_EQ(RMaskedL.binaryAnd(RMaskedR).getLower(), APInt(8, 0b10'00101'0));
+ EXPECT_EQ(RMaskedR.binaryAnd(RMaskedL).getLower(), APInt(8, 0b10'00101'0));
+
+ ConstantRange RMaskedL1(APInt(8, 0b00'011'010), APInt(8, 0b00'100'100 + 1));
+ ConstantRange RMaskedR1(APInt(8, 0b00'111'010), APInt(8, 0b00'111'110 + 1));
+ EXPECT_EQ(RMaskedL1.binaryAnd(RMaskedR1).getLower(), APInt(8, 0b00'011'000));
+ EXPECT_EQ(RMaskedR1.binaryAnd(RMaskedL1).getLower(), APInt(8, 0b00'011'000));
+
+ ConstantRange RMaskedL2(APInt(8, 0b'0111u), APInt(8, 0b'1101u + 1u));
+ ConstantRange RMaskedR2(APInt(8, 0xff), APInt(8, 0));
+ EXPECT_EQ(RMaskedL2.binaryAnd(RMaskedR2), RMaskedL2);
+ EXPECT_EQ(RMaskedR2.binaryAnd(RMaskedL2), RMaskedL2);
zsrkmyn wrote:
Added.
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
https://github.com/zsrkmyn updated
https://github.com/llvm/llvm-project/pull/120352
>From 19555edc7e2749a6e904c80d963a46431b23b6d1 Mon Sep 17 00:00:00 2001
From: Senran Zhang
Date: Tue, 17 Dec 2024 16:15:25 +0800
Subject: [PATCH] [ConstantRange] Estimate tighter lower (upper) bounds for
masked binary and (or)
Co-author: Yingwei Zheng (@dtcxzyw)
---
clang/test/CodeGen/AArch64/fpm-helpers.c | 18 ++--
llvm/lib/IR/ConstantRange.cpp | 76 ++--
.../SCCP/range-and-or-bit-masked.ll | 88 +++
llvm/unittests/IR/ConstantRangeTest.cpp | 31 +++
4 files changed, 198 insertions(+), 15 deletions(-)
create mode 100644 llvm/test/Transforms/SCCP/range-and-or-bit-masked.ll
diff --git a/clang/test/CodeGen/AArch64/fpm-helpers.c
b/clang/test/CodeGen/AArch64/fpm-helpers.c
index 4bced01d5c71fa..6264b5caeb4f50 100644
--- a/clang/test/CodeGen/AArch64/fpm-helpers.c
+++ b/clang/test/CodeGen/AArch64/fpm-helpers.c
@@ -35,7 +35,7 @@ extern "C" {
//
fpm_t test_init() { return __arm_fpm_init(); }
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -6) i64 @test_src1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -8
@@ -44,7 +44,7 @@ fpm_t test_src1_1() {
return __arm_set_fpm_src1_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -6) i64 @test_src1_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 1
@@ -53,7 +53,7 @@ fpm_t test_src1_2() {
return __arm_set_fpm_src1_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -48) i64 @test_src2_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -57
@@ -62,7 +62,7 @@ fpm_t test_src2_1() {
return __arm_set_fpm_src2_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -48) i64 @test_src2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 8
@@ -71,7 +71,7 @@ fpm_t test_src2_2() {
return __arm_set_fpm_src2_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -384) i64 @test_dst1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -449
@@ -80,7 +80,7 @@ fpm_t test_dst1_1() {
return __arm_set_fpm_dst_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -384) i64 @test_dst2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 64
@@ -139,21 +139,21 @@ fpm_t test_lscale() { return
__arm_set_fpm_lscale(INIT_ZERO, 127); }
//
fpm_t test_lscale2() { return __arm_set_fpm_lscale2(INIT_ZERO, 63); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2147483648
//
fpm_t test_nscale_1() { return __arm_set_fpm_nscale(INIT_ZERO, -128); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2130706432
//
fpm_t test_nscale_2() { return __arm_set_fpm_nscale(INIT_ZERO, 127); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_3(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_3(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 4278190080
diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index d81a292916fdea..35664353989929 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -1520,15 +1520,72 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'00101'1, ; LLo
+/// 10'1'0] ; LHi
+/// RHS = [10'1'0, ; RLo
+/// 10'1'1] ; RHi
+///
+/// we know that the higher 2 bits of
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
zsrkmyn wrote: A soft ping to @MaskRay @nikic . :-) https://github.com/llvm/llvm-project/pull/120352 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
zsrkmyn wrote:
Ah, by applying the patch below, I just found the lower bound is still not
optimal for non-wrapped cases. E.g., for 4-bit ints, given 2 ranges,
```
[0011, ]
[1101, ]
```
the optimal lower bound is 1, while the algorithm gives 0.
```diff
diff --git a/llvm/unittests/IR/ConstantRangeTest.cpp
b/llvm/unittests/IR/ConstantRangeTest.cpp
index e1d9b3e387b2..74a49e6842cb 100644
--- a/llvm/unittests/IR/ConstantRangeTest.cpp
+++ b/llvm/unittests/IR/ConstantRangeTest.cpp
@@ -112,6 +112,10 @@ bool PreferSmallestNonFullSigned(const ConstantRange &CR1,
return PreferSmallestSigned(CR1, CR2);
}
+bool PreferSmallerLowerBound(const ConstantRange &CR1, const ConstantRange
&CR2) {
+ return CR1.getLower().ult(CR2.getLower());
+}
+
testing::AssertionResult rangeContains(const ConstantRange &CR, const APInt &N,
ArrayRef Inputs) {
if (CR.contains(N))
@@ -2726,6 +2730,13 @@ TEST_F(ConstantRangeTest, binaryAnd) {
},
[](const APInt &N1, const APInt &N2) { return N1 & N2; }, PreferSmallest,
CheckSingleElementsOnly);
+
+ TestBinaryOpExhaustive(
+ [](const ConstantRange &CR1, const ConstantRange &CR2) {
+return CR1.binaryAnd(CR2);
+ },
+ [](const APInt &N1, const APInt &N2) { return N1 & N2; },
+ PreferSmallerLowerBound, CheckNonWrappedOnly);
}
TEST_F(ConstantRangeTest, binaryOr) {
```
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
https://github.com/zsrkmyn updated
https://github.com/llvm/llvm-project/pull/120352
>From 9c49208195b25c6cf5bdbd0f6d85ed5f8348812d Mon Sep 17 00:00:00 2001
From: Senran Zhang
Date: Tue, 17 Dec 2024 16:15:25 +0800
Subject: [PATCH] [ConstantRange] Estimate tighter lower (upper) bounds for
masked binary and (or)
Co-author: Yingwei Zheng (@dtcxzyw)
---
clang/test/CodeGen/AArch64/fpm-helpers.c | 18 ++--
llvm/lib/IR/ConstantRange.cpp | 76 ++--
.../SCCP/range-and-or-bit-masked.ll | 88 +++
llvm/unittests/IR/ConstantRangeTest.cpp | 16
4 files changed, 183 insertions(+), 15 deletions(-)
create mode 100644 llvm/test/Transforms/SCCP/range-and-or-bit-masked.ll
diff --git a/clang/test/CodeGen/AArch64/fpm-helpers.c
b/clang/test/CodeGen/AArch64/fpm-helpers.c
index 4bced01d5c71fa..6264b5caeb4f50 100644
--- a/clang/test/CodeGen/AArch64/fpm-helpers.c
+++ b/clang/test/CodeGen/AArch64/fpm-helpers.c
@@ -35,7 +35,7 @@ extern "C" {
//
fpm_t test_init() { return __arm_fpm_init(); }
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -6) i64 @test_src1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -8
@@ -44,7 +44,7 @@ fpm_t test_src1_1() {
return __arm_set_fpm_src1_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -6) i64 @test_src1_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 1
@@ -53,7 +53,7 @@ fpm_t test_src1_2() {
return __arm_set_fpm_src1_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -48) i64 @test_src2_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -57
@@ -62,7 +62,7 @@ fpm_t test_src2_1() {
return __arm_set_fpm_src2_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -48) i64 @test_src2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 8
@@ -71,7 +71,7 @@ fpm_t test_src2_2() {
return __arm_set_fpm_src2_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -384) i64 @test_dst1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -449
@@ -80,7 +80,7 @@ fpm_t test_dst1_1() {
return __arm_set_fpm_dst_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -384) i64 @test_dst2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 64
@@ -139,21 +139,21 @@ fpm_t test_lscale() { return
__arm_set_fpm_lscale(INIT_ZERO, 127); }
//
fpm_t test_lscale2() { return __arm_set_fpm_lscale2(INIT_ZERO, 63); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2147483648
//
fpm_t test_nscale_1() { return __arm_set_fpm_nscale(INIT_ZERO, -128); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2130706432
//
fpm_t test_nscale_2() { return __arm_set_fpm_nscale(INIT_ZERO, 127); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_3(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_3(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 4278190080
diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index d81a292916fdea..f778494b1917fe 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -1520,15 +1520,72 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'00101'1, ; LLo
+/// 10'1'0] ; LHi
+/// RHS = [10'1'0, ; RLo
+/// 10'1'1] ; RHi
+///
+/// we know that the higher 2 bits of the
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
https://github.com/zsrkmyn edited https://github.com/llvm/llvm-project/pull/120352 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -1520,15 +1520,72 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'00101'1, ; LLo
+/// 10'1'0] ; LHi
+/// RHS = [10'1'0, ; RLo
+/// 10'1'1] ; RHi
+///
+/// we know that the higher 2 bits of the result is always 10; and we also
+/// notice that RHS[1:6] are always 1, so the result[1:6] can no be less than
zsrkmyn wrote:
Thanks! Resolved.
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -1520,15 +1520,102 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'001'010, ; LLo
+/// 10'100'000] ; LHi
+/// RHS = [10'111'010, ; RLo
+/// 10'111'100] ; RHi
+///
+/// we know that the higher 2 bits of the result is always '10'; and note that
+/// there's at least one bit is 1 in LHS[3:6] (since the range is continuous),
+/// and all bits in RHS[3:6] are 1, so we know the lower bound of the result is
+/// 10'001'000.
+///
+/// The algorithm is as follows,
+/// 1. we first calculate a mask to mask out the higher common bits by
+/// Mask = (LLo ^ LHi) | (LLo ^ LHi) | (LLo ^ RLo);
+/// Mask = set all non-leading-zero bits to 1 for Mask;
+/// 2. find the bit field with at least 1 in LHS (i.e., bit 3:6 in the example)
+///after applying the mask, with
+/// StartBit = BitWidth - (LLo & Mask).clz() - 1;
+/// EndBit = BitWidth - (LHi & Mask).clz();
+/// 3. check if all bits in [StartBit:EndBit] in RHS are 1, and all bits of
+///RLo and RHi in [StartBit:BitWidth] are same, and if so, the lower bound
+///can be updated to
+/// LowerBound = LLo & Keep;
+///where Keep is a mask to mask out trailing bits (the lower 3 bits in the
+///example);
+/// 4. repeat the step 2 and 3 with LHS and RHS swapped, and update the lower
+///bound with the smaller one.
+static APInt estimateBitMaskedAndLowerBound(const ConstantRange &LHS,
+const ConstantRange &RHS) {
+ auto BitWidth = LHS.getBitWidth();
+ // If either is full set or unsigned wrapped, then the range must contain '0'
+ // which leads the lower bound to 0.
+ if ((LHS.isFullSet() || RHS.isFullSet()) ||
+ (LHS.isWrappedSet() || RHS.isWrappedSet()))
+return APInt::getZero(BitWidth);
+
+ auto LLo = LHS.getLower();
+ auto LHi = LHS.getUpper() - 1;
zsrkmyn wrote:
May I know why?
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -1520,15 +1520,102 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'001'010, ; LLo
+/// 10'100'000] ; LHi
+/// RHS = [10'111'010, ; RLo
+/// 10'111'100] ; RHi
+///
+/// we know that the higher 2 bits of the result is always '10'; and note that
+/// there's at least one bit is 1 in LHS[3:6] (since the range is continuous),
+/// and all bits in RHS[3:6] are 1, so we know the lower bound of the result is
+/// 10'001'000.
+///
+/// The algorithm is as follows,
+/// 1. we first calculate a mask to mask out the higher common bits by
+/// Mask = (LLo ^ LHi) | (LLo ^ LHi) | (LLo ^ RLo);
+/// Mask = set all non-leading-zero bits to 1 for Mask;
+/// 2. find the bit field with at least 1 in LHS (i.e., bit 3:6 in the example)
+///after applying the mask, with
+/// StartBit = BitWidth - (LLo & Mask).clz() - 1;
+/// EndBit = BitWidth - (LHi & Mask).clz();
+/// 3. check if all bits in [StartBit:EndBit] in RHS are 1, and all bits of
+///RLo and RHi in [StartBit:BitWidth] are same, and if so, the lower bound
+///can be updated to
+/// LowerBound = LLo & Keep;
+///where Keep is a mask to mask out trailing bits (the lower 3 bits in the
+///example);
+/// 4. repeat the step 2 and 3 with LHS and RHS swapped, and update the lower
+///bound with the smaller one.
+static APInt estimateBitMaskedAndLowerBound(const ConstantRange &LHS,
+const ConstantRange &RHS) {
+ auto BitWidth = LHS.getBitWidth();
+ // If either is full set or unsigned wrapped, then the range must contain '0'
+ // which leads the lower bound to 0.
+ if ((LHS.isFullSet() || RHS.isFullSet()) ||
+ (LHS.isWrappedSet() || RHS.isWrappedSet()))
+return APInt::getZero(BitWidth);
+
+ auto LLo = LHS.getLower();
+ auto LHi = LHS.getUpper() - 1;
+ auto RLo = RHS.getLower();
+ auto RHi = RHS.getUpper() - 1;
+
+ // Calculate the mask that mask out the higher common bits.
+ auto Mask = (LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo);
+ unsigned LeadingZeros = Mask.countLeadingZeros();
+ Mask.setLowBits(BitWidth - LeadingZeros);
+
+ auto estimateBound =
+ [BitWidth, &Mask](const APInt &ALo, const APInt &AHi, const APInt &BLo,
+const APInt &BHi) -> std::optional {
+unsigned LeadingZeros = (ALo & Mask).countLeadingZeros();
+if (LeadingZeros == BitWidth)
+ return std::nullopt;
+
+unsigned StartBit = BitWidth - LeadingZeros - 1;
+
+if (BLo.extractBits(BitWidth - StartBit, StartBit) !=
+BHi.extractBits(BitWidth - StartBit, StartBit))
+ return std::nullopt;
+
+unsigned EndBit = BitWidth - (AHi & Mask).countLeadingZeros();
+if (!(BLo.extractBits(EndBit - StartBit, StartBit) &
+ BHi.extractBits(EndBit - StartBit, StartBit))
+ .isAllOnes())
+ return std::nullopt;
+
+APInt Keep(BitWidth, 0);
+Keep.setBits(StartBit, BitWidth);
+return Keep & ALo;
+ };
+
+ auto LowerBoundByLHS = estimateBound(LLo, LHi, RLo, RHi);
+ auto LowerBoundByRHS = estimateBound(RLo, RHi, LLo, LHi);
+
+ if (LowerBoundByLHS && LowerBoundByRHS)
+return LowerBoundByLHS->ult(*LowerBoundByRHS) ? *LowerBoundByLHS
zsrkmyn wrote:
Great catch!
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -1520,15 +1520,102 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'001'010, ; LLo
+/// 10'100'000] ; LHi
+/// RHS = [10'111'010, ; RLo
+/// 10'111'100] ; RHi
+///
+/// we know that the higher 2 bits of the result is always '10'; and note that
+/// there's at least one bit is 1 in LHS[3:6] (since the range is continuous),
+/// and all bits in RHS[3:6] are 1, so we know the lower bound of the result is
+/// 10'001'000.
+///
+/// The algorithm is as follows,
+/// 1. we first calculate a mask to mask out the higher common bits by
+/// Mask = (LLo ^ LHi) | (LLo ^ LHi) | (LLo ^ RLo);
+/// Mask = set all non-leading-zero bits to 1 for Mask;
+/// 2. find the bit field with at least 1 in LHS (i.e., bit 3:6 in the example)
+///after applying the mask, with
+/// StartBit = BitWidth - (LLo & Mask).clz() - 1;
+/// EndBit = BitWidth - (LHi & Mask).clz();
+/// 3. check if all bits in [StartBit:EndBit] in RHS are 1, and all bits of
+///RLo and RHi in [StartBit:BitWidth] are same, and if so, the lower bound
+///can be updated to
+/// LowerBound = LLo & Keep;
+///where Keep is a mask to mask out trailing bits (the lower 3 bits in the
+///example);
+/// 4. repeat the step 2 and 3 with LHS and RHS swapped, and update the lower
+///bound with the smaller one.
+static APInt estimateBitMaskedAndLowerBound(const ConstantRange &LHS,
+const ConstantRange &RHS) {
+ auto BitWidth = LHS.getBitWidth();
+ // If either is full set or unsigned wrapped, then the range must contain '0'
+ // which leads the lower bound to 0.
+ if ((LHS.isFullSet() || RHS.isFullSet()) ||
+ (LHS.isWrappedSet() || RHS.isWrappedSet()))
+return APInt::getZero(BitWidth);
+
+ auto LLo = LHS.getLower();
+ auto LHi = LHS.getUpper() - 1;
+ auto RLo = RHS.getLower();
+ auto RHi = RHS.getUpper() - 1;
+
+ // Calculate the mask that mask out the higher common bits.
+ auto Mask = (LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo);
+ unsigned LeadingZeros = Mask.countLeadingZeros();
+ Mask.setLowBits(BitWidth - LeadingZeros);
+
+ auto estimateBound =
+ [BitWidth, &Mask](const APInt &ALo, const APInt &AHi, const APInt &BLo,
+const APInt &BHi) -> std::optional {
+unsigned LeadingZeros = (ALo & Mask).countLeadingZeros();
+if (LeadingZeros == BitWidth)
+ return std::nullopt;
+
+unsigned StartBit = BitWidth - LeadingZeros - 1;
+
+if (BLo.extractBits(BitWidth - StartBit, StartBit) !=
+BHi.extractBits(BitWidth - StartBit, StartBit))
+ return std::nullopt;
+
+unsigned EndBit = BitWidth - (AHi & Mask).countLeadingZeros();
+if (!(BLo.extractBits(EndBit - StartBit, StartBit) &
+ BHi.extractBits(EndBit - StartBit, StartBit))
+ .isAllOnes())
+ return std::nullopt;
+
+APInt Keep(BitWidth, 0);
+Keep.setBits(StartBit, BitWidth);
+return Keep & ALo;
zsrkmyn wrote:
clearLowBits works in place and returns void, and that's why I didn't use it
LOL.
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -1520,15 +1520,102 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'001'010, ; LLo
+/// 10'100'000] ; LHi
+/// RHS = [10'111'010, ; RLo
+/// 10'111'100] ; RHi
+///
+/// we know that the higher 2 bits of the result is always '10'; and note that
+/// there's at least one bit is 1 in LHS[3:6] (since the range is continuous),
+/// and all bits in RHS[3:6] are 1, so we know the lower bound of the result is
+/// 10'001'000.
+///
+/// The algorithm is as follows,
+/// 1. we first calculate a mask to mask out the higher common bits by
+/// Mask = (LLo ^ LHi) | (LLo ^ LHi) | (LLo ^ RLo);
+/// Mask = set all non-leading-zero bits to 1 for Mask;
+/// 2. find the bit field with at least 1 in LHS (i.e., bit 3:6 in the example)
+///after applying the mask, with
+/// StartBit = BitWidth - (LLo & Mask).clz() - 1;
+/// EndBit = BitWidth - (LHi & Mask).clz();
+/// 3. check if all bits in [StartBit:EndBit] in RHS are 1, and all bits of
+///RLo and RHi in [StartBit:BitWidth] are same, and if so, the lower bound
+///can be updated to
+/// LowerBound = LLo & Keep;
+///where Keep is a mask to mask out trailing bits (the lower 3 bits in the
+///example);
+/// 4. repeat the step 2 and 3 with LHS and RHS swapped, and update the lower
+///bound with the smaller one.
+static APInt estimateBitMaskedAndLowerBound(const ConstantRange &LHS,
+const ConstantRange &RHS) {
+ auto BitWidth = LHS.getBitWidth();
+ // If either is full set or unsigned wrapped, then the range must contain '0'
+ // which leads the lower bound to 0.
+ if ((LHS.isFullSet() || RHS.isFullSet()) ||
+ (LHS.isWrappedSet() || RHS.isWrappedSet()))
zsrkmyn wrote:
Extra parenthesis was added here to avoid clang-format to break the line
unintentionally. :-D
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
https://github.com/zsrkmyn edited https://github.com/llvm/llvm-project/pull/120352 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
zsrkmyn wrote: > > Failed Tests > > Clang.CodeGen/AArch64/fpm-helpers.c > > Is it related with this patch? Thx! I thought it wasn't as it's 'Clang.CodeGen'. Fixed now. https://github.com/llvm/llvm-project/pull/120352 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
https://github.com/zsrkmyn updated
https://github.com/llvm/llvm-project/pull/120352
>From 90f753998f605cefa912fc92d776bc90a7ca74f5 Mon Sep 17 00:00:00 2001
From: Senran Zhang
Date: Tue, 17 Dec 2024 16:15:25 +0800
Subject: [PATCH] [ConstantRange] Estimate tighter lower (upper) bounds for
masked binary and (or)
---
clang/test/CodeGen/AArch64/fpm-helpers.c | 18 +--
llvm/lib/IR/ConstantRange.cpp | 106 +-
.../SCCP/range-and-or-bit-masked.ll | 88 +++
3 files changed, 197 insertions(+), 15 deletions(-)
create mode 100644 llvm/test/Transforms/SCCP/range-and-or-bit-masked.ll
diff --git a/clang/test/CodeGen/AArch64/fpm-helpers.c
b/clang/test/CodeGen/AArch64/fpm-helpers.c
index 4bced01d5c71fa..3b356c0d1136d1 100644
--- a/clang/test/CodeGen/AArch64/fpm-helpers.c
+++ b/clang/test/CodeGen/AArch64/fpm-helpers.c
@@ -35,7 +35,7 @@ extern "C" {
//
fpm_t test_init() { return __arm_fpm_init(); }
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -4) i64 @test_src1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -8
@@ -44,7 +44,7 @@ fpm_t test_src1_1() {
return __arm_set_fpm_src1_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -4) i64 @test_src1_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 1
@@ -53,7 +53,7 @@ fpm_t test_src1_2() {
return __arm_set_fpm_src1_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -32) i64 @test_src2_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -57
@@ -62,7 +62,7 @@ fpm_t test_src2_1() {
return __arm_set_fpm_src2_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -32) i64 @test_src2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 8
@@ -71,7 +71,7 @@ fpm_t test_src2_2() {
return __arm_set_fpm_src2_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -256) i64 @test_dst1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -449
@@ -80,7 +80,7 @@ fpm_t test_dst1_1() {
return __arm_set_fpm_dst_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -256) i64 @test_dst2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 64
@@ -139,21 +139,21 @@ fpm_t test_lscale() { return
__arm_set_fpm_lscale(INIT_ZERO, 127); }
//
fpm_t test_lscale2() { return __arm_set_fpm_lscale2(INIT_ZERO, 63); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4286578688) i64
@test_nscale_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2147483648
//
fpm_t test_nscale_1() { return __arm_set_fpm_nscale(INIT_ZERO, -128); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4286578688) i64
@test_nscale_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2130706432
//
fpm_t test_nscale_2() { return __arm_set_fpm_nscale(INIT_ZERO, 127); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_3(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4286578688) i64
@test_nscale_3(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 4278190080
diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index d81a292916fdea..2a8438582cd55f 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -1520,15 +1520,102 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'001'010, ; LLo
+/// 10'100'000] ; LHi
+/// RHS = [10'111'010, ; RLo
+/// 10'111'100] ; RHi
+///
+/// we know that the higher 2 bits of the result is always '10'; and note that
+/// there's at least one bit is 1 in LHS[3:6] (since
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -1538,10 +1625,17 @@ ConstantRange ConstantRange::binaryOr(const
ConstantRange &Other) const {
ConstantRange KnownBitsRange =
fromKnownBits(toKnownBits() | Other.toKnownBits(), false);
+
+ // ~a & ~b>= x
+ // <=> ~(~a & ~b) <= ~x
+ // <=> a | b <= ~x
+ // <=> a | b < ~x + 1
+ // thus, UpperBound(a | b) == ~LowerBound(~a & ~b) + 1
+ auto UpperBound =
zsrkmyn wrote:
Fixed! Thx!
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
https://github.com/zsrkmyn updated
https://github.com/llvm/llvm-project/pull/120352
>From 3351cf82f3fef3bf22cd274e16c3e23133cd7754 Mon Sep 17 00:00:00 2001
From: Senran Zhang
Date: Tue, 17 Dec 2024 16:15:25 +0800
Subject: [PATCH] [ConstantRange] Estimate tighter lower (upper) bounds for
masked binary and (or)
---
clang/test/CodeGen/AArch64/fpm-helpers.c | 18 +--
llvm/lib/IR/ConstantRange.cpp | 105 +-
.../SCCP/range-and-or-bit-masked.ll | 88 +++
3 files changed, 196 insertions(+), 15 deletions(-)
create mode 100644 llvm/test/Transforms/SCCP/range-and-or-bit-masked.ll
diff --git a/clang/test/CodeGen/AArch64/fpm-helpers.c
b/clang/test/CodeGen/AArch64/fpm-helpers.c
index 4bced01d5c71fa..3b356c0d1136d1 100644
--- a/clang/test/CodeGen/AArch64/fpm-helpers.c
+++ b/clang/test/CodeGen/AArch64/fpm-helpers.c
@@ -35,7 +35,7 @@ extern "C" {
//
fpm_t test_init() { return __arm_fpm_init(); }
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -4) i64 @test_src1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -8
@@ -44,7 +44,7 @@ fpm_t test_src1_1() {
return __arm_set_fpm_src1_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -4) i64 @test_src1_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 1
@@ -53,7 +53,7 @@ fpm_t test_src1_2() {
return __arm_set_fpm_src1_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -32) i64 @test_src2_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -57
@@ -62,7 +62,7 @@ fpm_t test_src2_1() {
return __arm_set_fpm_src2_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -32) i64 @test_src2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 8
@@ -71,7 +71,7 @@ fpm_t test_src2_2() {
return __arm_set_fpm_src2_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -256) i64 @test_dst1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -449
@@ -80,7 +80,7 @@ fpm_t test_dst1_1() {
return __arm_set_fpm_dst_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -256) i64 @test_dst2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 64
@@ -139,21 +139,21 @@ fpm_t test_lscale() { return
__arm_set_fpm_lscale(INIT_ZERO, 127); }
//
fpm_t test_lscale2() { return __arm_set_fpm_lscale2(INIT_ZERO, 63); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4286578688) i64
@test_nscale_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2147483648
//
fpm_t test_nscale_1() { return __arm_set_fpm_nscale(INIT_ZERO, -128); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4286578688) i64
@test_nscale_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2130706432
//
fpm_t test_nscale_2() { return __arm_set_fpm_nscale(INIT_ZERO, 127); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_3(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4286578688) i64
@test_nscale_3(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 4278190080
diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index d81a292916fdea..14e35514ca0ff2 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -1520,15 +1520,101 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'001'010, ; LLo
+/// 10'100'000] ; LHi
+/// RHS = [10'111'010, ; RLo
+/// 10'111'100] ; RHi
+///
+/// we know that the higher 2 bits of the result is always '10'; and note that
+/// there's at least one bit is 1 in LHS[3:6] (since
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
zsrkmyn wrote: @dtcxzyw, I've updated the patch. It's quite simple. You can forget about the previous patch and start a review from scratch. unittests weren't updated with your patch, since the upper bound wasn't optimal (for AND op). I'm thinking if I need to add a new test mode to test the optimal lower (upper) bound only for AND (or). https://github.com/llvm/llvm-project/pull/120352 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
https://github.com/zsrkmyn updated
https://github.com/llvm/llvm-project/pull/120352
>From 2cb7f076f4b101ab0503b51e84e3493ae2ba8060 Mon Sep 17 00:00:00 2001
From: Senran Zhang
Date: Tue, 17 Dec 2024 16:15:25 +0800
Subject: [PATCH] [ConstantRange] Estimate tighter lower (upper) bounds for
masked binary and (or)
Co-author: Yingwei Zheng (@dtcxzyw)
---
clang/test/CodeGen/AArch64/fpm-helpers.c | 18 +--
llvm/lib/IR/ConstantRange.cpp | 76 ++-
.../SCCP/range-and-or-bit-masked.ll | 122 ++
3 files changed, 201 insertions(+), 15 deletions(-)
create mode 100644 llvm/test/Transforms/SCCP/range-and-or-bit-masked.ll
diff --git a/clang/test/CodeGen/AArch64/fpm-helpers.c
b/clang/test/CodeGen/AArch64/fpm-helpers.c
index 4bced01d5c71fa..6264b5caeb4f50 100644
--- a/clang/test/CodeGen/AArch64/fpm-helpers.c
+++ b/clang/test/CodeGen/AArch64/fpm-helpers.c
@@ -35,7 +35,7 @@ extern "C" {
//
fpm_t test_init() { return __arm_fpm_init(); }
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -6) i64 @test_src1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -8
@@ -44,7 +44,7 @@ fpm_t test_src1_1() {
return __arm_set_fpm_src1_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src1_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -6) i64 @test_src1_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 1
@@ -53,7 +53,7 @@ fpm_t test_src1_2() {
return __arm_set_fpm_src1_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -48) i64 @test_src2_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -57
@@ -62,7 +62,7 @@ fpm_t test_src2_1() {
return __arm_set_fpm_src2_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_src2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -48) i64 @test_src2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 8
@@ -71,7 +71,7 @@ fpm_t test_src2_2() {
return __arm_set_fpm_src2_format(INIT_ZERO, __ARM_FPM_E4M3);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst1_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -384) i64 @test_dst1_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 -449
@@ -80,7 +80,7 @@ fpm_t test_dst1_1() {
return __arm_set_fpm_dst_format(INIT_ONES, __ARM_FPM_E5M2);
}
-// CHECK-LABEL: define dso_local noundef i64 @test_dst2_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, -384) i64 @test_dst2_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 64
@@ -139,21 +139,21 @@ fpm_t test_lscale() { return
__arm_set_fpm_lscale(INIT_ZERO, 127); }
//
fpm_t test_lscale2() { return __arm_set_fpm_lscale2(INIT_ZERO, 63); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_1(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_1(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2147483648
//
fpm_t test_nscale_1() { return __arm_set_fpm_nscale(INIT_ZERO, -128); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_2(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_2(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 2130706432
//
fpm_t test_nscale_2() { return __arm_set_fpm_nscale(INIT_ZERO, 127); }
-// CHECK-LABEL: define dso_local noundef range(i64 0, 4294967296) i64
@test_nscale_3(
+// CHECK-LABEL: define dso_local noundef range(i64 0, 4278190081) i64
@test_nscale_3(
// CHECK-SAME: ) local_unnamed_addr #[[ATTR0]] {
// CHECK-NEXT: [[ENTRY:.*:]]
// CHECK-NEXT:ret i64 4278190080
diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index d81a292916fdea..8b36d72b7105b7 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -1520,15 +1520,72 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'00101'1, ; LLo
+/// 10'1'0] ; LHi
+/// RHS = [10'1'0, ; RLo
+/// 10'1'1] ; RHi
+///
+/// we know that the higher 2 bits of the result is always 10; and we also
+/// notice that RHS[1:6] a
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -1520,15 +1520,101 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'001'010, ; LLo
+/// 10'100'000] ; LHi
+/// RHS = [10'111'010, ; RLo
+/// 10'111'100] ; RHi
+///
+/// we know that the higher 2 bits of the result is always '10'; and note that
+/// there's at least one bit is 1 in LHS[3:6] (since the range is continuous),
+/// and all bits in RHS[3:6] are 1, so we know the lower bound of the result is
+/// 10'001'000.
+///
+/// The algorithm is as follows,
+/// 1. we first calculate a mask to mask out the higher common bits by
+/// Mask = (LLo ^ LHi) | (LLo ^ LHi) | (LLo ^ RLo);
+/// Mask = set all non-leading-zero bits to 1 for Mask;
+/// 2. find the bit field with at least 1 in LHS (i.e., bit 3:6 in the example)
+///after applying the mask, with
+/// StartBit = BitWidth - (LLo & Mask).clz() - 1;
+/// EndBit = BitWidth - (LHi & Mask).clz();
+/// 3. check if all bits in [StartBit:EndBit] in RHS are 1, and all bits of
+///RLo and RHi in [StartBit:BitWidth] are same, and if so, the lower bound
+///can be updated to
+/// LowerBound = LLo & Keep;
+///where Keep is a mask to mask out trailing bits (the lower 3 bits in the
+///example);
+/// 4. repeat the step 2 and 3 with LHS and RHS swapped, and update the lower
+///bound with the larger one.
+static APInt estimateBitMaskedAndLowerBound(const ConstantRange &LHS,
+const ConstantRange &RHS) {
+ auto BitWidth = LHS.getBitWidth();
+ // If either is full set or unsigned wrapped, then the range must contain '0'
+ // which leads the lower bound to 0.
+ if ((LHS.isFullSet() || RHS.isFullSet()) ||
+ (LHS.isWrappedSet() || RHS.isWrappedSet()))
+return APInt::getZero(BitWidth);
+
+ auto LLo = LHS.getLower();
+ auto LHi = LHS.getUpper() - 1;
+ auto RLo = RHS.getLower();
+ auto RHi = RHS.getUpper() - 1;
+
+ // Calculate the mask that mask out the higher common bits.
+ auto Mask = (LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo);
+ unsigned LeadingZeros = Mask.countLeadingZeros();
+ Mask.setLowBits(BitWidth - LeadingZeros);
+
+ auto estimateBound =
+ [BitWidth, &Mask](const APInt &ALo, const APInt &AHi, const APInt &BLo,
+const APInt &BHi) -> std::optional {
+unsigned LeadingZeros = (ALo & Mask).countLeadingZeros();
+if (LeadingZeros == BitWidth)
+ return std::nullopt;
+
+unsigned StartBit = BitWidth - LeadingZeros - 1;
zsrkmyn wrote:
The whole algorithm is actually extremely simple. I made things complicated...
You'll see how stupid I am after I update the PR later. Many thanks for the
review!
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (PR #120352)
@@ -1520,15 +1520,101 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'001'010, ; LLo
+/// 10'100'000] ; LHi
+/// RHS = [10'111'010, ; RLo
+/// 10'111'100] ; RHi
+///
+/// we know that the higher 2 bits of the result is always '10'; and note that
+/// there's at least one bit is 1 in LHS[3:6] (since the range is continuous),
+/// and all bits in RHS[3:6] are 1, so we know the lower bound of the result is
+/// 10'001'000.
+///
+/// The algorithm is as follows,
+/// 1. we first calculate a mask to mask out the higher common bits by
+/// Mask = (LLo ^ LHi) | (LLo ^ LHi) | (LLo ^ RLo);
+/// Mask = set all non-leading-zero bits to 1 for Mask;
+/// 2. find the bit field with at least 1 in LHS (i.e., bit 3:6 in the example)
+///after applying the mask, with
+/// StartBit = BitWidth - (LLo & Mask).clz() - 1;
+/// EndBit = BitWidth - (LHi & Mask).clz();
+/// 3. check if all bits in [StartBit:EndBit] in RHS are 1, and all bits of
+///RLo and RHi in [StartBit:BitWidth] are same, and if so, the lower bound
+///can be updated to
+/// LowerBound = LLo & Keep;
+///where Keep is a mask to mask out trailing bits (the lower 3 bits in the
+///example);
+/// 4. repeat the step 2 and 3 with LHS and RHS swapped, and update the lower
+///bound with the larger one.
+static APInt estimateBitMaskedAndLowerBound(const ConstantRange &LHS,
+const ConstantRange &RHS) {
+ auto BitWidth = LHS.getBitWidth();
+ // If either is full set or unsigned wrapped, then the range must contain '0'
+ // which leads the lower bound to 0.
+ if ((LHS.isFullSet() || RHS.isFullSet()) ||
+ (LHS.isWrappedSet() || RHS.isWrappedSet()))
+return APInt::getZero(BitWidth);
+
+ auto LLo = LHS.getLower();
+ auto LHi = LHS.getUpper() - 1;
+ auto RLo = RHS.getLower();
+ auto RHi = RHS.getUpper() - 1;
+
+ // Calculate the mask that mask out the higher common bits.
+ auto Mask = (LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo);
+ unsigned LeadingZeros = Mask.countLeadingZeros();
+ Mask.setLowBits(BitWidth - LeadingZeros);
+
+ auto estimateBound =
+ [BitWidth, &Mask](const APInt &ALo, const APInt &AHi, const APInt &BLo,
+const APInt &BHi) -> std::optional {
+unsigned LeadingZeros = (ALo & Mask).countLeadingZeros();
+if (LeadingZeros == BitWidth)
+ return std::nullopt;
+
+unsigned StartBit = BitWidth - LeadingZeros - 1;
zsrkmyn wrote:
Great point! Actually we can do so by slightly extend the `StartBit` to lower
bits if extended bits in B are all ones.
E.g., given
```
CR_A: [01101110,
01110001]
CR_B: {0110}
```
the lower bound is `01101000` by the current algorithm (`StartBit` is 3,
counting from 0), but we notice that the bits 2 and 1 are also 1 in range B, so
we can extend the `StartBit` to 1. And the lower bound becomes `01101110`.
This can be done by some easy change. I'ma refine and update the PR.
https://github.com/llvm/llvm-project/pull/120352
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
