summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [InstSimplify] use ConstantRange to simplify or-of-icmpsSanjay Patel2017-05-071-55/+2
| | | | | | | | | | | | | We can simplify (or (icmp X, C1), (icmp X, C2)) to 'true' or one of the icmps in many cases. I had to check some of these with Alive to prove to myself it's right, but everything seems to check out. Eg, the deleted code in instcombine was completely ignoring predicates with mismatched signedness. This is a follow-up to: https://reviews.llvm.org/rL301260 https://reviews.llvm.org/D32143 llvm-svn: 302370
* [InstCombine] don't use DeMorgan's Law on integer constants (2nd try)Sanjay Patel2017-05-021-18/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This was originally checked in here: https://reviews.llvm.org/rL301923 And reverted here: https://reviews.llvm.org/rL301924 Because there's a clang test that would fail after this. I fixed/removed the offending CHECK lines in: https://reviews.llvm.org/rL301928 So let's try this again. Original commit message: This is the fold that causes the infinite loop in BoringSSL (https://github.com/google/boringssl/blob/master/crypto/cipher/e_rc2.c) when we fix instcombine demanded bits to prefer 'not' ops as in https://reviews.llvm.org/D32255. There are 2 or 3 problems with dyn_castNotVal, and I don't think we can reinstate https://reviews.llvm.org/D32255 until dyn_castNotVal is completely eliminated. 1. As shown here, it transforms 'not' into random xor. This transform is harmful to SCEV and codegen because 'not' can often be folded while random xor cannot. 2. It does not transform vector constants. This is actually a good thing, but if you don't believe the above argument, then we shouldn't have excluded vectors. 3. It tries to avoid transforming not(not(X)). That's nice, but it doesn't match the greedy nature of instcombine. If we DeMorganize a pattern that has an extra 'not' in it: ~(~(~X) & Y) --> (~X | ~Y) That's just another case of DeMorgan, so we should trust that we'll fold that pattern too: (~X | ~ Y) --> ~(X & Y) Differential Revision: https://reviews.llvm.org/D32665 llvm-svn: 301929
* revert r301923 : [InstCombine] don't use DeMorgan's Law on integer constantsSanjay Patel2017-05-021-21/+18
| | | | | | There's a clang test that is wrongly using -O1 and failing after this commit. llvm-svn: 301924
* [InstCombine] don't use DeMorgan's Law on integer constantsSanjay Patel2017-05-021-18/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | This is the fold that causes the infinite loop in BoringSSL (https://github.com/google/boringssl/blob/master/crypto/cipher/e_rc2.c) when we fix instcombine demanded bits to prefer 'not' ops as in D32255. There are 2 or 3 problems with dyn_castNotVal, and I don't think we can reinstate D32255 until dyn_castNotVal is completely eliminated. 1. As shown here, it transforms 'not' into random xor. This transform is harmful to SCEV and codegen because 'not' can often be folded while random xor cannot. 2. It does not transform vector constants. This is actually a good thing, but if you don't believe the above argument, then we shouldn't have excluded vectors. 3. It tries to avoid transforming not(not(X)). That's nice, but it doesn't match the greedy nature of instcombine. If we DeMorganize a pattern that has an extra 'not' in it: ~(~(~X) & Y) --> (~X | ~Y) That's just another case of DeMorgan, so we should trust that we'll fold that pattern too: (~X | ~ Y) --> ~(X & Y) Differential Revision: https://reviews.llvm.org/D32665 llvm-svn: 301923
* [InstCombine] check one-use before applying DeMorgan nor/nand foldsSanjay Patel2017-05-011-10/+14
| | | | | | | | | | | | | | | If we have ~(~X & Y), it only makes sense to transform it to (X | ~Y) when we do not need the intermediate (~X & Y) value. In that case, we would need an extra instruction to generate ~Y + 'or' (as shown in the test changes). It's ok if we have multiple uses of ~X or Y, however. In those cases, we may not reduce the instruction count or critical path, but we might improve throughput because we can generate ~X and ~Y in parallel. Whether that actually makes perf sense or not for a target is something we can't answer in IR. Differential Revision: https://reviews.llvm.org/D32703 llvm-svn: 301848
* [InstCombine] fix matcher to bind to specific operand (PR32830)Sanjay Patel2017-04-271-1/+1
| | | | | | | Matching any random value would be very wrong: https://bugs.llvm.org/show_bug.cgi?id=32830 llvm-svn: 301594
* InstCombine: Use the new SimplifyQuery versions of Simplify*. Use ↵Daniel Berlin2017-04-261-3/+3
| | | | | | AssumptionCache, DominatorTree, TargetLibraryInfo everywhere. llvm-svn: 301464
* [InstCombine] Add missing commute handling to (A | B) & (B ^ (~A)) -> (A & B)Craig Topper2017-04-251-3/+8
| | | | | | | | The matching here wasn't able to handle all the possible commutes. It always assumed the not would be on the left of the xor, but that's not guaranteed. Differential Revision: https://reviews.llvm.org/D32474 llvm-svn: 301316
* [InstCombine] Use commutable matchers to reduce some code. NFCCraig Topper2017-04-251-4/+2
| | | | llvm-svn: 301294
* [InstSimplify] use ConstantRange to simplify more and-of-icmpsSanjay Patel2017-04-241-40/+0
| | | | | | | | | | | | | We can simplify (and (icmp X, C1), (icmp X, C2)) to one of the icmps in many cases. I had to check some of these with Alive to prove to myself it's right, but everything seems to check out. Eg, the code in instcombine was completely ignoring predicates with mismatched signedness. Handling or-of-icmps would be a follow-up step. Differential Revision: https://reviews.llvm.org/D32143 llvm-svn: 301260
* [InstSimplify] move (A & ~B) | (A ^ B) -> (A ^ B) from InstCombineSanjay Patel2017-04-241-13/+0
| | | | | | | | | | | This is a straight cut and paste, but there's a bigger problem: if this fold exists for simplifyOr, there should be a DeMorganized version for simplifyAnd. But more than that, we have a patchwork of ad hoc logic optimizations in InstCombine. There should be some structure to ensure that we're not missing sibling folds across and/or/xor. llvm-svn: 301213
* [InstCombine] add/move folds for [not]-xorSanjay Patel2017-04-231-38/+67
| | | | | | | | | | | | We handled all of the commuted variants for plain xor already, although they were scattered around and sometimes folded less efficiently using distributive laws. We had no folds for not-xor. Handling all of these patterns consistently is part of trying to reinstate: https://reviews.llvm.org/rL300977 llvm-svn: 301144
* [InstCombine] add pattern matches for commuted variants of xor-to-xorSanjay Patel2017-04-231-34/+55
| | | | | | | | | There's probably some better way to write this that eliminates the code duplication without hurting readability, but at least this eliminates the logic holes and is hopefully slightly more efficient than creating new instructions. llvm-svn: 301129
* [InstCombine] use 'match' to reduce code; NFCISanjay Patel2017-04-221-36/+31
| | | | | | | | | | | The later uses of dyn_castNotVal in this block are either incomplete (doesn't handle vector constants) or overstepping (shouldn't handle constants at all), but this first use is just unnecessary. 'I' is obviously not a constant, and it can't be a not-of-a-not because that would already be instsimplified. llvm-svn: 301088
* [APInt] Rename getSignBit to getSignMaskCraig Topper2017-04-201-2/+2
| | | | | | | | getSignBit is a static function that creates an APInt with only the sign bit set. getSignMask seems like a better name to convey its functionality. In fact several places use it and then store in an APInt named SignMask. Differential Revision: https://reviews.llvm.org/D32108 llvm-svn: 300856
* [InstCombine] Matchers work with both ConstExpr and Instructions.Davide Italiano2017-04-171-2/+2
| | | | | | | | | | So, `cast<Instruction>` is not guaranteed to succeed. Change the code so that we create a new constant and use it in the newly created instruction, as it's done in other places in InstCombine. OK'ed by Sanjay/Craig. Fixes PR32686. llvm-svn: 300495
* [InstCombine] allow (X != C1 && X != C2) and similar patterns to match splat ↵Sanjay Patel2017-04-151-19/+19
| | | | | | vector constants llvm-svn: 300402
* [InstCombine] (X != C1 && X != C2) --> (X | (C1 ^ C2)) != C2Sanjay Patel2017-04-141-36/+65
| | | | | | | | | | ...when C1 differs from C2 by one bit and C1 <u C2: http://rise4fun.com/Alive/Vuo And move related folds to a helper function. This reduces code duplication and will make it easier to remove the scalar-only restriction as a follow-up step. llvm-svn: 300364
* [InstCombine] fold X == 0 || X == -1 to one compare (PR32524)Sanjay Patel2017-04-131-1/+5
| | | | | | | | | | | | | | | | This is effectively a retry of: https://reviews.llvm.org/rL299851 but now we have tests and an assert to make sure the bug that was exposed with that attempt will not happen again. I'll fix the code duplication and missing sibling fold next, but I want to make this change as small as possible to reduce risk since I messed it up last time. This should fix: https://bugs.llvm.org/show_bug.cgi?id=32524 llvm-svn: 300236
* [InstCombine] use similar ops for related folds; NFCISanjay Patel2017-04-131-10/+9
| | | | | | | | | | | | | | | It's less efficient to produce 'ule' than 'ult' since we know we're going to canonicalize to 'ult', but we shouldn't have duplicated code for these folds. As a trade-off, this was a pretty terrible way to make a '2'. :) if (LHSC == SubOne(RHSC)) AddC = ConstantExpr::getSub(AddOne(RHSC), LHSC); The next steps are to share the code to fix PR32524 and add the missing 'and' fold that was left out when PR14708 was fixed: https://bugs.llvm.org/show_bug.cgi?id=14708 llvm-svn: 300222
* [InstCombine] fix assert to not always be trueSanjay Patel2017-04-131-1/+1
| | | | llvm-svn: 300202
* [InstCombine] morph an existing instruction instead of creating a new oneSanjay Patel2017-04-121-7/+6
| | | | | | | | | | | | One potential way to make InstCombine (very slightly?) faster is to recycle instructions when possible instead of creating new ones. It's not explicitly stated AFAIK, but we don't consider this an "InstSimplify". We could, however, make a new layer to house transforms like this if that makes InstCombine more manageable (just throwing out an idea; not sure how much opportunity is actually here). Differential Revision: https://reviews.llvm.org/D31863 llvm-svn: 300067
* [InstCombine][IR] Add a commutable BinOp matcher. Use it to reduce some ↵Craig Topper2017-04-121-2/+1
| | | | | | code. NFC llvm-svn: 300030
* revert r299851 - [InstCombine] fix matching of or-of-icmps constants (PR32524)Sanjay Patel2017-04-111-16/+12
| | | | | | This is a candidate culprit for multiple bot fails, so reverting pending investigation. llvm-svn: 299955
* [InstCombine] improve variable names; NFCISanjay Patel2017-04-101-34/+34
| | | | llvm-svn: 299871
* [InstCombine] fix matching of or-of-icmps constants (PR32524)Sanjay Patel2017-04-101-12/+16
| | | | | | | | | | | Also, make the same change in and-of-icmps and remove a hack for detecting that case. Finally, add some FIXME comments because the code duplication here is awful. This should fix the remaining IR problem noted in: https://bugs.llvm.org/show_bug.cgi?id=32524 llvm-svn: 299851
* [InstCombine] use m_c_And and m_c_Xor to handle commuted versions of a ↵Craig Topper2017-04-101-2/+2
| | | | | | transform. llvm-svn: 299837
* [InstCombine] Remove unnecessary dyn_cast to BinaryOperator around some ↵Craig Topper2017-04-101-31/+29
| | | | | | | | matcher checks in visitXor. The matchers themselves should be enough. llvm-svn: 299835
* [InstCombine] Make the (A|B)^B -> A & ~B transform code consistent with the ↵Craig Topper2017-04-101-5/+5
| | | | | | | | very similar (A&B)^B -> ~A & B code. This should be NFC except for the addition of hasOneUse check. I think this code is still overly complicated and should use matchers, but first I wanted to make it consistent. llvm-svn: 299834
* [InstCombine] Use m_OneUse to shorten some code. NFCCraig Topper2017-04-101-6/+3
| | | | llvm-svn: 299833
* [InstCombine] remove dead cases from icmp pair switches; NFCISanjay Patel2017-04-091-32/+0
| | | | | | | | | | | | "PredicatesFoldable" returns false for signed/unsigned mismatched pairs, so these cases should never exist. We'll default to 'unreachable' on those predicate combos instead. Most of what's left in these switches belongs in InstSimplify (and may already be there), so there's probably more that can be done to reduce this code. llvm-svn: 299829
* [InstCombine] Extend some OR combines to support vectors.Craig Topper2017-04-091-19/+23
| | | | | | | | This adds support for these combines for vectors (X^C)|Y -> (X|Y)^C iff Y&C == 0 Y|(X^C) -> (X|Y)^C iff Y&C == 0 llvm-svn: 299822
* [InstCombine] Extend a canonicalization check to apply to vector constants too.Craig Topper2017-04-091-1/+2
| | | | llvm-svn: 299821
* [InstCombine] Use the SubOne helper function to shorten some code. NFCCraig Topper2017-04-091-7/+4
| | | | llvm-svn: 299819
* [InstCombine] rename variable for easier reading; NFCCraig Topper2017-04-091-9/+9
| | | | | | We usually give constants a 'C' somewhere in the name... llvm-svn: 299818
* [InstCombine] Handle more commuted cases of ((A & B) | ~A) -> (~A | B)Craig Topper2017-04-071-3/+4
| | | | llvm-svn: 299747
* [InstCombine] Add more commuted patterns to support folding ((~A & B) | A) ↵Craig Topper2017-04-071-3/+4
| | | | | | -> (A | B). llvm-svn: 299737
* [InstCombine] Remove redundant combine from visitAndCraig Topper2017-04-061-90/+0
| | | | | | | | This combine is fully handled by SimplifyDemandedInstructionBits as of r299658 where I fixed this code to ensure the Add/Sub had only a single user. Otherwise it would fire and create additional instructions. That fix resulted in an improvement to code generated for tsan which is why I committed it before deleting. Differential Revision: https://reviews.llvm.org/D31543 llvm-svn: 299704
* [InstCombine] Fix a case where we weren't checking that an instruction had a ↵Craig Topper2017-04-061-6/+9
| | | | | | single use resulting in extra instructions being created. llvm-svn: 299658
* [InstCombine] fix formatting and variable names; NFCISanjay Patel2017-04-051-236/+252
| | | | | | | There must be some opportunity to refactor big chunks of nearly duplicated code in FoldOrOfICmps / FoldAndOfICmps. Also, none of this works with vectors, but it should. llvm-svn: 299568
* [InstCombine] Support folding and/or/xor with a constant vector RHS into ↵Craig Topper2017-04-041-3/+6
| | | | | | | | | | selects and phis Currently we only fold with ConstantInt RHS. This generalizes to any Constant RHS. Differential Revision: https://reviews.llvm.org/D31610 llvm-svn: 299466
* [InstCombine] Remove canonicalization for (X & C1) | C2 --> (X | C2) & ↵Craig Topper2017-04-031-11/+0
| | | | | | | | | | (C1|C2) when C1 & C2 have common bits. It turns out that SimplifyDemandedInstructionBits will get called earlier and remove bits from C1 first. Effectively doing (X & (C1&C2)) | C2. So by the time it got to this check there could be no common bits. I think the DAGCombiner has the same check but its check can be executed because it handles demanded bits later. I'll look at it next. llvm-svn: 299384
* [DAGCombine][InstCombine] Fix inverted if condition in equivalent comments ↵Craig Topper2017-04-031-1/+1
| | | | | | in DAGCombine and InstCombine. NFC llvm-svn: 299378
* Revert r299337 "[InstCombine] Remove redundant combine from visitAnd"Craig Topper2017-04-031-0/+87
| | | | | | | | One of the tsan bots started failing at this commit. I don't see anything obviously wrong with the commit so trying this to see if it recovers. Failing log: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-autoconf/builds/6792 llvm-svn: 299366
* [InstCombine] fix formatting for foldLogOpOfMaskedICmps and related bits; NFCISanjay Patel2017-04-031-145/+158
| | | | | | | | | | | | 1. Improve enum, function, and variable names. 2. Improve comments. 3. Fix variable capitalization. 4. Run clang-format. As an existing code comment suggests, this should work with vector types / splat constants too, so making this look right first will reduce the diffs needed for that change. llvm-svn: 299365
* [InstCombine] Remove a And transform that should be handled by ↵Craig Topper2017-04-031-7/+0
| | | | | | SimplifyDemandedInstructionBits. NFCI llvm-svn: 299349
* [InstCombine] Make InstCombiner::OptAndOp take a BinaryOperator instead of ↵Craig Topper2017-04-021-3/+3
| | | | | | | | | | an Instruction. The callers have already performed the necessary cast before calling. This allows us to remove a comment that says the instruction must be a BinaryOperator and make it explicit in the argument type. Had to add a default case to the switch because BinaryOperator::getOpcode() returns a BinaryOps enum. llvm-svn: 299339
* [InstCombine] Remove redundant combine from visitAndCraig Topper2017-04-021-87/+0
| | | | | | | | | | As far as I can tell this combine is fully handled by SimplifyDemandedInstructionBits. I was only looking at this because it is the only user of APIntOps::isShiftedMask which is itself broken. As demonstrated by r299187. I was going to fix isShiftedMask and needed to make sure we had coverage for the new cases it would expose to this combine. But looks like we can nuke it instead. Differential Revision: https://reviews.llvm.org/D31543 llvm-svn: 299337
* [APInt] Fix bugs in isShiftedMask to match behavior of the similar function ↵Craig Topper2017-03-311-1/+1
| | | | | | | | | | in MathExtras.h This removes a parameter from the routine that was responsible for a lot of the issue. It was a bit count that had to be set to the BitWidth of the APInt and would get passed to getLowBitsSet. This guaranteed the call to getLowBitsSet would create an all ones value. This was then compared to (V | (V-1)). So the only shifted masks we detected had to have the MSB set. The one in tree user is a transform in InstCombine that never fires due to earlier transforms covering the case better. I've submitted a patch to remove it completely, but for now I've just adapted it to the new interface for isShiftedMask. llvm-svn: 299273
* [InstCombine] Remove some code from visitAnd that dealt with trying to ↵Craig Topper2017-03-231-12/+0
| | | | | | | | reduce the LHS of a sub to 0. This should now be fully handled by SimplifyDemandedInstructionBits now. Now that we call ShrinkDemandedConstant on the RHS of sub this should be taken care of. This code doesn't trigger on any in tree regressions, but did before ShrinkDemandedConstant was added to the RHS. llvm-svn: 298644
OpenPOWER on IntegriCloud