summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* Revert r335513: [SCEVExp] Advance found insertion pointFlorian Hahn2018-06-251-4/+3
| | | | llvm-svn: 335522
* [SCEVExp] Advance found insertion point until we find a non-dbg instruction.Florian Hahn2018-06-251-3/+4
| | | | | | | | | | | | | This avoids creating unnecessary casts if the IP used to be a dbg info intrinsic. Fixes PR37727. Reviewers: vsk, aprantl, sanjoy, efriedma Reviewed By: vsk, efriedma Differential Revision: https://reviews.llvm.org/D47874 llvm-svn: 335513
* [InstSimplify] fold div/rem of zexted boolSanjay Patel2018-06-251-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | I was looking at an unrelated fold and noticed that we don't have this simplification (because the other fold would break existing tests). Name: zext udiv %z = zext i1 %x to i32 %r = udiv i32 %y, %z => %r = %y Name: zext urem %z = zext i1 %x to i32 %r = urem i32 %y, %z => %r = 0 Name: zext sdiv %z = zext i1 %x to i32 %r = sdiv i32 %y, %z => %r = %y Name: zext srem %z = zext i1 %x to i32 %r = srem i32 %y, %z => %r = 0 https://rise4fun.com/Alive/LZ9 llvm-svn: 335512
* Add Triple::isMIPS()/isMIPS32()/isMIPS64(). NFCAlexander Richardson2018-06-251-2/+1
| | | | | | | | | | | | | | There are quite a few if statements that enumerate all these cases. It gets even worse in our fork of LLVM where we also have a Triple::cheri (which is mips64 + CHERI instructions) and we had to update all if statements that check for Triple::mips64 to also handle Triple::cheri. This patch helps to reduce our diff to upstream and should also make some checks more readable. Reviewed By: atanasyan Differential Revision: https://reviews.llvm.org/D48548 llvm-svn: 335493
* [DA] Delinearise AddRecs if we can prove they don't wrapDavid Green2018-06-251-2/+21
| | | | | | | | | | | We can prove that some delinearized subscripts do not wrap around to become negative by the fact that they are from inbound geps of load/store locations. This helps improve the delinearisation in cases where we can't prove that they are non-negative from SCEV alone. Differential Revision: https://reviews.llvm.org/D48481 llvm-svn: 335481
* [MSSA] Add domination number verifier; NFCGeorge Burgess IV2018-06-251-0/+39
| | | | | | | | | | | It's easy for domination numbers to get out-of-date, and this is no more costly than any of the other verifiers we already have, so it seems nice to have. A stage3 build with this Works On My Machine, so this hasn't caught any bugs... yet. :) llvm-svn: 335444
* [MSSA] Remove incorrect comment + `auto`ify dyn_cast results; NFCGeorge Burgess IV2018-06-221-6/+5
| | | | llvm-svn: 335399
* [LegacyPM] Fix PR37888 by teaching the legacy loop pass manager how toChandler Carruth2018-06-221-1/+10
| | | | | | | | | | | | | | | | | clear out deleted loops from the current queue beyond just the current loop. This is important because SimpleLoopUnswitch will now enqueue the same loop to be re-processed. When it does this with the legacy PM, we don't have a way of canceling the rest of the pipeline and so we can end up deleting the loop before we reprocess it. =/ This change also makes it easy to support deleting other loops in the queue to process, although I don't have any use cases for that. Differential Revision: https://reviews.llvm.org/D48470 llvm-svn: 335317
* [SCEV] Re-apply r335197 (with Polly fixes).Tim Shen2018-06-211-0/+54
| | | | | | | | | | | | | | | | | Summary: This initiates a discussion on changing Polly accordingly while re-applying r335197 (D48338). I have never worked on Polly. The proposed change to param_div_div_div_2.ll is not educated, but just patterns that match the output. All LLVM files are already reviewed in D48338. Reviewers: jdoerfert, bollu, efriedma Subscribers: jlebar, sanjoy, hiraditya, llvm-commits, bixia Differential Revision: https://reviews.llvm.org/D48453 llvm-svn: 335292
* [DA] Enable -da-delinearize by defaultDavid Green2018-06-211-9/+54
| | | | | | | | | | | | | This enables da-delinearize in Dependence Analysis for delinearizing array accesses into multiple dimensions. This can help to increase the power of Dependence analysis on multi-dimensional arrays and prevent having to fall back to the slower and less accurate MIV tests. It adds static checks on the bounds of the arrays to ensure that one dimension doesn't overflow into another, and brings our code in line with our tests. Differential Revision: https://reviews.llvm.org/D45872 llvm-svn: 335217
* Revert "[SCEV] Improve zext(A /u B) and zext(A % B)"Tim Shen2018-06-211-54/+0
| | | | | | This reverts commit r335197, as some bots are not happy. llvm-svn: 335198
* [SCEV] Improve zext(A /u B) and zext(A % B)Tim Shen2018-06-211-0/+54
| | | | | | | | | | | | | | | Summary: Try to match udiv and urem patterns, and sink zext down to the leaves. I'm not entirely sure why some unrelated tests change, but the added <nsw>s seem right. Reviewers: sanjoy Subscribers: jlebar, hiraditya, bixia, llvm-commits Differential Revision: https://reviews.llvm.org/D48338 llvm-svn: 335197
* [MemorySSA] Verify Phi incoming blocks are block predecessors.Alina Sbirlea2018-06-201-1/+5
| | | | | | | | | | | | Summary: Make the MemorySSA verify also check that all Phi incoming blocks are block predecessors. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D48333 llvm-svn: 335174
* [InstSimplify] Fix missed optimization in simplifyUnsignedRangeCheck()Sanjay Patel2018-06-201-1/+1
| | | | | | | | | | | | | | | | | | | | | For both operands are unsigned, the following optimizations are valid, and missing: 1. X > Y && X != 0 --> X > Y 2. X > Y || X != 0 --> X != 0 3. X <= Y || X != 0 --> true 4. X <= Y || X == 0 --> X <= Y 5. X > Y && X == 0 --> false unsigned foo(unsigned x, unsigned y) { return x > y && x != 0; } should fold to x > y, but I found we haven't done it right now. besides, unsigned foo(unsigned x, unsigned y) { return x < y && y != 0; } Has been folded to x < y, so there may be a bug. Patch by: Li Jia He! Differential Revision: https://reviews.llvm.org/D47922 llvm-svn: 335129
* [IR] move shuffle mask queries from TTI to ShuffleVectorInstSanjay Patel2018-06-191-168/+18
| | | | | | | | | | | | | | | | The optimizer is getting smarter (eg, D47986) about differentiating shuffles based on its mask values, so we should make queries on the mask constant operand generally available to avoid code duplication. We'll probably use this soon in the vectorizers and instcombine (D48023 and https://bugs.llvm.org/show_bug.cgi?id=37806). We might clean up TTI a bit more once all of its current 'SK_*' options are covered. Differential Revision: https://reviews.llvm.org/D48236 llvm-svn: 335067
* Revert "[SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags"Sanjoy Das2018-06-191-19/+6
| | | | | | | | | | | | | | 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
* Fix namespaces. No functionality change.Benjamin Kramer2018-06-161-1/+1
| | | | llvm-svn: 334890
* Revert "[SCEV] Use LLVM_MARK_AS_BITMASK_ENUM in SCEV." -- breaks MSVC builds.Justin Lebar2018-06-161-34/+38
| | | | | | This reverts D48237. llvm-svn: 334878
* Revert "[SCEV] Simplify some flags expressions." -- dependent revision ↵Justin Lebar2018-06-161-4/+4
| | | | | | | | breaks MSVC builds. This reverts D48238. llvm-svn: 334877
* [SCEV] Simplify some flags expressions.Justin Lebar2018-06-151-4/+4
| | | | | | | | | | | | | | Summary: Sending for presubmit review out of an abundance of caution; it would be bad to mess this up. Reviewers: sanjoy Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D48238 llvm-svn: 334875
* [SCEV] Use LLVM_MARK_AS_BITMASK_ENUM in SCEV.Justin Lebar2018-06-151-38/+34
| | | | | | | | | | | | | | | | | | Summary: Obviates the need for mask/clear/setFlags helpers. There are some expressions here which can be simplified, but to keep this easy to review, I have not simplified them in this patch. No functional change. Reviewers: sanjoy Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D48237 llvm-svn: 334874
* [BPI] Remove unnecessary std::listBenjamin Kramer2018-06-151-5/+4
| | | | | | vector is sufficient here. No functionality change intended. llvm-svn: 334865
* [MSSA] Print more optimization informationGeorge Burgess IV2018-06-143-49/+71
| | | | | | | | | | | | | | In particular, when asked to print a MemoryAccess, we'll now print where defs are optimized to, and we'll print optimized access types. This patch also introduces an operator<< to make printing AliasResults easier. Patch by Juneyoung Lee! Differential Revision: https://reviews.llvm.org/D47860 llvm-svn: 334760
* [SCEV] Fix a variable name, NFC.Justin Lebar2018-06-141-6/+6
| | | | llvm-svn: 334738
* [SCEV] Simplify zext/trunc idiom that appears when handling bitmasks.Justin Lebar2018-06-141-0/+26
| | | | | | | | | | | | | | | | | | | 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] Simplify trunc-of-add/mul to add/mul-of-trunc under more circumstances.Justin Lebar2018-06-141-32/+22
| | | | | | | | | | | | | | | | | | | | Summary: Previously we would do this simplification only if it did not introduce any new truncs (excepting new truncs which replace other cast ops). This change weakens this condition: If the number of truncs stays the same, but we're able to transform trunc(X + Y) to X + trunc(Y), that's still simpler, and it may open up additional transformations. While we're here, also clean up some duplicated code. Reviewers: sanjoy Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D48160 llvm-svn: 334736
* [SCEV] Fix indentation and combine two if statements in getMulExpr, NFC.Justin Lebar2018-06-141-15/+14
| | | | llvm-svn: 334735
* [CostModel] Cleanup isSingleSourceVectorMask to match other shuffle ↵Simon Pilgrim2018-06-141-10/+12
| | | | | | matchers. NFCI. llvm-svn: 334699
* [CostModel] Recognise REVERSE shuffle mask if the elements come from the ↵Simon Pilgrim2018-06-141-4/+11
| | | | | | second src llvm-svn: 334698
* [CostModel] Recognise BROADCAST shuffle mask if the elements come from the ↵Simon Pilgrim2018-06-131-4/+11
| | | | | | second src llvm-svn: 334620
* [CostModel] Replace ShuffleKind::SK_Alternate with ShuffleKind::SK_Select ↵Simon Pilgrim2018-06-121-19/+15
| | | | | | | | | | | | | | | | | | (PR33744) As discussed on PR33744, this patch relaxes ShuffleKind::SK_Alternate which requires shuffle masks to only match an alternating pattern from its 2 sources: e.g. v4f32: <0,5,2,7> or <4,1,6,3> This seems far too restrictive as most SIMD hardware which will implement it using a general blend/bit-select instruction, so replaces it with SK_Select, permitting elements from either source as long as they are inline: e.g. v4f32: <0,5,2,7>, <4,1,6,3>, <0,1,6,7>, <4,1,2,3> etc. This initial patch just updates the name and cost model shuffle mask analysis, later patch reviews will update SLP to better utilise this - it still limits itself to SK_Alternate style patterns. Differential Revision: https://reviews.llvm.org/D47985 llvm-svn: 334513
* Fix signed/unsigned warning. NFCI.Simon Pilgrim2018-06-121-2/+2
| | | | llvm-svn: 334509
* [CostModel] Treat Identity shuffle masks as zero costSimon Pilgrim2018-06-121-0/+20
| | | | | | | | | | As discussed on D47985, identity shuffle masks should probably be free. I've limited this to the case where the input and output types all match - but we could probably accept all cases. Differential Revision: https://reviews.llvm.org/D47986 llvm-svn: 334506
* [SCEV] Add transform zext((A * B * ...)<nuw>) --> (zext(A) * zext(B) * ↵Justin Lebar2018-06-111-0/+12
| | | | | | | | | | | | ...)<nuw>. Reviewers: sanjoy Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D48041 llvm-svn: 334429
* [SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags where safe.Justin Lebar2018-06-111-6/+19
| | | | | | | | | | | | | 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
* Fix indentation in ScalarEvolution.cpp.Justin Lebar2018-06-111-26/+26
| | | | | | Whitespace-only change. (clang-formatted the whole block.) llvm-svn: 334427
* [SCEV] Canonicalize "A /u C1 /u C2" to "A /u (C1*C2)".Tim Shen2018-06-111-0/+15
| | | | | | | | | | | | Summary: FWIW InstCombine already folds this. Also avoid the case where C1*C2 overflows. Reviewers: sunfish, sanjoy Subscribers: hiraditya, bixia, llvm-commits Differential Revision: https://reviews.llvm.org/D47965 llvm-svn: 334425
* [SCEV] Look through zero-extends in howFarToZeroKrzysztof Parzyszek2018-06-081-1/+11
| | | | | | | | | | | | An expression like (zext i2 {(trunc i32 (1 + %B) to i2),+,1}<%while.body> to i32) will become zero exactly when the nested value becomes zero in its type. Strip injective operations from the input value in howFarToZero to make the value simpler. Differential Revision: https://reviews.llvm.org/D47951 llvm-svn: 334318
* [NFC][InstSimplify] SimplifyAddInst(): coding style: variable names.Roman Lebedev2018-06-081-5/+5
| | | | llvm-svn: 334299
* [InstSimplify] add nuw %x, -1 -> -1 fold.Roman Lebedev2018-06-081-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: `%ret = add nuw i8 %x, C` From [[ https://llvm.org/docs/LangRef.html#add-instruction | langref ]]: nuw and nsw stand for “No Unsigned Wrap” and “No Signed Wrap”, respectively. If the nuw and/or nsw keywords are present, the result value of the add is a poison value if unsigned and/or signed overflow, respectively, occurs. So if `C` is `-1`, `%x` can only be `0`, and the result is always `-1`. I'm not sure we want to use `KnownBits`/`LVI` here, because there is exactly one possible value (all bits set, `-1`), so some other pass should take care of replacing the known-all-ones with constant `-1`. The `test/Transforms/InstCombine/set-lowbits-mask-canonicalize.ll` change *is* confusing. What happening is, before this: (omitting `nuw` for simplicity) 1. First, InstCombine D47428/rL334127 folds `shl i32 1, %NBits`) to `shl nuw i32 -1, %NBits` 2. Then, InstSimplify D47883/rL334222 folds `shl nuw i32 -1, %NBits` to `-1`, 3. `-1` is inverted to `0`. But now: 1. *This* InstSimplify fold `%ret = add nuw i32 %setbit, -1` -> `-1` happens first, before InstCombine D47428/rL334127 fold could happen. Thus we now end up with the opposite constant, and it is all good: https://rise4fun.com/Alive/OA9 https://rise4fun.com/Alive/sldC Was mentioned in D47428 review. Follow-up for D47883. Reviewers: spatel, craig.topper Reviewed By: spatel Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D47908 llvm-svn: 334298
* [BPI] Apply invoke heuristic before loop branch heuristicArtur Pilipenko2018-06-081-11/+8
| | | | | | | | | | Currently the loop branch heuristic is applied before the invoke heuristic which makes us overestimate the probability of the unwind destination of invokes inside loops. This in turn makes us grossly underestimate the frequencies of loops with invokes. Reviewed By: skatkov, vsk Differential Revision: https://reviews.llvm.org/D47371 llvm-svn: 334285
* [InstSimplify] shl nuw C, %x -> C iff signbit is set on C.Roman Lebedev2018-06-071-0/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: `%r = shl nuw i8 C, %x` As per langref: ``` If the nuw keyword is present, then the shift produces a poison value if it shifts out any non-zero bits. ``` Thus, if the sign bit is set on `C`, then `%x` can only be `0`, which means that `%r` can only be `C`. Or in other words, set sign bit means that the signed value is negative, so the constant is `<= 0`. https://rise4fun.com/Alive/WMk https://rise4fun.com/Alive/udv Was mentioned in D47428 review. We already handle the `0` constant, https://godbolt.org/g/UZq1sJ, so this only handles negative constants. Could use computeKnownBits() / LazyValueInfo, but the cost-benefit analysis (https://reviews.llvm.org/D47891) suggests it isn't worth it. Reviewers: spatel, craig.topper Reviewed By: spatel Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D47883 llvm-svn: 334222
* [TargetLibraryInfo] add mappings from LLVM sin/cos intrinsics to SVML callsSanjay Patel2018-06-071-0/+16
| | | | | | | | | | | | | | | These weren't included in D19544 - probably just an oversight. D40044 made it more likely that we'll have LLVM math intrinsics rather than libcalls, so this bug was more easily exposed. As the tests/code show, we already have the complete mappings for pow/exp/log. I don't have any experience with SVML, so I don't know if anything else is missing. It's also not clear to me that we should be doing this transform in IR rather than DAG/isel, but that's a separate issue. Differential Revision: https://reviews.llvm.org/D47610 llvm-svn: 334211
* [ThinLTO] Rename index IsAnalysis flag to HaveGVs (NFC)Teresa Johnson2018-06-061-1/+1
| | | | | | | | | With the upcoming patch to add summary parsing support, IsAnalysis would be true in contexts where we are not performing module summary analysis. Rename to the more specific and approprate HaveGVs, which is essentially what this flag is indicating. llvm-svn: 334140
* [ValueTracking] Match select abs pattern when there's an sext involvedJohn Brawn2018-06-041-6/+18
| | | | | | | | | | | | | | When checking a select to see if it matches an abs, allow the true/false values to be a sign-extension of the comparison value instead of requiring that they're directly the comparison value, as all the comparison cares about is the sign of the value. This fixes a regression due to r333702, where we were no longer generating ctlz due to isKnownNonNegative failing to match such a pattern. Differential Revision: https://reviews.llvm.org/D47631 llvm-svn: 333927
* [DA] Fix direction vectors for weakZeroSrcSIVDavid Green2018-05-311-4/+4
| | | | | | | | | | Both weakZeroSrcSIV and weakZeroDstSIV are currently giving the same direction vectors. Fix weakZeroSrcSIVtest by flipping the directions it gives. Differential Revision: https://reviews.llvm.org/D46678 llvm-svn: 333658
* [ValueTracking] Fix endless recursion in isKnownNonZero()Karl-Johan Karlsson2018-05-301-4/+5
| | | | | | | | | | | | | | | | | | | | | Summary: The isKnownNonZero() function have checks that abort the recursion when it reaches the specified max depth. However one of the recursive calls was placed before the max depth check was done, resulting in a endless recursion that eventually triggered a segmentation fault. Fixed the problem by moving the max depth check above the first recursive call. Reviewers: Prazek, nlopes, spatel, craig.topper, hfinkel Reviewed By: hfinkel Subscribers: hfinkel, bjope, llvm-commits Differential Revision: https://reviews.llvm.org/D47531 llvm-svn: 333557
* [AliasSet] Teach the alias set how to handle atomic memcpy/memmove/memsetDaniel Neilson2018-05-301-8/+11
| | | | | | | | | Summary: The atomic variants of the memcpy/memmove/memset intrinsics can be treated the same was as the regular forms, with respect to aliasing. Update the AliasSetTracker to treat the atomic forms the same was as the regular forms. llvm-svn: 333551
* [BasicAA] Teach the analysis about atomic memcpyDaniel Neilson2018-05-291-1/+1
| | | | | | | | Summary: A simple change to derive mod/ref info from the atomic memcpy intrinsic in the same way as from the regular memcpy intrinsic. llvm-svn: 333454
* [MemorySSA] Reflow comments + clean up control flow; NFCGeorge Burgess IV2018-05-262-5/+11
| | | | | | | Style guide says `else`s after returns are iffy, and I agree. I also don't know what broke the comments here and in CFLAA, but *shrug*. llvm-svn: 333332
OpenPOWER on IntegriCloud