aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/ValueTracking.cpp
AgeCommit message (Collapse)AuthorFilesLines
2019-03-03[ValueTracking] do not try to peek through bitcasts in ↵Sanjay Patel1-3/+1
computeKnownBitsFromAssume() There are no tests for this case, and I'm not sure how it could ever work, so I'm just removing this option from the matcher. This should fix PR40940: https://bugs.llvm.org/show_bug.cgi?id=40940 llvm-svn: 355292
2019-03-01[ValueTracking] Known bits support for unsigned saturating add/subNikita Popov1-0/+31
We have two sources of known bits: 1. For adds leading ones of either operand are preserved. For sub leading zeros of LHS and leading ones of RHS become leading zeros in the result. 2. The saturating math is a select between add/sub and an all-ones/ zero value. As such we can carry out the add/sub known bits calculation, and only preseve the known one/zero bits respectively. Differential Revision: https://reviews.llvm.org/D58329 llvm-svn: 355223
2019-02-28[ValueTracking] More accurate unsigned sub overflow detectionNikita Popov1-11/+9
Second part of D58593. Compute precise overflow conditions based on all known bits, rather than just the sign bits. Unsigned a - b overflows iff a < b, and we can determine whether this always/never happens based on the minimal and maximal values achievable for a and b subject to the known bits constraint. llvm-svn: 355109
2019-02-28Add support for computing "zext of value" in KnownBits. NFCIBjorn Pettersson1-5/+2
Summary: The description of KnownBits::zext() and KnownBits::zextOrTrunc() has confusingly been telling that the operation is equivalent to zero extending the value we're tracking. That has not been true, instead the user has been forced to explicitly set the extended bits as known zero afterwards. This patch adds a second argument to KnownBits::zext() and KnownBits::zextOrTrunc() to control if the extended bits should be considered as known zero or as unknown. Reviewers: craig.topper, RKSimon Reviewed By: RKSimon Subscribers: javed.absar, hiraditya, jdoerfert, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58650 llvm-svn: 355099
2019-02-28[ValueTracking] More accurate unsigned add overflow detectionNikita Popov1-14/+10
Part of D58593. Compute precise overflow conditions based on all known bits, rather than just the sign bits. Unsigned a + b overflows iff a > ~b, and we can determine whether this always/never happens based on the minimal and maximal values achievable for a and ~b subject to the known bits constraint. llvm-svn: 355072
2019-02-14Teach isGuaranteedToTransferExecutionToSuccessor about widenable conditionsMax Kazantsev1-1/+2
Widenable condition intrinsic is guaranteed to return value, notify the isGuaranteedToTransferExecutionToSuccessor function about it. llvm-svn: 354020
2019-02-08Implementation of asm-goto support in LLVMCraig Topper1-0/+1
This patch accompanies the RFC posted here: http://lists.llvm.org/pipermail/llvm-dev/2018-October/127239.html This patch adds a new CallBr IR instruction to support asm-goto inline assembly like gcc as used by the linux kernel. This instruction is both a call instruction and a terminator instruction with multiple successors. Only inline assembly usage is supported today. This also adds a new INLINEASM_BR opcode to SelectionDAG and MachineIR to represent an INLINEASM block that is also considered a terminator instruction. There will likely be more bug fixes and optimizations to follow this, but we felt it had reached a point where we would like to switch to an incremental development model. Patch by Craig Topper, Alexander Ivchenko, Mikhail Dvoretckii Differential Revision: https://reviews.llvm.org/D53765 llvm-svn: 353563
2019-01-30[NFC] fix trivial typos in commentsHiroshi Inoue1-1/+1
llvm-svn: 352602
2019-01-26[ValueTracking] Look through casts when determining non-nullnessJohannes Doerfert1-0/+22
Bitcast and certain Ptr2Int/Int2Ptr instructions will not alter the value of their operand and can therefore be looked through when we determine non-nullness. Differential Revision: https://reviews.llvm.org/D54956 llvm-svn: 352293
2019-01-19Update the file headers across all of the LLVM projects in the monorepoChandler Carruth1-4/+3
to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
2019-01-07[CallSite removal] Migrate all Alias Analysis APIs to use the newlyChandler Carruth1-14/+14
minted `CallBase` class instead of the `CallSite` wrapper. This moves the largest interwoven collection of APIs that traffic in `CallSite`s. While a handful of these could have been migrated with a minorly more shallow migration by converting from a `CallSite` to a `CallBase`, it hardly seemed worth it. Most of the APIs needed to migrate together because of the complex interplay of AA APIs and the fact that converting from a `CallBase` to a `CallSite` isn't free in its current implementation. Out of tree users of these APIs can fairly reliably migrate with some combination of `.getInstruction()` on the `CallSite` instance and casting the resulting pointer. The most generic form will look like `CS` -> `cast_or_null<CallBase>(CS.getInstruction())` but in most cases there is a more elegant migration. Hopefully, this migrates enough APIs for users to fully move from `CallSite` to the base class. All of the in-tree users were easily migrated in that fashion. Thanks for the review from Saleem! Differential Revision: https://reviews.llvm.org/D55641 llvm-svn: 350503
2019-01-04[ValueTracking] Fix a misuse of APInt in GetPointerBaseWithConstantOffsetFlorian Hahn1-1/+8
GetPointerBaseWithConstantOffset include this code, where ByteOffset and GEPOffset are both of type llvm::APInt : ByteOffset += GEPOffset.getSExtValue(); The problem with this line is that getSExtValue() returns an int64_t, but the += matches an overload for uint64_t. The problem is that the resulting APInt is no longer considered to be signed. That in turn causes assertion failures later on if the relevant pointer type is > 64 bits in width and the GEPOffset was negative. Changing it to ByteOffset += GEPOffset.sextOrTrunc(ByteOffset.getBitWidth()); resolves the issue and explicitly performs the sign-extending or truncation. Additionally, instead of asserting later if the result is > 64 bits, it breaks out of the loop in that case. See also https://reviews.llvm.org/D24729 https://reviews.llvm.org/D24772 This commit must be merged after D38662 in order for the test to pass. Patch by Michael Ferguson <mpfergu@gmail.com>. Reviewers: reames, sanjoy, hfinkel Reviewed By: hfinkel Differential Revision: https://reviews.llvm.org/D38501 llvm-svn: 350395
2018-12-21[IR] Add Instruction::isLifetimeStartOrEnd, NFCVedant Kumar1-2/+1
Instruction::isLifetimeStartOrEnd() checks whether an Instruction is an llvm.lifetime.start or an llvm.lifetime.end intrinsic. This was suggested as a cleanup in D55967. Differential Revision: https://reviews.llvm.org/D56019 llvm-svn: 349964
2018-12-19[ValueTracking] remove unused parameters from helper functions; NFCSanjay Patel1-23/+16
llvm-svn: 349641
2018-12-02[ValueTracking] Support funnel shifts in computeKnownBits()Nikita Popov1-0/+21
If the shift amount is known, we can determine the known bits of the output based on the known bits of two inputs. This is essentially the same functionality as implemented in D54869, but for ValueTracking rather than InstCombine SimplifyDemandedBits. Differential Revision: https://reviews.llvm.org/D55140 llvm-svn: 348091
2018-12-02[ValueTracking] add helper function for testing implied condition; NFCISanjay Patel1-0/+32
We were duplicating code around the existing isImpliedCondition() that checks for a predecessor block/dominating condition, so make that a wrapper call. llvm-svn: 348088
2018-11-28[ValueTracking] Determine always-overflow condition for unsigned subNikita Popov1-6/+11
Always-overflow was already determined for unsigned addition, but not subtraction. This patch establishes parity. This allows us to perform some additional simplifications for signed saturating subtractions. This change is part of https://reviews.llvm.org/D54534. llvm-svn: 347771
2018-11-04[ValueTracking] determine sign of 0.0 from select when matching min/max FPSanjay Patel1-0/+21
In PR39475: https://bugs.llvm.org/show_bug.cgi?id=39475 ..we may fail to recognize/simplify fabs() in some cases because we do not canonicalize fcmp with a -0.0 operand. Adding that canonicalization can cause regressions on min/max FP tests, so that's this patch: for the purpose of determining whether something is min/max, let the value returned by the select determine how we treat a 0.0 operand in the fcmp. This patch doesn't actually change the -0.0 to +0.0. It just changes the analysis, so we don't fail to recognize equivalent min/max patterns that only differ in the signbit of 0.0. Differential Revision: https://reviews.llvm.org/D54001 llvm-svn: 346097
2018-11-03[ValueTracking] peek through 2-input shuffles in ComputeNumSignBitsSanjay Patel1-19/+34
This patch gives the IR ComputeNumSignBits the same functionality as the DAG version (the code is derived from the existing code). This an extension of the single input shuffle analysis added with D53659. Differential Revision: https://reviews.llvm.org/D53987 llvm-svn: 346071
2018-11-02[ValueTracking] allow non-canonical shuffles when computing signbitsSanjay Patel1-8/+10
This possibility is noted in D53987 for a different case, so we need to adjust the existing code. llvm-svn: 345988
2018-10-26[ValueTracking] peek through shuffles in ComputeNumSignBits (PR37549)Sanjay Patel1-0/+21
The motivating case is from PR37549: https://bugs.llvm.org/show_bug.cgi?id=37549 The analysis improvement allows us to form a vector 'select' out of bitwise logic (the use of ComputeNumSignBits was added at rL345149). The smaller test shows another InstCombine improvement - we use ComputeNumSignBits to add 'nsw' to shift-left. But the negative test shows an example where we must not add 'nsw' - when the shuffle mask contains undef elements. Differential Revision: https://reviews.llvm.org/D53659 llvm-svn: 345429
2018-10-19[InstCombine] InstCombine and InstSimplify for minimum and maximumThomas Lively1-0/+6
Summary: Depends on D52765 Reviewers: aheejin, dschuff Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D52766 llvm-svn: 344799
2018-09-28[ValueTracking] Allow select patterns to work on FP vectorsThomas Lively1-0/+22
Summary: This CL allows constant vectors of floats to be recognized as non-NaN and non-zero in select patterns. This change makes `matchSelectPattern` more powerful generally, but was motivated specifically because I wanted fminnan and fmaxnan to be created for vector versions of the scalar patterns they are created for. Tested with check-all on all targets. A testcase in the WebAssembly backend that tests the non-nan codepath is in an upcoming CL. Reviewers: aheejin, dschuff Subscribers: sunfish, llvm-commits Differential Revision: https://reviews.llvm.org/D52324 llvm-svn: 343364
2018-09-21Merge clang's isRepeatedBytePattern with LLVM's isBytewiseValueJF Bastien1-32/+62
Summary: his code was in CGDecl.cpp and really belongs in LLVM's isBytewiseValue. Teach isBytewiseValue the tricks clang's isRepeatedBytePattern had, including merging undef properly, and recursing on more types. clang part of this patch: D51752 Subscribers: dexonsmith, llvm-commits Differential Revision: https://reviews.llvm.org/D51751 llvm-svn: 342709
2018-08-30Re-enable "[NFC] Unify guards detection"Max Kazantsev1-2/+2
rL340921 has been reverted by rL340923 due to linkage dependency from Transform/Utils to Analysis which is not allowed. In this patch this has been fixed, a new utility function moved to Analysis. Differential Revision: https://reviews.llvm.org/D51152 llvm-svn: 341014
2018-08-29Revert r340921 "[NFC] Unify guards detection"Hans Wennborg1-2/+2
This broke the build, see e.g. http://lab.llvm.org:8011/builders/clang-cmake-armv8-lnt/builds/4626/ http://lab.llvm.org:8011/builders/clang-ppc64be-linux-lnt/builds/18647/ http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/5856/ http://lab.llvm.org:8011/builders/lld-x86_64-freebsd/builds/22800/ > We have multiple places in code where we try to identify whether or not > some instruction is a guard. This patch factors out this logic into a separate > utility function which works uniformly in all places. > > Differential Revision: https://reviews.llvm.org/D51152 > Reviewed By: fedor.sergeev llvm-svn: 340923
2018-08-29[NFC] Unify guards detectionMax Kazantsev1-2/+2
We have multiple places in code where we try to identify whether or not some instruction is a guard. This patch factors out this logic into a separate utility function which works uniformly in all places. Differential Revision: https://reviews.llvm.org/D51152 Reviewed By: fedor.sergeev llvm-svn: 340921
2018-08-23[ValueTracking] Fix assert message and add test case for r340546 and PR38677.Craig Topper1-1/+1
The bug was already fixed. This just adds a test case for it. llvm-svn: 340556
2018-08-23[ValueTracking] Fix an assert from r340480.Craig Topper1-1/+3
We need to allow ConstantExpr Selects in addition to SelectInst. I'll try to put together a test case, but I wanted to fix the issues being reported. Fixes PR38677 llvm-svn: 340546
2018-08-22[ValueTracking] Teach computeNumSignBits to understand min/max clamp ↵Craig Topper1-1/+37
patterns with constant/splat values If we have a min/max pair we can do a better job of counting sign bits if we look at them together. This is similar to what is done in the SelectionDAG version of computeNumSignBits for ISD::SMAX/SMIN. Differential Revision: https://reviews.llvm.org/D51112 llvm-svn: 340480
2018-08-20ValueTracking: Handle more instructions in isKnownNeverNaNMatt Arsenault1-3/+33
llvm-svn: 340187
2018-08-17[InstrSimplify,NewGVN] Add option to ignore additional instr info when ↵Florian Hahn1-81/+94
simplifying. NewGVN uses InstructionSimplify for simplifications of leaders of congruence classes. It is not guaranteed that the metadata or other flags/keywords (like nsw or exact) of the leader is available for all members in a congruence class, so we cannot use it for simplification. This patch adds a InstrInfoQuery struct with a boolean field UseInstrInfo (which defaults to true to keep the current behavior as default) and a set of helper methods to get metadata/keywords for a given instruction, if UseInstrInfo is true. The whole thing might need a better name, to avoid confusion with TargetInstrInfo but I am not sure what a better name would be. The current patch threads through InstrInfoQuery to the required places, which is messier then it would need to be, if InstructionSimplify and ValueTracking would share the same Query struct. The reason I added it as a separate struct is that it can be shared between InstructionSimplify and ValueTracking's query objects. Also, some places do not need a full query object, just the InstrInfoQuery. It also updates some interfaces that do not take a Query object, but a set of optional parameters to take an additional boolean UseInstrInfo. See https://bugs.llvm.org/show_bug.cgi?id=37540. Reviewers: dberlin, davide, efriedma, sebpop, hiraditya Reviewed By: hiraditya Differential Revision: https://reviews.llvm.org/D47143 llvm-svn: 340031
2018-08-09ValueTracking: Start enhancing isKnownNeverNaNMatt Arsenault1-3/+21
llvm-svn: 339399
2018-08-06ValueTracking: Handle canonicalize in CannotBeNegativeZeroMatt Arsenault1-0/+1
Also fix apparently missing test coverage for any of the handling here. llvm-svn: 339023
2018-08-06Re-enable "[ValueTracking] Teach isKnownNonNullFromDominatingCondition about ↵Max Kazantsev1-10/+33
AND" The patch was reverted because of bug detected by sanitizer. The bug is fixed, respective tests added. Differential Revision: https://reviews.llvm.org/D50172 llvm-svn: 339005
2018-08-06Revert rL338990 to see if it causes sanitizer failuresMax Kazantsev1-28/+10
Multiple failues reported by sanitizer-x86_64-linux, seem to be caused by this patch. Reverting to see if they sustain without it. Differential Revision: https://reviews.llvm.org/D50172 llvm-svn: 338994
2018-08-06[ValueTracking] Teach isKnownNonNullFromDominatingCondition about ANDMax Kazantsev1-10/+28
`isKnownNonNullFromDominatingCondition` is able to prove non-null basing on `br` or `guard` by `%p != null` condition, but is unable to do so basing on `(%p != null) && %other_cond`. This patch allows it to do so. Differential Revision: https://reviews.llvm.org/D50172 Reviewed By: reames llvm-svn: 338990
2018-08-02[ValueTracking] fix maxnum miscompile for cannotBeOrderedLessThanZero (PR37776)Sanjay Patel1-4/+7
This adds the NAN checks suggested in PR37776: https://bugs.llvm.org/show_bug.cgi?id=37776 If both operands to maxnum are NAN, that should get constant folded, so we don't have to handle that case. This is the same assumption as other FP ops in this function. Returning 'false' is always conservatively correct. Copying from the bug report: Currently, we have this for "when is cannotBeOrderedLessThanZero (mustBePositiveOrNaN) true for maxnum": L ------------------- | Pos | Neg | NaN | ------------------------ |Pos | x | x | x | ------------------------ R |Neg | x | | x | ------------------------ |NaN | x | x | x | ------------------------ The cases with (Neg & NaN) are wrong. We should have: L ------------------- | Pos | Neg | NaN | ------------------------ |Pos | x | x | x | ------------------------ R |Neg | x | | | ------------------------ |NaN | x | | x | ------------------------ Differential Revision: https://reviews.llvm.org/D50081 llvm-svn: 338716
2018-07-30Remove trailing spaceFangrui Song1-6/+6
sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
2018-07-25Fix llvm::ComputeNumSignBits with some operations and llvm.assumeStanislav Mekhanoshin1-7/+7
Currently ComputeNumSignBits does early exit while processing some of the operations (add, sub, mul, and select). This prevents the function from using AssumptionCacheTracker if passed. Differential Revision: https://reviews.llvm.org/D49759 llvm-svn: 337936
2018-07-21[InstrSimplify] fold sdiv if two operands are negated and non-overflowChen Zheng1-8/+12
Differential Revision: https://reviews.llvm.org/D49382 llvm-svn: 337642
2018-07-16[InstCombine] add more SPFofSPF foldingChen Zheng1-24/+39
Differential Revision: https://reviews.llvm.org/D49238 llvm-svn: 337143
2018-07-12[InstCombine] Simplify isKnownNegationFangrui Song1-5/+2
llvm-svn: 336957
2018-07-12[InstSimplify] simplify add instruction if two operands are negativeChen Zheng1-0/+20
Differential Revision: https://reviews.llvm.org/D49216 llvm-svn: 336881
2018-07-09llvm: Add support for "-fno-delete-null-pointer-checks"Manoj Gupta1-1/+6
Summary: Support for this option is needed for building Linux kernel. This is a very frequently requested feature by kernel developers. More details : https://lkml.org/lkml/2018/4/4/601 GCC option description for -fdelete-null-pointer-checks: This Assume that programs cannot safely dereference null pointers, and that no code or data element resides at address zero. -fno-delete-null-pointer-checks is the inverse of this implying that null pointer dereferencing is not undefined. This feature is implemented in LLVM IR in this CL as the function attribute "null-pointer-is-valid"="true" in IR (Under review at D47894). The CL updates several passes that assumed null pointer dereferencing is undefined to not optimize when the "null-pointer-is-valid"="true" attribute is present. Reviewers: t.p.northover, efriedma, jyknight, chandlerc, rnk, srhines, void, george.burgess.iv Reviewed By: efriedma, george.burgess.iv Subscribers: eraman, haicheng, george.burgess.iv, drinkcat, theraven, reames, sanjoy, xbolva00, llvm-commits Differential Revision: https://reviews.llvm.org/D47895 llvm-svn: 336613
2018-07-06Use Type::isIntOrPtrTy where possible, NFCVedant Kumar1-1/+1
It's a bit neater to write T.isIntOrPtrTy() over `T.isIntegerTy() || T.isPointerTy()`. I used Python's re.sub with this regex to update users: r'([\w.\->()]+)isIntegerTy\(\)\s*\|\|\s*\1isPointerTy\(\)' llvm-svn: 336462
2018-07-02[ValueTracking] allow undef elements when matching vector absSanjay Patel1-32/+27
llvm-svn: 336111
2018-07-02Implement strip.invariant.groupPiotr Padlewski1-9/+12
Summary: This patch introduce new intrinsic - strip.invariant.group that was described in the RFC: Devirtualization v2 Reviewers: rsmith, hfinkel, nlopes, sanjoy, amharc, kuhar Subscribers: arsenm, nhaehnle, JDevlieghere, hiraditya, xbolva00, llvm-commits Differential Revision: https://reviews.llvm.org/D47103 Co-authored-by: Krzysztof Pszeniczny <krzysztof.pszeniczny@gmail.com> llvm-svn: 336073
2018-06-04[ValueTracking] Match select abs pattern when there's an sext involvedJohn Brawn1-6/+18
When checking a select to see if it matches an abs, allow the true/false values to be a sign-extension of the comparison value instead of requiring that they're directly the comparison value, as all the comparison cares about is the sign of the value. This fixes a regression due to r333702, where we were no longer generating ctlz due to isKnownNonNegative failing to match such a pattern. Differential Revision: https://reviews.llvm.org/D47631 llvm-svn: 333927
2018-05-30[ValueTracking] Fix endless recursion in isKnownNonZero()Karl-Johan Karlsson1-4/+5
Summary: The isKnownNonZero() function have checks that abort the recursion when it reaches the specified max depth. However one of the recursive calls was placed before the max depth check was done, resulting in a endless recursion that eventually triggered a segmentation fault. Fixed the problem by moving the max depth check above the first recursive call. Reviewers: Prazek, nlopes, spatel, craig.topper, hfinkel Reviewed By: hfinkel Subscribers: hfinkel, bjope, llvm-commits Differential Revision: https://reviews.llvm.org/D47531 llvm-svn: 333557
generated by cgit v1.1 at 2025-10-15 10:38:43 +0000