summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [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
* [CFL-AA] Remove unneeded function declaration. NFCI.Davide Italiano2017-06-261-3/+0
| | | | llvm-svn: 306268
* [MemDep] Cleanup return after else & use `auto`. NFC.Davide Italiano2017-06-251-3/+3
| | | | llvm-svn: 306255
* [AST] Fix a bug in aliasesUnknownInst. Make sure we are comparing the ↵Xin Tong2017-06-251-2/+2
| | | | | | | | | | | | | | | | unknown instructions in the alias set and the instruction interested in. Summary: Make sure we are comparing the unknown instructions in the alias set and the instruction interested in. I believe this is clearly a bug (missed opportunity). I can also add some test cases if desired. Reviewers: hfinkel, davide, dberlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34597 llvm-svn: 306241
* [SCEV] Avoid copying ConstantRange just to get the min/max valueCraig Topper2017-06-241-67/+62
| | | | | | | | | | | | | | | | | | | | | Summary: This patch changes getRange to getRangeRef and returns a reference to the ConstantRange object stored inside the DenseMap caches. We then take advantage of that to add new helper methods that can return min/max value of a signed or unsigned ConstantRange using that reference without first copying the ConstantRange. getRangeRef calls itself recursively and I believe the reference return is fine for those calls. I've left getSignedRange and getUnsignedRange returning a ConstantRange object so they will make a copy now. This is to ensure safety since the reference will be invalidated if the DenseMap changes. I'm sure there are still more places that can take advantage of the reference and I'll submit future patches as I find them. Reviewers: sanjoy, davide Reviewed By: sanjoy Subscribers: zzheng, llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D32978 llvm-svn: 306229
* fix trivial typos in comment, NFCHiroshi Inoue2017-06-241-1/+1
| | | | llvm-svn: 306211
* [IR][AssumptionCache] Add m_Shift and m_BitwiseLogic matchers to replace a ↵Craig Topper2017-06-241-9/+2
| | | | | | | | | | | | | | | | | | | couple m_CombineOr Summary: m_CombineOr isn't very efficient. The code using it is also quite verbose. This patch adds m_Shift and m_BitwiseLogic matchers to make the using code more concise and improve the match efficiency. Reviewers: spatel, davide Reviewed By: davide Subscribers: davide, llvm-commits Differential Revision: https://reviews.llvm.org/D34593 llvm-svn: 306206
* [ValueTracking][InstCombine] Use m_Shr instead m_CombineOr(m_LShr, m_AShr). NFCCraig Topper2017-06-241-5/+2
| | | | llvm-svn: 306205
* [Analysis][Transforms] Use commutable matchers instead of m_CombineOr in a ↵Craig Topper2017-06-241-4/+2
| | | | | | few places. NFC llvm-svn: 306204
* Make visible isDereferenceableAndAlignedPointer(..., const APInt &Size, ...)Vitaly Buka2017-06-241-0/+10
| | | | | | | | | | | | Summary: Used by D34311 and D34467 Reviewers: hfinkel, efriedma Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34585 llvm-svn: 306193
* [InlineCost] Do not take INT_MAX when Cost is negativeJun Bum Lim2017-06-231-5/+11
| | | | | | | | | | | | | | Summary: visitSwitchInst should not take INT_MAX when Cost is negative. Instead of INT_MAX , we also use a valid upperbound cost when overflow occurs in Cost. Reviewers: hans, echristo, dmgreen Reviewed By: dmgreen Subscribers: mcrosier, javed.absar, llvm-commits, eraman Differential Revision: https://reviews.llvm.org/D34436 llvm-svn: 306118
* [JumpThreading] Teach jump threading how to analyze (and (cmp A, C1), (cmp ↵Craig Topper2017-06-231-0/+20
| | | | | | | | | | | | | | A, C2)) after InstCombine has turned it into (cmp (add A, C3), C4) Currently JumpThreading can use LazyValueInfo to analyze an 'and' or 'or' of compare if the compare is fed by a livein of a basic block. This can be used to to prove the condition can't be met for some predecessor and the jump from that predecessor can be moved to the false path of the condition. But if the compare is something that InstCombine turns into an add and a single compare, it can't be analyzed because the livein is now an input to the add and not the compare. This patch adds a new method to LVI to get a ConstantRange on an edge. Then we teach jump threading to detect the add livein feeding a compare and to get the ConstantRange and propagate it. Differential Revision: https://reviews.llvm.org/D33262 llvm-svn: 306085
* [LVI] Teach LVI to reason about ORs of icmps similar to how it reasons about ↵Craig Topper2017-06-231-5/+5
| | | | | | | | | | | | | | | | ANDs of icmps Summary: LVI can reason about an AND of icmps on the true dest of a branch. I believe we can do similar for the false dest of ORs. This allows us to get the same answer for the demorganed versions of some of the AND test cases as you can see. Reviewers: anna, reames Reviewed By: reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34431 llvm-svn: 306076
* [BasicAA] Add type check and Value equality check around code added in r305481.Craig Topper2017-06-221-5/+8
| | | | | | | | This matches the checks done at the beginning of isKnownNonEqual that this code is partially emulating. Without this we can get assertion failures due to the bit widths of the KnownBits not matching. llvm-svn: 306044
* [BasicAA] Use MayAlias instead of PartialAlias for fallback.Michael Kruse2017-06-211-5/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Using various methods, BasicAA tries to determine whether two GetElementPtr memory locations alias when its base pointers are known to be equal. When none of its heuristics are applicable, it falls back to PartialAlias to, according to a comment, protect TBAA making a wrong decision in case of unions and malloc. PartialAlias is not correct, because a PartialAlias result implies that some, but not all, bytes overlap which is not necessarily the case here. AAResults returns the first analysis result that is not MayAlias. BasicAA is always the first alias analysis. When it returns PartialAlias, no other analysis is queried to give a more exact result (which was the intention of returning PartialAlias instead of MayAlias). For instance, ScopedAA could return a more accurate result. The PartialAlias hack was introduced in r131781 (and re-applied in r132632 after some reverts) to fix llvm.org/PR9971 where TBAA returns a wrong NoAlias result due to a union. A test case for the malloc case mentioned in the comment was not provided and I don't think it is affected since it returns an omnipotent char anyway. Since r303851 (https://reviews.llvm.org/D33328) clang does emit specific TBAA for unions anymore (but "omnipotent char" instead). Hence, the PartialAlias workaround is not required anymore. This patch passes the test-suite and check-llvm/check-clang of a self-hoisted build on x64. Reviewed By: hfinkel Differential Revision: https://reviews.llvm.org/D34318 llvm-svn: 305938
* [SCEV] Make MulOpsInlineThreshold lower to avoid excessive compilation timeMax Kazantsev2017-06-211-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | MulOpsInlineThreshold option of SCEV is defaulted to 1000, which is inadequately high. When constructing SCEVs of expressions like: x1 = a * a x2 = x1 * x1 x3 = x2 * x2 ... We actually have huge SCEVs with max allowed amount of operands inlined. Such expressions are easy to get from unrolling of loops looking like x = a for (i = 0; i < n; i++) x = x * x Or more tricky cases where big powers are involved. If some non-linear analysis tries to work with a SCEV that has 1000 operands, it may lead to excessively long compilation. The attached test does not pass within 1 minute with default threshold. This patch decreases its default value to 32, which looks much more reasonable if we use analyzes with complexity O(N^2) or O(N^3) working with SCEV. Differential Revision: https://reviews.llvm.org/D34397 llvm-svn: 305882
* [SCEV][NFC] Fix a misleading description of AddOpsInlineThresholdMax Kazantsev2017-06-201-1/+1
| | | | | | | | | The description of this option was copy-pasted from another one and does not correspond to reality. Differential Revision: https://reviews.llvm.org/D34390 llvm-svn: 305782
* [BDCE] Add comments. NFCXin Tong2017-06-191-0/+2
| | | | llvm-svn: 305739
* [SCEV] Teach SCEVExpander to expand BinPowMax Kazantsev2017-06-191-5/+43
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Current implementation of SCEVExpander demonstrates a very naive behavior when it deals with power calculation. For example, a SCEV for x^8 looks like (x * x * x * x * x * x * x * x) If we try to expand it, it generates a very straightforward sequence of muls, like: x2 = mul x, x x3 = mul x2, x x4 = mul x3, x ... x8 = mul x7, x This is a non-efficient way of doing that. A better way is to generate a sequence of binary power calculation. In this case the expanded calculation will look like: x2 = mul x, x x4 = mul x2, x2 x8 = mul x4, x4 In some cases the code size reduction for such SCEVs is dramatic. If we had a loop: x = a; for (int i = 0; i < 3; i++) x = x * x; And this loop have been fully unrolled, we have something like: x = a; x2 = x * x; x4 = x2 * x2; x8 = x4 * x4; The SCEV for x8 is the same as in example above, and if we for some reason want to expand it, we will generate naively 7 multiplications instead of 3. The BinPow expansion algorithm here allows to keep code size reasonable. This patch teaches SCEV Expander to generate a sequence of BinPow multiplications if we have repeating arguments in SCEVMulExpressions. Differential Revision: https://reviews.llvm.org/D34025 llvm-svn: 305663
* DivergencyAnalysis patch for reviewAlexander Timofeev2017-06-152-1/+5
| | | | llvm-svn: 305494
* [BasicAA] Don't call isKnownNonEqual if we might be have gone through a PHINode.Craig Topper2017-06-151-4/+18
| | | | | | | | | | | | This is a fix for the test case in PR32314. Basic Alias Analysis can ask if two nodes are known non-equal after looking through a phi node to find a GEP. isAddOfNonZero saw an add of a constant from the same phi and said that its output couldn't be equal. But Basic Alias Analysis was really asking about the value from the previous loop iteration. This patch at least makes that case not happen anymore, I'm not sure if there were still other ways this can fail. As was discussed in the bug, it looks like fixing BasicAA would be difficult so this patch seemed like a possible workaround Differential Revision: https://reviews.llvm.org/D33136 llvm-svn: 305481
* [ScalarEvolution] Apply Depth limit to getMulExprMax Kazantsev2017-06-151-53/+76
| | | | | | | | | | | | | | | | | | | | | This is a fix for PR33292 that shows a case of extremely long compilation of a single .c file with clang, with most time spent within SCEV. We have a mechanism of limiting recursion depth for getAddExpr to avoid long analysis in SCEV. However, there are calls from getAddExpr to getMulExpr and back that do not propagate the info about depth. As result of this, a chain getAddExpr -> ... .> getAddExpr -> getMulExpr -> getAddExpr -> ... -> getAddExpr can be extremely long, with every segment of getAddExpr's being up to max depth long. This leads either to long compilation or crash by stack overflow. We face this situation while analyzing big SCEVs in the test of PR33292. This patch applies the same limit on max expression depth for getAddExpr and getMulExpr. Differential Revision: https://reviews.llvm.org/D33984 llvm-svn: 305463
* [ValueTracking] Correct early out in computeKnownBitsFromOperator to work ↵Craig Topper2017-06-141-1/+2
| | | | | | | | | | | | with non power of 2 bit widths There's an early out that's trying to detect when we don't know any bits that make up the legal range of a shift. The code subtracts one from BitWidth which creates a mask in the lower bits for power of 2 bit widths. This is then ANDed with the known bits to see if any of those bits are known. If the bit width isn't a power of 2 this creates a non-sensical mask. This patch corrects this by rounding up to a power of 2 before doing the subtract and mask. Differential Revision: https://reviews.llvm.org/D34165 llvm-svn: 305400
* Strip UTF8 BOM that got added for some reason in rL305163Simon Pilgrim2017-06-131-1/+1
| | | | llvm-svn: 305282
* fix typos/formatting; NFCSanjay Patel2017-06-121-1/+1
| | | | llvm-svn: 305243
* Address http://bugs.llvm.org/pr32207 by making BannerPrinted local to ↵Yaron Keren2017-06-121-4/+4
| | | | | | | | | | runOnSCC and skipping banner for function declarations. Reviewed By: Mehdi AMINI Differential Revision: https://reviews.llvm.org/D34086 llvm-svn: 305179
* Fix unused variable warning on non-debug EXPENSIVE_CHECKS buildsSimon Pilgrim2017-06-111-1/+2
| | | | llvm-svn: 305163
OpenPOWER on IntegriCloud