aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Transforms/Scalar/IndVarSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [indvars] Revert r139579 until 401.bzip -arch i386 miscompilation is fixed. ↵Andrew Trick2011-09-131-1/+1
| | | | | | PR10920. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139583 91177308-0d34-0410-b5e6-96231b3b80d8
* Disable IV rewriting by default. See PR10916.Andrew Trick2011-09-131-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139579 91177308-0d34-0410-b5e6-96231b3b80d8
* [indvars] Fix bugs in floating point IV range checks noticed by inspection.Andrew Trick2011-09-131-10/+10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139574 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename -disable-iv-rewrite to -enable-iv-rewrite=false in preparation for ↵Andrew Trick2011-09-121-42/+20
| | | | | | default change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139517 91177308-0d34-0410-b5e6-96231b3b80d8
* [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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139453 91177308-0d34-0410-b5e6-96231b3b80d8
* Comment formatting.Andrew Trick2011-09-091-15/+16
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139375 91177308-0d34-0410-b5e6-96231b3b80d8
* Add -verify-indvars for imperfect SCEV trip count verification after indvars.Andrew Trick2011-09-061-1/+9
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139169 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't sink landingpad instructions during ind-var simplification.Bill Wendling2011-08-261-0/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@138651 91177308-0d34-0410-b5e6-96231b3b80d8
* Use getFirstInsertionPt instead of getFirstNonPHI so that it skips to the properBill Wendling2011-08-241-3/+3
| | | | | | | insertion place. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@138473 91177308-0d34-0410-b5e6-96231b3b80d8
* Cleanup. Make ScalarEvolution an explicit argument of theAndrew Trick2011-08-101-2/+2
| | | | | | | SimplifyIndVar utility since it is required. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137202 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137197 91177308-0d34-0410-b5e6-96231b3b80d8
* 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137013 91177308-0d34-0410-b5e6-96231b3b80d8
* Cleanup: make std::pair usage slightly less indecipherable without actually ↵Andrew Trick2011-07-211-7/+8
| | | | | | naming variables! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135684 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135669 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a GCC warning.Jay Foad2011-07-201-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135581 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars: Added getInsertPointForUses to find a valid place to truncate the IV.Andrew Trick2011-07-201-15/+32
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135568 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135566 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars -disable-iv-rewrite fix: derived GEP IVsAndrew Trick2011-07-201-0/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135558 91177308-0d34-0410-b5e6-96231b3b80d8
* Compiler warning.Andrew Trick2011-07-181-3/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135426 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135420 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars: Added verification that LFTR and other indvars goodness doesAndrew Trick2011-07-181-1/+20
| | | | | | | not interfere with BackedgeTakenCount computation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135412 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135409 91177308-0d34-0410-b5e6-96231b3b80d8
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-181-11/+11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135375 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135335 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars: remove ExprToIVMap because it won't be needed by LFTR.Andrew Trick2011-07-161-9/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135334 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134941 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars -disable-iv-rewrite: ExprToMap lives in Pass data, so be moreAndrew Trick2011-07-061-1/+2
| | | | | | | careful about referencing values. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134537 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars -disable-iv-rewrite: Added SimplifyCongruentIVs.Andrew Trick2011-07-061-1/+58
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134530 91177308-0d34-0410-b5e6-96231b3b80d8
* Preserve debug loc.Devang Patel2011-07-051-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134441 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars -disable-iv-rewrite: avoid multiple IVs in weird cases.Andrew Trick2011-07-051-18/+30
| | | | | | | Putting back the helper that I removed on 7/1 to do this right. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134423 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars -disable-iv-rewrite: bug fix involving weird geps and related cleanup.Andrew Trick2011-07-021-46/+51
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134306 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars -disable-iv-rewrite: handle cloning binary operators that cannot ↵Andrew Trick2011-06-301-3/+7
| | | | | | overflow. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134177 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars -disable-iv-rewrite: handle an edge case involving identity phis.Andrew Trick2011-06-301-3/+8
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134124 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars -disable-iv-rewrite: insert new trunc instructions carefully.Andrew Trick2011-06-291-13/+21
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134112 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars -disable-iv-rewrite: just because SCEV ignores casts doesn'tAndrew Trick2011-06-291-0/+1
| | | | | | | mean they can be removed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134054 91177308-0d34-0410-b5e6-96231b3b80d8
* cleanup: misleading comment.Andrew Trick2011-06-281-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134010 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEVExpander: give new insts a name that identifies the reponsible pass.Andrew Trick2011-06-281-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133992 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars --disable-iv-rewrite: sever ties with IVUsers.Andrew Trick2011-06-281-6/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133988 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars --disable-iv-rewrite: Defer evaluating s/zext until SCEVAndrew Trick2011-06-281-40/+57
| | | | | | | evaluates all other IV exprs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133982 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars -disable-iv-rewrite: run RLEV after SimplifyIVUsers forAndrew Trick2011-06-271-4/+6
| | | | | | | a bit more control over the order SCEVs are evaluated. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133959 91177308-0d34-0410-b5e6-96231b3b80d8
* Set debug loc.Devang Patel2011-06-221-0/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133636 91177308-0d34-0410-b5e6-96231b3b80d8
* IVUsers no longer needs to record the phis.Andrew Trick2011-06-211-10/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133518 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars -disable-iv-rewrite: Adds support for eliminating identityAndrew Trick2011-06-211-100/+237
| | | | | | | | | | | | | | | | | | | | ops. This is a rewrite of the IV simplification algorithm used by -disable-iv-rewrite. To avoid perturbing the default mode, I temporarily split the driver and created SimplifyIVUsersNoRewrite. The idea is to avoid doing opcode/pattern matching inside IndVarSimplify. SCEV already does it. We want to optimize with the full generality of SCEV, but optimize def-use chains top down on-demand rather than rewriting the entire expression bottom-up. This was easy to do for operations that SCEV can prove are identity function. So we're now eliminating bitmasks and zero extends this way. A result of this rewrite is that indvars -disable-iv-rewrite no longer requires IVUsers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133502 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars: incremental fixes for -disable-iv-rewrite and testcases.Andrew Trick2011-05-261-21/+72
| | | | | | | | | Use a proper worklist for use-def traversal without holding onto an iterator. Now that we process all IV uses, we need complete logic for resusing existing derived IV defs. See HoistStep. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132103 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars: fixed IV cloning in -disable-iv-rewrite mode with associatedAndrew Trick2011-05-251-52/+114
| | | | | | | cleanup and overdue test cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132038 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars: Prototyping Sign/ZeroExtend elimination without canonical IVs.Andrew Trick2011-05-201-102/+352
| | | | | | | | | | | No functionality enabled by default. Use -disable-iv-rewrite. Extended IVUsers to keep track of the phi that represents the users' IV. Added the WidenIV transform to replace a narrow IV with a wide IV by doing a one-for-one replacement of IV users instead of expanding the SCEV expressions. [sz]exts are removed and truncs are inserted. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131744 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars: minor cleanup in preparation for sign/zero extend elimination.Andrew Trick2011-05-201-18/+11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131716 91177308-0d34-0410-b5e6-96231b3b80d8
* Convert SimplifyIVUsers into a worklist instead of a single pass overAndrew Trick2011-05-131-1/+1
| | | | | | | the users. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131277 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars: Added SimplifyIVUsers.Andrew Trick2011-05-121-85/+99
| | | | | | | | Interleave IV simplifications. Currently involves EliminateComparison and EliminateRemainder. Next I'll add EliminateExtend. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131210 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars: Added DisableIVRewrite and WidenIVs.Andrew Trick2011-05-041-9/+115
| | | | | | | | | This adds functionality to remove size/zero extension during indvars without generating a canonical IV and rewriting all IV users. It's disabled by default so should have no effect on codegen. Work in progress. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130829 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2025-06-02 00:29:06 +0000