summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Add a comment to the commit r165187.Jakub Staszak2012-10-041-1/+3
| | | | llvm-svn: 165238
* Fix PR13967.Jakub Staszak2012-10-031-1/+4
| | | | llvm-svn: 165187
* Make MemoryBuiltins aware of TargetLibraryInfo.Benjamin Kramer2012-08-291-7/+10
| | | | | | | | | | | | | | | | This disables malloc-specific optimization when -fno-builtin (or -ffreestanding) is specified. This has been a problem for a long time but became more severe with the recent memory builtin improvements. Since the memory builtin functions are used everywhere, this required passing TLI in many places. This means that functions that now have an optional TLI argument, like RecursivelyDeleteTriviallyDeadFunctions, won't remove dead mallocs anymore if the TLI argument is missing. I've updated most passes to do the right thing. Fixes PR13694 and probably others. llvm-svn: 162841
* indvars: drive by heuristics fix.Andrew Trick2012-07-181-1/+1
| | | | | | Minor oversight noticed by inspection. Sorry no unit test. llvm-svn: 160422
* indvars: Linear function test replace should avoid reusing undef.Andrew Trick2012-07-181-5/+67
| | | | | | | | | | | | | | | | | | | | | | | Fixes PR13371: indvars pass incorrectly substitutes 'undef' values. I do not like this fix. It's needed until/unless the meaning of undef changes. It attempts to be complete according to the IR spec, but I don't have much confidence in the implementation given the difficulty testing undefined behavior. Worse, this invalidates some of my hard-fought work on indvars and LSR to optimize pointer induction variables. It results benchmark regressions, which I'll track internally. On x86_64 no LTO I see: -3% huffbench -3% 400.perlbench -8% fhourstones My only suggestion for recovering is to change the meaning of undef. If we could trust an arbitrary instruction to produce a some real value that can be manipulated (e.g. incremented) according to non-undef rules, then this case could be easily handled with SCEV. llvm-svn: 160421
* More IndVarSimplify cleanup.Andrew Trick2012-03-241-25/+16
| | | | llvm-svn: 153362
* Remove -enable-iv-rewrite, which has been unsupported since 3.0.Andrew Trick2012-03-221-265/+7
| | | | llvm-svn: 153260
* LSR fix: Add isSimplifiedLoopNest to IVUsers analysis.Andrew Trick2012-03-161-4/+9
| | | | | | | | | | | | | | Only record IVUsers that are dominated by simplified loop headers. Otherwise SCEVExpander will crash while looking for a preheader. I previously tried to work around this in LSR itself, but that was insufficient. This way, LSR can continue to run if some uses are not in simple loops, as long as we don't attempt to analyze those users. Fixes <rdar://problem/11049788> Segmentation fault: 11 in LoopStrengthReduce llvm-svn: 152892
* Remove dead code. Improve llvm_unreachable text. Simplify some control flow.Ahmed Charles2012-02-191-1/+0
| | | | llvm-svn: 150918
* Fix typo.Nick Lewycky2012-01-281-2/+2
| | | | llvm-svn: 149185
* SCEVExpander fixes. Affects LSR and indvars.Andrew Trick2012-01-201-4/+4
| | | | | | | | | | | | | | | | LSR has gradually been improved to more aggressively reuse existing code, particularly existing phi cycles. This exposed problems with the SCEVExpander's sloppy treatment of its insertion point. I applied some rigor to the insertion point problem that will hopefully avoid an endless bug cycle in this area. Changes: - Always used properlyDominates to check safe code hoisting. - The insertion point provided to SCEV is now considered a lower bound. This is usually a block terminator or the use itself. Under no cirumstance may SCEVExpander insert below this point. - LSR is reponsible for finding a "canonical" insertion point across expansion of different expressions. - Robust logic to determine whether IV increments are in "expanded" form and/or can be safely hoisted above some insertion point. Fixes PR11783: SCEVExpander assert. llvm-svn: 148535
* Indvars: guard against exponential behavior in isHighCostExpansion.Andrew Trick2011-12-121-2/+7
| | | | | | | | This should always be done as a matter of principal. I don't have a case that exposes the problem. I just noticed this recently while scanning the code and realized I meant to fix it long ago. llvm-svn: 146438
* Add support for vectors of pointers.Nadav Rotem2011-12-051-0/+5
| | | | llvm-svn: 145801
* SCEV fix. In general, Add/Mul expressions should not inherit NSW/NUW.Andrew Trick2011-11-291-2/+6
| | | | | | | This reverts r139450, fixes r139453, and adds much needed comments and a unit test. llvm-svn: 145367
* Move code into anonymous namespaces.Benjamin Kramer2011-11-261-12/+10
| | | | llvm-svn: 145154
* Rewrite LinearFunctionTestReplace to handle pointer-type IVs.Andrew Trick2011-11-021-73/+116
| | | | | | | | We've been hitting asserts in this code due to the many supported combintions of modes (iv-rewrite/no-iv-rewrite) and IV types. This second rewrite of the code attempts to deal with these cases systematically. llvm-svn: 143546
* Add parentheses to disambiguate the precedence of these operations andChandler Carruth2011-11-021-2/+2
| | | | | | silence -Wparentheses. llvm-svn: 143534
* Broaden an assert to handle enable-iv-rewrite=true following r143183.Andrew Trick2011-11-021-1/+1
| | | | | | Narrowest possible fix for PR11279. llvm-svn: 143522
* LFTR should avoid a type mismatch with null pointer IVs.Andrew Trick2011-10-281-16/+18
| | | | | | Fixes rdar://10359193 Indvar LinearFunctionTestReplace assertion llvm-svn: 143183
* It is not safe to sink an alloca into a stacksave/stackrestore pair, so ↵Eli Friedman2011-10-271-5/+6
| | | | | | don't do that. <rdar://problem/10352360> llvm-svn: 143093
* Fix indvars randomness by removing iteration over a map.Andrew Trick2011-10-151-12/+12
| | | | | | | | | | | | | I rewrote the algorithm a while back so it doesn't require map lookup, but neglected to change the data structure. This was caught by llvm-gcc self host, not because there's anything special about llvm-gcc, but because it is the only test for nondeterminism we currently have. Unit tests don't work well for everything; we should always try to have a nondeterminism stress test running. Fixes PR11133: llvm-gcc self host .o mismatch after enable-iv-rewrite=false llvm-svn: 142036
* Move replaceCongruentIVs into SCEVExapander and bias toward "expanded"Andrew Trick2011-10-111-87/+6
| | | | | | | | | | | IVs. Indvars previously chose randomly between congruent IVs. Now it will bias the decision toward IVs that SCEVExpander likes to create. This was not done to fix any problem, it's just a welcome side effect of factoring code. llvm-svn: 141633
* indvars should hoist [sz]ext because licm is not rerun.Andrew Trick2011-09-281-17/+27
| | | | llvm-svn: 140670
* Reapply r139759. Disable IV rewriting by default. See PR10916.Andrew Trick2011-09-151-1/+1
| | | | llvm-svn: 139842
* [indvars] Revert r139579 until 401.bzip -arch i386 miscompilation is fixed. ↵Andrew Trick2011-09-131-1/+1
| | | | | | PR10920. llvm-svn: 139583
* Disable IV rewriting by default. See PR10916.Andrew Trick2011-09-131-1/+1
| | | | llvm-svn: 139579
* [indvars] Fix bugs in floating point IV range checks noticed by inspection.Andrew Trick2011-09-131-10/+10
| | | | llvm-svn: 139574
* Rename -disable-iv-rewrite to -enable-iv-rewrite=false in preparation for ↵Andrew Trick2011-09-121-42/+20
| | | | | | default change. llvm-svn: 139517
* [disable-iv-rewrite] Allow WidenIV to handle NSW/NUW operationsAndrew Trick2011-09-101-1/+40
| | | | | | | | | | | | better. Don't immediately give up when an add operation can't be trivially sign/zero-extended within a loop. If it has NSW/NUW flags, generate a new expression with sign extended (non-recurrent) operand. As before, if SCEV says that all sign extends are loop invariant, then we can widen the operation. llvm-svn: 139453
* Comment formatting.Andrew Trick2011-09-091-15/+16
| | | | llvm-svn: 139375
* Add -verify-indvars for imperfect SCEV trip count verification after indvars.Andrew Trick2011-09-061-1/+9
| | | | llvm-svn: 139169
* Don't sink landingpad instructions during ind-var simplification.Bill Wendling2011-08-261-0/+4
| | | | llvm-svn: 138651
* Use getFirstInsertionPt instead of getFirstNonPHI so that it skips to the properBill Wendling2011-08-241-3/+3
| | | | | | insertion place. llvm-svn: 138473
* Cleanup. Make ScalarEvolution an explicit argument of theAndrew Trick2011-08-101-2/+2
| | | | | | SimplifyIndVar utility since it is required. llvm-svn: 137202
* Added a SimplifyIndVar utility to simplify induction variable usersAndrew Trick2011-08-101-328/+48
| | | | | | | | | | | | | | | | based on ScalarEvolution without changing the induction variable phis. This utility is the main tool of IndVarSimplifyPass, but the pass also restructures induction variables in strange ways that are sensitive to pass ordering. This provides a way for other loop passes to simplify new uses of induction variables created during transformation. The utility may be used by any pass that preserves ScalarEvolution. Soon LoopUnroll will use it. The net effect in this checkin is to cleanup the IndVarSimplify pass by factoring out the SimplifyIndVar algorithm into a standalone utility. llvm-svn: 137197
* Made SCEV's UDiv expressions more canonical. When dividing aAndrew Trick2011-08-061-0/+65
| | | | | | | | | | | | | | | | | | | | | | | recurrence, the initial values low bits can sometimes be ignored. To take advantage of this, added FoldIVUser to IndVarSimplify to fold an IV operand into a udiv/lshr if the operator doesn't affect the result. -indvars -disable-iv-rewrite now transforms i = phi i4 i1 = i0 + 1 idx = i1 >> (2 or more) i4 = i + 4 into i = phi i4 idx = i0 >> ... i4 = i + 4 llvm-svn: 137013
* Cleanup: make std::pair usage slightly less indecipherable without actually ↵Andrew Trick2011-07-211-7/+8
| | | | | | naming variables! llvm-svn: 135684
* move tier out of an anonymous namespace, it doesn't make senseChris Lattner2011-07-211-13/+11
| | | | | | | | to for it to be an an anon namespace and be in a header. Eliminate some extraenous uses of tie. llvm-svn: 135669
* Fix a GCC warning.Jay Foad2011-07-201-2/+2
| | | | llvm-svn: 135581
* indvars: Added getInsertPointForUses to find a valid place to truncate the IV.Andrew Trick2011-07-201-15/+32
| | | | llvm-svn: 135568
* indvars -disable-iv-rewrite: Add NarrowIVDefUse to cache def-useAndrew Trick2011-07-201-54/+61
| | | | | | | info. Holding Use* pointers is bad form even though it happened to work in this case. llvm-svn: 135566
* indvars -disable-iv-rewrite fix: derived GEP IVsAndrew Trick2011-07-201-0/+6
| | | | llvm-svn: 135558
* Compiler warning.Andrew Trick2011-07-181-3/+3
| | | | llvm-svn: 135426
* indvars: LinearFunctionTestReplace for non-canonical IVs.Andrew Trick2011-07-181-48/+292
| | | | | | | | | | For -disable-iv-rewrite, perform LFTR without generating a new "canonical" induction variable. Instead find the "best" existing induction variable for use in the loop exit test and compute the final value of that IV for use in the new loop exit test. In short, convert to a simple eq/ne exit test as long as it's cheap to do so. llvm-svn: 135420
* indvars: Added verification that LFTR and other indvars goodness doesAndrew Trick2011-07-181-1/+20
| | | | | | not interfere with BackedgeTakenCount computation. llvm-svn: 135412
* indvars: Added isHighCostExpansion. Avoid generating extra ops in theAndrew Trick2011-07-181-17/+51
| | | | | | | preheader for the sole purpose of LFTR, since LFTR itself is usually not a clear optimization. llvm-svn: 135409
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-181-11/+11
| | | | llvm-svn: 135375
* indvars: fix a pass-sensitivity issue that would hit the SCEVExpanderAndrew Trick2011-07-161-2/+13
| | | | | | | assertion I added in r135333. Check for the existence of a preheader before expanding a recurrence. llvm-svn: 135335
* indvars: remove ExprToIVMap because it won't be needed by LFTR.Andrew Trick2011-07-161-9/+3
| | | | llvm-svn: 135334
* indvars: Code reorganization in preparation forAndrew Trick2011-07-121-589/+624
| | | | | | | | | | | | | | | | | LinearFunctionTestReplace rewrite. No functionality. I've been wanting to group the indvar subphases into sections and order them by their logical sequence. My next checkin adds functions related to LFTR, and doing the reorg now should help reviewers. Since, most of the code in IndVarSimplify.cpp has recently been replaced or will be replaced soon, obscuring blame should not be an issue. This seems like an ideal time to shuffle the code around. I'm happy to take more suggestions for cleaning up the code. Or if you've been wanting to cleanup anything in this file yourself, now is a good time. llvm-svn: 134941
OpenPOWER on IntegriCloud