summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [InstCombine] fix and enhance udiv/urem narrowingSanjay Patel2017-08-241-24/+41
| | | | | | | | | | | | | | There are 3 small independent changes here: 1. Account for multiple uses in the pattern matching: avoid the transform if it increases the instruction count. 2. Add a missing fold for the case where the numerator is the constant: http://rise4fun.com/Alive/E2p 3. Enable all folds for vector types. There's still one more potential change - use "shouldChangeType()" to keep from transforming to an illegal integer type. Differential Revision: https://reviews.llvm.org/D36988 llvm-svn: 311726
* [IR] Add Type::isIntOrIntVectorTy(unsigned) similar to the existing ↵Craig Topper2017-07-091-3/+2
| | | | | | isIntegerTy(unsigned), but also works for vectors. llvm-svn: 307492
* [InstCombine] Make InstCombine's IRBuilder be passed by reference everywhereCraig Topper2017-07-071-45/+43
| | | | | | | | Previously the InstCombiner class contained a pointer to an IR builder that had been passed to the constructor. Sometimes this would be passed to helper functions as either a pointer or the pointer would be dereferenced to be passed by reference. This patch makes it a reference everywhere including the InstCombiner class itself so there is more inconsistency. This a large, but mechanical patch. I've done very minimal formatting changes on it despite what clang-format wanted to do. llvm-svn: 307451
* [InstCombine] Propagate nsw flag when turning mul by pow2 into shift when ↵Craig Topper2017-06-271-2/+2
| | | | | | | | | | | | the constant is a vector splat or the scalar bit width is larger than 64-bits The check to see if we can propagate the nsw flag used m_ConstantInt(uint64_t*&) which doesn't work with splat vectors and has a restriction that the bitwidth of the ConstantInt must be 64-bits are less. This patch changes it to use m_APInt to remove both these issues Differential Revision: https://reviews.llvm.org/D34699 llvm-svn: 306457
* [InstCombine] Pass a proper context instruction to all of the calls into ↵Craig Topper2017-06-091-8/+11
| | | | | | | | | | | | | | | | InstSimplify Summary: This matches the behavior we already had for compares and makes us consistent everywhere. Reviewers: dberlin, hfinkel, spatel Reviewed By: dberlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D33604 llvm-svn: 305049
* [InstCombine][InstSimplify] Use APInt::isNullValue/isOneValue to reduce ↵Craig Topper2017-06-071-1/+1
| | | | | | | | compiled code for comparing APInts with 0 and 1. NFC These methods are specifically optimized to only counting leading zeros without an additional uint64_t compare. llvm-svn: 304876
* [InstCombine] Add an InstCombine specific wrapper around ↵Craig Topper2017-05-251-5/+3
| | | | | | | | isKnownToBeAPowerOfTwo to shorten code. NFC We have wrappers for several other ValueTracking methods that take care of passing all of the analysis and assumption cache parameters. This extends it to isKnownToBeAPowerOfTwo. llvm-svn: 303924
* [InstCombine] Cleanup the interface for overflow checksCraig Topper2017-05-221-5/+6
| | | | | | | | | | | | | | | | | | Summary: Fix naming conventions and const correctness. This completes the changes made in rL303029. Patch by Yoav Ben-Shalom. Reviewers: craig.topper Reviewed By: craig.topper Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D33377 llvm-svn: 303529
* [ValueTracking] Replace all uses of ComputeSignBit with computeKnownBits.Craig Topper2017-05-151-5/+3
| | | | | | | | This patch finishes off the conversion of ComputeSignBit to computeKnownBits. Differential Revision: https://reviews.llvm.org/D33166 llvm-svn: 303035
* [InstCombine] Merge duplicate functionality between InstCombine and ↵Craig Topper2017-05-151-8/+4
| | | | | | | | | | | | | | | | | | | | | | | ValueTracking Summary: Merge overflow computation for signed add, appearing both in InstCombine and ValueTracking. As part of the merge, cleanup the interface for overflow checks in InstCombine. Patch by Yoav Ben-Shalom. Reviewers: craig.topper, majnemer Reviewed By: craig.topper Subscribers: takuto.ikuta, llvm-commits Differential Revision: https://reviews.llvm.org/D32946 llvm-svn: 303029
* InstCombine: Use the new SimplifyQuery versions of Simplify*. Use ↵Daniel Berlin2017-04-261-11/+8
| | | | | | AssumptionCache, DominatorTree, TargetLibraryInfo everywhere. llvm-svn: 301464
* [APInt] Rename getSignBit to getSignMaskCraig Topper2017-04-201-2/+2
| | | | | | | | getSignBit is a static function that creates an APInt with only the sign bit set. getSignMask seems like a better name to convey its functionality. In fact several places use it and then store in an APInt named SignMask. Differential Revision: https://reviews.llvm.org/D32108 llvm-svn: 300856
* [InstCombine] Simplify 1/X for vectors.Craig Topper2017-04-171-16/+15
| | | | llvm-svn: 300439
* [InstCombine] Add support for vector srem->urem.Craig Topper2017-04-171-7/+5
| | | | llvm-svn: 300437
* [InstCombine] Add support for turning vector sdiv into udiv.Craig Topper2017-04-171-18/+16
| | | | llvm-svn: 300435
* [InstCombine] Support folding a subtract with a constant LHS into a phi nodeCraig Topper2017-04-141-3/+3
| | | | | | | | | | | | We currently only support folding a subtract into a select but not a PHI. This fixes that. I had to fix an assumption in FoldOpIntoPhi that assumed the PHI node was always in operand 0. Now we pass it in like we do for FoldOpIntoSelect. But we still require some dancing to find the Constant when we create the BinOp or ConstantExpr. This is based code is similar to what we do for selects. Since I touched all call sites, this also renames FoldOpIntoPhi to foldOpIntoPhi to match coding standards. Differential Revision: https://reviews.llvm.org/D31686 llvm-svn: 300363
* [InstCombine] improve readability; NFCISanjay Patel2017-03-141-29/+23
| | | | llvm-svn: 297755
* [InstCombine] add a wrapper for a common pair of transforms; NFCISanjay Patel2017-01-101-24/+7
| | | | | | | Some of the callers are artificially limiting this transform to integer types; this should make it easier to incrementally remove that restriction. llvm-svn: 291620
* InstCombine: fdiv -x, -y -> fdiv x, yMatt Arsenault2017-01-101-0/+10
| | | | llvm-svn: 291611
* [InstCombine] Address post-commit feedbackDavid Majnemer2016-12-301-1/+2
| | | | llvm-svn: 290741
* [InstCombine] More thoroughly canonicalize the position of zextsDavid Majnemer2016-12-301-0/+73
| | | | | | | | We correctly canonicalized (add (sext x), (sext y)) to (sext (add x, y)) where possible. However, we didn't perform the same canonicalization for zexts or for muls. llvm-svn: 290733
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-11/+12
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Remove the AssumptionCacheHal Finkel2016-12-151-12/+11
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* fix formatting; NFCSanjay Patel2016-11-211-1/+0
| | | | llvm-svn: 287582
* [InstCombine] Teach the udiv folding logic how to handle constant expressions.Andrea Di Biagio2016-09-261-11/+14
| | | | | | | | | | | | | | | | | | | This patch fixes PR30366. Function foldUDivShl() worked under the assumption that one of the values in input to the function was always an instance of llvm::Instruction. However, function visitUDivOperand() (the only user of foldUDivShl) was clearly violating that precondition; internally, visitUDivOperand() uses pattern matches to check the operands of a udiv. Pattern matchers for binary operators know how to handle both Instruction and ConstantExpr values. This patch fixes the problem in foldUDivShl(). Now we use pattern matchers instead of explicit casts to Instruction. The reduced test case from PR30366 has been added to test file InstCombine/udiv-simplify.ll. Differential Revision: https://reviews.llvm.org/D24565 llvm-svn: 282398
* [InstCombine] fold X urem C -> X < C ? X : X - C when C is big (PR28672)Sanjay Patel2016-09-221-0/+8
| | | | | | | | | | | | We already have the udiv variant of this transform, so I think this is ok for InstCombine too even though there is an increase in IR instructions. As the tests and TODO comments show, the transform can lead to follow-on combines. This should fix: https://llvm.org/bugs/show_bug.cgi?id=28672 Differential Revision: https://reviews.llvm.org/D24527 llvm-svn: 282209
* InstCombine: Replace some never-null pointers with references. NFCJustin Bogner2016-08-051-12/+12
| | | | llvm-svn: 277792
* [InstCombine] shrink type of sdiv if dividend is sexted and constant divisor ↵Sanjay Patel2016-06-271-0/+17
| | | | | | | | | | | is small enough (PR28153) This should fix PR28153: https://llvm.org/bugs/show_bug.cgi?id=28153 Differential Revision: http://reviews.llvm.org/D21769 llvm-svn: 273951
* [InstCombine] refactor sdiv by APInt transforms (NFC)Sanjay Patel2016-06-271-9/+10
| | | | | | | There's at least one more fold to do here: https://llvm.org/bugs/show_bug.cgi?id=28153 llvm-svn: 273904
* [InstCombine] use m_APInt for div --> ashr foldSanjay Patel2016-06-271-8/+6
| | | | | | The APInt matcher works with splat vectors, so we get this fold for vectors too. llvm-svn: 273897
* Add safety check to InstCombiner::commonIRemTransformsSanjoy Das2016-06-051-2/+11
| | | | | | | | | | | | | | | | Since FoldOpIntoPhi speculates the binary operation to potentially each of the predecessors of the PHI node (pulling it out of arbitrary control dependence in the process), we can FoldOpIntoPhi only if we know the operation doesn't have UB. This also brings up an interesting profitability question -- the way it is written today, commonIRemTransforms will hoist out work from dynamically dead code into code that will execute at runtime. Perhaps that isn't the best canonicalization? Fixes PR27968. llvm-svn: 271857
* reduce indent; NFCSanjay Patel2016-05-221-19/+19
| | | | llvm-svn: 270372
* 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
OpenPOWER on IntegriCloud