diff options
author | Dan Gohman <gohman@apple.com> | 2009-06-24 01:05:09 +0000 |
---|---|---|
committer | Dan Gohman <gohman@apple.com> | 2009-06-24 01:05:09 +0000 |
commit | 61e0c4c24a62428be531ddd4ac751733a7a26dc6 (patch) | |
tree | 159a03239e043f9a0b2773d9cc3fdbcd0c5bee1a /lib | |
parent | a5cc003c88a34783b1f8f09fea86298c58823cce (diff) | |
download | external_llvm-61e0c4c24a62428be531ddd4ac751733a7a26dc6.zip external_llvm-61e0c4c24a62428be531ddd4ac751733a7a26dc6.tar.gz external_llvm-61e0c4c24a62428be531ddd4ac751733a7a26dc6.tar.bz2 |
Teach GetMinSignBits about SCEVAddExprs.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74045 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 32 |
1 files changed, 32 insertions, 0 deletions
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 7abd0a5..436b79d 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -2402,6 +2402,38 @@ ScalarEvolution::GetMinSignBits(const SCEV* S) { getTypeSizeInBits(C->getOperand()->getType())); } + if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { + unsigned BitWidth = getTypeSizeInBits(A->getType()); + + // Special case decrementing a value (ADD X, -1): + if (const SCEVConstant *CRHS = dyn_cast<SCEVConstant>(A->getOperand(0))) + if (CRHS->isAllOnesValue()) { + SmallVector<const SCEV *, 4> OtherOps(A->op_begin() + 1, A->op_end()); + const SCEV *OtherOpsAdd = getAddExpr(OtherOps); + unsigned LZ = GetMinLeadingZeros(OtherOpsAdd); + + // If the input is known to be 0 or 1, the output is 0/-1, which is all + // sign bits set. + if (LZ == BitWidth - 1) + return BitWidth; + + // If we are subtracting one from a positive number, there is no carry + // out of the result. + if (LZ > 0) + return GetMinSignBits(OtherOpsAdd); + } + + // Add can have at most one carry bit. Thus we know that the output + // is, at worst, one more bit than the inputs. + unsigned Min = BitWidth; + for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) { + unsigned N = GetMinSignBits(A->getOperand(i)); + Min = std::min(Min, N) - 1; + if (Min == 0) return 1; + } + return 1; + } + if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { // For a SCEVUnknown, ask ValueTracking. return ComputeNumSignBits(U->getValue(), TD); |