summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [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
* [MemorySSA] preservesAll() implies preserves<MemorySSA>(). NFCI.Davide Italiano2017-06-111-1/+0
| | | | llvm-svn: 305160
* [InstSimplify] Don't constant fold or DCE calls that are marked nobuiltinAndrew Kaylor2017-06-094-19/+31
| | | | | | Differential Revision: https://reviews.llvm.org/D33737 llvm-svn: 305132
* [LVI] Fix spelling error in comment. NFCCraig Topper2017-06-091-1/+1
| | | | llvm-svn: 305115
* [LVI] Const correct and rename the LVILatticeVal parameter to ↵Craig Topper2017-06-091-9/+8
| | | | | | | | getPredicateResult. NFC Previously it was non-const reference named Result which would tend to make someone think that it was an outparam when really its an input. llvm-svn: 305114
* [LazyValueInfo] Don't run the more complex predicate handling code for EQ ↵Craig Topper2017-06-091-8/+8
| | | | | | | | | | | | | | | | | | | and NE in getPredicateResult Summary: Unless I'm mistaken, the special handling for EQ/NE should cover everything and there is no reason to fallthrough to the more complex code. For that matter I'm not sure there's any reason to special case EQ/NE other than avoiding creating temporary ConstantRanges. This patch moves the complex code into an else so we only do it when we are handling a predicate other than EQ/NE. Reviewers: anna, reames, resistor, Farhana Reviewed By: anna Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34000 llvm-svn: 305086
* [ValueTracking] fix typo; NFCSanjay Patel2017-06-091-1/+1
| | | | llvm-svn: 305080
* Write summaries for merged modules when splitting modules for ThinLTO.Peter Collingbourne2017-06-081-0/+10
| | | | | | | | | This is to prepare to allow for dead stripping of globals in the merged modules. Differential Revision: https://reviews.llvm.org/D33921 llvm-svn: 305027
* [LazyValueInfo] Make LVILatticeVal intersect method take arguments by ↵Craig Topper2017-06-081-1/+1
| | | | | | reference so we don't copy ConstantRanges unless we need to. llvm-svn: 304990
* [BPI] Don't assume that strcmp returning >0 is more likely than <0John Brawn2017-06-082-7/+48
| | | | | | | | | | | | | | | | | | | | The zero heuristic assumes that integers are more likely positive than negative, but this also has the effect of assuming that strcmp return values are more likely positive than negative. Given that for nonzero strcmp return values it's the ordering of arguments that determines the sign of the result there's no reason to assume that's true. Fix this by inspecting the LHS of the compare and using TargetLibraryInfo to decide if it's strcmp-like, and if so only assume that nonzero is more likely than zero i.e. strings are more often different than the same. This causes a slight code generation change in the spec2006 benchmark 403.gcc, but with no noticeable performance impact. The intent of this patch is to allow better optimisation of dhrystone on Cortex-M cpus, but currently it won't as there are also some changes that need to be made to if-conversion. Differential Revision: https://reviews.llvm.org/D33934 llvm-svn: 304970
* GlobalsModRef: Ensure optnone+readonly/readnone attributes are respectedDavid Blaikie2017-06-071-8/+5
| | | | llvm-svn: 304945
* [mssa] Fix case when there is no definition in a block prior to an inserted use.Alina Sbirlea2017-06-071-11/+6
| | | | | | | | | | | | | | | Summary: Check that the first access before one being tested is valid. Before this patch, if there was no definition prior to the Use being tested, the first time Iter was deferenced, it hit the sentinel. Reviewers: dberlin, gbiv Subscribers: sanjoy, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D33950 llvm-svn: 304926
* [InstCombine][InstSimplify] Use APInt::isNullValue/isOneValue to reduce ↵Craig Topper2017-06-071-6/+6
| | | | | | | | compiled code for comparing APInts with 0 and 1. NFC These methods are specifically optimized to only counting leading zeros without an additional uint64_t compare. llvm-svn: 304876
* Update libdeps to add BinaryFormat, introduced in r304864.NAKAMURA Takumi2017-06-071-1/+1
| | | | llvm-svn: 304869
* Reorder and reformat.NAKAMURA Takumi2017-06-071-1/+1
| | | | llvm-svn: 304868
* [LazyValueInfo] Remove redundant calls to ConstantRange::contains. The same ↵Craig Topper2017-06-071-2/+2
| | | | | | exact call was made in the if above and we already know it returned true. NFC llvm-svn: 304857
* [CFLAA] Remove unused include. NFCI.Davide Italiano2017-06-061-1/+0
| | | | llvm-svn: 304842
* GlobalsModRef+OptNone: Don't prove readnone/other properties from an optnone ↵David Blaikie2017-06-061-3/+14
| | | | | | | | | | | | | | | | | | | | function Seems like at least one reasonable interpretation of optnone is that the optimizer never "looks inside" a function. This fix is consistent with that interpretation. Specifically this came up in the situation: f3 calls f2 calls f1 f2 is always_inline f1 is optnone The application of readnone to f1 (& thus to f2) caused the inliner to kill the call to f2 as being trivially dead (without even checking the cost function, as it happens - not sure if that's also a bug). llvm-svn: 304833
* [LVI Printer] Rely on the LVI analysis functions rather than the LVI cacheAnna Thomas2017-06-061-64/+89
| | | | | | | | | | | | | | | | | | | | | | | Summary: LVIPrinter pass was previously relying on the LVICache. We now directly call the the LVI functions which solves the value if the LVI information is not already available in the cache. This has 2 benefits over the printing of LVI cache: 1. higher coverage (i.e. catches errors) in LVI code when cache value is invalidated. 2. relies on the core functions, and not dependent on the LVI cache (which may be scrapped at some point). It would still catch any cache invalidation errors, since we first go through the cache. Reviewers: reames, dberlin, sanjoy Reviewed by: reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32135 llvm-svn: 304819
* [Atomics][LoopIdiom] Recognize unordered atomic memcpyAnna Thomas2017-06-061-0/+4
| | | | | | | | | | | | | | | | | | | | | | Summary: Expanding the loop idiom test for memcpy to also recognize unordered atomic memcpy. The only difference for recognizing an unordered atomic memcpy and instead of a normal memcpy is that the loads and/or stores involved are unordered atomic operations. Background: http://lists.llvm.org/pipermail/llvm-dev/2017-May/112779.html Patch by Daniel Neilson! Reviewers: reames, anna, skatkov Reviewed By: reames, anna Subscribers: llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D33243 llvm-svn: 304806
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-0620-29/+27
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
OpenPOWER on IntegriCloud