summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LazyValueInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* Move isKnownNonNull out of AliasAnalysis.h and into ValueTracking.cpp sinceDan Gohman2013-01-311-1/+0
| | | | | | | it isn't really an AliasAnalysis concept, and ValueTracking has similar things that it could plausibly share code with some day. llvm-svn: 174027
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-4/+4
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-7/+7
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Hoist out some work done inside a loop doing a linear scan over allNick Lewycky2012-10-261-12/+17
| | | | | | | | | | | | instructions in a block. GetUnderlyingObject is more expensive than it looks as it can, for instance, call SimplifyInstruction. This might have some behavioural changes in odd corner cases, but only because of some strange artefacts of the original implementation. If you were relying on those, we can fix that by replacing this with a smarter algorithm. Change passes the existing tests. llvm-svn: 166754
* Move TargetData to DataLayout.Micah Villmow2012-10-081-4/+4
| | | | llvm-svn: 165402
* Revert 'Fix a typo 'iff' => 'if''. iff is an abreviation of if and only if. ↵Sylvestre Ledru2012-09-271-2/+2
| | | | | | See: http://en.wikipedia.org/wiki/If_and_only_if Commit 164767 llvm-svn: 164768
* Fix a typo 'iff' => 'if'Sylvestre Ledru2012-09-271-2/+2
| | | | llvm-svn: 164767
* JumpThreading: when default destination is the destination of some cases in aManman Ren2012-09-051-3/+6
| | | | | | | | | switch, make sure we include the value for the cases when calculating edge value from switch to the default destination. rdar://12241132 llvm-svn: 163270
* Reduce duplicated hash map lookups.Benjamin Kramer2012-08-221-2/+4
| | | | llvm-svn: 162362
* make LazyValueInfo analyze the default case of switch statements (we know ↵Nuno Lopes2012-06-281-16/+15
| | | | | | that in the default branch the value cannot be any of the switch cases) llvm-svn: 159353
* make LVI::getEdgeValue() always intersect the constraints of the edge with ↵Nuno Lopes2012-06-281-36/+53
| | | | | | the range of the block. Previously it was only performing the intersection for a few cases, thus losing precision llvm-svn: 159320
* allow LazyValueInfo::getEdgeValue() to reason about multiple edges from the ↵Nuno Lopes2012-05-181-11/+6
| | | | | | same switch instruction by doing union of ranges (which may still be conservative, but it's more aggressive than before) llvm-svn: 157071
* minor simplification in the call to ConstantRange constructorNuno Lopes2012-05-171-1/+1
| | | | llvm-svn: 157024
* llvm::SwitchInstStepan Dyatkovskiy2012-03-111-1/+1
| | | | | | | Renamed methods caseBegin, caseEnd and caseDefault with case_begin, case_end, and case_default. Added some notes relative to case iterators. llvm-svn: 152532
* Taken into account Duncan's comments for r149481 dated by 2nd Feb 2012:Stepan Dyatkovskiy2012-03-081-3/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120130/136146.html Implemented CaseIterator and it solves almost all described issues: we don't need to mix operand/case/successor indexing anymore. Base iterator class is implemented as a template since it may be initialized either from "const SwitchInst*" or from "SwitchInst*". ConstCaseIt is just a read-only iterator. CaseIt is read-write iterator; it allows to change case successor and case value. Usage of iterator allows totally remove resolveXXXX methods. All indexing convertions done automatically inside the iterator's getters. Main way of iterator usage looks like this: SwitchInst *SI = ... // intialize it somehow for (SwitchInst::CaseIt i = SI->caseBegin(), e = SI->caseEnd(); i != e; ++i) { BasicBlock *BB = i.getCaseSuccessor(); ConstantInt *V = i.getCaseValue(); // Do something. } If you want to convert case number to TerminatorInst successor index, just use getSuccessorIndex iterator's method. If you want initialize iterator from TerminatorInst successor index, use CaseIt::fromSuccessorIndex(...) method. There are also related changes in llvm-clients: klee and clang. llvm-svn: 152297
* LVI: Recognize the form instcombine canonicalizes range checks into when ↵Benjamin Kramer2012-03-021-4/+16
| | | | | | | | | | forming constant ranges. This could probably be made a lot smarter, but this is a common case and doesn't require LVI to scan a lot of code. With this change CVP can optimize away the "shift == 0" case in Hashing.h that only gets hit when "shift" is in a range not containing 0. llvm-svn: 151919
* SwitchInst refactoring.Stepan Dyatkovskiy2012-02-011-2/+2
| | | | | | | | | | | | | | | | | The purpose of refactoring is to hide operand roles from SwitchInst user (programmer). If you want to play with operands directly, probably you will need lower level methods than SwitchInst ones (TerminatorInst or may be User). After this patch we can reorganize SwitchInst operands and successors as we want. What was done: 1. Changed semantics of index inside the getCaseValue method: getCaseValue(0) means "get first case", not a condition. Use getCondition() if you want to resolve the condition. I propose don't mix SwitchInst case indexing with low level indexing (TI successors indexing, User's operands indexing), since it may be dangerous. 2. By the same reason findCaseValue(ConstantInt*) returns actual number of case value. 0 means first case, not default. If there is no case with given value, ErrorIndex will returned. 3. Added getCaseSuccessor method. I propose to avoid usage of TerminatorInst::getSuccessor if you want to resolve case successor BB. Use getCaseSuccessor instead, since internal SwitchInst organization of operands/successors is hidden and may be changed in any moment. 4. Added resolveSuccessorIndex and resolveCaseIndex. The main purpose of these methods is to see how case successors are really mapped in TerminatorInst. 4.1 "resolveSuccessorIndex" was created if you need to level down from SwitchInst to TerminatorInst. It returns TerminatorInst's successor index for given case successor. 4.2 "resolveCaseIndex" converts low level successors index to case index that curresponds to the given successor. Note: There are also related compatability fix patches for dragonegg, klee, llvm-gcc-4.0, llvm-gcc-4.2, safecode, clang. llvm-svn: 149481
* Remove dead code.Bill Wendling2012-01-181-45/+0
| | | | llvm-svn: 148384
* A DenseMap of a std::map isn't a very good idea because the "grow()" method willBill Wendling2012-01-121-2/+2
| | | | | | | need to make a deep copy of each of the std::maps. Use a std::map of the std::map instead. This improves the compile time of sqlite3 by ~2%. llvm-svn: 148003
* Revert r147978. A DenseMap's iterators may become invalidated here.Bill Wendling2012-01-111-1/+2
| | | | llvm-svn: 147980
* Use a DenseMap.Bill Wendling2012-01-111-2/+1
| | | | | | This appears to improve sqlite3's compile time by ~2%. llvm-svn: 147978
* Clear the new cache.Benjamin Kramer2011-12-031-0/+1
| | | | llvm-svn: 145771
* Add a "seen blocks" cache to LVI to avoid a linear scan over the whole cache ↵Benjamin Kramer2011-12-031-1/+13
| | | | | | | | | just to remove no blocks from the maps. -15% on ARMDisassembler.cpp (Release build). It's not that great to add another layer of caching to the caching-heavy LVI but I don't see a better way. llvm-svn: 145770
* Fix a few more places where TargetData/TargetLibraryInfo is not being passed.Chad Rosier2011-12-021-9/+23
| | | | | | Add FIXMEs to places that are non-trivial to fix. llvm-svn: 145661
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-181-3/+3
| | | | llvm-svn: 135375
OpenPOWER on IntegriCloud