summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/Reassociate
Commit message (Collapse)AuthorAgeFilesLines
...
* [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
* Reassociate: Reprocess RedoInsts after each instAditya Nandakumar2016-01-263-5/+62
| | | | | | | | | | Previously the RedoInsts was processed at the end of the block. However it was possible that it left behind some instructions that were not canonicalized. This should guarantee that any previous instruction in the basic block is canonicalized before we process a new instruction. llvm-svn: 258830
* Instructions to be redone only if from the same BBAditya Nandakumar2016-01-071-0/+20
| | | | | | | While adding instructions(possible roots) to be redone, make sure they are from the same basic block. llvm-svn: 257112
* Remove dead instructions before RedoingAditya Nandakumar2016-01-042-1/+35
| | | | | | | | | Before reevaluating instructions, iterate over all instructions to be reevaluated and remove trivially dead instructions and if any of it's operands become trivially dead, mark it for deletion until all trivially dead instructions have been removed llvm-svn: 256773
* Fix another infinite loop in Reassociate caused by Constant::isZero().Owen Anderson2015-11-201-0/+13
| | | | | | Not all zero vectors are ConstantDataVector's. llvm-svn: 253723
* Fix a pair of issues that caused an infinite loop in reassociate.Owen Anderson2015-11-201-0/+20
| | | | | | | | Terrifyingly, one of them is a mishandling of floating point vectors in Constant::isZero(). How exactly this issue survived this long is beyond me. llvm-svn: 253655
* Add intermediate subtract instructions to reassociation worklist.Owen Anderson2015-11-168-17/+48
| | | | | | | | | | We sometimes create intermediate subtract instructions during reassociation. Adding these to the worklist to revisit exposes many additional reassociation opportunities. Patch by Aditya Nandakumar. llvm-svn: 253240
* Fix a bunch of trivial cases of 'CHECK[^:]*$' in the tests. NFCIJonathan Roelofs2015-08-101-1/+1
| | | | | | | I looked into adding a warning / error for this to FileCheck, but there doesn't seem to be a good way to avoid it triggering on the instances of it in RUN lines. llvm-svn: 244481
* [Reassociation] Fix miscompile for va_arg arguments.Quentin Colombet2015-08-061-0/+28
| | | | | | | | | | | | | | | | iisUnmovableInstruction() had a list of instructions hardcoded which are considered unmovable. The list lacked (at least) an entry for the va_arg and cmpxchg instructions. Fix this by introducing a new Instruction::mayBeMemoryDependent() instead of maintaining another instruction list. Patch by Matthias Braun <matze@braunis.de>. Differential Revision: http://reviews.llvm.org/D11577 rdar://problem/22118647 llvm-svn: 244244
* [Reassociate] Don't propogate flags when creating negationsDavid Majnemer2015-06-242-2/+17
| | | | | | | | | Reassociate mutated existing instructions in order to form negations which would create additional reassociate opportunities. This fixes PR23926. llvm-svn: 240593
* [Reassociate] Canonicalizing 'x [+-] (-Constant * y)' isn't always a winDavid Majnemer2015-05-282-14/+12
| | | | | | | | | | | | | Canonicalizing 'x [+-] (-Constant * y)' is not a win if we don't *know* we will open up CSE opportunities. If the multiply was 'nsw', then negating 'y' requires us to clear the 'nsw' flag. If this is actually worth pursuing, it is probably more appropriate to do so in GVN or EarlyCSE. This fixes PR23675. llvm-svn: 238397
* [opaque pointer type] Add textual IR support for explicit type parameter to ↵David Blaikie2015-04-161-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | the call instruction See r230786 and r230794 for similar changes to gep and load respectively. Call is a bit different because it often doesn't have a single explicit type - usually the type is deduced from the arguments, and just the return type is explicit. In those cases there's no need to change the IR. When that's not the case, the IR usually contains the pointer type of the first operand - but since typed pointers are going away, that representation is insufficient so I'm just stripping the "pointerness" of the explicit type away. This does make the IR a bit weird - it /sort of/ reads like the type of the first operand: "call void () %x(" but %x is actually of type "void ()*" and will eventually be just of type "ptr". But this seems not too bad and I don't think it would benefit from repeating the type ("void (), void () * %x(" and then eventually "void (), ptr %x(") as has been done with gep and load. This also has a side benefit: since the explicit type is no longer a pointer, there's no ambiguity between an explicit type and a function that returns a function pointer. Previously this case needed an explicit type (eg: a function returning a void() function was written as "call void () () * @x(" rather than "call void () * @x(" because of the ambiguity between a function returning a pointer to a void() function and a function returning void). No ambiguity means even function pointer return types can just be written alone, without writing the whole function's type. This leaves /only/ the varargs case where the explicit type is required. Given the special type syntax in call instructions, the regex-fu used for migration was a bit more involved in its own unique way (as every one of these is) so here it is. Use it in conjunction with the apply.sh script and associated find/xargs commands I've provided in rr230786 to migrate your out of tree tests. Do let me know if any of this doesn't cover your cases & we can iterate on a more general script/regexes to help others with out of tree tests. About 9 test cases couldn't be automatically migrated - half of those were functions returning function pointers, where I just had to manually delete the function argument types now that we didn't need an explicit function type there. The other half were typedefs of function types used in calls - just had to manually drop the * from those. import fileinput import sys import re pat = re.compile(r'((?:=|:|^|\s)call\s(?:[^@]*?))(\s*$|\s*(?:(?:\[\[[a-zA-Z0-9_]+\]\]|[@%](?:(")?[\\\?@a-zA-Z0-9_.]*?(?(3)"|)|{{.*}}))(?:\(|$)|undef|inttoptr|bitcast|null|asm).*$)') addrspace_end = re.compile(r"addrspace\(\d+\)\s*\*$") func_end = re.compile("(?:void.*|\)\s*)\*$") def conv(match, line): if not match or re.search(addrspace_end, match.group(1)) or not re.search(func_end, match.group(1)): return line return line[:match.start()] + match.group(1)[:match.group(1).rfind('*')].rstrip() + match.group(2) + line[match.end():] for line in sys.stdin: sys.stdout.write(conv(re.search(pat, line), line)) llvm-svn: 235145
* Reapply "[Reassociate] Add initial support for vector instructions."Robert Lougher2015-03-131-43/+189
| | | | | | | | | This reapplies the patch previously committed at revision 232190. This was reverted at revision 232196 as it caused test failures in tests that did not expect operands to be commuted. I have made the tests more resilient to reassociation in revision 232206. llvm-svn: 232209
* Revert: "[Reassociate] Add initial support for vector instructions."Robert Lougher2015-03-131-189/+43
| | | | | | | This reverts revision 232190 due to buildbot failure reported on clang-hexagon-elf for test arm64_vtst.c. To be investigated. llvm-svn: 232196
* [Reassociate] Add initial support for vector instructions.Robert Lougher2015-03-131-43/+189
| | | | | | | | | | | | | | This patch adds initial support for vector instructions to the reassociation pass. It enables most parts of the pass to work with vectors but to keep the size of the patch small, optimization of Xor trees, canonicalization of negative constants and converting shifts to muls, etc., have been left out. This will be handled in later patches. The patch is based on an initial patch by Chad Rosier. Differential Revision: http://reviews.llvm.org/D7566 llvm-svn: 232190
* [opaque pointer type] Add textual IR support for explicit type parameter to ↵David Blaikie2015-02-276-36/+36
| | | | | | | | | | | | | | | | | | | | | | | | load instruction Essentially the same as the GEP change in r230786. A similar migration script can be used to update test cases, though a few more test case improvements/changes were required this time around: (r229269-r229278) import fileinput import sys import re pat = re.compile(r"((?:=|:|^)\s*load (?:atomic )?(?:volatile )?(.*?))(| addrspace\(\d+\) *)\*($| *(?:%|@|null|undef|blockaddress|getelementptr|addrspacecast|bitcast|inttoptr|\[\[[a-zA-Z]|\{\{).*$)") for line in sys.stdin: sys.stdout.write(re.sub(pat, r"\1, \2\3*\4", line)) Reviewers: rafael, dexonsmith, grosser Differential Revision: http://reviews.llvm.org/D7649 llvm-svn: 230794
* [opaque pointer type] Add textual IR support for explicit type parameter to ↵David Blaikie2015-02-272-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | getelementptr instruction One of several parallel first steps to remove the target type of pointers, replacing them with a single opaque pointer type. This adds an explicit type parameter to the gep instruction so that when the first parameter becomes an opaque pointer type, the type to gep through is still available to the instructions. * This doesn't modify gep operators, only instructions (operators will be handled separately) * Textual IR changes only. Bitcode (including upgrade) and changing the in-memory representation will be in separate changes. * geps of vectors are transformed as: getelementptr <4 x float*> %x, ... ->getelementptr float, <4 x float*> %x, ... Then, once the opaque pointer type is introduced, this will ultimately look like: getelementptr float, <4 x ptr> %x with the unambiguous interpretation that it is a vector of pointers to float. * address spaces remain on the pointer, not the type: getelementptr float addrspace(1)* %x ->getelementptr float, float addrspace(1)* %x Then, eventually: getelementptr float, ptr addrspace(1) %x Importantly, the massive amount of test case churn has been automated by same crappy python code. I had to manually update a few test cases that wouldn't fit the script's model (r228970,r229196,r229197,r229198). The python script just massages stdin and writes the result to stdout, I then wrapped that in a shell script to handle replacing files, then using the usual find+xargs to migrate all the files. update.py: import fileinput import sys import re ibrep = re.compile(r"(^.*?[^%\w]getelementptr inbounds )(((?:<\d* x )?)(.*?)(| addrspace\(\d\)) *\*(|>)(?:$| *(?:%|@|null|undef|blockaddress|getelementptr|addrspacecast|bitcast|inttoptr|\[\[[a-zA-Z]|\{\{).*$))") normrep = re.compile( r"(^.*?[^%\w]getelementptr )(((?:<\d* x )?)(.*?)(| addrspace\(\d\)) *\*(|>)(?:$| *(?:%|@|null|undef|blockaddress|getelementptr|addrspacecast|bitcast|inttoptr|\[\[[a-zA-Z]|\{\{).*$))") def conv(match, line): if not match: return line line = match.groups()[0] if len(match.groups()[5]) == 0: line += match.groups()[2] line += match.groups()[3] line += ", " line += match.groups()[1] line += "\n" return line for line in sys.stdin: if line.find("getelementptr ") == line.find("getelementptr inbounds"): if line.find("getelementptr inbounds") != line.find("getelementptr inbounds ("): line = conv(re.match(ibrep, line), line) elif line.find("getelementptr ") != line.find("getelementptr ("): line = conv(re.match(normrep, line), line) sys.stdout.write(line) apply.sh: for name in "$@" do python3 `dirname "$0"`/update.py < "$name" > "$name.tmp" && mv "$name.tmp" "$name" rm -f "$name.tmp" done The actual commands: From llvm/src: find test/ -name *.ll | xargs ./apply.sh From llvm/src/tools/clang: find test/ -name *.mm -o -name *.m -o -name *.cpp -o -name *.c | xargs -I '{}' ../../apply.sh "{}" From llvm/src/tools/polly: find test/ -name *.ll | xargs ./apply.sh After that, check-all (with llvm, clang, clang-tools-extra, lld, compiler-rt, and polly all checked out). The extra 'rm' in the apply.sh script is due to a few files in clang's test suite using interesting unicode stuff that my python script was throwing exceptions on. None of those files needed to be migrated, so it seemed sufficient to ignore those cases. Reviewers: rafael, dexonsmith, grosser Differential Revision: http://reviews.llvm.org/D7636 llvm-svn: 230786
* Reassociate: cannot negate a INT_MIN valueMehdi Amini2015-02-111-0/+13
| | | | | | | | | | | | | | | | | | Summary: When trying to canonicalize negative constants out of multiplication expressions, we need to check that the constant is not INT_MIN which cannot be negated. Reviewers: mcrosier Reviewed By: mcrosier Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D7286 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 228872
* Fix Reassociate handling of constant in presence of undef floatMehdi Amini2015-01-161-0/+25
| | | | | | http://reviews.llvm.org/D6993 llvm-svn: 226245
* Revert "[Reassociate] As the expression tree is rewritten make sure the ↵Chad Rosier2014-11-1916-54/+53
| | | | | | | | | | | | | operands are" This reverts commit r222142. This is causing/exposing an execution-time regression in spec2006/gcc and coremark on AArch64/A57/Ofast. Conflicts: test/Transforms/Reassociate/optional-flags.ll llvm-svn: 222398
* [Reassociate] Use test cases that can actually be optimized to verify optionalChad Rosier2014-11-181-11/+12
| | | | | | | flags are cleared. The reassociation pass was just reordering the leaf nodes in the previous test cases. llvm-svn: 222250
* [Reassociate] As the expression tree is rewritten make sure the operands areChad Rosier2014-11-1716-46/+46
| | | | | | emitted in canonical form. llvm-svn: 222142
* [Reassociate] Canonicalize constants to RHS operand.Chad Rosier2014-11-173-6/+6
| | | | | | Fix a thinko where the RHS was already a constant. llvm-svn: 222139
* [Reassociate] Canonicalize the operands of all binary operators.Chad Rosier2014-11-142-1/+20
| | | | llvm-svn: 222008
* [Reassociate] Canonicalize operands of vector binary operators.Chad Rosier2014-11-141-2/+50
| | | | | | | | Prior to this commit fmul and fadd binary operators were being canonicalized for both scalar and vector versions. We now canonicalize add, mul, and, or, and xor vector instructions. llvm-svn: 222006
* [Reassociate] Canonicalize constants to RHS operand.Chad Rosier2014-11-143-7/+7
| | | | llvm-svn: 222005
* [Reassociate] Canonicalize negative constants out of expressions.Chad Rosier2014-11-111-0/+48
| | | | | | Add support for FDiv, which was regressed by the previous commit. llvm-svn: 221738
* [Reassociate] Canonicalize negative constants out of expressions.Chad Rosier2014-11-114-73/+114
| | | | | | | | This is a reapplication of r221171, but we only perform the transformation on expressions which include a multiplication. We do not transform rem/div operations as this doesn't appear to be safe in all cases. llvm-svn: 221721
* [Reassociate] Better preserve NSW/NUW flags.Chad Rosier2014-11-071-0/+34
| | | | | | | | Part of PR12985. Phabricator Revision: http://reviews.llvm.org/D6172 llvm-svn: 221555
* [Reassociate] Don't reassociate when mixing regular and fast-math FPChad Rosier2014-11-061-0/+18
| | | | | | | | | instructions. Inlining might cause such cases and it's not valid to reassociate floating-point instructions without the unsafe algebra flag. Patch by Mehdi Amini <mehdi_amini@apple.com>! llvm-svn: 221462
OpenPOWER on IntegriCloud