https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/171991
>From bb0f8d1bb61be121183b9e85811148090e9da1c7 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Fri, 12 Dec 2025 11:04:51 +0000 Subject: [PATCH] [DA] Introduce OverflowSafeSignedAPInt to prevent potential overflow --- llvm/lib/Analysis/DependenceAnalysis.cpp | 187 ++++++++++++++---- .../infer_affine_domain_ovlf.ll | 2 +- 2 files changed, 147 insertions(+), 42 deletions(-) diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp index 9b9c80a9b3266..59722f41a07eb 100644 --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -377,6 +377,95 @@ struct SCEVMonotonicityChecker friend struct SCEVVisitor<SCEVMonotonicityChecker, SCEVMonotonicity>; }; +/// A wrapper class for std::optional<APInt> that provides arithmetic operators +/// with overflow checking in a signed sense. This allows us to omit inserting +/// an overflow check at every arithmetic operation, which simplifies the code +/// if the operations are chained like `a + b + c + ...`. +/// +/// If an calculation overflows, the result becomes "unknown" which is +/// internally represented by std::nullopt. If some operand of an arithmetic +/// operation is "unknown", the result is also "unknown". +struct OverflowSafeSignedAPInt { + OverflowSafeSignedAPInt() : Value(std::nullopt) {} + OverflowSafeSignedAPInt(const APInt &V) : Value(V) {} + OverflowSafeSignedAPInt(const std::optional<APInt> &V) : Value(V) {} + + OverflowSafeSignedAPInt operator+(const OverflowSafeSignedAPInt &RHS) const { + if (!Value || !RHS.Value) + return OverflowSafeSignedAPInt(); + bool Overflow; + APInt Result = Value->sadd_ov(*RHS.Value, Overflow); + if (Overflow) + return OverflowSafeSignedAPInt(); + return OverflowSafeSignedAPInt(Result); + } + + OverflowSafeSignedAPInt operator+(int RHS) const { + if (!Value) + return OverflowSafeSignedAPInt(); + return *this + fromInt(RHS); + } + + OverflowSafeSignedAPInt operator-(const OverflowSafeSignedAPInt &RHS) const { + if (!Value || !RHS.Value) + return OverflowSafeSignedAPInt(); + bool Overflow; + APInt Result = Value->ssub_ov(*RHS.Value, Overflow); + if (Overflow) + return OverflowSafeSignedAPInt(); + return OverflowSafeSignedAPInt(Result); + } + + OverflowSafeSignedAPInt operator-(int RHS) const { + if (!Value) + return OverflowSafeSignedAPInt(); + return *this - fromInt(RHS); + } + + OverflowSafeSignedAPInt operator*(const OverflowSafeSignedAPInt &RHS) const { + if (!Value || !RHS.Value) + return OverflowSafeSignedAPInt(); + bool Overflow; + APInt Result = Value->smul_ov(*RHS.Value, Overflow); + if (Overflow) + return OverflowSafeSignedAPInt(); + return OverflowSafeSignedAPInt(Result); + } + + OverflowSafeSignedAPInt operator-() const { + if (!Value) + return OverflowSafeSignedAPInt(); + if (Value->isMinSignedValue()) + return OverflowSafeSignedAPInt(); + return OverflowSafeSignedAPInt(-*Value); + } + + operator bool() const { return Value.has_value(); } + + bool operator!() const { return !Value.has_value(); } + + const APInt &operator*() const { + assert(Value && "Value is not available."); + return *Value; + } + + const APInt *operator->() const { + assert(Value && "Value is not available."); + return &*Value; + } + +private: + /// Underlying value. std::nullopt means "unknown". An arithmetic operation on + /// "unknown" always produces "unknown". + std::optional<APInt> Value; + + OverflowSafeSignedAPInt fromInt(uint64_t V) const { + assert(Value && "Value is not available."); + return OverflowSafeSignedAPInt( + APInt(Value->getBitWidth(), V, /*isSigned=*/true)); + } +}; + } // anonymous namespace // Used to test the dependence analyzer. @@ -1579,6 +1668,9 @@ bool DependenceInfo::weakCrossingSIVtest(const SCEV *Coeff, // Computes the GCD of AM and BM. // Also finds a solution to the equation ax - by = gcd(a, b). // Returns true if dependence disproved; i.e., gcd does not divide Delta. +// +// We don't use OverflowSafeSignedAPInt here because it's known that this +// algorithm doesn't overflow. static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y) { APInt A0(Bits, 1, true), A1(Bits, 0, true); @@ -1609,7 +1701,14 @@ static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM, return false; } -static APInt floorOfQuotient(const APInt &A, const APInt &B) { +static OverflowSafeSignedAPInt +floorOfQuotient(const OverflowSafeSignedAPInt &OA, + const OverflowSafeSignedAPInt &OB) { + if (!OA || !OB) + return OverflowSafeSignedAPInt(); + + APInt A = *OA; + APInt B = *OB; APInt Q = A; // these need to be initialized APInt R = A; APInt::sdivrem(A, B, Q, R); @@ -1617,20 +1716,25 @@ static APInt floorOfQuotient(const APInt &A, const APInt &B) { return Q; if ((A.sgt(0) && B.sgt(0)) || (A.slt(0) && B.slt(0))) return Q; - else - return Q - 1; + return OverflowSafeSignedAPInt(Q) - 1; } -static APInt ceilingOfQuotient(const APInt &A, const APInt &B) { +static OverflowSafeSignedAPInt +ceilingOfQuotient(const OverflowSafeSignedAPInt &OA, + const OverflowSafeSignedAPInt &OB) { + if (!OA || !OB) + return OverflowSafeSignedAPInt(); + + APInt A = *OA; + APInt B = *OB; APInt Q = A; // these need to be initialized APInt R = A; APInt::sdivrem(A, B, Q, R); if (R == 0) return Q; if ((A.sgt(0) && B.sgt(0)) || (A.slt(0) && B.slt(0))) - return Q + 1; - else - return Q; + return OverflowSafeSignedAPInt(Q) + 1; + return Q; } /// Given an affine expression of the form A*k + B, where k is an arbitrary @@ -1662,29 +1766,26 @@ static APInt ceilingOfQuotient(const APInt &A, const APInt &B) { /// while working with them. /// /// Preconditions: \p A is non-zero, and we know A*k + B is non-negative. -static std::pair<std::optional<APInt>, std::optional<APInt>> -inferDomainOfAffine(const APInt &A, const APInt &B, - const std::optional<APInt> &UB) { - assert(A != 0 && "A must be non-zero"); - std::optional<APInt> TL, TU; - if (A.sgt(0)) { +static std::pair<OverflowSafeSignedAPInt, OverflowSafeSignedAPInt> +inferDomainOfAffine(OverflowSafeSignedAPInt A, OverflowSafeSignedAPInt B, + OverflowSafeSignedAPInt UB) { + assert(A && B && "A and B must be available"); + assert(*A != 0 && "A must be non-zero"); + OverflowSafeSignedAPInt TL, TU; + if (A->sgt(0)) { TL = ceilingOfQuotient(-B, A); - LLVM_DEBUG(dbgs() << "\t Possible TL = " << *TL << "\n"); + LLVM_DEBUG(if (TL) dbgs() << "\t Possible TL = " << *TL << "\n"); + // New bound check - modification to Banerjee's e3 check - if (UB) { - // TODO?: Overflow check for UB - B - TU = floorOfQuotient(*UB - B, A); - LLVM_DEBUG(dbgs() << "\t Possible TU = " << *TU << "\n"); - } + TU = floorOfQuotient(UB - B, A); + LLVM_DEBUG(if (TU) dbgs() << "\t Possible TU = " << *TU << "\n"); } else { TU = floorOfQuotient(-B, A); - LLVM_DEBUG(dbgs() << "\t Possible TU = " << *TU << "\n"); + LLVM_DEBUG(if (TU) dbgs() << "\t Possible TU = " << *TU << "\n"); + // New bound check - modification to Banerjee's e3 check - if (UB) { - // TODO?: Overflow check for UB - B - TL = ceilingOfQuotient(*UB - B, A); - LLVM_DEBUG(dbgs() << "\t Possible TL = " << *TL << "\n"); - } + TL = ceilingOfQuotient(UB - B, A); + LLVM_DEBUG(if (TL) dbgs() << "\t Possible TL = " << *TL << "\n"); } return std::make_pair(TL, TU); } @@ -1783,8 +1884,8 @@ bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, auto [TL0, TU0] = inferDomainOfAffine(TB, TX, UM); auto [TL1, TU1] = inferDomainOfAffine(TA, TY, UM); - auto CreateVec = [](const std::optional<APInt> &V0, - const std::optional<APInt> &V1) { + auto CreateVec = [](const OverflowSafeSignedAPInt &V0, + const OverflowSafeSignedAPInt &V1) { SmallVector<APInt, 2> Vec; if (V0) Vec.push_back(*V0); @@ -1814,29 +1915,33 @@ bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, // explore directions unsigned NewDirection = Dependence::DVEntry::NONE; - APInt LowerDistance, UpperDistance; - // TODO: Overflow check may be needed. + OverflowSafeSignedAPInt LowerDistance, UpperDistance; + OverflowSafeSignedAPInt OTY(TY), OTX(TX), OTA(TA), OTB(TB), OTL(TL), OTU(TU); + // NOTE: It's unclear whether these calculations can overflow. At the moment, + // we conservatively assume they can. if (TA.sgt(TB)) { - LowerDistance = (TY - TX) + (TA - TB) * TL; - UpperDistance = (TY - TX) + (TA - TB) * TU; + LowerDistance = (OTY - OTX) + (OTA - OTB) * OTL; + UpperDistance = (OTY - OTX) + (OTA - OTB) * OTU; } else { - LowerDistance = (TY - TX) + (TA - TB) * TU; - UpperDistance = (TY - TX) + (TA - TB) * TL; + LowerDistance = (OTY - OTX) + (OTA - OTB) * OTU; + UpperDistance = (OTY - OTX) + (OTA - OTB) * OTL; } - LLVM_DEBUG(dbgs() << "\t LowerDistance = " << LowerDistance << "\n"); - LLVM_DEBUG(dbgs() << "\t UpperDistance = " << UpperDistance << "\n"); + if (!LowerDistance || !UpperDistance) + return false; + + LLVM_DEBUG(dbgs() << "\t LowerDistance = " << *LowerDistance << "\n"); + LLVM_DEBUG(dbgs() << "\t UpperDistance = " << *UpperDistance << "\n"); - APInt Zero(Bits, 0, true); - if (LowerDistance.sle(Zero) && UpperDistance.sge(Zero)) { + if (LowerDistance->sle(0) && UpperDistance->sge(0)) { NewDirection |= Dependence::DVEntry::EQ; ++ExactSIVsuccesses; } - if (LowerDistance.slt(0)) { + if (LowerDistance->slt(0)) { NewDirection |= Dependence::DVEntry::GT; ++ExactSIVsuccesses; } - if (UpperDistance.sgt(0)) { + if (UpperDistance->sgt(0)) { NewDirection |= Dependence::DVEntry::LT; ++ExactSIVsuccesses; } @@ -2172,8 +2277,8 @@ bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, LLVM_DEBUG(dbgs() << "\t TA = " << TA << "\n"); LLVM_DEBUG(dbgs() << "\t TB = " << TB << "\n"); - auto CreateVec = [](const std::optional<APInt> &V0, - const std::optional<APInt> &V1) { + auto CreateVec = [](const OverflowSafeSignedAPInt &V0, + const OverflowSafeSignedAPInt &V1) { SmallVector<APInt, 2> Vec; if (V0) Vec.push_back(*V0); diff --git a/llvm/test/Analysis/DependenceAnalysis/infer_affine_domain_ovlf.ll b/llvm/test/Analysis/DependenceAnalysis/infer_affine_domain_ovlf.ll index 21fe1ef71d9df..b141c4428afc8 100644 --- a/llvm/test/Analysis/DependenceAnalysis/infer_affine_domain_ovlf.ll +++ b/llvm/test/Analysis/DependenceAnalysis/infer_affine_domain_ovlf.ll @@ -32,7 +32,7 @@ define void @infer_affine_domain_ovfl(ptr %A) { ; CHECK-EXACT-SIV-NEXT: Src: store i8 0, ptr %gep.0, align 1 --> Dst: store i8 0, ptr %gep.0, align 1 ; CHECK-EXACT-SIV-NEXT: da analyze - consistent output [*]! ; CHECK-EXACT-SIV-NEXT: Src: store i8 0, ptr %gep.0, align 1 --> Dst: store i8 1, ptr %gep.1, align 1 -; CHECK-EXACT-SIV-NEXT: da analyze - none! +; CHECK-EXACT-SIV-NEXT: da analyze - output [*|<]! ; CHECK-EXACT-SIV-NEXT: Src: store i8 1, ptr %gep.1, align 1 --> Dst: store i8 1, ptr %gep.1, align 1 ; CHECK-EXACT-SIV-NEXT: da analyze - consistent output [*]! ; _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
