summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopRotation.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [LoopRotate] Get and update MSSA only if available in legacy pass manager.Alina Sbirlea2020-02-261-5/+6
| | | | | | | | | | | | | | | | | | | | | Summary: Potential fix for: https://bugs.llvm.org/show_bug.cgi?id=44889 and https://bugs.llvm.org/show_bug.cgi?id=44408 In the legacy pass manager, loop rotate need not compute MemorySSA when not being in the same loop pass manager with other loop passes. There isn't currently a way to differentiate between the two cases, so this attempts to limit the usage in LoopRotate to only update MemorySSA when the analysis is already available. The side-effect of this is that it will split the Loop pipeline. This issue does not apply to the new pass manager, where we have a flag specifying if all loop passes in that loop pass manager preserve MemorySSA. Reviewers: dmgreen, fedor.sergeev, nikic Subscribers: Prazek, hiraditya, george.burgess.iv, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D74574 (cherry picked from commit 1326a5a4cfe004181f2ec8231d84ecda2b93cb25)
* Add missing includes needed to prune LLVMContext.h include, NFCReid Kleckner2019-11-141-0/+1
| | | | | These are a pre-requisite to removing #include "llvm/Support/Options.h" from LLVMContext.h: https://reviews.llvm.org/D70280
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [LoopRotate] Unconditionally get DomTree.Florian Hahn2019-10-081-3/+2
| | | | | | | | LoopRotate is a loop pass and the DomTree should always be available. Similar to a70c5261436322a53187d67b8bdc0445d0463a9a llvm-svn: 374036
* [LoopRotate] Unconditionally get ScalarEvolution.Florian Hahn2019-10-081-3/+2
| | | | | | | | | | | | Summary: LoopRotate is a loop pass and SE should always be available. Reviewers: anemet, asbirlea Reviewed By: asbirlea Differential Revision: https://reviews.llvm.org/D68573 llvm-svn: 374026
* [MemorySSA] Loop passes should mark MSSA preserved when available.Alina Sbirlea2019-08-171-1/+1
| | | | | | | | This patch applies only to the new pass manager. Currently, when MSSA Analysis is available, and pass to each loop pass, it will be preserved by that loop pass. Hence, mark the analysis preserved based on that condition, vs the current `EnableMSSALoopDependency`. This leaves the global flag to affect only the entry point in the loop pass manager (in FunctionToLoopPassAdaptor). llvm-svn: 369181
* Only passes that preserve MemorySSA must mark it as preserved.Alina Sbirlea2019-06-111-1/+4
| | | | | | | | | | | | | | | | | | | | Summary: The method `getLoopPassPreservedAnalyses` should not mark MemorySSA as preserved, because it's being called in a lot of passes that do not preserve MemorySSA. Instead, mark the MemorySSA analysis as preserved by each pass that does preserve it. These changes only affect the new pass mananger. Reviewers: chandlerc Subscribers: mehdi_amini, jlebar, Prazek, george.burgess.iv, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D62536 llvm-svn: 363091
* 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
* Update MemorySSA in LoopRotate.Alina Sbirlea2018-10-241-4/+24
| | | | | | | | | | | | Summary: Teach LoopRotate to preserve MemorySSA. Enable tests for correctness, dependency disabled by default. Subscribers: sanjoy, jlebar, Prazek, george.burgess.iv, llvm-commits Differential Revision: https://reviews.llvm.org/D51718 llvm-svn: 345216
* Refine the loop rotation's APIJin Lin2018-04-191-3/+4
| | | | | | | | | | | | | | | | Summary: The following changes addresses the following two issues. 1) The existing loop rotation pass contains both loop latch simplification and loop rotation. So one flag RotationOnly is added to be passed to the loop rotation pass. 2) The threshold value is initialized with MAX_UINT since the loop rotation utility should not have threshold limit. Reviewers: dmgreen, efriedma Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D45582 llvm-svn: 330362
* [LoopRotate] Restructuring LoopRotation.cpp to create Loop Rotation Pass ↵David Green2018-03-291-581/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | with Loop Rotation Utility Interface The existing LoopRotation.cpp is implemented as one of loop passes instead of being a utility. The user cannot easily perform the loop rotation selectively (or on demand) under different optimization level. For example, the loop rotation is needed as part of the logic to convert a loop into a loop with bottom test for a transformation. If the loop rotation is simply added as a loop pass before the transformation, the pass is skipped if it is compiled at –O0 or if it is explicitly disabled by the user, causing the compiler to generate incorrect code. Furthermore, as a loop pass it will rotate all loops instead of just the relevant loops. We provide a utility interface for the loop rotation so that the loop rotation can be called on demand. The changeset is as follows: - Create a new file lib/Transforms/Utils/LoopRotationUtils.cpp and move the main implementation of class LoopRotate into this file. - Create a new file llvm/include/Transform/Utils/LoopRotationUtils.h with the interface LoopRotation(...). - Original LoopRotation.cpp is changed to use the utility function LoopRotation in LoopRotationUtils.cpp. This is done in the same way community did for mem-to-reg implementation. Patch by Jin Lin! Differential Revision: https://reviews.llvm.org/D44595 llvm-svn: 328766
* Fix a couple of layering violations in TransformsDavid Blaikie2018-03-211-1/+1
| | | | | | | | | | | | | Remove #include of Transforms/Scalar.h from Transform/Utils to fix layering. Transforms depends on Transforms/Utils, not the other way around. So remove the header and the "createStripGCRelocatesPass" function declaration (& definition) that is unused and motivated this dependency. Move Transforms/Utils/Local.h into Analysis because it's used by Analysis/MemoryBuiltins.cpp. llvm-svn: 328165
* [Debug] Add a utility to propagate dbg.value to new PHIs, NFCVedant Kumar2018-01-251-33/+1
| | | | | | | | | | This simply moves an existing utility to Utils for reuse. Split out of: https://reviews.llvm.org/D42551 Patch by Matt Davis! llvm-svn: 323471
* [LoopRotate] Detect loops with indirect branches better (we're giving up on ↵Michael Zolotukhin2018-01-091-1/+1
| | | | | | them). llvm-svn: 322137
* [LoopRotate] processLoop should return true even if it just simplified the ↵Craig Topper2017-11-151-1/+1
| | | | | | | | | | | | | | loop latch without making any other changes Simplifying a loop latch changes the IR and we need to make sure the pass manager knows to invalidate analysis passes if that happened. PR35210 discovered a case where we failed to invalidate the post dominator tree after this simplification because we no changes other than simplifying the loop latch. Fixes PR35210. Differential Revision: https://reviews.llvm.org/D40035 llvm-svn: 318237
* loop-rotate: avoid duplicating dbg.value intrinsics in the entry block.Adrian Prantl2017-11-011-0/+24
| | | | | | | | This fixes the second half of PR35113. This reapplies r317106 without modifications. llvm-svn: 317121
* Revert r317106 to facilitate reverting r317105.Adrian Prantl2017-11-011-24/+0
| | | | llvm-svn: 317109
* loop-rotate: avoid duplicating dbg.value intrinsics in the entry block.Adrian Prantl2017-11-011-0/+24
| | | | | | This fixes the second half of PR35113. llvm-svn: 317106
* loop-rotate: simplify code by using llvm::findDbgValues(). (NFC)Adrian Prantl2017-10-311-31/+23
| | | | llvm-svn: 317037
* [LoopRotate][Dominators] Use the incremental API to update DomTreeJakub Kuderski2017-08-171-66/+13
| | | | | | | | | | | | | | Summary: This patch teaches LoopRotate to use the new incremental API to update the DominatorTree. Reviewers: dberlin, davide, grosser, sanjoy Reviewed By: dberlin, davide Subscribers: hiraditya, llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D35581 llvm-svn: 311125
* [LoopRotate] Fix DomTree update logic for unreachable nodes. Fix PR33701.Jakub Kuderski2017-07-121-4/+16
| | | | | | | | | | | | | | | | | | | Summary: LoopRotate manually updates the DoomTree by iterating over all predecessors of a basic block and computing the Nearest Common Dominator. When a predecessor happens to be unreachable, `DT.findNearestCommonDominator` returns nullptr. This patch teaches LoopRotate to handle this case and fixes [[ https://bugs.llvm.org/show_bug.cgi?id=33701 | PR33701 ]]. In the future, LoopRotate should be taught to use the new incremental API for updating the DomTree. Reviewers: dberlin, davide, uabelho, grosser Subscribers: efriedma, mzolotukhin Differential Revision: https://reviews.llvm.org/D35074 llvm-svn: 307828
* [IR] De-virtualize ~Value to save a vptrReid Kleckner2017-05-181-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Implements PR889 Removing the virtual table pointer from Value saves 1% of RSS when doing LTO of llc on Linux. The impact on time was positive, but too noisy to conclusively say that performance improved. Here is a link to the spreadsheet with the original data: https://docs.google.com/spreadsheets/d/1F4FHir0qYnV0MEp2sYYp_BuvnJgWlWPhWOwZ6LbW7W4/edit?usp=sharing This change makes it invalid to directly delete a Value, User, or Instruction pointer. Instead, such code can be rewritten to a null check and a call Value::deleteValue(). Value objects tend to have their lifetimes managed through iplist, so for the most part, this isn't a big deal. However, there are some places where LLVM deletes values, and those places had to be migrated to deleteValue. I have also created llvm::unique_value, which has a custom deleter, so it can be used in place of std::unique_ptr<Value>. I had to add the "DerivedUser" Deleter escape hatch for MemorySSA, which derives from User outside of lib/IR. Code in IR cannot include MemorySSA headers or call the MemoryAccess object destructors without introducing a circular dependency, so we need some level of indirection. Unfortunately, no class derived from User may have any virtual methods, because adding a virtual method would break User::getHungOffOperands(), which assumes that it can find the use list immediately prior to the User object. I've added a static_assert to the appropriate OperandTraits templates to help people avoid this trap. Reviewers: chandlerc, mehdi_amini, pete, dberlin, george.burgess.iv Reviewed By: chandlerc Subscribers: krytarowski, eraman, george.burgess.iv, mzolotukhin, Prazek, nlewycky, hans, inglorion, pcc, tejohnson, dberlin, llvm-commits Differential Revision: https://reviews.llvm.org/D31261 llvm-svn: 303362
* LoopRotate: Fix use after scope bugDaniel Berlin2017-04-281-3/+4
| | | | llvm-svn: 301702
* Kill off the old SimplifyInstruction API by converting remaining users.Daniel Berlin2017-04-281-8/+5
| | | | llvm-svn: 301673
* Fix unused-variable warning caused by r301407.Haojian Wu2017-04-261-2/+0
| | | | llvm-svn: 301411
* Convert LoopRotation to use SimplifyQuery version of SimplifyInstruction. ↵Daniel Berlin2017-04-261-7/+13
| | | | | | Add AssumptionCache, DominatorTree, TLI if available. llvm-svn: 301407
* [LoopRotate] Propagate dbg.value intrinsicsSam Parker2017-03-081-3/+45
| | | | | | | | | | | | Recommitting patch which was previously reverted in r297159. These changes should address the casting issues. The original patch enables dbg.value intrinsics to be attached to newly inserted PHI nodes. Differential Review: https://reviews.llvm.org/D30701 llvm-svn: 297269
* Revert r297132, it caused PR32171Nico Weber2017-03-071-45/+3
| | | | llvm-svn: 297159
* [LoopRotate] Update dbg.value intrinsicsSam Parker2017-03-071-3/+45
| | | | | | | | Propagate debug info through the newly inserted PHI nodes. Differential Revision: https://reviews.llvm.org/D30190 llvm-svn: 297132
* [PM] Introduce an analysis set used to preserve all analyses overChandler Carruth2017-01-151-0/+1
| | | | | | | | | | | | | | | a function's CFG when that CFG is unchanged. This allows transformation passes to simply claim they preserve the CFG and analysis passes to check for the CFG being preserved to remove the fanout of all analyses being listed in all passes. I've gone through and removed or cleaned up as many of the comments reminding us to do this as I could. Differential Revision: https://reviews.llvm.org/D28627 llvm-svn: 292054
* [PM] Separate the LoopAnalysisManager from the LoopPassManager and moveChandler Carruth2017-01-111-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-13/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [PM] Introduce a reasonable port of the main per-module pass pipelineChandler Carruth2016-12-221-2/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | from the old pass manager in the new one. I'm not trying to support (initially) the numerous options that are currently available to customize the pass pipeline. If we end up really wanting them, we can add them later, but I suspect many are no longer interesting. The simplicity of omitting them will help a lot as we sort out what the pipeline should look like in the new PM. I've also documented to the best of my ability *why* each pass or group of passes is used so that reading the pipeline is more helpful. In many cases I think we have some questionable choices of ordering and I've left FIXME comments in place so we know what to come back and revisit going forward. But for now, I've left it as similar to the current pipeline as I could. Lastly, I've had to comment out several places where passes are not ported to the new pass manager or where the loop pass infrastructure is not yet ready. I did at least fix a few bugs in the loop pass infrastructure uncovered by running the full pipeline, but I didn't want to go too far in this patch -- I'll come back and re-enable these as the infrastructure comes online. But I'd like to keep the comments in place because I don't want to lose track of which passes need to be enabled and where they go. One thing that seemed like a significant API improvement was to require that we don't build pipelines for O0. It seems to have no real benefit. I've also switched back to returning pass managers by value as at this API layer it feels much more natural to me for composition. But if others disagree, I'm happy to go back to an output parameter. I'm not 100% happy with the testing strategy currently, but it seems at least OK. I may come back and try to refactor or otherwise improve this in subsequent patches but I wanted to at least get a good starting point in place. Differential Revision: https://reviews.llvm.org/D28042 llvm-svn: 290325
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-8/+18
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Remove the AssumptionCacheHal Finkel2016-12-151-18/+8
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* Preserve assumption cache in loop-rotate.Eli Friedman2016-11-091-0/+4
| | | | | | | | | | | No testcase included because I can't figure out how to reduce it. (It's easy to write a testcase where rotation clones an assume, but that doesn't actually seem to trigger the crash in opt on its own; maybe an issue with the laziness?) Differential Revision: https://reviews.llvm.org/D26434 llvm-svn: 286410
* Replace "fallthrough" comments with LLVM_FALLTHROUGHJustin Bogner2016-08-171-1/+2
| | | | | | | This is a mechanical change of comments in switches like fallthrough, fall-through, or fall-thru to use the LLVM_FALLTHROUGH macro instead. llvm-svn: 278902
* 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
* Give helper classes/functions internal linkage. NFC.Benjamin Kramer2016-07-101-0/+2
| | | | llvm-svn: 275014
* Apply clang-tidy's modernize-loop-convert to most of lib/Transforms.Benjamin Kramer2016-06-261-7/+6
| | | | | | Only minor manual fixes. No functionality change intended. llvm-svn: 273808
* Reinstate r273711David Majnemer2016-06-251-2/+7
| | | | | | | | | | r273711 was reverted by r273743. The inliner needs to know about any call sites in the inlined function. These were obscured if we replaced a call to undef with an undef but kept the call around. This fixes PR28298. llvm-svn: 273753
* Revert r273711, it caused PR28298.Nico Weber2016-06-241-7/+2
| | | | llvm-svn: 273743
* SimplifyInstruction does not imply DCEDavid Majnemer2016-06-241-2/+7
| | | | | | | We cannot remove an instruction with no uses just because SimplifyInstruction succeeds. It may have side effects. llvm-svn: 273711
* LoopRotate: restructure code to simplify functionsSebastian Pop2016-06-141-41/+59
| | | | | | | | | | | | We move the loop rotate functions in a separate class to avoid passing multiple parameters to each function. This cleanup will help with further development of loop rotation. NFC. Patch written by Aditya Kumar and Sebastian Pop. Differential Revision: http://reviews.llvm.org/D21311 llvm-svn: 272672
* Don't try to rotate a loop more than once - we never do this anyway.Michael Zolotukhin2016-06-101-14/+10
| | | | | | | | | | | | | | | | | | | | | Summary: I can't find a case where we can rotate a loop more than once, and it looks like we never do this. To rotate a loop following conditions should be met: 1) its header should be exiting 2) its latch shouldn't be exiting But after the first rotation the header becomes the new latch, so this condition can never be true any longer. Tested on with an assert on LNT testsuite and make check. Reviewers: hfinkel, sanjoy Subscribers: sebpop, sanjoy, llvm-commits, mzolotukhin Differential Revision: http://reviews.llvm.org/D20181 llvm-svn: 272439
* Update Debug Intrinsics in RewriteUsesOfClonedInstructions in LoopRotationChuang-Yu Cheng2016-05-101-0/+34
| | | | | | | | | | | | | | | | | | | | | | Loop rotation clones instruction from the old header into the preheader. If there were uses of values produced by these instructions that were outside the loop, we have to insert PHI nodes to merge the two values. If the values are used by DbgIntrinsics they will be used as a MetadataAsValue of a ValueAsMetadata of the original values, and iterating all of the uses of the original value will not update the DbgIntrinsics. The new code checks if the values are used by DbgIntrinsics and if so, updates them using essentially the same logic as the original code. The attached testcase demonstrates the issue. Without the fix, the DbgIntrinic outside the loop uses values computed inside the loop, even though these values do not dominate the DbgIntrinsic. Author: Thomas Jablin (tjablin) Reviewers: dblaikie aprantl kbarton hfinkel cycheng http://reviews.llvm.org/D19564 llvm-svn: 269034
* PM: Port LoopRotation to the new loop pass managerJustin Bogner2016-05-031-8/+33
| | | | llvm-svn: 268452
* 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
OpenPOWER on IntegriCloud