summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
Commit message (Collapse)AuthorAgeFilesLines
* Merging r344454, r344455, r344645:Tom Stellard2018-11-021-2/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ------------------------------------------------------------------------ r344454 | xbolva00 | 2018-10-13 08:21:55 -0700 (Sat, 13 Oct 2018) | 11 lines [InstCombine] Fixed crash with aliased functions Summary: Fixes PR39177 Reviewers: spatel, jbuening Reviewed By: jbuening Subscribers: jbuening, llvm-commits Differential Revision: https://reviews.llvm.org/D53129 ------------------------------------------------------------------------ ------------------------------------------------------------------------ r344455 | xbolva00 | 2018-10-13 08:26:13 -0700 (Sat, 13 Oct 2018) | 2 lines [NFC] Fixed duplicated test file ------------------------------------------------------------------------ ------------------------------------------------------------------------ r344645 | xbolva00 | 2018-10-16 14:18:31 -0700 (Tue, 16 Oct 2018) | 9 lines [InstCombine] Cleanup libfunc attribute inferring Reviewers: efriedma Reviewed By: efriedma Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D53338 ------------------------------------------------------------------------ llvm-svn: 345921
* Merging r341094:Hans Wennborg2018-08-311-0/+42
| | | | | | | | | | | | | | | | | | | | ------------------------------------------------------------------------ r341094 | efriedma | 2018-08-30 20:59:24 +0200 (Thu, 30 Aug 2018) | 11 lines [SROA] Fix alignment for uses of PHI nodes. Splitting an alloca can decrease the alignment of GEPs into the partition. Normally, rewriting accounts for this, but the code was missing for uses of PHI nodes and select instructions. Fixes https://bugs.llvm.org/show_bug.cgi?id=38707 . Differential Revision: https://reviews.llvm.org/D51335 ------------------------------------------------------------------------ llvm-svn: 341220
* Merging r340900:Hans Wennborg2018-08-301-0/+8
| | | | | | | | | | | | | | | ------------------------------------------------------------------------ r340900 | hans | 2018-08-29 08:55:27 +0200 (Wed, 29 Aug 2018) | 6 lines LoopSink: Don't sink into blocks without an insertion point (PR38462) In the PR, LoopSink was trying to sink into a catchswitch block, which doesn't have a valid insertion point. Differential Revision: https://reviews.llvm.org/D51307 ------------------------------------------------------------------------ llvm-svn: 341048
* Revert r338431: "Add DebugCounters to DivRemPairs"George Burgess IV2018-07-311-6/+0
| | | | | | | This reverts r338431; the test it added is making buildbots unhappy. Locally, I can repro the failure on reverse-iteration builds. llvm-svn: 338442
* Add DebugCounters to DivRemPairsGeorge Burgess IV2018-07-311-0/+6
| | | | | | | | | | For people who don't use DebugCounters, NFCI. Patch by Zhizhou Yang! Differential Revision: https://reviews.llvm.org/D50033 llvm-svn: 338431
* [NFC] Collect statistics in GuardWideningMax Kazantsev2018-07-311-0/+4
| | | | llvm-svn: 338348
* Remove trailing spaceFangrui Song2018-07-3017-52/+52
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* [NFC] Prepare GuardWidening for widening of cond branchesMax Kazantsev2018-07-301-27/+61
| | | | llvm-svn: 338229
* [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
* Revert r337904: [IPSCCP] Use PredicateInfo to propagate facts from cmp ↵Florian Hahn2018-07-251-118/+8
| | | | | | | | instructions. I suspect it is causing the clang-stage2-Rthinlto failures. llvm-svn: 337956
* Recommit r333268: [IPSCCP] Use PredicateInfo to propagate facts from cmp ↵Florian Hahn2018-07-251-8/+118
| | | | | | | | | | | | | | | | | | | | instructions. r337828 resolves a PredicateInfo issue with unnamed types. Original message: This patch updates IPSCCP to use PredicateInfo to propagate facts to true branches predicated by EQ and to false branches predicated by NE. As a follow up, we should be able to extend it to also propagate additional facts about nonnull. Reviewers: davide, mssimpso, dberlin, efriedma Reviewed By: davide, dberlin llvm-svn: 337904
* [DebugCounters] Keep track of total countsGeorge Burgess IV2018-07-231-1/+1
| | | | | | | | | | | | | | This patch makes debug counters keep track of the total number of times we've called `shouldExecute` for each counter, so it's easier to build automated tooling on top of these. A patch to print these counts is coming soon. Patch by Zhizhou Yang! Differential Revision: https://reviews.llvm.org/D49560 llvm-svn: 337748
* [GVN] Don't use the eliminated load as an available value in phi constructionJohn Brawn2018-07-231-0/+9
| | | | | | | | | | | In ConstructSSAForLoadSet if an available value is actually the load that we're doing SSA construction to eliminate, then we can omit it as SSAUpdate will add in the value for the phi that will be replacing it anyway. This can result in simpler IR which can allow further optimisation. Differential Revision: https://reviews.llvm.org/D44160 llvm-svn: 337686
* [GVNHoist] safeToHoistLdSt allows illegal hoistingAlexandros Lamprineas2018-07-231-1/+1
| | | | | | | | | | | | | Bug fix for PR36787. When reasoning if it's safe to hoist a load we want to make sure that the defining memory access dominates the new insertion point of the hoisted instruction. safeToHoistLdSt calls firstInBB(InsertionPoint,DefiningAccess) which returns false if InsertionPoint == DefiningAccess, and therefore it falsely thinks it's safe to hoist. Differential Revision: https://reviews.llvm.org/D49555 llvm-svn: 337674
* Early exit with cheaper checksAditya Kumar2018-07-211-13/+12
| | | | | | | Reviewers: sebpop,davide,fhahn,trentxintong Differential Revision: https://reviews.llvm.org/D49617 llvm-svn: 337643
* [IPSCCP] Fix for bot failure caused by r337548Florian Hahn2018-07-201-1/+1
| | | | llvm-svn: 337554
* Recommit r328307: [IPSCCP] Use constant range information for comparisons of ↵Florian Hahn2018-07-201-110/+80
| | | | | | | | | | | | | | | | | | | | | | | | | | | parameters. This version contains a fix to add values for which the state in ParamState change to the worklist if the state in ValueState did not change. To avoid adding the same value multiple times, mergeInValue returns true, if it added the value to the worklist. The value is added to the worklist depending on its state in ValueState. Original message: For comparisons with parameters, we can use the ParamState lattice elements which also provide constant range information. This improves the code for PR33253 further and gets us closer to use ValueLatticeElement for all values. Also, as we are using the range information in the solver directly, we do not need tryToReplaceWithConstantRange afterwards anymore. Reviewers: dberlin, mssimpso, davide, efriedma Reviewed By: mssimpso Differential Revision: https://reviews.llvm.org/D43762 llvm-svn: 337548
* [SCCP] Don't use markForcedConstant on branch conditions.Eli Friedman2018-07-191-73/+62
| | | | | | | | | | | | It's more aggressive than we need to be, and leads to strange workarounds in other places like call return value inference. Instead, just directly mark an edge viable. Tests by Florian Hahn. Differential Revision: https://reviews.llvm.org/D49408 llvm-svn: 337507
* [IPSCCP] Run Solve each time we resolved an undef in a function.Florian Hahn2018-07-171-3/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Once we resolved an undef in a function we can run Solve, which could lead to finding a constant return value for the function, which in turn could turn undefs into constants in other functions that call it, before resolving undefs there. Computationally the amount of work we are doing stays the same, just the order we process things is slightly different and potentially there are a few less undefs to resolve. We are still relying on the order of functions in the IR, which means depending on the order, we are able to resolve the optimal undef first or not. For example, if @test1 comes before @testf, we find the constant return value of @testf too late and we cannot use it while solving @test1. This on its own does not lead to more constants removed in the test-suite, probably because currently we have to be very lucky to visit applicable functions in the right order. Maybe we manage to come up with a better way of resolving undefs in more 'profitable' functions first. Reviewers: efriedma, mssimpso, davide Reviewed By: efriedma, davide Differential Revision: https://reviews.llvm.org/D49385 llvm-svn: 337283
* [LSR] If no Use is interesting, early return.Tim Shen2018-07-131-1/+3
| | | | | | | | | | | | | | | Summary: By looking at the callers of getUse(), we can see that even though IVUsers may offer uses, but they may not be interesting to LSR. It's possible that none of them is interesting. Reviewers: sanjoy Subscribers: jlebar, hiraditya, bixia, llvm-commits Differential Revision: https://reviews.llvm.org/D49049 llvm-svn: 337072
* Temporarily revert "Recommit r328307: [IPSCCP] Use constant range ↵Eric Christopher2018-07-121-81/+111
| | | | | | | | | | information for comparisons of parameters." as it's causing miscompiles. A testcase was provided in the original review thread. This reverts commit r336098. llvm-svn: 336877
* [LoopIdiomRecognize] Don't convert a do while loop to ctlz.Craig Topper2018-07-111-10/+15
| | | | | | | | | | | | | | | | | | | This commit suppresses turning loops like this into "(bitwidth - ctlz(input))". unsigned foo(unsigned input) { unsigned num = 0; do { ++num; input >>= 1; } while (input != 0); return num; } The loop version returns a value of 1 for both an input of 0 and an input of 1. Converting to a naive ctlz does not preserve that. Theoretically we could do better if we checked isKnownNonZero or we could insert a select to handle the divergence. But until we have motivating cases for that, this is the easiest solution. llvm-svn: 336864
* [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
* llvm: Add support for "-fno-delete-null-pointer-checks"Manoj Gupta2018-07-092-11/+23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Support for this option is needed for building Linux kernel. This is a very frequently requested feature by kernel developers. More details : https://lkml.org/lkml/2018/4/4/601 GCC option description for -fdelete-null-pointer-checks: This Assume that programs cannot safely dereference null pointers, and that no code or data element resides at address zero. -fno-delete-null-pointer-checks is the inverse of this implying that null pointer dereferencing is not undefined. This feature is implemented in LLVM IR in this CL as the function attribute "null-pointer-is-valid"="true" in IR (Under review at D47894). The CL updates several passes that assumed null pointer dereferencing is undefined to not optimize when the "null-pointer-is-valid"="true" attribute is present. Reviewers: t.p.northover, efriedma, jyknight, chandlerc, rnk, srhines, void, george.burgess.iv Reviewed By: efriedma, george.burgess.iv Subscribers: eraman, haicheng, george.burgess.iv, drinkcat, theraven, reames, sanjoy, xbolva00, llvm-commits Differential Revision: https://reviews.llvm.org/D47895 llvm-svn: 336613
* [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
* [LoopIdiomRecognize] Support for converting loops that use LSHR to CTLZ.Craig Topper2018-07-081-13/+21
| | | | | | | | | | | | | | | | | | | | | In the 'detectCTLZIdiom' function support for loops that use LSHR instruction instead of ASHR has been added. This supports creating ctlz from the following code. int lzcnt(int x) { int count = 0; while (x > 0) { count++; x = x >> 1; } return count; } Patch by Olga Moldovanova Differential Revision: https://reviews.llvm.org/D48354 llvm-svn: 336509
* [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
* [LoopSink] Make the enforcement of determinism deterministic.Benjamin Kramer2018-07-061-4/+6
| | | | | | | | | | | | | | LoopBlockNumber is a DenseMap<BasicBlock*, int>, comparing the result of find() will compare a pair<BasicBlock*, int>. That's of course depending on pointer ordering which varies from run to run. Reverse iteration doesn't find this because we're copying to a vector first. This bug has been there since 2016 but only recently showed up on clang selfhost with FDO and ThinLTO, which is also why I didn't manage to get a reasonable test case for this. Add an assert that would've caught this. llvm-svn: 336439
* Revert r332168: "Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading.""Michael Zolotukhin2018-07-051-19/+15
| | | | | | | There were a couple of issues reported (PR38047, PR37929) - I'll reland the patch when I figure out and fix the rootcause. llvm-svn: 336393
* [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
* Replace "Replacable" with "Replaceable". [NFC]Alina Sbirlea2018-07-021-13/+13
| | | | llvm-svn: 336133
* Recommit r328307: [IPSCCP] Use constant range information for comparisons of ↵Florian Hahn2018-07-021-111/+81
| | | | | | | | | | | | | | | | | | | | | | | | | | | parameters. This version contains a fix to add values for which the state in ParamState change to the worklist if the state in ValueState did not change. To avoid adding the same value multiple times, mergeInValue returns true, if it added the value to the worklist. The value is added to the worklist depending on its state in ValueState. Original message: For comparisons with parameters, we can use the ParamState lattice elements which also provide constant range information. This improves the code for PR33253 further and gets us closer to use ValueLatticeElement for all values. Also, as we are using the range information in the solver directly, we do not need tryToReplaceWithConstantRange afterwards anymore. Reviewers: dberlin, mssimpso, davide, efriedma Reviewed By: mssimpso Differential Revision: https://reviews.llvm.org/D43762 llvm-svn: 336098
* [UnrollAndJam] New Unroll and Jam passDavid Green2018-07-014-9/+463
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a simple implementation of the unroll-and-jam classical loop optimisation. The basic idea is that we take an outer loop of the form: for i.. ForeBlocks(i) for j.. SubLoopBlocks(i, j) AftBlocks(i) Instead of doing normal inner or outer unrolling, we unroll as follows: for i... i+=2 ForeBlocks(i) ForeBlocks(i+1) for j.. SubLoopBlocks(i, j) SubLoopBlocks(i+1, j) AftBlocks(i) AftBlocks(i+1) Remainder Loop So we have unrolled the outer loop, then jammed the two inner loops into one. This can lead to a simpler inner loop if memory accesses can be shared between the now jammed loops. To do this we have to prove that this is all safe, both for the memory accesses (using dependence analysis) and that ForeBlocks(i+1) can move before AftBlocks(i) and SubLoopBlocks(i, j). Differential Revision: https://reviews.llvm.org/D41953 llvm-svn: 336062
* [instsimplify] Move the instsimplify pass to use more obvious file namesChandler Carruth2018-06-293-0/+146
| | | | | | | | | | | | | | | | and diretory. Also cleans up all the associated naming to be consistent and removes the public access to the pass ID which was unused in LLVM. Also runs clang-format over parts that changed, which generally cleans up a bunch of formatting. This is in preparation for doing some internal cleanups to the pass. Differential Revision: https://reviews.llvm.org/D47352 llvm-svn: 336028
* Revert "Extend CFGPrinter and CallPrinter with Heat Colors"Sean Fertile2018-06-291-1/+1
| | | | | | This reverts r335996 which broke graph printing in Polly. llvm-svn: 336000
* Extend CFGPrinter and CallPrinter with Heat ColorsSean Fertile2018-06-291-1/+1
| | | | | | | | | | | | | | | Extends the CFGPrinter and CallPrinter with heat colors based on heuristics or profiling information. The colors are enabled by default and can be toggled on/off for CFGPrinter by using the option -cfg-heat-colors for both -dot-cfg[-only] and -view-cfg[-only]. Similarly, the colors can be toggled on/off for CallPrinter by using the option -callgraph-heat-colors for both -dot-callgraph and -view-callgraph. Patch by Rodrigo Caetano Rocha! Differential Revision: https://reviews.llvm.org/D40425 llvm-svn: 335996
* [SROA] Preserve DebugLoc when rewriting alloca partitionsAnastasis Grammenos2018-06-281-0/+2
| | | | | | | | | When rewriting an alloca partition copy the DL from the old alloca over the the new one. Differential Revision: https://reviews.llvm.org/D48640 llvm-svn: 335904
* [SCCP] Mark CFG as preserved.Florian Hahn2018-06-281-0/+2
| | | | | | | | | | | | SCCP does not change the CFG, so we can mark it as preserved. Reviewers: dberlin, efriedma, davide Reviewed By: davide Differential Revision: https://reviews.llvm.org/D47149 llvm-svn: 335820
* [JumpThreading] Don't try to rewrite a use if it's already valid.Michael Zolotukhin2018-06-261-10/+12
| | | | | | | | | | | | | | | | | | | Summary: When recording uses we need to rewrite after cloning a loop we need to check if the use is not dominated by the original def. The initial assumption was that the cloned basic block will introduce a new path and thus the original def will only dominate the use if they are in the same BB, but as the reproducer from PR37745 shows it's not always the case. This fixes PR37745. Reviewers: haicheng, Ka-Ka Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D48111 llvm-svn: 335675
* LoopUnroll: Allow analyzing intrinsic call costsMatt Arsenault2018-06-261-2/+7
| | | | | | | | | | | I'm not sure why the code here is skipping calls since TTI does try to do something for general calls, but it at least should allow intrinsics. Skip intrinsics that should not be omitted as calls, which is by far the most common case on AMDGPU. llvm-svn: 335645
* [IPSCCP] Change dead blocks to unreachable after visiting all executable blocks.Florian Hahn2018-06-261-3/+11
| | | | | | | | | | | | | | | | | changeToUnreachable may remove PHI nodes from executable blocks we found values for and we would fail to replace them. By changing dead blocks to unreachable after we replaced constants in all executable blocks, we ensure such PHI nodes are replaced by their known value before. Fixes PR37780. Reviewers: efriedma, davide Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D48421 llvm-svn: 335588
* [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
* [LoopIdiomRecognize] Fix a couple places where it appears we were ↵Craig Topper2018-06-251-6/+5
| | | | | | unintenionally making copies of DebugLoc. llvm-svn: 335521
* Fix invariant fdiv hoisting in LICMStanislav Mekhanoshin2018-06-231-14/+14
| | | | | | | | | | | | | FDiv is replaced with multiplication by reciprocal and invariant reciprocal is hoisted out of the loop, while multiplication remains even if invariant. Switch checks for all invariant operands and only invariant denominator to fix the issue. Differential Revision: https://reviews.llvm.org/D48447 llvm-svn: 335411
* [LoopReroll] Rewrite induction variable rewriting.Eli Friedman2018-06-221-177/+59
| | | | | | | | | | | | | | | | | | | | This gets rid of a bunch of weird special cases; instead, just use SCEV rewriting for everything. In addition to being simpler, this fixes a bug where we would use the wrong stride in certain edge cases. The one bit I'm not quite sure about is the trip count handling, specifically the FIXME about overflow. In general, I think we need to widen the exit condition, but that's probably not profitable if the new type isn't legal, so we probably need a check somewhere. That said, I don't think I'm making the existing problem any worse. As a followup to this, a bunch of IV-related code in root-finding could be cleaned up; with SCEV-based rewriting, there isn't any reason to assume a loop will have exactly one or two PHI nodes. Differential Revision: https://reviews.llvm.org/D45191 llvm-svn: 335400
* [LoopUnswitch]Fix comparison for DomTree updates.Alina Sbirlea2018-06-221-2/+3
| | | | | | | | | | | | | | | | | | | Summary: In LoopUnswitch when replacing a branch Parent -> Succ with a conditional branch Parent -> True & Parent->False, the DomTree updates should insert an edge for each of True/False if True/False are different than Succ, and delete Parent->Succ edge if both are different. The comparison with Succ appears to be incorect, it's comparing with Parent instead. There is no test failing either before or after this change, but it seems to me this is the right way to do the update. Reviewers: chandlerc, kuhar Subscribers: sanjoy, jlebar, llvm-commits Differential Revision: https://reviews.llvm.org/D48457 llvm-svn: 335369
* Revert r335206 "Recommit r333268: [IPSCCP] Use PredicateInfo to propagate ↵Francis Visoiu Mistrih2018-06-211-112/+8
| | | | | | | | | | | facts from cmp instructions." This reverts commit r335206. As discussed here: https://reviews.llvm.org/rL333740, a fix will come tomorrow. In the meanwhile, revert this to fix some bots. llvm-svn: 335272
* Recommit r333268: [IPSCCP] Use PredicateInfo to propagate facts from cmp ↵Florian Hahn2018-06-211-8/+112
| | | | | | | | | | | | | | | | | | | | | instructions. r335150 should resolve the issues with the clang-with-thin-lto-ubuntu and clang-with-lto-ubuntu builders. Original message: This patch updates IPSCCP to use PredicateInfo to propagate facts to true branches predicated by EQ and to false branches predicated by NE. As a follow up, we should be able to extend it to also propagate additional facts about nonnull. Reviewers: davide, mssimpso, dberlin, efriedma Reviewed By: davide, dberlin llvm-svn: 335206
* [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
OpenPOWER on IntegriCloud