summaryrefslogtreecommitdiff
path: root/llvm/lib/Support/KnownBits.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Support/KnownBits.cpp')
-rw-r--r--llvm/lib/Support/KnownBits.cpp132
1 files changed, 120 insertions, 12 deletions
diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp
index 3623a54ae476..d997bd85f1e0 100644
--- a/llvm/lib/Support/KnownBits.cpp
+++ b/llvm/lib/Support/KnownBits.cpp
@@ -12,6 +12,8 @@
//===----------------------------------------------------------------------===//
#include "llvm/Support/KnownBits.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
#include <cassert>
using namespace llvm;
@@ -181,11 +183,37 @@ KnownBits KnownBits::shl(const KnownBits &LHS, const KnownBits &RHS) {
unsigned MinTrailingZeros = LHS.countMinTrailingZeros();
// Minimum shift amount low bits are known zero.
- if (RHS.getMinValue().ult(BitWidth)) {
- MinTrailingZeros += RHS.getMinValue().getZExtValue();
+ APInt MinShiftAmount = RHS.getMinValue();
+ if (MinShiftAmount.ult(BitWidth)) {
+ MinTrailingZeros += MinShiftAmount.getZExtValue();
MinTrailingZeros = std::min(MinTrailingZeros, BitWidth);
}
+ // If the maximum shift is in range, then find the common bits from all
+ // possible shifts.
+ APInt MaxShiftAmount = RHS.getMaxValue();
+ if (MaxShiftAmount.ult(BitWidth) && !LHS.isUnknown()) {
+ uint64_t ShiftAmtZeroMask = (~RHS.Zero).getZExtValue();
+ uint64_t ShiftAmtOneMask = RHS.One.getZExtValue();
+ assert(MinShiftAmount.ult(MaxShiftAmount) && "Illegal shift range");
+ Known.Zero.setAllBits();
+ Known.One.setAllBits();
+ for (uint64_t ShiftAmt = MinShiftAmount.getZExtValue(),
+ MaxShiftAmt = MaxShiftAmount.getZExtValue();
+ ShiftAmt <= MaxShiftAmt; ++ShiftAmt) {
+ // Skip if the shift amount is impossible.
+ if ((ShiftAmtZeroMask & ShiftAmt) != ShiftAmt ||
+ (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
+ continue;
+ KnownBits SpecificShift;
+ SpecificShift.Zero = LHS.Zero << ShiftAmt;
+ SpecificShift.One = LHS.One << ShiftAmt;
+ Known = KnownBits::commonBits(Known, SpecificShift);
+ if (Known.isUnknown())
+ break;
+ }
+ }
+
Known.Zero.setLowBits(MinTrailingZeros);
return Known;
}
@@ -208,11 +236,37 @@ KnownBits KnownBits::lshr(const KnownBits &LHS, const KnownBits &RHS) {
unsigned MinLeadingZeros = LHS.countMinLeadingZeros();
// Minimum shift amount high bits are known zero.
- if (RHS.getMinValue().ult(BitWidth)) {
- MinLeadingZeros += RHS.getMinValue().getZExtValue();
+ APInt MinShiftAmount = RHS.getMinValue();
+ if (MinShiftAmount.ult(BitWidth)) {
+ MinLeadingZeros += MinShiftAmount.getZExtValue();
MinLeadingZeros = std::min(MinLeadingZeros, BitWidth);
}
+ // If the maximum shift is in range, then find the common bits from all
+ // possible shifts.
+ APInt MaxShiftAmount = RHS.getMaxValue();
+ if (MaxShiftAmount.ult(BitWidth) && !LHS.isUnknown()) {
+ uint64_t ShiftAmtZeroMask = (~RHS.Zero).getZExtValue();
+ uint64_t ShiftAmtOneMask = RHS.One.getZExtValue();
+ assert(MinShiftAmount.ult(MaxShiftAmount) && "Illegal shift range");
+ Known.Zero.setAllBits();
+ Known.One.setAllBits();
+ for (uint64_t ShiftAmt = MinShiftAmount.getZExtValue(),
+ MaxShiftAmt = MaxShiftAmount.getZExtValue();
+ ShiftAmt <= MaxShiftAmt; ++ShiftAmt) {
+ // Skip if the shift amount is impossible.
+ if ((ShiftAmtZeroMask & ShiftAmt) != ShiftAmt ||
+ (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
+ continue;
+ KnownBits SpecificShift = LHS;
+ SpecificShift.Zero.lshrInPlace(ShiftAmt);
+ SpecificShift.One.lshrInPlace(ShiftAmt);
+ Known = KnownBits::commonBits(Known, SpecificShift);
+ if (Known.isUnknown())
+ break;
+ }
+ }
+
Known.Zero.setHighBits(MinLeadingZeros);
return Known;
}
@@ -234,17 +288,43 @@ KnownBits KnownBits::ashr(const KnownBits &LHS, const KnownBits &RHS) {
unsigned MinLeadingOnes = LHS.countMinLeadingOnes();
// Minimum shift amount high bits are known sign bits.
- if (RHS.getMinValue().ult(BitWidth)) {
+ APInt MinShiftAmount = RHS.getMinValue();
+ if (MinShiftAmount.ult(BitWidth)) {
if (MinLeadingZeros) {
- MinLeadingZeros += RHS.getMinValue().getZExtValue();
+ MinLeadingZeros += MinShiftAmount.getZExtValue();
MinLeadingZeros = std::min(MinLeadingZeros, BitWidth);
}
if (MinLeadingOnes) {
- MinLeadingOnes += RHS.getMinValue().getZExtValue();
+ MinLeadingOnes += MinShiftAmount.getZExtValue();
MinLeadingOnes = std::min(MinLeadingOnes, BitWidth);
}
}
+ // If the maximum shift is in range, then find the common bits from all
+ // possible shifts.
+ APInt MaxShiftAmount = RHS.getMaxValue();
+ if (MaxShiftAmount.ult(BitWidth) && !LHS.isUnknown()) {
+ uint64_t ShiftAmtZeroMask = (~RHS.Zero).getZExtValue();
+ uint64_t ShiftAmtOneMask = RHS.One.getZExtValue();
+ assert(MinShiftAmount.ult(MaxShiftAmount) && "Illegal shift range");
+ Known.Zero.setAllBits();
+ Known.One.setAllBits();
+ for (uint64_t ShiftAmt = MinShiftAmount.getZExtValue(),
+ MaxShiftAmt = MaxShiftAmount.getZExtValue();
+ ShiftAmt <= MaxShiftAmt; ++ShiftAmt) {
+ // Skip if the shift amount is impossible.
+ if ((ShiftAmtZeroMask & ShiftAmt) != ShiftAmt ||
+ (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
+ continue;
+ KnownBits SpecificShift = LHS;
+ SpecificShift.Zero.ashrInPlace(ShiftAmt);
+ SpecificShift.One.ashrInPlace(ShiftAmt);
+ Known = KnownBits::commonBits(Known, SpecificShift);
+ if (Known.isUnknown())
+ break;
+ }
+ }
+
Known.Zero.setHighBits(MinLeadingZeros);
Known.One.setHighBits(MinLeadingOnes);
return Known;
@@ -332,10 +412,11 @@ KnownBits KnownBits::abs(bool IntMinIsPoison) const {
return KnownAbs;
}
-KnownBits KnownBits::computeForMul(const KnownBits &LHS, const KnownBits &RHS) {
+KnownBits KnownBits::mul(const KnownBits &LHS, const KnownBits &RHS) {
unsigned BitWidth = LHS.getBitWidth();
+ assert(BitWidth == RHS.getBitWidth() && !LHS.hasConflict() &&
+ !RHS.hasConflict() && "Operand mismatch");
- assert(!LHS.hasConflict() && !RHS.hasConflict());
// Compute a conservative estimate for high known-0 bits.
unsigned LeadZ =
std::max(LHS.countMinLeadingZeros() + RHS.countMinLeadingZeros(),
@@ -411,6 +492,24 @@ KnownBits KnownBits::computeForMul(const KnownBits &LHS, const KnownBits &RHS) {
return Res;
}
+KnownBits KnownBits::mulhs(const KnownBits &LHS, const KnownBits &RHS) {
+ unsigned BitWidth = LHS.getBitWidth();
+ assert(BitWidth == RHS.getBitWidth() && !LHS.hasConflict() &&
+ !RHS.hasConflict() && "Operand mismatch");
+ KnownBits WideLHS = LHS.sext(2 * BitWidth);
+ KnownBits WideRHS = RHS.sext(2 * BitWidth);
+ return mul(WideLHS, WideRHS).extractBits(BitWidth, BitWidth);
+}
+
+KnownBits KnownBits::mulhu(const KnownBits &LHS, const KnownBits &RHS) {
+ unsigned BitWidth = LHS.getBitWidth();
+ assert(BitWidth == RHS.getBitWidth() && !LHS.hasConflict() &&
+ !RHS.hasConflict() && "Operand mismatch");
+ KnownBits WideLHS = LHS.zext(2 * BitWidth);
+ KnownBits WideRHS = RHS.zext(2 * BitWidth);
+ return mul(WideLHS, WideRHS).extractBits(BitWidth, BitWidth);
+}
+
KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS) {
unsigned BitWidth = LHS.getBitWidth();
assert(!LHS.hasConflict() && !RHS.hasConflict());
@@ -474,9 +573,10 @@ KnownBits KnownBits::srem(const KnownBits &LHS, const KnownBits &RHS) {
}
// The sign bit is the LHS's sign bit, except when the result of the
- // remainder is zero. If it's known zero, our sign bit is also zero.
- if (LHS.isNonNegative())
- Known.makeNonNegative();
+ // remainder is zero. The magnitude of the result should be less than or
+ // equal to the magnitude of the LHS. Therefore any leading zeros that exist
+ // in the left hand side must also exist in the result.
+ Known.Zero.setHighBits(LHS.countMinLeadingZeros());
return Known;
}
@@ -504,3 +604,11 @@ KnownBits &KnownBits::operator^=(const KnownBits &RHS) {
Zero = std::move(Z);
return *this;
}
+
+void KnownBits::print(raw_ostream &OS) const {
+ OS << "{Zero=" << Zero << ", One=" << One << "}";
+}
+void KnownBits::dump() const {
+ print(dbgs());
+ dbgs() << "\n";
+}
generated by cgit v1.3 (git 2.53.0) at 2026-07-30 18:33:08 +0000