summaryrefslogtreecommitdiff
path: root/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
Commit message (Collapse)AuthorAge
* InstCombine: Stop two transforms duelingDavid Majnemer2014-06-19
| | | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211258 91177308-0d34-0410-b5e6-96231b3b80d8
* Optimize integral reciprocal (udiv 1, x and sdiv 1, x) to not use division. ↵Nick Lewycky2014-05-14
| | | | | | This fires exactly once in a clang bootstrap, but covers a few different results from http://www.cs.utah.edu/~regehr/souper/ git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208750 91177308-0d34-0410-b5e6-96231b3b80d8
* Reorder shuffle and binary operation.Serge Pavlov2014-05-11
| | | | | | | | | | | | | | 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208488 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207196 91177308-0d34-0410-b5e6-96231b3b80d8
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-22
| | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206844 91177308-0d34-0410-b5e6-96231b3b80d8
* [Modules] Sink all the DEBUG_TYPE defines for InstCombine out of theChandler Carruth2014-04-21
| | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206777 91177308-0d34-0410-b5e6-96231b3b80d8
* [Modules] Move the LLVM IR pattern match header into the IR library, itChandler Carruth2014-03-04
| | | | | | obviously is coupled to the IR. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202818 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename many DataLayout variables from TD to DL.Rafael Espindola2014-02-21
| | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@201827 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix all the remaining lost-fast-math-flags bugs I've been able to find. The ↵Owen Anderson2014-01-20
| | | | | | | | | most important of these are cases in the generic logic for combining BinaryOperators. This logic hadn't been updated to handle FastMathFlags, and it took me a while to detect it because it doesn't show up in a simple search for CreateFAdd. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@199629 91177308-0d34-0410-b5e6-96231b3b80d8
* InstCombine: Teach most integer add/sub/mul/div combines how to deal with ↵Benjamin Kramer2014-01-19
| | | | | | vectors. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@199602 91177308-0d34-0410-b5e6-96231b3b80d8
* InstCombine: Refactor fmul/fdiv combines to handle vectors.Benjamin Kramer2014-01-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@199598 91177308-0d34-0410-b5e6-96231b3b80d8
* InstCombine: Make the (fmul X, -1.0) -> (fsub -0.0, X) transform handle ↵Benjamin Kramer2014-01-18
| | | | | | | | vectors too. PR18532. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@199553 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix an instance where we would drop fast math flags when performing an fdiv ↵Owen Anderson2014-01-16
| | | | | | to reciprocal multiply transformation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@199425 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a bug in InstCombine where we failed to preserve fast math flags when ↵Owen Anderson2014-01-16
| | | | | | optimizing an FMUL expression. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@199424 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach InstCombine that (fmul X, -1.0) can be simplified to (fneg X), which ↵Owen Anderson2014-01-16
| | | | | | LLVM expresses as (fsub -0.0, X). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@199420 91177308-0d34-0410-b5e6-96231b3b80d8
* InstCombine: Replace manual fast math flag copying with the new IRBuilder ↵Benjamin Kramer2013-09-30
| | | | | | | | | RAII helper. Defines away the issue where cast<Instruction> would fail because constant folding happened. Also slightly cleaner. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191674 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a bug in InstCombine where it attempted to cast a Value* to an Instruction*Joey Gouly2013-09-30
| | | | | | | | | | when it was actually a Constant*. There are quite a few other casts to Instruction that might have the same problem, but this is the only one I have a test case for. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191668 91177308-0d34-0410-b5e6-96231b3b80d8
* [Fast-math] Disable "(C1/X)*C2 => (C1*C2)/X" if C1/X has multiple uses.Shuxin Yang2013-09-19
| | | | | | | | | | | | | | | | | | | If "C1/X" were having multiple uses, the only benefit of this transformation is to potentially shorten critical path. But it is at the cost of instroducing additional div. The additional div may or may not incur cost depending on how div is implemented. If it is implemented using Newton–Raphson iteration, it dosen't seem to incur any cost (FIXME). However, if the div blocks the entire pipeline, that sounds to be pretty expensive. Let CodeGen to take care this transformation. This patch sees 6% on a benchmark. rdar://15032743 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191037 91177308-0d34-0410-b5e6-96231b3b80d8
* Correct case of m_UIToFp to m_UIToFP to match instruction name, add m_SIToFP ↵Stephen Lin2013-07-26
| | | | | | for consistency. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187225 91177308-0d34-0410-b5e6-96231b3b80d8
* InstCombine: call FoldOpIntoSelect for all floating binops, not just fmulStephen Lin2013-07-20
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186759 91177308-0d34-0410-b5e6-96231b3b80d8
* Restore r181216, which was partially reverted in r182499.Stephen Lin2013-07-17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186533 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a microoptimization for urem.Nick Lewycky2013-07-13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186235 91177308-0d34-0410-b5e6-96231b3b80d8
* InstCombine: Reimplementation of visitUDivOperandDavid Majnemer2013-07-04
| | | | | | | | | | | | This transform was originally added in r185257 but later removed in r185415. The original transform would create instructions speculatively and then discard them if the speculation was proved incorrect. This has been replaced with a scheme that splits the transform into two parts: preflight and fold. While we preflight, we build up fold actions that inform the folding stage on how to act. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185667 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert r185257 (InstCombine: Be more agressive optimizing 'udiv' instrs with ↵Hal Finkel2013-07-02
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 'select' denoms) I'm reverting this commit because: 1. As discussed during review, it needs to be rewritten (to avoid creating and then deleting instructions). 2. This is causing optimizer crashes. Specifically, I'm seeing things like this: While deleting: i1 % Use still stuck around after Def is destroyed: <badref> = select i1 <badref>, i32 0, i32 1 opt: /src/llvm-trunk/lib/IR/Value.cpp:79: virtual llvm::Value::~Value(): Assertion `use_empty() && "Uses remain when a value is destroyed!"' failed. I'd guess that these will go away once we're no longer creating/deleting instructions here, but just in case, I'm adding a regression test. Because the code is bring rewritten, I've just XFAIL'd the original regression test. Original commit message: InstCombine: Be more agressive optimizing 'udiv' instrs with 'select' denoms Real world code sometimes has the denominator of a 'udiv' be a 'select'. LLVM can handle such cases but only when the 'select' operands are symmetric in structure (both select operands are a constant power of two or a left shift, etc.). This falls apart if we are dealt a 'udiv' where the code is not symetric or if the select operands lead us to more select instructions. Instead, we should treat the LHS and each select operand as a distinct divide operation and try to optimize them independently. If we can to simplify each operation, then we can replace the 'udiv' with, say, a 'lshr' that has a new select with a bunch of new operands for the select. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185415 91177308-0d34-0410-b5e6-96231b3b80d8
* InstCombine: Be more agressive optimizing 'udiv' instrs with 'select' denomsDavid Majnemer2013-06-29
| | | | | | | | | | | | | | | | | | Real world code sometimes has the denominator of a 'udiv' be a 'select'. LLVM can handle such cases but only when the 'select' operands are symmetric in structure (both select operands are a constant power of two or a left shift, etc.). This falls apart if we are dealt a 'udiv' where the code is not symetric or if the select operands lead us to more select instructions. Instead, we should treat the LHS and each select operand as a distinct divide operation and try to optimize them independently. If we can to simplify each operation, then we can replace the 'udiv' with, say, a 'lshr' that has a new select with a bunch of new operands for the select. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185257 91177308-0d34-0410-b5e6-96231b3b80d8
* In InstCombine{AddSub,MulDivRem} convert APFloat.isFiniteNonZero() && ↵Michael Gottesman2013-06-26
| | | | | | !APFloat.isDenormal => APFloat.isNormal. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185037 91177308-0d34-0410-b5e6-96231b3b80d8
* [APFloat] Converted all references to APFloat::isNormal => ↵Michael Gottesman2013-06-19
| | | | | | | | APFloat::isFiniteNonZero. Turns out all the references were in llvm and not in clang. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@184356 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify code. No functionality change.Jakub Staszak2013-06-06
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@183461 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify multiplications by vectors whose elements are powers of 2.Rafael Espindola2013-05-31
| | | | | | Patch by Andrea Di Biagio. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@183005 91177308-0d34-0410-b5e6-96231b3b80d8
* This is an update to a previous commit (r181216).Jean-Luc Duprat2013-05-22
| | | | | | | | | | | | | | | | | | | | | | | | | | The earlier change list introduced the following inst combines: B * (uitofp i1 C) —> select C, B, 0 A * (1 - uitofp i1 C) —> select C, 0, A select C, 0, B + select C, A, 0 —> select C, A, B Together these 3 changes would simplify : A * (1 - uitofp i1 C) + B * uitofp i1 C down to : select C, B, A In practice we found that the first two substitutions can have a negative effect on performance, because they reduce opportunities to use FMA contractions; between the two options FMAs are often the better choice. This change list amends the previous one to enable just these inst combines: select C, B, 0 + select C, 0, A —> select C, B, A A * (1 - uitofp i1 C) + B * uitofp i1 C —> select C, B, A git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@182499 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix two typoSylvestre Ledru2013-05-14
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181848 91177308-0d34-0410-b5e6-96231b3b80d8
* InstCombine: Flip the order of two urem transformsDavid Majnemer2013-05-12
| | | | | | | | | | | | | | | There are two transforms in visitUrem that conflict with each other. *) One, if a divisor is a power of two, subtracts one from the divisor and turns it into a bitwise-and. *) The other unwraps both operands if they are surrounded by zext instructions. Flipping the order allows the subtraction to go beneath the sign extension. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181668 91177308-0d34-0410-b5e6-96231b3b80d8
* InstCombine: Turn urem to bitwise-and more oftenDavid Majnemer2013-05-11
| | | | | | | | Use isKnownToBeAPowerOfTwo in visitUrem so that we may more aggressively fold away urem instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181661 91177308-0d34-0410-b5e6-96231b3b80d8
* InstCombine: Verify the type before transforming uitofp into select.Benjamin Kramer2013-05-10
| | | | | | PR15952. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181586 91177308-0d34-0410-b5e6-96231b3b80d8
* Provide InstCombines for the following 3 cases:Jean-Luc Duprat2013-05-06
| | | | | | | | | | | | | | | A * (1 - (uitofp i1 C)) -> select C, 0, A B * (uitofp i1 C) -> select C, B, 0 select C, 0, A + select C, B, 0 -> select C, B, A These come up in code that has been hand-optimized from a select to a linear blend, on platforms where that may have mattered. We want to undo such changes with the following transform: A*(1 - uitofp i1 C) + B*(uitofp i1 C) -> select C, A, B git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181216 91177308-0d34-0410-b5e6-96231b3b80d8
* Tidy up a bit. No functional change.Jim Grosbach2013-04-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@178915 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a bug in instcombine for fmul in fast math mode.Quentin Colombet2013-02-28
| | | | | | | | | | | | | | | | | 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
* 1. Hoist minus sign as high as possible in an attempt to revealShuxin Yang2013-01-15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* This change is to implement following rules under the condition C_A and/or C_RShuxin Yang2013-01-14
| | | | | | | | | | | | | | | | | | | | | | --------------------------------------------------------------------------- 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
* Cosmetical changne in order to conform to coding std.Shuxin Yang2013-01-07
| | | | | | | 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
* This change is to implement following rules:Shuxin Yang2013-01-07
| | | | | | | | | | | | 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
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-02
| | | | | | | | | | | | | | | | | | | | | 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
* rdar://12753946Shuxin Yang2012-12-14
| | | | | | | 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
* Rename isPowerOfTwo to isKnownToBeAPowerOfTwo.Rafael Espindola2012-12-13
| | | | | | | | 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
* The TargetData is not used for the isPowerOfTwo determination. It has neverRafael Espindola2012-12-12
| | | | | | | | | | 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
* Remove redunant optimizations from InstCombine, instead call the appropriate ↵Michael Ilseman2012-12-12
| | | | | | functions from SimplifyInstruction git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169941 91177308-0d34-0410-b5e6-96231b3b80d8
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-03
| | | | | | | | | | | | | | | | | 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
* reversed the logic of the log2 detection routine to reduce the number of ↵Pedro Artigas2012-11-30
| | | | | | nested ifs git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169049 91177308-0d34-0410-b5e6-96231b3b80d8
* Addresses many style issues with prior checkin (r169025)Pedro Artigas2012-11-30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169043 91177308-0d34-0410-b5e6-96231b3b80d8
* Add fast math inst combine X*log2(Y*0.5)-->X*log2(Y)-XPedro Artigas2012-11-30
| | | | | | | | reviewed by Michael Ilseman <milseman@apple.com> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169025 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-15 02:47:27 +0000