summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Convert PHI getIncomingValue() to foreach over incoming_values(). NFC.Pete Cooper2015-05-121-2/+2
| | | | | | | | We already had a method to iterate over all the incoming values of a PHI. This just changes all eligible code to use it. Ineligible code included anything which cared about the index, or was also trying to get the i'th incoming BB. llvm-svn: 237169
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-11/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [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-7/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Make use of @llvm.assume in ValueTracking (computeKnownBits, etc.)Hal Finkel2014-09-071-19/+27
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* fixed typo in commentSanjay Patel2014-07-221-1/+1
| | | | llvm-svn: 213614
* Move ashr optimization from InstCombineShift to InstSimplify.Suyog Sarda2014-07-171-5/+0
| | | | | | | | | Refactor code, no functionality change, test case moved from instcombine to instsimplify. Differential Revision: http://reviews.llvm.org/D4102 llvm-svn: 213231
* Remove redundant code in InstCombineShift, no functionality change because ↵Nick Lewycky2014-06-191-5/+0
| | | | | | instsimplify already does this and instcombine calls instsimplify a few lines above. Patch by Suyog Sarda! llvm-svn: 211250
* Reorder shuffle and binary operation.Serge Pavlov2014-05-111-0/+9
| | | | | | | | | | | | | This patch enables transformations: BinOp(shuffle(v1), shuffle(v2)) -> shuffle(BinOp(v1, v2)) BinOp(shuffle(v1), const1) -> shuffle(BinOp, const2) They allow to eliminate extra shuffles in some cases. Differential Revision: http://reviews.llvm.org/D3525 llvm-svn: 208488
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-10/+10
| | | | llvm-svn: 207196
* Remove dead code in instcombine.Matt Arsenault2014-04-231-11/+2
| | | | | | | | | Don't replace shifts greater than the type with the maximum shift. This isn't hit anywhere in the tests, and somewhere else is replacing these with undef. llvm-svn: 207000
* [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
* Revert "Revert r206045, "Fix shift by constants for vector.""Matt Arsenault2014-04-141-15/+33
| | | | | | Fix cases where the Value itself is used, and not the constant value. llvm-svn: 206214
* Whitespace.NAKAMURA Takumi2014-04-141-1/+0
| | | | llvm-svn: 206154
* Revert r206045, "Fix shift by constants for vector."NAKAMURA Takumi2014-04-141-22/+12
| | | | | | It broke some builders, at least, i686. llvm-svn: 206153
* Fix shift by constants for vector.Matt Arsenault2014-04-111-12/+22
| | | | | | ashr <N x iM>, <N x iM> M -> undef llvm-svn: 206045
* [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-3/+3
| | | | | | | | | 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
* Revert r174152. The shift amount may overflow and in that case this ↵Nadav Rotem2013-02-011-6/+0
| | | | | | transformation is illegal. llvm-svn: 174156
* Optimize shift lefts of a constant by a value plus constant into a single shift.Nadav Rotem2013-02-011-0/+6
| | | | llvm-svn: 174152
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-1/+1
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use m_OneUse pattern instead of hasOneUse() method.Jakub Staszak2012-12-091-7/+4
| | | | | | No functionality change. llvm-svn: 169703
* Remove trailing spaces.Jakub Staszak2012-12-091-80/+80
| | | | llvm-svn: 169701
* 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
* Move TargetData to DataLayout.Micah Villmow2012-10-081-1/+1
| | | | llvm-svn: 165402
* Revert 'Fix a typo 'iff' => 'if''. iff is an abreviation of if and only if. ↵Sylvestre Ledru2012-09-271-2/+2
| | | | | | See: http://en.wikipedia.org/wiki/If_and_only_if Commit 164767 llvm-svn: 164768
* Fix a typo 'iff' => 'if'Sylvestre Ledru2012-09-271-2/+2
| | | | llvm-svn: 164767
* PR12967: Don't crash when trying to fold a shift that's larger than the ↵Benjamin Kramer2012-05-271-1/+1
| | | | | | type's size. llvm-svn: 157548
* Reapply r155136 after fixing PR12599.Jakob Stoklund Olesen2012-04-231-39/+35
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Original commit message: Defer some shl transforms to DAGCombine. The shl instruction is used to represent multiplication by a constant power of two as well as bitwise left shifts. Some InstCombine transformations would turn an shl instruction into a bit mask operation, making it difficult for later analysis passes to recognize the constsnt multiplication. Disable those shl transformations, deferring them to DAGCombine time. An 'shl X, C' instruction is now treated mostly the same was as 'mul X, C'. These transformations are deferred: (X >>? C) << C --> X & (-1 << C) (When X >> C has multiple uses) (X >>? C1) << C2 --> X << (C2-C1) & (-1 << C2) (When C2 > C1) (X >>? C1) << C2 --> X >>? (C1-C2) & (-1 << C2) (When C1 > C2) The corresponding exact transformations are preserved, just like div-exact + mul: (X >>?,exact C) << C --> X (X >>?,exact C1) << C2 --> X << (C2-C1) (X >>?,exact C1) << C2 --> X >>?,exact (C1-C2) The disabled transformations could also prevent the instruction selector from recognizing rotate patterns in hash functions and cryptographic primitives. I have a test case for that, but it is too fragile. llvm-svn: 155362
* Revert r155136 "Defer some shl transforms to DAGCombine."Jakob Stoklund Olesen2012-04-201-35/+39
| | | | | | | | | While the patch was perfect and defect free, it exposed a really nasty bug in X86 SelectionDAG that caused an llc crash when compiling lencod. I'll put the patch back in after fixing the SelectionDAG problem. llvm-svn: 155181
* Defer some shl transforms to DAGCombine.Jakob Stoklund Olesen2012-04-191-39/+35
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The shl instruction is used to represent multiplication by a constant power of two as well as bitwise left shifts. Some InstCombine transformations would turn an shl instruction into a bit mask operation, making it difficult for later analysis passes to recognize the constsnt multiplication. Disable those shl transformations, deferring them to DAGCombine time. An 'shl X, C' instruction is now treated mostly the same was as 'mul X, C'. These transformations are deferred: (X >>? C) << C --> X & (-1 << C) (When X >> C has multiple uses) (X >>? C1) << C2 --> X << (C2-C1) & (-1 << C2) (When C2 > C1) (X >>? C1) << C2 --> X >>? (C1-C2) & (-1 << C2) (When C1 > C2) The corresponding exact transformations are preserved, just like div-exact + mul: (X >>?,exact C) << C --> X (X >>?,exact C1) << C2 --> X << (C2-C1) (X >>?,exact C1) << C2 --> X >>?,exact (C1-C2) The disabled transformations could also prevent the instruction selector from recognizing rotate patterns in hash functions and cryptographic primitives. I have a test case for that, but it is too fragile. llvm-svn: 155136
* Convert assert(0) to llvm_unreachableCraig Topper2012-02-071-1/+1
| | | | llvm-svn: 149967
* Remove pointless asserts.Nick Lewycky2012-01-041-2/+0
| | | | llvm-svn: 147529
* Teach instcombine all sorts of great stuff about shifts that have exact, nuw orNick Lewycky2012-01-041-6/+56
| | | | | | nsw bits on them. llvm-svn: 147528
* Make use of the exact bit when optimizing '(X >>exact 3) << 1' to eliminate theNick Lewycky2011-12-311-5/+11
| | | | | | | 'and' that would zero out the trailing bits, and to produce an exact shift ourselves. llvm-svn: 147391
* Fix a few more places where TargetData/TargetLibraryInfo is not being passed.Chad Rosier2011-12-021-1/+2
| | | | | | Add FIXMEs to places that are non-trivial to fix. llvm-svn: 145661
* Make sure to correctly clear the exact/nuw/nsw flags off of shifts when they ↵Eli Friedman2011-07-291-19/+27
| | | | | | are combined together. <rdar://problem/9859829> llvm-svn: 136435
* 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
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-181-1/+1
| | | | llvm-svn: 135375
* Balance parentheses.Benjamin Kramer2011-04-291-1/+1
| | | | llvm-svn: 130489
* InstCombine: turn (C1 << A) << C2) into (C1 << C2) << A)Benjamin Kramer2011-04-291-1/+8
| | | | | | Fixes PR9809. llvm-svn: 130485
* Enhance a bunch of transformations in instcombine to start generatingChris Lattner2011-02-101-17/+60
| | | | | | | | | | | exact/nsw/nuw shifts and have instcombine infer them when it can prove that the relevant properties are true for a given shift without them. Also, a variety of refactoring to use the new patternmatch logic thrown in for good luck. I believe that this takes care of a bunch of related code quality issues attached to PR8862. llvm-svn: 125267
* Teach instsimplify some tricks about exact/nuw/nsw shifts.Chris Lattner2011-02-091-3/+7
| | | | | | improve interfaces to instsimplify to take this info. llvm-svn: 125196
* Null initialize a few variables flagged byTed Kremenek2011-01-231-1/+1
| | | | | | | | | | clang's -Wuninitialized-experimental warning. While these don't look like real bugs, clang's -Wuninitialized-experimental analysis is stricter than GCC's, and these fixes have the benefit of being general nice cleanups. llvm-svn: 124073
* Move some shift transforms out of instcombine and into InstructionSimplify.Duncan Sands2011-01-141-26/+10
| | | | | | | | | | | | While there, I noticed that the transform "undef >>a X -> undef" was wrong. For example if X is 2 then the top two bits must be equal, so the result can not be anything. I fixed this in the constant folder as well. Also, I made the transform for "X << undef" stronger: it now folds to undef always, even though X might be zero. This is in accordance with the LangRef, but I must admit that it is fairly aggressive. Also, I added "i32 X << 32 -> undef" following the LangRef and the constant folder, likewise fairly aggressive. llvm-svn: 123417
* When determining if we can fold (x >> C1) << C2, the bits that we need to ↵Owen Anderson2010-12-231-1/+2
| | | | | | | | verify are zero are not the low bits of x, but the bits that WILL be the low bits after the operation completes. llvm-svn: 122529
* Really check that the bits that will become zero are actually already zeroDan Gohman2010-12-091-2/+1
| | | | | | before eliminating the operation that zeros them. This fixes rdar://8739316. llvm-svn: 121353
* The srem -> urem transform is not safe for any divisor that's not a power of ↵Benjamin Kramer2010-11-231-11/+9
| | | | | | | | | | two. E.g. -5 % 5 is 0 with srem and 1 with urem. Also addresses Frits van Bommel's comments. llvm-svn: 120049
* InstCombine: Reduce "X shift (A srem B)" to "X shift (A urem B)" iff B is ↵Benjamin Kramer2010-11-231-0/+15
| | | | | | | | positive. This allows to transform the rem in "1 << ((int)x % 8);" to an and. llvm-svn: 120028
OpenPOWER on IntegriCloud