summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/Reassociate
Commit message (Collapse)AuthorAgeFilesLines
* Migrate function attribute "no-frame-pointer-elim-non-leaf" to ↵Fangrui Song2019-12-241-1/+1
| | | | "frame-pointer"="non-leaf" as cleanups after D56351
* [DBG][OPT] Attempt to salvage or undef debug info when removing trivially ↵Tom Weaver2019-11-122-0/+145
| | | | | | | | deletable instructions in the Reassociate Expression pass. Reviewed By: aprantl, vsk Differential revision: https://reviews.llvm.org/D69943
* Revert "[DBG][OPT] Attempt to salvage or undef debug info when removing ↵Tom Weaver2019-11-112-145/+0
| | | | | | trivially deletable instructions in the Reassociate Expression pass." This reverts commit 1984a27db58e9053371ab6d6dc288c81c8a071ac.
* [DBG][OPT] Attempt to salvage or undef debug info when removing trivially ↵Tom Weaver2019-11-112-0/+145
| | | | | | | | deletable instructions in the Reassociate Expression pass. Reviewed By: aprantl, vsk Differential revision: https://reviews.llvm.org/D69943
* [Reassoc] Small fix to support unary FNeg in NegateValue(...)Cameron McInally2019-08-231-0/+24
| | | | | | Differential Revision: https://reviews.llvm.org/D66612 llvm-svn: 369772
* [Reassociate] try harder to convert negative FP constants to positiveSanjay Patel2019-08-103-86/+85
| | | | | | | | | | | | | | | | | | | | | | This is an extension of a transform that tries to produce positive floating-point constants to improve canonicalization (and hopefully lead to more reassociation and CSE). The original patches were: D4904 D5363 (rL221721) But as the test diffs show, these were limited to basic patterns by walking from an instruction to its single user rather than recursively moving up the def-use sequence. No fast-math is required here because we're only rearranging implicit FP negations in intermediate ops. A motivating bug is: https://bugs.llvm.org/show_bug.cgi?id=32939 Differential Revision: https://reviews.llvm.org/D65954 llvm-svn: 368512
* [Reassociate] add more tests with negative FP constants; NFCSanjay Patel2019-08-081-0/+332
| | | | llvm-svn: 368290
* [Tests] Autogen a bunch of Reassociate tests for ease of updatePhilip Reames2019-08-0118-242/+374
| | | | llvm-svn: 367634
* [InstCombine] canonicalize fneg before fmul/fdivSanjay Patel2019-07-311-4/+17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Reverse the canonicalization of fneg relative to fmul/fdiv. That makes it easier to implement the transforms (and possibly other fneg transforms) in 1 place because we can always start the pattern match from fneg (either the legacy binop or the new unop). There's a secondary practical benefit seen in PR21914 and PR42681: https://bugs.llvm.org/show_bug.cgi?id=21914 https://bugs.llvm.org/show_bug.cgi?id=42681 ...hoisting fneg rather than sinking seems to play nicer with LICM in IR (although this change may expose analysis holes in the other direction). 1. The instcombine test changes show the expected neutral IR diffs from reversing the order. 2. The reassociation tests show that we were missing an optimization opportunity to fold away fneg-of-fneg. My reading of IEEE-754 says that all of these transforms are allowed (regardless of binop/unop fneg version) because: "For all other operations [besides copy/abs/negate/copysign], this standard does not specify the sign bit of a NaN result." In all of these transforms, we always have some other binop (fadd/fsub/fmul/fdiv), so we are free to flip the sign bit of a potential intermediate NaN operand. (If that interpretation is wrong, then we must already have a bug in the existing transforms?) 3. The clang tests shouldn't exist as-is, but that's effectively a revert of rL367149 (the test broke with an extension of the pre-existing fneg canonicalization in rL367146). Differential Revision: https://reviews.llvm.org/D65399 llvm-svn: 367447
* [NFC][Reassociate] Add unary FNeg tests to fast-ReassociateVector.llCameron McInally2019-06-241-0/+57
| | | | llvm-svn: 364232
* [Reassociate] Remove bogus assert reported in PR42349.Cameron McInally2019-06-201-0/+18
| | | | | | | | Also, add a FIXME for the unsafe transform on a unary FNeg. A unary FNeg can only be transformed to a FMul by -1.0 when the nnan flag is present. The unary FNeg project is a WIP, so the unsafe transformation is acceptable until that work is complete. The bogus assert with introduced in D63445. llvm-svn: 363998
* [Reassociate] Handle unary FNeg in the Reassociate passCameron McInally2019-06-191-4/+17
| | | | | | Differential Revision: https://reviews.llvm.org/D63445 llvm-svn: 363813
* [NFC][Reassociate] Fix mistake in 468b2adCameron McInally2019-06-051-10/+8
| | | | | | Missed 2 'fast fsub(0.0,X) -> fneg(X)' changes. llvm-svn: 362631
* [NFC][Reassociate] Add unary fneg tests to fast-basictest.llCameron McInally2019-06-051-0/+69
| | | | llvm-svn: 362630
* [NFC][Reassociate] Regenerate CHECKs for fast-basictest.llCameron McInally2019-06-051-15/+15
| | | | llvm-svn: 362627
* Fix new reassociate-catchswitch.ll testReid Kleckner2019-05-081-0/+5
| | | | llvm-svn: 360279
* [Reassociation] Place moved instructions after landing padsDavid Greene2019-05-082-0/+95
| | | | | | | | | | | | | | | | | Reassociation's NegateValue moved instructions to the beginning of blocks (after PHIs) without checking for exception handling pads. It's possible for reassociation to move something into an exception handling block so we need to make sure we don't move things too early in the block. This change advances the insertion point past any exception handling pads. If the block we want to move into contains a catchswitch, we cannot move into it. In that case just create a new neg as if we had not found an existing neg to move. Differential Revision: https://reviews.llvm.org/D61089 llvm-svn: 360262
* Add FNeg IR constant folding supportCameron McInally2019-05-051-1/+1
| | | | llvm-svn: 359982
* Revert "Temporarily Revert "Add basic loop fusion pass.""Eric Christopher2019-04-1764-0/+4687
| | | | | | | | 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-1764-4687/+0
| | | | | | | | As it's causing some bot failures (and per request from kbarton). This reverts commit r358543/ab70da07286e618016e78247e4a24fcb84077fda. llvm-svn: 358546
* Fix non-determinism in Reassociate caused by address coincidencesDaniel Sanders2019-03-221-0/+107
| | | | | | | | | | | | | | | | | | | | | | | Summary: Between building the pair map and querying it there are a few places that erase and create Values. It's rare but the address of these newly created Values is occasionally the same as a just-erased Value that we already have in the pair map. These coincidences should be accounted for to avoid non-determinism. Thanks to Roman Tereshin for the test case. Reviewers: rtereshin, bogner Reviewed By: rtereshin Subscribers: mgrang, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D59401 llvm-svn: 356803
* [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
OpenPOWER on IntegriCloud