summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Consistently use LoopAnalysisManagerSean Silva2016-08-091-1/+1
| | | | | | | | | | | | | | | | | One exception here is LoopInfo which must forward-declare it (because the typedef is in LoopPassManager.h which depends on LoopInfo). Also, some includes for LoopPassManager.h were needed since that file provides the typedef. Besides a general consistently benefit, the extra layer of indirection allows the mechanical part of https://reviews.llvm.org/D23256 that requires touching every transformation and analysis to be factored out cleanly. Thanks to David for the suggestion. llvm-svn: 278079
* [PM] Port Dead Loop Deletion Pass to the new PMJun Bum Lim2016-07-141-57/+72
| | | | | | | | | | | | Summary: Port Dead Loop Deletion Pass to the new pass manager. Reviewers: silvas, davide Subscribers: llvm-commits, sanjoy, mcrosier Differential Revision: https://reviews.llvm.org/D21483 llvm-svn: 275453
* Apply clang-tidy's modernize-loop-convert to most of lib/Transforms.Benjamin Kramer2016-06-261-6/+4
| | | | | | Only minor manual fixes. No functionality change intended. llvm-svn: 273808
* Use all_of instead of a raw loop; NFCSanjoy Das2016-05-031-6/+4
| | | | | | | Added some tests despite being NFC, since it looks like nothing was exercising the "all incoming values to exit PHIs are same" logic. llvm-svn: 268407
* [LoopDeletion] Clear SCEV loop dispositionsSanjoy Das2016-05-031-11/+27
| | | | | | | | | | | `Loop::makeLoopInvariant` can hoist instructions out of loops, so loop dispositions for the loop it operated on may need to be cleared. We can be smarter here (especially around how `forgetLoopDispositions` is implemented), but let's be correct first. Fixes PR27570. llvm-svn: 268406
* Re-commit optimization bisect support (r267022) without new pass manager ↵Andrew Kaylor2016-04-221-1/+1
| | | | | | | | | | support. The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the OptBisect handling). Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267231
* Revert "Initial implementation of optimization bisect support."Vedant Kumar2016-04-221-1/+1
| | | | | | | | This reverts commit r267022, due to an ASan failure: http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549 llvm-svn: 267115
* Initial implementation of optimization bisect support.Andrew Kaylor2016-04-211-1/+1
| | | | | | | | | | | | This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to track down test failures that are caused by incorrect optimizations. The bisection is enabled using a new command line option (-opt-bisect-limit). Individual passes that may be skipped call the OptBisect object (via an LLVMContext) to see if they should be skipped based on the bisect limit. A finer level of control (disabling individual transformations) can be managed through an addition OptBisect method, but this is not yet used. The skip checking in this implementation is based on (and replaces) the skipOptnoneFunction check. Where that check was being called, a new call has been inserted in its place which checks the bisect limit and the optnone attribute. A new function call has been added for module and SCC passes that behaves in a similar way. Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267022
* [LoopDeletion] Add an assert that verifies LCSSASanjoy Das2016-02-211-1/+3
| | | | | | | This is inspired by PR24804 -- had this assert been there before, isolating the root cause for PR24804 would have been far easier. llvm-svn: 261481
* [LPM] Factor all of the loop analysis usage updates into a common helperChandler Carruth2016-02-191-17/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* LoopInfo: Simplify ownership of Loop objectsJustin Bogner2016-01-081-1/+1
| | | | | | | | | | | It's strange that LoopInfo mostly owns the Loop objects, but that it defers deleting them to the loop pass manager. Instead, change the oddly named "updateUnloop" to "markAsRemoved" and have it queue the Loop object for deletion. We can't delete the Loop immediately when we remove it, since we need its pointer identity still, so we'll mark the object as "invalid" so that clients can see what's going on. llvm-svn: 257191
* LPM: Make callers of LPM.deleteLoopFromQueue update LoopInfo directly. NFCJustin Bogner2015-12-161-5/+4
| | | | | | | | | | | As of r255720, the loop pass manager will DTRT when passes update the loop info for removed loops, so they no longer need to reach into LPPassManager APIs to do this kind of transformation. This change very nearly removes the need for the LPPassManager to even be passed into loop passes - the only remaining pass that uses the LPM argument is LoopUnswitch. llvm-svn: 255797
* Add GlobalsAA as preserved to a bunch of transformsJames Molloy2015-09-101-0/+2
| | | | | | GlobalsAA must by definition be preserved in function passes, but the passmanager doesn't know that. Make each pass explicitly preserve GlobalsAA. llvm-svn: 247263
* [PM] Port ScalarEvolution to the new pass manager.Chandler Carruth2015-08-171-4/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* 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
* [PM] Split the LoopInfo object apart from the legacy pass, creatingChandler Carruth2015-01-171-4/+4
| | | | | | | | | | 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
* Use range based for loops to avoid needing to re-mention SmallPtrSet size.Craig Topper2014-08-241-3/+2
| | | | llvm-svn: 216351
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+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 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-2/+2
| | | | | | class. llvm-svn: 202953
* Disable most IR-level transform passes on functions marked 'optnone'.Paul Robinson2014-02-061-0/+3
| | | | | | | | | Ideally only those transform passes that run at -O0 remain enabled, in reality we get as close as we reasonably can. Passes are responsible for disabling themselves, it's not the job of the pass manager to do it for them. llvm-svn: 200892
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-131-4/+4
| | | | | | | | | | | | | | | | | | | | | | | 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
* Use SmallVectorImpl& instead of SmallVector to avoid repeating small vector ↵Craig Topper2013-07-141-4/+4
| | | | | | size. llvm-svn: 186274
* Use SmallVectorImpl::iterator/const_iterator instead of SmallVector to avoid ↵Craig Topper2013-07-041-1/+1
| | | | | | specifying the vector size. llvm-svn: 185606
* Make method private. Keep coding standard.Jakub Staszak2013-03-181-26/+28
| | | | llvm-svn: 177348
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-3/+3
| | | | | | | | | | | | | | | | | 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
* Clean whitespaces.Nadav Rotem2012-07-241-25/+25
| | | | llvm-svn: 160668
* Don't use PN->replaceUsesOfWith() to change a PHINode's incoming blocks,Jay Foad2011-06-211-1/+3
| | | | | | | because it won't work after my phi operand changes, because the incoming blocks will no longer be Uses. llvm-svn: 133512
* Make LoopDeletion work on loops with multiple edges, as long as the incomingCameron Zwarich2011-02-221-8/+15
| | | | | | values from all of the loop's exiting blocks are equal. Patch by Andrew Clinton. llvm-svn: 126253
* Remove code for updating dominance frontiers and some outdated references toCameron Zwarich2011-01-181-5/+1
| | | | | | dominance and post-dominance frontiers. llvm-svn: 123725
* Use SmallVector instead of SmallPtrSet and avoid non-deterministic behavior.Devang Patel2011-01-121-3/+3
| | | | llvm-svn: 123318
* split dom frontier handling stuff out to its own DominanceFrontier header,Chris Lattner2011-01-021-0/+1
| | | | | | so that Dominators.h is *just* domtree. Also prune #includes a bit. llvm-svn: 122714
* Passes do not need to recursively initialize passes that they preserve, ifOwen Anderson2010-10-191-1/+0
| | | | | | | they do not also require them. This allows us to reduce inter-pass linkage dependencies. llvm-svn: 116854
* Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson2010-10-191-1/+3
| | | | | | | | | | | | | | | | | 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/+9
| | | | | | | | | 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
* Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson2010-08-061-1/+1
| | | | llvm-svn: 110460
* Revert r110396 to fix buildbots.Owen Anderson2010-08-061-1/+1
| | | | llvm-svn: 110410
* Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson2010-08-051-1/+1
| | | | | | | | address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. llvm-svn: 110396
* Remove LCSSA's bogus dependence on LoopSimplify and LoopSimplify's bogusDan Gohman2010-07-261-1/+1
| | | | | | | | | | | | | | dependence on DominanceFrontier. Instead, add an explicit DominanceFrontier pass in StandardPasses.h to ensure that it gets scheduled at the right time. Declare that loop unrolling preserves ScalarEvolution, and shuffle some getAnalysisUsages. This eliminates one LoopSimplify and one LCCSA run in the standard compile opts sequence. llvm-svn: 109413
* Fix batch of converting RegisterPass<> to INTIALIZE_PASS().Owen Anderson2010-07-211-1/+2
| | | | llvm-svn: 109045
* Use pre-increment instead of post-increment when the result is not used.Dan Gohman2010-06-221-3/+3
| | | | llvm-svn: 106542
* LoopDeletion depends on loops having dedicated exits.Dan Gohman2009-11-051-0/+4
| | | | llvm-svn: 86180
* Rename forgetLoopBackedgeTakenCount to forgetLoop, because itDan Gohman2009-10-311-1/+1
| | | | | | clears out more information than just the stored backedge taken count. llvm-svn: 85664
* Simplify this code. LoopDeletion doesn't need to explicit check thatDan Gohman2009-10-261-24/+2
| | | | | | | the loop exiting block dominates the latch block; if ScalarEvolution can prove that the trip-count is finite, that's sufficient. llvm-svn: 85165
* Make LoopDeletion check the maximum backedge taken count, rather than theDan Gohman2009-10-231-1/+1
| | | | | | | exact backedge taken count, when checking for infinite loops. This allows it to delete loops with multiple exit conditions. llvm-svn: 84952
* eliminate VISIBILITY_HIDDEN from Transforms/Scalar. PR4861Chris Lattner2009-09-021-3/+1
| | | | llvm-svn: 80766
* Make makeLoopInvariant report whether it made any changes or not,Dan Gohman2009-07-151-40/+12
| | | | | | and use this to simplify more code. llvm-svn: 75722
* Tell ScalarEvolution to forget a loop before starting to delete it.Dan Gohman2009-07-081-6/+6
| | | | | | | This way ScalarEvolution can examine the loop to determine what state it needs to update, if it chooses. llvm-svn: 75029
OpenPOWER on IntegriCloud