summaryrefslogtreecommitdiffstats
path: root/llvm/test/Analysis/ValueTracking
Commit message (Collapse)AuthorAgeFilesLines
* Fix llvm::ComputeNumSignBits with some operations and llvm.assumeStanislav Mekhanoshin2018-07-251-0/+109
| | | | | | | | | | 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
* Simplify recursive launder.invariant.group and stripPiotr Padlewski2018-07-121-6/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch is crucial for proving equality laundered/stripped pointers. eg: bool foo(A *a) { return a == std::launder(a); } Clang with -fstrict-vtable-pointers will emit something like: define dso_local zeroext i1 @_Z3fooP1A(%struct.A* %a) { entry: %c = bitcast %struct.A* %a to i8* %call = tail call i8* @llvm.launder.invariant.group.p0i8(i8* %c) %0 = bitcast %struct.A* %a to i8* %1 = tail call i8* @llvm.strip.invariant.group.p0i8(i8* %0) %2 = tail call i8* @llvm.strip.invariant.group.p0i8(i8* %call) %cmp = icmp eq i8* %1, %2 ret i1 %cmp } and because %2 can be replaced with @llvm.strip.invariant.group(%0) and that %2 and %1 will produce the same value (because strip is readnone) we can replace compare with true. Reviewers: rsmith, hfinkel, majnemer, amharc, kuhar Subscribers: llvm-commits, hiraditya Differential Revision: https://reviews.llvm.org/D47423 llvm-svn: 336963
* Revert "[InstCombine] Delay foldICmpUsingKnownBits until simple transforms ↵Max Kazantsev2018-07-061-1/+1
| | | | | | are done" llvm-svn: 336410
* [InstCombine] Delay foldICmpUsingKnownBits until simple transforms are doneMax Kazantsev2018-07-031-1/+1
| | | | | | | | | | | | This patch changes order of transform in InstCombineCompares to avoid performing transforms based on ranges which produce complex bit arithmetics before more simple things (like folding with constants) are done. See PR37636 for the motivating example. Differential Revision: https://reviews.llvm.org/D48584 Reviewed By: spatel, lebedev.ri llvm-svn: 336172
* Implement strip.invariant.groupPiotr Padlewski2018-07-021-2/+19
| | | | | | | | | | | | | | | | 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
* Fix aliasing of launder.invariant.groupPiotr Padlewski2018-05-231-0/+21
| | | | | | | | | | | | | | | | | | | Summary: Patch for capture tracking broke bootstrap of clang with -fstict-vtable-pointers which resulted in debbugging nightmare. It was fixed https://reviews.llvm.org/D46900 but as it turned out, there were other parts like inliner (computing of noalias metadata) that I found after bootstraping with enabled assertions. Reviewers: hfinkel, rsmith, chandlerc, amharc, kuhar Subscribers: JDevlieghere, eraman, llvm-commits, hiraditya Differential Revision: https://reviews.llvm.org/D47088 llvm-svn: 333070
* Propagate nonnull and dereferenceable throught launderPiotr Padlewski2018-05-182-0/+44
| | | | | | | | | | | | | | | Summary: invariant.group.launder should not stop propagation of nonnull and dereferenceable, because e.g. we would not be able to hoist loads speculatively. Reviewers: rsmith, amharc, kuhar, xbolva00, hfinkel Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D46972 llvm-svn: 332788
* [IR] Do not assume that function pointers are alignedMikhail Maltsev2018-04-271-0/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The value tracking analysis uses function alignment to infer that the least significant bits of function pointers are known to be zero. Unfortunately, this is not correct for ARM targets: the least significant bit of a function pointer stores the ARM/Thumb state information (i.e., the LSB is set for Thumb functions and cleared for ARM functions). The original approach (https://reviews.llvm.org/D44781) introduced a new field for function pointer alignment in the DataLayout structure to address this. But it seems unlikely that optimizations based on function pointer alignment would bring much benefit in practice to justify the additional maintenance burden, so this patch simply assumes that function pointer alignment is always unknown. Reviewers: javed.absar, efriedma Reviewed By: efriedma Subscribers: kristof.beyls, llvm-commits, hfinkel, rogfer01 Differential Revision: https://reviews.llvm.org/D46110 llvm-svn: 331025
* [ValueTracking] add recursion depth param to matchSelectPattern Sanjay Patel2018-01-241-0/+46
| | | | | | | | | | | | | | | | | | | | | | | We're getting bug reports: https://bugs.llvm.org/show_bug.cgi?id=35807 https://bugs.llvm.org/show_bug.cgi?id=35840 https://bugs.llvm.org/show_bug.cgi?id=36045 ...where we blow up the stack in value tracking because other passes are sending in selects that have an operand that is itself the select. We don't currently have a reliable way to avoid analyzing dead code that may take non-standard forms, so bail out when things go too far. This mimics the recursion depth limitations in other parts of value tracking. Unfortunately, this pushes the underlying problems for other passes (jump-threading, simplifycfg, correlated-propagation) into hiding. If someone wants to uncover those again, the first draft of this patch on Phab would do that (it would assert rather than bail out). Differential Revision: https://reviews.llvm.org/D42442 llvm-svn: 323331
* [ValueTracking] Adding missed lit-test for commit r316208Nikolai Bozhenov2018-01-041-0/+27
| | | | | | | | | | Reviewers: reames, hfinkel Differential Revision: https://reviews.llvm.org/D34101 Patch by: Olga Chupina <olga.chupina@intel.com> llvm-svn: 321792
* Give up on array allocas in getPointerDereferenceableBytesBjorn Steinbrink2017-12-201-12/+0
| | | | | | | | | | | | | | | Summary: As suggested by Eli Friedman, don't try to handle array allocas here, because of possible overflows, instead rely on instcombine converting them to allocations of array types. Reviewers: efriedma Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41398 llvm-svn: 321159
* Treat sret arguments as being dereferenceable in ↵Bjorn Steinbrink2017-12-191-1/+11
| | | | | | | | | | | | getPointerDereferenceableBytes() Reviewers: rnk, hfinkel, efriedma Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41355 llvm-svn: 321061
* Re-commit "Properly handle multi-element and dynamically sized allocas in ↵Bjorn Steinbrink2017-12-171-0/+17
| | | | | | | | | getPointerDereferenceableBytes()"" llvm-clang-x86_64-expensive-checks-win is still broken, so the failure seems unrelated. llvm-svn: 320953
* Revert "Properly handle multi-element and dynamically sized allocas in ↵Bjorn Steinbrink2017-12-171-17/+0
| | | | | | | | | | getPointerDereferenceableBytes()" This reverts commit 217067d5179882de9deb60d2e866befea4c126e7. Fails on llvm-clang-x86_64-expensive-checks-win llvm-svn: 320945
* Properly handle byval arguments in getPointerDereferenceableBytes()Bjorn Steinbrink2017-12-171-1/+15
| | | | | | | | | | | | | | Summary: For byval arguments, the number of dereferenceable bytes is equal to the size of the pointee, not the pointer. Reviewers: hfinkel, rnk Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41305 llvm-svn: 320939
* Properly handle multi-element and dynamically sized allocas in ↵Bjorn Steinbrink2017-12-171-0/+17
| | | | | | | | | | | | getPointerDereferenceableBytes() Reviewers: hfinkel, rnk Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41288 llvm-svn: 320938
* [ValueTracking] return zero when there's conflict in known bits of a shift ↵Sanjay Patel2017-10-121-10/+4
| | | | | | | | (PR34838) Poison allows us to return a better result than undef. llvm-svn: 315595
* [ValueTracking] Don't delete assumes of side-effectful instructionsHal Finkel2017-08-141-1/+12
| | | | | | | | | | | | | | | | | | | | | | | | ValueTracking has to strike a balance when attempting to propagate information backwards from assumes, because if the information is trivially propagated backwards, it can appear to LLVM that the assumption is known to be true, and therefore can be removed. This is sound (because an assumption has no semantic effect except for causing UB), but prevents the assume from allowing further optimizations. The isEphemeralValueOf check exists to try and prevent this issue by not removing the source of an assumption. This tries to make it a little bit more general to handle the case of side-effectful instructions, such as in %0 = call i1 @get_val() %1 = xor i1 %0, true call void @llvm.assume(i1 %1) Patch by Ariel Ben-Yehuda, thanks! Differential Revision: https://reviews.llvm.org/D36590 llvm-svn: 310859
* [ValueTracking] Revert r310583 which enabled functionality that still isChandler Carruth2017-08-141-27/+0
| | | | | | | | | | | | | | | | | | | | | | | | | causing compile time issues. Moreover, the patch *deleted* the flag in addition to changing the default, and links to a code review that doesn't even discuss the flag and just has an update to a Clang test case. I've followed up on the commit thread to ask for numbers on compile time at this point, leaving the flag in place until things stabilize, and pointing at specific code that seems to exhibit excessive compile time with this patch. Original commit message for r310583: """ [ValueTracking] Enabling ValueTracking patch by default (recommit). Part 2. The original patch was an improvement to IR ValueTracking on non-negative integers. It has been checked in to trunk (D18777, r284022). But was disabled by default due to performance regressions. Perf impact has improved. The patch would be enabled by default. """" llvm-svn: 310816
* [ValueTracking] Enabling ValueTracking patch by default (recommit). Part 2.Nikolai Bozhenov2017-08-101-0/+27
| | | | | | | | | | | | | | | The original patch was an improvement to IR ValueTracking on non-negative integers. It has been checked in to trunk (D18777, r284022). But was disabled by default due to performance regressions. Perf impact has improved. The patch would be enabled by default. Reviewers: reames, hfinkel Differential Revision: https://reviews.llvm.org/D34101 Patch by: Olga Chupina <olga.chupina@intel.com> llvm-svn: 310583
* [ValueTracking] use nonnull argument attribute to eliminate null checksSanjay Patel2017-02-121-7/+50
| | | | | | | | | | | Enhancing value tracking's analysis of null-ness was suggested in D27855, so here's a first attempt at that. This is part of solving: https://llvm.org/bugs/show_bug.cgi?id=28430 Differential Revision: https://reviews.llvm.org/D28204 llvm-svn: 294897
* [ValueTracking] regenerate checks; NFCSanjay Patel2017-01-091-7/+15
| | | | llvm-svn: 291468
* [ValueTracking] add tests for known-nonnull-at; NFCSanjay Patel2016-12-311-0/+57
| | | | llvm-svn: 290790
* [InstSimplify] allow integer vector types to use computeKnownBitsSanjay Patel2016-11-271-15/+3
| | | | | | | | Note that the non-splat lshr+lshr test folded, but that does not work in general. Something is missing or wrong in computeKnownBits as the non-splat shl+shl test still shows. llvm-svn: 288005
* add tests to show missing analysis; NFCSanjay Patel2016-11-271-0/+71
| | | | llvm-svn: 287998
* Fix known zero bits for addrspacecast.Yaxun Liu2016-11-211-0/+24
| | | | | | | | | | Currently LLVM assumes that a pointer addrspacecasted to a different addr space is equivalent to trunc or zext bitwise, which is not true. For example, in amdgcn target, when a null pointer is addrspacecasted from addr space 4 to 0, its value is changed from i64 0 to i32 -1. This patch teaches LLVM not to assume known bits of addrspacecast instruction to its operand. Differential Revision: https://reviews.llvm.org/D26803 llvm-svn: 287545
* [Loads] Fix crash in is isDereferenceableAndAlignedPointer()Tom Stellard2016-10-281-0/+21
| | | | | | | | | | | | | | | Summary: We were trying to add APInt values with different bit sizes after visiting an addrspacecast instruction which changed the bit width of the pointer. Reviewers: majnemer, hfinkel Subscribers: hfinkel, wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D24774 llvm-svn: 285407
* [ValueTracking] Fix crash in GetPointerBaseWithConstantOffset()Tom Stellard2016-10-071-0/+26
| | | | | | | | | | | | | | | | | | | Summary: While walking defs of pointer operands we were assuming that the pointer size would remain constant. This is not true, because addresspacecast instructions may cast the pointer to an address space with a different pointer width. This partial reverts r282612, which was a more conservative solution to this problem. Reviewers: reames, sanjoy, apilipenko Subscribers: wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D24772 llvm-svn: 283557
* [ValueTracking] Teach computeKnownBits and ComputeNumSignBits to look ↵Bjorn Pettersson2016-10-061-0/+28
| | | | | | | | | | | | | | | through ExtractElement. Summary: The computeKnownBits and ComputeNumSignBits functions in ValueTracking can now do a simple look-through of ExtractElement. Reviewers: majnemer, spatel Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24955 llvm-svn: 283434
* auto-generate checksSanjay Patel2016-09-161-2/+4
| | | | llvm-svn: 281756
* The patch improves ValueTracking on left shift with nsw flag.Evgeny Stupachenko2016-08-241-0/+55
| | | | | | | | | | | | Summary: The patch fixes PR28946. Reviewers: majnemer, sanjoy Differential Revision: http://reviews.llvm.org/D23296 From: Li Huang llvm-svn: 279684
* Remove missing file from r279433 reversalArtur Pilipenko2016-08-221-97/+0
| | | | llvm-svn: 279434
* Revert "[ValueTracking] Improve ValueTracking on left shift with nsw flag"Sanjoy Das2016-08-151-24/+0
| | | | | | This reverts commit r278172. It causes PR28946. llvm-svn: 278740
* [ValueTracking] An improvement to IR ValueTracking on Non-negative IntegersAndrew Kaylor2016-08-101-0/+97
| | | | | | | | Patch by Li Huang Differential Revision: https://reviews.llvm.org/D18777 llvm-svn: 278267
* [ValueTracking] Improve ValueTracking on left shift with nsw flagAndrew Kaylor2016-08-091-0/+24
| | | | | | | | Patch by Li Huang Differential Revison: https://reviews.llvm.org/D23296 llvm-svn: 278172
* Teach isDereferenceablePointer to look through returned-argument functionsHal Finkel2016-07-111-1/+4
| | | | | | | | | For functions which are known to return their argument, isDereferenceableAndAlignedPointer can examine the argument value. Differential Revision: http://reviews.llvm.org/D9384 llvm-svn: 275038
* Reduce dependence on pointee types when deducing dereferenceabilitySanjoy Das2016-06-011-0/+82
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Change some of the internal interfaces in Loads.cpp to keep track of the number of bytes we're trying to prove dereferenceable using an explicit `Size` parameter. Before this, the `Size` parameter was implicitly inferred from the pointee type of the pointer whose dereferenceability we were trying to prove, causing us to be conservative around bitcasts. This was unfortunate since bitcast instructions are no-ops and should never break optimizations. With an explicit `Size` parameter, we're more precise (as shown in the test cases), and the code is simpler. We should eventually move towards a `DerefQuery` struct that groups together a base pointer, an offset, a size and an alignment; but this patch is a first step. Reviewers: apilipenko, dblaikie, hfinkel, reames Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20764 llvm-svn: 271406
* Use DL preferred alignment for alloca in Value::getPointerAlignmentArtur Pilipenko2016-04-271-1/+7
| | | | | | | | | | Teach Value::getPointerAlignment that allocas with no explicit alignment are aligned to preferred alignment of the allocated type. Reviewed By: hfinkel Differential Revision: http://reviews.llvm.org/D17569 llvm-svn: 267689
* InstCombine: Restrict computeKnownBits() on all Values to OptLevel > 2Matthias Braun2016-03-091-5/+5
| | | | | | | | | | | | | | | | | | As part of r251146 InstCombine was extended to call computeKnownBits on every value in the function to determine whether it happens to be constant. This increases typical compiletime by 1-3% (5% in irgen+opt time) in my measurements. On the other hand this case did not trigger once in the whole llvm-testsuite. This patch introduces the notion of ExpensiveCombines which are only enabled for OptLevel > 2. I removed the check in InstructionSimplify as that is called from various places where the OptLevel is not known but given the rarity of the situation I think a check in InstCombine is enough. Differential Revision: http://reviews.llvm.org/D16835 llvm-svn: 263047
* [ValueTracking] Remove dead code from an old experimentPhilip Reames2016-03-032-62/+0
| | | | | | | | | | This experiment was originally about trying to use facts implied dominating conditions to infer more precise known bits. While the compile time was found to be acceptable on several large code bases, we never found sufficiently profitable examples to justify turning on the code by default. Given this, it's time to abandon the experiment. Several folks have commented that they've found this useful for experimentation, but nothing has come of those experiments. Given how easy the patch is to apply, there's no reason to leave the code in tree. For anyone interested in further investigation in this area, I recommend finding the summary email I sent on one of the original review threads. In particular, I now believe the use-list based approach is strictly worse than the dom-tree-walking approach. llvm-svn: 262646
* Revert "[ValueTracking] Understand more select patterns in ComputeKnownBits"James Molloy2016-01-141-62/+0
| | | | | | This reverts commit r257769. Backing this out because of stage2 failures. llvm-svn: 257773
* [ValueTracking] Understand more select patterns in ComputeKnownBitsJames Molloy2016-01-141-0/+62
| | | | | | | | | | | | | Some patterns of select+compare allow us to know exactly the value of the uppermost bits in the select result. For example: %b = icmp ugt i32 %a, 5 %c = select i1 %b, i32 2, i32 %a Here we know that %c is bounded by 5, and therefore KnownZero = ~APInt(5).getActiveBits() = ~7. There are several such patterns, and this patch attempts to understand a reasonable subset of them - namely when the base values are the same (as above), and when they are related by a simple (add nsw), for example (add nsw %a, 4) and %a. llvm-svn: 257769
* [ValueTracking] fix bug computing isKnownToBeAPowerOfTwo() with arithmetic ↵Sanjay Patel2015-12-301-0/+20
| | | | | | | | | | | | | | shift right (PR25900) This is a fix for: https://llvm.org/bugs/show_bug.cgi?id=25900 If we think that an arithmetic right shift of a power of two is always a power of two, an sdiv gets wrongly converted to udiv. Differential Revision: http://reviews.llvm.org/D15827 llvm-svn: 256655
* [gc.statepoint] Change gc.statepoint intrinsic's return type to token type ↵Chen Li2015-12-261-4/+4
| | | | | | | | | | | | | | instead of i32 type Summary: This patch changes gc.statepoint intrinsic's return type to token type instead of i32 type. Using token types could prevent LLVM to merge different gc.statepoint nodes into PHI nodes and cause further problems with gc relocations. The patch also changes the way on how gc.relocate and gc.result look for their corresponding gc.statepoint on unwind path. The current implementation uses the selector value extracted from a { i8*, i32 } landingpad as a hook to find the gc.statepoint, while the patch directly uses a token type landingpad (http://reviews.llvm.org/D15405) to find the gc.statepoint. Reviewers: sanjoy, JosephTremoulet, pgavlin, igor-laevsky, mjacob Subscribers: reames, mjacob, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D15662 llvm-svn: 256443
* [ValueTracking] Properly handle non-sized types in isAligned function.Michael Zolotukhin2015-12-211-0/+20
| | | | | | | | | | Reviewers: apilipenko, reames, sanjoy, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D15597 llvm-svn: 256192
* [ValueTracking] Use !range metadata more aggressively in KnownBitsSanjoy Das2015-10-281-0/+34
| | | | | | | | | | | | | | Summary: Teach `computeKnownBitsFromRangeMetadata` to use `!range` metadata more aggressively. Reviewers: majnemer, nlewycky, jingyue Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14100 llvm-svn: 251487
* [ValueTracking] Extend r251146 to catch a fairly common caseJames Molloy2015-10-261-0/+13
| | | | | | | | | | | | | Even though we may not know the value of the shifter operand, it's possible we know the shifter operand is non-zero. This can allow us to infer more known bits - for example: %1 = load %p !range {1, 5} %2 = shl %q, %1 We don't know %1, but we do know that it is nonzero so %2[0] is known zero, and importantly %2 is known non-zero. Calling isKnownNonZero is nontrivially expensive so use an Optional to run it lazily and cache its result. llvm-svn: 251294
* [ValueTracking] Add a new predicate: isKnownNonEqual()James Molloy2015-10-221-0/+21
| | | | | | | | | | | | | | isKnownNonEqual(A, B) returns true if it can be determined that A != B. At the moment it only knows two facts, that a non-wrapping add of nonzero to a value cannot be that value: A + B != A [where B != 0, addition is nsw or nuw] and that contradictory known bits imply two values are not equal. This patch also hooks this up to InstSimplify; InstSimplify had a peephole for the first fact but not the second so this teaches InstSimplify a new trick too (alas no measured performance impact!) llvm-svn: 251012
* [ValueTracking] Teach isKnownNonZero about monotonically increasing PHIsJames Molloy2015-09-291-0/+49
| | | | | | | | If a PHI starts at a non-negative constant, monotonically increases (only adds of a constant are supported at the moment) and that add does not wrap, then the PHI is known never to be zero. llvm-svn: 248796
* Introduce !align metadata for load instructionArtur Pilipenko2015-09-281-0/+8
| | | | | | | | Reviewed By: hfinkel Differential Revision: http://reviews.llvm.org/D12853 llvm-svn: 248721
OpenPOWER on IntegriCloud