summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [SCEV] Make getUDivExactExpr handle non-nuw multiplies correctly.Eli Friedman2017-01-181-16/+21
| | | | | | | | | | | | | | | | | To avoid regressions, make ScalarEvolution::createSCEV a bit more clever. Also get rid of some useless code in ScalarEvolution::howFarToZero which was hiding this bug. No new testcase because it's impossible to actually expose this bug: we don't have any in-tree users of getUDivExactExpr besides the two functions I just mentioned, and they both dodged the problem. I'll try to add some interesting users in a followup. Differential Revision: https://reviews.llvm.org/D28587 llvm-svn: 292449
* Improve the `-filter-print-funcs` option to skip the banner for CGSCC pass ↵Mehdi Amini2017-01-181-3/+13
| | | | | | | | | | | | | | | when nothing is to be printed Before, it would print a sequence of: *** IR Dump After Function Integration/Inlining ****** *** IR Dump After Function Integration/Inlining ****** *** IR Dump After Function Integration/Inlining ****** ... for every single function in the module. llvm-svn: 292442
* [TLI] Appease spurious MSVC warning using llvm_unreachable. NFC.Ahmed Bougacha2017-01-171-1/+2
| | | | | | | | | | | | | r292188 confused MSVC because of the combined lack of a default case and return statement. Move the unreachable outside of the NumLibFuncs case, to make it obvious that all cases should be handled. llvm_unreachable is __declspec(noreturn), so I'm assuming this does appease MSVC. llvm-svn: 292246
* [ValueTracking] recognize a 'not' of an assumed condition as falseSanjay Patel2017-01-172-3/+12
| | | | | | | | Also, add the corresponding match to the AssumptionCache's 'Affected Values' list. Differential Revision: https://reviews.llvm.org/D28485 llvm-svn: 292239
* [ValueTracking] Extend known bits to understand @llvm.bitreverse.Chad Rosier2017-01-171-0/+5
| | | | | | Differential Revision: https://reviews.llvm.org/D28780 llvm-svn: 292233
* [TLI] Add prototype checking for all remaining LibFuncs.Ahmed Bougacha2017-01-171-31/+186
| | | | | | | | | | | | | | This is another step towards unifying all LibFunc prototype checks. This work started in r267758 (D19469); add the remaining checks. Also add a unittest that checks each libfunc declared with a known-valid and known-invalid prototype. New libfuncs added in the future are required to have prototype checking in place; the known-valid test will fail otherwise. Differential Revision: https://reviews.llvm.org/D28030 llvm-svn: 292188
* [TLI] Alphabetize some of the prototype check switch. NFC.Ahmed Bougacha2017-01-171-27/+27
| | | | llvm-svn: 292187
* Fix use-after-free bug in AffectedValueCallbackVH::allUsesReplacedWithHal Finkel2017-01-161-10/+17
| | | | | | | | | | | | | When transferring affected values in the cache from an old value, identified by the value of the current callback, to the specified new value we might need to insert a new entry into the DenseMap which constitutes the cache. Doing so might delete the current callback object. Move the copying logic into a new function, a member of the assumption cache itself, so that we don't run into UB should the callback handle itself be removed mid-copy. Differential Revision: https://reviews.llvm.org/D28749 llvm-svn: 292133
* Use getLoopLatch in place of isLoopSimplifyFormXin Tong2017-01-151-4/+7
| | | | | | | | | | | | | | Summary: Use getLoopLatch in place of isLoopSimplifyForm. we do not need to know whether the loop has a preheader nor dedicated exits. Reviewers: hfinkel, sanjoy, atrick, mkuper Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D28724 llvm-svn: 292078
* Reverted: Track validity of pass resultsSerge Pavlov2017-01-154-7/+2
| | | | | | Commits r291882 and related r291887. llvm-svn: 292062
* [PM] Teach the optimization remarks emitter to handle invalidationChandler Carruth2017-01-151-0/+12
| | | | | | | | | | events. This pass sometimes has a pointer to BlockFrequencyInfo so it needs custom invalidation logic. It is also otherwise immutable so we can reduce the number of invalidations that happen substantially. llvm-svn: 292058
* [PM] Introduce an analysis set used to preserve all analyses overChandler Carruth2017-01-155-0/+46
| | | | | | | | | | | | | | | a function's CFG when that CFG is unchanged. This allows transformation passes to simply claim they preserve the CFG and analysis passes to check for the CFG being preserved to remove the fanout of all analyses being listed in all passes. I've gone through and removed or cleaned up as many of the comments reminding us to do this as I could. Differential Revision: https://reviews.llvm.org/D28627 llvm-svn: 292054
* [PM] The assumption cache is fundamentally designed to be self-updating,Chandler Carruth2017-01-151-1/+0
| | | | | | | | | | | | | | mark it as never invalidated in the new PM. The old PM already required this to work, and after a discussion with Hal this seems to really be the only sensible answer. The cache gracefully degrades as the IR is mutated, and most things which do this should already be incrementally updating the cache. This gets rid of a bunch of logic preserving and testing the invalidation of this analysis. llvm-svn: 292039
* Removing potentially error-prone fallthrough. NFCMarcello Maggioni2017-01-141-0/+1
| | | | | | | | This fallthrough if other cases are added between fabs and default could cause fabs to fall to the next case resulting in a bug. Better getting rid of it immediately just to be sure. llvm-svn: 292003
* Compute summary before calling extractProfTotalWeightEaswaran Raman2017-01-141-11/+11
| | | | | | | | | | extractProfTotalWeight checks if the profile type is sample profile, but before that we have to ensure that summary is available. Also expanded the unittest to test the case where there is no summar Differential Revision: https://reviews.llvm.org/D28708 llvm-svn: 291982
* [SCEV] Limit recursion depth of constant evolving.Michael Liao2017-01-131-3/+10
| | | | | | | | | | - For a loop body with VERY complicated exit condition evaluation, constant evolving may run out of stack on platforms such as Windows. Need to limit the recursion depth. Differential Revision: https://reviews.llvm.org/D28629 llvm-svn: 291927
* Remove unused lambda captures. NFCMalcolm Parsons2017-01-131-3/+3
| | | | llvm-svn: 291916
* Apply clang-tidy's performance-unnecessary-value-param to LLVM.Benjamin Kramer2017-01-131-2/+2
| | | | | | | With some minor manual fixes for using function_ref instead of std::function. No functional change intended. llvm-svn: 291904
* RegionPass: Set isExecuted flag correctlyTobias Grosser2017-01-131-0/+1
| | | | | | | This was forgotten in r291882. Without this fix, the Polly build bots are broken. llvm-svn: 291887
* Track validity of pass resultsSerge Pavlov2017-01-133-2/+6
| | | | | | | | | | | | | | | | | | | | | | | | Running tests with expensive checks enabled exhibits some problems with verification of pass results. First, the pass verification may require results of analysis that are not available. For instance, verification of loop info requires results of dominator tree analysis. A pass may be marked as conserving loop info but does not need to be dependent on DominatorTreePass. When a pass manager tries to verify that loop info is valid, it needs dominator tree, but corresponding analysis may be already destroyed as no user of it remained. Another case is a pass that is skipped. For instance, entities with linkage available_externally do not need code generation and such passes are skipped for them. In this case result verification must also be skipped. To solve these problems this change introduces a special flag to the Pass structure to mark passes that have valid results. If this flag is reset, verifications dependent on the pass result are skipped. Differential Revision: https://reviews.llvm.org/D27190 llvm-svn: 291882
* ProfileSummaryInfo improvements.Easwaran Raman2017-01-131-5/+48
| | | | | | | | | | | * Add is{Hot|Cold}CallSite methods * Fix a bug in isHotBB where it was looking for MD_prof on a return instruction * Use MD_prof data only if sample profiling was used to collect profiles. * Add an unit test to ProfileSummaryInfo Differential Revision: https://reviews.llvm.org/D28584 llvm-svn: 291878
* [SCEV] Simplify SolveLinEquationWithOverflow a bit.Eli Friedman2017-01-121-7/+8
| | | | | | Cleanup in preparation for generalizing it. llvm-svn: 291808
* [Devirtualization] MemDep returns non-local !invariant.group dependenciesPiotr Padlewski2017-01-121-8/+55
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Memory Dependence Analysis was limited to return only local dependencies for invariant.group handling. Now it returns NonLocal when it finds it and then by asking getNonLocalPointerDependency we get found dep. Thanks to this we are able to devirtualize loops! void indirect(A &a, int n) { for (int i = 0 ; i < n; i++) a.foo(); } void test(int n) { A a; indirect(a); } After inlining a.foo() will be changed to direct call, even if foo and A::A() is external (but only if vtable definition is be available). Reviewers: nlewycky, dberlin, chandlerc, rsmith Subscribers: mehdi_amini, davide, llvm-commits Differential Revision: https://reviews.llvm.org/D28137 llvm-svn: 291762
* [SCEV] Make howFarToZero max backedge-taken count check for precondition.Eli Friedman2017-01-111-0/+17
| | | | | | | | | Refines max backedge-taken count if a loop like "for (int i = 0; i != n; ++i) { /* body */ }" is rotated. Differential Revision: https://reviews.llvm.org/D28536 llvm-svn: 291704
* [SCEV] Make howFarToZero use a simpler formula for max backedge-taken count.Eli Friedman2017-01-111-11/+2
| | | | | | | | | This is both easier to understand, and produces a tighter bound in certain cases. Differential Revision: https://reviews.llvm.org/D28393 llvm-svn: 291701
* [MemDep] NFC variable name changePiotr Padlewski2017-01-111-3/+3
| | | | llvm-svn: 291679
* Make processing @llvm.assume more efficient - Add affected values to the ↵Hal Finkel2017-01-113-2/+114
| | | | | | | | | | | | | | | | | | | | | | | | assumption cache Here's my second try at making @llvm.assume processing more efficient. My previous attempt, which leveraged operand bundles, r289755, didn't end up working: it did make assume processing more efficient but eliminating the assumption cache made ephemeral value computation too expensive. This is a more-targeted change. We'll keep the assumption cache, but extend it to keep a map of affected values (i.e. values about which an assumption might provide some information) to the corresponding assumption intrinsics. This allows ValueTracking and LVI to find assumptions relevant to the value being queried without scanning all assumptions in the function. The fact that ValueTracking started doing O(number of assumptions in the function) work, for every known-bits query, has become prohibitively expensive in some cases. As discussed during the review, this is a pragmatic fix that, longer term, will likely be replaced by a more-principled solution (perhaps based on an extended SSA form). Differential Revision: https://reviews.llvm.org/D28459 llvm-svn: 291671
* [PM] Separate the LoopAnalysisManager from the LoopPassManager and moveChandler Carruth2017-01-115-95/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | the latter to the Transforms library. While the loop PM uses an analysis to form the IR units, the current plan is to have the PM itself establish and enforce both loop simplified form and LCSSA. This would be a layering violation in the analysis library. Fundamentally, the idea behind the loop PM is to *transform* loops in addition to running passes over them, so it really seemed like the most natural place to sink this was into the transforms library. We can't just move *everything* because we also have loop analyses that rely on a subset of the invariants. So this patch splits the the loop infrastructure into the analysis management that has to be part of the analysis library, and the transform-aware pass manager. This also required splitting the loop analyses' printer passes out to the transforms library, which makes sense to me as running these will transform the code into LCSSA in theory. I haven't split the unittest though because testing one component without the other seems nearly intractable. Differential Revision: https://reviews.llvm.org/D28452 llvm-svn: 291662
* [X86] updating TTI costs for arithmetic instructions on X86\SLM arch.Mohammed Agabaria2017-01-112-3/+7
| | | | | | | | | | | | updated instructions: pmulld, pmullw, pmulhw, mulsd, mulps, mulpd, divss, divps, divsd, divpd, addpd and subpd. special optimization case which replaces pmulld with pmullw\pmulhw\pshuf seq. In case if the real operands bitwidth <= 16. Differential Revision: https://reviews.llvm.org/D28104 llvm-svn: 291657
* [PM] Rewrite the loop pass manager to use a worklist and augmented runChandler Carruth2017-01-115-54/+198
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | arguments much like the CGSCC pass manager. This is a major redesign following the pattern establish for the CGSCC layer to support updates to the set of loops during the traversal of the loop nest and to support invalidation of analyses. An additional significant burden in the loop PM is that so many passes require access to a large number of function analyses. Manually ensuring these are cached, available, and preserved has been a long-standing burden in LLVM even with the help of the automatic scheduling in the old pass manager. And it made the new pass manager extremely unweildy. With this design, we can package the common analyses up while in a function pass and make them immediately available to all the loop passes. While in some cases this is unnecessary, I think the simplicity afforded is worth it. This does not (yet) address loop simplified form or LCSSA form, but those are the next things on my radar and I have a clear plan for them. While the patch is very large, most of it is either mechanically updating loop passes to the new API or the new testing for the loop PM. The code for it is reasonably compact. I have not yet updated all of the loop passes to correctly leverage the update mechanisms demonstrated in the unittests. I'll do that in follow-up patches along with improved FileCheck tests for those passes that ensure things work in more realistic scenarios. In many cases, there isn't much we can do with these until the loop simplified form and LCSSA form are in place. Differential Revision: https://reviews.llvm.org/D28292 llvm-svn: 291651
* InstSimplify: Refactor function to use more switchesMatt Arsenault2017-01-111-38/+51
| | | | llvm-svn: 291634
* InstSimplify: Eliminate fabs on known positiveMatt Arsenault2017-01-112-22/+64
| | | | llvm-svn: 291624
* Refactor inline threshold update code.Easwaran Raman2017-01-091-22/+19
| | | | | | | | | | Functional change: Previously, if a callee is cold, we used ColdThreshold if it minimizes the existing threshold. This was irrespective of whether we were optimizing for minsize (-Oz) or not. But -Oz uses very low threshold to begin with and the inlining with -Oz is expected to be tuned for lowering code size, so there is no good reason to set an even lower threshold for cold callees. We now lower the threshold for cold callees only when -Oz is not used. For default values of -inlinethreshold and -inlinecold-threshold, this change has no effect and this simplifies the code. NFC changes: Group all threshold updates that are guarded by !Caller->optForMinSize() and within that group threshold updates that require profile summary info. Differential revision: https://reviews.llvm.org/D28369 llvm-svn: 291487
* Intrinsic::Bitreverse is safe to speculateXin Tong2017-01-091-0/+1
| | | | | | | | | | | | Summary: Intrinsic::Bitreverse is safe to speculate Reviewers: hfinkel, mkuper, arsenm, jmolloy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28471 llvm-svn: 291456
* [PM] Teach SCEV to invalidate itself when its dependencies becomeChandler Carruth2017-01-091-0/+12
| | | | | | | | | | | | | invalid. This fixes use-after-free bugs that will arise with any interesting use of SCEV. I've added a dedicated test that works diligently to trigger these kinds of bugs in the new pass manager and also checks for them explicitly as well as triggering ASan failures when things go squirly. llvm-svn: 291426
* [MemDep] NFC walk invariant.group graph only downPiotr Padlewski2017-01-081-26/+16
| | | | | | | | | | | | | | Summary: By using stripPointerCasts we can get to the root value and then walk down the bitcast graph Reviewers: reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28181 llvm-svn: 291405
* [LCSSA] Fix some typos. NFCI.Davide Italiano2017-01-081-3/+3
| | | | llvm-svn: 291404
* [InstSimplify] Optimize away udivs in the presence of range metadataDavid Majnemer2017-01-061-0/+10
| | | | | | We know that udiv %V, C can be optimized away to 0 if %V is ult C. llvm-svn: 291296
* [InstSimplify] Optimize away urems in the presence of range metadataDavid Majnemer2017-01-061-0/+10
| | | | | | We know that urem %V, C can be optimized away to %V if %V is ult C. llvm-svn: 291282
* ThinLTO: add early "dead-stripping" on the IndexTeresa Johnson2017-01-051-4/+27
| | | | | | | | | | | | | | | | | | | | | | | | Summary: Using the linker-supplied list of "preserved" symbols, we can compute the list of "dead" symbols, i.e. the one that are not reachable from a "preserved" symbol transitively on the reference graph. Right now we are using this information to mark these functions as non-eligible for import. The impact is two folds: - Reduction of compile time: we don't import these functions anywhere or import the function these symbols are calling. - The limited number of import/export leads to better internalization. Patch originally by Mehdi Amini. Reviewers: mehdi_amini, pcc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23488 llvm-svn: 291177
* [ThinLTO] Use DenseSet instead of SmallPtrSet for holding GUIDsTeresa Johnson2017-01-051-4/+4
| | | | | | | | | Should fix some more bot failures from r291108. This should have been a DenseSet, since GUID is not a pointer type. It caused some bots to fail, but for some reason I wasnt't getting a build failure. llvm-svn: 291115
* [ThinLTO] Subsume all importing checks into a single flagTeresa Johnson2017-01-051-26/+71
| | | | | | | | | | | | | | | | | | | Summary: This adds a new summary flag NotEligibleToImport that subsumes several existing flags (NoRename, HasInlineAsmMaybeReferencingInternal and IsNotViableToInline). It also subsumes the checking of references on the summary that was being done during the thin link by eligibleForImport() for each candidate. It is much more efficient to do that checking once during the per-module summary build and record it in the summary. Reviewers: mehdi_amini Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28169 llvm-svn: 291108
* Currently isLikelyComplexAddressComputation tries to figure out if the given ↵Mohammed Agabaria2017-01-051-2/+3
| | | | | | | | | | | | | stride seems to be 'complex' and need some extra cost for address computation handling. This code seems to be target dependent which may not be the same for all targets. Passed the decision whether the given stride is complex or not to the target by sending stride information via SCEV to getAddressComputationCost instead of 'IsComplex'. Specifically at X86 targets we dont see any significant address computation cost in case of the strided access in general. Differential Revision: https://reviews.llvm.org/D27518 llvm-svn: 291106
* [ValueTracking] remove stale comments; NFCSanjay Patel2017-01-021-6/+0
| | | | | | | The checks were improved with: https://reviews.llvm.org/rL290194 llvm-svn: 290826
* AVX-512 Loop Vectorizer: Cost calculation for interleave load/store patterns.Elena Demikhovsky2017-01-021-0/+32
| | | | | | | | | | | | X86 target does not provide any target specific cost calculation for interleave patterns.It uses the common target-independent calculation, which gives very high numbers. As a result, the scalar version is chosen in many cases. The situation on AVX-512 is even worse, since we have 3-src shuffles that significantly reduce the cost. In this patch I calculate the cost on AVX-512. It will allow to compare interleave pattern with gather/scatter and choose a better solution (PR31426). * Shiffle-broadcast cost will be changed in Simon's upcoming patch. Differential Revision: https://reviews.llvm.org/D28118 llvm-svn: 290810
* Fix an issue with isGuaranteedToTransferExecutionToSuccessorSanjoy Das2016-12-311-6/+20
| | | | | | | | | | | | | | I'm not sure if this was intentional, but today isGuaranteedToTransferExecutionToSuccessor returns true for readonly and argmemonly calls that may throw. This commit changes the function to not implicitly infer nounwind this way. Even if we eventually specify readonly calls as not throwing, isGuaranteedToTransferExecutionToSuccessor is not the best place to infer that. We should instead teach FunctionAttrs or some other such pass to tag readonly functions / calls as nounwind instead. llvm-svn: 290794
* Avoid const_cast; NFCSanjoy Das2016-12-311-2/+3
| | | | llvm-svn: 290793
* [ValueTracking] make dominator tree requirement explicit for ↵Sanjay Patel2016-12-311-1/+6
| | | | | | | | | | | | | | | | | isKnownNonNullFromDominatingCondition(); NFCI I don't think this hole is currently exposed, but I crashed regression tests for jump-threading and loop-vectorize after I added calls to isKnownNonNullAt() in InstSimplify as part of trying to solve PR28430: https://llvm.org/bugs/show_bug.cgi?id=28430 That's because they call into value tracking with a context instruction, but no other parts of the query structure filled in. For more background, see the discussion in: https://reviews.llvm.org/D27855 llvm-svn: 290786
* [LVI] Remove count/erase idiom in favor of checking result value of erasePhilip Reames2016-12-301-6/+2
| | | | | | Minor compile time win. Avoids an additional O(N) scan in the case where we are removing an element and costs nothing when we aren't. llvm-svn: 290768
* [MemDep] Handle gep with zeros for invariant.groupPiotr Padlewski2016-12-301-20/+39
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: gep 0, 0 is equivalent to bitcast. LLVM canonicalizes it to getelementptr because it make SROA can then handle it. Simple case like void g(A &a) { z(a); if (glob) a.foo(); } void testG() { A a; g(a); } was not devirtualized with -fstrict-vtable-pointers because luck of handling for gep 0 in Memory Dependence Analysis Reviewers: dberlin, nlewycky, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28126 llvm-svn: 290763
OpenPOWER on IntegriCloud