summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Remove uses of builtin comma operator.Richard Trieu2016-02-181-4/+7
| | | | | | Cleanup for upcoming Clang warning -Wcomma. No functionality change intended. llvm-svn: 261270
* function names start with a lowercase letter; NFCSanjay Patel2016-02-011-25/+25
| | | | llvm-svn: 259425
* InstCombine: fabs(x) * fabs(x) -> x * xMatt Arsenault2016-01-301-4/+15
| | | | llvm-svn: 259295
* function names start with a lower case letter ; NFCSanjay Patel2016-01-121-3/+3
| | | | llvm-svn: 257496
* InstCombine: Remove ilist iterator implicit conversions, NFCDuncan P. N. Exon Smith2015-10-131-3/+3
| | | | | | | Stop relying on implicit conversions of ilist iterators in LLVMInstCombine. No functionality change intended. llvm-svn: 250183
* don't repeat function names in comments; NFCSanjay Patel2015-09-091-7/+5
| | | | llvm-svn: 247154
* [InstCombine] Don't divide by zero when evaluating a potential transformDavid Majnemer2015-09-061-0/+8
| | | | | | | | | | Trivial multiplication by zero may survive the worklist. We tried to reassociate the multiplication with a division instruction, causing us to divide by zero; bail out instead. This fixes PR24726. llvm-svn: 246939
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-1/+1
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-1/+1
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* [InstCombine] (mul nsw 1, INT_MIN) != (shl nsw 1, 31)David Majnemer2015-04-181-2/+6
| | | | | | | Multiplying INT_MIN by 1 doesn't trigger nsw. However, shifting 1 into the sign bit *does* trigger nsw. llvm-svn: 235250
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-13/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [InstCombine] Fix an assertion when fmul has a ConstantExpr operandMichael Kuperstein2015-03-051-2/+2
| | | | | | | | | isNormalFp and isFiniteNonZeroFp should not assume vector operands can not be constant expressions. Patch by Pawel Jurek <pawel.jurek@intel.com> Differential Revision: http://reviews.llvm.org/D8053 llvm-svn: 231359
* InstSimplify: simplify 0 / X if nnan and nszMehdi Amini2015-02-231-2/+4
| | | | | From: Fiona Glaser <fglaser@apple.com> llvm-svn: 230238
* [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-15/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: match can find ConstantExprs, don't assume we have a ValueDavid Majnemer2015-01-041-2/+2
| | | | | | | | | | We assumed the output of a match was a Value, this would cause us to assert because we would fail a cast<>. Instead, use a helper in the Operator family to hide the distinction between Value and Constant. This fixes PR22087. llvm-svn: 225127
* Analysis: Reformulate WillNotOverflowUnsignedMul for reusabilityDavid Majnemer2015-01-021-34/+3
| | | | | | | | WillNotOverflowUnsignedMul's smarts will live in ValueTracking as computeOverflowForUnsignedMul. It now returns a tri-state result: never overflows, always overflows and sometimes overflows. llvm-svn: 225076
* InstCombine: Infer nuw for multipliesDavid Majnemer2014-12-261-0/+38
| | | | | | | A multiply cannot unsigned wrap if there are bitwidth, or more, leading zero bits between the two operands. llvm-svn: 224849
* InstCombe: Infer nsw for multipliesDavid Majnemer2014-12-261-0/+47
| | | | | | | We already utilize this logic for reducing overflow intrinsics, it makes sense to reuse it for normal multiplies as well. llvm-svn: 224847
* InstCombine: Don't create an unused instructionDavid Majnemer2014-11-241-2/+1
| | | | | | | | | | We would create an instruction but not inserting it. Not inserting the unused instruction would lead us to verification failure. This fixes PR21653. llvm-svn: 222659
* InstCombine: Propagate exact for (sdiv X, Pow2) -> (udiv X, Pow2)David Majnemer2014-11-221-2/+4
| | | | llvm-svn: 222625
* InstCombine: Propagate exact for (sdiv X, Y) -> (udiv X, Y)David Majnemer2014-11-221-1/+3
| | | | llvm-svn: 222624
* InstCombine: Propagate exact for (sdiv -X, C) -> (sdiv X, -C)David Majnemer2014-11-221-4/+6
| | | | llvm-svn: 222623
* InstCombine: Propagate exact in (udiv (lshr X,C1),C2) -> (udiv x,C1<<C2)David Majnemer2014-11-221-2/+7
| | | | llvm-svn: 222620
* InstCombine: Propagate NSW/NUW for X*(1<<Y) -> X<<YDavid Majnemer2014-11-221-4/+17
| | | | llvm-svn: 222613
* InstCombine: Propagate NSW for -X * -Y -> X * YDavid Majnemer2014-11-221-3/+10
| | | | llvm-svn: 222612
* InstCombine: Preserve nsw when folding X*(2^C) -> X << CDavid Majnemer2014-11-221-0/+2
| | | | llvm-svn: 222606
* InstCombine: Preserve nsw/nuw for ((X << C2)*C1) -> (X * (C1 << C2))David Majnemer2014-11-221-3/+12
| | | | llvm-svn: 222605
* InstCombine: Preserve nsw for (mul %V, -1) -> (sub 0, %V)David Majnemer2014-11-221-2/+7
| | | | llvm-svn: 222604
* InstCombine: Don't miscompile X % ((Pow2 << A) >>u B)David Majnemer2014-10-141-7/+4
| | | | | | | | | | | | | | | | | | | We assumed that A must be greater than B because the right hand side of a remainder operator must be nonzero. However, it is possible for A to be less than B if Pow2 is a power of two greater than 1. Take for example: i32 %A = 0 i32 %B = 31 i32 Pow2 = 2147483648 ((Pow2 << 0) >>u 31) is non-zero but A is less than B. This fixes PR21274. llvm-svn: 219713
* fix formatting; NFCSanjay Patel2014-10-141-33/+25
| | | | llvm-svn: 219645
* InstCombine: Fix miscompile in X % -Y -> X % Y transformDavid Majnemer2014-10-131-6/+6
| | | | | | | | | | | We assumed that negation operations of the form (0 - %Z) resulted in a negative number. This isn't true if %Z was originally negative. Substituting the negative number into the remainder operation may result in undefined behavior because the dividend might be INT_MIN. This fixes PR21256. llvm-svn: 219639
* InstCombine: Don't miscompile (x lshr C1) udiv C2David Majnemer2014-10-131-4/+10
| | | | | | | | | | | | | We have a transform that changes: (x lshr C1) udiv C2 into: x udiv (C2 << C1) However, it is unsafe to do so if C2 << C1 discards any of C2's bits. This fixes PR21255. llvm-svn: 219634
* InstCombine: Simplify commonIDivTransformsDavid Majnemer2014-10-121-86/+76
| | | | | | | | | | A helper routine, MultiplyOverflows, was a less efficient reimplementation of APInt's smul_ov and umul_ov. While we are here, clean up the code so it's more uniform. No functionality change intended. llvm-svn: 219583
* InstCombine: Don't fold (X <<s log(INT_MIN)) /s INT_MIN to XDavid Majnemer2014-10-111-1/+2
| | | | | | | | | | Consider the case where X is 2. (2 <<s 31)/s-2147483648 is zero but we would fold to X. Note that this is valid when we are in the unsigned domain because we require NUW: 2 <<u 31 results in poison. This fixes PR21245. llvm-svn: 219568
* InstCombine, InstSimplify: (%X /s C1) /s C2 isn't always 0 when C1 * C2 overflowDavid Majnemer2014-10-111-5/+4
| | | | | | | | | | | | | | | | | | 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
* InstCombine: mul to shl shouldn't preserve nswDavid Majnemer2014-10-111-2/+0
| | | | | | | | | | | | | | | | | consider: mul i32 nsw %x, -2147483648 this instruction will not result in poison if %x is 1 however, if we transform this into: shl i32 nsw %x, 31 then we will be generating poison because we just shifted into the sign bit. This fixes PR21242. llvm-svn: 219566
* Reformat if statement to comply with LLVM standards. NFC.Suyog Sarda2014-10-071-2/+4
| | | | | | Differential Revision: http://reviews.llvm.org/D5644 llvm-svn: 219203
* Reformat to comply with LLVM coding standards using clang-format.Suyog Sarda2014-10-071-5/+4
| | | | | | | | NFC. Differential Revision: http://reviews.llvm.org/D5645 llvm-svn: 219202
* [InstCombine] Reformat if statements to comply with LLVM Coding Standards.Tilmann Scheller2014-10-071-2/+6
| | | | | | | | Patch by Sonam Kumari! Differential Revision: http://reviews.llvm.org/D5643 llvm-svn: 219198
* Optimize square root squared (PR21126).Sanjay Patel2014-10-021-0/+5
| | | | | | | | | | | When unsafe-fp-math is enabled, we can turn sqrt(X) * sqrt(X) into X. This can happen in the real world when calculating x ** 3/2. This occurs in test-suite/SingleSource/Benchmarks/BenchmarkGame/n-body.c. Differential Revision: http://reviews.llvm.org/D5584 llvm-svn: 218906
* Use the local variable that other clauses around here are already using.Sanjay Patel2014-10-021-1/+1
| | | | llvm-svn: 218876
* Make use of @llvm.assume in ValueTracking (computeKnownBits, etc.)Hal Finkel2014-09-071-20/+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
* InstCombine: Respect recursion depth in visitUDivOperandDavid Majnemer2014-08-301-4/+4
| | | | llvm-svn: 216817
* Remove an InstCombine that transformed patterns like (x * uitofp i1 y) to ↵Owen Anderson2014-08-171-30/+0
| | | | | | | | | | | | | (select y, x, 0.0) when the multiply has fast math flags set. While this might seem like an obvious canonicalization, there is one subtle problem with it. The result of the original expression is undef when x is NaN (remember, fast math flags), but the result of the select is always defined when x is NaN. This means that the new expression is strictly more defined than the original one. One unfortunate consequence of this is that the transform is not reversible! It's always legal to make increase the defined-ness of an expression, but it's not legal to reduce it. Thus, targets that prefer the original form of the expression cannot reverse the transform to recover it. Another way to think of it is that the transform has lost source-level information (the fast math flags), which is undesirable. llvm-svn: 215825
* InstCombine: Combine mul with div.David Majnemer2014-08-161-2/+75
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | We can combne a mul with a div if one of the operands is a multiple of the other: %mul = mul nsw nuw %a, C1 %ret = udiv %mul, C2 => %ret = mul nsw %a, (C1 / C2) This can expose further optimization opportunities if we end up multiplying or dividing by a power of 2. Consider this small example: define i32 @f(i32 %a) { %mul = mul nuw i32 %a, 14 %div = udiv exact i32 %mul, 7 ret i32 %div } which gets CodeGen'd to: imull $14, %edi, %eax imulq $613566757, %rax, %rcx shrq $32, %rcx subl %ecx, %eax shrl %eax addl %ecx, %eax shrl $2, %eax retq We can now transform this into: define i32 @f(i32 %a) { %shl = shl nuw i32 %a, 1 ret i32 %shl } which gets CodeGen'd to: leal (%rdi,%rdi), %eax retq This fixes PR20681. llvm-svn: 215815
* InstCombine: Optimize x/INT_MIN to x==INT_MINDavid Majnemer2014-07-021-0/+4
| | | | | | | The result of x/INT_MIN is either 0 or 1, we can just use an icmp instead. llvm-svn: 212167
* InstCombine: Stop two transforms duelingDavid Majnemer2014-06-191-2/+5
| | | | | | | | | | | | | | | | | | | | | | InstCombineMulDivRem has: // Canonicalize (X+C1)*CI -> X*CI+C1*CI. InstCombineAddSub has: // W*X + Y*Z --> W * (X+Z) iff W == Y These two transforms could fight with each other if C1*CI would not fold away to something simpler than a ConstantExpr mul. The InstCombineMulDivRem transform only acted on ConstantInts until r199602 when it was changed to operate on all Constants in order to let it fire on ConstantVectors. To fix this, make this transform more careful by checking to see if we actually folded away C1*CI. This fixes PR20079. llvm-svn: 211258
* Optimize integral reciprocal (udiv 1, x and sdiv 1, x) to not use division. ↵Nick Lewycky2014-05-141-1/+20
| | | | | | This fires exactly once in a clang bootstrap, but covers a few different results from http://www.cs.utah.edu/~regehr/souper/ llvm-svn: 208750
* Reorder shuffle and binary operation.Serge Pavlov2014-05-111-0/+24
| | | | | | | | | | | | | 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
OpenPOWER on IntegriCloud