summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [LVI] Handle constants defensivelyPhilip Reames2016-02-101-3/+7
| | | | | | | | | | There's nothing preventing callers of LVI from asking for lattice values representing a Constant. In fact, given that several callers are walking back through PHI nodes and trying to simplify predicates, such queries are actually quite common. This is mostly harmless today, but we start volatiling assertions if we add new calls to getBlockValue in otherwise reasonable places. Note that this change is not NFC. Specifically: 1) The result returned through getValueAt will now be more precise. In principle, this could trigger any latent infinite optimization loops in callers, but in practice, we're unlikely to see this. 2) The result returned through getBlockValueAt is potentially weakened for non-constants that were previously queried. With the old code, you had the possibility that a later query might bypass the cache and discover some information the original query did not. I can't find a scenario which actually causes this to happen, but it was in principle possible. On the other hand, this may end up reducing compile time when the same value is queried repeatedly. llvm-svn: 260439
* [MemoryBuiltins] Fix an issue with hasNoAliasAttrSanjoy Das2016-02-091-1/+1
| | | | | | | | | | | | | | | | | | | | | | | Summary: `hasNoAliasAttr` is buggy: it checks to see if the called function has a `noalias` attribute, which is incorrect since functions are not even allowed to have the `noalias` attribute. The comment on its only caller, `llvm::isNoAliasFn`, makes it pretty clear that the intention to do the `noalias` check on the return value, and not the callee. Unfortunately I couldn't find a way to test this upstream -- fixing this does not change the observable behavior of any of the passes that use this. This is not very surprising, since `noalias` does not tell anything about the contents of the allocated memory (so, e.g., you still cannot fold loads). I'll be happy to be proven wrong though. Reviewers: chandlerc, reames Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D17037 llvm-svn: 260298
* [GMR/OperandBundles] Teach getModRefBehavior about operand bundlesSanjoy Das2016-02-091-7/+8
| | | | | | | | | In general, memory restrictions on a called function (e.g. readnone) cannot be transferred to a CallSite that has operand bundles. It is possible to make this inference smarter, but lets fix the behavior to be correct first. llvm-svn: 260193
* Add an "addUsedAAAnalyses" helper functionSanjoy Das2016-02-091-0/+11
| | | | | | | | | | | | | | | | | | | Summary: Passes that call `getAnalysisIfAvailable<T>` also need to call `addUsedIfAvailable<T>` in `getAnalysisUsage` to indicate to the legacy pass manager that it uses `T`. This contract was being violated by passes that used `createLegacyPMAAResults`. This change fixes this by exposing a helper in AliasAnalysis.h, `addUsedAAAnalyses`, that is complementary to createLegacyPMAAResults and does the right thing when called from `getAnalysisUsage`. Reviewers: chandlerc Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D17010 llvm-svn: 260183
* Remove SCEVAAWrapperPass from createLegacyPMAAResults; NFCSanjoy Das2016-02-091-2/+0
| | | | | | | | | | | | | | | Summary: createLegacyPMAAResults is only called by CGSCC and Module passes, so the call to getAnalysisIfAvailable<SCEVAAWrapperPass>() never succeeds (SCEVAAWrapperPass is a function pass). Reviewers: chandlerc Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D17009 llvm-svn: 260182
* This patch is to fix PR26529 caused by r259736.Wei Mi2016-02-091-4/+3
| | | | | | | | | | | | | | | | IndVarSimplify assumes scAddRecExpr to be expanded in literal form instead of canonical form by calling disableCanonicalMode after it creates SCEVExpander. When CanonicalMode is disabled, SCEVExpander::expand should always return PHI node for scAddRecExpr. r259736 broke the assumption. The fix is to let SCEVExpander::expand skip the reuse Value logic if CanonicalMode is false. In addition, Besides IndVarSimplify, LSR pass also calls disableCanonicalMode before doing rewrite. We can remove the original check of LSRMode in reuse Value logic and use CanonicalMode instead. llvm-svn: 260174
* Factor out UnrollAnalyzer to Analysis, and add unit tests for it.Michael Zolotukhin2016-02-082-0/+192
| | | | | | | | | | | | | | | | Summary: Unrolling Analyzer is already pretty complicated, and it becomes harder and harder to exercise it with usual IR tests, as with them we can only check the final decision: whether the loop is unrolled or not. This change factors this framework out from LoopUnrollPass to analyses, which allows to use unit tests. The change itself is supposed to be NFC, except adding a couple of tests. I plan to add more tests as I add new functionality and find/fix bugs. Reviewers: chandlerc, hfinkel, sanjoy Subscribers: zzheng, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D16623 llvm-svn: 260169
* [SCEV][LAA] Re-commit r260085 and r260086, this time with a fix for the memorySilviu Baranga2016-02-083-28/+299
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | sanitizer issue. The PredicatedScalarEvolution's copy constructor wasn't copying the Generation value, and was leaving it un-initialized. Original commit message: [SCEV][LAA] Add no wrap SCEV predicates and use use them to improve strided pointer detection Summary: This change adds no wrap SCEV predicates with: - support for runtime checking - support for expression rewriting: (sext ({x,+,y}) -> {sext(x),+,sext(y)} (zext ({x,+,y}) -> {zext(x),+,sext(y)} Note that we are sign extending the increment of the SCEV, even for the zext case. This is needed to cover the fairly common case where y would be a (small) negative integer. In order to do this, this change adds two new flags: nusw and nssw that are applicable to AddRecExprs and permit the transformations above. We also change isStridedPtr in LAA to be able to make use of these predicates. With this feature we should now always be able to work around overflow issues in the dependence analysis. Reviewers: mzolotukhin, sanjoy, anemet Subscribers: mzolotukhin, sanjoy, llvm-commits, rengolin, jmolloy, hfinkel Differential Revision: http://reviews.llvm.org/D15412 llvm-svn: 260112
* Revert r260086 and r260085. They have broken the memorySilviu Baranga2016-02-083-298/+28
| | | | | | sanitizer bots. llvm-svn: 260087
* [SCEV][LAA] Add no wrap SCEV predicates and use use them to improve strided ↵Silviu Baranga2016-02-083-28/+298
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | pointer detection Summary: This change adds no wrap SCEV predicates with: - support for runtime checking - support for expression rewriting: (sext ({x,+,y}) -> {sext(x),+,sext(y)} (zext ({x,+,y}) -> {zext(x),+,sext(y)} Note that we are sign extending the increment of the SCEV, even for the zext case. This is needed to cover the fairly common case where y would be a (small) negative integer. In order to do this, this change adds two new flags: nusw and nssw that are applicable to AddRecExprs and permit the transformations above. We also change isStridedPtr in LAA to be able to make use of these predicates. With this feature we should now always be able to work around overflow issues in the dependence analysis. Reviewers: mzolotukhin, sanjoy, anemet Subscribers: mzolotukhin, sanjoy, llvm-commits, rengolin, jmolloy, hfinkel Differential Revision: http://reviews.llvm.org/D15412 llvm-svn: 260085
* CallAnalyzer::analyzeCall: change the condition back to "Cost < Threshold"Hans Wennborg2016-02-051-1/+1
| | | | | | | | In r252595, I inadvertently changed the condition to "Cost <= Threshold", which caused a significant size regression in Chrome. This commit rectifies that. llvm-svn: 259915
* Fix a regression for r259736.Wei Mi2016-02-041-3/+10
| | | | | | | | | When SCEV expansion tries to reuse an existing value, it is needed to ensure that using the Value at the InsertPt will not break LCSSA. The fix adds a check that InsertPt is either inside the candidate Value's parent loop, or the candidate Value's parent loop is nullptr. llvm-svn: 259815
* [SCEV] Add boolean accessors for NSW, NUW and NW; NFCSanjoy Das2016-02-041-14/+14
| | | | llvm-svn: 259809
* [SCEV] Try to reuse existing value during SCEV expansionWei Mi2016-02-042-5/+113
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Current SCEV expansion will expand SCEV as a sequence of operations and doesn't utilize the value already existed. This will introduce redundent computation which may not be cleaned up throughly by following optimizations. This patch introduces an ExprValueMap which is a map from SCEV to the set of equal values with the same SCEV. When a SCEV is expanded, the set of values is checked and reused whenever possible before generating a sequence of operations. The original commit triggered regressions in Polly tests. The regressions exposed two problems which have been fixed in current version. 1. Polly will generate a new function based on the old one. To generate an instruction for the new function, it builds SCEV for the old instruction, applies some tranformation on the SCEV generated, then expands the transformed SCEV and insert the expanded value into new function. Because SCEV expansion may reuse value cached in ExprValueMap, the value in old function may be inserted into new function, which is wrong. In SCEVExpander::expand, there is a logic to check the cached value to be used should dominate the insertion point. However, for the above case, the check always passes. That is because the insertion point is in a new function, which is unreachable from the old function. However for unreachable node, DominatorTreeBase::dominates thinks it will be dominated by any other node. The fix is to simply add a check that the cached value to be used in expansion should be in the same function as the insertion point instruction. 2. When the SCEV is of scConstant type, expanding it directly is cheaper than reusing a normal value cached. Although in the cached value set in ExprValueMap, there is a Constant type value, but it is not easy to find it out -- the cached Value set is not sorted according to the potential cost. Existing reuse logic in SCEVExpander::expand simply chooses the first legal element from the cached value set. The fix is that when the SCEV is of scConstant type, don't try the reuse logic. simply expand it. Differential Revision: http://reviews.llvm.org/D12090 llvm-svn: 259736
* [ScalarEvolutionExpander] Simplify findInsertPointAfterDavid Majnemer2016-02-031-8/+6
| | | | | | | No functional change is intended. The loop could only execute, at most, once. llvm-svn: 259701
* Revert r259662, which caused regressions on polly tests.Wei Mi2016-02-032-111/+5
| | | | llvm-svn: 259675
* [SCEV] Try to reuse existing value during SCEV expansionWei Mi2016-02-032-5/+111
| | | | | | | | | | | | | | | | Current SCEV expansion will expand SCEV as a sequence of operations and doesn't utilize the value already existed. This will introduce redundent computation which may not be cleaned up throughly by following optimizations. This patch introduces an ExprValueMap which is a map from SCEV to the set of equal values with the same SCEV. When a SCEV is expanded, the set of values is checked and reused whenever possible before generating a sequence of operations. Differential Revision: http://reviews.llvm.org/D12090 llvm-svn: 259662
* [DemandedBits] Revert r249687 due to PR26071James Molloy2016-02-031-7/+0
| | | | | | | | | | | | | | This regresses a test in LoopVectorize, so I'll need to go away and think about how to solve this in a way that isn't broken. From the writeup in PR26071: What's happening is that ComputeKnownZeroes is telling us that all bits except the LSB are zero. We're then deciding that only the LSB needs to be demanded from the icmp's inputs. This is where we're wrong - we're assuming that after simplification the bits that were known zero will continue to be known zero. But they're not - during trivialization the upper bits get changed (because an XOR isn't shrunk), so the icmp fails. The fault is in demandedbits - its contract does clearly state that a non-demanded bit may either be zero or one. llvm-svn: 259649
* [LVI] Fix debug outputPhilip Reames2016-02-021-3/+3
| | | | | | Due to staleness in a patch I committed yesterday, the debug output was reporting overdefined cases as being undefined. Confusing to say the least. The mistake appears to have only effected the debug output thankfully. llvm-svn: 259594
* [LVI] Code motion only [NFC]Philip Reames2016-02-021-64/+62
| | | | | | I introduced a declaration in 259583 to keep the diff readable. This change just moves the definition up to remove the declaration again. llvm-svn: 259585
* [LVI] Refactor to use newly introduced intersect utility Philip Reames2016-02-021-32/+19
| | | | | | | | This patch uses the newly introduced 'intersect' utility (from 259461: [LVI] Introduce an intersect operation on lattice values) to simplify existing code in LVI. While not introducing any new concepts, this change is probably not NFC. The common 'intersect' function is more powerful that the ad-hoc implementations we'd had in a couple of places. Given that, we may see optimizations triggering a bit more often. llvm-svn: 259583
* Fix Clang-tidy readability-redundant-control-flow warnings; other minor fixes.Eugene Zelenko2016-02-021-3/+13
| | | | | | Differential revision: http://reviews.llvm.org/D16793 llvm-svn: 259539
* [LCG] Build an edge abstraction for the LazyCallGraph and use it toChandler Carruth2016-02-021-133/+160
| | | | | | | | | | | | | | | | | | | | | differentiate between indirect references to functions an direct calls. This doesn't do a whole lot yet other than change the print out produced by the analysis, but it lays the groundwork for a very major change I'm working on next: teaching the call graph to actually be a call graph, modeling *both* the indirect reference graph and the call graph simultaneously. More details on that in the next patch though. The rest of this is essentially a bunch of over-engineering that won't be interesting until the next patch. But this also isolates essentially all of the churn necessary to introduce the edge abstraction from the very important behavior change necessary in order to separately model the two graphs. So it should make review of the subsequent patch a bit easier at the cost of making this patch seem poorly motivated. ;] Differential Revision: http://reviews.llvm.org/D16038 llvm-svn: 259463
* [LVI] Introduce an intersect operation on lattice valuesPhilip Reames2016-02-021-32/+85
| | | | | | | | | | | | LVI has several separate sources of facts - edge local conditions, recursive queries, assumes, and control independent value facts - which all apply to the same value at the same location. The existing implementation was very conservative about exploiting all of these facts at once. This change introduces an "intersect" function specifically to abstract the action of picking a good set of facts from all of the separate facts given. At the moment, this function is relatively simple (i.e. mostly just reuses the bits which were already there), but even the minor additions reveal the inherent power. For example, JumpThreading is now capable of doing an inductive proof that a particular value is always positive and removing a half range check. I'm currently only using the new intersect function in one place. If folks are happy with the direction of the work, I plan on making a series of small changes without review to replace mergeIn with intersect at all the appropriate places. Differential Revision: http://reviews.llvm.org/D14476 llvm-svn: 259461
* [LVI] Fix a latent bug in getValueAtPhilip Reames2016-02-021-0/+8
| | | | | | | | This routine was returning Undefined for most queries. This was utterly wrong. Amusingly, we do not appear to have any callers of this which are actually trying to exploit unreachable code or this would have broken the world. A better approach would be to explicit describe the intersection of facts. That's blocked behind http://reviews.llvm.org/D14476 and I wanted to fix the current bug. llvm-svn: 259446
* [LVI] Remove overly tight assert from 259429Philip Reames2016-02-011-2/+2
| | | | | | I'll submit a test case shortly which covers this, but it's causing clang self host problems in the builders so I wanted to get it removed. llvm-svn: 259432
* [LVI] Add select handlingPhilip Reames2016-02-011-0/+49
| | | | | | | | Teach LVI to handle select instructions in the exact same way it handles PHI nodes. This is useful since various parts of the optimizer convert PHI nodes into selects and we don't want these transformations to cause inferior optimization. Note that this patch does nothing to exploit the implied constraint on the inputs represented by the select condition itself. That will be a later patch and is blocked on http://reviews.llvm.org/D14476 llvm-svn: 259429
* Avoid inlining call sites in unreachable-terminated blockJun Bum Lim2016-02-011-6/+17
| | | | | | | | | | | | | Summary: If the normal destination of the invoke or the parent block of the call site is unreachable-terminated, there is little point in inlining the call site unless there is literally zero cost. Unlike my previous change (D15289), this change specifically handle the call sites followed by unreachable in the same basic block for call or in the normal destination for the invoke. This change could be a reasonable first step to conservatively inline call sites leading to an unreachable-terminated block while BFI / BPI is not yet available in inliner. Reviewers: manmanren, majnemer, hfinkel, davidxl, mcrosier, dblaikie, eraman Subscribers: dblaikie, davidxl, mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D16616 llvm-svn: 259403
* [SCEV] Clean up isKnownPredicateViaConstantRanges; NFCISanjoy Das2016-02-011-63/+20
| | | | | | | | | | | | | | | - ScalarEvolution::isKnownPredicateViaConstantRanges duplicates some logic already present in ConstantRange, use ConstantRange for those bits. - In some cases ScalarEvolution::isKnownPredicateViaConstantRanges returns `false` to mean "definitely false" (e.g. see the `LHSRange.getSignedMin().sge(RHSRange.getSignedMax())` case for `ICmpInst::ICMP_SLT`), but for `isKnownPredicateViaConstantRanges`, `false` actually means "don't know". Get rid of this extra bit of code to avoid confusion. llvm-svn: 259401
* [SCEV] Rename isKnownPredicateWithRanges; NFCSanjoy Das2016-02-011-7/+8
| | | | | | | Make it obvious that it uses constant ranges, and use `Via` instead of `With`, like other similar functions in SCEV. llvm-svn: 259400
* [ValueTracking] Improve isKnownNonZero for PHI of non-zero constantsJun Bum Lim2016-02-011-0/+6
| | | | | | It is clear that a PHI is a non-zero if all incoming values are non-zero constants. llvm-svn: 259370
* [BasicAA] NFC - revised comment for function adjustToPointerSize()Gerolf Hoflehner2016-01-301-1/+1
| | | | llvm-svn: 259300
* [BasicAA] Fix for missing must alias (D16343)Gerolf Hoflehner2016-01-301-0/+3
| | | | llvm-svn: 259299
* [BasicAA] Update on r259290 - added missing castGerolf Hoflehner2016-01-301-1/+1
| | | | llvm-svn: 259298
* [BasicAA] NFC - utility function for two's complement wrap-aroundGerolf Hoflehner2016-01-301-7/+15
| | | | llvm-svn: 259290
* Avoid overly large SmallPtrSet/SmallSetMatthias Braun2016-01-303-4/+4
| | | | | | | These sets perform linear searching in small mode so it is never a good idea to use SmallSize/N bigger than 32. llvm-svn: 259283
* Annotate dump() methods with LLVM_DUMP_METHOD, addressing Richard Smith ↵Yaron Keren2016-01-299-10/+10
| | | | | | | | r259192 post commit comment. clang part in r259232, this is the LLVM part of the patch. llvm-svn: 259240
* Lower inlining threshold when the caller has minsize attribute.Easwaran Raman2016-01-281-8/+8
| | | | | | | | | | | | When the caller has optsize attribute, we reduce the inlinining threshold to OptSizeThreshold (=75) if it is not already lower than that. We don't do the same for minsize and I suspect it was not intentional. This also addresses a FIXME regarding checking optsize attribute explicitly instead of using the right wrapper. Differential Revision: http://reviews.llvm.org/D16493 llvm-svn: 259120
* ValueTracking: Use fixed array for assumption exclude set in Query.Matthias Braun2016-01-281-15/+27
| | | | | | | | | | | | The Query structure is constructed often and is relevant for compiletime performance. We can replace the SmallPtrSet for assumption exclusions in this structure with a fixed size array because we know the maximum number of elements. This improves typical clang -O3 -emit-llvm compiletime by 1.2% in my measurements. Differential Revision: http://reviews.llvm.org/D16204 llvm-svn: 259025
* Minor style cleanup of CFLAA. NFC.George Burgess IV2016-01-281-6/+11
| | | | llvm-svn: 259008
* [TTI] Add getPrefetchDistance from PPCLoopDataPrefetch, NFCAdam Nemet2016-01-271-0/+4
| | | | | | | | | | | This patch is part of the work to make PPCLoopDataPrefetch target-independent (http://thread.gmane.org/gmane.comp.compilers.llvm.devel/92758). As it was discussed in the above thread, getPrefetchDistance is currently using instruction count which may change in the future. llvm-svn: 258995
* Add support for objc_unsafeClaimAutoreleasedReturnValue to theJohn McCall2016-01-271-0/+14
| | | | | | | | | | | | | | | | ObjC ARC Optimizer. The main implication of this is: 1. Ensuring that we treat it conservatively in terms of optimization. 2. We put the ASM marker on it so that the runtime can recognize objc_unsafeClaimAutoreleasedReturnValue from releaseRV. <rdar://problem/21567064> Patch by Michael Gottesman! llvm-svn: 258970
* Make some headers self-contained, remove unused includes that violate layering.Benjamin Kramer2016-01-272-2/+0
| | | | llvm-svn: 258937
* Disable all standard lib functions for NVVM.Justin Lebar2016-01-261-0/+14
| | | | | | | | | | | | | | | | | Summary: NVVM doesn't have a standard library, as currently implemented, so this just isn't going to work. I'd like to revisit this, since it's hiding opportunities for optimization, but correctness comes first. Thank you to hfinkel for pointing me in the right direction here. Reviewers: tra Subscribers: echristo, jhen, llvm-commits, hfinkel Differential Revision: http://reviews.llvm.org/D16604 llvm-svn: 258884
* Remove autoconf supportChris Bieneman2016-01-261-15/+0
| | | | | | | | | | | | | | | | Summary: This patch is provided in preparation for removing autoconf on 1/26. The proposal to remove autoconf on 1/26 was discussed on the llvm-dev thread here: http://lists.llvm.org/pipermail/llvm-dev/2016-January/093875.html "I felt a great disturbance in the [build system], as if millions of [makefiles] suddenly cried out in terror and were suddenly silenced. I fear something [amazing] has happened." - Obi Wan Kenobi Reviewers: chandlerc, grosbach, bob.wilson, tstellarAMD, echristo, whitequark Subscribers: chfast, simoncook, emaste, jholewinski, tberghammer, jfb, danalbert, srhines, arsenm, dschuff, jyknight, dsanders, joker.eph, llvm-commits Differential Revision: http://reviews.llvm.org/D16471 llvm-svn: 258861
* [LIR] Add support for structs and hand unrolled loopsHaicheng Wu2016-01-261-0/+72
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a recommit of r258620 which causes PR26293. The original message: Now LIR can turn following codes into memset: typedef struct foo { int a; int b; } foo_t; void bar(foo_t *f, unsigned n) { for (unsigned i = 0; i < n; ++i) { f[i].a = 0; f[i].b = 0; } } void test(foo_t *f, unsigned n) { for (unsigned i = 0; i < n; i += 2) { f[i] = 0; f[i+1] = 0; } } llvm-svn: 258777
* Speculatively revert r258620 as it is the likely culprid of PR26293.Quentin Colombet2016-01-251-72/+0
| | | | llvm-svn: 258703
* [DemandedBits] Fix computation of demanded bits for ICmpsJames Molloy2016-01-251-1/+1
| | | | | | | | | | The computation of ICmp demanded bits is independent of the individual operand being evaluated. We simply return a mask consisting of the minimum leading zeroes of both operands. We were incorrectly passing "I" to ComputeKnownBits - this should be "UserI->getOperand(0)". In cases where we were evaluating the 1th operand, we were taking the minimum leading zeroes of it and itself. This should fix PR26266. llvm-svn: 258690
* Remove duplicate documentation in ConstantFolding.cpp. NFC.Manuel Jacob2016-01-231-22/+0
| | | | | | The documentation for these functions is already present in the header file. llvm-svn: 258649
* [LIR] Add support for structs and hand unrolled loopsHaicheng Wu2016-01-231-0/+72
| | | | | | | | | | | | | | | | | | | | | | | | | Now LIR can turn following codes into memset: typedef struct foo { int a; int b; } foo_t; void bar(foo_t *f, unsigned n) { for (unsigned i = 0; i < n; ++i) { f[i].a = 0; f[i].b = 0; } } void test(foo_t *f, unsigned n) { for (unsigned i = 0; i < n; i += 2) { f[i] = 0; f[i+1] = 0; } } llvm-svn: 258620
OpenPOWER on IntegriCloud