summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Check for all known bits on ret in InstCombineHal Finkel2014-09-071-0/+18
| | | | | | | | | | From a combination of @llvm.assume calls (and perhaps through other means, such as range metadata), it is possible that all bits of a return value might be known. Previously, InstCombine did not check for this (which is understandable given assumptions of constant propagation), but means that we'd miss simple cases where assumptions are involved. llvm-svn: 217346
* Make use of @llvm.assume in ValueTracking (computeKnownBits, etc.)Hal Finkel2014-09-071-1/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Add an Assumption-Tracking PassHal Finkel2014-09-071-1/+5
| | | | | | | | | | | | | | | | | | | | | | | | This adds an immutable pass, AssumptionTracker, which keeps a cache of @llvm.assume call instructions within a module. It uses callback value handles to keep stale functions and intrinsics out of the map, and it relies on any code that creates new @llvm.assume calls to notify it of the new instructions. The benefit is that code needing to find @llvm.assume intrinsics can do so directly, without scanning the function, thus allowing the cost of @llvm.assume handling to be negligible when none are present. The current design is intended to be lightweight. We don't keep track of anything until we need a list of assumptions in some function. The first time this happens, we scan the function. After that, we add/remove @llvm.assume calls from the cache in response to registration calls and ValueHandle callbacks. There are no new direct test cases for this pass, but because it calls it validation function upon module finalization, we'll pick up detectable inconsistencies from the other tests that touch @llvm.assume calls. This pass will be used by follow-up commits that make use of @llvm.assume. llvm-svn: 217334
* Revert "Revert two GEP-related InstCombine commits"David Majnemer2014-09-011-11/+42
| | | | | | | | | | | | | | This reverts commit r216698 which reverted r216523 and r216598. We would attempt to perform the transformation even if the match() failed because, as a side effect, it would set V. This would trick us into believing that we correctly found a place to correctly apply the transform. An additional test case was added to getelementptr.ll so that we might not regress in the future. llvm-svn: 216890
* Revert two GEP-related InstCombine commitsDavid Majnemer2014-08-291-40/+11
| | | | | | | This reverts commit r216523 and r216598; people have reported regressions. llvm-svn: 216698
* InstCombine: Combine gep X, (Y-X) to YDavid Majnemer2014-08-271-14/+25
| | | | | | | | We try to perform this transform in InstSimplify but we aren't always able to. Sometimes, we need to insert a bitcast if X and Y don't have the same time. llvm-svn: 216598
* InstCombine: Optimize GEP's involving ptrtoint betterDavid Majnemer2014-08-271-11/+29
| | | | | | | | | | | | | | We supported transforming: (gep i8* X, -(ptrtoint Y)) to: (inttoptr (sub (ptrtoint X), (ptrtoint Y))) However, this only fired if 'X' had type i8*. Generalize this to support various types of different sizes. This results in much better CodeGen, especially for pointers to packed structs. llvm-svn: 216523
* This patch enables SimplifyUsingDistributiveLaws() to handle following pattens.Dinesh Dwivedi2014-08-261-15/+45
| | | | | | | | | | | | (X >> Z) & (Y >> Z) -> (X&Y) >> Z for all shifts. (X >> Z) | (Y >> Z) -> (X|Y) >> Z for all shifts. (X >> Z) ^ (Y >> Z) -> (X^Y) >> Z for all shifts. These patterns were previously handled separately in visitAnd()/visitOr()/visitXor(). Differential Revision: http://reviews.llvm.org/D4951 llvm-svn: 216443
* Repace SmallPtrSet with SmallPtrSetImpl in function arguments to avoid ↵Craig Topper2014-08-211-1/+1
| | | | | | needing to mention the size. llvm-svn: 216158
* Revert "Repace SmallPtrSet with SmallPtrSetImpl in function arguments to ↵Craig Topper2014-08-181-1/+1
| | | | | | | | avoid needing to mention the size." Getting a weird buildbot failure that I need to investigate. llvm-svn: 215870
* Repace SmallPtrSet with SmallPtrSetImpl in function arguments to avoid ↵Craig Topper2014-08-171-1/+1
| | | | | | needing to mention the size. llvm-svn: 215868
* Allwo bitcast + struct GEP transform to work with addrspacecastMatt Arsenault2014-08-121-3/+20
| | | | llvm-svn: 215467
* Revert "[C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) ↵Duncan P. N. Exon Smith2014-07-211-2/+2
| | | | | | | | | iterator ranges." This reverts commit r213474 (and r213475), which causes a miscompile on a stage2 LTO build. I'll reply on the list in a moment. llvm-svn: 213562
* [C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) iterator ↵Manuel Jacob2014-07-201-2/+2
| | | | | | | | | | | | | | | | | | ranges. Summary: This patch introduces two new iterator ranges and updates existing code to use it. No functional change intended. Test Plan: All tests (make check-all) still pass. Reviewers: dblaikie Reviewed By: dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4481 llvm-svn: 213474
* Utilize CastInst::CreatePointerBitCastOrAddrSpaceCast here.Manuel Jacob2014-07-161-9/+6
| | | | llvm-svn: 213189
* When we sink an instruction, this can open up opportunity for the operands ↵Aditya Nandakumar2014-07-111-2/+11
| | | | | | to be sunk - add them to the worklist llvm-svn: 212847
* InstCombine: Fix a crash in Descale for multiply-by-zeroDuncan P. N. Exon Smith2014-07-101-0/+6
| | | | | | | | | | Fix a crash in `InstCombiner::Descale()` when a multiply-by-zero gets created as an argument to a GEP partway through an iteration, causing -instcombine to optimize the GEP before the multiply. rdar://problem/17615671 llvm-svn: 212742
* Feeding isSafeToSpeculativelyExecute its DataLayout pointerHal Finkel2014-07-101-1/+1
| | | | | | | | | | | | | | isSafeToSpeculativelyExecute can optionally take a DataLayout pointer. In the past, this was mainly used to make better decisions regarding divisions known not to trap, and so was not all that important for users concerned with "cheap" instructions. However, now it also helps look through bitcasts for dereferencable loads, and will also be important if/when we add a dereferencable pointer attribute. This is some initial work to feed a DataLayout pointer through to callers of isSafeToSpeculativelyExecute, generally where one was already available. llvm-svn: 212720
* Fix for PR20059 (instcombine reorders shufflevector after instruction that ↵Sanjay Patel2014-07-091-0/+6
| | | | | | | | | | | | may trap) In PR20059 ( http://llvm.org/pr20059 ), instcombine eliminates shuffles that are necessary before performing an operation that can trap (srem). This patch calls isSafeToSpeculativelyExecute() and bails out of the optimization in SimplifyVectorOp() if needed. Differential Revision: http://reviews.llvm.org/D4424 llvm-svn: 212629
* Make helper functions static.Benjamin Kramer2014-07-071-2/+2
| | | | llvm-svn: 212460
* InstCombine: Don't try to reorder shuffles where the mask is a ConstantExpr.Benjamin Kramer2014-06-241-1/+3
| | | | | | We can't analyze the individual values of a vector expression. PR20114. llvm-svn: 211581
* Refactored and updated SimplifyUsingDistributiveLaws() to Dinesh Dwivedi2014-06-191-53/+142
| | | | | | | | | | | | * Find factorization opportunities using identity values. * Find factorization opportunities by treating shl(X, C) as mul (X, shl(C)) * Keep NSW flag while simplifying instruction using factorization. This fixes PR19263. Differential Revision: http://reviews.llvm.org/D3799 llvm-svn: 211261
* Add a Constant version of stripPointerCasts.Rafael Espindola2014-06-041-3/+3
| | | | | | Thanks to rnk for the suggestion. llvm-svn: 210205
* Clauses in a landingpad are always Constant. Use a stricter type.Rafael Espindola2014-06-041-4/+4
| | | | llvm-svn: 210203
* And fix my fix to sink down through the type at the right time. MyChandler Carruth2014-05-291-8/+9
| | | | | | | | | original fix would actually trigger the *exact* same crasher as the original bug for a different reason. Awesomesauce. Working on test cases now, but wanted to get bots healthier. llvm-svn: 209860
* Fix one bug in the latest incarnation of r209843 -- combining GEPsChandler Carruth2014-05-291-8/+13
| | | | | | | | | | across PHI nodes. The code was computing the Idxs from the 'GEP' variable's indices when what it wanted was Op1's indices. This caused an ASan heap-overflow for me that pin pointed the issue when Op1 had more indices than GEP did. =] I'll let Louis add a specific test case for this if he wants. llvm-svn: 209857
* Add support for combining GEPs across PHI nodesLouis Gerbarg2014-05-291-0/+79
| | | | | | | | | | | | | | | | | | | | | | | | Currently LLVM will generally merge GEPs. This allows backends to use more complex addressing modes. In some cases this is not happening because there is PHI inbetween the two GEPs: GEP1--\ |-->PHI1-->GEP3 GEP2--/ This patch checks to see if GEP1 and GEP2 are similiar enough that they can be cloned (GEP12) in GEP3's BB, allowing GEP->GEP merging (GEP123): GEP1--\ --\ --\ |-->PHI1-->GEP3 ==> |-->PHI2->GEP12->GEP3 == > |-->PHI2->GEP123 GEP2--/ --/ --/ This also breaks certain use chains that are preventing GEP->GEP merges that the the existing instcombine would merge otherwise. Tests included. llvm-svn: 209843
* Revert "Add support for combining GEPs across PHI nodes"Rafael Espindola2014-05-281-79/+0
| | | | | | | | This reverts commit r209755. it was the real cause of the libc++ build failure. llvm-svn: 209775
* Add support for combining GEPs across PHI nodesLouis Gerbarg2014-05-281-0/+79
| | | | | | | | | | | | | | | | | | | | | | | | Currently LLVM will generally merge GEPs. This allows backends to use more complex addressing modes. In some cases this is not happening because there is PHI inbetween the two GEPs: GEP1--\ |-->PHI1-->GEP3 GEP2--/ This patch checks to see if GEP1 and GEP2 are similiar enough that they can be cloned (GEP12) in GEP3's BB, allowing GEP->GEP merging (GEP123): GEP1--\ --\ --\ |-->PHI1-->GEP3 ==> |-->PHI2->GEP12->GEP3 == > |-->PHI2->GEP123 GEP2--/ --/ --/ This also breaks certain use chains that are preventing GEP->GEP merges that the the existing instcombine would merge otherwise. Tests included. llvm-svn: 209755
* Revert r209049 and r209065, "Add support for combining GEPs across PHI nodes"NAKAMURA Takumi2014-05-171-66/+0
| | | | | | It broke clang selfhosting even after r209065. llvm-svn: 209067
* Fix for sanitizer crash introduced in r209049Louis Gerbarg2014-05-171-1/+8
| | | | | | | | | | This patch fixes 3 issues introduced by r209049 that only showed up in on the sanitizer buildbots. One was a typo in a compare. The other is a check to confirm that the single differing value in the two incoming GEPs is the same type. The final issue was the the IRBuilder under some circumstances would build PHIs in the middle of the block. llvm-svn: 209065
* Add support for combining GEPs across PHI nodesLouis Gerbarg2014-05-161-0/+59
| | | | | | | | | | | | | | | | | | | | | | | | | | Currently LLVM will generally merge GEPs. This allows backends to use more complex addressing modes. In some cases this is not happening because there is PHI inbetween the two GEPs: GEP1--\ |-->PHI1-->GEP3 GEP2--/ This patch checks to see if GEP1 and GEP2 are similiar enough that they can be cloned (GEP12) in GEP3's BB, allowing GEP->GEP merging (GEP123): GEP1--\ --\ --\ |-->PHI1-->GEP3 ==> |-->PHI2->GEP12->GEP3 == > |-->PHI2->GEP123 GEP2--/ --/ --/ This also breaks certain use chains that are preventing GEP->GEP merges that the the existing instcombine would merge otherwise. Tests included. rdar://15547484 llvm-svn: 209049
* Fix the case when reordering shuffle and binop produces a constant.Serge Pavlov2014-05-141-13/+13
| | | | | | This resolves PR19737. llvm-svn: 208762
* Fix type of shuffle obtained from reordering with binary operationSerge Pavlov2014-05-121-1/+1
| | | | | | | | In transformation: BinOp(shuffle(v1,undef), shuffle(v2,undef)) -> shuffle(BinOp(v1, v2),undef) type of the undef argument must be same as type of BinOp. llvm-svn: 208531
* Fix reordering of shuffles and binary operationsSerge Pavlov2014-05-121-0/+1
| | | | | | | | | | | | Do not apply transformation: BinOp(shuffle(v1), shuffle(v2)) -> shuffle(BinOp(v1, v2)) if operands v1 and v2 are of different size. This change fixes PR19717, which was caused by r208488. llvm-svn: 208518
* Reorder shuffle and binary operation.Serge Pavlov2014-05-111-0/+94
| | | | | | | | | | | | | 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
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-59/+59
| | | | 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
* Fix PR19270 - type mismatch caused by invalid optimization.Eli Bendersky2014-04-031-3/+27
| | | | | | Patch by Jingyue Wu. llvm-svn: 205547
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-12/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] llvm-svn: 203364
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-1/+1
| | | | | | class. llvm-svn: 202953
* [Modules] Move CFG.h to the IR library as it defines graph traits overChandler Carruth2014-03-041-1/+1
| | | | | | IR types. llvm-svn: 202827
* [Modules] Move ValueHandle into the IR library where Value itself lives.Chandler Carruth2014-03-041-1/+1
| | | | | | | | | | | Move the test for this class into the IR unittests as well. This uncovers that ValueMap too is in the IR library. Ironically, the unittest for ValueMap is useless in the Support library (honestly, so was the ValueHandle test) and so it already lives in the IR unittests. Mmmm, tasty layering. llvm-svn: 202821
* [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
* [Modules] Move GetElementPtrTypeIterator into the IR library. As itsChandler Carruth2014-03-041-1/+1
| | | | | | | | | name might indicate, it is an iterator over the types in an instruction in the IR.... You see where this is going. Another step of modularizing the support library. llvm-svn: 202815
* Make DataLayout a plain object, not a pass.Rafael Espindola2014-02-251-1/+2
| | | | | | | Instead, have a DataLayoutPass that holds one. This will allow parts of LLVM don't don't handle passes to also use DataLayout. llvm-svn: 202168
* Rename many DataLayout variables from TD to DL.Rafael Espindola2014-02-211-55/+55
| | | | | | | | | 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
* Do more addrspacecast transforms that happen for bitcast.Matt Arsenault2014-02-141-6/+12
| | | | | | Makes addrspacecast (gep) do addrspacecast (gep) instead. llvm-svn: 201376
* Disable most IR-level transform passes on functions marked 'optnone'.Paul Robinson2014-02-061-0/+3
| | | | | | | | | Ideally only those transform passes that run at -O0 remain enabled, in reality we get as close as we reasonably can. Passes are responsible for disabling themselves, it's not the job of the pass manager to do it for them. llvm-svn: 200892
* Fix known typosAlp Toker2014-01-241-2/+2
| | | | | | | Sweep the codebase for common typos. Includes some changes to visible function names that were misspelt. llvm-svn: 200018
OpenPOWER on IntegriCloud