summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [InstCombine] Fix PR24605.Sanjoy Das2015-08-281-0/+6
| | | | | | | | | | | | | | PR24605 is caused due to an incorrect insert point in instcombine's IR builder. When simplifying %t = add X Y ... %m = icmp ... %t the replacement for %t should be placed before %t, not before %m, as there could be a use of %t between %t and %m. llvm-svn: 246315
* Re-apply r245635, "[InstCombine] Transform A & (L - 1) u< L --> L != 0"Sanjoy Das2015-08-211-0/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | The original checkin was buggy, this change has a fix. Original commit message: [InstCombine] Transform A & (L - 1) u< L --> L != 0 Summary: This transform is never a pessimization at the IR level (since it replaces an `icmp` with another), and has potentiall payoffs: 1. It may make the `icmp` fold away or become loop invariant. 2. It may make the `A & (L - 1)` computation dead. This shows up in Java, in range checks generated by array accesses of the form `a[i & (a.length - 1)]`. Reviewers: reames, majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12210 llvm-svn: 245753
* Revert r245635, "[InstCombine] Transform A & (L - 1) u< L --> L != 0"NAKAMURA Takumi2015-08-211-13/+0
| | | | | | It caused miscompilation in clang. llvm-svn: 245678
* [InstCombine] Transform A & (L - 1) u< L --> L != 0Sanjoy Das2015-08-201-0/+13
| | | | | | | | | | | | | | | | | | | | Summary: This transform is never a pessimization at the IR level (since it replaces an `icmp` with another), and has potentiall payoffs: 1. It may make the `icmp` fold away or become loop invariant. 2. It may make the `A & (L - 1)` computation dead. This shows up in Java, in range checks generated by array accesses of the form `a[i & (a.length - 1)]`. Reviewers: reames, majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12210 llvm-svn: 245635
* [InstCombine] Replace an and+icmp with a trunc+icmpDavid Majnemer2015-08-161-0/+17
| | | | | | | | Bitwise arithmetic can obscure a simple sign-test. If replacing the mask with a truncate is preferable if the type is legal because it permits us to rephrase the comparison more explicitly. llvm-svn: 245171
* Fix PR24354.Sanjoy Das2015-08-111-3/+2
| | | | | | | | | | `InstCombiner::OptimizeOverflowCheck` was asserting an invariant (operands to binary operations are ordered by decreasing complexity) that wasn't really an invariant. Fix this by instead having `InstCombiner::OptimizeOverflowCheck` establish the invariant if it does not hold. llvm-svn: 244676
* [InstSimplify] Fold away ord/uno fcmps when nnan is present.Benjamin Kramer2015-07-101-2/+2
| | | | | | | This is important to fold away the slow case of complex multiplies emitted by clang. llvm-svn: 241911
* [InstCombine] call SimplifyICmpInst with correct contextJingyue Wu2015-06-251-2/+4
| | | | | | | | | | | | | | | | | | | | | Summary: Fixes PR23809. Without passing the context to SimplifyICmpInst, we would use the assume to prove that the condition feeding the assume is trivially true (see isValidAssumeForContext in ValueTracking.cpp), causing the removal of the assume which may be useful for later optimizations. Test Plan: pr23800.ll Reviewers: hfinkel, majnemer Reviewed By: hfinkel Subscribers: henryhu, llvm-commits, wengxt, broune, meheff, eliben Differential Revision: http://reviews.llvm.org/D10695 llvm-svn: 240683
* [InstCombine][NFC] Add a ``break;`` statement.Sanjoy Das2015-06-051-0/+1
| | | | | | | | This change is NFC because both the ``break;`` and the fall through end up returning immediately. However, this helps clarify intent and also ensures correctness in case more ``case`` blocks are added later. llvm-svn: 239172
* [InstCombine] Fix PR23751.Sanjoy Das2015-06-051-0/+1
| | | | | | PR23751 was caused by a missing ``break;`` in r234388. llvm-svn: 239171
* [InstSimplify] Handle some overflow intrinsics in InstSimplifyDavid Majnemer2015-05-221-12/+0
| | | | | | | | | This change does a few things: - Move some InstCombine transforms to InstSimplify - Run SimplifyCall from within InstCombine::visitCallInst - Teach InstSimplify to fold [us]mul_with_overflow(X, undef) to 0. llvm-svn: 237995
* [InstCombine] X - 0 is equal to X, not undefDavid Majnemer2015-05-211-27/+21
| | | | | | | | | A refactoring made @llvm.ssub.with.overflow.i32(i32 %X, i32 0) transform into undef instead of %X. This fixes PR23624. llvm-svn: 237968
* Reapply r237539 with a fix for the Chromium build.James Molloy2015-05-201-0/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Make sure if we're truncating a constant that would then be sign extended that the sign extension of the truncated constant is the same as the original constant. > Canonicalize min/max expressions correctly. > > This patch introduces a canonical form for min/max idioms where one operand > is extended or truncated. This often happens when the other operand is a > constant. For example: > > %1 = icmp slt i32 %a, i32 0 > %2 = sext i32 %a to i64 > %3 = select i1 %1, i64 %2, i64 0 > > Would now be canonicalized into: > > %1 = icmp slt i32 %a, i32 0 > %2 = select i1 %1, i32 %a, i32 0 > %3 = sext i32 %2 to i64 > > This builds upon a patch posted by David Majenemer > (https://www.marc.info/?l=llvm-commits&m=143008038714141&w=2). That pass > passively stopped instcombine from ruining canonical patterns. This > patch additionally actively makes instcombine canonicalize too. > > Canonicalization of expressions involving a change in type from int->fp > or fp->int are not yet implemented. llvm-svn: 237821
* Revert r237539: "Reapply r237520 with another fix for infinite looping"Hans Wennborg2015-05-191-13/+0
| | | | | | This caused PR23583. llvm-svn: 237739
* Simplify IRBuilder::CreateCall* by using ArrayRef+initializer_list/braced ↵David Blaikie2015-05-181-2/+2
| | | | | | init only llvm-svn: 237624
* Reapply r237520 with another fix for infinite loopingJames Molloy2015-05-171-0/+13
| | | | | | | | | SimplifyDemandedBits was "simplifying" a constant by removing just sign bits. This caused a canonicalization race between different parts of instcombine. Fix and regression test added - third time lucky? llvm-svn: 237539
* Revert commits r237521 and r237520.James Molloy2015-05-161-13/+0
| | | | | | | | The AArch64 LNT bot is unhappy - I've found that the problem is in SimpliftDemandedBits, but that's going to require another code review so reverting in the meantime. llvm-svn: 237528
* Reapply r237453 with a fix for the test timeouts.James Molloy2015-05-161-0/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The test timeouts were due to instcombine fighting itself. Regression test added. Original log message: Canonicalize min/max expressions correctly. This patch introduces a canonical form for min/max idioms where one operand is extended or truncated. This often happens when the other operand is a constant. For example: %1 = icmp slt i32 %a, i32 0 %2 = sext i32 %a to i64 %3 = select i1 %1, i64 %2, i64 0 Would now be canonicalized into: %1 = icmp slt i32 %a, i32 0 %2 = select i1 %1, i32 %a, i32 0 %3 = sext i32 %2 to i64 This builds upon a patch posted by David Majenemer (https://www.marc.info/?l=llvm-commits&m=143008038714141&w=2). That pass passively stopped instcombine from ruining canonical patterns. This patch additionally actively makes instcombine canonicalize too. Canonicalization of expressions involving a change in type from int->fp or fp->int are not yet implemented. llvm-svn: 237520
* Revert "Canonicalize min/max expressions correctly."James Molloy2015-05-151-13/+0
| | | | | | | This reverts r237453 - it was causing timeouts on some bots. Reverting while I investigate (it's probably InstCombine fighting itself...) llvm-svn: 237458
* Canonicalize min/max expressions correctly.James Molloy2015-05-151-0/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch introduces a canonical form for min/max idioms where one operand is extended or truncated. This often happens when the other operand is a constant. For example: %1 = icmp slt i32 %a, i32 0 %2 = sext i32 %a to i64 %3 = select i1 %1, i64 %2, i64 0 Would now be canonicalized into: %1 = icmp slt i32 %a, i32 0 %2 = select i1 %1, i32 %a, i32 0 %3 = sext i32 %2 to i64 This builds upon a patch posted by David Majenemer (https://www.marc.info/?l=llvm-commits&m=143008038714141&w=2). That pass passively stopped instcombine from ruining canonical patterns. This patch additionally actively makes instcombine canonicalize too. Canonicalization of expressions involving a change in type from int->fp or fp->int are not yet implemented. llvm-svn: 237453
* Subtraction is not commutative. Fixes PR23212!Nick Lewycky2015-04-131-1/+2
| | | | llvm-svn: 234780
* [InstCombine][CodeGenPrep] Create llvm.uadd.with.overflow in CGP.Sanjoy Das2015-04-101-44/+12
| | | | | | | | | | | | | | | | | | | Summary: This change moves creating calls to `llvm.uadd.with.overflow` from InstCombine to CodeGenPrep. Combining overflow check patterns into calls to the said intrinsic in InstCombine inhibits optimization because it introduces an intrinsic call that not all other transforms and analyses understand. Depends on D8888. Reviewers: majnemer, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8889 llvm-svn: 234638
* [InstCombine] Refactor out OptimizeOverflowCheck. NFCI.Sanjoy Das2015-04-081-0/+107
| | | | | | | | | | | | | | | | | | | Summary: This patch adds an enum `OverflowCheckFlavor` and a function `OptimizeOverflowCheck`. This will allow InstCombine to optimize overflow checks without directly introducing an intermediate call to the `llvm.$op.with.overflow` instrinsics. This specific change is a refactoring and does not intend to change behavior. Reviewers: majnemer, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8888 llvm-svn: 234388
* InstCombine: fold (A << C) == (B << C) --> ((A^B) & (~0U >> C)) == 0Benjamin Kramer2015-03-261-0/+15
| | | | | | | Anding and comparing with zero can be done in a single instruction on most archs so this is a bit cheaper. llvm-svn: 233291
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-29/+19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [InstCombine] Fix a bug when combining `icmp` from `ptrtoint`Michael Liao2015-02-131-7/+10
| | | | | | | | | | | | - First, there's a crash when we try to combine that pointers into `icmp` directly by creating a `bitcast`, which is invalid if that two pointers are from different address spaces. - It's not always appropriate to cast one pointer to another if they are from different address spaces as that is not no-op cast. Instead, we only combine `icmp` from `ptrtoint` if that two pointers are of the same address space. llvm-svn: 229063
* [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] Move TargetLibraryInfo into the Analysis library.Chandler Carruth2015-01-151-1/+1
| | | | | | | | | | | | | | | | While the term "Target" is in the name, it doesn't really have to do with the LLVM Target library -- this isn't an abstraction which LLVM targets generally need to implement or extend. It has much more to do with modeling the various runtime libraries on different OSes and with different runtime environments. The "target" in this sense is the more general sense of a target of cross compilation. This is in preparation for porting this analysis to the new pass manager. No functionality changed, and updates inbound for Clang and Polly. llvm-svn: 226078
* InstCombine: Don't take A-B<0 into A<B if A-B has other usesDavid Majnemer2015-01-141-26/+28
| | | | | | This fixes PR22226. llvm-svn: 226023
* Fix fcmp + fabs instcombines when using the intrinsicMatt Arsenault2015-01-081-26/+28
| | | | | | | This was only handling the libcall. This is another example of why only the intrinsic should ever be used when it exists. llvm-svn: 225465
* Convert fcmp with 0.0 from casted integers to icmpMatt Arsenault2015-01-061-4/+34
| | | | | | | | | | | | | | | | | | | This is already handled in general when it is known the conversion can't lose bits with smaller integer types casted into wider floating point types. This pattern happens somewhat often in GPU programs that cast workitem intrinsics to float, which are often compared with 0. Specifically handle the special case of compares with zero which should also be known to not lose information. I had a more general version of this which allows equality compares if the casted float is exactly representable in the integer, but I'm not 100% confident that is always correct. Also fold cases that aren't integers to true / false. llvm-svn: 225265
* [PM] Split the AssumptionTracker immutable pass into two separate APIs:Chandler Carruth2015-01-041-5/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* InstCombine: try to transform A-B < 0 into A < BDavid Majnemer2014-12-311-0/+20
| | | | | | | We are allowed to move the 'B' to the right hand side if we an prove there is no signed overflow and if the comparison itself is signed. llvm-svn: 225034
* Removed extra line from a comment to test first commit. NFC.Ankur Garg2014-11-281-1/+0
| | | | llvm-svn: 222916
* InstCombine: Silence a parenthesis warningDavid Majnemer2014-11-221-1/+1
| | | | llvm-svn: 222609
* [InstCombine] Re-commit of r218721 (Optimize icmp-select-icmp sequence)Gerolf Hoflehner2014-11-211-4/+150
| | | | | | | Fixes the self-host fail. Note that this commit activates dominator analysis in the combiner by default (like the original commit did). llvm-svn: 222590
* InstCombine: Rely on cmpxchg's return code when it's strongDavid Majnemer2014-11-061-0/+16
| | | | | | | Comparing the result of a cmpxchg instruction can be replaced with an extractvalue of the cmpxchg success indicator. llvm-svn: 221498
* InstCombine: Don't assume that m_ZExt matches an InstructionDavid Majnemer2014-11-011-2/+2
| | | | | | | | | | | | m_ZExt might bind against a ConstantExpr instead of an Instruction. Assuming this, using cast<Instruction>, results in InstCombine crashing. Instead, introduce ZExtOperator to bridge both Instruction and ConstantExpr ZExts. This fixes PR21445. llvm-svn: 221069
* InstCombine: Combine (X+cst) < 0 --> X < -cstDavid Majnemer2014-11-011-0/+6
| | | | | | | | | | | | | This can happen pretty often in code that looks like: int foo = bar - 1; if (foo < 0) do stuff In this case, bar < 1 is an equivalent condition. This transform requires that the add instruction be annotated with nsw. llvm-svn: 221045
* InstCombine: Remove overzealous assertsDavid Majnemer2014-10-251-12/+19
| | | | | | | | | | | | | | These asserts can trigger if the worklist iteration order is sufficiently unlucky. Instead of adding special case logic to handle these edge conditions, just bail out on trying to transform them: InstSimplify will get them when it reaches them on the worklist. This fixes PR21378. N.B. No test case is included because any test would rely on the fragile worklist iteration order. llvm-svn: 220612
* InstCombine: Simplify FoldICmpCstShrCstDavid Majnemer2014-10-211-48/+16
| | | | | | | | | This function was complicated by the fact that it tried to perform canonicalizations that were already preformed by InstSimplify. Remove this extra code and move the tests over to InstSimplify. Add asserts to make sure our preconditions hold before we make any assumptions. llvm-svn: 220314
* InstCombine: Optimize icmp eq/ne (shl Const2, A), Const1David Majnemer2014-10-191-1/+48
| | | | | | | | | | | | | | | The following implements the optimization for sequences of the form: icmp eq/ne (shl Const2, A), Const1 Such sequences can be transformed to: icmp eq/ne A, (TrailingZeros(Const1) - TrailingZeros(Const2)) This handles only the equality operators for now. Other operators need to be handled. Patch by Ankur Garg! llvm-svn: 220162
* [InstCombine] Fix wrong folding of constant comparisons involving ashr and ↵Andrea Di Biagio2014-10-091-1/+2
| | | | | | | | | | | | | | negative values. This patch fixes a bug in method InstCombiner::FoldCmpCstShrCst where we wrongly computed the distance between the highest bits set of two negative values. This fixes PR21222. Differential Revision: http://reviews.llvm.org/D5700 llvm-svn: 219406
* Revert "[InstCombine] re-commit r218721 with fix for pr21199"Justin Bogner2014-10-081-134/+2
| | | | | | | | | | | | | This seems to cause a miscompile when building clang, which causes a bootstrapped clang to fail or crash in several of its tests. See: http://lab.llvm.org:8013/builders/clang-x86_64-darwin11-RA/builds/1184 http://bb.pgr.jp/builders/clang-3stage-x86_64-linux/builds/7813 This reverts commit r219282. llvm-svn: 219317
* [InstCombine] re-commit r218721 with fix for pr21199Gerolf Hoflehner2014-10-081-2/+134
| | | | | | | | The icmp-select-icmp optimization targets select-icmp.eq only. This is now ensured by testing the branch predicate explictly. This commit also includes the test case for pr21199. llvm-svn: 219282
* Revert r219175 - [InstCombine] re-commit r218721 icmp-select-icmp optimizationHans Wennborg2014-10-081-138/+2
| | | | | | This seems to have caused PR21199. llvm-svn: 219264
* [InstCombine] re-commit r218721 icmp-select-icmp optimizationGerolf Hoflehner2014-10-071-2/+138
| | | | | | | | | Takes care of the assert that caused build fails. Rather than asserting the code checks now that the definition and use are in the same block, and does not attempt to optimize when that is not the case. llvm-svn: 219175
* Revert r218721, r218735.Evgeniy Stepanov2014-10-011-142/+2
| | | | | | | | | | Failing bootstrap on Linux (arm, x86). http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/13139/steps/bootstrap%20clang/logs/stdio http://lab.llvm.org:8011/builders/clang-cmake-armv7-a15-selfhost/builds/470 http://lab.llvm.org:8011/builders/clang-native-arm-lnt/builds/8518 llvm-svn: 218752
* [InstCombine] Fix for assert build failures caused by r218721Gerolf Hoflehner2014-10-011-1/+7
| | | | | | | | | The icmp-select-icmp optimization made the implicit assumption that the select-icmp instructions are in the same block and asserted on it. The fix explicitly checks for that condition and conservatively suppresses the optimization when it is violated. llvm-svn: 218735
* [InstCombine] Optimize icmp-select-icmpGerolf Hoflehner2014-10-011-2/+136
| | | | | | | | | | | | | | | | | | | | | | | | | | | In special cases select instructions can be eliminated by replacing them with a cheaper bitwise operation even when the select result is used outside its home block. The instances implemented are patterns like %x=icmp.eq %y=select %x,%r, null %z=icmp.eq|neq %y, null br %z,true, false ==> %x=icmp.ne %y=icmp.eq %r,null %z=or %x,%y br %z,true,false The optimization is integrated into the instruction combiner and performed only when all uses of the select result can be replaced by the select operand proper. For this dominator information is used and dominance is now a required analysis pass in the combiner. The optimization itself is iterative. The critical step is to replace the select result with the non-constant select operand. So the select becomes local and the combiner iteratively works out simpler code pattern and eventually eliminates the select. rdar://17853760 llvm-svn: 218721
OpenPOWER on IntegriCloud