aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/ScalarEvolution.cpp
AgeCommit message (Collapse)Author
2009-05-13Add three new helper routines, getNoopOrZeroExtend,Dan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71632 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-12When forgetting SCEVs for loop PHIs, don't forget SCEVUnknown values.Dan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71533 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-12Fix GetMinTrailingZeros for SCEVSignExtend and SCEVZeroExtendExpr toDan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71532 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-09Allow scalar evolution to compute iteration counts for loops with a Eli Friedman
pointer-based condition. This fixes PR3171. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71354 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-09Rename PaddedSize to AllocSize, in the hope that thisDuncan Sands
will make it more obvious what it represents, and stop it being confused with the StoreSize. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71349 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-09Don't attempt to handle unsized types in ScalarEvolution's GEP analyzer.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71302 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-08Fix bogus overflow checks by replacing them with actualDan Gohman
overflow checks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71284 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-08Fold trunc casts into add-recurrence expressions, allowing theDan Gohman
add-recurrence to be exposed. Add a new SCEV folding rule to help simplify expressions in the presence of these extra truncs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71264 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-08Fix another bug in r71252. This code supports GetElementPtrDan Gohman
constant exprs as well as instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71262 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-08Add memoization for getSCEVAtScope results for instructionsDan Gohman
which are not analyzed with SCEV techniques, which can require brute-forcing through a large number of instructions. This fixes a massive compile-time issue on 400.perlbench (in particular, the loop in MD5Transform). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71259 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-08Make the SCEV* form of getSCEVAtScope public, to allow ScalarEvolutionDan Gohman
clients to use it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71258 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-08Fix an error from r71252.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71255 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-08Factor out the code for creating SCEVs for GEPs into aDan Gohman
separate function. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71252 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-08Implement several new SCEV folding rules for UDiv SCEVs.Dan Gohman
This fixes an old FIXME, and is needed by some upcoming changes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71247 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-07SCEVComplexityCompare's new code was missing SCEVUDivExpr. ImplementDan Gohman
the SCEVUDivExpr case. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71173 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-07Make ScalarEvolution's GroupByComplexity more thorough. In additionDan Gohman
to sorting SCEVs by their kind, sort SCEVs of the same kind according to their operands. This helps avoid things like (a+b) being a distinct expression from (b+a). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71160 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-07Trim unnecessary headers. Code in Analysis shouldn't use TransformsDan Gohman
headers due to library dependencies. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71159 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-07Factor out a common base class between SCEVCommutativeExpr andDan Gohman
SCEVAddRecExpr. This eliminates redundant code for visiting all the operands of an expression. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71157 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-06Use stable_sort instead of plain sort to avoid the risk of generatingDan Gohman
trivially different code on different hosts (due to differing std::sort implementations). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71124 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-04Re-apply 70645, converting ScalarEvolution to useDan Gohman
CallbackVH, with fixes. allUsesReplacedWith need to walk the def-use chains and invalidate all users of a value that is replaced. SCEVs of users need to be recalcualted even if the new value is equivalent. Also, make forgetLoopPHIs walk def-use chains, since any SCEV that depends on a PHI should be recalculated when more information about that PHI becomes available. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70927 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-04Fix an 80-column violation.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70925 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-04Fix doxygen comment syntax.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70924 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-04Constify a bunch of SCEV-using code.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70919 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-03Revert r70645 for now; it's causing a variety of regressions.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70661 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-02Convert ScalarEvolution to use CallbackVH for its internal map. ThisDan Gohman
makes ScalarEvolution::deleteValueFromRecords, and it's code that subtly needed to be called before ReplaceAllUsesWith, unnecessary. It also makes ValueDeletionListener unnecessary. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70645 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-02When ScalarEvolution is told to forget the trip count for a loop, haveDan Gohman
it also forget any SCEVs associated with loop-header PHIs in the loop, as they may be dependent on trip count information. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70633 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-01When printing a SCEVUnknown with pointer type, don't print anDan Gohman
artificial "ptrtoint", as it tends to clutter up complicated expressions. The cast operators now print both source and destination types, which is usually sufficient. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70554 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-01Fix an 80-column violation.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70550 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-01When creating cast scevs, canonicalize the destination type. ThisDan Gohman
avoids duplicate scevs that differ only in type. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70549 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-01hasSCEV() was declared in ScalarEvolution.h, but never defined. This must haveTorok Edwin
gone lost during the pImpl conversion. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70536 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-30Add some comments, and tidy up some whitespace.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70510 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-30Extend ScalarEvolution's getBackedgeTakenCount to be able toDan Gohman
compute an upper-bound value for the trip count, in addition to the actual trip count. Use this to allow getZeroExtendExpr and getSignExtendExpr to fold casts in more cases. This may eventually morph into a more general value-range analysis capability; there are certainly plenty of places where more complete value-range information would allow more folding. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70509 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-30Don't try to mix integers and pointers in an icmp instructionDan Gohman
in getSCEVAtScope. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70495 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-30Fix ScalarEvolution::print to print a value for any Instruction withDan Gohman
a SCEVable type, not just integer types. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70463 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-29Implement getSCEVAtScope for SCEV cast expressions.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70422 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-29Generalize the cast-of-addrec folding to handle folding of SCEVs likeDan Gohman
(sext i8 {-128,+,1} to i64) to i64 {-128,+,1}, where the iteration crosses from negative to positive, but is still safe if the trip count is within range. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70421 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-29Include the source type in SCEV cast expression debug output, andDan Gohman
print sext, zext, and trunc, instead of signextend, zeroextend, and truncate, respectively, for consistency with the main IR. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70405 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-29Fix recent regression in gcc.dg/pr26719.c (6835035).Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70386 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-29Update comments to reflect the current code.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70357 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-27Teach getZeroExtendExpr and getSignExtendExpr to use trip-countDan Gohman
information to simplify [sz]ext({a,+,b}) to {zext(a),+,[zs]ext(b)}, as appropriate. These functions and the trip count code each call into the other, so this requires careful handling to avoid infinite recursion. During the initial trip count computation, conservative SCEVs are used, which are subsequently discarded once the trip count is actually known. Among other benefits, this change lets LSR automatically eliminate some unnecessary zext-inreg and sext-inreg operation where the operand is an induction variable. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70241 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-27Handle ands with ~0 correctly too. This fixes PR4052.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70176 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-25Handle ands with 0 and shifts by 0 correctly. These aren'tDan Gohman
common, but indvars shouldn't crash on them. This fixes PR4054. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70051 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-23Simplify trunc(extend(x)) in SCEVs, just for completeness. Also fix some oddNick Lewycky
whitespace in the same file. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69870 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-22Simplify trivial cast-of-cast SCEVs.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69809 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-21De-pImpl-ify ScalarEvolution. The pImpl pattern doesn't provide muchDan Gohman
practical benefit in the case of ScalarEvolution, and it's otherwise a nuisance. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69749 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-21When turning (ashr(shl(x, n), n)) into sext(trunc(x)), the width of theDan Gohman
type to truncate to should be the number of bits of the value that are preserved, not the number that are clobbered with sign-extension. This fixes regressions in ldecod. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69704 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-21Teach ScalarEvolution how to recognize zext-inreg and sext-inreg,Dan Gohman
as they appear in LLVM IR. This isn't particularly interesting on its own; this is just setting up some infrastructure. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69655 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-21This FIXME is fixed, now that SCEV understands pointers.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69651 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-21Factor out a common base class from SCEVTruncateExpr, SCEVZeroExtendExpr,Dan Gohman
and SCEVSignExtendExpr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69649 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-21Usage getAnalysisToUpdate for TargetData, per PR760.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69645 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-06-24 04:45:30 +0000