summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LazyValueInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [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
* fix typo; NFCSanjay Patel2015-01-091-1/+1
| | | | llvm-svn: 225524
* more efficient use of a dyn_cast; no functional change intendedSanjay Patel2015-01-091-3/+3
| | | | llvm-svn: 225523
* [PM] Split the AssumptionTracker immutable pass into two separate APIs:Chandler Carruth2015-01-041-23/+26
| | | | | | | | | | | | | | | | | | | | | | | | | | | | a cache of assumptions for a single function, and an immutable pass that manages those caches. The motivation for this change is two fold. Immutable analyses are really hacks around the current pass manager design and don't exist in the new design. This is usually OK, but it requires that the core logic of an immutable pass be reasonably partitioned off from the pass logic. This change does precisely that. As a consequence it also paves the way for the *many* utility functions that deal in the assumptions to live in both pass manager worlds by creating an separate non-pass object with its own independent API that they all rely on. Now, the only bits of the system that deal with the actual pass mechanics are those that actually need to deal with the pass mechanics. Once this separation is made, several simplifications become pretty obvious in the assumption cache itself. Rather than using a set and callback value handles, it can just be a vector of weak value handles. The callers can easily skip the handles that are null, and eventually we can wrap all of this up behind a filter iterator. For now, this adds boiler plate to the various passes, but this kind of boiler plate will end up making it possible to port these passes to the new pass manager, and so it will end up factored away pretty reasonably. llvm-svn: 225131
* LazyValueInfo: Actually re-visit partially solved block-values in ↵Hans Wennborg2014-11-251-58/+78
| | | | | | | | | | | | | | | | | | | | | | | | | | solveBlockValue() If solveBlockValue() needs results from predecessors that are not already computed, it returns false with the intention of resuming when the dependencies have been resolved. However, the computation would never be resumed since an 'overdefined' result had been placed in the cache, preventing any further computation. The point of placing the 'overdefined' result in the cache seems to have been to break cycles, but we can check for that when inserting work items in the BlockValue stack instead. This makes the "stop and resume" mechanism of solveBlockValue() work as intended, unlocking more analysis. Using this patch shaves 120 KB off a 64-bit Chromium build on Linux. I benchmarked compiling bzip2.c at -O2 but couldn't measure any difference in compile time. Tests by Jiangning Liu from r215343 / PR21238, Pete Cooper, and me. Differential Revision: http://reviews.llvm.org/D6397 llvm-svn: 222768
* LazyValueInfo: range'ify some for-loops. No functional change.Hans Wennborg2014-11-211-34/+19
| | | | llvm-svn: 222557
* LazyValueInfo: fix some typos and indentation, etc. NFC.Hans Wennborg2014-11-211-10/+12
| | | | llvm-svn: 222554
* [LVI] Add some additional comments about caching and context instructionsHal Finkel2014-10-161-0/+13
| | | | | | | | Philip Reames and I had a long conversation about this, mostly because it is not obvious why the current logic is correct. Hopefully, these comments will prevent such confusion in the future. llvm-svn: 219882
* [LVI] Check for @llvm.assume dominating the edge branchHal Finkel2014-10-141-0/+2
| | | | | | | | | | | | | When LazyValueInfo uses @llvm.assume intrinsics to provide edge-value constraints, we should check for intrinsics that dominate the edge's branch, not just any potential context instructions. An assumption that dominates the edge's branch represents a truth on that edge. This is specifically useful, for example, if multiple predecessors assume a pointer to be nonnull, allowing us to simplify a later null comparison. The test case, and an initial patch, were provided by Philip Reames. Thanks! llvm-svn: 219688
* [LVI] Revert the remainder of "r218231 - Add two thresholds ↵Hal Finkel2014-10-101-22/+0
| | | | | | | | | lvi-overdefined-BB-threshold and lvi-overdefined-threshold" Some of r218231 was reverted with the code that used it in r218971, but not all of it. This removes the rest (which is now dead). llvm-svn: 219469
* Revert r215343.James Molloy2014-10-031-25/+1
| | | | | | This was contentious and needs invesigation. llvm-svn: 218971
* Add two thresholds lvi-overdefined-BB-threshold and lvi-overdefined-thresholdJiangning Liu2014-09-221-2/+32
| | | | | | | | | | for LVI algorithm. For a specific value to be lowered, when the number of basic blocks being checked for overdefined lattice value is larger than lvi-overdefined-BB-threshold, or the times of encountering overdefined value for a single basic block is larger than lvi-overdefined-threshold, the LVI algorithm will stop further lowering the lattice value. llvm-svn: 218231
* Make use of @llvm.assume from LazyValueInfoHal Finkel2014-09-071-77/+189
| | | | | | | | | | | | | | | | | | | | | | | This change teaches LazyValueInfo to use the @llvm.assume intrinsic. Like with the known-bits change (r217342), this requires feeding a "context" instruction pointer through many functions. Aside from a little refactoring to reuse the logic that turns predicates into constant ranges in LVI, the only new code is that which can 'merge' the range from an assumption into that otherwise computed. There is also a small addition to JumpThreading so that it can have LVI use assumptions in the same block as the comparison feeding a conditional branch. With this patch, we can now simplify this as expected: int foo(int a) { __builtin_assume(a > 5); if (a > 3) { bar(); return 1; } return 0; } llvm-svn: 217345
* In LVI(Lazy Value Info), originally value on a BB can only be caculated once,Jiangning Liu2014-08-111-2/+17
| | | | | | | | | and the lattice will be updated to be a state other than "undefined". This limiation could miss some opportunities of lowering "overdefined" to be an even accurate value. So this patch ask the algorithm to try to lower the lattice value again even if the value has been lowered to be "overdefined". llvm-svn: 215343
* Revert "[C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) ↵Duncan P. N. Exon Smith2014-07-211-2/+2
| | | | | | | | | iterator ranges." This reverts commit r213474 (and r213475), which causes a miscompile on a stage2 LTO build. I'll reply on the list in a moment. llvm-svn: 213562
* [C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) iterator ↵Manuel Jacob2014-07-201-2/+2
| | | | | | | | | | | | | | | | | | ranges. Summary: This patch introduces two new iterator ranges and updates existing code to use it. No functional change intended. Test Plan: All tests (make check-all) still pass. Reviewers: dblaikie Reviewed By: dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4481 llvm-svn: 213474
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | definition below all the header #include lines, lib/Analysis/... edition. This one has a bit extra as there were *other* #define's before #include lines in addition to DEBUG_TYPE. I've sunk all of them as a block. llvm-svn: 206843
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-151-9/+9
| | | | | | instead of comparing to nullptr. llvm-svn: 206243
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-3/+3
| | | | | | class. llvm-svn: 202945
* [Modules] Move the ConstantRange class into the IR library. This isChandler Carruth2014-03-041-1/+1
| | | | | | | | | | a bit surprising, as the class is almost entirely abstracted away from any particular IR, however it encodes the comparsion predicates which mutate ranges as ICmp predicate codes. This is reasonable as they're used for both instructions and constants. Thus, it belongs in the IR library with instructions and constants. llvm-svn: 202838
* [Modules] Move CFG.h to the IR library as it defines graph traits overChandler Carruth2014-03-041-1/+1
| | | | | | IR types. llvm-svn: 202827
* [Modules] Move ValueHandle into the IR library where Value itself lives.Chandler Carruth2014-03-041-1/+1
| | | | | | | | | | | Move the test for this class into the IR unittests as well. This uncovers that ValueMap too is in the IR library. Ironically, the unittest for ValueMap is useless in the Support library (honestly, so was the ValueHandle test) and so it already lives in the IR unittests. Mmmm, tasty layering. llvm-svn: 202821
* [Modules] Move the LLVM IR pattern match header into the IR library, itChandler Carruth2014-03-041-1/+1
| | | | | | obviously is coupled to the IR. llvm-svn: 202818
* Make DataLayout a plain object, not a pass.Rafael Espindola2014-02-251-1/+2
| | | | | | | Instead, have a DataLayoutPass that holds one. This will allow parts of LLVM don't don't handle passes to also use DataLayout. llvm-svn: 202168
* Rename some member variables from TD to DL.Rafael Espindola2014-02-181-4/+4
| | | | | | TargetData was renamed DataLayout back in r165242. llvm-svn: 201581
* Use SmallVectorImpl::iterator/const_iterator instead of SmallVector to avoid ↵Craig Topper2013-07-041-4/+4
| | | | | | specifying the vector size. llvm-svn: 185606
OpenPOWER on IntegriCloud