summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LoopPass.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-1/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
* ftime-trace: Trace loop passesRussell Gallop2019-05-311-0/+3
| | | | | | | | | | These can take a significant amount of time in some builds. Suggested by Andrea Di Biagio. Differential Revision: https://reviews.llvm.org/D62666 llvm-svn: 362219
* [IR] Refactor attribute methods in Function class (NFC)Evandro Menezes2019-04-041-1/+1
| | | | | | | | Rename the functions that query the optimization kind attributes. Differential revision: https://reviews.llvm.org/D60287 llvm-svn: 357731
* [IR] Create new method in `Function` class (NFC)Evandro Menezes2019-04-031-1/+1
| | | | | | | | | Create method `optForNone()` testing for the function level equivalent of `-O0` and refactor appropriately. Differential revision: https://reviews.llvm.org/D59852 llvm-svn: 357638
* Fix IR/Analysis layering issue with OptBisectRichard Trieu2019-02-281-2/+6
| | | | | | | | | | | | | OptBisect is in IR due to LLVMContext using it. However, it uses IR units from Analysis as well. This change moves getDescription functions from OptBisect to their respective IR units. Generating names for IR units will now be up to the callers, keeping the Analysis IR units in Analysis. To prevent unnecessary string generation, isEnabled function is added so that callers know when the description needs to be generated. Differential Revision: https://reviews.llvm.org/D58406 llvm-svn: 355068
* 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
* [LoopPass] fixing 'Modification' messages in -debug-pass=Executions for loop ↵Fedor Sergeev2018-11-191-2/+4
| | | | | | | | | | | | | passes Legacy loop pass manager is issuing "Made Modification" message after each Loop Pass run, however condition for issuing it is accumulated among all the runs. That leads to confusing 'modification' messages as soon as the first modification is done. Changing condition to be "current pass made modifications", similar to how it is being done in all other pass managers. llvm-svn: 347215
* Output per-function size-info remarksJessica Paquette2018-09-061-2/+4
| | | | | | | | | | | This patch adds per-function size information remarks. Previously, passing -Rpass-analysis=size-info would only give you per-module changes. By adding the ability to do this per-function, it's easier to see which functions contributed the most to size changes. https://reviews.llvm.org/D51467 llvm-svn: 341588
* [NFC] Optionally pass a function to emitInstrCountChangedRemarkJessica Paquette2018-08-311-1/+1
| | | | | | | | | In basic block, loop, and function passes, we already have a function that we can use to emit optimization remarks. We can use that instead of searching the module for the first suitable function (that is, one that contains at least one basic block.) llvm-svn: 341253
* [NFC] Pass the instruction delta to emitInstrCountChangedRemarkJessica Paquette2018-08-311-1/+1
| | | | | | | | | | | | | | | Instead of counting the size of the entire module every time we run a pass, pass along a delta instead and use that to emit the remark. This means we only have to use (on average) smaller IR units to calculate instruction counts. E.g, in a BB pass, we only need to look at the delta of the BB instead of the delta of the entire module. 6/6 (This improved compile time for size remarks on sqlite3 + O2 significantly) llvm-svn: 341250
* [NFC] Pre-calculate loop IR counts in size remarks.Jessica Paquette2018-08-311-5/+18
| | | | | | | | | | | | Another commit reducing compile time in size remarks. Cache the size of the module and loop, and update values based off of deltas instead. Avoid recalculating the size of the whole module whenever possible. 3/6 llvm-svn: 341247
* [NFC][PassTiming] factor out generic PassTimingInfoFedor Sergeev2018-08-281-0/+1
| | | | | | | | Moving PassTimingInfo from legacy pass manager code into a separate header. Making it suitable for both legacy and new pass manager. Adding a test on -time-passes main functionality. llvm-svn: 340872
* [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
OpenPOWER on IntegriCloud