aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Fix recent regression in gcc.dg/pr26719.c (6835035).Dale Johannesen2009-04-291-2/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70386 91177308-0d34-0410-b5e6-96231b3b80d8
* Update comments to reflect the current code.Dan Gohman2009-04-291-4/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70357 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70241 91177308-0d34-0410-b5e6-96231b3b80d8
* Handle ands with ~0 correctly too. This fixes PR4052.Dan Gohman2009-04-271-0/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70176 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70051 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify trunc(extend(x)) in SCEVs, just for completeness. Also fix some oddNick Lewycky2009-04-231-4/+12
| | | | | | | whitespace in the same file. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69870 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify trivial cast-of-cast SCEVs.Dan Gohman2009-04-221-0/+12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69809 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69749 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69704 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69655 91177308-0d34-0410-b5e6-96231b3b80d8
* This FIXME is fixed, now that SCEV understands pointers.Dan Gohman2009-04-211-3/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69651 91177308-0d34-0410-b5e6-96231b3b80d8
* Factor out a common base class from SCEVTruncateExpr, SCEVZeroExtendExpr,Dan Gohman2009-04-211-15/+13
| | | | | | | and SCEVSignExtendExpr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69649 91177308-0d34-0410-b5e6-96231b3b80d8
* Usage getAnalysisToUpdate for TargetData, per PR760.Dan Gohman2009-04-211-2/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69645 91177308-0d34-0410-b5e6-96231b3b80d8
* Introduce encapsulation for ScalarEvolution's TargetData object, and refactorDan Gohman2009-04-211-68/+122
| | | | | | | the code to minimize dependencies on TargetData. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69644 91177308-0d34-0410-b5e6-96231b3b80d8
* Move some assertion checks so they can do more complete checking.Dan Gohman2009-04-211-6/+8
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69643 91177308-0d34-0410-b5e6-96231b3b80d8
* Convert ScalarEvolution to use raw_ostream instead of OStream.Dan Gohman2009-04-211-22/+32
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69640 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a ScalarEvolution::getCouldNotCompute() function, and use itDan Gohman2009-04-181-12/+21
| | | | | | | instead of allocating and leaking new SCEVCouldNotCompute objects. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69452 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69307 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69258 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65382 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64918 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64810 91177308-0d34-0410-b5e6-96231b3b80d8
* Strengthen the "non-constant stride must dominate loop preheader" check.Evan Cheng2009-02-171-0/+40
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64703 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64407 91177308-0d34-0410-b5e6-96231b3b80d8
* Start generating arbitrary precision integer SCEVs. This removes the temporarynicholas2009-01-251-11/+1
| | | | | | | code that rounded up and capped the size. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62958 91177308-0d34-0410-b5e6-96231b3b80d8
* Reinstate r60509 from Dale:Nick Lewycky2009-01-161-0/+1
| | | | | | | Make the debugging dump be a full line. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62325 91177308-0d34-0410-b5e6-96231b3b80d8
* Wind SCEV back in time, to Nov 18th. This 'fixes' PR3275, PR3294, PR3295,Nick Lewycky2009-01-131-202/+41
| | | | | | | PR3296 and PR3302. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62160 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61600 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't try to analyze this "backward" case. This is overly conservative Nick Lewycky2009-01-021-0/+12
| | | | | | | pending a correct solution. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61589 91177308-0d34-0410-b5e6-96231b3b80d8
* Generalize support for analyzing loops to include SLE/SGE loop exit conditionsNick Lewycky2008-12-161-24/+23
| | | | | | | and support for non-unit strides with signed exit conditions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61082 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert my re-instated reverted commit, fixes the bootstrap build on x86-64 ↵Nick Lewycky2008-12-121-15/+15
| | | | | | linux. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60951 91177308-0d34-0410-b5e6-96231b3b80d8
* Sneaky, sneaky: move the -1 to the outside of the SMax. Reinstate theNick Lewycky2008-12-111-15/+15
| | | | | | | optimization of SGE/SLE with unit stride, now that it works properly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60881 91177308-0d34-0410-b5e6-96231b3b80d8
* Back out 60748 for now. It's breaking SPASS, 254.gap, and 464.h264ref.Evan Cheng2008-12-091-5/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60776 91177308-0d34-0410-b5e6-96231b3b80d8
* It's easy to handle SLE/SGE when the loop has a unit stride.Nick Lewycky2008-12-091-1/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60748 91177308-0d34-0410-b5e6-96231b3b80d8
* Minor cleanup. Use dyn_cast, not isa/cast pairs. No functionality change.Nick Lewycky2008-12-061-5/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60623 91177308-0d34-0410-b5e6-96231b3b80d8
* Make the debugging dump be a full line.Dale Johannesen2008-12-031-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60509 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a new SCEV representing signed division.Nick Lewycky2008-12-021-10/+67
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60407 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a utility function that detects whether a loop is guaranteed to be finite.Nick Lewycky2008-11-181-31/+127
| | | | | | | | | | | | Use it to safely handle less-than-or-equals-to exit conditions in loops. These also occur when the loop exit branch is exit on true because SCEV inverses the icmp predicate. Use it again to handle non-zero strides, but only with an unsigned comparison in the exit condition. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59528 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unused variable.Duncan Sands2008-11-181-3/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59515 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't brute-force analyze cubic or higher polynomials.Nick Lewycky2008-11-161-21/+0
| | | | | | | | If this patch causes a performance regression for anyone, please let me know, and it can be fixed in a different way with much more effort. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59384 91177308-0d34-0410-b5e6-96231b3b80d8
* Silence unused variable warning.Devang Patel2008-11-111-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59064 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't crash analyzing certain quadratics (addrec of {X,+,Y,+,1}).Nick Lewycky2008-11-031-0/+5
| | | | | | | We're still waiting on code that actually analyzes them properly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@58592 91177308-0d34-0410-b5e6-96231b3b80d8
* Disallow the construction of SCEVs with could-not-compute operands. Catch CNCsNick Lewycky2008-10-131-72/+6
| | | | | | | | returned by BinomialCoefficient and don't try to operate with them. This replaces the previous fix for PR2857. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@57431 91177308-0d34-0410-b5e6-96231b3b80d8
* Allow the construction of SCEVs with SCEVCouldNotCompute operands, byNick Lewycky2008-10-041-0/+67
| | | | | | | implementing folding. Fixes PR2857. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@57049 91177308-0d34-0410-b5e6-96231b3b80d8
* Finally re-apply r46959. This is made feasible by the combinationDan Gohman2008-09-161-2/+2
| | | | | | | of r56230, r56232, and r56246. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56247 91177308-0d34-0410-b5e6-96231b3b80d8
* Improve instcombine's handling of integer min and max in two ways:Dan Gohman2008-09-161-5/+0
| | | | | | | | | | | | | | | | | - Recognize expressions like "x > -1 ? x : 0" as min/max and turn them into expressions like "x < 0 ? 0 : x", which is easily recognizable as a min/max operation. - Refrain from folding expression like "y/2 < 1" to "y < 2" when the comparison is being used as part of a min or max idiom, like "y/2 < 1 ? 1 : y/2". In that case, the division has another use, so folding doesn't eliminate it, and obfuscates the min/max, making it harder to recognize as a min/max operation. These benefit ScalarEvolution, CodeGen, and anything else that wants to recognize integer min and max. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56246 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach ScalarEvolution to consider loop preheaders in the search forDan Gohman2008-09-151-8/+38
| | | | | | | | an if statement that guards a loop, to allow indvars to avoid smax operations in more situations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56232 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix WriteAsOperand to not emit a leading space character. AdjustDan Gohman2008-09-141-4/+4
| | | | | | | | | | | | | | | | | | | its callers to emit a space character before calling it when a space is needed. This fixes several spurious whitespace issues in ScalarEvolution's debug dumps. See the test changes for examples. This also fixes odd space-after-tab indentation in the output for switch statements, and changes calls from being printed like this: call void @foo( i32 %x ) to this: call void @foo(i32 %x) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56196 91177308-0d34-0410-b5e6-96231b3b80d8
* Extend ScalarEvolution's executesAtLeastOnce logic to be able toDan Gohman2008-08-121-55/+57
| | | | | | | | | continue past the first conditional branch when looking for a relevant test. This helps it avoid using MAX expressions in loop trip counts in more cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54697 91177308-0d34-0410-b5e6-96231b3b80d8
* Canonicalize nested AddRecs in by nesting them in order of loop depth.Dan Gohman2008-08-081-0/+13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54545 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2025-06-03 20:56:05 +0000