summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* [MemoryDepAnalysis] Fix compile time slowdownBruno Cardoso Lopes2014-10-011-0/+22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | - Problem One program takes ~3min to compile under -O2. This happens after a certain function A is inlined ~700 times in a function B, inserting thousands of new BBs. This leads to 80% of the compilation time spent in GVN::processNonLocalLoad and MemoryDependenceAnalysis::getNonLocalPointerDependency, while searching for nonlocal information for basic blocks. Usually, to avoid spending a long time to process nonlocal loads, GVN bails out if it gets more than 100 deps as a result from MD->getNonLocalPointerDependency. However this only happens *after* all nonlocal information for BBs have been computed, which is the bottleneck in this scenario. For instance, there are 8280 times where getNonLocalPointerDependency returns deps with more than 100 bbs and from those, 600 times it returns more than 1000 blocks. - Solution Bail out early during the nonlocal info computation whenever we reach a specified threshold. This patch proposes a 100 BBs threshold, it also reduces the compile time from 3min to 23s. - Testing The test-suite presented no compile nor execution time regressions. Some numbers from my machine (x86_64 darwin): - 17s under -Oz (which avoids inlining). - 1.3s under -O1. - 2m51s under -O2 ToT *** 23s under -O2 w/ Result.size() > 100 - 1m54s under -O2 w/ Result.size() > 500 With NumResultsLimit = 100, GVN yields the same outcome as in the unlimited 3min version. http://reviews.llvm.org/D5532 rdar://problem/18188041 llvm-svn: 218792
* [BasicAA] Make better use of zext and sign informationHal Finkel2014-09-301-2/+29
| | | | | | | | | | | | | | | | | 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: 218714
* Ignore annotation function calls in cost computationDavid Peixotto2014-09-261-0/+1
| | | | | | | | | | | The annotation instructions are dropped during codegen and have no impact on size. In some cases, the annotations were preventing the unroller from unrolling a loop because the annotation calls were pushing the cost over the unrolling threshold. Differential Revision: http://reviews.llvm.org/D5335 llvm-svn: 218525
* Fix assertion in LICM doFinalization()David Peixotto2014-09-241-0/+11
| | | | | | | | | | | | | | | | The doFinalization method checks that the LoopToAliasSetMap is empty. LICM populates that map as it runs through the loop nest, deleting the entries for child loops as it goes. However, if a child loop is deleted by another pass (e.g. unrolling) then the loop will never be deleted from the map because LICM walks the loop nest to find entries it can delete. The fix is to delete the loop from the map and free the alias set when the loop is deleted from the loop nest. Differential Revision: http://reviews.llvm.org/D5305 llvm-svn: 218387
* Add two thresholds lvi-overdefined-BB-threshold and lvi-overdefined-thresholdJiangning Liu2014-09-221-2/+32
| | | | | | | | | | for LVI algorithm. For a specific value to be lowered, when the number of basic blocks being checked for overdefined lattice value is larger than lvi-overdefined-BB-threshold, or the times of encountering overdefined value for a single basic block is larger than lvi-overdefined-threshold, the LVI algorithm will stop further lowering the lattice value. llvm-svn: 218231
* Add file to CMake build as well.Eric Christopher2014-09-181-0/+1
| | | | llvm-svn: 218005
* Add a new pass FunctionTargetTransformInfo. This pass serves as aEric Christopher2014-09-182-5/+56
| | | | | | | | | | | shim between the TargetTransformInfo immutable pass and the Subtarget via the TargetMachine and Function. Migrate a single call from BasicTargetTransformInfo as an example and provide shims where TargetMachine begins taking a Function to determine the subtarget. No functional change. llvm-svn: 218004
* InstSimplify: Don't allow (x srem y) urem y -> x srem yDavid Majnemer2014-09-171-3/+5
| | | | | | | | | | | Let's consider the case where: %x i16 = 32768 %y i16 = 384 %x srem %y = 65408 (%x srem %y) urem %y = 128 llvm-svn: 217939
* InstSimplify: ((X % Y) % Y) -> (X % Y)David Majnemer2014-09-171-0/+5
| | | | | | | | Patch by Sonam Kumari! Differential Revision: http://reviews.llvm.org/D5350 llvm-svn: 217937
* InstSimplify: Simplify trivial and/or of icmpsDavid Majnemer2014-09-151-0/+114
| | | | | | | | | | | | | Some ICmpInsts when anded/ored with another ICmpInst trivially reduces to true or false depending on whether or not all integers or no integers satisfy the intersected/unioned range. This sort of trivial looking code can come about when InstCombine performs a range reduction-type operation on sdiv and the like. This fixes PR20916. llvm-svn: 217750
* Fix an ODR violation consisting of two 'struct Query' in the global namespace.Benjamin Kramer2014-09-122-0/+4
| | | | | | Put them in their own anonymous namespaces. Found by GCC's new -Wodr (PR20915). llvm-svn: 217662
* Rename getMaximumUnrollFactor -> getMaxInterleaveFactor; also rename option ↵Sanjay Patel2014-09-101-3/+3
| | | | | | | | | | | names controlling this variable. "Unroll" is not the appropriate name for this variable. Clang already uses the term "interleave" in pragmas and metadata for this. Differential Revision: http://reviews.llvm.org/D5066 llvm-svn: 217528
* Make use @llvm.assume for loop guards in ScalarEvolutionHal Finkel2014-09-071-6/+24
| | | | | | | | | This adds a basic (but important) use of @llvm.assume calls in ScalarEvolution. When SE is attempting to validate a condition guarding a loop (such as whether or not the loop count can be zero), this check should also include dominating assumptions. llvm-svn: 217348
* Make use of @llvm.assume from LazyValueInfoHal Finkel2014-09-071-77/+189
| | | | | | | | | | | | | | | | | | | | | | | This change teaches LazyValueInfo to use the @llvm.assume intrinsic. Like with the known-bits change (r217342), this requires feeding a "context" instruction pointer through many functions. Aside from a little refactoring to reuse the logic that turns predicates into constant ranges in LVI, the only new code is that which can 'merge' the range from an assumption into that otherwise computed. There is also a small addition to JumpThreading so that it can have LVI use assumptions in the same block as the comparison feeding a conditional branch. With this patch, we can now simplify this as expected: int foo(int a) { __builtin_assume(a > 5); if (a > 3) { bar(); return 1; } return 0; } llvm-svn: 217345
* Add additional patterns for @llvm.assume in ValueTrackingHal Finkel2014-09-071-0/+212
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This builds on r217342, which added the infrastructure to compute known bits using assumptions (@llvm.assume calls). That original commit added only a few patterns (to catch common cases related to determining pointer alignment); this change adds several other patterns for simple cases. r217342 contained that, for assume(v & b = a), bits in the mask that are known to be one, we can propagate known bits from the a to v. It also had a known-bits transfer for assume(a = b). This patch adds: assume(~(v & b) = a) : For those bits in the mask that are known to be one, we can propagate inverted known bits from the a to v. assume(v | b = a) : For those bits in b that are known to be zero, we can propagate known bits from the a to v. assume(~(v | b) = a): For those bits in b that are known to be zero, we can propagate inverted known bits from the a to v. assume(v ^ b = a) : For those bits in b that are known to be zero, we can propagate known bits from the a to v. For those bits in b that are known to be one, we can propagate inverted known bits from the a to v. assume(~(v ^ b) = a) : For those bits in b that are known to be zero, we can propagate inverted known bits from the a to v. For those bits in b that are known to be one, we can propagate known bits from the a to v. assume(v << c = a) : For those bits in a that are known, we can propagate them to known bits in v shifted to the right by c. assume(~(v << c) = a) : For those bits in a that are known, we can propagate them inverted to known bits in v shifted to the right by c. assume(v >> c = a) : For those bits in a that are known, we can propagate them to known bits in v shifted to the right by c. assume(~(v >> c) = a) : For those bits in a that are known, we can propagate them inverted to known bits in v shifted to the right by c. assume(v >=_s c) where c is non-negative: The sign bit of v is zero assume(v >_s c) where c is at least -1: The sign bit of v is zero assume(v <=_s c) where c is negative: The sign bit of v is one assume(v <_s c) where c is non-positive: The sign bit of v is one assume(v <=_u c): Transfer the known high zero bits assume(v <_u c): Transfer the known high zero bits (if c is know to be a power of 2, transfer one more) A small addition to InstCombine was necessary for some of the test cases. The problem is that when InstCombine was simplifying and, or, etc. it would fail to check the 'do I know all of the bits' condition before checking less specific conditions and would not fully constant-fold the result. I'm not sure how to trigger this aside from using assumptions, so I've just included the change here. llvm-svn: 217343
* Make use of @llvm.assume in ValueTracking (computeKnownBits, etc.)Hal Finkel2014-09-078-250/+729
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change, which allows @llvm.assume to be used from within computeKnownBits (and other associated functions in ValueTracking), adds some (optional) parameters to computeKnownBits and friends. These functions now (optionally) take a "context" instruction pointer, an AssumptionTracker pointer, and also a DomTree pointer, and most of the changes are just to pass this new information when it is easily available from InstSimplify, InstCombine, etc. As explained below, the significant conceptual change is that known properties of a value might depend on the control-flow location of the use (because we care that the @llvm.assume dominates the use because assumptions have control-flow dependencies). This means that, when we ask if bits are known in a value, we might get different answers for different uses. The significant changes are all in ValueTracking. Two main changes: First, as with the rest of the code, new parameters need to be passed around. To make this easier, I grouped them into a structure, and I made internal static versions of the relevant functions that take this structure as a parameter. The new code does as you might expect, it looks for @llvm.assume calls that make use of the value we're trying to learn something about (often indirectly), attempts to pattern match that expression, and uses the result if successful. By making use of the AssumptionTracker, the process of finding @llvm.assume calls is not expensive. Part of the structure being passed around inside ValueTracking is a set of already-considered @llvm.assume calls. This is to prevent a query using, for example, the assume(a == b), to recurse on itself. The context and DT params are used to find applicable assumptions. An assumption needs to dominate the context instruction, or come after it deterministically. In this latter case we only handle the specific case where both the assumption and the context instruction are in the same block, and we need to exclude assumptions from being used to simplify their own ephemeral values (those which contribute only to the assumption) because otherwise the assumption would prove its feeding comparison trivial and would be removed. This commit adds the plumbing and the logic for a simple masked-bit propagation (just enough to write a regression test). Future commits add more patterns (and, correspondingly, more regression tests). llvm-svn: 217342
* Add functions for finding ephemeral valuesHal Finkel2014-09-072-8/+103
| | | | | | | | | | | | | | | | This adds a set of utility functions for collecting 'ephemeral' values. These are LLVM IR values that are used only by @llvm.assume intrinsics (directly or indirectly), and thus will be removed prior to code generation, implying that they should be considered free for certain purposes (like inlining). The inliner's cost analysis, and a few other passes, have been updated to account for ephemeral values using the provided functionality. This functionality is important for the usability of @llvm.assume, because it limits the "non-local" side-effects of adding llvm.assume on inlining, loop unrolling, etc. (these are hints, and do not generate code, so they should not directly contribute to estimates of execution cost). llvm-svn: 217335
* Add an Assumption-Tracking PassHal Finkel2014-09-072-0/+114
| | | | | | | | | | | | | | | | | | | | | | | | This adds an immutable pass, AssumptionTracker, which keeps a cache of @llvm.assume call instructions within a module. It uses callback value handles to keep stale functions and intrinsics out of the map, and it relies on any code that creates new @llvm.assume calls to notify it of the new instructions. The benefit is that code needing to find @llvm.assume intrinsics can do so directly, without scanning the function, thus allowing the cost of @llvm.assume handling to be negligible when none are present. The current design is intended to be lightweight. We don't keep track of anything until we need a list of assumptions in some function. The first time this happens, we scan the function. After that, we add/remove @llvm.assume calls from the cache in response to registration calls and ValueHandle callbacks. There are no new direct test cases for this pass, but because it calls it validation function upon module finalization, we'll pick up detectable inconsistencies from the other tests that touch @llvm.assume calls. This pass will be used by follow-up commits that make use of @llvm.assume. llvm-svn: 217334
OpenPOWER on IntegriCloud