summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/InstructionSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Remove duplicated code; NFCSanjoy Das2016-10-021-1/+1
| | | | | | | ICmpInst::makeConstantRange does exactly the same thing as ConstantRange::makeExactICmpRegion. llvm-svn: 283059
* [InstSimplify] allow or-of-icmps folds with vector splat constantsSanjay Patel2016-09-281-12/+11
| | | | llvm-svn: 282592
* [InstSimplify] allow and-of-icmps folds with vector splat constantsSanjay Patel2016-09-281-10/+9
| | | | llvm-svn: 282590
* move variables closer to their uses; add FIXMEs; NFCSanjay Patel2016-09-201-10/+10
| | | | llvm-svn: 281972
* Simplify code a bit. No functional change intended.Andrea Di Biagio2016-09-021-15/+16
| | | | | | | We don't need to call `GetCompareTy(LHS)' every single time true or false is returned from function SimplifyFCmpInst as suggested by Sanjay in review D24142. llvm-svn: 280491
* [instsimplify] Fix incorrect folding of an ordered fcmp with a vector of all ↵Andrea Di Biagio2016-09-021-1/+1
| | | | | | | | | | | | | | | | | | | | | | | NaN. This patch fixes a crash caused by an incorrect folding of an ordered comparison between a packed floating point vector and a splat vector of NaN. An ordered comparison between a vector and a constant vector of NaN, should always be folded into a constant vector where each element is i1 false. Since revision 266175, SimplifyFCmpInst folds the ordered fcmp into a scalar 'false'. Later on, this would cause an assertion failure, since the value type of the folded value doesn't match the expected value type of the uses of the original instruction: "Assertion failed: New->getType() == getType() && "replaceAllUses of value with new value of different type!". This patch fixes the issue and adds a test case to the already existing test InstSimplify/floating-point-compares.ll. Differential Revision: https://reviews.llvm.org/D24143 llvm-svn: 280488
* [InstSimplify] allow icmp with constant folds for splat vectors, part 2Sanjay Patel2016-08-231-83/+77
| | | | | | | | | | | | Completes the m_APInt changes for simplifyICmpWithConstant(). Other commits in this series: https://reviews.llvm.org/rL279492 https://reviews.llvm.org/rL279530 https://reviews.llvm.org/rL279534 https://reviews.llvm.org/rL279538 llvm-svn: 279543
* [InstSimplify] allow icmp with constant folds for splat vectors, part 1Sanjay Patel2016-08-231-6/+10
| | | | llvm-svn: 279538
* [InstSimplify] add helper function for SimplifyICmpInst(); NFCISanjay Patel2016-08-221-133/+143
| | | | | | | | | And add a FIXME because the helper excludes folds for vectors. It's not clear yet how many of these are actually testable (and therefore necessary?) because later analysis uses computeKnownBits and other methods to catch many of these cases. llvm-svn: 279492
* Replace "fallthrough" comments with LLVM_FALLTHROUGHJustin Bogner2016-08-171-5/+5
| | | | | | | This is a mechanical change of comments in switches like fallthrough, fall-through, or fall-thru to use the LLVM_FALLTHROUGH macro instead. llvm-svn: 278902
* [InstSimplify] Fold gep (gep V, C), (xor V, -1) to C-1David Majnemer2016-08-161-1/+7
| | | | llvm-svn: 278779
* Use range algorithms instead of unpacking begin/endDavid Majnemer2016-08-111-4/+4
| | | | | | No functionality change is intended. llvm-svn: 278417
* [InstSimplify] Fold gep (gep V, C), (sub 0, V) to CDavid Majnemer2016-08-071-0/+20
| | | | llvm-svn: 277952
* [InstSimplify] Try hard to simplify pointer comparisonsDavid Majnemer2016-08-071-0/+10
| | | | | | | Simplify ptrtoint comparisons involving operands with different source types. llvm-svn: 277951
* [InstCombine] use m_APInt to allow icmp eq (op X, Y), C folds for splat ↵Sanjay Patel2016-08-041-7/+6
| | | | | | | | | constant vectors I'm removing a misplaced pair of more specific folds from InstCombine in this patch as well, so we know where those folds are happening in InstSimplify. llvm-svn: 277738
* Reinstate "[CloneFunction] Don't remove side effecting calls"David Majnemer2016-08-041-2/+4
| | | | | | | This reinstates r277611 + r277614 and reverts r277642. A cast_or_null should have been a dyn_cast_or_null. llvm-svn: 277691
* Revert "[CloneFunction] Don't remove side effecting calls"Reid Kleckner2016-08-031-4/+2
| | | | | | | | | This reverts commit r277611 and the followup r277614. Bootstrap builds and chromium builds are crashing during inlining after this change. llvm-svn: 277642
* [CloneFunction] Don't remove side effecting callsDavid Majnemer2016-08-031-2/+4
| | | | | | | | | | | We were able to figure out that the result of a call is some constant. While propagating that fact, we added the constant to the value map. This is problematic because it results in us losing the call site when processing the value map. This fixes PR28802. llvm-svn: 277611
* [InstSimplify] Cast folding can be made more genericDavid Majnemer2016-07-261-46/+43
| | | | | | Use isEliminableCastPair to determine if a pair of casts are foldable. llvm-svn: 276777
* Reapply: [InstSimplify] Add support for bitcasts"David Majnemer2016-07-261-0/+29
| | | | | | | This reverts commit r276700 and reapplies r276698. The relevant clang tests have been updated. llvm-svn: 276727
* Revert "[InstSimplify] Add support for bitcasts"David Majnemer2016-07-251-29/+0
| | | | | | | This reverts commit r276698. Clang has tests which rely on the optimizer :( llvm-svn: 276700
* [InstSimplify] Add support for bitcastsDavid Majnemer2016-07-251-0/+29
| | | | | | | BitCasts of BitCasts can be folded away as can BitCasts which don't change the type of the operand. llvm-svn: 276698
* [InstSimplify] Fold trunc([zs]ext(%V)) -> %VDavid Majnemer2016-07-251-1/+7
| | | | | | Truncates can completely cancel out a zext or sext instruction. llvm-svn: 276604
* [InstSimplify] don't crash handling a pointer or aggregate typeSanjay Patel2016-07-211-0/+3
| | | | llvm-svn: 276345
* [InstSimplify] recognize trunc + icmp sgt/slt variants of select ↵Sanjay Patel2016-07-211-7/+33
| | | | | | | | | | | | | | | | | | simplifications (PR28466) rL245171 exposed a hole in InstSimplify that manifested in a strange way in PR28466: https://llvm.org/bugs/show_bug.cgi?id=28466 It's possible to use trunc + icmp sgt/slt in place of an and + icmp eq/ne, so we need to recognize that pattern to eliminate selects that are choosing between some value and some bitmasked version of that value. Note that there is significant room for improvement (refactoring) and enhancement (more patterns, possibly in InstCombine rather than here). Differential Revision: https://reviews.llvm.org/D22537 llvm-svn: 276341
* [InstSimplify][InstCombine] don't crash when folding vector selects of icmpSanjay Patel2016-07-201-1/+4
| | | | | | Differential Revision: https://reviews.llvm.org/D22602 llvm-svn: 276209
* refactor SimplifySelectInst; NFCISanjay Patel2016-07-181-97/+115
| | | | llvm-svn: 275911
* Simplify llvm.masked.load w/ undef masksDavid Majnemer2016-07-141-5/+21
| | | | | | | We can always pick the passthru value if the mask is undef: we are permitted to treat the mask as-if it were filled with zeros. llvm-svn: 275379
* Move a transform from InstCombine to InstSimplify.David Majnemer2016-07-131-0/+9
| | | | | | | This transform doesn't require any new instructions, it can safely live in InstSimplify. llvm-svn: 275344
* Pointer-comparison folding should look through returned-argument functionsHal Finkel2016-07-111-0/+5
| | | | | | | | | For functions which are known to return a specific argument, pointer-comparison folding can look through the function calls as part of its analysis. Differential Revision: http://reviews.llvm.org/D9387 llvm-svn: 275039
* Remove dead TLI arg of isKnownNonNull and propagate deadness. NFC.Sean Silva2016-07-021-4/+3
| | | | | | | | | | | | | | This actually uncovered a surprisingly large chain of ultimately unused TLI args. From what I can gather, this argument is a remnant of when isKnownNonNull would look at the TLI directly. The current approach seems to be that InferFunctionAttrs runs early in the pipeline and uses TLI to annotate the TLI-dependent non-null information as return attributes. This also removes the dependence of functionattrs on TLI altogether. llvm-svn: 274455
* [InstSimplify] Replace calls to null with undefDavid Majnemer2016-06-251-1/+2
| | | | | | | Calling null is undefined behavior, we can simplify the resulting value to undef. llvm-svn: 273777
* [InstSimplify] analyze (optionally casted) icmps to eliminate obviously ↵Sanjay Patel2016-06-201-4/+31
| | | | | | | | | | | | | | | false logic (PR27869) By moving this transform to InstSimplify from InstCombine, we sidestep the problem/question raised by PR27869: https://llvm.org/bugs/show_bug.cgi?id=27869 ...where InstCombine turns an icmp+zext into a shift causing us to miss the fold. Credit to David Majnemer for a draft patch of the changes to InstructionSimplify.cpp. Differential Revision: http://reviews.llvm.org/D21512 llvm-svn: 273200
* fix formatting, typo; NFCSanjay Patel2016-06-191-1/+1
| | | | llvm-svn: 273118
* IR: Introduce local_unnamed_addr attribute.Peter Collingbourne2016-06-141-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | If a local_unnamed_addr attribute is attached to a global, the address is known to be insignificant within the module. It is distinct from the existing unnamed_addr attribute in that it only describes a local property of the module rather than a global property of the symbol. This attribute is intended to be used by the code generator and LTO to allow the linker to decide whether the global needs to be in the symbol table. It is possible to exclude a global from the symbol table if three things are true: - This attribute is present on every instance of the global (which means that the normal rule that the global must have a unique address can be broken without being observable by the program by performing comparisons against the global's address) - The global has linkonce_odr linkage (which means that each linkage unit must have its own copy of the global if it requires one, and the copy in each linkage unit must be the same) - It is a constant or a function (which means that the program cannot observe that the unique-address rule has been broken by writing to the global) Although this attribute could in principle be computed from the module contents, LTO clients (i.e. linkers) will normally need to be able to compute this property as part of symbol resolution, and it would be inefficient to materialize every module just to compute it. See: http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160509/356401.html http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160516/356738.html for earlier discussion. Part of the fix for PR27553. Differential Revision: http://reviews.llvm.org/D20348 llvm-svn: 272709
* Avoid copies of std::strings and APInt/APFloats where we only read from itBenjamin Kramer2016-06-081-1/+1
| | | | | | | | As suggested by clang-tidy's performance-unnecessary-copy-initialization. This can easily hit lifetime issues, so I audited every change and ran the tests under asan, which came back clean. llvm-svn: 272126
* [InstSimplify] use computeKnownBits on shift amount operandsSanjay Patel2016-05-101-0/+16
| | | | | | | | | | | | | | Do simplifications common to all shift instructions based on the amount shifted: 1. If the shift amount is known larger than the bitwidth, the result is undefined. 2. If the valid bits of the shift amount are all known to be 0, it's a shift by zero, so the shift operand is the result. Note that we could generalize the shift-by-zero transform into a shift-by-constant if all of the valid bits in the shift amount are known, but that would have to be done in InstCombine rather than here because it would mean we need to create a new shift instruction. Differential Revision: http://reviews.llvm.org/D19874 llvm-svn: 269114
* Fold compares irrespective of whether allocation can be elidedAnna Thomas2016-05-031-5/+21
| | | | | | | | | | | | | | | | | | | Summary When a non-escaping pointer is compared to a global value, the comparison can be folded even if the corresponding malloc/allocation call cannot be elided. We need to make sure the global value is not null, since comparisons to null cannot be folded. In future, we should also handle cases when the the comparison instruction dominates the pointer escape. Reviewers: sanjoy Subscribers s.egerton, llvm-commits Differential Revision: http://reviews.llvm.org/D19549 llvm-svn: 268390
* Introduce llvm.load.relative intrinsic.Peter Collingbourne2016-04-221-0/+61
| | | | | | | | | | | | | | | | | | | This intrinsic takes two arguments, ``%ptr`` and ``%offset``. It loads a 32-bit value from the address ``%ptr + %offset``, adds ``%ptr`` to that value and returns it. The constant folder specifically recognizes the form of this intrinsic and the constant initializers it may load from; if a loaded constant initializer is known to have the form ``i32 trunc(x - %ptr)``, the intrinsic call is folded to ``x``. LLVM provides that the calculation of such a constant initializer will not overflow at link time under the medium code model if ``x`` is an ``unnamed_addr`` function. However, it does not provide this guarantee for a constant initializer folded into a function body. This intrinsic can be used to avoid the possibility of overflows when loading from such a constant. Differential Revision: http://reviews.llvm.org/D18367 llvm-svn: 267223
* Add optimization for 'icmp slt (or A, B), A' and some related idioms based ↵Nick Lewycky2016-04-211-15/+42
| | | | | | | | | | | | | | | | | | | | 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-6/+3
| | | | | | Phabricator Revision: http://reviews.llvm.org/D19277 llvm-svn: 266904
* [ValueTracking] Improve isImpliedCondition for conditions with matching ↵Chad Rosier2016-04-191-6/+12
| | | | | | | | | | | | | | | 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
* [InstCombine] We folded an fcmp to an i1 instead of a vector of i1David Majnemer2016-04-131-12/+19
| | | | | | | | | Remove an ad-hoc transform in InstCombine and replace it with more general machinery (ValueTracking, InstructionSimplify and VectorUtils). This fixes PR27332. llvm-svn: 266175
* Don't IPO over functions that can be de-refinedSanjoy Das2016-04-081-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Minor code cleanups. NFC.Junmo Park2016-04-051-2/+2
| | | | llvm-svn: 265468
* [InstSimplify] Restore fsub 0.0, (fsub 0.0, X) ==> X optznBenjamin Kramer2016-02-291-1/+1
| | | | | | | I accidentally removed this in r262212 but there was no test coverage to detect it. llvm-svn: 262215
* [InstSimplify] fsub 0.0, (fsub -0.0, X) ==> X is only safe if signed zeros ↵Benjamin Kramer2016-02-291-7/+8
| | | | | | | | are ignored. Only allow fsub -0.0, (fsub -0.0, X) ==> X without nsz. PR26746. llvm-svn: 262212
* [opaque pointer types] [NFC] Add an explicit type argument to ↵Eduard Burtescu2016-01-221-1/+1
| | | | | | | | | | | | ConstantFoldLoadFromConstPtr. Reviewers: mjacob, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D16418 llvm-svn: 258472
* [InstCombine] Simplify (x >> y) <= xDavid Majnemer2016-01-211-2/+4
| | | | | | | | | | | | This commit extends the patterns recognised by InstSimplify to also handle (x >> y) <= x in the same way as (x /u y) <= x. The missing optimisation was found investigating why LLVM did not optimise away bound checks in a binary search: https://github.com/rust-lang/rust/pull/30917 Patch by Andrea Canciani! Differential Revision: http://reviews.llvm.org/D16402 llvm-svn: 258422
* Change ConstantFoldInstOperands to take Instruction instead of opcode and ↵Manuel Jacob2016-01-211-2/+1
| | | | | | | | | | | | | | | | | | | | | type. NFC. Summary: The previous form, taking opcode and type, is moved to an internal helper and the new form, taking an instruction, is a wrapper around this helper. Although this is a slight cleanup on its own, the main motivation is to refactor the constant folding API to ease migration to opaque pointers. This will be follow-up work. Reviewers: eddyb Subscribers: dblaikie, llvm-commits Differential Revision: http://reviews.llvm.org/D16383 llvm-svn: 258391
OpenPOWER on IntegriCloud