summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* Rename 'TD' to 'DL' in this function as the argument is now a DataLayoutChandler Carruth2014-10-181-7/+7
| | | | | | argument. llvm-svn: 220151
* Fix the other comment to use modern doxygen style and be a bit moreChandler Carruth2014-10-181-4/+8
| | | | | | | direct. Notably, comment on the fact that the loaded type is significant in that it determines how wide of an access must be safe. llvm-svn: 220150
* More formatting cleanup brought to you by clang-format.Chandler Carruth2014-10-181-5/+8
| | | | llvm-svn: 220149
* Clean up doxygen syntax and reword comments to flow better, have a briefChandler Carruth2014-10-181-15/+20
| | | | | | section, and not have unfinished sentence fragments. llvm-svn: 220147
* Clean up the formatting and trailing whitespace of a routine beforeChandler Carruth2014-10-181-16/+19
| | | | | | editting it. llvm-svn: 220146
* [LVI] Add some additional comments about caching and context instructionsHal Finkel2014-10-161-0/+13
| | | | | | | | Philip Reames and I had a long conversation about this, mostly because it is not obvious why the current logic is correct. Hopefully, these comments will prevent such confusion in the future. llvm-svn: 219882
* Revert "r219834 - Teach ScalarEvolution to sharpen range information"Sanjoy Das2014-10-151-38/+0
| | | | | | | This change breaks the asan buildbots: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/13468 llvm-svn: 219878
* Teach ScalarEvolution to sharpen range information.Sanjoy Das2014-10-151-0/+38
| | | | | | | | | | | | 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. phabricator: http://reviews.llvm.org/D5639 llvm-svn: 219834
* Treat the WorkSet used to find ephemeral values as double-endedHal Finkel2014-10-151-1/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | We need to make sure that we visit all operands of an instruction before moving deeper in the operand graph. We had been pushing operands onto the back of the work set, and popping them off the back as well, meaning that we might visit an instruction before visiting all of its uses that sit in between it and the call to @llvm.assume. To provide an explicit example, given the following: %q0 = extractelement <4 x float> %rd, i32 0 %q1 = extractelement <4 x float> %rd, i32 1 %q2 = extractelement <4 x float> %rd, i32 2 %q3 = extractelement <4 x float> %rd, i32 3 %q4 = fadd float %q0, %q1 %q5 = fadd float %q2, %q3 %q6 = fadd float %q4, %q5 %qi = fcmp olt float %q6, %q5 call void @llvm.assume(i1 %qi) %q5 is used by both %qi and %q6. When we visit %qi, it will be marked as ephemeral, and we'll queue %q6 and %q5. %q6 will be marked as ephemeral and we'll queue %q4 and %q5. Under the old system, we'd then visit %q4, which would become ephemeral, %q1 and then %q0, which would become ephemeral as well, and now we have a problem. We'd visit %rd, but it would not be marked as ephemeral because we've not yet visited %q2 and %q3 (because we've not yet visited %q5). This will be covered by a test case in a follow-up commit that enables ephemeral-value awareness in the SLP vectorizer. llvm-svn: 219815
* [CFL-AA] CFL-AA should not assert on an va_arg instructionHal Finkel2014-10-141-0/+11
| | | | | | | | | | The CFL-AA implementation was missing a visit* routine for va_arg instructions, causing it to assert when run on a function that had one. For now, handle these in a conservative way. Fixes PR20954. llvm-svn: 219718
* [LVI] Check for @llvm.assume dominating the edge branchHal Finkel2014-10-141-0/+2
| | | | | | | | | | | | | When LazyValueInfo uses @llvm.assume intrinsics to provide edge-value constraints, we should check for intrinsics that dominate the edge's branch, not just any potential context instructions. An assumption that dominates the edge's branch represents a truth on that edge. This is specifically useful, for example, if multiple predecessors assume a pointer to be nonnull, allowing us to simplify a later null comparison. The test case, and an initial patch, were provided by Philip Reames. Thanks! llvm-svn: 219688
* [modules] Stop excluding Support/Debug.h from the Support module. This headerRichard Smith2014-10-131-1/+0
| | | | | | | has been modular since r206822, and excluding it was leading to workarounds such as the one in r219592, which this change removes. llvm-svn: 219593
* [Modules] Add some missing includes to make files compile stand-alone.Benjamin Kramer2014-10-121-1/+1
| | | | llvm-svn: 219592
* AssumptionTracker: Don't create temporary CallbackVHs.Benjamin Kramer2014-10-111-3/+5
| | | | | | Those are expensive to create in cold cache scenarios. NFC. llvm-svn: 219575
* InstCombine, InstSimplify: (%X /s C1) /s C2 isn't always 0 when C1 * C2 overflowDavid Majnemer2014-10-111-0/+10
| | | | | | | | | | | | | | | | | | consider: C1 = INT_MIN C2 = -1 C1 * C2 overflows without a doubt but consider the following: %x = i32 INT_MIN This means that (%X /s C1) is 1 and (%X /s C1) /s C2 is -1. N. B. Move the unsigned version of this transform to InstSimplify, it doesn't create any new instructions. This fixes PR21243. llvm-svn: 219567
* [SCEV] Add some asserts to the recently improved trip count computationChandler Carruth2014-10-111-0/+22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | routines and fix all of the bugs they expose. I hit a test case that crashed even without these asserts due to passing a non-exiting latch to the ExitingBlock parameter of the trip count computation machinery. However, when I add the nice asserts, it turns out we have plenty of coverage of these bugs, they just didn't manifest in crashers. The core problem seems to stem from an assumption that the latch *is* the exiting block. While this is often true, and somewhat the "normal" way to think about loops, it isn't necessarily true. The correct way to call the trip count routines in a *generic* fashion (that is, without a particular exit in mind) is to just use the loop's single exiting block if it has one. The trip count can't be computed generically unless it does. This works great for the loop vectorizer. The loop unroller actually *wants* to select the latch when it has to chose between multiple exits because for unrolling it is the latch trips that matter. But if this is the desire, it needs to explicitly guard for non-exiting latches and check for the generic trip count in that case. I've added the asserts, and added convenience APIs for querying the trip count generically that check for a single exit block. I've kept the APIs consistent between computing trip count and trip multiples. Thansk to Mark for the help debugging and tracking down the *right* fix here! llvm-svn: 219550
* This patch teaches ScalarEvolution to pick and use !range metadata.Sanjoy Das2014-10-101-0/+41
| | | | | | | | | | | | It also makes it more aggressive in querying range information by adding a call to isKnownPredicateWithRanges to isLoopBackedgeGuardedByCond and isLoopEntryGuardedByCond. phabricator: http://reviews.llvm.org/D5638 Reviewed by: atrick, hfinkel llvm-svn: 219532
* This patch de-pessimizes the calculation of loop trip counts inMark Heffernan2014-10-101-353/+325
| | | | | | | | | | | | | | | | | | | | | ScalarEvolution in the presence of multiple exits. Previously all loops exits had to have identical counts for a loop trip count to be considered computable. This pessimization was implemented by calling getBackedgeTakenCount(L) rather than getExitCount(L, ExitingBlock) inside of ScalarEvolution::getSmallConstantTripCount() (see the FIXME in the comments of that function). The pessimization was added to fix a corner case involving undefined behavior (pr/16130). This patch more precisely handles the undefined behavior case allowing the pessimization to be removed. ControlsExit replaces IsSubExpr to more precisely track the case where undefined behavior is expected to occur. Because undefined behavior is tracked more precisely we can remove MustExit from ExitLimit. MustExit was used to track the case where the limit was computed potentially assuming undefined behavior even if undefined behavior didn't necessarily occur. llvm-svn: 219517
* [LVI] Revert the remainder of "r218231 - Add two thresholds ↵Hal Finkel2014-10-101-22/+0
| | | | | | | | | lvi-overdefined-BB-threshold and lvi-overdefined-threshold" Some of r218231 was reverted with the code that used it in r218971, but not all of it. This removes the rest (which is now dead). llvm-svn: 219469
* Revert "[BasicAA] Revert "Revert r218714 - Make better use of zext and sign ↵Hal Finkel2014-10-091-41/+2
| | | | | | | | information."" This reverts commit r219135 -- still causing miscompiles in SPEC it seems... llvm-svn: 219432
* [BasicAA] Revert "Revert r218714 - Make better use of zext and sign ↵Hal Finkel2014-10-061-2/+41
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | information." 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: 219135
* BFI: Improve assertion message, since it's actually firingDuncan P. N. Exon Smith2014-10-061-1/+2
| | | | | | | This assertion is firing because -loop-unroll is failing to preserve -loop-info (see PR20987). Improve it. llvm-svn: 219130
* [CFL-AA] Update for handling of globals and more testsHal Finkel2014-10-061-3/+11
| | | | | | | | | | | | | | | | | | We used to return PartialAlias if *either* variable being queried interacted with arguments or globals. AFAICT, we can change this to only returning MayAlias iff *both* variables being queried interacted with arguments or globals. Also, adding some basic functionality tests: some basic IPA tests, checking that we give conservative responses with arguments/globals thrown in the mix, and ensuring that we trace values through stores and loads. Note that saying that 'x' interacted with arguments or globals means that the Attributes of the StratifiedSet that 'x' belongs to has any bits set. Patch by George Burgess IV, thanks! llvm-svn: 219122
* Simplify code. No functionality change.Benjamin Kramer2014-10-051-4/+2
| | | | llvm-svn: 219082
* Make AAMDNodes ctor and operator bool (!!!) explicit, mop up bugs and ↵Benjamin Kramer2014-10-043-6/+9
| | | | | | weirdness exposed by it. llvm-svn: 219068
* PR21145: Teach LLVM about C++14 sized deallocation functions.Richard Smith2014-10-031-1/+5
| | | | | | | | C++14 adds new builtin signatures for 'operator delete'. This change allows new/delete pairs to be removed in C++14 onwards, as they were in C++11 and before. llvm-svn: 219014
* Revert r215343.James Molloy2014-10-031-25/+1
| | | | | | This was contentious and needs invesigation. llvm-svn: 218971
* [BasicAA] Revert r218714 - Make better use of zext and sign information.Lang Hames2014-10-031-29/+2
| | | | | | | | | This patch broke 447.dealII on Darwin. I'm currently working on a reduced test-case, but reverting for now to keep the bots happy. <rdar://problem/18530107> llvm-svn: 218944
* Remove duplicate function names from comments. NFC.Sanjay Patel2014-10-021-43/+35
| | | | llvm-svn: 218875
* Silence a -Wsign-compare warning. NFC.Aaron Ballman2014-10-021-2/+2
| | | | llvm-svn: 218868
* Adds 'override' to overriding methods. NFC.Argyrios Kyrtzidis2014-10-011-1/+1
| | | | llvm-svn: 218815
* Make the sqrt intrinsic return undef for a negative input.Sanjay Patel2014-10-011-2/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | As discussed here: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140609/220598.html And again here: http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-September/077168.html The sqrt of a negative number when using the llvm intrinsic is undefined. We should return undef rather than 0.0 to match the definition in the LLVM IR lang ref. This change should not affect any code that isn't using "no-nans-fp-math"; ie, no-nans is a requirement for generating the llvm intrinsic in place of a sqrt function call. Unfortunately, the behavior introduced by this patch will not match current gcc, xlc, icc, and possibly other compilers. The current clang/llvm behavior of returning 0.0 doesn't either. We knowingly approve of this difference with the other compilers in an attempt to flag code that is invoking undefined behavior. A front-end warning should also try to convince the user that the program will fail: http://llvm.org/bugs/show_bug.cgi?id=21093 Differential Revision: http://reviews.llvm.org/D5527 llvm-svn: 218803
OpenPOWER on IntegriCloud