Index: llvm/include/llvm/IR/ConstantRange.h =================================================================== --- llvm/include/llvm/IR/ConstantRange.h +++ llvm/include/llvm/IR/ConstantRange.h @@ -526,6 +526,11 @@ /// \p IntMinIsPoison is false. ConstantRange abs(bool IntMinIsPoison = false) const; + /// Calculate absolute value range. If the original range contains zero, then + /// the resulting range will be bounded if and only if \p ZeroIsPoison is + /// false. + ConstantRange ctlz(bool ZeroIsPoison = false) const; + /// Represents whether an operation on the given constant range is known to /// always or never overflow. enum class OverflowResult { Index: llvm/lib/IR/ConstantRange.cpp =================================================================== --- llvm/lib/IR/ConstantRange.cpp +++ llvm/lib/IR/ConstantRange.cpp @@ -945,6 +945,7 @@ case Intrinsic::smin: case Intrinsic::smax: case Intrinsic::abs: + case Intrinsic::ctlz: return true; default: return false; @@ -976,6 +977,12 @@ assert(IntMinIsPoison->getBitWidth() == 1 && "Must be boolean"); return Ops[0].abs(IntMinIsPoison->getBoolValue()); } + case Intrinsic::ctlz: { + const APInt *ZeroIsPoison = Ops[1].getSingleElement(); + assert(ZeroIsPoison && "Must be known (immarg)"); + assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean"); + return Ops[0].ctlz(ZeroIsPoison->getBoolValue()); + } default: assert(!isIntrinsicSupported(IntrinsicID) && "Shouldn't be supported"); llvm_unreachable("Unsupported intrinsic"); @@ -1667,6 +1674,45 @@ APIntOps::umax(-SMin, SMax) + 1); } +ConstantRange ConstantRange::ctlz(bool ZeroIsPoison) const { + if (isEmptySet()) + return getEmpty(); + + APInt Zero = APInt::getZero(getBitWidth()); + if (ZeroIsPoison && contains(Zero)) { + // ZeroIsPoison is set, and zero is contained. We discern three cases, in + // which a zero can appear: + // 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc. + // 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc. + // 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc. + + if (getLower().isZero()) { + if ((getUpper() - 1).isZero()) { + // We have in input interval of kind [0, 1). In this case we cannot + // really help but return empty-set. + return getEmpty(); + } + + // Compute the resulting range by excluding zero from Lower. + return ConstantRange( + APInt(getBitWidth(), (getUpper() - 1).countLeadingZeros()), + APInt(getBitWidth(), (getLower() + 1).countLeadingZeros() + 1)); + } else if ((getUpper() - 1).isZero()) { + // Compute the resulting range by excluding zero from Upper. + return ConstantRange( + Zero, APInt(getBitWidth(), getLower().countLeadingZeros() + 1)); + } else { + return ConstantRange(Zero, APInt(getBitWidth(), getBitWidth())); + } + } + + // Zero is either safe or not in the range. The output range is composed by + // the result of countLeadingZero of the two extremes. + return getNonEmpty( + APInt(getBitWidth(), getUnsignedMax().countLeadingZeros()), + APInt(getBitWidth(), getUnsignedMin().countLeadingZeros() + 1)); +} + ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow( const ConstantRange &Other) const { if (isEmptySet() || Other.isEmptySet()) Index: llvm/test/Transforms/CorrelatedValuePropagation/range.ll =================================================================== --- llvm/test/Transforms/CorrelatedValuePropagation/range.ll +++ llvm/test/Transforms/CorrelatedValuePropagation/range.ll @@ -964,12 +964,10 @@ ; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[ELSE:%.*]] ; CHECK: if: ; CHECK-NEXT: [[CTLZ:%.*]] = call i16 @llvm.ctlz.i16(i16 [[X]], i1 false) -; CHECK-NEXT: [[RES:%.*]] = icmp uge i16 [[CTLZ]], 8 -; CHECK-NEXT: ret i1 [[RES]] +; CHECK-NEXT: ret i1 true ; CHECK: else: ; CHECK-NEXT: [[CTLZ2:%.*]] = call i16 @llvm.ctlz.i16(i16 [[X]], i1 false) -; CHECK-NEXT: [[RES2:%.*]] = icmp ult i16 [[CTLZ2]], 8 -; CHECK-NEXT: ret i1 [[RES2]] +; CHECK-NEXT: ret i1 true ; %cmp = icmp ult i16 %x, 256 br i1 %cmp, label %if, label %else Index: llvm/unittests/IR/ConstantRangeTest.cpp =================================================================== --- llvm/unittests/IR/ConstantRangeTest.cpp +++ llvm/unittests/IR/ConstantRangeTest.cpp @@ -2397,6 +2397,21 @@ }); } +TEST_F(ConstantRangeTest, Ctlz) { + TestUnaryOpExhaustive([](const ConstantRange &CR) { return CR.ctlz(); }, + [](const APInt &N) { + return APInt(N.getBitWidth(), N.countLeadingZeros()); + }); + + TestUnaryOpExhaustive( + [](const ConstantRange &CR) { return CR.ctlz(/*ZeroIsPoison=*/true); }, + [](const APInt &N) -> std::optional { + if (N.isZero()) + return std::nullopt; + return APInt(N.getBitWidth(), N.countLeadingZeros()); + }); +} + TEST_F(ConstantRangeTest, castOps) { ConstantRange A(APInt(16, 66), APInt(16, 128)); ConstantRange FpToI8 = A.castOp(Instruction::FPToSI, 8);