summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LoopInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* A new algorithm for computing LoopInfo. Temporarily disabled.Andrew Trick2012-06-201-1/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | -stable-loops enables a new algorithm for generating the Loop forest. It differs from the original algorithm in a few respects: - Not determined by use-list order. - Initially guarantees RPO order of block and subloops. - Linear in the number of CFG edges. - Nonrecursive. I didn't want to change the LoopInfo API yet, so the block lists are still inclusive. This seems strange to me, and it means that building LoopInfo is not strictly linear, but it may not be a problem in practice. At least the block lists start out in RPO order now. In the future we may add an attribute or wrapper analysis that allows other passes to assume RPO order. The primary motivation of this work was not to optimize LoopInfo, but to allow reproducing performance issues by decomposing the compilation stages. I'm often unable to do this with the current LoopInfo, because the loop tree order determines Loop pass order. Serializing the IR tends to invert the order, which reverses the optimization order. This makes it nearly impossible to debug interdependent loop optimizations such as LSR. I also believe this will provide more stable performance results across time. llvm-svn: 158790
* Move the implementation of LoopInfo into LoopInfoImpl.h.Andrew Trick2012-06-201-0/+5
| | | | | | | | | The implementation only needs inclusion from LoopInfo.cpp and MachineLoopInfo.cpp. Clients of the interface should only include the interface. This makes the interface readable and speeds up rebuilds after modifying the implementation. llvm-svn: 158787
* Fix 12513: Loop unrolling breaks with indirect branches.Andrew Trick2012-04-101-0/+11
| | | | | | | | Take this opportunity to generalize the indirectbr bailout logic for loop transformations. CFG transformations will never get indirectbr right, and there's no point trying. llvm-svn: 154386
* Move Instruction::isSafeToSpeculativelyExecute out of VMCore andDan Gohman2011-12-141-1/+2
| | | | | | | | | into Analysis as a standalone function, since there's no need for it to be in VMCore. Also, update it to use isKnownNonZero and other goodies available in Analysis, making it more precise, enabling more aggressive optimization. llvm-svn: 146610
* Remove the temporary flag -disable-unroll-scev and dead code.Andrew Trick2011-11-281-93/+0
| | | | | | SCEV should now be used for trip count analysis, not LoopInfo. llvm-svn: 145262
* Fix a corner case in updating LoopInfo after fully unrolling an outer loop.Andrew Trick2011-11-181-11/+9
| | | | | | | | | | | The loop tree's inclusive block lists are painful and expensive to update. (I have no idea why they're inclusive). The design was supposed to handle this case but the implementation missed it and my unit tests weren't thorough enough. Fixes PR11335: loop unroll update. llvm-svn: 144970
* LoopInfo::updateUnloop fix, and verify Block->Loop maps.Andrew Trick2011-08-261-2/+13
| | | | | | Fixes an oversight, and adds verification to catch it in the unloop.ll tests. llvm-svn: 138622
* Make a bunch of symbols private.Benjamin Kramer2011-08-191-0/+2
| | | | llvm-svn: 138025
* Revert r137655. There is some question about whether the 'landingpad'Bill Wendling2011-08-171-0/+3
| | | | | | instruction should be marked as potentially reading and/or writing memory. llvm-svn: 137863
* Duncan pointed out that the LandingPadInst might read memory. (It might alsoBill Wendling2011-08-151-3/+0
| | | | | | write to memory.) Marking it as such makes some checks for immobility go away. llvm-svn: 137655
* The landingpad instruction isn't loop-invariant.Bill Wendling2011-08-151-0/+3
| | | | llvm-svn: 137628
* Silence a bunch (but not all) "variable written but not read" warningsDuncan Sands2011-08-121-4/+4
| | | | | | when building with assertions disabled. llvm-svn: 137460
* Fix for LoopInfo::updateUnloop. Remove subloop blocks from formerAndrew Trick2011-08-111-16/+29
| | | | | | | | | ancestor loops. I have a unit test that depends on scev-unroll, which unfortunately isn't checked in. But I will check it in when I can. llvm-svn: 137341
* Cleanup. Another thorough review by Nick!Andrew Trick2011-08-111-6/+6
| | | | llvm-svn: 137317
* Reapplying r136844.Andrew Trick2011-08-101-0/+244
| | | | | | | | | | | | | | | | | | | | 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
* Cleanup. Added LoopBlocksDFS::perform for simple clients.Andrew Trick2011-08-101-0/+13
| | | | llvm-svn: 137195
* Reverting r136884 updateUnloop, which crashed a linux builder.Andrew Trick2011-08-041-242/+0
| | | | llvm-svn: 136857
* An algorithm for incrementally updating LoopInfo within aAndrew Trick2011-08-031-0/+242
| | | | | | | | | | | | | | | | | | | 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-3/+3
| | | | llvm-svn: 136843
* Fix typo pointed out by Trevor Harmon.Duncan Sands2010-11-131-1/+1
| | | | llvm-svn: 119001
* Begin adding static dependence information to passes, which will allow us toOwen Anderson2010-10-121-1/+3
| | | | | | | | | 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
* pull a simple method out of LICM into a new Chris Lattner2010-09-061-6/+10
| | | | | | | | | | Loop::hasLoopInvariantOperands method. Remove a useless and confusing Loop::isLoopInvariant(Instruction) method, which didn't do what you thought it did. No functionality change. llvm-svn: 113133
* Eliminate getCanonicalInductionVariableIncrement's last user andDan Gohman2010-07-231-17/+5
| | | | | | eliminate it. llvm-svn: 109270
* Simplify this code; it can use the regular CFG utlities rather thanDan Gohman2010-07-231-13/+7
| | | | | | the BlockTraits abstractions. llvm-svn: 109268
* Fix batch of converting RegisterPass<> to INTIALIZE_PASS().Owen Anderson2010-07-211-2/+1
| | | | llvm-svn: 109045
* cache result of operator*Gabor Greif2010-07-091-3/+4
| | | | llvm-svn: 107967
* Fix a bunch of namespace polution.Dan Gohman2010-04-151-2/+2
| | | | llvm-svn: 101376
* Add a DominatorTree argument to isLCSSA so that it doesn't have toDan Gohman2010-03-101-9/+2
| | | | | | | compute a set of reachable blocks for itself each time it is called, which is fairly frequently. llvm-svn: 98179
* Make isLCSSA ignore uses in blocks not reachable from the entry block,Dan Gohman2010-03-091-3/+14
| | | | | | as LCSSA no longer transforms such uses. llvm-svn: 98033
* Restore dump() methods to Loop and MachineLoop.Dan Gohman2010-01-051-0/+5
| | | | llvm-svn: 92772
* Add Loop contains utility methods for testing whether a loopDan Gohman2009-12-181-1/+1
| | | | | | | | contains another loop, or an instruction. The loop form is substantially more efficient on large loops than the typical code it replaces. llvm-svn: 91654
* Make getUniqueExitBlocks's precondition assert more precise, toDan Gohman2009-12-111-3/+3
| | | | | | avoid spurious failures. This fixes PR5758. llvm-svn: 91147
* Teach getSmallConstantTripMultiple about Shl operators.Dan Gohman2009-11-201-0/+5
| | | | llvm-svn: 89426
* Minor tidiness fixes.Dan Gohman2009-11-091-4/+3
| | | | llvm-svn: 86565
* Factor out the predicate code for loopsimplify form exit blocks intoDan Gohman2009-11-051-6/+8
| | | | | | a separate helper function. llvm-svn: 86159
* Fix another place that calls Loop::contains a lot to construct a sortedDan Gohman2009-10-201-1/+4
| | | | | | | | container of the blocks and do efficient lookups. This makes isLoopSimplifyForm much faster on large loops, fixing a significant compile-time issue in builds with assertions enabled. llvm-svn: 84673
* Move the dominator verification code out of special code embedded withinDan Gohman2009-09-281-0/+21
| | | | | | | | | | | | 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
* Re-apply r80926, with fixes: keep the domtree informed of new blocksDan Gohman2009-09-081-0/+10
| | | | | | | | | | | | | | | 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-10/+0
| | | | | | tests significantly. llvm-svn: 81101
* Smallvectorize switchExitBlocks.Dan Gohman2009-09-031-1/+1
| | | | llvm-svn: 80942
* Add a verifyAnalysis to LoopInfo, LoopSimplify, and LCSSA form that verifyDan Gohman2009-09-031-0/+10
| | | | | | | | | that these passes are properly preserved. Fix several transformation passes that claimed to preserve LoopSimplify form but weren't. llvm-svn: 80926
* Move getUniqueExitBlocks from LoopBase to Loop, since they depend onDan Gohman2009-09-031-0/+68
| | | | | | | LoopSimplify form, which is currently only available on Loops (and not MachineLoops). Also, move the code out of the header file. llvm-svn: 80923
* remove uses of llvm/Support/Streams.h.Chris Lattner2009-08-231-1/+0
| | | | llvm-svn: 79838
* Change Pass::print to take a raw ostream instead of std::ostream,Chris Lattner2009-08-231-3/+2
| | | | | | update all code that this affects. llvm-svn: 79830
* eliminate the std::ostream form of WriteAsOperand and update clients.Chris Lattner2009-08-231-0/+6
| | | | | | This also updates dominator related stuff. llvm-svn: 79825
* Replace isTrapping with a new, similar method called Eli Friedman2009-07-171-7/+2
| | | | | | | | | | isSafeToSpeculativelyExecute. The new method is a bit closer to what the callers actually care about in that it rejects more things callers don't want. It also adds more precise handling for integer division, and unifies code for analyzing the legality of a speculative load. llvm-svn: 76150
* Add an isLoopSimplifyForm() predicate, following the example ofDan Gohman2009-07-161-0/+24
| | | | | | | isLCSSAForm(), to test whether a loop is in the form guaranteed by the LoopSimplify pass. llvm-svn: 76077
* Make makeLoopInvariant report whether it made any changes or not,Dan Gohman2009-07-151-4/+7
| | | | | | and use this to simplify more code. llvm-svn: 75722
* Introduce a new LoopInfo utility function makeLoopInvariant, whichDan Gohman2009-07-141-1/+62
| | | | | | | | | | | works similar to isLoopInvariant, except that it will do trivial hoisting to try to make the value loop invariant if it isn't already. This makes it easier for transformation passes to clear trivial instructions out of the way (the regular LICM pass doesn't run until relatively late). This is code factored out of LoopSimplify and other places. llvm-svn: 75578
OpenPOWER on IntegriCloud