summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Use SmallPtrSet explicitly for SmallSets with pointer types (NFC).Florian Hahn2018-06-121-7/+7
| | | | | | | | | | | | | | Currently SmallSet<PointerTy> inherits from SmallPtrSet<PointerTy>. This patch replaces such types with SmallPtrSet, because IMO it is slightly clearer and allows us to get rid of unnecessarily including SmallSet.h Reviewers: dblaikie, craig.topper Reviewed By: dblaikie Differential Revision: https://reviews.llvm.org/D47836 llvm-svn: 334492
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-16/+21
| | | | | | | | | | | | | | | | 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
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-15/+15
| | | | | | | | | | | | | | | | 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
* 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
* Add MemorySSA as loop dependency, disabled by default [NFC].Alina Sbirlea2017-11-211-1/+2
| | | | | | | | | | | | | | | | | Summary: First step in adding MemorySSA as dependency for loop pass manager. Adding the dependency under a flag. New pass manager: MSSA pointer in LoopStandardAnalysisResults can be null. Legacy and new pass manager: Use cl::opt EnableMSSALoopDependency. Disabled by default. Reviewers: sanjoy, davide, gberry Subscribers: mehdi_amini, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D40274 llvm-svn: 318772
* [Transforms] Fix some Clang-tidy modernize and Include What You Use ↵Eugene Zelenko2017-10-161-14/+26
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 315940
* Add a getPointerOperandType() helper to LoadInst and StoreInst; NFCSanjoy Das2017-04-181-2/+1
| | | | | | I will use this in a later change. llvm-svn: 300613
* Add a wrapper around copy_if in STLExtras; NFCSanjoy Das2017-02-211-9/+9
| | | | | | I will add one more use for this in a later change. llvm-svn: 295685
* [PM] Port LoopLoadElimination to the new pass manager and wire it intoChandler Carruth2017-01-271-27/+60
| | | | | | | | | | | the main pipeline. This is a very straight forward port. Nothing weird or surprising. This brings the number of missing passes from the new PM's pipeline down to three. llvm-svn: 293249
* Fix LoopLoadElimination to keep original alignment on the inital hoisted storeMehdi Amini2017-01-061-1/+3
| | | | | | | | | | | This is fixing a bug where Loop Vectorization is widening a load but with a lower alignment. Hoisting the load without propagating the alignment will allow inst-combine to later deduce a higher alignment that what the pointer actually is. Differential Revision: https://reviews.llvm.org/D28408 llvm-svn: 291281
* [LoopVersioning] Require loop-simplify form for loop versioning.Florian Hahn2016-12-191-0/+5
| | | | | | | | | | | | | | | | Summary: Requiring loop-simplify form for loop versioning ensures that the runtime check block always dominates the exit block. This patch closes #30958 (https://llvm.org/bugs/show_bug.cgi?id=30958). Reviewers: silviu.baranga, hfinkel, anemet, ashutosh.nema Subscribers: ashutosh.nema, mzolotukhin, efriedma, hfinkel, llvm-commits Differential Revision: https://reviews.llvm.org/D27469 llvm-svn: 290116
* Fix some Clang-tidy and Include What You Use warnings; other minor fixes (NFC).Eugene Zelenko2016-11-301-4/+25
| | | | | | This preparation to remove SetVector.h dependency on SmallSet.h. llvm-svn: 288256
* LoopLoadElimination should preserve GlobalsAA.Eli Friedman2016-09-161-0/+2
| | | | | | | | Avoids losing GlobalsAA in the standard pass pipeline. Differential Revision: https://reviews.llvm.org/D24094 llvm-svn: 281757
* Use the range variant of transform instead of unpacking begin/endDavid Majnemer2016-08-121-1/+1
| | | | | | No functionality change is intended. llvm-svn: 278476
* Use range algorithms instead of unpacking begin/endDavid Majnemer2016-08-111-4/+3
| | | | | | No functionality change is intended. llvm-svn: 278417
* Rename LoopAccessAnalysis to LoopAccessLegacyAnalysis /NFCXinliang David Li2016-07-081-3/+3
| | | | llvm-svn: 274927
* [PM] refactor LoopAccessInfo code part-2Xinliang David Li2016-07-011-4/+4
| | | | | | Differential Revision: http://reviews.llvm.org/D21636 llvm-svn: 274334
* [LLE] Don't hoist conditionally executed loadsAdam Nemet2016-06-281-0/+11
| | | | | | | | If the load is conditional we can't hoist its 0-iteration instance to the preheader because that would make it unconditional. Thus we would access a memory location that the original loop did not access. llvm-svn: 273991
* [LAA] Default getInfo to not speculate symbolic strides. NFCAdam Nemet2016-06-161-1/+1
| | | | | | | Soon we won't be passing Strides to getInfo and then we'll have fewer call sites to update. llvm-svn: 272878
* Revert r272194 No need for it if loop Analysis Manager is usedXinliang David Li2016-06-091-1/+1
| | | | llvm-svn: 272243
* [PM] Refector LoopAccessInfo analysis code Xinliang David Li2016-06-081-1/+1
| | | | | | | | This is the preparation patch to port the analysis to new PM Differential Revision: http://reviews.llvm.org/D20560 llvm-svn: 272194
* [LAA] Rename "isStridedPtr" with "getPtrStride". NFC.Denis Zobnin2016-05-101-2/+2
| | | | | | | Changing misleading function name was approved in http://reviews.llvm.org/D17268. Patch by Roman Shirokiy. llvm-svn: 269021
* [LLE] Fix typo from r263058Adam Nemet2016-05-021-1/+1
| | | | | | | | This was meant to check unit stride for both the load and the store. Thanks to Roman Shirokiy for noticing this. llvm-svn: 268251
* Re-commit optimization bisect support (r267022) without new pass manager ↵Andrew Kaylor2016-04-221-0/+3
| | | | | | | | | | support. The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the OptBisect handling). Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267231
* Revert "Initial implementation of optimization bisect support."Vedant Kumar2016-04-221-3/+0
| | | | | | | | This reverts commit r267022, due to an ASan failure: http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549 llvm-svn: 267115
* Initial implementation of optimization bisect support.Andrew Kaylor2016-04-211-0/+3
| | | | | | | | | | | | This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to track down test failures that are caused by incorrect optimizations. The bisection is enabled using a new command line option (-opt-bisect-limit). Individual passes that may be skipped call the OptBisect object (via an LLVMContext) to see if they should be skipped based on the bisect limit. A finer level of control (disabling individual transformations) can be managed through an addition OptBisect method, but this is not yet used. The skip checking in this implementation is based on (and replaces) the skipOptnoneFunction check. Where that check was being called, a new call has been inserted in its place which checks the bisect limit and the optnone attribute. A new function call has been added for module and SCC passes that behaves in a similar way. Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267022
* [LLE] Check for mismatching types between the store and the load earlierAdam Nemet2016-03-241-4/+6
| | | | | | | | | | | | | | | isDependenceDistanceOfOne asserts that the store and the load access through the same type. This function is also used by removeDependencesFromMultipleStores so we need to make sure we filter out mismatching types before reaching this point. Now we do this when the initial candidates are gathered. This is a refinement of the fix made in r262267. Fixes PR27048. llvm-svn: 264313
* [LLE] Add missed LoopSimplify dependenceAdam Nemet2016-03-101-0/+3
| | | | | | | | | The code assumed that we always had a preheader without making the pass dependent on LoopSimplify. Thanks to Mattias Eriksson V for reporting this. llvm-svn: 263173
* [LLE] Add missing check for unit strideAdam Nemet2016-03-091-5/+13
| | | | | | | | | | I somehow missed this. The case in GCC (global_alloc) was similar to the new testcase except it had an array of structs rather than a two dimensional array. Fixes RP26885. llvm-svn: 263058
* [LLE] Fix a commentAdam Nemet2016-02-291-3/+3
| | | | llvm-svn: 262270
* [LLE] Fix SingleSource/Benchmarks/Polybench/stencils/jacobi-2d-imper with PollyAdam Nemet2016-02-291-0/+5
| | | | | | | | | We can actually have dependences between accesses with different underlying types. Bail in this case. A test will follow shortly. llvm-svn: 262267
* [LoopLoadElim] Don't allow versioning when optForSizeAdam Nemet2016-02-051-2/+9
| | | | | | This was requested in the review of D16300. llvm-svn: 259861
* [SCEV] Add and use SCEVConstant::getAPInt; NFCISanjoy Das2015-12-171-1/+1
| | | | llvm-svn: 255921
* [LLE] Use the PredicatedScalarEvolution interface to query SCEVs for dependencesSilviu Baranga2015-12-101-16/+15
| | | | | | | | | | | | | | | | | Summary: LAA uses the PredicatedScalarEvolution interface, so it can produce forward/backward dependences having SCEVs that are AddRecExprs only after being transformed by PredicatedScalarEvolution. Use PredicatedScalarEvolution to get the expected expressions. Reviewers: anemet Subscribers: llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D15382 llvm-svn: 255241
* Re-commit r255115, with the PredicatedScalarEvolution class moved toSilviu Baranga2015-12-091-3/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ScalarEvolution.h, in order to avoid cyclic dependencies between the Transform and Analysis modules: [LV][LAA] Add a layer over SCEV to apply run-time checked knowledge on SCEV expressions Summary: This change creates a layer over ScalarEvolution for LAA and LV, and centralizes the usage of SCEV predicates. The SCEVPredicatedLayer takes the statically deduced knowledge by ScalarEvolution and applies the knowledge from the SCEV predicates. The end goal is that both LAA and LV should use this interface everywhere. This also solves a problem involving the result of SCEV expression rewritting when the predicate changes. Suppose we have the expression (sext {a,+,b}) and two predicates P1: {a,+,b} has nsw P2: b = 1. Applying P1 and then P2 gives us {a,+,1}, while applying P2 and the P1 gives us sext({a,+,1}) (the AddRec expression was changed by P2 so P1 no longer applies). The SCEVPredicatedLayer maintains the order of transformations by feeding back the results of previous transformations into new transformations, and therefore avoiding this issue. The SCEVPredicatedLayer maintains a cache to remember the results of previous SCEV rewritting results. This also has the benefit of reducing the overall number of expression rewrites. Reviewers: mzolotukhin, anemet Subscribers: jmolloy, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D14296 llvm-svn: 255122
* Revert r255115 until we figure out how to fix the bot failures.Silviu Baranga2015-12-091-4/+3
| | | | llvm-svn: 255117
* [LV][LAA] Add a layer over SCEV to apply run-time checked knowledge on SCEV ↵Silviu Baranga2015-12-091-3/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | expressions Summary: This change creates a layer over ScalarEvolution for LAA and LV, and centralizes the usage of SCEV predicates. The SCEVPredicatedLayer takes the statically deduced knowledge by ScalarEvolution and applies the knowledge from the SCEV predicates. The end goal is that both LAA and LV should use this interface everywhere. This also solves a problem involving the result of SCEV expression rewritting when the predicate changes. Suppose we have the expression (sext {a,+,b}) and two predicates P1: {a,+,b} has nsw P2: b = 1. Applying P1 and then P2 gives us {a,+,1}, while applying P2 and the P1 gives us sext({a,+,1}) (the AddRec expression was changed by P2 so P1 no longer applies). The SCEVPredicatedLayer maintains the order of transformations by feeding back the results of previous transformations into new transformations, and therefore avoiding this issue. The SCEVPredicatedLayer maintains a cache to remember the results of previous SCEV rewritting results. This also has the benefit of reducing the overall number of expression rewrites. Reviewers: mzolotukhin, anemet Subscribers: jmolloy, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D14296 llvm-svn: 255115
* Allow LLE/LD and the loop versioning infrastructure to use SCEV predicatesSilviu Baranga2015-11-091-2/+15
| | | | | | | | | | | | | | | | | | | Summary: LAA currently generates a set of SCEV predicates that must be checked by users. In the case of Loop Distribute/Loop Load Elimination, no such predicates could have been emitted, since we don't allow stride versioning. However, in the future there could be SCEV predicates that will need to be checked. This change adds support for SCEV predicate versioning in the Loop Distribute, Loop Load Eliminate and the loop versioning infrastructure. Reviewers: anemet Subscribers: mssimpso, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D14240 llvm-svn: 252467
* ADT: Remove last implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-11-071-1/+1
| | | | | | | | | | Some implicit ilist iterator conversions have crept back into Analysis, Transforms, Hexagon, and llvm-stress. This removes them. I'll commit a patch immediately after this to disallow them (in a separate patch so that it's easy to revert if necessary). llvm-svn: 252371
* Fix unused variable warning from r252017Adam Nemet2015-11-041-3/+2
| | | | llvm-svn: 252019
* LLE 6/6: Add LoopLoadElimination passAdam Nemet2015-11-031-0/+554
Summary: The goal of this pass is to perform store-to-load forwarding across the backedge of a loop. E.g.: for (i) A[i + 1] = A[i] + B[i] => T = A[0] for (i) T = T + B[i] A[i + 1] = T The pass relies on loop dependence analysis via LoopAccessAnalisys to find opportunities of loop-carried dependences with a distance of one between a store and a load. Since it's using LoopAccessAnalysis, it was easy to also add support for versioning away may-aliasing intervening stores that would otherwise prevent this transformation. This optimization is also performed by Load-PRE in GVN without the option of multi-versioning. As was discussed with Daniel Berlin in http://reviews.llvm.org/D9548, this is inferior to a more loop-aware solution applied here. Hopefully, we will be able to remove some complexity from GVN/MemorySSA as a consequence. In the long run, we may want to extend this pass (or create a new one if there is little overlap) to also eliminate loop-indepedent redundant loads and store that *require* versioning due to may-aliasing intervening stores/loads. I have some motivating cases for store elimination. My plan right now is to wait for MemorySSA to come online first rather than using memdep for this. The main motiviation for this pass is the 456.hmmer loop in SPECint2006 where after distributing the original loop and vectorizing the top part, we are left with the critical path exposed in the bottom loop. Being able to promote the memory dependence into a register depedence (even though the HW does perform store-to-load fowarding as well) results in a major gain (~20%). This gain also transfers over to x86: it's around 8-10%. Right now the pass is off by default and can be enabled with -enable-loop-load-elim. On the LNT testsuite, there are two performance changes (negative number -> improvement): 1. -28% in Polybench/linear-algebra/solvers/dynprog: the length of the critical paths is reduced 2. +2% in Polybench/stencils/adi: Unfortunately, I couldn't reproduce this outside of LNT The pass is scheduled after the loop vectorizer (which is after loop distribution). The rational is to try to reuse LAA state, rather than recomputing it. The order between LV and LLE is not critical because normally LV does not touch scalar st->ld forwarding cases where vectorizing would inhibit the CPU's st->ld forwarding to kick in. LoopLoadElimination requires LAA to provide the full set of dependences (including forward dependences). LAA is known to omit loop-independent dependences in certain situations. The big comment before removeDependencesFromMultipleStores explains why this should not occur for the cases that we're interested in. Reviewers: dberlin, hfinkel Subscribers: junbuml, dberlin, mssimpso, rengolin, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D13259 llvm-svn: 252017
OpenPOWER on IntegriCloud