summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LoopPass.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Enable the new LoopInfo algorithm by default.Andrew Trick2012-06-261-3/+7
| | | | | | | | | | | | | | | | | | | | | | | | The primary advantage is that loop optimizations will be applied in a stable order. This helps debugging and unit test creation. It is also a better overall implementation without pathologically bad performance on deep functions. On large functions (llvm-stress --size=200000 | opt -loops) Before: 0.1263s After: 0.0225s On deep functions (after tweaking llvm-stress, thanks Nadav): Before: 0.2281s After: 0.0227s See r158790 for more comments. The loop tree is now consistently generated in forward order, but loop passes are applied in reverse order over the program. If we have a loop optimization that prefers forward order, that can easily be achieved by adding a different type of LoopPassManager. llvm-svn: 159183
* Take out the debug info probe stuff. It's making some changes toEric Christopher2012-03-231-21/+2
| | | | | | | the PassManager annoying and should be reimplemented as a decorator on top of existing passes (as should the timing data). llvm-svn: 153305
* Reapply r138695. Fix PassManager stack depths.Andrew Trick2011-08-291-4/+4
| | | | | | Patch by Xiaoyi Guo! llvm-svn: 138737
* Reverting r138695 to see if it fixes clang self host.Andrew Trick2011-08-271-4/+4
| | | | llvm-svn: 138701
* Fix PassManager stack depths.Andrew Trick2011-08-271-4/+4
| | | | | | Patch by Xiaoyi Guo! llvm-svn: 138695
* Reapplying r136844.Andrew Trick2011-08-101-50/+6
| | | | | | | | | | | | | | | | | | | | An algorithm for incrementally updating LoopInfo within a LoopPassManager. The incremental update should be extremely cheap in most cases and can be used in places where it's not feasible to regenerate the entire loop forest. - "Unloop" is a node in the loop tree whose last backedge has been removed. - Perform reverse dataflow on the block inside Unloop to propagate the nearest loop from the block's successors. - For reducible CFG, each block in unloop is visited exactly once. This is because unloop no longer has a backedge and blocks within subloops don't change parents. - Immediate subloops are summarized by the nearest loop reachable from their exits or exits within nested subloops. - At completion the unloop blocks each have a new parent loop, and each immediate subloop has a new parent. llvm-svn: 137276
* Reverting r136884 updateUnloop, which crashed a linux builder.Andrew Trick2011-08-041-6/+50
| | | | llvm-svn: 136857
* An algorithm for incrementally updating LoopInfo within aAndrew Trick2011-08-031-50/+6
| | | | | | | | | | | | | | | | | | | LoopPassManager. The incremental update should be extremely cheap in most cases and can be used in places where it's not feasible to regenerate the entire loop forest. - "Unloop" is a node in the loop tree whose last backedge has been removed. - Perform reverse dataflow on the block inside Unloop to propagate the nearest loop from the block's successors. - For reducible CFG, each block in unloop is visited exactly once. This is because unloop no longer has a backedge and blocks within subloops don't change parents. - Immediate subloops are summarized by the nearest loop reachable from their exits or exits within nested subloops. - At completion the unloop blocks each have a new parent loop, and each immediate subloop has a new parent. llvm-svn: 136844
* whitespaceAndrew Trick2011-08-031-28/+28
| | | | llvm-svn: 136843
* Introduce DebugInfoProbe. This is used to monitor how llvm optimizer is ↵Devang Patel2011-03-101-2/+21
| | | | | | | | | | | | treating debugging information. It generates output that lools like 8 times line number info lost by Scalar Replacement of Aggregates (SSAUp) 1 times line number info lost by Simplify well-known library calls 12 times variable info lost by Jump Threading llvm-svn: 127381
* zap dead code.Chris Lattner2010-09-041-1/+0
| | | | llvm-svn: 113073
* Revert r111199; it breaks -debug-pass=Structure output.Dan Gohman2010-08-191-1/+1
| | | | llvm-svn: 111500
* Make dumpPassStructure be a PMDataManager abstraction, rather thanDan Gohman2010-08-161-1/+1
| | | | | | | | | | a Pass abstraction, since that's the level it's actually used at. Rename Pass' dumpPassStructure to dumpPass. This eliminates an awkward use of getAsPass() to convert a PMDataManager* into a Pass* just to permit a dumpPassStructure call. llvm-svn: 111199
* Make LoopPass::getContainedPass return a LoopPass* instead of a Pass*Dan Gohman2010-08-111-5/+5
| | | | | | and remove casts from all its callers. llvm-svn: 110848
* Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson2010-08-061-3/+3
| | | | llvm-svn: 110460
* Revert r110396 to fix buildbots.Owen Anderson2010-08-061-3/+3
| | | | llvm-svn: 110410
* Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson2010-08-051-3/+3
| | | | | | | | address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. llvm-svn: 110396
* Ok, third time's the charm. No changes from last time except the CMakeDavid Greene2010-04-021-0/+40
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | source addition. Apparently the buildbots were wrong about failures. --- Add some switches helpful for debugging: -print-before=<Pass Name> Dump IR before running pass <Pass Name>. -print-before-all Dump IR before running each pass. -print-after-all Dump IR after running each pass. These are helpful when tracking down a miscompilation. It is easy to get IR dumps and do diffs on them, etc. To make this work well, add a new getPrinterPass API to Pass so that each kind of pass (ModulePass, FunctionPass, etc.) can create a Pass suitable for dumping out the kind of object the Pass works on. llvm-svn: 100249
* Revert 100204. It broke a bunch of tests and apparently changed what passes ↵Evan Cheng2010-04-021-40/+0
| | | | | | are run during codegen. llvm-svn: 100207
* Let's try this again. Re-apply 100143 including an apparent missingDavid Greene2010-04-021-0/+40
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | <string> include. For some reason the buildbot choked on this while my builds did not. It's probably due to a difference in system headers. --- Add some switches helpful for debugging: -print-before=<Pass Name> Dump IR before running pass <Pass Name>. -print-before-all Dump IR before running each pass. -print-after-all Dump IR after running each pass. These are helpful when tracking down a miscompilation. It is easy to get IR dumps and do diffs on them, etc. To make this work well, add a new getPrinterPass API to Pass so that each kind of pass (ModulePass, FunctionPass, etc.) can create a Pass suitable for dumping out the kind of object the Pass works on. llvm-svn: 100204
* Revert r100143.Eric Christopher2010-04-011-40/+0
| | | | llvm-svn: 100146
* Add some switches helpful for debugging:David Greene2010-04-011-0/+40
| | | | | | | | | | | | | | | | | | | | | | | -print-before=<Pass Name> Dump IR before running pass <Pass Name>. -print-before-all Dump IR before running each pass. -print-after-all Dump IR after running each pass. These are helpful when tracking down a miscompilation. It is easy to get IR dumps and do diffs on them, etc. To make this work well, add a new getPrinterPass API to Pass so that each kind of pass (ModulePass, FunctionPass, etc.) can create a Pass suitable for dumping out the kind of object the Pass works on. llvm-svn: 100143
* s/getNameStr/getName/Benjamin Kramer2010-03-311-3/+3
| | | | llvm-svn: 100011
* reapply my timer rewrite with a change for PassManager to store Chris Lattner2010-03-301-5/+7
| | | | | | timers by pointer instead of by-value. llvm-svn: 99871
* revert r99862 which is causing FNT failures.Chris Lattner2010-03-301-7/+5
| | | | llvm-svn: 99870
* fairly major rewrite of various timing related stuff.Chris Lattner2010-03-301-5/+7
| | | | llvm-svn: 99862
* eliminate a bunch more unneeded dynamic_cast's.Chris Lattner2010-01-221-27/+18
| | | | llvm-svn: 94156
* Fix this debug output to handle the case where the loop has been deleted.Dan Gohman2009-09-281-1/+2
| | | | llvm-svn: 82994
* Include the name of the loop header in debug messages.Dan Gohman2009-09-281-4/+9
| | | | llvm-svn: 82993
* Move the dominator verification code out of special code embedded withinDan Gohman2009-09-281-4/+12
| | | | | | | | | | | | the PassManager code into a regular verifyAnalysis method. Also, reorganize loop verification. Make the LoopPass infrastructure call verifyLoop as needed instead of having LoopInfo::verifyAnalysis check every loop in the function after each looop pass. Add a new command-line argument, -verify-loop-info, to enable the expensive full checking. llvm-svn: 82952
* Move this assert to check the condition as soon as it is known.Dan Gohman2009-09-281-1/+1
| | | | llvm-svn: 82951
* Extend the StartPassTimer and StopPassTimer functions so that theDan Gohman2009-09-281-2/+2
| | | | | | | | code that stops the timer doesn't have to search to find the timer object before it stops the timer. This avoids a lock acquisition and a few other things done with the timer running. llvm-svn: 82949
* Fix an old copy+pasto.Dan Gohman2009-09-271-1/+1
| | | | llvm-svn: 82947
* Extract the code for inserting a loop into the loop queue intoDan Gohman2009-09-271-3/+7
| | | | | | a separate function. llvm-svn: 82946
* When a loop is deleted, immediately release all of the activeDan Gohman2009-09-271-0/+9
| | | | | | | | LoopPasses for that loop. This avoids trouble with the PassManager trying to call verifyAnalysis on them, and frees up some memory sooner rather than later. llvm-svn: 82945
* Delete a bogus comment.Dan Gohman2009-09-271-1/+0
| | | | llvm-svn: 82908
* Don't try to verify a LoopPass analysis if the loop has been deleted.Dan Gohman2009-09-031-1/+3
| | | | llvm-svn: 80919
* convert LoopInfo.h and GraphWriter.h to use raw_ostreamChris Lattner2009-08-231-1/+1
| | | | llvm-svn: 79836
* Call doInitialization(), releaseMemory(), and doFinalization() for ↵Torok Edwin2009-06-291-0/+3
| | | | | | | | | | on-the-fly passes as well. Also don't call finalizers for LoopPass if initialization was not called. Add a unittest that tests that these methods are called, in the proper order, and the correct number of times. llvm-svn: 74438
* Before deleting a basic block, give other loop passes a chance cleanup ↵Devang Patel2009-03-251-0/+7
| | | | | | analysis values, related to the instructions in the basic block. llvm-svn: 67719
* Sprinkle some PrettyStackEntry magic into the passmanager. With this, we nowChris Lattner2009-03-061-5/+7
| | | | | | | | | | | | | | | | get nice and happy stack traces when we crash in an optimizer or codegen. For example, an abort put in UnswitchLoops now looks like this: Stack dump: 0. Program arguments: clang pr3399.c -S -O3 1. <eof> parser at end of file 2. per-module optimization passes 3. Running pass 'CallGraph Pass Manager' on module 'pr3399.c'. 4. Running pass 'Loop Pass Manager' on function '@foo' 5. Running pass 'Unswitch loops' on basic block '%for.inc' Abort llvm-svn: 66260
* Add a method to ScalarEvolution for telling it when a loop has beenDan Gohman2009-02-171-3/+0
| | | | | | | | | | | modified in a way that may effect the trip count calculation. Change IndVars to use this method when it rewrites pointer or floating-point induction variables instead of using a doInitialization method to sneak these changes in before ScalarEvolution has a chance to see the loop. This eliminates the need for LoopPass to depend on ScalarEvolution. llvm-svn: 64810
* Move dumpPassStructure out of line.Dan Gohman2009-02-171-0/+10
| | | | llvm-svn: 64796
* Tidy up several unbeseeming casts from pointer to intptr_t.Dan Gohman2008-09-041-1/+1
| | | | llvm-svn: 55779
* Don't call getAnalysisUsage unless -debug-pass is enabled. This speedsChris Lattner2008-08-081-4/+2
| | | | | | up the passmgr by avoiding useless work. llvm-svn: 54528
* Fix spelling of "hierarchy" in comments.Dan Gohman2008-07-111-1/+1
| | | | llvm-svn: 53489
* Keep track of inherited analysis (e.g. dominator tree).Devang Patel2008-07-031-0/+3
| | | | llvm-svn: 53088
* Fix typos in comments. Devang Patel2008-07-011-1/+1
| | | | | | Thanks for the feedback! llvm-svn: 52978
* Add dom info verifier.Devang Patel2008-07-011-0/+3
| | | | llvm-svn: 52967
* Remove attribution from file headers, per discussion on llvmdev.Chris Lattner2007-12-291-2/+2
| | | | llvm-svn: 45418
OpenPOWER on IntegriCloud