summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-8/+8
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* [LegacyPM] Make the 'addLoop' method accept a loop to add rather thanChandler Carruth2017-05-251-1/+6
| | | | | | | | | | | | | | 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
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-05-011-2/+3
| | | | | | This relands r301424. llvm-svn: 301812
* [LoopUnswitch] Make DEBUG output more readable (part 2).Davide Italiano2017-04-291-1/+1
| | | | | | | | | I fixed my miscompile in r301722 and I hope I don't have to take a look at this code again now that Chandler has a new LoopUnswitch pass, but maybe this could be of use for somebody else in the meanwhile. llvm-svn: 301723
* [LoopUnswitch] Don't remove instructions with side effects.Davide Italiano2017-04-291-1/+2
| | | | | | | | This fixes PR32818. Differential Revision: https://reviews.llvm.org/D32664 llvm-svn: 301722
* [LoopUnswitch] Make DEBUG output more readable.Davide Italiano2017-04-281-1/+1
| | | | | | | | | While debugging a miscompile I realized loopunswitch doesn't put newlines when printing the instruction being replacement. Ending up with a single line with many instruction replaced isn't the best for readability and/or mental sanity. llvm-svn: 301692
* Reverts commit r301424, r301425 and r301426Sanjoy Das2017-04-261-5/+5
| | | | | | | | | | | | Commits were: "Use WeakVH instead of WeakTrackingVH in AliasSetTracker's UnkownInsts" "Add a new WeakVH value handle; NFC" "Rename WeakVH to WeakTrackingVH; NFC" The changes assumed pointers are 8 byte aligned on all architectures. llvm-svn: 301429
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-04-261-5/+5
| | | | | | | | | | | | | | | | Summary: I plan to use WeakVH to mean "nulls itself out on deletion, but does not track RAUW" in a subsequent commit. Reviewers: dblaikie, davide Reviewed By: davide Subscribers: arsenm, mehdi_amini, mcrosier, mzolotukhin, jfb, llvm-commits, nhaehnle Differential Revision: https://reviews.llvm.org/D32266 llvm-svn: 301424
* Correct grammar. NFCXin Tong2017-04-231-1/+1
| | | | llvm-svn: 301135
* [IR] Redesign the case iterator in SwitchInst to actually be an iteratorChandler Carruth2017-04-121-11/+11
| | | | | | | | | | | | | | | | and to expose a handle to represent the actual case rather than having the iterator return a reference to itself. All of this allows the iterator to be used with common STL facilities, standard algorithms, etc. Doing this exposed some missing facilities in the iterator facade that I've fixed and required some work to the actual iterator to fully support the necessary API. Differential Revision: https://reviews.llvm.org/D31548 llvm-svn: 300032
* Only unswitch loops with uniform conditionsStanislav Mekhanoshin2017-03-171-4/+19
| | | | | | | | | | | | | | | | | | Loop unswitching can be extremely harmful for a SIMT target. In case if hoisted condition is not uniform a SIMT machine will execute both clones of a loop sequentially. Therefor LoopUnswitch checks if the condition is non-divergent. Since DivergenceAnalysis adds an expensive PostDominatorTree analysis not needed for non-SIMT targets a new option is added to avoid unneded analysis initialization. The method getAnalysisUsage is called when TargetTransformInfo is not yet available and we cannot use it here. For that reason a new field DivergentTarget is added to PassManagerBuilder to control the behavior and set this field from a target. Differential Revision: https://reviews.llvm.org/D30796 llvm-svn: 298104
* [LoopUnswitch] Common pushing LIC's user to worklist.Xin Tong2017-02-281-4/+2
| | | | llvm-svn: 296432
* Fix a bug when unswitching on partial LIV for SwitchInstXin Tong2017-02-271-32/+128
| | | | | | | | | | | | | | Summary: Fix a bug when unswitching on partial LIV for SwitchInst. Reviewers: hfinkel, efriedma, sanjoy Reviewed By: sanjoy Subscribers: david2050, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D29107 llvm-svn: 296363
* Fix an iterator invalidation bug when simplifying LIC user.Xin Tong2017-02-241-1/+7
| | | | | | | | LoopUnswitch/simplify-with-nonvalness.ll is the test case for this. The LIC has 2 users and deleting the 1st user when it can be simplified invalidated the iterator for the 2nd user. llvm-svn: 296069
* LoopUnswitch - Simplify based on known not to a be constant.Xin Tong2017-02-231-3/+44
| | | | | | | | | | | | | | Summary: In case we do not know what the condition is in an unswitched loop, but we know its definitely NOT a known constant. We can perform simplifcations based on this information. Reviewers: sanjoy, hfinkel, chenli, efriedma Reviewed By: efriedma Subscribers: david2050, llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D28968 llvm-svn: 296041
* Test commit permissionKarl-Johan Karlsson2017-02-141-1/+1
| | | | | | Removing whitespace. llvm-svn: 295037
* [LoopUnswitch] Remove BFI usage (dead code)Philip Reames2017-02-101-43/+0
| | | | | | | | Chandler mentioned at the last social that the need for BFI in the new pass manager was causing a slight hiccup for this pass. Given this code has been checked in, but off for over a year, it makes sense to just remove it for now. Note that there's nothing wrong with the general idea - it's actually a quite good one - and once we have the infrastructure in place to implement this without the full recompuation on every loop, we absolutely should. llvm-svn: 294715
* Constant fold switch inst when looking for trivial conditions to unswitch on.Xin Tong2017-01-271-2/+10
| | | | | | | | | | | | Summary: Constant fold switch inst when looking for trivial conditions to unswitch on. Reviewers: sanjoy, chenli, hfinkel, efriedma Subscribers: llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D29037 llvm-svn: 293250
* Fix use after freeXin Tong2017-01-061-1/+1
| | | | | | | | | | | | Summary: Fix use after free in LoopUnswitch Reviewers: chenli, atrick, hfinkel, mzolotukhin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28412 llvm-svn: 291288
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-7/+20
| | | | | | | 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-20/+7
| | | | | | | | | 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
* [Loop Unswitch] Patch to selective unswitch only the reachable branch ↵Abhilash Bhandari2016-11-251-1/+36
| | | | | | | | | | | | | | | | instructions. Summary: The iterative algorithm for Loop Unswitching may render some of the branches unreachable in the unswitched loops. Given the exponential nature of the algorithm, this is quite an overhead. This patch fixes this problem by selectively unswitching only those branches within a loop that are reachable from the loop header. Reviewers: Michael Zolothukin, Anna Thomas, Weiming Zhao. Subscribers: llvm-commits. Differential Revision: http://reviews.llvm.org/D26299 llvm-svn: 287925
* Cleanup : Use metadata preserving API for branch creationXinliang David Li2016-09-031-9/+4
| | | | | | | Use the wrapper API in IRBuilder that does meta data copy to create new branch in LoopUnswitch. llvm-svn: 280602
* Possible fix of test failures on win bots Xinliang David Li2016-08-231-3/+3
| | | | llvm-svn: 279542
* [Profile] refactor meta data copying/swapping codeXinliang David Li2016-08-231-37/+8
| | | | | | Differential Revision: http://reviews.llvm.org/D23619 llvm-svn: 279523
* Replace "fallthrough" comments with LLVM_FALLTHROUGHJustin Bogner2016-08-171-1/+1
| | | | | | | 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
* Preserve the assumption cache more oftenDavid Majnemer2016-08-161-6/+7
| | | | | | | We were clearing it out in LoopUnswitch and InlineFunction instead of attempting to preserve it. llvm-svn: 278860
* Apply clang-tidy's modernize-loop-convert to most of lib/Transforms.Benjamin Kramer2016-06-261-10/+8
| | | | | | Only minor manual fixes. No functionality change intended. llvm-svn: 273808
* [LoopUnswitch] Unswitch on conditions feeding into guardsSanjoy Das2016-06-261-7/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This is a straightforward extension of what LoopUnswitch does to branches to guards. That is, we unswitch ``` for (;;) { ... guard(loop_invariant_cond); ... } ``` into ``` if (loop_invariant_cond) { for (;;) { ... // There is no need to emit guard(true) ... } } else { for (;;) { ... guard(false); // SimplifyCFG will clean this up by adding an // unreachable after the guard(false) ... } } ``` Reviewers: majnemer Subscribers: mcrosier, llvm-commits, mzolotukhin Differential Revision: http://reviews.llvm.org/D21725 llvm-svn: 273801
* [LoopUnswitch] Avoid exponential behaviorSanjoy Das2016-06-251-4/+22
| | | | | | | | | | | | Summary: (No semantic change intended). Reviewers: majnemer, bogner, mzolotukhin Subscribers: mcrosier, llvm-commits, mzolotukhin Differential Revision: http://reviews.llvm.org/D21707 llvm-svn: 273763
* Disable MSan-hostile loop unswitching.Evgeniy Stepanov2016-06-101-0/+18
| | | | | | | | | | | | | Loop unswitching may cause MSan false positive when the unswitch condition is not guaranteed to execute. This is very similar to ASan and TSan special case in llvm::isSafeToSpeculativelyExecute (they don't like speculative loads and stores), but for branch instructions. This is a workaround for PR28054. llvm-svn: 272421
* [LoopUnroll] Unroll loops which have exit blocks to EH padsDavid Majnemer2016-05-031-0/+5
| | | | | | | | | | | | | We were overly cautious in our analysis of loops which have invokes which unwind to EH pads. The loop unroll transform is safe because it only clones blocks in the loop body, it does not try to split critical edges involving EH pads. Instead, move the necessary safety check to LoopUnswitch. N.B. The safety check for loop unswitch is covered by an existing test which fails without it. llvm-svn: 268357
* 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
* IR: RF_IgnoreMissingValues => RF_IgnoreMissingLocals, NFCDuncan P. N. Exon Smith2016-04-071-1/+1
| | | | | | | | | | | | | | | | | | | | | | | Clarify what this RemapFlag actually means. - Change the flag name to match its intended behaviour. - Clearly document that it's not supposed to affect globals. - Add a host of FIXMEs to indicate how to fix the behaviour to match the intent of the flag. RF_IgnoreMissingLocals should only affect the behaviour of RemapInstruction for function-local operands; namely, for operands of type Argument, Instruction, and BasicBlock. Currently, it is *only* passed into RemapInstruction calls (and the transitive MapValue calls that it makes). When I split Metadata from Value I didn't understand the flag, and I used it in a bunch of places for "global" metadata. This commit doesn't have any functionality change, but prepares to cleanup MapMetadata and MapValue. llvm-svn: 265628
* [LPM] Factor all of the loop analysis usage updates into a common helperChandler Carruth2016-02-191-14/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | routine. We were getting this wrong in small ways and generally being very inconsistent about it across loop passes. Instead, let's have a common place where we do this. One minor downside is that this will require some analyses like SCEV in more places than they are strictly needed. However, this seems benign as these analyses are complete no-ops, and without this consistency we can in many cases end up with the legacy pass manager scheduling deciding to split up a loop pass pipeline in order to run the function analysis half-way through. It is very, very annoying to fix these without just being very pedantic across the board. The only loop passes I've not updated here are ones that use AU.setPreservesAll() such as IVUsers (an analysis) and the pass printer. They seemed less relevant. With this patch, almost all of the problems in PR24804 around loop pass pipelines are fixed. The one remaining issue is that we run simplify-cfg and instcombine in the middle of the loop pass pipeline. We've recently added some loop variants of these passes that would seem substantially cleaner to use, but this at least gets us much closer to the previous state. Notably, the seven loop pass managers is down to three. I've not updated the loop passes using LoopAccessAnalysis because that analysis hasn't been fully wired into LoopSimplify/LCSSA, and it isn't clear that those transforms want to support those forms anyways. They all run late anyways, so this is harmless. Similarly, LSR is left alone because it already carefully manages its forms and doesn't need to get fused into a single loop pass manager with a bunch of other loop passes. LoopReroll didn't use loop simplified form previously, and I've updated the test case to match the trivially different output. Finally, I've also factored all the pass initialization for the passes that use this technique as well, so that should be done regularly and reliably. Thanks to James for the help reviewing and thinking about this stuff, and Ben for help thinking about it as well! Differential Revision: http://reviews.llvm.org/D17435 llvm-svn: 261316
* LoopPass: Simplify the API for adding a new loop. NFCJustin Bogner2015-10-221-5/+4
| | | | | | | 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
* [LoopUnswitch] Correct misleading comments.Chen Li2015-10-141-2/+1
| | | | | | | | | | Reviewers: reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13738 llvm-svn: 250317
* Scalar: Remove remaining ilist iterator implicit conversionsDuncan P. N. Exon Smith2015-10-131-9/+11
| | | | | | | | | | | | | | | | | | | Remove remaining `ilist_iterator` implicit conversions from LLVMScalarOpts. This change exposed some scary behaviour in lib/Transforms/Scalar/SCCP.cpp around line 1770. This patch changes a call from `Function::begin()` to `&Function::front()`, since the return was immediately being passed into another function that takes a `Function*`. `Function::front()` started to assert, since the function was empty. Note that `Function::end()` does not point at a legal `Function*` -- it points at an `ilist_half_node` -- so the other function was getting garbage before. (I added the missing check for `Function::isDeclaration()`.) Otherwise, no functionality change intended. llvm-svn: 250211
* Generalize convergent check to handle invokes as well as calls.Owen Anderson2015-10-091-4/+4
| | | | llvm-svn: 249892
* Teach LoopUnswitch not to perform non-trivial unswitching on loops ↵Owen Anderson2015-10-091-0/+14
| | | | | | | | | | | containing convergent operations. Doing so could cause the post-unswitching convergent ops to be control-dependent on the unswitch condition where they were not before. This check could be refined to allow unswitching where the convergent operation was already control-dependent on the unswitch condition. llvm-svn: 249874
* [LoopUnswitch] Add block frequency analysis to recognize hot/cold regionsChen Li2015-09-291-0/+48
| | | | | | | | | | | | Summary: This patch adds block frequency analysis to LoopUnswitch pass to recognize hot/cold regions. For cold regions the pass only performs trivial unswitches since they do not increase code size, and for hot regions everything works as before. This helps to minimize code growth in cold regions and be more aggressive in hot regions. Currently the default cold regions are blocks with frequencies below 20% of function entry frequency, and it can be adjusted via -loop-unswitch-cold-block-frequency flag. The entire feature is controlled via -loop-unswitch-with-block-frequency flag and it is off by default. Reviewers: broune, silvas, dnovillo, reames Subscribers: davidxl, llvm-commits Differential Revision: http://reviews.llvm.org/D11605 llvm-svn: 248777
* [LoopUnswitch] Require DominatorTree info.Michael Zolotukhin2015-09-221-11/+7
| | | | | | | | | | | | | | | | | | | | | Summary: We should either require the DT info to be available, or check if it's available in every place we use DT (and we already miss such check in one place, which causes failures in some cases). As other loop passes preserve DT and it's usually available, it makes sense to just require it here. There is no regression test, because the bug only shows up if pass manager decides to clean DT info right before LoopUnswitch. If loop-unswitch is run separately, DT is available, so bug isn't exposed. Reviewers: chandlerc, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13036 llvm-svn: 248230
* Fix UB: can't bind a reference to nullptr (NFC)Mehdi Amini2015-09-211-1/+1
| | | | | From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 248213
* Add GlobalsAA as preserved to a bunch of transformsJames Molloy2015-09-101-0/+2
| | | | | | GlobalsAA must by definition be preserved in function passes, but the passmanager doesn't know that. Make each pass explicitly preserve GlobalsAA. llvm-svn: 247263
* [PM] Port ScalarEvolution to the new pass manager.Chandler Carruth2015-08-171-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change makes ScalarEvolution a stand-alone object and just produces one from a pass as needed. Making this work well requires making the object movable, using references instead of overwritten pointers in a number of places, and other refactorings. I've also wired it up to the new pass manager and added a RUN line to a test to exercise it under the new pass manager. This includes basic printing support much like with other analyses. But there is a big and somewhat scary change here. Prior to this patch ScalarEvolution was never *actually* invalidated!!! Re-running the pass just re-wired up the various other analyses and didn't remove any of the existing entries in the SCEV caches or clear out anything at all. This might seem OK as everything in SCEV that can uses ValueHandles to track updates to the values that serve as SCEV keys. However, this still means that as we ran SCEV over each function in the module, we kept accumulating more and more SCEVs into the cache. At the end, we would have a SCEV cache with every value that we ever needed a SCEV for in the entire module!!! Yowzers. The releaseMemory routine would dump all of this, but that isn't realy called during normal runs of the pipeline as far as I can see. To make matters worse, there *is* actually a key that we don't update with value handles -- there is a map keyed off of Loop*s. Because LoopInfo *does* release its memory from run to run, it is entirely possible to run SCEV over one function, then over another function, and then lookup a Loop* from the second function but find an entry inserted for the first function! Ouch. To make matters still worse, there are plenty of updates that *don't* trip a value handle. It seems incredibly unlikely that today GVN or another pass that invalidates SCEV can update values in *just* such a way that a subsequent run of SCEV will incorrectly find lookups in a cache, but it is theoretically possible and would be a nightmare to debug. With this refactoring, I've fixed all this by actually destroying and recreating the ScalarEvolution object from run to run. Technically, this could increase the amount of malloc traffic we see, but then again it is also technically correct. ;] I don't actually think we're suffering from tons of malloc traffic from SCEV because if we were, the fact that we never clear the memory would seem more likely to have come up as an actual problem before now. So, I've made the simple fix here. If in fact there are serious issues with too much allocation and deallocation, I can work on a clever fix that preserves the allocations (while clearing the data) between each run, but I'd prefer to do that kind of optimization with a test case / benchmark that shows why we need such cleverness (and that can test that we actually make it faster). It's possible that this will make some things faster by making the SCEV caches have higher locality (due to being significantly smaller) so until there is a clear benchmark, I think the simple change is best. Differential Revision: http://reviews.llvm.org/D12063 llvm-svn: 245193
* [LoopUnswitch] Check OptimizeForSize before traversing over all basic blocks ↵Chen Li2015-08-131-7/+6
| | | | | | | | | | | | | | in current loop Summary: This patch moves the check of OptimizeForSize before traversing over all basic blocks in current loop. If OptimizeForSize is set to true, no non-trivial unswitch is ever allowed. Therefore, the early exit will help reduce compilation time. This patch should be NFC. Reviewers: reames, weimingz, broune Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11997 llvm-svn: 244868
* don't repeat function names in comments; NFCSanjay Patel2015-08-111-39/+34
| | | | llvm-svn: 244672
* fix 80-cols; NFCSanjay Patel2015-08-111-19/+22
| | | | llvm-svn: 244668
OpenPOWER on IntegriCloud