summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [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
* [PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatibleChandler Carruth2015-09-091-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | with the new pass manager, and no longer relying on analysis groups. This builds essentially a ground-up new AA infrastructure stack for LLVM. The core ideas are the same that are used throughout the new pass manager: type erased polymorphism and direct composition. The design is as follows: - FunctionAAResults is a type-erasing alias analysis results aggregation interface to walk a single query across a range of results from different alias analyses. Currently this is function-specific as we always assume that aliasing queries are *within* a function. - AAResultBase is a CRTP utility providing stub implementations of various parts of the alias analysis result concept, notably in several cases in terms of other more general parts of the interface. This can be used to implement only a narrow part of the interface rather than the entire interface. This isn't really ideal, this logic should be hoisted into FunctionAAResults as currently it will cause a significant amount of redundant work, but it faithfully models the behavior of the prior infrastructure. - All the alias analysis passes are ported to be wrapper passes for the legacy PM and new-style analysis passes for the new PM with a shared result object. In some cases (most notably CFL), this is an extremely naive approach that we should revisit when we can specialize for the new pass manager. - BasicAA has been restructured to reflect that it is much more fundamentally a function analysis because it uses dominator trees and loop info that need to be constructed for each function. All of the references to getting alias analysis results have been updated to use the new aggregation interface. All the preservation and other pass management code has been updated accordingly. The way the FunctionAAResultsWrapperPass works is to detect the available alias analyses when run, and add them to the results object. This means that we should be able to continue to respect when various passes are added to the pipeline, for example adding CFL or adding TBAA passes should just cause their results to be available and to get folded into this. The exception to this rule is BasicAA which really needs to be a function pass due to using dominator trees and loop info. As a consequence, the FunctionAAResultsWrapperPass directly depends on BasicAA and always includes it in the aggregation. This has significant implications for preserving analyses. Generally, most passes shouldn't bother preserving FunctionAAResultsWrapperPass because rebuilding the results just updates the set of known AA passes. The exception to this rule are LoopPass instances which need to preserve all the function analyses that the loop pass manager will end up needing. This means preserving both BasicAAWrapperPass and the aggregating FunctionAAResultsWrapperPass. Now, when preserving an alias analysis, you do so by directly preserving that analysis. This is only necessary for non-immutable-pass-provided alias analyses though, and there are only three of interest: BasicAA, GlobalsAA (formerly GlobalsModRef), and SCEVAA. Usually BasicAA is preserved when needed because it (like DominatorTree and LoopInfo) is marked as a CFG-only pass. I've expanded GlobalsAA into the preserved set everywhere we previously were preserving all of AliasAnalysis, and I've added SCEVAA in the intersection of that with where we preserve SCEV itself. One significant challenge to all of this is that the CGSCC passes were actually using the alias analysis implementations by taking advantage of a pretty amazing set of loop holes in the old pass manager's analysis management code which allowed analysis groups to slide through in many cases. Moving away from analysis groups makes this problem much more obvious. To fix it, I've leveraged the flexibility the design of the new PM components provides to just directly construct the relevant alias analyses for the relevant functions in the IPO passes that need them. This is a bit hacky, but should go away with the new pass manager, and is already in many ways cleaner than the prior state. Another significant challenge is that various facilities of the old alias analysis infrastructure just don't fit any more. The most significant of these is the alias analysis 'counter' pass. That pass relied on the ability to snoop on AA queries at different points in the analysis group chain. Instead, I'm planning to build printing functionality directly into the aggregation layer. I've not included that in this patch merely to keep it smaller. Note that all of this needs a nearly complete rewrite of the AA documentation. I'm planning to do that, but I'd like to make sure the new design settles, and to flesh out a bit more of what it looks like in the new pass manager first. Differential Revision: http://reviews.llvm.org/D12080 llvm-svn: 247167
* [LoopVectorize] Extract InductionInfo into a helper class...James Molloy2015-08-271-2/+2
| | | | | | | | ... and move it into LoopUtils where it can be used by other passes, just like ReductionDescriptor. The API is very similar to ReductionDescriptor - that is, not very nice at all. Sorting these both out will come in a followup. NFC llvm-svn: 246145
* [PM] Port ScalarEvolution to the new pass manager.Chandler Carruth2015-08-171-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change makes ScalarEvolution a stand-alone object and just produces one from a pass as needed. Making this work well requires making the object movable, using references instead of overwritten pointers in a number of places, and other refactorings. I've also wired it up to the new pass manager and added a RUN line to a test to exercise it under the new pass manager. This includes basic printing support much like with other analyses. But there is a big and somewhat scary change here. Prior to this patch ScalarEvolution was never *actually* invalidated!!! Re-running the pass just re-wired up the various other analyses and didn't remove any of the existing entries in the SCEV caches or clear out anything at all. This might seem OK as everything in SCEV that can uses ValueHandles to track updates to the values that serve as SCEV keys. However, this still means that as we ran SCEV over each function in the module, we kept accumulating more and more SCEVs into the cache. At the end, we would have a SCEV cache with every value that we ever needed a SCEV for in the entire module!!! Yowzers. The releaseMemory routine would dump all of this, but that isn't realy called during normal runs of the pipeline as far as I can see. To make matters worse, there *is* actually a key that we don't update with value handles -- there is a map keyed off of Loop*s. Because LoopInfo *does* release its memory from run to run, it is entirely possible to run SCEV over one function, then over another function, and then lookup a Loop* from the second function but find an entry inserted for the first function! Ouch. To make matters still worse, there are plenty of updates that *don't* trip a value handle. It seems incredibly unlikely that today GVN or another pass that invalidates SCEV can update values in *just* such a way that a subsequent run of SCEV will incorrectly find lookups in a cache, but it is theoretically possible and would be a nightmare to debug. With this refactoring, I've fixed all this by actually destroying and recreating the ScalarEvolution object from run to run. Technically, this could increase the amount of malloc traffic we see, but then again it is also technically correct. ;] I don't actually think we're suffering from tons of malloc traffic from SCEV because if we were, the fact that we never clear the memory would seem more likely to have come up as an actual problem before now. So, I've made the simple fix here. If in fact there are serious issues with too much allocation and deallocation, I can work on a clever fix that preserves the allocations (while clearing the data) between each run, but I'd prefer to do that kind of optimization with a test case / benchmark that shows why we need such cleverness (and that can test that we actually make it faster). It's possible that this will make some things faster by making the SCEV caches have higher locality (due to being significantly smaller) so until there is a clear benchmark, I think the simple change is best. Differential Revision: http://reviews.llvm.org/D12063 llvm-svn: 245193
* Fix some comment typos.Benjamin Kramer2015-08-081-11/+11
| | | | llvm-svn: 244402
* Revert "Remove unnecessary null check. NFC."Pete Cooper2015-07-271-0/+3
| | | | | | | | | | | This reverts commit r243167. Duncan pointed out that dyn_cast can return null in these cases, so this was an unsafe commit to make. Sorry for the noise. Worryingly there were no tests which fail... llvm-svn: 243302
* Remove unnecessary null check. NFC.Pete Cooper2015-07-241-3/+0
| | | | | | | | Since both places which set this variable do so with dyn_cast, and not dyn_cast_or_null, its impossible to get a nullptr here, so we can remove the check. llvm-svn: 243167
* Avoid using Loop::getSubLoopsVector.Benjamin Kramer2015-07-131-6/+6
| | | | | | | Passes should never modify it, just use the const version. While there reduce copying in LoopInterchange. No functional change intended. llvm-svn: 242041
* Rename Reduction variables/structures to Recurrence.Tyler Nowicki2015-06-161-4/+4
| | | | | | | | A reduction is a special kind of recurrence. In the loop vectorizer we currently identify basic reductions. Future patches will extend this to identifying basic recurrences. llvm-svn: 239835
* Fix LoopInterchange/reductions.ll test for debug buildsAndrew Kaylor2015-04-241-2/+2
| | | | llvm-svn: 235734
OpenPOWER on IntegriCloud