summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [SCEV] Minor cleanup: rename method, C++11'ify; NFCSanjoy Das2016-03-011-4/+3
| | | | llvm-svn: 262374
* [LAA] Add missing debug outputAdam Nemet2016-03-011-1/+3
| | | | llvm-svn: 262279
* [InstSimplify] Restore fsub 0.0, (fsub 0.0, X) ==> X optznBenjamin Kramer2016-02-291-1/+1
| | | | | | | I accidentally removed this in r262212 but there was no test coverage to detect it. llvm-svn: 262215
* [InstSimplify] fsub 0.0, (fsub -0.0, X) ==> X is only safe if signed zeros ↵Benjamin Kramer2016-02-291-7/+8
| | | | | | | | are ignored. Only allow fsub -0.0, (fsub -0.0, X) ==> X without nsz. PR26746. llvm-svn: 262212
* [PM] Appease mingw32's auto-import DLL build with minimal tweaks, with fix ↵NAKAMURA Takumi2016-02-2812-0/+25
| | | | | | | | for clang. char AnalysisBase::ID should be declared as extern and defined in one module. llvm-svn: 262188
* Revert r262185, "[PM] Appease mingw32's auto-import DLL build with minimal ↵NAKAMURA Takumi2016-02-2812-25/+0
| | | | | | | | tweaks." I'll rework soon. llvm-svn: 262186
* [PM] Appease mingw32's auto-import DLL build with minimal tweaks.NAKAMURA Takumi2016-02-2812-0/+25
| | | | | | char AnalysisBase::ID should be declared as extern and defined in one module. llvm-svn: 262185
* [PM] Provide explicit instantiation declarations and definitions for theChandler Carruth2016-02-272-0/+4
| | | | | | PassManager and AnalysisManager template specializations as well. llvm-svn: 262128
* [PM] Provide two templates for the two directionalities of analysisChandler Carruth2016-02-272-82/+12
| | | | | | | | | | | | | | | | | | | | | | | | manager proxies and use those rather than repeating their definition four times. There are real differences between the two directions: outer AMs are const and don't need to have invalidation tracked. But every proxy in a particular direction is identical except for the analysis manager type and the IR unit they proxy into. This makes them prime candidates for nice templates. I've started introducing explicit template instantiation declarations and definitions as well because we really shouldn't be emitting all this everywhere. I'm going to go back and add the same for the other templates like this in a follow-up patch. I've left the analysis manager as an opaque type rather than using two IR units and requiring it to be an AnalysisManager template specialization. I think its important that users retain the ability to provide their own custom analysis management layer and provided it has the appropriate API everything should Just Work. llvm-svn: 262127
* Suppress an uncovered switch warning [NFC]Philip Reames2016-02-271-0/+1
| | | | llvm-svn: 262109
* [LVI] Extend select handling to catch min/max/clamp idiomsPhilip Reames2016-02-261-3/+71
| | | | | | | | | | Most of this is fairly straight forward. Add handling for min/max via existing matcher utility and ConstantRange routines. Add handling for clamp by exploiting condition constraints on inputs. Note that I'm only handling two constant ranges at this point. It would be reasonable to consider treating overdefined as a full range if the instruction is typed as an integer, but that should be a separate change. Differential Revision: http://reviews.llvm.org/D17184 llvm-svn: 262085
* [PM] Introduce CRTP mixin base classes to help define passes andChandler Carruth2016-02-2620-49/+0
| | | | | | | | | | | | | | | | | analyses in the new pass manager. These just handle really basic stuff: turning a type name into a string statically that is nice to print in logs, and getting a static unique ID for each analysis. Sadly, the format of passes in anonymous namespaces makes using their names in tests really annoying so I've customized the names of the no-op passes to keep tests sane to read. This is the first of a few simplifying refactorings for the new pass manager that should reduce boilerplate and confusion. llvm-svn: 262004
* [LoopUnrollAnalyzer] Check that we're using SCEV for the same loop we're ↵Michael Zolotukhin2016-02-261-1/+1
| | | | | | | | | | | | | | simulating. Summary: Check that we're using SCEV for the same loop we're simulating. Otherwise, we might try to use the iteration number of the current loop in SCEV expressions for inner/outer loops IVs, which is clearly incorrect. Reviewers: chandlerc, hfinkel Subscribers: sanjoy, llvm-commits, mzolotukhin Differential Revision: http://reviews.llvm.org/D17632 llvm-svn: 261958
* Introduce RegionInfoAnalysis, which compute Region Tree in the new ↵Hongbin Zheng2016-02-251-0/+34
| | | | | | | | PassManager. NFC Differential Revision: http://reviews.llvm.org/D17571 llvm-svn: 261904
* Introduce DominanceFrontierAnalysis to the new PassManager to compute ↵Hongbin Zheng2016-02-253-19/+39
| | | | | | | | DominanceFrontier. NFC Differential Revision: http://reviews.llvm.org/D17570 llvm-svn: 261903
* Introduce analysis pass to compute PostDominators in the new pass manager. NFCHongbin Zheng2016-02-255-27/+70
| | | | | | Differential Revision: http://reviews.llvm.org/D17537 llvm-svn: 261902
* Revert "Introduce analysis pass to compute PostDominators in the new pass ↵Hongbin Zheng2016-02-255-70/+27
| | | | | | | | manager. NFC" This reverts commit a3e5cc6a51ab5ad88d1760c63284294a4e34c018. llvm-svn: 261891
* Revert "Introduce DominanceFrontierAnalysis to the new PassManager to ↵Hongbin Zheng2016-02-253-39/+19
| | | | | | | | compute DominanceFrontier. NFC" This reverts commit 109c38b2226a87b0be73fa7a0a8c1a81df20aeb2. llvm-svn: 261890
* Revert "Introduce RegionInfoAnalysis, which compute Region Tree in the new ↵Hongbin Zheng2016-02-251-34/+0
| | | | | | | | PassManager. NFC" This reverts commit 8228b4d374edeb4cc0c5fddf6e1ab876918ee126. llvm-svn: 261889
* Introduce RegionInfoAnalysis, which compute Region Tree in the new ↵Hongbin Zheng2016-02-251-0/+34
| | | | | | | | PassManager. NFC Differential Revision: http://reviews.llvm.org/D17571 llvm-svn: 261884
* Introduce DominanceFrontierAnalysis to the new PassManager to compute ↵Hongbin Zheng2016-02-253-19/+39
| | | | | | | | DominanceFrontier. NFC Differential Revision: http://reviews.llvm.org/D17570 llvm-svn: 261883
* Introduce analysis pass to compute PostDominators in the new pass manager. NFCHongbin Zheng2016-02-255-27/+70
| | | | | | Differential Revision: http://reviews.llvm.org/D17537 llvm-svn: 261882
* PM: Implement a basic loop pass managerJustin Bogner2016-02-252-0/+46
| | | | | | | | | | | This creates the new-style LoopPassManager and wires it up with dummy and print passes. This version doesn't support modifying the loop nest at all. It will be far easier to discuss and evaluate the approaches to that with this in place so that the boilerplate is out of the way. llvm-svn: 261831
* NFC. Move isDereferenceable to Loads.h/cppArtur Pilipenko2016-02-243-203/+206
| | | | | | | | | | This is a part of the refactoring to unify isSafeToLoadUnconditionally and isDereferenceablePointer functions. In subsequent change I'm going to eliminate isDerferenceableAndAlignedPointer from Loads API, leaving isSafeToLoadSpecualtively the only function to check is load instruction can be speculated. Reviewed By: hfinkel Differential Revision: http://reviews.llvm.org/D16180 llvm-svn: 261736
* NFC. Move getAlignment helper function from ValueTracking to Value class. Artur Pilipenko2016-02-241-42/+2
| | | | | | | | Reviewed By: reames, hfinkel Differential Revision: http://reviews.llvm.org/D16144 llvm-svn: 261735
* [PM] Remove an overly aggressive assert now that I can actually test theChandler Carruth2016-02-231-1/+0
| | | | | | | | | | | | | | | | | pattern that triggers it. This essentially requires an immutable function analysis, as that will survive anything we do to invalidate it. When we have such patterns, the function analysis manager will not get cleared between runs of the proxy. If we actually need an assert about how things are queried, we can add more elaborate machinery for computing it, but so far I'm not aware of significant value provided. Thanks to Justin Lebar for noticing this when he made a (seemingly innocuous) change to FunctionAttrs that is enough to trigger it in one test there. Now it is covered by a direct test of the pass manager code. llvm-svn: 261627
* [PM] Improve the API and comments around the analysis manager proxies.Chandler Carruth2016-02-231-0/+8
| | | | | | | | | | | | | | | | | | | | | | | | These are really handles that ensure the analyses get cleared at appropriate places, and as such copying doesn't really make sense. Instead, they should look more like unique ownership objects. Make that the case. Relatedly, if you create a temporary of one and move out of it its destructor shouldn't actually clear anything. I don't think there is any code that can trigger this currently, but it seems like a more robust implementation. If folks want, I can add a unittest that forces this to be exercised, but that seems somewhat pointless -- whether a temporary is ever created in the innards of AnalysisManager is not really something we should be adding a reliance on, but I didn't want to leave a timebomb in the code here. If anyone has a cleaner way to represent this, I'm all ears, but I wanted to assure myself that this wasn't in fact responsible for another bug I'm chasing down (it wasn't) and figured I'd commit that. llvm-svn: 261594
* More detailed dependence test between volatile and non-volatile accessesKrzysztof Parzyszek2016-02-221-24/+26
| | | | | | Differential Revision: http://reviews.llvm.org/D16857 llvm-svn: 261589
* [ConstantRange] Rename a method and add more docSanjoy Das2016-02-221-5/+4
| | | | | | | | Rename makeNoWrapRegion to a more obvious makeGuaranteedNoWrapRegion, and add a comment about the counter-intuitive aspects of the function. This is to help prevent cases like PR26628. llvm-svn: 261532
* ADT: Remove == and != comparisons between ilist iterators and pointersDuncan P. N. Exon Smith2016-02-211-3/+3
| | | | | | | | | | | | | | I missed == and != when I removed implicit conversions between iterators and pointers in r252380 since they were defined outside ilist_iterator. Since they depend on getNodePtrUnchecked(), they indirectly rely on UB. This commit removes all uses of these operators. (I'll delete the operators themselves in a separate commit so that it can be easily reverted if necessary.) There should be NFC here. llvm-svn: 261498
* ScalerEvolution: Only erase temporary values if they actually have been addedTobias Grosser2016-02-211-5/+6
| | | | | | This addresses post-review comments from Sanjoy Das for r261485. llvm-svn: 261486
* ScalarEvolution: Do not keep temporary PHI values in ValueExprMapTobias Grosser2016-02-211-0/+5
| | | | | | | | | | Before this patch simplified SCEV expressions for PHI nodes were only returned the very first time getSCEV() was called, but later calls to getSCEV always returned the non-simplified value, which had "temporarily" been stored in the ValueExprMap, but was never removed and consequently blocked the caching of the simplified PHI expression. llvm-svn: 261485
* When MemoryDependenceAnalysis hits a CFG with many transparent blocks,Joerg Sonnenberger2016-02-201-6/+26
| | | | | | | | | | | | | | | | | | the algorithm easily degrades into quadratic memory and time complexity. The easiest example is a long chain of BBs that don't otherwise use a location. The caching will add an entry for every intermediate block and limiting the number of results doesn't help as no results are produced until a definition is found. Introduce a limit similar to the existing instructions-per-block limit. This limit counts the total number of blocks checked. If the limit is reached, entries are considered unknown. The initial value is 1000, which avoids regressions for normal sized functions while still limiting edge cases to reasnable memory consumption and execution time. Differential Revision: http://reviews.llvm.org/D16123 llvm-svn: 261430
* [LVI] Move ConstantRanges instead of copying.Benjamin Kramer2016-02-201-9/+8
| | | | | | | | No functional change intended. Copying small (<= 64 bits) APInts isn't expensive but bloats code by generating the slow path everywhere. Moving doesn't care about the size of the value. llvm-svn: 261426
* [PM/AA] Wire up CFLAA to the new pass manager fully, and port one of itsChandler Carruth2016-02-201-0/+1
| | | | | | | | | tests over to exercise this code. This uncovered a few missing bits here and there in the analysis, but nothing interesting. llvm-svn: 261404
* [PM/AA] Port alias analysis evaluator to the new pass manager, and useChandler Carruth2016-02-202-71/+66
| | | | | | | | | | | | | | | | it to actually test the new pass manager AA wiring. This patch was extracted from the (somewhat too large) D12357 and rebosed on top of the slightly different design of the new pass manager AA wiring that I just landed. With this we can start testing the AA in a thorough way with the new pass manager. Some minor cleanups to the code in the pass was necessitated here, but otherwise it is a very minimal change. Differential Revision: http://reviews.llvm.org/D17372 llvm-svn: 261403
* [SCEV] Don't spell `SCEV *` variables as `Scev`; NFCSanjoy Das2016-02-201-15/+14
| | | | | | | It reads odd since most other places name a `SCEV *` as `S`. Pure renaming change. llvm-svn: 261393
* [SCEV] Don't use std::make_pair; NFCSanjoy Das2016-02-201-15/+14
| | | | | | `{A, B}` reads cleaner than `std::make_pair(A, B)`. llvm-svn: 261392
* Remove uses of builtin comma operator.Richard Trieu2016-02-183-6/+12
| | | | | | Cleanup for upcoming Clang warning -Wcomma. No functionality change intended. llvm-svn: 261270
* [CaptureTracking] Support atomicrmw and cmpxchgPhilip Reames2016-02-181-0/+11
| | | | | | | | | | | | These atomic operations are conceptually both a load and store from the same location. As such, we can treat them as the most conservative of those two components which in practice, means we can treat them like stores. An cmpxchg or atomicrmw captures the values, but not the locations accessed. Note: We can probably be more aggressive about the comparison value in an cmpxhg since to have it be in memory, it must already be captured, but I figured it was better to avoid that for the moment. Note 2: It turns out that since we don't actually support cmpxchg of pointer type, writing a negative test is impossible. Differential Revision: http://reviews.llvm.org/D17400 llvm-svn: 261245
* [AliasSetTracker] Teach AliasSetTracker about MemSetInstHaicheng Wu2016-02-171-0/+41
| | | | | | | This change is to fix the problem discussed in http://lists.llvm.org/pipermail/llvm-dev/2016-February/095446.html. llvm-svn: 261052
* [LCG] Construct an actual call graph with call-edge SCCs nested insideChandler Carruth2016-02-171-388/+1181
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | reference-edge SCCs. This essentially builds a more normal call graph as a subgraph of the "reference graph" that was the old model. This allows both to exist and the different use cases to use the aspect which addresses their needs. Specifically, the pass manager and other *ordering* constrained logic can use the reference graph to achieve conservative order of visit, while analyses reasoning about attributes and other properties derived from reachability can reason about the direct call graph. Note that this isn't necessarily complete: it doesn't model edges to declarations or indirect calls. Those can be found by scanning the instructions of the function if desirable, and in fact every user currently does this in order to handle things like calls to instrinsics. If useful, we could consider caching this information in the call graph to save the instruction scans, but currently that doesn't seem to be important. An important realization for why the representation chosen here works is that the call graph is a formal subset of the reference graph and thus both can live within the same data structure. All SCCs of the call graph are necessarily contained within an SCC of the reference graph, etc. The design is to build 'RefSCC's to model SCCs of the reference graph, and then within them more literal SCCs for the call graph. The formation of actual call edge SCCs is not done lazily, unlike reference edge 'RefSCC's. Instead, once a reference SCC is formed, it directly builds the call SCCs within it and stores them in a post-order sequence. This is used to provide a consistent platform for mutation and update of the graph. The post-order also allows for very efficient updates in common cases by bounding the number of nodes (and thus edges) considered. There is considerable common code that I'm still looking for the best way to factor out between the various DFS implementations here. So far, my attempts have made the code harder to read and understand despite reducing the duplication, which seems a poor tradeoff. I've not given up on figuring out the right way to do this, but I wanted to wait until I at least had the system working and tested to continue attempting to factor it differently. This also requires introducing several new algorithms in order to handle all of the incremental update scenarios for the more complex structure involving two edge colorings. I've tried to comment the algorithms sufficiently to make it clear how this is expected to work, but they may still need more extensive documentation. I know that there are some changes which are not strictly necessarily coupled here. The process of developing this started out with a very focused set of changes for the new structure of the graph and algorithms, but subsequent changes to bring the APIs and code into consistent and understandable patterns also ended up touching on other aspects. There was no good way to separate these out without causing *massive* merge conflicts. Ultimately, to a large degree this is a rewrite of most of the core algorithms in the LCG class and so I don't think it really matters much. Many thanks to the careful review by Sanjoy Das! Differential Revision: http://reviews.llvm.org/D16802 llvm-svn: 261040
* Revert 260705, it appears to be causing pr26628Philip Reames2016-02-161-21/+0
| | | | | | The root issue appears to be a confusion around what makeNoWrapRegion actually does. It seems likely we need two versions of this function with slightly different semantics. llvm-svn: 260981
* [SCEVExpander] Make findExistingExpansion smarterJunmo Park2016-02-161-25/+35
| | | | | | | | | | | | | Summary: Extending findExistingExpansion can use existing value in ExprValueMap. This patch gives 0.3~0.5% performance improvements on benchmarks(test-suite, spec2000, spec2006, commercial benchmark) Reviewers: mzolotukhin, sanjoy, zzheng Differential Revision: http://reviews.llvm.org/D15559 llvm-svn: 260938
* [PM/AA] Actually wire the AAManager I built for the new pass managerChandler Carruth2016-02-131-0/+3
| | | | | | | | | | | | into the new pass manager and fix the latent bugs there. This lets everything live together nicely, but it isn't really useful yet. I never finished wiring the AA layer up for the new pass manager, and so subsequent patches will change this to do that wiring and get AA stuff more fully integrated into the new pass manager. Turns out this is necessary even to get functionattrs ported over. =] llvm-svn: 260836
* [ConstantFolding] Reduce APInt and APFloat copying.Benjamin Kramer2016-02-131-1/+1
| | | | llvm-svn: 260826
* Add convergent property to CodeMetrics.Justin Lebar2016-02-121-1/+4
| | | | | | | | | | | | Summary: No functional changes. Reviewers: jingyue, arsenm Subscribers: arsenm, llvm-commits Differential Revision: http://reviews.llvm.org/D17126 llvm-svn: 260728
* [LVI] Exploit nsw/nuw when computing constant rangesPhilip Reames2016-02-121-0/+21
| | | | | | | | | | As the title says. Modelled after similar code in SCEV. This is useful when analysing induction variables in loops which have been canonicalized by other passes. I wrote the tests as non-loops specifically to avoid the generality introduced in http://reviews.llvm.org/D17174. While that can handle many induction variables without *needing* to exploit nsw, there's no reason not to use it if we've already proven it. Differential Revision: http://reviews.llvm.org/D17177 llvm-svn: 260705
* [LVI] Improve select handling to use conditionPhilip Reames2016-02-121-0/+19
| | | | | | | | | | This patches teaches LVI to recognize clamp idioms (e.g. select(a > 5, a, 5) will always produce something greater than 5. The tests end up being somewhat simplistic because trying to exercise the case I actually care about (a loop with a range check on a clamped secondary induction variable) ends up tripping across a couple of other imprecisions in the analysis. Ah, the joys of LVI... Differential Revision: http://reviews.llvm.org/D16827 llvm-svn: 260627
* Make context-sensitive isDereferenceable queries in isSafeToLoadUnconditionallyArtur Pilipenko2016-02-111-2/+8
| | | | | | | | | | This is a part of the refactoring to unify isSafeToLoadUnconditionally and isDereferenceablePointer functions. In the subsequent change isSafeToSpeculativelyExecute will be modified to use isSafeToLoadUnconditionally instead of isDereferenceableAndAlignedPointer. Reviewed By: reames Differential Revision: http://reviews.llvm.org/D16227 llvm-svn: 260520
OpenPOWER on IntegriCloud