summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/LoopUnroll.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [LPM] Fix PR18616 where the shifts to the loop pass manager to extractChandler Carruth2014-01-281-3/+5
| | | | | | | | | | | | | | | | | | | | | | | | | LCSSA from it caused a crasher with the LoopUnroll pass. This crasher is really nasty. We destroy LCSSA form in a suprising way. When unrolling a loop into an outer loop, we not only need to restore LCSSA form for the outer loop, but for all children of the outer loop. This is somewhat obvious in retrospect, but hey! While this seems pretty heavy-handed, it's not that bad. Fundamentally, we only do this when we unroll a loop, which is already a heavyweight operation. We're unrolling all of these hypothetical inner loops as well, so their size and complexity is already on the critical path. This is just adding another pass over them to re-canonicalize. I have a test case from PR18616 that is great for reproducing this, but pretty useless to check in as it relies on many 10s of nested empty loops that get unrolled and deleted in just the right order. =/ What's worse is that investigating this has exposed another source of failure that is likely to be even harder to test. I'll try to come up with test cases for these fixes, but I want to get the fixes into the tree first as they're causing crashes in the wild. llvm-svn: 200273
* [LPM] Make LoopSimplify no longer a LoopPass and instead both a utilityChandler Carruth2014-01-231-8/+26
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | function and a FunctionPass. This has many benefits. The motivating use case was to be able to compute function analysis passes *after* running LoopSimplify (to avoid invalidating them) and then to run other passes which require LoopSimplify. Specifically passes like unrolling and vectorization are critical to wire up to BranchProbabilityInfo and BlockFrequencyInfo so that they can be profile aware. For the LoopVectorize pass the only things in the way are LoopSimplify and LCSSA. This fixes LoopSimplify and LCSSA is next on my list. There are also a bunch of other benefits of doing this: - It is now very feasible to make more passes *preserve* LoopSimplify because they can simply run it after changing a loop. Because subsequence passes can assume LoopSimplify is preserved we can reduce the runs of this pass to the times when we actually mutate a loop structure. - The new pass manager should be able to more easily support loop passes factored in this way. - We can at long, long last observe that LoopSimplify is preserved across SCEV. This *halves* the number of times we run LoopSimplify!!! Now, getting here wasn't trivial. First off, the interfaces used by LoopSimplify are all over the map regarding how analysis are updated. We end up with weird "pass" parameters as a consequence. I'll try to clean at least some of this up later -- I'll have to have it all clean for the new pass manager. Next up I discovered a really frustrating bug. LoopUnroll *claims* to preserve LoopSimplify. That's actually a lie. But the way the LoopPassManager ends up running the passes, it always ran LoopSimplify on the unrolled-into loop, rectifying this oversight before any verification could kick in and point out that in fact nothing was preserved. So I've added code to the unroller to *actually* simplify the surrounding loop when it succeeds at unrolling. The only functional change in the test suite is that we now catch a case that was previously missed because SCEV and other loop transforms see their containing loops as simplified and thus don't miss some opportunities. One test case has been converted to check that we catch this case rather than checking that we miss it but at least don't get the wrong answer. Note that I have #if-ed out all of the verification logic in LoopSimplify! This is a temporary workaround while extracting these bits from the LoopPassManager. Currently, there is no way to have a pass in the LoopPassManager which preserves LoopSimplify along with one which does not. The LPM will try to verify on each loop in the nest that LoopSimplify holds but the now-Function-pass cannot distinguish what loop is being verified and so must try to verify all of them. The inner most loop is clearly no longer simplified as there is a pass which didn't even *attempt* to preserve it. =/ Once I get LCSSA out (and maybe LoopVectorize and some other fixes) I'll be able to re-enable this check and catch any places where we are still failing to preserve LoopSimplify. If this causes problems I can back this out and try to commit *all* of this at once, but so far this seems to work and allow much more incremental progress. llvm-svn: 199884
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-131-2/+3
| | | | | | | | | | | | | | | | | | | | | | | 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
* Don't #include heavy Dominators.h file in LoopInfo.h. This change reducesJakub Staszak2013-12-071-0/+1
| | | | | | overall time of LLVM compilation by ~1%. llvm-svn: 196667
* Utils/LoopUnroll.cpp: Tweak (StringRef)OldName to be valid until it is used, ↵NAKAMURA Takumi2013-11-171-1/+3
| | | | | | | | since r194601. eraseFromParent() invalidates OldName. llvm-svn: 194970
* Use StringRef instead of std::stringJakub Staszak2013-11-131-1/+1
| | | | llvm-svn: 194601
* Replace some unnecessary vector copies with references.Benjamin Kramer2013-09-151-2/+0
| | | | llvm-svn: 190770
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-1/+1
| | | | | | | | | | | | | | | | | | | | | 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-1/+1
| | | | | | | | | | | | | | | | | 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
* LoopUnroll: always check for NULL LoopPassManagerAndrew Trick2012-06-051-3/+5
| | | | llvm-svn: 158007
* Allow NULL LoopPassManager argument in UnrollLoop. PR12734.Andrew Trick2012-05-081-20/+24
| | | | llvm-svn: 156358
* Fix 12513: Loop unrolling breaks with indirect branches.Andrew Trick2012-04-101-0/+6
| | | | | | | | 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
* Avoid a confusing assert for silly options: -unroll-runtime -unroll-count=1.Andrew Trick2011-12-161-0/+5
| | | | | | No need for an explicit test case for an unsupported combination of options. llvm-svn: 146721
* Add -unroll-runtime for unrolling loops with run-time trip counts.Andrew Trick2011-12-091-7/+22
| | | | | | | | | | | | | Patch by Brendon Cahoon! This extends the existing LoopUnroll and LoopUnrollPass. Brendon measured no regressions in the llvm test suite with -unroll-runtime enabled. This implementation works by using the existing loop unrolling code to unroll the loop by a power-of-two (default 8). It generates an if-then-else sequence of code prior to the loop to execute the extra iterations before entering the unrolled loop. llvm-svn: 146245
* Comments. Thanks for the spell check Nick!Andrew Trick2011-08-101-2/+2
| | | | | | Also, my apologies for spoiling the autocomplete on SimplifyInstructions.cpp. I couldn't think of a better filename. llvm-svn: 137229
* Invoke SimplifyIndVar when we partially unroll a loop. Fixes PR10534.Andrew Trick2011-08-101-1/+24
| | | | llvm-svn: 137203
* Cleanup. Added LoopBlocksDFS::perform for simple clients.Andrew Trick2011-08-101-7/+2
| | | | llvm-svn: 137195
* Fix the LoopUnroller to handle nontrivial loops and partial unrolling.Andrew Trick2011-08-101-52/+60
| | | | | | | | | | These are not individual bug fixes. I had to rewrite a good chunk of the unroller to make it sane. I think it was getting lucky on trivial completely unrolled loops with no early exits. I included some fairly simple unit tests for partial unrolling. I didn't do much stress testing, so it may not be perfect, but should be usable now. llvm-svn: 137190
* LoopUnroll looks like it has some stale code. Remove it to prove my sanity ↵Andrew Trick2011-08-091-6/+1
| | | | | | and avoid further confusion. llvm-svn: 137106
* SCEV: Use AssertingVH to catch dangling BasicBlock* when passes forgetAndrew Trick2011-08-031-2/+9
| | | | | | to notify SCEV of a change. Add forgetLoop in a couple of those places. llvm-svn: 136797
* Add clarifying comments for the new arguments to UnrollLoop.Andrew Trick2011-07-251-0/+12
| | | | llvm-svn: 135988
* Move trip count discovery outside of the generic LoopUnroll helper. ThisAndrew Trick2011-07-231-12/+2
| | | | | | removes its dependence on canonical induction variables. llvm-svn: 135829
* whitespaceAndrew Trick2011-07-231-7/+7
| | | | llvm-svn: 135828
* Reinstate r133513 (reverted in r133700) with an additional fix for aJay Foad2011-06-231-39/+46
| | | | | | -Wshorten-64-to-32 warning in Instructions.h. llvm-svn: 133708
* Revert r133513:Eric Christopher2011-06-231-46/+39
| | | | | | | | | "Reinstate r133435 and r133449 (reverted in r133499) now that the clang self-hosted build failure has been fixed (r133512)." Due to some additional warnings. llvm-svn: 133700
* Remove unused variables.Benjamin Kramer2011-06-211-2/+2
| | | | llvm-svn: 133514
* Reinstate r133435 and r133449 (reverted in r133499) now that the clangJay Foad2011-06-211-32/+39
| | | | | | self-hosted build failure has been fixed (r133512). llvm-svn: 133513
* Revert r133435 and r133449 to appease buildbots.Chad Rosier2011-06-211-39/+32
| | | | llvm-svn: 133499
* Change how PHINodes store their operands.Jay Foad2011-06-201-32/+39
| | | | | | | | | | | | | | | | | | | Change PHINodes to store simple pointers to their incoming basic blocks, instead of full-blown Uses. Note that this loses an optimization in SplitCriticalEdge(), because we can no longer walk the use list of a BasicBlock to find phi nodes. See the comment I removed starting "However, the foreach loop is slow for blocks with lots of predecessors". Extend replaceAllUsesWith() on a BasicBlock to also update any phi nodes in the block's successors. This mimics what would have happened when PHINodes were proper Users of their incoming blocks. (Note that this only works if OldBB->replaceAllUsesWith(NewBB) is called when OldBB still has a terminator instruction, so it still has some successors.) llvm-svn: 133435
* Don't unroll loops whose header block's address is taken.Chris Lattner2011-02-181-2/+10
| | | | | | | | | | | | | | | | | This is part of a futile attempt to not "break" bizzaro code like this: l1: printf("l1: %p\n", &&l1); ++x; if( x < 3 ) goto l1; Previously we'd fold &&l1 to 1, which is fine per our semantics but not helpful to the user. llvm-svn: 125827
* random cleanupsChris Lattner2011-01-111-2/+2
| | | | llvm-svn: 123221
* Remove all uses of the "ugly" method BranchInst::setUnconditionalDest().Jay Foad2011-01-071-1/+3
| | | | llvm-svn: 123025
* Replace calls to ConstantFoldInstruction with calls to SimplifyInstructionDuncan Sands2010-11-231-5/+6
| | | | | | | in two places that are really interested in simplified instructions, not constants. llvm-svn: 120044
* Be more consistent in using ValueToValueMapTy.Rafael Espindola2010-10-131-4/+3
| | | | llvm-svn: 116387
* Preserve ScalarEvolution in the loop unroller.Dan Gohman2010-07-261-0/+6
| | | | llvm-svn: 109412
* Use ValueMap instead of DenseMap.Devang Patel2010-06-241-3/+3
| | | | | | The ValueMapper used by various cloning utility maps MDNodes also. llvm-svn: 106706
* Cosmetic change.Devang Patel2010-06-231-9/+9
| | | | | | Do not use "ValueMap" as a name for a local variable or an argument. llvm-svn: 106698
* Rename ValueMapTy as ValueToValueMapTy to clearly indicate that this has no ↵Devang Patel2010-04-201-4/+4
| | | | | | replationship with ADT/ValueMap. llvm-svn: 101950
* Add a DominatorTree argument to isLCSSA so that it doesn't have toDan Gohman2010-03-101-6/+0
| | | | | | | compute a set of reachable blocks for itself each time it is called, which is fairly frequently. llvm-svn: 98179
* Don't bother with sprintf, just pass the Twine through.Benjamin Kramer2010-01-271-5/+1
| | | | llvm-svn: 94684
* Change errs() to dbgs().David Greene2010-01-051-11/+11
| | | | llvm-svn: 92600
* Add Loop contains utility methods for testing whether a loopDan Gohman2009-12-181-4/+4
| | | | | | | | 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
* remove a bunch of extraneous LLVMContext argumentsChris Lattner2009-11-061-2/+1
| | | | | | from various APIs, addressing PR5325. llvm-svn: 86231
* Teach LoopUnroll how to bail if LoopSimplify can't give it what it needs.Dan Gohman2009-11-051-1/+12
| | | | llvm-svn: 86164
* Revert r85667. LoopUnroll currently can't call utility functions whichDan Gohman2009-10-311-1/+47
| | | | | | | auto-update the DominatorTree because it doesn't keep the DominatorTree current while it works. llvm-svn: 85670
* Merge the enhancements from LoopUnroll's FoldBlockIntoPredecessor intoDan Gohman2009-10-311-47/+1
| | | | | | | MergeBlockIntoPredecessor. This makes SimplifyCFG slightly more aggressive, and makes it unnecessary for LoopUnroll to have its own copy of this code. llvm-svn: 85667
* Simplify this code.Dan Gohman2009-10-311-2/+2
| | | | llvm-svn: 85662
* Rename UnrollLoop.cpp to LoopUnroll.cpp, and LoopUnroll.cpp toDan Gohman2009-10-311-0/+372
LoopUnrollPass.cpp, for consistency with other passes which are similarly split. llvm-svn: 85659
OpenPOWER on IntegriCloud