summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LoopPass.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [ORE] Move loop invariant ORE checks outside the PM loop.Xin Tong2018-07-221-2/+6
| | | | | | | | | | | | | | Summary: This takes 22ms out of ~20s compiling sqlite3.c because we call it for every unit of compilation and every pass. Reviewers: paquette, anemet Subscribers: mehdi_amini, llvm-commits Differential Revision: https://reviews.llvm.org/D49586 llvm-svn: 337654
* [LegacyPM] Fix PR37888 by teaching the legacy loop pass manager how toChandler Carruth2018-06-221-1/+10
| | | | | | | | | | | | | | | | | clear out deleted loops from the current queue beyond just the current loop. This is important because SimpleLoopUnswitch will now enqueue the same loop to be re-processed. When it does this with the legacy PM, we don't have a way of canceling the rest of the pipeline and so we can end up deleting the loop before we reprocess it. =/ This change also makes it easy to support deleting other loops in the queue to process, although I don't have any use cases for that. Differential Revision: https://reviews.llvm.org/D48470 llvm-svn: 335317
* Add remarks describing when a pass changes the IR instruction count of a moduleJessica Paquette2018-05-181-1/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | This patch adds a remark which tells the user when a pass changes the number of IR instructions in a module. It can be enabled by using -Rpass-analysis=size-info. The point of this is to make it easier to collect statistics on how passes modify programs in terms of code size. This is similar in concept to timing reports, but using a remark-based interface makes it easy to diff changes over multiple compilations of the same program. By adding functionality like this, we can see * Which passes impact code size the most * How passes impact code size at different optimization levels * Which pass might have contributed the most to an overall code size regression The patch lives in the legacy pass manager, but since it's simply emitting remarks, it shouldn't be too difficult to adapt the functionality to the new pass manager as well. This can also be adapted to handle MachineInstr counts in code gen passes. https://reviews.llvm.org/D38768 llvm-svn: 332739
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-2/+2
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* [NFC] OptPassGate extracted from OptBisectFedor Sergeev2018-03-271-1/+1
| | | | | | | | | | | | | | | Summary: This is an NFC refactoring of the OptBisect class to split it into an optional pass gate interface used by LLVMContext and the Optional Pass Bisector (OptBisect) used for debugging of optional passes. This refactoring is needed for D44464, which introduces setOptPassGate() method to allow implementations other than OptBisect. Patch by Yevgeny Rouban. Reviewers: andrew.w.kaylor, fedor.sergeev, vsk, dberlin, Eugene.Zelenko, reames, skatkov Reviewed By: fedor.sergeev Differential Revision: https://reviews.llvm.org/D44821 llvm-svn: 328637
* Follow-up for r324429: "[LCSSAVerification] Run verification only when ↵Michael Zolotukhin2018-02-071-1/+5
| | | | | | | | | | | | | asserts are enabled." Before r324429 we essentially didn't have a verification of LCSSA, so no wonder that it has been broken: currently loop-sink breaks it (the attached test illustrates the failure). It was detected during a stage2 RA build, so to unbreak it I'm disabling the check for now. llvm-svn: 324445
* [LCSSAVerification] Run verification only when asserts are enabled.Michael Zolotukhin2018-02-071-1/+3
| | | | llvm-svn: 324429
* [PM/Unswitch] Teach SimpleLoopUnswitch to do non-trivial unswitching,Chandler Carruth2017-11-171-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | making it no longer even remotely simple. The pass will now be more of a "full loop unswitching" pass rather than anything substantively simpler than any other approach. I plan to rename it accordingly once the dust settles. The key ideas of the new loop unswitcher are carried over for non-trivial unswitching: 1) Fully unswitch a branch or switch instruction from inside of a loop to outside of it. 2) Update the CFG and IR. This avoids needing to "remember" the unswitched branches as well as avoiding excessively cloning and reliance on complex parts of simplify-cfg to cleanup the cfg. 3) Update the analyses (where we can) rather than just blowing them away or relying on something else updating them. Sadly, #3 is somewhat compromised here as the dominator tree updates were too complex for me to want to reason about. I will need to make another attempt to do this now that we have a nice dynamic update API for dominators. However, we do adhere to #3 w.r.t. LoopInfo. This approach also adds an important principls specific to non-trivial unswitching: not *all* of the loop will be duplicated when unswitching. This fact allows us to compute the cost in terms of how much *duplicate* code is inserted rather than just on raw size. Unswitching conditions which essentialy partition loops will work regardless of the total loop size. Some remaining issues that I will be addressing in subsequent commits: - Handling unstructured control flow. - Unswitching 'switch' cases instead of just branches. - Moving to the dynamic update API for dominators. Some high-level, interesting limitationsV that folks might want to push on as follow-ups but that I don't have any immediate plans around: - We could be much more clever about not cloning things that will be deleted. In fact, we should be able to delete *nothing* and do a minimal number of clones. - There are many more interesting selection criteria for which branch to unswitch that we might want to look at. One that I'm interested in particularly are a set of conditions which all exit the loop and which can be merged into a single unswitched test of them. Differential revision: https://reviews.llvm.org/D34200 llvm-svn: 318549
* Use a BumpPtrAllocator for Loop objectsSanjoy Das2017-09-281-9/+17
| | | | | | | | | | | | | | | Summary: And now that we no longer have to explicitly free() the Loop instances, we can (with more ease) use the destructor of LoopBase to do what LoopBase::clear() was doing. Reviewers: chandlerc Subscribers: mehdi_amini, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D38201 llvm-svn: 314375
* Tighten the invariants around LoopBase::invalidateSanjoy Das2017-09-201-3/+1
| | | | | | | | | | | | | | | | | Summary: With this change: - Methods in LoopBase trip an assert if the receiver has been invalidated - LoopBase::clear frees up the memory held the LoopBase instance This change also shuffles things around as necessary to work with this stricter invariant. Reviewers: chandlerc Subscribers: mehdi_amini, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D38055 llvm-svn: 313708
* [LegacyPM] Make the 'addLoop' method accept a loop to add rather thanChandler Carruth2017-05-251-15/+8
| | | | | | | | | | | | | | having it internally allocate the loop. This is a much more flexible API and necessary in the new loop unswitch to reasonably support both new and old PMs in common code. It also just seems like a cleaner separation of concerns. NFC, this should just be a pure refactoring. Differential Revision: https://reviews.llvm.org/D33528 llvm-svn: 303834
* 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
OpenPOWER on IntegriCloud