summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-10/+11
| | | | llvm-svn: 207196
* Remove more default address space argument usage.Matt Arsenault2014-04-231-2/+3
| | | | | | These places are inconsequential in practice. llvm-svn: 207021
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | | | | | | definition below all of the header #include lines, lib/Transforms/... edition. This one is tricky for two reasons. We again have a couple of passes that define something else before the includes as well. I've sunk their name macros with the DEBUG_TYPE. Also, InstCombine contains headers that need DEBUG_TYPE, so now those headers #define and #undef DEBUG_TYPE around their code, leaving them well formed modular headers. Fixing these headers was a large motivation for all of these changes, as "leaky" macros of this form are hard on the modules implementation. llvm-svn: 206844
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-17/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] llvm-svn: 203364
* [Layering] Move DebugInfo.h into the IR library where its implementationChandler Carruth2014-03-061-1/+1
| | | | | | already lives. llvm-svn: 203046
* [Layering] Move DIBuilder.h into the IR library where its implementationChandler Carruth2014-03-061-1/+1
| | | | | | already lives. llvm-svn: 203038
* [Modules] Move CFG.h to the IR library as it defines graph traits overChandler Carruth2014-03-041-1/+1
| | | | | | IR types. llvm-svn: 202827
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-1/+1
| | | | | | Remove the old functions. llvm-svn: 202636
* [cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth2014-01-131-1/+1
| | | | | | | | | | | | | | | | | | directory. These passes are already defined in the IR library, and it doesn't make any sense to have the headers in Analysis. Long term, I think there is going to be a much better way to divide these matters. The dominators code should be fully separated into the abstract graph algorithm and have that put in Support where it becomes obvious that evn Clang's CFGBlock's can use it. Then the verifier can manually construct dominance information from the Support-driven interface while the Analysis library can provide a pass which both caches, reconstructs, and supports a nice update API. But those are very long term, and so I don't want to leave the really confusing structure until that day arrives. llvm-svn: 199082
* Correct word hyphenationsAlp Toker2013-12-051-2/+2
| | | | | | | This patch tries to avoid unrelated changes other than fixing a few hyphen-related ambiguities and contractions in nearby lines. llvm-svn: 196471
* Add a function object to compare the first or second component of a std::pair.Benjamin Kramer2013-08-241-26/+5
| | | | | | Replace instances of this scattered around the code base. llvm-svn: 189169
* Fix a really terrifying but improbable bug in mem2reg. If you have seenChandler Carruth2013-08-141-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | extremely subtle miscompilations (such as a load getting replaced with the value stored *below* the load within a basic block) related to promoting an alloca to an SSA value, there is the dim possibility that you hit this. Please let me know if you won this unfortunate lottery. The first half of mem2reg's core logic (as it is used both in the standalone mem2reg pass and in SROA) builds up a mapping from 'Instruction *' to the index of that instruction within its basic block. This allows quickly establishing which store dominate a particular load even for large basic blocks. We cache this information throughout the run of mem2reg over a function in order to amortize the cost of computing it. This is not in and of itself a strange pattern in LLVM. However, it introduces a very important constraint: absolutely no instruction can be deleted from the program without updating the mapping. Otherwise a newly allocated instruction might get the same pointer address, and then end up with a wrong index. Yes, LLVM routinely suffers from a *single threaded* variant of the ABA problem. Most places in LLVM don't find avoiding this an imposition because they don't both delete and create new instructions iteratively, but mem2reg *loves* to do this... All the time. Fortunately, the mem2reg code was really careful about updating this cache to handle this eventuallity... except when it comes to the debug declare intrinsic. Oops. The fix is to invalidate that pointer in the cache when we delete it, the same as we do when deleting alloca instructions and other instructions. I've also caused the same bug in new code while working on a fix to PR16867, so this seems to be a really unfortunate pattern. Hopefully in subsequent patches the deletion of dead instructions can be consolidated sufficiently to make it less likely that we'll see future occurences of this bug. Sorry for not having a test case, but I have literally no idea how to reliably trigger this kind of thing. It may be single-threaded, but it remains an ABA problem. It would require a really amazing number of stars to align. llvm-svn: 188367
* Revert r187191, which broke opt -mem2reg on the testcases included in PR16867.Nick Lewycky2013-08-131-164/+98
| | | | | | | | | | | | However, opt -O2 doesn't run mem2reg directly so nobody noticed until r188146 when SROA started sending more things directly down the PromoteMemToReg path. In order to revert r187191, I also revert dependent revisions r187296, r187322 and r188146. Fixes PR16867. Does not add the testcases from that PR, but both of them should get added for both mem2reg and sroa when this revert gets unreverted. llvm-svn: 188327
* Thread DataLayout through the callers and into mem2reg. This will beChandler Carruth2013-07-281-8/+13
| | | | | | | useful in a subsequent patch, but causes an unfortunate amount of noise, so I pulled it out into a separate patch. llvm-svn: 187322
* Merge the removal of dead instructions and lifetime markers with theChandler Carruth2013-07-271-41/+32
| | | | | | | | | | | analysis of the alloca. We don't need to visit all the users twice for this. We build up a kill list during the analysis and then just process it afterward. This recovers the tiny bit of performance lost by moving to the visitor based analysis system as it removes one entire use-list walk from mem2reg. In some cases, this is now faster than mem2reg was previously. llvm-svn: 187296
* Re-implement the analysis of uses in mem2reg to be significantly moreChandler Carruth2013-07-261-87/+157
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | robust. It now uses an InstVisitor and worklist to actually walk the uses of the Alloca transitively and detect the pattern which we can directly promote: loads & stores of the whole alloca and instructions we can completely ignore. Also, with this new implementation teach both the predicate for testing whether we can promote and the promotion engine itself to use the same code so we no longer have strange divergence between the two code paths. I've added some silly test cases to demonstrate that we can handle slightly more degenerate code patterns now. See the below for why this is even interesting. Performance impact: roughly 1% regression in the performance of SROA or ScalarRepl on a large C++-ish test case where most of the allocas are basically ready for promotion. The reason is because of silly redundant work that I've left FIXMEs for and which I'll address in the next commit. I wanted to separate this commit as it changes the behavior. Once the redundant work in removing the dead uses of the alloca is fixed, this code appears to be faster than the old version. =] So why is this useful? Because the previous requirement for promotion required a *specific* visit pattern of the uses of the alloca to verify: we *had* to look for no more than 1 intervening use. The end goal is to have SROA automatically detect when an alloca is already promotable and directly hand it to the mem2reg machinery rather than trying to partition and rewrite it. This is a 25% or more performance improvement for SROA, and a significant chunk of the delta between it and ScalarRepl. To get there, we need to make mem2reg actually capable of promoting allocas which *look* promotable to SROA without have SROA do tons of work to massage the code into just the right form. This is actually the tip of the iceberg. There are tremendous potential savings we can realize here by de-duplicating work between mem2reg and SROA. llvm-svn: 187191
* mem2reg: Minor STL usage cleanup. No functionality change.Benjamin Kramer2013-07-211-11/+8
| | | | llvm-svn: 186790
* Make the mem2reg interface use an ArrayRef as it keeps a copy of theseChandler Carruth2013-07-211-5/+6
| | | | | | to iterate over. llvm-svn: 186788
* Hoist the rest of the logic for promoting single-store allocas into theChandler Carruth2013-07-211-23/+31
| | | | | | | | | | | | helper function. This leaves both trivial cases handled entirely in helper functions and merely manages the list of allocas to process in the run method. The next step will be to handle all of the trivial promotion work prior to even creating the core class and the subsequent simplifications that enables. llvm-svn: 186784
* Hoist the rest of the logic for fully promoting allocas with all uses inChandler Carruth2013-07-211-55/+33
| | | | | | | | | | | | | | a single block into the helper routine. This takes advantage of the fact that we can directly replace uses prior to any store with undef to simplify matters and unconditionally promote allocas only used within one block. I've removed the special handling for the case of no stores existing. This has no semantic effect but might slow things down. I'll fix that in a later patch when I refactor this entire thing to be easier to manage the different cases. llvm-svn: 186783
* Remove a method made dead by the prior refactoring.Chandler Carruth2013-07-211-5/+0
| | | | llvm-svn: 186782
* Hoist the two trivial promotion routines out of the big class thatChandler Carruth2013-07-201-161/+158
| | | | | | | | | | | | | | | handles the general cases. The hope is to refactor this so that we don't end up building the entire class for the trivial cases. I also want to lift a lot of the early pre-processing in the initial segment of run() into a separate routine, and really none of it needs to happen inside the primary promotion class. These routines in particular used none of the actual state in the promotion class, so they don't really make sense as members. llvm-svn: 186781
* Hoist the AllocaInfo struct to the top of the file.Chandler Carruth2013-07-201-59/+57
| | | | | | | | This struct is nicely independent of everything else, and we already needed a foward declaration here. It's simpler to just define it immediately. llvm-svn: 186780
* Sink a typedef and comparator down to the function that actually uses them.Chandler Carruth2013-07-201-8/+10
| | | | llvm-svn: 186779
* Don't allocate the DIBuilder on the heap and remove all the complexityChandler Carruth2013-07-201-16/+8
| | | | | | that ensued from that. llvm-svn: 186777
* Rename constructor parameters to follow the common member-shadowingChandler Carruth2013-07-201-3/+3
| | | | | | pattern and conform to the naming conventions. llvm-svn: 186776
* Reformat the implementation of mem2reg with clang-format so that myChandler Carruth2013-07-201-344/+360
| | | | | | subsequent changes don't introduce inconsistencies. llvm-svn: 186775
* Remove a DenseMapInfo specialization for std::pair -- we have one ofChandler Carruth2013-07-201-20/+0
| | | | | | those baked into DenseMap now. llvm-svn: 186773
* Update mem2reg's comments to conform to the new doxygen standards. NoChandler Carruth2013-07-201-74/+58
| | | | | | functionality changed. llvm-svn: 186772
* Use SmallVectorImpl::iterator/const_iterator instead of SmallVector to avoid ↵Craig Topper2013-07-041-1/+1
| | | | | | specifying the vector size. llvm-svn: 185606
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-6/+6
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-12/+12
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Fix typo.Julien Lerouge2012-10-231-1/+1
| | | | llvm-svn: 166456
* Explain why DenseMap is still used here instead of MapVector.Julien Lerouge2012-10-231-1/+9
| | | | llvm-svn: 166454
* Iterating over a DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*> is notJulien Lerouge2012-10-221-4/+4
| | | | | | | | | deterministic, replace it with a DenseMap<std::pair<unsigned, unsigned>, PHINode*> (we already have a map from BasicBlock to unsigned). <rdar://problem/12541389> llvm-svn: 166435
* The DIBuilder class is just a wrapper around debug info creationBill Wendling2012-06-291-1/+1
| | | | | | | (a.k.a. MDNodes). The module doesn't belong in Analysis. Move it to the VMCore instead. llvm-svn: 159414
* Move lib/Analysis/DebugInfo.cpp to lib/VMCore/DebugInfo.cpp andBill Wendling2012-06-281-1/+1
| | | | | | | | | include/llvm/Analysis/DebugInfo.h to include/llvm/DebugInfo.h. The reasoning is because the DebugInfo module is simply an interface to the debug info MDNodes and has nothing to do with analysis. llvm-svn: 159312
* Switch mem2reg to use the new hashing infrastructure.Chandler Carruth2012-03-051-1/+3
| | | | llvm-svn: 152026
* Fix 80-column violation.Chad Rosier2012-02-201-1/+2
| | | | llvm-svn: 150998
* Propagate TargetLibraryInfo throughout ConstantFolding.cpp and Chad Rosier2011-12-011-1/+1
| | | | | | | InstructionSimplify.cpp. Other fixups as needed. Part of rdar://10500969 llvm-svn: 145559
* Add comments and test for atomic load/store and mem2reg.Eli Friedman2011-08-151-0/+4
| | | | llvm-svn: 137690
* Move onlyUsedByLifetimeMarkers to ValueTracking so that it can be used by otherNick Lewycky2011-06-271-16/+1
| | | | | | passes as well. llvm-svn: 133904
* When promoting an alloca to registers discard any lifetime intrinsics.Nick Lewycky2011-06-171-0/+59
| | | | llvm-svn: 133251
* Make LoadAndStorePromoter preserve debug info and create llvm.dbg.values whenCameron Zwarich2011-05-241-12/+0
| | | | | | promoting allocas to SSA variables. Fixes <rdar://problem/9479036>. llvm-svn: 131953
* Remove unused STL header includes.Jay Foad2011-04-231-1/+0
| | | | llvm-svn: 130068
* PR9214: Convert Metadata API to use ArrayRef.Jay Foad2011-04-211-1/+1
| | | | llvm-svn: 129932
* Remove PHINode::reserveOperandSpace(). Instead, add a parameter toJay Foad2011-03-301-2/+1
| | | | | | PHINode::Create() giving the (known or expected) number of operands. llvm-svn: 128537
* Refactor into a separate utility function.Devang Patel2011-03-171-29/+14
| | | | llvm-svn: 127832
* Do not use DIFactory. Use DIBuilder.Devang Patel2011-02-241-6/+7
| | | | llvm-svn: 126398
* Convert two std::vectors to SmallVectors for a 3.4% speedup running -scalarreplCameron Zwarich2011-01-231-2/+2
| | | | | | on test-suite + SPEC2000 & SPEC2006. llvm-svn: 124068
OpenPOWER on IntegriCloud