summaryrefslogtreecommitdiff
path: root/lib/Analysis
Commit message (Collapse)AuthorAge
* Revert "Introduce a string_ostream string builder facilty"Alp Toker2014-06-26
| | | | | | Temporarily back out commits r211749, r211752 and r211754. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211814 91177308-0d34-0410-b5e6-96231b3b80d8
* This patch removed duplicate code for matching patterns Dinesh Dwivedi2014-06-26
| | | | | | | | | | | which are now handled in SimplifyUsingDistributiveLaws() (after r211261) Differential Revision: http://reviews.llvm.org/D4253 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211768 91177308-0d34-0410-b5e6-96231b3b80d8
* MSVC build fix following r211749Alp Toker2014-06-26
| | | | | | Avoid strndup() git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211752 91177308-0d34-0410-b5e6-96231b3b80d8
* Introduce a string_ostream string builder faciltyAlp Toker2014-06-26
| | | | | | | | | | | | | | | | | | | | string_ostream is a safe and efficient string builder that combines opaque stack storage with a built-in ostream interface. small_string_ostream<bytes> additionally permits an explicit stack storage size other than the default 128 bytes to be provided. Beyond that, storage is transferred to the heap. This convenient class can be used in most places an std::string+raw_string_ostream pair or SmallString<>+raw_svector_ostream pair would previously have been used, in order to guarantee consistent access without byte truncation. The patch also converts much of LLVM to use the new facility. These changes include several probable bug fixes for truncated output, a programming error that's no longer possible with the new interface. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211749 91177308-0d34-0410-b5e6-96231b3b80d8
* Support: Move class ScaledNumberDuncan P. N. Exon Smith2014-06-24
| | | | | | | | ScaledNumber has been cleaned up enough to pull out of BFI now. Still work to do there (tests for shifting, bloated printing code, etc.), but it seems clean enough for its new home. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211562 91177308-0d34-0410-b5e6-96231b3b80d8
* BFI: Un-floatify more languageDuncan P. N. Exon Smith2014-06-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211561 91177308-0d34-0410-b5e6-96231b3b80d8
* Support: Extract ScaledNumbers::MinScale and MaxScaleDuncan P. N. Exon Smith2014-06-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211558 91177308-0d34-0410-b5e6-96231b3b80d8
* BFI: Change language from "exponent" to "scale"Duncan P. N. Exon Smith2014-06-23
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211557 91177308-0d34-0410-b5e6-96231b3b80d8
* BFI: Rename UnsignedFloat => ScaledNumberDuncan P. N. Exon Smith2014-06-23
| | | | | | | A lot of the docs and API are out of date, but I'll leave that for a separate commit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211555 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEVExpander: Fold constant PHIs harder. The logic below only understands ↵Benjamin Kramer2014-06-21
| | | | | | | | proper IVs. PR20093. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211433 91177308-0d34-0410-b5e6-96231b3b80d8
* Add back functionality removed in r210497.Richard Trieu2014-06-21
| | | | | | | Instead of asserting, output a message stating that a null pointer was found. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211430 91177308-0d34-0410-b5e6-96231b3b80d8
* Support: Write ScaledNumber::getQuotient() and getProduct()Duncan P. N. Exon Smith2014-06-20
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211409 91177308-0d34-0410-b5e6-96231b3b80d8
* [ValueTracking] Extend range metadata to call/invokeJingyue Wu2014-06-19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: With this patch, range metadata can be added to call/invoke including IntrinsicInst. Previously, it could only be added to load. Rename computeKnownBitsLoad to computeKnownBitsFromRangeMetadata because range metadata is not only used by load. Update the language reference to reflect this change. Test Plan: Add several tests in range-2.ll to confirm the verifier is happy with having range metadata on call/invoke. Add two tests in AddOverFlow.ll to confirm annotating range metadata to call/invoke can benefit InstCombine. Reviewers: meheff, nlewycky, reames, hfinkel, eliben Reviewed By: eliben Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4187 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211281 91177308-0d34-0410-b5e6-96231b3b80d8
* Move optimization of some cases of (A & C1)|(B & C2) from instcombine to ↵Nick Lewycky2014-06-19
| | | | | | instsimplify. Patch by Rahul Jain, plus some last minute changes by me -- you can blame me for any bugs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211252 91177308-0d34-0410-b5e6-96231b3b80d8
* Make instsimplify's analysis of icmp eq/ne use computeKnownBits to determine ↵Nick Lewycky2014-06-19
| | | | | | whether the icmp is always true or false. Patch by Suyog Sarda! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211251 91177308-0d34-0410-b5e6-96231b3b80d8
* Removing an "if (!this)" check from two print methods. The condition willRichard Trieu2014-06-09
| | | | | | | | never be true in a well-defined context. The checking for null pointers has been moved into the caller logic so it does not rely on undefined behavior. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@210497 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove old fenv.h workaround for a historic clang driver bugAlp Toker2014-06-09
| | | | | | | | | | | Tested and works fine with clang using libstdc++. All indications are that this was fixed some time ago and isn't a problem with any clang version we support. I've added a note in PR6907 which is still open for some reason. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@210485 91177308-0d34-0410-b5e6-96231b3b80d8
* Fold FEnv.h into the implementationAlp Toker2014-06-09
| | | | | | | | | | | | | | | | | | Support headers shouldn't use config.h definitions, and they should never be undefined like this. ConstantFolding.cpp was the only user of this facility and already includes config.h for other math features, so it makes sense to move the checks there at point of use. (The implicit config.h was also quite dangerous -- removing the FEnv.h include would have silently disabled math constant folding without causing any tests to fail. Need to investigate -Wundef once the cleanup is done.) This eliminates the last config.h include from LLVM headers, paving the way for more consistent configuration checks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@210483 91177308-0d34-0410-b5e6-96231b3b80d8
* ScalarEvolution: Derive element size from the type of the loaded elementTobias Grosser2014-06-08
| | | | | | | | | | Before, we where looking at the size of the pointer type that specifies the location from which to load the element. This did not make any sense at all. This change fixes a bug in the delinearization where we failed to delinerize certain load instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@210435 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a new attribute called 'jumptable' that creates jump-instruction tables ↵Tom Roeder2014-06-05
| | | | | | | | | | | | | for functions marked with this attribute. It includes a pass that rewrites all indirect calls to jumptable functions to pass through these tables. This also adds backend support for generating the jump-instruction tables on ARM and X86. Note that since the jumptable attribute creates a second function pointer for a function, any function marked with jumptable must also be marked with unnamed_addr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@210280 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a Constant version of stripPointerCasts.Rafael Espindola2014-06-04
| | | | | | Thanks to rnk for the suggestion. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@210205 91177308-0d34-0410-b5e6-96231b3b80d8
* implement missing SCEVDivision caseSebastian Pop2014-05-29
| | | | | | | | without this case we would end on an infinite recursion: the remainder is zero, so Numerator - Remainder is equal to Numerator and so we would recursively ask for the division of Numerator by Denominator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209838 91177308-0d34-0410-b5e6-96231b3b80d8
* fail to find dimensions when ElementSize is nullptrSebastian Pop2014-05-29
| | | | | | | | when ScalarEvolution::getElementSize returns nullptr it is safe to early return in ScalarEvolution::findArrayDimensions such that we avoid later problems when we try to divide the terms by ElementSize. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209837 91177308-0d34-0410-b5e6-96231b3b80d8
* test check-in: added missing parenthesis in commentSanjay Patel2014-05-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209763 91177308-0d34-0410-b5e6-96231b3b80d8
* avoid type mismatch when building SCEVsSebastian Pop2014-05-27
| | | | | | | | | | | This is a corner case I have stumbled upon when dealing with ARM64 type conversions. I was not able to extract a testcase for the community codebase to fail on. The patch conservatively discards a division that would have ended up in an ICE due to a type mismatch when building a multiply expression. I have also added code to a place that builds add expressions and in which we should be careful not to pass in operands of different types. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209694 91177308-0d34-0410-b5e6-96231b3b80d8
* do not use the GCD to compute the delinearization stridesSebastian Pop2014-05-27
| | | | | | | | | | | We do not need to compute the GCD anymore after we removed the constant coefficients from the terms: the terms are now all parametric expressions and there is no need to recognize constant terms that divide only a subset of the terms. We only rely on the size of the terms, i.e., the number of operands in the multiply expressions, to sort the terms and recognize the parametric dimensions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209693 91177308-0d34-0410-b5e6-96231b3b80d8
* remove BasePointer before delinearizingSebastian Pop2014-05-27
| | | | | | | | | | No functional change is intended: instead of relying on the delinearization to come up with the base pointer as a remainder of the divisions in the delinearization, we just compute it from the array access and use that value. We substract the base pointer from the SCEV to be delinearized and that simplifies the work of the delinearizer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209692 91177308-0d34-0410-b5e6-96231b3b80d8
* remove constant termsSebastian Pop2014-05-27
| | | | | | | | | | | | | | | | | | | | | | The delinearization is needed only to remove the non linearity induced by expressions involving multiplications of parameters and induction variables. There is no problem in dealing with constant times parameters, or constant times an induction variable. For this reason, the current patch discards all constant terms and multipliers before running the delinearization algorithm on the terms. The only thing remaining in the term expressions are parameters and multiply expressions of parameters: these simplified term expressions are passed to the array shape recognizer that will not recognize constant dimensions anymore: these will be recognized as different strides in parametric subscripts. The only important special case of a constant dimension is the size of elements. Instead of relying on the delinearization to infer the size of an element, compute the element size from the base address type. This is a much more precise way of computing the element size than before, as we would have mixed together the size of an element with the strides of the innermost dimension. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209691 91177308-0d34-0410-b5e6-96231b3b80d8
* Some cleanup for r209568.Michael Zolotukhin2014-05-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209634 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement sext(C1 + C2*X) --> sext(C1) + sext(C2*X) andMichael Zolotukhin2014-05-24
| | | | | | | | | | | sext{C1,+,C2} --> sext(C1) + sext{0,+,C2} transformation in Scalar Evolution. That helps SLP-vectorizer to recognize consecutive loads/stores. <rdar://problem/14860614> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209568 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix and improve SCEV ComputeBackedgeTankCount.Andrew Trick2014-05-23
| | | | | | | | | | | | | This is a follow-up to r209358: PR19799: Indvars miscompile due to an incorrect max backedge taken count from SCEV. That fix was incomplete as pointed out by Arnold and Michael Z. The code was also too confusing. It needed a careful rewrite with more unit tests. This version will also happen to optimize more cases. <rdar://17005101> PR19799: Indvars miscompile... git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209545 91177308-0d34-0410-b5e6-96231b3b80d8
* ScalarEvolution: Fix handling of AddRecs in isKnownPredicateJustin Bogner2014-05-23
| | | | | | | | | | | | | ScalarEvolution::isKnownPredicate() can wrongly reduce a comparison when both the LHS and RHS are SCEVAddRecExprs. This checks that both LHS and RHS are guarded in the case when both are SCEVAddRecExprs. The test case is against indvars because I could not find a way to directly test SCEV. Patch by Sanjay Patel! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209487 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a bug in SCEV's backedge taken count computation from my prior fix in Jan.Andrew Trick2014-05-22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | This has to do with the trip count computation for loops with multiple exits, which is quite subtle. Most passes just ask for a single trip count number, so we must be conservative assuming any exit could be taken. Normally, we rely on the "exact" trip count, which was correctly given as "unknown". However, SCEV also gives a "max" back-edge taken count. The loops max BE taken count is conservatively a maximum over the max of each exit's non-exiting iterations count. Note that some exit tests can be skipped so the max loop back-edge taken count can actually exceed the max non-exiting iterations for some exits. However, when we know the loop *latch* cannot be skipped, we can directly use its max taken count disregarding other exits. I previously took the minimum here without checking whether the other exit could be skipped. The correct, and simpler thing to do here is just to directly use the loop latch's max non-exiting iterations as the loops max back-edge count. In the problematic test case, the first loop exit had a max of zero non-exiting iterations, but could be skipped. The loop latch was known not to be skipped but had max of one non-exiting iteration. We incorrectly claimed the loop back-edge could be taken zero times, when it is actually taken one time. Fixes Loop %for.body.i: <multiple exits> Unpredictable backedge-taken count. Loop %for.body.i: max backedge-taken count is 1. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209358 91177308-0d34-0410-b5e6-96231b3b80d8
* Clean up language and grammar.Eric Christopher2014-05-20
| | | | | | | Based on a patch by jfcaron3@gmail.com! PR19806 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209216 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach isKnownNonNull that a nonnull return is not null. Add a test for this ↵Nick Lewycky2014-05-20
| | | | | | case as well as the case of a nonnull attribute (already handled but not tested). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209193 91177308-0d34-0410-b5e6-96231b3b80d8
* Add 'nonnull', a new parameter and return attribute which indicates that the ↵Nick Lewycky2014-05-20
| | | | | | pointer is not null. Instcombine will elide comparisons between these and null. Patch by Luqman Aden! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209185 91177308-0d34-0410-b5e6-96231b3b80d8
* Check the alwaysinline attribute on the call as well as on the caller.Peter Collingbourne2014-05-19
| | | | | | Differential Revision: http://reviews.llvm.org/D3815 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209150 91177308-0d34-0410-b5e6-96231b3b80d8
* InstSimplify: Improve handling of ashr/lshrDavid Majnemer2014-05-16
| | | | | | | | | | | | | | Summary: Analyze the range of values produced by ashr/lshr cst, %V when it is being used in an icmp. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3774 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209000 91177308-0d34-0410-b5e6-96231b3b80d8
* InstSimplify: Optimize using dividend in sdivDavid Majnemer2014-05-16
| | | | | | | | | | | | | | | Summary: The dividend in an sdiv tells us the largest and smallest possible results. Use this fact to optimize comparisons against an sdiv with a constant dividend. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3795 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208999 91177308-0d34-0410-b5e6-96231b3b80d8
* Add C API for thread yielding callback.Juergen Ributzka2014-05-16
| | | | | | | | | | | | | | | | | | | | | Sometimes a LLVM compilation may take more time then a client would like to wait for. The problem is that it is not possible to safely suspend the LLVM thread from the outside. When the timing is bad it might be possible that the LLVM thread holds a global mutex and this would block any progress in any other thread. This commit adds a new yield callback function that can be registered with a context. LLVM will try to yield by calling this callback function, but there is no guaranteed frequency. LLVM will only do so if it can guarantee that suspending the thread won't block any forward progress in other LLVM contexts in the same process. Once the client receives the call back it can suspend the thread safely and resume it at another time. Related to <rdar://problem/16728690> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208945 91177308-0d34-0410-b5e6-96231b3b80d8
* Instead of littering asserts throughout the code after every call toJay Foad2014-05-15
| | | | | | | computeKnownBits, consolidate them into one assert at the end of computeKnownBits itself. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208876 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach the constant folder to look through bitcast constant expressionsChandler Carruth2014-05-15
| | | | | | | | | | | | | | | | | | | | | | | | | | much more effectively when trying to constant fold a load of a constant. Previously, we only handled bitcasts by trying to find a totally generic byte representation of the constant and use that. Now, we look through the bitcast to see what constant we might fold the load into, and then try to form a constant expression cast of the found value that would be equivalent to loading the value. You might wonder why on earth this actually matters. Well, turns out that the Itanium ABI causes us to create a single array for a vtable where the first elements are virtual base offsets, followed by the virtual function pointers. Because the array is homogenous the element type is consistently i8* and we inttoptr the virtual base offsets into the initial elements. Then constructors bitcast these pointers to i64 pointers prior to loading them. Boom, no more constant folding of virtual base offsets. This is the first fix to LLVM to address the *insane* performance Eric Niebler discovered with Clang on his range comprehensions[1]. There is more to come though, this doesn't *really* fix the problem fully. [1]: http://ericniebler.com/2014/04/27/range-comprehensions/ git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208856 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix typosAlp Toker2014-05-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208839 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename ComputeMaskedBits to computeKnownBits. "Masked" has beenJay Foad2014-05-14
| | | | | | inappropriate since it lost its Mask parameter in r154011. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208811 91177308-0d34-0410-b5e6-96231b3b80d8
* InstSimplify: Optimize signed icmp of -(zext V)David Majnemer2014-05-14
| | | | | | | | | | | | | | | | Summary: We know that -(zext V) will always be <= zero, simplify signed icmps that have these. Uncovered using http://www.cs.utah.edu/~regehr/souper/ Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3754 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208809 91177308-0d34-0410-b5e6-96231b3b80d8
* Update the comments for ComputeMaskedBits, which lost its Mask parameterJay Foad2014-05-14
| | | | | | in r154011. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208757 91177308-0d34-0410-b5e6-96231b3b80d8
* use nullptr instead of NULLSebastian Pop2014-05-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208622 91177308-0d34-0410-b5e6-96231b3b80d8
* do not assert when delinearization failsSebastian Pop2014-05-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208615 91177308-0d34-0410-b5e6-96231b3b80d8
* use isZero()Sebastian Pop2014-05-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208614 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEV: Use range-based for loop and fold variable into assert.Benjamin Kramer2014-05-10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208476 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-28 02:39:54 +0000