summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LazyValueInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [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
* [LVI] Remove overly tight assert from 259429Philip Reames2016-02-011-2/+2
| | | | | | I'll submit a test case shortly which covers this, but it's causing clang self host problems in the builders so I wanted to get it removed. llvm-svn: 259432
* [LVI] Add select handlingPhilip Reames2016-02-011-0/+49
| | | | | | | | Teach LVI to handle select instructions in the exact same way it handles PHI nodes. This is useful since various parts of the optimizer convert PHI nodes into selects and we don't want these transformations to cause inferior optimization. Note that this patch does nothing to exploit the implied constraint on the inputs represented by the select condition itself. That will be a later patch and is blocked on http://reviews.llvm.org/D14476 llvm-svn: 259429
* [LazyValueInfo] Stop inserting overdefined values into ValueCache toAkira Hatanaka2015-12-111-18/+48
| | | | | | | | | | | | | | | | | | reduce memory usage. Previously, LazyValueInfoCache inserted overdefined lattice values into both ValueCache and OverDefinedCache. This wasn't necessary and was causing LazyValueInfo to use an excessive amount of memory in some cases. This patch changes LazyValueInfoCache to insert overdefined values only into OverDefinedCache. The memory usage decreases by 70 to 75% when one of the files in llvm is compiled. rdar://problem/11388615 Differential revision: http://reviews.llvm.org/D15391 llvm-svn: 255320
* [LVI] Update a comment to clarify what's actually happening and whyPhilip Reames2015-11-041-3/+22
| | | | llvm-svn: 252033
* Fix an unused variable warning which broke the clang-cmake-mips builderPhilip Reames2015-10-291-1/+1
| | | | llvm-svn: 251614
* [LVI/CVP] Teach LVI about range metadataPhilip Reames2015-10-291-0/+26
| | | | | | | | | | | | | | Somewhat shockingly for an analysis pass which is computing constant ranges, LVI did not understand the ranges provided by range metadata. As part of this change, I included a change to CVP primarily because doing so made it much easier to write small self contained test cases. CVP was previously only handling the non-local operand case, but given that LVI can sometimes figure out information about instructions standalone, I don't see any reason to restrict this. There could possibly be a compile time impact from this, but I suspect it should be minimal. If anyone has an example which substaintially regresses, please let me know. I could restrict the block local handling to ICmps feeding Terminator instructions if needed. Note that this patch continues a somewhat bad practice in LVI. In many cases, we know facts about values, and separate context sensitive facts about values. LVI makes no effort to distinguish and will frequently cache the same value fact repeatedly for different contexts. I would like to change this, but that's a large enough change that I want it to go in separately with clear documentation of what's changing. Other examples of this include the non-null handling, and arguments. As a meta comment: the entire motivation of this change was being able to write smaller (aka reasonable sized) test cases for a future patch teaching LVI about select instructions. Differential Revision: http://reviews.llvm.org/D13543 llvm-svn: 251606
* [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
* [LazyValueInfo] Look through Phi nodes when trying to prove a predicatePhilip Reames2015-08-311-5/+35
| | | | | | | | | | | | | | | | | | If asked to prove a predicate about a value produced by a PHI node, LazyValueInfo was unable to do so even if the predicate was known to be true for each input to the PHI. This prevented JumpThreading from eliminating a provably redundant branch. The problematic test case looks something like this: ListNode *p = ...; while (p != null) { if (!p) return; x = g->x; // unrelated p = p->next } The null check at the top of the loop is redundant since the value of 'p' is null checked on entry to the loop and before executing the backedge. This resulted in us a) executing an extra null check per iteration and b) not being able to LICM unrelated loads after the check since we couldn't prove they would execute or that their dereferenceability wasn't effected by the null check on the first iteration. Differential Revision: http://reviews.llvm.org/D12383 llvm-svn: 246465
* [LVI] Use a SmallVector instead of SmallPtrSet. NFCBruno Cardoso Lopes2015-08-211-2/+2
| | | | llvm-svn: 245739
* [LVI] Avoid iterator invalidation in LazyValueInfoCache::threadEdgeBruno Cardoso Lopes2015-08-201-1/+1
| | | | | | | Do that by copying out the elements to another SmallPtrSet. Follow up from r245309. llvm-svn: 245590
* [LVI] Use a SmallDenseMap instead of std::map for ValueCacheEntryTyBruno Cardoso Lopes2015-08-181-1/+2
| | | | | | | | | | | | | | Historically there seems to be some resistance regarding the change to DenseMap (r147980). However, I couldn't find cases of iterator invalidation for ValueCacheEntryTy, but only for ValueCache, which I left untouched. This reduces 20s on an internal testcase. Follow up from r245309. Differential Revision: http://reviews.llvm.org/D11651 rdar://problem/21320066 llvm-svn: 245314
* [LVI] Improve LazyValueInfo compile time performanceBruno Cardoso Lopes2015-08-181-29/+32
| | | | | | | | | | | | | | | | | Changes in LoopUnroll in the past six months exposed scalability issues in LazyValueInfo when used from JumpThreading. One internal test that used to take 20s under -O2 now takes 6min. This commit change the OverDefinedCache from DenseSet<std::pair<AssertingVH<BasicBlock>, Value*>> to DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>> and reduces compile time down to 1m40s. Differential Revision: http://reviews.llvm.org/D11651 rdar://problem/21320066 llvm-svn: 245309
* -Wdeprecated-clean: Fix cases of violating the rule of 5 in ways that are ↵David Blaikie2015-08-031-1/+1
| | | | | | | | | | | | | | | | | | | | | | deprecated in C++11 Various value handles needed to be copy constructible and copy assignable (mostly for their use in DenseMap). But to avoid an API that might allow accidental slicing, make these members protected in the base class and make derived classes final (the special members become implicitly public there - but disallowing further derived classes that might be sliced to the intermediate type). Might be worth having a warning a bit like -Wnon-virtual-dtor that catches public move/copy assign/ctors in classes with virtual functions. (suppressable in the same way - by making them protected in the base, and making the derived classes final) Could be fancier and only diagnose them when they're actually called, potentially. Also allow a few default implementations where custom implementations (especially with non-standard return types) were implemented. llvm-svn: 243909
* [LVI] Cleanup whitespaces. NFCBruno Cardoso Lopes2015-07-281-61/+61
| | | | llvm-svn: 243430
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-2/+2
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-2/+2
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* Move logic from JumpThreading into LazyValue info to simplify caller. Philip Reames2015-06-161-2/+34
| | | | | | | | This change is hopefully NFC. The only tricky part is that I changed the context instruction being used to the branch rather than the comparison. I believe both to be correct, but the branch is strictly more powerful. With the moved code, using the branch instruction is required for the basic block comparison test to return the same result. The previous code was able to directly access both the branch and the comparison where the revised code is not. Differential Revision: http://reviews.llvm.org/D9652 llvm-svn: 239797
* [ConstantRange] Split makeICmpRegion in two.Sanjoy Das2015-03-181-2/+2
| | | | | | | | | | | | | | | | | | | | Summary: This change splits `makeICmpRegion` into `makeAllowedICmpRegion` and `makeSatisfyingICmpRegion` with slightly different contracts. The first one is useful for determining what values some expression //may// take, given that a certain `icmp` evaluates to true. The second one is useful for determining what values are guaranteed to //satisfy// a given `icmp`. Reviewers: nlewycky Reviewed By: nlewycky Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8345 llvm-svn: 232575
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-47/+55
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Now that the DataLayout is a mandatory part of the module, let's start cleaning the codebase. This patch is a first attempt at doing that. This patch is not exactly NFC as for instance some places were passing a nullptr instead of the DataLayout, possibly just because there was a default value on the DataLayout argument to many functions in the API. Even though it is not purely NFC, there is no change in the validation. I turned as many pointer to DataLayout to references, this helped figuring out all the places where a nullptr could come up. I had initially a local version of this patch broken into over 30 independant, commits but some later commit were cleaning the API and touching part of the code modified in the previous commits, so it seemed cleaner without the intermediate state. Test Plan: Reviewers: echristo Subscribers: llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231740
* Make DataLayout Non-Optional in the ModuleMehdi Amini2015-03-041-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: DataLayout keeps the string used for its creation. As a side effect it is no longer needed in the Module. This is "almost" NFC, the string is no longer canonicalized, you can't rely on two "equals" DataLayout having the same string returned by getStringRepresentation(). Get rid of DataLayoutPass: the DataLayout is in the Module The DataLayout is "per-module", let's enforce this by not duplicating it more than necessary. One more step toward non-optionality of the DataLayout in the module. Make DataLayout Non-Optional in the Module Module->getDataLayout() will never returns nullptr anymore. Reviewers: echristo Subscribers: resistor, llvm-commits, jholewinski Differential Revision: http://reviews.llvm.org/D7992 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231270
* Reduce double set lookups.Benjamin Kramer2015-02-271-2/+1
| | | | llvm-svn: 230798
* [PM] Separate the TargetLibraryInfo object from the immutable pass.Chandler Carruth2015-01-151-3/+3
| | | | | | | | | | | | | | The pass is really just a means of accessing a cached instance of the TargetLibraryInfo object, and this way we can re-use that object for the new pass manager as its result. Lots of delta, but nothing interesting happening here. This is the common pattern that is developing to allow analyses to live in both the old and new pass manager -- a wrapper pass in the old pass manager emulates the separation intrinsic to the new pass manager between the result and pass for analyses. llvm-svn: 226157
* [PM] Move TargetLibraryInfo into the Analysis library.Chandler Carruth2015-01-151-1/+1
| | | | | | | | | | | | | | | | While the term "Target" is in the name, it doesn't really have to do with the LLVM Target library -- this isn't an abstraction which LLVM targets generally need to implement or extend. It has much more to do with modeling the various runtime libraries on different OSes and with different runtime environments. The "target" in this sense is the more general sense of a target of cross compilation. This is in preparation for porting this analysis to the new pass manager. No functionality changed, and updates inbound for Clang and Polly. llvm-svn: 226078
* remove names from comments; NFCSanjay Patel2015-01-091-40/+35
| | | | llvm-svn: 225526
* fix typos; NFCSanjay Patel2015-01-091-3/+3
| | | | llvm-svn: 225525
OpenPOWER on IntegriCloud