================
@@ -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'10000'0] ; LHi
+/// RHS = [10'11111'0, ; RLo
+/// 10'11111'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'00000'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'11111'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);
----------------
dtcxzyw wrote:
Oops, ignore me.
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
