aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
Commit message (Collapse)AuthorAgeFilesLines
* This changes the PromoteMemToReg function to create "pruned" SSA form, notChris Lattner2003-10-051-24/+109
| | | | | | | | | | | | | | | | | | | | | "minimal" SSA form (in other words, it doesn't insert dead PHIs). This speeds up the mem2reg pass very significantly because it doesn't have to do a lot of frivolous work in many common cases. In the 252.eon function I have been playing with, this doesn't even insert the 120 PHI nodes that it used to which were trivially dead (in the process of promoting 356 alloca instructions overall). This speeds up the mem2reg pass from 1.2459s to 0.1284s. More significantly, the DCE pass used to take 2.4138s to remove the 120 dead PHI nodes that mem2reg constructed, now it takes 0.0134s (which is the time to scan the function and decide that there is nothing dead). So overall, on this one function, we speed things up a total of 3.5179s, which is a 24.8x speedup! :) This change is tested by the Mem2Reg/2003-10-05-DeadPHIInsertion.ll test, which now passes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8884 91177308-0d34-0410-b5e6-96231b3b80d8
* Change the interface to PromoteMemToReg to also take a DominatorTreeChris Lattner2003-10-051-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8883 91177308-0d34-0410-b5e6-96231b3b80d8
* Speed up the mem2reg transform for allocas which are only read/written in a ↵Chris Lattner2003-10-051-5/+84
| | | | | | | | | | | | | | | | | | | | | | | | single basic block. This is amazingly common in code generated by the C/C++ front-ends. This change makes it not have to insert ANY phi nodes, whereas before it would insert a ton of dead ones which DCE would have to clean up. Thus, this fix improves compile-time performance of these trivial allocas in two ways: 1. It doesn't have to do the walking and book-keeping for renaming 2. It does not insert dead phi nodes for them which would have to subsequently be cleaned up. On my favorite testcase from 252.eon, this special case handles 305 out of 356 promoted allocas in the function. It speeds up the mem2reg pass from 7.5256s to 1.2505s. It inserts 677 fewer dead PHI nodes, which speeds up a subsequent -dce pass from 18.7524s to 2.4806s. There are still 120 trivially dead PHI nodes being inserted for variables used in multiple basic blocks, but they are not handled by this patch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8881 91177308-0d34-0410-b5e6-96231b3b80d8
* The first PHI node may be null, scan for the first non-null oneChris Lattner2003-10-051-1/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8865 91177308-0d34-0410-b5e6-96231b3b80d8
* The VersionNumbers vector is only used during PHI placement. Turn it into ↵Chris Lattner2003-10-051-10/+6
| | | | | | an argument, allowing us to get rid of the vector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8864 91177308-0d34-0410-b5e6-96231b3b80d8
* * Update file header commentChris Lattner2003-10-051-44/+64
| | | | | | | | | | | | | | *** Revamp the code which handled unreachable code in the function. Now the code is much more efficient for high-degree basic blocks, such as those that occur in the 252.eon SPEC benchmark. For the interested, the time to promote a SINGLE alloca in _ZN7mrScene4ReadERSi function used to be > 3.5s. Now it is < .075s. The function has a LOT of allocas in it, so it appeared to be infinite looping, this should make it much nicer. :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8863 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify the loop a bitChris Lattner2003-10-051-10/+9
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8862 91177308-0d34-0410-b5e6-96231b3b80d8
* There is no need for separate WriteSets and PhiNodeBlocks lists. It is just aChris Lattner2003-10-051-18/+8
| | | | | | | | work-list of value definitions. This allows elimination of the explicit 'iterative' step of the algorithm, and also reuses temporary memory better. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8861 91177308-0d34-0410-b5e6-96231b3b80d8
* The PhiNodes 2D vector is only used during PHI node placement. It doesn'tChris Lattner2003-10-051-11/+10
| | | | | | | need to be an instance variable! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8860 91177308-0d34-0410-b5e6-96231b3b80d8
* * Document instance vars betterChris Lattner2003-10-051-20/+26
| | | | | | | | * Fuse two parallel loops * Use a more specific type for AllocaLookup git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8859 91177308-0d34-0410-b5e6-96231b3b80d8
* Two small cleanups/speedups:Chris Lattner2003-10-051-29/+31
| | | | | | | | * Do not insert a new entry into NewPhiNodes during the rename pass if there are no PHIs in a block. * Do not compute WriteSets in parallel git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8858 91177308-0d34-0410-b5e6-96231b3b80d8
* * Minor cleanupsChris Lattner2003-10-051-42/+28
| | | | | | | | | * Eliminate the KillList instance variable, instead, just delete loads and stores as they are "renamed", and delete allocas when they are done * Make the 'visited' set an instance variable to avoid passing it on the stack. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8857 91177308-0d34-0410-b5e6-96231b3b80d8
* Spell `necessary' correctly.Misha Brukman2003-08-181-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7944 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix bug: mem2reg/2003-04-24-MultipleIdenticalSuccessors.llChris Lattner2003-04-251-7/+8
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5919 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix iterator invalidation problemChris Lattner2003-04-241-2/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5895 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix bug where use still existed in dead codeChris Lattner2003-04-211-0/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5824 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix bug: Mem2reg/2003-04-18-DeadBlockProblem.llChris Lattner2003-04-181-4/+17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5810 91177308-0d34-0410-b5e6-96231b3b80d8
* * Fix bug: Mem2Reg/2003-04-10-DFNotFound.llChris Lattner2003-04-101-9/+26
| | | | | | | | * Make Mem2Reg assign version numbers now for renamed variables instead of .mem2reg suffixes. This produces what people think of as SSA. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5771 91177308-0d34-0410-b5e6-96231b3b80d8
* Change the mem2reg interface to accept a TargetData argumentChris Lattner2003-03-031-6/+11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5685 91177308-0d34-0410-b5e6-96231b3b80d8
* Split mem2reg promotion into two parts: a function which does the work, andChris Lattner2003-02-221-85/+53
| | | | | | | a pass which wraps the function. This allows other passes to use the functionality git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5610 91177308-0d34-0410-b5e6-96231b3b80d8
* Clean up std namespace referencesChris Lattner2003-02-221-32/+29
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5608 91177308-0d34-0410-b5e6-96231b3b80d8
* - Rename AnalysisUsage::preservesAll to getPreservesAll & preservesCFG toChris Lattner2002-10-211-1/+1
| | | | | | | setPreservesCFG to be less confusing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4255 91177308-0d34-0410-b5e6-96231b3b80d8
* Updates to work with recent Statistic's changes:Chris Lattner2002-10-011-4/+3
| | | | | | | | | | | | | * Renamed StatisticReporter.h/cpp to Statistic.h/cpp * Broke constructor to take two const char * arguments instead of one, so that indendation can be taken care of automatically. * Sort the list by pass name when printing * Make sure to print all statistics as a group, instead of randomly when the statistics dtors are called. * Updated ProgrammersManual with new semantics. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4002 91177308-0d34-0410-b5e6-96231b3b80d8
* - Fix bug: Mem2Reg/2002-05-01-ShouldNotPromoteThisAlloca.llChris Lattner2002-09-241-2/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3917 91177308-0d34-0410-b5e6-96231b3b80d8
* Clean up code due to auto-insert constructorsChris Lattner2002-09-101-6/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3665 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminated the MemAccessInst class, folding contents into GEP class.Chris Lattner2002-08-221-17/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3487 91177308-0d34-0410-b5e6-96231b3b80d8
* - Cleaned up the interface to AnalysisUsage to take analysis class namesChris Lattner2002-08-081-1/+1
| | | | | | | | instead of ::ID's. - Pass::getAnalysis<> now no longer takes an optional argument git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3265 91177308-0d34-0410-b5e6-96231b3b80d8
* * Add support for different "PassType's"Chris Lattner2002-07-261-1/+1
| | | | | | | | | | | | | | | | * Add new RegisterOpt/RegisterAnalysis templates for registering passes that are to show up in opt or analyze * Register Analyses now * Change optimizations to use RegisterOpt instead of RegisterPass * Add support for different "PassType's" * Add new RegisterOpt/RegisterAnalysis templates for registering passes that are to show up in opt or analyze * Register Analyses now * Change optimizations to use RegisterOpt instead of RegisterPass * Remove getPassName implementations from various subclasses git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3113 91177308-0d34-0410-b5e6-96231b3b80d8
* *** empty log message ***Chris Lattner2002-07-231-2/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3016 91177308-0d34-0410-b5e6-96231b3b80d8
* MEGAPATCH checkin.Chris Lattner2002-06-251-11/+10
| | | | | | | For details, See: docs/2002-06-25-MegaPatchInfo.txt git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2779 91177308-0d34-0410-b5e6-96231b3b80d8
* Add support for printing out statistics information when -stats is added toChris Lattner2002-05-101-0/+5
| | | | | | | the command line git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2601 91177308-0d34-0410-b5e6-96231b3b80d8
* Merge all individual .h files into a single Scalar.h fileChris Lattner2002-05-071-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2537 91177308-0d34-0410-b5e6-96231b3b80d8
* Fixed bug: ↵Chris Lattner2002-05-011-0/+3
| | | | | | test/Regression/Transforms/Mem2Reg/2002-05-01-ShouldNotPromoteThisAlloca.ll git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2423 91177308-0d34-0410-b5e6-96231b3b80d8
* changes because iMemory.h no longer #includes DerivedTypes.hChris Lattner2002-04-291-2/+3
| | | | | | | This only requires Type.h anyway git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2405 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate duplicate or unneccesary #include'sChris Lattner2002-04-291-1/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2397 91177308-0d34-0410-b5e6-96231b3b80d8
* Add new optional getPassName() virtual function that a Pass can overrideChris Lattner2002-04-291-0/+2
| | | | | | | to make debugging output a lot nicer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2395 91177308-0d34-0410-b5e6-96231b3b80d8
* Tighten up the AnalysisUsage of lots of passes, primarily to correctly ↵Chris Lattner2002-04-281-0/+1
| | | | | | indicate whether or not they invalidate the CFGA git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2386 91177308-0d34-0410-b5e6-96231b3b80d8
* Split ConstantVals.h into Constant.h and Constants.hChris Lattner2002-04-281-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2378 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate the PromoteInstance class, incorporating it into the PromotePassChris Lattner2002-04-281-63/+57
| | | | | | | class. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2375 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate visited, CurrentValue, and WriteSets as instance variables ofChris Lattner2002-04-281-53/+54
| | | | | | | | | PromoteInstance. Make them local variables that are passed around as appropriate. Especially in the case of CurrentValue, this makes the code simpler. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2374 91177308-0d34-0410-b5e6-96231b3b80d8
* * Fix bug: test/Regression/Transforms/Mem2Reg/2002-03-28-UninitializedVal.llChris Lattner2002-04-281-4/+12
| | | | | | | * Minor cleanup that was missed in last patch git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2373 91177308-0d34-0410-b5e6-96231b3b80d8
* This huge changeset is a strictly cleanup changeChris Lattner2002-04-281-228/+174
| | | | | | | Bugfixes will come in the next revision so that the diff is obvious. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2372 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate the cfg namespace, moving LoopInfo, Dominators, Interval* classesChris Lattner2002-04-281-3/+0
| | | | | | | to the global namespace git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2370 91177308-0d34-0410-b5e6-96231b3b80d8
* Change the Dominator info and LoopInfo classes to keep track of ↵Chris Lattner2002-04-281-4/+4
| | | | | | | | | BasicBlock's, not const BasicBlocks git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2337 91177308-0d34-0410-b5e6-96231b3b80d8
* * Rename MethodPass class to FunctionPassChris Lattner2002-04-271-8/+6
| | | | | | | | | | | | | | | | - Rename runOnMethod to runOnFunction * Transform getAnalysisUsageInfo into getAnalysisUsage - Method is now const - It now takes one AnalysisUsage object to fill in instead of 3 vectors to fill in - Pass's now specify which other passes they _preserve_ not which ones they modify (be conservative!) - A pass can specify that it preserves all analyses (because it never modifies the underlying program) * s/Method/Function/g in other random places as well git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2333 91177308-0d34-0410-b5e6-96231b3b80d8
* Add #includes to make up for #includes pruned out of header files.Chris Lattner2002-04-091-2/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2207 91177308-0d34-0410-b5e6-96231b3b80d8
* s/Method/FunctionChris Lattner2002-04-081-1/+0
| | | | | | | Remove extraneous #includes of llvm/Assembly/Writer git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2178 91177308-0d34-0410-b5e6-96231b3b80d8
* Change references to the Method class to be references to the FunctionChris Lattner2002-04-071-19/+16
| | | | | | | | class. The Method class is obsolete (renamed) and all references to it are being converted over to Function. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2144 91177308-0d34-0410-b5e6-96231b3b80d8
* * Move classes aroundCameron Buschardt2002-03-271-29/+36
| | | | | | | | * rename constructor function * Move stuff into anonymous namespaces git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2007 91177308-0d34-0410-b5e6-96231b3b80d8
* Implemented promote mem->reg pass.Cameron Buschardt2002-03-271-64/+286
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2005 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2025-11-28 01:11:30 +0000