summaryrefslogtreecommitdiffstats
path: root/llvm/test/Analysis/LoopAccessAnalysis
Commit message (Collapse)AuthorAgeFilesLines
* Revert "[IRBuilder] Fold consistently for or/and whether constant is LHS or RHS"Petr Hosek2019-07-071-5/+19
| | | | | | | | | | This reverts commit r365260 which broke the following tests: Clang :: CodeGenCXX/cfi-mfcall.cpp Clang :: CodeGenObjC/ubsan-nullability.m LLVM :: Transforms/LoopVectorize/AArch64/pr36032.ll llvm-svn: 365284
* [IRBuilder] Fold consistently for or/and whether constant is LHS or RHSPhilip Reames2019-07-061-19/+5
| | | | | | Without this, we have the unfortunate property that tests are dependent on the order of operads passed the CreateOr and CreateAnd functions. In actual usage, we'd promptly optimize them away, but it made tests slightly more verbose than they should have been. llvm-svn: 365260
* LoopDistribute/LAA: Respect convergentMatt Arsenault2019-06-121-0/+73
| | | | | | | | | | | | | | | | | | This case is slightly tricky, because loop distribution should be allowed in some cases, and not others. As long as runtime dependency checks don't need to be introduced, this should be OK. This is further complicated by the fact that LoopDistribute partially ignores if LAA says that vectorization is safe, and then does its own runtime pointer legality checks. Note this pass still does not handle noduplicate correctly, as this should always be forbidden with it. I'm not going to bother trying to fix it, as it would require more effort and I think noduplicate should be removed. https://reviews.llvm.org/D62607 llvm-svn: 363160
* [SCEV] Add explicit representations of umin/sminKeno Fischer2019-05-072-1/+51
| | | | | | | | | | | | | | | | | | Summary: Currently we express umin as `~umax(~x, ~y)`. However, this becomes a problem for operands in non-integral pointer spaces, because `~x` is not something we can compute for `x` non-integral. However, since comparisons are generally still allowed, we are actually able to express `umin(x, y)` directly as long as we don't try to express is as a umax. Support this by adding an explicit umin/smin representation to SCEV. We do this by factoring the existing getUMax/getSMax functions into a new function that does all four. The previous two functions were largely identical. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D50167 llvm-svn: 360159
* [LV] Avoid vectorizing unsafe dependencies in uniform addressAnna Thomas2018-11-194-8/+8
| | | | | | | | | | | | | | | | | | | Summary: Currently, when vectorizing stores to uniform addresses, the only instance we prevent vectorization is if there are multiple stores to the same uniform address causing an unsafe dependency. This patch teaches LAA to avoid vectorizing loops that have an unsafe cross-iteration dependency between a load and a store to the same uniform address. Fixes PR39653. Reviewers: Ayal, efriedma Subscribers: rkruppe, llvm-commits Differential Revision: https://reviews.llvm.org/D54538 llvm-svn: 347220
* [LV] Teach vectorizer about variant value store into uniform addressAnna Thomas2018-10-164-12/+16
| | | | | | | | | | | | | | | | | | | | Summary: Teach vectorizer about vectorizing variant value stores to uniform address. Similar to rL343028, we do not allow vectorization if we have multiple stores to the same uniform address. Cost model already has the change for considering the extract instruction cost for a variant value store. See added test cases for how vectorization is done. The patch also contains changes to the ORE messages. Reviewers: Ayal, mkuper, anemet, hsaito Subscribers: rkruppe, llvm-commits Differential Revision: https://reviews.llvm.org/D52656 llvm-svn: 344613
* [LV][LAA] Vectorize loop invariant values stored into loop invariant addressAnna Thomas2018-09-254-8/+8
| | | | | | | | | | | | | | | | | | | Summary: We are overly conservative in loop vectorizer with respect to stores to loop invariant addresses. More details in https://bugs.llvm.org/show_bug.cgi?id=38546 This is the first part of the fix where we start with vectorizing loop invariant values to loop invariant addresses. This also includes changes to ORE for stores to invariant address. Reviewers: anemet, Ayal, mkuper, mssimpso Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D50665 llvm-svn: 343028
* [SCEV] Don't expand Wrap predicate using inttoptr in ni addrspacesKeno Fischer2018-07-262-8/+62
| | | | | | | | | | | | | | | Summary: In non-integral address spaces, we're not allowed to introduce inttoptr/ptrtoint intrinsics. Instead, we need to expand any pointer arithmetic as geps on the base pointer. Luckily this is a common task for SCEV, so all we have to do here is hook up the corresponding helper function and add test case. Fixes PR38290 Reviewers: sanjoy Differential Revision: https://reviews.llvm.org/D49832 llvm-svn: 338073
* Re-apply "[SCEV] Strengthen StrengthenNoWrapFlags (reapply r334428)."Tim Shen2018-07-132-10/+10
| | | | llvm-svn: 337075
* Revert "[SCEV] Strengthen StrengthenNoWrapFlags (reapply r334428)."Tim Shen2018-07-062-10/+10
| | | | | | This reverts commit r336140. Our tests shows that LSR assert fails with it. llvm-svn: 336473
* [SCEV] Strengthen StrengthenNoWrapFlags (reapply r334428).Tim Shen2018-07-022-10/+10
| | | | | | | | | | | | | | | | Summary: Comment on Transforms/LoopVersioning/incorrect-phi.ll: With the change SCEV is able to prove that the loop doesn't wrap-self (due to zext i16 to i64), disabling the entire loop versioning pass. Removed the zext and just use i64. Reviewers: sanjoy Subscribers: jlebar, hiraditya, javed.absar, bixia, llvm-commits Differential Revision: https://reviews.llvm.org/D48409 llvm-svn: 336140
* Revert "[SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags"Sanjoy Das2018-06-192-4/+4
| | | | | | | | | | | | | | This reverts r334428. It incorrectly marks some multiplications as nuw. Tim Shen is working on a proper fix. Original commit message: [SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags where safe. Summary: Previously we would add them for adds, but not multiplies. llvm-svn: 335016
* [SCEV] Simplify zext/trunc idiom that appears when handling bitmasks.Justin Lebar2018-06-141-2/+2
| | | | | | | | | | | | | | | | | | | Summary: Specifically, we transform zext(2^K * (trunc X to iN)) to iM -> 2^K * (zext(trunc X to i{N-K}) to iM)<nuw> This is helpful because pulling the 2^K out of the zext allows further optimizations. Reviewers: sanjoy Subscribers: hiraditya, llvm-commits, timshen Differential Revision: https://reviews.llvm.org/D48158 llvm-svn: 334737
* [SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags where safe.Justin Lebar2018-06-112-6/+6
| | | | | | | | | | | | | Summary: Previously we would add them for adds, but not multiplies. Reviewers: sanjoy Subscribers: llvm-commits, hiraditya Differential Revision: https://reviews.llvm.org/D48038 llvm-svn: 334428
* [LAA] Allow more run-time alias checks by coercing pointer expressions to ↵Silviu Baranga2017-09-121-0/+107
| | | | | | | | | | | | | | | | | | | | | | AddRecExprs Summary: LAA can only emit run-time alias checks for pointers with affine AddRec SCEV expressions. However, non-AddRecExprs can be now be converted to affine AddRecExprs using SCEV predicates. This change tries to add the minimal set of SCEV predicates in order to enable run-time alias checking. Reviewers: anemet, mzolotukhin, mkuper, sanjoy, hfinkel Reviewed By: hfinkel Subscribers: mssimpso, Ayal, dorit, roman.shirokiy, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D17080 llvm-svn: 313012
* [LV/LoopAccess] Check statically if an unknown dependence distance can be Dorit Nuzman2017-02-122-4/+103
| | | | | | | | | | | | | | | | | | | | | | | proven larger than the loop-count This fixes PR31098: Try to resolve statically data-dependences whose compile-time-unknown distance can be proven larger than the loop-count, instead of resorting to runtime dependence checking (which are not always possible). For vectorization it is sufficient to prove that the dependence distance is >= VF; But in some cases we can prune unknown dependence distances early, and even before selecting the VF, and without a runtime test, by comparing the distance against the loop iteration count. Since the vectorized code will be executed only if LoopCount >= VF, proving distance >= LoopCount also guarantees that distance >= VF. This check is also equivalent to the Strong SIV Test. Reviewers: mkuper, anemet, sanjoy Differential Revision: https://reviews.llvm.org/D28044 llvm-svn: 294892
* [Loop Vectorizer] Fixed memory confilict checks.Elena Demikhovsky2016-08-283-11/+62
| | | | | | | | | Fixed a bug in run-time checks for possible memory conflicts inside loop. The bug is in Low <-> High boundaries calculation. The High boundary should be calculated as "last memory access pointer + element size". Differential revision: https://reviews.llvm.org/D23176 llvm-svn: 279930
* [LAA] Port test to the new PMAdam Nemet2016-07-081-3/+13
| | | | | | | | | | | This is a follow-on to r274452. The LAA with the new PM is a loop pass so we go from inner to outer loops. Also using a CHECK-NOT didn't make much sense because we print something in either case; whether an invariant is 'found' or 'not found'. llvm-svn: 274935
* [PM] Avoid getResult on a higher level in LoopAccessAnalysisSean Silva2016-07-0721-21/+21
| | | | | | | 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-0221-1/+22
| | | | | | | It is implemented as a LoopAnalysis pass as discussed and agreed upon. llvm-svn: 274452
* [LAA] Improve non-wrapping pointer detection by handling loop-invariant case.Andrey Turetskiy2016-06-071-0/+67
| | | | | | | | | | | | | 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
* [SCEV] No-wrap flags are not propagated when folding "{S,+,X}+T ==> {S+T,+,X}"Oleg Ranevskyy2016-05-252-7/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: **Description** This makes `WidenIV::widenIVUse` (IndVarSimplify.cpp) fail to widen narrow IV uses in some cases. The latter affects IndVarSimplify which may not eliminate narrow IV's when there actually exists such a possibility, thereby producing ineffective code. When `WidenIV::widenIVUse` gets a NarrowUse such as `{(-2 + %inc.lcssa),+,1}<nsw><%for.body3>`, it first tries to get a wide recurrence for it via the `getWideRecurrence` call. `getWideRecurrence` returns recurrence like this: `{(sext i32 (-2 + %inc.lcssa) to i64),+,1}<nsw><%for.body3>`. Then a wide use operation is generated by `cloneIVUser`. The generated wide use is evaluated to `{(-2 + (sext i32 %inc.lcssa to i64))<nsw>,+,1}<nsw><%for.body3>`, which is different from the `getWideRecurrence` result. `cloneIVUser` sees the difference and returns nullptr. This patch also fixes the broken LLVM tests by adding missing <nsw> entries introduced by the correction. **Minimal reproducer:** ``` int foo(int a, int b, int c); int baz(); void bar() { int arr[20]; int i = 0; for (i = 0; i < 4; ++i) arr[i] = baz(); for (; i < 20; ++i) arr[i] = foo(arr[i - 4], arr[i - 3], arr[i - 2]); } ``` **Clang command line:** ``` clang++ -mllvm -debug -S -emit-llvm -O3 --target=aarch64-linux-elf test.cpp -o test.ir ``` **Expected result:** The ` -mllvm -debug` log shows that all the IV's for the second `for` loop have been eliminated. Reviewers: sanjoy Subscribers: atrick, asl, aemerson, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D20058 llvm-svn: 270695
* [LAA] Check independence of strided accesses before forward caseMatthew Simpson2016-05-191-0/+45
| | | | | | | | | | | | 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] Include MaxSafeDepDistBytes in the analysis print-outAdam Nemet2016-05-131-0/+37
| | | | llvm-svn: 269508
* [SCEV] Improve the run-time checking of the NoWrap predicateSilviu Baranga2016-04-251-12/+127
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This implements a new method of run-time checking the NoWrap SCEV predicates, which should be easier to optimize and nicer for targets that don't correctly handle multiplication/addition of large integer types (like i128). If the AddRec is {a,+,b} and the backedge taken count is c, the idea is to check that |b| * c doesn't have unsigned overflow, and depending on the sign of b, that: a + |b| * c >= a (b >= 0) or a - |b| * c <= a (b <= 0) where the comparisons above are signed or unsigned, depending on the flag that we're checking. The advantage of doing this is that we avoid extending to a larger type and we avoid the multiplication of large types (multiplying i128 can be expensive). Reviewers: sanjoy Subscribers: llvm-commits, mzolotukhin Differential Revision: http://reviews.llvm.org/D19266 llvm-svn: 267389
* [SCEV][LAA] Add tests for SCEV expression transformations performed during LAASilviu Baranga2016-04-141-0/+21
| | | | | | | | | | | | | | | | | | | | 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
* [LAA] Support memchecks involving loop-invariant addressesAdam Nemet2016-03-241-0/+38
| | | | | | | | | | | | | | | | | | | | 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][LAA] Re-commit r260085 and r260086, this time with a fix for the memorySilviu Baranga2016-02-081-0/+292
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-292/+0
| | | | | | sanitizer bots. llvm-svn: 260087
* [LoopVersioning] Don't assert when there are no memchecksSilviu Baranga2016-02-081-10/+10
| | | | | | | | | | | | We shouldn't assert when there are no memchecks, since we can have SCEV checks. There is already an assert covering the case where there are no SCEV checks or memchecks. This also changes the LAA pointer wrapping versioning test to use the loop versioning pass (this was how I managed to trigger the assert in the loop versioning pass). llvm-svn: 260086
* [SCEV][LAA] Add no wrap SCEV predicates and use use them to improve strided ↵Silviu Baranga2016-02-081-0/+292
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [Vectorization] Actually return from error case in isStridedPtrKyle Butt2016-01-081-0/+29
| | | | | | | | | | 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
* Fix LoopAccessAnalysis when potentially nullptr check are involvedMehdi Amini2015-11-051-0/+38
| | | | | | | | | | | | | | 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 3/6: Rename InterestingDependence to Dependences, NFCAdam Nemet2015-11-038-22/+22
| | | | | | | | | | | | | | 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-0/+64
| | | | | | | | | | | | | | | | | | | | | 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-032-0/+52
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [LAA] Fix typo in testAdam Nemet2015-08-111-1/+1
| | | | llvm-svn: 244690
* [LAA] Add clarifying comments for the checking pointer grouping algorithm. NFCSilviu Baranga2015-07-281-2/+7
| | | | llvm-svn: 243416
* [LAA] Split out a helper to print a collection of memchecksAdam Nemet2015-07-271-21/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is effectively an NFC but we can no longer print the index of the pointer group so instead I print its address. This still lets us cross-check the section that list the checks against the section that list the groups (see how I modified the test). E.g. before we printed this: Run-time memory checks: Check 0: Comparing group 0: %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc Against group 1: %arrayidxA = getelementptr i16, i16* %a, i64 %ind %arrayidxA1 = getelementptr i16, i16* %a, i64 %add ... Grouped accesses: Group 0: (Low: %c High: (78 + %c)) Member: {%c,+,4}<%for.body> Member: {(2 + %c),+,4}<%for.body> Now we print this (changes are underlined): Run-time memory checks: Check 0: Comparing group (0x7f9c6040c320): ~~~~~~~~~~~~~~ %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind Against group (0x7f9c6040c358): ~~~~~~~~~~~~~~ %arrayidxA1 = getelementptr i16, i16* %a, i64 %add %arrayidxA = getelementptr i16, i16* %a, i64 %ind ... Grouped accesses: Group 0x7f9c6040c320: ~~~~~~~~~~~~~~ (Low: %c High: (78 + %c)) Member: {(2 + %c),+,4}<%for.body> Member: {%c,+,4}<%for.body> llvm-svn: 243354
* Fix memcheck interval ends for pointers with negative stridesSilviu Baranga2015-07-161-0/+89
| | | | | | | | | | | | | | | | | | | | | | | | Summary: The checking pointer grouping algorithm assumes that the starts/ends of the pointers are well formed (start <= end). The runtime memory checking algorithm also assumes this by doing: start0 < end1 && start1 < end0 to detect conflicts. This check only works if start0 <= end0 and start1 <= end1. This change correctly orders the interval ends by either checking the stride (if it is constant) or by using min/max SCEV expressions. Reviewers: anemet, rengolin Subscribers: rengolin, llvm-commits Differential Revision: http://reviews.llvm.org/D11149 llvm-svn: 242400
* Cleanup after r241809 - remove uncessary call to std::sortSilviu Baranga2015-07-132-12/+12
| | | | | | | | | | | | | | Summary: The iteration order within a member of DepCands is deterministic and therefore we don't have to sort the accesses within a member. We also don't have to copy the indices of the pointers into a vector, since we can iterate over the members of the class. Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11145 llvm-svn: 242033
* Add a test of a regression discovered during testing of r241673Silviu Baranga2015-07-091-0/+64
| | | | | | | | | | | | | | | Summary: We were missing a corner case where DepCands was not available, but we were using DepCands to compute the checking pointer groups. This adds a test for that regression. Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11068 llvm-svn: 241818
* Don't rely on the DepCands iteration order when constructing checking ↵Silviu Baranga2015-07-092-30/+30
| | | | | | | | | | | | | | | | | | | pointer groups Summary: The checking pointer group construction algorithm relied on the iteration on DepCands. We would need the same leaders across runs and the same iteration order over the underlying std::set for determinism. This changes the algorithm to process the pointers in the order in which they were added to the runtime check, which is deterministic. We need to update the tests, since the order in which pointers appear has changed. No new tests were added, since it is impossible to test for non-determinism. Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11064 llvm-svn: 241809
* [LAA] Revert a small part of r239295Adam Nemet2015-07-081-0/+42
| | | | | | | | | | | | | | | | This commit ([LAA] Fix estimation of number of memchecks) regressed the logic a bit. We shouldn't quit the analysis if we encounter a pointer without known bounds *unless* we actually need to emit a memcheck for it. The original code was using NumComparisons which is now computed differently. Instead I compute NeedRTCheck from NumReadPtrChecks and NumWritePtrChecks. As side note, I find the separation of NeedRTCheck and CanDoRT confusing, so I will try to merge them in a follow-up patch. llvm-svn: 241756
* [LAA] Merge memchecks for accesses separated by a constant offsetSilviu Baranga2015-07-083-6/+174
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Often filter-like loops will do memory accesses that are separated by constant offsets. In these cases it is common that we will exceed the threshold for the allowable number of checks. However, it should be possible to merge such checks, sice a check of any interval againt two other intervals separated by a constant offset (a,b), (a+c, b+c) will be equivalent with a check againt (a, b+c), as long as (a,b) and (a+c, b+c) overlap. Assuming the loop will be executed for a sufficient number of iterations, this will be true. If not true, checking against (a, b+c) is still safe (although not equivalent). As long as there are no dependencies between two accesses, we can merge their checks into a single one. We use this technique to construct groups of accesses, and then check the intervals associated with the groups instead of checking the accesses directly. Reviewers: anemet Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10386 llvm-svn: 241673
* [LAA] Try to prove non-wrapping of pointers if SCEV cannotAdam Nemet2015-06-261-0/+41
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Scalar evolution does not propagate the non-wrapping flags to values that are derived from a non-wrapping induction variable because the non-wrapping property could be flow-sensitive. This change is a first attempt to establish the non-wrapping property in some simple cases. The main idea is to look through the operations defining the pointer. As long as we arrive to a non-wrapping AddRec via a small chain of non-wrapping instruction, the pointer should not wrap either. I believe that this essentially is what Andy described in http://article.gmane.org/gmane.comp.compilers.llvm.cvs/220731 as the way forward. Reviewers: aschwaighofer, nadav, sanjoy, atrick Reviewed By: atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10472 llvm-svn: 240798
* [LAA] Fix estimation of number of memchecksSilviu Baranga2015-06-081-0/+58
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: We need to add a runtime memcheck for pair of accesses (x,y) where at least one of x and y are writes. Assuming we have w writes and r reads, currently this number is estimated as being w* (w+r-1). This estimation will count (write,write) pairs twice and will overestimate the number of checks required. This change adds a getNumberOfChecks method to RuntimePointerCheck, which will count the number of runtime checks needed (similar in implementation to needsAnyChecking) and uses it to produce the correct number of runtime checks. Test Plan: llvm test suite spec2k spec2k6 Performance results: no changes observed (not surprising since the formula for 1 writer is basically the same, which would covers most cases - at least with the current check limit). Reviewers: anemet Reviewed By: anemet Subscribers: mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D10217 llvm-svn: 239295
* [LoopAccessAnalysis] Teach LAA to check the memory dependence between ↵Hao Liu2015-06-081-0/+540
| | | | | | | | strided accesses. Differential Revision: http://reviews.llvm.org/D9368 llvm-svn: 239285
* [LoopAccesses] If shouldRetryWithRuntimeCheck, reset InterestingDependencesAdam Nemet2015-05-181-0/+57
| | | | | | | | When dependence analysis encounters a non-constant distance between memory accesses it aborts the analysis and falls back to run-time checks only. In this case we weren't resetting the array of dependences. llvm-svn: 237574
* [LoopAccesses] Rearrange printed lines in -analyzeAdam Nemet2015-05-181-1/+0
| | | | | | | "Store to invariant address..." is moved as the last line. This is not the prime result of the analysis. Plus it simplifies some of the tests. llvm-svn: 237573
OpenPOWER on IntegriCloud