aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
AgeCommit message (Collapse)Author
2013-02-28Fix a bug in instcombine for fmul in fast math mode.Quentin Colombet
The instcombine recognized pattern looks like: a = b * c d = a +/- Cst or a = b * c d = Cst +/- a When creating the new operands for fadd or fsub instruction following the related fmul, the first operand was created with the second original operand (M0 was created with C1) and the second with the first (M1 with Opnd0). The fix consists in creating the new operands with the appropriate original operand, i.e., M0 with Opnd0 and M1 with C1. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176300 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-151. Hoist minus sign as high as possible in an attempt to revealShuxin Yang
some optimization opportunities (in the enclosing supper-expressions). rule 1. (-0.0 - X ) * Y => -0.0 - (X * Y) if expression "-0.0 - X" has only one reference. rule 2. (0.0 - X ) * Y => -0.0 - (X * Y) if expression "0.0 - X" has only one reference, and the instruction is marked "noSignedZero". 2. Eliminate negation (The compiler was already able to handle these opt if the 0.0s are replaced with -0.0.) rule 3: (0.0 - X) * (0.0 - Y) => X * Y rule 4: (0.0 - X) * C => X * -C if the expr is flagged "noSignedZero". 3. Rule 5: (X*Y) * X => (X*X) * Y if X!=Y and the expression is flagged with "UnsafeAlgebra". The purpose of this transformation is two-fold: a) to form a power expression (of X). b) potentially shorten the critical path: After transformation, the latency of the instruction Y is amortized by the expression of X*X, and therefore Y is in a "less critical" position compared to what it was before the transformation. 4. Remove the InstCombine code about simplifiying "X * select". The reasons are following: a) The "select" is somewhat architecture-dependent, therefore the higher level optimizers are not able to precisely predict if the simplification really yields any performance improvement or not. b) The "select" operator is bit complicate, and tends to obscure optimization opportunities. It is btter to keep it as low as possible in expr tree, and let CodeGen to tackle the optimization. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172551 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-14This change is to implement following rules under the condition C_A and/or C_RShuxin Yang
--------------------------------------------------------------------------- C_A: reassociation is allowed C_R: reciprocal of a constant C is appropriate, which means - 1/C is exact, or - reciprocal is allowed and 1/C is neither a special value nor a denormal. ----------------------------------------------------------------------------- rule1: (X/C1) / C2 => X / (C2*C1) (if C_A) => X * (1/(C2*C1)) (if C_A && C_R) rule 2: X*C1 / C2 => X * (C1/C2) if C_A rule 3: (X/Y)/Z = > X/(Y*Z) (if C_A && at least one of Y and Z is symbolic value) rule 4: Z/(X/Y) = > (Z*Y)/X (similar to rule3) rule 5: C1/(X*C2) => (C1/C2) / X (if C_A) rule 6: C1/(X/C2) => (C1*C2) / X (if C_A) rule 7: C1/(C2/X) => (C1/C2) * X (if C_A) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172488 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-07Cosmetical changne in order to conform to coding std.Shuxin Yang
Thank Eric Christopher for figuring out these problems! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171805 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-07This change is to implement following rules:Shuxin Yang
o. X/C1 * C2 => X * (C2/C1) (if C2/C1 is neither special FP nor denormal) o. X/C1 * C2 -> X/(C1/C2) (if C2/C1 is either specical FP or denormal, but C1/C2 is a normal Fp) Let MDC denote multiplication or dividion with one & only one operand being a constant o. (MDC ± C1) * C2 => (MDC * C2) ± (C1 * C2) (so long as the constant-folding doesn't yield any denormal or special value) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171793 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-02Move all of the header files which are involved in modelling the LLVM IRChandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171366 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-14rdar://12753946Shuxin Yang
Implement rule : "x * (select cond 1.0, 0.0) -> select cond x, 0.0" git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@170226 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-13Rename isPowerOfTwo to isKnownToBeAPowerOfTwo.Rafael Espindola
In a previous thread it was pointed out that isPowerOfTwo is not a very precise name since it can return false for powers of two if it is unable to show that they are powers of two. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@170093 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-12The TargetData is not used for the isPowerOfTwo determination. It has neverRafael Espindola
been used in the first place. It simply was passed to the function and to the recursive invocations. Simply drop the parameter and update the callers for the new signature. Patch by Saleem Abdulrasool! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169988 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-12Remove redunant optimizations from InstCombine, instead call the appropriate ↵Michael Ilseman
functions from SimplifyInstruction git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169941 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-03Use the new script to sort the includes of every file under lib.Chandler Carruth
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. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-30reversed the logic of the log2 detection routine to reduce the number of ↵Pedro Artigas
nested ifs git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169049 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-30Addresses many style issues with prior checkin (r169025)Pedro Artigas
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169043 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-30Add fast math inst combine X*log2(Y*0.5)-->X*log2(Y)-XPedro Artigas
reviewed by Michael Ilseman <milseman@apple.com> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169025 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-08Move TargetData to DataLayout.Micah Villmow
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165402 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-27Revert 'Fix a typo 'iff' => 'if''. iff is an abreviation of if and only if. ↵Sylvestre Ledru
See: http://en.wikipedia.org/wiki/If_and_only_if Commit 164767 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164768 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-27Fix a typo 'iff' => 'if'Sylvestre Ledru
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164767 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-21InstCombine: Make sure we use the pre-zext type when creating a constant of ↵Benjamin Kramer
a value that is zext'd. Fixes PR13250. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164377 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-30InstCombine: Fix comment to reflect the code.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162911 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-30It is illegal to transform (sdiv (ashr X c1) c2) -> (sdiv x (2^c1 * c2)),Nadav Rotem
because C always rounds towards zero. Thanks Dirk and Ben. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162899 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-28InstCombine: Defensively avoid undefined shifts by limiting the amount to ↵Benjamin Kramer
the bit width. No test case, undefined shifts get folded early, but can occur when other transforms generate a constant. Thanks to Duncan for bringing this up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162755 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-28InstCombine: Guard the transform introduced in r162743 against large ints ↵Benjamin Kramer
and non-const shifts. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162751 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-28Make sure that we don't call getZExtValue on values > 64 bits.Nadav Rotem
Thanks Benjamin for noticing this. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162749 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-28Teach InstCombine to canonicalize [SU]div+[AL]shl patterns.Nadav Rotem
For example: %1 = lshr i32 %x, 2 %2 = udiv i32 %1, 100 rdar://12182093 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162743 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-21Look pass zext to strength reduce an udiv. Patch by David Majnemer. ↵Evan Cheng
rdar://11721329 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158946 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-06Remove some dead code and tidy things up now that vectors use ConstantDataVectorChris Lattner
instead of always using ConstantVector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149912 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-27continue making the world safe for ConstantDataVector. At this point,Chris Lattner
we should (theoretically optimize and codegen ConstantDataVector as well as ConstantVector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149116 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-25use ConstantVector::getSplat in a few places.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148929 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-07InstCombine now optimizes vector udiv by power of 2 to shiftsPete Cooper
Fixes r8429 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144036 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-27Stop emitting instructions with the name "tmp" they eat up memory and have ↵Benjamin Kramer
to be uniqued, without any benefit. If someone prefers %tmp42 to %42, run instnamer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140634 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-18land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135375 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-15start using the new helper methods a bit.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135251 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-01Reapply 132348 with fixes. rdar://problem/6501862Stuart Hastings
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132402 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-31Revert to pacify a buildbot. rdar://problem/6501862Stuart Hastings
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132351 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-31Followup to 132316; accept arbitrary constants, add with a constant,Stuart Hastings
sub with a non-constant. Fix comments, enlarge test case. rdar://problem/6501862 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132348 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-30(1 - X) * (-2) -> (x - 1) * 2, for all positive nonzero powers of 2Stuart Hastings
rdar://problem/6501862 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132316 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-23rearrange two transforms, since one subsumes the other. Make the ↵Chris Lattner
shift-exactness xform recurse. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131888 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-23Transform any logical shift of a power of two into an exact/NUW shift whenChris Lattner
in a known-non-zero context. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131887 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-23use the valuetracking isPowerOfTwo function, which is more powerful than ↵Chris Lattner
checking for a constant directly. Thanks to Duncan for pointing this out. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131885 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-22add some random notes.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131862 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-22Carve out a place in instcombine to put transformations which work knowing ↵Chris Lattner
that their result is non-zero. Implement an example optimization (PR9814), which allows us to transform: A / ((1 << B) >>u 2) into: A >>u (B-2) which we compile into: _divu3: ## @divu3 leal -2(%rsi), %ecx shrl %cl, %edi movl %edi, %eax ret instead of: _divu3: ## @divu3 movb %sil, %cl movl $1, %esi shll %cl, %esi shrl $2, %esi movl %edi, %eax xorl %edx, %edx divl %esi, %eax ret git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131860 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-02Remove unused variable.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130705 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-02Move some rem transforms out of instcombine and into instsimplify.Duncan Sands
This automagically provides a transform noticed by my super-optimizer as occurring quite often: "rem x, (select cond, x, 1)" -> 0. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130694 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-30InstCombine: Turn (zext A) udiv (zext B) into (zext (A udiv B)). Same for ↵Benjamin Kramer
urem or constant B. This obviously helps a lot if the division would be turned into a libcall (think i64 udiv on i386), but div is also one of the few remaining instructions on modern CPUs that become more expensive when the bitwidth gets bigger. This also helps register pressure on i386 when dividing chars, divb needs two 8-bit parts of a 16 bit register as input where divl uses two registers. int foo(unsigned char a) { return a/10; } int bar(unsigned char a, unsigned char b) { return a/b; } compiles into (x86_64) _foo: imull $205, %edi, %eax shrl $11, %eax ret _bar: movzbl %dil, %eax divb %sil, %al movzbl %al, %eax ret git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130615 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-30Use SimplifyDemandedBits on div instructions.Benjamin Kramer
This folds away silly stuff like (a&255)/1000 -> 0. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130614 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-30InstCombine: If the divisor of an fdiv has an exact inverse, turn it into an ↵Benjamin Kramer
fmul. Fixes PR9587. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128546 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-10Enhance a bunch of transformations in instcombine to start generatingChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125267 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-06enhance vmcore to know that udiv's can be exact, and add a trivialChris Lattner
instcombine xform to exercise this. Nothing forms exact udivs yet though. This is progress on PR8862 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124992 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-29Call SimplifyFDivInst() in InstCombiner::visitFDiv().Frits van Bommel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124535 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-29Move InstCombine's knowledge of fdiv to SimplifyInstruction().Frits van Bommel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124534 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-29 00:37:46 +0000