summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/MemorySSAUpdater.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [NFC] fix trivial typos in commentsHiroshi Inoue2019-02-051-2/+2
| | | | llvm-svn: 353147
* [MemorySSA] Extend removeMemoryAccess API to optimize MemoryPhis.Alina Sbirlea2019-01-311-1/+21
| | | | | | | | | | | | | | | | Summary: EarlyCSE needs to optimize MemoryPhis after an access is removed and has special handling for it. This should be handled by MemorySSA instead. The default remains that MemoryPhis are *not* optimized after an access is removed. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, llvm-commits, Prazek Differential Revision: https://reviews.llvm.org/D57199 llvm-svn: 352787
* 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
* [IR] Add hasNPredecessors, hasNPredecessorsOrMore to BasicBlockVedant Kumar2018-11-191-1/+1
| | | | | | | | | | | | | | | | | | | | | | | Add methods to BasicBlock which make it easier to efficiently check whether a block has N (or more) predecessors. This can be more efficient than using pred_size(), which is a linear time operation. We might consider adding similar methods for successors. I haven't done so in this patch because succ_size() is already O(1). With this patch applied, I measured a 0.065% compile-time reduction in user time for running `opt -O3` on the sqlite3 amalgamation (30 trials). The change in mergeStoreIntoSuccessor alone saves 45 million linked list iterations in a stage2 Release build of llc. See llvm.org/PR39702 for a harder but more general way of achieving similar results. Differential Revision: https://reviews.llvm.org/D54686 llvm-svn: 347256
* Use llvm::copy. NFCFangrui Song2018-11-171-1/+1
| | | | llvm-svn: 347126
* [TI removal] Make variables declared as `TerminatorInst` and initializedChandler Carruth2018-10-151-1/+1
| | | | | | | | | | | | | by `getTerminator()` calls instead be declared as `Instruction`. This is the biggest remaining chunk of the usage of `getTerminator()` that insists on the narrow type and so is an easy batch of updates. Several files saw more extensive updates where this would cascade to requiring API updates within the file to use `Instruction` instead of `TerminatorInst`. All of these were trivial in nature (pervasively using `Instruction` instead just worked). llvm-svn: 344502
* [MemorySSAUpdater] Avoid creating self-referencing MemoryDefsAlexandros Lamprineas2018-09-111-4/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Fix for https://bugs.llvm.org/show_bug.cgi?id=38807, which occurred while compiling SemaTemplateInstantiate.cpp with clang and GVNHoist enabled. In the following example: 1=def(entry) / \ 2=def(1) 4=def(1) 3=def(2) 5=def(4) When removing the MemoryDef 2=def(1) from its basic block, and just before adding it to the end of the parent basic block, we first replace all its uses with the defining memory access: 3=def(2) -> 3=def(1) Then we call insertDef for adding 2=def(1) to the parent basic block, where we replace the uses of 1=def(entry) with 2=def(1). Doing so we create a self reference: 2=def(1) -> 2=def(2) (bad) 3=def(1) -> 3=def(2) (ok) 4=def(1) -> 4=def(2) (ok) Differential Revision: https://reviews.llvm.org/D51801 llvm-svn: 341947
* API to update MemorySSA for cloned blocks and added CFG edges.Alina Sbirlea2018-09-101-0/+518
| | | | | | | | | | | | | | | | Summary: End goal is to update MemorySSA in all loop passes. LoopUnswitch clones all blocks in a loop. SimpleLoopUnswitch clones some blocks. LoopRotate clones some instructions. Some of these loop passes also make CFG changes. This is an API based on what I found needed in LoopUnswitch, SimpleLoopUnswitch, LoopRotate, LoopInstSimplify, LoopSimplifyCFG. Adding dependent patches using this API for context. Reviewers: george.burgess.iv, dberlin Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D45299 llvm-svn: 341855
* [MemorySSA] Update MemoryPhi wiring for block splitting to consider if ↵Alina Sbirlea2018-09-071-1/+10
| | | | | | | | | | | | | | | | | identical edges were merged. Summary: Block splitting is done with either identical edges being merged, or not. Only critical edges can be split without merging identical edges based on an option. Teach the memoryssa updater to take this into account: for the same edge between two blocks only move one entry from the Phi in Old to the new Phi in New. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D51563 llvm-svn: 341709
* [IR] Begin removal of TerminatorInst by removing successor manipulation.Chandler Carruth2018-08-261-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The core get and set routines move to the `Instruction` class. These routines are only valid to call on instructions which are terminators. The iterator and *generic* range based access move to `CFG.h` where all the other generic successor and predecessor access lives. While moving the iterator here, simplify it using the iterator utilities LLVM provides and updates coding style as much as reasonable. The APIs remain pointer-heavy when they could better use references, and retain the odd behavior of `operator*` and `operator->` that is common in LLVM iterators. Adjusting this API, if desired, should be a follow-up step. Non-generic range iteration is added for the two instructions where there is an especially easy mechanism and where there was code attempting to use the range accessor from a specific subclass: `indirectbr` and `br`. In both cases, the successors are contiguous operands and can be easily iterated via the operand list. This is the first major patch in removing the `TerminatorInst` type from the IR's instruction type hierarchy. This change was discussed in an RFC here and was pretty clearly positive: http://lists.llvm.org/pipermail/llvm-dev/2018-May/123407.html There will be a series of much more mechanical changes following this one to complete this move. Differential Revision: https://reviews.llvm.org/D47467 llvm-svn: 340698
* [MemorySSAUpdater] Update Phi operands after trivial Phi eliminationAlexandros Lamprineas2018-07-231-15/+13
| | | | | | | | | | | | Bug fix for PR37445. The underlying problem and its fix are similar to PR37808. The bug lies in MemorySSAUpdater::getPreviousDefRecursive(), where PhiOps is computed before the call to tryRemoveTrivialPhi() and it ends up being out of date, pointing to stale data. We have now turned each of the PhiOps into a TrackingVH<MemoryAccess>. Differential Revision: https://reviews.llvm.org/D49425 llvm-svn: 337680
* [MemorySSA] Add API to update MemoryPhis, following CFG changes.Alina Sbirlea2018-07-201-0/+29
| | | | | | | | | | | | | | | | Summary: When splitting predecessors in BasicBlockUtils, we create a new block as an immediate predecessor of the original BB, then we connect a given set of predecessors to the new block. The API in this patch will be used to update MemoryPhis for this CFG change. If all predecessors are being moved, we move the MemoryPhi directly. Otherwise we create a new MemoryPhi in the NewBB and populate its incoming values, while deleting them from BB's Phi. [Split from D45299 for easier review] Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D49156 llvm-svn: 337581
* [MemorySSAUpdater] Remove deleted trivial Phis from active worksetAlexandros Lamprineas2018-07-161-7/+12
| | | | | | | | | | | | | Bug fix for PR37808. The regression test is a reduced version of the original reproducer attached to the bug report. As stated in the report, the problem was that InsertedPHIs was keeping dangling pointers to deleted Memory-Phis. MemoryPhis are created eagerly and sometimes get zapped shortly afterwards. I've used WeakVH instead of an expensive removal operation from the active workset. Differential Revision: https://reviews.llvm.org/D48372 llvm-svn: 337149
* Remove redundant *_or_null checks; NFCGeorge Burgess IV2018-07-121-2/+2
| | | | | | | For the first one, we dereference `NewDef` right before the `if` anyway. For the second, we shouldn't have NULL users(). llvm-svn: 336952
* [MemorySSA] Add APIs to move memory accesses between blocks, following CFG ↵Alina Sbirlea2018-07-111-0/+50
| | | | | | | | | | | | | | | | changes. Summary: The move APIs added in this patch will be used to update MemorySSA when CFG changes merge or split blocks, by moving memory accesses accordingly in MemorySSA's internal data structures. [Split from D45299 for easier review] Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D48897 llvm-svn: 336860
* [MemorySSA] Add APIs to MemoryPhis to delete incoming blocks/values, and an ↵Alina Sbirlea2018-06-291-0/+33
| | | | | | | | | | | | | | | | updater API to remove blocks. Summary: MemoryPhis now have APIs analogous to BB Phis to remove an incoming value/block. The MemorySSAUpdater uses the above APIs when updating MemorySSA given a set of dead blocks about to be deleted. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D48396 llvm-svn: 336015
* [MemorySSA] Reflow comments + clean up control flow; NFCGeorge Burgess IV2018-05-261-3/+9
| | | | | | | Style guide says `else`s after returns are iffy, and I agree. I also don't know what broke the comments here and in CFLAA, but *shrug*. llvm-svn: 333332
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-1/+1
| | | | | | | | | | | | | | | | We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
* [MemorySSAUpdater] Mark Phi users of a node being moved as non-optimizeZhaoshi Zheng2018-04-091-0/+17
| | | | | | | | | | Fix PR36484, as suggested: <quote> during moves, mark the direct users of the erased things that were phis as "not to be optimized" <quote> llvm-svn: 329621
* [MemorySSA] Fix exponential compile-time updating MemorySSA.Eli Friedman2018-03-261-15/+28
| | | | | | | | | | | | | | | | | | | | | | | MemorySSAUpdater::getPreviousDefRecursive is a recursive algorithm, for each block, it computes the previous definition for each predecessor, then takes those definitions and combines them. But currently it doesn't remember results which it already computed; this means it can visit the same block multiple times, which adds up to exponential time overall. To fix this, this patch adds a cache. If we computed the result for a block already, we don't need to visit it again because we'll come up with the same result. Well, unless we RAUW a MemoryPHI; in that case, the TrackingVH will be updated automatically. This matches the original source paper for this algorithm. The testcase isn't really a test for the bug, but it adds coverage for the case where tryRemoveTrivialPhi erases an existing PHI node. (It's hard to write a good regression test for a performance issue.) Differential Revision: https://reviews.llvm.org/D44715 llvm-svn: 328577
* Remove redundant includes from lib/Analysis.Michael Zolotukhin2017-12-131-2/+0
| | | | llvm-svn: 320617
* MemorySSAUpdater: Only add phis to insertedphis if we actually inserted ↵Daniel Berlin2017-09-271-3/+2
| | | | | | them, not if we just found existing ones llvm-svn: 314273
* [mssa] Fix case when there is no definition in a block prior to an inserted use.Alina Sbirlea2017-06-071-11/+6
| | | | | | | | | | | | | | | Summary: Check that the first access before one being tested is valid. Before this patch, if there was no definition prior to the Use being tested, the first time Iter was deferenced, it hit the sentinel. Reviewers: dberlin, gbiv Subscribers: sanjoy, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D33950 llvm-svn: 304926
* 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
* [MSSA] Clean up the updater a bit. NFCGeorge Burgess IV2017-04-211-5/+4
| | | | | | | | - Mark an internal function static - Remove the llvm namespace (just holding on to the `using namespace llvm;` Works on My Machine(TM)) llvm-svn: 300947
* MemorySSA: Move to Analysis, from Transforms/Utils. It's used asDaniel Berlin2017-04-111-0/+494
Analysis, it has Analysis passes, and once NewGVN is made an Analysis, this removes the cross dependency from Analysis to Transform/Utils. NFC. llvm-svn: 299980
OpenPOWER on IntegriCloud