From a78dc4d6c8afc51c9a6985b167043af33e246830 Mon Sep 17 00:00:00 2001 From: Max Kazantsev Date: Tue, 15 Jan 2019 09:51:34 +0000 Subject: [PATCH] [NFC] Move some functions to LoopUtils llvm-svn: 351179 --- llvm/include/llvm/Transforms/Utils/LoopUtils.h | 17 ++++++++ .../Scalar/InductiveRangeCheckElimination.cpp | 48 +++------------------- llvm/lib/Transforms/Utils/LoopUtils.cpp | 36 ++++++++++++++++ 3 files changed, 59 insertions(+), 42 deletions(-) diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h index 1740e9e..8c2527b 100644 --- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -323,6 +323,23 @@ Value *createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, /// Flag set: NSW, NUW, exact, and all of fast-math. void propagateIRFlags(Value *I, ArrayRef VL, Value *OpValue = nullptr); +/// Returns true if we can prove that \p S is defined and always negative in +/// loop \p L. +bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE); + +/// Returns true if we can prove that \p S is defined and always non-negative in +/// loop \p L. +bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, + ScalarEvolution &SE); + +/// Returns true if \p S is defined and never is equal to signed/unsigned max. +bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, + bool Signed); + +/// Returns true if \p S is defined and never is equal to signed/unsigned min. +bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, + bool Signed); + } // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H diff --git a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp index c5ed6d5..0e6dcfd 100644 --- a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp +++ b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp @@ -689,17 +689,6 @@ void LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block, PN->setIncomingBlock(i, ReplaceBy); } -static bool CannotBeMaxInLoop(const SCEV *BoundSCEV, Loop *L, - ScalarEvolution &SE, bool Signed) { - unsigned BitWidth = cast(BoundSCEV->getType())->getBitWidth(); - APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) : - APInt::getMaxValue(BitWidth); - auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; - return SE.isAvailableAtLoopEntry(BoundSCEV, L) && - SE.isLoopEntryGuardedByCond(L, Predicate, BoundSCEV, - SE.getConstant(Max)); -} - /// Given a loop with an deccreasing induction variable, is it possible to /// safely calculate the bounds of a new loop using the given Predicate. static bool isSafeDecreasingBound(const SCEV *Start, @@ -795,31 +784,6 @@ static bool isSafeIncreasingBound(const SCEV *Start, SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit)); } -static bool CannotBeMinInLoop(const SCEV *BoundSCEV, Loop *L, - ScalarEvolution &SE, bool Signed) { - unsigned BitWidth = cast(BoundSCEV->getType())->getBitWidth(); - APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) : - APInt::getMinValue(BitWidth); - auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; - return SE.isAvailableAtLoopEntry(BoundSCEV, L) && - SE.isLoopEntryGuardedByCond(L, Predicate, BoundSCEV, - SE.getConstant(Min)); -} - -static bool isKnownNonNegativeInLoop(const SCEV *BoundSCEV, const Loop *L, - ScalarEvolution &SE) { - const SCEV *Zero = SE.getZero(BoundSCEV->getType()); - return SE.isAvailableAtLoopEntry(BoundSCEV, L) && - SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, BoundSCEV, Zero); -} - -static bool isKnownNegativeInLoop(const SCEV *BoundSCEV, const Loop *L, - ScalarEvolution &SE) { - const SCEV *Zero = SE.getZero(BoundSCEV->getType()); - return SE.isAvailableAtLoopEntry(BoundSCEV, L) && - SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, BoundSCEV, Zero); -} - Optional LoopStructure::parseLoopStructure(ScalarEvolution &SE, BranchProbabilityInfo *BPI, Loop &L, @@ -977,12 +941,12 @@ LoopStructure::parseLoopStructure(ScalarEvolution &SE, // ... ... // } } if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) && - CannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/false)) { + cannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/false)) { Pred = ICmpInst::ICMP_UGT; RightSCEV = SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType())); DecreasedRightValueByOne = true; - } else if (CannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/true)) { + } else if (cannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/true)) { Pred = ICmpInst::ICMP_SGT; RightSCEV = SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType())); @@ -1042,11 +1006,11 @@ LoopStructure::parseLoopStructure(ScalarEvolution &SE, // ... ... // } } if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) && - CannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ false)) { + cannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ false)) { Pred = ICmpInst::ICMP_ULT; RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType())); IncreasedRightValueByOne = true; - } else if (CannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ true)) { + } else if (cannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ true)) { Pred = ICmpInst::ICMP_SLT; RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType())); IncreasedRightValueByOne = true; @@ -1514,7 +1478,7 @@ bool LoopConstrainer::run() { if (Increasing) ExitPreLoopAtSCEV = *SR.LowLimit; else { - if (CannotBeMinInLoop(*SR.HighLimit, &OriginalLoop, SE, + if (cannotBeMinInLoop(*SR.HighLimit, &OriginalLoop, SE, IsSignedPredicate)) ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS); else { @@ -1543,7 +1507,7 @@ bool LoopConstrainer::run() { if (Increasing) ExitMainLoopAtSCEV = *SR.HighLimit; else { - if (CannotBeMinInLoop(*SR.LowLimit, &OriginalLoop, SE, + if (cannotBeMinInLoop(*SR.LowLimit, &OriginalLoop, SE, IsSignedPredicate)) ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS); else { diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp index 3866395..a93d1ae 100644 --- a/llvm/lib/Transforms/Utils/LoopUtils.cpp +++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -928,3 +928,39 @@ void llvm::propagateIRFlags(Value *I, ArrayRef VL, Value *OpValue) { VecOp->andIRFlags(V); } } + +bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L, + ScalarEvolution &SE) { + const SCEV *Zero = SE.getZero(S->getType()); + return SE.isAvailableAtLoopEntry(S, L) && + SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, S, Zero); +} + +bool llvm::isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, + ScalarEvolution &SE) { + const SCEV *Zero = SE.getZero(S->getType()); + return SE.isAvailableAtLoopEntry(S, L) && + SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, S, Zero); +} + +bool llvm::cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, + bool Signed) { + unsigned BitWidth = cast(S->getType())->getBitWidth(); + APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) : + APInt::getMinValue(BitWidth); + auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; + return SE.isAvailableAtLoopEntry(S, L) && + SE.isLoopEntryGuardedByCond(L, Predicate, S, + SE.getConstant(Min)); +} + +bool llvm::cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, + bool Signed) { + unsigned BitWidth = cast(S->getType())->getBitWidth(); + APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) : + APInt::getMaxValue(BitWidth); + auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; + return SE.isAvailableAtLoopEntry(S, L) && + SE.isLoopEntryGuardedByCond(L, Predicate, S, + SE.getConstant(Max)); +} -- 2.7.4