summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* Remove redundant virtual on overriden functions.David Blaikie2014-11-141-2/+2
| | | | llvm-svn: 222023
* Revert r219432 - "Revert "[BasicAA] Revert "Revert r218714 - Make better use ↵Hal Finkel2014-11-131-5/+55
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | of zext and sign information.""" Let's try this again... This reverts r219432, plus a bug fix. Description of the bug in r219432 (by Nick): The bug was using AllPositive to break out of the loop; if the loop break condition i != e is changed to i != e && AllPositive then the test_modulo_analysis_with_global test I've added will fail as the Modulo will be calculated incorrectly (as the last loop iteration is skipped, so Modulo isn't updated with its Scale). Nick also adds this comment: ComputeSignBit is safe to use in loops as it takes into account phi nodes, and the == EK_ZeroEx check is safe in loops as, no matter how the variable changes between iterations, zero-extensions will always guarantee a zero sign bit. The isValueEqualInPotentialCycles check is therefore definitely not needed as all the variable analysis holds no matter how the variables change between loop iterations. And this patch also adds another enhancement to GetLinearExpression - basically to convert ConstantInts to Offsets (see test_const_eval and test_const_eval_scaled for the situations this improves). Original commit message: This reverts r218944, which reverted r218714, plus a bug fix. Description of the bug in r218714 (by Nick): The original patch forgot to check if the Scale in VariableGEPIndex flipped the sign of the variable. The BasicAA pass iterates over the instructions in the order they appear in the function, and so BasicAliasAnalysis::aliasGEP is called with the variable it first comes across as parameter GEP1. Adding a %reorder label puts the definition of %a after %b so aliasGEP is called with %b as the first parameter and %a as the second. aliasGEP later calculates that %a == %b + 1 - %idxprom where %idxprom >= 0 (if %a was passed as the first parameter it would calculate %b == %a - 1 + %idxprom where %idxprom >= 0) - ignoring that %idxprom is scaled by -1 here lead the patch to incorrectly conclude that %a > %b. Revised patch by Nick White, thanks! Thanks to Lang to isolating the bug. Slightly modified by me to add an early exit from the loop and avoid unnecessary, but expensive, function calls. Original commit message: Two related things: 1. Fixes a bug when calculating the offset in GetLinearExpression. The code previously used zext to extend the offset, so negative offsets were converted to large positive ones. 2. Enhance aliasGEP to deduce that, if the difference between two GEP allocations is positive and all the variables that govern the offset are also positive (i.e. the offset is strictly after the higher base pointer), then locations that fit in the gap between the two base pointers are NoAlias. Patch by Nick White! llvm-svn: 221876
* Teach ScalarEvolution to sharpen range information.Sanjoy Das2014-11-131-0/+60
| | | | | | | | | | | | | | | | | | If x is known to have the range [a, b), in a loop predicated by (icmp ne x, a) its range can be sharpened to [a + 1, b). Get ScalarEvolution and hence IndVars to exploit this fact. This change triggers an optimization to widen-loop-comp.ll, so it had to be edited to get it to pass. This change was originally landed in r219834 but had a bug and broke ASan. It was reverted in r219878, and is now being re-landed after fixing the original bug. phabricator: http://reviews.llvm.org/D5639 reviewed by: atrick llvm-svn: 221839
* CGSCC should not treat intrinsic calls like function calls (PR21403)Sanjay Patel2014-11-121-1/+8
| | | | | | | | | | | | | | | | Make the handling of calls to intrinsics in CGSCC consistent: they are not treated like regular function calls because they are never lowered to function calls. Without this patch, we can get dangling pointer asserts from the subsequent loop that processes callsites because it already ignores intrinsics. See http://llvm.org/bugs/show_bug.cgi?id=21403 for more details / discussion. Differential Revision: http://reviews.llvm.org/D6124 llvm-svn: 221802
* Revert "IR: MDNode => Value"Duncan P. N. Exon Smith2014-11-116-24/+26
| | | | | | | | | | | | | | | | | Instead, we're going to separate metadata from the Value hierarchy. See PR21532. This reverts commit r221375. This reverts commit r221373. This reverts commit r221359. This reverts commit r221167. This reverts commit r221027. This reverts commit r221024. This reverts commit r221023. This reverts commit r220995. This reverts commit r220994. llvm-svn: 221711
* Add Forward Control-Flow Integrity.Tom Roeder2014-11-111-1/+16
| | | | | | | | | | | | | | | | | | | | This commit adds a new pass that can inject checks before indirect calls to make sure that these calls target known locations. It supports three types of checks and, at compile time, it can take the name of a custom function to call when an indirect call check fails. The default failure function ignores the error and continues. This pass incidentally moves the function JumpInstrTables::transformType from private to public and makes it static (with a new argument that specifies the table type to use); this is so that the CFI code can transform function types at call sites to determine which jump-instruction table to use for the check at that site. Also, this removes support for jumptables in ARM, pending further performance analysis and discussion. Review: http://reviews.llvm.org/D4167 llvm-svn: 221708
* Indentation fixesMichael Liao2014-11-061-38/+38
| | | | llvm-svn: 221472
* remove extra breaks; NFCSanjay Patel2014-11-051-4/+1
| | | | llvm-svn: 221374
* InstSimplify: Exact shifts of X by Y are X if X has the lsb setDavid Majnemer2014-11-051-11/+31
| | | | | | | | | Exact shifts may not shift out any non-zero bits. Use computeKnownBits to determine when this occurs and just return the left hand side. This fixes PR21477. llvm-svn: 221325
* Analysis: Make isSafeToSpeculativelyExecute fire less for dividesDavid Majnemer2014-11-041-15/+23
| | | | | | | | | | | | | Divides and remainder operations do not behave like other operations when they are given poison: they turn into undefined behavior. It's really hard to know if the operands going into a div are or are not poison. Because of this, we should only choose to speculate if there are constant operands which we can easily reason about. This fixes PR21412. llvm-svn: 221318
* InstSimplify: Fold a hasNoSignedWrap() call into a match() expressionDavid Majnemer2014-11-041-2/+1
| | | | | | No functionality change intended, it's just a little more concise. llvm-svn: 221281
* InstSimplify: Fold a hasNoUnsignedWrap() call into a match() expressionDavid Majnemer2014-11-041-2/+1
| | | | | | No functionality change intended, it's just a little more concise. llvm-svn: 221280
* remove function names from comments; NFCSanjay Patel2014-11-041-39/+35
| | | | llvm-svn: 221274
* fix typo in commentSanjay Patel2014-11-041-1/+1
| | | | llvm-svn: 221273
* Use AA in LoadCombineHal Finkel2014-11-031-1/+6
| | | | | | | | | | | | | | LoadCombine can be smarter about aborting when a writing instruction is encountered, instead of aborting upon encountering any writing instruction, use an AliasSetTracker, and only abort when encountering some write that might alias with the loads that could potentially be combined. This was originally motivated by comments made (and a test case provided) by David Majnemer in response to PR21448. It turned out that LoadCombine was not responsible for that PR, but LoadCombine should also be improved so that unrelated stores (and @llvm.assume) don't interrupt load combining. llvm-svn: 221203
* IR: MDNode => Value: Instruction::getMetadata()Duncan P. N. Exon Smith2014-11-016-31/+29
| | | | | | | | | | Change `Instruction::getMetadata()` to return `Value` as part of PR21433. Update most callers to use `Instruction::getMDNode()`, which wraps the result in a `cast_or_null<MDNode>`. llvm-svn: 221024
* [SCEV] Improve Scalar Evolution's use of no {un,}signed wrap flagsBradley Smith2014-10-311-6/+26
| | | | | | | | | | | | | | | In a case where we have a no {un,}signed wrap flag on the increment, if RHS - Start is constant then we can avoid inserting a max operation bewteen the two, since we can statically determine which is greater. This allows us to unroll loops such as: void testcase3(int v) { for (int i=v; i<=v+1; ++i) f(i); } llvm-svn: 220960
* Add handling for range metadata in ValueTracking isKnownNonZeroPhilip Reames2014-10-301-0/+29
| | | | | | | | | | | If we load from a location with range metadata, we can use information about the ranges of the loaded value for optimization purposes. This helps to remove redundant checks and canonicalize checks for other optimization passes. This particular patch checks whether a value is known to be non-zero from the range metadata. Currently, these tests are against InstCombine. In theory, all of these should be InstSimplify since we're not inserting any new instructions. Moving the code may follow in a separate change. Reviewed by: Hal Differential Revision: http://reviews.llvm.org/D5947 llvm-svn: 220925
* Reformat partially, where I touched for whitespace changes.NAKAMURA Takumi2014-10-282-12/+7
| | | | llvm-svn: 220773
* Untabify and whitespace cleanups.NAKAMURA Takumi2014-10-282-12/+11
| | | | llvm-svn: 220771
* Clean up assume intrinsic pattern matching, no need to check that the ↵Benjamin Kramer2014-10-251-11/+6
| | | | | | | | argument is a value. Also make it const safe and remove superfluous casting. NFC. llvm-svn: 220616
* [InstSimplify] Support constant folding to vector of pointersBruno Cardoso Lopes2014-10-221-2/+12
| | | | | | | | | | | | | | | | | | | ConstantFolding crashes when trying to InstSimplify the following load: @a = private unnamed_addr constant %mst { i8* inttoptr (i64 -1 to i8*), i8* inttoptr (i64 -1 to i8*) }, align 8 %x = load <2 x i8*>* bitcast (%mst* @a to <2 x i8*>*), align 8 This patch fix this by adding support to this type of folding: %x = load <2 x i8*>* bitcast (%mst* @a to <2 x i8*>*), align 8 ==> gets folded to: %x = <2 x i8*> <i8* inttoptr (i64 -1 to i8*), i8* inttoptr (i64 -1 to i8*)> llvm-svn: 220380
* Revert "Teach the load analysis to allow finding available values which ↵Hans Wennborg2014-10-211-10/+4
| | | | | | | | require" (r220277) This seems to have caused PR21330. llvm-svn: 220349
* Add minnum / maxnum intrinsicsMatt Arsenault2014-10-213-0/+19
| | | | | | | | | | | | These are named following the IEEE-754 names for these functions, rather than the libm fmin / fmax to avoid possible ambiguities. Some languages may implement something resembling fmin / fmax which return NaN if either operand is to propagate errors. These implement the IEEE-754 semantics of returning the other operand if either is a NaN representing missing data. llvm-svn: 220341
* remove function names from comments; NFCSanjay Patel2014-10-211-2/+2
| | | | llvm-svn: 220309
* Teach the load analysis to allow finding available values which requireChandler Carruth2014-10-211-4/+10
| | | | | | | | | | | | | | | | | | | | 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: 220277
* Introduce enum values for previously defined metadata types. (NFC)Philip Reames2014-10-212-2/+4
| | | | | | | | | | | Our metadata scheme lazily assigns IDs to string metadata, but we have a mechanism to preassign them as well. Using a preassigned ID is helpful since we get compile time type checking, and avoid some (minimal) string construction and comparison. This change adds enum value for three existing metadata types: + MD_nontemporal = 9, // "nontemporal" + MD_mem_parallel_loop_access = 10, // "llvm.mem.parallel_loop_access" + MD_nonnull = 11 // "nonnull" I went through an updated various uses as well. I made no attempt to get all uses; I focused on the ones which were easily grepable and easily to translate. For example, there were several items in LoopInfo.cpp I chose not to update. llvm-svn: 220248
* Introduce a 'nonnull' metadata on Load instructions.Philip Reames2014-10-201-0/+4
| | | | | | | | | The newly introduced 'nonnull' metadata is analogous to existing 'nonnull' attributes, but applies to load instructions rather than call arguments or returns. Long term, it would be nice to combine these into a single construct. The value of the load is allowed to vary between successive loads, but null is not a valid value to be loaded by any load marked nonnull. Reviewed by: Hal Finkel Differential Revision: http://reviews.llvm.org/D5220 llvm-svn: 220240
* Fix a miscompile introduced in r220178.Chandler Carruth2014-10-201-4/+5
| | | | | | | | | | | | | | | | | | The original code had an implicit assumption that if the test for allocas or globals was reached, the two pointers were not equal. With my changes to make the pointer analysis more powerful here, I also had to guard against circumstances where the results weren't useful. That in turn violated the assumption and gave rise to a circumstance in which we could have a store with both the queried pointer and stored pointer rooted at *the same* alloca. Clearly, we cannot ignore such a store. There are other things we might do in this code to better handle the case of both pointers ending up at the same alloca or global, but it seems best to at least make the test explicit in what it intends to check. I've added tests for both the alloca and global case here. llvm-svn: 220190
* Teach the load analysis driving core instcombine logic and other bits ofChandler Carruth2014-10-201-21/+43
| | | | | | | | | | | | | | | | | | | logic to look through pointer casts, making them trivially stronger in the face of loads and stores with intervening pointer casts. I've included a few test cases that demonstrate the kind of folding instcombine can do without pointer casts and then variations which obfuscate the logic through bitcasts. Without this patch, the variations all fail to optimize fully. This is more important now than it has been in the past as I've started moving the load canonicialization to more closely follow the value type requirements rather than the pointer type requirements and thus this needs to be prepared for more pointer casts. When I made the same change to stores several test cases regressed without logic along these lines so I wanted to systematically improve matters first. llvm-svn: 220178
* Move previously dead code to handle computing the known bits of an aliasChandler Carruth2014-10-191-10/+11
| | | | | | | | | | | | | | up to where it actually works as intended. The problem is that a GlobalAlias isa GlobalValue and so the prior block handled all of the cases. This allows us to constant fold based on the actual constant expression in the global alias. As an example, see the last function in the newly added test case which explicitly aligns an unaligned pointer using constant expression math. Without this change, we fail to see that and fold an alignment test to zero. llvm-svn: 220164
* Fix a long-standing miscompile in the load analysis that was uncoveredChandler Carruth2014-10-191-11/+0
| | | | | | | | | | | | | | | | | | | by my refactoring of this code. The method isSafeToLoadUnconditionally assumes that the load will proceed with the preferred type alignment. Given that, it has to ensure that the alloca or global is at least that aligned. It has always done this historically when a datalayout is present, but has never checked it when the datalayout is absent. When I refactored the code in r220156, I exposed this path when datalayout was present and that turned the latent bug into a patent bug. This fixes the issue by just removing the special case which allows folding things without datalayout. This isn't worth the complexity of trying to tease apart when it is or isn't safe without actually knowing the preferred alignment. llvm-svn: 220161
* Switch how the datalayout availability test is handled in this code toChandler Carruth2014-10-191-7/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | make much more sense and in theory be more correct. If you trace the code alllll the way back to when it was first introduced, the comments make it slightly more clear what was going on here. At that time, the only way Base != V was if DL (then TD) was non-null. As a consequence, if DL *was* null, that meant we were loading directly from the alloca or global found above the test. After refactoring, this has become at least terribly subtle and potentially incorrect. There are many forms of pointer manipulation that can be traversed without DataLayout, and some of them would in fact change the size of object being loaded vs. allocated. Rather than this subtlety, I've hoisted the actual 'return true' bits into the code which actually found an alloca or global and based them on the loaded pointer being that alloca or global. This is both more clear and safer. I've also added comments about exactly why this set of predicates is used. I've also corrected a misleading comment about globals -- if overridden they may not just have a different size, they may be null and completely unsafe to load from! Hopefully this confuses the next reader a bit less. I don't have any test cases or anything, the patch is motivated strictly to improve the readability of the code. llvm-svn: 220156
OpenPOWER on IntegriCloud