summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* 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
* [CFLAA] Reflow comments; NFCGeorge Burgess IV2018-05-261-6/+4
| | | | llvm-svn: 333330
* Replace AA's uses of uint64_t with LocationSize; NFC.George Burgess IV2018-05-253-26/+30
| | | | | | | | | | | | | | | | The uint64_ts that we pass around AA to represent MemoryLocation sizes are logically an Optional<uint64_t>. In D44748, we want to add an extra 'imprecise' bit to this Optional<uint64_t> to represent whether a given MemoryLocation size is an upper-bound or an exact size. For more context on why, please see D44748. That patch is quite large, but reviewers seem to be OK with the approach. In D45581 (my first attempt to split 'noise' out of D44748), reames asked that I land a precursor that is solely replacing uint64_t with LocationSize, which starts out as `using LocationSize = uint64_t;`. He also gave me the OK to submit this rename without further review. llvm-svn: 333314
* Recommit r333226 "[ValueTracking] Teach computeKnownBits that the result of ↵Craig Topper2018-05-251-0/+6
| | | | | | | | | | | | | | | | an absolute value pattern that uses nsw flag is always positive." Libfuzzer tests have been fixed to prevent being optimized. Original commit message: If the nsw flag is used in the absolute value then it is undefined for INT_MIN. For all other value it will produce a positive number. So we can assume the result is positive. This breaks some InstCombine abs/nabs combining tests because we simplify the second compare from known bits rather than as the whole pattern. Looks like we can probably fix it by adding a neg+abs/nabs combine to just swap the select operands. N Differential Revision: https://reviews.llvm.org/D47041 llvm-svn: 333300
* [MustExecute] Fix a debug invariant issue in isGuaranteedToExecute()David Stenberg2018-05-251-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: Look past debug intrinsics when querying whether an instruction is the first instruction in the header block. The commit includes a reproducer for a case where LICM would not hoist an instruction, due to the presence of the intrinsic. A caveat with this commit is that the check will not work properly if the instruction at hand is a debug intrinsic. I assume that no one depends on isGuaranteedToExecute() to return true for debug intrinsics for these cases (and that this might be an indication of another debug invariant issue), so I thought that it was not worth adding that extra bit of complexity. Reviewers: reames, anna Reviewed By: anna Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D47197 llvm-svn: 333274
* Revert r333226 "[ValueTracking] Teach computeKnownBits that the result of an ↵Craig Topper2018-05-251-6/+0
| | | | | | | | | | absolute value pattern that uses nsw flag is always positive." This breaks some libFuzzer tests. http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fuzzer/builds/15589/steps/check-fuzzer/logs/stdio Reverting to investigate llvm-svn: 333253
* [ValueTracking] Teach computeKnownBits that the result of an absolute value ↵Craig Topper2018-05-241-0/+6
| | | | | | | | | | | | pattern that uses nsw flag is always positive. If the nsw flag is used in the absolute value then it is undefined for INT_MIN. For all other value it will produce a positive number. So we can assume the result is positive. This breaks some InstCombine abs/nabs combining tests because we simplify the second compare from known bits rather than as the whole pattern. Looks like we can probably fix it by adding a neg+abs/nabs combine to just swap the select operands. Need to check alive to make sure there are no corner cases. Differential Revision: https://reviews.llvm.org/D47041 llvm-svn: 333226
* [Dominators] Add PDT constructor from FunctionJakub Kuderski2018-05-231-2/+1
| | | | | | | | | | | | | | | | Summary: This patch adds a PDT constructor from Function and lets codes previously using a local class to do this use PostDominatorTree class directly. Reviewers: davide, kuhar, grosser, dberlin Reviewed By: kuhar Author: NutshellySima Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D46709 llvm-svn: 333102
* Fix aliasing of launder.invariant.groupPiotr Padlewski2018-05-234-29/+52
| | | | | | | | | | | | | | | | | | | Summary: Patch for capture tracking broke bootstrap of clang with -fstict-vtable-pointers which resulted in debbugging nightmare. It was fixed https://reviews.llvm.org/D46900 but as it turned out, there were other parts like inliner (computing of noalias metadata) that I found after bootstraping with enabled assertions. Reviewers: hfinkel, rsmith, chandlerc, amharc, kuhar Subscribers: JDevlieghere, eraman, llvm-commits, hiraditya Differential Revision: https://reviews.llvm.org/D47088 llvm-svn: 333070
* [InstCombine] Remove calloc transformationsDavid Bolvansky2018-05-222-30/+2
| | | | | | | | | | | | | | Summary: Previous patch does not care if a value is changed between calloc and strlen. This needs to be removed from InstCombine and maybe moved to DSE later after some rework. Reviewers: efriedma Reviewed By: efriedma Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D47218 llvm-svn: 333022
* [InstCombine] Calloc-ed strings optimizationsDavid Bolvansky2018-05-222-3/+32
| | | | | | | | | | | | | | | | Summary: Example cases: strlen(calloc(...)) -> 0 Reviewers: efriedma, bkramer Reviewed By: bkramer Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D47059 llvm-svn: 332990
* [TTI] Add uniform/non-uniform constant Pow2 detection to ↵Simon Pilgrim2018-05-221-13/+28
| | | | | | | | | | | | | | | | TargetTransformInfo::getInstructionThroughput This enables us to detect more fast path sdiv cases under cost analysis. This patch also enables us to handle non-uniform-constant pow2 cases for X86 SDIV costs. Found while working on D46276 Future patches can then extend the vectorizers to more fully support non-uniform pow2 cases. Differential Revision: https://reviews.llvm.org/D46637 llvm-svn: 332969
* [EarlyCSE] Improve EarlyCSE of some absolute value cases.Craig Topper2018-05-211-0/+2
| | | | | | | | | | Change matchSelectPattern to return X and -X for ABS/NABS in a well defined order. Adjust EarlyCSE to account for this. Ensure the SPF result is some kind of min/max and not abs/nabs in one place in InstCombine that made me nervous. Prevously we returned the two operands of the compare part of the abs pattern. The RHS is always going to be a 0i, 1 or -1 constant. This isn't a very meaningful thing to return for any one. There's also some freedom in the abs pattern as to what happens when the value is equal to 0. This freedom led to early cse failing to match when different constants were used in otherwise equivalent operations. By returning the input and its negation in a defined order we can ensure an exact match. This also makes sure both patterns use the exact same subtract instruction for the negation. I believe CSE should evebntually make this happen and properly merge the nsw/nuw flags. But I'm not familiar with CSE and what order it does things in so it seemed like it might be good to really enforce that they were the same. Differential Revision: https://reviews.llvm.org/D47037 llvm-svn: 332865
* Propagate nonnull and dereferenceable throught launderPiotr Padlewski2018-05-182-3/+9
| | | | | | | | | | | | | | | Summary: invariant.group.launder should not stop propagation of nonnull and dereferenceable, because e.g. we would not be able to hoist loads speculatively. Reviewers: rsmith, amharc, kuhar, xbolva00, hfinkel Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D46972 llvm-svn: 332788
* Dissallow non-empty metadata for invariant.groupPiotr Padlewski2018-05-181-3/+3
| | | | | | | | | | | | | | | Summary: This feature is not needed, but it might be usefull in the future to use metadata to mark what which function should support it (and strip it when not). Reviewers: rsmith, sanjoy, amharc, kuhar Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D45419 llvm-svn: 332787
* Constant fold launder of null and undefPiotr Padlewski2018-05-181-1/+12
| | | | | | | | | | | | | | | Summary: This might be useful because clang will add some barriers for pointer comparisons. Reviewers: majnemer, dberlin, hfinkel, nlewycky, davide, rsmith, amharc, kuhar Subscribers: davide, amharc, llvm-commits Differential Revision: https://reviews.llvm.org/D32423 llvm-svn: 332786
* [MemDep] Fixed handling of invariant.groupPiotr Padlewski2018-05-181-5/+26
| | | | | | | | | | | | | | | | | | Summary: Memdep had funny bug related to invariant.groups - because it did not invalidated cache, in some very rare cases it was possible to show memory dependence of the instruction that was deleted, but because other instruction took it's place it resulted in call to vtable! Thanks @amharc for repro!. Reviewers: dberlin, kuhar, amharc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D45320 Co-authored-by: Krzysztof Pszeniczny <krzysztof.pszeniczny@gmail.com> llvm-svn: 332781
OpenPOWER on IntegriCloud