aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/ScalarEvolution.cpp
AgeCommit message (Collapse)Author
2009-07-06Finish LLVMContext-ing lib/Analysis. This required pushing LLVMContext's ↵Owen Anderson
through the ValueTracking API. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74873 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-06Thread LLVMContext through the constant folding APIs, which touches a lot of ↵Owen Anderson
files. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74844 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-04When comparing constants, consider a less wide constant to be "less complex"Nick Lewycky
than a wider one, before trying to compare their contents which will crash if their sizes are different. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74792 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-30Minor code cleanups.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74551 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-29Use getSCEV instead of getUnknown to create a SCEV for aDan Gohman
Constant. This lets ConstantInts be handled as SCEVConstant instead of SCEVUnknown, as getUnknown no longer has special-case code for ConstantInt and friends. This usually doesn't affect the final output, since the constants end up getting folded later, but it does make intermediate expressions more obvious in many cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74459 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-29Don't cache PHI exit values from exhaustive evaluations, becauseDan Gohman
an individual exhaustive evaluation reflects only the exit value implied by an individual exit, which may differ from the actual exit value of the loop if there are other exits. This fixes PR4477. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74447 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-29Simplify this code, and avoid using APInt(). This fixesDan Gohman
(otherwise harmless) uninitialized value warnings that Duncan found with gcc-4.4. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74437 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-27Convert ScalarEvolution to use BumpPtrAllocator and FoldingSet, insteadDan Gohman
of a team of individual allocations and a team of std::maps. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74393 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-26Fix ScalarEvolution::getAddRecExpr's code which canonicalized theDan Gohman
nesting order of nested AddRec expressions to skip the transformation if it would introduce an AddRec with operands not loop-invariant with respect to its loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74343 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-26Fix SCEVAddRecExpr::isLoopInvariant to test if all of its operandsDan Gohman
are loop invariant, not just the start operand. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74338 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24Minor whitespace cleanups.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74074 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24Simplify [su]max(MAX, n) to MAX. This comes up in loop tripcountDan Gohman
computations in loops with multiple exits. Adjust the testcase for PR4436 so that the relevant portion isn't optimized away. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74073 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24Delete some orphaned comments, fix some 80-column violations,Dan Gohman
and tidy up a few other formatting issues. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74060 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24Extend ScalarEvolution's multiple-exit support to compute exactDan Gohman
trip counts in more cases. Generalize ScalarEvolution's isLoopGuardedByCond code to recognize And and Or conditions, splitting the code out into an isNecessaryCond helper function so that it can evaluate Ands and Ors recursively, and make SCEVExpander be much more aggressive about hoisting instructions out of loops. test/CodeGen/X86/pr3495.ll has an additional instruction now, but it appears to be due to an arbitrary register allocation difference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74048 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24Teach GetMinSignBits about SCEVAddExprs.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74045 91177308-0d34-0410-b5e6-96231b3b80d8
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
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-17 06:33:03 +0000