summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/NaryReassociate
Commit message (Collapse)AuthorAgeFilesLines
* Revert "Temporarily Revert "Add basic loop fusion pass.""Eric Christopher2019-04-178-0/+489
| | | | | | | | 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-178-489/+0
| | | | | | | | As it's causing some bot failures (and per request from kbarton). This reverts commit r358543/ab70da07286e618016e78247e4a24fcb84077fda. llvm-svn: 358546
* [NaryReassociate] Detect deleted instr with WeakVHKarl-Johan Karlsson2018-05-241-0/+29
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: If NaryReassociate succeed it will, when replacing the old instruction with the new instruction, also recursively delete trivially dead instructions from the old instruction. However, if the input to the NaryReassociate pass contain dead code it is not save to recursively delete trivially deadinstructions as it might lead to deleting the newly created instruction. This patch will fix the problem by using WeakVH to detect this rare case, when the newly created instruction is dead, and it will then restart the basic block iteration from the beginning. This fixes pr37539 Reviewers: tra, meheff, grosser, sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D47139 llvm-svn: 333155
* Add early exit on reassociation of 0 expression.Evgeny Stupachenko2018-03-071-0/+19
| | | | | | | | | | | | | | Summary: Before the patch a try to reassociate ((v * 16) * 0) * 1 fall into infinite loop Reviewers: pankajchawla Differential Revision: http://reviews.llvm.org/D41467 From: Evgeny Stupachenko <evstupac@gmail.com> <evgeny.v.stupachenko@intel.com> llvm-svn: 326861
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-2/+2
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Make processing @llvm.assume more efficient by using operand bundlesHal Finkel2016-12-151-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | There was an efficiency problem with how we processed @llvm.assume in ValueTracking (and other places). The AssumptionCache tracked all of the assumptions in a given function. In order to find assumptions relevant to computing known bits, etc. we searched every assumption in the function. For ValueTracking, that means that we did O(#assumes * #values) work in InstCombine and other passes (with a constant factor that can be quite large because we'd repeat this search at every level of recursion of the analysis). Several of us discussed this situation at the last developers' meeting, and this implements the discussed solution: Make the values that an assume might affect operands of the assume itself. To avoid exposing this detail to frontends and passes that need not worry about it, I've used the new operand-bundle feature to add these extra call "operands" in a way that does not affect the intrinsic's signature. I think this solution is relatively clean. InstCombine adds these extra operands based on what ValueTracking, LVI, etc. will need and then those passes need only search the users of the values under consideration. This should fix the computational-complexity problem. At this point, no passes depend on the AssumptionCache, and so I'll remove that as a follow-up change. Differential Revision: https://reviews.llvm.org/D27259 llvm-svn: 289755
* [PM] Port NaryReassociate to the new PMWei Mi2016-07-215-0/+5
| | | | | | Differential Revision: https://reviews.llvm.org/D22648 llvm-svn: 276349
* [NaryReassociate] allow candidate to have a different typeJingyue Wu2015-12-181-0/+17
| | | | | | | | | | | | | | | | Summary: If Candiadte may have a different type from GEP, we should bitcast or pointer cast it to GEP's type so that the later RAUW doesn't complain. Added a test in nary-gep.ll Reviewers: tra, meheff Subscribers: mcrosier, llvm-commits, jholewinski Differential Revision: http://reviews.llvm.org/D15618 llvm-svn: 256035
* [NaryReassociate] SeenExprs records WeakVHJingyue Wu2015-10-011-0/+14
| | | | | | | | | | | | | | | | Summary: The instructions SeenExprs records may be deleted during rewriting. FindClosestMatchingDominator should ignore these deleted instructions. Fixes PR24301. Reviewers: grosser Subscribers: grosser, llvm-commits Differential Revision: http://reviews.llvm.org/D13315 llvm-svn: 248983
* [NaryReassociate] Improve test CHECKMehdi Amini2015-09-162-3/+6
| | | | | | | | | | | Add `CHECK` directives for the function calls. Differential Revision: http://reviews.llvm.org/D12885 Patch by: Volkan Keles <vkeles@apple.com> From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 247774
* [NaryReassociate] Add support for Mul instructionsMarcello Maggioni2015-09-151-0/+18
| | | | | | | | | This patch extends the current pass by handling Mul instructions as well. Patch by: Volkan Keles (vkeles@apple.com) llvm-svn: 247705
* [NaryReassociate] enhances nsw by leveraging @llvm.assumeJingyue Wu2015-07-011-0/+36
| | | | | | | | | | | | | | | | | | | | | Summary: nsw are flaky and can often be removed by optimizations. This patch enhances nsw by leveraging @llvm.assume in the IR. Specifically, NaryReassociate now understands that assume(a + b >= 0) && assume(a >= 0) ==> a +nsw b As a result, it can split more sext(a + b) into sext(a) + sext(b) for CSE. Test Plan: nary-gep.ll Reviewers: broune, meheff Subscribers: jholewinski, llvm-commits Differential Revision: http://reviews.llvm.org/D10822 llvm-svn: 241139
* [NaryReassociate] Run EarlyCSE after NaryReassociateJingyue Wu2015-05-281-9/+22
| | | | | | | | | | | | | | | | | | | | | | | Summary: This patch made two improvements to NaryReassociate and the NVPTX pipeline 1. Run EarlyCSE/GVN after NaryReassociate to get rid of redundant common expressions. 2. When adding an instruction to SeenExprs, maps both the SCEV before and after reassociation to that instruction. Test Plan: updated @reassociate_gep_nsw in nary-gep.ll Reviewers: meheff, broune Reviewed By: broune Subscribers: dberlin, jholewinski, llvm-commits Differential Revision: http://reviews.llvm.org/D9947 llvm-svn: 238396
* [NaryReassoc] reassociate GEP for CSEJingyue Wu2015-05-211-0/+77
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: x = &a[i]; y = &a[i + j]; => y = x + j; along with some refactoring work such as extracting method findClosestMatchingDominator. Depends on D9786 which provides the ScalarEvolution::getGEPExpr interface. Test Plan: nary-gep.ll Reviewers: meheff, broune Reviewed By: broune Subscribers: jholewinski, llvm-commits Differential Revision: http://reviews.llvm.org/D9802 llvm-svn: 237971
* [NaryReassociate] avoid running foreverJingyue Wu2015-05-131-0/+11
| | | | | | | | | Avoid running forever by checking we are not reassociating an expression into the same form. Tested with @avoid_infinite_loops in nary-add.ll llvm-svn: 237269
* Resurrect r235688Jingyue Wu2015-04-242-0/+49
| | | | | | | | We should skip vector types which are not SCEVable. test/CodeGen/NVPTX/sched2.ll passes llvm-svn: 235695
* Revert r235688Jingyue Wu2015-04-242-49/+0
| | | | | | Seems breaking builds llvm-svn: 235690
* [NVPTX] enable NaryReassociate in NVPTXJingyue Wu2015-04-242-0/+49
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: We run NaryReassociate right after SLSR because SLSR enables many opportunities for NaryReassociate. For example, in nary-slsr.ll foo((a + b) + c); foo((a + b * 2) + c); foo((a + b * 3) + c); // 2 muls and 6 adds after SLSR: ab = a + b; foo(ab + c); ab2 = ab + b; foo(ab2 + c); ab3 = ab2 + b; foo(ab3 + c); // 6 adds after NaryReassociate: abc = (a + b) + c; foo(abc); ab2c = abc + b; foo(ab2c); ab3c = ab2c + b; foo(ab3c); // 4 adds Test Plan: nary-slsr.ll Reviewers: jholewinski, eliben Reviewed By: eliben Subscribers: jholewinski, llvm-commits Differential Revision: http://reviews.llvm.org/D9066 llvm-svn: 235688
* [NaryReassociate] run NaryReassociate iterativelyJingyue Wu2015-04-171-2/+22
| | | | | | | | | | | | | | | | | | | | | | | Summary: An alternative is to use a worklist approach. However, that approach would break the traversing order so that we couldn't lookup SeenExprs efficiently. I don't see a clear winner here, so I picked the easier approach. Along with two minor improvements: 1. preserves ScalarEvolution by forgetting instructions replaced 2. removes dead code locally avoiding the need of running DCE afterwards Test Plan: add to slsr-add.ll a test that requires multiple iterations Reviewers: broune, dberlin, atrick, meheff Reviewed By: atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9058 llvm-svn: 235151
* [NaryReassociate] speeds up candidate searchingJingyue Wu2015-04-161-1/+52
| | | | | | | | | | | | | | | | | | | | | Summary: This fixes a left-over efficiency issue in D8950. As Andrew and Daniel suggested, we can store the candidates in a stack and pop the top element when it does not dominate the current instruction. This reduces the worst-case time complexity to O(n). Test Plan: a new test in nary-add.ll that exercises this optimization. Reviewers: broune, dberlin, meheff, atrick Reviewed By: atrick Subscribers: llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D9055 llvm-svn: 235129
* Simplify n-ary adds by reassociationJingyue Wu2015-04-141-0/+127
Summary: This transformation reassociates a n-ary add so that the add can partially reuse existing instructions. For example, this pass can simplify void foo(int a, int b) { bar(a + b); bar((a + 2) + b); } to void foo(int a, int b) { int t = a + b; bar(t); bar(t + 2); } saving one add instruction. Fixes PR22357 (https://llvm.org/bugs/show_bug.cgi?id=22357). Test Plan: nary-add.ll Reviewers: broune, dberlin, hfinkel, meheff, sanjoy, atrick Reviewed By: sanjoy, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8950 llvm-svn: 234855
OpenPOWER on IntegriCloud