summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* InstSimplify: Don't bother if getScalarSizeInBits returns zeroDavid Majnemer2014-12-201-4/+5
| | | | | | | getScalarSizeInBits returns zero when the comparison operands are not integral. No functionality change intended. llvm-svn: 224675
* Simplify the codeDavid Majnemer2014-12-201-41/+25
| | | | | | No functionality change intended. llvm-svn: 224673
* InstSimplify: Optimize away pointless comparisonsDavid Majnemer2014-12-201-2/+38
| | | | | | | | | (X & INT_MIN) ? X & INT_MAX : X into X & INT_MAX (X & INT_MIN) ? X : X & INT_MAX into X (X & INT_MIN) ? X | INT_MIN : X into X (X & INT_MIN) ? X : X | INT_MIN into X | INT_MIN llvm-svn: 224669
* Remove redundant assignment.Tilmann Scheller2014-12-191-1/+0
| | | | | | Found with the Clang static analyzer. llvm-svn: 224570
* InstSimplify: shl nsw/nuw undef, %V -> undefDavid Majnemer2014-12-171-13/+7
| | | | | | | | | | We can always choose an value for undef which might cause %V to shift out an important bit except for one case, when %V is zero. However, shl behaves like an identity function when the right hand side is zero. llvm-svn: 224405
* Teach ScalarEvolution to exploit min and max expressions when provingSanjoy Das2014-12-151-8/+93
| | | | | | | | | | | | | | | | isKnownPredicate. The motivation for this change is to optimize away checks in loops like this: limit = min(t, len) for (i = 0 to limit) if (i >= len || i < 0) throw_array_of_of_bounds(); a[i] = ... Differential Revision: http://reviews.llvm.org/D6635 llvm-svn: 224285
* Clarify HowFarToZero computation when the step is a positive power of two. ↵Mark Heffernan2014-12-151-8/+13
| | | | | | Functionally this should be identical to the existing code except for the case where Step is maximally negative (eg, INT_MIN). We now punt in that one corner case to make reasoning about the code easier. llvm-svn: 224274
* Sink store based on alias analysisElena Demikhovsky2014-12-151-10/+11
| | | | | | | | | | | | - by Ella Bolshinsky The alias analysis is used define whether the given instruction is a barrier for store sinking. For 2 identical stores, following instructions are checked in the both basic blocks, to determine whether they are sinking barriers. http://reviews.llvm.org/D6420 llvm-svn: 224247
* Loop Vectorizer minor changes in the code - Elena Demikhovsky2014-12-141-4/+4
| | | | | | | | some comments, function names, identation. Reviewed here: http://reviews.llvm.org/D6527 llvm-svn: 224218
* ScalarEvolution: Remove SCEVUDivision, it's unusedDavid Majnemer2014-12-141-93/+26
| | | | | | This is just a code simplification, no functionality change is intended. llvm-svn: 224216
* ValueTracking: Don't recurse too deeply in computeKnownBitsFromAssumeDavid Majnemer2014-12-121-0/+4
| | | | | | | | | Respect the MaxDepth recursion limit, doing otherwise will trigger an assert in computeKnownBits. This fixes PR21891. llvm-svn: 224168
* Fix PR21694. r219517 added a use of SCEV divide in HowFarToZero computation. ↵Mark Heffernan2014-12-101-10/+8
| | | | | | This divide can produce incorrect results as we are using an unsigned divide for what should be a modular divide. This change reverts back to a more conservative computation using trailing zeros. llvm-svn: 223974
* ConstantFold, InstSimplify: undef >>a x can be either -1 or 0, choose 0David Majnemer2014-12-101-2/+2
| | | | | | Zero is usually a nicer constant to have than -1. llvm-svn: 223969
* InstSimplify: [al]shr exact undef, %X -> undefDavid Majnemer2014-12-101-2/+6
| | | | | | | Exact shifts always keep the non-zero bits of their input. This means it keeps it's undef bits. llvm-svn: 223923
* InstSimplify: div %X, 0 -> undefDavid Majnemer2014-12-101-0/+4
| | | | | | We already optimized rem %X, 0 to undef, we should do the same for div. llvm-svn: 223919
* IR: Split Metadata from ValueDuncan P. N. Exon Smith2014-12-094-17/+27
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Split `Metadata` away from the `Value` class hierarchy, as part of PR21532. Assembly and bitcode changes are in the wings, but this is the bulk of the change for the IR C++ API. I have a follow-up patch prepared for `clang`. If this breaks other sub-projects, I apologize in advance :(. Help me compile it on Darwin I'll try to fix it. FWIW, the errors should be easy to fix, so it may be simpler to just fix it yourself. This breaks the build for all metadata-related code that's out-of-tree. Rest assured the transition is mechanical and the compiler should catch almost all of the problems. Here's a quick guide for updating your code: - `Metadata` is the root of a class hierarchy with three main classes: `MDNode`, `MDString`, and `ValueAsMetadata`. It is distinct from the `Value` class hierarchy. It is typeless -- i.e., instances do *not* have a `Type`. - `MDNode`'s operands are all `Metadata *` (instead of `Value *`). - `TrackingVH<MDNode>` and `WeakVH` referring to metadata can be replaced with `TrackingMDNodeRef` and `TrackingMDRef`, respectively. If you're referring solely to resolved `MDNode`s -- post graph construction -- just use `MDNode*`. - `MDNode` (and the rest of `Metadata`) have only limited support for `replaceAllUsesWith()`. As long as an `MDNode` is pointing at a forward declaration -- the result of `MDNode::getTemporary()` -- it maintains a side map of its uses and can RAUW itself. Once the forward declarations are fully resolved RAUW support is dropped on the ground. This means that uniquing collisions on changing operands cause nodes to become "distinct". (This already happened fairly commonly, whenever an operand went to null.) If you're constructing complex (non self-reference) `MDNode` cycles, you need to call `MDNode::resolveCycles()` on each node (or on a top-level node that somehow references all of the nodes). Also, don't do that. Metadata cycles (and the RAUW machinery needed to construct them) are expensive. - An `MDNode` can only refer to a `Constant` through a bridge called `ConstantAsMetadata` (one of the subclasses of `ValueAsMetadata`). As a side effect, accessing an operand of an `MDNode` that is known to be, e.g., `ConstantInt`, takes three steps: first, cast from `Metadata` to `ConstantAsMetadata`; second, extract the `Constant`; third, cast down to `ConstantInt`. The eventual goal is to introduce `MDInt`/`MDFloat`/etc. and have metadata schema owners transition away from using `Constant`s when the type isn't important (and they don't care about referring to `GlobalValue`s). In the meantime, I've added transitional API to the `mdconst` namespace that matches semantics with the old code, in order to avoid adding the error-prone three-step equivalent to every call site. If your old code was: MDNode *N = foo(); bar(isa <ConstantInt>(N->getOperand(0))); baz(cast <ConstantInt>(N->getOperand(1))); bak(cast_or_null <ConstantInt>(N->getOperand(2))); bat(dyn_cast <ConstantInt>(N->getOperand(3))); bay(dyn_cast_or_null<ConstantInt>(N->getOperand(4))); you can trivially match its semantics with: MDNode *N = foo(); bar(mdconst::hasa <ConstantInt>(N->getOperand(0))); baz(mdconst::extract <ConstantInt>(N->getOperand(1))); bak(mdconst::extract_or_null <ConstantInt>(N->getOperand(2))); bat(mdconst::dyn_extract <ConstantInt>(N->getOperand(3))); bay(mdconst::dyn_extract_or_null<ConstantInt>(N->getOperand(4))); and when you transition your metadata schema to `MDInt`: MDNode *N = foo(); bar(isa <MDInt>(N->getOperand(0))); baz(cast <MDInt>(N->getOperand(1))); bak(cast_or_null <MDInt>(N->getOperand(2))); bat(dyn_cast <MDInt>(N->getOperand(3))); bay(dyn_cast_or_null<MDInt>(N->getOperand(4))); - A `CallInst` -- specifically, intrinsic instructions -- can refer to metadata through a bridge called `MetadataAsValue`. This is a subclass of `Value` where `getType()->isMetadataTy()`. `MetadataAsValue` is the *only* class that can legally refer to a `LocalAsMetadata`, which is a bridged form of non-`Constant` values like `Argument` and `Instruction`. It can also refer to any other `Metadata` subclass. (I'll break all your testcases in a follow-up commit, when I propagate this change to assembly.) llvm-svn: 223802
* InstSimplify: Try to bring back the rest of r223583David Majnemer2014-12-081-2/+7
| | | | | | | This reverts r223624 with a small tweak, hopefully this will make stage3 equivalent. llvm-svn: 223679
* Revert a part of r223583, for now. It seems causing different emission ↵NAKAMURA Takumi2014-12-081-5/+0
| | | | | | between stage2(gcc-clang) and stage3 clang. Investigating. llvm-svn: 223624
* InstSimplify: Optimize away useless unsigned comparisonsDavid Majnemer2014-12-061-0/+49
| | | | | | Code like X < Y && Y == 0 should always be folded away to false. llvm-svn: 223583
* Canonicalize multiplies by looking at whether the operands have any ↵Nick Lewycky2014-12-061-5/+26
| | | | | | constants themselves. Patch by Tim Murray! llvm-svn: 223554
* BFI: Saturate when combining edges to a successorDuncan P. N. Exon Smith2014-12-051-4/+17
| | | | | | | | | | | | When a loop gets bundled up, its outgoing edges are quite large, and can just barely overflow 64-bits. If one successor has multiple incoming edges -- and that successor is getting all the incoming mass -- combining just its edges can overflow. Handle that by saturating rather than asserting. This fixes PR21622. llvm-svn: 223500
* Revert "r223364 - Revert r223347 which has caused crashes on bootstrap bots."Hal Finkel2014-12-041-3/+14
| | | | | | | | | | | | | | | | | | | | Reapply r223347, with a fix to not crash on uninserted instructions (or more precisely, instructions in uninserted blocks). bugpoint was able to reduce the test case somewhat, but it is still somewhat large (and relies on setting things up to be simplified during inlining), so I've not included it here. Nevertheless, it is clear what is going on and why. Original commit message: Restrict somewhat the memory-allocation pointer cmp opt from r223093 Based on review comments from Richard Smith, restrict this optimization from applying to globals that might resolve lazily to other dynamically-loaded modules, and also from dynamic allocas (which might be transformed into malloc calls). In short, take extra care that the compared-to pointer is really simultaneously live with the memory allocation. llvm-svn: 223371
* Revert r223347 which has caused crashes on bootstrap bots.Alexander Potapenko2014-12-041-13/+3
| | | | llvm-svn: 223364
* Masked Load / Store Intrinsics - the CodeGen part.Elena Demikhovsky2014-12-041-0/+11
| | | | | | | | | | | | | | | | | | I'm recommiting the codegen part of the patch. The vectorizer part will be send to review again. Masked Vector Load and Store Intrinsics. Introduced new target-independent intrinsics in order to support masked vector loads and stores. The loop vectorizer optimizes loops containing conditional memory accesses by generating these intrinsics for existing targets AVX2 and AVX-512. The vectorizer asks the target about availability of masked vector loads and stores. Added SDNodes for masked operations and lowering patterns for X86 code generator. Examples: <16 x i32> @llvm.masked.load.v16i32(i8* %addr, <16 x i32> %passthru, i32 4 /* align */, <16 x i1> %mask) declare void @llvm.masked.store.v8f64(i8* %addr, <8 x double> %value, i32 4, <8 x i1> %mask) Scalarizer for other targets (not AVX2/AVX-512) will be done in a separate patch. http://reviews.llvm.org/D6191 llvm-svn: 223348
* Restrict somewhat the memory-allocation pointer cmp opt from r223093Hal Finkel2014-12-041-3/+13
| | | | | | | | | | Based on review comments from Richard Smith, restrict this optimization from applying to globals that might resolve lazily to other dynamically-loaded modules, and also from dynamic allocas (which might be transformed into malloc calls). In short, take extra care that the compared-to pointer is really simultaneously live with the memory allocation. llvm-svn: 223347
* Simplify pointer comparisons involving memory allocation functionsHal Finkel2014-12-011-0/+35
| | | | | | | | | | | | | System memory allocation functions, which are identified at the IR level by the noalias attribute on the return value, must return a pointer into a memory region disjoint from any other memory accessible to the caller. We can use this property to simplify pointer comparisons between allocated memory and local stack addresses and the addresses of global variables. Neither the stack nor global variables can overlap with the region used by the memory allocator. Fixes PR21556. llvm-svn: 223093
* [Statepoints 1/4] Statepoint infrastructure for garbage collection: IR ↵Philip Reames2014-12-011-0/+4
| | | | | | | | | | | | | | Intrinsics The statepoint intrinsics are intended to enable precise root tracking through the compiler as to support garbage collectors of all types. The addition of the statepoint intrinsics to LLVM should have no impact on the compilation of any program which does not contain them. There are no side tables created, no extra metadata, and no inhibited optimizations. A statepoint works by transforming a call site (or safepoint poll site) into an explicit relocation operation. It is the frontend's responsibility (or eventually the safepoint insertion pass we've developed, but that's not part of this patch series) to ensure that any live pointer to a GC object is correctly added to the statepoint and explicitly relocated. The relocated value is just a normal SSA value (as seen by the optimizer), so merges of relocated and unrelocated values are just normal phis. The explicit relocation operation, the fact the statepoint is assumed to clobber all memory, and the optimizers standard semantics ensure that the relocations flow through IR optimizations correctly. This is the first patch in a small series. This patch contains only the IR parts; the documentation and backend support will be following separately. The entire series can be seen as one combined whole in http://reviews.llvm.org/D5683. Reviewed by: atrick, ributzka llvm-svn: 223078
* Relax an assert a bit to avoid a crash on unreachable code.Rafael Espindola2014-12-011-1/+1
| | | | | | Patch by Duncan Exon Smith with a small tweak by me. llvm-svn: 222984
* Revert "Masked Vector Load and Store Intrinsics."Duncan P. N. Exon Smith2014-11-281-11/+0
| | | | | | | | | | | This reverts commit r222632 (and follow-up r222636), which caused a host of LNT failures on an internal bot. I'll respond to the commit on the list with a reproduction of one of the failures. Conflicts: lib/Target/X86/X86TargetTransformInfo.cpp llvm-svn: 222936
* InstSimplify: Restore optimizations lost in r210006David Majnemer2014-11-271-0/+34
| | | | | | | | | | This restores our ability to optimize: (X & C) ? X & ~C : X into X & ~C (X & C) ? X : X & ~C into X (X & C) ? X | C : X into X (X & C) ? X : X | C into X | C llvm-svn: 222868
* LazyValueInfo: Actually re-visit partially solved block-values in ↵Hans Wennborg2014-11-251-58/+78
| | | | | | | | | | | | | | | | | | | | | | | | | | solveBlockValue() If solveBlockValue() needs results from predecessors that are not already computed, it returns false with the intention of resuming when the dependencies have been resolved. However, the computation would never be resumed since an 'overdefined' result had been placed in the cache, preventing any further computation. The point of placing the 'overdefined' result in the cache seems to have been to break cycles, but we can check for that when inserting work items in the BlockValue stack instead. This makes the "stop and resume" mechanism of solveBlockValue() work as intended, unlocking more analysis. Using this patch shaves 120 KB off a 64-bit Chromium build on Linux. I benchmarked compiling bzip2.c at -O2 but couldn't measure any difference in compile time. Tests by Jiangning Liu from r215343 / PR21238, Pete Cooper, and me. Differential Revision: http://reviews.llvm.org/D6397 llvm-svn: 222768
* Revert r220349 to re-instate r220277 with a fix for PR21330 -- quiteChandler Carruth2014-11-251-4/+10
| | | | | | | | | | | | | | | | | | | | | | | | | clearly only exactly equal width ptrtoint and inttoptr casts are no-op casts, it says so right there in the langref. Make the code agree. Original log from r220277: Teach the load analysis to allow finding available values which require inttoptr or ptrtoint cast provided there is datalayout available. Eventually, the datalayout can just be required but in practice it will always be there today. To go with the ability to expose available values requiring a ptrtoint or inttoptr cast, helpers are added to perform one of these three casts. These smarts are necessary to finish canonicalizing loads and stores to the operational type requirements without regressing fundamental combines. I've added some test cases. These should actually improve as the load combining and store combining improves, but they may fundamentally be highlighting some missing combines for select in addition to exercising the specific added logic to load analysis. llvm-svn: 222739
* InstSimplify: Handle some simple tautological comparisonsDavid Majnemer2014-11-251-0/+34
| | | | | | | | This handles cases where we are comparing a masked value against itself. The analysis could be further improved by making it recursive but such expense is not currently justified. llvm-svn: 222716
* Factor check for the assume intrinsic out of checks in ↵Philip Reames2014-11-241-42/+39
| | | | | | | | | | | | | | computeKnownBitsFromAssume We were matching against the assume intrinsic in every check. Since we know that it must be an assume, this is just wasted work. Somewhat surprisingly, matching an intrinsic id is actually relatively expensive. It devolves to a string construction and comparison in Function::isIntrinsic. I originally spotted this because it showed up in a performance profile of my compiler. I've since discovered a separate issue which seems to be the actual root cause, but this is minor perf goodness regardless. I'm likely to follow up with another change to factor out the comparison matching. There's no need to match the compare instruction in every single one of the tests. Differential Revision: http://reviews.llvm.org/D6312 llvm-svn: 222709
* Remove the unused FindUsedTypes pass.Rafael Espindola2014-11-243-101/+0
| | | | | | It was dead since r134829. llvm-svn: 222684
* Add and use Type::subtypes. NFC.Rafael Espindola2014-11-241-3/+2
| | | | llvm-svn: 222682
* Masked Vector Load and Store Intrinsics.Elena Demikhovsky2014-11-231-0/+11
| | | | | | | | | | | | | | Introduced new target-independent intrinsics in order to support masked vector loads and stores. The loop vectorizer optimizes loops containing conditional memory accesses by generating these intrinsics for existing targets AVX2 and AVX-512. The vectorizer asks the target about availability of masked vector loads and stores. Added SDNodes for masked operations and lowering patterns for X86 code generator. Examples: <16 x i32> @llvm.masked.load.v16i32(i8* %addr, <16 x i32> %passthru, i32 4 /* align */, <16 x i1> %mask) declare void @llvm.masked.store.v8f64(i8* %addr, <8 x double> %value, i32 4, <8 x i1> %mask) Scalarizer for other targets (not AVX2/AVX-512) will be done in a separate patch. http://reviews.llvm.org/D6191 llvm-svn: 222632
* InstSimplify: Simplify (sub 0, X) -> X if it's NUWDavid Majnemer2014-11-221-11/+3
| | | | | | This is a generalization of the X - (0 - Y) -> X transform. llvm-svn: 222611
* LazyValueInfo: range'ify some for-loops. No functional change.Hans Wennborg2014-11-211-34/+19
| | | | llvm-svn: 222557
* LazyValueInfo: fix some typos and indentation, etc. NFC.Hans Wennborg2014-11-211-10/+12
| | | | llvm-svn: 222554
* AliasSet: Simplify mergeSetInDavid Majnemer2014-11-191-4/+3
| | | | | | No functional change intended. llvm-svn: 222376
* AliasSetTracker: UnknownInsts should contribute to the refcountDavid Majnemer2014-11-191-15/+26
| | | | | | | | | | | | | | | | | | | AliasSetTracker::addUnknown may create an AliasSet devoid of pointers just to contain an instruction if no suitable AliasSet already exists. It will then AliasSet::addUnknownInst and we will be done. However, it's possible for addUnknown to choose an existing AliasSet to addUnknownInst. If this were to occur, we are in a bit of a pickle: removing pointers from the AliasSet can cause the entire AliasSet to become destroyed, taking our unknown instructions out with them. Instead, keep track whether or not our AliasSet has any unknown instructions. This fixes PR21582. llvm-svn: 222338
* Update SetVector to rely on the underlying set's insert to return a ↵David Blaikie2014-11-1917-32/+37
| | | | | | | | | | | | | pair<iterator, bool> This is to be consistent with StringSet and ultimately with the standard library's associative container insert function. This lead to updating SmallSet::insert to return pair<iterator, bool>, and then to update SmallPtrSet::insert to return pair<iterator, bool>, and then to update all the existing users of those functions... llvm-svn: 222334
* ScalarEvolution: Construct SCEVDivision's Derived type instead of itselfDavid Majnemer2014-11-171-12/+21
| | | | | | | | | | | | SCEVDivision::divide constructed an object of SCEVDivision<Derived> instead of Derived. divide would call visit which would cast the SCEVDivision<Derived> to type Derived. As it happens, SCEVDivision<Derived> and Derived currently have the same layout but this is fragile and grounds for UB. Instead, just construct Derived. No functional change intended. llvm-svn: 222126
* ScalarEvolution: Introduce SCEVSDivision and SCEVUDivisionDavid Majnemer2014-11-161-15/+58
| | | | | | | | | | | It turns out that not all users of SCEVDivision want the same signedness. Let the users determine which operation they'd like by explicitly choosing SCEVUDivision or SCEVSDivision. findArrayDimensions and computeAccessFunctions will use SCEVSDivision while HowFarToZero will use SCEVUDivision. llvm-svn: 222104
* [DependenceAnalysis] Allow subscripts of different typesJingyue Wu2014-11-161-4/+27
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: Several places in DependenceAnalysis assumes both SCEVs in a subscript pair share the same integer type. For instance, isKnownPredicate calls SE->getMinusSCEV(X, Y) which asserts X and Y share the same type. However, DependenceAnalysis fails to ensure this assumption when producing a subscript pair, causing tests such as NonCanonicalizedSubscript to crash. With this patch, DependenceAnalysis runs unifySubscriptType before producing any subscript pair, ensuring the assumption. Test Plan: Added NonCanonicalizedSubscript.ll on which DependenceAnalysis before the fix crashed because subscripts have different types. Reviewers: spop, sebpop, jingyue Reviewed By: jingyue Subscribers: eliben, meheff, llvm-commits Differential Revision: http://reviews.llvm.org/D6289 llvm-svn: 222100
* ScalarEvolution: HowFarToZero was wrongly using signed divisionDavid Majnemer2014-11-161-10/+10
| | | | | | | | | | | HowFarToZero was supposed to use unsigned division in order to calculate the backedge taken count. However, SCEVDivision::divide performs signed division. Unless I am mistaken, no users of SCEVDivision actually want signed arithmetic: switch to udiv and urem. This fixes PR21578. llvm-svn: 222093
* InstSimplify: Optimize ICmpInst xform that uses computeKnownBitsDavid Majnemer2014-11-161-21/+17
| | | | | | | | | | | | A few things: - computeKnownBits is relatively expensive, let's delay its use as long as we can. - Don't create two APInt values just to run computeKnownBits on a ConstantInt, we already know the exact value! - Avoid creating a temporary APInt value in order to calculate unary negation. llvm-svn: 222092
* Revert "Don't make assumptions about the name of private global variables."Reid Kleckner2014-11-151-1/+0
| | | | | | | | This reverts commit r222061. It's causing linker errors. llvm-svn: 222077
* Don't make assumptions about the name of private global variables.Rafael Espindola2014-11-141-0/+1
| | | | | | | | | | | | | | | | | Private variables are can be renamed, so it is not reliable to make decisions on the name. The name is also dropped by the assembler before getting to the linker, so using the name causes a disconnect between how llvm makes a decision (var name) and how the linker makes a decision (section it is in). This patch changes one case where we were looking at the variable name to use the section instead. Test tuning by Michael Gottesman. llvm-svn: 222061
OpenPOWER on IntegriCloud