summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Remove an irrelevant comment.Dan Gohman2009-05-191-3/+1
| | | | llvm-svn: 72132
* Trim unneeded #includes.Dan Gohman2009-05-191-2/+0
| | | | llvm-svn: 72130
* Teach SCEVExpander to expand arithmetic involving pointers into GEPDan Gohman2009-05-191-6/+6
| | | | | | | | | | | | | | | | 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
* Use abs64 in one more place.Dale Johannesen2009-05-141-1/+1
| | | | llvm-svn: 71775
* Factor the code for collecting IV users out of LSR into an IVUsers class,Dan Gohman2009-05-121-566/+369
| | | | | | | | | | | | | | | | | | | | | | | | and generalize it so that it can be used by IndVarSimplify. Implement the base IndVarSimplify transformation code using IVUsers. This removes TestOrigIVForWrap and associated code, as ScalarEvolution now has enough builtin overflow detection and folding logic to handle all the same cases, and more. Run "opt -iv-users -analyze -disable-output" on your favorite loop for an example of what IVUsers does. This lets IndVarSimplify eliminate IV casts and compute trip counts in more cases. Also, this happens to finally fix the remaining testcases in PR1301. Now that IndVarSimplify is being more aggressive, it occasionally runs into the problem where ScalarEvolutionExpander's code for avoiding duplicate expansions makes it difficult to ensure that all expanded instructions dominate all the instructions that will use them. As a temporary measure, IndVarSimplify now uses a FixUsesBeforeDefs function to fix up instructions inserted by SCEVExpander. Fortunately, this code is contained, and can be easily removed once a more comprehensive solution is available. llvm-svn: 71535
* Re-apply 70645, converting ScalarEvolution to useDan Gohman2009-05-041-2/+0
| | | | | | | | | | | | 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
* Revert r70645 for now; it's causing a variety of regressions.Dan Gohman2009-05-031-0/+2
| | | | llvm-svn: 70661
* Convert ScalarEvolution to use CallbackVH for its internal map. ThisDan Gohman2009-05-021-2/+0
| | | | | | | | | makes ScalarEvolution::deleteValueFromRecords, and it's code that subtly needed to be called before ReplaceAllUsesWith, unnecessary. It also makes ValueDeletionListener unnecessary. llvm-svn: 70645
* Remove an obsolete comment.Dan Gohman2009-04-271-5/+3
| | | | llvm-svn: 70262
* Fix PR 4086, a bug in FP IV elimination.Dale Johannesen2009-04-271-2/+4
| | | | llvm-svn: 70247
* Change SCEVExpander's expandCodeFor to provide more flexibilityDan Gohman2009-04-231-15/+12
| | | | | | | | | | | with the persistent insertion point, and change IndVars to make use of it. This fixes a bug where IndVars was holding on to a stale insertion point and forcing the SCEVExpander to continue to use it. This fixes PR4038. llvm-svn: 69892
* Make sure both operands have binary instructions have the same type.Evan Cheng2009-04-221-11/+23
| | | | llvm-svn: 69844
* A few more places where the check of use_empty is needed.Evan Cheng2009-04-221-0/+3
| | | | llvm-svn: 69842
* Avoid deferencing use_begin() if value does not have a use.Evan Cheng2009-04-221-0/+1
| | | | llvm-svn: 69836
* Introduce encapsulation for ScalarEvolution's TargetData object, and refactorDan Gohman2009-04-211-20/+20
| | | | | | the code to minimize dependencies on TargetData. llvm-svn: 69644
* Use more const qualifiers with SCEV interfaces.Dan Gohman2009-04-181-4/+5
| | | | llvm-svn: 69450
* Expand GEPs in ScalarEvolution expressions. SCEV expressions can nowDan Gohman2009-04-161-122/+35
| | | | | | | | | | | | | | | | | | | | | 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
* Eliminate zext over (iv | const) or (signed iv),Dale Johannesen2009-04-151-22/+77
| | | | | | | | and sext over (iv | const), if a longer iv is available. Allow expressions to have more than one zext/sext parent. All from OpenSSL. llvm-svn: 69241
* Eliminate zext over (iv & const) or ((iv+const)&const)Dale Johannesen2009-04-151-31/+89
| | | | | | | if a longer iv is available. These subscript forms are not common; they're a bottleneck in OpenSSL. llvm-svn: 69215
* Enhance induction variable code to remove theDale Johannesen2009-04-151-40/+121
| | | | | | | | | sext around sext(shorter IV + constant), using a longer IV instead, when it can figure out the add can't overflow. This comes up a lot in subscripting; mainly affects 64 bit. llvm-svn: 69123
* Rename ScalarEvolution's getIterationCount to getBackedgeTakenCount,Dan Gohman2009-02-241-36/+35
| | | | | | | | | 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
* Back out the change in 64918 that used sign-extensions when promotingDan Gohman2009-02-231-34/+12
| | | | | | | | | trip counts that use signed comparisons. It's not obviously the best approach for preserving trip count information, and at any rate there isn't anything in the tree right now that makes use of that, so for now always using zero-extensions is preferable. llvm-svn: 65347
* IndVarSimplify preserves ScalarEvolution. In theDan Gohman2009-02-231-0/+1
| | | | | | | -std-compile-opts sequence, this avoids the need for ScalarEvolution to be rerun before LoopDeletion. llvm-svn: 65318
* Use a sign-extend instead of a zero-extend when promoting aDan Gohman2009-02-181-15/+39
| | | | | | | | | | | | 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
* Simplify by using dyn_cast instead of isa and cast.Dan Gohman2009-02-181-6/+5
| | | | llvm-svn: 64917
* Fix a corner case in the new indvars promotion logic: if thereDan Gohman2009-02-181-19/+25
| | | | | | | | | | are multiple IV's in a loop, some of them may under go signed or unsigned wrapping even if the IV that's used in the loop exit condition doesn't. Restrict sign-extension-elimination and zero-extension-elimination to only those that operate on the original loop-controlling IV. llvm-svn: 64866
* Add a method to ScalarEvolution for telling it when a loop has beenDan Gohman2009-02-171-9/+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
* Delete trailing whitespace.Dan Gohman2009-02-171-34/+34
| | | | llvm-svn: 64784
* Fix 80-column violation.Dan Gohman2009-02-171-1/+2
| | | | llvm-svn: 64766
* Simplify; fix some 80-column violations.Dan Gohman2009-02-171-6/+7
| | | | llvm-svn: 64702
* Delete this long-commented-out code. The situation it seems to haveDan Gohman2009-02-161-26/+0
| | | | | | | been written for is no longer relevant with the elimination of signed and unsigned types. llvm-svn: 64625
* Extend the IndVarSimplify support for promoting induction variables:Dan Gohman2009-02-141-44/+134
| | | | | | | | | - Test for signed and unsigned wrapping conditions, instead of just testing for non-negative induction ranges. - Handle loops with GT comparisons, in addition to LT comparisons. - Support more cases of induction variables that don't start at 0. llvm-svn: 64532
* Clarify debug output.Dan Gohman2009-02-141-1/+1
| | | | llvm-svn: 64531
* Simplify some code. hasComputableLoopEvolution is overkill in this case.Dan Gohman2009-02-141-9/+8
| | | | | | No functionality change. llvm-svn: 64530
* Teach IndVarSimplify to optimize code using the C "int" type forDan Gohman2009-02-121-226/+200
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Revert r60042. IndVarSimplify should check if APFloat is PPCDoubleDouble ↵Evan Cheng2008-11-261-0/+2
| | | | | | first before trying to convert it to an integer. llvm-svn: 60072
* Cast to remove warning about comparing signed and unsigned.Bill Wendling2008-11-181-1/+1
| | | | llvm-svn: 59518
* Give SIToFPInst preference over UIToFPInst because it is faster on platforms ↵Devang Patel2008-11-181-3/+20
| | | | | | that are widely used. llvm-svn: 59476
* While handling floating point IVs lift restrictions on initial value and ↵Devang Patel2008-11-171-25/+42
| | | | | | increment value. llvm-svn: 59471
* Handle floating point ivs during doInitialization().Devang Patel2008-11-171-144/+130
| | | | llvm-svn: 59466
* eliminate some std::set's.Chris Lattner2008-11-161-9/+10
| | | | llvm-svn: 59409
* Turn floating point IVs into integer IVs where possible.Devang Patel2008-11-031-0/+150
| | | | | | | | This allows SCEV users to effectively calculate trip count. LSR later on transforms back integer IVs to floating point IVs later on to avoid int-to-float casts inside the loop. llvm-svn: 58625
* Change create*Pass factory functions to return Pass* instead ofDaniel Dunbar2008-10-221-1/+1
| | | | | | | | | | | LoopPass*. - Although less precise, this means they can be used in clients without RTTI (who would otherwise need to include LoopPass.h, which eventually includes things using dynamic_cast). This was the simplest solution that presented itself, but I am happy to use a better one if available. llvm-svn: 58010
* fix white spaces.Devang Patel2008-09-101-5/+5
| | | | llvm-svn: 56056
* if loop induction variable is always sign or zero extended then Devang Patel2008-09-091-1/+118
| | | | | | extend the type of induction variable. llvm-svn: 56017
* Remove unused map.Devang Patel2008-09-051-1/+0
| | | | llvm-svn: 55861
* Tidy up several unbeseeming casts from pointer to intptr_t.Dan Gohman2008-09-041-1/+1
| | | | llvm-svn: 55779
* Pass the computed iteration count value to RewriteLoopExitValuesDan Gohman2008-08-051-4/+4
| | | | | | instead of having it call getIterationCount again. llvm-svn: 54380
* Use Loop::block_iterator.Dan Gohman2008-06-221-3/+5
| | | | llvm-svn: 52616
* Use recently added getTruncateOrZeroExtend method to make the code shorter.Wojciech Matyjewicz2008-06-131-5/+1
| | | | llvm-svn: 52251
OpenPOWER on IntegriCloud