summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [LVI] Add an API to LazyValueInfo so that it can export ConstantRangesJohn Regehr2016-05-021-0/+16
| | | | | | | | | that it computes. Currently this is used for testing and precision tuning, but it might be used by optimizations later. Differential Revision: http://reviews.llvm.org/D19179 llvm-svn: 268291
* [CFLAA] Fix a use-of-invalid-pointer bug.George Burgess IV2016-05-021-1/+6
| | | | | | | | | | | | As shown in the diff, we used to add to CFLAA's cache by doing `Cache[Fn] = buildSetsFrom(Fn)`. `buildSetsFrom(Fn)` may cause `Cache` to reallocate its underlying storage, if this happens and `Cache[Fn]` was evaluated prior to `buildSetsFrom(Fn)`, then we'll store the result to a bad address. Patch by Jia Chen. llvm-svn: 268269
* Fixed MSVC 'not all control paths return a value' warningSimon Pilgrim2016-05-011-0/+1
| | | | llvm-svn: 268198
* [SCEV] When printing via -analysis, dump loop dispositionSanjoy Das2016-05-011-0/+25
| | | | | | | | | | | There are currently some bugs in tree around SCEV caching an incorrect loop disposition. Printing out loop dispositions will let us write whitebox tests as those are fixed. The dispositions are printed as a list in "inside out" order, i.e. innermost loop first. llvm-svn: 268177
* [ValueTracking] Make the code in lookThroughCastDavid Majnemer2016-04-291-16/+9
| | | | | | No functionality change is intended. llvm-svn: 268108
* [InstCombine] Determine the result of a select based on a dominating condition.Chad Rosier2016-04-291-1/+4
| | | | | | Differential Revision: http://reviews.llvm.org/D19550 llvm-svn: 268104
* [ValueTracking] matchSelectPattern needs to be more careful around FPDavid Majnemer2016-04-291-19/+31
| | | | | | | | | | | | matchSelectPattern attempts to see through casts which mask min/max patterns from being more obvious. Under certain circumstances, it would misidentify a sequence of instructions as a min/max because it assumed that folding casts would preserve the result. This is not the case for floating point <-> integer casts. This fixes PR27575. llvm-svn: 268086
* [BasicAA] Treat llvm.assume as not accessing memory in ↵Geoff Berry2016-04-291-0/+6
| | | | | | | | | | | | getModRefBehavior(Function) Reviewers: dberlin, chandlerc, hfinkel, reames, sanjoy Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D19730 llvm-svn: 268068
* Unify XDEBUG and EXPENSIVE_CHECKS (into the latter), and add an option to ↵Filipe Cabecinhas2016-04-292-2/+2
| | | | | | | | | | | | | | | | | | | the cmake build to enable them. Summary: Historically, we had a switch in the Makefiles for turning on "expensive checks". This has never been ported to the cmake build, but the (dead-ish) code is still around. This will also make it easier to turn it on in buildbots. Reviewers: chandlerc Subscribers: jyknight, mzolotukhin, RKSimon, gberry, llvm-commits Differential Revision: http://reviews.llvm.org/D19723 llvm-svn: 268050
* DivergenceAnalysis: Fix crash with unreachable blocksMatt Arsenault2016-04-291-0/+5
| | | | | | | Unreachable blocks may not be in the dominator tree, so don't crash on them. llvm-svn: 268001
* [Inliner] Formatting. NFC.Chad Rosier2016-04-281-36/+41
| | | | | | | Patch by Aditya Kumar! Differential Revision: http://reviews.llvm.org/D19047 llvm-svn: 267888
* [TLI] Unify LibFunc signature checking. NFCI.Ahmed Bougacha2016-04-274-96/+560
| | | | | | | | | I tried to be as close as possible to the strongest check that existed before; cleaning these up properly is left for future work. Differential Revision: http://reviews.llvm.org/D19469 llvm-svn: 267758
* [TLI] Fix indentation. NFC.Ahmed Bougacha2016-04-271-1/+1
| | | | llvm-svn: 267757
* [TTI] Add hook for vector extract with extensionMatthew Simpson2016-04-271-0/+8
| | | | | | | | | | | | | | | This change adds a new hook for estimating the cost of vector extracts followed by zero- and sign-extensions. The motivating example for this change is the SMOV and UMOV instructions on AArch64. These instructions move data from vector to general purpose registers while performing the corresponding extension (sign-extend for SMOV and zero-extend for UMOV) at the same time. For these operations, TargetTransformInfo can assume the extensions are free and only report the cost of the vector extract. The SLP vectorizer has been updated to make use of the new hook. Differential Revision: http://reviews.llvm.org/D18523 llvm-svn: 267725
* [ThinLTO] Refine fix to avoid renaming of uses in inline assembly.Teresa Johnson2016-04-271-6/+14
| | | | | | | | | | | | | | | | | Summary: Refine the workaround from r266877 that attempts to prevent renaming of locals in inline assembly, so that in addition to looking for a llvm.used local value, that there is at least one inline assembly call in the module. Otherwise, debug functions added to the llvm.used can block importing/exporting unnecessarily. Reviewers: joker.eph Subscribers: llvm-commits, joker.eph Differential Revision: http://reviews.llvm.org/D19573 llvm-svn: 267717
* NFC. Introduce Value::getPointerDerferecnceableBytesArtur Pilipenko2016-04-271-27/+2
| | | | | | | | | | Extract a part of isDereferenceableAndAlignedPointer functionality to Value::getPointerDerferecnceableBytes. Currently it's a NFC, but in future I'm going to accumulate all the logic about value dereferenceability in this function similarly to Value::getPointerAlignment function (D16144). Reviewed By: reames Differential Revision: http://reviews.llvm.org/D17572 llvm-svn: 267708
* isSafeToLoadUnconditionally support queries without a contextArtur Pilipenko2016-04-271-3/+6
| | | | | | | | | | This is required to use this function from isSafeToSpeculativelyExecute Reviewed By: hfinkel Differential Revision: http://reviews.llvm.org/D16231 llvm-svn: 267692
* [LVI] Delete stale and misleading comment.Philip Reames2016-04-271-5/+0
| | | | llvm-svn: 267661
* [LVI] Add a comment explaining a subtle piece of codePhilip Reames2016-04-271-15/+23
| | | | | | Or at least, I didn't understand the implications the first several times I read it it. llvm-svn: 267648
* [LVI] Reduce compile time by lazily scanning blocks if neededPhilip Reames2016-04-271-26/+26
| | | | | | | | | | When encountering a non-local pointer, LVI would eagerly scan the block for dereferences of the given object to prove the pointer to be non null. That's all well and good, but *then* we'd go recurse through our input blocks. As a result, we could end up scanning each and every block we traverse, even if the final definition was obviously non null or we found a constant value somewhere up the chain. The previous code papered over this by using the isKnownNonNull routine from value tracking. This made the duplication less painful in the common case. Instead, we know do the block scan only *after* we've gotten the recursive results back. This lets us stop scanning individual blocks as soon as we've determined it to be non-null in any predecessor block and use our usual merge rules to propagate that information cheaply through successor blocks. For a pointer which can be found non-null, this does strictly less work and sometimes substaintially so. Note that the case where we *can't* prove something non-null is still the really expensive case. We end up scanning each and every block looking for a dereference and never end up finding one. llvm-svn: 267642
* [LVI] Cut short search if we know we can't return a useful resultPhilip Reames2016-04-261-9/+44
| | | | | | Previously we were recursing on our operands for unary and binary operators regardless of whether we knew how to reason about the operator in question. This has the effect of doing a potentially large amount of work, only to throw it away. By checking whether the operation is one LVI can handle, we can cut short the search and return the (overdefined) answer more quickly. The quality of the results produced should not change. llvm-svn: 267626
* [LVI] Apply transfer rule for overdefine inputs for binary operatorsPhilip Reames2016-04-261-11/+16
| | | | | | | | As pointed out by John Regehr over in http://reviews.llvm.org/D19485, LVI was being incredibly stupid about applying its transfer rules. Rather than gathering local facts from the expression itself, it was simply giving up entirely if one of the inputs was overdefined. This greatly impacts the precision of the overall analysis and makes it far more fragile as well. This patch builds on 267609 which did the same thing for unary casts. llvm-svn: 267620
* [LVI] A better fix for the assertion error introduced by 267609Philip Reames2016-04-261-10/+11
| | | | | | Essentially, I was using the wrong size function. For types which were sized, but not primitive, I wasn't getting a useful size for the operand and failed an assert. I fixed this, and also added a guard that the input is a sized type. Test case is for the original mistake. I'm not sure how to actually exercise the sized type check. llvm-svn: 267618
* [LVI] Speculative fix for assertion seen in clang botsPhilip Reames2016-04-261-0/+6
| | | | | | I'll clean this up and add a test case shortly. I want to make sure this does actually fix the bots; if not, I'll revert. llvm-svn: 267617
* [LVI] Infer local facts from unary expressionsPhilip Reames2016-04-261-16/+20
| | | | | | | | | | As pointed out by John Regehr over in http://reviews.llvm.org/D19485, LVI was being incredibly stupid about applying its transfer rules. Rather than gathering local facts from the expression itself, it was simply giving up entirely if one of the inputs was overdefined. This greatly impacts the precision of the overall analysis and makes it far more fragile as well. This patch implements only the unary operation case. Once this is in, I'll implement the same for the binary operations. Differential Revision: http://reviews.llvm.org/D19492 llvm-svn: 267609
* [LVI] Make a precondition explicit rather than handling a case which never ↵Philip Reames2016-04-251-1/+2
| | | | | | happens [NFC] llvm-svn: 267481
* [LVI] Clarify comments describing the lattice valuesPhilip Reames2016-04-251-5/+10
| | | | | | There has been much recent confusion about the partition in the lattice between constant and non-constant values. Hopefully, documenting this will prevent confusion going forward. llvm-svn: 267440
* [LVI] Split solveBlockValueConstantRange into two [NFC]Philip Reames2016-04-251-31/+63
| | | | | | This function handled both unary and binary operators. Cloning and specializing leads to much easier to follow code with minimal duplicatation. llvm-svn: 267438
* [ValueTracking] Improve isImpliedCondition when the dominating cond is false.Chad Rosier2016-04-251-3/+6
| | | | llvm-svn: 267430
* [SCEV] Improve the run-time checking of the NoWrap predicateSilviu Baranga2016-04-251-19/+63
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This implements a new method of run-time checking the NoWrap SCEV predicates, which should be easier to optimize and nicer for targets that don't correctly handle multiplication/addition of large integer types (like i128). If the AddRec is {a,+,b} and the backedge taken count is c, the idea is to check that |b| * c doesn't have unsigned overflow, and depending on the sign of b, that: a + |b| * c >= a (b >= 0) or a - |b| * c <= a (b <= 0) where the comparisons above are signed or unsigned, depending on the flag that we're checking. The advantage of doing this is that we avoid extending to a larger type and we avoid the multiplication of large types (multiplying i128 can be expensive). Reviewers: sanjoy Subscribers: llvm-commits, mzolotukhin Differential Revision: http://reviews.llvm.org/D19266 llvm-svn: 267389
* Remove emacs mode markers from .cpp files. NFCNick Lewycky2016-04-242-2/+2
| | | | | | .cpp files are unambiguously C++, you only need the mode markers on .h files. llvm-svn: 267353
* [ThinLTO] Remove GlobalValueInfo class from indexTeresa Johnson2016-04-241-11/+8
| | | | | | | | | | | | | | | | Summary: Remove the GlobalValueInfo and change the ModuleSummaryIndex to directly reference summary objects. The info structure was there to support lazy parsing of the combined index summary objects, which is no longer needed and not supported. Reviewers: joker.eph Subscribers: joker.eph, llvm-commits Differential Revision: http://reviews.llvm.org/D19462 llvm-svn: 267344
* Reorganize GlobalValueSummary with a "Flags" bitfield.Mehdi Amini2016-04-241-2/+4
| | | | | | | | | | Right now it only contains the LinkageType, but will be extended with "hasSection", "isOptSize", "hasInlineAssembly", etc. Differential Revision: http://reviews.llvm.org/D19404 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 267319
* Re-commit optimization bisect support (r267022) without new pass manager ↵Andrew Kaylor2016-04-222-5/+18
| | | | | | | | | | support. The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the OptBisect handling). Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267231
* Introduce llvm.load.relative intrinsic.Peter Collingbourne2016-04-222-0/+66
| | | | | | | | | | | | | | | | | | | 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
* CodeGen: Use PLT relocations for relative references to unnamed_addr functions.Peter Collingbourne2016-04-221-2/+6
| | | | | | | | | | | | | The relative vtable ABI (PR26723) needs PLT relocations to refer to virtual functions defined in other DSOs. The unnamed_addr attribute means that the function's address is not significant, so we're allowed to substitute it with the address of a PLT entry. Also includes a bonus feature: addends for COFF image-relative references. Differential Revision: http://reviews.llvm.org/D17938 llvm-svn: 267211
* 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
* Revert "Initial implementation of optimization bisect support."Vedant Kumar2016-04-222-18/+5
| | | | | | | | This reverts commit r267022, due to an ASan failure: http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549 llvm-svn: 267115
* [SCEV] Extract out a `isSCEVExprNeverPoison` helper; NFCISanjoy Das2016-04-221-29/+41
| | | | | | | | | | | | | | Summary: Also adds a small comment blurb on control flow + no-wrap flags, since that question came up a few days back on llvm-dev. Reviewers: bjarke.roune, broune Subscribers: sanjoy, mcrosier, llvm-commits, mzolotukhin Differential Revision: http://reviews.llvm.org/D19209 llvm-svn: 267110
* Initial implementation of optimization bisect support.Andrew Kaylor2016-04-212-5/+18
| | | | | | | | | | | | This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to track down test failures that are caused by incorrect optimizations. The bisection is enabled using a new command line option (-opt-bisect-limit). Individual passes that may be skipped call the OptBisect object (via an LLVMContext) to see if they should be skipped based on the bisect limit. A finer level of control (disabling individual transformations) can be managed through an addition OptBisect method, but this is not yet used. The skip checking in this implementation is based on (and replaces) the skipOptnoneFunction check. Where that check was being called, a new call has been inserted in its place which checks the bisect limit and the optnone attribute. A new function call has been added for module and SCC passes that behaves in a similar way. Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267022
* [unordered] Add tests and conservative handling in support of future changes ↵Philip Reames2016-04-211-0/+20
| | | | | | | | [NFCI] This change adds a couple of test cases to make sure FindAvailableLoadedValue does the right thing. At the moment, the code added is dead, but separating it makes follow on changes far more obvious. llvm-svn: 266999
* 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-212-43/+50
| | | | | | | | | | | | | | | | | | | | 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-202-67/+55
| | | | | | Phabricator Revision: http://reviews.llvm.org/D19277 llvm-svn: 266904
* [ThinLTO] Prevent importing of "llvm.used" valuesTeresa Johnson2016-04-201-0/+25
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch prevents importing from (and therefore exporting from) any module with a "llvm.used" local value. Local values need to be promoted and renamed when importing, and their presense on the llvm.used variable indicates that there are opaque uses that won't see the rename. One such example is a use in inline assembly. See also the discussion at: http://lists.llvm.org/pipermail/llvm-dev/2016-April/098047.html As part of this, move collectUsedGlobalVariables out of Transforms/Utils and into IR/Module so that it can be used more widely. There are several other places in LLVM that used copies of this code that can be cleaned up as a follow on NFC patch. Reviewers: joker.eph Subscribers: pcc, llvm-commits, joker.eph Differential Revision: http://reviews.llvm.org/D18986 llvm-svn: 266877
* [ValueTracking, VectorUtils] Refactor getIntrinsicIDForCallDavid Majnemer2016-04-193-148/+158
| | | | | | | | | | | | | 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-192-11/+111
| | | | | | | | | | | | | | | 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
* [DependenceAnalysis] Refactor uses of getConstantPart. NFC.Brendon Cahoon2016-04-191-36/+21
| | | | | | | | | | Rather than checking for the SCEV type prior to calling getContantPart, perform the checks in the function. This reduces the number of places where the checks are needed. Differential Revision: http://reviews.llvm.org/D19241 llvm-svn: 266759
* Correct IDF calculator for ReverseIDFDaniel Berlin2016-04-191-5/+14
| | | | | | | | | | | | | | Summary: Need to use predecessors for reverse graph, successors for forward graph. succ_iterator/pred_iterator are not compatible, this patch is all the work necessary to work around that (which is what everywhere else does). Not sure if there is a better way, so cc'ing some random folks to take a gander :) Reviewers: dblaikie, qcolombet, echristo Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D18796 llvm-svn: 266718
OpenPOWER on IntegriCloud