summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
* Change TargetLibraryInfo analysis passes to always require FunctionTeresa Johnson2019-09-071-6/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This is the first change to enable the TLI to be built per-function so that -fno-builtin* handling can be migrated to use function attributes. See discussion on D61634 for background. This is an enabler for fixing handling of these options for LTO, for example. This change should not affect behavior, as the provided function is not yet used to build a specifically per-function TLI, but rather enables that migration. Most of the changes were very mechanical, e.g. passing a Function to the legacy analysis pass's getTLI interface, or in Module level cases, adding a callback. This is similar to the way the per-function TTI analysis works. There was one place where we were looking for builtins but not in the context of a specific function. See FindCXAAtExit in lib/Transforms/IPO/GlobalOpt.cpp. I'm somewhat concerned my workaround could provide the wrong behavior in some corner cases. Suggestions welcome. Reviewers: chandlerc, hfinkel Subscribers: arsenm, dschuff, jvesely, nhaehnle, mehdi_amini, javed.absar, sbc100, jgravelle-google, eraman, aheejin, steven_wu, george.burgess.iv, dexonsmith, jfb, asbirlea, gchatelet, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D66428 llvm-svn: 371284
* [AliasAnalysis] Second prototype to cache BasicAA / anyAA state.Alina Sbirlea2019-03-221-3/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Adding contained caching to AliasAnalysis. BasicAA is currently the only one using it. AA changes: - This patch is pulling the caches from BasicAAResults to AAResults, meaning the getModRefInfo call benefits from the IsCapturedCache as well when in "batch mode". - All AAResultBase implementations add the QueryInfo member to all APIs. AAResults APIs maintain wrapper APIs such that all alias()/getModRefInfo call sites are unchanged. - AA now provides a BatchAAResults type as a wrapper to AAResults. It keeps the AAResults instance and a QueryInfo instantiated to batch mode. It delegates all work to the AAResults instance with the batched QueryInfo. More API wrappers may be needed in BatchAAResults; only the minimum needed is currently added. MemorySSA changes: - All walkers are now templated on the AA used (AliasAnalysis=AAResults or BatchAAResults). - At build time, we optimize uses; now we create a local walker (lives only as long as OptimizeUses does) using BatchAAResults. - All Walkers have an internal AA and only use that now, never the AA in MemorySSA. The Walkers receive the AA they will use when built. - The walker we use for queries after the build is instantiated on AliasAnalysis and is built after building MemorySSA and setting AA. - All static methods doing walking are now templated on AliasAnalysisType if they are used both during build and after. If used only during build, the method now only takes a BatchAAResults. If used only after build, the method now takes an AliasAnalysis. Subscribers: sanjoy, arsenm, jvesely, nhaehnle, jlebar, george.burgess.iv, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D59315 llvm-svn: 356783
* [CFLAnders] Fix typo in comment; NFCGeorge Burgess IV2019-03-081-1/+1
| | | | | | | | Patch by Enna1! Differential Revision: https://reviews.llvm.org/D58756 llvm-svn: 355715
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* Replace most users of UnknownSize with LocationSize::unknown(); NFCGeorge Burgess IV2018-10-101-3/+3
| | | | | | | | | | | | Moving away from UnknownSize is part of the effort to migrate us to LocationSizes (e.g. the cleanup promised in D44748). This doesn't entirely remove all of the uses of UnknownSize; some uses require tweaks to assume that UnknownSize isn't just some kind of int. This patch is intended to just be a trivial replacement for all places where LocationSize::unknown() will Just Work. llvm-svn: 344186
* Make LocationSize a proper Optional type; NFCGeorge Burgess IV2018-10-091-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is the second in a series of changes intended to make https://reviews.llvm.org/D44748 more easily reviewable. Please see that patch for more context. The first change being r344012. Since I was requested to do all of this with post-commit review, this is about as small as I can make this patch. This patch makes LocationSize into an actual type that wraps a uint64_t; users are required to call getValue() in order to get the size now. If the LocationSize has an Unknown size (e.g. if LocSize == MemoryLocation::UnknownSize), getValue() will assert. This also adds DenseMap specializations for LocationInfo, which required taking two more values from the set of values LocationInfo can represent. Hence, heavy users of multi-exabyte arrays or structs may observe slightly lower-quality code as a result of this change. The intent is for getValue()s to be very close to a corresponding hasValue() (which is often spelled `!= MemoryLocation::UnknownSize`). Sadly, small diff context appears to crop that out sometimes, and the last change in DSE does require a bit of nonlocal reasoning about control-flow. :/ This also removes an assert, since it's now redundant with the assert in getValue(). llvm-svn: 344013
* Use locals instead of struct fields; NFCGeorge Burgess IV2018-10-091-6/+8
| | | | | | | | | | | | | | | | | | | | | | | | | This is one of a series of changes intended to make https://reviews.llvm.org/D44748 more easily reviewable. Please see that patch for more context. Since I was requested to do all of this with post-commit review, this is about as small as I can make it (beyond committing changes to these few files separately, but they're incredibly similar in spirit, so...) On its own, this change doesn't make a great deal of sense. I plan on having a follow-up Real Soon Now(TM) to make the bits here make more sense. :) In particular, the next change in this series is meant to make LocationSize an actual type, which you have to call .getValue() on in order to get at the uint64_t inside. Hence, this change refactors code so that: - we only need to call the soon-to-come getValue() once in most cases, and - said call to getValue() happens very closely to a piece of code that checks if the LocationSize has a value (e.g. if it's != UnknownSize). llvm-svn: 344012
* llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)Fangrui Song2018-09-271-2/+2
| | | | | | | | | | | | Summary: The convenience wrapper in STLExtras is available since rL342102. Reviewers: dblaikie, javed.absar, JDevlieghere, andreadb Subscribers: MatzeB, sanjoy, arsenm, dschuff, mehdi_amini, sdardis, nemanjai, jvesely, nhaehnle, sbc100, jgravelle-google, eraman, aheejin, kbarton, JDevlieghere, javed.absar, gbedwell, jrtc27, mgrang, atanasyan, steven_wu, george.burgess.iv, dexonsmith, kristina, jsji, llvm-commits Differential Revision: https://reviews.llvm.org/D52573 llvm-svn: 343163
* Replace AA's uses of uint64_t with LocationSize; NFC.George Burgess IV2018-05-251-3/+3
| | | | | | | | | | | | | | | | The uint64_ts that we pass around AA to represent MemoryLocation sizes are logically an Optional<uint64_t>. In D44748, we want to add an extra 'imprecise' bit to this Optional<uint64_t> to represent whether a given MemoryLocation size is an upper-bound or an exact size. For more context on why, please see D44748. That patch is quite large, but reviewers seem to be OK with the approach. In D45581 (my first attempt to split 'noise' out of D44748), reames asked that I land a precursor that is solely replacing uint64_t with LocationSize, which starts out as `using LocationSize = uint64_t;`. He also gave me the OK to submit this rename without further review. llvm-svn: 333314
* Revert r332657: "[AA] cfl-anders-aa with field sensitivity"George Burgess IV2018-05-171-135/+102
| | | | | | | I don't believe the person who LGTMed this review has appropriate context on this code. I apologize if I'm wrong. llvm-svn: 332674
* [AA] cfl-anders-aa with field sensitivityDavid Bolvansky2018-05-171-102/+135
| | | | | | | | | | | | | | | | | | | Summary: There was some unfinished work started for offset tracking in CFLGraph by the author of implementation of Andersen algorithm. This work was completed and support for field sensitivity was added to the core of Andersen algorithm. The performance results seem promising. SPEC2006 int_base score was increased by 1.1 % (I compared clang 6.0 with clang 6.0 with this patch). The avergae compile time was increased by +- 1 % according my measures with small and medium C/C++ projects (I did not tested it on the large projects with milions of lines of code) Reviewers: chandlerc, george.burgess.iv, rja Reviewed By: rja Subscribers: rja, llvm-commits Differential Revision: https://reviews.llvm.org/D46282 llvm-svn: 332657
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-2/+3
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* [Analysis] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang2018-04-011-2/+2
| | | | | | | | | | | | | | | | | | | | | | Summary: r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key. To make use of that infrastructure we need to invoke llvm::sort instead of std::sort. Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort. Refer D44363 for a list of all the required patches. Reviewers: sanjoy, dexonsmith, hfinkel, RKSimon Reviewed By: dexonsmith Subscribers: david2050, llvm-commits Differential Revision: https://reviews.llvm.org/D44944 llvm-svn: 328925
* Fix more spelling mistakes in comments of LLVM Analysis passesVedant Kumar2018-03-021-2/+2
| | | | | | | | Patch by Reshabh Sharma! Differential Revision: https://reviews.llvm.org/D43939 llvm-svn: 326601
* [Analysis] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko2017-08-111-28/+66
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 310766
* CFLAA: return MustAlias when pointers p, q are equal, i.e.,Nuno Lopes2017-08-091-1/+1
| | | | | | | | | | | must-alias(p, sz_p, p, sz_q) irrespective of access sizes sz_p, sz_q As discussed a couple of weeks ago on the ML. This makes the behavior consistent with that of BasicAA. AA clients already check the obj size themselves and may not require the obj size to match exactly the access size (e.g., in case of store forwarding) llvm-svn: 310495
* [CFLAA] Move a common function to the header to reduce duplication.Davide Italiano2017-06-271-11/+0
| | | | | | Differential Revision: https://reviews.llvm.org/D34660 llvm-svn: 306354
* [CFLAA] Change FunctionHandle to be common to Steensgaard's and Andersens'Davide Italiano2017-06-261-2/+2
| | | | | | Differential Revision: https://reviews.llvm.org/D34638 llvm-svn: 306348
* Apply clang-tidy's performance-unnecessary-value-param to LLVM.Benjamin Kramer2017-01-131-2/+2
| | | | | | | With some minor manual fixes for using function_ref instead of std::function. No functional change intended. llvm-svn: 291904
* [PM] Change the static object whose address is used to uniquely identifyChandler Carruth2016-11-231-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | analyses to have a common type which is enforced rather than using a char object and a `void *` type when used as an identifier. This has a number of advantages. First, it at least helps some of the confusion raised in Justin Lebar's code review of why `void *` was being used everywhere by having a stronger type that connects to documentation about this. However, perhaps more importantly, it addresses a serious issue where the alignment of these pointer-like identifiers was unknown. This made it hard to use them in pointer-like data structures. We were already dodging this in dangerous ways to create the "all analyses" entry. In a subsequent patch I attempted to use these with TinyPtrVector and things fell apart in a very bad way. And it isn't just a compile time or type system issue. Worse than that, the actual alignment of these pointer-like opaque identifiers wasn't guaranteed to be a useful alignment as they were just characters. This change introduces a type to use as the "key" object whose address forms the opaque identifier. This both forces the objects to have proper alignment, and provides type checking that we get it right everywhere. It also makes the types somewhat less mysterious than `void *`. We could go one step further and introduce a truly opaque pointer-like type to return from the `ID()` static function rather than returning `AnalysisKey *`, but that didn't seem to be a clear win so this is just the initial change to get to a reliably typed and aligned object serving is a key for all the analyses. Thanks to Richard Smith and Justin Lebar for helping pick plausible names and avoid making this refactoring many times. =] And thanks to Sean for the super fast review! While here, I've tried to move away from the "PassID" nomenclature entirely as it wasn't really helping and is overloaded with old pass manager constructs. Now we have IDs for analyses, and key objects whose address can be used as IDs. Where possible and clear I've shortened this to just "ID". In a few places I kept "AnalysisID" to make it clear what was being identified. Differential Revision: https://reviews.llvm.org/D27031 llvm-svn: 287783
* Make some LLVM_CONSTEXPR variables const. NFC.George Burgess IV2016-08-251-4/+2
| | | | | | | | | | This patch changes LLVM_CONSTEXPR variable declarations to const variable declarations, since LLVM_CONSTEXPR expands to nothing if the current compiler doesn't support constexpr. In all of the changed cases, it looks like the code intended the variable to be const instead of sometimes-constexpr sometimes-not. llvm-svn: 279696
* Consistently use FunctionAnalysisManagerSean Silva2016-08-091-1/+1
| | | | | | | | | | | Besides a general consistently benefit, the extra layer of indirection allows the mechanical part of https://reviews.llvm.org/D23256 that requires touching every transformation and analysis to be factored out cleanly. Thanks to David for the suggestion. llvm-svn: 278077
* [CFLAA] Be more conservative with values we haven't seen.George Burgess IV2016-08-021-11/+16
| | | | | | | | | | | | | | There were issues with simply reporting AttrUnknown on previously-unknown values in CFLAnders. So, we now act *entirely* conservatively for values we haven't seen before. As in the prior patch (r277362), writing a lit test for this isn't exactly trivial. If someone wants a test badly, I'm willing to try to write one. Patch by Jia Chen. Differential Revision: https://reviews.llvm.org/D23077 llvm-svn: 277533
* [CFLAA] Remove modref queries from CFLAA.George Burgess IV2016-08-011-106/+0
| | | | | | | | | | | | | | | | | | | | As it turns out, modref queries are broken with CFLAA. Specifically, the data source we were using for determining modref behaviors explicitly ignores operations on non-pointer values. So, it wouldn't note e.g. storing an i32 to an i32* (or loading an i64 from an i64*). It also ignores external function calls, rather than acting conservatively for them. (N.B. These operations, where necessary, *are* tracked by CFLAA; we just use a different mechanism to do so. Said mechanism is relatively imprecise, so it's unlikely that we can provide reasonably good modref answers with it as implemented.) Patch by Jia Chen. Differential Revision: https://reviews.llvm.org/D22978 llvm-svn: 277366
* [CFLAA] Make CFLAnders more conservative with new Values.George Burgess IV2016-08-011-4/+7
| | | | | | | | | | | | | | Currently, CFLAnders assumes that values it hasn't seen don't alias anything. This patch fixes that. Given that the only way for this to happen is to query AA, rely on specific transformations happening, then query AA again (looking for a specific set of queries), lit testing is a bit difficult. If someone really wants a test, I'm happy to add one. Patch by Jia Chen. Differential Revision: https://reviews.llvm.org/D22981 llvm-svn: 277362
* [CFLAA] Add getModRefBehavior to CFLAnders.George Burgess IV2016-07-271-0/+106
| | | | | | | | | | | This patch lets CFLAnders respond to mod-ref queries. It also includes a small bugfix to CFLSteens. Patch by Jia Chen. Differential Revision: https://reviews.llvm.org/D22823 llvm-svn: 276939
* [CFLAA] Add more offset-sensitivity tracking.George Burgess IV2016-07-221-27/+136
| | | | | | | | | | | | | | | | | | | This patch teaches FunctionInfo about offsets. Like the last patch, this one doesn't introduce any visible functionality change (the core algorithm knows nothing about offsets; they're just plumbed through). Tests will come when we start acting differently because of the offsets. Patch by Jia Chen. (N.B. I made a tiny change to Jia's patch to avoid warnings by GCC: I put DenseMapInfo specializations in the `llvm` namespace. Only realized that those appeared when compiling locally. :) ) Differential Revision: https://reviews.llvm.org/D22634 llvm-svn: 276486
* Attempt to appease MSVC buildbots.George Burgess IV2016-07-191-8/+10
| | | | | | Broken by r276026. llvm-svn: 276032
* [CFLAA] Add some interproc. analysis to CFLAnders.George Burgess IV2016-07-191-8/+156
| | | | | | | | | | | This patch adds function summary support to CFLAnders. It also comes with a lot of tests! Woohoo! Patch by Jia Chen. Differential Revision: https://reviews.llvm.org/D22450 llvm-svn: 276026
* [CFLAA] Teach CFLAnders to distinguish reads from writes.George Burgess IV2016-07-191-50/+95
| | | | | | | | | | | | | | | | | | | | | | | This patch adds more specific edges to CFLAndersAliasAnalysis. The goal of these edges is to give us more information about *how* two values that MayAlias alias. With this, we can now tell cases like a = b; // ergo, a may alias b apart from a = c; b = c; // so, a may alias b, but only because they were both assigned to c. ...And others. Patch by Jia Chen. Differential Revision: https://reviews.llvm.org/D22429 llvm-svn: 276023
* [CFLAA] Add attributes handling for CFLAnders.George Burgess IV2016-07-151-9/+127
| | | | | | | | | | | | This patch adds proper handling of stratified attributes into our anders-style CFLAA implementation. It also comes bundled with more CFLAnders tests. :) Patch by Jia Chen. Differential Revision: https://reviews.llvm.org/D22325 llvm-svn: 275604
* [CFLAA] Add an initial CFLAnders implementation.George Burgess IV2016-07-151-3/+409
| | | | | | | | | | | | | This adds an incomplete anders-style implementation for CFLAA. It's incomplete in that it's missing interprocedural analysis, attrs handling, etc. and that it needs more tests. More tests and features will be added in future commits. Patch by Jia Chen. Differential Revision: https://reviews.llvm.org/D22291 llvm-svn: 275602
* [CFLAA] Split the CFL graph out from CFLSteens. NFC.George Burgess IV2016-07-061-0/+2
| | | | | | | | Patch by Jia Chen. Differential Revision: http://reviews.llvm.org/D21963 llvm-svn: 274591
* [CFLAA] Split into Anders+Steens analysis.George Burgess IV2016-07-061-0/+58
StratifiedSets (as implemented) is very fast, but its accuracy is also limited. If we take a more aggressive andersens-like approach, we can be way more accurate, but we'll also end up being slower. So, we've decided to split CFLAA into CFLSteensAA and CFLAndersAA. Long-term, we want to end up in a place where CFLSteens is queried first; if it can provide an answer, great (since queries are basically map lookups). Otherwise, we'll fall back to CFLAnders, BasicAA, etc. This patch splits everything out so we can try to do something like that when we get a reasonable CFLAnders implementation. Patch by Jia Chen. Differential Revision: http://reviews.llvm.org/D21910 llvm-svn: 274589
OpenPOWER on IntegriCloud