summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* PSCEV] Create AddRec for Phis in cases of possible integer overflow,Dorit Nuzman2017-07-181-13/+372
| | | | | | | | | | | | | using runtime checks Extend the SCEVPredicateRewriter to work a bit harder when it encounters an UnknownSCEV for a Phi node; Try to build an AddRecurrence also for Phi nodes whose update chain involves casts that can be ignored under the proper runtime overflow test. This is one step towards addressing PR30654. Differential revision: http://reviews.llvm.org/D30041 llvm-svn: 308299
* [Analysis] RemoveTotalMemInst counting in InstCount to avoid reading back ↵Craig Topper2017-07-181-8/+0
| | | | | | | | | | | | | | | | | | | | | other Statistic variables Summary: Previously, we counted TotalMemInst by reading certain instruction counters before and after calling visit and then finding the difference. But that wouldn't be thread safe if this same pass was being ran on multiple threads. This list of "memory instructions" doesn't make sense to me as it includes call/invoke and is missing atomics. This patch removes the counter all together. Reviewers: hfinkel, chandlerc, davide Reviewed By: davide Subscribers: davide, llvm-commits Differential Revision: https://reviews.llvm.org/D33608 llvm-svn: 308260
* Analysis/MemorySSA.cpp: Prune unused "llvm/Transforms/Scalar.h".NAKAMURA Takumi2017-07-171-1/+0
| | | | llvm-svn: 308162
* [InstSimplify] Use commutable matchers to simplify some code. NFCCraig Topper2017-07-161-14/+7
| | | | llvm-svn: 308125
* [PM/LCG] Teach the LazyCallGraph to maintain reference edges from everyChandler Carruth2017-07-152-10/+43
| | | | | | | | | | | | | | | | | | | | | | | | | | function to every defined function known to LLVM as a library function. LLVM can introduce calls to these functions either by replacing other library calls or by recognizing patterns (such as memset_pattern or vector math patterns) and replacing those with calls. When these library functions are actually defined in the module, we need to have reference edges to them initially so that we visit them during the CGSCC walk in the right order and can effectively rebuild the call graph afterward. This was discovered when building code with Fortify enabled as that is a common case of both inline definitions of library calls and simplifications of code into calling them. This can in extreme cases of LTO-ing with libc introduce *many* more reference edges. I discussed a bunch of different options with folks but all of them are unsatisfying. They either make the graph operations substantially more complex even when there are *no* defined libfuncs, or they introduce some other complexity into the callgraph. So this patch goes with the simplest possible solution of actual synthetic reference edges. If this proves to be a memory problem, I'm happy to implement one of the clever techniques to save memory here. llvm-svn: 308088
* [TTI] Refine the cost of EXT in getUserCost()Haicheng Wu2017-07-151-0/+5
| | | | | | | | | | | Now, getUserCost() only checks the src and dst types of EXT to decide it is free or not. This change first checks the types, then calls isExtFreeImpl(), and check if EXT can form ExtLoad at last. Currently, only AArch64 has customized implementation of isExtFreeImpl() to check if EXT can be folded into its use. Differential Revision: https://reviews.llvm.org/D34458 llvm-svn: 308076
* [Dominators] Make IsPostDominator a template parameterJakub Kuderski2017-07-144-6/+9
| | | | | | | | | | | | | | | | | Summary: DominatorTreeBase used to have IsPostDominators (bool) member to indicate if the tree is a dominator or a postdominator tree. This made it possible to switch between the two 'modes' at runtime, but it isn't used in practice anywhere. This patch makes IsPostDominator a template argument. This way, it is easier to switch between different algorithms at compile-time based on this argument and design external utilities around it. It also makes it impossible to incidentally assign a postdominator tree to a dominator tree (and vice versa), and to further simplify template code in GenericDominatorTreeConstruction. Reviewers: dberlin, sanjoy, davide, grosser Reviewed By: dberlin Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D35315 llvm-svn: 308040
* [PM] Fix a silly bug in my recent update to the CG update logic.Chandler Carruth2017-07-121-1/+1
| | | | | | | | I used the wrong variable to update. This was even covered by a unittest I wrote, and the comments for the unittest were correct (if confusing) but the test itself just matched the buggy behavior. =[ llvm-svn: 307764
* [MemoryBuiltins] Allow truncation in visitAllocaInst()Mikael Holmen2017-07-121-17/+24
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Solves PR33689. If the pointer size is less than the size of the type used for the array size in an alloca (the <ty> type below) then we could trigger the assert in the PR. In that example we have pointer size i16 and <ty> is i32. <result> = alloca [inalloca] <type> [, <ty> <NumElements>] [, align <alignment>] Handle the situation by allowing truncation as well as zero extension in ObjectSizeOffsetVisitor::visitAllocaInst(). Also, we now detect overflow in visitAllocaInst(), similar to how it was already done in visitCallSite(). Reviewers: craig.topper, rnk, george.burgess.iv Reviewed By: george.burgess.iv Subscribers: davide, llvm-commits Differential Revision: https://reviews.llvm.org/D35003 llvm-svn: 307754
* Whitespace.NAKAMURA Takumi2017-07-111-1/+1
| | | | llvm-svn: 307614
* Revert r307581, "Avoid doing conservative phi checks in ↵NAKAMURA Takumi2017-07-112-12/+8
| | | | | | | | aliasSameBasePointerGEPs() if no phis have been visited yet." It broke stage2 tests in selfhosting. llvm-svn: 307613
* Avoid doing conservative phi checks in aliasSameBasePointerGEPs() if no phis ↵Farhana Aleen2017-07-102-8/+12
| | | | | | | | | | | | have been visited yet. Reviewers: Daniel Berlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34478 llvm-svn: 307581
* fix typos in comments and error messages; NFCHiroshi Inoue2017-07-101-2/+2
| | | | llvm-svn: 307533
* [PM] Fix a nasty bug in the new PM where we failed to properlyChandler Carruth2017-07-092-21/+50
| | | | | | | | | | | | | | | | | | | | | | | | invalidation of analyses when merging SCCs. While I've added a bunch of testing of this, it takes something much more like the inliner to really trigger this as you need to have partially-analyzed SCCs with updates at just the right time. So I've added a direct test for this using the inliner and verifying the domtree. Without the changes here, this test ends up finding a stale dominator tree. However, to handle this properly, we need to invalidate analyses *before* merging the SCCs. After talking to Philip and Sanjoy about this they convinced me this was the right approach. To do this, we need a callback mechanism when merging SCCs so we can observe the cycle that will be merged before the merge happens. This API update ended up being surprisingly easy. With this commit, the new PM passes the test-suite again. It hadn't since MemorySSA was enabled for EarlyCSE as that also will find this bug very quickly. llvm-svn: 307498
* [PM] Add unittesting of the call graph update logic with complexChandler Carruth2017-07-091-6/+51
| | | | | | | | | | | dependencies between analyses. This uncovers even more issues with the proxies and the splitting apart of SCCs which are fixed in this patch. I discovered this while trying to add more rigorous testing for a change I'm making to the call graph update invalidation logic. llvm-svn: 307497
* [IR] Add Type::isIntOrIntVectorTy(unsigned) similar to the existing ↵Craig Topper2017-07-092-10/+8
| | | | | | isIntegerTy(unsigned), but also works for vectors. llvm-svn: 307492
* [IR] Make use of ↵Craig Topper2017-07-092-4/+3
| | | | | | Type::isPtrOrPtrVectorTy/isIntOrIntVectorTy/isFPOrFPVectorTy to shorten code. NFC llvm-svn: 307491
* fix trivial typos; NFCHiroshi Inoue2017-07-092-3/+3
| | | | | | sucessor -> successor llvm-svn: 307488
* [PM] Finish implementing and fix a chain of bugs uncovered by testingChandler Carruth2017-07-091-22/+88
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | the invalidation propagation logic from an SCC to a Function. I wrote the infrastructure to test this but didn't actually use it in the unit test where it was designed to be used. =[ My bad. Once I actually added it to the test case I discovered that it also hadn't been properly implemented, so I've implemented it. The logic in the FAM proxy for an SCC pass to propagate invalidation follows the same ideas as the FAM proxy for a Module pass, but the implementation is a bit different to reflect the fact that it is forwarding just for an SCC. However, implementing this correctly uncovered a surprising "bug" (it was conservatively correct but relatively very expensive) in how we handle invalidation when splitting one SCC into multiple SCCs. We did an eager invalidation when in reality we should be deferring invaliadtion for the *current* SCC to the CGSCC pass manager and just invaliating the newly constructed SCCs. Otherwise we end up invalidating too much too soon. This was exposed by the inliner test case that I've updated. Now, we invalidate *just* the split off '(test1_f)' SCC when doing the CG update, and then the inliner finishes and invalidates the '(test1_g, test1_h)' SCC's analyses. The first few attempts at fixing this hit still more bugs, but all of those are covered by existing tests. For example, the inliner should also preserve the FAM proxy to avoid unnecesasry invalidation, and this is safe because the CG update routines it uses handle any necessary adjustments to the FAM proxy. Finally, the unittests for the CGSCC pass manager needed a bunch of updates where we weren't correctly preserving the FAM proxy because it hadn't been fully implemented and failing to preserve it didn't matter. Note that this doesn't yet fix the current crasher due to MemSSA finding a stale dominator tree, but without this the fix to that crasher doesn't really make any sense when testing because it relies on the proxy behavior. llvm-svn: 307487
* Increase the import-threshold for crtical functions.Dehao Chen2017-07-071-1/+1
| | | | | | | | | | | | | | Summary: For interative sample-pgo, if a hot call site is inlined in the profiling binary, we should inline it in before profile annotation in the backend. Before that, the compile phase first collects all GUIDs that needs to be imported and creates virtual "hot" call edge in the summary. However, "hot" is not good enough to guarantee the callsites get inlined. This patch introduces "critical" call edge, and assign much higher importing threshold for those edges. Reviewers: tejohnson Reviewed By: tejohnson Subscribers: sanjoy, mehdi_amini, llvm-commits, eraman Differential Revision: https://reviews.llvm.org/D35096 llvm-svn: 307439
* [DemandedBits] fix formatting; NFCSanjay Patel2017-07-071-9/+6
| | | | llvm-svn: 307403
* [ValueTracking] Fix the identity case (LHS => RHS) when the LHS is false.Chad Rosier2017-07-071-2/+2
| | | | | | | | | Prior to this commit both of the added test cases were passing. However, in the latter case (test7) we were doing a lot more work to arrive at the same answer (i.e., we were using isImpliedCondMatchingOperands() to determine the implication.). llvm-svn: 307400
* Extend memcpy expansion in Transform/Utils to handle wider operand types.Sean Fertile2017-07-071-0/+25
| | | | | | | | | | | Adds loop expansions for known-size and unknown-sized memcpy calls, allowing the target to provide the operand types through TTI callbacks. The default values for the TTI callbacks use int8 operand types and matches the existing behaviour if they aren't overridden by the target. Differential revision: https://reviews.llvm.org/D32536 llvm-svn: 307346
* [ValueTracking] Support icmps fed by 'and' and 'or'.Chad Rosier2017-07-061-7/+32
| | | | | | | | | | This patch adds support for handling some forms of ands and ors in ValueTracking's isImpliedCondition API. PR33611 https://reviews.llvm.org/D34901 llvm-svn: 307304
* [Constants] Replace calls to ConstantInt::equalsInt(0)/equalsInt(1) with ↵Craig Topper2017-07-062-4/+4
| | | | | | isZero and isOne. NFCI llvm-svn: 307293
* [Constants] If we already have a ConstantInt*, prefer to use ↵Craig Topper2017-07-066-12/+12
| | | | | | | | isZero/isOne/isMinusOne instead of isNullValue/isOneValue/isAllOnesValue inherited from Constant. NFCI Going through the Constant methods requires redetermining that the Constant is a ConstantInt and then calling isZero/isOne/isMinusOne. llvm-svn: 307292
* [DependenceAnalysis] Make sure base objects are the same when comparing GEPsBrendon Cahoon2017-07-051-1/+2
| | | | | | | | | | | | | | | The dependence analysis was returning incorrect information when using the GEPs to compute dependences. The analysis uses the GEP indices under certain conditions, but was doing it incorrectly when the base objects of the GEP are aliases, but pointing to different locations in the same array. This patch adds another check for the base objects. If the base pointer SCEVs are not equal, then the dependence analysis should fall back on the path that uses the whole SCEV for the dependence check. This fixes PR33567. Differential Revision: https://reviews.llvm.org/D34702 llvm-svn: 307203
* fix trivial typos, NFCHiroshi Inoue2017-07-011-2/+2
| | | | llvm-svn: 306952
* [Dominators] Reapply r306892, r306893, r306893.Jakub Kuderski2017-07-011-10/+2
| | | | | | | | | This reverts commit r306907 and reapplies the patches in the title. The patches used to make one of the CodeGen/ARM/2011-02-07-AntidepClobber.ll test to fail because of a missing null check. llvm-svn: 306919
* [ORE] Add diagnostics hotness thresholdBrian Gesiak2017-06-301-0/+7
| | | | | | | | | | | | | | | | | | | | Summary: Add an option to prevent diagnostics that do not meet a minimum hotness threshold from being output. When generating optimization remarks for large codebases with a ton of cold code paths, this option can be used to limit the optimization remark output at a reasonable size. Discussion of this change can be read here: http://lists.llvm.org/pipermail/llvm-dev/2017-June/114377.html Reviewers: anemet, davidxl, hfinkel Reviewed By: anemet Subscribers: qcolombet, javed.absar, fhahn, eraman, llvm-commits Differential Revision: https://reviews.llvm.org/D34867 llvm-svn: 306912
* Revert "[Dominators] Teach IDF to use level information"Jakub Kuderski2017-06-301-2/+10
| | | | | | | | | | | | | | This reverts commit r306894. Revert "[Dominators] Add NearestCommonDominator verification" This reverts commit r306893. Revert "[Dominators] Keep tree level in DomTreeNode and use it to find NCD and answer dominance queries" This reverts commit r306892. llvm-svn: 306907
* [Dominators] Teach IDF to use level informationJakub Kuderski2017-06-301-10/+2
| | | | | | | | | | | | | | Summary: This patch teaches IteratedDominanceFrontier to use the level information stored in DomTreeNodes instead of calculating it manually. Reviewers: dberlin, sanjoy, davide Reviewed By: davide Subscribers: davide, llvm-commits Differential Revision: https://reviews.llvm.org/D34703 llvm-svn: 306894
* [ORE] Unify spelling as "diagnostics hotness"Brian Gesiak2017-06-301-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: To enable profile hotness information in diagnostics output, Clang takes the option `-fdiagnostics-show-hotness` -- that's "diagnostics", with an "s" at the end. Clang also defines `CodeGenOptions::DiagnosticsWithHotness`. LLVM, on the other hand, defines `LLVMContext::getDiagnosticHotnessRequested` -- that's "diagnostic", not "diagnostics". It's a small difference, but it's confusing, typo-inducing, and frustrating. Add a new method with the spelling "diagnostics", and "deprecate" the old spelling. Reviewers: anemet, davidxl Reviewed By: anemet Subscribers: llvm-commits, mehdi_amini Differential Revision: https://reviews.llvm.org/D34864 llvm-svn: 306848
* Revert of r306525: "Canonicalize clamp of float types to minmax"Nikolai Bozhenov2017-06-301-68/+1
| | | | llvm-svn: 306815
* [SCEV] Use depth limit instead of local cache for SExt and ZExtMax Kazantsev2017-06-301-124/+119
| | | | | | | | | | | | | | | | In rL300494 there was an attempt to deal with excessive compile time on invocations of getSign/ZeroExtExpr using local caching. This approach only helps if we request the same SCEV multiple times throughout recursion. But in the bug PR33431 we see a case where we request different values all the time, so caching does not help and the size of the cache grows enormously. In this patch we remove the local cache for this methods and add the recursion depth limit instead, as we do for arithmetics. This gives us a guarantee that the invocation sequence is limited and reasonably short. Differential Revision: https://reviews.llvm.org/D34273 llvm-svn: 306785
* [CFLAA] Remove unneded function declaration. NFCI.Davide Italiano2017-06-291-2/+0
| | | | llvm-svn: 306754
* Reverting r306695 while investigating failing test case.Alexandre Isoard2017-06-291-26/+0
| | | | | | | Failing test case: Transforms/LoopVectorize.iv_outside_user.ll llvm-svn: 306723
* ScalarEvolution: Add URem supportAlexandre Isoard2017-06-291-0/+26
| | | | | | | | | | | | | | | | | | | | In LLVM IR the following code: %r = urem <ty> %t, %b is equivalent to: %q = udiv <ty> %t, %b %s = mul <ty> nuw %q, %b %r = sub <ty> nuw %t, %q ; (t / b) * b + (t % b) = t As UDiv, Mul and Sub are already supported by SCEV, URem can be implemented with minimal effort this way. Note: While SRem and SDiv are also related this way, SCEV does not provides SDiv yet. llvm-svn: 306695
* [TBAA] Remove metadata keyword from IR examples in comments (NFC).Florian Hahn2017-06-291-10/+10
| | | | | | The metadata keyword has been removed from the IR. llvm-svn: 306675
* [TargetTransformInfo, API] Add a list of operands to TTI::getUserCostEvgeny Astigeevich2017-06-291-2/+3
| | | | | | | | | | | | | | | | | | | | The changes are a result of discussion of https://reviews.llvm.org/D33685. It solves the following problem: 1. We can inform getGEPCost about simplified indices to help it with calculating the cost. But getGEPCost does not take into account the context which GEPs are used in. 2. We have getUserCost which can take the context into account but we cannot inform about simplified indices. With the changes getUserCost will have access to additional information as getGEPCost has. The one parameter getUserCost is also provided. Differential Revision: https://reviews.llvm.org/D34057 llvm-svn: 306674
* Fix a typo.Eric Christopher2017-06-281-1/+1
| | | | llvm-svn: 306599
* [LoopUnroll] Pass SCEV to getUnrollingPreferences hook. NFCI.Geoff Berry2017-06-281-2/+2
| | | | | | | | | | Reviewers: sanjoy, anna, reames, apilipenko, igor-laevsky, mkuper Subscribers: jholewinski, arsenm, mzolotukhin, nemanjai, nhaehnle, javed.absar, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D34531 llvm-svn: 306554
* Revert r306528Nikolai Bozhenov2017-06-281-0/+9
| | | | llvm-svn: 306536
* [ValueTracking] Enabling existing ValueTracking patch by default.Nikolai Bozhenov2017-06-281-9/+0
| | | | | | | | | | | | | | | The original patch was an improvement to IR ValueTracking on non-negative integers. It has been checked in to trunk (D18777, r284022). But was disabled by default due to performance regressions. Perf impact has improved. The patch would be enabled by default. Reviewers: reames Differential Revision: https://reviews.llvm.org/D34101 Patch by: Olga Chupina <olga.chupina@intel.com> llvm-svn: 306528
* [InstCombine] Canonicalize clamp of float types to minmax in fast mode.Nikolai Bozhenov2017-06-281-1/+68
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This commit allows matchSelectPattern to recognize clamp of float arguments in the presence of FMF the same way as already done for integers. This case is a little different though. With integers, given the min/max pattern is recognized, DAGBuilder starts selecting MIN/MAX "automatically". That is not the case for float, because for them only full FMINNAN/FMINNUM/FMAXNAN/FMAXNUM ISD nodes exist and they do care about NaNs. On the other hand, some backends (e.g. X86) have only FMIN/FMAX nodes that do not care about NaNS and the former NAN/NUM nodes are illegal thus selection is not happening. So I decided to do such kind of transformation in IR (InstCombiner) instead of complicating the logic in the backend. Reviewers: spatel, jmolloy, majnemer, efriedma, craig.topper Reviewed By: efriedma Subscribers: hiraditya, javed.absar, n.bozhenov, llvm-commits Patch by Andrei Elovikov <andrei.elovikov@intel.com> Differential Revision: https://reviews.llvm.org/D33186 llvm-svn: 306525
* [NewPM/Inliner] Reduce threshold for cold callsites in the non-PGO caseEaswaran Raman2017-06-271-1/+30
| | | | | | Differential Revision: https://reviews.llvm.org/D34312 llvm-svn: 306484
* [Analysis] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko2017-06-271-23/+17
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 306472
* [CFLAA] Move a common function to the header to reduce duplication.Davide Italiano2017-06-272-24/+2
| | | | | | Differential Revision: https://reviews.llvm.org/D34660 llvm-svn: 306354
* [CFLAA] Use raw pointers instead of Optional<Pointer>. NFC.Davide Italiano2017-06-271-9/+9
| | | | | | | | | Using Optional<> here doesn't seem to be terribly valuable, but this is not the main point of this change. The change enables us to merge the (now) two identical copies of parentFunctionOfValue() that Steensgaard's and Andersens' provide. llvm-svn: 306351
* [CFLAA] Change FunctionHandle to be common to Steensgaard's and Andersens'Davide Italiano2017-06-262-3/+3
| | | | | | Differential Revision: https://reviews.llvm.org/D34638 llvm-svn: 306348
OpenPOWER on IntegriCloud