summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [SCEV] Eta reduce some lambdas; NFCSanjoy Das2016-11-101-3/+2
| | | | llvm-svn: 286429
* Add isHotBB helper function to ProfileSummaryInfoDehao Chen2016-11-091-0/+20
| | | | | | | | | | | | Summary: This will unify all BB hotness checks. Reviewers: eraman, davidxl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D26353 llvm-svn: 286415
* [SCEV] Refactor out a useful pattern; NFCSanjoy Das2016-11-091-134/+20
| | | | llvm-svn: 286386
* Revert "[ThinLTO] Prevent exporting of locals used/defined in module level asm"Mehdi Amini2016-11-092-58/+5
| | | | | | | | This reverts commit r286297. Introduces a dependency from libAnalysis to libObject, which I missed during the review. llvm-svn: 286329
* [ValueTracking] recognize obfuscated variants of umin/umaxSanjay Patel2016-11-091-1/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | The smallest tests that expose this are codegen tests (because SelectionDAGBuilder::visitSelect() uses matchSelectPattern to create UMAX/UMIN nodes), but it's also possible to see the effects in IR alone with folds of min/max pairs. If these were written as unsigned compares in IR, InstCombine canonicalizes the unsigned compares to signed compares. Ie, running the optimizer pessimizes the codegen for this case without this patch: define <4 x i32> @umax_vec(<4 x i32> %x) { %cmp = icmp ugt <4 x i32> %x, <i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647> %sel = select <4 x i1> %cmp, <4 x i32> %x, <4 x i32> <i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647> ret <4 x i32> %sel } $ ./opt umax.ll -S | ./llc -o - -mattr=avx vpmaxud LCPI0_0(%rip), %xmm0, %xmm0 $ ./opt -instcombine umax.ll -S | ./llc -o - -mattr=avx vpxor %xmm1, %xmm1, %xmm1 vpcmpgtd %xmm0, %xmm1, %xmm1 vmovaps LCPI0_0(%rip), %xmm2 ## xmm2 = [2147483647,2147483647,2147483647,2147483647] vblendvps %xmm1, %xmm0, %xmm2, %xmm0 Differential Revision: https://reviews.llvm.org/D26096 llvm-svn: 286318
* [ThinLTO] Prevent exporting of locals used/defined in module level asmTeresa Johnson2016-11-082-5/+58
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch uses the same approach added for inline asm in r285513 to similarly prevent promotion/renaming of locals used or defined in module level asm. All static global values defined in normal IR and used in module level asm should be included on either the llvm.used or llvm.compiler.used global. The former were already being flagged as NoRename in the summary, and I've simply added llvm.compiler.used values to this handling. Module level asm may also contain defs of values. We need to prevent export of any refs to local values defined in module level asm (e.g. a ref in normal IR), since that also requires renaming/promotion of the local. To do that, the summary index builder looks at all values in the module level asm string that are not marked Weak or Global, which is exactly the set of locals that are defined. A summary is created for each of these local defs and flagged as NoRename. This required adding handling to the BitcodeWriter to look at GV declarations to see if they have a summary (rather than skipping them all). Finally, added an assert to IRObjectFile::CollectAsmUndefinedRefs to ensure that an MCAsmParser is available, otherwise the module asm parse would silently fail. Initialized the asm parser in the opt tool for use in testing this fix. Fixes PR30610. Reviewers: mehdi_amini Subscribers: johanengelen, krasin, llvm-commits Differential Revision: https://reviews.llvm.org/D26146 llvm-svn: 286297
* [BasicAA] Teach BasicAA to handle the inaccessiblememonly and ↵Andrew Kaylor2016-11-082-2/+7
| | | | | | | | inaccessiblemem_or_argmemonly attributes Differential Revision: https://reviews.llvm.org/D26382 llvm-svn: 286294
* [TBAA] Drop support for "old style" scalar TBAA tagsSanjoy Das2016-11-081-57/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: We've had support for auto upgrading old style scalar TBAA access metadata tags into the "new" struct path aware TBAA metadata for 3 years now. The only way to actually generate old style TBAA was explicitly through the IRBuilder API. I think this is a good time for dropping support for old style scalar TBAA. I'm not removing support for textual or bitcode upgrade -- if you have IR with the old style scalar TBAA tags that go through the AsmParser orf the bitcode parser before LLVM sees them, they will keep working as usual. Note: %val = load i32, i32* %ptr, !tbaa !N !N = < scalar tbaa node > is equivalent to %val = load i32, i32* %ptr, !tbaa !M !N = < scalar tbaa node > !M = !{!N, !N, 0} Reviewers: manmanren, chandlerc, sunfish Subscribers: mcrosier, llvm-commits, mgorny Differential Revision: https://reviews.llvm.org/D26229 llvm-svn: 286291
* NFC small changes in MemDepPiotr Padlewski2016-11-081-3/+3
| | | | llvm-svn: 286260
* Adds the loop end location to the loop metadata.Amara Emerson2016-11-081-7/+24
| | | | | | | | | | This additional information can be used to improve the locations when generating remarks for loops. Patch by Florian Hahn. Differential Revision: https://reviews.llvm.org/D25763 llvm-svn: 286227
* [OptDiag, opt-viewer] Save callee's location and display as linkAdam Nemet2016-11-071-0/+2
| | | | | | | | | | | | | With this we get a new field in the YAML record if the value being streamed out has a debug location. For examples, please see the changes to the tests. This is then used in opt-viewer to display a link for the callee function in the inlining remarks. Differential Revision: https://reviews.llvm.org/D26366 llvm-svn: 286169
* [AliasSetTracker] Make AST smarter about assume intrinsics that don't ↵Chad Rosier2016-11-071-0/+12
| | | | | | | | actually affect memory. Differential Revision: https://reviews.llvm.org/D26252 llvm-svn: 286108
* DCE math library calls with a constant operand.Eli Friedman2016-11-021-0/+149
| | | | | | | | | | | On platforms which use -fmath-errno, math libcalls without any uses require some extra checks to figure out if they are actually dead. Fixes https://llvm.org/bugs/show_bug.cgi?id=30464 . Differential Revision: https://reviews.llvm.org/D25970 llvm-svn: 285857
* [ValueTracking] remove TODO comment; NFCSanjay Patel2016-11-011-2/+0
| | | | | | | | | | InstCombine should always canonicalize patterns like the one shown in the comment when visiting 'select' insts in adjustMinMax(). Scalars were already handled there, and vector splats are handled after: https://reviews.llvm.org/rL285732 llvm-svn: 285744
* [TBAA] Use wrapper objects instead of raw getOperand s; NFCSanjoy Das2016-11-011-33/+47
| | | | | | | | | | | | This is intended to make the semantic intent clearer. The wrapper objects are now generic to avoid `const_cast` s. Since `const` ness is part of the API of `MDNode::getMostGenericTBAA` (and therefore I can't make things `const` all the way through without some code churn outside TypeBasedAliasAnalysis.cpp), this seemed like the cleanest solution. llvm-svn: 285665
* [TBAA] Rename accessors to be more idiomatic; NFCSanjoy Das2016-11-011-10/+10
| | | | llvm-svn: 285661
* [SCEV] Try to order n-ary expressions in CompareValueComplexitySanjoy Das2016-10-311-10/+35
| | | | llvm-svn: 285535
* [SCEV] In CompareValueComplexity, order global values by their nameSanjoy Das2016-10-301-0/+15
| | | | llvm-svn: 285529
* [SCEV] Use auto for consistency with an upcoming change; NFCSanjoy Das2016-10-301-4/+4
| | | | llvm-svn: 285528
* [ThinLTO] Use per-summary flag to prevent exporting locals used in inline asmTeresa Johnson2016-10-301-46/+30
| | | | | | | | | | | | | | | | | | | | | Summary: Instead of using the workaround of suppressing the entire index for modules that call inline asm that may reference locals, use the NoRename flag on the summary for any locals in the llvm.used set, and add a reference edge from any functions containing inline asm. This avoids issues from having no summaries despite the module defining global values, which was preventing more aggressive index-based optimization. It will be followed by a subsequent patch to make a similar fix for local references in module level asm (to fix PR30610). Reviewers: mehdi_amini Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D26121 llvm-svn: 285513
* [ValueTracking] recognize more variants of smin/smaxSanjay Patel2016-10-291-10/+18
| | | | | | | | | | | | | Try harder to detect obfuscated min/max patterns: the initial pattern was added with D9352 / rL236202. There was a bug fix for PR27137 at rL264996, but I think we can do better by folding the corresponding smax pattern and commuted variants. The codegen tests demonstrate the effect of ValueTracking on the backend via SelectionDAGBuilder. We can't expose these differences minimally in IR because we don't have smin/smax intrinsics for IR. Differential Revision: https://reviews.llvm.org/D26091 llvm-svn: 285499
* [Loads] Fix crash in is isDereferenceableAndAlignedPointer()Tom Stellard2016-10-281-2/+5
| | | | | | | | | | | | | | | Summary: We were trying to add APInt values with different bit sizes after visiting an addrspacecast instruction which changed the bit width of the pointer. Reviewers: majnemer, hfinkel Subscribers: hfinkel, wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D24774 llvm-svn: 285407
* [LCSSA] Perform LCSSA verification only for the current loop nest.Igor Laevsky2016-10-282-0/+15
| | | | | | | | | Now LPPassManager will run LCSSA verification only for the top-level loop which was processed on the current iteration. Differential Revision: https://reviews.llvm.org/D25873 llvm-svn: 285394
* [ThinLTO] Create AliasSummary when building indexTeresa Johnson2016-10-281-6/+24
| | | | | | | | | | | | | | | | | | | Summary: Previously we were creating the alias summary on the fly while writing the summary to bitcode. This moves the creation of these summaries to the module summary index builder where we build the rest of the summary index. This is going to be necessary for setting the NoRename flag for values possibly used in inline asm or module level asm. Reviewers: mehdi_amini Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D26049 llvm-svn: 285379
* [ValueTracking] fix matchSelectPattern to allow vector splat folds of ↵Sanjay Patel2016-10-271-6/+8
| | | | | | min/max/abs/nabs llvm-svn: 285303
* Simplify `x >=u x >> y` and `x >=u x udiv y`Sanjoy Das2016-10-261-0/+11
| | | | | | | | | | | | | | | | | | | Summary: Extends InstSimplify to handle both `x >=u x >> y` and `x >=u x udiv y`. This is a folloup of rL258422 and https://github.com/rust-lang/rust/pull/30917 where llvm failed to optimize away the bounds checking in a binary search. Patch by Arthur Silva! Reviewers: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D25941 llvm-svn: 285228
* Revert "[AliasSetTracker] Make AST smarter about intrinsics that don't ↵Chad Rosier2016-10-261-15/+0
| | | | | | | | | | | actually affect memory." This reverts commit r285191. LICM appears to rely on the Alias Set Tracker hitting lifetime markers to prevent code from being moved outside of the original scope. llvm-svn: 285227
* [AliasSetTracker] Make AST smarter about intrinsics that don't actually ↵Chad Rosier2016-10-261-0/+15
| | | | | | | | affect memory. Differential Revision: https://reviews.llvm.org/D25969 llvm-svn: 285191
* Fix regression from my recent GlobalsAA fix.Eli Friedman2016-10-241-1/+3
| | | | | | | | | | | | | There are two fixes here: one, AnalyzeUsesOfPointer can't return false until it has checked all the uses of the pointer. Two, if a global uses another global, we have to assume the address of the first global escapes. Fixes https://llvm.org/bugs/show_bug.cgi?id=30707 . Differential Revision: https://reviews.llvm.org/D25798 llvm-svn: 285034
* [BasicAA] Fix - missed alias in GEP expressionsGerolf Hoflehner2016-10-221-5/+11
| | | | | | | | | | | | In BasicAA GEP operand values get adjusted ("wrap-around") based on the pointersize. Otherwise, in non-64b modes, AA could report false negatives. However, a wrap-around is valid only for a fully evaluated expression. It had been introduced to fix an alias problem in http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160118/326163.html. This commit restricts the wrap-around to constant gep operands only where the value is known at compile-time. llvm-svn: 284908
* Analysis: Move llvm::getConstantRangeFromMetadata to IR library.Peter Collingbourne2016-10-211-22/+0
| | | | | | | | We're about to start using it there. Differential Revision: https://reviews.llvm.org/D25877 llvm-svn: 284865
* [LVI] Fix a bug with a guard being the very first instruction in a BB not ↵Artur Pilipenko2016-10-211-5/+4
| | | | | | | | taken into account While looking for guards use reverse iterator and scan up to rend() not to begin() llvm-svn: 284827
* [LoopUnroll] Keep the loop test only on the first iteration of max-or-zero loopsJohn Brawn2016-10-211-17/+40
| | | | | | | | | | | | | | | | When we have a loop with a known upper bound on the number of iterations, and furthermore know that either the number of iterations will be either exactly that upper bound or zero, then we can fully unroll up to that upper bound keeping only the first loop test to check for the zero iteration case. Most of the work here is in plumbing this 'max-or-zero' information from the part of scalar evolution where it's detected through to loop unrolling. I've also gone for the safe default of 'false' everywhere but howManyLessThans which could probably be improved. Differential Revision: https://reviews.llvm.org/D25682 llvm-svn: 284818
* [SCEV] Add a threshold to restrict number of mul operands to be inlined into ↵Li Huang2016-10-201-0/+7
| | | | | | | | | | | | | SCEV This is to avoid inlining too many multiplication operands into a SCEV, which could take exponential time in the worst case. Reviewers: Sanjoy Das, Mehdi Amini, Michael Zolotukhin Differential Revision: https://reviews.llvm.org/D25794 llvm-svn: 284784
* Retire llvm::alignOf in favor of C++11 alignof.Benjamin Kramer2016-10-201-1/+1
| | | | | | No functionality change intended. llvm-svn: 284733
* Do a sweep over move ctors and remove those that are identical to the default.Benjamin Kramer2016-10-201-11/+2
| | | | | | | | | | All of these existed because MSVC 2013 was unable to synthesize default move ctors. We recently dropped support for it so all that error-prone boilerplate can go. No functionality change intended. llvm-svn: 284721
* [InstSimplify] fold negation of sign-bitSanjay Patel2016-10-191-3/+20
| | | | | | | | | | | | | | | | 0 - X --> X, if X is 0 or the minimum signed value 0 - X --> 0, if X is 0 or the minimum signed value and the sub is NSW I noticed this pattern might be created in the backend after the change from D25485, so we'll want to add a similar fold for the DAG. The use of computeKnownBits in InstSimplify may be something to investigate if the compile time of InstSimplify is noticeable. We could replace computeKnownBits with specific pattern matchers or limit the recursion. Differential Revision: https://reviews.llvm.org/D25785 llvm-svn: 284649
* [AliasSetTracker] Add support for memcpy and memmove.Chad Rosier2016-10-191-1/+23
| | | | | | Differential Revision: https://reviews.llvm.org/D25776 llvm-svn: 284630
* [AliasSetTracker] Return void for add() functions. NFC.Chad Rosier2016-10-191-42/+24
| | | | | | Differential Revision: https://reviews.llvm.org/D25748 llvm-svn: 284628
* [SCEV] Make CompareValueComplexity a little bit smarterSanjoy Das2016-10-181-2/+12
| | | | | | | | This helps canonicalization in some cases. Thanks to Pankaj Chawla for the investigation and the test case! llvm-svn: 284501
* [SCEV] Extract out a helper function; NFCSanjoy Das2016-10-181-45/+46
| | | | llvm-svn: 284500
* [SCEV] More accurate calculation of max backedge count of some less-than loopsJohn Brawn2016-10-181-28/+53
| | | | | | | | | | | | | | | | | | | | | In loops that look something like i = n; do { ... } while(i++ < n+k); where k is a constant, the maximum backedge count is k (in fact the backedge count will be either 0 or k, depending on whether n+k wraps). More generally for LHS < RHS if RHS-(LHS of first comparison) is a constant then the loop will iterate either 0 or that constant number of times. This allows for more loop unrolling with the recent upper bound loop unrolling changes, and I'm working on a patch that will let loop unrolling additionally make use of the loop being executed either 0 or k times (we need to retain the loop comparison only on the first unrolled iteration). Differential Revision: https://reviews.llvm.org/D25607 llvm-svn: 284465
* [SCEV] Consider delinearization pattern with extension with identity factorTobias Grosser2016-10-171-1/+2
| | | | | | | | | | | | Summary: The delinearization algorithm did not consider terms which had an extension without a multiply factor, i.e. a identify factor. We lose cases where size is char type where there will no multiply factor. Reviewers: sanjoy, grosser Subscribers: mzolotukhin, Eugene.Zelenko, llvm-commits, mssimpso, sanjoy, grosser Differential Revision: https://reviews.llvm.org/D16492 llvm-svn: 284378
* Test commit. (NFC)Li Huang2016-10-151-1/+1
| | | | llvm-svn: 284307
* Create llvm.addressofreturnaddress intrinsicAlbert Gutowski2016-10-121-0/+1
| | | | | | | | | | | | Summary: We need a new LLVM intrinsic to implement MS _AddressOfReturnAddress builtin on 64-bit Windows. Reviewers: majnemer, rnk Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D25293 llvm-svn: 284061
* Reapply "[LoopUnroll] Use the upper bound of the loop trip count to fullly ↵Haicheng Wu2016-10-121-10/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | unroll a loop" Reappy r284044 after revert in r284051. Krzysztof fixed the error in r284049. The original summary: This patch tries to fully unroll loops having break statement like this for (int i = 0; i < 8; i++) { if (a[i] == value) { found = true; break; } } GCC can fully unroll such loops, but currently LLVM cannot because LLVM only supports loops having exact constant trip counts. The upper bound of the trip count can be obtained from calling ScalarEvolution::getMaxBackedgeTakenCount(). Part of the patch is the refactoring work in SCEV to prevent duplicating code. The feature of using the upper bound is enabled under the same circumstance when runtime unrolling is enabled since both are used to unroll loops without knowing the exact constant trip count. llvm-svn: 284053
* Revert "[LoopUnroll] Use the upper bound of the loop trip count to fullly ↵Haicheng Wu2016-10-121-20/+10
| | | | | | | | unroll a loop" This reverts commit r284044. llvm-svn: 284051
* [LoopUnroll] Use the upper bound of the loop trip count to fullly unroll a loopHaicheng Wu2016-10-121-10/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch tries to fully unroll loops having break statement like this for (int i = 0; i < 8; i++) { if (a[i] == value) { found = true; break; } } GCC can fully unroll such loops, but currently LLVM cannot because LLVM only supports loops having exact constant trip counts. The upper bound of the trip count can be obtained from calling ScalarEvolution::getMaxBackedgeTakenCount(). Part of the patch is the refactoring work in SCEV to prevent duplicating code. The feature of using the upper bound is enabled under the same circumstance when runtime unrolling is enabled since both are used to unroll loops without knowing the exact constant trip count. Differential Revision: https://reviews.llvm.org/D24790 llvm-svn: 284044
* [ValueTracking] An improvement to IR ValueTracking on Non-negative IntegersArtur Pilipenko2016-10-121-3/+46
| | | | | | | | | | Since this change is known to cause performance degradations in some cases it's commited under a temporary flag which is turned off by default. Patch by Li Huang Differential Revision: https://reviews.llvm.org/D18777 llvm-svn: 284022
* [LCG] Add the necessary functionality to the LazyCallGraph to support inlining.Chandler Carruth2016-10-121-1/+164
| | | | | | | | | | | | | | | | | | | | | | | | | | | | The basic inlining operation makes the following changes to the call graph: 1) Add edges that were previously transitive edges. This is always trivial and this patch gives the LCG helper methods to make this more convenient. 2) Remove the inlined edge. We had existing support for this, but it contained bugs that needed to be fixed. Testing in the same pattern as the inliner exposes these bugs very nicely. 3) Delete a function when it becomes dead because it is internal and all calls have been inlined. The LCG had no support at all for this operation, so this adds that support. Two unittests have been added that exercise this specific mutation pattern to the call graph. They were extremely effective in uncovering bugs. Sadly, a large fraction of the code here is just to implement those unit tests, but I think they're paying for themselves. =] This was split out of a patch that actually uses the routines to implement inlining in the new pass manager in order to isolate (with unit tests) the logic that was entirely within the LCG. Many thanks for the careful review from folks! There will be a few minor follow-up patches based on the comments in the review as well. Differential Revision: https://reviews.llvm.org/D24225 llvm-svn: 283982
OpenPOWER on IntegriCloud