summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/LCSSA.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-131-4/+4
| | | | | | | | | | | | | | | | | | | | | | | can be used by both the new pass manager and the old. This removes it from any of the virtual mess of the pass interfaces and lets it derive cleanly from the DominatorTreeBase<> template. In turn, tons of boilerplate interface can be nuked and it turns into a very straightforward extension of the base DominatorTree interface. The old analysis pass is now a simple wrapper. The names and style of this split should match the split between CallGraph and CallGraphWrapperPass. All of the users of DominatorTree have been updated to match using many of the same tricks as with CallGraph. The goal is that the common type remains the resulting DominatorTree rather than the pass. This will make subsequent work toward the new pass manager significantly easier. Also in numerous places things became cleaner because I switched from re-running the pass (!!! mid way through some other passes run!!!) to directly recomputing the domtree. llvm-svn: 199104
* [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
* Quick look-up for block in loop.Wan Xiaofei2013-10-261-13/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch implements quick look-up for block in loop by maintaining a hash set for blocks. It improves the efficiency of loop analysis a lot, the biggest improvement could be 5-6%(458.sjeng). Below are the compilation time for our benchmark in llc before & after the patch. Benchmark llc - trunk llc - patched 401.bzip2 0.339081 100.00% 0.329657 102.86% 403.gcc 19.853966 100.00% 19.605466 101.27% 429.mcf 0.049823 100.00% 0.048451 102.83% 433.milc 0.514898 100.00% 0.510217 100.92% 444.namd 1.109328 100.00% 1.103481 100.53% 445.gobmk 4.988028 100.00% 4.929114 101.20% 456.hmmer 0.843871 100.00% 0.825865 102.18% 458.sjeng 0.754238 100.00% 0.714095 105.62% 464.h264ref 2.9668 100.00% 2.90612 102.09% 471.omnetpp 4.556533 100.00% 4.511886 100.99% bitmnp01 0.038168 100.00% 0.0357 106.91% idctrn01 0.037745 100.00% 0.037332 101.11% libquake2 3.78689 100.00% 3.76209 100.66% libquake_ 2.251525 100.00% 2.234104 100.78% linpack 0.033159 100.00% 0.032788 101.13% matrix01 0.045319 100.00% 0.043497 104.19% nbench 0.333161 100.00% 0.329799 101.02% tblook01 0.017863 100.00% 0.017666 101.12% ttsprk01 0.054337 100.00% 0.053057 102.41% Reviewer : Andrew Trick <atrick@apple.com>, Hal Finkel <hfinkel@anl.gov> Approver : Andrew Trick <atrick@apple.com> Test : Pass make check-all & llvm test-suite llvm-svn: 193460
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-3/+3
| | | | | | | | | | | | | | | | | | | | | 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-7/+7
| | | | | | | | | | | | | | | | | 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
* LCSSA: Try to recover compile time regressions due to SCEV updates.Benjamin Kramer2012-10-311-15/+9
| | | | | | | | | - Use value handle tricks to communicate use replacements instead of forgetLoop, this is a lot faster. - Move the "big hammer" out of the main loop so it's not called for every instruction. This should recover most (if not all) compile time regressions introduced by this code. llvm-svn: 167136
* LCSSA: Add a workaround for another nasty SCEV cache invalidation issue.Benjamin Kramer2012-10-311-0/+5
| | | | | | | I'm not entirely happy with this solution, but I don't see a smarter way currently. Fixes PR14214. llvm-svn: 167112
* Fix SCEV cache invalidation in LCSSA and LoopSimplify.Benjamin Kramer2012-10-261-0/+14
| | | | | | | | | | | | | | The LoopSimplify bug is pretty harmless because the loop goes from unanalyzable to analyzable but the LCSSA bug is very nasty. It only comes into play with a specific order of the LoopPassManager worklist and can cause actual miscompilations, when a SCEV refers to a value that has been replaced with PHI node. SCEVExpander may then insert code into the wrong place, either violating domination or randomly miscompiling stuff. Comes with an extensive test case reduced from the test-suite with bugpoint+SCEVValidator. llvm-svn: 166787
* There is no need to force DebugLoc on a PHI at this point.Devang Patel2011-05-161-2/+0
| | | | llvm-svn: 131427
* Set debug location for new PHI nodes created in exit block. Devang Patel2011-05-041-0/+2
| | | | llvm-svn: 130894
* Remove PHINode::reserveOperandSpace(). Instead, add a parameter toJay Foad2011-03-301-2/+3
| | | | | | PHINode::Create() giving the (known or expected) number of operands. llvm-svn: 128537
* Clean up something noticed by Fritz.Cameron Zwarich2011-03-151-1/+1
| | | | llvm-svn: 127684
* Do not add PHIs with no users when creating LCSSA form. Patch by Andrew Clinton.Cameron Zwarich2011-03-151-0/+10
| | | | llvm-svn: 127674
* split dom frontier handling stuff out to its own DominanceFrontier header,Chris Lattner2011-01-021-3/+0
| | | | | | so that Dominators.h is *just* domtree. Also prune #includes a bit. llvm-svn: 122714
* Passes do not need to recursively initialize passes that they preserve, ifOwen Anderson2010-10-191-3/+0
| | | | | | | they do not also require them. This allows us to reduce inter-pass linkage dependencies. llvm-svn: 116854
* Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson2010-10-191-1/+3
| | | | | | | | | | | | | | | | | exposes an initializeMyPassFunction(), which must be called in the pass's constructor. This function uses static dependency declarations to recursively initialize the pass's dependencies. Clients that only create passes through the createFooPass() APIs will require no changes. Clients that want to use the CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h before parsing commandline arguments. I have tested this with all standard configurations of clang and llvm-gcc on Darwin. It is possible that there are problems with the static dependencies that will only be visible with non-standard options. If you encounter any crash in pass registration/creation, please send the testcase to me directly. llvm-svn: 116820
* Begin adding static dependence information to passes, which will allow us toOwen Anderson2010-10-121-1/+7
| | | | | | | | | perform initialization without static constructors AND without explicit initialization by the client. For the moment, passes are required to initialize both their (potential) dependencies and any passes they preserve. I hope to be able to relax the latter requirement in the future. llvm-svn: 116334
* Now with fewer extraneous semicolons!Owen Anderson2010-10-071-1/+1
| | | | llvm-svn: 115996
* Reapply commit 112699, speculatively reverted by echristo, sinceDuncan Sands2010-09-021-1/+1
| | | | | | | | | I'm sure it is harmless. Original commit message: If PrototypeValue is erased in the middle of using the SSAUpdator then the SSAUpdator may access freed memory. Instead, simply pass in the type and name explicitly, which is all that was used anyway. llvm-svn: 112810
* Speculatively revert 112699 and 112702, they seem to be causingEric Christopher2010-09-011-1/+1
| | | | | | self host errors on clang-x86-64. llvm-svn: 112719
* If PrototypeValue is erased in the middle of using the SSAUpdatorDuncan Sands2010-09-011-1/+1
| | | | | | | then the SSAUpdator may access freed memory. Instead, simply pass in the type and name explicitly, which is all that was used anyway. llvm-svn: 112699
* Now that PassInfo and Pass::ID have been separated, move the rest of the ↵Owen Anderson2010-08-231-1/+1
| | | | | | passes over to the new registration API. llvm-svn: 111815
* Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson2010-08-061-2/+2
| | | | llvm-svn: 110460
* Revert r110396 to fix buildbots.Owen Anderson2010-08-061-2/+2
| | | | llvm-svn: 110410
* Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson2010-08-051-2/+2
| | | | | | | | address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. llvm-svn: 110396
* Remove LCSSA's bogus dependence on LoopSimplify and LoopSimplify's bogusDan Gohman2010-07-261-7/+2
| | | | | | | | | | | | | | dependence on DominanceFrontier. Instead, add an explicit DominanceFrontier pass in StandardPasses.h to ensure that it gets scheduled at the right time. Declare that loop unrolling preserves ScalarEvolution, and shuffle some getAnalysisUsages. This eliminates one LoopSimplify and one LCCSA run in the standard compile opts sequence. llvm-svn: 109413
* Reorder the contents of various getAnalysisUsage functions, eliminatingDan Gohman2010-07-161-11/+7
| | | | | | a redundant loopsimplify run from the default -O2 sequence. llvm-svn: 108539
* cache result of operator*Gabor Greif2010-07-091-3/+4
| | | | llvm-svn: 107968
* Add a DominatorTree argument to isLCSSA so that it doesn't have toDan Gohman2010-03-101-2/+2
| | | | | | | compute a set of reachable blocks for itself each time it is called, which is fairly frequently. llvm-svn: 98179
* Fix a comment in a typo that Duncan noticed.Dan Gohman2009-11-091-1/+1
| | | | llvm-svn: 86575
* Generalize LCSSA to handle loops with exits with predecessors outsideDan Gohman2009-11-091-2/+14
| | | | | | | | | | | | the loop. This is needed because with indirectbr it may not be possible for LoopSimplify to guarantee that all loop exit predecessors are inside the loop. This fixes PR5437. LCCSA no longer actually requires LoopSimplify form, but for now it must still have the dependency because the PassManager doesn't know how to schedule LoopSimplify otherwise. llvm-svn: 86569
* Delete an unused member variable.Dan Gohman2009-11-051-2/+0
| | | | llvm-svn: 86160
* rewrite LCSSA to use SSAUpdate, to only return true if it modifiesChris Lattner2009-10-111-154/+130
| | | | | | the IR, and to implement the FIXME'd optimization. llvm-svn: 83748
* clean up and simplify some code. Don't use setvector when things will beChris Lattner2009-10-111-28/+23
| | | | | | | inserted only once, just use vector. Don't compute ExitBlocks unless we need it, change std::sort to array_pod_sort. llvm-svn: 83747
* random tidyingChris Lattner2009-10-101-7/+5
| | | | llvm-svn: 83701
* Remove a redundant #ifndef and add an assertion string.Dan Gohman2009-09-281-3/+1
| | | | llvm-svn: 82991
* Re-apply r80926, with fixes: keep the domtree informed of new blocksDan Gohman2009-09-081-3/+14
| | | | | | | | | | | | | | | that get created during loop unswitching, and fix SplitBlockPredecessors' LCSSA updating code to create new PHIs instead of trying to just move existing ones. Also, optimize Loop::verifyLoop, since it gets called a lot. Use searches on a sorted list of blocks instead of calling the "contains" function, as is done in other places in the Loop class, since "contains" does a linear search. Also, don't call verifyLoop from LoopSimplify or LCSSA, as the PassManager is already calling verifyLoop as part of LoopInfo's verifyAnalysis. llvm-svn: 81221
* Revert r80926. It causes loop unswitch assertion and slow down some JIT ↵Evan Cheng2009-09-061-16/+3
| | | | | | tests significantly. llvm-svn: 81101
* Add a verifyAnalysis to LoopInfo, LoopSimplify, and LCSSA form that verifyDan Gohman2009-09-031-3/+16
| | | | | | | | | that these passes are properly preserved. Fix several transformation passes that claimed to preserve LoopSimplify form but weren't. llvm-svn: 80926
* Move more code back to 2.5 APIs.Owen Anderson2009-07-301-1/+1
| | | | llvm-svn: 77635
* Get rid of the Pass+Context magic.Owen Anderson2009-07-221-1/+1
| | | | llvm-svn: 76702
* More LLVMContext-ification.Owen Anderson2009-07-051-1/+2
| | | | llvm-svn: 74807
* Fix LCSSA to avoid emitting a PHI node for the unwind destination ofDan Gohman2009-06-261-2/+11
| | | | | | | an invoke instruction, since the value isn't really live across that edge. llvm-svn: 74242
* Real fix for PR3549, by using caching for predecessor counts in addition to ↵Owen Anderson2009-04-221-11/+13
| | | | | | | | the predecessors themselves. This halves the time to optimize the testcase, beyond what my previous patch did. llvm-svn: 69792
* Use PredIteratorCache in LCSSA, which gives a 37% overall speedup on the ↵Owen Anderson2009-04-221-2/+5
| | | | | | testcase from PR3549. More improvements to come. llvm-svn: 69788
* Simplify the logic of getting hold of a PHI predecessor block.Gabor Greif2009-01-231-4/+2
| | | | | | | | | There is now a direct way from value-use-iterator to incoming block in PHINode's API. This way we avoid the iterator->index->iterator trip, and especially the costly getOperandNo() invocation. Additionally there is now an assertion that the iterator really refers to one of the PHI's Uses. llvm-svn: 62869
* Change create*Pass factory functions to return Pass* instead ofDaniel Dunbar2008-10-221-1/+1
| | | | | | | | | | | LoopPass*. - Although less precise, this means they can be used in clients without RTTI (who would otherwise need to include LoopPass.h, which eventually includes things using dynamic_cast). This was the simplest solution that presented itself, but I am happy to use a better one if available. llvm-svn: 58010
* Tidy up several unbeseeming casts from pointer to intptr_t.Dan Gohman2008-09-041-1/+1
| | | | llvm-svn: 55779
* Enable first-class aggregates support.Dan Gohman2008-07-231-21/+1
| | | | | | | | | | | | Remove the GetResultInst instruction. It is still accepted in LLVM assembly and bitcode, where it is now auto-upgraded to ExtractValueInst. Also, remove support for return instructions with multiple values. These are auto-upgraded to use InsertValueInst instructions. The IRBuilder still accepts multiple-value returns, and auto-upgrades them to InsertValueInst instructions. llvm-svn: 53941
* Fix whitespace in whitespace-significant pseudocode in a comment.Dan Gohman2008-06-031-2/+2
| | | | llvm-svn: 51890
OpenPOWER on IntegriCloud