summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [IRCE] Switch over to LLVM_DUMP_METHOD. NFCI.Davide Italiano2016-08-181-2/+1
| | | | llvm-svn: 279079
* Replace "fallthrough" comments with LLVM_FALLTHROUGHJustin Bogner2016-08-171-3/+3
| | | | | | | This is a mechanical change of comments in switches like fallthrough, fall-through, or fall-thru to use the LLVM_FALLTHROUGH macro instead. llvm-svn: 278902
* Scalar: Avoid dereferencing end() in InductiveRangeCheckEliminationDuncan P. N. Exon Smith2016-08-171-3/+3
| | | | | | | | | BasicBlock::Create isn't designed to take iterators (which might be end()), but pointers (which might be nullptr). Fix the UB that was converting end() to a BasicBlock* by calling BasicBlock::getNextNode() in the first place. llvm-svn: 278883
* [IRCE] Change variable grouping; NFCSanjoy Das2016-08-141-2/+2
| | | | llvm-svn: 278619
* [IRCE] Create llvm::Loop instances for cloned out loopsSanjoy Das2016-08-141-10/+45
| | | | llvm-svn: 278618
* [IRCE] Don't iterate on loops that were cloned outSanjoy Das2016-08-141-0/+12
| | | | | | | | | | | | | | | | IRCE has the ability to further version pre-loops and post-loops that it created, but this isn't useful at all. This change teaches IRCE to leave behind some metadata in the loops it creates (by cloning the main loop) so that these new loops are not re-processed by IRCE. Today this bug is hidden by another bug -- IRCE does not update LoopInfo properly so the loop pass manager does not re-invoke IRCE on the loops it split out. However, once the latter is fixed the bug addressed in this change causes IRCE to infinite-loop in some cases (e.g. it splits out a pre-loop, a pre-pre-loop from that, a pre-pre-pre-loop from that and so on). llvm-svn: 278617
* [IRCE] Add better DEBUG diagnostic; NFCSanjoy Das2016-08-141-1/+3
| | | | | | | NFC meaning IRCE should not _do_ anything different, but -debug-only=irce will be a little friendlier. llvm-svn: 278616
* [IRCE] Be resilient in the face of non-simplified loopsSanjoy Das2016-08-131-1/+4
| | | | | | | | Loops containing `indirectbr` may not be in simplified form, even after running LoopSimplify. Reject then gracefully, instead of tripping an assert. llvm-svn: 278611
* [IRCE] Use dyn_cast instead of explicit isa/cast; NFCSanjoy Das2016-08-131-10/+8
| | | | llvm-svn: 278607
* [IRCE] Use range-for; NFCSanjoy Das2016-08-131-5/+3
| | | | llvm-svn: 278606
* [IRCE] Remove unused headers; NFCSanjoy Das2016-08-061-7/+0
| | | | llvm-svn: 277892
* [IRCE] Preserve loop-simplify formSanjoy Das2016-08-061-0/+2
| | | | | | | | Fixes PR28764. Right now there is no way to test this, but (as mentioned on the PR) with Michael Zolotukhin's yet to be checked in LoopSimplify verfier, 8 of the llvm-lit tests for IRCE crash. llvm-svn: 277891
* [IRCE] Rename variable; NFCSanjoy Das2016-08-021-6/+6
| | | | | | There is nothing "Original" about "OriginalLoopInfo". llvm-svn: 277506
* [IRCE] Preserve DomTree and LCSSASanjoy Das2016-08-021-5/+11
| | | | | | | This changes IRCE to "preserve" LCSSA and DomTree by recomputing them. It still does not preserve LoopSimplify. llvm-svn: 277505
* [IRCE] Add an option to skip profitability checksSanjoy Das2016-07-221-2/+7
| | | | | | | | If `-irce-skip-profitability-checks` is passed in, IRCE will kick in in all cases where it is legal for it to kick in. This flag is intended to help diagnose and analyse performance issues. llvm-svn: 276372
* [IRCE] Use getTerminator instead of rbegin; NFCSanjoy Das2016-06-231-5/+5
| | | | llvm-svn: 273586
* [IRCE] Use C++11 style initializers; NFCSanjoy Das2016-05-261-9/+5
| | | | llvm-svn: 270815
* [IRCE] Optimize conjunctions of range checksSanjoy Das2016-05-261-51/+69
| | | | | | | | | | | | | After this change, we do the expected thing for cases like ``` Check0Passed = /* range check IRCE can optimize */ Check1Passed = /* range check IRCE can optimize */ if (!(Check0Passed && Check1Passed)) throw_Exception(); ``` llvm-svn: 270804
* [IRCE] Refactor out a parseRangeCheckFromCond; NFCSanjoy Das2016-05-261-50/+39
| | | | | | | This will later hold more general logic to parse conjunctions of range checks. llvm-svn: 270802
* [IRCE] Return a Value*, not SCEV* from parseRangeCheck; NFCSanjoy Das2016-05-241-26/+10
| | | | | | | This is better layering, since the caller needs to check if the index was an add-rec anyway. llvm-svn: 270582
* [IRCE] Optimize "uses" not branches; NFCISanjoy Das2016-05-231-9/+10
| | | | | | | | | | This changes IRCE to optimize uses, and not branches. This change is NFCI since the uses we do inspect are in practice only ever going to be the condition use in conditional branches; but this flexibility will later allow us to analyze more complex expressions than just a direct branch on a range check. llvm-svn: 270500
* [IRCE] Don't use an allocator for range checks; NFCSanjoy Das2016-05-211-37/+28
| | | | | | | | The InductiveRangeCheck struct is only five words long; so passing these around value is fine. The allocator makes the code look more complex than it is. llvm-svn: 270309
* [IRCE] Don't pass IRBuilder<> where unnecessary; NFCSanjoy Das2016-05-211-8/+6
| | | | llvm-svn: 270308
* Add opt-bisect support to additional passes that can be skippedAndrew Kaylor2016-05-031-0/+3
| | | | | | Differential Revision: http://reviews.llvm.org/D19882 llvm-svn: 268457
* [NFC] Header cleanupMehdi Amini2016-04-181-1/+0
| | | | | | | | | | | | | | Removed some unused headers, replaced some headers with forward class declarations. Found using simple scripts like this one: clear && ack --cpp -l '#include "llvm/ADT/IndexedMap.h"' | xargs grep -L 'IndexedMap[<]' | xargs grep -n --color=auto 'IndexedMap' Patch by Eugene Kosov <claprix@yandex.ru> Differential Revision: http://reviews.llvm.org/D19219 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 266595
* IR: RF_IgnoreMissingValues => RF_IgnoreMissingLocals, NFCDuncan P. N. Exon Smith2016-04-071-1/+1
| | | | | | | | | | | | | | | | | | | | | | | Clarify what this RemapFlag actually means. - Change the flag name to match its intended behaviour. - Clearly document that it's not supposed to affect globals. - Add a host of FIXMEs to indicate how to fix the behaviour to match the intent of the flag. RF_IgnoreMissingLocals should only affect the behaviour of RemapInstruction for function-local operands; namely, for operands of type Argument, Instruction, and BasicBlock. Currently, it is *only* passed into RemapInstruction calls (and the transitive MapValue calls that it makes). When I split Metadata from Value I didn't understand the flag, and I used it in a bunch of places for "global" metadata. This commit doesn't have any functionality change, but prepares to cleanup MapMetadata and MapValue. llvm-svn: 265628
* Return StringRef instead of a naked char*; NFCSanjoy Das2016-03-091-2/+2
| | | | llvm-svn: 262989
* [IRCE] Reflow comments; NFCSanjoy Das2016-03-091-4/+2
| | | | llvm-svn: 262988
* [LPM] Factor all of the loop analysis usage updates into a common helperChandler Carruth2016-02-191-8/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | routine. We were getting this wrong in small ways and generally being very inconsistent about it across loop passes. Instead, let's have a common place where we do this. One minor downside is that this will require some analyses like SCEV in more places than they are strictly needed. However, this seems benign as these analyses are complete no-ops, and without this consistency we can in many cases end up with the legacy pass manager scheduling deciding to split up a loop pass pipeline in order to run the function analysis half-way through. It is very, very annoying to fix these without just being very pedantic across the board. The only loop passes I've not updated here are ones that use AU.setPreservesAll() such as IVUsers (an analysis) and the pass printer. They seemed less relevant. With this patch, almost all of the problems in PR24804 around loop pass pipelines are fixed. The one remaining issue is that we run simplify-cfg and instcombine in the middle of the loop pass pipeline. We've recently added some loop variants of these passes that would seem substantially cleaner to use, but this at least gets us much closer to the previous state. Notably, the seven loop pass managers is down to three. I've not updated the loop passes using LoopAccessAnalysis because that analysis hasn't been fully wired into LoopSimplify/LCSSA, and it isn't clear that those transforms want to support those forms anyways. They all run late anyways, so this is harmless. Similarly, LSR is left alone because it already carefully manages its forms and doesn't need to get fused into a single loop pass manager with a bunch of other loop passes. LoopReroll didn't use loop simplified form previously, and I've updated the test case to match the trivially different output. Finally, I've also factored all the pass initialization for the passes that use this technique as well, so that should be done regularly and reliably. Thanks to James for the help reviewing and thinking about this stuff, and Ben for help thinking about it as well! Differential Revision: http://reviews.llvm.org/D17435 llvm-svn: 261316
* Scalar: Remove some implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-10-131-2/+2
| | | | | | | Remove some of the implicit ilist iterator conversions in LLVMScalarOpts. More to go. llvm-svn: 250197
* [IRCE] Add INITIALIZE_PASS_DEPENDENCY invocations.Sanjoy Das2015-09-091-2/+9
| | | | | | IRCE was just using INITIALIZE_PASS(), which is incorrect. llvm-svn: 247122
* [PM] Port ScalarEvolution to the new pass manager.Chandler Carruth2015-08-171-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change makes ScalarEvolution a stand-alone object and just produces one from a pass as needed. Making this work well requires making the object movable, using references instead of overwritten pointers in a number of places, and other refactorings. I've also wired it up to the new pass manager and added a RUN line to a test to exercise it under the new pass manager. This includes basic printing support much like with other analyses. But there is a big and somewhat scary change here. Prior to this patch ScalarEvolution was never *actually* invalidated!!! Re-running the pass just re-wired up the various other analyses and didn't remove any of the existing entries in the SCEV caches or clear out anything at all. This might seem OK as everything in SCEV that can uses ValueHandles to track updates to the values that serve as SCEV keys. However, this still means that as we ran SCEV over each function in the module, we kept accumulating more and more SCEVs into the cache. At the end, we would have a SCEV cache with every value that we ever needed a SCEV for in the entire module!!! Yowzers. The releaseMemory routine would dump all of this, but that isn't realy called during normal runs of the pipeline as far as I can see. To make matters worse, there *is* actually a key that we don't update with value handles -- there is a map keyed off of Loop*s. Because LoopInfo *does* release its memory from run to run, it is entirely possible to run SCEV over one function, then over another function, and then lookup a Loop* from the second function but find an entry inserted for the first function! Ouch. To make matters still worse, there are plenty of updates that *don't* trip a value handle. It seems incredibly unlikely that today GVN or another pass that invalidates SCEV can update values in *just* such a way that a subsequent run of SCEV will incorrectly find lookups in a cache, but it is theoretically possible and would be a nightmare to debug. With this refactoring, I've fixed all this by actually destroying and recreating the ScalarEvolution object from run to run. Technically, this could increase the amount of malloc traffic we see, but then again it is also technically correct. ;] I don't actually think we're suffering from tons of malloc traffic from SCEV because if we were, the fact that we never clear the memory would seem more likely to have come up as an actual problem before now. So, I've made the simple fix here. If in fact there are serious issues with too much allocation and deallocation, I can work on a clever fix that preserves the allocations (while clearing the data) between each run, but I'd prefer to do that kind of optimization with a test case / benchmark that shows why we need such cleverness (and that can test that we actually make it faster). It's possible that this will make some things faster by making the SCEV caches have higher locality (due to being significantly smaller) so until there is a clear benchmark, I think the simple change is best. Differential Revision: http://reviews.llvm.org/D12063 llvm-svn: 245193
* Create a wrapper pass for BranchProbabilityInfo.Cong Hou2015-07-151-2/+3
| | | | | | | | This new wrapper pass is useful when we want to do branch probability analysis conditionally (e.g. only in PGO mode) but don't want to add one more pass dependence. http://reviews.llvm.org/D11241 llvm-svn: 242349
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-2/+2
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-2/+2
| | | | | | | | | | | | | 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
* [IRCE] Fix how IRCE checks for no-sign-overflow.Sanjoy Das2015-03-241-14/+24
| | | | | | | | | IRCE requires the induction variables it handles to not sign-overflow. The current scheme of checking if sext({X,+,S}) == {sext(X),+,sext(S)} fails when SCEV simplifies sext(X) too. After this change we //also// check no-signed-wrap by looking at the flags set on the SCEVAddRecExpr. llvm-svn: 233102
* [IRCE] Fix a regression introduced in r232444.Sanjoy Das2015-03-241-9/+20
| | | | | | | IRCE should not try to eliminate range checks that check an induction variable against a loop-varying length. llvm-svn: 233101
* Re-sort includes with sort-includes.py and insert raw_ostream.h where it's used.Benjamin Kramer2015-03-231-8/+3
| | | | llvm-svn: 232998
* Fix GCC -Wparentheses warning (& reformat now that the precedence is fixed)David Blaikie2015-03-171-2/+2
| | | | | | | Benign warning (clang deliberately suppresses this case) but does regularly produce bad formatting, so it's nice to fix/reformat. llvm-svn: 232508
* Use an underlying enum type of unsigned to silence a -Wmicrosoft warning ↵Reid Kleckner2015-03-171-1/+1
| | | | | | about being unable to put (unsigned)-1 into the default underyling type of int llvm-svn: 232498
* [IRCE] Add a -irce-print-range-checks option.Sanjoy Das2015-03-171-6/+15
| | | | | | | -irce-print-range-checks prints out the set of range checks recognized by IRCE. llvm-svn: 232451
* [IRCE] Add comments, NFC.Sanjoy Das2015-03-171-4/+27
| | | | | | | This change adds some comments that justify why a potentially overflowing operation is safe. llvm-svn: 232445
* [IRCE] Support half-range checks.Sanjoy Das2015-03-171-128/+152
| | | | | | | | | | | | This change to IRCE gets it to recognize "half" range checks. Half range checks are range checks that only either check if the index is `slt` some positive integer ("length") or if the index is `sge` `0`. The range solver does not try to be clever / aggressive about solving half-range checks -- it transforms "I < L" to "0 <= I < L" and "0 <= I" to "0 <= I < INT_SMAX". This is safe, but not always optimal. llvm-svn: 232444
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-4/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Now that the DataLayout is a mandatory part of the module, let's start cleaning the codebase. This patch is a first attempt at doing that. This patch is not exactly NFC as for instance some places were passing a nullptr instead of the DataLayout, possibly just because there was a default value on the DataLayout argument to many functions in the API. Even though it is not purely NFC, there is no change in the validation. I turned as many pointer to DataLayout to references, this helped figuring out all the places where a nullptr could come up. I had initially a local version of this patch broken into over 30 independant, commits but some later commit were cleaning the API and touching part of the code modified in the previous commits, so it seemed cleaner without the intermediate state. Test Plan: Reviewers: echristo Subscribers: llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231740
* IRCE: only touch loops that have been shown to have a highSanjoy Das2015-02-261-4/+17
| | | | | | backedge-taken count in profiliing data. llvm-svn: 230619
* IRCE: generalize to handle loops with decreasing induction variables.Sanjoy Das2015-02-261-207/+358
| | | | | | | | | IRCE can now split the iteration space for loops like: for (i = n; i >= 0; i--) a[i + k] = 42; // bounds check on access llvm-svn: 230618
* IRCE: print newline after printing an InductiveRangeCheck.Sanjoy Das2015-02-261-0/+1
| | | | llvm-svn: 230607
* IRCE: generalize InductiveRangeCheck::computeSafeIterationSpace toSanjoy Das2015-02-211-32/+57
| | | | | | | | | | work with a non-canonical induction variable. This is currently a non-functional change because we only ever call computeSafeIterationSpace on a canonical induction variable; but the generalization will be useful in a later commit. llvm-svn: 230151
* IRCE: use SCEVs instead of llvm::Value's for intermediateSanjoy Das2015-02-211-46/+30
| | | | | | | | | calculations. Semantically non-functional change. This gets rid of some of the SCEV -> Value -> SCEV round tripping and the Construct(SMin|SMax)Of and MaybeSimplify helper routines. llvm-svn: 230150
* Make helper functions/classes/globals static. NFC.Benjamin Kramer2015-02-061-4/+4
| | | | llvm-svn: 228410
OpenPOWER on IntegriCloud