summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [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
* Port DemandedBits to the new pass manager.Michael Kuperstein2016-04-182-23/+43
| | | | | | Differential Revision: http://reviews.llvm.org/D18679 llvm-svn: 266699
* [BPI] Consider deoptimize calls as "unreachable"Sanjoy Das2016-04-181-1/+6
| | | | | | | | | | | | | | Summary: Calls to @llvm.experimental.deoptimize are expected to "never execute", so optimize them as such. Reviewers: chandlerc Subscribers: junbuml, mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D19095 llvm-svn: 266654
* Revert r266488.Easwaran Raman2016-04-181-1/+1
| | | | | | This goes with r266477 which has been reverted. llvm-svn: 266631
* Revert "Replace the use of MaxFunctionCount module flag"Eric Liu2016-04-181-4/+2
| | | | | | | | | | This reverts commit r266477. This commit introduces cyclic dependency. This commit has "Analysis" depend on "ProfileData", while "ProfileData" depends on "Object", which depends on "BitCode", which depends on "Analysis". llvm-svn: 266619
* [NFC] Header cleanupMehdi Amini2016-04-187-14/+1
| | | | | | | | | | | | | | Removed some unused headers, replaced some headers with forward class declarations. Found using simple scripts like this one: clear && ack --cpp -l '#include "llvm/ADT/IndexedMap.h"' | xargs grep -L 'IndexedMap[<]' | xargs grep -n --color=auto 'IndexedMap' Patch by Eugene Kosov <claprix@yandex.ru> Differential Revision: http://reviews.llvm.org/D19219 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 266595
* Add ProfileData to required_librariesEaswaran Raman2016-04-151-1/+1
| | | | | | This should fix ppc64be build breakage due to r266477 llvm-svn: 266488
* Replace the use of MaxFunctionCount module flagEaswaran Raman2016-04-151-2/+4
| | | | | | | | Adds an interface to get ProfileSummary for a module and makes InlineCost use ProfileSummary to get max function count. Differential Revision: http://reviews.llvm.org/D18622 llvm-svn: 266477
* [TTI] Add getInliningThresholdMultiplier.Justin Lebar2016-04-152-0/+8
| | | | | | | | | | | | | | | | Summary: InlineCost's threshold is multiplied by this value. This lets us adjust the inlining threshold up or down on a per-target basis. For example, we might want to increase the threshold on targets where calls are unusually expensive. Reviewers: chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D18560 llvm-svn: 266405
* [AliasSetTracker] Correctly handle changing the size of an entryMichael Kuperstein2016-04-141-15/+20
| | | | | | | | | | | | | If the size of an AST entry changes, we also need to make sure we perform necessary alias set merges, as the new size may overlap pointers in other sets. We happen to run into this with memset, because memset allows an entry for a i8* pointer to have a decidedly non-i8 size. This fixes PR27262. Differential Revision: http://reviews.llvm.org/D18939 llvm-svn: 266381
* [ARM] Adding IEEE-754 SIMD detection to loop vectorizerRenato Golin2016-04-141-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Some SIMD implementations are not IEEE-754 compliant, for example ARM's NEON. This patch teaches the loop vectorizer to only allow transformations of loops that either contain no floating-point operations or have enough allowance flags supporting lack of precision (ex. -ffast-math, Darwin). For that, the target description now has a method which tells us if the vectorizer is allowed to handle FP math without falling into unsafe representations, plus a check on every FP instruction in the candidate loop to check for the safety flags. This commit makes LLVM behave like GCC with respect to ARM NEON support, but it stops short of fixing the underlying problem: sub-normals. Neither GCC nor LLVM have a flag for allowing sub-normal operations. Before this patch, GCC only allows it using unsafe-math flags and LLVM allows it by default with no way to turn it off (short of not using NEON at all). As a first step, we push this change to make it safe and in sync with GCC. The second step is to discuss a new sub-normal's flag on both communitues and come up with a common solution. The third step is to improve the FastMath flags in LLVM to encode sub-normals and use those flags to restrict NEON FP. Fixes PR16275. llvm-svn: 266363
* [DivergenceAnalysis] Treat PHI with incoming undef as constantNicolai Haehnle2016-04-141-1/+1
| | | | | | | | | | | | | | | | | | | | | | | Summary: If a PHI has an incoming undef, we can pretend that it is equal to one non-undef, non-self incoming value. This is particularly relevant in combination with the StructurizeCFG pass, which introduces PHI nodes with undefs. Previously, this lead to branch conditions that were uniform before StructurizeCFG to become non-uniform afterwards, which confused the SIAnnotateControlFlow pass. This fixes a crash when Mesa radeonsi compiles a shader from dEQP-GLES3.functional.shaders.switch.switch_in_for_loop_dynamic_vertex Reviewers: arsenm, tstellarAMD, jingyue Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D19013 llvm-svn: 266347
* [SCEV][LAA] Add tests for SCEV expression transformations performed during LAASilviu Baranga2016-04-142-0/+28
| | | | | | | | | | | | | | | | | | | | Summary: Add a print method to Predicated Scalar Evolution which prints all interesting transformations done by PSE. Loop Access Analysis will now print this as part of the analysis output. We now use this to check the exact expression transformations that were done by PSE in LAA. The additional checking also acts as white-box testing for the getAsAddRec method. Reviewers: anemet, sanjoy Subscribers: sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D18792 llvm-svn: 266334
* [CodeGen] Teach LLVM how to lower @llvm.{min,max}num to {MIN,MAX}NANDavid Majnemer2016-04-142-5/+11
| | | | | | | | | | | | | | | The behavior of {MIN,MAX}NAN differs from that of {MIN,MAX}NUM when only one of the inputs is NaN: -NUM will return the non-NaN argument while -NAN would return NaN. It is desirable to lower to @llvm.{min,max}num to -NAN if they don't have a native instruction for -NUM. Notably, ARMv7 NEON's vmin has the -NAN semantics. N.B. Of course, it is only safe to do this if the intrinsic call is marked nnan. llvm-svn: 266279
* [CFLAA] Fix up code style a bit. NFC.George Burgess IV2016-04-132-292/+276
| | | | llvm-svn: 266262
* Return immediately from analyzeCall if analyzeBlock returns false.Easwaran Raman2016-04-131-14/+2
| | | | | | This is part of the patch reviewed at http://reviews.llvm.org/D17584 llvm-svn: 266249
* 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
* Calculate __builtin_object_size when pointer depends on a conditionPetar Jovanovic2016-04-131-14/+35
| | | | | | | | | | | | | | | | This patch fixes calculating of builtin_object_size if it depends on a condition. Before this patch compiler did not know how to calculate the object size when it finds a condition that cannot be eliminated. This patch enables calculating of builtin_object_size even in case when condition cannot be eliminated by choosing minimum or maximum value as a result from condition. Choosing minimum or maximum value from condition is based on the second argument of __builtin_object_size function. Patch by Strahinja Petrovic. Differential Revision: http://reviews.llvm.org/D18438 llvm-svn: 266193
* [InstCombine] We folded an fcmp to an i1 instead of a vector of i1David Majnemer2016-04-133-65/+71
| | | | | | | | | Remove an ad-hoc transform in InstCombine and replace it with more general machinery (ValueTracking, InstructionSimplify and VectorUtils). This fixes PR27332. llvm-svn: 266175
* Add space between words in verify-scev-maps option help messageJeroen Ketema2016-04-121-1/+1
| | | | llvm-svn: 266149
* Add the allocsize attribute to LLVM.George Burgess IV2016-04-121-55/+101
| | | | | | | | | | | | | | | | `allocsize` is a function attribute that allows users to request that LLVM treat arbitrary functions as allocation functions. This patch makes LLVM accept the `allocsize` attribute, and makes `@llvm.objectsize` recognize said attribute. The review for this was split into two patches for ease of reviewing: D18974 and D14933. As promised on the revisions, I'm landing both patches as a single commit. Differential Revision: http://reviews.llvm.org/D14933 llvm-svn: 266032
* This reverts commit r265913 and r265912Sanjoy Das2016-04-112-110/+5
| | | | | | | | | See PR27315 r265913: "[IndVars] Eliminate op.with.overflow when possible" r265912: "[SCEV] See through op.with.overflow intrinsics" llvm-svn: 265950
* [ThinLTO] Move summary computation from BitcodeWriter to new passTeresa Johnson2016-04-113-0/+188
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This is the first step in also serializing the index out to LLVM assembly. The per-module summary written to bitcode is moved out of the bitcode writer and to a new analysis pass (ModuleSummaryIndexWrapperPass). The pass itself uses a new builder class to compute index, and the builder class is used directly in places where we don't have a pass manager (e.g. llvm-as). Because we are computing summaries outside of the bitcode writer, we no longer can use value ids created by the bitcode writer's ValueEnumerator. This required changing the reference graph edge type to use a new ValueInfo class holding a union between a GUID (combined index) and Value* (permodule index). The Value* are converted to the appropriate value ID during bitcode writing. Also, this enables removal of the BitWriter library's dependence on the Analysis library that was previously required for the summary computation. Reviewers: joker.eph Subscribers: joker.eph, llvm-commits Differential Revision: http://reviews.llvm.org/D18763 llvm-svn: 265941
* [SCEV] See through op.with.overflow intrinsicsSanjoy Das2016-04-102-5/+110
| | | | | | | | | | | | | | | 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
* Refactor Threshold computation. NFC.Easwaran Raman2016-04-081-22/+35
| | | | | | This is part of changes reviewed in http://reviews.llvm.org/D17584. llvm-svn: 265852
* Propagate Undef in llvm.cos IntrinsicSanjoy Das2016-04-081-0/+5
| | | | | | | | | | | | | | | | | | Summary: The llvm cos intrinsic currently does not propagate undef's. This change transforms cos(undef) to null value or 0. There are 2 test cases added as well. Patch by Anna Thomas! Reviewers: sanjoy Subscribers: majnemer, llvm-commits Differential Revision: http://reviews.llvm.org/D18863 llvm-svn: 265825
* Re-commit [SCEV] Introduce a guarded backedge taken count and use it in LAA ↵Silviu Baranga2016-04-083-89/+234
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | and LV This re-commits r265535 which was reverted in r265541 because it broke the windows bots. The problem was that we had a PointerIntPair which took a pointer to a struct allocated with new. The problem was that new doesn't provide sufficient alignment guarantees. This pattern was already present before r265535 and it just happened to work. To fix this, we now separate the PointerToIntPair from the ExitNotTakenInfo struct into a pointer and a bool. Original commit message: Summary: When the backedge taken codition is computed from an icmp, SCEV can deduce the backedge taken count only if one of the sides of the icmp is an AddRecExpr. However, due to sign/zero extensions, we sometimes end up with something that is not an AddRecExpr. However, we can use SCEV predicates to produce a 'guarded' expression. This change adds a method to SCEV to get this expression, and the SCEV predicate associated with it. In HowManyGreaterThans and HowManyLessThans we will now add a SCEV predicate associated with the guarded backedge taken count when the analyzed SCEV expression is not an AddRecExpr. Note that we only do this as an alternative to returning a 'CouldNotCompute'. We use new feature in Loop Access Analysis and LoopVectorize to analyze and transform more loops. Reviewers: anemet, mzolotukhin, hfinkel, sanjoy Subscribers: flyingforyou, mcrosier, atrick, mssimpso, sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D17201 llvm-svn: 265786
OpenPOWER on IntegriCloud