summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [LazyValueInfo] Stop inserting overdefined values into ValueCache toAkira Hatanaka2015-12-111-18/+48
| | | | | | | | | | | | | | | | | | reduce memory usage. Previously, LazyValueInfoCache inserted overdefined lattice values into both ValueCache and OverDefinedCache. This wasn't necessary and was causing LazyValueInfo to use an excessive amount of memory in some cases. This patch changes LazyValueInfoCache to insert overdefined values only into OverDefinedCache. The memory usage decreases by 70 to 75% when one of the files in llvm is compiled. rdar://problem/11388615 Differential revision: http://reviews.llvm.org/D15391 llvm-svn: 255320
* Re-commit r255115, with the PredicatedScalarEvolution class moved toSilviu Baranga2015-12-092-44/+88
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ScalarEvolution.h, in order to avoid cyclic dependencies between the Transform and Analysis modules: [LV][LAA] Add a layer over SCEV to apply run-time checked knowledge on SCEV expressions Summary: This change creates a layer over ScalarEvolution for LAA and LV, and centralizes the usage of SCEV predicates. The SCEVPredicatedLayer takes the statically deduced knowledge by ScalarEvolution and applies the knowledge from the SCEV predicates. The end goal is that both LAA and LV should use this interface everywhere. This also solves a problem involving the result of SCEV expression rewritting when the predicate changes. Suppose we have the expression (sext {a,+,b}) and two predicates P1: {a,+,b} has nsw P2: b = 1. Applying P1 and then P2 gives us {a,+,1}, while applying P2 and the P1 gives us sext({a,+,1}) (the AddRec expression was changed by P2 so P1 no longer applies). The SCEVPredicatedLayer maintains the order of transformations by feeding back the results of previous transformations into new transformations, and therefore avoiding this issue. The SCEVPredicatedLayer maintains a cache to remember the results of previous SCEV rewritting results. This also has the benefit of reducing the overall number of expression rewrites. Reviewers: mzolotukhin, anemet Subscribers: jmolloy, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D14296 llvm-svn: 255122
* Revert r255115 until we figure out how to fix the bot failures.Silviu Baranga2015-12-091-44/+43
| | | | llvm-svn: 255117
* [LV][LAA] Add a layer over SCEV to apply run-time checked knowledge on SCEV ↵Silviu Baranga2015-12-091-43/+44
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | expressions Summary: This change creates a layer over ScalarEvolution for LAA and LV, and centralizes the usage of SCEV predicates. The SCEVPredicatedLayer takes the statically deduced knowledge by ScalarEvolution and applies the knowledge from the SCEV predicates. The end goal is that both LAA and LV should use this interface everywhere. This also solves a problem involving the result of SCEV expression rewritting when the predicate changes. Suppose we have the expression (sext {a,+,b}) and two predicates P1: {a,+,b} has nsw P2: b = 1. Applying P1 and then P2 gives us {a,+,1}, while applying P2 and the P1 gives us sext({a,+,1}) (the AddRec expression was changed by P2 so P1 no longer applies). The SCEVPredicatedLayer maintains the order of transformations by feeding back the results of previous transformations into new transformations, and therefore avoiding this issue. The SCEVPredicatedLayer maintains a cache to remember the results of previous SCEV rewritting results. This also has the benefit of reducing the overall number of expression rewrites. Reviewers: mzolotukhin, anemet Subscribers: jmolloy, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D14296 llvm-svn: 255115
* [SCEV] Use for-each; NFCSanjoy Das2015-12-081-19/+13
| | | | llvm-svn: 255069
* [SCEV] Move some struct declarations inside functions; NFCSanjoy Das2015-12-081-63/+54
| | | | | | | | | Reduces the scope over which the struct is visible, making its usages obvious. I did not move structs in cases where this wasn't a clear win (the struct is too large, or is grouped in some other interesting way). llvm-svn: 255003
* [SCEV] Fix indentation; NFCSanjoy Das2015-12-081-150/+150
| | | | llvm-svn: 255002
* [IndVars] Have getInsertPointForUses preserve LCSSASanjoy Das2015-12-081-0/+9
| | | | | | | | | | | | | | | Summary: Also add a stricter post-condition for IndVarSimplify. Fixes PR25578. Test case by Michael Zolotukhin. Reviewers: hfinkel, atrick, mzolotukhin Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D15059 llvm-svn: 254977
* [SCEVExpander] Have hoistIVInc preserve LCSSASanjoy Das2015-12-081-0/+3
| | | | | | | | | | | | | | | | Summary: (Note: the problematic invocation of hoistIVInc that caused PR24804 came from IndVarSimplify, not from SCEVExpander itself) Fixes PR24804. Test case by David Majnemer. Reviewers: hfinkel, majnemer, atrick, mzolotukhin Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D15058 llvm-svn: 254976
* Use updated threshold for indirect call bonusEaswaran Raman2015-12-071-2/+2
| | | | | | | | When considering foo->bar inlining, if there is an indirect call in foo which gets resolved to a direct call (say baz), then we try to inline baz into bar with a threshold T and subtract max(T - Cost(bar->baz), 0) from Cost(foo->bar). This patch uses max(Threshold(bar->baz) - Cost(bar->baz)) instead, where Thresheld(bar->baz) could be different from T due to bonuses or subtractions. Threshold(bar->baz) - Cost(bar->baz) better represents the desirability of inlining baz into bar. Differential Revision: http://reviews.llvm.org/D14309 llvm-svn: 254945
* fix 'the the '; NFCSanjay Patel2015-12-071-1/+1
| | | | llvm-svn: 254928
* [Analysis] Become aware of MSVC's new/delete functionsDavid Majnemer2015-12-031-2/+22
| | | | | | | | The compiler can take advantage of the allocation/deallocation function's properties. We knew how to do this for Itanium but had no support for MSVC-style functions. llvm-svn: 254656
* Test commit.Easwaran Raman2015-12-031-2/+2
| | | | | | Remove blank spaces at the end of comments llvm-svn: 254630
* Fix class SCEVPredicate has virtual functions and accessible non-virtual ↵Andy Gibbs2015-12-031-0/+2
| | | | | | | | | | destructor. It is not enough to simply make the destructor virtual since there is a g++ 4.7 issue (see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=53613) that throws the error "looser throw specifier for ... overridding ~SCEVPredicate() noexcept". llvm-svn: 254592
* Forgot to add this file with r254562.David Majnemer2015-12-021-0/+41
| | | | llvm-svn: 254565
* Move EH-specific helper functions to a more appropriate placeDavid Majnemer2015-12-022-48/+1
| | | | | | No functionality change is intended. llvm-svn: 254562
* Fixed a failure in getSpaltValue()Elena Demikhovsky2015-12-011-1/+2
| | | | llvm-svn: 254409
* Fixed a failure in cost calculation for vector GEPElena Demikhovsky2015-12-011-3/+4
| | | | | | | | | Cost calculation for vector GEP failed with due to invalid cast to GEP index operand. The bug is fixed, added a test. http://reviews.llvm.org/D14976 llvm-svn: 254408
* Introduce a range version of std::find, and use in SCEVSanjoy Das2015-12-011-2/+1
| | | | | | | | | | Reviewers: dblaikie, pcc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D15064 llvm-svn: 254391
* Introduce a range version of std::any_of, and use it in SCEVSanjoy Das2015-12-011-4/+3
| | | | | | | | | | Reviewers: dblaikie, pcc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D15063 llvm-svn: 254390
* Replace all weight-based interfaces in MBB with probability-based ↵Cong Hou2015-12-011-0/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | interfaces, and update all uses of old interfaces. (This is the second attempt to submit this patch. The first caused two assertion failures and was reverted. See https://llvm.org/bugs/show_bug.cgi?id=25687) The patch in http://reviews.llvm.org/D13745 is broken into four parts: 1. New interfaces without functional changes (http://reviews.llvm.org/D13908). 2. Use new interfaces in SelectionDAG, while in other passes treat probabilities as weights (http://reviews.llvm.org/D14361). 3. Use new interfaces in all other passes. 4. Remove old interfaces. This patch is 3+4 above. In this patch, MBB won't provide weight-based interfaces any more, which are totally replaced by probability-based ones. The interface addSuccessor() is redesigned so that the default probability is unknown. We allow unknown probabilities but don't allow using it together with known probabilities in successor list. That is to say, we either have a list of successors with all known probabilities, or all unknown probabilities. In the latter case, we assume each successor has 1/N probability where N is the number of successors. An assertion checks if the user is attempting to add a successor with the disallowed mixed use as stated above. This can help us catch many misuses. All uses of weight-based interfaces are now updated to use probability-based ones. Differential revision: http://reviews.llvm.org/D14973 llvm-svn: 254377
* Revert r254348: "Replace all weight-based interfaces in MBB with ↵Hans Wennborg2015-12-011-6/+0
| | | | | | | | | | probability-based interfaces, and update all uses of old interfaces." and the follow-up r254356: "Fix a bug in MachineBlockPlacement that may cause assertion failure during BranchProbability construction." Asserts were firing in Chromium builds. See PR25687. llvm-svn: 254366
* Replace all weight-based interfaces in MBB with probability-based ↵Cong Hou2015-12-011-0/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | interfaces, and update all uses of old interfaces. The patch in http://reviews.llvm.org/D13745 is broken into four parts: 1. New interfaces without functional changes (http://reviews.llvm.org/D13908). 2. Use new interfaces in SelectionDAG, while in other passes treat probabilities as weights (http://reviews.llvm.org/D14361). 3. Use new interfaces in all other passes. 4. Remove old interfaces. This patch is 3+4 above. In this patch, MBB won't provide weight-based interfaces any more, which are totally replaced by probability-based ones. The interface addSuccessor() is redesigned so that the default probability is unknown. We allow unknown probabilities but don't allow using it together with known probabilities in successor list. That is to say, we either have a list of successors with all known probabilities, or all unknown probabilities. In the latter case, we assume each successor has 1/N probability where N is the number of successors. An assertion checks if the user is attempting to add a successor with the disallowed mixed use as stated above. This can help us catch many misuses. All uses of weight-based interfaces are now updated to use probability-based ones. Differential revision: http://reviews.llvm.org/D14973 llvm-svn: 254348
* [SCEV] Use lambda instead of std::bind; NFCSanjoy Das2015-11-291-2/+3
| | | | | | The lambda is more readable. llvm-svn: 254276
* [SCEV] Use range version of all_of; NFCSanjoy Das2015-11-291-13/+10
| | | | llvm-svn: 254275
* Remove unnecessary intermediate lambda. NFCCraig Topper2015-11-292-5/+2
| | | | llvm-svn: 254243
* [LoopVectorize] Use MapVector rather than DenseMap for MinBWs.Charlie Turner2015-11-261-3/+3
| | | | | | | | | | | | | | | | | The order in which instructions are truncated in truncateToMinimalBitwidths effects code generation. Switch to a map with a determinisic order, since the iteration order over a DenseMap is not defined. This code is not hot, so the difference in container performance isn't interesting. Many thanks to David Blaikie for making me aware of MapVector! Fixes PR25490. Differential Revision: http://reviews.llvm.org/D14981 llvm-svn: 254179
* [Analysis/CallGraph] Switch dump() definitions over to LLVM_DUMP_METHOD.Davide Italiano2015-11-231-6/+3
| | | | llvm-svn: 253842
* [SCEV] Use C++11'ismsSanjoy Das2015-11-221-24/+19
| | | | llvm-svn: 253837
* [SCEVExpander] Use C++isms; NFCSanjoy Das2015-11-211-43/+28
| | | | llvm-svn: 253801
* Add some constantness to GetSuccessorNumber().Rong Xu2015-11-201-2/+3
| | | | llvm-svn: 253733
* ScalarEvolution: do not set nuw when creating exprs of form <expr> + <all-ones>.Peter Collingbourne2015-11-201-4/+2
| | | | | | | | | | | The nuw constraint will not be satisfied unless <expr> == 0. This bug has been around since r102234 (in 2010!), but was uncovered by r251052, which introduced more aggressive optimization of nuw scev expressions. Differential Revision: http://reviews.llvm.org/D14850 llvm-svn: 253627
* Revert "Change memcpy/memset/memmove to have dest and source alignments."Pete Cooper2015-11-191-5/+5
| | | | | | | | | | This reverts commit r253511. This likely broke the bots in http://lab.llvm.org:8011/builders/clang-ppc64-elf-linux2/builds/20202 http://bb.pgr.jp/builders/clang-3stage-i686-linux/builds/3787 llvm-svn: 253543
* Change memcpy/memset/memmove to have dest and source alignments.Pete Cooper2015-11-181-5/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Note, this was reviewed (and more details are in) http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20151109/312083.html These intrinsics currently have an explicit alignment argument which is required to be a constant integer. It represents the alignment of the source and dest, and so must be the minimum of those. This change allows source and dest to each have their own alignments by using the alignment attribute on their arguments. The alignment argument itself is removed. There are a few places in the code for which the code needs to be checked by an expert as to whether using only src/dest alignment is safe. For those places, they currently take the minimum of src/dest alignments which matches the current behaviour. For example, code which used to read: call void @llvm.memcpy.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 500, i32 8, i1 false) will now read: call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 8 %dest, i8* align 8 %src, i32 500, i1 false) For out of tree owners, I was able to strip alignment from calls using sed by replacing: (call.*llvm\.memset.*)i32\ [0-9]*\,\ i1 false\) with: $1i1 false) and similarly for memmove and memcpy. I then added back in alignment to test cases which needed it. A similar commit will be made to clang which actually has many differences in alignment as now IRBuilder can generate different source/dest alignments on calls. In IRBuilder itself, a new argument was added. Instead of calling: CreateMemCpy(Dst, Src, getInt64(Size), DstAlign, /* isVolatile */ false) you now call CreateMemCpy(Dst, Src, getInt64(Size), DstAlign, SrcAlign, /* isVolatile */ false) There is a temporary class (IntegerAlignment) which takes the source alignment and rejects implicit conversion from bool. This is to prevent isVolatile here from passing its default parameter to the source alignment. Note, changes in future can now be made to codegen. I didn't change anything here, but this change should enable better memcpy code sequences. Reviewed by Hal Finkel. llvm-svn: 253511
* Revert "Revert "Strip metadata when speculatively hoisting instructions ↵Igor Laevsky2015-11-181-0/+7
| | | | | | | | (r252604)" Failing clang test is now fixed by the r253458. llvm-svn: 253459
* Default SetVector to use a DenseSet.Rafael Espindola2015-11-181-6/+4
| | | | | | | | | | | | | | | We use to have an odd difference among MapVector and SetVector. The map used a DenseMop, but the set used a SmallSet, which in turn uses a std::set. I have changed SetVector to use a DenseSet. If you were depending on the old behaviour you can pass an explicit set type or use SmallSetVector. The common cases for needing to do it are: * Optimizing for small sets. * Sets for types not supported by DenseSet. llvm-svn: 253439
* Specify explicit storage type for AllocType. NFC.George Burgess IV2015-11-171-1/+1
| | | | llvm-svn: 253366
* [AliasAnalysis] CatchPad and CatchRet can modify escaped memoryDavid Majnemer2015-11-171-0/+26
| | | | | | | CatchPad and CatchRet behave a lot like function calls: they can potentially modify any memory which has been escaped. llvm-svn: 253323
* Fix a typo in BasicAliasAnalysisDavid Majnemer2015-11-171-1/+1
| | | | llvm-svn: 253322
* Move helper classes into anonymous namespaces. NFC.Benjamin Kramer2015-11-161-0/+4
| | | | llvm-svn: 253189
* Revert r252990.Akira Hatanaka2015-11-131-1/+10
| | | | | | Some of the buildbots are still failing. llvm-svn: 252999
* Provide a way to specify inliner's attribute compatibility and merging.Akira Hatanaka2015-11-131-10/+1
| | | | | | | | | | | | | | | | | | This reapplies r252949. I've changed the type of FuncName to be std::string instead of StringRef in emitFnAttrCompatCheck. Original commit message for r252949: Provide a way to specify inliner's attribute compatibility and merging rules using table-gen. NFC. This commit adds new classes CompatRule and MergeRule to Attributes.td, which are used to generate code to check attribute compatibility and merge attributes of the caller and callee. rdar://problem/19836465 llvm-svn: 252990
* Revert r252949.Akira Hatanaka2015-11-121-1/+10
| | | | | | It broke some of the bots including clang-x64-ninja-win7. llvm-svn: 252951
* Provide a way to specify inliner's attribute compatibility and mergingAkira Hatanaka2015-11-121-10/+1
| | | | | | | | | | | | rules using table-gen. NFC. This commit adds new classes CompatRule and MergeRule to Attributes.td, which are used to generate code to check attribute compatibility and merge attributes of the caller and callee. rdar://problem/19836465 llvm-svn: 252949
* Revert r243347 "Add TargetTransformInfo::isZExtFree."Sanjoy Das2015-11-121-4/+0
| | | | | | | | | | | r243347 was intended to support a change to LSR (r243348). That change to LSR has since had to be reverted (r243939) because it was buggy, and now the code added in r243347 is untested and unexercised. Given that, I think it is appropriate to revert r243347 for now, with the intent of adding it back in later if I get around to checking in a fixed version of r243348. llvm-svn: 252948
* [ValueTracking] Remove untested / unreachable code, NFCSanjoy Das2015-11-111-18/+5
| | | | | | | | Right now isTruePredicate is only ever called with Pred == ICMP_SLE or ICMP_ULE, and the ICMP_SLT and ICMP_ULT cases are dead. This change removes the untested dead code so that the function is not misleading. llvm-svn: 252676
* [ValueTracking] Teach isImpliedCondition a new bitwise trickSanjoy Das2015-11-101-0/+30
| | | | | | | | | | | | | | | | | | | Summary: This change teaches isImpliedCondition to prove things like (A | 15) < L ==> (A | 14) < L if the low 4 bits of A are known to be zero. Depends on D14391 Reviewers: majnemer, reames, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14392 llvm-svn: 252673
* [ValueTracking] Use m_APInt instead of m_ConstantInt, NFCSanjoy Das2015-11-101-7/+8
| | | | | | | | This change would add functionality if isImpliedCondition worked on vector types; but since it bail out on vector predicates this change is an NFC. llvm-svn: 252672
* [ValueTracking] Recognize that and(x, add (x, -1)) clears the low bitPhilip Reames2015-11-101-0/+16
| | | | | | | | | | This is a cleaned up version of a patch by John Regehr with permission. Originally found via the souper tool. If we add an odd number to x, then bitwise-and the result with x, we know that the low bit of the result must be zero. Either it was zero in x originally, or the add cleared it in the temporary value. As a result, one of the two values anded together must have the bit cleared. Differential Revision: http://reviews.llvm.org/D14315 llvm-svn: 252629
* Revert "Strip metadata when speculatively hoisting instructions"Renato Golin2015-11-101-7/+0
| | | | | | | This reverts commit r252604, as it broke all ARM and AArch64 buildbots, as well as some x86, et al. llvm-svn: 252623
OpenPOWER on IntegriCloud