summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine
Commit message (Collapse)AuthorAgeFilesLines
* [InstCombine] add (ashr (shl i32 X, 31), 31), 1 --> and (not X), 1Sanjay Patel2017-05-101-0/+10
| | | | | | | | | | | | | | This is another step towards favoring 'not' ops over random 'xor' in IR: https://bugs.llvm.org/show_bug.cgi?id=32706 This transformation may have occurred in longer IR sequences using computeKnownBits, but that could be much more expensive to calculate. As the scalar result shows, we do not currently favor 'not' in all cases. The 'not' created by the transform is transformed again (unnecessarily). Vectors don't have this problem because vectors are (wrongly) excluded from several other combines. llvm-svn: 302659
* [InstCombine] add helper function for add X, C folds; NFCISanjay Patel2017-05-101-34/+45
| | | | llvm-svn: 302605
* [InstCombine] clean up matchDeMorgansLaws(); NFCISanjay Patel2017-05-091-32/+13
| | | | | | | | | | | | | | The motivation for getting rid of dyn_castNotVal is to allow fixing: https://bugs.llvm.org/show_bug.cgi?id=32706 So this was supposed to be functional-change-intended for the case of inverting constants and applying DeMorgan. However, I can't find any cases where that pattern will actually get to matchDeMorgansLaws() because we have other folds in visitAnd/visitOr that do the same thing. So this ends up just being a clean-up patch with slight efficiency improvement, but no-functional-change-intended. llvm-svn: 302581
* [InstCombineCasts] Fix checks in sext->lshr->trunc pattern.Sanjay Patel2017-05-091-6/+14
| | | | | | | | | | | | | | | The comment says to avoid the case where zero bits are shifted into the truncated value, but the code checks that the shift is smaller than the truncated value instead of the number of bits added by the sign extension. Fixing this allows a shift by more than the value size to be introduced, which is undefined behavior, so the shift is capped at the value size minus one, which has the expected behavior of filling the value with the sign bit. Patch by Jacob Young! Differential Revision: https://reviews.llvm.org/D32285 llvm-svn: 302548
* [InstCombine] add folds for not-of-shift-rightSanjay Patel2017-05-081-15/+32
| | | | | | | | | | | | | | | This is another step towards getting rid of dyn_castNotVal, so we can recommit: https://reviews.llvm.org/rL300977 As the tests show, we were missing the lshr case for constants and both ashr/lshr vector splat folds. The ashr case with constant was being performed inefficiently in 2 steps. It's also possible there was a latent bug in that case because we can't do that fold if the constant is positive: http://rise4fun.com/Alive/Bge llvm-svn: 302465
* [InstCombine] use local variable to reduce code duplication; NFCISanjay Patel2017-05-081-14/+11
| | | | llvm-svn: 302438
* [InstCombine/InstSimplify] add comments about code duplication; NFCSanjay Patel2017-05-081-0/+3
| | | | llvm-svn: 302436
* [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
* [KnownBits] Add wrapper methods for setting and clear all bits in the ↵Craig Topper2017-05-053-4/+3
| | | | | | | | | | underlying APInts in KnownBits. This adds routines for reseting KnownBits to unknown, making the value all zeros or all ones. It also adds methods for querying if the value is zero, all ones or unknown. Differential Revision: https://reviews.llvm.org/D32637 llvm-svn: 302262
* [InstCombine][KnownBits] Use KnownBits better to detect nsw addsCraig Topper2017-05-031-32/+44
| | | | | | | | | | | Change checkRippleForAdd from a heuristic to a full check - if it is provable that the add does not overflow return true, otherwise false. Patch by Yoav Ben-Shalom Differential Revision: https://reviews.llvm.org/D32686 llvm-svn: 302093
* [KnownBits] Add methods for determining if KnownBits is a constant valueCraig Topper2017-05-031-4/+4
| | | | | | | | This patch adds isConstant and getConstant for determining if KnownBits represents a constant value and to retrieve the value. Use them to simplify code. Differential Revision: https://reviews.llvm.org/D32785 llvm-svn: 302091
* [KnownBits] Add zext, sext, and trunc methods to KnownBitsCraig Topper2017-05-031-12/+6
| | | | | | | | This patch adds zext, sext, and trunc methods to KnownBits and uses them where possible. Differential Revision: https://reviews.llvm.org/D32784 llvm-svn: 302088
* [IR] Abstract away ArgNo+1 attribute indexing as much as possibleReid Kleckner2017-05-031-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Do three things to help with that: - Add AttributeList::FirstArgIndex, which is an enumerator currently set to 1. It allows us to change the indexing scheme with fewer changes. - Add addParamAttr/removeParamAttr. This just shortens addAttribute call sites that would otherwise need to spell out FirstArgIndex. - Remove some attribute-specific getters and setters from Function that take attribute list indices. Most of these were only used from BuildLibCalls, and doesNotAlias was only used to test or set if the return value is malloc-like. I'm happy to split the patch, but I think they are probably easier to review when taken together. This patch should be NFC, but it sets the stage to change the indexing scheme to this, which is more convenient when indexing into an array: 0: func attrs 1: retattrs 2...: arg attrs Reviewers: chandlerc, pete, javed.absar Subscribers: david2050, llvm-commits Differential Revision: https://reviews.llvm.org/D32811 llvm-svn: 302060
* [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
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-05-011-4/+4
| | | | | | This relands r301424. llvm-svn: 301812
* [KnownBits] Add methods for determining if the known bits represent a ↵Craig Topper2017-04-291-4/+4
| | | | | | | | | | | | | | | | negative/nonnegative number and add methods for changing the negative/nonnegative state Summary: This patch adds isNegative, isNonNegative for querying whether the sign bit is known. It also adds makeNegative and makeNonNegative for controlling the sign bit. Reviewers: RKSimon, spatel, davide Reviewed By: RKSimon Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32651 llvm-svn: 301747
* [APInt] Add clearSignBit method. Use it and setSignBit in a few places. NFCICraig Topper2017-04-282-3/+3
| | | | llvm-svn: 301656
* [APInt] Use inplace shift methods where possible. NFCICraig Topper2017-04-282-2/+2
| | | | llvm-svn: 301612
* [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 APInt bit counting methods to avoid a temporary APInt. NFCCraig Topper2017-04-271-6/+6
| | | | llvm-svn: 301516
* InstCombine: Use the new SimplifyQuery versions of Simplify*. Use ↵Daniel Berlin2017-04-2611-68/+68
| | | | | | AssumptionCache, DominatorTree, TargetLibraryInfo everywhere. llvm-svn: 301464
* [ValueTracking] Introduce a KnownBits struct to wrap the two APInts for ↵Craig Topper2017-04-268-321/+284
| | | | | | | | | | | | | | | | computeKnownBits This patch introduces a new KnownBits struct that wraps the two APInt used by computeKnownBits. This allows us to treat them as more of a unit. Initially I've just altered the signatures of computeKnownBits and InstCombine's simplifyDemandedBits to pass a KnownBits reference instead of two separate APInt references. I'll do similar to the SelectionDAG version of computeKnownBits/simplifyDemandedBits as a separate patch. I've added a constructor that allows initializing both APInts to the same bit width with a starting value of 0. This reduces the repeated pattern of initializing both APInts. Once place default constructed the APInts so I added a default constructor for those cases. Going forward I would like to add more methods that will work on the pairs. For example trunc, zext, and sext occur on both APInts together in several places. We should probably add a clear method that can be used to clear both pieces. Maybe a method to check for conflicting information. A method to return (Zero|One) so we don't write it out everywhere. Maybe a method for (Zero|One).isAllOnesValue() to determine if all bits are known. I'm sure there are many other methods we can come up with. Differential Revision: https://reviews.llvm.org/D32376 llvm-svn: 301432
* Reverts commit r301424, r301425 and r301426Sanjoy Das2017-04-261-4/+4
| | | | | | | | | | | | Commits were: "Use WeakVH instead of WeakTrackingVH in AliasSetTracker's UnkownInsts" "Add a new WeakVH value handle; NFC" "Rename WeakVH to WeakTrackingVH; NFC" The changes assumed pointers are 8 byte aligned on all architectures. llvm-svn: 301429
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-04-261-4/+4
| | | | | | | | | | | | | | | | Summary: I plan to use WeakVH to mean "nulls itself out on deletion, but does not track RAUW" in a subsequent commit. Reviewers: dblaikie, davide Reviewed By: davide Subscribers: arsenm, mehdi_amini, mcrosier, mzolotukhin, jfb, llvm-commits, nhaehnle Differential Revision: https://reviews.llvm.org/D32266 llvm-svn: 301424
* [InstCombine] Remove redundant code from SimplifyUsingDistributiveLawsCraig Topper2017-04-251-16/+0
| | | | | | | | | | The code I've removed here exists in ExpandBinOp in InstSimplify which we call into before SimplifyUsingDistributiveLaws. The code in InstSimplify looks to have been copied from here. I verified this code doesn't fire on any lit tests. Not that that proves its definitely dead. Differential Revision: https://reviews.llvm.org/D32472 llvm-svn: 301341
* [APInt] Use isSubsetOf, intersects, and bit counting methods to reduce ↵Craig Topper2017-04-252-3/+3
| | | | | | | | | | | | | | temporary APInts This patch uses various APInt methods to reduce temporary APInt creation. This should be all of the unrelated cleanups that got buried in D32376(creating a KnownBits struct) as well as some pointed out by Simon during the review of that. Plus a few improvements to use counting instead of masking. I've left out any places where we do something like (KnownZero & KnownOne) != 0 as I plan to add a helper method to KnownBits to ask that question and didn't want to thrash that code an additional time. Differential Revision: https://reviews.llvm.org/D32495 llvm-svn: 301338
* [InstCombine] Remove superfluous curly braces around a single line if body. NFCCraig Topper2017-04-251-2/+1
| | | | llvm-svn: 301326
* [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: Fix assert when reassociating fsub with undefMatt Arsenault2017-04-241-0/+5
| | | | | | | | | | | | | There is logic to track the expected number of instructions produced. It thought in this case an instruction would be necessary to negate the result, but here it folded into a ConstantExpr fneg when the non-undef value operand was cancelled out by the second fsub. I'm not sure why we don't fold constant FP ops with undef currently, but I think that would also avoid this problem. llvm-svn: 301199
* InstCombine/AMDGPU: Fix constant folding of llvm.amdgcn.{icmp,fcmp}Nicolai Haehnle2017-04-241-2/+20
| | | | | | | | | | | | | | | | | | Summary: The return value of these intrinsics should always have 0 bits for inactive threads. This means that when all arguments are constant and the comparison evaluates to true, the intrinsic should return the current exec mask. Fixes some GL_ARB_shader_ballot tests. Reviewers: arsenm Subscribers: kzhuravl, wdng, yaxunl, dstuttard, tpr, llvm-commits, t-tye Differential Revision: https://reviews.llvm.org/D32344 llvm-svn: 301195
* [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
* Revert "[APInt] Fix a few places that use APInt::getRawData to operate ↵Renato Golin2017-04-232-2/+2
| | | | | | | | | | | | | | | | within the normal API." This reverts commit r301105, 4, 3 and 1, as a follow up of the previous revert, which broke even more bots. For reference: Revert "[APInt] Use operator<<= where possible. NFC" Revert "[APInt] Use operator<<= instead of shl where possible. NFC" Revert "[APInt] Use ashInPlace where possible." PR32754. llvm-svn: 301111
* [APInt] Use operator<<= instead of shl where possible. NFCCraig Topper2017-04-232-2/+2
| | | | llvm-svn: 301103
* [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
* Fix for PR32740 - Invalid floating type, unreachable between r300969 and r301029Artur Pilipenko2017-04-221-2/+5
| | | | | | The bug was introduced by r301018 "[InstCombine] fadd double (sitofp x), y check that the promotion is valid". The patch didn't expect that fadd can be on vectors not necessarily scalars. Add vector support along with the test. llvm-svn: 301070
* [InstCombine] revert r300977 and r301021Sanjay Patel2017-04-211-14/+4
| | | | | | This can cause an inf-loop. Investigating... llvm-svn: 301035
* [InstCombine] use isSubsetOf() for efficiencySanjay Patel2017-04-211-1/+1
| | | | | | | | | | C | ~D == -1 ~(C | ~D) == 0 ~C & D == 0 D & ~C == 0 D.isSubsetOf(C) llvm-svn: 301021
* [InstCombine] fadd double (sitofp x), y check that the promotion is validArtur Pilipenko2017-04-211-22/+38
| | | | | | | | | | | | | | | Doing these transformations check that the result of integer addition is representable in the FP type. (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst)) (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y)) This is a fix for https://bugs.llvm.org//show_bug.cgi?id=27036 Reviewed By: andrew.w.kaylor, scanon, spatel Differential Revision: https://reviews.llvm.org/D31182 llvm-svn: 301018
* [InstCombine] prefer xor with -1 because 'not' is easier to understand (PR32706)Sanjay Patel2017-04-211-4/+14
| | | | | | | | | This matches the demanded bits behavior in the DAG and should fix: https://bugs.llvm.org/show_bug.cgi?id=32706 Differential Revision: https://reviews.llvm.org/D32255 llvm-svn: 300977
* [InstCombine] Remove the zextOrTrunc from ShrinkDemandedConstant.Craig Topper2017-04-201-4/+2
| | | | | | | | The demanded mask and the constant should always be the same width for all callers today. Also stop copying the demanded mask as its passed in. We should avoid allocating memory unless we are going to do something. The final AND to create the new constant will take care of it. llvm-svn: 300927
* [InstCombine] function names start with lower-case letter; NFCSanjay Patel2017-04-202-3/+3
| | | | | | Forgot to make this fix with the signature change in r300911. llvm-svn: 300912
* [InstCombine] allow shl+shr demanded bits folds with splat constantsSanjay Patel2017-04-202-22/+17
| | | | llvm-svn: 300911
* [InstCombine] allow shl demanded bits folds with splat constantsSanjay Patel2017-04-201-2/+4
| | | | | | More fixes are needed to enable the helper SimplifyShrShlDemandedBits(). llvm-svn: 300898
OpenPOWER on IntegriCloud