summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ValueTracking.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Have isKnownNotFullPoison be smarter around control flowSanjoy Das2016-04-221-14/+32
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: (... while still not using a PostDomTree) The way we use isKnownNotFullPoison from SCEV today, the new CFG walking logic will not trigger for any realistic cases -- it will kick in only for situations where we could have merged the contiguous basic blocks anyway[0], since the poison generating instruction dominates all of its non-PHI uses (which are the only uses we consider right now). However, having this change in place will allow a later bugfix to break fewer llvm-lit tests. [0]: i.e. cases where block A branches to block B and B is A's only successor and A is B's only predecessor. Reviewers: broune, bjarke.roune Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D19212 llvm-svn: 267175
* Address Philip's post-commit feedback for r266987. NFC.Chad Rosier2016-04-211-2/+2
| | | | llvm-svn: 266998
* Refactor implied condition logic from ValueTracking directly into CmpInst. NFC.Chad Rosier2016-04-211-52/+2
| | | | | | Differential Revision: http://reviews.llvm.org/D19330 llvm-svn: 266987
* Add optimization for 'icmp slt (or A, B), A' and some related idioms based ↵Nick Lewycky2016-04-211-28/+8
| | | | | | | | | | | | | | | | | | | | on knowledge of the sign bit for A and B. No matter what value you OR in to A, the result of (or A, B) is going to be UGE A. When A and B are positive, it's SGE too. If A is negative, OR'ing a value into it can't make it positive, but can increase its value closer to -1, therefore (or A, B) is SGE A. Working through all possible combinations produces this truth table: ``` A is +, -, +/- F F F + B is T F ? - ? F ? +/- ``` The related optimizations are flipping the 'slt' for 'sge' which always NOTs the result (if the result is known), and swapping the LHS and RHS while swapping the comparison predicate. There are more idioms left to implement (aren't there always!) but I've stopped here because any more would risk becoming unreasonable for reviewers. llvm-svn: 266939
* [ValueTracking] Make isImpliedCondition return an Optional<bool>. NFC.Chad Rosier2016-04-201-61/+52
| | | | | | Phabricator Revision: http://reviews.llvm.org/D19277 llvm-svn: 266904
* [ValueTracking, VectorUtils] Refactor getIntrinsicIDForCallDavid Majnemer2016-04-191-2/+149
| | | | | | | | | | | | | The functionality contained within getIntrinsicIDForCall is two-fold: it checks if a CallInst's callee is a vectorizable intrinsic. If it isn't an intrinsic, it attempts to map the call's target to a suitable intrinsic. Move the mapping functionality into getIntrinsicForCallSite and rename getIntrinsicIDForCall to getVectorIntrinsicIDForCall while reimplementing it in terms of getIntrinsicForCallSite. llvm-svn: 266801
* [ValueTracking] Improve isImpliedCondition for conditions with matching ↵Chad Rosier2016-04-191-5/+99
| | | | | | | | | | | | | | | operands. This patch improves SimplifyCFG to catch cases like: if (a < b) { if (a > b) <- known to be false unreachable; } Phabricator Revision: http://reviews.llvm.org/D18905 llvm-svn: 266767
* Simplify strlen to a subtraction for certain cases.David L Kreitzer2016-04-131-13/+21
| | | | | | | | Patch by Li Huang (li1.huang@intel.com) Differential Revision: http://reviews.llvm.org/D18230 llvm-svn: 266200
* [InstCombine] We folded an fcmp to an i1 instead of a vector of i1David Majnemer2016-04-131-51/+50
| | | | | | | | | Remove an ad-hoc transform in InstCombine and replace it with more general machinery (ValueTracking, InstructionSimplify and VectorUtils). This fixes PR27332. llvm-svn: 266175
* This reverts commit r265913 and r265912Sanjoy Das2016-04-111-61/+0
| | | | | | | | | See PR27315 r265913: "[IndVars] Eliminate op.with.overflow when possible" r265912: "[SCEV] See through op.with.overflow intrinsics" llvm-svn: 265950
* [SCEV] See through op.with.overflow intrinsicsSanjoy Das2016-04-101-0/+61
| | | | | | | | | | | | | | | Summary: This change teaches SCEV to see reduce `(extractvalue 0 (op.with.overflow X Y))` into `op X Y` (with a no-wrap tag if possible). Reviewers: atrick, regehr Subscribers: mcrosier, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D18684 llvm-svn: 265912
* Don't IPO over functions that can be de-refinedSanjoy Das2016-04-081-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Fixes PR26774. If you're aware of the issue, feel free to skip the "Motivation" section and jump directly to "This patch". Motivation: I define "refinement" as discarding behaviors from a program that the optimizer has license to discard. So transforming: ``` void f(unsigned x) { unsigned t = 5 / x; (void)t; } ``` to ``` void f(unsigned x) { } ``` is refinement, since the behavior went from "if x == 0 then undefined else nothing" to "nothing" (the optimizer has license to discard undefined behavior). Refinement is a fundamental aspect of many mid-level optimizations done by LLVM. For instance, transforming `x == (x + 1)` to `false` also involves refinement since the expression's value went from "if x is `undef` then { `true` or `false` } else { `false` }" to "`false`" (by definition, the optimizer has license to fold `undef` to any non-`undef` value). Unfortunately, refinement implies that the optimizer cannot assume that the implementation of a function it can see has all of the behavior an unoptimized or a differently optimized version of the same function can have. This is a problem for functions with comdat linkage, where a function can be replaced by an unoptimized or a differently optimized version of the same source level function. For instance, FunctionAttrs cannot assume a comdat function is actually `readnone` even if it does not have any loads or stores in it; since there may have been loads and stores in the "original function" that were refined out in the currently visible variant, and at the link step the linker may in fact choose an implementation with a load or a store. As an example, consider a function that does two atomic loads from the same memory location, and writes to memory only if the two values are not equal. The optimizer is allowed to refine this function by first CSE'ing the two loads, and the folding the comparision to always report that the two values are equal. Such a refined variant will look like it is `readonly`. However, the unoptimized version of the function can still write to memory (since the two loads //can// result in different values), and selecting the unoptimized version at link time will retroactively invalidate transforms we may have done under the assumption that the function does not write to memory. Note: this is not just a problem with atomics or with linking differently optimized object files. See PR26774 for more realistic examples that involved neither. This patch: This change introduces a new set of linkage types, predicated as `GlobalValue::mayBeDerefined` that returns true if the linkage type allows a function to be replaced by a differently optimized variant at link time. It then changes a set of IPO passes to bail out if they see such a function. Reviewers: chandlerc, hfinkel, dexonsmith, joker.eph, rnk Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D18634 llvm-svn: 265762
* Mark some FP intrinsics as safe to speculatively executePeter Zotov2016-04-031-4/+16
| | | | | | | | | | | | | | | | | | Floating point intrinsics in LLVM are generally not speculatively executed, since most of them are defined to behave the same as libm functions, which set errno. However, the only error that can happen when executing ceil, floor, nearbyint, rint and round libm functions per POSIX.1-2001 is -ERANGE, and that requires the maximum value of the exponent to be smaller than the number of mantissa bits, which is not the case with any of the floating point types supported by LLVM. The trunc and copysign functions never set errno per per POSIX.1-2001. Differential Revision: http://reviews.llvm.org/D18643 llvm-svn: 265262
* [InstCombine] Fix incorrect rule from rL236202Sanjoy Das2016-03-311-1/+2
| | | | | | | The rule for SMIN introduced in rL236202 doesn't work as advertised: the check for Pred == ICmpInst::ICMP_SGT was missing. llvm-svn: 264996
* Delete trailing whitespaceSanjoy Das2016-03-311-1/+1
| | | | llvm-svn: 264995
* [ValueTracking] Extract isKnownPositive [NFCI]Philip Reames2016-03-091-0/+12
| | | | | | Extract out a generic interface from a recently landed patch and document a TODO in case compile time becomes a problem. llvm-svn: 263062
* [ValueTracking] "constant fold" an experimental hidden optionPhilip Reames2016-03-031-7/+0
| | | | llvm-svn: 262648
* [ValueTracking] Remove dead code from an old experimentPhilip Reames2016-03-031-208/+2
| | | | | | | | | | 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
* NFC. Move isDereferenceable to Loads.h/cppArtur Pilipenko2016-02-241-202/+1
| | | | | | | | | | This is a part of the refactoring to unify isSafeToLoadUnconditionally and isDereferenceablePointer functions. In subsequent change I'm going to eliminate isDerferenceableAndAlignedPointer from Loads API, leaving isSafeToLoadSpecualtively the only function to check is load instruction can be speculated. Reviewed By: hfinkel Differential Revision: http://reviews.llvm.org/D16180 llvm-svn: 261736
* NFC. Move getAlignment helper function from ValueTracking to Value class. Artur Pilipenko2016-02-241-42/+2
| | | | | | | | Reviewed By: reames, hfinkel Differential Revision: http://reviews.llvm.org/D16144 llvm-svn: 261735
* Remove uses of builtin comma operator.Richard Trieu2016-02-181-3/+6
| | | | | | Cleanup for upcoming Clang warning -Wcomma. No functionality change intended. llvm-svn: 261270
* [ValueTracking] Improve isKnownNonZero for PHI of non-zero constantsJun Bum Lim2016-02-011-0/+6
| | | | | | It is clear that a PHI is a non-zero if all incoming values are non-zero constants. llvm-svn: 259370
* ValueTracking: Use fixed array for assumption exclude set in Query.Matthias Braun2016-01-281-15/+27
| | | | | | | | | | | | The Query structure is constructed often and is relevant for compiletime performance. We can replace the SmallPtrSet for assumption exclusions in this structure with a fixed size array because we know the maximum number of elements. This improves typical clang -O3 -emit-llvm compiletime by 1.2% in my measurements. Differential Revision: http://reviews.llvm.org/D16204 llvm-svn: 259025
* [opaque pointer types] [NFC] GEP: replace get(Pointer)ElementType uses with ↵Eduard Burtescu2016-01-191-6/+4
| | | | | | | | | | | | | | | | | | get{Source,Result}ElementType. Summary: GEPOperator: provide getResultElementType alongside getSourceElementType. This is made possible by adding a result element type field to GetElementPtrConstantExpr, which GetElementPtrInst already has. GEP: replace get(Pointer)ElementType uses with get{Source,Result}ElementType. Reviewers: mjacob, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D16275 llvm-svn: 258145
* [opaque pointer types] Alloca: use getAllocatedType() instead of ↵Eduard Burtescu2016-01-181-1/+1
| | | | | | | | | | | | getType()->getPointerElementType(). Reviewers: mjacob Subscribers: llvm-commits, dblaikie Differential Revision: http://reviews.llvm.org/D16272 llvm-svn: 258028
* GlobalValue: use getValueType() instead of getType()->getPointerElementType().Manuel Jacob2016-01-161-1/+1
| | | | | | | | | | | | Reviewers: mjacob Subscribers: jholewinski, arsenm, dsanders, dblaikie Patch by Eduard Burtescu. Differential Revision: http://reviews.llvm.org/D16260 llvm-svn: 257999
* ValueTracking: Put DataLayout reference into the Query structure, NFC.Matthias Braun2016-01-151-257/+250
| | | | | | | | | It looks nicer and improves the compiletime of a typical clang -O3 -emit-llvm run by ~0.6% for me. Differential Revision: http://reviews.llvm.org/D16205 llvm-svn: 257944
* Revert "[ValueTracking] Understand more select patterns in ComputeKnownBits"James Molloy2016-01-141-39/+1
| | | | | | This reverts commit r257769. Backing this out because of stage2 failures. llvm-svn: 257773
* [ValueTracking] Understand more select patterns in ComputeKnownBitsJames Molloy2016-01-141-1/+39
| | | | | | | | | | | | | 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
* CannotBeOrderedLessThanZero: add some missing casesFiona Glaser2016-01-121-0/+12
| | | | llvm-svn: 257542
* [Statepoints] Refactor GCRelocateOperands into an intrinsic wrapper. NFC.Manuel Jacob2016-01-051-6/+3
| | | | | | | | | | | | | | | Summary: This commit renames GCRelocateOperands to GCRelocateInst and makes it an intrinsic wrapper, similar to e.g. MemCpyInst. Also, all users of GCRelocateOperands were changed to use the new intrinsic wrapper instead. Reviewers: sanjoy, reames Subscribers: reames, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D15762 llvm-svn: 256811
* [MemoryBuiltins] Remove isOperatorNewLike by consolidating non-null ↵Philip Reames2016-01-041-4/+0
| | | | | | | | | | | | inference handling This patch removes the isOperatorNewLike predicate since it was only being used to establish a non-null return value and we have attributes specifically for that purpose with generic handling. To keep approximate the same behaviour for existing frontends, I added the various operator new like (i.e. instances of operator new) to InferFunctionAttrs. It's not really clear to me why this isn't handled in Clang, but I didn't want to break existing code and any subtle assumptions it might have. Once this patch is in, I'm going to start separating the isAllocLike family of predicates. These appear to be being used for a mixture of things which should be more clearly separated and documented. Today, they're being used to indicate (at least) aliasing facts, CSE-ability, and default values from an allocation site. Differential Revision: http://reviews.llvm.org/D15820 llvm-svn: 256787
* Fix a horrible infloop in value tracking in the face of dead code.Chandler Carruth2016-01-041-1/+6
| | | | | | | | | | | | | | | Amazingly, we just never triggered this without: 1) Moving code around for MetadataTracking so that a certain *different* amount of inlining occurs in the per-TU compile step. 2) Then you LTO opt or clang with a bootstrap, and get inlining, loop opts, and GVN line up everything *just* right. I don't really know how we didn't hit this before. We really need to be fuzz testing stuff, it shouldn't be hard to trigger. I'm working on crafting a reduced nice test case, and will submit that when I have it, but I want to get LTO build bots going again. llvm-svn: 256735
* [ValueTracking] fix bug computing isKnownToBeAPowerOfTwo() with arithmetic ↵Sanjay Patel2015-12-301-2/+3
| | | | | | | | | | | | | | 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
* [ValueTracking] Properly handle non-sized types in isAligned function.Michael Zolotukhin2015-12-211-1/+5
| | | | | | | | | | Reviewers: apilipenko, reames, sanjoy, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D15597 llvm-svn: 256192
* [IR] Remove terminatepadDavid Majnemer2015-12-141-1/+0
| | | | | | | | | | | | | It turns out that terminatepad gives little benefit over a cleanuppad which calls the termination function. This is not sufficient to implement fully generic filters but MSVC doesn't support them which makes terminatepad a little over-designed. Depends on D15478. Differential Revision: http://reviews.llvm.org/D15479 llvm-svn: 255522
* [IR] Reformulate LLVM's EH funclet IRDavid Majnemer2015-12-121-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | While we have successfully implemented a funclet-oriented EH scheme on top of LLVM IR, our scheme has some notable deficiencies: - catchendpad and cleanupendpad are necessary in the current design but they are difficult to explain to others, even to seasoned LLVM experts. - catchendpad and cleanupendpad are optimization barriers. They cannot be split and force all potentially throwing call-sites to be invokes. This has a noticable effect on the quality of our code generation. - catchpad, while similar in some aspects to invoke, is fairly awkward. It is unsplittable, starts a funclet, and has control flow to other funclets. - The nesting relationship between funclets is currently a property of control flow edges. Because of this, we are forced to carefully analyze the flow graph to see if there might potentially exist illegal nesting among funclets. While we have logic to clone funclets when they are illegally nested, it would be nicer if we had a representation which forbade them upfront. Let's clean this up a bit by doing the following: - Instead, make catchpad more like cleanuppad and landingpad: no control flow, just a bunch of simple operands; catchpad would be splittable. - Introduce catchswitch, a control flow instruction designed to model the constraints of funclet oriented EH. - Make funclet scoping explicit by having funclet instructions consume the token produced by the funclet which contains them. - Remove catchendpad and cleanupendpad. Their presence can be inferred implicitly using coloring information. N.B. The state numbering code for the CLR has been updated but the veracity of it's output cannot be spoken for. An expert should take a look to make sure the results are reasonable. Reviewers: rnk, JosephTremoulet, andrew.w.kaylor Differential Revision: http://reviews.llvm.org/D15139 llvm-svn: 255422
* [ValueTracking] Remove untested / unreachable code, NFCSanjoy Das2015-11-111-18/+5
| | | | | | | | Right now isTruePredicate is only ever called with Pred == ICMP_SLE or ICMP_ULE, and the ICMP_SLT and ICMP_ULT cases are dead. This change removes the untested dead code so that the function is not misleading. llvm-svn: 252676
* [ValueTracking] Teach isImpliedCondition a new bitwise trickSanjoy Das2015-11-101-0/+30
| | | | | | | | | | | | | | | | | | | Summary: This change teaches isImpliedCondition to prove things like (A | 15) < L ==> (A | 14) < L if the low 4 bits of A are known to be zero. Depends on D14391 Reviewers: majnemer, reames, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14392 llvm-svn: 252673
* [ValueTracking] Use m_APInt instead of m_ConstantInt, NFCSanjoy Das2015-11-101-7/+8
| | | | | | | | This change would add functionality if isImpliedCondition worked on vector types; but since it bail out on vector predicates this change is an NFC. llvm-svn: 252672
* [ValueTracking] Recognize that and(x, add (x, -1)) clears the low bitPhilip Reames2015-11-101-0/+16
| | | | | | | | | | This is a cleaned up version of a patch by John Regehr with permission. Originally found via the souper tool. If we add an odd number to x, then bitwise-and the result with x, we know that the low bit of the result must be zero. Either it was zero in x originally, or the add cleared it in the temporary value. As a result, one of the two values anded together must have the bit cleared. Differential Revision: http://reviews.llvm.org/D14315 llvm-svn: 252629
* [ValueTracking] Add parameters to isImpliedCondition; NFCSanjoy Das2015-11-061-8/+22
| | | | | | | | | | | | | | | | Summary: This change makes the `isImpliedCondition` interface similar to the rest of the functions in ValueTracking (in that it takes a DataLayout, AssumptionCache etc.). This is an NFC, intended to make a later diff less noisy. Depends on D14369 Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14391 llvm-svn: 252333
* [ValueTracking] De-pessimize isImpliedCondition around unsigned comparesSanjoy Das2015-11-061-4/+4
| | | | | | | | | | | | | | | Summary: Currently `isImpliedCondition` will optimize "I +_nuw C < L ==> I < L" only if C is positive. This is an unnecessary restriction -- the implication holds even if `C` is negative. Reviewers: reames, majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14369 llvm-svn: 252332
* [ValueTracking] Add a framework for encoding implication rulesSanjoy Das2015-11-061-21/+67
| | | | | | | | | | | | | | | | | | | | | Summary: This change adds a framework for adding more smarts to `isImpliedCondition` around inequalities. Informally, `isImpliedCondition` will now try to prove "A < B ==> C < D" by proving "C <= A && B <= D", since then it follows "C <= A < B <= D". While this change is in principle NFC, I could not think of a way to not handle cases like "i +_nsw 1 < L ==> i < L +_nsw 1" (that ValueTracking did not handle before) while keeping the change understandable. I've added tests for these cases. Reviewers: reames, majnemer, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14368 llvm-svn: 252331
* [ValueTracking] Expose `implies` via ValueTracking, NFCSanjoy Das2015-10-281-0/+40
| | | | | | | | | | | | Summary: This will allow a later patch to `JumpThreading` use this functionality. Reviewers: reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13971 llvm-svn: 251488
* [ValueTracking] Use !range metadata more aggressively in KnownBitsSanjoy Das2015-10-281-9/+15
| | | | | | | | | | | | | | 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] Don't special case wrapped ConstantRanges; NFCISanjoy Das2015-10-271-3/+1
| | | | | | | | | | | | | | | | | | | Use `getUnsignedMax` directly instead of special casing a wrapped ConstantRange. The previous code would have been "buggy" (and this would have been a semantic change) if LLVM allowed !range metadata to denote full ranges. E.g. in %val = load i1, i1* %ptr, !range !{i1 1, i1 1} ;; == full set ValueTracking would conclude that the high bit (IOW the only bit) in %val was zero. Since !range metadata does not allow empty or full ranges, this change is just a minor stylistic improvement. llvm-svn: 251380
* [ValueTracking] Extend r251146 to catch a fairly common caseJames Molloy2015-10-261-2/+22
| | | | | | | | | | | | | 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
* Use all_of to simplify control flow. NFC.Benjamin Kramer2015-10-241-8/+2
| | | | llvm-svn: 251202
* Extract out getConstantRangeFromMetadata; NFCSanjoy Das2015-10-241-0/+22
| | | | | | | | | | | | The loop idiom creating a ConstantRange is repeated twice in the codebase, time to give it a name and a home. The loop is also repeated in `rangeMetadataExcludesValue`, but using `getConstantRangeFromMetadata` there would not be an NFC -- the range returned by `getConstantRangeFromMetadata` may contain a value that none of the subranges did. llvm-svn: 251180
OpenPOWER on IntegriCloud