summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [ValueTracking] do not overwrite analysis results already computedJingyue Wu2015-06-151-146/+160
| | | | | | | | | | | | | | | | | | Summary: ValueTracking used to overwrite the analysis results computed from assumes and dominating conditions. This patch fixes this issue. Test Plan: test/Analysis/ValueTracking/assume.ll Reviewers: hfinkel, majnemer Reviewed By: majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10283 llvm-svn: 239718
* [InstSimplify] fsub nnan x, x -> 0.0 is valid without ninfBenjamin Kramer2015-06-141-2/+2
| | | | | | | Both inf - inf and (-inf) - (-inf) are NaN, so it's already covered by nnan. llvm-svn: 239702
* [InstSimplify] Add self-fdiv identities for -ffinite-math-only.Benjamin Kramer2015-06-141-0/+15
| | | | | | | | | When NaNs and Infs are ignored we can fold X / X -> 1.0 -X / X -> -1.0 X / -X -> -1.0 llvm-svn: 239701
* Don't create instructions from ConstantExpr's in CFLAliasAnalysis.Pete Cooper2015-06-121-12/+41
| | | | | | | | | | The CFLAA code currently calls ConstantExpr::getAsInstruction which creates an instruction from a constant expr. We then pass that instruction to the InstVisitor to analyze it. Its not necessary to create these instructions as we can just cast from Constant to Operator in the visitor. This is how other InstVisitor’s such as SelectionDAGBuilder handle ConstantExpr. llvm-svn: 239616
* Rangify for loops, NFC.Yaron Keren2015-06-121-8/+6
| | | | llvm-svn: 239596
* [GVN] Set proper debug locations for some instructions created by GVN.Alexey Samsonov2015-06-101-3/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Determining proper debug locations for instructions created in PHITransAddr is tricky. We use a simple approach here and simply copy debug locations from instructions computing load address to "corresponding" instructions re-creating the address computation in predecessor basic blocks. This may not always be correct, given all the rearrangement and simplification going on, and debug locations may jump around a lot, as the basic blocks we copy locations between may be very far from each other. Still, this would work good in most simple cases (e.g. when chain of address computing instruction is short, or our mapping turns out to be 1-to-1), and we desire to have *some* reasonable debug locations associated with newly inserted instructions. See http://reviews.llvm.org/D10351 review thread for more details. Test Plan: regression test suite Reviewers: spatel, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10351 llvm-svn: 239479
* Replace loop with std::equal. NFC intended.Benjamin Kramer2015-06-091-7/+1
| | | | llvm-svn: 239430
* Minor refactoring of GEP handling in isDereferenceablePointerArtur Pilipenko2015-06-081-28/+15
| | | | | | | | | | For GEP instructions isDereferenceablePointer checks that all indices are constant and within bounds. Replace this index calculation logic to a call to accumulateConstantOffset. Separated from the http://reviews.llvm.org/D9791 Reviewed By: sanjoy Differential Revision: http://reviews.llvm.org/D9874 llvm-svn: 239299
* [LAA] Fix estimation of number of memchecksSilviu Baranga2015-06-081-38/+34
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: We need to add a runtime memcheck for pair of accesses (x,y) where at least one of x and y are writes. Assuming we have w writes and r reads, currently this number is estimated as being w* (w+r-1). This estimation will count (write,write) pairs twice and will overestimate the number of checks required. This change adds a getNumberOfChecks method to RuntimePointerCheck, which will count the number of runtime checks needed (similar in implementation to needsAnyChecking) and uses it to produce the correct number of runtime checks. Test Plan: llvm test suite spec2k spec2k6 Performance results: no changes observed (not surprising since the formula for 1 writer is basically the same, which would covers most cases - at least with the current check limit). Reviewers: anemet Reviewed By: anemet Subscribers: mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D10217 llvm-svn: 239295
* [LoopVectorize] Teach Loop Vectorizor about interleaved memory accesses.Hao Liu2015-06-082-7/+9
| | | | | | | | | | | | | | | | | | | | | | | | Interleaved memory accesses are grouped and vectorized into vector load/store and shufflevector. E.g. for (i = 0; i < N; i+=2) { a = A[i]; // load of even element b = A[i+1]; // load of odd element ... // operations on a, b, c, d A[i] = c; // store of even element A[i+1] = d; // store of odd element } The loads of even and odd elements are identified as an interleave load group, which will be transfered into vectorized IRs like: %wide.vec = load <8 x i32>, <8 x i32>* %ptr %vec.even = shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 0, i32 2, i32 4, i32 6> %vec.odd = shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 1, i32 3, i32 5, i32 7> The stores of even and odd elements are identified as an interleave store group, which will be transfered into vectorized IRs like: %interleaved.vec = shufflevector <4 x i32> %vec.even, %vec.odd, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7> store <8 x i32> %interleaved.vec, <8 x i32>* %ptr This optimization is currently disabled by defaut. To try it by adding '-enable-interleaved-mem-accesses=true'. llvm-svn: 239291
* [LoopAccessAnalysis] Teach LAA to check the memory dependence between ↵Hao Liu2015-06-081-12/+101
| | | | | | | | strided accesses. Differential Revision: http://reviews.llvm.org/D9368 llvm-svn: 239285
* Add isLegalAddressingMode address space argument to TTIMatt Arsenault2015-06-071-4/+6
| | | | | | | Update to match the TLI version, and remove the TLI version's default argument. llvm-svn: 239260
* [InstCombine, InstSimplify] Move xforms from Combine to SimplifyDavid Majnemer2015-06-061-11/+138
| | | | | | | | There were several SelectInst combines that always returned an existing instruction instead of modifying an old one or creating a new one. These are prime candidates for moving to InstSimplify. llvm-svn: 239229
* [PM/AA] Start refactoring AliasAnalysis to remove the analysis group andChandler Carruth2015-06-046-92/+111
| | | | | | | | | | | | | | | | | | | | | port it to the new pass manager. All this does is extract the inner "location" class used by AA into its own full fledged type. This seems *much* cleaner as MemoryDependence and soon MemorySSA also use this heavily, and it doesn't make much sense being inside the AA infrastructure. This will also make it much easier to break apart the AA infrastructure into something that stands on its own rather than using the analysis group design. There are a few places where this makes APIs not make sense -- they were taking an AliasAnalysis pointer just to build locations. I'll try to clean those up in follow-up commits. Differential Revision: http://reviews.llvm.org/D10228 llvm-svn: 239003
* [PHITransAddr] Don't translate unreachable valuesDavid Majnemer2015-06-012-9/+13
| | | | | | | | | | | Unreachable values may use themselves in strange ways due to their dominance property. Attempting to translate through them can lead to infinite recursion, crashing LLVM. Instead, claim that we weren't able to translate the value. This fixes PR23096. llvm-svn: 238702
* [PHITransAddr] Use std::find instead of std::countDavid Majnemer2015-06-011-2/+4
| | | | | | | There is no need to visit all the elements if we are merely performing a membership check. NFCI. llvm-svn: 238701
* Replace push_back(Constructor(foo)) with emplace_back(foo) for non-trivial typesBenjamin Kramer2015-05-292-4/+4
| | | | | | | | | | | | | | | | | | | | If the type isn't trivially moveable emplace can skip a potentially expensive move. It also saves a couple of characters. Call sites were found with the ASTMatcher + some semi-automated cleanup. memberCallExpr( argumentCountIs(1), callee(methodDecl(hasName("push_back"))), on(hasType(recordDecl(has(namedDecl(hasName("emplace_back")))))), hasArgument(0, bindTemporaryExpr( hasType(recordDecl(hasNonTrivialDestructor())), has(constructExpr()))), unless(isInTemplateInstantiation())) No functional change intended. llvm-svn: 238602
* [DependenceAnalysis] Extend unifySubscriptType for handling coupled ↵Jingyue Wu2015-05-291-17/+53
| | | | | | | | | | | | | | | | | | | | | | | subscript groups. Summary: In continuation to an earlier commit to DependenceAnalysis.cpp by jingyue (r222100), the type for all subscripts in a coupled group need to be the same since constraints from one subscript may be propagated to another during testing. During testing, new SCEVs may be created and the operands for these need to be the same. This patch extends unifySubscriptType() to work on lists of subscript pairs, ensuring a common extended type for all of them. Test Plan: Added a test case to NonCanonicalizedSubscript.ll which causes dependence analysis to crash without this fix. All regression tests pass. Reviewers: spop, sebpop, jingyue Reviewed By: jingyue Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9698 llvm-svn: 238573
* Enable exitValue rewrite only when the cost of expansion is low.Wei Mi2015-05-281-9/+25
| | | | | | | | The patch evaluates the expansion cost of exitValue in indVarSimplify pass, and only does the rewriting when the expansion cost is low or loop can be deleted with the rewriting. It provides an option "-replexitval=" to control the default aggressiveness of the exitvalue rewriting. It also fixes some missing cases in SCEVExpander::isHighCostExpansionHelper to enhance the evaluation of SCEV expansion cost. Differential Revision: http://reviews.llvm.org/D9800 llvm-svn: 238507
* Add BranchProbabilityInfo::releaseMemory to clear the Weights field.Pete Cooper2015-05-281-0/+4
| | | | | | | | BranchProbabilityInfo was leaking 3MB of memory when running 'opt -O2 verify-uselistorder.lto.bc'. This was due to the Weights member not being cleared once the pass is no longer needed. This adds the releaseMemory override to clear that field. The other fields are cleared at the end of runOnFunction so can stay there. llvm-svn: 238462
* [inliner] Fix the early-exit of the inline cost analysis to correctlyChandler Carruth2015-05-271-25/+32
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | model the dense vector instruction bonuses. Previously, this code really didn't effectively compute the density of inlined vector instructions and apply the intended inliner bonus. It would try to compute it repeatedly while analyzing the function and didn't handle the case where future vector instructions would tip the scales back towards the bonus. Instead, speculatively apply all possible bonuses to the threshold initially. Once we *know* that a certain bonus can not be applied, subtract it. This should delay early bailout enough to get much more consistent results without actually causing us to analyze huge swaths of code. I expect some (hopefully mild) compile time hit here, and some swings in performance, but this was definitely the intended behavior of these bonuses. This also dramatically simplifies the computation of the bonuses to not interact with each other in confusing ways. The previous code didn't do a good job of this and the values for bonuses may be surprising but are at least now clearly written in the code. Finally, fix code to be in line with comments and use zero as the bailout condition. Patch by Easwaran Raman, with some comment tweaks by me to try and further clarify what is going on with this code. http://reviews.llvm.org/D8267 llvm-svn: 238276
* [InstSimplify] Handle some overflow intrinsics in InstSimplifyDavid Majnemer2015-05-221-5/+43
| | | | | | | | | This change does a few things: - Move some InstCombine transforms to InstSimplify - Run SimplifyCall from within InstCombine::visitCallInst - Teach InstSimplify to fold [us]mul_with_overflow(X, undef) to 0. llvm-svn: 237995
* Revert r236894 "[BasicAA] Fix zext & sext handling"Hans Wennborg2015-05-221-199/+60
| | | | | | This seems to have caused PR23626: Clang miscompiles webkit's base64 decoder llvm-svn: 237984
* Test commit. Fix typo in MemDerefPrinter.cpp comment.Artur Pilipenko2015-05-211-1/+1
| | | | llvm-svn: 237893
* Reapply r237539 with a fix for the Chromium build.James Molloy2015-05-201-2/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Make sure if we're truncating a constant that would then be sign extended that the sign extension of the truncated constant is the same as the original constant. > Canonicalize min/max expressions correctly. > > This patch introduces a canonical form for min/max idioms where one operand > is extended or truncated. This often happens when the other operand is a > constant. For example: > > %1 = icmp slt i32 %a, i32 0 > %2 = sext i32 %a to i64 > %3 = select i1 %1, i64 %2, i64 0 > > Would now be canonicalized into: > > %1 = icmp slt i32 %a, i32 0 > %2 = select i1 %1, i32 %a, i32 0 > %3 = sext i32 %2 to i64 > > This builds upon a patch posted by David Majenemer > (https://www.marc.info/?l=llvm-commits&m=143008038714141&w=2). That pass > passively stopped instcombine from ruining canonical patterns. This > patch additionally actively makes instcombine canonicalize too. > > Canonicalization of expressions involving a change in type from int->fp > or fp->int are not yet implemented. llvm-svn: 237821
* Change Function::getIntrinsicID() to return an Intrinsic::ID. NFC.Pete Cooper2015-05-202-3/+3
| | | | | | | | Now that Intrinsic::ID is a typed enum, we can forward declare it and so return it from this method. This updates all users which were either using an unsigned to store it, or had a now unnecessary cast. llvm-svn: 237810
* Dereferenceable, dereferenceable_or_null metadata for loadsSanjoy Das2015-05-191-0/+13
| | | | | | | | | | | | | | | | | | | | Summary: Introduce dereferenceable, dereferenceable_or_null metadata for loads with the same semantic as corresponding attributes. This patch depends on http://reviews.llvm.org/D9253 Patch by Artur Pilipenko! Reviewers: hfinkel, sanjoy, reames Reviewed By: sanjoy, reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9365 llvm-svn: 237720
* Exploit dereferenceable_or_null attribute in LICM passSanjoy Das2015-05-181-17/+99
| | | | | | | | | | | | | | | | | | | | Summary: Allow hoisting of loads from values marked with dereferenceable_or_null attribute. For values marked with the attribute perform context-sensitive analysis to determine whether it's known-non-null or not. Patch by Artur Pilipenko! Reviewers: hfinkel, sanjoy, reames Reviewed By: reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9253 llvm-svn: 237593
* [ScalarEvolution] refactor: extract interface getGEPExprJingyue Wu2015-05-181-41/+55
| | | | | | | | | | | | | | | | | | Summary: This allows other passes (such as SLSR) to compute the SCEV expression for an imaginary GEP. Test Plan: no regression Reviewers: atrick, sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9786 llvm-svn: 237589
* [LoopAccesses] If shouldRetryWithRuntimeCheck, reset InterestingDependencesAdam Nemet2015-05-181-2/+7
| | | | | | | | When dependence analysis encounters a non-constant distance between memory accesses it aborts the analysis and falls back to run-time checks only. In this case we weren't resetting the array of dependences. llvm-svn: 237574
* [LoopAccesses] Rearrange printed lines in -analyzeAdam Nemet2015-05-181-4/+4
| | | | | | | "Store to invariant address..." is moved as the last line. This is not the prime result of the analysis. Plus it simplifies some of the tests. llvm-svn: 237573
* [LoopAccesses] Debug improvementAdam Nemet2015-05-181-0/+1
| | | | | | Report pointers with unknown bounds. llvm-svn: 237572
* Allow min/max detection to see through casts.James Molloy2015-05-151-14/+56
| | | | | | | | | | | | | | This teaches the min/max idiom detector in ValueTracking to see through casts such as SExt/ZExt/Trunc. SCEV can already do this, so we're bringing non-SCEV analyses up to the same level. The returned LHS/RHS will not match the type of the original SelectInst any more, so a CastOp is returned too to inform the caller how to convert to the SelectInst's type. No in-tree users yet; this will be used by InstCombine in a followup. llvm-svn: 237452
* [DependenceAnalysis] Fix for PR21585: collectUpperBound triggers assertsJames Molloy2015-05-151-2/+20
| | | | | | | | | | collectUpperBound hits an assertion when the back edge count is wider then the desired type. If that happens, truncate the backedge count. Patch by Philip Pfaffe! llvm-svn: 237439
* [ValueTracking] refactor: extract method haveNoCommonBitsSetJingyue Wu2015-05-141-0/+15
| | | | | | | | | | | | | | | | | | | | | Summary: Extract method haveNoCommonBitsSet so that we don't have to duplicate this logic in InstCombine and SeparateConstOffsetFromGEP. This patch also makes SeparateConstOffsetFromGEP more precise by passing DominatorTree to computeKnownBits. Test Plan: value-tracking-domtree.ll that tests ValueTracking indeed leverages dominating conditions Reviewers: broune, meheff, majnemer Reviewed By: majnemer Subscribers: jholewinski, llvm-commits Differential Revision: http://reviews.llvm.org/D9734 llvm-svn: 237407
* [ConstantFolding] Fix wrong folding of intrinsic 'convert.from.fp16'.Andrea Di Biagio2015-05-141-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Function 'ConstantFoldScalarCall' (in ConstantFolding.cpp) works under the wrong assumption that a call to 'convert.from.fp16' returns a value of type 'float'. However, intrinsic 'convert.from.fp16' can be overloaded; for example, we can call 'convert.from.fp16.f64' to convert from half to double; etc. Before this patch, the following example would have triggered an assertion failure in opt (with -constprop): ``` define double @foo() { entry: %0 = call double @llvm.convert.from.fp16.f64(i16 0) ret double %0 } ``` This patch fixes the problem in ConstantFolding.cpp. When folding a call to convert.from.fp16, we perform a different kind of conversion based on the call return type. Added test 'Transform/ConstProp/convert-from-fp16.ll'. Differential Revision: http://reviews.llvm.org/D9771 llvm-svn: 237377
* Add llvm::all_of which wraps std::all_of.Pete Cooper2015-05-131-5/+1
| | | | | | | | | | This version doesn't need begin/end but can instead just take a type which has begin/end methods. Use this to replace an eligible foreach loop in LoopInfo found by David Blaikie in r237224. Reviewed by David Blaikie. llvm-svn: 237301
* Test commit: Remove unnecessary spaces.Teresa Johnson2015-05-131-1/+1
| | | | llvm-svn: 237259
* Constify arguments in AliasSetTracker methods. NFCPete Cooper2015-05-131-4/+5
| | | | llvm-svn: 237225
* Change a loop in LoopInfo to foreach. NFCPete Cooper2015-05-131-2/+2
| | | | llvm-svn: 237224
* Constify arguments to methods in LoopInfo. NFCPete Cooper2015-05-131-3/+3
| | | | llvm-svn: 237223
* Convert PHI getIncomingValue() to foreach over incoming_values(). NFC.Pete Cooper2015-05-125-21/+15
| | | | | | | | We already had a method to iterate over all the incoming values of a PHI. This just changes all eligible code to use it. Ineligible code included anything which cared about the index, or was also trying to get the i'th incoming BB. llvm-svn: 237169
* Rip min/max pattern matching out of InstCombine and intoJames Molloy2015-05-111-0/+81
| | | | | | | | | | | ValueTracking. This matching functionality is useful in more than just InstCombine, so make it available in ValueTracking. NFC. llvm-svn: 236998
* [BasicAA] Fix zext & sext handlingSanjoy Das2015-05-081-60/+199
| | | | | | | | | | | | | | | | | | | | | | | Summary: There are several unhandled edge cases in BasicAA's GetLinearExpression method. This changes fixes outstanding issues, including zext / sext of a constant with the sign bit set, and the refusal to decompose zexts or sexts of wrapping arithmetic. Test Plan: Unit tests added in //q.ext.ll//. Patch by Nick White. Reviewers: hfinkel, sanjoy Reviewed By: hfinkel, sanjoy Subscribers: sanjoy, llvm-commits, hfinkel Differential Revision: http://reviews.llvm.org/D6682 llvm-svn: 236894
* Fix information loss in branch probability computation.Diego Novillo2015-05-071-12/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This addresses PR 22718. When branch weights are too large, they were being clamped to the range [1, MaxWeightForBB]. But this clamping is only applied to edges that go outside the range, so it distorts the relative branch probabilities. This patch changes the weight calculation to scale every branch so the relative probabilities are preserved. The scaling is done differently now. First, all the branch weights are added up, and if the sum exceeds 32 bits, it computes an integer scale to bring all the weights within the range. The patch fixes an existing test that had slightly wrong branch probabilities due to the previous clamping. It now gets branch weights scaled accordingly. Reviewers: dexonsmith Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9442 llvm-svn: 236750
* Populate list of vectorizable functions for Accelerate library.Michael Zolotukhin2015-05-071-4/+32
| | | | | | | | | | | | | | | | | | | Summary: This patch adds majority of supported by Accelerate library functions to the list of vectorizable functions. The full list of available vector functions could be found here: https://developer.apple.com/library/mac/documentation/Performance/Conceptual/vecLib/index.html Test Plan: Unit tests are added. Reviewers: hfinkel, aschwaighofer, nadav Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9543 llvm-svn: 236747
* Added support for building against Android API-9 SDKVince Harron2015-05-071-1/+1
| | | | | | | | | | Created an abstraction for log2, llvm::Log2 in Support/MathExtras.h Hid Android problems inside of it Differential Revision: http://reviews.llvm.org/D9467 llvm-svn: 236680
* Allow 0-weight branches in BranchProbabilityInfo.Diego Novillo2015-05-061-5/+7
| | | | | | | | | | | | | | | | | | | | | | | Summary: When computing branch weights in BPI, we used to disallow branches with weight 0. This is a minor nuisance, because a branch with weight 0 is different to "don't have information". In the context of instrumentation, it may mean "never executed", in the context of sampling, it means "never or seldom executed". In allowing 0 weight branches, I ran into issues with the switch expansion code in selection DAG. It is currently hardwired to not handle branches with weight 0. To maintain the current behaviour, I changed it to use 1 when it finds 0, but perhaps the algorithm needs changes to tolerate branches with weight zero. Reviewers: hansw Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9533 llvm-svn: 236617
* [X86] Disable loop unrolling in loop vectorization pass when VF is 1.Wei Mi2015-05-061-2/+2
| | | | | | | | | | | | | The patch disabled unrolling in loop vectorization pass when VF==1 on x86 architecture, by setting MaxInterleaveFactor to 1. Unrolling in loop vectorization pass may introduce the cost of overflow check, memory boundary check and extra prologue/epilogue code when regular unroller will unroll the loop another time. Disable it when VF==1 remove the unnecessary cost on x86. The same can be done for other platforms after verifying interleaving/memory bound checking to be not perf critical on those platforms. Differential Revision: http://reviews.llvm.org/D9515 llvm-svn: 236613
* [Statepoint] Clean up Statepoint.h: accessor names.Sanjoy Das2015-05-061-1/+2
| | | | | | Use getFoo() as accessors consistently and some other naming changes. llvm-svn: 236564
OpenPOWER on IntegriCloud