summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [LoopInterchange] Improve inner exit loop safety checks.Florian Hahn2019-12-041-33/+36
| | | | | | | | | | | | | | | | | | | | The PHI node checks for inner loop exits are too permissive currently. As indicated by an existing comment, we should only allow LCSSA PHI nodes that are part of reductions or are only used outside of the loop nest. We ensure this by checking the users of the LCSSA PHIs. Specifically, it is not safe to use an exiting value from the inner loop in the latch of the outer loop. It also moves the inner loop exit check before the outer loop exit check. Fixes PR43473. Reviewers: efriedma, mcrosier Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D68144
* [LoopInterchange] Adjust assertions when updating successors.Florian Hahn2019-11-241-19/+35
| | | | | | | | | | | Currently the assertion in updateSuccessor is overly strict in some cases and overly relaxed in other cases. For branches to the inner and outer loop preheader it is too strict, because they can either be unconditional branches or conditional branches with duplicate targets. Both cases are fine and we can allow updating multiple successors. On the other hand, we have to at least update one successor. This patch adds such an assertion.
* 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
* [LoopInterchange] Only skip PHIs with incoming values from the inner loop.Florian Hahn2019-11-121-7/+7
| | | | | | | | | | | | | | Currently we have limited support for outer loops with multiple basic blocks after the inner loop exit. But the current checks for creating PHIs for loop exit values only assumes the header and latches of the outer loop. It is better to just skip incoming values defined in the original inner loops. Those are handled earlier. Reviewers: efriedma, mcrosier Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D70059
* [LoopInterchange] Drop unused splitInnerLoopHeader declaration.Florian Hahn2019-09-111-1/+0
| | | | llvm-svn: 371601
* [LoopInterchange] Properly move condition, induction increment and ops to latch.Florian Hahn2019-09-111-11/+50
| | | | | | | | | | | | | | | | | | | | | | | Currently we only rely on the induction increment to come before the condition to ensure the required instructions get moved to the new latch. This patch duplicates and moves the required instructions to the newly created latch. We move the condition to the end of the new block, then process its operands. We stop at operands that are defined outside the loop, or are the induction PHI. We duplicate the instructions and update the uses in the moved instructions, to ensure other users remain intact. See the added test2 for such an example. Reviewers: efriedma, mcrosier Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D67367 llvm-svn: 371595
* Delete dead storesFangrui Song2019-07-121-3/+1
| | | | llvm-svn: 365903
* [LoopInterchange] Fix handling of LCSSA nodes defined in headers and latches.Florian Hahn2019-05-261-22/+64
| | | | | | | | | | | | | | | | | | The code to preserve LCSSA PHIs currently only properly supports reduction PHIs and PHIs for values defined outside the latches. This patch improves the LCSSA PHI handling to cover PHIs for values defined in the latches. Fixes PR41725. Reviewers: efriedma, mcrosier, davide, jdoerfert Reviewed By: jdoerfert Differential Revision: https://reviews.llvm.org/D61576 llvm-svn: 361743
* Revert [LOOPINFO] Extend Loop object to add utilities to get the loop ↵Kit Barton2019-05-231-1/+28
| | | | | | | | bounds, step, induction variable, and guard branch. This reverts r361517 (git commit 2049e4dd8f61100f88f14db33bd95d197bcbfbbc) llvm-svn: 361553
* [LOOPINFO] Extend Loop object to add utilities to get the loop bounds, ↵Kit Barton2019-05-231-28/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | step, induction variable, and guard branch. Summary: This PR extends the loop object with more utilities to get loop bounds, step, induction variable, and guard branch. There already exists passes which try to obtain the loop induction variable in their own pass, e.g. loop interchange. It would be useful to have a common area to get these information. Moreover, loop fusion (https://reviews.llvm.org/D55851) is planning to use getGuard() to extend the kind of loops it is able to fuse, e.g. rotated loop with non-constant upper bound, which would have a loop guard. /// Example: /// for (int i = lb; i < ub; i+=step) /// <loop body> /// --- pseudo LLVMIR --- /// beforeloop: /// guardcmp = (lb < ub) /// if (guardcmp) goto preheader; else goto afterloop /// preheader: /// loop: /// i1 = phi[{lb, preheader}, {i2, latch}] /// <loop body> /// i2 = i1 + step /// latch: /// cmp = (i2 < ub) /// if (cmp) goto loop /// exit: /// afterloop: /// /// getBounds /// getInitialIVValue --> lb /// getStepInst --> i2 = i1 + step /// getStepValue --> step /// getFinalIVValue --> ub /// getCanonicalPredicate --> '<' /// getDirection --> Increasing /// getGuard --> if (guardcmp) goto loop; else goto afterloop /// getInductionVariable --> i1 /// getAuxiliaryInductionVariable --> {i1} /// isCanonical --> false Committed on behalf of @Whitney (Whitney Tsang). Reviewers: kbarton, hfinkel, dmgreen, Meinersbur, jdoerfert, syzaara, fhahn Reviewed By: kbarton Subscribers: tvvikram, bmahjour, etiotto, fhahn, jsji, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D60565 llvm-svn: 361517
* [MemorySSA] Teach LoopSimplify to preserve MemorySSA.Alina Sbirlea2019-05-081-2/+4
| | | | | | | | | | | | | | | Summary: Preserve MemorySSA in LoopSimplify, in the old pass manager, if the analysis is available. Do not preserve it in the new pass manager. Update tests. Subscribers: nemanjai, jlebar, javed.absar, Prazek, kbarton, zzheng, jsji, llvm-commits, george.burgess.iv, chandlerc Tags: #llvm Differential Revision: https://reviews.llvm.org/D60833 llvm-svn: 360270
* [NFC] BasicBlock: refactor changePhiUses() out of replacePhiUsesWith(), use itRoman Lebedev2019-05-051-14/+8
| | | | | | | | | | | | | | | | | | | | | Summary: It is a common thing to loop over every `PHINode` in some `BasicBlock` and change old `BasicBlock` incoming block to a new `BasicBlock` incoming block. `replaceSuccessorsPhiUsesWith()` already had code to do that, it just wasn't a function. So outline it into a new function, and use it. Reviewers: chandlerc, craig.topper, spatel, danielcdh Reviewed By: craig.topper Subscribers: llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D61013 llvm-svn: 359996
* [NFC] PHINode: introduce replaceIncomingBlockWith() function, use itRoman Lebedev2019-05-051-7/+2
| | | | | | | | | | | | | | | | | | | | Summary: There is `PHINode::getBasicBlockIndex()`, `PHINode::setIncomingBlock()` and `PHINode::getNumOperands()`, but no function to replace every specified `BasicBlock*` predecessor with some other specified `BasicBlock*`. Clearly, there are a lot of places that could use that functionality. Reviewers: chandlerc, craig.topper, spatel, danielcdh Reviewed By: craig.topper Subscribers: llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D61011 llvm-svn: 359995
* 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
* [LoopInterchange] Support reductions across inner and outer loop.Florian Hahn2018-11-081-44/+130
| | | | | | | | | | | | | | | | | | | | | This patch adds logic to detect reductions across the inner and outer loop by following the incoming values of PHI nodes in the outer loop. If the incoming values take part in a reduction in the inner loop or come from outside the outer loop, we found a reduction spanning across inner and outer loop. With this change, ~10% more loops are interchanged in the LLVM test-suite + SPEC2006. Fixes https://bugs.llvm.org/show_bug.cgi?id=30472 Reviewers: mcrosier, efriedma, karthikthecool, davide, hfinkel, dmgreen Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D43245 llvm-svn: 346438
* [LoopInterchange] Fix unused variables in release buildFlorian Hahn2018-11-011-0/+2
| | | | llvm-svn: 345881
* [LoopInterchange] Remove support for inner-only reductions.Florian Hahn2018-11-011-105/+20
| | | | | | | | | | | | | | | | | | | | | | Inner-loop only reductions require additional checks to make sure they form a load-phi-store cycle across inner and outer loop. Otherwise the reduction value is not properly preserved. This patch disables interchanging such loops for now, as it causes miscompiles in some cases and it seems to apply only for a tiny amount of loops. Across the test-suite, SPEC2000 and SPEC2006, 61 instead of 62 loops are interchange with inner loop reduction support disabled. With -loop-interchange-threshold=-1000, 3256 instead of 3267. See the discussion and history of D53027 for an outline of how such legality checks could look like. Reviewers: efriedma, mcrosier, davide Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D53027 llvm-svn: 345877
* [LoopInterchange] Remove unused variable PreserveLCSSA (NFC).Florian Hahn2018-10-031-1/+0
| | | | llvm-svn: 343676
* Recommit r343308: [LoopInterchange] Turn into a loop pass.Florian Hahn2018-10-011-42/+14
| | | | llvm-svn: 343450
* Revert r343308: [LoopInterchange] Turn into a loop pass.Florian Hahn2018-09-281-14/+43
| | | | llvm-svn: 343310
* [LoopInterchange] Turn into a loop pass.Florian Hahn2018-09-281-43/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch turns LoopInterchange into a loop pass. It now only considers top-level loops and tries to move the innermost loop to the optimal position within the loop nest. By only looking at top-level loops, we might miss a few opportunities the function pass would get (e.g. if we have a loop nest of 3 loops, in the function pass we might process loops at level 1 and 2 and move the inner most loop to level 1, and then we process loops at levels 0, 1, 2 and interchange again, because we now have a different inner loop). But I think it would be better to handle such cases by picking the best inner loop from the start and avoid re-visiting the same loops again. The biggest advantage of it being a function pass is that it interacts nicely with the other loop passes. Without this patch, there are some performance regressions on AArch64 with loop interchanging enabled, where no loops were interchanged, but we missed out on some other loop optimizations. It also removes the SimplifyCFG run. We are just changing branches, so the CFG should not be more complicated, besides the additional 'unique' preheaders this pass might create. Reviewers: chandlerc, efriedma, mcrosier, javed.absar, xbolva00 Reviewed By: xbolva00 Differential Revision: https://reviews.llvm.org/D51702 llvm-svn: 343308
* [LoopInterchange] Preserve LCSSA.Florian Hahn2018-09-261-18/+54
| | | | | | | | | | | | | | | | | | This patch extends LoopInterchange to move LCSSA to the right place after interchanging. This is required for LoopInterchange to become a function pass. An alternative to the manual moving of the PHIs, we could also re-form the LCSSA phis for a set of interchanged loops, but that's more expensive. Reviewers: efriedma, mcrosier, davide Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D52154 llvm-svn: 343132
* [LoopInterchange] Preserve ScalarEvolution, by forgetting about interchanged ↵Florian Hahn2018-09-141-0/+5
| | | | | | | | | | | | | | | | | | | | | | loops. As preparation for LoopInterchange becoming a loop pass, it needs to preserve ScalarEvolution. Even though interchanging should not change the trip count of the loop, it modifies loop entry, latch and exit blocks. I added -verify-scev to some loop interchange tests, but the verification does not catch problems caused by missing invalidation of SE in loop interchange, as the trip counts themselves do not change. So there might be potential to make the SE verification covering more stuff in the future. Reviewers: mkazantsev, efriedma, karthikthecool Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D52026 llvm-svn: 342209
* [LoopInterchange] Cleanup unused variables.Florian Hahn2018-09-061-8/+2
| | | | llvm-svn: 341537
* [LoopInterchange] Move preheader creation to transform stage and simplify.Florian Hahn2018-09-061-25/+18
| | | | | | | | | | | | | | | | | | | There is no need to create preheaders in the analysis stage, we only need them when adjusting the branches. Also, the only cases we need to create our own preheaders is when they have more than 1 predecessors or PHI nodes (even with only 1 predecessor, we could have an LCSSA phi node). I have simplified the conditions and added some assertions to be sure. Because we know the inner and outer loop need to be tightly nested, it is sufficient to check if the inner loop preheader is the outer loop header to check if we need to create a new preheader. Reviewers: efriedma, mcrosier, karthikthecool Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D51703 llvm-svn: 341533
* [IR] Begin removal of TerminatorInst by removing successor manipulation.Chandler Carruth2018-08-261-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The core get and set routines move to the `Instruction` class. These routines are only valid to call on instructions which are terminators. The iterator and *generic* range based access move to `CFG.h` where all the other generic successor and predecessor access lives. While moving the iterator here, simplify it using the iterator utilities LLVM provides and updates coding style as much as reasonable. The APIs remain pointer-heavy when they could better use references, and retain the odd behavior of `operator*` and `operator->` that is common in LLVM iterators. Adjusting this API, if desired, should be a follow-up step. Non-generic range iteration is added for the two instructions where there is an especially easy mechanism and where there was code attempting to use the range accessor from a specific subclass: `indirectbr` and `br`. In both cases, the successors are contiguous operands and can be easily iterated via the operand list. This is the first major patch in removing the `TerminatorInst` type from the IR's instruction type hierarchy. This change was discussed in an RFC here and was pretty clearly positive: http://lists.llvm.org/pipermail/llvm-dev/2018-May/123407.html There will be a series of much more mechanical changes following this one to complete this move. Differential Revision: https://reviews.llvm.org/D47467 llvm-svn: 340698
* [LoopInterchange] Move PHI handling to adjustLoopBranches.Florian Hahn2018-06-191-30/+40
| | | | | | | | | | | | | | | | | | | | | This patch moves the logic to handle reduction PHI nodes to the end of adjustLoopBranches. Reduction PHI nodes in the outer loop header can be moved to the inner loop header and reduction PHI nodes from the inner loop header can be moved to the outer loop header. In the latter situation, we have to deal with 1 kind of PHI nodes: PHI nodes that are part of inner loop-only reductions. We can replace the PHI node with the value coming from outside the inner loop. Reviewers: mcrosier, efriedma, karthikthecool Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D46198 llvm-svn: 335027
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-73/+81
| | | | | | | | | | | | | | | | 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
* [LoopInterchange] Update some loops to use range base for loops (NFC).Florian Hahn2018-05-021-30/+24
| | | | llvm-svn: 331342
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-2/+2
| | | | | | | | | | | | | | | | We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
* [LoopInterchange] Allow some loops with PHI nodes in the exit block.Florian Hahn2018-04-271-23/+48
| | | | | | | | | | | | | | | | | | | | We currently support LCSSA PHI nodes in the outer loop exit, if their incoming values do not come from the outer loop latch or if the outer loop latch has a single predecessor. In that case, the outer loop latch will be executed only if the inner loop gets executed. If we have multiple predecessors for the outer loop latch, it may be executed even if the inner loop does not get executed. This is a first step to support the case described in https://bugs.llvm.org/show_bug.cgi?id=30472 Reviewers: efriedma, karthikthecool, mcrosier Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D43237 llvm-svn: 331037
* [LoopInterchange] Ignore debug intrinsics during legality checks.Florian Hahn2018-04-261-3/+3
| | | | | | | | | | | | Reviewers: aprantl, mcrosier, karthikthecool Reviewed By: aprantl Subscribers: mattd, vsk, #debug-info, llvm-commits Differential Revision: https://reviews.llvm.org/D45379 llvm-svn: 330931
* [LoopInterchange] Use getExitBlock()/getExitingBlock instead of manual impl.Florian Hahn2018-04-251-33/+27
| | | | | | | | | | | | | | | This also means we have to check if the latch is the exiting block now, as `transform` expects the latches to be the exiting blocks too. https://bugs.llvm.org/show_bug.cgi?id=36586 Reviewers: efriedma, davide, karthikthecool Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D45279 llvm-svn: 330806
* [LoopInterchange] Make isProfitableForVectorization slightly more conservative.Florian Hahn2018-04-241-1/+2
| | | | | | | | | | | | | | | | After D43236, we started interchanging loops with empty dependence matrices. In isProfitableForVectorization, we try to determine if interchanging makes the loop dependences more friendly to the vectorizer. If there are no dependences, we should not interchange, based on that heuristic. Reviewers: efriedma, mcrosier, karthikthecool, blitz.opensource Reviewed By: mcrosier Differential Revision: https://reviews.llvm.org/D45208 llvm-svn: 330738
* [LoopInterchange] Do not change LI for BBs in child loops.Florian Hahn2018-04-231-0/+3
| | | | | | | | | | | | | | If a loop with child loops becomes our new inner loop after interchanging, we only need to update LoopInfo for the blocks defined in the old outer loop. BBs in child loops will stay there. Reviewers: efriedma, karthikthecool, mcrosier Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D45970 llvm-svn: 330653
* [LoopInterchange] Add stats counter for number of interchanged loops.Florian Hahn2018-04-051-0/+4
| | | | | | | | | | Reviewers: samparker, karthikthecool, blitz.opensource Reviewed By: samparker Differential Revision: https://reviews.llvm.org/D45209 llvm-svn: 329269
* [LoopInterchange] Preserve LoopInfo after interchanging.Florian Hahn2018-04-051-13/+72
| | | | | | | | | | | | | | LoopInterchange relies on LoopInfo being up-to-date, so we should preserve it after interchanging. This patch updates restructureLoops to move the BBs of the interchanged loops to the right place. Reviewers: davide, efriedma, karthikthecool, mcrosier Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D45278 llvm-svn: 329264
* [LoopInterchange] Add remark for calls preventing interchanging.Florian Hahn2018-04-031-0/+7
| | | | | | | | | | | | | | It also updates test/Transforms/LoopInterchange/call-instructions.ll to use accesses where we can prove dependence after D35430. Reviewers: sebpop, karthikthecool, blitz.opensource Reviewed By: sebpop Differential Revision: https://reviews.llvm.org/D45206 llvm-svn: 329111
* Transforms: Introduce Transforms/Utils.h rather than spreading the ↵David Blaikie2018-03-281-0/+1
| | | | | | | | | declarations amongst Scalar.h and IPO.h Fixes layering - Transforms/Utils shouldn't depend on including a Scalar or IPO header, because Scalar and IPO depend on Utils. llvm-svn: 328717
* DA: remove uses of GEP, only ask SCEVSebastian Pop2018-03-061-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | It's been quite some time the Dependence Analysis (DA) is broken, as it uses the GEP representation to "identify" multi-dimensional arrays. It even wrongly detects multi-dimensional arrays in single nested loops: from test/Analysis/DependenceAnalysis/Coupled.ll, example @couple6 ;; for (long int i = 0; i < 50; i++) { ;; A[i][3*i - 6] = i; ;; *B++ = A[i][i]; DA used to detect two subscripts, which makes no sense in the LLVM IR or in C/C++ semantics, as there are no guarantees as in Fortran of subscripts not overlapping into a next array dimension: maximum nesting levels = 1 SrcPtrSCEV = %A DstPtrSCEV = %A using GEPs subscript 0 src = {0,+,1}<nuw><nsw><%for.body> dst = {0,+,1}<nuw><nsw><%for.body> class = 1 loops = {1} subscript 1 src = {-6,+,3}<nsw><%for.body> dst = {0,+,1}<nuw><nsw><%for.body> class = 1 loops = {1} Separable = {} Coupled = {1} With the current patch, DA will correctly work on only one dimension: maximum nesting levels = 1 SrcSCEV = {(-2424 + %A)<nsw>,+,1212}<%for.body> DstSCEV = {%A,+,404}<%for.body> subscript 0 src = {(-2424 + %A)<nsw>,+,1212}<%for.body> dst = {%A,+,404}<%for.body> class = 1 loops = {1} Separable = {0} Coupled = {} This change removes all uses of GEP from DA, and we now only rely on the SCEV representation. The patch does not turn on -da-delinearize by default, and so the DA analysis will be more conservative in the case of multi-dimensional memory accesses in nested loops. I disabled some interchange tests, as the DA is not able to disambiguate the dependence anymore. To make DA stronger, we may need to compute a bound on the number of iterations based on the access functions and array dimensions. The patch cleans up all the CHECKs in test/Transforms/LoopInterchange/*.ll to avoid checking for snippets of LLVM IR: this form of checking is very hard to maintain. Instead, we now check for output of the pass that are more meaningful than dozens of lines of LLVM IR. Some tests now require -debug messages and thus only enabled with asserts. Patch written by Sebastian Pop and Aditya Kumar. Differential Revision: https://reviews.llvm.org/D35430 llvm-svn: 326837
* [LoopInterchange] Loops with empty dependency matrix are safe.Florian Hahn2018-02-261-3/+0
| | | | | | | | | | | | | | | | | | | | The dependency matrix is only empty if no conflicting load/store instructions have been found. In that case, it is safe to interchange. For the LLVM test-suite, after this change around 1900 loops are interchanged, whereas it is 15 before this change. On cortex-a57, this gives an improvement of -0.57% on the geomean execution time of SPEC2006, SPEC2000 and the test-suite. There are a few small perf regressions, but I think we can improve on those by making the cost model better. Reviewers: karthikthecool, mcrosier Reviewed by: karthikthecool Differential Revision: https://reviews.llvm.org/D43236 llvm-svn: 326077
* [LoopInterchange] Incrementally update the dominator tree.Florian Hahn2018-02-141-34/+40
| | | | | | | | | | | | | We can use incremental dominator tree updates to avoid re-calculating the dominator tree after interchanging 2 loops. Reviewers: dmgreen, kuhar Reviewed By: kuhar Differential Revision: https://reviews.llvm.org/D43176 llvm-svn: 325122
* [LoopInterchange] Check number of latch successors before accessing them.Florian Hahn2018-02-131-1/+1
| | | | | | | | | | | | | | | | In cases where the OuterMostLoopLatchBI only has a single successor, accessing the second successor will fail. This fixes a failure when building the test-suite with loop-interchange enabled. Reviewers: mcrosier, karthikthecool, davide Reviewed by: karthikthecool Differential Revision: https://reviews.llvm.org/D42906 llvm-svn: 324994
* [LoopInterchange] Simplify splitInnerLoopHeader logic (NFC).Florian Hahn2018-02-121-11/+4
| | | | | | | We can use SplitBlock for both cases, which makes the code slightly simpler and updates both LoopInfo and the dominator tree. llvm-svn: 324881
* [LoopInterchange] Fix phi node ordering miscompile.David Green2017-10-211-1/+6
| | | | | | | | | | | The way that splitInnerLoopHeader splits blocks requires that the induction PHI will be the first PHI in the inner loop header. This makes sure that is actually the case when there are both IV and reduction phis. Differential Revision: https://reviews.llvm.org/D38682 llvm-svn: 316261
* [Transforms] Fix some Clang-tidy modernize and Include What You Use ↵Eugene Zelenko2017-10-161-47/+48
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 315940
* [NFC] Convert OptimizationRemarkEmitter old emit() calls to new closureVivek Pandya2017-10-111-86/+102
| | | | | | | | | | | | | | parameterized emit() calls Summary: This is not functional change to adopt new emit() API added in r313691. Reviewed By: anemet Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D38285 llvm-svn: 315476
* Rename OptimizationDiagnosticInfo.* to OptimizationRemarkEmitter.*Adam Nemet2017-10-091-1/+1
| | | | | | | Sync it up with the name of the class actually defined here. This has been bothering me for a while... llvm-svn: 315249
* [LoopInterchange] Skip zext instructions when looking for induction var.Florian Hahn2017-08-251-1/+2
| | | | | | | | | | | | | | | | | | Summary: SimplifyIndVar may introduce zext instructions to widen arguments of the loop exit check. They should not prevent us from splitting the loop at the induction variable, but maybe the check should be more conservative, e.g. making sure it only extends arguments used by a comparison? Reviewers: karthikthecool, mcrosier, mzolotukhin Reviewed By: mcrosier Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D34879 llvm-svn: 311783
* [LoopInterchange] Do not interchange loops with function calls.Florian Hahn2017-07-311-0/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Without any information about the called function, we cannot be sure that it is safe to interchange loops which contain function calls. For example there could be dependences that prevent interchanging between accesses in the called function and the loops. Even functions without any parameters could cause problems, as they could access memory using global pointers. For now, I think it is only safe to interchange loops with calls marked as readnone. With this patch, the LLVM test suite passes with `-O3 -mllvm -enable-loopinterchange` and LoopInterchangeProfitability::isProfitable returning true for all loops. check-llvm and check-clang also pass when bootstrapped in a similar fashion, although only 3 loops got interchanged. Reviewers: karthikthecool, blitz.opensource, hfinkel, mcrosier, mkuper Reviewed By: mcrosier Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D35489 llvm-svn: 309547
OpenPOWER on IntegriCloud