summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/Analysis/LoopInfoTest.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Rename LoopInfo::isRotated() to LoopInfo::isRotatedForm().Kit Barton2019-12-121-17/+17
| | | | | | This patch renames the LoopInfo::isRotated() method to LoopInfo::isRotatedForm() to make it clear that the method checks whether the loop is in rotated form, not whether the loop has been rotated by the LoopRotation pass.
* [Loop] Add isRotated method to Loop class.Kit Barton2019-12-111-0/+55
| | | | | | | | | | | | | | | | | | Summary: This patch adds a method to determine if a loop is in rotated form (the latch is an exiting block). It also modifies the getLoopGuardBranch method to use this new method. This method can also be used in Loopfusion. Once this patch lands I will make the corresponding changes there. Reviewers: jdoerfert, Meinersbur, dmgreen, etiotto, Whitney, fhahn, hfinkel Reviewed By: Meinersbur Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65958
* [LOOPGUARD] Remove asserts in getLoopGuardBranchWhitney Tsang2019-10-061-0/+85
| | | | | | | | | | | | | Summary: The assertion in getLoopGuardBranch can be a 'return nullptr' under if condition. Authored By: DTharun Reviewer: Whitney, fhahn Reviewed By: Whitney, fhahn Subscribers: fhahn, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D66084 llvm-svn: 373857
* [LOOPGUARD] Disable loop with multiple loop exiting blocks.Whitney Tsang2019-09-261-0/+120
| | | | | | | | | | | | | | | | | | | | Summary: As discussed in the loop group meeting. With the current definition of loop guard, we should not allow multiple loop exiting blocks. For loops that has multiple loop exiting blocks, we can simply unable to find the loop guard. When getUniqueExitBlock() obtains a vector size not equals to one, that means there is either no exit blocks or there exists more than one unique block the loop exit to. If we don't disallow loop with multiple loop exit blocks, then with our current implementation, there can exist exit blocks don't post dominated by the non pre-header successor of the guard block. Reviewer: reames, Meinersbur, kbarton, etiotto, bmahjour Reviewed By: Meinersbur, kbarton Subscribers: fhahn, hiraditya, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D66529 llvm-svn: 373011
* [LOOPINFO] Introduce the loop guard API.Whitney Tsang2019-07-251-61/+102
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This is the first patch for the loop guard. We introduced getLoopGuardBranch() and isGuarded(). This currently only works on simplified loop, as it requires a preheader and a latch to identify the guard. It will work on loops of the form: /// GuardBB: /// br cond1, Preheader, ExitSucc <== GuardBranch /// Preheader: /// br Header /// Header: /// ... /// br Latch /// Latch: /// br cond2, Header, ExitBlock /// ExitBlock: /// br ExitSucc /// ExitSucc: Prior discussions leading upto the decision to introduce the loop guard API: http://lists.llvm.org/pipermail/llvm-dev/2019-May/132607.html Reviewer: reames, kbarton, hfinkel, jdoerfert, Meinersbur, dmgreen Reviewed By: reames Subscribers: wuzish, hiraditya, jsji, llvm-commits, bmahjour, etiotto Tag: LLVM Differential Revision: https://reviews.llvm.org/D63885 llvm-svn: 367033
* [LoopInfo] Fix getUniqueNonLatchExitBlocksSerguei Katkov2019-07-171-0/+43
| | | | | | | | | | | | | | | | | | | | | | | | It is possible that exit block has two predecessors and one of them is a latch block while another is not. Current algorithm is based on the assumption that all exits are dedicated and therefore we can check only first predecessor of loop exit to find all unique exits. However if we do not consider latch block and it is first predecessor of some exit then this exit will be found. Regression test is added. As a side effect of algorithm re-writing, the restriction that all exits are dedicated is eliminated. Reviewers: reames, fhahn, efriedma Reviewed By: efriedma Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D64787 llvm-svn: 366294
* [LoopInfo] Introduce getUniqueNonLatchExitBlocks utility functionSerguei Katkov2019-07-151-0/+46
| | | | | | | | | | | | Extract the code from LoopUnrollRuntime into utility function to re-use it in D63923. Reviewers: reames, mkuper Reviewed By: reames Subscribers: fhahn, hiraditya, zzheng, dmgreen, llvm-commits Differential Revision: https://reviews.llvm.org/D64548 llvm-svn: 366040
* [LOOPINFO] Extend Loop object to add utilities to get the loop bounds,Whitney Tsang2019-06-051-0/+900
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | step, and loop induction variable. Summary: This PR extends the loop object with more utilities to get loop bounds, step, and loop induction variable. There already exists passes which try to obtain the loop induction variable in their own pass, e.g. loop interchange. It would be useful to have a common area to get these information. /// Example: /// for (int i = lb; i < ub; i+=step) /// <loop body> /// --- pseudo LLVMIR --- /// beforeloop: /// guardcmp = (lb < ub) /// if (guardcmp) goto preheader; else goto afterloop /// preheader: /// loop: /// i1 = phi[{lb, preheader}, {i2, latch}] /// <loop body> /// i2 = i1 + step /// latch: /// cmp = (i2 < ub) /// if (cmp) goto loop /// exit: /// afterloop: /// /// getBounds /// getInitialIVValue --> lb /// getStepInst --> i2 = i1 + step /// getStepValue --> step /// getFinalIVValue --> ub /// getCanonicalPredicate --> '<' /// getDirection --> Increasing /// getInductionVariable --> i1 /// getAuxiliaryInductionVariable --> {i1} /// isCanonical --> false Reviewers: kbarton, hfinkel, dmgreen, Meinersbur, jdoerfert, syzaara, fhahn Reviewed By: kbarton Subscribers: tvvikram, bmahjour, etiotto, fhahn, jsji, hiraditya, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D60565 llvm-svn: 362644
* Revert "Title: [LOOPINFO] Extend Loop object to add utilities to get the loop"Whitney Tsang2019-06-051-900/+0
| | | | | | This reverts commit d34797dfc26c61cea19f45669a13ea572172ba34. llvm-svn: 362615
* Title: [LOOPINFO] Extend Loop object to add utilities to get the loopWhitney Tsang2019-06-051-0/+900
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | bounds, step, and loop induction variable. Summary: This PR extends the loop object with more utilities to get loop bounds, step, and loop induction variable. There already exists passes which try to obtain the loop induction variable in their own pass, e.g. loop interchange. It would be useful to have a common area to get these information. /// Example: /// for (int i = lb; i < ub; i+=step) /// <loop body> /// --- pseudo LLVMIR --- /// beforeloop: /// guardcmp = (lb < ub) /// if (guardcmp) goto preheader; else goto afterloop /// preheader: /// loop: /// i1 = phi[{lb, preheader}, {i2, latch}] /// <loop body> /// i2 = i1 + step /// latch: /// cmp = (i2 < ub) /// if (cmp) goto loop /// exit: /// afterloop: /// /// getBounds /// getInitialIVValue --> lb /// getStepInst --> i2 = i1 + step /// getStepValue --> step /// getFinalIVValue --> ub /// getCanonicalPredicate --> '<' /// getDirection --> Increasing /// getInductionVariable --> i1 /// getAuxiliaryInductionVariable --> {i1} /// isCanonical --> false Reviewers: kbarton, hfinkel, dmgreen, Meinersbur, jdoerfert, syzaara, fhahn Reviewed By: kbarton Subscribers: tvvikram, bmahjour, etiotto, fhahn, jsji, hiraditya, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D60565 llvm-svn: 362609
* Revert [LOOPINFO] Extend Loop object to add utilities to get the loop ↵Kit Barton2019-05-231-900/+0
| | | | | | | | bounds, step, induction variable, and guard branch. This reverts r361517 (git commit 2049e4dd8f61100f88f14db33bd95d197bcbfbbc) llvm-svn: 361553
* [LOOPINFO] Extend Loop object to add utilities to get the loop bounds, ↵Kit Barton2019-05-231-0/+900
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | step, induction variable, and guard branch. Summary: This PR extends the loop object with more utilities to get loop bounds, step, induction variable, and guard branch. There already exists passes which try to obtain the loop induction variable in their own pass, e.g. loop interchange. It would be useful to have a common area to get these information. Moreover, loop fusion (https://reviews.llvm.org/D55851) is planning to use getGuard() to extend the kind of loops it is able to fuse, e.g. rotated loop with non-constant upper bound, which would have a loop guard. /// Example: /// for (int i = lb; i < ub; i+=step) /// <loop body> /// --- pseudo LLVMIR --- /// beforeloop: /// guardcmp = (lb < ub) /// if (guardcmp) goto preheader; else goto afterloop /// preheader: /// loop: /// i1 = phi[{lb, preheader}, {i2, latch}] /// <loop body> /// i2 = i1 + step /// latch: /// cmp = (i2 < ub) /// if (cmp) goto loop /// exit: /// afterloop: /// /// getBounds /// getInitialIVValue --> lb /// getStepInst --> i2 = i1 + step /// getStepValue --> step /// getFinalIVValue --> ub /// getCanonicalPredicate --> '<' /// getDirection --> Increasing /// getGuard --> if (guardcmp) goto loop; else goto afterloop /// getInductionVariable --> i1 /// getAuxiliaryInductionVariable --> {i1} /// isCanonical --> false Committed on behalf of @Whitney (Whitney Tsang). Reviewers: kbarton, hfinkel, dmgreen, Meinersbur, jdoerfert, syzaara, fhahn Reviewed By: kbarton Subscribers: tvvikram, bmahjour, etiotto, fhahn, jsji, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D60565 llvm-svn: 361517
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* [LoopInfo][FIX] Remove leftover dump in unit testJohannes Doerfert2018-09-111-1/+0
| | | | llvm-svn: 341968
* [LoopInfo] Fix Loop::getLoopID() for loops with multiple latchesJohannes Doerfert2018-09-111-0/+56
| | | | | | | | The previous implementation traversed all loop blocks and bailed if one was not a latch block. Since we are only interested in latch blocks, we should only traverse those. llvm-svn: 341926
* [LoopInfo] Add helper methods to compute two useful orderings of theChandler Carruth2017-01-201-0/+75
| | | | | | | | | | | | | | | | | | | | | | loops in a function. These are relatively confusing to talk about and compute correctly so it seems really good to write down their implementation in one place. I've replaced one place we needed this in the loop PM infrastructure and I have another place in a pending patch that wants it. We can't quite use this for the core loop PM walk because there we're sometimes working on a sub-forest. I'll add the expected unittests before committing this but wanted to make sure folks were happy with these names / comments. Credit goes to Richard Smith for the idea for naming the order where siblings are in reverse program order but the tree traversal remains preorder. Differential Revision: https://reviews.llvm.org/D28932 llvm-svn: 292569
* Refactor out LoopInfo computation so that it can be used byXin Tong2017-01-171-41/+48
| | | | | | | | | | | | | | | | | | other test cases. Summary: Refactor out LoopInfo computation so that it can be used by other test cases. So i am changing this test proactively for later commit, which will use this function. Reviewers: sanjoy, hfinkel Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28778 llvm-svn: 292250
* Empty line. NFC.Xin Tong2017-01-151-1/+0
| | | | llvm-svn: 292081
* Use getLoopLatch in place of isLoopSimplifyFormXin Tong2017-01-151-0/+77
Summary: Use getLoopLatch in place of isLoopSimplifyForm. we do not need to know whether the loop has a preheader nor dedicated exits. Reviewers: hfinkel, sanjoy, atrick, mkuper Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D28724 llvm-svn: 292078
OpenPOWER on IntegriCloud