summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [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
* Fix "Combine bit test + conditional or into simple math"David Majnemer2013-04-301-0/+64
| | | | | | | | | This fixes the optimization introduced in r179748 and reverted in r179750. While the optimization was sound, it did not properly respect differences in bit-width. llvm-svn: 180777
* Keep coding stanard. Don't use "else if" after "return".Jakub Staszak2013-04-191-3/+4
| | | | llvm-svn: 179826
* Revert "Combine bit test + conditional or into simple math"David Majnemer2013-04-181-61/+0
| | | | | | It is causing stage2 builds to fail, let's get them running again. llvm-svn: 179750
* Combine bit test + conditional or into simple mathDavid Majnemer2013-04-181-0/+61
| | | | | | | | | | | | | | | | Simplify: (select (icmp eq (and X, C1), 0), Y, (or Y, C2)) Into: (or (shl (and X, C1), C3), y) Where: C3 = Log(C2) - Log(C1) If: C1 and C2 are both powers of two llvm-svn: 179748
* Tidy up a bit. No functional change.Jim Grosbach2013-04-051-2/+2
| | | | llvm-svn: 178915
* Check if Type is a vector before calling function Type::getVectorNumElements.Akira Hatanaka2013-03-281-3/+4
| | | | llvm-svn: 178208
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-1/+1
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* InstCombine: Fix an edge case where constant icmps could sneak into ↵Benjamin Kramer2012-10-201-0/+4
| | | | | | | | ConstantFoldInstOperands and crash. Have to refactor the ConstantFolder interface one day to define bugs like this away. Fixes PR14131. llvm-svn: 166374
* Move TargetData to DataLayout.Micah Villmow2012-10-081-1/+1
| | | | llvm-svn: 165402
* Surprisingly, we missed a trivial case here. Fix that!Nick Lewycky2012-09-281-0/+4
| | | | llvm-svn: 164814
* Prefer shuffles to selects. Backends love shuffles!Nick Lewycky2012-09-271-1/+19
| | | | llvm-svn: 164763
* fix infinite loop in instcombine in the presence of a (malformed) ↵Nuno Lopes2012-07-271-0/+4
| | | | | | | | self-referencing select inst. This can happen as long as the instruction is not reachable. Instcombine does generate these unreachable malformed selects when doing RAUW llvm-svn: 160874
* Simplify demanded bits of select sources where the condition is a constant ↵Pete Cooper2012-07-261-0/+11
| | | | | | vector llvm-svn: 160835
* Fix a bug in FoldSelectOpOp. Bitcast ops may change the number of vector ↵Nadav Rotem2012-06-071-0/+6
| | | | | | elements, which may disagree with the select condition type. llvm-svn: 158166
* InstCombine: Fix infinite loop when encountering switch on trivial icmp.Benjamin Kramer2012-05-281-1/+1
| | | | | | | | | | | | The test case feeds the following into InstCombine's visitSelect: %tobool8 = icmp ne i32 0, 0 %phitmp = select i1 %tobool8, i32 3, i32 0 Then instcombine replaces the right side of the switch with 0, doesn't notice that nothing changes and tries again indefinitely. This fixes PR12897. llvm-svn: 157587
* More dead code removal (using -Wunreachable-code)David Blaikie2012-01-201-1/+0
| | | | llvm-svn: 148578
* Added InstCombine for "select cond, ~cond, x" type patternsPete Cooper2011-12-151-0/+7
| | | | | | These can be reduced to "~cond & x" or "~cond | x" llvm-svn: 146624
* Fix a few more places where TargetData/TargetLibraryInfo is not being passed.Chad Rosier2011-12-021-14/+17
| | | | | | Add FIXMEs to places that are non-trivial to fix. llvm-svn: 145661
* Add a new icmp+select optz'n. Also shows off the load(cst) folding added inNick Lewycky2011-10-021-0/+6
| | | | | | r140966. llvm-svn: 140969
* Enhance a couple places where we were doing constant folding of instructions,Nick Lewycky2011-10-021-1/+6
| | | | | | but not load instructions. Noticed by inspection. llvm-svn: 140966
* Clean up includes of llvm/Analysis/ConstantFolding.h so it's included where ↵Eli Friedman2011-07-201-0/+1
| | | | | | it's used and not included where it isn't. llvm-svn: 135628
* Use ArrayRef in ConstantFoldInstOperands and ConstantFoldCall.Jay Foad2011-07-191-1/+1
| | | | llvm-svn: 135477
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-181-2/+2
| | | | llvm-svn: 135375
* PR10180: Fix a instcombine crash with FP vectors.Eli Friedman2011-06-231-2/+2
| | | | llvm-svn: 133756
* ConstantFoldInstOperands doesn't like compares, hand it off to instsimplify ↵Benjamin Kramer2011-05-281-0/+10
| | | | | | | | instead. Fixes PR10040. llvm-svn: 132254
* InstCombine: Make switch folding with equality compares more aggressive by ↵Benjamin Kramer2011-05-271-15/+54
| | | | | | | | trying instsimplify on the arm where we know the compared value. Stuff like "x == y ? y : x&y" now folds into "x&y". llvm-svn: 132185
OpenPOWER on IntegriCloud