summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* LPM: Stop threading `Pass *` through all of the loop utility APIs. NFCJustin Bogner2015-12-151-6/+4
| | | | | | | | | | | | | | | | | | | | | | A large number of loop utility functions take a `Pass *` and reach into it to find out which analyses to preserve. There are a number of problems with this: - The APIs have access to pretty well any Pass state they want, so it's hard to tell what they may or may not do. - Other APIs have copied these and pass around a `Pass *` even though they don't even use it. Some of these just hand a nullptr to the API since the callers don't even have a pass available. - Passes in the new pass manager don't work like the current ones, so the APIs can't be used as is there. Instead, we should explicitly thread the analysis results that we actually care about through these APIs. This is both simpler and more reusable. llvm-svn: 255669
* [IndVars] Preserve LCSSA in `eliminateIdentitySCEV`Sanjoy Das2015-10-071-0/+3
| | | | | | | | | | | | | | | | | | | | Summary: After r249211, SCEV can see through some LCSSA phis. Add a `replacementPreservesLCSSAForm` check before replacing uses of these phi nodes with a simplified use of the induction variable to avoid breaking LCSSA. Fixes 25047. Depends on D13460. Reviewers: atrick, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13461 llvm-svn: 249575
* [IndVars] Don't break dominance in `eliminateIdentitySCEV`Sanjoy Das2015-10-061-9/+33
| | | | | | | | | | | | | | | | | | | | | | | Summary: After r249211, `getSCEV(X) == getSCEV(Y)` does not guarantee that X and Y are related in the dominator tree, even if X is an operand to Y (I've included a toy example in comments, and a real example as a test case). This commit changes `SimplifyIndVar` to require a `DominatorTree`. I don't think this is a problem because `ScalarEvolution` requires it anyway. Fixes PR25051. Depends on D13459. Reviewers: atrick, hfinkel Subscribers: joker.eph, llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D13460 llvm-svn: 249471
* [IndVars] Extract out eliminateIdentitySCEV, NFCSanjoy Das2015-10-061-4/+14
| | | | | | | | | | | Summary: Reflow a comment while at it. Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13459 llvm-svn: 249470
* [SCEV] Introduce ScalarEvolution::getOne and getZero.Sanjoy Das2015-09-231-2/+1
| | | | | | | | | | | | | | | | | | Summary: It is fairly common to call SE->getConstant(Ty, 0) or SE->getConstant(Ty, 1); this change makes such uses a little bit briefer. I've refactored the call sites I could find easily to use getZero / getOne. Reviewers: hfinkel, majnemer, reames Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12947 llvm-svn: 248362
* Fix some comment typos.Benjamin Kramer2015-08-081-4/+4
| | | | llvm-svn: 244402
* [IndVars] Improved logging under DEBUG(); NFC.Sanjoy Das2015-08-061-6/+3
| | | | | | | Before this, we'd print the modified comparision in the "Simplified comparison" case. That looked misleading. llvm-svn: 244264
* [IndVars] Make loop varying predicates loop invariant.Sanjoy Das2015-07-271-5/+54
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Was D9784: "Remove loop variant range check when induction variable is strictly increasing" This change re-implements D9784 with the two differences: 1. It does not use SCEVExpander and does not generate new instructions. Instead, it does a quick local search for existing `llvm::Value`s that it needs when modifying the `icmp` instruction. 2. It is more general -- it deals with both increasing and decreasing induction variables. I've added all of the tests included with D9784, and two more. As an example on what this change does (copied from D9784): Given C code: ``` for (int i = M; i < N; i++) // i is known not to overflow if (i < 0) break; a[i] = 0; } ``` This transformation produces: ``` for (int i = M; i < N; i++) if (M < 0) break; a[i] = 0; } ``` Which can be unswitched into: ``` if (!(M < 0)) for (int i = M; i < N; i++) a[i] = 0; } ``` I went back and forth on whether the top level logic should live in `SimplifyIndvar::eliminateIVComparison` or be put into its own routine. Right now I've put it under `eliminateIVComparison` because even though the `icmp` is not *eliminated*, it no longer is an IV comparison. I'm open to putting it in its own helper routine if you think that is better. Reviewers: reames, nicholas, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11278 llvm-svn: 243331
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-1/+1
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-1/+1
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* Replace push_back(Constructor(foo)) with emplace_back(foo) for non-trivial typesBenjamin Kramer2015-05-291-5/+5
| | | | | | | | | | | | | | | | | | | | If the type isn't trivially moveable emplace can skip a potentially expensive move. It also saves a couple of characters. Call sites were found with the ASTMatcher + some semi-automated cleanup. memberCallExpr( argumentCountIs(1), callee(methodDecl(hasName("push_back"))), on(hasType(recordDecl(has(namedDecl(hasName("emplace_back")))))), hasArgument(0, bindTemporaryExpr( hasType(recordDecl(hasNonTrivialDestructor())), has(constructExpr()))), unless(isInTemplateInstantiation())) No functional change intended. llvm-svn: 238602
* SimplifyIV comments and dead argument cleanup.Andrew Trick2015-05-181-2/+1
| | | | | | Remove crufty comments. IVUsers hasn't been used here for a long time. llvm-svn: 237586
* [IndVarSimplify] use the "canonical" way to infer no-wrap.Sanjoy Das2015-03-041-78/+40
| | | | | | | | | | | | | | | | | | | | | | Summary: rL225282 introduced an ad-hoc way to promote some additions to nuw or nsw. Since then SCEV has become smarter in directly proving no-wrap; and using the canonical "ext(A op B) == ext(A) op ext(B)" method of proving no-wrap is just as powerful now. Rip out the existing complexity in favor of getting SCEV to do all the heaving lifting internally. This change does not add any unit tests because it is supposed to be a non-functional change. Tests added in rL225282 and rL226075 are valid tests for this change. Reviewers: atrick, majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D7981 llvm-svn: 231306
* [PM] Remove a dead field.Chandler Carruth2015-01-171-7/+3
| | | | | | | | | This was dead even before I refactored how we initialized it, but my refactoring made it trivially dead and it is now caught by a Clang warning. This fixes the warning and should clean up the -Werror bot failures (sorry!). llvm-svn: 226376
* [PM] Split the LoopInfo object apart from the legacy pass, creatingChandler Carruth2015-01-171-11/+8
| | | | | | | | | | a LoopInfoWrapperPass to wire the object up to the legacy pass manager. This switches all the clients of LoopInfo over and paves the way to port LoopInfo to the new pass manager. No functionality change is intended with this iteration. llvm-svn: 226373
* SimplifyIndVar: Remove unused variableDavid Majnemer2015-01-151-3/+0
| | | | | | OtherOperandIdx is not used anymore, remove it to silence warnings. llvm-svn: 226138
* Fix PR22222Sanjoy Das2015-01-151-11/+1
| | | | | | | | | | | The bug was introduced in r225282. r225282 assumed that sub X, Y is the same as add X, -Y. This is not correct if we are going to upgrade the sub to sub nuw. This change fixes the issue by making the optimization ignore sub instructions. Differential Revision: http://reviews.llvm.org/D6979 llvm-svn: 226075
* This patch teaches IndVarSimplify to add nuw and nsw to certain kindsSanjoy Das2015-01-061-0/+125
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | of operations that provably don't overflow. For example, we can prove %civ.inc below does not sign-overflow. With this change, IndVarSimplify changes %civ.inc to an add nsw. define i32 @foo(i32* %array, i32* %length_ptr, i32 %init) { entry: %length = load i32* %length_ptr, !range !0 %len.sub.1 = sub i32 %length, 1 %upper = icmp slt i32 %init, %len.sub.1 br i1 %upper, label %loop, label %exit loop: %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ] %civ.inc = add i32 %civ, 1 %cmp = icmp slt i32 %civ.inc, %length br i1 %cmp, label %latch, label %break latch: store i32 0, i32* %array %check = icmp slt i32 %civ.inc, %len.sub.1 br i1 %check, label %loop, label %break break: ret i32 %civ.inc exit: ret i32 42 } Differential Revision: http://reviews.llvm.org/D6748 llvm-svn: 225282
* Update SetVector to rely on the underlying set's insert to return a ↵David Blaikie2014-11-191-1/+1
| | | | | | | | | | | | | pair<iterator, bool> This is to be consistent with StringSet and ultimately with the standard library's associative container insert function. This lead to updating SmallSet::insert to return pair<iterator, bool>, and then to update SmallPtrSet::insert to return pair<iterator, bool>, and then to update all the existing users of those functions... llvm-svn: 222334
* remove function names from comments; NFCSanjay Patel2014-11-121-11/+10
| | | | llvm-svn: 221798
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-13/+13
| | | | llvm-svn: 207196
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-2/+2
| | | | | | | | | | | | | | | | | definition below all of the header #include lines, lib/Transforms/... edition. This one is tricky for two reasons. We again have a couple of passes that define something else before the includes as well. I've sunk their name macros with the DEBUG_TYPE. Also, InstCombine contains headers that need DEBUG_TYPE, so now those headers #define and #undef DEBUG_TYPE around their code, leaving them well formed modular headers. Fixing these headers was a large motivation for all of these changes, as "leaky" macros of this form are hard on the modules implementation. llvm-svn: 206844
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-13/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] llvm-svn: 203364
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-1/+1
| | | | | | Remove the old functions. llvm-svn: 202636
* Make DataLayout a plain object, not a pass.Rafael Espindola2014-02-251-1/+2
| | | | | | | Instead, have a DataLayoutPass that holds one. This will allow parts of LLVM don't don't handle passes to also use DataLayout. llvm-svn: 202168
* Rename many DataLayout variables from TD to DL.Rafael Espindola2014-02-211-2/+2
| | | | | | | | | I am really sorry for the noise, but the current state where some parts of the code use TD (from the old name: TargetData) and other parts use DL makes it hard to write a patch that changes where those variables come from and how they are passed along. llvm-svn: 201827
* [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
* Re-sort all of the includes with ./utils/sort_includes.py so thatChandler Carruth2014-01-071-2/+2
| | | | | | | | | | subsequent changes are easier to review. About to fix some layering issues, and wanted to separate out the necessary churn. Also comment and sink the include of "Windows.h" in three .inc files to match the usage in Memory.inc. llvm-svn: 198685
* Add support to indvars for optimizing sadd.with.overflow.Andrew Trick2013-12-231-1/+81
| | | | | | | | | | | | | | | | 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
* Don't use a potentially expensive shift if all we want is one set bit.Benjamin Kramer2013-07-111-1/+1
| | | | | | No functionality change. llvm-svn: 186095
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-2/+2
| | | | | | | | | | | | | | | | | | | | | 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-5/+5
| | | | | | | | | | | | | | | | | 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
* Move TargetData to DataLayout.Micah Villmow2012-10-081-3/+3
| | | | llvm-svn: 165402
* Remove unused private fields found by clang's new -Wunused-private-field.Benjamin Kramer2012-06-061-2/+0
| | | | | | | | There are some that I didn't remove this round because they looked like obvious stubs. There are dead variables in gtest too, they should be fixed upstream. llvm-svn: 158090
* Remove unused simplifyIVUsersAndrew Trick2012-03-221-41/+0
| | | | llvm-svn: 153262
* LSR fix: Add isSimplifiedLoopNest to IVUsers analysis.Andrew Trick2012-03-161-2/+4
| | | | | | | | | | | | | | 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
* Unweaken vtables as per ↵David Blaikie2011-12-201-0/+2
| | | | | | http://llvm.org/docs/CodingStandards.html#ll_virtual_anch llvm-svn: 146960
* Fix an overly general check in SimplifyIndvar to handle useless phi cycles.Andrew Trick2011-11-171-2/+2
| | | | | | | | | | | | | | The right way to check for a binary operation is cast<BinaryOperator>. The original check: cast<Instruction> && numOperands() == 2 would match phi "instructions", leading to an infinite loop in extreme corner case: a useless phi with operands [self, constant] that prior optimization passes failed to remove, being used in the loop by another useless phi, in turn being used by an lshr or udiv. Fixes PR11350: runaway iteration assertion. llvm-svn: 144935
* Stop emitting instructions with the name "tmp" they eat up memory and have ↵Benjamin Kramer2011-09-271-2/+1
| | | | | | | | to be uniqued, without any benefit. If someone prefers %tmp42 to %42, run instnamer. llvm-svn: 140634
* [indvars] Fix PR10946: SCEV cannot handle Vector IVs.Andrew Trick2011-09-191-0/+6
| | | | llvm-svn: 140026
* Comments. Thanks for the spell check Nick!Andrew Trick2011-08-101-2/+2
| | | | | | Also, my apologies for spoiling the autocomplete on SimplifyInstructions.cpp. I couldn't think of a better filename. llvm-svn: 137229
* Cleanup. Make ScalarEvolution an explicit argument of theAndrew Trick2011-08-101-9/+9
| | | | | | SimplifyIndVar utility since it is required. llvm-svn: 137202
* SimplifyIndVar: make foldIVUser iterative to fold a chain of operands.Andrew Trick2011-08-101-12/+26
| | | | llvm-svn: 137199
* Added a SimplifyIndVar utility to simplify induction variable usersAndrew Trick2011-08-101-0/+413
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
OpenPOWER on IntegriCloud