summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [ValueTracking] Implement SignBitMustBeZero correctly for sqrt.Justin Lebar2017-01-261-4/+12
| | | | | | | | | | | | | | Summary: Previously we assumed that the result of sqrt(x) always had 0 as its sign bit. But sqrt(-0) == -0. Reviewers: hfinkel, efriedma, sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28928 llvm-svn: 293115
* New OptimizationRemarkEmitter pass for MIRAdam Nemet2017-01-251-38/+37
| | | | | | | | | | | | | | | | | This allows MIR passes to emit optimization remarks with the same level of functionality that is available to IR passes. It also hooks up the greedy register allocator to report spills. This allows for interesting use cases like increasing interleaving on a loop until spilling of registers is observed. I still need to experiment whether reporting every spill scales but this demonstrates for now that the functionality works from llc using -pass-remarks*=<pass>. Differential Revision: https://reviews.llvm.org/D29004 llvm-svn: 293110
* [OptDiag] Split code region out of DiagnosticInfoOptimizationBaseAdam Nemet2017-01-251-3/+5
| | | | | | | | | | | | | | | | | | Code region is the only part of this class that is IR-specific. Code region is moved down in the inheritance tree to a new derived class, called DiagnosticInfoIROptimization. All the existing remarks are derived from this new class now. This allows the new MIR pass-remark classes to be derived from DiagnosticInfoOptimizationBase. Also because we keep the name DiagnosticInfoOptimizationBase, the clang parts don't need any adjustment. Differential Revision: https://reviews.llvm.org/D29003 llvm-svn: 293109
* Mark @llvm.powi.* as safe to speculatively execute.whitequark2017-01-251-0/+4
| | | | | | | | | | | | Floating point intrinsics in LLVM are generally not speculatively executed, since most of them are defined to behave the same as libm functions, which set errno. However, the @llvm.powi.* intrinsics do not correspond to any libm function, and lacks any defined error handling semantics in LangRef. It most certainly does not alter errno. llvm-svn: 293041
* Rewind instantiations of OuterAnalysisManagerProxy in r289317, r291651, and ↵NAKAMURA Takumi2017-01-252-3/+2
| | | | | | | | | | r291662. I found root class should be instantiated for variadic tempate to instantiate static member explicitly. This will fix failures in mingw DLL build. llvm-svn: 293017
* [InstSimplify] try to eliminate icmp Pred (add nsw X, C1), C2Sanjay Patel2017-01-241-3/+17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | I was surprised to see that we're missing icmp folds based on 'add nsw' in InstCombine, but we should handle the InstSimplify cases first because that could make the InstCombine code simpler. Here are Alive-based proofs for the logic: Name: add_neg_constant Pre: C1 < 0 && (C2 > ((1<<(width(C1)-1)) + C1)) %a = add nsw i7 %x, C1 %b = icmp sgt %a, C2 => %b = false Name: add_pos_constant Pre: C1 > 0 && (C2 < ((1<<(width(C1)-1)) + C1 - 1)) %a = add nsw i6 %x, C1 %b = icmp slt %a, C2 => %b = false Name: nuw Pre: C1 u>= C2 %a = add nuw i11 %x, C1 %b = icmp ult %a, C2 => %b = false Differential Revision: https://reviews.llvm.org/D29053 llvm-svn: 292952
* [PH] Replace uses of AssertingVH from members of analysis results withChandler Carruth2017-01-241-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | a lazy-asserting PoisoningVH. AssertVH is fundamentally incompatible with cache-invalidation of analysis results. The invaliadtion happens after the AssertingVH has already fired. Instead, use a PoisoningVH that will assert if the dangling handle is ever used rather than merely be assigned or destroyed. This patch also removes all of the (numerous) doomed attempts to work around this fundamental incompatibility. It is a pretty significant simplification IMO. The most interesting change is in the Inliner where we still do some clearing because we don't want to rely on the coarse grained invalidation strategy of the containing pass manager. However, I prefer the approach that contains this logic to the cleanup phase of the Inliner, and I think we could enhance the CGSCC analysis management layer to make this even better in the future if desired. The rest is straight cleanup. I've also added a test for one of the harder cases to work around: when a *module analysis* contains many AssertingVHes pointing at functions. Differential Revision: https://reviews.llvm.org/D29006 llvm-svn: 292928
* Make VerifyDomInfo and VerifyLoopInfo global variablesSerge Pavlov2017-01-241-2/+2
| | | | | | | | | | | | | | | Verifications of dominator tree and loop info are expensive operations so they are disabled by default. They can be enabled by command line options -verify-dom-info and -verify-loop-info. These options however enable checks only in files Dominators.cpp and LoopInfo.cpp. If some transformation changes dominaror tree and/or loop info, it would be convenient to place similar checks to the files implementing the transformation. This change makes corresponding flags global, so they can be used in any file to optionally turn verification on. llvm-svn: 292889
* [Analysis] Add LibFunc_ prefix to enums in TargetLibraryInfo. (NFC)David L. Jones2017-01-236-767/+767
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The LibFunc::Func enum holds enumerators named for libc functions. Unfortunately, there are real situations, including libc implementations, where function names are actually macros (musl uses "#define fopen64 fopen", for example; any other transitively visible macro would have similar effects). Strictly speaking, a conforming C++ Standard Library should provide any such macros as functions instead (via <cstdio>). However, there are some "library" functions which are not part of the standard, and thus not subject to this rule (fopen64, for example). So, in order to be both portable and consistent, the enum should not use the bare function names. The old enum naming used a namespace LibFunc and an enum Func, with bare enumerators. This patch changes LibFunc to be an enum with enumerators prefixed with "LibFFunc_". (Unfortunately, a scoped enum is not sufficient to override macros.) There are additional changes required in clang. Reviewers: rsmith Subscribers: mehdi_amini, mzolotukhin, nemanjai, llvm-commits Differential Revision: https://reviews.llvm.org/D28476 llvm-svn: 292848
* [PGO] add debug option to view annotated cfg after prof use annotationXinliang David Li2017-01-231-2/+11
| | | | | | Differential Revision: http://reviews.llvm.org/D28967 llvm-svn: 292815
* [InstSimplify] refactor finding limits for icmp with binop; NFCISanjay Patel2017-01-231-105/+146
| | | | llvm-svn: 292812
* [PM] Teach LVI to correctly invalidate itself when its dependenciesChandler Carruth2017-01-231-0/+12
| | | | | | | | | | | | become unavailable. The AssumptionCache is now immutable but it still needs to respond to DomTree invalidation if it ended up caching one. This lets us remove one of the explicit invalidates of LVI but the other one continues to avoid hitting a latent bug. llvm-svn: 292769
* [ValueTracking] tighten up matchMinMax(); NFCISanjay Patel2017-01-211-40/+14
| | | | | | | | | This is similar to what the caller (matchSelectPattern()) does. In all cases where we succeed in matching a min/max pattern, the values in that pattern will be the values of the 'select', so hoist that and remove a bunch of duplicated code. llvm-svn: 292725
* Add missing dependency to "Module Summary Analysis" passMehdi Amini2017-01-211-0/+1
| | | | | | This is fixing a clang crash when running `clang -flto=thin -save-temps` llvm-svn: 292711
* [ConstantFolding] Constant-fold llvm.sqrt(x) like other intrinsics.Justin Lebar2017-01-211-13/+2
| | | | | | | | | | | | | | | | | | | | | | Summary: Currently we return undef, but we're in the process of changing the LangRef so that llvm.sqrt behaves like the other math intrinsics, matching the return value of the standard libcall but not setting errno. This change is legal even without the LangRef change because currently calling llvm.sqrt(x) where x is negative is spec'ed to be UB. But in practice it's also safe because we're simply constant-folding fewer inputs: Inputs >= -0 get constant-folded as before, but inputs < -0 now aren't constant-folded, because ConstantFoldFP aborts if the host math function raises an fp exception. Reviewers: hfinkel, efriedma, sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28929 llvm-svn: 292692
* Improve PGO support for the new inlinerEaswaran Raman2017-01-201-17/+40
| | | | | | | | | | | | | | | | | | | | | | | | This adds the following to the new PM based inliner in PGO mode: * Use block frequency analysis to derive callsite's profile count and use that to adjust thresholds of hot and cold callsites. * Incrementally update the BFI of the caller after a callee gets inlined into it. This incremental update is only within an invocation of the run method - BFI is not preserved across calls to run. Update the function entry count of the callee after inlining it into a caller. * I've tuned the thresholds for the hot and cold callsites using a hacked up version of the old inliner that explicitly computes BFI on a set of internal benchmarks and spec. Once the new PM based pipeline stabilizes (IIRC Chandler mentioned there are known issues) I'll benchmark this again and adjust the thresholds if required. Inliner PGO support. Differential revision: https://reviews.llvm.org/D28331 llvm-svn: 292666
* [ValueTracking] recognize variations of 'clamp' to improve codegen (PR31693)Sanjay Patel2017-01-201-1/+39
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | By enhancing value tracking, we allow an existing min/max canonicalization to kick in and improve codegen for several targets that have min/max instructions. Unfortunately, recognizing min/max in value tracking may cause us to hit a hack in InstCombiner::visitICmpInst() more often: http://lists.llvm.org/pipermail/llvm-dev/2017-January/109340.html ...but I'm hoping we can remove that soon. Correctness proofs based on Alive: Name: smaxmin Pre: C1 < C2 %cmp2 = icmp slt i8 %x, C2 %min = select i1 %cmp2, i8 %x, i8 C2 %cmp3 = icmp slt i8 %x, C1 %r = select i1 %cmp3, i8 C1, i8 %min => %cmp2 = icmp slt i8 %x, C2 %min = select i1 %cmp2, i8 %x, i8 C2 %cmp1 = icmp sgt i8 %min, C1 %r = select i1 %cmp1, i8 %min, i8 C1 Name: sminmax Pre: C1 > C2 %cmp2 = icmp sgt i8 %x, C2 %max = select i1 %cmp2, i8 %x, i8 C2 %cmp3 = icmp sgt i8 %x, C1 %r = select i1 %cmp3, i8 C1, i8 %max => %cmp2 = icmp sgt i8 %x, C2 %max = select i1 %cmp2, i8 %x, i8 C2 %cmp1 = icmp slt i8 %max, C1 %r = select i1 %cmp1, i8 %max, i8 C1 ---------------------------------------- Optimization: smaxmin Done: 1 Optimization is correct! ---------------------------------------- Optimization: sminmax Done: 1 Optimization is correct! Name: umaxmin Pre: C1 u< C2 %cmp2 = icmp ult i8 %x, C2 %min = select i1 %cmp2, i8 %x, i8 C2 %cmp3 = icmp ult i8 %x, C1 %r = select i1 %cmp3, i8 C1, i8 %min => %cmp2 = icmp ult i8 %x, C2 %min = select i1 %cmp2, i8 %x, i8 C2 %cmp1 = icmp ugt i8 %min, C1 %r = select i1 %cmp1, i8 %min, i8 C1 Name: uminmax Pre: C1 u> C2 %cmp2 = icmp ugt i8 %x, C2 %max = select i1 %cmp2, i8 %x, i8 C2 %cmp3 = icmp ugt i8 %x, C1 %r = select i1 %cmp3, i8 C1, i8 %max => %cmp2 = icmp ugt i8 %x, C2 %max = select i1 %cmp2, i8 %x, i8 C2 %cmp1 = icmp ult i8 %max, C1 %r = select i1 %cmp1, i8 %max, i8 C1 ---------------------------------------- Optimization: umaxmin Done: 1 Optimization is correct! ---------------------------------------- Optimization: uminmax Done: 1 Optimization is correct! llvm-svn: 292660
* Recommit "[InlineCost] Use TTI to check if GEP is free." #3Haicheng Wu2017-01-201-2/+18
| | | | | | | | | | | | This is the third attemp to recommit r292526. The original summary: Currently, a GEP is considered free only if its indices are all constant. TTI::getGEPCost() can give target-specific more accurate analysis. TTI is already used for the cost of many other instructions. llvm-svn: 292633
* Revert "Recommit "[InlineCost] Use TTI to check if GEP is free." #2"Haicheng Wu2017-01-201-18/+2
| | | | | | This reverts commit r292616 because the test case still has problem. llvm-svn: 292618
* Recommit "[InlineCost] Use TTI to check if GEP is free." #2Haicheng Wu2017-01-201-2/+18
| | | | | | | | | | | | This is the second attemp to recommit r292526. The original summary: Currently, a GEP is considered free only if its indices are all constant. TTI::getGEPCost() can give target-specific more accurate analysis. TTI is already used for the cost of many other instructions. llvm-svn: 292616
* Revert "Recommit "[InlineCost] Use TTI to check if GEP is free.""Haicheng Wu2017-01-201-18/+2
| | | | | | This reverts commit r292570. The test still has problem. llvm-svn: 292572
* Recommit "[InlineCost] Use TTI to check if GEP is free."Haicheng Wu2017-01-201-2/+18
| | | | | | | | | | | | This recommits r292526 which is reverted in r292529 after fixing the test case. The original summary: Currently, a GEP is considered free only if its indices are all constant. TTI::getGEPCost() can give target-specific more accurate analysis. TTI is already used for the cost of many other instructions. llvm-svn: 292570
* [LoopInfo] Add helper methods to compute two useful orderings of theChandler Carruth2017-01-201-18/+4
| | | | | | | | | | | | | | | | | | | | | | loops in a function. These are relatively confusing to talk about and compute correctly so it seems really good to write down their implementation in one place. I've replaced one place we needed this in the loop PM infrastructure and I have another place in a pending patch that wants it. We can't quite use this for the core loop PM walk because there we're sometimes working on a sub-forest. I'll add the expected unittests before committing this but wanted to make sure folks were happy with these names / comments. Credit goes to Richard Smith for the idea for naming the order where siblings are in reverse program order but the tree traversal remains preorder. Differential Revision: https://reviews.llvm.org/D28932 llvm-svn: 292569
* [AliasAnalysis] Fences do not modify constant memory locationAnna Thomas2017-01-201-0/+8
| | | | | | | | | | | | | | | | | | | Summary: Fence instructions are currently marked as `ModRef` for all memory locations. We can improve this for constant memory locations (such as constant globals), since fence instructions cannot modify these locations. This helps us to forward constant loads across fences (added test case in GVN). There were no changes in behaviour for similar test cases in early-cse and licm. Reviewers: dberlin, sanjoy, reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28914 llvm-svn: 292546
* Revert "[InlineCost] Use TTI to check if GEP is free."Haicheng Wu2017-01-191-18/+2
| | | | | | This reverts commit r292526. The test case has problem. llvm-svn: 292529
* [InlineCost] Use TTI to check if GEP is free.Haicheng Wu2017-01-191-2/+18
| | | | | | | | | | Currently, a GEP is considered free only if its indices are all constant. TTI::getGEPCost() can give target-specific more accurate analysis. TTI is already used for the cost of many other instructions. Differential Revision: https://reviews.llvm.org/D28693 llvm-svn: 292526
* Add an interface to scale the frequencies of a set of blocks.Easwaran Raman2017-01-191-0/+22
| | | | | | | | The scaling is done with reference to the the new frequency of a reference block. Differential Revision: https://reviews.llvm.org/D28535 llvm-svn: 292507
* [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
OpenPOWER on IntegriCloud