summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Try to appease MSVC, NFCI.Sanjoy Das2015-10-031-90/+91
| | | | | | | | This time by lifting the lambda's in `createNodeFromSelectLikePHI` to the file scope. Looks like there are differences in capture rules between clang and MSVC? llvm-svn: 249222
* Try to appease the MSVC bots, NFCI.Sanjoy Das2015-10-031-1/+1
| | | | llvm-svn: 249219
* Try to appease the MSVC bots, NFC.Sanjoy Das2015-10-021-1/+2
| | | | llvm-svn: 249216
* [SCEV] Recognize simple br-phi patternsSanjoy Das2015-10-021-141/+284
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Teach SCEV to match patterns like ``` br %cond, label %left, label %right left: br label %merge right: br label %merge merge: V = phi [ %x, %left ], [ %y, %right ] ``` as "select %cond, %x, %y". Before this SCEV would match PHI nodes exclusively to add recurrences. This addresses PR25005. Reviewers: joker.eph, joker-eph, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13378 llvm-svn: 249211
* inariant.group handling in GVNPiotr Padlewski2015-10-021-0/+69
| | | | | | | | | | | | The most important part required to make clang devirtualization works ( ͡°͜ʖ ͡°). The code is able to find non local dependencies, but unfortunatelly because the caller can only handle local dependencies, I had to add some restrictions to look for dependencies only in the same BB. http://reviews.llvm.org/D12992 llvm-svn: 249196
* [SCEV] Refactor out a createNodeForSelectSanjoy Das2015-10-021-88/+100
| | | | | | | | | | | | | Summary: We will shortly re-use this for select-like br-phi pairs. Reviewers: atrick, joker-eph, joker.eph Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D13377 llvm-svn: 249177
* [SCEV] Try to prove predicates by splitting themSanjoy Das2015-10-021-3/+33
| | | | | | | | | | | | | | | | | | | | | Summary: This change teaches SCEV that to prove `A u< B` it is sufficient to prove each of these facts individually: - B >= 0 - A s< B - A >= 0 In practice, SCEV sometimes finds it easier to prove these facts individually than to prove `A u< B` as one atomic step. Reviewers: reames, atrick, nlewycky, hfinkel Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D13042 llvm-svn: 249168
* Refactor computeKnownBits alignment handling codeArtur Pilipenko2015-09-301-53/+38
| | | | | | | | Reviewed By: reames, hfinkel Differential Revision: http://reviews.llvm.org/D12958 llvm-svn: 248892
* [ValueTracking] Lower dom-conditions-dom-blocks and dom-conditions-max-uses ↵Igor Laevsky2015-09-291-2/+2
| | | | | | | | | | thresholds On some of our benchmarks this change shows about 50% compile time improvement without any noticeable performance difference. Differential Revision: http://reviews.llvm.org/D13248 llvm-svn: 248801
* [ValueTracking] Teach isKnownNonZero about monotonically increasing PHIsJames Molloy2015-09-291-0/+20
| | | | | | | | If a PHI starts at a non-negative constant, monotonically increases (only adds of a constant are supported at the moment) and that add does not wrap, then the PHI is known never to be zero. llvm-svn: 248796
* [SCEV] Don't crash on pointer comparisonsSanjoy Das2015-09-281-2/+1
| | | | | | | | | | | | `ScalarEvolution::isImpliedCondOperandsViaNoOverflow` tries to cast the operand type of the comparison it is given to an `IntegerType`. This is incorrect because it could actually be simplifying a comparison between two pointers. Switch it to using `getTypeSizeInBits` instead, which does the right thing for both pointers and integers. Fixed PR24956. llvm-svn: 248743
* Introduce !align metadata for load instructionArtur Pilipenko2015-09-281-0/+5
| | | | | | | | Reviewed By: hfinkel Differential Revision: http://reviews.llvm.org/D12853 llvm-svn: 248721
* [InstSimplify] Fold simple known implications to truePhilip Reames2015-09-281-0/+47
| | | | | | | | | | This was split off of http://reviews.llvm.org/D13040 to make it easier to test the correctness of the implication logic. For the moment, this only handles a single easy case which shows up when eliminating and combining range checks. In the (near) future, I plan to extend this for other cases which show up in range checks, but I wanted to make those changes incrementally once the framework was in place. At the moment, the implication logic will be used by three places. One in InstSimplify (this review) and two in SimplifyCFG (http://reviews.llvm.org/D13040 & http://reviews.llvm.org/D13070). Can anyone think of other locations this style of reasoning would make sense? Differential Revision: http://reviews.llvm.org/D13074 llvm-svn: 248719
* [SCEV] identical instructions don't compute equal valuesSanjoy Das2015-09-271-1/+8
| | | | | | | | | | | | Before this change `HasSameValue` would return true for distinct `alloca` instructions if they happened to be allocating the same type (`alloca` instructions are not specified as reading memory). This change adds an explicit whitelist of instruction types for which "identical" instructions compute the same value. Fixes PR24952. llvm-svn: 248690
* [Bug 24848] Use range metadata to constant fold comparisons between two valuesChen Li2015-09-261-0/+26
| | | | | | | | | | | | | | | Summary: This is the second part of fixing bug 24848 https://llvm.org/bugs/show_bug.cgi?id=24848. If both operands of a comparison have range metadata, they should be used to constant fold the comparison. Reviewers: sanjoy, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13177 llvm-svn: 248650
* [SCEV] Reapply 'Teach isLoopBackedgeGuardedByCond to exploit trip counts'Sanjoy Das2015-09-251-0/+16
| | | | | | | | | | | | | | | | | | | | | | Summary: If the trip count of a specific backedge is `N`, then we know that backedge is effectively guarded by the condition `{0,+,1} u< N`. This change teaches SCEV to use this condition to prove things in `isLoopBackedgeGuardedByCond`. Depends on D12948 Depends on D12949 The original checkin, r248608 had to be backed out due to an issue with a ObjCXX unit test. That issue is now fixed, so re-landing. Reviewers: atrick, reames, majnemer, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12950 llvm-svn: 248638
* [SCEV] Reapply 'Exploit A < B => (A+K) < (B+K) when possible'Sanjoy Das2015-09-251-0/+143
| | | | | | | | | | | | | | | | | | | | | | | Summary: This change teaches SCEV's `isImpliedCond` two new identities: A u< B u< -C => (A + C) u< (B + C) A s< B s< INT_MIN - C => (A + C) s< (B + C) While these are useful on their own, they're really intended to support D12950. The original checkin, r248606 had to be backed out due to an issue with a ObjCXX unit test. That issue is now fixed, so re-landing. Reviewers: atrick, reames, majnemer, nlewycky, hfinkel Subscribers: aadg, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12948 llvm-svn: 248637
* Revert two SCEV changes that caused test failures in clang.Sanjoy Das2015-09-251-159/+0
| | | | | | r248606: "[SCEV] Exploit A < B => (A+K) < (B+K) when possible" r248608: "[SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts." llvm-svn: 248614
* more space; NFCSanjay Patel2015-09-251-0/+1
| | | | llvm-svn: 248609
* [SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts.Sanjoy Das2015-09-251-0/+16
| | | | | | | | | | | | | | | | | | | Summary: If the trip count of a specific backedge is `N`, then we know that backedge is effectively guarded by the condition `{0,+,1} u< N`. This change teaches SCEV to use this condition to prove things in `isLoopBackedgeGuardedByCond`. Depends on D12948 Depends on D12949 Reviewers: atrick, reames, majnemer, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12950 llvm-svn: 248608
* [SCEV] Extract helper function from isImpliedCond; NFCSanjoy Das2015-09-251-0/+8
| | | | | | | | | | | | | Summary: This new helper routine will be used in a subsequent change. Reviewers: hfinkel Subscribers: hfinkel, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12949 llvm-svn: 248607
* [SCEV] Exploit A < B => (A+K) < (B+K) when possibleSanjoy Das2015-09-251-0/+143
| | | | | | | | | | | | | | | | | | | | Summary: This change teaches SCEV's `isImpliedCond` two new identities: A u< B u< -C => (A + C) u< (B + C) A s< B s< INT_MIN - C => (A + C) s< (B + C) While these are useful on their own, they're really intended to support D12950. Reviewers: atrick, reames, majnemer, nlewycky, hfinkel Subscribers: aadg, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12948 llvm-svn: 248606
* [GlobalsAA] Teach GlobalsAA about nocaptureJames Molloy2015-09-251-1/+61
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Arguments to function calls marked "nocapture" can be marked as non-escaping. However, nocapture is defined in terms of the lifetime of the callee, and if the callee can directly or indirectly recurse to the caller, the semantics of nocapture are invalid. Therefore, we eagerly discover which SCC each function belongs to, and later can check if callee and caller of a callsite belong to the same SCC, in which case there could be recursion. This means that we can't be so optimistic in getModRefInfo(ImmutableCallsite) - previously we assumed all call arguments never aliased with an escaping global. Now we need to check, because a global could now be passed as an argument but still not escape. This also solves a related conformance problem: MemCpyOptimizer can turn non-escaping stores of globals into calls to intrinsics like llvm.memcpy/llvm/memset. This confuses GlobalsAA, which knows the global can't escape and so returns NoModRef when queried, when obviously a memcpy/memset call does indeed reference and modify its arguments. This fixes PR24800, PR24801, and PR24802. llvm-svn: 248576
* [ValueTracking] Teach isKnownNonZero a new trickJames Molloy2015-09-241-0/+17
| | | | | | | | If the shifter operand is a constant, and all of the bits shifted out are known to be zero, then if X is known non-zero at least one non-zero bit must remain. llvm-svn: 248508
* Fix a think-o in which functions these should surroundJustin Bogner2015-09-241-2/+2
| | | | llvm-svn: 248465
* Add some NDEBUG checks I accidentally dropped in r248462Justin Bogner2015-09-241-0/+2
| | | | llvm-svn: 248464
* BasicAA: Move BasicAAResult::alias out-of-line. NFCJustin Bogner2015-09-241-0/+41
| | | | | | | This makes the header more readable and cleans up some unnecessary header differences between NDEBUG and !NDEBUG. llvm-svn: 248462
* [Bug 24848] Use range metadata to constant fold comparisons with constant valuesChen Li2015-09-231-2/+32
| | | | | | | | | | | | | | | Summary: This is the first part of fixing bug 24848 https://llvm.org/bugs/show_bug.cgi?id=24848. When range metadata is provided, it should be used to constant fold comparisons with constant values. Reviewers: sanjoy, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12988 llvm-svn: 248402
* [SCEV] Introduce ScalarEvolution::getOne and getZero.Sanjoy Das2015-09-232-44/+39
| | | | | | | | | | | | | | | | | | Summary: It is fairly common to call SE->getConstant(Ty, 0) or SE->getConstant(Ty, 1); this change makes such uses a little bit briefer. I've refactored the call sites I could find easily to use getZero / getOne. Reviewers: hfinkel, majnemer, reames Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12947 llvm-svn: 248362
* Untabify.NAKAMURA Takumi2015-09-221-7/+5
| | | | llvm-svn: 248264
* Reformat comment lines.NAKAMURA Takumi2015-09-221-2/+2
| | | | llvm-svn: 248262
* Reformat.NAKAMURA Takumi2015-09-221-2/+1
| | | | llvm-svn: 248261
* [SCEV] Use SaveAndRestore<T> instead of a hand rolled struct; NFCI.Sanjoy Das2015-09-221-13/+2
| | | | | | | `ClearWalkingBEDominatingCondsOnExit` is exactly `SaveAndRestore<bool>`, so use `SaveAndRestore<bool>` instead. llvm-svn: 248227
* Fix for pr24866Philip Reames2015-09-211-1/+8
| | | | | | Turns out that not every basic block is guaranteed to have a node within the DominatorTree. This is really hard to trigger, but the test case from the PR managed to do so. There's active discussion continuing about what documentation and/or invariants needed cleaned up. llvm-svn: 248216
* [DivergenceAnalysis] Separated definition of class into header.Marcello Maggioni2015-09-211-54/+25
| | | | | | | | | | | | The definition of the DivergenceAnalysis pass was in a CPP file and wasn't accessible to users of the analysis to get it through "getAnalysis<>()". This patch extracts the definition into a separate header that can be used by users of the analysis to fetch the results. Patch by Volkan Keles (vkeles@apple.com) llvm-svn: 248186
* Clean up: Refactoring the hardcoded value of 6 for ↵Larisse Voufo2015-09-182-2/+15
| | | | | | FindAvailableLoadedValue()'s parameter MaxInstsToScan. (Complete version of r247497. See D12886) llvm-svn: 248022
* [LazyValueInfo] Report nonnull range for nonnull pointersIgor Laevsky2015-09-181-2/+4
| | | | | | | | | | | | Currently LazyValueInfo will report only alloca's as having nonnull range. For loads with !nonnull metadata it will bailout with no additional information. Same is true for calls returning nonnull pointers. This change extends LazyValueInfo to handle additional nonnull instructions. Differential Revision: http://reviews.llvm.org/D12932 llvm-svn: 247985
* Support align attribute for return valuesArtur Pilipenko2015-09-181-0/+2
| | | | | | | | Reviewed By: reames Differential Revision: http://reviews.llvm.org/D12844 llvm-svn: 247984
* fix typo; NFCSanjay Patel2015-09-171-1/+1
| | | | llvm-svn: 247938
* [SCEV] Use auto instead of full iterator type; NFCI.Sanjoy Das2015-09-171-2/+1
| | | | llvm-svn: 247919
* ScalarEvolution: added tmp to avoid use-after-dtor in for loop.Naomi Musgrave2015-09-161-2/+5
| | | | | | | | | | | | | | | | | Summary: For loop destroyed current instance before invoking next. Temporary variable added to prevent use-after-dtor when invoke destructor on current instance. Reviewers: eugenis Subscribers: llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D12912 Rename temp var. llvm-svn: 247867
* constify the Function parameter to the TTI creation callback andEric Christopher2015-09-161-4/+4
| | | | | | propagate to all callers/users/etc. llvm-svn: 247864
* Revert "Clean up: Refactoring the hardcoded value of 6 for ↵Larisse Voufo2015-09-151-3/+2
| | | | | | FindAvailableLoadedValue()'s parameter MaxInstsToScan." for preliminary community discussion (See. D12886) llvm-svn: 247716
* 80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; ↵Sanjay Patel2015-09-151-4/+5
| | | | | | NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC80-cols; NFC llvm-svn: 247700
* [InstCombineCalls] Use isKnownNonNullAt() to check nullness of passing ↵Chen Li2015-09-141-0/+4
| | | | | | | | | | | | | | arguments at callsite Summary: This patch replaces isKnownNonNull() with isKnownNonNullAt() when checking nullness of passing arguments at callsite. In this way it can handle cases where the argument does not have nonnull attribute but has a dominating null check from the CFG. It also adds assertions in isKnownNonNull() and isKnownNonNullFromDominatingCondition() to make sure the value checked is pointer type (as defined in LLVM document). These assertions might trip failures in things which are not covered under llvm/test, but fixes should be pretty obvious. Reviewers: reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12779 llvm-svn: 247587
* GlobalsAAResult: Try to fix crash.NAKAMURA Takumi2015-09-141-10/+16
| | | | | | | | | | | | DeletionCallbackHandle holds GAR in its creation. It assumes; - It is registered as CallbackVH. It should not be moved in its life. - Its parent, GAR, may be moved. To move list<DeletionCallbackHandle> GlobalsAAResult::Handles, GAR must be updated with the destination in GlobalsAAResult(&&). llvm-svn: 247534
* Clean up: Refactoring the hardcoded value of 6 for ↵Larisse Voufo2015-09-121-2/+3
| | | | | | FindAvailableLoadedValue()'s parameter MaxInstsToScan. llvm-svn: 247497
* [SCEV] Consistently Handle Expressions That Cannot Be DividedMatthew Simpson2015-09-101-36/+26
| | | | | | | | | | | | | | | | This patch addresses the issue of SCEV division asserting on some input expressions (e.g., non-affine expressions) and quietly giving up on others. When giving up, we set the quotient to be equal to zero and the remainder to be equal to the numerator. With this patch, we always quietly give up when we cannot perform the division. This patch also adds a test case for DependenceAnalysis that previously caused an assertion. Differential Revision: http://reviews.llvm.org/D11725 llvm-svn: 247314
* GlobalsAAResult(&&): Move every members.NAKAMURA Takumi2015-09-101-1/+6
| | | | | | Or, one of MSVC builders failed with unexpected behavior. llvm-svn: 247247
* [ScalarEvolution] Fix PR24757.Sanjoy Das2015-09-101-2/+42
| | | | | | | | | | | | | | | | | | | Summary: PR24757 was caused by some incorect math in `ScalarEvolution::HowFarToZero` -- the smallest unsigned solution for X in 2^N * A = 2^N * X is not necessarily A. Reviewers: atrick, majnemer, meheff Subscribers: llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D12721 llvm-svn: 247242
OpenPOWER on IntegriCloud