aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/LazyValueInfo.cpp
AgeCommit message (Collapse)AuthorFilesLines
2017-06-08[LazyValueInfo] Make LVILatticeVal intersect method take arguments by ↵Craig Topper1-1/+1
reference so we don't copy ConstantRanges unless we need to. llvm-svn: 304990
2017-06-07[LazyValueInfo] Remove redundant calls to ConstantRange::contains. The same ↵Craig Topper1-2/+2
exact call was made in the if above and we already know it returned true. NFC llvm-svn: 304857
2017-06-06[LVI Printer] Rely on the LVI analysis functions rather than the LVI cacheAnna Thomas1-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
2017-06-03[LazyValueInfo] Use Type::getIntegerBitWidth instead of casting to ↵Craig Topper1-2/+1
IntegerType to call getBitWidth. NFC llvm-svn: 304656
2017-06-03[LazyValueInfo] Make solveBlockValueCast take a CastInst* instead of ↵Craig Topper1-18/+18
Instruction*. Makes getOpcode return the appropriate enum without a cast. NFC llvm-svn: 304655
2017-06-02[LazyValueInfo] Fix formatting NFC.Craig Topper1-1/+1
llvm-svn: 304567
2017-06-02[LazyValueInfo] Make solveBlockValueBinaryOp take a BinaryOperator* instead ↵Craig Topper1-14/+14
of Instruction*. This removes a cast of getOpcode to BinaryOps. llvm-svn: 304563
2017-06-02[LazyValueInfo] Fix typo in comment. NFCCraig Topper1-1/+1
llvm-svn: 304560
2017-05-06[LazyValueInfo] Avoid unnecessary copies of ConstantRangesCraig Topper1-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
2017-04-28[LazyValueInfo] Fix typo in comment. NFCCraig Topper1-1/+1
llvm-svn: 301655
2017-04-12[IR] Redesign the case iterator in SwitchInst to actually be an iteratorChandler Carruth1-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
2017-03-23[LVIPrinterPass] Print LVI info for function argumentsAnna Thomas1-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
2017-03-22[LVI] Add an LVI printer pass to capture test LVI cache after transformationsAnna Thomas1-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
2017-03-12[LVI] Add Datalayout to the class LazyValueInfo since all its Impls require ↵Anna Thomas1-1/+1
it. NFC llvm-svn: 297583
2017-02-24Fix Indentation. NFCIXin Tong1-2/+2
llvm-svn: 296169
2017-02-09LVI: Fix use-of-uninitialized-value after r294463Vitaly Buka1-1/+1
BlockValueStack can be reallocated making reference e invalid. llvm-svn: 294572
2017-02-08LVI: Add a per-value worklist limit to LazyValueInfo.Daniel Berlin1-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
2017-02-07[LVI] Switch from BFS to DFS exploration orderPhilip Reames1-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
2017-01-26[PM] Use PoisoningVH correctly when merely deleting entries in a mapChandler Carruth1-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
2017-01-24[PH] Replace uses of AssertingVH from members of analysis results withChandler Carruth1-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
2017-01-23[PM] Teach LVI to correctly invalidate itself when its dependenciesChandler Carruth1-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
2017-01-11Make processing @llvm.assume more efficient - Add affected values to the ↵Hal Finkel1-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
2016-12-30[LVI] Remove count/erase idiom in favor of checking result value of erasePhilip Reames1-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
2016-12-30[LVI] Manually hoist computation from loopPhilip Reames1-7/+12
Minor compile time win. Not known to be a hot spot, just something I noticed while reading. llvm-svn: 290759
2016-12-19Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper1-21/+27
This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
2016-12-15Remove the AssumptionCacheHal Finkel1-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
2016-12-15Make processing @llvm.assume more efficient by using operand bundlesHal Finkel1-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
2016-12-07Reintroduce a check accidentally removed in 288873 to fix clang botsPhilip Reames1-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
2016-12-07Fix a warning introduced in r288874Philip Reames1-1/+0
llvm-svn: 288884
2016-12-07[LVI] Remove used return value from markX functionsPhilip Reames1-28/+26
llvm-svn: 288874
2016-12-07[LVI] Simplify mergeIn codePhilip Reames1-24/+20
Remove the unused return type, use early return, use assignment operator. llvm-svn: 288873
2016-12-07[LVI] Simplify obfuscated codePhilip Reames1-14/+0
It doesn't matter why something is overdefined if it is... llvm-svn: 288871
2016-12-06[LVI] Remove dead code in mergeInPhilip Reames1-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
2016-12-06[LVI] Extract a helper functionPhilip Reames1-32/+22
Extracting a helper function out of solveBlockValue makes the contract around the cache much easier to understand. llvm-svn: 288766
2016-12-06[LVI] Hide the last markX function on LVILatticeValPhilip Reames1-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
2016-12-06[LVI] Hide a confusing internal interfacePhilip Reames1-16/+19
llvm-svn: 288764
2016-12-06[LVI] Remove duplicate code using existing helper functionPhilip Reames1-6/+2
llvm-svn: 288761
2016-12-01Factor out common parts of LVI and Float2Int into ConstantRange [NFCI]Philip Reames1-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
2016-12-01Revert previous whitespace changePhilip Reames1-1/+0
llvm-svn: 288312
2016-12-01Test commit of whitespace to check permissions.Philip Reames1-0/+1
llvm-svn: 288311
2016-11-23[PM] Change the static object whose address is used to uniquely identifyChandler Carruth1-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
2016-10-21[LVI] Fix a bug with a guard being the very first instruction in a BB not ↵Artur Pilipenko1-5/+4
taken into account While looking for guards use reverse iterator and scan up to rend() not to begin() llvm-svn: 284827
2016-10-02Remove duplicated code; NFCSanjoy Das1-2/+2
ICmpInst::makeConstantRange does exactly the same thing as ConstantRange::makeExactICmpRegion. llvm-svn: 283059
2016-09-15Add some shortcuts in LazyValueInfo to reduce compile time of Correlated ↵Wei Mi1-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
2016-09-12[LVI] Complete the abstract of the cache layer [NFCI]Philip Reames1-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
2016-09-12[LVI] Sink a couple more cache manipulation routines into the cache itself ↵Philip Reames1-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
2016-09-12[LVI] Abstract out the actual cache logic [NFCI]Philip Reames1-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
2016-08-12[LVI] Take guards into accountArtur Pilipenko1-11/+29
Teach LVI to gather control dependant constraints from guards. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D23358 llvm-svn: 278518
2016-08-12[LVI] Fix potential memory corruption in getValueFromConditionArtur Pilipenko1-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
2016-08-12[LVI] Take range metadata into account while calculating icmp condition ↵Artur Pilipenko1-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
generated by cgit v1.1 at 2025-10-11 18:22:59 +0000