summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolutionNormalization.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* Teach SCEV normalization to de/normalize non-affine add recsSanjoy Das2017-04-251-32/+39
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Before this change, SCEV Normalization would incorrectly normalize non-affine add recurrences. To work around this there was (still is) a check in place to make sure we only tried to normalize affine add recurrences. We recently found a bug in aforementioned check to bail out of normalizing non-affine add recurrences. However, instead of fixing the bailout, I have decided to teach SCEV normalization to work correctly with non-affine add recurrences, making the bailout unnecessary (I'll remove it in a subsequent change). I've also added some unit tests (which would have failed before this change). Reviewers: atrick, sunfish, efriedma Reviewed By: atrick Subscribers: mcrosier, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D32104 llvm-svn: 301281
* Rewrite SCEV Normalization using SCEVRewriteVisitor; NFCSanjoy Das2017-04-141-121/+57
| | | | | | | Removes all of the boilerplate, cache management etc. from ScalarEvolutionNormalization, and keeps only the interesting bits. llvm-svn: 300349
* Remove "#if 0"ed out assertSanjoy Das2017-04-141-5/+0
| | | | | | | | | | | It won't compile after the recent changes I've made, and I think keeping it in provides very little value. Instead I've added (in an earlier commit) a C++ unit test to check the Denormalize(Normalized(X)) == X property for specific instances of X, which is what the assert was trying to do anyway. llvm-svn: 300339
* Delete some unnecessary boilerplateSanjoy Das2017-04-141-47/+29
| | | | | | | | | | | | The PostIncTransform class was not pulling its weight, so delete it and use free functions instead. This also makes the use of `function_ref` more idiomatic. We were storing an instance of function_ref in the PostIncTransform class before, which was fine in that specific case, but the usage after this change is more obviously okay. llvm-svn: 300338
* Use range forSanjoy Das2017-04-141-3/+1
| | | | llvm-svn: 300334
* Simplify PostIncTransform further; NFCSanjoy Das2017-04-141-16/+19
| | | | | | | Instead of having two ways to check if an add recurrence needs to be normalized, just pass in one predicate to decide that. llvm-svn: 300333
* Tighten the API for ScalarEvolutionNormalizationSanjoy Das2017-04-141-6/+34
| | | | llvm-svn: 300331
* Remove NormalizeAutodetect; NFCSanjoy Das2017-04-141-108/+23
| | | | | | | | | It is cleaner to have a callback based system where the logic of whether an add recurrence is normalized or not lives on IVUsers. This is one step in a multi-step cleanup. llvm-svn: 300330
* Use transform instead of manual loop; NFCSanjoy Das2017-04-141-5/+5
| | | | llvm-svn: 300291
* Remove emacs mode markers from .cpp files. NFCNick Lewycky2016-04-241-1/+1
| | | | | | .cpp files are unambiguously C++, you only need the mode markers on .h files. llvm-svn: 267353
* Analysis: Remove implicit ilist iterator conversionsDuncan P. N. Exon Smith2015-10-101-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Remove implicit ilist iterator conversions from LLVMAnalysis. I came across something really scary in `llvm::isKnownNotFullPoison()` which relied on `Instruction::getNextNode()` being completely broken (not surprising, but scary nevertheless). This function is documented (and coded to) return `nullptr` when it gets to the sentinel, but with an `ilist_half_node` as a sentinel, the sentinel check looks into some other memory and we don't recognize we've hit the end. Rooting out these scary cases is the reason I'm removing the implicit conversions before doing anything else with `ilist`; I'm not at all surprised that clients rely on badness. I found another scary case -- this time, not relying on badness, just bad (but I guess getting lucky so far) -- in `ObjectSizeOffsetEvaluator::compute_()`. Here, we save out the insertion point, do some things, and then restore it. Previously, we let the iterator auto-convert to `Instruction*`, and then set it back using the `Instruction*` version: Instruction *PrevInsertPoint = Builder.GetInsertPoint(); /* Logic that may change insert point */ if (PrevInsertPoint) Builder.SetInsertPoint(PrevInsertPoint); The check for `PrevInsertPoint` doesn't protect correctly against bad accesses. If the insertion point has been set to the end of a basic block (i.e., `SetInsertPoint(SomeBB)`), then `GetInsertPoint()` returns an iterator pointing at the list sentinel. The version of `SetInsertPoint()` that's getting called will then call `PrevInsertPoint->getParent()`, which explodes horribly. The only reason this hasn't blown up is that it's fairly unlikely the builder is adding to the end of the block; usually, we're adding instructions somewhere before the terminator. llvm-svn: 249925
* Fix typos in comments, NFCRobin Morisset2014-08-291-1/+1
| | | | | | | | | | | | | | Summary: Just fixing comments, no functional change. Test Plan: N/A Reviewers: jfb Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D5130 llvm-svn: 216784
* test check-in: added missing parenthesis in commentSanjay Patel2014-05-281-1/+1
| | | | llvm-svn: 209763
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-151-1/+1
| | | | | | instead of comparing to nullptr. llvm-svn: 206243
* Add stride normalization to SCEV Normalize/Denormalize transformation.Michael Zolotukhin2014-03-181-3/+26
| | | | llvm-svn: 204161
* [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
* Fix LSR: don't normalize quadratic recurrences.Andrew Trick2013-10-251-5/+13
| | | | | | | | | | Partial fix for PR17459: wrong code at -O3 on x86_64-linux-gnu (affecting trunk and 3.3) ScalarEvolutionNormalization was attempting to normalize by adding and subtracting strides. Chained recurrences don't work that way. llvm-svn: 193437
* More dead code removal (using -Wunreachable-code)David Blaikie2012-01-201-1/+0
| | | | llvm-svn: 148578
* Remove unnecessary default cases in switches that cover all enum values.David Blaikie2012-01-101-1/+0
| | | | llvm-svn: 147855
* Fix memory corruption I introduced a few checkins ago.Andrew Trick2011-10-131-5/+6
| | | | | | Self-review easily caught this obvious bug. llvm-svn: 141880
* SCEV: Rewrite TrandformForPostIncUse to handle expression DAGs, notAndrew Trick2011-10-131-30/+70
| | | | | | | | just expression trees. Partially fixes PR11090. Test case will be with the full fix. llvm-svn: 141868
* Added SCEV::NoWrapFlags to manage unsigned, signed, and self wrapAndrew Trick2011-03-141-1/+2
| | | | | | | | | properties. Added the self-wrap flag for SCEV::AddRecExpr. A slew of temporary FIXMEs indicate the intention of the no-self-wrap flag without changing behavior in this revision. llvm-svn: 127590
* Disable the asserts that check that normalization is perfectlyDan Gohman2010-09-031-2/+7
| | | | | | | | | invertible. ScalarEvolution's folding routines don't always succeed in canonicalizing equal expressions to a single canonical form, and this can cause these asserts to fail, even though there's no actual correctness problem. This fixes PR8066. llvm-svn: 113021
* Fix SCEV denormalization of expressions where the exit value fromDan Gohman2010-07-201-32/+55
| | | | | | | one loop is involved in the increment of an addrec for another loop. This fixes rdar://8168938. llvm-svn: 108863
* Change an argument from an Instruction* to a Value*, which is allDan Gohman2010-07-201-5/+5
| | | | | | that is needed here. llvm-svn: 108850
* Minor code cleanups.Dan Gohman2010-07-201-0/+5
| | | | llvm-svn: 108848
* Minor code simplification.Dan Gohman2010-07-201-6/+3
| | | | llvm-svn: 108793
* Fix normalization and de-normalization of non-affine SCEVs.Dan Gohman2010-06-041-6/+9
| | | | llvm-svn: 105480
* Generalize IVUsers to track arbitrary expressions rather than expressionsDan Gohman2010-04-071-0/+150
explicitly split into stride-and-offset pairs. Also, add the ability to track multiple post-increment loops on the same expression. This refines the concept of "normalizing" SCEV expressions used for to post-increment uses, and introduces a dedicated utility routine for normalizing and denormalizing expressions. This fixes the expansion of expressions which are post-increment users of more than one loop at a time. More broadly, this takes LSR another step closer to being able to reason about more than one loop at a time. llvm-svn: 100699
OpenPOWER on IntegriCloud