summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [InstCombine] use local variable to reduce code; NFCISanjay Patel2017-06-281-18/+14
| | | | llvm-svn: 306560
* [Analysis][Transforms] Use commutable matchers instead of m_CombineOr in a ↵Craig Topper2017-06-241-2/+1
| | | | | | few places. NFC llvm-svn: 306204
* [InstCombine] Recognize and simplify three way comparison idiomsAnna Thomas2017-06-231-4/+92
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Many languages have a three way comparison idiom where comparing two values produces not a boolean, but a tri-state value. Typical values (e.g. as used in the lcmp/fcmp bytecodes from Java) are -1 for less than, 0 for equality, and +1 for greater than. We actually do a great job already of converting three way comparisons into binary comparisons when the result produced has one a single use. Unfortunately, such values can have more than one use, and in that case, our existing optimizations break down. The patch adds a peephole which converts a three-way compare + test idiom into a binary comparison on the original inputs. It focused on replacing the test on the result of the three way compare and does nothing about removing the three way compare itself. That's left to other optimizations (which do actually kick in commonly.) We currently recognize one idiom on signed integer compare. In the future, we plan to recognize and simplify other comparison idioms on other signed/unsigned datatypes such as floats, vectors etc. This is a resurrection of Philip Reames' original patch: https://reviews.llvm.org/D19452 Reviewers: majnemer, apilipenko, reames, sanjoy, mkazantsev Reviewed by: mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34278 llvm-svn: 306100
* [InstCombine][InstSimplify] Use APInt::isNullValue/isOneValue to reduce ↵Craig Topper2017-06-071-31/+35
| | | | | | | | compiled code for comparing APInts with 0 and 1. NFC These methods are specifically optimized to only counting leading zeros without an additional uint64_t compare. llvm-svn: 304876
* [InstCombine] Fix two asserts that were accidentally checking that an APInt ↵Craig Topper2017-06-071-2/+2
| | | | | | | | pointer is non-zero instead of checking that the APInt self is non-zero. I believe this code used to use APInt references which would have worked. But then they were changed to pointers to allow m_APInt to be used. llvm-svn: 304875
* [InstCombine] fix icmp with not op and constant to work with splat vector ↵Sanjay Patel2017-06-021-3/+3
| | | | | | constant llvm-svn: 304562
* [InstCombine] improve perf by not creating a known non-canonical instructionSanjay Patel2017-06-021-3/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Op1 (RHS) is a constant, so putting it on the LHS makes us churn through visitICmp an extra time to canonicalize it: INSTCOMBINE ITERATION #1 on cmpnot IC: ADDING: 3 instrs to worklist IC: Visiting: %notx = xor i8 %x, -1 IC: Visiting: %cmp = icmp sgt i8 %notx, 42 IC: Old = %cmp = icmp sgt i8 %notx, 42 New = <badref> = icmp sgt i8 -43, %x IC: ADD: %cmp = icmp sgt i8 -43, %x IC: ERASE %1 = icmp sgt i8 %notx, 42 IC: ADD: %notx = xor i8 %x, -1 IC: DCE: %notx = xor i8 %x, -1 IC: ERASE %notx = xor i8 %x, -1 IC: Visiting: %cmp = icmp sgt i8 -43, %x IC: Mod = %cmp = icmp sgt i8 -43, %x New = %cmp = icmp slt i8 %x, -43 IC: ADD: %cmp = icmp slt i8 %x, -43 IC: Visiting: %cmp = icmp slt i8 %x, -43 IC: Visiting: ret i1 %cmp If we create the swapped ICmp directly, we go faster: INSTCOMBINE ITERATION #1 on cmpnot IC: ADDING: 3 instrs to worklist IC: Visiting: %notx = xor i8 %x, -1 IC: Visiting: %cmp = icmp sgt i8 %notx, 42 IC: Old = %cmp = icmp sgt i8 %notx, 42 New = <badref> = icmp slt i8 %x, -43 IC: ADD: %cmp = icmp slt i8 %x, -43 IC: ERASE %1 = icmp sgt i8 %notx, 42 IC: ADD: %notx = xor i8 %x, -1 IC: DCE: %notx = xor i8 %x, -1 IC: ERASE %notx = xor i8 %x, -1 IC: Visiting: %cmp = icmp slt i8 %x, -43 IC: Visiting: ret i1 %cmp llvm-svn: 304558
* [InstCombine] Pass the DominatorTree, AssumptionCache, and context ↵Craig Topper2017-05-261-2/+2
| | | | | | | | | | instruction to a few calls to isKnownPositive, isKnownNegative, and isKnownNonZero Every other place in InstCombine that uses these methods in ValueTracking already pass this information. This makes the remaining sites consistent. Differential Revision: https://reviews.llvm.org/D33567 llvm-svn: 304018
* [InstCombine] Add an InstCombine specific wrapper around ↵Craig Topper2017-05-251-1/+1
| | | | | | | | isKnownToBeAPowerOfTwo to shorten code. NFC We have wrappers for several other ValueTracking methods that take care of passing all of the analysis and assumption cache parameters. This extends it to isKnownToBeAPowerOfTwo. llvm-svn: 303924
* [InstCombine] make icmp-mul fold more efficientSanjay Patel2017-05-251-5/+7
| | | | | | | | | | | There's probably a lot more like this (see also comments in D33338 about responsibility), but I suspect we don't usually get a visible manifestation. Given the recent interest in improving InstCombine efficiency, another potential micro-opt that could be repeated several times in this function: morph the existing icmp pred/operands instead of creating a new instruction. llvm-svn: 303860
* [InstCombine] use m_APInt to allow icmp-mul-mul vector foldSanjay Patel2017-05-241-11/+12
| | | | | | | | | The swapped operands in the first test is a manifestation of an inefficiency for vectors that doesn't exist for scalars because the IRBuilder checks for an all-ones mask for scalars, but not vectors. llvm-svn: 303818
* [ValueTracking] Convert most of the calls to computeKnownBits to use the ↵Craig Topper2017-05-241-2/+1
| | | | | | | | | | version that returns the KnownBits object. This continues the changes started when computeSignBit was replaced with this new version of computeKnowBits. Differential Revision: https://reviews.llvm.org/D33431 llvm-svn: 303773
* [InstCombine] allow icmp-xor folds for vectors (PR33138)Sanjay Patel2017-05-231-5/+9
| | | | | | | | | This fixes the first part of: https://bugs.llvm.org/show_bug.cgi?id=33138 More work is needed for the bitcasted variant. llvm-svn: 303660
* [InstCombine] Cleanup the interface for overflow checksCraig Topper2017-05-221-4/+4
| | | | | | | | | | | | | | | | | | Summary: Fix naming conventions and const correctness. This completes the changes made in rL303029. Patch by Yoav Ben-Shalom. Reviewers: craig.topper Reviewed By: craig.topper Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D33377 llvm-svn: 303529
* [InstCombine] handle icmp i1 X, C early to avoid creating an unknown patternSanjay Patel2017-05-171-0/+23
| | | | | | | | | | | The missing optimization for xor-of-icmps still needs to be added, but by being more efficient (not generating unnecessary logic ops with constants) we avoid the bug. See discussion in post-commit comments: https://reviews.llvm.org/D32143 llvm-svn: 303312
* [InstCombine] move icmp bool canonicalizations to helper; NFCSanjay Patel2017-05-171-43/+54
| | | | | | | | As noted in the post-commit comments in D32143, we should be catching the constant operand cases sooner to be more efficient and less likely to expose a missing fold. llvm-svn: 303309
* [InstCombine] restrict icmp fold with 2 sdiv exact operands (PR32949)Sanjay Patel2017-05-151-2/+9
| | | | | | | | | | | | | | | | This is the InstCombine counterpart to D32954. I added some comments about the code duplication in: rL302436 Alive-based verification: http://rise4fun.com/Alive/dPw This is a 2nd fix for the problem reported in: https://bugs.llvm.org/show_bug.cgi?id=32949 Differential Revision: https://reviews.llvm.org/D32970 llvm-svn: 303105
* [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
* [KnownBits] Add wrapper methods for setting and clear all bits in the ↵Craig Topper2017-05-051-1/+1
| | | | | | | | | | 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
* [APInt] Add clearSignBit method. Use it and setSignBit in a few places. NFCICraig Topper2017-04-281-2/+2
| | | | llvm-svn: 301656
* InstCombine: Use the new SimplifyQuery versions of Simplify*. Use ↵Daniel Berlin2017-04-261-4/+5
| | | | | | AssumptionCache, DominatorTree, TargetLibraryInfo everywhere. llvm-svn: 301464
* [ValueTracking] Introduce a KnownBits struct to wrap the two APInts for ↵Craig Topper2017-04-261-36/+31
| | | | | | | | | | | | | | | | 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
* [APInt] Rename getSignBit to getSignMaskCraig Topper2017-04-201-10/+10
| | | | | | | | 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] Support folding a subtract with a constant LHS into a phi nodeCraig Topper2017-04-141-2/+2
| | | | | | | | | | | | We currently only support folding a subtract into a select but not a PHI. This fixes that. I had to fix an assumption in FoldOpIntoPhi that assumed the PHI node was always in operand 0. Now we pass it in like we do for FoldOpIntoSelect. But we still require some dancing to find the Constant when we create the BinOp or ConstantExpr. This is based code is similar to what we do for selects. Since I touched all call sites, this also renames FoldOpIntoPhi to foldOpIntoPhi to match coding standards. Differential Revision: https://reviews.llvm.org/D31686 llvm-svn: 300363
* [InstCombine] Use APInt::getBitsSetFrom instead of inverting the result of ↵Craig Topper2017-04-131-4/+2
| | | | | | getLowBitsSet. NFC llvm-svn: 300265
* Revert accidentally-committed files in r300252.Richard Smith2017-04-131-403/+0
| | | | llvm-svn: 300253
* Remove all allocation and divisions from GreatestCommonDivisorRichard Smith2017-04-131-0/+403
| | | | | | | | | | | Switch from Euclid's algorithm to Stein's algorithm for computing GCD. This avoids the (expensive) APInt division operation in favour of bit operations. Remove all memory allocation from within the GCD loop by tweaking our `lshr` implementation so it can operate in-place. Differential Revision: https://reviews.llvm.org/D31968 llvm-svn: 300252
* [InstCombine] add fold for icmp with or mask of low bits (PR32542)Sanjay Patel2017-04-051-0/+9
| | | | | | | | | | | | | | | | | | | | We already have these 'and' folds: // X & -C == -C -> X > u ~C // X & -C != -C -> X <= u ~C // iff C is a power of 2 ...but we were missing the 'or' siblings. http://rise4fun.com/Alive/n6 This should improve: https://bugs.llvm.org/show_bug.cgi?id=32524 ...but there are 2 or more other pieces to fix still. Differential Revision: https://reviews.llvm.org/D31712 llvm-svn: 299570
* [InstCombine] Change the interface of SimplifyDemandedBits so that it takes ↵Craig Topper2017-03-251-2/+2
| | | | | | | | the instruction and operand instead of the Use. The first thing it did was get the User for the Use to get the instruction back. This requires looking through the Uses for the User using the waymarking walk. That's pretty fast, but its probably still better to just pass the Instruction we already had. llvm-svn: 298772
* [InstCombine] Avoid faulty combines of select-cmp-brBjorn Pettersson2017-03-021-3/+5
| | | | | | | | | | | | | | | | | | | | | | Summary: When InstCombine is optimizing certain select-cmp-br patterns it replaces the result of the select in uses outside of the basic block containing the select. This is only legal if the path from the select to the outside use is disjoint from all other paths out from the originating basic block. The problem found was that InstCombiner::replacedSelectWithOperand did not consider the case when both edges out from the br pointed to the same label. In that case the paths aren't disjoint and the transformation is illegal. This patch avoids the faulty rewrites by verifying that there is a single flow to the successor where we want to replace uses. Reviewers: llvm-commits, spatel, majnemer Differential Revision: https://reviews.llvm.org/D30455 llvm-svn: 296752
* [InstCombine] fold icmp sgt/slt (add nsw X, C2), C --> icmp sgt/slt X, (C - C2)Sanjay Patel2017-02-121-6/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | I found one special case of this transform for 'slt 0', so I removed that and added the general transform. Alive code to check correctness: Name: slt_no_overflow Pre: WillNotOverflowSignedSub(C1, C2) %a = add nsw i8 %x, C2 %b = icmp slt %a, C1 => %b = icmp slt %x, C1 - C2 Name: sgt_no_overflow Pre: WillNotOverflowSignedSub(C1, C2) %a = add nsw i8 %x, C2 %b = icmp sgt %a, C1 => %b = icmp sgt %x, C1 - C2 http://rise4fun.com/Alive/MH Differential Revision: https://reviews.llvm.org/D29774 llvm-svn: 294898
* [InstCombine] add local name for repeated calls; NFC Sanjay Patel2017-02-081-6/+4
| | | | llvm-svn: 294470
* [InstCombine] Make max size array combine a tunable.Davide Italiano2017-02-071-1/+3
| | | | | | | Requested by Sanjoy/Hal a while ago, and forgotten by me (r283612). llvm-svn: 294323
* fix formatting; NFCSanjay Patel2017-01-311-1/+1
| | | | llvm-svn: 293652
* [InstCombine] Make sure that LHS and RHS have the same type inSilviu Baranga2017-01-311-0/+4
| | | | | | | | | | | | | | | | | transformToIndexedCompare If they don't have the same type, the size of the constant index would need to be adjusted (and this wouldn't be always possible). Alternatively we could try the analysis with the initial RHS value, which would guarantee that the two sides have the same type. However it is unlikely that in practice this would pass our transformation requirements. Fixes PR31808 (https://llvm.org/bugs/show_bug.cgi?id=31808). llvm-svn: 293629
* [InstCombine] move icmp transforms that might be recognized as min/max and ↵Sanjay Patel2017-01-271-10/+21
| | | | | | | | | | | | | | | | | | | | | | inf-loop (PR31751) This is a minimal patch to avoid the infinite loop in: https://llvm.org/bugs/show_bug.cgi?id=31751 But the general problem is bigger: we're not canonicalizing all of the min/max forms reported by value tracking's matchSelectPattern(), and we don't define min/max consistently. Some code uses matchSelectPattern(), other code uses matchers like m_Umax, and others have their own inline definitions which may be subtly different from any of the above. The reason that the test cases in this patch need a cast op to trigger is because we don't (yet) canonicalize all min/max forms based on matchSelectPattern() in canonicalizeMinMaxWithConstant(), but we do make min/max+cast transforms based on matchSelectPattern() in visitSelectInst(). The location of the icmp transforms that trigger the inf-loop seems arbitrary at best, so I'm moving those behind the min/max fence in visitICmpInst() as the quick fix. llvm-svn: 293345
* [InstCombine] icmp Pred (shl nsw X, C1), C0 --> icmp Pred X, C0 >> C1Sanjay Patel2017-01-191-24/+43
| | | | | | | | | | | | | | Try harder to fold icmp with shl nsw as discussed here: http://lists.llvm.org/pipermail/llvm-dev/2017-January/108749.html This is similar to the 'shl nuw' transforms that were added with D25913. This may eventually help solve: https://llvm.org/bugs/show_bug.cgi?id=30773 Differential Revision: https://reviews.llvm.org/D28406 llvm-svn: 292492
* [InstCombine] add an assert to make a shl+icmp transform assumption ↵Sanjay Patel2017-01-181-1/+9
| | | | | | explicit; NFCI llvm-svn: 292440
* [InstCombine] remove a redundant check; NFCISanjay Patel2017-01-181-2/+0
| | | | | | | I missed deleting this check when I refactored this chunk in: https://reviews.llvm.org/rL292260 llvm-svn: 292433
* [InstCombine] refactor foldICmpShlConstant(); NFCISanjay Patel2017-01-171-32/+35
| | | | | | | This reduces the size of and increases the symmetry with the planned functional change in: https://reviews.llvm.org/D28406 llvm-svn: 292260
* [InstCombine] optimize unsigned icmp of incrementSanjay Patel2017-01-131-0/+25
| | | | | | | | | | | | | | | | | | | | | | | Allows LLVM to optimize sequences like the following: %add = add nuw i32 %x, 1 %cmp = icmp ugt i32 %add, %y Into: %cmp = icmp uge i32 %x, %y Previously, only signed comparisons were being handled. Decrements could also be handled, but 'sub nuw %x, 1' is currently canonicalized to 'add %x, -1' in InstCombineAddSub, losing the nuw flag. Removing that canonicalization seems like it might have far-reaching ramifications so I kept this simple for now. Patch by Matti Niemenmaa! Differential Revision: https://reviews.llvm.org/D24700 llvm-svn: 291975
* fix comment typos; NFCSanjay Patel2017-01-091-5/+5
| | | | llvm-svn: 291447
* [InstCombine] add folds for icmp (umin|umax X, Y), XSanjay Patel2016-12-191-19/+54
| | | | | | | | This is a follow-up to: https://reviews.llvm.org/rL289855 (https://reviews.llvm.org/D27531) https://reviews.llvm.org/rL290111 llvm-svn: 290118
* [InstCombine] add folds for icmp (smax X, Y), XSanjay Patel2016-12-191-17/+35
| | | | | | | This is a follow-up to: https://reviews.llvm.org/rL289855 (D27531) llvm-svn: 290111
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-3/+3
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* [InstCombine] add folds for icmp (smin X, Y), XSanjay Patel2016-12-151-0/+37
| | | | | | | | | | | | | | Min/max canonicalization (r287585) exposes the fact that we're missing combines for min/max patterns. This patch won't solve the example that was attached to that thread, so something else still needs fixing. The line between InstCombine and InstSimplify gets blurry here because sometimes the icmp instruction that we want to fold to already exists, but sometimes it's the swapped form of what we want. Corresponding changes for smax/umin/umax to follow. Differential Revision: https://reviews.llvm.org/D27531 llvm-svn: 289855
* Remove the AssumptionCacheHal Finkel2016-12-151-3/+3
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* Replace APFloatBase static fltSemantics data members with getter functionsStephan Bergmann2016-12-141-6/+6
| | | | | | | | | | | | | At least the plugin used by the LibreOffice build (<https://wiki.documentfoundation.org/Development/Clang_plugins>) indirectly uses those members (through inline functions in LLVM/Clang include files in turn using them), but they are not exported by utils/extract_symbols.py on Windows, and accessing data across DLL/EXE boundaries on Windows is generally problematic. Differential Revision: https://reviews.llvm.org/D26671 llvm-svn: 289647
* IR: Change the gep_type_iterator API to avoid always exposing the "current" ↵Peter Collingbourne2016-12-021-2/+2
| | | | | | | | | | | | | type. Instead, expose whether the current type is an array or a struct, if an array what the upper bound is, and if a struct the struct type itself. This is in preparation for a later change which will make PointerType derive from Type rather than SequentialType. Differential Revision: https://reviews.llvm.org/D26594 llvm-svn: 288458
OpenPOWER on IntegriCloud