summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Fixed a bug with how we determine bitset indices.George Burgess IV2015-01-211-1/+1
| | | | llvm-svn: 226671
* [PM] Port LoopInfo to the new pass manager, adding both a LoopAnalysisChandler Carruth2015-01-201-0/+21
| | | | | | | | | | | | | | pass and a LoopPrinterPass with the expected associated wiring. I've added a RUN line to the only test case (!!!) we have that actually prints loops. Everything seems to be working. This is somewhat exciting as this is the first analysis using another analysis to go in for the new pass manager. =D I also believe it is the last analysis necessary for porting instcombine, but of course I may yet discover more. llvm-svn: 226560
* [PM] Now that LoopInfo isn't in the Pass type hierarchy, it is muchChandler Carruth2015-01-181-26/+11
| | | | | | | | | | | | cleaner to derive from the generic base. Thise removes a ton of boiler plate code and somewhat strange and pointless indirections. It also remove a bunch of the previously needed friend declarations. To fully remove these, I also lifted the verify logic into the generic LoopInfoBase, which seems good anyways -- it is generic and useful logic even for the machine side. llvm-svn: 226385
* [PM] Cleanup more warnings my refactoring exposed where now we haveChandler Carruth2015-01-171-0/+2
| | | | | | | | | unused variables in a no-asserts build. I've fixed this by putting the entire loop behind an #ifndef as it contains nothing other than asserts. llvm-svn: 226377
* [PM] Split the LoopInfo object apart from the legacy pass, creatingChandler Carruth2015-01-1710-50/+56
| | | | | | | | | | a LoopInfoWrapperPass to wire the object up to the legacy pass manager. This switches all the clients of LoopInfo over and paves the way to port LoopInfo to the new pass manager. No functionality change is intended with this iteration. llvm-svn: 226373
* [PM] Port TargetLibraryInfo to the new pass manager, provided by theChandler Carruth2015-01-151-1/+22
| | | | | | | | | | | | | | | | | | | | TargetLibraryAnalysis pass. There are actually no direct tests of this already in the tree. I've added the most basic test that the pass manager bits themselves work, and the TLI object produced will be tested by an upcoming patches as they port passes which rely on TLI. This is starting to point out the awkwardness of the invalidate API -- it seems poorly fitting on the *result* object. I suspect I will change it to live on the analysis instead, but that's not for this change, and I'd rather have a few more passes ported in order to have more experience with how this plays out. I believe there is only one more analysis required in order to start porting instcombine. =] llvm-svn: 226160
* [PM] Separate the TargetLibraryInfo object from the immutable pass.Chandler Carruth2015-01-156-31/+44
| | | | | | | | | | | | | | 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
* Update libdeps since TLI was moved from Target to Analysis in r226078.NAKAMURA Takumi2015-01-151-1/+1
| | | | llvm-svn: 226126
* [PM] Move TargetLibraryInfo into the Analysis library.Chandler Carruth2015-01-159-7/+762
| | | | | | | | | | | | | | | | 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
* For PR21145: recognise a builtin call to a known deallocation function even ifRichard Smith2015-01-151-1/+1
| | | | | | | | it's defined in the current module. Clang generates this situation for the C++14 sized deallocation functions, because it generates a weak definition in case one isn't provided by the C++ runtime library. llvm-svn: 226069
* [cleanup] Re-sort all the #include lines in LLVM usingChandler Carruth2015-01-148-11/+10
| | | | | | | | | | | utils/sort_includes.py. I clearly haven't done this in a while, so more changed than usual. This even uncovered a missing include from the InstrProf library that I've added. No functionality changed here, just mechanical cleanup of the include order. llvm-svn: 225974
* Revert r225854: [PM] Move the LazyCallGraph printing functionality toChandler Carruth2015-01-141-38/+36
| | | | | | | | | | | | | | | a print method. This was formulated on a bad idea, but sadly I didn't uncover how bad this was until I got further down the path. I had hoped that we could provide a low boilerplate way of printing analyses, but it just doesn't seem like this really fits the needs of the analyses. Not all analyses really want to do printing, and those that do don't all use the same interface. Instead, with the new pass manager let's just take advantage of the fact that creating an explicit printer pass like the LCG has is pretty low boilerplate already and rely on that for testing. llvm-svn: 225861
* [PM] Move the LazyCallGraph printing functionality to a print method.Chandler Carruth2015-01-131-36/+38
| | | | | | | | I'm adding generic analysis printing utility pass support which will require such a method (or a specialization) so this will let the existing printing logic satisfy that. llvm-svn: 225854
* [PM] Remove the defunt CGSCC-specific debug flag.Chandler Carruth2015-01-131-4/+0
| | | | | | | | Even before I sunk the debug flag into the opt tool this had been made obsolete by factoring the pass and analysis managers into a single set of templates that all used the core flag. No functionality changed here. llvm-svn: 225842
* [PM] Refactor the new pass manager to use a single template to implementChandler Carruth2015-01-131-32/+0
| | | | | | | | | | | | | | | | | | | | | | | the generic functionality of the pass managers themselves. In the new infrastructure, the pass "manager" isn't actually interesting at all. It just pipelines a single chunk of IR through N passes. We don't need to know anything about the IR or the passes to do this really and we can replace the 3 implementations of the exact same functionality with a single generic PassManager template, complementing the single generic AnalysisManager template. I've left typedefs in place to give convenient names to the various obvious instantiations of the template. With this, I think I've nuked almost all of the redundant logic in the managers, and I think the overall design is actually simpler for having single templates that clearly indicate there is no special logic here. The logging is made somewhat more annoying by this change, but I don't think the difference is worth having heavy-weight traits to help log things. llvm-svn: 225783
* Standardize {pred,succ,use,user}_empty()Ramkumar Ramachandra2015-01-131-1/+1
| | | | | | | | | The functions {pred,succ,use,user}_{begin,end} exist, but many users have to check *_begin() with *_end() by hand to determine if the BasicBlock or User is empty. Fix this with a standard *_empty(), demonstrating a few usecases. llvm-svn: 225760
* [PM] Fold all three analysis managers into a single AnalysisManagerChandler Carruth2015-01-131-100/+0
| | | | | | | | | | | | | | | | | | | | | | | | | template. This consolidates three copies of nearly the same core logic. It adds "complexity" to the ModuleAnalysisManager in that it makes it possible to share a ModuleAnalysisManager across multiple modules... But it does so by deleting *all of the code*, so I'm OK with that. This will naturally make fixing bugs in this code much simpler, etc. The only down side here is that we have to use 'typename' and 'this->' in various places, and the implementation is lifted into the header. I'll take that for the code size reduction. The convenient names are still typedef-ed and used throughout so that users can largely ignore this aspect of the implementation. The follow-up change to this will do the exact same refactoring for the PassManagers. =D It turns out that the interesting different code is almost entirely in the adaptors. At the end, that should be essentially all that is left. llvm-svn: 225757
* [PM] Re-clang-format much of this code as the code has changed some andChandler Carruth2015-01-131-2/+2
| | | | | | | | so has clang-format. Notably, this fixes a bunch of formatting in the CGSCC pass manager side of things that has been improved in clang-format recently. llvm-svn: 225743
* Fix PR22179.Sanjoy Das2015-01-101-42/+33
| | | | | | | | | | | We were incorrectly inferring nsw for certain SCEVs. We can be more aggressive here (see Richard Smith's comment on http://llvm.org/bugs/show_bug.cgi?id=22179) but this change just focuses on correctness. Differential Revision: http://reviews.llvm.org/D6914 llvm-svn: 225591
* 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
* [REFACTOR] Push logic from MemDepPrinter into getNonLocalPointerDependencyPhilip Reames2015-01-092-35/+24
| | | | | | | | Previously, MemDepPrinter handled volatile and unordered accesses without involving MemoryDependencyAnalysis. By making a slight tweak to the documented interface - which is respected by both callers - we can move this responsibility to MDA for the benefit of any future callers. This is basically just cleanup. In the future, we may decide to extend MDA's non local dependency analysis to return useful results for ordered or volatile loads. I believe (but have not really checked in detail) that local dependency analyis does get useful results for ordered, but not volatile, loads. llvm-svn: 225483
* [Refactor] Have getNonLocalPointerDependency take the query instructionPhilip Reames2015-01-092-9/+49
| | | | | | | | | | Previously, MemoryDependenceAnalysis::getNonLocalPointerDependency was taking a list of properties about the instruction being queried. Since I'm about to need one more property to be passed down through the infrastructure - I need to know a query instruction is non-volatile in an inner helper - fix the interface once and for all. I also added some assertions and behaviour clarifications around volatile and ordered field accesses. At the moment, this is mostly to document expected behaviour. The only non-standard instructions which can currently reach this are atomic, but unordered, loads and stores. Neither ordered or volatile accesses can reach here. The call in GVN is protected by an isSimple check when it first considers the load. The calls in MemDepPrinter are protected by isUnordered checks. Both utilities also check isVolatile for loads and stores. llvm-svn: 225481
* Remove empty statement. No functionality change.Nick Lewycky2015-01-081-1/+0
| | | | llvm-svn: 225420
* [PM] Fix a pretty nasty bug where the new pass manager would invalidateChandler Carruth2015-01-071-6/+28
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | passes too many time. I think this is actually the issue that someone raised with me at the developer's meeting and in an email, but that we never really got to the bottom of. Having all the testing utilities made it much easier to dig down and uncover the core issue. When a pass manager is running many passes over a single function, we need it to invalidate the analyses between each run so that they can be re-computed as needed. We also need to track the intersection of preserved higher-level analyses across all the passes that we run (for example, if there is one module analysis which all the function analyses preserve, we want to track that and propagate it). Unfortunately, this interacted poorly with any enclosing pass adaptor between two IR units. It would see the intersection of preserved analyses, and need to invalidate any other analyses, but some of the un-preserved analyses might have already been invalidated *and recomputed*! We would fail to propagate the fact that the analysis had already been invalidated. The solution to this struck me as really strange at first, but the more I thought about it, the more natural it seemed. After a nice discussion with Duncan about it on IRC, it seemed even nicer. The idea is that invalidating an analysis *causes* it to be preserved! Preserving the lack of result is trivial. If it is recomputed, great. Until something *else* invalidates it again, we're good. The consequence of this is that the invalidate methods on the analysis manager which operate over many passes now consume their PreservedAnalyses object, update it to "preserve" every analysis pass to which it delivers an invalidation (regardless of whether the pass chooses to be removed, or handles the invalidation itself by updating itself). Then we return this augmented set from the invalidate routine, letting the pass manager take the result and use the intersection of *that* across each pass run to compute the final preserved set. This accounts for all the places where the early invalidation of an analysis has already "preserved" it for a future run. I've beefed up the testing and adjusted the assertions to show that we no longer repeatedly invalidate or compute the analyses across nested pass managers. llvm-svn: 225333
* Analysis: Reformulate WillNotOverflowUnsignedAdd for reusabilityDavid Majnemer2015-01-071-0/+29
| | | | | | | | WillNotOverflowUnsignedAdd's smarts will live in ValueTracking as computeOverflowForUnsignedAdd. It now returns a tri-state result: never overflows, always overflows and sometimes overflows. llvm-svn: 225329
* [PM] Add a utility pass template that synthesizes the invalidation ofChandler Carruth2015-01-061-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | a specific analysis result. This is quite handy to test things, and will also likely be very useful for debugging issues. You could narrow down pass validation failures by walking these invalidate pass runs up and down the pass pipeline, etc. I've added support to the pass pipeline parsing to be able to create one of these for any analysis pass desired. Just adding this class uncovered one latent bug where the AnalysisManager CRTP base class had a hard-coded Module type rather than using IRUnitT. I've also added tests for invalidation and caching of analyses in a basic way across all the pass managers. These in turn uncovered two more bugs where we failed to correctly invalidate an analysis -- its results were invalidated but the key for re-running the pass was never cleared and so it was never re-run. Quite nasty. I'm very glad to debug this here rather than with a full system. Also, yes, the naming here is horrid. I'm going to update some of the names to be slightly less awful shortly. But really, I've no "good" ideas for naming. I'll be satisfied if I can get it to "not bad". llvm-svn: 225246
* [PM] Add a collection of no-op analysis passes and switch the new passChandler Carruth2015-01-061-1/+4
| | | | | | | | | | | | manager tests to use them and be significantly more comprehensive. This, naturally, uncovered a bug where the CGSCC pass manager wasn't printing analyses when they were run. The only remaining core manipulator is I think an invalidate pass similar to the require pass. That'll be next. =] llvm-svn: 225240
* [PM] Don't run the machinery of invalidating all the analysis passesChandler Carruth2015-01-051-0/+4
| | | | | | | | | | | | | | | | | | | when all are being preserved. We want to short-circuit this for a couple of reasons. One, I don't really want passes to grow a dependency on actually receiving their invalidate call when they've been preserved. I'm thinking about removing this entirely. But more importantly, preserving everything is likely to be the common case in a lot of scenarios, and it would be really good to bypass all of the invalidation and preservation machinery there. Avoiding calling N opaque functions to try to invalidate things that are by definition still valid seems important. =] This wasn't really inpsired by much other than seeing the spam in the logging for analyses, but it seems better ot get it checked in rather than forgetting about it. llvm-svn: 225163
* [PM] Add names and debug logging for analysis passes to the new passChandler Carruth2015-01-051-0/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | manager. This starts to allow us to test analyses more easily, but it's really only the beginning. Some of the code here is still untestable without manual changes to create analysis passes, but I wanted to factor it into a small of chunks as possible. Next up in order to be able to test things are, in no particular order: - No-op analyses passes so we don't have to use real ones to exercise the pass maneger itself. - Automatic way of generating dummy passes that require an analysis be run, including a variant that calls a 'print' method on a pass to make it even easier to print out the results of an analysis. - Dummy passes that invalidate all analyses for their IR unit so we can test invalidation and re-runs. - Automatic way to print each analysis pass as it is re-run. - Automatic but optional verification of analysis passes everywhere possible. I'm not claiming I'll get to all of these immediately, but that's what is in the pipeline at some stage. I'm fleshing out exactly what I need and what to prioritize by working on converting analyses and then trying to test the conversion. =] llvm-svn: 225162
* [PM] Switch the new pass manager to use a reference-based API for IRChandler Carruth2015-01-052-20/+19
| | | | | | | | | | | | | | | | | | | | | units. This was debated back and forth a bunch, but using references is now clearly cleaner. Of all the code written using pointers thus far, in only one place did it really make more sense to have a pointer. In most cases, this just removes immediate dereferencing from the code. I think it is much better to get errors on null IR units earlier, potentially at compile time, than to delay it. Most notably, the legacy pass manager uses references for its routines and so as more and more code works with both, the use of pointers was likely to become really annoying. I noticed this when I ported the domtree analysis over and wrote the entire thing with references only to have it fail to compile. =/ It seemed better to switch now than to delay. We can, of course, revisit this is we learn that references are really problematic in the API. llvm-svn: 225145
* [PM] Cleanup a const_cast and other machinery left over in this codeChandler Carruth2015-01-041-2/+1
| | | | | | | | | from before I removed thet non-const use of the function. The unused variable that held the const_cast was already kindly removed by Michael. llvm-svn: 225143
* Fix unused variable warning for non-asserts builds. NFC.Michael Kuperstein2015-01-041-2/+2
| | | | llvm-svn: 225133
* [PM] Split the AssumptionTracker immutable pass into two separate APIs:Chandler Carruth2015-01-0414-426/+460
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* ValueTracking: ComputeNumSignBits should tolerate misshapen phi nodesDavid Majnemer2015-01-041-2/+5
| | | | | | | | | | | | PHI nodes can have zero operands in the middle of a transform. It is expected that utilities in Analysis don't freak out when this happens. Note that it is considered invalid to allow these misshapen phi nodes to make it to another pass. This fixes PR22086. llvm-svn: 225126
* ValueTracking: Make computeKnownBits for Arguments a little more clearDavid Majnemer2015-01-031-0/+3
| | | | | | | | | | | We would sometimes leave the out-param APInts untouched while going through computeKnownBits. While I don't know of a way to trigger a bug involving this in practice, it goes against the overall design of computeKnownBits. Found via code inspection. llvm-svn: 225109
* InstCombine: Detect when llvm.umul.with.overflow always overflowsDavid Majnemer2015-01-021-7/+16
| | | | | | | We know overflow always occurs if both ~LHSKnownZero * ~RHSKnownZero and LHSKnownOne * RHSKnownOne overflow. llvm-svn: 225077
* Analysis: Reformulate WillNotOverflowUnsignedMul for reusabilityDavid Majnemer2015-01-021-0/+39
| | | | | | | | WillNotOverflowUnsignedMul's smarts will live in ValueTracking as computeOverflowForUnsignedMul. It now returns a tri-state result: never overflows, always overflows and sometimes overflows. llvm-svn: 225076
* ValueTracking: Small cleanup in ComputeNumSignBitsDavid Majnemer2014-12-261-2/+2
| | | | | | | Constant contains the isAllOnesValue and isNullValue predicates, not ConstantInt. llvm-svn: 224848
* [ValueTracking] Move GlobalAlias handling to be after the max depth check in ↵Michael Kuperstein2014-12-231-15/+14
| | | | | | | | | | | | computeKnownBits() GlobalAlias handling used to be after GlobalValue handling, which meant it was, in practice, dead code. r220165 moved GlobalAlias handling to be before GlobalValue handling, but also moved it to be before the max depth check, causing an assert due to a recursion depth limit violation. This moves GlobalAlias handling forward to where it's safe, and changes the GlobalValue handling to only look at GlobalObjects. Differential Revision: http://reviews.llvm.org/D6758 llvm-svn: 224765
* InstSimplify: Don't bother if getScalarSizeInBits returns zeroDavid Majnemer2014-12-201-4/+5
| | | | | | | getScalarSizeInBits returns zero when the comparison operands are not integral. No functionality change intended. llvm-svn: 224675
* Simplify the codeDavid Majnemer2014-12-201-41/+25
| | | | | | No functionality change intended. llvm-svn: 224673
* InstSimplify: Optimize away pointless comparisonsDavid Majnemer2014-12-201-2/+38
| | | | | | | | | (X & INT_MIN) ? X & INT_MAX : X into X & INT_MAX (X & INT_MIN) ? X : X & INT_MAX into X (X & INT_MIN) ? X | INT_MIN : X into X (X & INT_MIN) ? X : X | INT_MIN into X | INT_MIN llvm-svn: 224669
* Remove redundant assignment.Tilmann Scheller2014-12-191-1/+0
| | | | | | Found with the Clang static analyzer. llvm-svn: 224570
* InstSimplify: shl nsw/nuw undef, %V -> undefDavid Majnemer2014-12-171-13/+7
| | | | | | | | | | We can always choose an value for undef which might cause %V to shift out an important bit except for one case, when %V is zero. However, shl behaves like an identity function when the right hand side is zero. llvm-svn: 224405
* Teach ScalarEvolution to exploit min and max expressions when provingSanjoy Das2014-12-151-8/+93
| | | | | | | | | | | | | | | | isKnownPredicate. The motivation for this change is to optimize away checks in loops like this: limit = min(t, len) for (i = 0 to limit) if (i >= len || i < 0) throw_array_of_of_bounds(); a[i] = ... Differential Revision: http://reviews.llvm.org/D6635 llvm-svn: 224285
* Clarify HowFarToZero computation when the step is a positive power of two. ↵Mark Heffernan2014-12-151-8/+13
| | | | | | Functionally this should be identical to the existing code except for the case where Step is maximally negative (eg, INT_MIN). We now punt in that one corner case to make reasoning about the code easier. llvm-svn: 224274
* Sink store based on alias analysisElena Demikhovsky2014-12-151-10/+11
| | | | | | | | | | | | - by Ella Bolshinsky The alias analysis is used define whether the given instruction is a barrier for store sinking. For 2 identical stores, following instructions are checked in the both basic blocks, to determine whether they are sinking barriers. http://reviews.llvm.org/D6420 llvm-svn: 224247
OpenPOWER on IntegriCloud