summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [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
* [PM] Port LCSSA to the new PM.Easwaran Raman2016-06-091-1/+1
| | | | | | Differential Revision: http://reviews.llvm.org/D21090 llvm-svn: 272294
* Apply most suggestions of clang-tidy's performance-unnecessary-value-paramBenjamin Kramer2016-06-081-1/+1
| | | | | | | Avoids unnecessary copies. All changes audited & pass tests with asan. No functional change intended. llvm-svn: 272190
* [PM] Port of the DepndenceAnalysis to the new PM.Chandler Carruth2016-05-121-8/+8
| | | | | | | | | | | | | Ported DA to the new PM by splitting the former DependenceAnalysis Pass into a DependenceInfo result type and DependenceAnalysisWrapperPass type and adding a new PM-style DependenceAnalysis analysis pass returning the DependenceInfo. Patch by Philip Pfaffe, most of the review by Justin. Differential Revision: http://reviews.llvm.org/D18834 llvm-svn: 269370
* Remove dead include. NFC.Chad Rosier2016-05-051-1/+0
| | | | llvm-svn: 268654
* Add opt-bisect support to additional passes that can be skippedAndrew Kaylor2016-05-031-0/+3
| | | | | | Differential Revision: http://reviews.llvm.org/D19882 llvm-svn: 268457
* LPM: Stop threading `Pass *` through all of the loop utility APIs. NFCJustin Bogner2015-12-151-10/+17
| | | | | | | | | | | | | | | | | | | | | | A large number of loop utility functions take a `Pass *` and reach into it to find out which analyses to preserve. There are a number of problems with this: - The APIs have access to pretty well any Pass state they want, so it's hard to tell what they may or may not do. - Other APIs have copied these and pass around a `Pass *` even though they don't even use it. Some of these just hand a nullptr to the API since the callers don't even have a pass available. - Passes in the new pass manager don't work like the current ones, so the APIs can't be used as is there. Instead, we should explicitly thread the analysis results that we actually care about through these APIs. This is both simpler and more reusable. llvm-svn: 255669
* Test commit access - Fix few missing '.' in comments of LoopInterchange code.Vikram TV2015-12-091-4/+4
| | | | llvm-svn: 255095
* Convert assert(false) into llvm_unreachable where it makes sense.Benjamin Kramer2015-10-251-1/+1
| | | | llvm-svn: 251266
* Scalar: Remove remaining ilist iterator implicit conversionsDuncan P. N. Exon Smith2015-10-131-3/+3
| | | | | | | | | | | | | | | | | | | Remove remaining `ilist_iterator` implicit conversions from LLVMScalarOpts. This change exposed some scary behaviour in lib/Transforms/Scalar/SCCP.cpp around line 1770. This patch changes a call from `Function::begin()` to `&Function::front()`, since the return was immediately being passed into another function that takes a `Function*`. `Function::front()` started to assert, since the function was empty. Note that `Function::end()` does not point at a legal `Function*` -- it points at an `ilist_half_node` -- so the other function was getting garbage before. (I added the missing check for `Function::isDeclaration()`.) Otherwise, no functionality change intended. llvm-svn: 250211
OpenPOWER on IntegriCloud