summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LoopAccessAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [LoopAccessAnalysis] Fix an integer overflowDavid Majnemer2016-07-071-22/+22
| | | | | | | | | We were inappropriately using 32-bit types to account for quantities that can be far larger. Fixed in PR28443. llvm-svn: 274737
* [PM] Avoid getResult on a higher level in LoopAccessAnalysisSean Silva2016-07-071-7/+15
| | | | | | | Note that require<domtree> and require<loops> aren't needed because they come in implicitly via the loop pass manager. llvm-svn: 274712
* [PM] Port LoopAccessInfo analysis to new PMXinliang David Li2016-07-021-0/+28
| | | | | | | It is implemented as a LoopAnalysis pass as discussed and agreed upon. llvm-svn: 274452
* [PM] refactor LoopAccessInfo code part-2Xinliang David Li2016-07-011-15/+15
| | | | | | Differential Revision: http://reviews.llvm.org/D21636 llvm-svn: 274334
* [LAA] Fix alphabetical sorting of headers. NFCAdam Nemet2016-07-011-1/+1
| | | | llvm-svn: 274302
* Reverted patch 273864Elena Demikhovsky2016-06-291-4/+4
| | | | llvm-svn: 274115
* Fixed consecutive memory access detection in Loop Vectorizer.Elena Demikhovsky2016-06-271-4/+4
| | | | | | | | | | | | | | | | It did not handle correctly cases without GEP. The following loop wasn't vectorized: for (int i=0; i<len; i++) *to++ = *from++; I use getPtrStride() to find Stride for memory access and return 0 is the Stride is not 1 or -1. Re-commit rL273257 - revision: http://reviews.llvm.org/D20789 llvm-svn: 273864
* [PM]: LoopAccessInfo simple refactoringXinliang David Li2016-06-221-22/+24
| | | | | | | To make definition of mov ctors easier. Differential Revision: http://reviews.llvm.org/D21563 llvm-svn: 273506
* reverted the prev commit due to assertion failureElena Demikhovsky2016-06-211-4/+4
| | | | llvm-svn: 273258
* Fixed consecutive memory access detection in Loop Vectorizer.Elena Demikhovsky2016-06-211-4/+4
| | | | | | | | | | | | | | | It did not handle correctly cases without GEP. The following loop wasn't vectorized: for (int i=0; i<len; i++) *to++ = *from++; I use getPtrStride() to find Stride for memory access and return 0 is the Stride is not 1 or -1. Differential revision: http://reviews.llvm.org/D20789 llvm-svn: 273257
* [LAA] Enable symbolic stride speculation for all LAA clientsAdam Nemet2016-06-171-16/+22
| | | | | | | | | | | | | | | This is a functional change for LLE and LDist. The other clients (LV, LVerLICM) already had this explicitly enabled. The temporary boolean parameter to LAA is removed that allowed turning off speculation of symbolic strides. This makes LAA's caching interface LAA::getInfo only take the loop as the parameter. This makes the interface more friendly to the new Pass Manager. The flag -enable-mem-access-versioning is moved from LV to a LAA which now allows turning off speculation globally. llvm-svn: 273064
* [LV] Move management of symbolic strides to LAA. NFCIAdam Nemet2016-06-161-13/+33
| | | | | | | | | | | | | | | | | | | This is still NFCI, so the list of clients that allow symbolic stride speculation does not change (yes: LV and LoopVersioningLICM, no: LLE, LDist). However since the symbolic strides are now managed by LAA rather than passed by client a new bool parameter is used to enable symbolic stride speculation. The existing test Transforms/LoopVectorize/version-mem-access.ll checks that stride speculation is performed for LV. The previously added test Transforms/LoopLoadElim/symbolic-stride.ll ensures that no speculation is performed for LLE. The next patch will change the functionality and turn on symbolic stride speculation in all of LAA's clients and remove the bool parameter. llvm-svn: 272970
* [LAA] Rename Strides to SymblicStrides in analyzeLoop. NFCAdam Nemet2016-06-161-7/+8
| | | | | | This is to facilitate to move of SymblicStrides from LV to LAA. llvm-svn: 272879
* [LAA] Default getInfo to not speculate symbolic strides. NFCAdam Nemet2016-06-161-3/+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-11/+12
| | | | llvm-svn: 272243
* [PM] Refector LoopAccessInfo analysis code Xinliang David Li2016-06-081-12/+11
| | | | | | | | This is the preparation patch to port the analysis to new PM Differential Revision: http://reviews.llvm.org/D20560 llvm-svn: 272194
* [LAA] Improve non-wrapping pointer detection by handling loop-invariant case.Andrey Turetskiy2016-06-071-4/+14
| | | | | | | | | | | | | This fixes PR26314. This patch adds new helper “isNoWrap” with detection of loop-invariant pointer case. Patch by Roman Shirokiy. Ref: https://llvm.org/bugs/show_bug.cgi?id=26314 Differential Revision: http://reviews.llvm.org/D17268 llvm-svn: 272014
* [LAA] Use load and store vectors (NFC)Matthew Simpson2016-06-061-11/+7
| | | | | | | Contributed-by: Aditya Kumar <hiraditya@msn.com> Differential Revision: http://reviews.llvm.org/D20953 llvm-svn: 271895
* [LAA] Check independence of strided accesses before forward caseMatthew Simpson2016-05-191-10/+11
| | | | | | | | | | | | This patch changes the order in which we attempt to prove the independence of strided accesses. We previously did this after we knew the dependence distance was positive. With this change, we check for independence before handling the negative distance case. The patch prevents LAA from reporting forward dependences for independent strided accesses. This change was requested in the review of D19984. llvm-svn: 270072
* [LAA] Rename forwarding conflict detection option (NFC)Matthew Simpson2016-05-161-6/+6
| | | | | | | This patch renames the option enabling the store-to-load forwarding conflict detection optimization. This change was requested in the review of D20241. llvm-svn: 269668
* [LAA] Comment couldPreventStoreLoadForward. NFCAdam Nemet2016-05-161-2/+8
| | | | | | | Also s/Cycles/Iters/ in NumCyclesForStoreLoadThroughMemory to make it clear that this is not about clock cycles but loop cycles/iterations. llvm-svn: 269667
* [LAA] clang-format the function couldPreventStoreLoadForward. NFCAdam Nemet2016-05-161-9/+9
| | | | llvm-svn: 269666
* [LAA] Add option to disable conflict detection (NFC)Matthew Simpson2016-05-161-2/+9
| | | | llvm-svn: 269654
* [LAA] Include MaxSafeDepDistBytes in the analysis print-outAdam Nemet2016-05-131-0/+3
| | | | llvm-svn: 269508
* [LAA] Prepare the code to print more things in the summary. NFCAdam Nemet2016-05-131-3/+3
| | | | llvm-svn: 269507
* [LAA] Use std::min. NFCAdam Nemet2016-05-121-4/+2
| | | | llvm-svn: 269356
* [LAA] Use re-written SCEV expressions when computing distancesSilviu Baranga2016-05-101-7/+2
| | | | | | | | | | | | This removes a redundant stride versioning step (we already do it in getPtrStride, so it has no effect) and uses PSE to get the SCEV expressions for the source and destination (this might have changed when getPtrStride was called). I discovered this through code inspection, and couldn't produce a regression test for it. llvm-svn: 269052
* [LAA] Rename "isStridedPtr" with "getPtrStride". NFC.Denis Zobnin2016-05-101-5/+5
| | | | | | | Changing misleading function name was approved in http://reviews.llvm.org/D17268. Patch by Roman Shirokiy. llvm-svn: 269021
* [LV] Hint at the new loop distribution pragma in optimization remarkAdam Nemet2016-05-091-2/+6
| | | | | | | | | | When we encounter unsafe memory dependencies, loop distribution could help. Even though, the diagnostics is in LAA, it's only currently emitted in the vectorizer. llvm-svn: 268987
* [LAA] Fix confusing debug messageAdam Nemet2016-05-051-1/+1
| | | | | | | | This message used to be correct, when all we cared about was whether the dependence was safe (i.e. NoDep) or unsafe. With the current more precise characterization, this is a forward dep. llvm-svn: 268695
* [ValueTracking, VectorUtils] Refactor getIntrinsicIDForCallDavid Majnemer2016-04-191-1/+1
| | | | | | | | | | | | | The functionality contained within getIntrinsicIDForCall is two-fold: it checks if a CallInst's callee is a vectorizable intrinsic. If it isn't an intrinsic, it attempts to map the call's target to a suitable intrinsic. Move the mapping functionality into getIntrinsicForCallSite and rename getIntrinsicIDForCall to getVectorIntrinsicIDForCall while reimplementing it in terms of getIntrinsicForCallSite. llvm-svn: 266801
* [SCEV][LAA] Add tests for SCEV expression transformations performed during LAASilviu Baranga2016-04-141-0/+5
| | | | | | | | | | | | | | | | | | | | Summary: Add a print method to Predicated Scalar Evolution which prints all interesting transformations done by PSE. Loop Access Analysis will now print this as part of the analysis output. We now use this to check the exact expression transformations that were done by PSE in LAA. The additional checking also acts as white-box testing for the getAsAddRec method. Reviewers: anemet, sanjoy Subscribers: sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D18792 llvm-svn: 266334
* Re-commit [SCEV] Introduce a guarded backedge taken count and use it in LAA ↵Silviu Baranga2016-04-081-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | and LV This re-commits r265535 which was reverted in r265541 because it broke the windows bots. The problem was that we had a PointerIntPair which took a pointer to a struct allocated with new. The problem was that new doesn't provide sufficient alignment guarantees. This pattern was already present before r265535 and it just happened to work. To fix this, we now separate the PointerToIntPair from the ExitNotTakenInfo struct into a pointer and a bool. Original commit message: Summary: When the backedge taken codition is computed from an icmp, SCEV can deduce the backedge taken count only if one of the sides of the icmp is an AddRecExpr. However, due to sign/zero extensions, we sometimes end up with something that is not an AddRecExpr. However, we can use SCEV predicates to produce a 'guarded' expression. This change adds a method to SCEV to get this expression, and the SCEV predicate associated with it. In HowManyGreaterThans and HowManyLessThans we will now add a SCEV predicate associated with the guarded backedge taken count when the analyzed SCEV expression is not an AddRecExpr. Note that we only do this as an alternative to returning a 'CouldNotCompute'. We use new feature in Loop Access Analysis and LoopVectorize to analyze and transform more loops. Reviewers: anemet, mzolotukhin, hfinkel, sanjoy Subscribers: flyingforyou, mcrosier, atrick, mssimpso, sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D17201 llvm-svn: 265786
* Revert r265535 until we know how we can fix the bots Silviu Baranga2016-04-061-2/+2
| | | | llvm-svn: 265541
* [SCEV] Introduce a guarded backedge taken count and use it in LAA and LVSilviu Baranga2016-04-061-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: When the backedge taken codition is computed from an icmp, SCEV can deduce the backedge taken count only if one of the sides of the icmp is an AddRecExpr. However, due to sign/zero extensions, we sometimes end up with something that is not an AddRecExpr. However, we can use SCEV predicates to produce a 'guarded' expression. This change adds a method to SCEV to get this expression, and the SCEV predicate associated with it. In HowManyGreaterThans and HowManyLessThans we will now add a SCEV predicate associated with the guarded backedge taken count when the analyzed SCEV expression is not an AddRecExpr. Note that we only do this as an alternative to returning a 'CouldNotCompute'. We use new feature in Loop Access Analysis and LoopVectorize to analyze and transform more loops. Reviewers: anemet, mzolotukhin, hfinkel, sanjoy Subscribers: flyingforyou, mcrosier, atrick, mssimpso, sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D17201 llvm-svn: 265535
* [LAA] Formatting fix in previous changeAdam Nemet2016-03-241-2/+1
| | | | llvm-svn: 264244
* [LAA] Support memchecks involving loop-invariant addressesAdam Nemet2016-03-241-17/+31
| | | | | | | | | | | | | | | | | | | | We used to only allow SCEVAddRecExpr for pointer expressions in order to be able to compute the bounds. However this is also trivially possible for loop-invariant addresses (scUnknown) since then the bounds are the address itself. Interestingly, we used allow this for the special case when the loop-invariant address happens to also be an SCEVAddRecExpr (in an outer loop). There are a couple more loops that are vectorized in SPEC after this. My guess is that the main reason we don't see more because for example a loop-invariant load is vectorized into a splat vector with several vector-inserts. This is likely to make the vectorization unprofitable. I.e. we don't notice that a later LICM will move all of this out of the loop so the cost estimate should really be 0. llvm-svn: 264243
* [SCEV] Change the SCEV Predicates interfaces for conversion to AddRecExpr to ↵Silviu Baranga2016-03-231-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | return SCEVAddRecExpr* instead of SCEV* Summary: This changes the conversion functions from SCEV * to SCEVAddRecExpr from ScalarEvolution and PredicatedScalarEvolution to return a SCEVAddRecExpr* instead of a SCEV* (which removes the need of most clients to do a dyn_cast right after calling these functions). We also don't add new predicates if the transformation was not successful. This is not entirely a NFC (as it can theoretically remove some predicates from LAA when we have an unknown dependece), but I couldn't find an obvious regression test for it. Reviewers: sanjoy Subscribers: sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D18368 llvm-svn: 264161
* [LAA] Add missing debug outputAdam Nemet2016-03-011-1/+3
| | | | llvm-svn: 262279
* Remove uses of builtin comma operator.Richard Trieu2016-02-181-2/+4
| | | | | | Cleanup for upcoming Clang warning -Wcomma. No functionality change intended. llvm-svn: 261270
* [SCEV][LAA] Re-commit r260085 and r260086, this time with a fix for the memorySilviu Baranga2016-02-081-18/+43
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | sanitizer issue. The PredicatedScalarEvolution's copy constructor wasn't copying the Generation value, and was leaving it un-initialized. Original commit message: [SCEV][LAA] Add no wrap SCEV predicates and use use them to improve strided pointer detection Summary: This change adds no wrap SCEV predicates with: - support for runtime checking - support for expression rewriting: (sext ({x,+,y}) -> {sext(x),+,sext(y)} (zext ({x,+,y}) -> {zext(x),+,sext(y)} Note that we are sign extending the increment of the SCEV, even for the zext case. This is needed to cover the fairly common case where y would be a (small) negative integer. In order to do this, this change adds two new flags: nusw and nssw that are applicable to AddRecExprs and permit the transformations above. We also change isStridedPtr in LAA to be able to make use of these predicates. With this feature we should now always be able to work around overflow issues in the dependence analysis. Reviewers: mzolotukhin, sanjoy, anemet Subscribers: mzolotukhin, sanjoy, llvm-commits, rengolin, jmolloy, hfinkel Differential Revision: http://reviews.llvm.org/D15412 llvm-svn: 260112
* Revert r260086 and r260085. They have broken the memorySilviu Baranga2016-02-081-43/+18
| | | | | | sanitizer bots. llvm-svn: 260087
* [SCEV][LAA] Add no wrap SCEV predicates and use use them to improve strided ↵Silviu Baranga2016-02-081-18/+43
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | pointer detection Summary: This change adds no wrap SCEV predicates with: - support for runtime checking - support for expression rewriting: (sext ({x,+,y}) -> {sext(x),+,sext(y)} (zext ({x,+,y}) -> {zext(x),+,sext(y)} Note that we are sign extending the increment of the SCEV, even for the zext case. This is needed to cover the fairly common case where y would be a (small) negative integer. In order to do this, this change adds two new flags: nusw and nssw that are applicable to AddRecExprs and permit the transformations above. We also change isStridedPtr in LAA to be able to make use of these predicates. With this feature we should now always be able to work around overflow issues in the dependence analysis. Reviewers: mzolotukhin, sanjoy, anemet Subscribers: mzolotukhin, sanjoy, llvm-commits, rengolin, jmolloy, hfinkel Differential Revision: http://reviews.llvm.org/D15412 llvm-svn: 260085
* [LIR] Add support for structs and hand unrolled loopsHaicheng Wu2016-01-261-0/+72
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a recommit of r258620 which causes PR26293. The original message: Now LIR can turn following codes into memset: typedef struct foo { int a; int b; } foo_t; void bar(foo_t *f, unsigned n) { for (unsigned i = 0; i < n; ++i) { f[i].a = 0; f[i].b = 0; } } void test(foo_t *f, unsigned n) { for (unsigned i = 0; i < n; i += 2) { f[i] = 0; f[i+1] = 0; } } llvm-svn: 258777
* Speculatively revert r258620 as it is the likely culprid of PR26293.Quentin Colombet2016-01-251-72/+0
| | | | llvm-svn: 258703
* [LIR] Add support for structs and hand unrolled loopsHaicheng Wu2016-01-231-0/+72
| | | | | | | | | | | | | | | | | | | | | | | | | Now LIR can turn following codes into memset: typedef struct foo { int a; int b; } foo_t; void bar(foo_t *f, unsigned n) { for (unsigned i = 0; i < n; ++i) { f[i].a = 0; f[i].b = 0; } } void test(foo_t *f, unsigned n) { for (unsigned i = 0; i < n; i += 2) { f[i] = 0; f[i+1] = 0; } } llvm-svn: 258620
* [LAA] Include function name in debug outputAdam Nemet2016-01-181-3/+4
| | | | llvm-svn: 258088
* [Vectorization] Actually return from error case in isStridedPtrKyle Butt2016-01-081-0/+1
| | | | | | | | | | The early return seems to be missed. This causes a radical and wrong loop optimization on powerpc. It isn't reproducible on x86_64, because "UseInterleaved" is false. Patch by Tim Shen. llvm-svn: 257134
* [SCEV] Add and use SCEVConstant::getAPInt; NFCISanjoy Das2015-12-171-2/+2
| | | | llvm-svn: 255921
* Re-commit r255115, with the PredicatedScalarEvolution class moved toSilviu Baranga2015-12-091-44/+45
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
OpenPOWER on IntegriCloud