summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* whitespaceAndrew Trick2011-03-091-18/+18
| | | | llvm-svn: 127340
* teach SCEV that the scale and addition of an inbounds gep don't NSW.Chris Lattner2011-02-131-2/+5
| | | | | | | This fixes a FIXME in scev-aa.ll (allowing a new no-alias result) and generally makes things more precise. llvm-svn: 125449
* Per discussion with Dan G, inbounds geps *certainly* can haveChris Lattner2011-02-111-3/+14
| | | | | | | | | | | unsigned overflow (e.g. "gep P, -1"), and while they can have signed wrap in theoretical situations, modelling an AddRec as not having signed wrap is going enough for any case we can think of today. In the future if this isn't enough, we can revisit this. Modeling them as having NUW isn't causing any known problems either FWIW. llvm-svn: 125410
* Fix memory corruption. If one of the SCEV creation functions calls another butNick Lewycky2011-01-261-0/+2
| | | | | | | doesn't return immediately after then the insert position in UniqueSCEVs will be out of date. No test because this is a memory corruption issue. Fixes PR9051! llvm-svn: 124282
* Add a comment.Dan Gohman2011-01-241-0/+1
| | | | llvm-svn: 124126
* Simplify some code with no functionality change. Make the test a lot moreNick Lewycky2011-01-231-12/+4
| | | | | | robust against smarter optimizations, using the power of FileCheck. llvm-svn: 124081
* Use value ranges to fold ext(trunc) in SCEV when possible.Nick Lewycky2011-01-231-0/+34
| | | | llvm-svn: 124062
* Have SCEV turn sext(x) into zext(x) when x is s>= 0. This applies many times inNick Lewycky2011-01-221-0/+4
| | | | | | "make check" alone. llvm-svn: 124046
* Similarly, analyze truncate through multiply.Nick Lewycky2011-01-191-0/+14
| | | | llvm-svn: 123842
* Add a missed SCEV fold that is required to continue analyzing the IR producedNick Lewycky2011-01-191-0/+14
| | | | | | | | | | | by indvars through the scev expander. trunc(add x, y) --> add(trunc x, y). Currently SCEV largely folds the other way which is probably wrong, but preserved to minimize churn. Instcombine doesn't do this fold either, demonstrating a missed optz'n opportunity on code doing add+trunc+add. llvm-svn: 123838
* Add a missing SCEV simplification sext(zext x) --> zext x.Nick Lewycky2011-01-191-0/+4
| | | | llvm-svn: 123832
* some comment improvements.Chris Lattner2011-01-111-3/+4
| | | | llvm-svn: 123243
* Temporarily revert 123133, it's causing some regressions and I'm tryingEric Christopher2011-01-111-8/+4
| | | | | | to get a testcase. llvm-svn: 123225
* the GEP faq says that only inbounds geps are guaranteed to not overflow.Chris Lattner2011-01-111-2/+3
| | | | llvm-svn: 123218
* add a fixme: ir isn't expressive enough.Chris Lattner2011-01-091-0/+1
| | | | llvm-svn: 123139
* Step #4 in improving trip count analysis: HowFarToZero can analyzeChris Lattner2011-01-091-2/+11
| | | | | | | NUW AddRec's much more aggressively. We now get a trip count for @test2 in nsw.ll llvm-svn: 123138
* rearrange some code, no functionality change.Chris Lattner2011-01-091-41/+45
| | | | llvm-svn: 123136
* Step #3 to improving trip count analysis: If we foldChris Lattner2011-01-091-4/+8
| | | | | | | | a + {b,+,stride} into {a+b,+,stride} (because a is LIV), then the resultant AddRec is NUW/NSW if the client says it is. llvm-svn: 123133
* Step #2 to improve trip count analysis for loops like this:Chris Lattner2011-01-091-6/+105
| | | | | | | | | | | | | | | | | | | void f(int* begin, int* end) { std::fill(begin, end, 0); } which turns into a != exit expression where one pointer is strided and (thanks to step #1) known to not overflow, and the other is loop invariant. The observation here is that, though the IV is strided by 4 in this case, that the IV *has* to become equal to the end value. It cannot "miss" the end value by stepping over it, because if it did, the strided IV expression would eventually wrap around. Handle this by turning A != B into "A-B != 0" where the A-B part is known to be NUW. llvm-svn: 123131
* teach SCEV analysis of PHI nodes that PHI recurences formedChris Lattner2011-01-091-0/+5
| | | | | | | with GEP instructions are always NUW, because PHIs cannot wrap the end of the address space. llvm-svn: 123105
* reduce indentation. Print <nuw> and <nsw> when dumping SCEV AddRec'sChris Lattner2011-01-091-49/+54
| | | | | | that have the bit set. llvm-svn: 123104
* PR5207: Change APInt methods trunc(), sext(), zext(), sextOrTrunc() andJay Foad2010-12-071-2/+2
| | | | | | | | zextOrTrunc(), and APSInt methods extend(), extOrTrunc() and new method trunc(), to be const and to return a new value instead of modifying the object in place. llvm-svn: 121120
* PR5207: Rename overloaded APInt methods set(), clear(), flip() toJay Foad2010-12-011-1/+1
| | | | | | setAllBits(), setBit(unsigned), etc. llvm-svn: 120564
* Simplify code. No change in functionality.Benjamin Kramer2010-11-201-2/+2
| | | | llvm-svn: 119908
* Silence warning about an uninitialized variable.Benjamin Kramer2010-11-191-1/+1
| | | | llvm-svn: 119800
* Factor code for testing whether replacing one value with anotherDuncan Sands2010-11-181-17/+2
| | | | | | | | preserves LCSSA form out of ScalarEvolution and into the LoopInfo class. Use it to check that SimplifyInstruction simplifications are not breaking LCSSA form. Fixes PR8622. llvm-svn: 119727
* Introduce memoization for ScalarEvolution dominates and properlyDominatesDan Gohman2010-11-181-58/+56
| | | | | | queries, and SCEVExpander getRelevantLoop queries. llvm-svn: 119595
* Factor out the code for purging a SCEV from all the various memoization maps.Dan Gohman2010-11-171-26/+13
| | | | | | | Some of these maps may merge in the future, but for now it's convenient to have a utility function for them. llvm-svn: 119587
* Merge the implementations of isLoopInvariant and hasComputableLoopEvolution, andDan Gohman2010-11-171-71/+58
| | | | | | | memoize the results. This improves compile time in code which highly complex expressions which get queried many times. llvm-svn: 119584
* Make SCEV::getType() and SCEV::print non-virtual. Move SCEV::hasOperandDan Gohman2010-11-171-105/+167
| | | | | | to ScalarEvolution. Delete SCEV::~SCEV. SCEV is no longer virtual. llvm-svn: 119578
* Move SCEV::dominates and properlyDominates to ScalarEvolution.Dan Gohman2010-11-171-58/+91
| | | | llvm-svn: 119570
* Move SCEV::isLoopInvariant and hasComputableLoopEvolution to be memberDan Gohman2010-11-171-81/+135
| | | | | | | functions of ScalarEvolution, in preparation for memoization and other optimizations. llvm-svn: 119562
* Before replacing a phi node with a different value, itDuncan Sands2010-11-171-11/+15
| | | | | | | | | | needs to be checked that this won't break LCSSA form. Change the existing checking method to a more direct one: rather than seeing if all predecessors belong to the loop, check that the replacing value is either not in any loop or is in a loop that contains the phi node. llvm-svn: 119556
* Verify SCEVAddRecExpr's invariant in ScalarEvolution::getAddRecExprDan Gohman2010-11-171-0/+3
| | | | | | | instead of in SCEVAddRecExpr's constructor, in preparation for an upcoming change. llvm-svn: 119554
* Fix ScalarEvolution's range memoization to avoid using aDan Gohman2010-11-171-44/+43
| | | | | | default ctor with ConstantRange. llvm-svn: 119550
* Have ScalarEvolution use SimplifyInstruction rather than hasConstantValue.Duncan Sands2010-11-171-1/+5
| | | | | | While there, add a note about an inefficiency I noticed. llvm-svn: 119458
* Memoize results from ScalarEvolution's getUnsignedRange and getSignedRange.Dan Gohman2010-11-171-43/+80
| | | | | | This fixes some extreme compile times on unrolled sha512 code. llvm-svn: 119455
* Make ScalarEvolution::forgetLoop forget all contained loops too, becauseDan Gohman2010-10-291-0/+5
| | | | | | | they may have ValuesAtScopes map entries referencing their outer loops. This fixes a user-after-free reported in PR8471. llvm-svn: 117698
* Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson2010-10-191-0/+1
| | | | | | | | | | | | | | | | | exposes an initializeMyPassFunction(), which must be called in the pass's constructor. This function uses static dependency declarations to recursively initialize the pass's dependencies. Clients that only create passes through the createFooPass() APIs will require no changes. Clients that want to use the CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h before parsing commandline arguments. I have tested this with all standard configurations of clang and llvm-gcc on Darwin. It is possible that there are problems with the static dependencies that will only be visible with non-standard options. If you encounter any crash in pass registration/creation, please send the testcase to me directly. llvm-svn: 116820
* Begin adding static dependence information to passes, which will allow us toOwen Anderson2010-10-121-1/+5
| | | | | | | | | perform initialization without static constructors AND without explicit initialization by the client. For the moment, passes are required to initialize both their (potential) dependencies and any passes they preserve. I hope to be able to relax the latter requirement in the future. llvm-svn: 116334
* Now with fewer extraneous semicolons!Owen Anderson2010-10-071-1/+1
| | | | llvm-svn: 115996
* Don't add the operand count to SCEV uniquing data; FoldingSetNodeIDDan Gohman2010-10-041-5/+0
| | | | | | already knows its own length, so this is redundant. llvm-svn: 115521
* Reapply r112432, now that the real problem is addressed.Dan Gohman2010-08-311-4/+9
| | | | llvm-svn: 112667
* Reapply r112433, now that the real problem is addressed.Dan Gohman2010-08-311-21/+24
| | | | llvm-svn: 112666
* Revert r110916. This patch is buggy because the code inside theDan Gohman2010-08-311-7/+4
| | | | | | inner loop doesn't update all the variables in the outer loop. llvm-svn: 112665
* Revert r112432. It appears to be exposing a problem in the emacs build.Dan Gohman2010-08-311-9/+4
| | | | llvm-svn: 112638
* Speculatively revert r112433.Dan Gohman2010-08-311-24/+21
| | | | llvm-svn: 112608
* Restructure the {A,+,B}<L> * {C,+,D}<L> folding so that it foldsDan Gohman2010-08-291-21/+24
| | | | | | | all applicable addrecs before recursing on getMulExpr, instead of recursing on getMulExpr for each one. llvm-svn: 112433
* Batch up subtracts along with adds, when analyzing long chains ofDan Gohman2010-08-291-4/+9
| | | | | | operations. llvm-svn: 112432
* Micro-optimize GroupByComplexity.Dan Gohman2010-08-291-2/+3
| | | | llvm-svn: 112431
OpenPOWER on IntegriCloud