summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/AliasSetTracker.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
* [LICM/AST] Check if the AliasAny set is removed from the tracker.Alina Sbirlea2019-09-121-2/+10
| | | | | | | | | | | | | | | | Summary: Resolves PR38513. Credit to @bjope for debugging this. Reviewers: hfinkel, uabelho, bjope Subscribers: sanjoy.google, bjope, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67417 llvm-svn: 371752
* [LICM/MSSA] Add promotion to scalars by building an AliasSetTracker with ↵Alina Sbirlea2019-02-061-0/+11
| | | | | | | | | | | | | | | | | | | | | | | | MemorySSA. Summary: Experimentally we found that promotion to scalars carries less benefits than sinking and hoisting in LICM. When using MemorySSA, we build an AliasSetTracker on demand in order to reuse the current infrastructure. We only build it if less than AccessCapForMSSAPromotion exist in the loop, a cap that is by default set to 250. This value ensures there are no runtime regressions, and there are small compile time gains for pathological cases. A much lower value (20) was found to yield a single regression in the llvm-test-suite and much higher benefits for compile times. Conservatively we set the current cap to a high value, but we will explore lowering it when MemorySSA is enabled by default. Reviewers: sanjoy, chandlerc Subscribers: nemanjai, jlebar, Prazek, george.burgess.iv, jfb, jsji, llvm-commits Differential Revision: https://reviews.llvm.org/D56625 llvm-svn: 353339
* [AliasSetTracker] Pass MustAlias to addPointer more often.Alina Sbirlea2019-02-061-24/+36
| | | | | | | | | | | | | | | Summary: Pass the alias info to addPointer when available. Will save an alias() call for must sets when adding a known Must or May alias. [Part of a series of cleanup patches] Reviewers: reames, mkazantsev Subscribers: sanjoy, jlebar, llvm-commits Differential Revision: https://reviews.llvm.org/D56613 llvm-svn: 353335
* [AliasSetTracker] Minor style tweak to avoid a variable w/two distinct live ↵Philip Reames2019-02-061-4/+2
| | | | | | ranges [NFC] llvm-svn: 353267
* [AliasSetTracker] Cleanup more comments. [NFCI]Alina Sbirlea2019-01-281-4/+6
| | | | llvm-svn: 352416
* [AliasSetTracker] Cleanup comments. [NFCI]Alina Sbirlea2019-01-281-5/+8
| | | | llvm-svn: 352406
* [AliasSetTracker] Update signature to aliasesPointer [NFCI].Alina Sbirlea2019-01-281-11/+13
| | | | llvm-svn: 352399
* 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
* [CallSite removal] Migrate all Alias Analysis APIs to use the newlyChandler Carruth2019-01-071-39/+39
| | | | | | | | | | | | | | | | | | | | | | | | | | minted `CallBase` class instead of the `CallSite` wrapper. This moves the largest interwoven collection of APIs that traffic in `CallSite`s. While a handful of these could have been migrated with a minorly more shallow migration by converting from a `CallSite` to a `CallBase`, it hardly seemed worth it. Most of the APIs needed to migrate together because of the complex interplay of AA APIs and the fact that converting from a `CallBase` to a `CallSite` isn't free in its current implementation. Out of tree users of these APIs can fairly reliably migrate with some combination of `.getInstruction()` on the `CallSite` instance and casting the resulting pointer. The most generic form will look like `CS` -> `cast_or_null<CallBase>(CS.getInstruction())` but in most cases there is a more elegant migration. Hopefully, this migrates enough APIs for users to fully move from `CallSite` to the base class. All of the in-tree users were easily migrated in that fashion. Thanks for the review from Saleem! Differential Revision: https://reviews.llvm.org/D55641 llvm-svn: 350503
* [AliasSetTracker] Misc cleanup (NFCI)Alina Sbirlea2018-11-011-14/+6
| | | | | Summary: Remove two redundant checks, add one in the unit test. Remove an unused method. Fix computation of TotalMayAliasSetSize. llvm-svn: 345911
* [AliasSetTracker] Cleanup addPointer interface. [NFCI]Alina Sbirlea2018-10-291-6/+6
| | | | | | | | | | | | | | Summary: Attempting to simplify the addPointer interface. Currently there's code decomposing a MemoryLocation into (Ptr, Size, AAMDNodes) only to recreate the MemoryLocation inside the call. Reviewers: reames, mkazantsev Subscribers: sanjoy, jlebar, llvm-commits Differential Revision: https://reviews.llvm.org/D53836 llvm-svn: 345548
* Replace most users of UnknownSize with LocationSize::unknown(); NFCGeorge Burgess IV2018-10-101-1/+1
| | | | | | | | | | | | 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
* [AST] Visit memtransfer arguments in orderPhilip Reames2018-09-101-1/+1
| | | | | | | | | | The only point to this change is the test diffs. When I remove this code entirely (in favor of the recently added generic handling), I don't want there to be any confusion due to spurious test diffs. As an aside, the fact out tests are AST construction order dependent is not great. I thought about fixing that, but the reasonable schemes I might want (e.g. sort by name) need the test diffs anyways. Philip llvm-svn: 341841
* [AST] Generalize argument specific aliasingPhilip Reames2018-09-071-0/+40
| | | | | | | | | | | | | | AliasSetTracker has special case handling for memset, memcpy and memmove which pre-existed argmemonly on functions and readonly and writeonly on arguments. This patch generalizes it using the AA infrastructure to any call correctly annotated. The motivation here is to cut down on confusion, not performance per se. For most instructions, there is a direct mapping to alias set. However, this is not guaranteed by the interface and was not in fact true for these three intrinsics *and only these three intrinsics*. I kept getting myself confused about this invariant, so I figured it would be good to clearly distinguish between a instructions and alias sets. Calls happened to be an easy target. The nice side effect is that custom implementations of memset/memcpy/memmove - including wrappers discovered by IPO - can now be optimized the same as builts by LICM. Note: The actual removal of the memset/memtransfer specific handling will happen in a follow on NFC patch. It was originally part of this one, but separate for ease of review and rebase. Differential Revision: https://reviews.llvm.org/D50730 llvm-svn: 341713
* Re-enable "[NFC] Unify guards detection"Max Kazantsev2018-08-301-2/+2
| | | | | | | | | | rL340921 has been reverted by rL340923 due to linkage dependency from Transform/Utils to Analysis which is not allowed. In this patch this has been fixed, a new utility function moved to Analysis. Differential Revision: https://reviews.llvm.org/D51152 llvm-svn: 341014
* [LICM] Hoist stores of invariant values to invariant addresses out of loopsPhilip Reames2018-08-291-3/+16
| | | | | | | | | | | | Teach LICM to hoist stores out of loops when the store writes to a location otherwise unused in the loop, writes a value which is invariant, and is guaranteed to execute if the loop is entered. Worth noting is that this transformation is partially overlapping with the existing promotion transformation. Reasons this is worthwhile anyway include: * For multi-exit loops, this doesn't require duplication of the store. * It kicks in for case where we can't prove we exit through a normal exit (i.e. we may throw), but can prove the store executes before that possible side exit. Differential Revision: https://reviews.llvm.org/D50925 llvm-svn: 340974
* Revert r340921 "[NFC] Unify guards detection"Hans Wennborg2018-08-291-2/+2
| | | | | | | | | | | | | | | | | | This broke the build, see e.g. http://lab.llvm.org:8011/builders/clang-cmake-armv8-lnt/builds/4626/ http://lab.llvm.org:8011/builders/clang-ppc64be-linux-lnt/builds/18647/ http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/5856/ http://lab.llvm.org:8011/builders/lld-x86_64-freebsd/builds/22800/ > We have multiple places in code where we try to identify whether or not > some instruction is a guard. This patch factors out this logic into a separate > utility function which works uniformly in all places. > > Differential Revision: https://reviews.llvm.org/D51152 > Reviewed By: fedor.sergeev llvm-svn: 340923
* [NFC] Unify guards detectionMax Kazantsev2018-08-291-2/+2
| | | | | | | | | | | We have multiple places in code where we try to identify whether or not some instruction is a guard. This patch factors out this logic into a separate utility function which works uniformly in all places. Differential Revision: https://reviews.llvm.org/D51152 Reviewed By: fedor.sergeev llvm-svn: 340921
* [AST] Minor whitespace cleanup [NFC]Philip Reames2018-08-221-11/+7
| | | | llvm-svn: 340440
* [AST] Fix a whitespace typo [NFC]Philip Reames2018-08-221-1/+1
| | | | llvm-svn: 340384
* [AST] Reorder code to reduce a future patch diff [NFC]Philip Reames2018-08-221-3/+3
| | | | llvm-svn: 340383
* [AST] Move a function definition into the cpp [NFC]Philip Reames2018-08-221-0/+12
| | | | llvm-svn: 340382
* [AST] Remove notion of volatile from alias sets [NFCI]Philip Reames2018-08-211-24/+8
| | | | | | | | | | Volatility is not an aliasing property. We used to model volatile as if it had extremely conservative aliasing implications, but that hasn't been true for several years now. So, it doesn't make sense to be in AliasSet. It also turns out the code is entirely a noop. Outside of the AST code to update it, there was only one user: load store promotion in LICM. L/S promotion doesn't need the check since it walks all the users of the address anyway. It already checks each load or store via !isUnordered which causes us to bail for volatile accesses. (Look at the lines immediately following the two remove asserts.) There is the possibility of some small compile time impact here, but the only case which will get noticeably slower is a loop with a large number of loads and stores to the same address where only the last one we inspect is volatile. This is sufficiently rare it's not worth optimizing for.. llvm-svn: 340312
* [AST] Mark invariant.starts as being readonlyPhilip Reames2018-08-211-1/+2
| | | | | | | | These intrinsics are modelled as writing for control flow purposes, but they don't actually write to any location. Marking these - as we did for guards - allows LICM to hoist loads out of loops containing invariant.starts. Differential Revision: https://reviews.llvm.org/D50861 llvm-svn: 340245
* [AST] Clarify printing of unknown size locations [NFC]Philip Reames2018-08-171-1/+4
| | | | | | Printing "unknown" is much more clear than an arbitrary large integer llvm-svn: 340108
* [LICM][NFC] Restructure pointer invalidation API in terms of MemoryLocationPhilip Reames2018-08-161-6/+7
| | | | | | | | Main value is just simplifying code. I'll further simply the argument handling case in a bit, but that involved a slightly orthogonal change so I went with the mildy ugly intermediate for this patch. Note that the isSized check in the old LICM code was not carried across. It turns out that check was dead. a) no test exercised it, and b) langref and verifier had been updated to disallow unsized types used in loads. llvm-svn: 339930
* [AliasSetTracker] Do not treat experimental_guard intrinsic as memory ↵Max Kazantsev2018-08-151-1/+7
| | | | | | | | | | | | | | | | writing instruction The `experimental_guard` intrinsic has memory write semantics to model the thread-exiting logic, but does not do any actual writes to memory. Currently, `AliasSetTracker` treats it as a normal memory write. As result, a loop-invariant load cannot be hoisted out of loop because the guard may possibly alias with it. This patch makes `AliasSetTracker` so that it doesn't treat guards as memory writes. Differential Revision: https://reviews.llvm.org/D50497 Reviewed By: reames llvm-svn: 339753
* [AST] Minor formatting cleanup [NFC]Philip Reames2018-08-131-8/+4
| | | | llvm-svn: 339627
* [AST] Cleanup code by using MemoryLocation utility [NFC]Philip Reames2018-08-131-43/+11
| | | | | | Differential Revision: https://reviews.llvm.org/D50588 llvm-svn: 339625
* Remove trailing spaceFangrui Song2018-07-301-8/+8
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* [AliasSet] Fix UnknownInstructions printingJakub Kuderski2018-06-271-2/+6
| | | | | | | | | | | | | | | | | Summary: AliasSet::print uses `I->printAsOperand` to print UnknownInstructions. The problem is that not all UnknownInstructions have names (e.g. call instructions). When such instructions are printed, they appear as `<badref>` in AliasSets, which is very confusing, as the values are perfectly valid. This patch fixes that by printing UnknownInstructions without a name using `print` instead of `printAsOperand`. Reviewers: asbirlea, chandlerc, sanjoy, grosser Reviewed By: asbirlea Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D48609 llvm-svn: 335751
* [AliasSet] Teach the alias set how to handle atomic memcpy/memmove/memsetDaniel Neilson2018-05-301-8/+11
| | | | | | | | | Summary: The atomic variants of the memcpy/memmove/memset intrinsics can be treated the same was as the regular forms, with respect to aliasing. Update the AliasSetTracker to treat the atomic forms the same was as the regular forms. llvm-svn: 333551
* Replace AA's uses of uint64_t with LocationSize; NFC.George Burgess IV2018-05-251-6/+8
| | | | | | | | | | | | | | | | 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
* IWYU for llvm-config.h in llvm, additions.Nico Weber2018-04-301-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | See r331124 for how I made a list of files missing the include. I then ran this Python script: for f in open('filelist.txt'): f = f.strip() fl = open(f).readlines() found = False for i in xrange(len(fl)): p = '#include "llvm/' if not fl[i].startswith(p): continue if fl[i][len(p):] > 'Config': fl.insert(i, '#include "llvm/Config/llvm-config.h"\n') found = True break if not found: print 'not found', f else: open(f, 'w').write(''.join(fl)) and then looked through everything with `svn diff | diffstat -l | xargs -n 1000 gvim -p` and tried to fix include ordering and whatnot. No intended behavior change. llvm-svn: 331184
* Modify ModRefInfo values using static inline method abstractions [NFC].Alina Sbirlea2017-12-051-8/+7
| | | | | | | | | | | | | | | | | Summary: The aim is to make ModRefInfo checks and changes more intuitive and less error prone using inline methods that abstract the bit operations. Ideally ModRefInfo would become an enum class, but that change will require a wider set of changes into FunctionModRefBehavior. Reviewers: sanjoy, george.burgess.iv, dberlin, hfinkel Subscribers: nlopes, llvm-commits Differential Revision: https://reviews.llvm.org/D40749 llvm-svn: 319821
* Add an @llvm.sideeffect intrinsicDan Gohman2017-11-081-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch implements Chandler's idea [0] for supporting languages that require support for infinite loops with side effects, such as Rust, providing part of a solution to bug 965 [1]. Specifically, it adds an `llvm.sideeffect()` intrinsic, which has no actual effect, but which appears to optimization passes to have obscure side effects, such that they don't optimize away loops containing it. It also teaches several optimization passes to ignore this intrinsic, so that it doesn't significantly impact optimization in most cases. As discussed on llvm-dev [2], this patch is the first of two major parts. The second part, to change LLVM's semantics to have defined behavior on infinite loops by default, with a function attribute for opting into potential-undefined-behavior, will be implemented and posted for review in a separate patch. [0] http://lists.llvm.org/pipermail/llvm-dev/2015-July/088103.html [1] https://bugs.llvm.org/show_bug.cgi?id=965 [2] http://lists.llvm.org/pipermail/llvm-dev/2017-October/118632.html Differential Revision: https://reviews.llvm.org/D38336 llvm-svn: 317729
* Reverting r315590; it did not include changes for llvm-tblgen, which is ↵Aaron Ballman2017-10-151-1/+1
| | | | | | | | causing link errors for several people. Error LNK2019 unresolved external symbol "public: void __cdecl `anonymous namespace'::MatchableInfo::dump(void)const " (?dump@MatchableInfo@?A0xf4f1c304@@QEBAXXZ) referenced in function "public: void __cdecl `anonymous namespace'::AsmMatcherEmitter::run(class llvm::raw_ostream &)" (?run@AsmMatcherEmitter@?A0xf4f1c304@@QEAAXAEAVraw_ostream@llvm@@@Z) llvm-tblgen D:\llvm\2017\utils\TableGen\AsmMatcherEmitter.obj 1 llvm-svn: 315854
* [dump] Remove NDEBUG from test to enable dump methods [NFC]Don Hinton2017-10-121-1/+1
| | | | | | | | | | | | | | | Summary: Add LLVM_FORCE_ENABLE_DUMP cmake option, and use it along with LLVM_ENABLE_ASSERTIONS to set LLVM_ENABLE_DUMP. Remove NDEBUG and only use LLVM_ENABLE_DUMP to enable dump methods. Move definition of LLVM_ENABLE_DUMP from config.h to llvm-config.h so it'll be picked up by public headers. Differential Revision: https://reviews.llvm.org/D38406 llvm-svn: 315590
* [Analysis] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko2017-07-241-6/+20
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 308936
* [AST] Fix a bug in aliasesUnknownInst. Make sure we are comparing the ↵Xin Tong2017-06-251-2/+2
| | | | | | | | | | | | | | | | unknown instructions in the alias set and the instruction interested in. Summary: Make sure we are comparing the unknown instructions in the alias set and the instruction interested in. I believe this is clearly a bug (missed opportunity). I can also add some test cases if desired. Reviewers: hfinkel, davide, dberlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34597 llvm-svn: 306241
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* Use a WeakVH for UnknownInstructions in AliasSetTrackerSanjoy Das2017-03-111-22/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This change solves the same problem as D30726, except that this only throws out the bathwater. AST was not correctly tracking and deleting UnknownInstructions via handles. The existing code only tracks "pointers" in its `ASTCallbackVH`, so an UnknownInstruction (that isn't also def'ing a pointer used by another memory instruction) never gets a `ASTCallbackVH`. There are two other ways to solve this problem: - Use the `PointerRec` scheme for both known and unknown instructions. - Use a `CallbackVH` that erases the offending Instruction from the UnknownInstruction list. Both of the above changes seemed to be significantly (and unnecessarily IMO) more complex than this. Reviewers: chandlerc, dberlin, hfinkel, reames Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D30849 llvm-svn: 297539
* [AliasSetTracker] Make AST smarter about assume intrinsics that don't ↵Chad Rosier2016-11-071-0/+12
| | | | | | | | actually affect memory. Differential Revision: https://reviews.llvm.org/D26252 llvm-svn: 286108
* Revert "[AliasSetTracker] Make AST smarter about intrinsics that don't ↵Chad Rosier2016-10-261-15/+0
| | | | | | | | | | | actually affect memory." This reverts commit r285191. LICM appears to rely on the Alias Set Tracker hitting lifetime markers to prevent code from being moved outside of the original scope. llvm-svn: 285227
* [AliasSetTracker] Make AST smarter about intrinsics that don't actually ↵Chad Rosier2016-10-261-0/+15
| | | | | | | | affect memory. Differential Revision: https://reviews.llvm.org/D25969 llvm-svn: 285191
* [AliasSetTracker] Add support for memcpy and memmove.Chad Rosier2016-10-191-1/+23
| | | | | | Differential Revision: https://reviews.llvm.org/D25776 llvm-svn: 284630
* [AliasSetTracker] Return void for add() functions. NFC.Chad Rosier2016-10-191-42/+24
| | | | | | Differential Revision: https://reviews.llvm.org/D25748 llvm-svn: 284628
* [AliasSetTracker] Degrade AliasSetTracker when may-alias sets get too large.Michael Kuperstein2016-08-191-9/+116
| | | | | | | | | | | | | | | | | | Repeated inserts into AliasSetTracker have quadratic behavior - inserting a pointer into AST is linear, since it requires walking over all "may" alias sets and running an alias check vs. every pointer in the set. We can avoid this by tracking the total number of pointers in "may" sets, and when that number exceeds a threshold, declare the tracker "saturated". This lumps all pointers into a single "may" set that aliases every other pointer. (This is a stop-gap solution until we migrate to MemorySSA) This fixes PR28832. Differential Revision: https://reviews.llvm.org/D23432 llvm-svn: 279274
* Add comment /NFCXinliang David Li2016-08-111-1/+2
| | | | llvm-svn: 278438
OpenPOWER on IntegriCloud