aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/InstructionSimplify.cpp
AgeCommit message (Collapse)AuthorFilesLines
2015-01-04[PM] Split the AssumptionTracker immutable pass into two separate APIs:Chandler Carruth1-182/+163
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
2014-12-20InstSimplify: Don't bother if getScalarSizeInBits returns zeroDavid Majnemer1-4/+5
getScalarSizeInBits returns zero when the comparison operands are not integral. No functionality change intended. llvm-svn: 224675
2014-12-20Simplify the codeDavid Majnemer1-41/+25
No functionality change intended. llvm-svn: 224673
2014-12-20InstSimplify: Optimize away pointless comparisonsDavid Majnemer1-2/+38
(X & INT_MIN) ? X & INT_MAX : X into X & INT_MAX (X & INT_MIN) ? X : X & INT_MAX into X (X & INT_MIN) ? X | INT_MIN : X into X (X & INT_MIN) ? X : X | INT_MIN into X | INT_MIN llvm-svn: 224669
2014-12-17InstSimplify: shl nsw/nuw undef, %V -> undefDavid Majnemer1-13/+7
We can always choose an value for undef which might cause %V to shift out an important bit except for one case, when %V is zero. However, shl behaves like an identity function when the right hand side is zero. llvm-svn: 224405
2014-12-10ConstantFold, InstSimplify: undef >>a x can be either -1 or 0, choose 0David Majnemer1-2/+2
Zero is usually a nicer constant to have than -1. llvm-svn: 223969
2014-12-10InstSimplify: [al]shr exact undef, %X -> undefDavid Majnemer1-2/+6
Exact shifts always keep the non-zero bits of their input. This means it keeps it's undef bits. llvm-svn: 223923
2014-12-10InstSimplify: div %X, 0 -> undefDavid Majnemer1-0/+4
We already optimized rem %X, 0 to undef, we should do the same for div. llvm-svn: 223919
2014-12-08InstSimplify: Try to bring back the rest of r223583David Majnemer1-2/+7
This reverts r223624 with a small tweak, hopefully this will make stage3 equivalent. llvm-svn: 223679
2014-12-08Revert a part of r223583, for now. It seems causing different emission ↵NAKAMURA Takumi1-5/+0
between stage2(gcc-clang) and stage3 clang. Investigating. llvm-svn: 223624
2014-12-06InstSimplify: Optimize away useless unsigned comparisonsDavid Majnemer1-0/+49
Code like X < Y && Y == 0 should always be folded away to false. llvm-svn: 223583
2014-12-04Revert "r223364 - Revert r223347 which has caused crashes on bootstrap bots."Hal Finkel1-3/+14
Reapply r223347, with a fix to not crash on uninserted instructions (or more precisely, instructions in uninserted blocks). bugpoint was able to reduce the test case somewhat, but it is still somewhat large (and relies on setting things up to be simplified during inlining), so I've not included it here. Nevertheless, it is clear what is going on and why. Original commit message: Restrict somewhat the memory-allocation pointer cmp opt from r223093 Based on review comments from Richard Smith, restrict this optimization from applying to globals that might resolve lazily to other dynamically-loaded modules, and also from dynamic allocas (which might be transformed into malloc calls). In short, take extra care that the compared-to pointer is really simultaneously live with the memory allocation. llvm-svn: 223371
2014-12-04Revert r223347 which has caused crashes on bootstrap bots.Alexander Potapenko1-13/+3
llvm-svn: 223364
2014-12-04Restrict somewhat the memory-allocation pointer cmp opt from r223093Hal Finkel1-3/+13
Based on review comments from Richard Smith, restrict this optimization from applying to globals that might resolve lazily to other dynamically-loaded modules, and also from dynamic allocas (which might be transformed into malloc calls). In short, take extra care that the compared-to pointer is really simultaneously live with the memory allocation. llvm-svn: 223347
2014-12-01Simplify pointer comparisons involving memory allocation functionsHal Finkel1-0/+35
System memory allocation functions, which are identified at the IR level by the noalias attribute on the return value, must return a pointer into a memory region disjoint from any other memory accessible to the caller. We can use this property to simplify pointer comparisons between allocated memory and local stack addresses and the addresses of global variables. Neither the stack nor global variables can overlap with the region used by the memory allocator. Fixes PR21556. llvm-svn: 223093
2014-11-27InstSimplify: Restore optimizations lost in r210006David Majnemer1-0/+34
This restores our ability to optimize: (X & C) ? X & ~C : X into X & ~C (X & C) ? X : X & ~C into X (X & C) ? X | C : X into X (X & C) ? X : X | C into X | C llvm-svn: 222868
2014-11-25InstSimplify: Handle some simple tautological comparisonsDavid Majnemer1-0/+34
This handles cases where we are comparing a masked value against itself. The analysis could be further improved by making it recursive but such expense is not currently justified. llvm-svn: 222716
2014-11-22InstSimplify: Simplify (sub 0, X) -> X if it's NUWDavid Majnemer1-11/+3
This is a generalization of the X - (0 - Y) -> X transform. llvm-svn: 222611
2014-11-19Update SetVector to rely on the underlying set's insert to return a ↵David Blaikie1-1/+1
pair<iterator, bool> This is to be consistent with StringSet and ultimately with the standard library's associative container insert function. This lead to updating SmallSet::insert to return pair<iterator, bool>, and then to update SmallPtrSet::insert to return pair<iterator, bool>, and then to update all the existing users of those functions... llvm-svn: 222334
2014-11-16InstSimplify: Optimize ICmpInst xform that uses computeKnownBitsDavid Majnemer1-21/+17
A few things: - computeKnownBits is relatively expensive, let's delay its use as long as we can. - Don't create two APInt values just to run computeKnownBits on a ConstantInt, we already know the exact value! - Avoid creating a temporary APInt value in order to calculate unary negation. llvm-svn: 222092
2014-11-05InstSimplify: Exact shifts of X by Y are X if X has the lsb setDavid Majnemer1-11/+31
Exact shifts may not shift out any non-zero bits. Use computeKnownBits to determine when this occurs and just return the left hand side. This fixes PR21477. llvm-svn: 221325
2014-11-04InstSimplify: Fold a hasNoSignedWrap() call into a match() expressionDavid Majnemer1-2/+1
No functionality change intended, it's just a little more concise. llvm-svn: 221281
2014-11-04InstSimplify: Fold a hasNoUnsignedWrap() call into a match() expressionDavid Majnemer1-2/+1
No functionality change intended, it's just a little more concise. llvm-svn: 221280
2014-10-11InstCombine, InstSimplify: (%X /s C1) /s C2 isn't always 0 when C1 * C2 overflowDavid Majnemer1-0/+10
consider: C1 = INT_MIN C2 = -1 C1 * C2 overflows without a doubt but consider the following: %x = i32 INT_MIN This means that (%X /s C1) is 1 and (%X /s C1) /s C2 is -1. N. B. Move the unsigned version of this transform to InstSimplify, it doesn't create any new instructions. This fixes PR21243. llvm-svn: 219567
2014-09-17InstSimplify: Don't allow (x srem y) urem y -> x srem yDavid Majnemer1-3/+5
Let's consider the case where: %x i16 = 32768 %y i16 = 384 %x srem %y = 65408 (%x srem %y) urem %y = 128 llvm-svn: 217939
2014-09-17InstSimplify: ((X % Y) % Y) -> (X % Y)David Majnemer1-0/+5
Patch by Sonam Kumari! Differential Revision: http://reviews.llvm.org/D5350 llvm-svn: 217937
2014-09-15InstSimplify: Simplify trivial and/or of icmpsDavid Majnemer1-0/+114
Some ICmpInsts when anded/ored with another ICmpInst trivially reduces to true or false depending on whether or not all integers or no integers satisfy the intersected/unioned range. This sort of trivial looking code can come about when InstCombine performs a range reduction-type operation on sdiv and the like. This fixes PR20916. llvm-svn: 217750
2014-09-12Fix an ODR violation consisting of two 'struct Query' in the global namespace.Benjamin Kramer1-0/+2
Put them in their own anonymous namespaces. Found by GCC's new -Wodr (PR20915). llvm-svn: 217662
2014-09-07Make use of @llvm.assume in ValueTracking (computeKnownBits, etc.)Hal Finkel1-115/+210
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
2014-08-28InstSimplify: Move a transform from InstCombine to InstSimplifyDavid Majnemer1-0/+35
Several combines involving icmp (shl C2, %X) C1 can be simplified without introducing any new instructions. Move them to InstSimplify; while we are at it, make them more powerful. llvm-svn: 216642
2014-08-27InstSimplify: Don't simplify gep X, (Y-X) to Y if types differDavid Majnemer1-1/+2
It's incorrect to perform this simplification if the types differ. A bitcast would need to be inserted for this to work. This fixes PR20771. llvm-svn: 216597
2014-08-27Reland r216439 215441, majnemer has a real fix for PR20771.Nico Weber1-11/+53
llvm-svn: 216586
2014-08-27Revert r216439 (and r216441, else the former doesn't revert cleanly).Nico Weber1-53/+11
It caused PR 20771. I'll land a test on the clang side. llvm-svn: 216582
2014-08-27InstSimplify: Compute comparison ranges for left shift instructionsDavid Majnemer1-0/+16
'shl nuw CI, x' produces [CI, CI << CLZ(CI)] 'shl nsw CI, x' produces [CI << CLO(CI)-1, CI] if CI is negative 'shl nsw CI, x' produces [CI, CI << CLZ(CI)-1] if CI is non-negative llvm-svn: 216570
2014-08-26InstSimplify: Fold gep X, (sub 0, ptrtoint(X)) to nullDavid Majnemer1-21/+32
Save InstCombine some work if we can perform this fold during InstSimplify. llvm-svn: 216441
2014-08-26InstSimplify: Simplify trivial pointer expressions like b + (e - b)David Majnemer1-5/+36
consider: long long *f(long long *b, long long *e) { return b + (e - b); } we would lower this to something like: define i64* @f(i64* %b, i64* %e) { %1 = ptrtoint i64* %e to i64 %2 = ptrtoint i64* %b to i64 %3 = sub i64 %1, %2 %4 = ashr exact i64 %3, 3 %5 = getelementptr inbounds i64* %b, i64 %4 ret i64* %5 } This should fold away to just 'e'. N.B. This adds m_SpecificInt as a convenient way to match against a particular 64-bit integer when using LLVM's match interface. llvm-svn: 216439
2014-07-31InstSimplify: Simplify (X - (0 - Y)) if the second sub is NUWDavid Majnemer1-0/+12
If the NUW bit is set for 0 - Y, we know that all values for Y other than 0 would produce a poison value. This allows us to replace (0 - Y) with 0 in the expression (X - (0 - Y)) which will ultimately leave us with X. This partially fixes PR20189. llvm-svn: 214384
2014-07-17Rectify r213231. Use proper version of 'ComputeNumSignBits'.Suyog Sarda1-1/+1
Earlier when the code was in InstCombine, we were calling the version of ComputeNumSignBits in InstCombine.h that automatically added the DataLayout* before calling into ValueTracking. When the code moved to InstSimplify, we are calling into ValueTracking directly without passing in the DataLayout*. This patch rectifies the same by passing DataLayout in ComputeNumSignBits. llvm-svn: 213295
2014-07-17Move ashr optimization from InstCombineShift to InstSimplify.Suyog Sarda1-0/+5
Refactor code, no functionality change, test case moved from instcombine to instsimplify. Differential Revision: http://reviews.llvm.org/D4102 llvm-svn: 213231
2014-07-14InstSimplify: Correct sdiv x / -1David Majnemer1-11/+13
Determining the bounds of x/ -1 would start off with us dividing it by INT_MIN. Suffice to say, this would not work very well. Instead, handle it upfront by checking for -1 and mapping it to the range: [INT_MIN + 1, INT_MAX. This means that the result of our division can be any value other than INT_MIN. llvm-svn: 212981
2014-07-14InstSimplify: The upper bound of X / C was missing a rounding stepDavid Majnemer1-1/+9
Summary: When calculating the upper bound of X / -8589934592, we would perform the following calculation: Floor[INT_MAX / 8589934592] However, flooring the result would make us wrongly come to the conclusion that 1073741824 was not in the set of possible values. Instead, use the ceiling of the result. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4502 llvm-svn: 212976
2014-07-04InstSimplify: Fix a bug when INT_MIN is in a sdivDavid Majnemer1-3/+9
When INT_MIN is the numerator in a sdiv, we would not properly handle overflow when calculating the bounds of possible values; abs(INT_MIN) is not a meaningful number. Instead, check and handle INT_MIN by reasoning that the largest value is INT_MIN/-2 and the smallest value is INT_MIN. This fixes PR20199. llvm-svn: 212307
2014-06-26This patch removed duplicate code for matching patterns Dinesh Dwivedi1-106/+1
which are now handled in SimplifyUsingDistributiveLaws() (after r211261) Differential Revision: http://reviews.llvm.org/D4253 llvm-svn: 211768
2014-06-19Move optimization of some cases of (A & C1)|(B & C2) from instcombine to ↵Nick Lewycky1-0/+32
instsimplify. Patch by Rahul Jain, plus some last minute changes by me -- you can blame me for any bugs. llvm-svn: 211252
2014-06-19Make instsimplify's analysis of icmp eq/ne use computeKnownBits to determine ↵Nick Lewycky1-0/+19
whether the icmp is always true or false. Patch by Suyog Sarda! llvm-svn: 211251
2014-05-16InstSimplify: Improve handling of ashr/lshrDavid Majnemer1-1/+21
Summary: Analyze the range of values produced by ashr/lshr cst, %V when it is being used in an icmp. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3774 llvm-svn: 209000
2014-05-16InstSimplify: Optimize using dividend in sdivDavid Majnemer1-0/+4
Summary: The dividend in an sdiv tells us the largest and smallest possible results. Use this fact to optimize comparisons against an sdiv with a constant dividend. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3795 llvm-svn: 208999
2014-05-14InstSimplify: Optimize signed icmp of -(zext V)David Majnemer1-0/+22
Summary: We know that -(zext V) will always be <= zero, simplify signed icmps that have these. Uncovered using http://www.cs.utah.edu/~regehr/souper/ Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3754 llvm-svn: 208809
2014-04-22[Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth1-1/+2
definition below all the header #include lines, lib/Analysis/... edition. This one has a bit extra as there were *other* #define's before #include lines in addition to DEBUG_TYPE. I've sunk all of them as a block. llvm-svn: 206843
2014-04-15[C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper1-76/+76
instead of comparing to nullptr. llvm-svn: 206243
generated by cgit v1.1 at 2025-10-17 11:00:06 +0000