summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombine.h
Commit message (Collapse)AuthorAgeFilesLines
* [PM] Rename InstCombine.h to InstCombineInternal.h in preparation forChandler Carruth2015-01-221-493/+0
| | | | | | | | | | | | | | | | 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] Refactor the InstCombiner interface to use an external worklist.Chandler Carruth2015-01-211-15/+27
| | | | | | | | | | | | | | | | | | | | | | | | | Because in its primary function pass the combiner is run repeatedly over the same function until doing so produces no changes, it is essentially to not re-allocate the worklist. However, as a utility, the more common pattern would be to put a limited set of instructions in the worklist rather than the entire function body. That is also the more likely pattern when used by the new pass manager. The result is a very light weight combiner that does the visiting with a separable worklist. This can then be wrapped up in a helper function for users that want a combiner utility, or as I have here it can be wrapped up in a pass which manages the iterations used when combining an entire function's instructions. Hopefully this removes some of the worst of the interface warts that became apparant with the last patch here. However, there is clearly more work. I've again left some FIXMEs for the most egregious. The ones that stick out to me are the exposure of the worklist and IR builder as public members, and the use of pointers rather than references. However, fixing these is likely to be much more mechanical and less interesting so I didn't want to touch them in this patch. llvm-svn: 226655
* [PM] Simplify (ha! ha!) the way that instcombine calls theChandler Carruth2015-01-211-2/+0
| | | | | | | | | | | | SimplifyLibCalls utility by sinking it into the specific call part of the combiner. This will avoid us needing to do any contortions to build this object in a subsequent refactoring I'm doing and seems generally better factored. We don't need this utility everywhere and it carries no interesting state so we might as well build it on demand. llvm-svn: 226654
* [PM] Separate the InstCombiner from its pass.Chandler Carruth2015-01-201-10/+4
| | | | | | | | | | | | | | | | | | | | This creates a small internal pass which runs the InstCombiner over a function. This is the hard part of porting InstCombine to the new pass manager, as at this point none of the code in InstCombine has access to a Pass object any longer. The resulting interface for the InstCombiner is pretty terrible. I'm not planning on leaving it that way. The key thing missing is that we need to separate the worklist from the combiner a touch more. Once that's done, it should be possible for *any* part of LLVM to just create a worklist with instructions, populate it, and then combine it until empty. The pass will just be the (obvious and important) special case of doing that for an entire function body. For now, this is the first increment of factoring to make all of this work. llvm-svn: 226618
* [PM] Reformat this code with clang-format so that subsequent changesChandler Carruth2015-01-201-9/+9
| | | | | | | | | | don't get muddied up by formatting changes. Some of these don't really seem like improvements to me, but they also don't seem any worse and I care much more about not formatting them manually than I do about the particular formatting. =] llvm-svn: 226610
* [PM] Clean up a bunch of the doxygen / API docs on the InstCombiner passChandler Carruth2015-01-201-50/+61
| | | | | | prior to refactoring it. llvm-svn: 226594
* [PM] Move the LoopInfo analysis pointer into the InstCombiner classChandler Carruth2015-01-201-1/+6
| | | | | | | | | | | along with the other analyses. The most obvious reason why is because eventually I need to separate out the pass layer from the rest of the instcombiner. However, it is also probably a compile time win as every query through the pass manager layer is pretty slow these days. llvm-svn: 226550
* Analysis: Reformulate WillNotOverflowUnsignedAdd for reusabilityDavid Majnemer2015-01-071-1/+4
| | | | | | | | WillNotOverflowUnsignedAdd's smarts will live in ValueTracking as computeOverflowForUnsignedAdd. It now returns a tri-state result: never overflows, always overflows and sometimes overflows. llvm-svn: 225329
* [PM] Split the AssumptionTracker immutable pass into two separate APIs:Chandler Carruth2015-01-041-13/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Analysis: Reformulate WillNotOverflowUnsignedMul for reusabilityDavid Majnemer2015-01-021-1/+4
| | | | | | | | 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/+1
| | | | | | | 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/+5
| | | | | | | We already utilize this logic for reducing overflow intrinsics, it makes sense to reuse it for normal multiplies as well. llvm-svn: 224847
* Strength reduce intrinsics with overflow into regular arithmetic operations ↵Erik Eckstein2014-12-171-0/+1
| | | | | | | | | | if possible. Some intrinsics, like s/uadd.with.overflow and umul.with.overflow, are already strength reduced. This change adds other arithmetic intrinsics: s/usub.with.overflow, smul.with.overflow. It completes the work on PR20194. llvm-svn: 224417
* Refactor creation of overflow result tuples in InstCombineCalls.Erik Eckstein2014-12-111-0/+14
| | | | | | Extract the creation of overflow result tuples in a separate function. NFC. llvm-svn: 224006
* [InstCombine] Minor optimization for bswap with binary opsSimon Pilgrim2014-12-041-0/+1
| | | | | | | | | | | | | | | | | Added instcombine optimizations for BSWAP with AND/OR/XOR ops: OP( BSWAP(x), BSWAP(y) ) -> BSWAP( OP(x, y) ) OP( BSWAP(x), CONSTANT ) -> BSWAP( OP(x, BSWAP(CONSTANT) ) ) Since its just a one liner, I've also added BSWAP to the DAGCombiner equivalent as well: fold (OP (bswap x), (bswap y)) -> (bswap (OP x, y)) Refactored bswap-fold tests to use FileCheck instead of just checking that the bswaps had gone. Differential Revision: http://reviews.llvm.org/D6407 llvm-svn: 223349
* InstCombine: simplify signed range checksErik Eckstein2014-12-031-0/+1
| | | | | | | | | Try to convert two compares of a signed range check into a single unsigned compare. Examples: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n llvm-svn: 223224
* [InstCombine] Re-commit of r218721 (Optimize icmp-select-icmp sequence)Gerolf Hoflehner2014-11-211-2/+14
| | | | | | | Fixes the self-host fail. Note that this commit activates dominator analysis in the combiner by default (like the original commit did). llvm-svn: 222590
* Clean up assume intrinsic pattern matching, no need to check that the ↵Benjamin Kramer2014-10-251-1/+1
| | | | | | | | argument is a value. Also make it const safe and remove superfluous casting. NFC. llvm-svn: 220616
* InstCombine: Optimize icmp eq/ne (shl Const2, A), Const1David Majnemer2014-10-191-0/+2
| | | | | | | | | | | | | | | The following implements the optimization for sequences of the form: icmp eq/ne (shl Const2, A), Const1 Such sequences can be transformed to: icmp eq/ne A, (TrailingZeros(Const1) - TrailingZeros(Const2)) This handles only the equality operators for now. Other operators need to be handled. Patch by Ankur Garg! llvm-svn: 220162
* Revert "[InstCombine] re-commit r218721 with fix for pr21199"Justin Bogner2014-10-081-9/+2
| | | | | | | | | | | | | This seems to cause a miscompile when building clang, which causes a bootstrapped clang to fail or crash in several of its tests. See: http://lab.llvm.org:8013/builders/clang-x86_64-darwin11-RA/builds/1184 http://bb.pgr.jp/builders/clang-3stage-x86_64-linux/builds/7813 This reverts commit r219282. llvm-svn: 219317
* [InstCombine] re-commit r218721 with fix for pr21199Gerolf Hoflehner2014-10-081-2/+9
| | | | | | | | The icmp-select-icmp optimization targets select-icmp.eq only. This is now ensured by testing the branch predicate explictly. This commit also includes the test case for pr21199. llvm-svn: 219282
* Revert r219175 - [InstCombine] re-commit r218721 icmp-select-icmp optimizationHans Wennborg2014-10-081-9/+2
| | | | | | This seems to have caused PR21199. llvm-svn: 219264
* [InstCombine] re-commit r218721 icmp-select-icmp optimizationGerolf Hoflehner2014-10-071-2/+9
| | | | | | | | | Takes care of the assert that caused build fails. Rather than asserting the code checks now that the definition and use are in the same block, and does not attempt to optimize when that is not the case. llvm-svn: 219175
* Revert r218721, r218735.Evgeniy Stepanov2014-10-011-9/+2
| | | | | | | | | | Failing bootstrap on Linux (arm, x86). http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/13139/steps/bootstrap%20clang/logs/stdio http://lab.llvm.org:8011/builders/clang-cmake-armv7-a15-selfhost/builds/470 http://lab.llvm.org:8011/builders/clang-native-arm-lnt/builds/8518 llvm-svn: 218752
* [InstCombine] Optimize icmp-select-icmpGerolf Hoflehner2014-10-011-2/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | In special cases select instructions can be eliminated by replacing them with a cheaper bitwise operation even when the select result is used outside its home block. The instances implemented are patterns like %x=icmp.eq %y=select %x,%r, null %z=icmp.eq|neq %y, null br %z,true, false ==> %x=icmp.ne %y=icmp.eq %r,null %z=or %x,%y br %z,true,false The optimization is integrated into the instruction combiner and performed only when all uses of the select result can be replaced by the select operand proper. For this dominator information is used and dominance is now a required analysis pass in the combiner. The optimization itself is iterative. The critical step is to replace the select result with the non-constant select operand. So the select becomes local and the combiner iteratively works out simpler code pattern and eventually eliminates the select. rdar://17853760 llvm-svn: 218721
* Check for all known bits on ret in InstCombineHal Finkel2014-09-071-0/+1
| | | | | | | | | | 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-12/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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/+12
| | | | | | | | | | | | | | | | | | | | | | | | 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
* InstCombine: Fold ((A | B) & C1) ^ (B & C2) -> (A & C1) ^ B if C1^C2=-1David Majnemer2014-08-211-0/+2
| | | | | | Adapted from a patch by Richard Smith, test-case written by me. llvm-svn: 216157
* InstCombine: Annotate sub with nuw when we prove it's safeDavid Majnemer2014-08-201-0/+1
| | | | | | | We can prove that a 'sub' can be a 'sub nuw' if the left-hand side is negative and the right-hand side is non-negative. llvm-svn: 216045
* InstCombine: Annotate sub with nsw when we prove it's safeDavid Majnemer2014-08-191-0/+1
| | | | | | | | | | We can prove that a 'sub' can be a 'sub nsw' under certain conditions: - The sign bits of the operands is the same. - Both operands have more than 1 sign bit. The subtraction cannot be a signed overflow in either case. llvm-svn: 216037
* Canonicalize header guards into a common format.Benjamin Kramer2014-08-131-2/+2
| | | | | | | | | | Add header guards to files that were missing guards. Remove #endif comments as they don't seem common in LLVM (we can easily add them back if we decide they're useful) Changes made by clang-tidy with minor tweaks. llvm-svn: 215558
* This patch implements optimization as mentioned in PR19753: Optimize ↵Suyog Sarda2014-07-221-0/+2
| | | | | | | | | | | | | | | | | comparisons with "ashr/lshr exact" of a constanst. It handles the errors which were seen in PR19958 where wrong code was being emitted due to earlier patch. Added code for lshr as well as non-exact right shifts. It implements : (icmp eq/ne (ashr/lshr const2, A), const1)" -> (icmp eq/ne A, Log2(const2/const1)) -> (icmp eq/ne A, Log2(const2) - Log2(const1)) Differential Revision: http://reviews.llvm.org/D4068 llvm-svn: 213678
* [InstCombine] mark ADD with nuw if no unsigned overflowJingyue Wu2014-06-171-0/+1
| | | | | | | | | | | | | | | | | | | | | | Summary: As a starting step, we only use one simple heuristic: if the sign bits of both a and b are zero, we can prove "add a, b" do not unsigned overflow, and thus convert it to "add nuw a, b". Updated all affected tests and added two new tests (@zero_sign_bit and @zero_sign_bit2) in AddOverflow.ll Test Plan: make check-all Reviewers: eliben, rafael, meheff, chandlerc Reviewed By: chandlerc Subscribers: chandlerc, llvm-commits Differential Revision: http://reviews.llvm.org/D4144 llvm-svn: 211084
* Added select flavour for ABS and NEG(ABS)Dinesh Dwivedi2014-06-061-2/+3
| | | | | | | | | | | | | | | | This patch can identify ABS(X) ==> (X >s 0) ? X : -X and (X >s -1) ? X : -X ABS(X) ==> (X <s 0) ? -X : X and (X <s 1) ? -X : X NABS(X) ==> (X >s 0) ? -X : X and (X >s -1) ? -X : X NABS(X) ==> (X <s 0) ? X : -X and (X <s 1) ? X : -X and can transform ABS(ABS(X)) -> ABS(X) NABS(NABS(X)) -> NABS(X) Differential Revision: http://reviews.llvm.org/D3658 llvm-svn: 210312
* Rename ComputeMaskedBits to computeKnownBits. "Masked" has beenJay Foad2014-05-141-3/+3
| | | | | | inappropriate since it lost its Mask parameter in r154011. llvm-svn: 208811
* Reorder shuffle and binary operation.Serge Pavlov2014-05-111-0/+2
| | | | | | | | | | | | | 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
* Tidy up whitespace with clang-format prior to making significantChandler Carruth2014-05-071-45/+41
| | | | | | changes. llvm-svn: 208229
* [InstCombine] Add optimization of redundant insertvalue instructions.Michael Zolotukhin2014-05-071-0/+1
| | | | | | rdar://problem/11861387 llvm-svn: 208214
* [C++] Use 'nullptr'.Craig Topper2014-04-281-5/+5
| | | | llvm-svn: 207394
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-2/+4
| | | | | | | | | | | | | | | | | 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
* Revert "Revert r206045, "Fix shift by constants for vector.""Matt Arsenault2014-04-141-1/+1
| | | | | | Fix cases where the Value itself is used, and not the constant value. llvm-svn: 206214
* Revert r206045, "Fix shift by constants for vector."NAKAMURA Takumi2014-04-141-1/+1
| | | | | | It broke some builders, at least, i686. llvm-svn: 206153
* Fix shift by constants for vector.Matt Arsenault2014-04-111-1/+1
| | | | | | ashr <N x iM>, <N x iM> M -> undef llvm-svn: 206045
* [Layering] Move InstVisitor.h into the IR library as it is prettyChandler Carruth2014-03-061-1/+1
| | | | | | obviously coupled to the IR. llvm-svn: 203064
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-2/+2
| | | | | | class. llvm-svn: 202953
* [Modules] Move the TargetFolder into the Analysis library. Historically,Chandler Carruth2014-03-041-1/+1
| | | | | | | | | this would have been required because of the use of DataLayout, but that has moved into the IR proper. It is still required because this folder uses the constant folding in the analysis library (which uses the datalayout) as the more aggressive basis of its folder. llvm-svn: 202832
* Make some DataLayout pointers const.Rafael Espindola2014-02-241-2/+2
| | | | | | No functionality change. Just reduces the noise of an upcoming patch. llvm-svn: 202087
* Rename many DataLayout variables from TD to DL.Rafael Espindola2014-02-211-7/+7
| | | | | | | | | 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
* InstCombine: Hoist 3 copies of AddOne/SubOne into a header.Benjamin Kramer2014-01-191-0/+9
| | | | llvm-svn: 199605
OpenPOWER on IntegriCloud