summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [LPM] Fix PR18642, a pretty nasty bug in IndVars that "never mattered"Chandler Carruth2014-01-291-7/+23
| | | | | | | | | | | | | | | | | | | | | | | because of the inside-out run of LoopSimplify in the LoopPassManager and the fact that LoopSimplify couldn't be "preserved" across two independent LoopPassManagers. Anyways, in that case, IndVars wasn't correctly preserving an LCSSA PHI node because it thought it was rewriting (via SCEV) the incoming value to a loop invariant value. While it may well be invariant for the current loop, it may be rewritten in terms of an enclosing loop's values. This in and of itself is fine, as the LCSSA PHI node in the enclosing loop for the inner loop value we're rewriting will have its own LCSSA PHI node if used outside of the enclosing loop. With me so far? Well, the current loop and the enclosing loop may share an exiting block and exit block, and when they do they also share LCSSA PHI nodes. In this case, its not valid to RAUW through the LCSSA PHI node. Expected crazy test included. llvm-svn: 200372
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-131-3/+3
| | | | | | | | | | | | | | | | | | | | | | | can be used by both the new pass manager and the old. This removes it from any of the virtual mess of the pass interfaces and lets it derive cleanly from the DominatorTreeBase<> template. In turn, tons of boilerplate interface can be nuked and it turns into a very straightforward extension of the base DominatorTree interface. The old analysis pass is now a simple wrapper. The names and style of this split should match the split between CallGraph and CallGraphWrapperPass. All of the users of DominatorTree have been updated to match using many of the same tricks as with CallGraph. The goal is that the common type remains the resulting DominatorTree rather than the pass. This will make subsequent work toward the new pass manager significantly easier. Also in numerous places things became cleaner because I switched from re-running the pass (!!! mid way through some other passes run!!!) to directly recomputing the domtree. llvm-svn: 199104
* [cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth2014-01-131-1/+1
| | | | | | | | | | | | | | | | | | directory. These passes are already defined in the IR library, and it doesn't make any sense to have the headers in Analysis. Long term, I think there is going to be a much better way to divide these matters. The dominators code should be fully separated into the abstract graph algorithm and have that put in Support where it becomes obvious that evn Clang's CFGBlock's can use it. Then the verifier can manually construct dominance information from the Support-driven interface while the Analysis library can provide a pass which both caches, reconstructs, and supports a nice update API. But those are very long term, and so I don't want to leave the really confusing structure until that day arrives. llvm-svn: 199082
* Reapply r198654 "indvars: sink truncates outside the loop."Andrew Trick2014-01-071-4/+23
| | | | | | | | | | | This doesn't seem to have actually broken anything. It was paranoia on my part. Trying again now that bots are more stable. This is a follow up of the r198338 commit that added truncates for lcssa phi nodes. Sinking the truncates below the phis cleans up the loop and simplifies subsequent analysis within the indvars pass. llvm-svn: 198678
* Revert "indvars: sink truncates outside the loop."Andrew Trick2014-01-071-23/+4
| | | | | | | | This reverts commit r198654. One of the bots reported a SciMark failure. llvm-svn: 198659
* indvars: sink truncates outside the loop.Andrew Trick2014-01-071-4/+23
| | | | | | | | This is a follow up of the r198338 commit that added truncates for lcssa phi nodes. Sinking the truncates below the phis cleans up the loop and simplifies subsequent analysis within the indvars pass. llvm-svn: 198654
* 80 col. comment.Andrew Trick2014-01-071-2/+2
| | | | llvm-svn: 198653
* indvars: cleanup the IV visitor. It does more than gather sext/zext info.Andrew Trick2014-01-021-25/+33
| | | | llvm-svn: 198353
* indvars: insert truncate at loop boundary to avoid redundant IVs.Andrew Trick2014-01-021-5/+12
| | | | | | | | | When widening an IV to remove s/zext, we generally try to eliminate the original narrow IV. However, LCSSA phi nodes outside the loop were still using the original IV. Clean this up more aggressively to avoid redundancy in generated code. llvm-svn: 198338
* Add support to indvars for optimizing sadd.with.overflow.Andrew Trick2013-12-231-3/+11
| | | | | | | | | | | | | | | | Split sadd.with.overflow into add + sadd.with.overflow to allow analysis and optimization. This should ideally be done after InstCombine, which can perform code motion (eventually indvars should run after all canonical instcombines). We want ISEL to recombine the add and the check, at least on x86. This is currently under an option for reducing live induction variables: -liv-reduce. The next step is reducing liveness of IVs that are live out of the overflow check paths. Once the related optimizations are fully developed, reviewed and tested, I do expect this to become default. llvm-svn: 197926
* Fix SCEVExpander: don't try to expand quadratic recurrences outside a loop.Andrew Trick2013-10-251-1/+2
| | | | | | | | | | | | Partial fix for PR17459: wrong code at -O3 on x86_64-linux-gnu (affecting trunk and 3.3) When SCEV expands a recurrence outside of a loop it attempts to scale by the stride of the recurrence. Chained recurrences don't work that way. We could compute binomial coefficients, but would hve to guarantee that the chained AddRec's are in a perfectly reduced form. llvm-svn: 193438
* Fix a bug in LinearFunctionTestReplace that created invalid loop exit checks.Juergen Ributzka2013-10-241-1/+7
| | | | | | Reviewed by Andy llvm-svn: 193303
* Clarify comments in genLoopLimit.Andrew Trick2013-10-241-3/+4
| | | | llvm-svn: 193292
* Teach ScalarEvolution about pointer address spacesMatt Arsenault2013-09-101-1/+1
| | | | llvm-svn: 190425
* LFTR improvement to avoid truncation.Andrew Trick2013-07-121-6/+32
| | | | | | This is a reimplemntation of the patch originally in r186107. llvm-svn: 186215
* Cleanup LFTR logic.Andrew Trick2013-07-121-28/+9
| | | | llvm-svn: 186214
* Cleanup: rename a variable to make the logic easier to follow.Andrew Trick2013-07-121-7/+7
| | | | llvm-svn: 186213
* Revert "indvars: Improve LFTR by eliminating truncation when comparingChandler Carruth2013-07-121-23/+4
| | | | | | | | | | | | | | | | | | | against a constant." This reverts commit r186107. It didn't handle wrapping arithmetic in the loop correctly and thus caused the following C program to count from 0 to UINT64_MAX instead of from 0 to 255 as intended: #include <stdio.h> int main() { unsigned char first = 0, last = 255; do { printf("%d\n", first); } while (first++ != last); } Full test case and instructions to reproduce with just the -indvars pass sent to the original review thread rather than to r186107's commit. llvm-svn: 186152
* indvars: Improve LFTR by eliminating truncation when comparing against a ↵Andrew Trick2013-07-111-4/+23
| | | | | | | | | | | | | | | | | constant. Patch by Michele Scandale! Adds a special handling of the case where, during the loop exit condition rewriting, the exit value is a constant of bitwidth lower than the type of the induction variable: instead of introducing a trunc operation in order to match correctly the operand types, it allows to convert the constant value to an equivalent constant, depending on the initial value of the induction variable and the trip count, in order have an equivalent comparison between the induction variable and the new constant. llvm-svn: 186107
* IndVarSimplify: check if loop invariant expansion can trapDavid Majnemer2013-06-041-1/+1
| | | | | | | | | | | | | | | IndVarSimplify is willing to move divide instructions outside of their loop bodies if they are invariant of the loop. However, it may not be safe to expand them if we do not know if they can trap. Instead, check to see if it is not safe to expand the instruction and skip the expansion. This fixes PR16041. Testcase by Rafael Ávila de Espíndola. llvm-svn: 183239
* IndVarSimplify: do not recompute an IV value outside of the loop if :Arnaud A. de Grandmaison2013-03-191-0/+39
| | | | | | | - it is trivially known to be used inside the loop in a way that can not be optimized away - there is no use outside of the loop which can take advantage of the computation hoisting llvm-svn: 177432
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-7/+7
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-11/+11
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Revert the series of commits starting with r166578 which introduced theChandler Carruth2012-11-011-7/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | getIntPtrType support for multiple address spaces via a pointer type, and also introduced a crasher bug in the constant folder reported in PR14233. These commits also contained several problems that should really be addressed before they are re-committed. I have avoided reverting various cleanups to the DataLayout APIs that are reasonable to have moving forward in order to reduce the amount of churn, and minimize the number of commits that were reverted. I've also manually updated merge conflicts and manually arranged for the getIntPtrType function to stay in DataLayout and to be defined in a plausible way after this revert. Thanks to Duncan for working through this exact strategy with me, and Nick Lewycky for tracking down the really annoying crasher this triggered. (Test case to follow in its own commit.) After discussing with Duncan extensively, and based on a note from Micah, I'm going to continue to back out some more of the more problematic patches in this series in order to ensure we go into the LLVM 3.2 branch with a reasonable story here. I'll send a note to llvmdev explaining what's going on and why. Summary of reverted revisions: r166634: Fix a compiler warning with an unused variable. r166607: Add some cleanup to the DataLayout changes requested by Chandler. r166596: Revert "Back out r166591, not sure why this made it through since I cancelled the command. Bleh, sorry about this! r166591: Delete a directory that wasn't supposed to be checked in yet. r166578: Add in support for getIntPtrType to get the pointer type based on the address space. llvm-svn: 167221
* In various places throughout the code generator, there were specialUlrich Weigand2012-10-291-2/+0
| | | | | | | | | checks to avoid performing compile-time arithmetic on PPCDoubleDouble. Now that APFloat supports arithmetic on PPCDoubleDouble, those checks are no longer needed, and we can treat the type like any other. llvm-svn: 166958
* Add in support for getIntPtrType to get the pointer type based on the ↵Micah Villmow2012-10-241-3/+7
| | | | | | | | | address space. This checkin also adds in some tests that utilize these paths and updates some of the clients. llvm-svn: 166578
* Indvars: Don't recursively delete instruction during BB iteration.Benjamin Kramer2012-10-191-3/+5
| | | | | | | This can invalidate the iterators leading to use after frees and crashes. Fixes PR12536. llvm-svn: 166291
* Move TargetData to DataLayout.Micah Villmow2012-10-081-6/+6
| | | | llvm-svn: 165402
* 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
OpenPOWER on IntegriCloud