summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/LoopInterchange/phi-ordering.ll
Commit message (Collapse)AuthorAgeFilesLines
* [LoopInterchange] Properly move condition, induction increment and ops to latch.Florian Hahn2019-09-111-4/+6
| | | | | | | | | | | | | | | | | | | | | | | Currently we only rely on the induction increment to come before the condition to ensure the required instructions get moved to the new latch. This patch duplicates and moves the required instructions to the newly created latch. We move the condition to the end of the new block, then process its operands. We stop at operands that are defined outside the loop, or are the induction PHI. We duplicate the instructions and update the uses in the moved instructions, to ensure other users remain intact. See the added test2 for such an example. Reviewers: efriedma, mcrosier Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D67367 llvm-svn: 371595
* Revert "Temporarily Revert "Add basic loop fusion pass.""Eric Christopher2019-04-171-0/+94
| | | | | | | | The reversion apparently deleted the test/Transforms directory. Will be re-reverting again. llvm-svn: 358552
* Temporarily Revert "Add basic loop fusion pass."Eric Christopher2019-04-171-94/+0
| | | | | | | | As it's causing some bot failures (and per request from kbarton). This reverts commit r358543/ab70da07286e618016e78247e4a24fcb84077fda. llvm-svn: 358546
* [LoopInterchange] Remove support for inner-only reductions.Florian Hahn2018-11-011-13/+5
| | | | | | | | | | | | | | | | | | | | | | Inner-loop only reductions require additional checks to make sure they form a load-phi-store cycle across inner and outer loop. Otherwise the reduction value is not properly preserved. This patch disables interchanging such loops for now, as it causes miscompiles in some cases and it seems to apply only for a tiny amount of loops. Across the test-suite, SPEC2000 and SPEC2006, 61 instead of 62 loops are interchange with inner loop reduction support disabled. With -loop-interchange-threshold=-1000, 3256 instead of 3267. See the discussion and history of D53027 for an outline of how such legality checks could look like. Reviewers: efriedma, mcrosier, davide Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D53027 llvm-svn: 345877
* [LoopInterchange] Preserve LCSSA.Florian Hahn2018-09-261-1/+1
| | | | | | | | | | | | | | | | | | This patch extends LoopInterchange to move LCSSA to the right place after interchanging. This is required for LoopInterchange to become a function pass. An alternative to the manual moving of the PHIs, we could also re-form the LCSSA phis for a set of interchanged loops, but that's more expensive. Reviewers: efriedma, mcrosier, davide Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D52154 llvm-svn: 343132
* [LoopInterchange] Preserve ScalarEvolution, by forgetting about interchanged ↵Florian Hahn2018-09-141-1/+1
| | | | | | | | | | | | | | | | | | | | | | loops. As preparation for LoopInterchange becoming a loop pass, it needs to preserve ScalarEvolution. Even though interchanging should not change the trip count of the loop, it modifies loop entry, latch and exit blocks. I added -verify-scev to some loop interchange tests, but the verification does not catch problems caused by missing invalidation of SE in loop interchange, as the trip counts themselves do not change. So there might be potential to make the SE verification covering more stuff in the future. Reviewers: mkazantsev, efriedma, karthikthecool Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D52026 llvm-svn: 342209
* [LoopInterchange] Preserve LoopInfo after interchanging.Florian Hahn2018-04-051-1/+1
| | | | | | | | | | | | | | LoopInterchange relies on LoopInfo being up-to-date, so we should preserve it after interchanging. This patch updates restructureLoops to move the BBs of the interchanged loops to the right place. Reviewers: davide, efriedma, karthikthecool, mcrosier Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D45278 llvm-svn: 329264
* [LoopInterchange] Update tests so DA can handle access after D35430.Florian Hahn2018-04-031-43/+79
| | | | | | | | | | | | | | | I have taken the opportunity to simplify some tests slightly and move parts around. It also brings back a few IR checks for interchangable loops. Reviewers: karthikthecool, sebpop, grosser Reviewed By: sebpop Differential Revision: https://reviews.llvm.org/D45207 llvm-svn: 329081
* DA: remove uses of GEP, only ask SCEVSebastian Pop2018-03-061-28/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | It's been quite some time the Dependence Analysis (DA) is broken, as it uses the GEP representation to "identify" multi-dimensional arrays. It even wrongly detects multi-dimensional arrays in single nested loops: from test/Analysis/DependenceAnalysis/Coupled.ll, example @couple6 ;; for (long int i = 0; i < 50; i++) { ;; A[i][3*i - 6] = i; ;; *B++ = A[i][i]; DA used to detect two subscripts, which makes no sense in the LLVM IR or in C/C++ semantics, as there are no guarantees as in Fortran of subscripts not overlapping into a next array dimension: maximum nesting levels = 1 SrcPtrSCEV = %A DstPtrSCEV = %A using GEPs subscript 0 src = {0,+,1}<nuw><nsw><%for.body> dst = {0,+,1}<nuw><nsw><%for.body> class = 1 loops = {1} subscript 1 src = {-6,+,3}<nsw><%for.body> dst = {0,+,1}<nuw><nsw><%for.body> class = 1 loops = {1} Separable = {} Coupled = {1} With the current patch, DA will correctly work on only one dimension: maximum nesting levels = 1 SrcSCEV = {(-2424 + %A)<nsw>,+,1212}<%for.body> DstSCEV = {%A,+,404}<%for.body> subscript 0 src = {(-2424 + %A)<nsw>,+,1212}<%for.body> dst = {%A,+,404}<%for.body> class = 1 loops = {1} Separable = {0} Coupled = {} This change removes all uses of GEP from DA, and we now only rely on the SCEV representation. The patch does not turn on -da-delinearize by default, and so the DA analysis will be more conservative in the case of multi-dimensional memory accesses in nested loops. I disabled some interchange tests, as the DA is not able to disambiguate the dependence anymore. To make DA stronger, we may need to compute a bound on the number of iterations based on the access functions and array dimensions. The patch cleans up all the CHECKs in test/Transforms/LoopInterchange/*.ll to avoid checking for snippets of LLVM IR: this form of checking is very hard to maintain. Instead, we now check for output of the pass that are more meaningful than dozens of lines of LLVM IR. Some tests now require -debug messages and thus only enabled with asserts. Patch written by Sebastian Pop and Aditya Kumar. Differential Revision: https://reviews.llvm.org/D35430 llvm-svn: 326837
* [LoopInterchange] Incrementally update the dominator tree.Florian Hahn2018-02-141-1/+1
| | | | | | | | | | | | | We can use incremental dominator tree updates to avoid re-calculating the dominator tree after interchanging 2 loops. Reviewers: dmgreen, kuhar Reviewed By: kuhar Differential Revision: https://reviews.llvm.org/D43176 llvm-svn: 325122
* [LoopInterchange] Fix phi node ordering miscompile.David Green2017-10-211-0/+90
The way that splitInnerLoopHeader splits blocks requires that the induction PHI will be the first PHI in the inner loop header. This makes sure that is actually the case when there are both IV and reduction phis. Differential Revision: https://reviews.llvm.org/D38682 llvm-svn: 316261
OpenPOWER on IntegriCloud