summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Trim unnecessary headers. Code in Analysis shouldn't use TransformsDan Gohman2009-05-071-3/+0
| | | | | | headers due to library dependencies. llvm-svn: 71159
* Factor out a common base class between SCEVCommutativeExpr andDan Gohman2009-05-071-10/+1
| | | | | | | SCEVAddRecExpr. This eliminates redundant code for visiting all the operands of an expression. llvm-svn: 71157
* Use stable_sort instead of plain sort to avoid the risk of generatingDan Gohman2009-05-061-1/+1
| | | | | | | trivially different code on different hosts (due to differing std::sort implementations). llvm-svn: 71124
* Re-apply 70645, converting ScalarEvolution to useDan Gohman2009-05-041-80/+114
| | | | | | | | | | | | 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. llvm-svn: 70927
* Fix an 80-column violation.Dan Gohman2009-05-041-1/+2
| | | | llvm-svn: 70925
* Fix doxygen comment syntax.Dan Gohman2009-05-041-1/+1
| | | | llvm-svn: 70924
* Constify a bunch of SCEV-using code.Dan Gohman2009-05-041-59/+61
| | | | llvm-svn: 70919
* Revert r70645 for now; it's causing a variety of regressions.Dan Gohman2009-05-031-25/+33
| | | | llvm-svn: 70661
* Convert ScalarEvolution to use CallbackVH for its internal map. ThisDan Gohman2009-05-021-33/+25
| | | | | | | | | makes ScalarEvolution::deleteValueFromRecords, and it's code that subtly needed to be called before ReplaceAllUsesWith, unnecessary. It also makes ValueDeletionListener unnecessary. llvm-svn: 70645
* When ScalarEvolution is told to forget the trip count for a loop, haveDan Gohman2009-05-021-3/+11
| | | | | | | it also forget any SCEVs associated with loop-header PHIs in the loop, as they may be dependent on trip count information. llvm-svn: 70633
* When printing a SCEVUnknown with pointer type, don't print anDan Gohman2009-05-011-4/+0
| | | | | | | | artificial "ptrtoint", as it tends to clutter up complicated expressions. The cast operators now print both source and destination types, which is usually sufficient. llvm-svn: 70554
* Fix an 80-column violation.Dan Gohman2009-05-011-1/+2
| | | | llvm-svn: 70550
* When creating cast scevs, canonicalize the destination type. ThisDan Gohman2009-05-011-0/+9
| | | | | | avoids duplicate scevs that differ only in type. llvm-svn: 70549
* hasSCEV() was declared in ScalarEvolution.h, but never defined. This must haveTorok Edwin2009-05-011-0/+6
| | | | | | gone lost during the pImpl conversion. llvm-svn: 70536
* Add some comments, and tidy up some whitespace.Dan Gohman2009-04-301-5/+7
| | | | llvm-svn: 70510
* Extend ScalarEvolution's getBackedgeTakenCount to be able toDan Gohman2009-04-301-65/+127
| | | | | | | | | | | | 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. llvm-svn: 70509
* Don't try to mix integers and pointers in an icmp instructionDan Gohman2009-04-301-12/+19
| | | | | | in getSCEVAtScope. llvm-svn: 70495
* Fix ScalarEvolution::print to print a value for any Instruction withDan Gohman2009-04-301-1/+1
| | | | | | a SCEVable type, not just integer types. llvm-svn: 70463
* Implement getSCEVAtScope for SCEV cast expressions.Dan Gohman2009-04-291-2/+25
| | | | llvm-svn: 70422
* Generalize the cast-of-addrec folding to handle folding of SCEVs likeDan Gohman2009-04-291-46/+33
| | | | | | | | (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. llvm-svn: 70421
* Include the source type in SCEV cast expression debug output, andDan Gohman2009-04-291-3/+3
| | | | | | | print sext, zext, and trunc, instead of signextend, zeroextend, and truncate, respectively, for consistency with the main IR. llvm-svn: 70405
* Fix recent regression in gcc.dg/pr26719.c (6835035).Dale Johannesen2009-04-291-2/+5
| | | | llvm-svn: 70386
* Update comments to reflect the current code.Dan Gohman2009-04-291-4/+4
| | | | llvm-svn: 70357
* Teach getZeroExtendExpr and getSignExtendExpr to use trip-countDan Gohman2009-04-271-9/+133
| | | | | | | | | | | | | | | | | 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. llvm-svn: 70241
* Handle ands with ~0 correctly too. This fixes PR4052.Dan Gohman2009-04-271-0/+2
| | | | llvm-svn: 70176
* Handle ands with 0 and shifts by 0 correctly. These aren'tDan Gohman2009-04-251-2/+9
| | | | | | common, but indvars shouldn't crash on them. This fixes PR4054. llvm-svn: 70051
* Simplify trunc(extend(x)) in SCEVs, just for completeness. Also fix some oddNick Lewycky2009-04-231-4/+12
| | | | | | whitespace in the same file. llvm-svn: 69870
* Simplify trivial cast-of-cast SCEVs.Dan Gohman2009-04-221-0/+12
| | | | llvm-svn: 69809
* De-pImpl-ify ScalarEvolution. The pImpl pattern doesn't provide muchDan Gohman2009-04-211-452/+165
| | | | | | | practical benefit in the case of ScalarEvolution, and it's otherwise a nuisance. llvm-svn: 69749
* When turning (ashr(shl(x, n), n)) into sext(trunc(x)), the width of theDan Gohman2009-04-211-1/+1
| | | | | | | | 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. llvm-svn: 69704
* Teach ScalarEvolution how to recognize zext-inreg and sext-inreg,Dan Gohman2009-04-211-0/+27
| | | | | | | as they appear in LLVM IR. This isn't particularly interesting on its own; this is just setting up some infrastructure. llvm-svn: 69655
* This FIXME is fixed, now that SCEV understands pointers.Dan Gohman2009-04-211-3/+0
| | | | llvm-svn: 69651
* Factor out a common base class from SCEVTruncateExpr, SCEVZeroExtendExpr,Dan Gohman2009-04-211-15/+13
| | | | | | and SCEVSignExtendExpr. llvm-svn: 69649
* Usage getAnalysisToUpdate for TargetData, per PR760.Dan Gohman2009-04-211-2/+1
| | | | llvm-svn: 69645
* Introduce encapsulation for ScalarEvolution's TargetData object, and refactorDan Gohman2009-04-211-68/+122
| | | | | | the code to minimize dependencies on TargetData. llvm-svn: 69644
* Move some assertion checks so they can do more complete checking.Dan Gohman2009-04-211-6/+8
| | | | llvm-svn: 69643
* Convert ScalarEvolution to use raw_ostream instead of OStream.Dan Gohman2009-04-211-22/+32
| | | | llvm-svn: 69640
* Add a ScalarEvolution::getCouldNotCompute() function, and use itDan Gohman2009-04-181-12/+21
| | | | | | instead of allocating and leaking new SCEVCouldNotCompute objects. llvm-svn: 69452
* Fix a bug with inttoptr/ptrtoint casts where the pointer has a differentDan Gohman2009-04-161-3/+6
| | | | | | | | size from the integer, requiring zero extension or truncation. Don't create ZExtInsts with pointer types. This fixes a regression in consumer-jpeg. llvm-svn: 69307
* Expand GEPs in ScalarEvolution expressions. SCEV expressions can nowDan Gohman2009-04-161-122/+283
| | | | | | | | | | | | | | | | | | | | | have pointer types, though in contrast to C pointer types, SCEV addition is never implicitly scaled. This not only eliminates the need for special code like IndVars' EliminatePointerRecurrence and LSR's own GEP expansion code, it also does a better job because it lets the normal optimizations handle pointer expressions just like integer expressions. Also, since LLVM IR GEPs can't directly index into multi-dimensional VLAs, moving the GEP analysis out of client code and into the SCEV framework makes it easier for clients to handle multi-dimensional VLAs the same way as other arrays. Some existing regression tests show improved optimization. test/CodeGen/ARM/2007-03-13-InstrSched.ll in particular improved to the point where if-conversion started kicking in; I turned it off for this test to preserve the intent of the test. llvm-svn: 69258
* Rename ScalarEvolution's getIterationCount to getBackedgeTakenCount,Dan Gohman2009-02-241-76/+99
| | | | | | | | | to more accurately describe what it does. Expand its doxygen comment to describe what the backedge-taken count is and how it differs from the actual iteration count of the loop. Adjust names and comments in associated code accordingly. llvm-svn: 65382
* Use a sign-extend instead of a zero-extend when promoting aDan Gohman2009-02-181-0/+15
| | | | | | | | | | | | trip count value when the original loop iteration condition is signed and the canonical induction variable won't undergo signed overflow. This isn't required for correctness; it just preserves more information about original loop iteration values. Add a getTruncateOrSignExtend method to ScalarEvolution, following getTruncateOrZeroExtend. llvm-svn: 64918
* Add a method to ScalarEvolution for telling it when a loop has beenDan Gohman2009-02-171-0/+16
| | | | | | | | | | | modified in a way that may effect the trip count calculation. Change IndVars to use this method when it rewrites pointer or floating-point induction variables instead of using a doInitialization method to sneak these changes in before ScalarEvolution has a chance to see the loop. This eliminates the need for LoopPass to depend on ScalarEvolution. llvm-svn: 64810
* Strengthen the "non-constant stride must dominate loop preheader" check.Evan Cheng2009-02-171-0/+40
| | | | llvm-svn: 64703
* Teach IndVarSimplify to optimize code using the C "int" type forDan Gohman2009-02-121-27/+73
| | | | | | | | | | | | | | | | | | | | | | | | | | | | loop induction on LP64 targets. When the induction variable is used in addressing, IndVars now is usually able to inserst a 64-bit induction variable and eliminates the sign-extending cast. This is also useful for code using C "short" types for induction variables on targets with 32-bit addressing. Inserting a wider induction variable is easy; the tricky part is determining when trunc(sext(i)) expressions are no-ops. This requires range analysis of the loop trip count. A common case is when the original loop iteration starts at 0 and exits when the induction variable is signed-less-than a fixed value; this case is now handled. This replaces IndVarSimplify's OptimizeCanonicalIVType. It was doing the same optimization, but it was limited to loops with constant trip counts, because it was running after the loop rewrite, and the information about the original induction variable is lost by that point. Rename ScalarEvolution's executesAtLeastOnce to isLoopGuardedByCond, generalize it to be able to test for ICMP_NE conditions, and move it to be a public function so that IndVars can use it. llvm-svn: 64407
* Start generating arbitrary precision integer SCEVs. This removes the temporaryNick Lewycky2009-01-251-11/+1
| | | | | | code that rounded up and capped the size. llvm-svn: 62958
* Reinstate r60509 from Dale:Nick Lewycky2009-01-161-0/+1
| | | | | | Make the debugging dump be a full line. llvm-svn: 62325
* Wind SCEV back in time, to Nov 18th. This 'fixes' PR3275, PR3294, PR3295,Nick Lewycky2009-01-131-202/+41
| | | | | | PR3296 and PR3302. llvm-svn: 62160
* We know it's always a SCEVConstant if it gets here, so just cast it andNick Lewycky2009-01-031-6/+2
| | | | | | inline the only use of isNegative. Fixes warning reported by Mike Stump. llvm-svn: 61600
* Don't try to analyze this "backward" case. This is overly conservative Nick Lewycky2009-01-021-0/+12
| | | | | | pending a correct solution. llvm-svn: 61589
OpenPOWER on IntegriCloud