summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
Commit message (Collapse)AuthorAgeFilesLines
* don't repeat function names in comments; NFCSanjay Patel2015-09-091-19/+16
| | | | llvm-svn: 247154
* Add support for floating-point minnum and maxnumJames Molloy2015-08-111-8/+29
| | | | | | | | | | | | | | | | | The select pattern recognition in ValueTracking (as used by InstCombine and SelectionDAGBuilder) only knew about integer patterns. This teaches it about minimum and maximum operations. matchSelectPattern() has been extended to return a struct containing the existing Flavor and a new enum defining the pattern's behavior when given one NaN operand. C minnum() is defined to return the non-NaN operand in this case, but the idiomatic C "a < b ? a : b" would return the NaN operand. ARM and AArch64 at least have different instructions for these different cases. llvm-svn: 244580
* [InstCombine, InstSimplify] Move xforms from Combine to SimplifyDavid Majnemer2015-06-061-115/+2
| | | | | | | | There were several SelectInst combines that always returned an existing instruction instead of modifying an old one or creating a new one. These are prime candidates for moving to InstSimplify. llvm-svn: 239229
* [InstCombine] Don't miscompile select to poisonDavid Majnemer2015-06-061-0/+13
| | | | | | | | | | | | | | | | If we have (select a, b, c), it is sometimes valid to simplify this to a single select operand. However, doing so is only valid if the computation doesn't inject poison into the computation. It might be helpful to consider the following example: (select (icmp ne %i, INT_MAX), (add nsw %i, 1), INT_MIN) The select is equivalent to (add %i, 1) but not (add nsw %i, 1). Self hosting on x86_64 revealed that this occurs very, very rarely so bailing out is hopefully pretty reasonable. llvm-svn: 239215
* Revert "[InstCombine] Rephrase fix to SimplifyWithOpReplaced"Renato Golin2015-06-051-22/+4
| | | | | | | | | This reverts commit r239141. This commit was an attempt to reintroduce a previous patch that broke many self-hosting bots with clang timeouts, but it still has slowdown issues, at least on ARM, increasing the compilation time (stage 2, clang's) by 5x. llvm-svn: 239175
* [InstCombine] Rephrase fix to SimplifyWithOpReplacedDavid Majnemer2015-06-051-4/+22
| | | | | | | | | | | | | | | | | | I don't have the IR which is causing the build bot breakage but I can postulate as to why they are timing out: 1. SimplifyWithOpReplaced was stripping flags from the simplified value. 2. visitSelectInstWithICmp was overriding SimplifyWithOpReplaced because it's simplification wasn't correct. 3. InstCombine would revisit the add instruction and note that it can rederive the flags. 4. By modifying the value, we chose to revisit instructions which reuse the value. One of the instructions is the original select, causing LLVM to never reach fixpoint. Instead, strip the flags only when we are sure we are going to perform the simplification. llvm-svn: 239141
* Revert "[InstCombine] Don't miscompile safe increment idiom"Daniel Jasper2015-06-051-21/+3
| | | | | | | | | This is breaking a lot of build bots and is causing very long-running compiles (infinite loops)? Likely, we shouldn't return nullptr? llvm-svn: 239139
* [InstCombine] Don't miscompile safe increment idiomDavid Majnemer2015-06-041-3/+21
| | | | | | | | | | | We cleverly handle cases where computation done in one argument of a select instruction is suitable for the other operand, thus obviating the need of the select and the comparison. However, the other operand cannot have flags. This fixes PR23757. llvm-svn: 239115
* Reapply r237539 with a fix for the Chromium build.James Molloy2015-05-201-6/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-18/+6
| | | | | | This caused PR23583. llvm-svn: 237739
* Reapply r237520 with another fix for infinite loopingJames Molloy2015-05-171-6/+18
| | | | | | | | | 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-18/+6
| | | | | | | | 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-6/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-18/+6
| | | | | | | 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-6/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Rip min/max pattern matching out of InstCombine and intoJames Molloy2015-05-111-88/+4
| | | | | | | | | | | ValueTracking. This matching functionality is useful in more than just InstCombine, so make it available in ValueTracking. NFC. llvm-svn: 236998
* [InstCombine] Add new rule for MIN(MAX(~A, ~B), ~C) et. al.Sanjoy Das2015-04-301-0/+86
| | | | | | | | | | | | | | | | | Summary: Optimizing these well are especially interesting for IRCE since it "clamps" values by generating this sort of pattern through SCEV expressions. Depends on D9352. Reviewers: majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9353 llvm-svn: 236203
* [InstCombine] Add a new formula for SMIN.Sanjoy Das2015-04-301-0/+11
| | | | | | | | | | | | | | | | Summary: After this change `MatchSelectPattern` recognizes the following form of SMIN: Y >s C ? ~Y : ~C == ~Y <s ~C ? ~Y : ~C = SMIN(~Y, ~C) Reviewers: majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9352 llvm-svn: 236202
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-18/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Simplify expressions involving boolean constants with clang-tidyDavid Blaikie2015-03-091-1/+1
| | | | | | | | Patch by Richard (legalize at xmission dot com). Differential Revision: http://reviews.llvm.org/D8154 llvm-svn: 231617
* InstCombine: Ensure select condition types are identical before mergingDavid Majnemer2015-03-031-28/+32
| | | | | | | | | | Selection conditions may be vectors or scalars. Make sure InstCombine doesn't indiscriminately assume that a select which is value dependent on another select have identical select condition types. This fixes PR22773. llvm-svn: 231156
* New instcombine rule: max(~a,~b) -> ~min(a, b)Sanjoy Das2015-02-241-2/+31
| | | | | | | | | | 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] Fix regression introduced at r227197.Andrea Di Biagio2015-02-131-10/+6
| | | | | | | | | | | | | | | | | | This patch fixes a problem I accidentally introduced in an instruction combine on select instructions added at r227197. That revision taught the instruction combiner how to fold a cttz/ctlz followed by a icmp plus select into a single cttz/ctlz with flag 'is_zero_undef' cleared. However, the new rule added at r227197 would have produced wrong results in the case where a cttz/ctlz with flag 'is_zero_undef' cleared was follwed by a zero-extend or truncate. In that case, the folded instruction would have been inserted in a wrong location thus leaving the CFG in an inconsistent state. This patch fixes the problem and add two reproducible test cases to existing test 'InstCombine/select-cmp-cttz-ctlz.ll'. llvm-svn: 229124
* InstCombine: Combine select sequences into a single selectMatthias Braun2015-02-061-0/+18
| | | | | | | | | | | | | | Normalize select(C0, select(C1, a, b), b) -> select((C0 & C1), a, b) select(C0, a, select(C1, a, b)) -> select((C0 | C1), a, b) This normal form may enable further combines on the And/Or and shortens paths for the values. Many targets prefer the other but can go back easily in CodeGen. Differential Revision: http://reviews.llvm.org/D7399 llvm-svn: 228409
* [InstCombine] Teach how to fold a select into a cttz/ctlz with the ↵Andrea Di Biagio2015-01-271-0/+63
| | | | | | | | | | | 'is_zero_undef' flag. This patch teaches the Instruction Combiner how to fold a cttz/ctlz followed by a icmp plus select into a single cttz/ctlz with flag 'is_zero_undef' cleared. Added test InstCombine/select-cmp-cttz-ctlz.ll. llvm-svn: 227197
* [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-22/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Squash an icmp+select into bitwise arithmeticDavid Majnemer2014-12-201-6/+24
| | | | | | | | | (X & INT_MIN) == 0 ? X ^ INT_MIN : X into X | INT_MIN (X & INT_MIN) != 0 ? X ^ INT_MIN : X into X & INT_MAX This fixes PR21993. llvm-svn: 224676
* InstCombine: Restore optimizations lost in r210006David Majnemer2014-11-271-0/+28
| | | | | | | | This restores our ability to optimize: (X & C) == 0 ? X ^ C : X into X | C (X & C) != 0 ? X ^ C : X into X & ~C llvm-svn: 222871
* Revert "Added inst combine transforms for single bit tests from Chris's note"David Majnemer2014-11-261-28/+1
| | | | | | | | | | | This reverts commit r210006, it miscompiled libapr which is used in who knows how many projects. A test has been added to ensure that we don't regress again. I'll work on a rewrite of what the optimization was trying to do later. llvm-svn: 222856
* Bug 21610: Canonicalize min/max fcmp selects to use ordered comparisonsMatt Arsenault2014-11-241-1/+30
| | | | llvm-svn: 222705
* Untabify and whitespace cleanups.NAKAMURA Takumi2014-10-281-5/+5
| | | | llvm-svn: 220771
* Make use of @llvm.assume in ValueTracking (computeKnownBits, etc.)Hal Finkel2014-09-071-12/+23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* This removes TODO added in http://reviews.llvm.org/D3658Dinesh Dwivedi2014-06-121-2/+9
| | | | | | | | | | | The patch transforms ABS(NABS(X)) -> ABS(X) NABS(ABS(X)) -> NABS(X) Differential Revision: http://reviews.llvm.org/D4040 llvm-svn: 210782
* Added select flavour for ABS and NEG(ABS)Dinesh Dwivedi2014-06-061-18/+48
| | | | | | | | | | | | | | | | This patch can identify ABS(X) ==> (X >s 0) ? X : -X and (X >s -1) ? X : -X ABS(X) ==> (X <s 0) ? -X : X and (X <s 1) ? -X : X NABS(X) ==> (X >s 0) ? -X : X and (X >s -1) ? -X : X NABS(X) ==> (X <s 0) ? X : -X and (X <s 1) ? X : -X and can transform ABS(ABS(X)) -> ABS(X) NABS(NABS(X)) -> NABS(X) Differential Revision: http://reviews.llvm.org/D3658 llvm-svn: 210312
* Added inst combine transforms for single bit tests from Chris's noteDinesh Dwivedi2014-06-021-1/+28
| | | | | | | | | | | | if ((x & C) == 0) x |= C becomes x |= C if ((x & C) != 0) x ^= C becomes x &= ~C if ((x & C) == 0) x ^= C becomes x |= C if ((x & C) != 0) x &= ~C becomes x &= ~C if ((x & C) == 0) x &= ~C becomes nothing Differential Revision: http://reviews.llvm.org/D3777 llvm-svn: 210006
* Added inst-combine for 'MIN(MIN(A, 97), 23)' and 'MAX(MAX(A, 23), 97)'Dinesh Dwivedi2014-05-191-5/+13
| | | | | | | | | | | This removes TODO added in r208849 [http://reviews.llvm.org/D3629] MIN(MIN(A, 97), 23) -> MIN(A, 23) MAX(MAX(A, 23), 97) -> MAX(A, 97) Differential Revision: http://reviews.llvm.org/D3785 llvm-svn: 209110
* Reverting r208848, reason: build failure: ↵Dinesh Dwivedi2014-05-151-37/+5
| | | | | | sanitizer-x86_64-linux-bootstrap/builds/3399 llvm-svn: 208852
* Added instcombine for 'MIN(MIN(A, 27), 93)' and 'MAX(MAX(A, 93), 27)'Dinesh Dwivedi2014-05-151-2/+18
| | | | | | | | | MIN(MIN(A, 23), 97) -> MIN(A, 23) MAX(MAX(A, 97), 23) -> MAX(A, 97) Differential Revision: http://reviews.llvm.org/D3629 llvm-svn: 208849
* Added inst combine transforms for single bit tests from Chris's noteDinesh Dwivedi2014-05-151-5/+37
| | | | | | | | | | | | | | | if ((x & C) == 0) x |= C becomes x |= C if ((x & C) != 0) x ^= C becomes x &= ~C if ((x & C) == 0) x ^= C becomes x |= C if ((x & C) != 0) x &= ~C becomes x &= ~C if ((x & C) == 0) x &= ~C becomes nothing Z3 Verifications code for above transform http://rise4fun.com/Z3/Pmsh Differential Revision: http://reviews.llvm.org/D3717 llvm-svn: 208848
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-31/+31
| | | | 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
* [Modules] Move the LLVM IR pattern match header into the IR library, itChandler Carruth2014-03-041-1/+1
| | | | | | obviously is coupled to the IR. llvm-svn: 202818
* Rename many DataLayout variables from TD to DL.Rafael Espindola2014-02-211-9/+9
| | | | | | | | | I am really sorry for the noise, but the current state where some parts of the code use TD (from the old name: TargetData) and other parts use DL makes it hard to write a patch that changes where those variables come from and how they are passed along. llvm-svn: 201827
* Fix more instances of dropped fast math flags when optimizing FADD ↵Owen Anderson2014-01-181-3/+14
| | | | | | instructions. All found by inspection (aka grep). llvm-svn: 199528
* InstCombine: Only foldSelectICmpAndOr for integer typesJustin Bogner2013-09-271-1/+1
| | | | | | | | | | Currently foldSelectICmpAndOr asserts if the "or" involves a vector containing several of the same power of two. We can easily avoid this by only performing the fold on integer types, like foldSelectICmpAnd does. Fixes <rdar://problem/15012516> llvm-svn: 191552
* InstCombine: Also turn selects fed by an and into arithmetic when the types ↵Benjamin Kramer2013-06-291-4/+9
| | | | | | | | | don't match. Inserting a zext or trunc is sufficient. This pattern is somewhat common in LLVM's pointer mangling code. llvm-svn: 185270
* Revert r164763 because it introduces new shuffles.Nadav Rotem2013-05-061-19/+1
| | | | | | Thanks Nick Lewycky for pointing this out. llvm-svn: 181177
* Fix a bug in foldSelectICmpAndOr.David Majnemer2013-04-301-1/+2
| | | | | | | Differences in bitwidth between X and Y could exist even if C1 and C2 have the same Log2 representation. llvm-svn: 180779
OpenPOWER on IntegriCloud