summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Fix a bug in the trip-count computation with And/Or. If either of theDan Gohman2009-06-221-8/+4
| | | | | | sides is CouldNotCompute, the resulting exact count must be CouldNotCompute. llvm-svn: 73920
* Remove the parent pointer from SCEV, since it did not end up being needed.Owen Anderson2009-06-221-30/+22
| | | | llvm-svn: 73907
* SCEVHandle is no more!Owen Anderson2009-06-221-256/+255
| | | | llvm-svn: 73906
* Fix some typos that Duncan noticed.Dan Gohman2009-06-221-2/+2
| | | | llvm-svn: 73903
* Banish global state from ScalarEvolution! SCEV uniquing is now done by ↵Owen Anderson2009-06-221-58/+50
| | | | | | | | | | | 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. llvm-svn: 73892
* Make use of getUMinFromMismatchedTypes when computing backedge-takenDan Gohman2009-06-221-14/+14
| | | | | | | | | | | | 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. llvm-svn: 73884
* Add a getUMinFromMismatchedTypes helper function.Dan Gohman2009-06-221-0/+16
| | | | llvm-svn: 73883
* Factor out code for computing umin and smin for SCEV expressions intoDan Gohman2009-06-221-7/+14
| | | | | | helper functions. Based on a patch by Nick Lewycky. llvm-svn: 73869
* Teach ScalarEvolution how to analyze loops with multiple exitDan Gohman2009-06-221-27/+221
| | | | | | | | | 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. llvm-svn: 73866
* Delete an unused variable.Dan Gohman2009-06-221-1/+0
| | | | llvm-svn: 73865
* Fix ScalarEvolution's backedge-taken count computations to check forDan Gohman2009-06-211-7/+29
| | | | | | | | overflow when computing a integer division to round up. Thanks to Nick Lewycky for noticing this! llvm-svn: 73862
* Generalize isLoopGuardedByCond's checking to consider twoDan Gohman2009-06-201-3/+27
| | | | | | | | | | 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. llvm-svn: 73807
* Use ScalarEvolution's new GetMinSignBits and GetMinLeadingZerosDan Gohman2009-06-201-3/+6
| | | | | | | in the loop backedge-taken count computation of the maximum possible trip count. llvm-svn: 73805
* Make GetMinTrailingZeros a member function of ScalarEvolution,Dan Gohman2009-06-191-22/+83
| | | | | | | | | | | 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. llvm-svn: 73794
* Make ScalarEvolution::print print getSCEVAtScope values forDan Gohman2009-06-191-2/+10
| | | | | | expressions, when interesting. llvm-svn: 73776
* Add a parent pointer to SCEV, in preparation for getting rid of the global ↵Owen Anderson2009-06-181-21/+26
| | | | | | uniquing tables. No functionality change. llvm-svn: 73728
* Recognize n != 0 ? n : 1 as umax(n, 1). Previously only ULT/UGT/ULE/UGEDan Gohman2009-06-181-0/+18
| | | | | | | comparisons were recognized for umax, but instcombine canonicalizes unsigned comparisons with zero to this simpler form. llvm-svn: 73717
* Update a comment to reflect the code.Dan Gohman2009-06-181-2/+1
| | | | llvm-svn: 73704
* Fix trailing whitespace from ScalarEvolution::print.Dan Gohman2009-06-181-2/+1
| | | | llvm-svn: 73666
* Teach ScalarEvolution how to recognize another xor(and(x, C), C) case.Dan Gohman2009-06-181-4/+19
| | | | | | | 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. llvm-svn: 73664
* Delete unnecessary braces.Dan Gohman2009-06-171-2/+1
| | | | llvm-svn: 73663
* Fix ScalarEvolution's Xor handling to not assume that an AndDan Gohman2009-06-171-3/+6
| | | | | | | that gets recognized with a SCEVZeroExtendExpr must be an And with a low-bits mask. With r73540, this is no longer the case. llvm-svn: 73594
* Instcombine's ShrinkDemandedConstant may strip bits out of constants,Dan Gohman2009-06-161-3/+18
| | | | | | | | obscuring what would otherwise be a low-bits mask. Use ComputeMaskedBits to compute what ShrinkDemandedConstant knew about to reconstruct a low-bits mask value. llvm-svn: 73540
* Support vector casts in more places, fixing a variety of assertionDan Gohman2009-06-151-3/+8
| | | | | | | | | | | | | | | 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. llvm-svn: 73431
* Implement more aggressive folding of add operand lists whenDan Gohman2009-06-141-0/+128
| | | | | | | | | | 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. llvm-svn: 73361
* Check for the short-circuiting condition before performingDan Gohman2009-06-141-1/+1
| | | | | | the potentially expensive erase. llvm-svn: 73359
* Do compare constant SCEV values in SCEVComplexityCompare, becauseDan Gohman2009-06-141-3/+12
| | | | | | | | 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. llvm-svn: 73358
* Convert several parts of the ScalarEvolution framework to useDan Gohman2009-06-141-37/+41
| | | | | | SmallVector instead of std::vector. llvm-svn: 73357
* Add a ScalarEvolution::getAnyExtendExpr utility function for performingDan Gohman2009-06-131-0/+59
| | | | | | extension with unspecified bits. llvm-svn: 73293
* Rename UnknownValue to CouldNotCompute, since it holds an instance ofDan Gohman2009-06-061-37/+37
| | | | | | SCEVCouldNotCompute, and not SCEVUnknown. llvm-svn: 72999
* Simplify.Devang Patel2009-06-051-15/+6
| | | | llvm-svn: 72970
* Remove some unnecessary #includes.Dan Gohman2009-06-051-1/+0
| | | | llvm-svn: 72948
* For the return type of SCEVUDivExpr, use the RHS' type instead ofDan Gohman2009-05-261-1/+6
| | | | | | | | 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. llvm-svn: 72424
* Various comment fixes.Dan Gohman2009-05-241-9/+14
| | | | llvm-svn: 72376
* Change ScalarEvolution::getSCEVAtScope to always return the original valueDan Gohman2009-05-241-21/+8
| | | | | | | | 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. llvm-svn: 72375
* Teach SCEV::isLoopInvariant and SCEV::hasComputableLoopEvolutionDan Gohman2009-05-201-2/+6
| | | | | | | about the convention from LoopInfo that a null Loop* means the entire function body. llvm-svn: 72152
* Make SCEVCallbackVH a private nested class inside ScalarEvolution, asDan Gohman2009-05-191-3/+3
| | | | | | it's an implementation detail. llvm-svn: 72122
* Teach SCEVExpander to expand arithmetic involving pointers into GEPDan Gohman2009-05-191-0/+7
| | | | | | | | | | | | | | | | 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. llvm-svn: 72093
* Silence Release-Asserts warnings.Daniel Dunbar2009-05-181-0/+1
| | | | llvm-svn: 72011
* Teach ScalarEvolution to recognize x^-1 in the case where non-demandedDan Gohman2009-05-181-0/+13
| | | | | | bits have been stripped out by instcombine. llvm-svn: 72010
* Delete a redundant 'else'.Dan Gohman2009-05-181-1/+1
| | | | llvm-svn: 72009
* Fix ScalarEvolution::isLoopGuardedByCond to accept a null Loop*, forDan Gohman2009-05-181-0/+4
| | | | | | | consistency with other routines that use a null Loop* to mean code not contained by any loop. llvm-svn: 72008
* Minor code cleanups. Do more of the work before the if statementsDan Gohman2009-05-181-16/+21
| | | | | | instead of within their controlling expressions. llvm-svn: 72007
* Add assertion checks to the SCEV operator creation methods to catchDan Gohman2009-05-181-0/+34
| | | | | | type mismatches. llvm-svn: 72006
* Make ScalarEvolution::isLoopGuardedByCond work even when the edgeDan Gohman2009-05-181-13/+27
| | | | | | entering a loop is a non-split critical edge. llvm-svn: 72004
* Add an isOne() utility function to ScalarEvolution, similar to isZero()Dan Gohman2009-05-181-1/+6
| | | | | | and similar to ConstantInt's isOne(). llvm-svn: 72003
* Add three new helper routines, getNoopOrZeroExtend,Dan Gohman2009-05-131-0/+47
| | | | | | | | | getNoopOrSignExtend, and getTruncateOrNoop. These are similar to getTruncateOrZeroExtend etc., except that they assert that the conversion is either not widening or narrowing, as appropriate. These will be used in some upcoming fixes. llvm-svn: 71632
* When forgetting SCEVs for loop PHIs, don't forget SCEVUnknown values.Dan Gohman2009-05-121-2/+12
| | | | | | | | | These values aren't analyzable, so they don't care if more information about the loop trip count can be had. Also, SCEVUnknown is used for a PHI while the PHI itself is being analyzed, so it needs to be left in the Scalars map. This fixes a variety of subtle issues. llvm-svn: 71533
* Fix GetMinTrailingZeros for SCEVSignExtend and SCEVZeroExtendExpr toDan Gohman2009-05-121-2/+2
| | | | | | | | | | return the correct value when the cast operand is all zeros. This ought to be pretty rare, because it would mean that the regular SCEV folding routines missed a case, though there are cases they might legitimately miss. Also, it's unlikely anything currently using GetMinTrailingZeros cares about this case. llvm-svn: 71532
* Allow scalar evolution to compute iteration counts for loops with a Eli Friedman2009-05-091-19/+8
| | | | | | pointer-based condition. This fixes PR3171. llvm-svn: 71354
OpenPOWER on IntegriCloud