summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LazyValueInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [LVI] Fix potential memory corruption in getValueFromConditionArtur Pilipenko2016-08-121-2/+4
| | | | | | Rewrite Visited[Cond] = getValueFromConditionImpl(..., Visited) statement which can lead to a memory corruption since getValueFromConditionImpl changes Visited map and invalidates the iterators. llvm-svn: 278514
* [LVI] Take range metadata into account while calculating icmp condition ↵Artur Pilipenko2016-08-121-0/+3
| | | | | | | | | | | | | | | | | constraints Take range metadata into account for conditions like this: %length = load i32, i32* %length_ptr, !range !{i32 0, i32 2147483647} %cmp = icmp ult i32 %a, %length This is a common pattern for range checks where the length of the array is dynamically loaded. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D23267 llvm-svn: 278496
* [LVI] Handle any predicate in comparisons like icmp <pred> (add Val, ↵Artur Pilipenko2016-08-121-2/+2
| | | | | | | | | | | | | | | | | Offset), ... Currently LVI can only gather value constraints from comparisons like: * icmp <pred> Val, ... * icmp ult (add Val, Offset), ... In fact we can handle any predicate in latter comparisons. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D23357 llvm-svn: 278493
* [LVI] Handle conditions in the form of (cond1 && cond2)Artur Pilipenko2016-08-101-8/+42
| | | | | | | | | | Teach LVI how to gather information from conditions in the form of (cond1 && cond2). Our out-of-tree front-end emits range checks in this form. Reviewed By: sanjoy Differential Revision: http://reviews.llvm.org/D23200 llvm-svn: 278231
* [LVI] NFC. Make getValueFromCondition return LVILatticeValue instead of ↵Artur Pilipenko2016-08-101-25/+16
| | | | | | | | | | changing reference argument Instead of returning bool and setting LVILatticeValue reference argument return LVILattice value. Use overdefined value to denote the case when we didn't gather any information from the condition. This change was separated from the review "[LVI] Handle conditions in the form of (cond1 && cond2)" (https://reviews.llvm.org/D23200#inline-199531). Once getValueFromCondition returns LVILatticeValue we can cache the result in Visited map. llvm-svn: 278224
* [LVI] Relax the assertion about LVILatticeVal type in getConstantRangeArtur Pilipenko2016-08-101-1/+4
| | | | | | | | | | | | | | | | | | | | The problem was triggered by my recent change in CVP (D23059). Current code expected that integer constants are represented by constantrange LVILatticeVal and never represented as LVILatticeVal with constant tag. That is true for ConstantInt constants, although ConstantExpr integer type constants are legally represented as constant LVILatticeVal. This code fails with CVP change in: @b = global i32 0, align 4 define void @test6(i32 %a) { bb: %add = add i32 %a, ptrtoint (i32* @b to i32) ret void } Currently getConstantRange code is not executed by any of the upstream passes. I'm going to add a test case to test/Transforms/CorrelatedValuePropagation/add.ll once I resubmit the CVP change. Reviewed By: sanjoy Differential Revision: http://reviews.llvm.org/D23194 llvm-svn: 278217
* [LVI] Make LVI smarter about comparisons with non-constantsArtur Pilipenko2016-08-091-19/+36
| | | | | | | | | | Make LVI smarter about comparisons with a non-constant. For example, a s< b constraints a to be in [INT_MIN, INT_MAX) range. This is a part of https://llvm.org/bugs/show_bug.cgi?id=28620 fix. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D23205 llvm-svn: 278122
* Revert 278107 which causes buildbot failures and in addition has wrong ↵Artur Pilipenko2016-08-091-33/+19
| | | | | | commit message llvm-svn: 278109
* Teach CorrelatedValuePropagation to mark adds as no wrapArtur Pilipenko2016-08-091-19/+33
| | | | | | | | | | Use LVI to prove that adds do not wrap. The change is motivated by https://llvm.org/bugs/show_bug.cgi?id=28620 bug and it's the first step to fix that problem. Reviewed By: sanjoy Differential Revision: http://reviews.llvm.org/D23059 llvm-svn: 278107
* [LVI] NFC. Fix a typo Bofore -> BeforeArtur Pilipenko2016-08-091-1/+1
| | | | llvm-svn: 278105
* [LVI] NFC. On the fast dest path use inverse predicate instead of inverse ↵Artur Pilipenko2016-08-081-4/+5
| | | | | | | | | | range result Gathering constantins from a condition on the false path ask makeAllowedICmpRegion about inverse predicate instead of inversing the resulting range. This change was separated from the review "[LVI] Make LVI smarter about comparisons with non-constants" (https://reviews.llvm.org/D23205#inline-198361) llvm-svn: 278009
* [LVI] NFC. Rename confusing local NegOffset to OffsetArtur Pilipenko2016-08-081-6/+6
| | | | | | NegOffset is not necessarily negative llvm-svn: 278008
* [LVI] NFC. Extract LHS, RHS, Predicate locals in getValueFromConditionArtur Pilipenko2016-08-081-11/+14
| | | | llvm-svn: 278007
* [LVI] NFC. Sink a condition type check from the caller down to ↵Artur Pilipenko2016-08-021-31/+33
| | | | | | | | getValueFromCondition This is a preparatory refactoring to support conditions other than ICmpInst. llvm-svn: 277479
* [LVI] NFC. Fix a typo getValueFromFromCondition -> getValueFromConditionArtur Pilipenko2016-08-021-11/+9
| | | | llvm-svn: 277466
* [LVI] Use DenseMap::find_as in LazyValueInfo.Justin Lebar2016-07-271-15/+29
| | | | | | | | | | | | | | | | | | | | | | Summary: This lets us avoid creating and destroying a CallbackVH every time we check the cache. This is good for a 2% e2e speedup when compiling one of the large Eigen tests at -O3. FTR, I tried making the ValueCache hashtable one-level -- i.e., mapping a pair (Value*, BasicBlock*) to a lattice value, and that didn't seem to provide any additional improvement. Saving a word in LVILatticeVal by merging the Tag and Val fields also didn't yield a speedup. Reviewers: reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D21951 llvm-svn: 276926
* Trailing whitespace.NAKAMURA Takumi2016-07-251-4/+4
| | | | llvm-svn: 276596
* Reformat blank lines.NAKAMURA Takumi2016-07-041-9/+8
| | | | llvm-svn: 274481
* Reformat comment lines.NAKAMURA Takumi2016-07-041-8/+8
| | | | llvm-svn: 274480
* Untabify.NAKAMURA Takumi2016-07-041-1/+1
| | | | llvm-svn: 274479
* Reformat.NAKAMURA Takumi2016-07-041-28/+25
| | | | llvm-svn: 274478
* Apply clang-tidy's modernize-loop-convert to lib/Analysis.Benjamin Kramer2016-06-261-2/+2
| | | | | | Only minor manual fixes. No functionality change intended. llvm-svn: 273816
* [PM] Port LVI to the new PM.Sean Silva2016-06-131-12/+26
| | | | | | | | | | | | | | | | | | | This is a bit gnarly since LVI is maintaining its own cache. I think this port could be somewhat cleaner, but I'd rather not spend too much time on it while we still have the old pass hanging around and limiting how much we can clean things up. Once the old pass is gone it will be easier (less time spent) to clean it up anyway. This is the last dependency needed for porting JumpThreading which I'll do in a follow-up commit (there's no printer pass for LVI or anything to test it, so porting a pass that depends on it seems best). I've been mostly following: r269370 / D18834 which ported Dependence Analysis r268601 / D19839 which ported BPI llvm-svn: 272593
* Apply most suggestions of clang-tidy's performance-unnecessary-value-paramBenjamin Kramer2016-06-081-1/+1
| | | | | | | Avoids unnecessary copies. All changes audited & pass tests with asan. No functional change intended. llvm-svn: 272190
* [LazyValueInfo] Simplify `return after else`. NFCI.Davide Italiano2016-05-251-4/+3
| | | | llvm-svn: 270779
* [LVI] Add an API to LazyValueInfo so that it can export ConstantRangesJohn Regehr2016-05-021-0/+16
| | | | | | | | | that it computes. Currently this is used for testing and precision tuning, but it might be used by optimizations later. Differential Revision: http://reviews.llvm.org/D19179 llvm-svn: 268291
* [LVI] Delete stale and misleading comment.Philip Reames2016-04-271-5/+0
| | | | llvm-svn: 267661
* [LVI] Add a comment explaining a subtle piece of codePhilip Reames2016-04-271-15/+23
| | | | | | Or at least, I didn't understand the implications the first several times I read it it. llvm-svn: 267648
* [LVI] Reduce compile time by lazily scanning blocks if neededPhilip Reames2016-04-271-26/+26
| | | | | | | | | | When encountering a non-local pointer, LVI would eagerly scan the block for dereferences of the given object to prove the pointer to be non null. That's all well and good, but *then* we'd go recurse through our input blocks. As a result, we could end up scanning each and every block we traverse, even if the final definition was obviously non null or we found a constant value somewhere up the chain. The previous code papered over this by using the isKnownNonNull routine from value tracking. This made the duplication less painful in the common case. Instead, we know do the block scan only *after* we've gotten the recursive results back. This lets us stop scanning individual blocks as soon as we've determined it to be non-null in any predecessor block and use our usual merge rules to propagate that information cheaply through successor blocks. For a pointer which can be found non-null, this does strictly less work and sometimes substaintially so. Note that the case where we *can't* prove something non-null is still the really expensive case. We end up scanning each and every block looking for a dereference and never end up finding one. llvm-svn: 267642
* [LVI] Cut short search if we know we can't return a useful resultPhilip Reames2016-04-261-9/+44
| | | | | | Previously we were recursing on our operands for unary and binary operators regardless of whether we knew how to reason about the operator in question. This has the effect of doing a potentially large amount of work, only to throw it away. By checking whether the operation is one LVI can handle, we can cut short the search and return the (overdefined) answer more quickly. The quality of the results produced should not change. llvm-svn: 267626
* [LVI] Apply transfer rule for overdefine inputs for binary operatorsPhilip Reames2016-04-261-11/+16
| | | | | | | | As pointed out by John Regehr over in http://reviews.llvm.org/D19485, LVI was being incredibly stupid about applying its transfer rules. Rather than gathering local facts from the expression itself, it was simply giving up entirely if one of the inputs was overdefined. This greatly impacts the precision of the overall analysis and makes it far more fragile as well. This patch builds on 267609 which did the same thing for unary casts. llvm-svn: 267620
* [LVI] A better fix for the assertion error introduced by 267609Philip Reames2016-04-261-10/+11
| | | | | | Essentially, I was using the wrong size function. For types which were sized, but not primitive, I wasn't getting a useful size for the operand and failed an assert. I fixed this, and also added a guard that the input is a sized type. Test case is for the original mistake. I'm not sure how to actually exercise the sized type check. llvm-svn: 267618
* [LVI] Speculative fix for assertion seen in clang botsPhilip Reames2016-04-261-0/+6
| | | | | | I'll clean this up and add a test case shortly. I want to make sure this does actually fix the bots; if not, I'll revert. llvm-svn: 267617
* [LVI] Infer local facts from unary expressionsPhilip Reames2016-04-261-16/+20
| | | | | | | | | | As pointed out by John Regehr over in http://reviews.llvm.org/D19485, LVI was being incredibly stupid about applying its transfer rules. Rather than gathering local facts from the expression itself, it was simply giving up entirely if one of the inputs was overdefined. This greatly impacts the precision of the overall analysis and makes it far more fragile as well. This patch implements only the unary operation case. Once this is in, I'll implement the same for the binary operations. Differential Revision: http://reviews.llvm.org/D19492 llvm-svn: 267609
* [LVI] Make a precondition explicit rather than handling a case which never ↵Philip Reames2016-04-251-1/+2
| | | | | | happens [NFC] llvm-svn: 267481
* [LVI] Clarify comments describing the lattice valuesPhilip Reames2016-04-251-5/+10
| | | | | | There has been much recent confusion about the partition in the lattice between constant and non-constant values. Hopefully, documenting this will prevent confusion going forward. llvm-svn: 267440
* [LVI] Split solveBlockValueConstantRange into two [NFC]Philip Reames2016-04-251-31/+63
| | | | | | This function handled both unary and binary operators. Cloning and specializing leads to much easier to follow code with minimal duplicatation. llvm-svn: 267438
* [LVI] Fix a bug which prevented use of !range metadata within a queryPhilip Reames2016-03-041-22/+10
| | | | | | The diff is relatively large since I took a chance to rearrange the code I had to touch in a more obvious way, but the key bit is merely using the !range metadata when we can't analyze the instruction further. The previous !range metadata code was essentially just dead since no binary operator or cast will have !range metadata (per Verifier) and it was otherwise dropped on the floor. llvm-svn: 262751
* Suppress an uncovered switch warning [NFC]Philip Reames2016-02-271-0/+1
| | | | llvm-svn: 262109
* [LVI] Extend select handling to catch min/max/clamp idiomsPhilip Reames2016-02-261-3/+71
| | | | | | | | | | Most of this is fairly straight forward. Add handling for min/max via existing matcher utility and ConstantRange routines. Add handling for clamp by exploiting condition constraints on inputs. Note that I'm only handling two constant ranges at this point. It would be reasonable to consider treating overdefined as a full range if the instruction is typed as an integer, but that should be a separate change. Differential Revision: http://reviews.llvm.org/D17184 llvm-svn: 262085
* [LVI] Move ConstantRanges instead of copying.Benjamin Kramer2016-02-201-9/+8
| | | | | | | | No functional change intended. Copying small (<= 64 bits) APInts isn't expensive but bloats code by generating the slow path everywhere. Moving doesn't care about the size of the value. llvm-svn: 261426
* Revert 260705, it appears to be causing pr26628Philip Reames2016-02-161-21/+0
| | | | | | The root issue appears to be a confusion around what makeNoWrapRegion actually does. It seems likely we need two versions of this function with slightly different semantics. llvm-svn: 260981
* [LVI] Exploit nsw/nuw when computing constant rangesPhilip Reames2016-02-121-0/+21
| | | | | | | | | | As the title says. Modelled after similar code in SCEV. This is useful when analysing induction variables in loops which have been canonicalized by other passes. I wrote the tests as non-loops specifically to avoid the generality introduced in http://reviews.llvm.org/D17174. While that can handle many induction variables without *needing* to exploit nsw, there's no reason not to use it if we've already proven it. Differential Revision: http://reviews.llvm.org/D17177 llvm-svn: 260705
* [LVI] Improve select handling to use conditionPhilip Reames2016-02-121-0/+19
| | | | | | | | | | This patches teaches LVI to recognize clamp idioms (e.g. select(a > 5, a, 5) will always produce something greater than 5. The tests end up being somewhat simplistic because trying to exercise the case I actually care about (a loop with a range check on a clamped secondary induction variable) ends up tripping across a couple of other imprecisions in the analysis. Ah, the joys of LVI... Differential Revision: http://reviews.llvm.org/D16827 llvm-svn: 260627
* [LVI] Handle constants defensivelyPhilip Reames2016-02-101-3/+7
| | | | | | | | | | There's nothing preventing callers of LVI from asking for lattice values representing a Constant. In fact, given that several callers are walking back through PHI nodes and trying to simplify predicates, such queries are actually quite common. This is mostly harmless today, but we start volatiling assertions if we add new calls to getBlockValue in otherwise reasonable places. Note that this change is not NFC. Specifically: 1) The result returned through getValueAt will now be more precise. In principle, this could trigger any latent infinite optimization loops in callers, but in practice, we're unlikely to see this. 2) The result returned through getBlockValueAt is potentially weakened for non-constants that were previously queried. With the old code, you had the possibility that a later query might bypass the cache and discover some information the original query did not. I can't find a scenario which actually causes this to happen, but it was in principle possible. On the other hand, this may end up reducing compile time when the same value is queried repeatedly. llvm-svn: 260439
* [LVI] Fix debug outputPhilip Reames2016-02-021-3/+3
| | | | | | Due to staleness in a patch I committed yesterday, the debug output was reporting overdefined cases as being undefined. Confusing to say the least. The mistake appears to have only effected the debug output thankfully. llvm-svn: 259594
* [LVI] Code motion only [NFC]Philip Reames2016-02-021-64/+62
| | | | | | I introduced a declaration in 259583 to keep the diff readable. This change just moves the definition up to remove the declaration again. llvm-svn: 259585
* [LVI] Refactor to use newly introduced intersect utility Philip Reames2016-02-021-32/+19
| | | | | | | | This patch uses the newly introduced 'intersect' utility (from 259461: [LVI] Introduce an intersect operation on lattice values) to simplify existing code in LVI. While not introducing any new concepts, this change is probably not NFC. The common 'intersect' function is more powerful that the ad-hoc implementations we'd had in a couple of places. Given that, we may see optimizations triggering a bit more often. llvm-svn: 259583
* [LVI] Introduce an intersect operation on lattice valuesPhilip Reames2016-02-021-32/+85
| | | | | | | | | | | | LVI has several separate sources of facts - edge local conditions, recursive queries, assumes, and control independent value facts - which all apply to the same value at the same location. The existing implementation was very conservative about exploiting all of these facts at once. This change introduces an "intersect" function specifically to abstract the action of picking a good set of facts from all of the separate facts given. At the moment, this function is relatively simple (i.e. mostly just reuses the bits which were already there), but even the minor additions reveal the inherent power. For example, JumpThreading is now capable of doing an inductive proof that a particular value is always positive and removing a half range check. I'm currently only using the new intersect function in one place. If folks are happy with the direction of the work, I plan on making a series of small changes without review to replace mergeIn with intersect at all the appropriate places. Differential Revision: http://reviews.llvm.org/D14476 llvm-svn: 259461
* [LVI] Fix a latent bug in getValueAtPhilip Reames2016-02-021-0/+8
| | | | | | | | This routine was returning Undefined for most queries. This was utterly wrong. Amusingly, we do not appear to have any callers of this which are actually trying to exploit unreachable code or this would have broken the world. A better approach would be to explicit describe the intersection of facts. That's blocked behind http://reviews.llvm.org/D14476 and I wanted to fix the current bug. llvm-svn: 259446
OpenPOWER on IntegriCloud