summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Revert r298711 "[InstCombine] Provide a way to calculate KnownZero/One for ↵Craig Topper2017-03-241-35/+21
| | | | | | | | Add/Sub in SimplifyDemandedUseBits without recursing into ComputeKnownBits" Tsan bot is failing. llvm-svn: 298745
* [InstCombine] Provide a way to calculate KnownZero/One for Add/Sub in ↵Craig Topper2017-03-241-21/+35
| | | | | | | | SimplifyDemandedUseBits without recursing into ComputeKnownBits SimplifyDemandedUseBits for Add/Sub already recursed down LHS and RHS for simplifying bits. If that didn't provide any simplifications we fall back to calling computeKnownBits which will recurse again. Instead just take the known bits for LHS and RHS we already have and call into a new function in ValueTracking that can calculate the known bits given the LHS/RHS bits. llvm-svn: 298711
* Revert "[ScalarEvolution] Re-enable Predicate implication from operations"Max Kazantsev2017-03-241-159/+16
| | | | | | | | This reverts commit rL298690 Causes failures on clang. llvm-svn: 298693
* [ScalarEvolution] Re-enable Predicate implication from operationsMax Kazantsev2017-03-241-16/+159
| | | | | | | | | | | | | | | | | | | | | | | | The patch rL298481 was reverted due to crash on clang-with-lto-ubuntu build. The reason of the crash was type mismatch between either a or b and RHS in the following situation: LHS = sext(a +nsw b) > RHS. This is quite rare, but still possible situation. Normally we need to cast all {a, b, RHS} to their widest type. But we try to avoid creation of new SCEV that are not constants to avoid initiating recursive analysis that can take a lot of time and/or cache a bad value for iterations number. To deal with this, in this patch we reject this case and will not try to analyze it if the type of sum doesn't match with the type of RHS. In this situation we don't need to create any non-constant SCEVs. This patch also adds an assertion to the method IsProvedViaContext so that we could fail on it and not go further into range analysis etc (because in some situations these analyzes succeed even when the passed arguments have wrong types, what should not normally happen). The patch also contains a fix for a problem with too narrow scope of the analysis caused by wrong usage of predicates in recursive invocations. The regression test on the said failure: test/Analysis/ScalarEvolution/implied-via-addition.ll llvm-svn: 298690
* [ValueTracking] Use uint64_t for CarryIn in computeKnownBitsAddSub instead ↵Craig Topper2017-03-241-2/+2
| | | | | | of a creating a temporary APInt. NFC llvm-svn: 298688
* [ValueTracking] Convert more places to use ↵Craig Topper2017-03-241-7/+6
| | | | | | setHighBits/setLowBits/setSignBit. NFCI llvm-svn: 298683
* Use isFunctionHotInCallGraph to set the function section prefix.Dehao Chen2017-03-231-0/+38
| | | | | | | | | | | | | | Summary: The current prefix based function layout algorithm only looks at function's entry count, which is not sufficient. A function should be grouped together if its entry count or any call edge count is hot. Reviewers: davidxl, eraman Reviewed By: eraman Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D31225 llvm-svn: 298656
* [LVIPrinterPass] Print LVI info for function argumentsAnna Thomas2017-03-231-0/+12
| | | | | | | | | Using AssemblyAnnotationWriter for LVI printer prints for instructions and basic blocks. So, we explicitly need to print LVI info for the arguments of the function (these are values and not instructions). llvm-svn: 298640
* Model ashr(shl(x, n), m) as mul(x, 2^(n-m)) when n > mZhaoshi Zheng2017-03-231-19/+46
| | | | | | | | | | | | | Given below case: %y = shl %x, n %z = ashr %y, m when n = m, SCEV models it as sext(trunc(x)). This patch tries to handle the case where n > m by using sext(mul(trunc(x), 2^(n-m)))) as the SCEV expression. llvm-svn: 298631
* revert test commit r298629Zhaoshi Zheng2017-03-231-4/+0
| | | | llvm-svn: 298630
* test commitZhaoshi Zheng2017-03-231-0/+4
| | | | llvm-svn: 298629
* [ValueTracking] Use APInt::isNegative instead of using operator[BitWidth-1]. ↵Craig Topper2017-03-231-7/+7
| | | | | | NFCI llvm-svn: 298584
* [ValueTracking] Use setAllBits/setSignBit/setLowBits/setHighBits. NFCICraig Topper2017-03-231-20/+22
| | | | llvm-svn: 298583
* [LVI] Add an LVI printer pass to capture test LVI cache after transformationsAnna Thomas2017-03-222-6/+97
| | | | | | | | | | | | | | | | | | | Summary: Adding a printer pass for printing the LVI cache values after transformations that use LVI. This will help us in identifying cases where LVI invariants are violated, or transforms that leave LVI in an incorrect state. Right now, I have added two test cases to show that the printer pass is working. I will be adding more test cases in a later change, once this change is checked in upstream. Reviewers: reames, dberlin, sanjoy, apilipenko Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D30790 llvm-svn: 298542
* Revert "[ScalarEvolution] Predicate implication from operations"Max Kazantsev2017-03-221-147/+16
| | | | | | | | This reverts commit rL298481 Fails clang-with-lto-ubuntu build. llvm-svn: 298489
* [ValueTracking] Make sure we keep range metadata information when ↵Craig Topper2017-03-221-2/+2
| | | | | | calculating known bits for calls to bitreverse intrinsic. llvm-svn: 298488
* [ValueTracking] use setLowBits/setHighBits/setBitsFrom to replace |= ↵Craig Topper2017-03-221-16/+13
| | | | | | getHighBits/getLowBits. NFCI llvm-svn: 298486
* [ScalarEvolution] Predicate implication from operationsMax Kazantsev2017-03-221-16/+147
| | | | | | | | | | | | | | | | | | | | | | | This patch allows SCEV predicate analysis to prove implication of some expression predicates from context predicates related to arguments of those expressions. It introduces three new rules: For addition: (A >X && B >= 0) || (B >= 0 && A > X) ===> (A + B) > X. For division: (A > X) && (0 < B <= X + 1) ===> (A / B > 0). (A > X) && (-B <= X < 0) ===> (A / B >= 0). Using these rules, SCEV is able to prove facts like "if X > 1 then X / 2 > 0". They can also be combined with the same context, to prove more complex expressions like "if X > 1 then X/2 + 1 > 1". Diffirential Revision: https://reviews.llvm.org/D30887 Reviewed by: sanjoy llvm-svn: 298481
* Let llvm.objectsize be conservative with null pointersGeorge Burgess IV2017-03-212-17/+25
| | | | | | | | | | | This adds a parameter to @llvm.objectsize that makes it return conservative values if it's given null. This fixes PR23277. Differential Revision: https://reviews.llvm.org/D28494 llvm-svn: 298430
* Do not inline hot callsites for samplepgo in thinlto compile phase.Dehao Chen2017-03-211-1/+1
| | | | | | | | | | | | | | Summary: Because SamplePGO passes will be invoked twice in ThinLTO build: once at compile phase, the other at backend. We want to make sure the IR at the 2nd phase matches the hot part in profile, thus we do not want to inline hot callsites in the first phase. Reviewers: tejohnson, eraman Reviewed By: tejohnson Subscribers: mehdi_amini, llvm-commits, Prazek Differential Revision: https://reviews.llvm.org/D31201 llvm-svn: 298428
* Use ProfileSummary:getProfileCount to get ScaledCount for ModuleSummaryDehao Chen2017-03-211-1/+1
| | | | | | | | | | | | | | Summary: ModuleSummary should use the standard interface of ProfileSummary::getProfileCount. Reviewers: eraman, tejohnson Reviewed By: tejohnson Subscribers: tejohnson, mehdi_amini, llvm-commits Differential Revision: https://reviews.llvm.org/D31154 llvm-svn: 298404
* Rename AttributeSet to AttributeListReid Kleckner2017-03-211-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: This class is a list of AttributeSetNodes corresponding the function prototype of a call or function declaration. This class used to be called ParamAttrListPtr, then AttrListPtr, then AttributeSet. It is typically accessed by parameter and return value index, so "AttributeList" seems like a more intuitive name. Rename AttributeSetImpl to AttributeListImpl to follow suit. It's useful to rename this class so that we can rename AttributeSetNode to AttributeSet later. AttributeSet is the set of attributes that apply to a single function, argument, or return value. Reviewers: sanjoy, javed.absar, chandlerc, pete Reviewed By: pete Subscribers: pete, jholewinski, arsenm, dschuff, mehdi_amini, jfb, nhaehnle, sbc100, void, llvm-commits Differential Revision: https://reviews.llvm.org/D31102 llvm-svn: 298393
* [ConstantFolding] Fix to prevent constant folding having to repeatedly scan ↵David Green2017-03-211-1/+1
| | | | | | | | | | | | | operands. NFCI After the loop unroll threshold was increased in r295538, very large constant expressions can be created. This prevents them from having to be recursively scanned, leading to a compile time blow-up. Differential Revision: https://reviews.llvm.org/D30689 llvm-svn: 298356
* [SCEV] Fix trip multiple calculationEli Friedman2017-03-201-10/+16
| | | | | | | | | | | | | | | | | | | | If loop bound containing calculations like min(a,b), the Scalar Evolution API getSmallConstantTripMultiple returns 4294967295 "-1" as the trip multiple. The problem is that, SCEV use -1 * umax to represent umin. The multiple constant -1 was returned, and the logic of guarding against huge trip counts was skipped. Because -1 has 32 active bits. The fix attempt to factor more general cases. First try to get the greatest power of two divisor of trip count expression. In case overflow happens, the trip count expression is still divisible by the greatest power of two divisor returned. Returns 1 if not divisible by 2. Patch by Huihui Zhang <huihuiz@codeaurora.org> Differential Revision: https://reviews.llvm.org/D30840 llvm-svn: 298301
* Use MutableArrayRef for APFloat::convertToIntegerSimon Pilgrim2017-03-201-3/+3
| | | | | | As discussed on D31074, use MutableArrayRef for destination integer buffers to help assert before stack overflows happen. llvm-svn: 298253
* Extract FindAvailablePtrLoadStore out of FindAvailableLoadedValue. NFCIXin Tong2017-03-191-14/+18
| | | | | | | | | | | | | | | | | | | Summary: Extract FindAvailablePtrLoadStore out of FindAvailableLoadedValue. Prepare for upcoming change which will do phi-translation for load on phi pointer in jump threading SimplifyPartiallyRedundantLoad. This is in preparation for https://reviews.llvm.org/D30543 Reviewers: efriedma, sanjoy, davide, dberlin Reviewed By: davide Subscribers: junbuml, davide, llvm-commits Differential Revision: https://reviews.llvm.org/D30524 llvm-svn: 298216
* [Analysis] bitreverse(undef) returns undefBrian Gesiak2017-03-191-1/+2
| | | | | | | | | | | | | | | | Summary: The reverse of an artbitrary bitpattern is also an arbitrary bitpattern. Reviewers: trentxintong, arsenm, majnemer Reviewed By: majnemer Subscribers: majnemer, wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D31118 llvm-svn: 298201
* [ValueTracking] Remove deadish code from computeKnownBitsAddSub.Craig Topper2017-03-181-24/+0
| | | | | | The code assigned to KnownZero, but later code unconditionally assigned over it. I'm pretty sure the later code can handle the same cases and more equally well. llvm-svn: 298190
* [ValueTracking] Add APInt::setSignBit and use it to replace ORing with ↵Craig Topper2017-03-181-6/+6
| | | | | | getSignBit which will malloc if the bit width is larger than 64. llvm-svn: 298180
* [SCEV] Use const Loop *L instead of Loop *L. NFCEli Friedman2017-03-171-6/+7
| | | | | | | | Use const pointer in the trip count and trip multiple calculations. Patch by Huihui Zhang <huihuiz@codeaurora.org> llvm-svn: 298161
* [SCEV] Compute affine range in another way to avoid bitwidth extending.Michael Zolotukhin2017-03-161-49/+90
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This approach has two major advantages over the existing one: 1. We don't need to extend bitwidth in our computations. Extending bitwidth is a big issue for compile time as we often end up working with APInts wider than 64bit, which is a slow case for APInt. 2. When we zero extend a wrapped range, we lose some information (we replace the range with [0, 1 << src bit width)). Thus, avoiding such extensions better preserves information. Correctness testing: I ran 'ninja check' with assertions that the new implementation of getRangeForAffineAR gives the same results as the old one (this functionality is not present in this patch). There were several failures - I inspected them manually and found out that they all are caused by the fact that we're returning more accurate results now (see bullet (2) above). Without such assertions 'ninja check' works just fine, as well as SPEC2006. Compile time testing: CTMark/Os: - mafft/pairlocalalign -16.98% - tramp3d-v4/tramp3d-v4 -12.72% - lencod/lencod -11.51% - Bullet/bullet -4.36% - ClamAV/clamscan -3.66% - 7zip/7zip-benchmark -3.19% - sqlite3/sqlite3 -2.95% - SPASS/SPASS -2.74% - Average -5.81% Performance testing: The changes are expected to be neutral for runtime performance. Reviewers: sanjoy, atrick, pete Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D30477 llvm-svn: 297992
* [ValueTracking] Out of range shifts might be undefOliver Stannard2017-03-141-0/+8
| | | | | | | | | | | | | | If it is possible for the RHS of a shift operation to be greater than or equal to the bit-width, then the result might be undef, and we can't report any known bits. In some cases, this was allowing a transformation in instcombine which widened an undef value from i1 to i32, increasing the range of values that a function could return. Differential revision: https://reviews.llvm.org/D30781 llvm-svn: 297724
* [TargetTransformInfo] getIntrinsicInstrCost() scalarization estimation improvedJonas Paulsson2017-03-142-9/+7
| | | | | | | | | | | | | | | | | | | | | getIntrinsicInstrCost() used to only compute scalarization cost based on types. This patch improves this so that the actual arguments are checked when they are available, in order to handle only unique non-constant operands. Tests updates: Analysis/CostModel/X86/arith-fp.ll Transforms/LoopVectorize/AArch64/interleaved_cost.ll Transforms/LoopVectorize/ARM/interleaved_cost.ll The improvement in getOperandsScalarizationOverhead() to differentiate on constants made it necessary to update the interleaved_cost.ll tests even though they do not relate to intrinsics. Review: Hal Finkel https://reviews.llvm.org/D29540 llvm-svn: 297705
* [LVI] Add Datalayout to the class LazyValueInfo since all its Impls require ↵Anna Thomas2017-03-121-1/+1
| | | | | | it. NFC llvm-svn: 297583
* Use a WeakVH for UnknownInstructions in AliasSetTrackerSanjoy Das2017-03-111-22/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This change solves the same problem as D30726, except that this only throws out the bathwater. AST was not correctly tracking and deleting UnknownInstructions via handles. The existing code only tracks "pointers" in its `ASTCallbackVH`, so an UnknownInstruction (that isn't also def'ing a pointer used by another memory instruction) never gets a `ASTCallbackVH`. There are two other ways to solve this problem: - Use the `PointerRec` scheme for both known and unknown instructions. - Use a `CallbackVH` that erases the offending Instruction from the UnknownInstruction list. Both of the above changes seemed to be significantly (and unnecessarily IMO) more complex than this. Reviewers: chandlerc, dberlin, hfinkel, reames Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D30849 llvm-svn: 297539
* [ProfileSummaryInfo] Remove unneeded braces. NFCI.Davide Italiano2017-03-101-2/+1
| | | | llvm-svn: 297506
* Refactor the PSI to extract getCallSiteCount and remove checks for profile type.Dehao Chen2017-03-101-32/+21
| | | | | | | | | | | | | | Summary: There is no need to check profile count as only CallInst will have metadata attached. Reviewers: eraman Reviewed By: eraman Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D30799 llvm-svn: 297500
* [SLP] Revert everything that has to do with memory access sorting.Michael Kuperstein2017-03-101-51/+0
| | | | | | | | | | | | This reverts r293386, r294027, r294029 and r296411. Turns out the SLP tree isn't actually a "tree" and we don't handle accessing the same packet of loads in several different orders well, causing miscompiles. Revert until we can fix this properly. llvm-svn: 297493
* Implement getPassName() for IR printing passes.Yaron Keren2017-03-103-0/+6
| | | | llvm-svn: 297442
* Do not use branch metadata to check if a basic block is hot.Dehao Chen2017-03-101-12/+1
| | | | | | | | | | | | | | Summary: We should not use that to check basic block hotness as optimization may mess it up. Reviewers: eraman Reviewed By: eraman Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D30800 llvm-svn: 297437
* [InstSimplify] allow folds for bool vector div/remSanjay Patel2017-03-091-3/+3
| | | | llvm-svn: 297411
* [InstSimplify] vector div/rem with any zero element in divisor is undefSanjay Patel2017-03-091-0/+11
| | | | | | | | | | | This was suggested as a DAG simplification in the review for rL297026 : http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20170306/435253.html ...but let's start with IR since we have actual docs for IR (LangRef). Differential Revision: https://reviews.llvm.org/D30665 llvm-svn: 297390
* Perform symbol binding for .symver versioned symbolsTeresa Johnson2017-03-091-3/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: In a .symver assembler directive like: .symver name, name2@@nodename "name2@@nodename" should get the same symbol binding as "name". While the ELF object writer is updating the symbol binding for .symver aliases before emitting the object file, not doing so when the module inline assembly is handled by the RecordStreamer is causing the wrong behavior in *LTO mode. E.g. when "name" is global, "name2@@nodename" must also be marked as global. Otherwise, the symbol is skipped when iterating over the LTO InputFile symbols (InputFile::Symbol::shouldSkip). So, for example, when performing any *LTO via the gold-plugin, the versioned symbol definition is not recorded by the plugin and passed back to the linker. If the object was in an archive, and there were no other symbols needed from that object, the object would not be included in the final link and references to the versioned symbol are undefined. The llvm-lto2 tests added will give an error about an unused symbol resolution without the fix. Reviewers: rafael, pcc Reviewed By: pcc Subscribers: mehdi_amini, llvm-commits Differential Revision: https://reviews.llvm.org/D30485 llvm-svn: 297332
* [SLP] Fixed non-deterministic behavior in Loop Vectorizer.Amjad Aboud2017-03-081-9/+11
| | | | | | Differential Revision: https://reviews.llvm.org/D30638 llvm-svn: 297257
* Handle UnreachableInst in isGuaranteedToTransferExecutionToSuccessorSebastian Pop2017-03-081-0/+2
| | | | | | | | | | | A block with an UnreachableInst does not transfer execution to a successor. The problem was exposed by GVN-hoist. This patch fixes bug 32153. Patch by Aditya Kumar. Differential Revision: https://reviews.llvm.org/D30667 llvm-svn: 297254
* [SLP] Revert r296863 due to miscompiles.Michael Kuperstein2017-03-061-24/+8
| | | | | | Details and reproducer are on the email thread for r296863. llvm-svn: 297103
* [InstSimplify] refactor related div/rem folds; NFCISanjay Patel2017-03-061-47/+37
| | | | llvm-svn: 297052
* [InstSimplify] remove misleading comments; NFCSanjay Patel2017-03-061-2/+2
| | | | | | Div/rem-of-0 does not cause faults/undef (not the same as div/rem-by-0). llvm-svn: 297029
* [SCEV] Decrease the recursion threshold for CompareValueComplexitySanjoy Das2017-03-051-6/+11
| | | | | | | | | | Fixes PR32142. r287232 accidentally increased the recursion threshold for CompareValueComplexity from 2 to 32. This change reverses that change by introducing a separate flag for CompareValueComplexity's threshold. llvm-svn: 296992
* [SLP] Fixes the bug due to absence of in order uses of scalars which needs ↵Mohammad Shahid2017-03-031-8/+24
| | | | | | | | | | | | | | | | to be available for VectorizeTree() API.This API uses it for proper mask computation to be used in shufflevector IR. The fix is to compute the mask for out of order memory accesses while building the vectorizable tree instead of actual vectorization of vectorizable tree.It also needs to recompute the proper Lane for external use of vectorizable scalars based on shuffle mask. Reviewers: mkuper Differential Revision: https://reviews.llvm.org/D30159 Change-Id: Ide8773ce0ad3562f3cf4d1a0ad0f487e2f60ce5d llvm-svn: 296863
OpenPOWER on IntegriCloud