summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LazyValueInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [LVI] Const correct and rename the LVILatticeVal parameter to ↵Craig Topper2017-06-091-9/+8
| | | | | | | | getPredicateResult. NFC Previously it was non-const reference named Result which would tend to make someone think that it was an outparam when really its an input. llvm-svn: 305114
* [LazyValueInfo] Don't run the more complex predicate handling code for EQ ↵Craig Topper2017-06-091-8/+8
| | | | | | | | | | | | | | | | | | | and NE in getPredicateResult Summary: Unless I'm mistaken, the special handling for EQ/NE should cover everything and there is no reason to fallthrough to the more complex code. For that matter I'm not sure there's any reason to special case EQ/NE other than avoiding creating temporary ConstantRanges. This patch moves the complex code into an else so we only do it when we are handling a predicate other than EQ/NE. Reviewers: anna, reames, resistor, Farhana Reviewed By: anna Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34000 llvm-svn: 305086
* [LazyValueInfo] Make LVILatticeVal intersect method take arguments by ↵Craig Topper2017-06-081-1/+1
| | | | | | reference so we don't copy ConstantRanges unless we need to. llvm-svn: 304990
* [LazyValueInfo] Remove redundant calls to ConstantRange::contains. The same ↵Craig Topper2017-06-071-2/+2
| | | | | | exact call was made in the if above and we already know it returned true. NFC llvm-svn: 304857
* [LVI Printer] Rely on the LVI analysis functions rather than the LVI cacheAnna Thomas2017-06-061-64/+89
| | | | | | | | | | | | | | | | | | | | | | | Summary: LVIPrinter pass was previously relying on the LVICache. We now directly call the the LVI functions which solves the value if the LVI information is not already available in the cache. This has 2 benefits over the printing of LVI cache: 1. higher coverage (i.e. catches errors) in LVI code when cache value is invalidated. 2. relies on the core functions, and not dependent on the LVI cache (which may be scrapped at some point). It would still catch any cache invalidation errors, since we first go through the cache. Reviewers: reames, dberlin, sanjoy Reviewed by: reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32135 llvm-svn: 304819
* [LazyValueInfo] Use Type::getIntegerBitWidth instead of casting to ↵Craig Topper2017-06-031-2/+1
| | | | | | IntegerType to call getBitWidth. NFC llvm-svn: 304656
* [LazyValueInfo] Make solveBlockValueCast take a CastInst* instead of ↵Craig Topper2017-06-031-18/+18
| | | | | | Instruction*. Makes getOpcode return the appropriate enum without a cast. NFC llvm-svn: 304655
* [LazyValueInfo] Fix formatting NFC.Craig Topper2017-06-021-1/+1
| | | | llvm-svn: 304567
* [LazyValueInfo] Make solveBlockValueBinaryOp take a BinaryOperator* instead ↵Craig Topper2017-06-021-14/+14
| | | | | | of Instruction*. This removes a cast of getOpcode to BinaryOps. llvm-svn: 304563
* [LazyValueInfo] Fix typo in comment. NFCCraig Topper2017-06-021-1/+1
| | | | llvm-svn: 304560
* [LazyValueInfo] Avoid unnecessary copies of ConstantRangesCraig Topper2017-05-061-7/+7
| | | | | | | | | | | | | | | | | | | | | Summary: ConstantRange contains two APInts which can allocate memory if their width is larger than 64-bits. So we shouldn't copy it when we can avoid it. This changes LVILatticeVal::getConstantRange() to return its internal ConstantRange by reference. This allows many places that just need a ConstantRange reference to avoid making a copy. Several places now capture the return value of getConstantRange() by reference so they can call methods on it that don't need a new object. Lastly it adds std::move in one place to capture to move a local ConstantRange into an LVILatticeVal. Reviewers: reames, dberlin, sanjoy, anna Reviewed By: reames Subscribers: grandinj, llvm-commits Differential Revision: https://reviews.llvm.org/D32884 llvm-svn: 302331
* [LazyValueInfo] Fix typo in comment. NFCCraig Topper2017-04-281-1/+1
| | | | llvm-svn: 301655
* [IR] Redesign the case iterator in SwitchInst to actually be an iteratorChandler Carruth2017-04-121-4/+4
| | | | | | | | | | | | | | | | and to expose a handle to represent the actual case rather than having the iterator return a reference to itself. All of this allows the iterator to be used with common STL facilities, standard algorithms, etc. Doing this exposed some missing facilities in the iterator facade that I've fixed and required some work to the actual iterator to fully support the necessary API. Differential Revision: https://reviews.llvm.org/D31548 llvm-svn: 300032
* [LVIPrinterPass] Print LVI info for function argumentsAnna Thomas2017-03-231-0/+12
| | | | | | | | | Using AssemblyAnnotationWriter for LVI printer prints for instructions and basic blocks. So, we explicitly need to print LVI info for the arguments of the function (these are values and not instructions). llvm-svn: 298640
* [LVI] Add an LVI printer pass to capture test LVI cache after transformationsAnna Thomas2017-03-221-6/+96
| | | | | | | | | | | | | | | | | | | Summary: Adding a printer pass for printing the LVI cache values after transformations that use LVI. This will help us in identifying cases where LVI invariants are violated, or transforms that leave LVI in an incorrect state. Right now, I have added two test cases to show that the printer pass is working. I will be adding more test cases in a later change, once this change is checked in upstream. Reviewers: reames, dberlin, sanjoy, apilipenko Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D30790 llvm-svn: 298542
* [LVI] Add Datalayout to the class LazyValueInfo since all its Impls require ↵Anna Thomas2017-03-121-1/+1
| | | | | | it. NFC llvm-svn: 297583
* Fix Indentation. NFCIXin Tong2017-02-241-2/+2
| | | | llvm-svn: 296169
* LVI: Fix use-of-uninitialized-value after r294463Vitaly Buka2017-02-091-1/+1
| | | | | | BlockValueStack can be reallocated making reference e invalid. llvm-svn: 294572
* LVI: Add a per-value worklist limit to LazyValueInfo.Daniel Berlin2017-02-081-6/+36
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: LVI is now depth first, which is optimal for iteration strategy in terms of work per call. However, the way the results get cached means it can still go very badly N^2 or worse right now. The overdefined cache is per-block, because LVI wants to try to get different results for the same name in different blocks (IE solve the problem PredicateInfo solves). This means even if we discover a value is overdefined after going very deep, it doesn't cache this information, causing it to end up trying to rediscover it again and again. The same is true for values along the way. In practice, overdefined anywhere should mean overdefined everywhere (this is how, for example, SCCP works). Until we get around to reworking the overdefined cache, we need to limit the worklist size we process. Note that permanently reverting the DFS strategy exploration seems the wrong strategy (temporarily seems fine if we really want). BFS is clearly the wrong approach, it just gets luckier on some testcases. It's also very hard to design an effective throttle for BFS. For DFS, the throttle is directly related to the depth of the CFG. So really deep CFGs will get cutoff, smaller ones will not. As the CFG simplifies, you get better results. In BFS, the limit is it's related to the fan-out times average block size, which is harder to reason about or make good choices for. Bug being filed about the overdefined cache, but it will require major surgery to fix it (plumbing predicateinfo through CVP or LVI). Note: I did not make this number configurable because i'm not sure anyone really needs to tweak this knob. We run CVP 3 times. On the testcases i have the slow ones happen in the middle, where CVP is doing cleanup work other things are effective at. Over the course of 3 runs, we don't see to have any real loss of performance. I haven't gotten a minimized testcase yet, but just imagine in your head a testcase where, going *up* the CFG, you have branches, one of which leads 50000 blocks deep, and the other, to something where the answer is overdefined immediately. BFS would discover the overdefined faster than DFS, but do more work to do so. In practice, the right answer is "once DFS discovers overdefined for a value, stop trying to get more info about that value" (and so, DFS would normally cache the overdefined results for every value it passed through in those 50k blocks, and never do that work again. But it don't, because of the naming problem) Reviewers: chandlerc, djasper Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29715 llvm-svn: 294463
* [LVI] Switch from BFS to DFS exploration orderPhilip Reames2017-02-071-14/+16
| | | | | | | | | | | | | | This patch changes the order in which LVI explores previously unexplored paths. Previously, the code used an BFS strategy where each unexplored input was added to the search queue before any of them were explored. This has the effect of causing all inputs to be explored before returning to re-evaluate the merge point (non-local or phi node). This has the unfortunate property of doing redundant work if one of the inputs to the merge is found to be overdefined (i.e. unanalysable). If any input is overdefined, the result of the merge will be too; regardless of the values of other inputs. The new code uses a DFS strategy where we re-evaluate the merge after evaluating each input. If we discover an overdefined input, we immediately return without exploring other inputs. We have reports of large (4-10x) improvements of compile time with this patch and some reports of more precise analysis results as well. See the review discussion for details. The original motivating case was pr10584. Differential Revision: https://reviews.llvm.org/D28190 llvm-svn: 294264
* [PM] Use PoisoningVH correctly when merely deleting entries in a mapChandler Carruth2017-01-261-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | with it. This code was dereferencing the PoisoningVH which isn't allowed once it is poisoned. But the code itself really doesn't need to access the pointer, it is just doing the safe stuff of clearing out data structures keyed on the pointer value. Change the code to use iterators to erase directly from a DenseMap. This is also substantially more efficient as it avoids lots of hashing and lookups to do the erasure. DenseMap supports iterating behind the iteration which is fairly easy to implement. Sadly, I don't have a test case here. I'm not even close and I don't know that I ever will be. The issue is that several of the tricky aspects of fixing this only show up when you cause the stack's SmallVector to be in *EXACTLY* the right location. I only ever got a reproduction for those with Clang, and only with *exactly* the right command line flags. Any adjustment, even to seemingly unrelated flags, would make partial and half-way solutions magically start to "work". In good news, all of this was caught with the LLVM test suite. Also, there is no *specific* code here that is untested, just that the old pattern of code won't immediately fail on any test case I've managed to contrive. llvm-svn: 293160
* [PH] Replace uses of AssertingVH from members of analysis results withChandler Carruth2017-01-241-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | a lazy-asserting PoisoningVH. AssertVH is fundamentally incompatible with cache-invalidation of analysis results. The invaliadtion happens after the AssertingVH has already fired. Instead, use a PoisoningVH that will assert if the dangling handle is ever used rather than merely be assigned or destroyed. This patch also removes all of the (numerous) doomed attempts to work around this fundamental incompatibility. It is a pretty significant simplification IMO. The most interesting change is in the Inliner where we still do some clearing because we don't want to rely on the coarse grained invalidation strategy of the containing pass manager. However, I prefer the approach that contains this logic to the cleanup phase of the Inliner, and I think we could enhance the CGSCC analysis management layer to make this even better in the future if desired. The rest is straight cleanup. I've also added a test for one of the harder cases to work around: when a *module analysis* contains many AssertingVHes pointing at functions. Differential Revision: https://reviews.llvm.org/D29006 llvm-svn: 292928
* [PM] Teach LVI to correctly invalidate itself when its dependenciesChandler Carruth2017-01-231-0/+12
| | | | | | | | | | | | become unavailable. The AssumptionCache is now immutable but it still needs to respond to DomTree invalidation if it ended up caching one. This lets us remove one of the explicit invalidates of LVI but the other one continues to avoid hitting a latent bug. llvm-svn: 292769
* Make processing @llvm.assume more efficient - Add affected values to the ↵Hal Finkel2017-01-111-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | assumption cache Here's my second try at making @llvm.assume processing more efficient. My previous attempt, which leveraged operand bundles, r289755, didn't end up working: it did make assume processing more efficient but eliminating the assumption cache made ephemeral value computation too expensive. This is a more-targeted change. We'll keep the assumption cache, but extend it to keep a map of affected values (i.e. values about which an assumption might provide some information) to the corresponding assumption intrinsics. This allows ValueTracking and LVI to find assumptions relevant to the value being queried without scanning all assumptions in the function. The fact that ValueTracking started doing O(number of assumptions in the function) work, for every known-bits query, has become prohibitively expensive in some cases. As discussed during the review, this is a pragmatic fix that, longer term, will likely be replaced by a more-principled solution (perhaps based on an extended SSA form). Differential Revision: https://reviews.llvm.org/D28459 llvm-svn: 291671
* [LVI] Remove count/erase idiom in favor of checking result value of erasePhilip Reames2016-12-301-6/+2
| | | | | | Minor compile time win. Avoids an additional O(N) scan in the case where we are removing an element and costs nothing when we aren't. llvm-svn: 290768
* [LVI] Manually hoist computation from loopPhilip Reames2016-12-301-7/+12
| | | | | | Minor compile time win. Not known to be a hot spot, just something I noticed while reading. llvm-svn: 290759
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-21/+27
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Remove the AssumptionCacheHal Finkel2016-12-151-22/+14
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* Make processing @llvm.assume more efficient by using operand bundlesHal Finkel2016-12-151-5/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | There was an efficiency problem with how we processed @llvm.assume in ValueTracking (and other places). The AssumptionCache tracked all of the assumptions in a given function. In order to find assumptions relevant to computing known bits, etc. we searched every assumption in the function. For ValueTracking, that means that we did O(#assumes * #values) work in InstCombine and other passes (with a constant factor that can be quite large because we'd repeat this search at every level of recursion of the analysis). Several of us discussed this situation at the last developers' meeting, and this implements the discussed solution: Make the values that an assume might affect operands of the assume itself. To avoid exposing this detail to frontends and passes that need not worry about it, I've used the new operand-bundle feature to add these extra call "operands" in a way that does not affect the intrinsic's signature. I think this solution is relatively clean. InstCombine adds these extra operands based on what ValueTracking, LVI, etc. will need and then those passes need only search the users of the values under consideration. This should fix the computational-complexity problem. At this point, no passes depend on the AssumptionCache, and so I'll remove that as a follow-up change. Differential Revision: https://reviews.llvm.org/D27259 llvm-svn: 289755
* Reintroduce a check accidentally removed in 288873 to fix clang botsPhilip Reames2016-12-071-4/+12
| | | | | | I believe this is the cause of the failure, but have not been able to confirm. Note that this is a speculative fix; I'm still waiting for a full build to finish as I synced and ended up doing a clean build which takes 20+ minutes on my machine. llvm-svn: 288886
* 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
OpenPOWER on IntegriCloud