summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Convert a std::map to a DenseMap for another 1.7% speedup on -scalarrepl.Cameron Zwarich2011-01-181-3/+3
| | | | llvm-svn: 123732
* Make a std::vector a SmallVector<*, 32> like the other vectors in the sameCameron Zwarich2011-01-181-1/+1
| | | | | | | function. This seems to be about a 1.5% speedup of -scalarrepl on test-suite with SPEC2000 and SPEC2006. llvm-svn: 123731
* Remove outdated references to dominance frontiers.Cameron Zwarich2011-01-181-7/+7
| | | | llvm-svn: 123724
* Roll r123609 back in with two changes that fix test failures with expensiveCameron Zwarich2011-01-171-50/+119
| | | | | | | | | | | | | | checks enabled: 1) Use '<' to compare integers in a comparison function rather than '<='. 2) Use the uniqued set DefBlocks rather than Info.DefiningBlocks to initialize the priority queue. The speedup of scalarrepl on test-suite + SPEC2000 + SPEC2006 is a bit less, at just under 16% rather than 17%. llvm-svn: 123662
* Roll out r123609 due to failures on the llvm-x86_64-linux-checks bot.Cameron Zwarich2011-01-171-118/+49
| | | | llvm-svn: 123618
* Eliminate the use of dominance frontiers in PromoteMemToReg. In addition toCameron Zwarich2011-01-171-49/+118
| | | | | | | | | | | | | eliminating a potentially quadratic data structure, this also gives a 17% speedup when running -scalarrepl on test-suite + SPEC2000 + SPEC2006. My initial experiment gave a greater speedup around 25%, but I moved the dominator tree level computation from dominator tree construction to PromoteMemToReg. Since this approach to computing IDFs has a much lower overhead than the old code using precomputed DFs, it is worth looking at using this new code for the second scalarrepl pass as well. llvm-svn: 123609
* split dom frontier handling stuff out to its own DominanceFrontier header,Chris Lattner2011-01-021-1/+1
| | | | | | so that Dominators.h is *just* domtree. Also prune #includes a bit. llvm-svn: 122714
* Don't keep track of inserted phis in PromoteMemoryToRegister: the informationDuncan Sands2010-11-221-8/+3
| | | | | | is never used. Patch by Cameron Zwarich. llvm-svn: 119963
* Have a few places that want to simplify phi nodes use SimplifyInstructionDuncan Sands2010-11-161-3/+4
| | | | | | rather than calling hasConstantValue. No intended functionality change. llvm-svn: 119352
* remove some dead code.Chris Lattner2010-08-181-8/+0
| | | | llvm-svn: 111344
* Don't look up the "dbg" metadata kind by name.Dan Gohman2010-07-201-4/+5
| | | | llvm-svn: 108961
* cache result of operator*Gabor Greif2010-07-091-3/+5
| | | | llvm-svn: 107966
* Use A.append(...) instead of A.insert(A.end(), ...) when A is aDan Gohman2010-06-211-3/+2
| | | | | | SmallVector, and other SmallVector simplifications. llvm-svn: 106452
OpenPOWER on IntegriCloud