summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LazyValueInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Fix a warning introduced in r288874Philip Reames2016-12-071-1/+0
| | | | llvm-svn: 288884
* [LVI] Remove used return value from markX functionsPhilip Reames2016-12-071-28/+26
| | | | llvm-svn: 288874
* [LVI] Simplify mergeIn codePhilip Reames2016-12-071-24/+20
| | | | | | Remove the unused return type, use early return, use assignment operator. llvm-svn: 288873
* [LVI] Simplify obfuscated codePhilip Reames2016-12-071-14/+0
| | | | | | It doesn't matter why something is overdefined if it is... llvm-svn: 288871
* [LVI] Remove dead code in mergeInPhilip Reames2016-12-061-18/+0
| | | | | | Integers are expressed in the lattice via constant ranges. They can never be represented by constants or not-constants; those are reserved for non-integer types. This code has been dead for literaly years. llvm-svn: 288767
* [LVI] Extract a helper functionPhilip Reames2016-12-061-32/+22
| | | | | | Extracting a helper function out of solveBlockValue makes the contract around the cache much easier to understand. llvm-svn: 288766
* [LVI] Hide the last markX function on LVILatticeValPhilip Reames2016-12-061-10/+10
| | | | | | This completes a small series of patches to hide the stateful updates of LVILatticeVal from the consuming code. The only remaining stateful API is mergeIn. llvm-svn: 288765
* [LVI] Hide a confusing internal interfacePhilip Reames2016-12-061-16/+19
| | | | llvm-svn: 288764
* [LVI] Remove duplicate code using existing helper functionPhilip Reames2016-12-061-6/+2
| | | | llvm-svn: 288761
* Factor out common parts of LVI and Float2Int into ConstantRange [NFCI]Philip Reames2016-12-011-50/+4
| | | | | | | | | | This just extracts out the transfer rules for constant ranges into a single shared point. As it happens, neither bit of code actually overlaps in terms of the handled operators, but with this change that could easily be tweaked in the future. I also want to have this separated out to make experimenting with a eager value info implementation and possibly a ValueTracking-like fixed depth recursion peephole version. There's no reason all four of these can't share a common implementation which reduces the chances of bugs. Differential Revision: https://reviews.llvm.org/D27294 llvm-svn: 288413
* Revert previous whitespace changePhilip Reames2016-12-011-1/+0
| | | | llvm-svn: 288312
* Test commit of whitespace to check permissions.Philip Reames2016-12-011-0/+1
| | | | llvm-svn: 288311
* [PM] Change the static object whose address is used to uniquely identifyChandler Carruth2016-11-231-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | analyses to have a common type which is enforced rather than using a char object and a `void *` type when used as an identifier. This has a number of advantages. First, it at least helps some of the confusion raised in Justin Lebar's code review of why `void *` was being used everywhere by having a stronger type that connects to documentation about this. However, perhaps more importantly, it addresses a serious issue where the alignment of these pointer-like identifiers was unknown. This made it hard to use them in pointer-like data structures. We were already dodging this in dangerous ways to create the "all analyses" entry. In a subsequent patch I attempted to use these with TinyPtrVector and things fell apart in a very bad way. And it isn't just a compile time or type system issue. Worse than that, the actual alignment of these pointer-like opaque identifiers wasn't guaranteed to be a useful alignment as they were just characters. This change introduces a type to use as the "key" object whose address forms the opaque identifier. This both forces the objects to have proper alignment, and provides type checking that we get it right everywhere. It also makes the types somewhat less mysterious than `void *`. We could go one step further and introduce a truly opaque pointer-like type to return from the `ID()` static function rather than returning `AnalysisKey *`, but that didn't seem to be a clear win so this is just the initial change to get to a reliably typed and aligned object serving is a key for all the analyses. Thanks to Richard Smith and Justin Lebar for helping pick plausible names and avoid making this refactoring many times. =] And thanks to Sean for the super fast review! While here, I've tried to move away from the "PassID" nomenclature entirely as it wasn't really helping and is overloaded with old pass manager constructs. Now we have IDs for analyses, and key objects whose address can be used as IDs. Where possible and clear I've shortened this to just "ID". In a few places I kept "AnalysisID" to make it clear what was being identified. Differential Revision: https://reviews.llvm.org/D27031 llvm-svn: 287783
* [LVI] Fix a bug with a guard being the very first instruction in a BB not ↵Artur Pilipenko2016-10-211-5/+4
| | | | | | | | taken into account While looking for guards use reverse iterator and scan up to rend() not to begin() llvm-svn: 284827
* Remove duplicated code; NFCSanjoy Das2016-10-021-2/+2
| | | | | | | ICmpInst::makeConstantRange does exactly the same thing as ConstantRange::makeExactICmpRegion. llvm-svn: 283059
* Add some shortcuts in LazyValueInfo to reduce compile time of Correlated ↵Wei Mi2016-09-151-0/+29
| | | | | | | | | | | | | | | Value Propagation. The patch is to partially fix PR10584. Correlated Value Propagation queries LVI to check non-null for pointer params of each callsite. If we know the def of param is an alloca instruction, we know it is non-null and can return early from LVI. Similarly, CVP queries LVI to check whether pointer for each mem access is constant. If the def of the pointer is an alloca instruction, we know it is not a constant pointer. These shortcuts can reduce the cost of CVP significantly. Differential Revision: https://reviews.llvm.org/D18066 llvm-svn: 281586
* [LVI] Complete the abstract of the cache layer [NFCI]Philip Reames2016-09-121-72/+94
| | | | | | | | Convert the previous introduced is-a relationship between the LVICache and LVIImple clases into a has-a relationship and hide all the implementation details of the cache from the lazy query layer. The only slightly concerning change here is removing the addition of a queried block into the SeenBlock set in LVIImpl::getBlockValue. As far as I can tell, this was effectively dead code. I think it *used* to be the case that getCachedValueInfo wasn't const and might end up inserting elements in the cache during lookup. That's no longer true and hasn't been for a while. I did fixup the const usage to make that more obvious. llvm-svn: 281272
* [LVI] Sink a couple more cache manipulation routines into the cache itself ↵Philip Reames2016-09-121-36/+45
| | | | | | | | [NFCI] The only interesting bit here is the refactor of the handle callback and even that's pretty straight-forward. llvm-svn: 281267
* [LVI] Abstract out the actual cache logic [NFCI]Philip Reames2016-09-121-89/+97
| | | | | | Seperate the caching logic from the implementation of the lazy analysis. For the moment, the lazy analysis impl has a is-a relationship with the cache; this will change to a has-a relationship shortly. This was done as two steps merely to keep the changes simple and the diff understandable. llvm-svn: 281266
* [LVI] Take guards into accountArtur Pilipenko2016-08-121-11/+29
| | | | | | | | | | Teach LVI to gather control dependant constraints from guards. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D23358 llvm-svn: 278518
* [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
OpenPOWER on IntegriCloud