summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* Enable constant propagation for more math functionsErik Schnetter2015-08-271-37/+55
| | | | | | | | | | | | Constant propagation for single precision math functions (such as tanf) is already working, but was not enabled. This patch enables these for many single-precision functions, and adds respective test cases. Newly handled functions: acosf asinf atanf atan2f ceilf coshf expf exp2f fabsf floorf fmodf logf log10f powf sinhf tanf tanhf llvm-svn: 246158
* isKnownNonNull needs to consider globals in non-zero address spaces.Pete Cooper2015-08-271-2/+5
| | | | | | | | | Globals in address spaces other than one may have 0 as a valid address, so we should not assume that they can be null. Reviewed by Philip Reames. llvm-svn: 246137
* [WinEH] Require token linkage in EH pad/ret signaturesJoseph Tremoulet2015-08-231-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: WinEHPrepare is going to require that cleanuppad and catchpad produce values of token type which are consumed by any cleanupret or catchret exiting the pad. This change updates the signatures of those operators to require/enforce that the type produced by the pads is token type and that the rets have an appropriate argument. The catchpad argument of a `CatchReturnInst` must be a `CatchPadInst` (and similarly for `CleanupReturnInst`/`CleanupPadInst`). To accommodate that restriction, this change adds a notion of an operator constraint to both LLParser and BitcodeReader, allowing appropriate sentinels to be constructed for forward references and appropriate error messages to be emitted for illegal inputs. Also add a verifier rule (noted in LangRef) that a catchpad with a catchpad predecessor must have no other predecessors; this ensures that WinEHPrepare will see the expected linear relationship between sibling catches on the same try. Lastly, remove some superfluous/vestigial casts from instruction operand setters operating on BasicBlocks. Reviewers: rnk, majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12108 llvm-svn: 245797
* [LAA] Hold bounds via ValueHandles during SCEV expansionAdam Nemet2015-08-211-3/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | SCEV expansion can invalidate previously expanded values. For example in SCEVExpander::ReuseOrCreateCast, if we already have the requested cast value but it's not at the desired location, a new cast is inserted and the old cast will be invalidated. Therefore, when expanding the bounds for the pointers, a later entry can invalidate the IR value for an earlier one. The fix is to store a value handle rather than the value itself. The newly added test has a more detailed description of how the bug triggers. This bug can have a negative but potentially highly variable performance impact in Loop Distribution. Because one of the bound values was invalidated and is an undef expression now, InstCombine is free to transform the array overlap check: Start0 <= End1 && Start1 <= End0 into: Start0 <= End1 So depending on the runtime location of the arrays, we would detect a conflict and fall back on the original loop of the versioned loop. Also tested compile time with SPEC2006 LTO bc files. llvm-svn: 245760
* [LVI] Use a SmallVector instead of SmallPtrSet. NFCBruno Cardoso Lopes2015-08-211-2/+2
| | | | llvm-svn: 245739
* [InstSimplify] add nuw %x, C2 must be at least C2David Majnemer2015-08-201-0/+3
| | | | | | | Use the fact that add nuw always creates a larger bit pattern when trying to simplify comparisons. llvm-svn: 245638
* [ValueTracking] computeOverflowForSignedAdd and isKnownNonNegativeJingyue Wu2015-08-201-0/+69
| | | | | | | | | | | | | | | | Summary: Refactor, NFC Extracts computeOverflowForSignedAdd and isKnownNonNegative from NaryReassociate to ValueTracking in case others need it. Reviewers: reames Subscribers: majnemer, llvm-commits Differential Revision: http://reviews.llvm.org/D11313 llvm-svn: 245591
* [LVI] Avoid iterator invalidation in LazyValueInfoCache::threadEdgeBruno Cardoso Lopes2015-08-201-1/+1
| | | | | | | Do that by copying out the elements to another SmallPtrSet. Follow up from r245309. llvm-svn: 245590
* [ARC] Pull the ObjC ARC components that really serve the role ofChandler Carruth2015-08-205-0/+869
| | | | | | | | | | | | | | analyses into LLVM's Analysis library rather than having them in a Transforms library. This is motivated by the need to have the core AliasAnalysis infrastructure be aware of the ObjCARCAliasAnalysis. However, it also seems like a nice and clean separation. Everything was very easy to move and this doesn't create much clutter in the analysis library IMO. Differential Revision: http://reviews.llvm.org/D12133 llvm-svn: 245541
* [SCEV] Fix GCC 4.8.0 ICE in lambda functionHal Finkel2015-08-191-7/+3
| | | | | | | | | Rewrite some code to not use a lambda function. The non-lambda code is just about as clean as the original, and not any longer. The lambda function causes an internal compiler error in GCC 4.8.0, and it is not worth breaking support for that compiler over this. NFC. llvm-svn: 245466
* [LAA] Comment how memchecks are codegenedAdam Nemet2015-08-191-0/+2
| | | | llvm-svn: 245465
* Fix how DependenceAnalysis calls delinearizationHal Finkel2015-08-191-17/+34
| | | | | | | | | | Fix how DependenceAnalysis calls delinearization, mirroring what is done in Delinearization.cpp (mostly by making sure to call getSCEVAtScope before delinearizing, and by removing the unnecessary 'Pairs == 1' check). Patch by Vaivaswatha Nagaraj! llvm-svn: 245408
* Make ScalarEvolution::isKnownPredicate a little smarterHal Finkel2015-08-191-1/+38
| | | | | | | | | | | | | | | | | | | | | | Here we make ScalarEvolution::isKnownPredicate, indirectly, a little smarter. Given some relational comparison operator OP, and two AddRec SCEVs, {I,+,S} OP {J,+,T}, we can reduce this to the comparison I OP J when S == T, both AddRecs are for the same loop, and both are known not to wrap. As it turns out, because of the way that backedge-guard expressions can be leveraged when computing known predicates, this allows indvars to simplify the if-statement comparison in this loop: void foo (int *a, int *b, int n) { for (int i = 0; i < n; ++i) { if (i > n) a[i] = b[i] + 1; } } which, somewhat surprisingly, we were not previously optimizing away. llvm-svn: 245400
* [BasicAA] Revert r221876 because it can produce incorrect aliasingQuentin Colombet2015-08-191-51/+4
| | | | | | information: see PR24468. llvm-svn: 245394
* [InstSimplify] Remove unused variableDavid Majnemer2015-08-181-6/+2
| | | | | | No functionality change is intended. llvm-svn: 245369
* [InstSimplify] Don't assume getAggregateElement will succeedDavid Majnemer2015-08-182-9/+4
| | | | | | | It isn't always possible to get a value from getAggregateElement. This fixes PR24488. llvm-svn: 245365
* [VectorUtils] Replace 'llvm::' qualification with 'using llvm'David Majnemer2015-08-181-18/+15
| | | | | | | No funcitonal change is intended, this just makes the file look more like the rest of LLVM. llvm-svn: 245364
* [PM/AA] Remove the last relics of the separate IPA library from LLVM,Chandler Carruth2015-08-1813-84/+13
| | | | | | | | | | | | | | | | | | | | | folding the code into the main Analysis library. There already wasn't much of a distinction between Analysis and IPA. A number of the passes in Analysis are actually IPA passes, and there doesn't seem to be any advantage to separating them. Moreover, it makes it hard to have interactions between analyses that are both local and interprocedural. In trying to make the Alias Analysis infrastructure work with the new pass manager, it becomes particularly awkward to navigate this split. I've tried to find all the places where we referenced this, but I may have missed some. I have also adjusted the C API to continue to be equivalently functional after this change. Differential Revision: http://reviews.llvm.org/D12075 llvm-svn: 245318
* [LVI] Use a SmallDenseMap instead of std::map for ValueCacheEntryTyBruno Cardoso Lopes2015-08-181-1/+2
| | | | | | | | | | | | | | Historically there seems to be some resistance regarding the change to DenseMap (r147980). However, I couldn't find cases of iterator invalidation for ValueCacheEntryTy, but only for ValueCache, which I left untouched. This reduces 20s on an internal testcase. Follow up from r245309. Differential Revision: http://reviews.llvm.org/D11651 rdar://problem/21320066 llvm-svn: 245314
* [LVI] Improve LazyValueInfo compile time performanceBruno Cardoso Lopes2015-08-181-29/+32
| | | | | | | | | | | | | | | | | Changes in LoopUnroll in the past six months exposed scalability issues in LazyValueInfo when used from JumpThreading. One internal test that used to take 20s under -O2 now takes 6min. This commit change the OverDefinedCache from DenseSet<std::pair<AssertingVH<BasicBlock>, Value*>> to DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>> and reduces compile time down to 1m40s. Differential Revision: http://reviews.llvm.org/D11651 rdar://problem/21320066 llvm-svn: 245309
* [ScalarEvolutionExpander] Reuse findExistingExpansion during expansion cost ↵Igor Laevsky2015-08-171-19/+11
| | | | | | | | | | calculation for division Primary purpose of this change is to reuse existing code inside findExistingExpansion. However it introduces very slight semantic change - findExistingExpansion now looks into exiting blocks instead of a loop latches. Originally heuristic was based on the fact that we want to look at the loop exit conditions. And since all exiting latches will be listed in the ExitingBlocks, heuristic stays roughly the same. Differential Revision: http://reviews.llvm.org/D12008 llvm-svn: 245227
* [BasicAliasAnalysis] Do not check ModRef table for intrinsicsIgor Laevsky2015-08-171-7/+0
| | | | | | | | All possible ModRef behaviours can be completely represented using existing LLVM IR attributes. Differential Revision: http://reviews.llvm.org/D12033 llvm-svn: 245224
* Take alignment into account in isSafeToSpeculativelyExecute and ↵Artur Pilipenko2015-08-172-39/+91
| | | | | | | | | | isSafeToLoadUnconditionally. Reviewed By: hfinkel, sanjoy, MatzeB Differential Revision: http://reviews.llvm.org/D9791 llvm-svn: 245223
* [GMR] isNonEscapingGlobalNoAlias() should look through Bitcasts/GEPs when ↵Michael Kuperstein2015-08-171-1/+1
| | | | | | | | | | looking at loads. This fixes yet another case from PR24288. Differential Revision: http://reviews.llvm.org/D12064 llvm-svn: 245207
* [PM] Port ScalarEvolution to the new pass manager.Chandler Carruth2015-08-178-157/+194
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change makes ScalarEvolution a stand-alone object and just produces one from a pass as needed. Making this work well requires making the object movable, using references instead of overwritten pointers in a number of places, and other refactorings. I've also wired it up to the new pass manager and added a RUN line to a test to exercise it under the new pass manager. This includes basic printing support much like with other analyses. But there is a big and somewhat scary change here. Prior to this patch ScalarEvolution was never *actually* invalidated!!! Re-running the pass just re-wired up the various other analyses and didn't remove any of the existing entries in the SCEV caches or clear out anything at all. This might seem OK as everything in SCEV that can uses ValueHandles to track updates to the values that serve as SCEV keys. However, this still means that as we ran SCEV over each function in the module, we kept accumulating more and more SCEVs into the cache. At the end, we would have a SCEV cache with every value that we ever needed a SCEV for in the entire module!!! Yowzers. The releaseMemory routine would dump all of this, but that isn't realy called during normal runs of the pipeline as far as I can see. To make matters worse, there *is* actually a key that we don't update with value handles -- there is a map keyed off of Loop*s. Because LoopInfo *does* release its memory from run to run, it is entirely possible to run SCEV over one function, then over another function, and then lookup a Loop* from the second function but find an entry inserted for the first function! Ouch. To make matters still worse, there are plenty of updates that *don't* trip a value handle. It seems incredibly unlikely that today GVN or another pass that invalidates SCEV can update values in *just* such a way that a subsequent run of SCEV will incorrectly find lookups in a cache, but it is theoretically possible and would be a nightmare to debug. With this refactoring, I've fixed all this by actually destroying and recreating the ScalarEvolution object from run to run. Technically, this could increase the amount of malloc traffic we see, but then again it is also technically correct. ;] I don't actually think we're suffering from tons of malloc traffic from SCEV because if we were, the fact that we never clear the memory would seem more likely to have come up as an actual problem before now. So, I've made the simple fix here. If in fact there are serious issues with too much allocation and deallocation, I can work on a clever fix that preserves the allocations (while clearing the data) between each run, but I'd prefer to do that kind of optimization with a test case / benchmark that shows why we need such cleverness (and that can test that we actually make it faster). It's possible that this will make some things faster by making the SCEV caches have higher locality (due to being significantly smaller) so until there is a clear benchmark, I think the simple change is best. Differential Revision: http://reviews.llvm.org/D12063 llvm-svn: 245193
* Revert r244127: [PM] Remove a failed attempt to port the CallGraphChandler Carruth2015-08-161-0/+15
| | | | | | | | | | | | | analysis ... It turns out that we *do* need the old CallGraph ported to the new pass manager. There are times where this model of a call graph is really superior to the one provided by the LazyCallGraph. For example, GlobalsModRef very specifically needs the model provided by CallGraph. While here, I've tried to make the move semantics actually work. =] llvm-svn: 245170
* [PM/AA] Delete the LibCallAliasAnalysis and all the associatedChandler Carruth2015-08-154-185/+0
| | | | | | | | | | | | | | | | | | infrastructure. This AA was never used in tree. It's infrastructure also completely overlaps that of TargetLibraryInfo which is used heavily by BasicAA to achieve similar goals to those stated for this analysis. As has come up in several discussions, the use case here is still really important, but this code isn't helping move toward that use case. Any progress on better supporting rich AA information for runtime library environments would likely be better off starting from scratch or starting from TargetLibraryInfo than from this base. Differential Revision: http://reviews.llvm.org/D12028 llvm-svn: 245155
* [IR] Give catchret an optional 'return value' operandDavid Majnemer2015-08-153-6/+9
| | | | | | | | | | | Some personality routines require funclet exit points to be clearly marked, this is done by producing a token at the funclet pad and consuming it at the corresponding ret instruction. CleanupReturnInst already had a spot for this operand but CatchReturnInst did not. Other personality routines don't need to use this which is why it has been made optional. llvm-svn: 245149
* [SCEV] Apply NSW and NUW flags via poison value analysis for sub, mul and shlBjarke Hammersholt Roune2015-08-141-34/+79
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: http://reviews.llvm.org/D11212 made Scalar Evolution able to propagate NSW and NUW flags from instructions to SCEVs for add instructions. This patch expands that to sub, mul and shl instructions. This change makes LSR able to generate pointer induction variables for loops like these, where the index is 32 bit and the pointer is 64 bit: for (int i = 0; i < numIterations; ++i) sum += ptr[i - offset]; for (int i = 0; i < numIterations; ++i) sum += ptr[i * stride]; for (int i = 0; i < numIterations; ++i) sum += ptr[3 * (i << 7)]; Reviewers: atrick, sanjoy Subscribers: sanjoy, majnemer, hfinkel, llvm-commits, meheff, jingyue, eliben Differential Revision: http://reviews.llvm.org/D11860 llvm-svn: 245118
* Separate out BDCE's analysis into a separate DemandedBits analysis.James Molloy2015-08-143-0/+366
| | | | | | | This allows other areas of the compiler to use BDCE's bit-tracking. NFCI. llvm-svn: 245039
* [IR] Add token typesDavid Majnemer2015-08-142-0/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This introduces the basic functionality to support "token types". The motivation stems from the need to perform operations on a Value whose provenance cannot be obscured. There are several applications for such a type but my immediate motivation stems from WinEH. Our personality routine enforces a single-entry - single-exit regime for cleanups. After several rounds of optimizations, we may be left with a terminator whose "cleanup-entry block" is not entirely clear because control flow has merged two cleanups together. We have experimented with using labels as operands inside of instructions which are not terminators to indicate where we came from but found that LLVM does not expect such exotic uses of BasicBlocks. Instead, we can use this new type to clearly associate the "entry point" and "exit point" of our cleanup. This is done by having the cleanuppad yield a Token and consuming it at the cleanupret. The token type makes it impossible to obscure or otherwise hide the Value, making it trivial to track the relationship between the two points. What is the burden to the optimizer? Well, it turns out we have already paid down this cost by accepting that there are certain calls that we are not permitted to duplicate, optimizations have to watch out for such instructions anyway. There are additional places in the optimizer that we will probably have to update but early examination has given me the impression that this will not be heroic. Differential Revision: http://reviews.llvm.org/D11861 llvm-svn: 245029
* [PM/AA] Extract the interface for GlobalsModRef into a header along withChandler Carruth2015-08-141-159/+63
| | | | | | | | | its creation function. This required shifting a bunch of method definitions to be out-of-line so that we could leave most of the implementation guts in the .cpp file. llvm-svn: 245021
* [PM/AA] Hoist the interface to TBAA into a dedicated header along withChandler Carruth2015-08-141-44/+2
| | | | | | its creation function. Update the relevant includes accordingly. llvm-svn: 245019
* [PM/AA] Run clang-format over TBAA code to normalize the formattingChandler Carruth2015-08-141-183/+187
| | | | | | before making substantial changes. llvm-svn: 245017
* [PM/AA] Clean up the SCEV-AA comment formatting and typos.Chandler Carruth2015-08-141-2/+3
| | | | llvm-svn: 245015
* [PM/AA] Run clang-format over the SCEV-AA code to normalize theChandler Carruth2015-08-141-10/+10
| | | | | | formatting. llvm-svn: 245014
* [PM/AA] Hoist the SCEV-AA interface to its own header and pull theChandler Carruth2015-08-141-39/+1
| | | | | | creation function into that header. llvm-svn: 245013
* [PM/AA] Hoist ScopedNoAliasAA's interface into a header and move theChandler Carruth2015-08-141-40/+1
| | | | | | | | | creation function there. Same basic refactoring as the other alias analyses. Nothing special required this time around. llvm-svn: 245012
* [PM/AA] Hoist the value handle definition for CFLAA into the header toChandler Carruth2015-08-141-22/+0
| | | | | | | satisfy libc++'s std::forward_list which requires the value type to be complete. llvm-svn: 245011
* [PM/AA] Run clang-format over the ScopedNoAliasAA pass prior to makingChandler Carruth2015-08-141-16/+12
| | | | | | substantial changes to normalize any formatting. llvm-svn: 245010
* [PM/AA] Extract a minimal interface for CFLAA to its own header file.Chandler Carruth2015-08-141-132/+78
| | | | | | | | | | I've used forward declarations and reorderd the source code some to make this reasonably clean and keep as much of the code as possible in the source file, including all the stratified set details. Just the basic AA interface and the create function are in the header file, and the header file is now included into the relevant locations. llvm-svn: 245009
* [PM/AA] Sink all the actual code from AliasAnalysisCounter back into theChandler Carruth2015-08-141-0/+59
| | | | | | | | | .cpp file to make the header much less noisy. Also makes it easy to use a static helper rather than a public method for printing lines of stats. llvm-svn: 245006
* [PM/AA] Run clang-format over this code to establish a clean baselineChandler Carruth2015-08-141-8/+20
| | | | | | for subsequent changes. llvm-svn: 245005
* [PM/AA] Hoist the AA counter pass into a header to match the analysisChandler Carruth2015-08-141-92/+1
| | | | | | | | | | | | | pattern. Also hoist the creation routine out of the generic header and into the pass header now that we have one. I've worked to not make any changes, even formatting ones here. I'll clean up the formatting and other things in a follow-up patch now that the code is in the right place. llvm-svn: 245004
* [PM/AA] Remove the function names and class names from doxygen commentsChandler Carruth2015-08-141-7/+5
| | | | | | and generally clean up their formatting. llvm-svn: 245002
* [PM/AA] Move the LibCall AA creation routine declaration to thatChandler Carruth2015-08-141-1/+0
| | | | | | analysis's header file to be more consistent with other analyses. llvm-svn: 245001
* [PM/AA] Run clang-format over LibCallAliasAnalysis prior to makingChandler Carruth2015-08-141-17/+17
| | | | | | substantial changes needed for the new pass manager's AA integration. llvm-svn: 245000
* [PM/AA] Remove the AliasDebugger pass.Chandler Carruth2015-08-123-132/+0
| | | | | | | | | | | | | | | | | | This debugger was designed to catch places where the old update API was failing to be used correctly. As I've removed the update API, it no longer serves any purpose. We can introduce new debugging aid passes around any future work w.r.t. updating AAs. Note that I've updated the documentation here, but really I need to rewrite the documentation to carefully spell out the ideas around stateful AA and how things are changing in the AA world. However, I'm hoping to do that as a follow-up to the refactoring of the AA infrastructure to work in both old and new pass managers so that I can write the documentation specific to that world. Differential Revision: http://reviews.llvm.org/D11984 llvm-svn: 244825
* [PM/AA] Add missing static dependency edges from DSE and memdep to TLI.Chandler Carruth2015-08-121-1/+2
| | | | | | | | I forgot to add these in r244780 and r244778. Sorry about that. Also order the static dependencies in a lexicographical order. llvm-svn: 244787
* [PM/AA] Have memdep explicitly get and use TargetLibraryInfo rather thanChandler Carruth2015-08-121-5/+7
| | | | | | | | | relying on sneaking it out of its AliasAnalysis. This abuse of AA (to shuffle TLI around rather than explicitly depending on it) is going away with my refactor of AA. llvm-svn: 244778
OpenPOWER on IntegriCloud