summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/LoopUnroll.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [UnrollAndJam] New Unroll and Jam passDavid Green2018-07-011-11/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a simple implementation of the unroll-and-jam classical loop optimisation. The basic idea is that we take an outer loop of the form: for i.. ForeBlocks(i) for j.. SubLoopBlocks(i, j) AftBlocks(i) Instead of doing normal inner or outer unrolling, we unroll as follows: for i... i+=2 ForeBlocks(i) ForeBlocks(i+1) for j.. SubLoopBlocks(i, j) SubLoopBlocks(i+1, j) AftBlocks(i) AftBlocks(i+1) Remainder Loop So we have unrolled the outer loop, then jammed the two inner loops into one. This can lead to a simpler inner loop if memory accesses can be shared between the now jammed loops. To do this we have to prove that this is all safe, both for the memory accesses (using dependence analysis) and that ForeBlocks(i+1) can move before AftBlocks(i) and SubLoopBlocks(i, j). Differential Revision: https://reviews.llvm.org/D41953 llvm-svn: 336062
* Move Analysis/Utils/Local.h back to TransformsDavid Blaikie2018-06-041-1/+1
| | | | | | | | | | Review feedback from r328165. Split out just the one function from the file that's used by Analysis. (As chandlerc pointed out, the original change only moved the header and not the implementation anyway - which was fine for the one function that was used (since it's a template/inlined in the header) but not in general) llvm-svn: 333954
* Revert 333358 as it's failing on some builders.David Green2018-05-271-11/+11
| | | | | | I'm guessing the tests reply on the ARM backend being built. llvm-svn: 333359
* [UnrollAndJam] Add a new Unroll and Jam passDavid Green2018-05-271-11/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a simple implementation of the unroll-and-jam classical loop optimisation. The basic idea is that we take an outer loop of the form: for i.. ForeBlocks(i) for j.. SubLoopBlocks(i, j) AftBlocks(i) Instead of doing normal inner or outer unrolling, we unroll as follows: for i... i+=2 ForeBlocks(i) ForeBlocks(i+1) for j.. SubLoopBlocks(i, j) SubLoopBlocks(i+1, j) AftBlocks(i) AftBlocks(i+1) Remainder So we have unrolled the outer loop, then jammed the two inner loops into one. This can lead to a simpler inner loop if memory accesses can be shared between the now-jammed loops. To do this we have to prove that this is all safe, both for the memory accesses (using dependence analysis) and that ForeBlocks(i+1) can move before AftBlocks(i) and SubLoopBlocks(i, j). Differential Revision: https://reviews.llvm.org/D41953 llvm-svn: 333358
* [LoopUnroll] Split out simplify code after Unroll into a new function. NFCDavid Green2018-05-161-34/+46
| | | | | | | | | So that it can be shared with other passes that may end up doing the same thing. Differential Revision: https://reviews.llvm.org/D45874 llvm-svn: 332450
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-27/+27
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* [NFC] Use forgetTopmostLoop instead of logic duplicationMax Kazantsev2018-04-241-6/+2
| | | | llvm-svn: 330683
* [LoopUnroll] Fix dangling pointers in SCEVMax Kazantsev2018-03-261-28/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Current logic of loop SCEV invalidation in Loop Unroller implicitly relies on fact that exit count of outer loops cannot rely on exiting blocks of inner loops, which is true in current implementation of backedge taken count calculation but is wrong in general. As result, when we only forget the loop that we have just unrolled, we may still have cached data for its outer loops (in particular, exit counts) which keeps references on blocks of inner loop that could have been changed or even deleted. The attached test demonstrates a situaton when after unrolling of innermost loop the outermost loop contains a dangling pointer on non-existant block. The problem shows up when we apply patch https://reviews.llvm.org/D44677 that makes SCEV smarter about exit count calculation. I am not sure if the bug exists without this patch, it appears that now it is accidentally correct just because in practice exact backedge taken count for outer loops with complex control flow inside is never calculated. But when SCEV learns to do so, this problem shows up. This patch replaces existing logic of SCEV loop invalidation with a correct one, which happens to be invalidation of outermost loop (which also leads to invalidation of all loops inside of it). It is the only way to ensure that no outer loop keeps dangling pointers on removed blocks, or just outdated information that has changed after unrolling. Differential Revision: https://reviews.llvm.org/D44818 Reviewed By: samparker llvm-svn: 328483
* [LoopUnroll] Simplify induction variables after peeling too.Florian Hahn2018-03-231-2/+3
| | | | | | | | | | | | | Loop peeling also has an impact on the induction variables, so we should benefit from induction variable simplification after peeling too. Reviewers: sanjoy, bogner, mzolotukhin, efriedma Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D43878 llvm-svn: 328301
* Fix a couple of layering violations in TransformsDavid Blaikie2018-03-211-1/+1
| | | | | | | | | | | | | Remove #include of Transforms/Scalar.h from Transform/Utils to fix layering. Transforms depends on Transforms/Utils, not the other way around. So remove the header and the "createStripGCRelocatesPass" function declaration (& definition) that is unused and motivated this dependency. Move Transforms/Utils/Local.h into Analysis because it's used by Analysis/MemoryBuiltins.cpp. llvm-svn: 328165
* [Dominators] Remove verifyDomTree and add some verifying for Post Dom TreesDavid Green2018-02-281-2/+2
| | | | | | | | | | | | Removes verifyDomTree, using assert(verify()) everywhere instead, and changes verify a little to always run IsSameAsFreshTree first in order to print good output when we find errors. Also adds verifyAnalysis for PostDomTrees, which will allow checking of PostDomTrees it the same way we check DomTrees and MachineDomTrees. Differential Revision: https://reviews.llvm.org/D41298 llvm-svn: 326315
* Use phi ranges to simplify code. No functionality change intended.Benjamin Kramer2017-12-301-13/+7
| | | | llvm-svn: 321585
* Remove redundant includes from lib/Transforms.Michael Zolotukhin2017-12-131-1/+0
| | | | llvm-svn: 320628
* loop-unroll: teach remapInstruction to update dbg.value intrinsics.Adrian Prantl2017-11-011-1/+15
| | | | | | | | Fixes PR35112. https://bugs.llvm.org/show_bug.cgi?id=35112 llvm-svn: 317138
* [LoopUnroll] Clean up remarks for unroll remainderDavid Green2017-10-311-24/+29
| | | | | | | | | | | | | | | | The optimisation remarks for loop unrolling with an unrolled remainder looks something like: test.c:7:18: remark: completely unrolled loop with 3 iterations [-Rpass=loop-unroll] C[i] += A[i*N+j]; ^ test.c:6:9: remark: unrolled loop by a factor of 4 with run-time trip count [-Rpass=loop-unroll] for(int j = 0; j < N; j++) ^ This removes the first of the two messages. Differential revision: https://reviews.llvm.org/D38725 llvm-svn: 316986
* Do not add discriminator encoding for debug intrinsics.Dehao Chen2017-10-261-2/+3
| | | | | | | | | | | | | | Summary: There are certain requirements for debug location of debug intrinsics, e.g. the scope of the DILocalVariable should be the same as the scope of its debug location. As a result, we should not add discriminator encoding for debug intrinsics. Reviewers: dblaikie, aprantl Reviewed By: aprantl Subscribers: JDevlieghere, aprantl, bjope, sanjoy, llvm-commits Differential Revision: https://reviews.llvm.org/D39343 llvm-svn: 316703
* [NFC] Convert OptimizationRemarkEmitter old emit() calls to new closureVivek Pandya2017-10-111-9/+13
| | | | | | | | | | | | | | parameterized emit() calls Summary: This is not functional change to adopt new emit() API added in r313691. Reviewed By: anemet Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D38285 llvm-svn: 315476
* Rename OptimizationDiagnosticInfo.* to OptimizationRemarkEmitter.*Adam Nemet2017-10-091-1/+1
| | | | | | | Sync it up with the name of the class actually defined here. This has been bothering me for a while... llvm-svn: 315249
* Use a BumpPtrAllocator for Loop objectsSanjoy Das2017-09-281-1/+1
| | | | | | | | | | | | | | | Summary: And now that we no longer have to explicitly free() the Loop instances, we can (with more ease) use the destructor of LoopBase to do what LoopBase::clear() was doing. Reviewers: chandlerc Subscribers: mehdi_amini, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D38201 llvm-svn: 314375
* Rename LoopUnrollStatus to LoopUnrollResult; NFCSanjoy Das2017-09-271-11/+11
| | | | | | A "Result" suffix is more appropriate here llvm-svn: 314350
* Rename markAsErased to erase, as pointed out in a previous review; NFCSanjoy Das2017-09-221-2/+2
| | | | llvm-svn: 313951
* Tighten the invariants around LoopBase::invalidateSanjoy Das2017-09-201-20/+18
| | | | | | | | | | | | | | | | | Summary: With this change: - Methods in LoopBase trip an assert if the receiver has been invalidated - LoopBase::clear frees up the memory held the LoopBase instance This change also shuffles things around as necessary to work with this stricter invariant. Reviewers: chandlerc Subscribers: mehdi_amini, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D38055 llvm-svn: 313708
* [LoopInfo] Make LoopBase and Loop destructors non-publicSanjoy Das2017-09-191-2/+2
| | | | | | | | | | | | | | | | | | | Summary: See comment for why I think this is a good idea. This change also: - Removes an SCEV test case. The SCEV test was not testing anything useful (most of it was `#if 0` ed out) and it would need to be updated to deal with a private ~Loop::Loop. - Updates the loop pass manager test case to deal with a private ~Loop::Loop. - Renames markAsRemoved to markAsErased to contrast with removeLoop, via the usual remove vs. erase idiom we already have for instructions and basic blocks. Reviewers: chandlerc Subscribers: mehdi_amini, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D37996 llvm-svn: 313695
* Allow ORE.emit to take a closure to delay building the remark objectAdam Nemet2017-09-191-8/+15
| | | | | | | | | | | In the lambda we are now returning the remark by value so we need to preserve its type in the insertion operator. This requires making the insertion operator generic. I've also converted a few cases to use the new API. It seems to work pretty well. See the LoopUnroller for a slightly more interesting case. llvm-svn: 313691
* [LoopUnroll] Properly update loop structure in case of successful peeling.Davide Italiano2017-08-281-2/+13
| | | | | | | | | | | When peeling kicks in, it updates the loop preheader. Later, a successful full unroll of the loop needs to update a PHI which i-th argument comes from the loop preheader, so it'd better look at the correct block. Fixes PR33437. Differential Revision: https://reviews.llvm.org/D37153 llvm-svn: 311922
* [LoopUnroll] Enable option to peel remainder loopSam Parker2017-08-141-2/+4
| | | | | | | | | | | | | | | | | | | | On some targets, the penalty of executing runtime unrolling checks and then not the unrolled loop can be significantly detrimental to performance. This results in the need to be more conservative with the unroll count, keeping a trip count of 2 reduces the overhead as well as increasing the chance of the unrolled body being executed. But being conservative leaves performance gains on the table. This patch enables the unrolling of the remainder loop introduced by runtime unrolling. This can help reduce the overhead of misunrolled loops because the cost of non-taken branches is much less than the cost of the backedge that would normally be executed in the remainder loop. This allows larger unroll factors to be used without suffering performance loses with smaller iteration counts. Differential Revision: https://reviews.llvm.org/D36309 llvm-svn: 310824
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-05-011-1/+1
| | | | | | This relands r301424. llvm-svn: 301812
* Kill off the old SimplifyInstruction API by converting remaining users.Daniel Berlin2017-04-281-1/+1
| | | | llvm-svn: 301673
* Reverts commit r301424, r301425 and r301426Sanjoy Das2017-04-261-1/+1
| | | | | | | | | | | | Commits were: "Use WeakVH instead of WeakTrackingVH in AliasSetTracker's UnkownInsts" "Add a new WeakVH value handle; NFC" "Rename WeakVH to WeakTrackingVH; NFC" The changes assumed pointers are 8 byte aligned on all architectures. llvm-svn: 301429
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-04-261-1/+1
| | | | | | | | | | | | | | | | Summary: I plan to use WeakVH to mean "nulls itself out on deletion, but does not track RAUW" in a subsequent commit. Reviewers: dblaikie, davide Reviewed By: davide Subscribers: arsenm, mehdi_amini, mcrosier, mzolotukhin, jfb, llvm-commits, nhaehnle Differential Revision: https://reviews.llvm.org/D32266 llvm-svn: 301424
* [LoopUnroll] Remove spurious newline.Davide Italiano2017-04-241-1/+0
| | | | | | | Eli pointed out in the review, but I didn't squash the two commits correctly. Pointy-hat to me. llvm-svn: 301241
* [LoopUnroll] Don't try to unroll non canonical loops.Davide Italiano2017-04-241-0/+15
| | | | | | | | | | | | The current Loop Unroll implementation works with loops having a single latch that contains a conditional branch to a block outside the loop (the other successor is, by defition of latch, the header). If this precondition doesn't hold, avoid unrolling the loop as the code is not ready to handle such circumstances. Differential Revision: https://reviews.llvm.org/D32261 llvm-svn: 301239
* The patch turns on epilogue unroll for loops with constant recurency start.Evgeny Stupachenko2017-03-021-1/+44
| | | | | | | | | | | | | | | | | Summary: Set unroll remainder to epilog if a loop contains a phi with constant parameter: loop: pn = phi [Const, PreHeader], [pn.next, Latch] ... Reviewer: hfinkel Differential Revision: http://reviews.llvm.org/D27004 From: Evgeny Stupachenko <evstupac@gmail.com> llvm-svn: 296770
* Encode duplication factor from loop vectorization and loop unrolling to ↵Dehao Chen2017-02-101-0/+7
| | | | | | | | | | | | | | | | | | | | | discriminator. Summary: This patch starts the implementation as discuss in the following RFC: http://lists.llvm.org/pipermail/llvm-dev/2016-October/106532.html When optimization duplicates code that will scale down the execution count of a basic block, we will record the duplication factor as part of discriminator so that the offline process tool can find the duplication factor and collect the accurate execution frequency of the corresponding source code. Two important optimization that fall into this category is loop vectorization and loop unroll. This patch records the duplication factor for these 2 optimizations. The recording will be guarded by a flag encode-duplication-in-discriminators, which is off by default. Reviewers: probinson, aprantl, davidxl, hfinkel, echristo Reviewed By: hfinkel Subscribers: mehdi_amini, anemet, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D26420 llvm-svn: 294782
* NFC: [LoopUnroll] More meaningful message in tracingAnna Thomas2017-02-031-1/+1
| | | | llvm-svn: 294017
* Shut up another GCC warning about operator precedence. NFC.Michael Kuperstein2017-02-011-1/+1
| | | | llvm-svn: 293812
* [LoopUnroll] Use addClonedBlockToLoopInfo to add loop header to LI (NFC).Florian Hahn2017-02-011-11/+8
| | | | | | | | | | | | | | | | | | | | Summary: I have a similar patch up for review already (D29173). If you prefer I can squash them both together. Also I think there more potential for code sharing between LoopUnroll.cpp and LoopUnrollRuntime.cpp. Do you think patches for that would be worthwhile? Reviewers: mkuper, mzolotukhin Reviewed By: mkuper, mzolotukhin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29311 llvm-svn: 293758
* NFC: Add debug tracing for more cases where loop unrolling fails.Anna Thomas2017-01-271-2/+8
| | | | llvm-svn: 293313
* [LoopUnroll] Properly update loopinfo for runtime unrolling by 2Michael Kuperstein2017-01-261-4/+7
| | | | | | | | | | | Even when we don't create a remainder loop (that is, when we unroll by 2), we may duplicate nested loops into the remainder. This is complicated by the fact the remainder may itself be either inserted into an outer loop, or at the top level. In the latter case, we may need to create new top-level loops. Differential Revision: https://reviews.llvm.org/D29156 llvm-svn: 293124
* [LoopUnroll] First form LCSSA, then loop-simplifyMichael Kuperstein2017-01-231-18/+17
| | | | | | | | | | | | | Running non-LCSSA-preserving LoopSimplify followed by LCSSA on (roughly) the same loop is incorrect, since LoopSimplify may break LCSSA arbitrarily higher in the loop nest. Instead, run LCSSA first, and then run LCSSA-preserving LoopSimplify on the result. This fixes PR31718. Differential Revision: https://reviews.llvm.org/D29055 llvm-svn: 292854
* [PM] Sink an LCSSA preservation assert from the LoopSimplify pass intoChandler Carruth2017-01-211-2/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | the library routine shared with the new PM and other code. This assert checks that when LCSSA preservation is requested we start in LCSSA form. Without this early assert, given *very* complex test cases we can hit an assert or crash much later on when trying to preserve LCSSA. The new PM's loop simplify doesn't need to (and indeed can't) preserve LCSSA as the new PM doesn't deal in transforms in the dependency graph. But we asked the library to and shockingly, this didn't work very well! Stop doing that. Now the assert will tell us immediately with existing test cases. Before this, it took a pretty convoluted input to trigger this. However, sinking the assert also found a bug in LoopUnroll where we asked simplifyLoop to preserve LCSSA *right before we reform it*. That's kinda silly and unsurprising that it wasn't available. =D Stop doing that too. We also would assert that the unrolled loop was in LCSSA even if preserving LCSSA was never requested! I don't have a test case or anything here. I spotted it by inspection and it seems quite obvious. No logic change anyways, that's just avoiding a spurrious assert. llvm-svn: 292710
* Preserve domtree and loop-simplify for runtime unrolling.Eli Friedman2017-01-181-16/+40
| | | | | | | | | | | | | | | | | Mostly straightforward changes; we just didn't do the computation before. One sort of interesting change in LoopUnroll.cpp: we weren't handling dominance for children of the loop latch correctly, but foldBlockIntoPredecessor hid the problem for complete unrolling. Currently punting on loop peeling; made some minor changes to isolate that problem to LoopUnrollPeel.cpp. Adds a flag -unroll-verify-domtree; it verifies the domtree immediately after we finish updating it. This is on by default for +Asserts builds. Differential Revision: https://reviews.llvm.org/D28073 llvm-svn: 292447
* [loop-unroll] Factor out code to update LoopInfo (NFC).Florian Hahn2017-01-101-17/+33
| | | | | | | | Move the code to update LoopInfo for cloned basic blocks to addClonedBlockToLoopInfo, as suggested in https://reviews.llvm.org/D28482. llvm-svn: 291614
* Add a comment for a todo in LoopUnroll post cleanupPhilip Reames2016-12-301-0/+5
| | | | llvm-svn: 290769
* [LoopUnroll] Modify a comment to clarify the usage of TripCount. NFC.Haicheng Wu2016-12-201-8/+8
| | | | | | | | | Make it clear that TripCount is the upper bound of the iteration on which control exits LatchBlock. Differential Revision: https://reviews.llvm.org/D26675 llvm-svn: 290199
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-5/+12
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Remove the AssumptionCacheHal Finkel2016-12-151-12/+5
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* [LoopUnroll] Implement profile-based loop peelingMichael Kuperstein2016-11-301-10/+26
| | | | | | | | | | | | | | | | | | | This implements PGO-driven loop peeling. The basic idea is that when the average dynamic trip-count of a loop is known, based on PGO, to be low, we can expect a performance win by peeling off the first several iterations of that loop. Unlike unrolling based on a known trip count, or a trip count multiple, this doesn't save us the conditional check and branch on each iteration. However, it does allow us to simplify the straight-line code we get (constant-folding, etc.). This is important given that we know that we will usually only hit this code, and not the actual loop. This is currently disabled by default. Differential Revision: https://reviews.llvm.org/D25963 llvm-svn: 288274
* [LoopUnroll] Keep the loop test only on the first iteration of max-or-zero loopsJohn Brawn2016-10-211-6/+7
| | | | | | | | | | | | | | | | When we have a loop with a known upper bound on the number of iterations, and furthermore know that either the number of iterations will be either exactly that upper bound or zero, then we can fully unroll up to that upper bound keeping only the first loop test to check for the zero iteration case. Most of the work here is in plumbing this 'max-or-zero' information from the part of scalar evolution where it's detected through to loop unrolling. I've also gone for the safe default of 'false' everywhere but howManyLessThans which could probably be improved. Differential Revision: https://reviews.llvm.org/D25682 llvm-svn: 284818
OpenPOWER on IntegriCloud