summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/Reassociate
Commit message (Collapse)AuthorAgeFilesLines
* [PatternMatch] Handle undef vectors consistentlySanjay Patel2018-11-201-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | This patch fixes the issue noticed in D54532. The problem is that cst_pred_ty-based matchers like m_Zero() currently do not match scalar undefs (as expected), but *do* match vector undefs. This may lead to optimization inconsistencies in rare cases. There is only one existing test for which output changes, reverting the change from D53205. The reason here is that vector fsub undef, %x is no longer matched as an m_FNeg(). While I think that the new output is technically worse than the previous one, it is consistent with scalar, and I don't think it's really important either way (generally that undef should have been folded away prior to reassociation.) I've also added another test case for this issue based on InstructionSimplify. It took some effort to find that one, as in most cases undef folds are either checked first -- and in the cases where they aren't it usually happens to not make a difference in the end. This is the only case I was able to come up with. Prior to this patch the test case simplified to undef in the scalar case, but zeroinitializer in the vector case. Patch by: @nikic (Nikita Popov) Differential Revision: https://reviews.llvm.org/D54631 llvm-svn: 347318
* [FPEnv] Convert more BinaryOperator::isFNeg(...) to m_FNeg(...)Cameron McInally2018-10-241-2/+2
| | | | | | | | This work is to avoid regressions when we seperate FNeg from the FSub IR instruction. Differential Revision: https://reviews.llvm.org/D53205 llvm-svn: 345146
* [Reassociate] replace fake binop queries with 'match' APISanjay Patel2018-10-232-7/+3
| | | | | | | | | | | | | | | | | We need to update this code before introducing an 'fneg' instruction in IR, so we might as well kill off the integer neg/not queries too. This is no-functional-change-intended for scalar code and most vector code. For vectors, we can see that the 'match' API allows for undef elements in constants, so we optimize those cases better. Ideally, there would be a test for each code diff, but I don't see evidence of that for the existing code, so I didn't try very hard to come up with new vector tests for each code change. Differential Revision: https://reviews.llvm.org/D53533 llvm-svn: 345042
* [Reassociate] remove bogus tests; NFCSanjay Patel2018-10-221-28/+0
| | | | | | | | I was trying to provide test coverage for D53533 with rL344964, but these don't do it...and I don't think they add any value, so deleting. llvm-svn: 344969
* [Reassociate] add vector tests with undef elements; NFCSanjay Patel2018-10-223-43/+107
| | | | | | | | Also, regenerate checks for these files. We should do better on the vector tests by using the PatternMatch API instead of BinaryOperator::isNot/isNeg. llvm-svn: 344964
* revert r341288 - [Reassociate] swap binop operands to increase factoring ↵Sanjay Patel2018-09-121-45/+35
| | | | | | | | potential This causes or exposes indeterminism that is visible in the output of -reassociate. llvm-svn: 342083
* [Reassociate] swap binop operands to increase factoring potentialSanjay Patel2018-09-021-35/+45
| | | | | | | | | | | | | | | | | | | | | | | | | | | If we have a pair of binops feeding another pair of binops, rearrange the operands so the matching pair are together because that allows easy factorization folds to happen in instcombine: ((X << S) & Y) & (Z << S) --> ((X << S) & (Z << S)) & Y (reassociation) --> ((X & Z) << S) & Y (factorize shift from 'and' ops optimization) This is part of solving PR37098: https://bugs.llvm.org/show_bug.cgi?id=37098 Note that there's an instcombine version of this patch attached there, but we're trying to make instcombine have less responsibility to improve compile-time efficiency. For reasons I still don't completely understand, reassociate does this kind of transform sometimes, but misses everything in my motivating cases. This patch on its own is gluing an independent cleanup chunk to the end of the existing RewriteExprTree() loop. We can build on it and do something stronger to better order the full expression tree like D40049. That might be an alternative to the proposal to add a separate reassociation pass like D41574. Differential Revision: https://reviews.llvm.org/D45842 llvm-svn: 341288
* [Constants] add identity constants for fadd/fmulSanjay Patel2018-07-032-10/+7
| | | | | | | | | | | | | | | | As the test diffs show, the current users of getBinOpIdentity() are InstCombine and Reassociate. SLP vectorizer is a candidate for using this functionality too (D28907). The InstCombine shuffle improvements are part of the planned enhancements noted in D48830. InstCombine actually has several other uses of getBinOpIdentity() via SimplifyUsingDistributiveLaws(), but we don't call that for any FP ops. Fixing that might be another part of removing the custom reassociation in InstCombine that is only done for fadd+fmul. llvm-svn: 336215
* [Reassociate] add tests for binop with identity constant; NFCSanjay Patel2018-07-031-0/+74
| | | | llvm-svn: 336214
* [Reassociate] regenerate checks; NFCSanjay Patel2018-07-031-77/+115
| | | | llvm-svn: 336211
* [Reassociate] add test for missing FP constant analysis; NFCSanjay Patel2018-07-031-3/+19
| | | | llvm-svn: 336208
* [Reassociate] Prevent infinite loops when processing PHIs.Davide Italiano2018-05-111-0/+28
| | | | | | | | | | | | | | | | | | | | | | Phi nodes can reside in live blocks but one of their incoming arguments can come from a dead block. Dead blocks and reassociate don't play nice together. In fact, reassociate performs an RPO as a first step to avoid processing dead blocks. The reason why Reassociate might not fixpoint when examining dead blocks is that the following: %xor0 = xor i16 %xor1, undef %xor1 = xor i16 %xor0, undef is perfectly valid LLVM IR (if it appears in a dead block), so the worklist algorithm keeps pushing the two instructions for reexamination. Note that this is not Reassociate fault, at least not entirely. It's llvm that has a weird definition of dominance. Fixes PR37390. llvm-svn: 332100
* [DebugInfo] Add DILabel metadata and intrinsic llvm.dbg.label.Shiva Chen2018-05-092-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In order to set breakpoints on labels and list source code around labels, we need collect debug information for labels, i.e., label name, the function label belong, line number in the file, and the address label located. In order to keep these information in LLVM IR and to allow backend to generate debug information correctly. We create a new kind of metadata for labels, DILabel. The format of DILabel is !DILabel(scope: !1, name: "foo", file: !2, line: 3) We hope to keep debug information as much as possible even the code is optimized. So, we create a new kind of intrinsic for label metadata to avoid the metadata is eliminated with basic block. The intrinsic will keep existing if we keep it from optimized out. The format of the intrinsic is llvm.dbg.label(metadata !1) It has only one argument, that is the DILabel metadata. The intrinsic will follow the label immediately. Backend could get the label metadata through the intrinsic's parameter. We also create DIBuilder API for labels to be used by Frontend. Frontend could use createLabel() to allocate DILabel objects, and use insertLabel() to insert llvm.dbg.label intrinsic in LLVM IR. Differential Revision: https://reviews.llvm.org/D45024 Patch by Hsiangkai Wang. llvm-svn: 331841
* [reassociate] Fix excessive revisits when processing long chains of ↵Daniel Sanders2018-05-021-0/+37
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | reassociatable instructions. Summary: Some of our internal testing detected a major compile time regression which I've tracked down to: r278938 - Revert "Reassociate: Reprocess RedoInsts after each inst". It appears that processing long chains of reassociatable instructions causes non-linear (potentially exponential) growth in the number of times an instruction is revisited. For example, the included test revisits instructions 220 times in a 20-instruction test. It appears that r278938 reversed the order instructions were visited and that this is preventing scheduled revisits from being cancelled as a result of visiting the instructions naturally during normal processing. However, simply reversing the order also harmed the generated code. Upon closer inspection, it was discovered that revisits occurred in the opposite order to the first pass (Thanks to escha for spotting that). This patch makes the revisit order consistent with the first pass which allows more revisits to be cancelled. This does appear to have a small impact on the generated code in few cases but it significantly reduces compile-time. After this patch, our internal test that was most affected by the regression dropped from ~2 million revisits to ~4k resulting in Reassociate having 0.46% of the runtime it had before (99.54% improvement). Here's the summaries reported by lnt for the LLVM test-suite with --benchmarking-only: | metric | geomean before patch | geomean after patch | delta | | ----- | ----- | ----- | ----- | | compile time | 0.1956 | 0.1261 | -35.54% | | execution time | 0.3240 | 0.3237 | - | | code size | 7365.4459 | 7365.6079 | - | The results have a few wins and losses on compile-time, mostly in the +/- 2.5% range. There was one outlier though: | Performance Regressions - compile_time | Δ | Previous | Current | | MultiSource/Benchmarks/ASC_Sequoia/CrystalMk/CrystalMk | 9.82% | 2.0473 | 2.2483 | Reviewers: javed.absar, dberlin Reviewed By: dberlin Subscribers: kristof.beyls, llvm-commits Differential Revision: https://reviews.llvm.org/D45734 llvm-svn: 331381
* [Reassociate] add a test with debug info; NFCSanjay Patel2018-04-271-4/+77
| | | | | | | | | As suggested in D45842 (although still not sure if we're going to advance that), we must invalidate references to instructions that have been recycled (operands were changed, so result is different). llvm-svn: 331083
* [DebugInfo] Invalidate debug info in ReassociatePass::RewriteExprTreeBjorn Pettersson2018-04-251-0/+79
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: When Reassociate is rewriting an expression tree it may reuse old binary expression nodes, for new expressions. Whenever an expression node is reused, but with a non-trivial change in the result, we need to invalidate any debug info that is associated with the node. If for example rewriting x = mul a, b y = mul c, x into x = mul c, b y = mul a, x we still get the same result for 'y', but 'x' is a new expression. All debug info referring to 'x' must be invalidated (marked as optimized out) since we no longer calculate the expected value. As a side-effect this patch avoid (at least some) problems where reassociate could end up creating IR with debug-use before def. Earlier the dbg.value nodes where left untouched in the IR, while the reused binary nodes where sinked to just before the root node of the rewritten expression tree. See PR27273 for more info about such problems. Reviewers: dblaikie, aprantl, dexonsmith Reviewed By: aprantl Subscribers: JDevlieghere, llvm-commits Tags: #debug-info Differential Revision: https://reviews.llvm.org/D45975 llvm-svn: 330804
* [Reassociate] add baseline tests for binop swapping; NFCSanjay Patel2018-04-191-0/+286
| | | | | | | | | Similar to rL330086, I don't know if we want to do these transforms here, but we might as well have the tests here either way to show that this pass is missing potential functionality (intentionally or not). llvm-svn: 330368
* [InstCombine] Enable Add/Sub simplifications with only 'reassoc' FMFWarren Ristow2018-04-143-5/+118
| | | | | | | | These simplifications were previously enabled only with isFast(), but that is more restrictive than required. Since r317488, FMF has 'reassoc' to control these cases at a finer level. llvm-svn: 330089
* [Reassociate] fix test to be independent of FP undefSanjay Patel2018-03-081-14/+17
| | | | llvm-svn: 327071
* [ConstantFold] fp_binop undef, undef --> undefSanjay Patel2018-03-082-7/+9
| | | | | | | | | | | | | | | | | These are uncontroversial and independent of a proposed LangRef edits (D44216). I tried to fix tests that would fold away: rL327004 rL327028 rL327030 rL327034 I'm not sure if the Reassociate tests are meaningless yet, but they probably will be as we add more folds, so if anyone has suggestions or wants to fix those, please do. Differential Revision: https://reviews.llvm.org/D44258 llvm-svn: 327058
* [InstCombine] allow fmul fold with less than 'fast'Sanjay Patel2018-03-021-4/+3
| | | | | | | | | | | | | | | | | | This is a retry of r326502 with updates to the reassociate test file that I missed the first time. @test15_reassoc in the supposed -reassociate test file (except that it tests 2 other passes too...) shows that there's no clear responsiblity for reassociation transforms. Instcombine now gets that case, but only because the constant values are identical. Otherwise, it would still miss that pattern. Reassociate doesn't get that case because it hasn't been updated to use less than 'fast' FMF. llvm-svn: 326513
* [Reassociate] regenerate checks; NFCSanjay Patel2018-03-011-61/+62
| | | | llvm-svn: 326511
* Reassociate: add global reassociation algorithmFiona Glaser2017-12-123-4/+19
| | | | | | | | | | | | | | | | | | | | | | | This algorithm (explained more in the source code) takes into account global redundancies by building a "pair map" to find common subexprs. The primary motivation of this is to handle situations like foo = (a * b) * c bar = (a * d) * c where we currently don't identify that "a * c" is redundant. Accordingly, it prioritizes the emission of a * c so that CSE can remove the redundant calculation later. Does not change the actual reassociation algorithm -- only the order in which the reassociated operand chain is reconstructed. Gives ~1.5% floating point math instruction count reduction on a large offline suite of graphics shaders. llvm-svn: 320515
* [Reassociation] regenerate test checks; NFCSanjay Patel2017-11-131-54/+55
| | | | llvm-svn: 318076
* [Reassociate] add tests with 'reassoc' FMF; NFCSanjay Patel2017-11-135-3/+311
| | | | llvm-svn: 318053
* [Reassociate] regenerate test checks; NFCSanjay Patel2017-11-092-22/+26
| | | | llvm-svn: 317841
* [Reassociate] auto-generate test checks; NFCSanjay Patel2017-11-094-47/+60
| | | | llvm-svn: 317819
* [Reassociate] don't name values "tmp"; NFCISanjay Patel2017-11-098-253/+279
| | | | | | | | | | The toxic stew of created values named 'tmp' and tests that already have values named 'tmp' and CHECK lines looking for values named 'tmp' causes bad things to happen in our test line auto-generation scripts because it wants to use 'TMP' as a prefix for unnamed values. Use less 'tmp' to avoid that. llvm-svn: 317818
* revert r317809 - [Reassociate] regenerate test checks; NFCSanjay Patel2017-11-091-14/+4
| | | | | | | The reassociate pass generates named values such as "%tmp2" which trips up the script's regex's because the script uses a 'TMP' prefix for unnamed values (%2). llvm-svn: 317810
* [Reassociate] regenerate test checks; NFCSanjay Patel2017-11-091-4/+14
| | | | llvm-svn: 317809
* [Reassociate] regenerate test checks; NFCSanjay Patel2017-11-091-66/+73
| | | | llvm-svn: 317806
* [Reassociate] add check lines; NFCSanjay Patel2017-11-091-1/+11
| | | | llvm-svn: 317805
* [Reassociate] add tests with 'reassoc' FMF and regenerate checks; NFCSanjay Patel2017-11-091-84/+254
| | | | llvm-svn: 317804
* [Reassociate] Remove FIXME from looptest.ll (NFC)Florian Hahn2017-10-311-2/+3
| | | | | | | | | | | | | | Summary: The loop invariant add (i+j) is reassoicated, I think the FIXME can be removed, because this is what the test case tries to check (AFAIK). I also changed the test to use FileCheck. Reviewers: mcrosier, davide Reviewed By: mcrosier, davide Subscribers: davide, llvm-commits Differential Revision: https://reviews.llvm.org/D39424 llvm-svn: 317000
* [Reassociate] auto-generate better checks; NFCSanjay Patel2017-10-132-20/+23
| | | | | | These would fail if the created variable names changed. llvm-svn: 315752
* [Reassociate] Do not drop debug location if replacement is missingMikael Holmen2017-08-241-0/+48
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: When reassociating an expression, do not drop the instruction's original debug location in case the replacement location is missing. The debug location must at least not be dropped for inlinable callsites of debug-info-bearing functions in debug-info-bearing functions. Failing to do so would result in an "inlinable function " "call in a function with debug info must have a !dbg location" error in the verifier. As preserving the original debug location is not expected to result in overly jumpy debug line information, it is preserved for all other cases too. This fixes PR34231: https://bugs.llvm.org/show_bug.cgi?id=34231 Original patch by David Stenberg Reviewers: davide, craig.topper, mcrosier, dblaikie, aprantl Reviewed By: davide, aprantl Subscribers: aprantl Differential Revision: https://reviews.llvm.org/D36865 llvm-svn: 311642
* [Reassociate] Don't canonicalize x + (-Constant * y) -> x - (Constant * y)..Chad Rosier2017-08-231-0/+22
| | | | | | | | | | | | | ..if the resulting subtract will be broken up later. This can cause us to get into an infinite loop. x + (-5.0 * y) -> x - (5.0 * y) ; Canonicalize neg const x - (5.0 * y) -> x + (0 - (5.0 * y)) ; Break up subtract x + (0 - (5.0 * y)) -> x + (-5.0 * y) ; Replace 0-X with X*-1. PR34078 llvm-svn: 311554
* [Reassociate] Make sure EraseInst sets MadeChangeMikael Holmen2017-06-271-0/+29
| | | | | | | | | | | | | | | | | | | | | Summary: EraseInst didn't report that it made IR changes through MadeChange. It is essential that changes to the IR are reported correctly, since for example ReassociatePass::run() will indicate that all analyses are preserved otherwise. And the CGPassManager determines if the CallGraph is up-to-date based on status from InstructionCombiningPass::runOnFunction(). Reviewers: craig.topper, rnk, davide Reviewed By: rnk, davide Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34616 llvm-svn: 306368
* [Reassociate] Support xor reassociating for splat vectorsCraig Topper2017-06-211-0/+101
| | | | | | | | | | | | | | Summary: This patch adds support for xors of splat vectors. Reviewers: mcrosier Reviewed By: mcrosier Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34354 llvm-svn: 305925
* [Reassociate] Support some reassociation of vector xorsCraig Topper2017-06-191-4/+14
| | | | | | | | | | | | | | | | | Summary: Currently we don't try to do anything with vector xors. This patch adds support for removing duplicate pairs from a chain of vector xors as its pretty easy to support. We still dont' try to combine the xors with and/ors, but I might try that in a future patch. Reviewers: mcrosier, davide, resistor Reviewed By: mcrosier Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34338 llvm-svn: 305704
* [Reassociate] Add negated value of negative constant to the Duplicates list.Chad Rosier2017-02-231-0/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In OptimizeAdd, we scan the operand list to see if there are any common factors between operands that can be factored out to reduce the number of multiplies (e.g., 'A*A+A*B*C+D' -> 'A*(A+B*C)+D'). For each operand of the operand list, we only consider unique factors (which is tracked by the Duplicate set). Now if we find a factor that is a negative constant, we add the negated value as a factor as well, because we can percolate the negate out. However, we mistakenly don't add this negated constant to the Duplicates set. Consider the expression A*2*-2 + B. Obviously, nothing to factor. For the added value A*2*-2 we over count 2 as a factor without this change, which causes the assert reported in PR30256. The problem is that this code is assuming that all the multiply operands of the add are already reassociated. This change avoids the issue by making OptimizeAdd tolerate multiplies which haven't been completely optimized; this sort of works, but we're doing wasted work: we'll end up revisiting the add later anyway. Another possible approach would be to enforce RPO iteration order more strongly. If we have RedoInsts, we process them immediately in RPO order, rather than waiting until we've finished processing the whole function. Intuitively, it seems like the natural approach: reassociation works on expression trees, so the optimization only works in one direction. That said, I'm not sure how practical that is given the current Reassociate; the "optimal" form for an expression depends on its use list (see all the uses of "user_back()"), so Reassociate is really an iterative optimization of sorts, so any changes here would probably get messy. PR30256 Differential Revision: https://reviews.llvm.org/D30228 llvm-svn: 296003
* Fixed the lost FastMathFlags in Reassociate optimization.Vyacheslav Klochkov2016-11-221-0/+14
| | | | | | | Reviewer: Hal Finkel. Differential Revision: https://reviews.llvm.org/D26957 llvm-svn: 287695
* reassociate-deadinst.ll: avoid accidental match on pathHubert Tong2016-11-211-1/+1
| | | | | | Pipe from stdin to avoid accidentally matching on the path. llvm-svn: 287583
* [Reassociate] Skip analysis of dead code to avoid infinite loop.Bjorn Pettersson2016-11-021-0/+37
| | | | | | | | | | | | | | | | | | | | | | | | Summary: It was detected that the reassociate pass could enter an inifite loop when analysing dead code. Simply skipping to analyse basic blocks that are dead avoids such problems (and as a side effect we avoid spending time on optimising dead code). The solution is using the same Reverse Post Order ordering of the basic blocks when doing the optimisations, as when building the precalculated rank map. A nice side-effect of this solution is that we now know that we only try to do optimisations for blocks with ranked instructions. Fixes https://llvm.org/bugs/show_bug.cgi?id=30818 Reviewers: llvm-commits, davide, eli.friedman, mehdi_amini Subscribers: dberlin Differential Revision: https://reviews.llvm.org/D26154 llvm-svn: 285793
* [Reassociate] Removing instructions mutates the IR.Davide Italiano2016-10-281-0/+16
| | | | | | | | | Fixes PR 30784. Discussed with Justin, who pointed out that in the new PassManager infrastructure we can have more fine-grained control on which analyses we want to preserve, but this is the best we can do with the current infrastructure. llvm-svn: 285380
* [Reassociate] Add test for PR28367.Chad Rosier2016-08-181-0/+28
| | | | llvm-svn: 279063
* Revert "Reassociate: Reprocess RedoInsts after each inst".Chad Rosier2016-08-173-62/+5
| | | | | | | | This reverts commit r258830, which introduced a bug described in PR28367. PR28367 llvm-svn: 278938
* Revert "[Reassociate] Avoid iterator invalidation when negating value."Chad Rosier2016-08-171-30/+0
| | | | | | This reverts commit r278928 due to lit test failures. llvm-svn: 278929
* [Reassociate] Avoid iterator invalidation when negating value.Chad Rosier2016-08-171-0/+30
| | | | | | | Differential Revision: https://reviews.llvm.org/D23464 PR28367 llvm-svn: 278928
* PM: Port Reassociate to the new pass managerJustin Bogner2016-04-261-0/+1
| | | | llvm-svn: 267631
OpenPOWER on IntegriCloud