summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LoopPass.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Implement getPassName() for IR printing passes.Yaron Keren2017-03-101-0/+2
| | | | llvm-svn: 297442
* Reverted: Track validity of pass resultsSerge Pavlov2017-01-151-1/+0
| | | | | | Commits r291882 and related r291887. llvm-svn: 292062
* Track validity of pass resultsSerge Pavlov2017-01-131-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | Running tests with expensive checks enabled exhibits some problems with verification of pass results. First, the pass verification may require results of analysis that are not available. For instance, verification of loop info requires results of dominator tree analysis. A pass may be marked as conserving loop info but does not need to be dependent on DominatorTreePass. When a pass manager tries to verify that loop info is valid, it needs dominator tree, but corresponding analysis may be already destroyed as no user of it remained. Another case is a pass that is skipped. For instance, entities with linkage available_externally do not need code generation and such passes are skipped for them. In this case result verification must also be skipped. To solve these problems this change introduces a special flag to the Pass structure to mark passes that have valid results. If this flag is reset, verifications dependent on the pass result are skipped. Differential Revision: https://reviews.llvm.org/D27190 llvm-svn: 291882
* [PM] Separate the LoopAnalysisManager from the LoopPassManager and moveChandler Carruth2017-01-111-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | the latter to the Transforms library. While the loop PM uses an analysis to form the IR units, the current plan is to have the PM itself establish and enforce both loop simplified form and LCSSA. This would be a layering violation in the analysis library. Fundamentally, the idea behind the loop PM is to *transform* loops in addition to running passes over them, so it really seemed like the most natural place to sink this was into the transforms library. We can't just move *everything* because we also have loop analyses that rely on a subset of the invariants. So this patch splits the the loop infrastructure into the analysis management that has to be part of the analysis library, and the transform-aware pass manager. This also required splitting the loop analyses' printer passes out to the transforms library, which makes sense to me as running these will transform the code into LCSSA in theory. I haven't split the unittest though because testing one component without the other seems nearly intractable. Differential Revision: https://reviews.llvm.org/D28452 llvm-svn: 291662
* [PM] Rewrite the loop pass manager to use a worklist and augmented runChandler Carruth2017-01-111-5/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | arguments much like the CGSCC pass manager. This is a major redesign following the pattern establish for the CGSCC layer to support updates to the set of loops during the traversal of the loop nest and to support invalidation of analyses. An additional significant burden in the loop PM is that so many passes require access to a large number of function analyses. Manually ensuring these are cached, available, and preserved has been a long-standing burden in LLVM even with the help of the automatic scheduling in the old pass manager. And it made the new pass manager extremely unweildy. With this design, we can package the common analyses up while in a function pass and make them immediately available to all the loop passes. While in some cases this is unnecessary, I think the simplicity afforded is worth it. This does not (yet) address loop simplified form or LCSSA form, but those are the next things on my radar and I have a clear plan for them. While the patch is very large, most of it is either mechanically updating loop passes to the new API or the new testing for the loop PM. The code for it is reasonably compact. I have not yet updated all of the loop passes to correctly leverage the update mechanisms demonstrated in the unittests. I'll do that in follow-up patches along with improved FileCheck tests for those passes that ensure things work in more realistic scenarios. In many cases, there isn't much we can do with these until the loop simplified form and LCSSA form are in place. Differential Revision: https://reviews.llvm.org/D28292 llvm-svn: 291651
* [LCSSA] Perform LCSSA verification only for the current loop nest.Igor Laevsky2016-10-281-0/+14
| | | | | | | | | Now LPPassManager will run LCSSA verification only for the top-level loop which was processed on the current iteration. Differential Revision: https://reviews.llvm.org/D25873 llvm-svn: 285394
* 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
* [LoopPass] Some minor cleanupsDavid Majnemer2016-07-191-7/+5
| | | | | | No functional change is intended. llvm-svn: 275999
* Apply clang-tidy's modernize-loop-convert to lib/Analysis.Benjamin Kramer2016-06-261-3/+1
| | | | | | Only minor manual fixes. No functionality change intended. llvm-svn: 273816
* Fix dynamically linked debug builds.Eli Friedman2016-06-201-0/+1
| | | | | | | | | | On the surface, this might not look like it does anything... but actually it brings in the declaration "extern template class AnalysisManager<Loop>;", which suppresses the instantiation of the constructor, which avoids the funny interaction between "extern template" and -fvisibility-inlines-hidden. llvm-svn: 273133
* [PM] Remove support for omitting the AnalysisManager argument to newChandler Carruth2016-06-171-2/+4
| | | | | | | | | | | | | | | | | | | | pass manager passes' `run` methods. This removes a bunch of SFINAE goop from the pass manager and just requires pass authors to accept `AnalysisManager<IRUnitT> &` as a dead argument. This is a small price to pay for the simplicity of the system as a whole, despite the noise that changing it causes at this stage. This will also helpfull allow us to make the signature of the run methods much more flexible for different kinds af passes to support things like intelligently updating the pass's progression over IR units. While this touches many, many, files, the changes are really boring. Mostly made with the help of my trusty perl one liners. Thanks to Sean and Hal for bouncing ideas for this with me in IRC. llvm-svn: 272978
* Re-commit optimization bisect support (r267022) without new pass manager ↵Andrew Kaylor2016-04-221-4/+10
| | | | | | | | | | 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-10/+4
| | | | | | | | 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-4/+10
| | | | | | | | | | | | 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
* LoopInfo: Simplify ownership of Loop objectsJustin Bogner2016-01-081-11/+10
| | | | | | | | | | | 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
* Recommit r256952 "Filtering IR printing for print-after-all/print-before-all"Weiming Zhao2016-01-061-1/+5
| | | | | | | | Fix lit test fail due to outputting an extra line. Differential Revision: http://reviews.llvm.org/D15776 llvm-svn: 256987
* Revert r256952 due to lit test fails.Weiming Zhao2016-01-061-5/+1
| | | | llvm-svn: 256954
* Filtering IR printing for print-after-all/print-before-allWeiming Zhao2016-01-061-1/+5
| | | | | | | | | | | | | | | Summary: This patch implements "-print-funcs" option to support function filtering for IR printing like -print-after-all, -print-before etc. Examples: -print-after-all -print-funcs=foo,bar Reviewers: mcrosier, joker.eph Subscribers: tejohnson, joker.eph, llvm-commits Differential Revision: http://reviews.llvm.org/D15776 llvm-svn: 256952
* LPM: Make callers of LPM.deleteLoopFromQueue update LoopInfo directly. NFCJustin Bogner2015-12-161-6/+0
| | | | | | | | | | | 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
* LPM: Simplify how passes mark loops for deletion. NFCJustin Bogner2015-12-161-35/+16
| | | | | | | | | | | | | | | | | | | | When a pass removes a loop it currently has to reach up into the LPPassManager's internals to update the state of the iteration over loops. This reverse dependency results in a pretty awkward interplay of the LPPassManager and its Passes. Here, we change this to instead keep track of when a loop has become "unlooped" in the Loop objects themselves, then the LPPassManager can check this and manipulate its own state directly. This opens the door to allow most of the loop passes to work without a backreference to the LPPassManager. I've kept passes calling the LPPassManager::deleteLoopFromQueue API now so I could put an assert in to prove that this is NFC, but a later pass will update passes just to preserve the LoopInfo directly and stop referencing the LPPassManager completely. llvm-svn: 255720
* PM: Rephrase PrintLoopPass as a wrapper around a new-style pass. NFCJustin Bogner2015-11-041-17/+9
| | | | | | | Splits PrintLoopPass into a new-style pass and a PrintLoopPassWrapper, much like we already do for PrintFunctionPass and PrintModulePass. llvm-svn: 252085
* LoopPass: Remove redoLoop, it isn't used. NFCJustin Bogner2015-10-221-13/+0
| | | | | | | | In r251064 I removed a logically unreachable call to `redoLoop`, and now there aren't any callers of this API at all. Remove the needless complexity. llvm-svn: 251067
* LoopPass: Simplify the API for adding a new loop. NFCJustin Bogner2015-10-221-27/+18
| | | | | | | The insertLoop() API is only used to add new loops, and has confusing ownership semantics. Simplify it by replacing it with addLoop(). llvm-svn: 251064
* 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
* Purge unused includes throughout libSupport.Benjamin Kramer2015-03-231-0/+1
| | | | | | NFC. llvm-svn: 232976
* [PM] Split the LoopInfo object apart from the legacy pass, creatingChandler Carruth2015-01-171-3/+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
* Fix assertion in LICM doFinalization()David Peixotto2014-09-241-0/+11
| | | | | | | | | | | | | | | | The doFinalization method checks that the LoopToAliasSetMap is empty. LICM populates that map as it runs through the loop nest, deleting the entries for child loops as it goes. However, if a child loop is deleted by another pass (e.g. unrolling) then the loop will never be deleted from the map because LICM walks the loop nest to find entries it can delete. The fix is to delete the loop from the map and free the alias set when the loop is deleted from the loop nest. Differential Revision: http://reviews.llvm.org/D5305 llvm-svn: 218387
* Add back functionality removed in r210497.Richard Trieu2014-06-211-2/+4
| | | | | | Instead of asserting, output a message stating that a null pointer was found. llvm-svn: 211430
* Removing an "if (!this)" check from two print methods. The condition willRichard Trieu2014-06-091-0/+1
| | | | | | | never be true in a well-defined context. The checking for null pointers has been moved into the caller logic so it does not rely on undefined behavior. llvm-svn: 210497
* Add C API for thread yielding callback.Juergen Ributzka2014-05-161-0/+3
| | | | | | | | | | | | | | | | | | | | | Sometimes a LLVM compilation may take more time then a client would like to wait for. The problem is that it is not possible to safely suspend the LLVM thread from the outside. When the timing is bad it might be possible that the LLVM thread holds a global mutex and this would block any progress in any other thread. This commit adds a new yield callback function that can be registered with a context. LLVM will try to yield by calling this callback function, but there is no guaranteed frequency. LLVM will only do so if it can guarantee that suspending the thread won't block any forward progress in other LLVM contexts in the same process. Once the client receives the call back it can suspend the thread safely and resume it at another time. Related to <rdar://problem/16728690> llvm-svn: 208945
* [Modules] Make Support/Debug.h modular. This requires it to not changeChandler Carruth2014-04-211-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | behavior based on other files defining DEBUG_TYPE, which means it cannot define DEBUG_TYPE at all. This is actually better IMO as it forces folks to define relevant DEBUG_TYPEs for their files. However, it requires all files that currently use DEBUG(...) to define a DEBUG_TYPE if they don't already. I've updated all such files in LLVM and will do the same for other upstream projects. This still leaves one important change in how LLVM uses the DEBUG_TYPE macro going forward: we need to only define the macro *after* header files have been #include-ed. Previously, this wasn't possible because Debug.h required the macro to be pre-defined. This commit removes that. By defining DEBUG_TYPE after the includes two things are fixed: - Header files that need to provide a DEBUG_TYPE for some inline code can do so by defining the macro before their inline code and undef-ing it afterward so the macro does not escape. - We no longer have rampant ODR violations due to including headers with different DEBUG_TYPE definitions. This may be mostly an academic violation today, but with modules these types of violations are easy to check for and potentially very relevant. Where necessary to suppor headers with DEBUG_TYPE, I have moved the definitions below the includes in this commit. I plan to move the rest of the DEBUG_TYPE macros in LLVM in subsequent commits; this one is big enough. The comments in Debug.h, which were hilariously out of date already, have been updated to reflect the recommended practice going forward. llvm-svn: 206822
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-151-2/+2
| | | | | | instead of comparing to nullptr. llvm-svn: 206243
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-2/+2
| | | | | | class. llvm-svn: 202945
* Constify the Optnone checks in IR passes.Paul Robinson2014-02-261-2/+2
| | | | llvm-svn: 202213
* Disable most IR-level transform passes on functions marked 'optnone'.Paul Robinson2014-02-061-0/+14
| | | | | | | | | 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] Rename the IR printing pass header to a more generic and correctChandler Carruth2014-01-121-1/+1
| | | | | | | | name to match the source file which I got earlier. Update the include sites. Also modernize the comments in the header to use the more recommended doxygen style. llvm-svn: 199041
* Move the LLVM IR asm writer header files into the IR directory, as theyChandler Carruth2014-01-071-1/+1
| | | | | | | | | | | | | | | | | are part of the core IR library in order to support dumping and other basic functionality. Rename the 'Assembly' include directory to 'AsmParser' to match the library name and the only functionality left their -- printing has been in the core IR library for quite some time. Update all of the #includes to match. All of this started because I wanted to have the layering in good shape before I started adding support for printing LLVM IR using the new pass infrastructure, and commandline support for the new pass infrastructure. llvm-svn: 198688
* Comment: try to clarify loop iteration order.Andrew Trick2013-07-201-0/+4
| | | | llvm-svn: 186774
* Enable the new LoopInfo algorithm by default.Andrew Trick2012-06-261-3/+7
| | | | | | | | | | | | | | | | | | | | | | | | The primary advantage is that loop optimizations will be applied in a stable order. This helps debugging and unit test creation. It is also a better overall implementation without pathologically bad performance on deep functions. On large functions (llvm-stress --size=200000 | opt -loops) Before: 0.1263s After: 0.0225s On deep functions (after tweaking llvm-stress, thanks Nadav): Before: 0.2281s After: 0.0227s See r158790 for more comments. The loop tree is now consistently generated in forward order, but loop passes are applied in reverse order over the program. If we have a loop optimization that prefers forward order, that can easily be achieved by adding a different type of LoopPassManager. llvm-svn: 159183
* Take out the debug info probe stuff. It's making some changes toEric Christopher2012-03-231-21/+2
| | | | | | | the PassManager annoying and should be reimplemented as a decorator on top of existing passes (as should the timing data). llvm-svn: 153305
* Reapply r138695. Fix PassManager stack depths.Andrew Trick2011-08-291-4/+4
| | | | | | Patch by Xiaoyi Guo! llvm-svn: 138737
* Reverting r138695 to see if it fixes clang self host.Andrew Trick2011-08-271-4/+4
| | | | llvm-svn: 138701
* Fix PassManager stack depths.Andrew Trick2011-08-271-4/+4
| | | | | | Patch by Xiaoyi Guo! llvm-svn: 138695
* Reapplying r136844.Andrew Trick2011-08-101-50/+6
| | | | | | | | | | | | | | | | | | | | An algorithm for incrementally updating LoopInfo within a LoopPassManager. The incremental update should be extremely cheap in most cases and can be used in places where it's not feasible to regenerate the entire loop forest. - "Unloop" is a node in the loop tree whose last backedge has been removed. - Perform reverse dataflow on the block inside Unloop to propagate the nearest loop from the block's successors. - For reducible CFG, each block in unloop is visited exactly once. This is because unloop no longer has a backedge and blocks within subloops don't change parents. - Immediate subloops are summarized by the nearest loop reachable from their exits or exits within nested subloops. - At completion the unloop blocks each have a new parent loop, and each immediate subloop has a new parent. llvm-svn: 137276
* Reverting r136884 updateUnloop, which crashed a linux builder.Andrew Trick2011-08-041-6/+50
| | | | llvm-svn: 136857
* An algorithm for incrementally updating LoopInfo within aAndrew Trick2011-08-031-50/+6
| | | | | | | | | | | | | | | | | | | LoopPassManager. The incremental update should be extremely cheap in most cases and can be used in places where it's not feasible to regenerate the entire loop forest. - "Unloop" is a node in the loop tree whose last backedge has been removed. - Perform reverse dataflow on the block inside Unloop to propagate the nearest loop from the block's successors. - For reducible CFG, each block in unloop is visited exactly once. This is because unloop no longer has a backedge and blocks within subloops don't change parents. - Immediate subloops are summarized by the nearest loop reachable from their exits or exits within nested subloops. - At completion the unloop blocks each have a new parent loop, and each immediate subloop has a new parent. llvm-svn: 136844
* whitespaceAndrew Trick2011-08-031-28/+28
| | | | llvm-svn: 136843
* Introduce DebugInfoProbe. This is used to monitor how llvm optimizer is ↵Devang Patel2011-03-101-2/+21
| | | | | | | | | | | | treating debugging information. It generates output that lools like 8 times line number info lost by Scalar Replacement of Aggregates (SSAUp) 1 times line number info lost by Simplify well-known library calls 12 times variable info lost by Jump Threading llvm-svn: 127381
* zap dead code.Chris Lattner2010-09-041-1/+0
| | | | llvm-svn: 113073
OpenPOWER on IntegriCloud