summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Add additional patterns for @llvm.assume in ValueTrackingHal Finkel2014-09-071-0/+24
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This builds on r217342, which added the infrastructure to compute known bits using assumptions (@llvm.assume calls). That original commit added only a few patterns (to catch common cases related to determining pointer alignment); this change adds several other patterns for simple cases. r217342 contained that, for assume(v & b = a), bits in the mask that are known to be one, we can propagate known bits from the a to v. It also had a known-bits transfer for assume(a = b). This patch adds: assume(~(v & b) = a) : For those bits in the mask that are known to be one, we can propagate inverted known bits from the a to v. assume(v | b = a) : For those bits in b that are known to be zero, we can propagate known bits from the a to v. assume(~(v | b) = a): For those bits in b that are known to be zero, we can propagate inverted known bits from the a to v. assume(v ^ b = a) : For those bits in b that are known to be zero, we can propagate known bits from the a to v. For those bits in b that are known to be one, we can propagate inverted known bits from the a to v. assume(~(v ^ b) = a) : For those bits in b that are known to be zero, we can propagate inverted known bits from the a to v. For those bits in b that are known to be one, we can propagate known bits from the a to v. assume(v << c = a) : For those bits in a that are known, we can propagate them to known bits in v shifted to the right by c. assume(~(v << c) = a) : For those bits in a that are known, we can propagate them inverted to known bits in v shifted to the right by c. assume(v >> c = a) : For those bits in a that are known, we can propagate them to known bits in v shifted to the right by c. assume(~(v >> c) = a) : For those bits in a that are known, we can propagate them inverted to known bits in v shifted to the right by c. assume(v >=_s c) where c is non-negative: The sign bit of v is zero assume(v >_s c) where c is at least -1: The sign bit of v is zero assume(v <=_s c) where c is negative: The sign bit of v is one assume(v <_s c) where c is non-positive: The sign bit of v is one assume(v <=_u c): Transfer the known high zero bits assume(v <_u c): Transfer the known high zero bits (if c is know to be a power of 2, transfer one more) A small addition to InstCombine was necessary for some of the test cases. The problem is that when InstCombine was simplifying and, or, etc. it would fail to check the 'do I know all of the bits' condition before checking less specific conditions and would not fully constant-fold the result. I'm not sure how to trigger this aside from using assumptions, so I've just included the change here. llvm-svn: 217343
* Make use of @llvm.assume in ValueTracking (computeKnownBits, etc.)Hal Finkel2014-09-071-15/+24
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* InstCombine: Don't unconditionally preserve 'nuw' when shrinking constantsDavid Majnemer2014-08-221-6/+12
| | | | | | | | | | | | Consider: %add = add nuw i32 %a, -16777216 %and = and i32 %add, 255 Regardless of whether or not we demand the sign bit of %add, we cannot replace -16777216 with 2130706432 without also removing 'nuw' from the instruction. llvm-svn: 216273
* InstCombine: Don't unconditionally preserve 'nsw' when shrinking constantsDavid Majnemer2014-08-221-0/+8
| | | | | | | | | | | | | | Consider: %add = add nsw i32 %a, -16777216 %and = and i32 %add, 255 Regardless of whether or not we demand the sign bit of %add, we cannot replace -16777216 with 2130706432 without also removing 'nsw' from the instruction. This fixes PR20377. llvm-svn: 216261
* Rename ComputeMaskedBits to computeKnownBits. "Masked" has beenJay Foad2014-05-141-13/+13
| | | | | | inappropriate since it lost its Mask parameter in r154011. llvm-svn: 208811
* [C++] Use 'nullptr'.Craig Topper2014-04-281-1/+1
| | | | llvm-svn: 207394
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-27/+27
| | | | 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-1/+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-2/+2
| | | | | | | | | 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
* Remove x86_sse42_crc32_64_8 intrinsic. It has no functional difference from ↵Craig Topper2013-10-151-1/+0
| | | | | | x86_sse42_crc32_32_8 and was not mapped to a clang builtin. I'm not even sure why this form of the instruction is even called out explicitly in the docs. Also add AutoUpgrade support to convert it into the other intrinsic with appropriate trunc and zext. llvm-svn: 192672
* InstCombine: Check for zero shift amounts before subtracting one causing ↵Benjamin Kramer2013-08-301-10/+15
| | | | | | | | | integer overflow. PR17026. Also avoid undefined shifts and shift amounts larger than 64 bits (those are always undef because we can't represent integer types that large). llvm-svn: 189672
* InstCombine: Don't just copy known bits from the first operand of an srem.Benjamin Kramer2013-05-091-1/+1
| | | | | | | That's obviously wrong. Conservatively restrict it to the sign bit, which matches the original intention of this analysis. Fixes PR15940. llvm-svn: 181518
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-2/+2
| | | | | | | | | | | | | | | | | | | | | 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
* Remove trailing whitespaceCraig Topper2012-12-221-126/+126
| | | | llvm-svn: 170990
* - Fix a problematic way in creating all-the-1 APInt.Shuxin Yang2012-12-121-2/+4
| | | | | | - Propagate "exact" bit of [l|a]shr instruction. llvm-svn: 169942
* For rdar://12329730, last piece.Shuxin Yang2012-12-041-1/+14
| | | | | | | | | | | | | | | | | | | | | This change attempts to simplify (X^Y) -> X or Y in the user's context if we know that only bits from X or Y are demanded. A minimized case is provided bellow. This change will simplify "t>>16" into "var1 >>16". ============================================================= unsigned foo (unsigned val1, unsigned val2) { unsigned t = val1 ^ 1234; return (t >> 16) | t; // NOTE: t is used more than once. } ============================================================= Note that if the "t" were used only once, the expression would be finally optimized as well. However, with with this change, the optimization will take place earlier. Reviewed by Nadav, Thanks a lot! llvm-svn: 169317
* rdar://12329730 (2nd part, revised)Shuxin Yang2012-12-041-1/+2
| | | | | | | The type of shirt-right (logical or arithemetic) should remain unchanged when transforming "X << C1 >> C2" into "X << (C1-C2)" llvm-svn: 169209
* rdar://12329730 (2nd part)Shuxin Yang2012-12-041-1/+85
| | | | | | | | | | | This change tries to simmplify E1 = " X >> C1 << C2" into : - E2 = "X << (C2 - C1)" if C2 > C1, or - E2 = "X >> (C1 - C2)" if C1 > C2, or - E2 = X if C1 == C2. Reviewed by Nadav. Thanks! llvm-svn: 169182
* 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
* Simplify demanded bits of select sources where the condition is a constant ↵Pete Cooper2012-07-261-0/+23
| | | | | | vector llvm-svn: 160835
* Teach SimplifyDemandedBits how to look through fpext and fptrunc to simplify ↵Pete Cooper2012-07-261-0/+6
| | | | | | their operand llvm-svn: 160823
* Back out r160101 and instead implement a dag combine to recover from ↵Evan Cheng2012-07-171-7/+0
| | | | | | instcombine transformation. llvm-svn: 160387
* Instcombine was transforming:Evan Cheng2012-07-121-0/+7
| | | | | | | | | | | | | | | | | | | | | | | | %shr = lshr i64 %key, 3 %0 = load i64* %val, align 8 %sub = add i64 %0, -1 %and = and i64 %sub, %shr ret i64 %and to: %shr = lshr i64 %key, 3 %0 = load i64* %val, align 8 %sub = add i64 %0, 2305843009213693951 %and = and i64 %sub, %shr ret i64 %and The demanded bit optimization is actually a pessimization because add -1 would be codegen'ed as a sub 1. Teach the demanded constant shrinking optimization to check for negated constant to make sure it is actually reducing the width of the constant. rdar://11793464 llvm-svn: 160101
* Always compute all the bits in ComputeMaskedBits.Rafael Espindola2012-04-041-16/+10
| | | | | | | | This allows us to keep passing reduced masks to SimplifyDemandedBits, but know about all the bits if SimplifyDemandedBits fails. This allows instcombine to simplify cases like the one in the included testcase. llvm-svn: 154011
* continue making the world safe for ConstantDataVector. At this point,Chris Lattner2012-01-271-1/+1
| | | | | | | we should (theoretically optimize and codegen ConstantDataVector as well as ConstantVector. llvm-svn: 149116
* use Constant::getAggregateElement to simplify a bunch of code.Chris Lattner2012-01-251-42/+22
| | | | llvm-svn: 148934
* use ConstantVector::getSplat in a few places.Chris Lattner2012-01-251-2/+2
| | | | llvm-svn: 148929
* basic instcombine support for CDS.Chris Lattner2012-01-241-11/+24
| | | | llvm-svn: 148806
* Teach instcombine all sorts of great stuff about shifts that have exact, nuw orNick Lewycky2012-01-041-2/+3
| | | | | | nsw bits on them. llvm-svn: 147528
* InstCombine: Canonicalize (2^n)-1 - x into (2^n)-1 ^ x iff x is known to be ↵Benjamin Kramer2011-12-241-0/+11
| | | | | | | | | | | smaller than 2^n. This has the obvious advantage of being commutable and is always a win on x86 because const - x wastes a register there. On less weird architectures this may lead to a regression because other arithmetic doesn't fuse with it anymore. I'll address that problem in a followup. llvm-svn: 147254
* Stop emitting instructions with the name "tmp" they eat up memory and have ↵Benjamin Kramer2011-09-271-6/+3
| | | | | | | | to be uniqued, without any benefit. If someone prefers %tmp42 to %42, run instnamer. llvm-svn: 140634
* Make demanded-elt simplification for shufflevector slightly stronger. ↵Eli Friedman2011-09-151-0/+3
| | | | | | Spotted by inspection. llvm-svn: 139768
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-181-6/+6
| | | | llvm-svn: 135375
* Renamed llvm.x86.sse42.crc32 intrinsics; crc64 doesn't exist. Chad Rosier2011-05-261-2/+2
| | | | | | | crc32.[8|16|32] have been renamed to .crc32.32.[8|16|32] and crc64.[8|16|32] have been renamed to .crc32.64.[8|64]. llvm-svn: 132163
* Revert r131664 and fix it in instcombine instead. rdar://9467055Evan Cheng2011-05-201-0/+4
| | | | llvm-svn: 131708
* Make the demanded bits/elements optimizations preserve debug line information.Eli Friedman2011-05-191-14/+14
| | | | | | I'm not sure this is quite ideal, but I can't really think of any better way to do it. llvm-svn: 131616
* X86 pmovsx/pmovzx ignore the upper half of their inputs.Stuart Hastings2011-05-171-1/+1
| | | | | | rdar://problem/6945110 llvm-svn: 131493
* PR9346: Prevent SimplifyDemandedBits from incorrectly introducingEli Friedman2011-03-091-0/+4
| | | | | | INT_MIN % -1. llvm-svn: 127306
* Add more analysis of the sign bit of an srem instruction. If the LHS is negativeNick Lewycky2011-03-071-0/+12
| | | | | | | then the result could go either way. If it's provably positive then so is the srem. Fixes PR9343 #7! llvm-svn: 127146
* teach SimplifyDemandedBits that exact shifts demand the bits they Chris Lattner2011-02-101-3/+23
| | | | | | | are shifting out since they do require them to be zeros. Similarly for NUW/NSW bits of shl llvm-svn: 125263
* PR5207: Change APInt methods trunc(), sext(), zext(), sextOrTrunc() andJay Foad2010-12-071-19/+19
| | | | | | | | zextOrTrunc(), and APSInt methods extend(), extOrTrunc() and new method trunc(), to be const and to return a new value instead of modifying the object in place. llvm-svn: 121120
* PR5207: Rename overloaded APInt methods set(), clear(), flip() toJay Foad2010-12-011-18/+18
| | | | | | setAllBits(), setBit(unsigned), etc. llvm-svn: 120564
* use ArgOperand APIGabor Greif2010-06-281-4/+4
| | | | llvm-svn: 107016
* use ArgOperand APIGabor Greif2010-06-241-4/+4
| | | | llvm-svn: 106737
* Revert 101465, it broke internal OpenGL testing.Eric Christopher2010-04-161-8/+8
| | | | | | | Probably the best way to know that all getOperand() calls have been handled is to replace that API instead of updating. llvm-svn: 101579
* reapply r101434Gabor Greif2010-04-161-8/+8
| | | | | | | | | | | | | with a fix for self-hosting rotate CallInst operands, i.e. move callee to the back of the operand array the motivation for this patch are laid out in my mail to llvm-commits: more efficient access to operands and callee, faster callgraph-construction, smaller compiler binary llvm-svn: 101465
OpenPOWER on IntegriCloud