summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [LCSSA] Don't use VH callbacks to invalidate SCEV when creating LCSSA phisDaniil Suchkov2019-12-061-5/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | In general ValueHandleBase::ValueIsRAUWd shouldn't be called when not all uses of the value were actually replaced, though, currently formLCSSAForInstructions calls it when it inserts LCSSA-phis. Calls of ValueHandleBase::ValueIsRAUWd were added to LCSSA specifically to update/invalidate SCEV. In the best case these calls duplicate some of the work already done by SE->forgetValue, though in case when SCEV of the value is SCEVUnknown, SCEV replaces the underlying value of SCEVUnknown with the new value (i.e. acts like LCSSA-phi actually fully replaces the value it is created for), which leads to SCEV being corrupted because LCSSA-phi rarely dominates all uses of its inputs. Fixes bug https://bugs.llvm.org/show_bug.cgi?id=44058. Reviewers: fhahn, efriedma, reames, sanjoy.google Reviewed By: fhahn Subscribers: hiraditya, javed.absar, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D70593
* [SimpleLoopUnswitch] Invalidate the topmost loop with ExitBB as exiting.Florian Hahn2019-12-041-2/+17
| | | | | | | | | | | | | | | | | | | | | | | | | | SCEV caches the exiting blocks when computing exit counts. In SimpleLoopUnswitch, we split the exit block of the loop to unswitch. Currently we only invalidate the loop containing that exit block, but if that block is the exiting block for a parent loop, we have stale cache entries. We have to invalidate the top-most loop that contains the exit block as exiting block. We might also be able to skip invalidating the loop containing the exit block, if the exit block is not an exiting block of that loop. There are also 2 more places in SimpleLoopUnswitch, that use a similar problematic approach to get the loop to invalidate. If the patch makes sense, I will also update those places to a similar approach (they deal with multiple exit blocks, so we cannot directly re-use getTopMostExitingLoop). Fixes PR43972. Reviewers: skatkov, reames, asbirlea, chandlerc Reviewed By: asbirlea Differential Revision: https://reviews.llvm.org/D70786
* [MemorySSA] Moving at the end often means before terminator.Alina Sbirlea2019-11-201-1/+1
| | | | | | | | | | | | | Moving accesses in MemorySSA at InsertionPlace::End, when an instruction is moved into a block, almost always means insert at the end of the block, but before the block terminator. This matters when the block terminator is a MemoryAccess itself (an invoke), and the insertion must be done before the terminator for the update to be correct. Insert an additional position: InsertionPlace:BeforeTerminator and update current usages where this applies. Resolves PR44027.
* 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
* SimpleLoopUnswitch - fix uninitialized variable and null dereference ↵Simon Pilgrim2019-10-161-2/+3
| | | | | | warnings. NFCI. llvm-svn: 374986
* [MemorySSA] Update DomTree before applying MSSA updates.Alina Sbirlea2019-10-151-8/+5
| | | | | | Update on the fix in rL374850. llvm-svn: 374918
* [MemorySSA] Update for partial unswitch.Alina Sbirlea2019-10-141-0/+7
| | | | | | | | Update MSSA for blocks cloned when doing partial unswitching. Enable additional testing with MSSA. Resolves PR43641. llvm-svn: 374850
* [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
* [MemorySSA] Use SetVector to avoid nondeterminism.Alina Sbirlea2019-07-121-3/+3
| | | | | | | | | | | | | | | | Summary: Use a SetVector for DeadBlockSet. Resolves PR42574. Reviewers: george.burgess.iv, uabelho, dblaikie Subscribers: jlebar, Prazek, mgrang, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64601 llvm-svn: 365970
* [SimpleLoopUnswitch] Don't consider unswitching `switch` insructions with ↵Serguei Katkov2019-07-101-1/+1
| | | | | | | | | | | | | | | one unique successor Only instructions with two or more unique successors should be considered for unswitching. Patch Author: Daniil Suchkov. Reviewers: reames, asbirlea, skatkov Reviewed By: skatkov Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D64404 llvm-svn: 365611
* [IRBuilder] Introduce helpers for and/or of multiple values at oncePhilip Reames2019-07-061-8/+3
| | | | | | | | We had versions of this code scattered around, so consolidate into one location. Not strictly NFC since the order of intermediate results may change in some places, but since these operations are associatives, should not change results. llvm-svn: 365259
* [SimpleLoopUnswitch] Implement handling of prof branch_weights metadata for ↵Yevgeny Rouban2019-07-011-17/+39
| | | | | | | | SwitchInst Differential Revision: https://reviews.llvm.org/D60606 llvm-svn: 364734
* Only passes that preserve MemorySSA must mark it as preserved.Alina Sbirlea2019-06-111-1/+5
| | | | | | | | | | | | | | | | | | | | 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
* Use llvm::stable_sortFangrui Song2019-04-231-4/+3
| | | | | | While touching the code, simplify if feasible. llvm-svn: 358996
* [MemorySSA & LoopPassManager] Resolve PR40038.Alina Sbirlea2019-02-221-3/+2
| | | | | | | | | | | | | | The correct edge being deleted is not to the unswitched exit block, but to the original block before it was split. That's the key in the map, not the value. The insert is correct. The new edge is to the .split block. The splitting turns OriginalBB into: OriginalBB -> OriginalBB.split. Assuming the orignal CFG edge: ParentBB->OriginalBB, we must now delete ParentBB->OriginalBB, not ParentBB->OriginalBB.split. llvm-svn: 354656
* [MemorySSA & LoopPassManager] Update MemorySSA in formDedicatedExitBlocks.Alina Sbirlea2019-02-211-5/+13
| | | | | | | MemorySSA is now updated when forming dedicated exit blocks. Resolves PR40037. llvm-svn: 354623
* [NFC] Rename DontDeleteUselessPHIs --> KeepOneInputPHIsMax Kazantsev2019-02-121-4/+4
| | | | llvm-svn: 353801
* [SimpleLoopUnswitch] Early check exit for trivial unswitch with MemorySSA.Alina Sbirlea2019-01-281-0/+4
| | | | | | | | | | | | | | | Summary: If MemorySSA is avaiable, we can skip checking all instructions if block has any Defs. (volatile loads are also Defs). We still need to check all instructions for "canThrow", even if no Defs are found. Reviewers: chandlerc Subscribers: sanjoy, jlebar, Prazek, george.burgess.iv, llvm-commits Differential Revision: https://reviews.llvm.org/D57129 llvm-svn: 352393
* 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
* [SimpleLoopUnswitch] Increment stats counter for unswitching switch instructionZaara Syeda2019-01-151-1/+4
| | | | | | | | | | | Increment statistics counter NumSwitches at unswitchNontrivialInvariants() for unswitching a non-trivial switch instruction. This is to fix a bug that it increments NumBranches even for the case of switch instruction. There is no functional change in this patch. Differential Revision: https://reviews.llvm.org/D56408 llvm-svn: 351193
* [SimpleLoopUnswitch] Remove debug dump.Alina Sbirlea2018-12-041-3/+1
| | | | llvm-svn: 348267
* Update MemorySSA in SimpleLoopUnswitch.Alina Sbirlea2018-12-041-77/+235
| | | | | | | | | | | Summary: Teach SimpleLoopUnswitch to preserve MemorySSA. Subscribers: sanjoy, jlebar, Prazek, george.burgess.iv, llvm-commits Differential Revision: https://reviews.llvm.org/D47022 llvm-svn: 348263
* [SimpleLoopUnswitch] adding cost multiplier to cap exponential unswitch withFedor Sergeev2018-11-161-2/+116
| | | | | | | | | | | | | | | | | | | | | We need to control exponential behavior of loop-unswitch so we do not get run-away compilation. Suggested solution is to introduce a multiplier for an unswitch cost that makes cost prohibitive as soon as there are too many candidates and too many sibling loops (meaning we have already started duplicating loops by unswitching). It does solve the currently known problem with compile-time degradation (PR 39544). Tests are built on top of a recently implemented CHECK-COUNT-<num> FileCheck directives. Reviewed By: chandlerc, mkazantsev Differential Revision: https://reviews.llvm.org/D54223 llvm-svn: 347097
* [SimpleLoopUnswitch] partial unswitch needs to be careful when replacing ↵Fedor Sergeev2018-11-071-1/+14
| | | | | | | | | | | | | | | | | | | | | | | | | invariants with constants When partial unswitch operates on multiple conditions at once, .e.g: if (Cond1 || Cond2 || NonInv) ... it should infer (and replace) values for individual conditions only on one side of unswitch and not another. More precisely only these derivations hold true: (Cond1 || Cond2) == false => Cond1 == Cond2 == false (Cond1 && Cond2) == true => Cond1 == Cond2 == true By the way we organize unswitching it means only replacing on "continue" blocks and never on "unswitched" ones. Since trivial unswitch does not have "unswitched" blocks it does not have this problem. Fixes PR 39568. Reviewers: chandlerc, asbirlea Differential Revision: https://reviews.llvm.org/D54211 llvm-svn: 346350
* Fix -Wdocumentation warning. NFCI.Simon Pilgrim2018-10-271-4/+4
| | | | llvm-svn: 345454
* [SimpleLoopUnswitch] Unswitch by experimental.guard intrinsicsMax Kazantsev2018-10-261-2/+107
| | | | | | | | | | | | | | | | | | This patch adds support of `llvm.experimental.guard` intrinsics to non-trivial simple loop unswitching. These intrinsics represent implicit control flow which has pretty much the same semantics as usual conditional branches. The algorithm of dealing with them is following: - Consider guards as unswitching candidates; - If a guard is considered the best candidate, turn it into a branch; - Apply normal unswitching algorithm on this branch. The patch has no compile time effect on code that does not contain any guards. Differential Revision: https://reviews.llvm.org/D53744 Reviewed By: chandlerc llvm-svn: 345387
* [SimpleLoopUnswitch] Make all checks before actual non-trivial unswitchMax Kazantsev2018-10-261-18/+20
| | | | | | | | | | | We should be able to make all relevant checks before we actually start the non-trivial unswitching, so that we could guarantee that once we have started the transform, it will always succeed. Reviewed By: chandlerc Differential Revision: https://reviews.llvm.org/D53747 llvm-svn: 345375
* [TI removal] Switch simple loop unswitch to `Instruction`.Chandler Carruth2018-10-181-5/+5
| | | | llvm-svn: 344719
* [TI removal] Make variables declared as `TerminatorInst` and initializedChandler Carruth2018-10-151-1/+1
| | | | | | | | | | | | | by `getTerminator()` calls instead be declared as `Instruction`. This is the biggest remaining chunk of the usage of `getTerminator()` that insists on the narrow type and so is an easy batch of updates. Several files saw more extensive updates where this would cascade to requiring API updates within the file to use `Instruction` instead of `TerminatorInst`. All of these were trivial in nature (pervasively using `Instruction` instead just worked). llvm-svn: 344502
* llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)Fangrui Song2018-09-271-5/+4
| | | | | | | | | | | | Summary: The convenience wrapper in STLExtras is available since rL342102. Reviewers: dblaikie, javed.absar, JDevlieghere, andreadb Subscribers: MatzeB, sanjoy, arsenm, dschuff, mehdi_amini, sdardis, nemanjai, jvesely, nhaehnle, sbc100, jgravelle-google, eraman, aheejin, kbarton, JDevlieghere, javed.absar, gbedwell, jrtc27, mgrang, atanasyan, steven_wu, george.burgess.iv, dexonsmith, kristina, jsji, llvm-commits Differential Revision: https://reviews.llvm.org/D52573 llvm-svn: 343163
* [SimpleLoopUnswitch] remove a chain of dead blocks at onceFedor Sergeev2018-09-041-19/+19
| | | | | | | | | | | | | | | | | | | | | | Recent change to deleteDeadBlocksFromLoop was not enough to fix all the problems related to dead blocks after nontrivial unswitching of switches. We need to delete all the dead blocks that were created during unswitching, otherwise we will keep having problems with phi's or dead blocks. This change removes all the dead blocks that are reachable from the loop, not trying to track whether these blocks are newly created by unswitching or not. While not completely correct, we are unlikely to get loose but reachable dead blocks that do not belong to our loop nest. It does fix all the failures currently known, in particular PR38778. Reviewed By: asbirlea Differential Revision: https://reviews.llvm.org/D51519 llvm-svn: 341398
* [SimpleLoopUnswitch] After unswitch delete dead blocks in parent loopsFedor Sergeev2018-08-291-2/+10
| | | | | | | | | | | | | | | | | | | | Summary: Assert from PR38737 happens on the dead block inside the parent loop after unswitching nontrivial switch in the inner loop. deleteDeadBlocksFromLoop now takes extra care to detect/remove dead blocks in all the parent loops in addition to the blocks from original loop being unswitched. Reviewers: asbirlea, chandlerc Reviewed By: asbirlea Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D51415 llvm-svn: 340955
* [SimpleLoopUnswitch] Form dedicated exits after trivial unswitches.Alina Sbirlea2018-08-281-5/+8
| | | | | | | | | | | | | | Summary: Form dedicated exits after trivial unswitches. Fixes PR38737, PR38283. Reviewers: chandlerc, fedor.sergeev Subscribers: sanjoy, jlebar, uabelho, llvm-commits Differential Revision: https://reviews.llvm.org/D51375 llvm-svn: 340871
* [SimpleLoopUnswitch] Fix DT updates for trivial branch unswitching.Alina Sbirlea2018-07-281-2/+4
| | | | | | | | | | | | | | | Summary: Fixing 2 issues with the DT update in trivial branch switching, though I don't have a case where DT update fails. 1. After splitting ParentBB->UnswitchedBB edge, new edges become: ParentBB->LoopExitBB->UnswitchedBB, so remove ParentBB->LoopExitBB edge. 2. AFAIU, for multiple CFG changes, DT should be updated using batch updates, vs consecutive addEdge and removeEdge calls. Reviewers: chandlerc, kuhar Subscribers: sanjoy, jlebar, llvm-commits Differential Revision: https://reviews.llvm.org/D49925 llvm-svn: 338180
* [PM/Unswitch] Fix unused variable in r336646.Chandler Carruth2018-07-101-0/+1
| | | | llvm-svn: 336647
* [PM/Unswitch] Fix a collection of closely related issues with trivialChandler Carruth2018-07-101-17/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | switch unswitching. The core problem was that the way we handled unswitching trivial exit edges through the default successor of a switch. For some reason I thought the right way to do this was to add a block containing unreachable and point the default successor at this block. In retrospect, this has an amazing number of problems. The first issue is the one that this pass has always worked around -- we have to *detect* such edges and avoid unswitching them again. This seemed pretty easy really. You juts look for an edge to a block containing unreachable. However, this pattern is woefully unsound. So many things can break it. The amazing thing is that I found a test case where *simple-loop-unswitch itself* breaks this! When we do a *non-trivial* unswitch of a switch we will end up splitting this exit edge. The result will be a default successor that is an exit and terminates in ... a perfectly normal branch. So the first test case that I started trying to fix is added to the nontrivial test cases. This is a ridiculous example that did just amazing things previously. With just unswitch, it would create 10+ copies of this stuff stamped out. But if you combine it *just right* with a bunch of other passes (like simplify-cfg, loop rotate, and some LICM) you can get it to do this infinitely. Or at least, I never got it to finish. =[ This, in turn, uncovered another related issue. When we are manipulating these switches after doing a trivial unswitch we never correctly updated PHI nodes to reflect our edits. As soon as I started changing how these edges were managed, it became obvious there were more issues that I couldn't realistically leave unaddressed, so I wrote more test cases around PHI updates here and ensured all of that works now. And this, in turn, required some adjustment to how we collect and manage the exit successor when it is the default successor. That showed a clear bug where we failed to include it in our search for the outer-most loop reached by an unswitched exit edge. This was actually already tested and the test case didn't work. I (wrongly) thought that was due to SCEV failing to analyze the switch. In fact, it was just a simple bug in the code that skipped the default successor. While changing this, I handled it correctly and have updated the test to reflect that we now get precise SCEV analysis of trip counts for the outer loop in one of these cases. llvm-svn: 336646
* [PM/Unswitch] Fix a nasty bug in the new PM's unswitch introduced inChandler Carruth2018-07-091-26/+81
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | r335553 with the non-trivial unswitching of switches. The code correctly updated most aspects of the CFG and analyses, but missed some crucial aspects: 1) When multiple cases have the same successor, we unswitch that a single time and replace the switch with a direct branch. The CFG here is correct, but the target of this direct branch may have had a PHI node with multiple entries in it. 2) When we still have to clone a successor of the switch into an unswitched copy of the loop, we'll delete potentially multiple edges entering this successor, not just one. 3) We also have to delete multiple edges entering the successors in the original loop when they have to be retained. 4) When the "retained successor" *also* occurs as a case successor, we just assert failed everywhere. This doesn't happen very easily because its always valid to simply drop the case -- the retained successor for switches is always the default successor. However, it is likely possible through some contrivance of different loop passes, unrolling, and simplifying for this to occur in practice and certainly there is nothing "invalid" about the IR so this pass needs to handle it. 5) In the case of #4, we also will replace these multiple edges with a direct branch much like in #1 and need to collapse the entries in any PHI nodes to a single enrty. All of this stems from the delightful fact that the same successor can show up in multiple parts of the switch terminator, and each of these are considered a distinct edge for the purpose of PHI nodes (and iterating the successors and predecessors) but not for unswitching itself, the dominator tree, or many other things. For the record, I intensely dislike this "feature" of the IR in large part because of the complexity it causes in passes like this. We already have a ton of logic building sets and handling duplicates, and we just had to add a bunch more. I've added a complex test case that covers all five of the above failure modes. I've also added a variation on it where #4 and #5 occur in loop exit, adding fun where we have an LCSSA PHI node with "multiple entries" despite have dedicated exits. There were no additional issues found by this, but it seems a useful corner case to cover with testing. One thing that working on all of this code has made painfully clear for me as well is how amazingly inefficient our PHI node representation is (in terms of the in-memory data structures and the APIs used to update them). This code has truly marvelous complexity bounds because every time we remove an entry from a PHI node we do a linear scan to find it and then a linear update to the data structure to remove it. We could in theory batch all of the PHI node updates into a single linear walk of the operands making this much more efficient, but the APIs fight hard against this and the fact that we have to handle duplicates in the peculiar manner we do (removing all but one in some cases) makes even implementing that very tedious and annoying. Anyways, none of this is new here or specific to loop unswitching. All code in LLVM that updates PHI node operands suffers from these problems. llvm-svn: 336536
* [PM/LoopUnswitch] Fix PR37889, producing the correct loop nest structureChandler Carruth2018-07-071-2/+81
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | after trivial unswitching. This PR illustrates that a fundamental analysis update was not performed with the new loop unswitch. This update is also somewhat fundamental to the core idea of the new loop unswitch -- we actually *update* the CFG based on the unswitching. In order to do that, we need to update the loop nest in addition to the domtree. For some reason, when writing trivial unswitching, I thought that the loop nest structure cannot be changed by the transformation. But the PR helps illustrate that it clearly can. I've expanded this to a number of different test cases that try to cover the different cases of this. When we unswitch, we move an exit edge of a loop out of the loop. If this exit edge changes which loop reached by an exit is the innermost loop, it changes the parent of the loop. Essentially, this transformation may hoist the inner loop up the nest. I've added the simple logic to handle this reliably in the trivial unswitching case. This just requires updating LoopInfo and rebuilding LCSSA on the impacted loops. In the trivial case, we don't even need to handle dedicated exits because we're only hoisting the one loop and we just split its preheader. I've also ported all of these tests to non-trivial unswitching and verified that the logic already there correctly handles the loop nest updates necessary. Differential Revision: https://reviews.llvm.org/D48851 llvm-svn: 336477
* [PM/LoopUnswitch] Fix PR37651 by correctly invalidating SCEV whenChandler Carruth2018-07-031-21/+84
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | unswitching loops. Original patch trying to address this was sent in D47624, but that didn't quite handle things correctly. There are two key principles used to select whether and how to invalidate SCEV-cached information about loops: 1) We must invalidate any info SCEV has cached before unswitching as we may change (or destroy) the loop structure by the act of unswitching, and make it hard to recover everything we want to invalidate within SCEV. 2) We need to invalidate all of the loops whose CFGs are mutated by the unswitching. Notably, this isn't the *entire* loop nest, this is every loop contained by the outermost loop reached by an exit block relevant to the unswitch. And we need to do this even when doing trivial unswitching. I've added more focused tests that directly check that SCEV starts off with imprecise information and after unswitching (and simplifying instructions) re-querying SCEV will produce precise information. These tests also specifically work to check that an *outer* loop's information becomes precise. However, the testing here is still a bit imperfect. Crafting test cases that reliably fail to be analyzed by SCEV before unswitching and succeed afterward proved ... very, very hard. It took me several hours and careful work to build these, and I'm not optimistic about necessarily coming up with more to cover more elaborate possibilities. Fortunately, the code pattern we are testing here in the pass is really straightforward and reliable. Thanks to Max Kazantsev for the initial work on this as well as the review, and to Hal Finkel for helping me talk through approaches to test this stuff even if it didn't come to much. Differential Revision: https://reviews.llvm.org/D47624 llvm-svn: 336183
* [PM/LoopUnswitch] Teach the new unswitch to handle nontrivialChandler Carruth2018-06-251-156/+201
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | unswitching of switches. This works much like trivial unswitching of switches in that it reliably moves the switch out of the loop. Here we potentially clone the entire loop into each successor of the switch and re-point the cases at these clones. Due to the complexity of actually doing nontrivial unswitching, this patch doesn't create a dedicated routine for handling switches -- it would duplicate far too much code. Instead, it generalizes the existing routine to handle both branches and switches as it largely reduces to looping in a few places instead of doing something once. This actually improves the results in some cases with branches due to being much more careful about how dead regions of code are managed. With branches, because exactly one clone is created and there are exactly two edges considered, somewhat sloppy handling of the dead regions of code was sufficient in most cases. But with switches, there are much more complicated patterns of dead code and so I've had to move to a more robust model generally. We still do as much pruning of the dead code early as possible because that allows us to avoid even cloning the code. This also surfaced another problem with nontrivial unswitching before which is that we weren't as precise in reconstructing loops as we could have been. This seems to have been mostly harmless, but resulted in pointless LCSSA PHI nodes and other unnecessary cruft. With switches, we have to get this *right*, and everything benefits from it. While the testing may seem a bit light here because we only have two real cases with actual switches, they do a surprisingly good job of exercising numerous edge cases. Also, because we share the logic with branches, most of the changes in this patch are reasonably well covered by existing tests. The new unswitch now has all of the same fundamental power as the old one with the exception of the single unsound case of *partial* switch unswitching -- that really is just loop specialization and not unswitching at all. It doesn't fit into the canonicalization model in any way. We can add a loop specialization pass that runs late based on profile data if important test cases ever come up here. Differential Revision: https://reviews.llvm.org/D47683 llvm-svn: 335553
* [PM/LoopUnswitch] Add partial non-trivial unswitching for invariantChandler Carruth2018-06-211-92/+237
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | conditions feeding a chain of `and`s or `or`s for a branch. Much like with full non-trivial unswitching, we rely on the pass manager to handle iterating until all of the profitable unswitches have been done. This is to allow other more profitable unswitches to fire on any of the cloned, simpler versions of the loop if viable. Threading the partial unswiching through the non-trivial unswitching logic motivated some minor refactorings. If those are too disruptive to make it reasonable to review this patch, I can separate them out, but it'll be somewhat timeconsuming so I wanted to send it for initial review as-is. Feel free to tell me whether it warrants pulling apart. I've tried to re-use (and factor out) logic form the partial trivial unswitching, but not as much could be shared as I had haped. Still, this wasn't as bad as I naively expected. Some basic testing is added, but I probably need more. Suggestions for things you'd like to see tested more than welcome. One thing I'd like to do is add some testing that when we schedule this with loop-instsimplify it effectively cleans up the cruft created. Last but not least, this uncovered a bug that has been in loop cloning the entire time for non-trivial unswitching. Specifically, we didn't correctly add the outer-most cloned loop to the list of cloned loops. This meant that LCSSA wouldn't be updated for it hypothetically, and more significantly that we would never visit it in the loop pass manager. I noticed this while checking loop-instsimplify by hand. I'll try to separate this bugfix out into its own patch with a more focused test. But it is just one line, so shouldn't significantly confuse the review here. After this patch, the only missing "feature" in this unswitch I'm aware of us non-trivial unswitching of switches. I'll try implementing *full* non-trivial unswitching of switches (which is at least a sound thing to implement), but *partial* non-trivial unswitching of switches is something I don't see any sound and principled way to implement. I also have no interesting test cases for the latter, so I'm not really worried. The rest of the things that need to be ported are bug-fixes and more narrow / targeted support for specific issues. Differential Revision: https://reviews.llvm.org/D47522 llvm-svn: 335203
* [PM/LoopUnswitch] Support partial trivial unswitching.Chandler Carruth2018-06-201-49/+171
| | | | | | | | | | | | | | | | | | | | | | | | | The idea of partial unswitching is to take a *part* of a branch's condition that is loop invariant and just unswitching that part. This primarily makes sense with i1 conditions of branches as opposed to switches. When dealing with i1 conditions, we can easily extract loop invariant inputs to a a branch and unswitch them to test them entirely outside the loop. As part of this, we now create much more significant cruft in the loop body, so this relies on adding cleanup passes to the loop pipeline and revisiting unswitched loops to do that cleanup before continuing to process them. This already appears to be more powerful at unswitching than the old loop unswitch pass, and so I'd appreciate pretty careful review in case I'm just missing some correctness checks. The `LIV-loop-condition` test case is not unswitched by the old unswitch pass, but is with this pass. Thanks to Sanjoy and Fedor for the review! Differential Revision: https://reviews.llvm.org/D46706 llvm-svn: 335156
* [NFC] fix trivial typos in commentsHiroshi Inoue2018-06-141-2/+2
| | | | llvm-svn: 334687
* [PM/LoopUnswitch] Fix how the cloned loops are handled when updating analyses.Chandler Carruth2018-06-021-44/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: I noticed this issue because we didn't put the primary cloned loop into the `NonChildClonedLoops` vector and so never iterated on it. Once I fixed that, it made it clear why I had to do a really complicated and unnecesasry dance when updating the loops to remain in canonical form -- I was unwittingly working around the fact that the primary cloned loop wasn't in the expected list of cloned loops. Doh! Now that we include it in this vector, we don't need to return it and we can consolidate the update logic as we correctly have a single place where it can be handled. I've just added a test for the iteration order aspect as every time I changed the update logic partially or incorrectly here, an existing test failed and caught it so that seems well covered (which is also evidenced by the extensive working around of this missing update). Reviewers: asbirlea, sanjoy Subscribers: mcrosier, hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D47647 llvm-svn: 333811
* [PM/LoopUnswitch] When using the new SimpleLoopUnswitch pass, scheduleChandler Carruth2018-05-301-25/+29
| | | | | | | | | | | | | | | | | | | | | | loop-cleanup passes at the beginning of the loop pass pipeline, and re-enqueue loops after even trivial unswitching. This will allow us to much more consistently avoid simplifying code while doing trivial unswitching. I've also added a test case that specifically shows effective iteration using this technique. I've unconditionally updated the new PM as that is always using the SimpleLoopUnswitch pass, and I've made the pipeline changes for the old PM conditional on using this new unswitch pass. I added a bunch of comments to the loop pass pipeline in the old PM to make it more clear what is going on when reviewing. Hopefully this will unblock doing *partial* unswitching instead of just full unswitching. Differential Revision: https://reviews.llvm.org/D47408 llvm-svn: 333493
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-17/+20
| | | | | | | | | | | | | | | | 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
* [PM/LoopUnswitch] Avoid pointlessly creating an exit block set.Chandler Carruth2018-05-101-19/+4
| | | | | | | This code can just test whether blocks are *in* the loop, which we already have a dedicated set tracking in the loop itself. llvm-svn: 332004
* [PM/LoopUnswitch] Remove the last manual domtree update code from loopChandler Carruth2018-05-011-170/+18
| | | | | | | | | unswitch and replace it with the amazingly simple update API code. This addresses piles of FIXMEs around the update logic here and makes everything substantially simpler. llvm-svn: 331247
* [PM/LoopUnswitch] Add back a successor set that was removed based onChandler Carruth2018-05-011-2/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | code review. It turns out this *is* necessary, and I read the comment on the API correctly the first time. ;] The `applyUpdates` routine requires that updates are "balanced". This is in order to cleanly handle cycles like inserting, removing, nad then re-inserting the same edge. This precludes inserting the same edge multiple times in a row as handling that would cause the insertion logic to become *ordered* instead of *unordered* (which is what the API provides). It happens that in this specific case nothing (other than an assert and contract violation) goes wrong because we're never inserting and removing the same edge. The implementation *happens* to do the right thing to eliminate redundant insertions in that case. But the requirement is there and there is an assert to catch it. Somehow, after the code review I never did another asserts-clang build testing loop-unswich for a long time. As a consequence, I didn't notice this despite a bunch of testing going on, but it shows up immediately with an asserts build of clang itself. llvm-svn: 331246
OpenPOWER on IntegriCloud