summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [AliasSetTracker] Degrade AliasSetTracker when may-alias sets get too large.Michael Kuperstein2016-08-191-9/+116
| | | | | | | | | | | | | | | | | | Repeated inserts into AliasSetTracker have quadratic behavior - inserting a pointer into AST is linear, since it requires walking over all "may" alias sets and running an alias check vs. every pointer in the set. We can avoid this by tracking the total number of pointers in "may" sets, and when that number exceeds a threshold, declare the tracker "saturated". This lumps all pointers into a single "may" set that aliases every other pointer. (This is a stop-gap solution until we migrate to MemorySSA) This fixes PR28832. Differential Revision: https://reviews.llvm.org/D23432 llvm-svn: 279274
* [PM] Rework the new PM support for building the ModuleSummaryIndex toChandler Carruth2016-08-191-33/+30
| | | | | | | | | | | | | | | | | | | | | | directly produce the index as the value type result. This requires making the index movable which is straightforward. It greatly simplifies things by allowing us to completely avoid the builder API and the layers of abstraction inherent there. Instead both pass managers can directly construct these when run by value. They still won't be constructed truly eagerly thanks to the optional in the legacy PM. The code that directly builds the index can also just share a direct function. A notable change here is that the result type of the analysis for the new PM is no longer a reference type. This was really problematic when making changes to how we handle result types to make our interface requirements *much* more strict and precise. But I think this is an overall improvement. Differential Revision: https://reviews.llvm.org/D23701 llvm-svn: 279216
* [Assumptions] Make collecting ephemeral values not quadratic in theChandler Carruth2016-08-181-23/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | number of assume intrinsics. The classical way to have a cache-friendly vector style container when we need queue semantics for BFS instead of stack semantics for DFS is to use an ever-growing vector and an index. Erasing from the front requires O(size) work, and unless we expect the worklist to grow *very* large, its probably cheaper to just grow and race down the list. But that makes it more bad that we're putting the assume intrinsics in this at all. We end up looking at the (by definition empty) use list to see if they're ephemeral (when we've already put them in that set), etc. Instead, directly populate the worklist with the operands when we mark the assume intrinsics as ephemeral. Also, test the visited set *before* putting things into the worklist so we don't accumulate the same value in the list 100s of times. It would be nice to use a set-vector for this but I think its useful to test the set earlier to avoid repeatedly querying whether the same instruction is safe to speculate. Hopefully with these changes the number of values pushed onto the worklist is smaller, and we avoid quadratic work by letting it grow as necessary. Differential Revision: https://reviews.llvm.org/D23396 llvm-svn: 279099
* SCEV: Don't assert about non-SCEV-able value in isSCEVExprNeverPoison() ↵Hans Wennborg2016-08-171-0/+4
| | | | | | | | (PR28932) Differential Revision: https://reviews.llvm.org/D23594 llvm-svn: 278999
* Replace a few more "fall through" comments with LLVM_FALLTHROUGHJustin Bogner2016-08-175-9/+13
| | | | | | Follow up to r278902. I had missed "fall through", with a space. llvm-svn: 278970
* [GraphWriter] Change GraphWriter to use NodeRef in GraphTraitsTim Shen2016-08-171-0/+1
| | | | | | | | | | | | | | | Summary: This is part of the "NodeType* -> NodeRef" migration. Notice that since GraphWriter prints object address as identity, I added a static_assert on NodeRef to be a pointer type. Reviewers: dblaikie Subscribers: llvm-commits, MatzeB Differential Revision: https://reviews.llvm.org/D23580 llvm-svn: 278966
* [LoopStrenghtReduce] Refactoring and addition of a new target cost function.Jonas Paulsson2016-08-171-0/+5
| | | | | | | | | | | | | | | | | | | | | | | Refactored so that a LSRUse owns its fixups, as oppsed to letting the LSRInstance own them. This makes it easier to rate formulas for LSRUses, since the fixups are available directly. The Offsets vector has been removed since it was no longer necessary. New target hook isFoldableMemAccessOffset(), which is used during formula rating. For SystemZ, this is useful to express that loads and stores with float or vector types with a big/negative offset should be avoided in loops. Without this, LSR will generate a lot of negative offsets that would require extra instructions for loading the address. Updated tests: test/CodeGen/SystemZ/loop-01.ll Reviewed by: Quentin Colombet and Ulrich Weigand. https://reviews.llvm.org/D19152 llvm-svn: 278927
* Replace "fallthrough" comments with LLVM_FALLTHROUGHJustin Bogner2016-08-172-9/+9
| | | | | | | This is a mechanical change of comments in switches like fallthrough, fall-through, or fall-thru to use the LLVM_FALLTHROUGH macro instead. llvm-svn: 278902
* ObjCARC: Don't increment or dereference end() when scanning argsDuncan P. N. Exon Smith2016-08-171-33/+37
| | | | | | | | | When there's only one argument and it doesn't match one of the known functions, return ARCInstKind::CallOrUser rather than falling through to the two argument case. The old behaviour both incremented past and dereferenced end(). llvm-svn: 278881
* Revert "Enhance SCEV to compute the trip count for some loops with unknown ↵Reid Kleckner2016-08-161-77/+4
| | | | | | | | stride." This reverts commit r278731. It caused http://crbug.com/638314 llvm-svn: 278853
* [InstSimplify] Fold gep (gep V, C), (xor V, -1) to C-1David Majnemer2016-08-161-1/+7
| | | | llvm-svn: 278779
* Revert "[ValueTracking] Improve ValueTracking on left shift with nsw flag"Sanjoy Das2016-08-151-13/+4
| | | | | | This reverts commit r278172. It causes PR28946. llvm-svn: 278740
* Enhance SCEV to compute the trip count for some loops with unknown stride.David L Kreitzer2016-08-151-4/+77
| | | | | | | | Patch by Pankaj Chawla Differential Revision: https://reviews.llvm.org/D22377 llvm-svn: 278731
* [ScopedNoAliasAA] collectMDInDomain should be a free functionDavid Majnemer2016-08-151-3/+2
| | | | | | | collectMDInDomain doesn't use any class members, making it a free function is not a functional change. llvm-svn: 278651
* [ScopedNoAliasAA] Only collect noalias nodes if we have alias.scope nodesDavid Majnemer2016-08-151-2/+4
| | | | | | No functional change is intended. llvm-svn: 278646
* [ScopedNoAliasAA] Replace !ScopeNodes.size() with ScopeNodes.empty()David Majnemer2016-08-151-1/+1
| | | | | | No functional change is intended. llvm-svn: 278645
* Revert "[ScopedNoAliasAA] Remove an unneccesary set"David Majnemer2016-08-151-13/+20
| | | | | | | This reverts commit r278641. I'm not sure why but this has upset the multistage builders... llvm-svn: 278644
* [ScopedNoAliasAA] Remove an unneccesary setDavid Majnemer2016-08-151-20/+13
| | | | | | | | | | | We are trying to prove that one group of operands is a subset of another. We did this by populating two Sets and determining that every element within one was inside the other. However, this is unnecessary. We can simply construct a single set and test if each operand is within it. llvm-svn: 278641
* Constify ValueTracking. NFC.Pete Cooper2016-08-131-99/+125
| | | | | | | Almost all of the method here are only analysing Value's as opposed to mutating them. Mark all of the easy ones as const. llvm-svn: 278585
* Fix some Clang-tidy modernize-use-using and Include What You Use warnings.Eugene Zelenko2016-08-131-5/+26
| | | | | | Differential revision: https://reviews.llvm.org/D23478 llvm-svn: 278583
* [BasicAA] Avoid calling GetUnderlyingObject, when the result of a previous ↵Ehsan Amiri2016-08-121-13/+25
| | | | | | | | | | call can be reused. Recursive calls to aliasCheck from alias[GEP|Select|PHI] may result in a second call to GetUnderlyingObject for a Value, whose underlying object is already computed. This patch ensures that in this situations, the underlying object is not computed again, and the result of the previous call is resued. https://reviews.llvm.org/D22305 llvm-svn: 278519
* [LVI] Take guards into accountArtur Pilipenko2016-08-121-11/+29
| | | | | | | | | | Teach LVI to gather control dependant constraints from guards. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D23358 llvm-svn: 278518
* [LVI] Fix potential memory corruption in getValueFromConditionArtur Pilipenko2016-08-121-2/+4
| | | | | | Rewrite Visited[Cond] = getValueFromConditionImpl(..., Visited) statement which can lead to a memory corruption since getValueFromConditionImpl changes Visited map and invalidates the iterators. llvm-svn: 278514
* [PM] Port ModuleSummaryIndex analysis to new pass managerTeresa Johnson2016-08-121-0/+13
| | | | | | | | | | | | | | | | | | | Summary: Port the ModuleSummaryAnalysisWrapperPass to the new pass manager. Use it in the ported BitcodeWriterPass (similar to how we use the legacy ModuleSummaryAnalysisWrapperPass in the legacy WriteBitcodePass). Also, pass the -module-summary opt flag through to the new pass manager pipeline and through to the bitcode writer pass, and add a test that uses it. Reviewers: mehdi_amini Subscribers: llvm-commits, mehdi_amini Differential Revision: https://reviews.llvm.org/D23439 llvm-svn: 278508
* [LVI] Take range metadata into account while calculating icmp condition ↵Artur Pilipenko2016-08-121-0/+3
| | | | | | | | | | | | | | | | | constraints Take range metadata into account for conditions like this: %length = load i32, i32* %length_ptr, !range !{i32 0, i32 2147483647} %cmp = icmp ult i32 %a, %length This is a common pattern for range checks where the length of the array is dynamically loaded. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D23267 llvm-svn: 278496
* [LVI] Handle any predicate in comparisons like icmp <pred> (add Val, ↵Artur Pilipenko2016-08-121-2/+2
| | | | | | | | | | | | | | | | | Offset), ... Currently LVI can only gather value constraints from comparisons like: * icmp <pred> Val, ... * icmp ult (add Val, Offset), ... In fact we can handle any predicate in latter comparisons. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D23357 llvm-svn: 278493
* Use the range variant of transform instead of unpacking begin/endDavid Majnemer2016-08-121-4/+3
| | | | | | No functionality change is intended. llvm-svn: 278476
* Use the range variant of remove_if instead of unpacking begin/endDavid Majnemer2016-08-121-4/+3
| | | | | | No functionality change is intended. llvm-svn: 278475
* Use the range variant of find/find_if instead of unpacking begin/endDavid Majnemer2016-08-121-20/+17
| | | | | | | | | If the result of the find is only used to compare against end(), just use is_contained instead. No functionality change is intended. llvm-svn: 278469
* Refactor isValidAssumeForContext to reduce duplication and indentation. NFC.Pete Cooper2016-08-121-27/+21
| | | | | | | This method had some duplicate code when we did or did not have a dom tree. Refactor it to remove the duplication, but also clean up the control flow to have less duplication. llvm-svn: 278450
* Add comment /NFCXinliang David Li2016-08-111-1/+2
| | | | llvm-svn: 278438
* Remove unnecessary extra version of isValidAssumeForContext. NFC.Pete Cooper2016-08-111-11/+5
| | | | | | | | | | | There were 2 versions of this method. A public one which takes a const Instruction* and a private implementation which takes a mutable Value* and casts to an Instruction*. There was no need for the 2 versions as all callers pass a const Instruction* and there was no need for a mutable pointer as we only do analysis here. llvm-svn: 278434
* Use the range variant of find instead of unpacking begin/endDavid Majnemer2016-08-114-13/+8
| | | | | | | | | If the result of the find is only used to compare against end(), just use is_contained instead. No functionality change is intended. llvm-svn: 278433
* Use range algorithms instead of unpacking begin/endDavid Majnemer2016-08-118-30/+23
| | | | | | No functionality change is intended. llvm-svn: 278417
* [SCEV] Update interface to handle SCEVExpander insert point motion.Geoff Berry2016-08-111-2/+1
| | | | | | | | | | | | | | | | | | | | Summary: This is an extension of the fix in r271424. That fix dealt with builder insert points being moved by SCEV expansion, but only for the lifetime of the expand call. This change modifies the interface so that LSR can safely call expand multiple times at the same insert point and do the right thing if one of the expansions decides to move the original insert point. This is a fix for PR28719. Reviewers: sanjoy Subscribers: llvm-commits, mcrosier, mzolotukhin Differential Revision: https://reviews.llvm.org/D23342 llvm-svn: 278413
* [AliasSetTracker] Delete dead codeMichael Kuperstein2016-08-111-129/+0
| | | | | | | | Deletes unused remove() and containsPointer() interfaces. NFC. Differential Revision: https://reviews.llvm.org/D23360 llvm-svn: 278365
* Make more fields of InlineParams Optional.Easwaran Raman2016-08-111-4/+8
| | | | | | Differential revision: https://reviews.llvm.org/D23386 llvm-svn: 278312
* Changed sign of LastCallToStaticBounsPiotr Padlewski2016-08-101-1/+1
| | | | | | | | | | | | | | | | | Summary: I think it is much better this way. When I firstly saw line: Cost += InlineConstants::LastCallToStaticBonus; I though that this is a bug, because everywhere where the cost is being reduced it is usuing -=. Reviewers: eraman, tejohnson, mehdi_amini Subscribers: llvm-commits, mehdi_amini Differential Revision: https://reviews.llvm.org/D23222 llvm-svn: 278290
* [ValueTracking] An improvement to IR ValueTracking on Non-negative IntegersAndrew Kaylor2016-08-101-1/+37
| | | | | | | | Patch by Li Huang Differential Revision: https://reviews.llvm.org/D18777 llvm-svn: 278267
* [LVI] Handle conditions in the form of (cond1 && cond2)Artur Pilipenko2016-08-101-8/+42
| | | | | | | | | | Teach LVI how to gather information from conditions in the form of (cond1 && cond2). Our out-of-tree front-end emits range checks in this form. Reviewed By: sanjoy Differential Revision: http://reviews.llvm.org/D23200 llvm-svn: 278231
* [LVI] NFC. Make getValueFromCondition return LVILatticeValue instead of ↵Artur Pilipenko2016-08-101-25/+16
| | | | | | | | | | changing reference argument Instead of returning bool and setting LVILatticeValue reference argument return LVILattice value. Use overdefined value to denote the case when we didn't gather any information from the condition. This change was separated from the review "[LVI] Handle conditions in the form of (cond1 && cond2)" (https://reviews.llvm.org/D23200#inline-199531). Once getValueFromCondition returns LVILatticeValue we can cache the result in Visited map. llvm-svn: 278224
* [LVI] Relax the assertion about LVILatticeVal type in getConstantRangeArtur Pilipenko2016-08-101-1/+4
| | | | | | | | | | | | | | | | | | | | The problem was triggered by my recent change in CVP (D23059). Current code expected that integer constants are represented by constantrange LVILatticeVal and never represented as LVILatticeVal with constant tag. That is true for ConstantInt constants, although ConstantExpr integer type constants are legally represented as constant LVILatticeVal. This code fails with CVP change in: @b = global i32 0, align 4 define void @test6(i32 %a) { bb: %add = add i32 %a, ptrtoint (i32* @b to i32) ret void } Currently getConstantRange code is not executed by any of the upstream passes. I'm going to add a test case to test/Transforms/CorrelatedValuePropagation/add.ll once I resubmit the CVP change. Reviewed By: sanjoy Differential Revision: http://reviews.llvm.org/D23194 llvm-svn: 278217
* Do not directly use inline threshold cl options in cost analysis.Easwaran Raman2016-08-101-57/+98
| | | | | | | | This adds an InlineParams struct which is populated from the command line options by getInlineParams and passed to getInlineCost for the call analyzer to use. Differential revision: https://reviews.llvm.org/D22120 llvm-svn: 278189
* [Inliner,OptDiag] Add hotness attribute to opt diagnosticsAdam Nemet2016-08-101-0/+24
| | | | | | | | | | | | | | | | | | | | Summary: The inliner not being a function pass requires the work-around of generating the OptimizationRemarkEmitter and in turn BFI on demand. This will go away after the new PM is ready. BFI is only computed inside ORE if the user has requested hotness information for optimization diagnostitics (-pass-remark-with-hotness at the 'opt' level). Thus there is no additional overhead without the flag. Reviewers: hfinkel, davidxl, eraman Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D22694 llvm-svn: 278185
* [ValueTracking] Improve ValueTracking on left shift with nsw flagAndrew Kaylor2016-08-091-4/+13
| | | | | | | | Patch by Li Huang Differential Revison: https://reviews.llvm.org/D23296 llvm-svn: 278172
* Fix the runtime error caused by "Use ValueOffsetPair to enhance value reuse ↵Wei Mi2016-08-091-9/+20
| | | | | | | | | | | | | | during SCEV expansion". The patch is to fix the bug in PR28705. It was caused by setting wrong return value for SCEVExpander::findExistingExpansion. The return values of findExistingExpansion have different meanings when the function is used in different ways so it is easy to make mistake. The fix creates two new interfaces to replace SCEVExpander::findExistingExpansion, and specifies where each interface is expected to be used. Differential Revision: https://reviews.llvm.org/D22942 llvm-svn: 278161
* Recommit "Use ValueOffsetPair to enhance value reuse during SCEV expansion".Wei Mi2016-08-092-33/+79
| | | | | | | | | | | | | | | | | | | | | | | | | The fix for PR28705 will be committed consecutively. In D12090, the ExprValueMap was added to reuse existing value during SCEV expansion. However, const folding and sext/zext distribution can make the reuse still difficult. A simplified case is: suppose we know S1 expands to V1 in ExprValueMap, and S1 = S2 + C_a S3 = S2 + C_b where C_a and C_b are different SCEVConstants. Then we'd like to expand S3 as V1 - C_a + C_b instead of expanding S2 literally. It is helpful when S2 is a complex SCEV expr and S2 has no entry in ExprValueMap, which is usually caused by the fact that S3 is generated from S1 after const folding. In order to do that, we represent ExprValueMap as a mapping from SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and S2->{V1, C_a} into the ExprValueMap when we create SCEV for V1. When S3 is expanded, it will first expand S2 to V1 - C_a because of S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b. Differential Revision: https://reviews.llvm.org/D21313 llvm-svn: 278160
* [AliasAnalysis] Treat invariant.start as read-memoryAnna Thomas2016-08-091-0/+26
| | | | | | | | | | | | | | | | | Summary: We teach alias analysis that invariant.start is readonly. This helps with GVN and memcopy optimizations that currently treat. invariant.start as a clobber. We need to treat this as readonly, so that DSE does not incorrectly remove stores prior to the invariant.start Reviewers: sanjoy, reames, majnemer, dberlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23214 llvm-svn: 278138
* [LVI] Make LVI smarter about comparisons with non-constantsArtur Pilipenko2016-08-091-19/+36
| | | | | | | | | | Make LVI smarter about comparisons with a non-constant. For example, a s< b constraints a to be in [INT_MIN, INT_MAX) range. This is a part of https://llvm.org/bugs/show_bug.cgi?id=28620 fix. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D23205 llvm-svn: 278122
* Revert 278107 which causes buildbot failures and in addition has wrong ↵Artur Pilipenko2016-08-091-33/+19
| | | | | | commit message llvm-svn: 278109
OpenPOWER on IntegriCloud