summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [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
* [LoopInterchange] Update code to use range-based for loops (NFC).Florian Hahn2017-07-241-28/+21
| | | | | | | | | | | | | | | | Summary: The remaining non range-based for loops do not iterate over full ranges, so leave them as they are. Reviewers: karthikthecool, blitz.opensource, mcrosier, mkuper, aemerson Reviewed By: aemerson Subscribers: aemerson, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D35777 llvm-svn: 308872
* [LoopInterchange] Add some optimization remarks.Florian Hahn2017-07-151-9/+110
| | | | | | | | | | | | Reviewers: anemet, karthikthecool, blitz.opensource Reviewed By: anemet Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D35122 llvm-svn: 308094
* [LoopInterchange] Add more debug messages to currentLimitations(). Florian Hahn2017-07-031-10/+34
| | | | | | | | | | | | | | Summary: This makes it easier to find out which limitation prevented this pass from doing its work. Reviewers: karthikthecool, mzolotukhin, efriedma, mcrosier Reviewed By: mcrosier Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D34940 llvm-svn: 307035
* Remove inclusion of SSAUpdater from several passes.Davide Italiano2017-01-291-1/+1
| | | | | | | | It is, in fact, unused. Found while reviewing Danny's new SSAUpdater and porting passes to it to see how the new API looked like. llvm-svn: 293407
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-0/+1
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Remove the AssumptionCacheHal Finkel2016-12-151-1/+0
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* Fix a bug found by inspection by PVS-Studio.Chandler Carruth2016-11-031-1/+1
| | | | | | | | | | | This condition is trivially always true prior to the change. The comment at the call site makes it clear that we expect *all* of these to be '=', 'S', or 'I' so fix the code. We have a bug I will update to track the fact that Clang doesn't warn on this: http://llvm.org/PR13101 llvm-svn: 285930
* [LoopInterchange] Track all dependencies, not just anti dependencies.Chad Rosier2016-09-211-50/+47
| | | | | | | | | | | | | | | | | Currently, we give up on loop interchange if we encounter a flow dependency anywhere in the loop list. Worse yet, we don't even track output dependencies. This patch updates the dependency matrix computation to track flow and output dependencies in the same way we track anti dependencies. This improves an internal workload by 2.2x. Note the loop interchange pass is off by default and it can be enabled with '-mllvm -enable-loopinterchange' Differential Revision: https://reviews.llvm.org/D24564 llvm-svn: 282101
* [LoopInterchange] Various cleanup. NFC.Chad Rosier2016-09-211-23/+19
| | | | llvm-svn: 282071
* [LoopInterchange] Typo. NFC.Chad Rosier2016-09-141-4/+4
| | | | llvm-svn: 281501
* [LoopInterchange] Add CL option to override cost threshold.Chad Rosier2016-09-141-3/+6
| | | | | | Mostly useful for getting consistent lit testing. llvm-svn: 281500
* [LoopInterchange] Cleanup debug whitespace. NFC.Chad Rosier2016-09-141-4/+4
| | | | llvm-svn: 281497
* [LoopInterchange] Minor refactor. NFC.Chad Rosier2016-09-131-12/+11
| | | | llvm-svn: 281334
* Don't use else if after return. Tidy comments. NFC.Chad Rosier2016-09-131-5/+3
| | | | llvm-svn: 281331
* Typo. NFC.Chad Rosier2016-09-131-3/+3
| | | | llvm-svn: 281330
* [LoopInterchange] Tidy up and remove unnecessary dyn_casts. NFC.Chad Rosier2016-09-131-13/+12
| | | | llvm-svn: 281328
* [LoopInterchange] Improve debug output. NFC.Chad Rosier2016-09-121-2/+2
| | | | llvm-svn: 281212
* Typo. NFC.Chad Rosier2016-09-071-1/+1
| | | | llvm-svn: 280834
* [LoopInterchange] Improve debug output. NFC.Chad Rosier2016-09-071-6/+6
| | | | llvm-svn: 280820
* [LoopInterchange] Improve debug output. NFC.Chad Rosier2016-09-071-4/+6
| | | | llvm-svn: 280819
* Use range algorithms instead of unpacking begin/endDavid Majnemer2016-08-111-2/+2
| | | | | | No functionality change is intended. llvm-svn: 278417
* [Loop Vectorizer] Handling loops FP induction variables.Elena Demikhovsky2016-07-241-1/+1
| | | | | | | | | | | | | | | | Allowed loop vectorization with secondary FP IVs. Like this: float *A; float x = init; for (int i=0; i < N; ++i) { A[i] = x; x -= fp_inc; } The auto-vectorization is possible when the induction binary operator is "fast" or the function has "unsafe" attribute. Differential Revision: https://reviews.llvm.org/D21330 llvm-svn: 276554
* Apply clang-tidy's modernize-loop-convert to most of lib/Transforms.Benjamin Kramer2016-06-261-8/+4
| | | | | | Only minor manual fixes. No functionality change intended. llvm-svn: 273808
* Switch more loops to be range-basedDavid Majnemer2016-06-241-8/+7
| | | | | | | This makes the code a little more concise, no functional change is intended. llvm-svn: 273644
* Delete more dead code.Rafael Espindola2016-06-221-16/+0
| | | | | | Found by gcc 6. llvm-svn: 273402
* Delete some dead code.Rafael Espindola2016-06-211-8/+0
| | | | | | Found by gcc 6. llvm-svn: 273303
OpenPOWER on IntegriCloud