summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LICM.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Fix a bunch of typoes. NFCFangrui Song2018-03-301-1/+1
| | | | llvm-svn: 328907
* Fix a block copying problem in LICMAndrew Kaylor2018-03-231-2/+8
| | | | | | Differential Revision: https://reviews.llvm.org/D44817 llvm-svn: 328336
* 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
* [LICM] Salvage DI from dying InstructionsAnastasis Grammenos2018-03-181-0/+1
| | | | | | | LICM deletes trivially dead instructions which it won't attempt to sink. Attempt to salvage debug values which reference these instructions. llvm-svn: 327800
* Test Commit NFC. Updated commentAnna Thomas2018-03-131-1/+1
| | | | llvm-svn: 327436
* Move llvm::computeLoopSafetyInfo from LICM.cpp to LoopUtils.cpp. NFCDavid Green2018-02-141-37/+0
| | | | | | | | | Move computeLoopSafetyInfo, defined in Transforms/Utils/LoopUtils.h, into the corresponding LoopUtils.cpp, as opposed to LICM where it resides at the moment. This will allow other functions from Transforms/Utils to reference it. llvm-svn: 325151
* [LICM] update BlockColors after splitting predecessorsJun Bum Lim2018-02-121-8/+23
| | | | | | | | | | Update BlockColors after splitting predecessors. Do not allow splitting EHPad for sinking when the BlockColors is not empty, so we can simply assign predecessor's color to the new block. Fixes PR36184 llvm-svn: 324916
* Re-commit : [LICM] Allow sinking when foldable in loopJun Bum Lim2017-12-151-29/+79
| | | | | | | | | | | | | | | | | | | | | | This recommits r320823 reverted due to the test failure in sink-foldable.ll and an unused variable. Added "REQUIRES: aarch64-registered-target" in the test and removed unused variable. Original commit message: Continue trying to sink an instruction if its users in the loop is foldable. This will allow the instruction to be folded in the loop by decoupling it from the user outside of the loop. Reviewers: hfinkel, majnemer, davidxl, efriedma, danielcdh, bmakam, mcrosier Reviewed By: hfinkel Subscribers: javed.absar, bmakam, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D37076 llvm-svn: 320858
* Revert "Re-commit : [LICM] Allow sinking when foldable in loop"Jun Bum Lim2017-12-151-78/+29
| | | | | | This reverts commit r320833. llvm-svn: 320836
* Re-commit : [LICM] Allow sinking when foldable in loopJun Bum Lim2017-12-151-29/+78
| | | | | | | | | | | | | | | | | | | | This recommit r320823 after fixing a test failure. Original commit message: Continue trying to sink an instruction if its users in the loop is foldable. This will allow the instruction to be folded in the loop by decoupling it from the user outside of the loop. Reviewers: hfinkel, majnemer, davidxl, efriedma, danielcdh, bmakam, mcrosier Reviewed By: hfinkel Subscribers: javed.absar, bmakam, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D37076 llvm-svn: 320833
* Revert "[LICM] Allow sinking when foldable in loop"Jun Bum Lim2017-12-151-78/+29
| | | | | | This reverts commit r320823. llvm-svn: 320828
* [LICM] Allow sinking when foldable in loopJun Bum Lim2017-12-151-29/+78
| | | | | | | | | | | | | | | | | Summary: Continue trying to sink an instruction if its users in the loop is foldable. This will allow the instruction to be folded in the loop by decoupling it from the user outside of the loop. Reviewers: hfinkel, majnemer, davidxl, efriedma, danielcdh, bmakam, mcrosier Reviewed By: hfinkel Subscribers: javed.absar, bmakam, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D37076 llvm-svn: 320823
* Add MemorySSA as loop dependency, disabled by default [NFC].Alina Sbirlea2017-11-211-4/+12
| | | | | | | | | | | | | | | | | Summary: First step in adding MemorySSA as dependency for loop pass manager. Adding the dependency under a flag. New pass manager: MSSA pointer in LoopStandardAnalysisResults can be null. Legacy and new pass manager: Use cl::opt EnableMSSALoopDependency. Disabled by default. Reviewers: sanjoy, davide, gberry Subscribers: mehdi_amini, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D40274 llvm-svn: 318772
* [LICM] Fix PR35342Jun Bum Lim2017-11-171-1/+1
| | | | | | | | | | | | | | Summary: This change fix PR35342 by replacing only the current use with undef in unreachable blocks. Reviewers: efriedma, mcrosier, igor-laevsky Reviewed By: efriedma Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D40184 llvm-svn: 318551
* [LICM] sink through non-trivially replicable PHIJun Bum Lim2017-11-031-56/+140
| | | | | | | | | | | | | | | | | | | Summary: The current LICM allows sinking an instruction only when it is exposed to exit blocks through a trivially replacable PHI of which all incoming values are the same instruction. This change enhance LICM to sink a sinkable instruction through non-trivially replacable PHIs by spliting predecessors of loop exits. Reviewers: hfinkel, majnemer, davidxl, bmakam, mcrosier, danielcdh, efriedma, jtony Reviewed By: efriedma Subscribers: nemanjai, dberlin, llvm-commits Differential Revision: https://reviews.llvm.org/D37163 llvm-svn: 317335
* [LICM] Restructure implicit exit handling to be more clear [NFCI]Philip Reames2017-10-261-27/+34
| | | | | | When going to explain this to someone else, I got tripped up by the complicated meaning of IsKnownNonEscapingObject in load-store promotion. Extract a helper routine and clarify naming/scopes to make this a bit more obvious. llvm-svn: 316699
* [NFC] Convert OptimizationRemarkEmitter old emit() calls to new closureVivek Pandya2017-10-111-15/+25
| | | | | | | | | | | | | | parameterized emit() calls Summary: This is not functional change to adopt new emit() API added in r313691. Reviewed By: anemet Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D38285 llvm-svn: 315476
* [LICM] Disallow sinking of unordered atomic loads into loopsMax Kazantsev2017-10-111-4/+10
| | | | | | | | | | | | | | | | | | | | | | | | Sinking of unordered atomic load into loop must be disallowed because it turns a single load into multiple loads. The relevant section of the documentation is: http://llvm.org/docs/Atomics.html#unordered, specifically the Notes for Optimizers section. Here is the full text of this section: > Notes for optimizers > In terms of the optimizer, this **prohibits any transformation that > transforms a single load into multiple loads**, transforms a store into > multiple stores, narrows a store, or stores a value which would not be > stored otherwise. Some examples of unsafe optimizations are narrowing > an assignment into a bitfield, rematerializing a load, and turning loads > and stores into a memcpy call. Reordering unordered operations is safe, > though, and optimizers should take advantage of that because unordered > operations are common in languages that need them. Patch by Daniil Suchkov! Reviewed By: reames Differential Revision: https://reviews.llvm.org/D38392 llvm-svn: 315438
* Rename OptimizationDiagnosticInfo.* to OptimizationRemarkEmitter.*Adam Nemet2017-10-091-1/+1
| | | | | | | Sync it up with the name of the class actually defined here. This has been bothering me for a while... llvm-svn: 315249
* Refactor collectChildrenInLoop to LoopUtils [NFC]Alina Sbirlea2017-09-151-23/+0
| | | | | | | | | | | | Summary: Move to LoopUtils method that collects all children of a node inside a loop. Reviewers: majnemer, sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D37870 llvm-svn: 313322
* Make promoteLoopAccessesToScalars independent of AliasSet [NFC]Alina Sbirlea2017-09-121-47/+52
| | | | | | | | | | | | | | | | | | | | | | | Summary: The current promoteLoopAccessesToScalars method receives an AliasSet, but the information used is in fact a list of Value*, known to must alias. Create the list ahead of time to make this method independent of the AliasSet class. While there is no functionality change, this adds overhead for creating a set of Value*, when promotion would normally exit earlier. This is meant to be as a first refactoring step in order to start replacing AliasSetTracker with MemorySSA. And while the end goal is to redesign LICM, the first few steps will focus on adding MemorySSA as an alternative to the AliasSetTracker using most of the existing functionality. Reviewers: mkuper, danielcdh, dberlin Subscribers: sanjoy, chandlerc, gberry, davide, llvm-commits Differential Revision: https://reviews.llvm.org/D35439 llvm-svn: 313075
* [LICM] Make sinkRegion and hoistRegion non-recursiveDavid Majnemer2017-07-201-96/+113
| | | | | | | | | | | | Large CFGs can cause us to blow up the stack because we would have a recursive step for each basic block in a region. Instead, create a worklist and iterate it. This limits the stack usage to something more manageable. Differential Revision: https://reviews.llvm.org/D35609 llvm-svn: 308582
* [IR] Prefer use_empty() to !hasNUsesOrMore(1) for clarity.Davide Italiano2017-05-161-1/+1
| | | | llvm-svn: 303218
* Revert "Compute safety information in a much finer granularity."Evgeniy Stepanov2017-04-241-11/+21
| | | | | | Use-after-free in llvm::isGuaranteedToExecute. llvm-svn: 301214
* Compute safety information in a much finer granularity.Xin Tong2017-04-241-21/+11
| | | | | | | | | | | | | | | | | | | Summary: Instead of keeping a variable indicating whether there are early exits in the loop. We keep all the early exits. This improves LICM's ability to move instructions out of the loop based on is-guaranteed-to-execute. I am going to update compilation time as well soon. Reviewers: hfinkel, sanjoy, efriedma, mkuper Reviewed By: hfinkel Subscribers: llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D32433 llvm-svn: 301196
* [LICM] Hoist fp division from the loops and replace by a reciprocalHal Finkel2017-04-111-0/+23
| | | | | | | | | | | When allowed, we can hoist a division out of a loop in favor of a multiplication by the reciprocal. Fixes PR32157. Patch by vit9696! Differential Revision: https://reviews.llvm.org/D30819 llvm-svn: 299911
* Make default value for disable-licm-promotion in licm explicit.Xin Tong2017-02-211-1/+2
| | | | llvm-svn: 295767
* Correct a typo, s/hosting/hoisting/Brian Cain2017-02-141-1/+1
| | | | llvm-svn: 295066
* [LICM] Make store promotion work in the face of unordered atomicsPhilip Reames2017-02-141-5/+27
| | | | | | | | | | | | | | | | | | | | | | | Extend our store promotion code to deal with unordered atomic accesses. Ordered atomics continue to be unhandled. Most of the change is straight-forward, the only complicated bit is in the reasoning around mixing of atomic and non-atomic memory access. Rather than trying to reason about the complex semantics in these cases, I simply disallowed promotion when both atomic and non-atomic accesses are present. This is conservatively correct. It seems really tempting to just promote all access to atomics, but the original accesses might have been conditional. Since we can't lower an arbitrary atomic type, it might not be safe to promote all access to atomic. Consider a loop like the following: while(b) { load i128 ... if (can lower i128 atomic) store atomic i128 ... else store i128 } It could be there's no race on the location and thus the code is perfectly well defined even if we can't lower a i128 atomically. It's not clear we need to be this conservative - arguably the program above is brocken since it can't be lowered unless the branch is folded - but I didn't want to have to fix any fallout which might result. Differential Revision: https://reviews.llvm.org/D15592 llvm-svn: 295015
* [LICM] Hoist loads that are dominated by invariant.start intrinsic, and are ↵Anna Thomas2017-02-021-0/+62
| | | | | | | | | | | | | | | | | | invariant in the loop. Summary: We can hoist out loads that are dominated by invariant.start, to the preheader. We conservatively assume the load is variant, if we see a corresponding use of invariant.start (it could be an invariant.end or an escaping call). Reviewers: mkuper, sanjoy, reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29331 llvm-svn: 293887
* [LICM] When we are recomputing the alias sets for a subloop, we cannotChandler Carruth2017-01-271-3/+0
| | | | | | | | | | | | | | | | | | | | | | | skip sub-subloops. The logic to skip subloops dated from when this code was shared with the cached case. Once it was factored out to only run in the case of recomputed subloops it became a dangerous bug. If a subsubloop contained an interfering instruction it would be silently skipped from the alias sets for LICM. With the old pass manager this was extremely hard to trigger as it would require failing to visit these subloops with the LICM pass but then visiting the outer loop somehow. I've not yet contrived any test case that actually manages to trigger this. But with the new pass manager we don't do the cross-loop caching hack that the old PM does and so we recompute alias set information from first principles. While this seems much cleaner and simpler it exposed this bug and would subtly miscompile code due to failing to correctly model the aliasing constraints of deeply nested loops. llvm-svn: 293273
* Improve what can be promoted in LICM.Xin Tong2017-01-191-6/+31
| | | | | | | | | | | | | | | | Summary: In case of non-alloca pointers, we check for whether it is a pointer from malloc-like calls and it is not captured. In such case, we can promote the pointer, as the caller will have no way to access this pointer even if there is unwinding in middle of the loop. Reviewers: hfinkel, sanjoy, reames, eli.friedman Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28834 llvm-svn: 292510
* Skip loop header while we can when computing loop safety infoXin Tong2017-01-181-1/+4
| | | | llvm-svn: 292310
* [PM] Introduce an analysis set used to preserve all analyses overChandler Carruth2017-01-151-3/+3
| | | | | | | | | | | | | | | 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-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-11/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [LICM] Report failing to hoist conditionally-executed loadsAdam Nemet2017-01-111-6/+20
| | | | | | | | | | | | These are interesting again because the user may not be aware that this is a common reason preventing LICM. A const is removed from an instruction pointer declaration in order to pass it to ORE. Differential Revision: https://reviews.llvm.org/D27940 llvm-svn: 291649
* [LICM] Report failing to hoist a load with an invariant addressAdam Nemet2017-01-111-4/+15
| | | | | | | | | | | | | | | | | These are interesting because lack of precision in alias information could be standing in the way of this optimization. An example is the case in the test suite that I showed in the DevMeeting talk: http://lab.llvm.org:8080/artifacts/opt-view_test-suite/build/MultiSource/Benchmarks/FreeBench/distray/CMakeFiles/distray.dir/html/_org_test-suite_MultiSource_Benchmarks_FreeBench_distray_distray.c.html#L236 canSinkOrHoistInst is also used from LoopSink, which does not use opt-remarks so we need to take ORE as an optional argument. Differential Revision: https://reviews.llvm.org/D27939 llvm-svn: 291648
* [LICM] Report successful hoist/sink/promotionAdam Nemet2017-01-111-19/+45
| | | | | | Differential Revision: https://reviews.llvm.org/D27938 llvm-svn: 291646
* [DWARF] Null out the debug locs of (loop invariant) instructions hoisted by ↵Wolfgang Pieb2017-01-061-0/+8
| | | | | | | | | | LICM in order to avoid jumpy line tables. Calls are left alone because they may be inlined. Differential Revision: https://reviews.llvm.org/D28390 llvm-svn: 291258
* [LICM] Allow promotion of some stores that are not guaranteed to execute.Michael Kuperstein2017-01-051-4/+24
| | | | | | | | | | | | | Promotion is always legal when a store within the loop is guaranteed to execute. However, this is not a necessary condition - for promotion to be memory model semantics-preserving, it is enough to have a store that dominates every exit block. This is because if the store dominates every exit block, the fact the exit block was executed implies the original store was executed as well. Differential Revision: https://reviews.llvm.org/D28147 llvm-svn: 291171
* [LICM] Small update to note changes made in hoistRegionAndrew Kaylor2017-01-051-0/+1
| | | | | | Differential Revision: https://reviews.llvm.org/D28363 llvm-svn: 291157
* [LICM] When promoting scalars, allow inserting stores to thread-local allocas.Michael Kuperstein2016-12-301-1/+2
| | | | | | | | | This is similar to the allocfn case - if an alloca is not captured, then it's necessarily thread-local. Differential Revision: https://reviews.llvm.org/D28170 llvm-svn: 290738
* [LICM] Remove unneeded tracking of whether changes were made. NFC.Michael Kuperstein2016-12-301-9/+7
| | | | | | | | "Changed" doesn't actually change within the loop, so there's no reason to keep track of it - we always return false during analysis and true after the transformation is made. llvm-svn: 290735
* [LICM] Make logic in promoteLoopAccessesToScalars easier to follow. NFC.Michael Kuperstein2016-12-301-40/+47
| | | | llvm-svn: 290734
* [LICM] Compute exit blocks for promotion eagerly. NFC.Michael Kuperstein2016-12-291-35/+36
| | | | | | | | | | | This moves the exit block and insertion point computation to be eager, instead of after seeing the first scalar we can promote. The cost is relatively small (the computation happens anyway, see discussion on D28147), and the code is easier to follow, and can bail out earlier if there's a catchswitch present. llvm-svn: 290729
* [LICM] Don't try to promote in loops where we have no chance to promote. NFC.Michael Kuperstein2016-12-291-10/+6
| | | | | | | | | | We would check whether we have a prehader *or* dedicated exit blocks, and go into the promotion loop. Then, for each alias set we'd check if we have a preheader *and* dedicated exit blocks, and bail if not. Instead, bail immediately if we don't have both. llvm-svn: 290728
* [LICM] Only recompute LCSSA when we actually promoted something.Michael Kuperstein2016-12-291-3/+6
| | | | | | | | | | | | We want to recompute LCSSA only when we actually promoted a value. This means we only need to look at changes made by promotion when deciding whether to recompute it or not, not at regular sinking/hoisting. (This was what the code was documented as doing, just not what it did) Hopefully NFC. llvm-svn: 290726
* [LICM] Plug a leak freeing the ASTs before clearing the map.Davide Italiano2016-12-231-0/+2
| | | | llvm-svn: 290433
* [LICM] Work around LICM needs to maintain state across loops.Davide Italiano2016-12-231-1/+6
| | | | | | | | | | | | | | | The pass creates some state which expects to be cleaned up by a later instance of the same pass. opt-bisect happens to expose this not ideal design because calling skipLoop() will result in this state not being cleaned up at times and an assertion firing in `doFinalization()`. Chandler tells me the new pass manager will give us options to avoid these design traps, but until it's not ready, we need a workaround for the current pass infrastructure. Fix provided by Andy Kaylor, see the review for a complete discussion. Differential Revision: https://reviews.llvm.org/D25848 llvm-svn: 290427
OpenPOWER on IntegriCloud