summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LoopAccessAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [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
* Revert r255115 until we figure out how to fix the bot failures.Silviu Baranga2015-12-091-44/+43
| | | | llvm-svn: 255117
* [LV][LAA] Add a layer over SCEV to apply run-time checked knowledge on SCEV ↵Silviu Baranga2015-12-091-43/+44
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* fix 'the the '; NFCSanjay Patel2015-12-071-1/+1
| | | | llvm-svn: 254928
* Fix LoopAccessAnalysis when potentially nullptr check are involvedMehdi Amini2015-11-051-1/+6
| | | | | | | | | | | | | | Summary: GetUnderlyingObjects() can return "null" among its list of objects, we don't want to deduce that two pointers can point to the same memory in this case, so filter it out. Reviewers: anemet Subscribers: dexonsmith, llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 252149
* [LAA] LLE 5/6: Add predicate functions Dependence::isForward/isBackward, NFCAdam Nemet2015-11-031-2/+22
| | | | | | | | | | | | Summary: Will be used by the LoopLoadElimination pass. Reviewers: hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13258 llvm-svn: 252016
* [LAA] LLE 3/6: Rename InterestingDependence to Dependences, NFCAdam Nemet2015-11-031-27/+21
| | | | | | | | | | | | | | Summary: We now collect all types of dependences including lexically forward deps not just "interesting" ones. Reviewers: hfinkel Subscribers: rengolin, llvm-commits Differential Revision: http://reviews.llvm.org/D13256 llvm-svn: 251985
* [LAA] LLE 2/6: Fix a NoDep case that should be a Forward dependenceAdam Nemet2015-11-031-1/+1
| | | | | | | | | | | | | | | | | | | | | Summary: When the dependence distance in zero then we have a loop-independent dependence from the earlier to the later access. No current client of LAA uses forward dependences so other than potentially hitting the MaxDependences threshold earlier, this change shouldn't affect anything right now. This and the previous patch were tested together for compile-time regression. None found in LNT/SPEC. Reviewers: hfinkel Subscribers: rengolin, llvm-commits Differential Revision: http://reviews.llvm.org/D13255 llvm-svn: 251973
* [LAA] LLE 1/6: Expose Forward dependencesAdam Nemet2015-11-031-13/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Before this change, we didn't use to collect forward dependences since none of the current clients (LV, LDist) required them. The motivation to also collect forward dependences is a new pass LoopLoadElimination (LLE) which discovers store-to-load forwarding opportunities across the loop's backedge. The pass uses both lexically forward or backward loop-carried dependences to detect these opportunities. The new pass also analyzes loop-independent (forward) dependences since they can conflict with the loop-carried dependences in terms of how the data flows through memory. The newly added test only covers loop-carried forward dependences because loop-independent ones are currently categorized as NoDep. The next patch will fix this. The two patches were tested together for compile-time regression. None found in LNT/SPEC. Note that with this change LAA provides all dependences rather than just "interesting" ones. A subsequent NFC patch will remove the now trivial isInterestingDependence and rename the APIs. Reviewers: hfinkel Subscribers: jmolloy, rengolin, llvm-commits Differential Revision: http://reviews.llvm.org/D13254 llvm-svn: 251972
* [SCEV][LV] Add SCEV Predicates and use them to re-implement stride versioningSilviu Baranga2015-11-021-25/+40
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: SCEV Predicates represent conditions that typically cannot be derived from static analysis, but can be used to reduce SCEV expressions to forms which are usable for different optimizers. ScalarEvolution now has the rewriteUsingPredicate method which can simplify a SCEV expression using a SCEVPredicateSet. The normal workflow of a pass using SCEVPredicates would be to hold a SCEVPredicateSet and every time assumptions need to be made a new SCEV Predicate would be created and added to the set. Each time after calling getSCEV, the user will call the rewriteUsingPredicate method. We add two types of predicates SCEVPredicateSet - implements a set of predicates SCEVEqualPredicate - tests for equality between two SCEV expressions We use the SCEVEqualPredicate to re-implement stride versioning. Every time we version a stride, we will add a SCEVEqualPredicate to the context. Instead of adding specific stride checks, LoopVectorize now adds a more generic SCEV check. We only need to add support for this in the LoopVectorizer since this is the only pass that will do stride versioning. Reviewers: mzolotukhin, anemet, hfinkel, sanjoy Subscribers: sanjoy, hfinkel, rengolin, jmolloy, llvm-commits Differential Revision: http://reviews.llvm.org/D13595 llvm-svn: 251800
* Put global classes into the appropriate namespace.Benjamin Kramer2015-10-281-0/+2
| | | | | | | Most of the cases belong into an anonymous namespace. No functionality change intended. llvm-svn: 251515
OpenPOWER on IntegriCloud