aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/ScalarEvolution.cpp
AgeCommit message (Collapse)Author
2009-06-24Move the special cases for constants out of getUnknown and intoDan Gohman
createSCEV. Also, recognize UndefValue in createSCEV. Change getIntegerSCEV's comment to avoid mentioning FP types, and re-implement it in terms of getConstant instead of getUnknown. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74041 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24Use ScalarEvolution::getConstant instead of getUnknown to createDan Gohman
SCEVConstants. This cleanup is a step toward letting getUnknown be simpler. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74037 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24Include the maximum trip count expression in ScalarEvolution's print output.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74035 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24Add an isAllOnesValue utility function, similar to isZero and isOne.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74032 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-22Fix a bug in the trip-count computation with And/Or. If either of theDan Gohman
sides is CouldNotCompute, the resulting exact count must be CouldNotCompute. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73920 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-22Remove the parent pointer from SCEV, since it did not end up being needed.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73907 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-22SCEVHandle is no more!Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73906 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-22Fix some typos that Duncan noticed.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73903 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-22Banish global state from ScalarEvolution! SCEV uniquing is now done by ↵Owen Anderson
tables attached to the ScalarEvolution pass. This also throws out the SCEV reference counting scheme, as the the SCEVs now have a lifetime controlled by the ScalarEvolution pass. Note that SCEVHandle is now a no-op, and will be remove in a future commit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73892 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-22Make use of getUMinFromMismatchedTypes when computing backedge-takenDan Gohman
counts for loops with multiple exits, replacing more conservative code which only handled constants. This is derived from a patch by Nick Lewycky. This also fixes llc aborts in ClamAV and others, as getUMinFromMismatchedTypes takes care of balancing the types before working with them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73884 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-22Add a getUMinFromMismatchedTypes helper function.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73883 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-22Factor out code for computing umin and smin for SCEV expressions intoDan Gohman
helper functions. Based on a patch by Nick Lewycky. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73869 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-22Teach ScalarEvolution how to analyze loops with multiple exitDan Gohman
blocks, and also exit blocks with multiple conditions (combined with (bitwise) ands and ors). It's often infeasible to compute an exact trip count in such cases, but a useful upper bound can often be found. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73866 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-22Delete an unused variable.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73865 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-21Fix ScalarEvolution's backedge-taken count computations to check forDan Gohman
overflow when computing a integer division to round up. Thanks to Nick Lewycky for noticing this! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73862 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-20Generalize isLoopGuardedByCond's checking to consider twoDan Gohman
SCEVUnknowns with identical Instructions to be equal. This allows it to analze cases such as the attached testcase, where the front-end has cloned the loop controlling expression. Along with r73805, this lets IndVarSimplify eliminate all the sign-extend casts in the loop in the attached testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73807 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-20Use ScalarEvolution's new GetMinSignBits and GetMinLeadingZerosDan Gohman
in the loop backedge-taken count computation of the maximum possible trip count. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73805 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-19Make GetMinTrailingZeros a member function of ScalarEvolution,Dan Gohman
so that it can access the TargetData member (when available) and use ValueTracking.h information to compute information for SCEVUnknown Values. Also add GetMinLeadingZeros and GetMinSignBits functions, with minimal implementations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73794 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-19Make ScalarEvolution::print print getSCEVAtScope values forDan Gohman
expressions, when interesting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73776 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-18Add a parent pointer to SCEV, in preparation for getting rid of the global ↵Owen Anderson
uniquing tables. No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73728 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-18Recognize n != 0 ? n : 1 as umax(n, 1). Previously only ULT/UGT/ULE/UGEDan Gohman
comparisons were recognized for umax, but instcombine canonicalizes unsigned comparisons with zero to this simpler form. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73717 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-18Update a comment to reflect the code.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73704 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-18Fix trailing whitespace from ScalarEvolution::print.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73666 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-18Teach ScalarEvolution how to recognize another xor(and(x, C), C) case.Dan Gohman
If C is a single bit and the and gets analyzed as a truncate and zero-extend, the xor can be represnted as an add. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73664 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-17Delete unnecessary braces.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73663 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-17Fix ScalarEvolution's Xor handling to not assume that an AndDan Gohman
that gets recognized with a SCEVZeroExtendExpr must be an And with a low-bits mask. With r73540, this is no longer the case. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73594 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-16Instcombine's ShrinkDemandedConstant may strip bits out of constants,Dan Gohman
obscuring what would otherwise be a low-bits mask. Use ComputeMaskedBits to compute what ShrinkDemandedConstant knew about to reconstruct a low-bits mask value. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73540 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-15Support vector casts in more places, fixing a variety of assertionDan Gohman
failures. To support this, add some utility functions to Type to help support vector/scalar-independent code. Change ConstantInt::get and ConstantFP::get to support vector types, and add an overload to ConstantInt::get that uses a static IntegerType type, for convenience. Introduce a new getConstant method for ScalarEvolution, to simplify common use cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73431 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-14Implement more aggressive folding of add operand lists whenDan Gohman
they contain multiplications of constants with add operations. This helps simplify several kinds of things; in particular it helps simplify expressions like ((-1 * (%a + %b)) + %a) to %b, as expressions like this often come up in loop trip count computations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73361 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-14Check for the short-circuiting condition before performingDan Gohman
the potentially expensive erase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73359 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-14Do compare constant SCEV values in SCEVComplexityCompare, becauseDan Gohman
even though the order doesn't matter at the top level of an expression, it does matter when the constant is a subexpression of an n-ary expression, because n-ary expressions are sorted lexicographically. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73358 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-14Convert several parts of the ScalarEvolution framework to useDan Gohman
SmallVector instead of std::vector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73357 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-13Add a ScalarEvolution::getAnyExtendExpr utility function for performingDan Gohman
extension with unspecified bits. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73293 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-06Rename UnknownValue to CouldNotCompute, since it holds an instance ofDan Gohman
SCEVCouldNotCompute, and not SCEVUnknown. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72999 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-05Simplify.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72970 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-05Remove some unnecessary #includes.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72948 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-26For the return type of SCEVUDivExpr, use the RHS' type instead ofDan Gohman
that of the LHS. It doesn't matter for correctness, but the LHS is more likely than the RHS to be a pointer type in exotic cases, and it's more tidy to have it return the integer type. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72424 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-24Various comment fixes.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72376 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-24Change ScalarEvolution::getSCEVAtScope to always return the original valueDan Gohman
in the case where a loop exit value cannot be computed, instead of only in some cases while using SCEVCouldNotCompute in others. This simplifies getSCEVAtScope's callers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72375 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-20Teach SCEV::isLoopInvariant and SCEV::hasComputableLoopEvolutionDan Gohman
about the convention from LoopInfo that a null Loop* means the entire function body. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72152 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-19Make SCEVCallbackVH a private nested class inside ScalarEvolution, asDan Gohman
it's an implementation detail. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72122 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-19Teach SCEVExpander to expand arithmetic involving pointers into GEPDan Gohman
instructions. It attempts to create high-level multi-operand GEPs, though in cases where this isn't possible it falls back to casting the pointer to i8* and emitting a GEP with that. Using GEP instructions instead of ptrtoint+arithmetic+inttoptr helps pointer analyses that don't use ScalarEvolution, such as BasicAliasAnalysis. Also, make the AddrModeMatcher more aggressive in handling GEPs. Previously it assumed that operand 0 of a GEP would require a register in almost all cases. It now does extra checking and can do more matching if operand 0 of the GEP is foldable. This fixes a problem that was exposed by SCEVExpander using GEPs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72093 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-18Silence Release-Asserts warnings.Daniel Dunbar
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72011 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-18Teach ScalarEvolution to recognize x^-1 in the case where non-demandedDan Gohman
bits have been stripped out by instcombine. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72010 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-18Delete a redundant 'else'.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72009 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-18Fix ScalarEvolution::isLoopGuardedByCond to accept a null Loop*, forDan Gohman
consistency with other routines that use a null Loop* to mean code not contained by any loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72008 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-18Minor code cleanups. Do more of the work before the if statementsDan Gohman
instead of within their controlling expressions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72007 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-18Add assertion checks to the SCEV operator creation methods to catchDan Gohman
type mismatches. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72006 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-18Make ScalarEvolution::isLoopGuardedByCond work even when the edgeDan Gohman
entering a loop is a non-split critical edge. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72004 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-18Add an isOne() utility function to ScalarEvolution, similar to isZero()Dan Gohman
and similar to ConstantInt's isOne(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72003 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-06-24 00:27:58 +0000