summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* fix variable names, typos ; NFCSanjay Patel2016-01-181-36/+36
| | | | llvm-svn: 258058
* fix typo; NFCSanjay Patel2016-01-181-1/+1
| | | | llvm-svn: 258057
* [InstCombine] Rewrite bswap/bitreverse handling completely.James Molloy2016-01-151-179/+8
| | | | | | | | | | | | | | There are several requirements that ended up with this design; 1. Matching bitreversals is too heavyweight for InstCombine and doesn't really need to be done so early. 2. Bitreversals and byteswaps are very related in their matching logic. 3. We want to implement support for matching more advanced bswap/bitreverse patterns like partial bswaps/bitreverses. 4. Bswaps are best matched early in InstCombine. The result of these is that a new utility function is created in Transforms/Utils/Local.h that can be configured to search for bswaps, bitreverses or both. InstCombine uses it to find only bswaps, CGP uses it to find only bitreversals. We can then extend the matching logic in one place only. llvm-svn: 257875
* getParent() ^ 3 == getModule() ; NFCISanjay Patel2015-12-141-6/+4
| | | | llvm-svn: 255511
* [InstCombine] Make MatchBSwap also match bit reversalsJames Molloy2015-12-111-102/+135
| | | | | | MatchBSwap has most of the functionality to match bit reversals already. If we switch it from looking at bytes to individual bits and remove a few early exits, we can extend the main recursive function to match any sequence of ORs, ANDs and shifts that assemble a value from different parts of another, base value. Once we have this bit->bit mapping, we can very simply detect if it is appropriate for a bswap or bitreverse. llvm-svn: 255334
* Do (A == C1 || A == C2) -> (A & ~(C1 ^ C2)) == C1 rather than (A == C1 || A ↵David Majnemer2015-12-021-4/+4
| | | | | | | | | | == C2) -> (A | (C1 ^ C2)) == C2 when C1 ^ C2 is a power of 2. Differential Revision: http://reviews.llvm.org/D14223 Patch by Amaury SECHET! llvm-svn: 254518
* [InstCombine] transform masking off of an FP sign bit into a fabs() ↵Sanjay Patel2015-10-081-4/+19
| | | | | | | | | | | | | | | | | | intrinsic call (PR24886) This is a partial fix for PR24886: https://llvm.org/bugs/show_bug.cgi?id=24886 Without this IR transform, the backend (x86 at least) was producing inefficient code. This patch is making 2 assumptions: 1. The canonical form of a fabs() operation is, in fact, the LLVM fabs() intrinsic. 2. The high bit of an FP value is always the sign bit; as noted in the bug report, this isn't specified by the LangRef. Differential Revision: http://reviews.llvm.org/D13076 llvm-svn: 249702
* [InstCombine] match De Morgan's Law hidden by zext ops (PR22723)Sanjay Patel2015-09-251-5/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a fix for PR22723: https://llvm.org/bugs/show_bug.cgi?id=22723 My first attempt at this was to change what I thought was the root problem: xor (zext i1 X to i32), 1 --> zext (xor i1 X, true) to i32 ...but we create the opposite pattern in InstCombiner::visitZExt(), so infinite loop! My next idea was to fix the matchIfNot() implementation in PatternMatch, but that would mean potentially returning a different size for the match than what was input. I think this would require all users of m_Not to check the size of the returned match, so I abandoned that idea. I settled on just fixing the exact case presented in the PR. This patch does allow the 2 functions in PR22723 to compile identically (x86): bool test(bool x, bool y) { return !x | !y; } bool test(bool x, bool y) { return !x || !y; } ... andb %sil, %dil xorb $1, %dil movb %dil, %al retq Differential Revision: http://reviews.llvm.org/D12705 llvm-svn: 248634
* [InstCombine] Recognize another bswap idiom.Charlie Turner2015-09-241-5/+9
| | | | | | | | | | | | | | | | | | | | | | | | Summary: The byte-swap recognizer can now notice that this ``` uint32_t bswap(uint32_t x) { x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16; x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8; return x; } ``` is a bswap. Fixes PR23863. Reviewers: nlewycky, hfinkel, hans, jmolloy, rengolin Subscribers: majnemer, rengolin, llvm-commits Differential Revision: http://reviews.llvm.org/D12637 llvm-svn: 248482
* refactor matches for De Morgan's Laws; NFCISanjay Patel2015-09-081-17/+32
| | | | llvm-svn: 247061
* remove function names from comments; NFCSanjay Patel2015-09-081-49/+45
| | | | llvm-svn: 247043
* Optimize bitwise even/odd test (-x&1 -> x&1) to not use negation.Balaram Makam2015-08-201-0/+4
| | | | | | | | | | | | Summary: We know that -x & 1 is equivalent to x & 1, avoid using negation for testing if a negative integer is even or odd. Reviewers: majnemer Subscribers: junbuml, mssimpso, gberry, mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D12156 llvm-svn: 245569
* Fix a crash where a utility function wasn't aware of fcmp vectors and ↵Nick Lewycky2015-08-141-1/+2
| | | | | | created a value with the wrong type. Fixes PR24458! llvm-svn: 245119
* [ConstantRange] Split makeICmpRegion in two.Sanjoy Das2015-03-181-2/+2
| | | | | | | | | | | | | | | | | | | | Summary: This change splits `makeICmpRegion` into `makeAllowedICmpRegion` and `makeSatisfyingICmpRegion` with slightly different contracts. The first one is useful for determining what values some expression //may// take, given that a certain `icmp` evaluates to true. The second one is useful for determining what values are guaranteed to //satisfy// a given `icmp`. Reviewers: nlewycky Reviewed By: nlewycky Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8345 llvm-svn: 232575
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-6/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Now that the DataLayout is a mandatory part of the module, let's start cleaning the codebase. This patch is a first attempt at doing that. This patch is not exactly NFC as for instance some places were passing a nullptr instead of the DataLayout, possibly just because there was a default value on the DataLayout argument to many functions in the API. Even though it is not purely NFC, there is no change in the validation. I turned as many pointer to DataLayout to references, this helped figuring out all the places where a nullptr could come up. I had initially a local version of this patch broken into over 30 independant, commits but some later commit were cleaning the API and touching part of the code modified in the previous commits, so it seemed cleaner without the intermediate state. Test Plan: Reviewers: echristo Subscribers: llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231740
* New instcombine rule: max(~a,~b) -> ~min(a, b)Sanjoy Das2015-02-241-21/+5
| | | | | | | | | | This case is interesting because ScalarEvolutionExpander lowers min(a, b) as ~max(~a,~b). I think the profitability heuristics can be made more clever/aggressive, but this is a start. Differential Revision: http://reviews.llvm.org/D7821 llvm-svn: 230285
* InstCombine: Allow folding of xor into icmp by changing the predicate for ↵Benjamin Kramer2015-02-121-3/+4
| | | | | | | | vectors The loop vectorizer can create this pattern. llvm-svn: 228954
* [PM] Rename InstCombine.h to InstCombineInternal.h in preparation forChandler Carruth2015-01-221-1/+1
| | | | | | | | | | | | | | | | creating a non-internal header file for the InstCombine pass. I thought about calling this InstCombiner.h or in some way more clearly associating it with the InstCombiner clas that it is primarily defining, but there are several other utility interfaces defined within this for InstCombine. If, in the course of refactoring, those end up moving elsewhere or going away, it might make more sense to make this the combiner's header alone. Naturally, this is a bikeshed to a certain degree, so feel free to lobby for a different shade of paint if this name just doesn't suit you. llvm-svn: 226783
* [PM] Split the AssumptionTracker immutable pass into two separate APIs:Chandler Carruth2015-01-041-9/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | a cache of assumptions for a single function, and an immutable pass that manages those caches. The motivation for this change is two fold. Immutable analyses are really hacks around the current pass manager design and don't exist in the new design. This is usually OK, but it requires that the core logic of an immutable pass be reasonably partitioned off from the pass logic. This change does precisely that. As a consequence it also paves the way for the *many* utility functions that deal in the assumptions to live in both pass manager worlds by creating an separate non-pass object with its own independent API that they all rely on. Now, the only bits of the system that deal with the actual pass mechanics are those that actually need to deal with the pass mechanics. Once this separation is made, several simplifications become pretty obvious in the assumption cache itself. Rather than using a set and callback value handles, it can just be a vector of weak value handles. The callers can easily skip the handles that are null, and eventually we can wrap all of this up behind a filter iterator. For now, this adds boiler plate to the various passes, but this kind of boiler plate will end up making it possible to port these passes to the new pass manager, and so it will end up factored away pretty reasonably. llvm-svn: 225131
* InstCombe: Infer nsw for multipliesDavid Majnemer2014-12-261-2/+1
| | | | | | | We already utilize this logic for reducing overflow intrinsics, it makes sense to reuse it for normal multiplies as well. llvm-svn: 224847
* [InstCombine] Minor optimization for bswap with binary opsSimon Pilgrim2014-12-041-0/+64
| | | | | | | | | | | | | | | | | Added instcombine optimizations for BSWAP with AND/OR/XOR ops: OP( BSWAP(x), BSWAP(y) ) -> BSWAP( OP(x, y) ) OP( BSWAP(x), CONSTANT ) -> BSWAP( OP(x, BSWAP(CONSTANT) ) ) Since its just a one liner, I've also added BSWAP to the DAGCombiner equivalent as well: fold (OP (bswap x), (bswap y)) -> (bswap (OP x, y)) Refactored bswap-fold tests to use FileCheck instead of just checking that the bswaps had gone. Differential Revision: http://reviews.llvm.org/D6407 llvm-svn: 223349
* InstCombine: simplify signed range checksErik Eckstein2014-12-031-0/+73
| | | | | | | | | Try to convert two compares of a signed range check into a single unsigned compare. Examples: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n llvm-svn: 223224
* InstCombine: FoldOrOfICmps harderDavid Majnemer2014-11-281-2/+25
| | | | | | | | | | | | We may be in a situation where the icmps might not be near each other in a tree of or instructions. Try to dig out related compare instructions and see if they combine. N.B. This won't fire on deep trees of compares because rewritting the tree might end up creating a net increase of IR. We may have to resort to something more sophisticated if this is a real problem. llvm-svn: 222928
* InstCombine: Fold away tautological masked comparesDavid Majnemer2014-11-181-1/+1
| | | | | | | | | It is impossible for (x & INT_MAX) == 0 && x == INT_MAX to ever be true. While this sort of reasoning should normally live in InstSimplify, the machinery that derives this result is not trivial to split out. llvm-svn: 222230
* InstCombine: Clean up foldLogOpOfMaskedICmpsDavid Majnemer2014-11-181-16/+14
| | | | | | No functional change intended. llvm-svn: 222229
* InstCombine: Turn (x != 0 & x <u C) into the canonical range check form (x-1 ↵Benjamin Kramer2014-10-121-0/+2
| | | | | | <u C-1) llvm-svn: 219585
* Make use of @llvm.assume in ValueTracking (computeKnownBits, etc.)Hal Finkel2014-09-071-21/+29
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change, which allows @llvm.assume to be used from within computeKnownBits (and other associated functions in ValueTracking), adds some (optional) parameters to computeKnownBits and friends. These functions now (optionally) take a "context" instruction pointer, an AssumptionTracker pointer, and also a DomTree pointer, and most of the changes are just to pass this new information when it is easily available from InstSimplify, InstCombine, etc. As explained below, the significant conceptual change is that known properties of a value might depend on the control-flow location of the use (because we care that the @llvm.assume dominates the use because assumptions have control-flow dependencies). This means that, when we ask if bits are known in a value, we might get different answers for different uses. The significant changes are all in ValueTracking. Two main changes: First, as with the rest of the code, new parameters need to be passed around. To make this easier, I grouped them into a structure, and I made internal static versions of the relevant functions that take this structure as a parameter. The new code does as you might expect, it looks for @llvm.assume calls that make use of the value we're trying to learn something about (often indirectly), attempts to pattern match that expression, and uses the result if successful. By making use of the AssumptionTracker, the process of finding @llvm.assume calls is not expensive. Part of the structure being passed around inside ValueTracking is a set of already-considered @llvm.assume calls. This is to prevent a query using, for example, the assume(a == b), to recurse on itself. The context and DT params are used to find applicable assumptions. An assumption needs to dominate the context instruction, or come after it deterministically. In this latter case we only handle the specific case where both the assumption and the context instruction are in the same block, and we need to exclude assumptions from being used to simplify their own ephemeral values (those which contribute only to the assumption) because otherwise the assumption would prove its feeding comparison trivial and would be removed. This commit adds the plumbing and the logic for a simple masked-bit propagation (just enough to write a regression test). Future commits add more patterns (and, correspondingly, more regression tests). llvm-svn: 217342
* InstCombine: Remove a special case patternDavid Majnemer2014-09-051-15/+18
| | | | | | | The special case did not work when run under -reassociate and can easily be expressed by a further generalization of an existing pattern. llvm-svn: 217227
* InstCombine: Try harder to combine icmp instructionsDavid Majnemer2014-08-301-3/+25
| | | | | | | | | | | | | consider: (and (icmp X, Y), (and Z, (icmp A, B))) It may be possible to combine (icmp X, Y) with (icmp A, B). If we successfully combine, create an 'and' instruction with Z. This fixes PR20814. N.B. There is room for improvement after this change but I'm not convinced it's worth chasing yet. llvm-svn: 216814
* This patch enables SimplifyUsingDistributiveLaws() to handle following pattens.Dinesh Dwivedi2014-08-261-39/+0
| | | | | | | | | | | | (X >> Z) & (Y >> Z) -> (X&Y) >> Z for all shifts. (X >> Z) | (Y >> Z) -> (X|Y) >> Z for all shifts. (X >> Z) ^ (Y >> Z) -> (X^Y) >> Z for all shifts. These patterns were previously handled separately in visitAnd()/visitOr()/visitXor(). Differential Revision: http://reviews.llvm.org/D4951 llvm-svn: 216443
* InstCombine: Fold ((A | B) & C1) ^ (B & C2) -> (A & C1) ^ B if C1^C2=-1David Majnemer2014-08-211-0/+44
| | | | | | Adapted from a patch by Richard Smith, test-case written by me. llvm-svn: 216157
* New InstCombine pattern: (icmp ult/ule (A + C1), C3) | (icmp ult/ule (A + ↵Yi Jiang2014-08-201-0/+55
| | | | | | C2), C3) to (icmp ult/ule ((A & ~(C1 ^ C2)) + max(C1, C2)), C3) under certain condition llvm-svn: 216135
* InstCombine: ((A & ~B) ^ (~A & B)) to A ^ BMayur Pandey2014-08-191-0/+10
| | | | | | | | | | | | | Proof using CVC3 follows: $ cat t.cvc A, B : BITVECTOR(32); QUERY BVXOR((A & ~B),(~A & B)) = BVXOR(A,B); $ cvc3 t.cvc Valid. Differential Revision: http://reviews.llvm.org/D4898 llvm-svn: 215974
* test commit (spelling correction)Mayur Pandey2014-08-191-1/+1
| | | | llvm-svn: 215970
* InstCombine: ((A | ~B) ^ (~A | B)) to A ^ BDavid Majnemer2014-08-141-0/+10
| | | | | | | | | | | | | | | Proof using CVC3 follows: $ cat t.cvc A, B : BITVECTOR(32); QUERY BVXOR((A | ~B),(~A |B)) = BVXOR(A,B); $ cvc3 t.cvc Valid. Patch by Mayur Pandey! Differential Revision: http://reviews.llvm.org/D4883 llvm-svn: 215621
* Added InstCombine Transform for ((B | C) & A) | B -> B | (A & C)David Majnemer2014-08-141-0/+4
| | | | | | | | | | | | Transform ((B | C) & A) | B --> B | (A & C) Z3 Link: http://rise4fun.com/Z3/hP6p Patch by Sonam Kumari! Differential Revision: http://reviews.llvm.org/D4865 llvm-svn: 215619
* InstCombine: Combine (xor (or %a, %b) (xor %a, %b)) to (add %a, %b)Karthik Bhat2014-08-131-0/+12
| | | | | | | | | | | | | Correctness proof of the transform using CVC3- $ cat t.cvc A, B : BITVECTOR(32); QUERY BVXOR(A | B, BVXOR(A,B) ) = A & B; $ cvc3 t.cvc Valid. llvm-svn: 215524
* This patch implements transform for pattern "(A & ~B) ^ (~A) -> ~(A & B)".Suyog Sarda2014-08-011-0/+5
| | | | | | Differential Revision: http://reviews.llvm.org/D4653 llvm-svn: 214479
* This patch implements transform for pattern "(A | B) & ((~A) ^ B) -> (A & B)".Suyog Sarda2014-08-011-0/+10
| | | | | | Differential Revision: http://reviews.llvm.org/D4628 llvm-svn: 214478
* This patch implements transform for pattern "( A & (~B)) | (A ^ B) -> (A ^ B)"Suyog Sarda2014-08-011-0/+10
| | | | | | Differential Revision: http://reviews.llvm.org/D4652 llvm-svn: 214477
* This patch implements transform for pattern "(A & B) | ((~A) ^ B) -> (~A ^ B)".Suyog Sarda2014-08-011-0/+10
| | | | | | | | Patch Credit to Ankit Jain ! Differential Revision: http://reviews.llvm.org/D4655 llvm-svn: 214476
* InstCombine: Simplify (A ^ B) or/and (A ^ B ^ C)David Majnemer2014-07-301-0/+24
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | While we can already transform A | (A ^ B) into A | B, things get bad once we have (A ^ B) | (A ^ B ^ Cst) because reassociation will morph this into (A ^ B) | ((A ^ Cst) ^ B). Our existing patterns fail once this happens. To fix this, we add a new pattern which looks through the tree of xor binary operators to see that, in fact, there exists a redundant xor operation. What follows bellow is a correctness proof of the transform using CVC3. $ cat t.cvc A, B, C : BITVECTOR(64); QUERY BVXOR(A, B) | BVXOR(BVXOR(B, C), A) = BVXOR(A, B) | C; QUERY BVXOR(BVXOR(A, C), B) | BVXOR(A, B) = BVXOR(A, B) | C; QUERY BVXOR(A, B) & BVXOR(BVXOR(B, C), A) = BVXOR(A, B) & ~C; QUERY BVXOR(BVXOR(A, C), B) & BVXOR(A, B) = BVXOR(A, B) & ~C; $ cvc3 < t.cvc Valid. Valid. Valid. Valid. llvm-svn: 214342
* Added InstCombine transform for pattern "(A & B) ^ (A ^ B) -> (A | B)"Suyog Sarda2014-07-221-0/+8
| | | | | | | | Patch idea by Ankit Jain ! Differential Revision: http://reviews.llvm.org/D4618 llvm-svn: 213677
* Added InstCombine Transform for patterns: Suyog Sarda2014-07-221-0/+10
| | | | | | | | | | "((~A & B) | A) -> (A | B)" and "((A & B) | ~A) -> (~A | B)" Original Patch credit to Ankit Jain !! Differential Revision: http://reviews.llvm.org/D4591 llvm-svn: 213676
* This patch implements transform for pattern "(A | B) ^ (~A) -> (A | ~B)".Suyog Sarda2014-07-221-0/+6
| | | | | | | | Patch Credit to Ankit Jain !! Differential Revision: http://reviews.llvm.org/D4588 llvm-svn: 213662
* Move optimization of some cases of (A & C1)|(B & C2) from instcombine to ↵Nick Lewycky2014-06-191-23/+0
| | | | | | instsimplify. Patch by Rahul Jain, plus some last minute changes by me -- you can blame me for any bugs. llvm-svn: 211252
* Reorder shuffle and binary operation.Serge Pavlov2014-05-111-0/+9
| | | | | | | | | | | | | This patch enables transformations: BinOp(shuffle(v1), shuffle(v2)) -> shuffle(BinOp(v1, v2)) BinOp(shuffle(v1), const1) -> shuffle(BinOp, const2) They allow to eliminate extra shuffles in some cases. Differential Revision: http://reviews.llvm.org/D3525 llvm-svn: 208488
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-69/+69
| | | | llvm-svn: 207196
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | | | | | | definition below all of the header #include lines, lib/Transforms/... edition. This one is tricky for two reasons. We again have a couple of passes that define something else before the includes as well. I've sunk their name macros with the DEBUG_TYPE. Also, InstCombine contains headers that need DEBUG_TYPE, so now those headers #define and #undef DEBUG_TYPE around their code, leaving them well formed modular headers. Fixing these headers was a large motivation for all of these changes, as "leaky" macros of this form are hard on the modules implementation. llvm-svn: 206844
* [Modules] Sink all the DEBUG_TYPE defines for InstCombine out of theChandler Carruth2014-04-211-0/+1
| | | | | | | | | | | header files and into the cpp files. These files will require more touches as the header files actually use DEBUG(). Eventually, I'll have to introduce a matched #define and #undef of DEBUG_TYPE for the header files, but that comes as step N of many to clean all of this up. llvm-svn: 206777
OpenPOWER on IntegriCloud