summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [PM] Implement the final conclusion as to how the analysis IDs shouldChandler Carruth2016-03-1120-15/+25
| | | | | | | | | | | | | | | | | | | | work in the face of the limitations of DLLs and templated static variables. This requires passes that use the AnalysisBase mixin provide a static variable themselves. So as to keep their APIs clean, I've made these private and befriended the CRTP base class (which is the common practice). I've added documentation to AnalysisBase for why this is necessary and at what point we can go back to the much simpler system. This is clearly a better pattern than the extern template as it caught *numerous* places where the template magic hadn't been applied and things were "just working" but would eventually have broken mysteriously. llvm-svn: 263216
* [PM/AA] Teach the AAManager how to handle module analyses in addition toChandler Carruth2016-03-111-0/+2
| | | | | | | function analyses, and use it to wire up globals-aa to the new pass manager. llvm-svn: 263211
* [CG] Back out my pointless move ctor and add the explicit templateChandler Carruth2016-03-101-0/+3
| | | | | | instantiation needed for the mingw dll build bot. llvm-svn: 263114
* [CG] Add a new pass manager printer pass for the old call graph andChandler Carruth2016-03-101-0/+6
| | | | | | | | | | | | | | | | | actually finish wiring up the old call graph. There were bugs in the old call graph that hadn't been caught because it wasn't being tested. It wasn't being tested because it wasn't in the pipeline system and we didn't have a printing pass to run in tests. This fixes all of that. As for why I'm still keeping the old call graph alive its so that I can port GlobalsAA to the new pass manager with out forking it to work with the lazy call graph. That's clearly the right eventual design, but it seems pragmatic to defer that until its necessary. The old call graph works just fine for GlobalsAA. llvm-svn: 263104
* [CG] Actually hoist up the generic CallGraphPrinter pass from a weirdChandler Carruth2016-03-102-0/+27
| | | | | | | | | | location in the opt tool to live along side the analysis in LLVM's libraries. No functionality changed here, but this will allow me to port the printer to the new pass manager as well. llvm-svn: 263101
* [CG] Rename the DOT printing pass to actually reference "DOT".Chandler Carruth2016-03-102-8/+8
| | | | | | | | | | | | | There is another pass by the generic name 'CallGraphPrinter' which is actually just a call graph printer tucked away inside the opt tool. I'd like to bring it out and make it follow the same patterns as the rest of the CallGraph code, but doing so would end up conflicting with the name of the DOT printing pass. So this makes the DOT printing pass name be more precise. No functionality changed here. llvm-svn: 263100
* [PM] Port memdep to the new pass manager.Chandler Carruth2016-03-103-86/+88
| | | | | | | | | | | | | | | | | | | | | | | This is a fairly straightforward port to the new pass manager with one exception. It removes a very questionable use of releaseMemory() in the old pass to invalidate its caches between runs on a function. I don't think this is really guaranteed to be safe. I've just used the more direct port to the new PM to address this by nuking the results object each time the pass runs. While this could cause some minor malloc traffic increase, I don't expect the compile time performance hit to be noticable, and it makes the correctness and other aspects of the pass much easier to reason about. In some cases, it may make things faster by making the sets and maps smaller with better locality. Indeed, the measurements collected by Bruno (thanks!!!) show mostly compile time improvements. There is sadly very limited testing at this point as there are only two tests of memdep, and both rely on GVN. I'll be porting GVN next and that will exercise this heavily though. Differential Revision: http://reviews.llvm.org/D17962 llvm-svn: 263082
* [BasicAA/MDA] Sink aliasing rules for malloc and calloc into BasicAAPhilip Reames2016-03-092-16/+17
| | | | | | | | | | MemoryDependenceAnalysis had a hard-coded exception to the general aliasing rules for malloc and calloc. The reasoning that applied there is equally valid in BasicAA and clarifies the remaining logic in MDA. In principal, this can expose slightly more optimization opportunities, but since essentially all of our aliasing aware memory optimization passes go through MDA, this will likely be NFC in practice. Differential Revision: http://reviews.llvm.org/D15912 llvm-svn: 263075
* [ValueTracking] Extract isKnownPositive [NFCI]Philip Reames2016-03-091-0/+12
| | | | | | Extract out a generic interface from a recently landed patch and document a TODO in case compile time becomes a problem. llvm-svn: 263062
* [SCEV] Slightly generalize getRangeViaFactoringSanjoy Das2016-03-091-13/+18
| | | | | | | | | Building on the previous change, this generalizes ScalarEvolution::getRangeViaFactoring to work with {Ext(C?A:B)+k0,+,Ext(C?A:B)+k1} where Ext can be a zero extend, sign extend or truncate operation, and k0 and k1 are constants. llvm-svn: 262979
* [SCEV] Slightly generalize getRangeViaFactoringSanjoy Das2016-03-091-23/+51
| | | | | | | | This change generalizes ScalarEvolution::getRangeViaFactoring to work with {Ext(C?A:B),+,Ext(C?A:B)} where Ext can be a zero extend, sign extend or truncate operation. llvm-svn: 262978
* use range-based for loop; NFCISanjay Patel2016-03-081-13/+12
| | | | llvm-svn: 262956
* Revert revisions 262636, 262643, 262679, and 262682.Easwaran Raman2016-03-081-86/+16
| | | | llvm-svn: 262883
* [memdep] Switch to range based for loops.Chandler Carruth2016-03-071-73/+46
| | | | llvm-svn: 262831
* [memdep] Switch a function to return true on success instead of false.Chandler Carruth2016-03-071-9/+9
| | | | | | | | This is much more clear and less surprising IMO. It also makes things more consistent with the increasingly large chunk of LLVM code that assumes true-on-success. llvm-svn: 262826
* [memdep] Cleanup the implementation doxygen comments and removeChandler Carruth2016-03-071-80/+35
| | | | | | | | | | duplicated comments. In several cases these had diverged making them especially nice to canonicalize. I checked to make sure we weren't losing important information of course. llvm-svn: 262825
* [memdep] Run clang-format over the header before porting it toChandler Carruth2016-03-071-144/+154
| | | | | | | | | | | the new pass manager. The port will involve substantial edits here, and would likely introduce bad formatting if formatted in isolation, so just get all the formatting up to snuff. I'll also go through and try to freshen the doxygen here as well as modernizing some of the code. llvm-svn: 262821
* [LVI] Fix a bug which prevented use of !range metadata within a queryPhilip Reames2016-03-041-22/+10
| | | | | | The diff is relatively large since I took a chance to rearrange the code I had to touch in a more obvious way, but the key bit is merely using the !range metadata when we can't analyze the instruction further. The previous !range metadata code was essentially just dead since no binary operator or cast will have !range metadata (per Verifier) and it was otherwise dropped on the floor. llvm-svn: 262751
* Fix a memory leak.Easwaran Raman2016-03-041-1/+4
| | | | llvm-svn: 262682
* [ValueTracking] "constant fold" an experimental hidden optionPhilip Reames2016-03-031-7/+0
| | | | llvm-svn: 262648
* [ValueTracking] Remove dead code from an old experimentPhilip Reames2016-03-031-208/+2
| | | | | | | | | | This experiment was originally about trying to use facts implied dominating conditions to infer more precise known bits. While the compile time was found to be acceptable on several large code bases, we never found sufficiently profitable examples to justify turning on the code by default. Given this, it's time to abandon the experiment. Several folks have commented that they've found this useful for experimentation, but nothing has come of those experiments. Given how easy the patch is to apply, there's no reason to leave the code in tree. For anyone interested in further investigation in this area, I recommend finding the summary email I sent on one of the original review threads. In particular, I now believe the use-list based approach is strictly worse than the dom-tree-walking approach. llvm-svn: 262646
* Fix breakage caused by r262636.Easwaran Raman2016-03-031-1/+1
| | | | | | Use LLVM_ATTRIBUTE_UNUSED instead of __attribute_((unused)) llvm-svn: 262643
* [SCEV] Prove no-overflow via constant rangesSanjoy Das2016-03-031-0/+41
| | | | | | | Exploit ScalarEvolution::getRange's newly acquired smartness (since r262438) by using that to infer nsw and nuw when possible. llvm-svn: 262639
* [SCEV] Be less eager about demoting zexts to sextsSanjoy Das2016-03-031-4/+5
| | | | | | | | | | | | After r262438 we can have provably positive NSW SCEV expressions whose zero extensions cannot be simplified (since r262438 makes SCEV better at computing constant ranges). This means demoting sexts of positive add recurrences eagerly can result in an unsimplified zero extension where we could have had a simplified sign extension. This change fixes the issue by teaching SCEV to demote sext of a positive SCEV expression to a zext only if the sext could not be simplified. llvm-svn: 262638
* Infrastructure for PGO enhancements in inlinerEaswaran Raman2016-03-031-16/+83
| | | | | | | | | | | | This patch provides the following infrastructure for PGO enhancements in inliner: Enable the use of block level profile information in inliner Incremental update of block frequency information during inlining Update the function entry counts of callees when they get inlined into callers. Differential Revision: http://reviews.llvm.org/D16381 llvm-svn: 262636
* [AA] Hoist the logic to reformulate various AA queries in terms of otherChandler Carruth2016-03-028-65/+158
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | parts of the AA interface out of the base class of every single AA result object. Because this logic reformulates the query in terms of some other aspect of the API, it would easily cause O(n^2) query patterns in alias analysis. These could in turn be magnified further based on the number of call arguments, and then further based on the number of AA queries made for a particular call. This ended up causing problems for Rust that were actually noticable enough to get a bug (PR26564) and probably other places as well. When originally re-working the AA infrastructure, the desire was to regularize the pattern of refinement without losing any generality. While I think it was successful, that is clearly proving to be too costly. And the cost is needless: we gain no actual improvement for this generality of making a direct query to tbaa actually be able to re-use some other alias analysis's refinement logic for one of the other APIs, or some such. In short, this is entirely wasted work. To the extent possible, delegation to other API surfaces should be done at the aggregation layer so that we can avoid re-walking the aggregation. In fact, this significantly simplifies the logic as we no longer need to smuggle the aggregation layer into each alias analysis (or the TargetLibraryInfo into each alias analysis just so we can form argument memory locations!). However, we also have some delegation logic inside of BasicAA and some of it even makes sense. When the delegation logic is baking in specific knowledge of aliasing properties of the LLVM IR, as opposed to simply reformulating the query to utilize a different alias analysis interface entry point, it makes a lot of sense to restrict that logic to a different layer such as BasicAA. So one aspect of the delegation that was in every AA base class is that when we don't have operand bundles, we re-use function AA results as a fallback for callsite alias results. This relies on the IR properties of calls and functions w.r.t. aliasing, and so seems a better fit to BasicAA. I've lifted the logic up to that point where it seems to be a natural fit. This still does a bit of redundant work (we query function attributes twice, once via the callsite and once via the function AA query) but it is *exactly* twice here, no more. The end result is that all of the delegation logic is hoisted out of the base class and into either the aggregation layer when it is a pure retargeting to a different API surface, or into BasicAA when it relies on the IR's aliasing properties. This should fix the quadratic query pattern reported in PR26564, although I don't have a stand-alone test case to reproduce it. It also seems general goodness. Now the numerous AAs that don't need target library info don't carry it around and depend on it. I think I can even rip out the general access to the aggregation layer and only expose that in BasicAA as it is the only place where we re-query in that manner. However, this is a non-trivial change to the AA infrastructure so I want to get some additional eyes on this before it lands. Sadly, it can't wait long because we should really cherry pick this into 3.8 if we're going to go this route. Differential Revision: http://reviews.llvm.org/D17329 llvm-svn: 262490
* [SCEV] Minor naming, braces cleanup; NFCSanjoy Das2016-03-021-5/+4
| | | | llvm-svn: 262459
* Add a comment with a rational for the unusual code structureSanjoy Das2016-03-021-0/+3
| | | | llvm-svn: 262454
* Qualify getRangeForAffineAR with this-> for MSVCSanjoy Das2016-03-021-2/+2
| | | | llvm-svn: 262453
* Perturb code in an attempt to appease MSVCSanjoy Das2016-03-021-9/+9
| | | | | | | | For some reason MSVC seems to think I'm calling getConstant() from a static context. Try to avoid this issue by explicitly specifying 'this->' (though I'm not confident that this will actually work). llvm-svn: 262451
* More code permutation to appease MSVCSanjoy Das2016-03-021-4/+7
| | | | llvm-svn: 262449
* Remove "auto" to appease the MSVC botsSanjoy Das2016-03-021-2/+2
| | | | llvm-svn: 262448
* [SCEV] Make getRange smarter around selectsSanjoy Das2016-03-021-0/+83
| | | | | | | | | | | | Have ScalarEvolution::getRange re-consider cases like "{C?A:B,+,C?P:Q}" by factoring out "C" and computing RangeOf{A,+,P} union RangeOf({B,+,Q}) instead. The latter can be easier to compute precisely in cases like "{C?0:N,+,C?1:-1}" N is the backedge taken count of the loop; since in such cases the latter form simplifies to [0,N+1) union [0,N+1). llvm-svn: 262438
* [SCEV] Extract out a getRangeForAffineAR; NFCSanjoy Das2016-03-021-57/+71
| | | | | | Pure code-motion change. Will be used later in making getRange more clever. llvm-svn: 262437
* [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
OpenPOWER on IntegriCloud