summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [ValueTracking] Remove a number of unused arguments. NFC.Chad Rosier2017-07-281-26/+17
| | | | llvm-svn: 309385
* [SCEV] Do not visit nodes twice in containsConstantSomewhereMax Kazantsev2017-07-281-13/+20
| | | | | | | | | | This patch reworks the function that searches constants in Add and Mul SCEV expression chains so that now it does not visit a node more than once, and also renames this function for better correspondence between its implementation and semantics. Differential Revision: https://reviews.llvm.org/D35931 llvm-svn: 309367
* Revert "[SCEV] Cache results of computeExitLimit"Sanjoy Das2017-07-281-21/+0
| | | | | | | | | This reverts commit r309080. The patch needs to clear out the ScalarEvolution::ExitLimits cache in forgetMemoizedResults. I've replied on the commit thread for the patch with more details. llvm-svn: 309357
* Changing the default MaxNumPromotions from 2 to 3.Dehao Chen2017-07-281-1/+1
| | | | | | | | | | | | | | Summary: In performance tuning, we see performance benefits when enlarge the maximum num promotion targets to 3. This is safe as soon as we have total percentage threshold properly setup (https://reviews.llvm.org/D35962) Reviewers: davidxl, tejohnson Reviewed By: tejohnson Subscribers: llvm-commits, sanjoy Differential Revision: https://reviews.llvm.org/D35966 llvm-svn: 309346
* Separate the ICP total threshold and remaining threshold.Dehao Chen2017-07-281-12/+20
| | | | | | | | | | | | | | Summary: In the current implementation, isPromotionProfitable only checks if the call count to a direct target is no less than a certain percentage threshold of the remaining call counts that have not been promoted. This causes code size problems when the target count is small but greater than a large portion of remaining counts. E.g. target1 takes 99.9%, while target2 takes 0.1%. Both targets will be promoted and inlined, makes the function size too large, which potentially prevents it from further inlining into its callers. This patch adds another percentage threshold against the total indirect call count. If the target count needs to be no less than both thresholds in order to be promoted speculatively. Reviewers: davidxl, tejohnson Reviewed By: tejohnson Subscribers: sanjoy, llvm-commits Differential Revision: https://reviews.llvm.org/D35962 llvm-svn: 309345
* [InlineCost, NFC] Change CallAnalyzer::isGEPFree to use TTI::getUserCost ↵Evgeny Astigeevich2017-07-271-6/+5
| | | | | | | | | | | | | | instead of TTI::getGEPCost Currently CallAnalyzer::isGEPFree uses TTI::getGEPCost to check if GEP is free. TTI::getGEPCost cannot handle cases when GEPs participate in Def-Use dependencies (see https://reviews.llvm.org/D31186 for example). There is TTI::getUserCost which can calculate the cost more accurately by taking dependencies into account. Differential Revision: https://reviews.llvm.org/D33685 llvm-svn: 309268
* [TTI] fixing a bug in the isLegalMaskedScatter APIMohammed Agabaria2017-07-271-1/+1
| | | | | | | | | isLegalMaskedScatter called the Gather version which is a bug. use test case is provided within the patch of AVX2 gathers at: https://reviews.llvm.org/D35772 Differential Revision: https://reviews.llvm.org/D35786 llvm-svn: 309260
* [SCEV] Cache results of computeExitLimitMax Kazantsev2017-07-261-0/+21
| | | | | | | | | This patch adds a cache for computeExitLimit to save compilation time. A lot of examples of tests that take extensive time to compile are attached to the bug 33494. Differential Revision: https://reviews.llvm.org/D35827 llvm-svn: 309080
* [SCEV] Remove unnecessary call to forgetMemoizedResultsSanjoy Das2017-07-261-3/+0
| | | | | | | | | | | | | `SCEVUnknown::allUsesReplacedWith` does not need to call `forgetMemoizedResults` since RAUW does a value-equivalent replacement by assumption. If this assumption was false then the later setValPtr(New) call would be incorrect too. This is a non-trivial performance optimization for functions with a large number of loops since `forgetMemoizedResults` walks all loop backedge taken counts to see if any of them use the SCEVUnknown being RAUWed. However, this improvement is difficult to demonstrate without checking in an excessively large IR file. llvm-svn: 309072
* [Analysis] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko2017-07-245-22/+53
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 308936
* [SCEV] Limit max size of AddRecExpr during evolvingMax Kazantsev2017-07-231-0/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | When SCEV calculates product of two SCEVAddRecs from the same loop, it tries to combine them into one big AddRecExpr. If the sizes of the initial SCEVs were `S1` and `S2`, the size of their product is `S1 + S2 - 1`, and every operand of the resulting SCEV is combined from operands of initial SCEV and has much higher complexity than they have. As result, if we try to calculate something like: %x1 = {a,+,b} %x2 = mul i32 %x1, %x1 %x3 = mul i32 %x2, %x1 %x4 = mul i32 %x3, %x2 ... The size of such SCEVs grows as `2^N`, and the arguments become more and more complex as we go forth. This leads to long compilation and huge memory consumption. This patch sets a limit after which we don't try to combine two `SCEVAddRecExpr`s into one. By default, max allowed size of the resulting AddRecExpr is set to 16. Differential Revision: https://reviews.llvm.org/D35664 llvm-svn: 308847
* [Analysis] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko2017-07-215-35/+90
| | | | | | other minor fixes (NFC). llvm-svn: 308787
* [SystemZ, LoopStrengthReduce]Jonas Paulsson2017-07-211-2/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch makes LSR generate better code for SystemZ in the cases of memory intrinsics, Load->Store pairs or comparison of immediate with memory. In order to achieve this, the following common code changes were made: * New TTI hook: LSRWithInstrQueries(), which defaults to false. Controls if LSR should do instruction-based addressing evaluations by calling isLegalAddressingMode() with the Instruction pointers. * In LoopStrengthReduce: handle address operands of memset, memmove and memcpy as address uses, and call isFoldableMemAccessOffset() for any LSRUse::Address, not just loads or stores. SystemZ changes: * isLSRCostLess() implemented with Insns first, and without ImmCost. * New function supportedAddressingMode() that is a helper for TTI methods looking at Instructions passed via pointers. Review: Ulrich Weigand, Quentin Colombet https://reviews.llvm.org/D35262 https://reviews.llvm.org/D35049 llvm-svn: 308729
* [PM/LCG] Follow-up fix to r308088 to handle deletion of libraryChandler Carruth2017-07-191-1/+6
| | | | | | | | | | | | | | | | | | | | | | | functions. In the prior commit, we provide ordering to the LCG between functions and library function definitions that they might begin to call through transformations. But we still would delete these library functions from the call graph if they became dead during inlining. While this immediately crashed, it also exposed a loss of information. We shouldn't remove definitions of library functions that can still usefully participate in the LCG-powered CGSCC optimization process. If new call edges are formed, we want to have definitions to be called. We can still remove these functions if truly dead using global-dce, etc, but removing them during the CGSCC walk is premature. This fixes a crash in the new PM when optimizing some unusual libraries that end up with "internal" lib functions such as the code in the "R" language's libraries. llvm-svn: 308417
* 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
OpenPOWER on IntegriCloud