aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/LoopStrengthReduce.cpp
AgeCommit message (Collapse)Author
2010-02-14When complicated expressions are broken down into subexpressionsDan Gohman
with multiplication by constants distributed through, occasionally those subexpressions can include both x and -x. For now, if this condition is discovered within LSR, just prune such cases away, as they won't be profitable. This fixes a "zero allocated in a base register" assertion failure. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96177 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-14Actually, this code doesn't have to be quite so conservative inDan Gohman
the no-TLI case. But it should still default to declining the transformation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96152 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-14Don't attempt aggressive post-inc uses if TargetLowering is not available,Dan Gohman
because profitability can't be sufficiently approximated. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96148 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-13Make LSR not crash if invoked without target lowering info, e.g. if invokedJohn McCall
from opt. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96135 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-13Fix a pruning heuristic which implicitly assumed that SmallPtrSet isDan Gohman
deterministically sorted. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96071 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-12Reapply 95979, a compile-time speedup, now that the bug it exposed is fixed.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96005 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-12Fix this code to avoid dereferencing an end() iterator inDan Gohman
offset distributions it doesn't expect. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96002 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-12Revert "Reverse the order for collecting the parts of an addrec. The order", itDaniel Dunbar
is breaking llvm-gcc bootstrap. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95988 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-12Reverse the order for collecting the parts of an addrec. The orderDan Gohman
doesn't matter, except that ScalarEvolution tends to need less time to fold the results this way. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95979 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-12Reapply the new LoopStrengthReduction code, with compile time andDan Gohman
bug fixes, and with improved heuristics for analyzing foreign-loop addrecs. This change also flattens IVUsers, eliminating the stride-oriented groupings, which makes it easier to work with. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95975 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-29Generic reformatting and comment fixing. No functionality change.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94771 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-29Add newline to debugging output, and fix some grammar-os in comment.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94765 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-22Revert LoopStrengthReduce.cpp to pre-r94061 for now.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94123 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-21When inserting expressions for post-increment users which containDan Gohman
loop-variant components, adds must be inserted after the increment. Keep track of the increment position for this case, and insert these adds in the correct location. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94110 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-21Include IVUsers information in LSR's debug output.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94108 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-21Prune the search for candidate formulae if the number of registerDan Gohman
operands exceeds the number of registers used in the initial solution, as that wouldn't lead to a profitable solution anyway. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94107 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-21Add a comment.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94104 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-21Re-implement the main strength-reduction portion of LoopStrengthReduction.Dan Gohman
This new version is much more aggressive about doing "full" reduction in cases where it reduces register pressure, and also more aggressive about rewriting induction variables to count down (or up) to zero when doing so reduces register pressure. It currently uses fairly simplistic algorithms for finding reuse opportunities, but it introduces a new framework allows it to combine multiple strategies at once to form hybrid solutions, instead of doing all full-reduction or all base+index. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94061 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-05Set Changed properly after calling DeleteDeadPHIs.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92735 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-23Remove dump routine and the associated Debug.h from a header. Patch upDavid Greene
other files to compensate. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92075 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-18Add Loop contains utility methods for testing whether a loopDan Gohman
contains another loop, or an instruction. The loop form is substantially more efficient on large loops than the typical code it replaces. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91654 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-18Minor code simplification.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91653 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-18Don't pass const pointers by reference.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91647 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-18Reapply LoopStrengthReduce and IVUsers cleanups, excluding the partDan Gohman
of 91296 that caused trouble -- the Processed list needs to be preserved for the livetime of the pass, as AddUsersIfInteresting is called from other passes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91641 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-17Revert 91280-91283, 91286-91289, 91291, 91293, 91295-91296. It apparently ↵Evan Cheng
introduced a non-deterministic behavior in the optimizer somewhere. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91598 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-15Delete an unused function.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91432 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-14Fix a thinko; isNotAlreadyContainedIn had a built-in negative, so theDan Gohman
condition was inverted when the code was converted to contains(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91295 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-14Remove unnecessary #includes.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91293 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-14Instead of having a ScalarEvolution pointer member in BasedUser, just passDan Gohman
the ScalarEvolution pointer into the functions which need it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91289 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-14Don't bother cleaning up if there's nothing to clean up.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91288 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-14Delete an unused variable.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91287 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-14LSR itself doesn't need LoopInfo.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91283 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-14LSR itself doesn't need DominatorTree.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91282 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-14Remove the code in LSR that manually hoists expansions out of loops;Dan Gohman
SCEVExpander does this automatically. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91281 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-14Minor code cleanups.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91280 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-17grammarJim Grosbach
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@89145 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-1780-column violationsJim Grosbach
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@89123 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-17Generalize OptimizeLoopTermCond to optimize more loop terminating icmp to ↵Evan Cheng
use postinc iv. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@89116 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-17Remove trailing whitespaceJim Grosbach
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@89110 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-12- Teach LSR to avoid changing cmp iv stride if it will create an immediate thatEvan Cheng
cannot be folded into target cmp instruction. - Avoid a phase ordering issue where early cmp optimization would prevent the later count-to-zero optimization. - Add missing checks which could cause LSR to reuse stride that does not have users. - Fix a bug in count-to-zero optimization code which failed to find the pre-inc iv's phi node. - Remove, tighten, loosen some incorrect checks disable valid transformations. - Quite a bit of code clean up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86969 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-11Block terminator may be a switch.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86761 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-10Generalize lsr code that optimize loop to count down towards zero.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86715 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-05Teach LSR to avoid calling SplitCriticalEdge on edges with indirectbr.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86193 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-05Update various Loop optimization passes to cope with the possibility thatDan Gohman
LoopSimplify form may not be available. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86175 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-26Make LSR's OptimizeShadowIV ignore induction variables with negativeDan Gohman
strides for now, because it doesn't handle them correctly. This fixes a miscompile of SingleSource/Benchmarks/Misc-C++/ray. This problem was usually hidden because indvars transforms such induction variables into negations of canonical induction variables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85118 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-25Remove ICmpInst::isSignedPredicate which was a reimplementationNick Lewycky
CmpInst::isSigned. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85037 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-27Instruction::clone does not need to take an LLVMContext&. Remove that andNick Lewycky
update all the callers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82889 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-08Re-apply r80926, with fixes: keep the domtree informed of new blocksDan Gohman
that get created during loop unswitching, and fix SplitBlockPredecessors' LCSSA updating code to create new PHIs instead of trying to just move existing ones. Also, optimize Loop::verifyLoop, since it gets called a lot. Use searches on a sorted list of blocks instead of calling the "contains" function, as is done in other places in the Loop class, since "contains" does a linear search. Also, don't call verifyLoop from LoopSimplify or LCSSA, as the PassManager is already calling verifyLoop as part of LoopInfo's verifyAnalysis. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81221 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-06Revert r80926. It causes loop unswitch assertion and slow down some JIT ↵Evan Cheng
tests significantly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81101 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-03Add a verifyAnalysis to LoopInfo, LoopSimplify, and LCSSA form that verifyDan Gohman
that these passes are properly preserved. Fix several transformation passes that claimed to preserve LoopSimplify form but weren't. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@80926 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-01 01:22:38 +0000