summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [SCEV] Get rid of an unnecessary lambda; NFCSanjoy Das2015-10-231-11/+9
| | | | llvm-svn: 251099
* [SCEV] Fix a latent bug in `getPreStartForExtend`Sanjoy Das2015-10-231-1/+3
| | | | | | | | | | | | | | | | | | I could not come up a way to test this -- I think this bug is latent today, and will not actually result in a miscompile. In `getPreStartForExtend`, SCEV constructs `PreStart` as a sum of all of `SA`'s operands except `Op`. It also uses `SA`'s no-wrap flags, and this is problematic because removing an element from an add expression can make it signed-wrap. E.g. if `SA` was `(127 + 1 + -1)`, then it could safely be `<nsw>` (since `sext(127) + sext(1) + sext(-1)` == `sext(127 + 1 + -1)`), but `(127 + 1)` (== `PreStart` if `Op` is `-1`) is not `<nsw>`. Transferring `<nuw>` from `SA` to `PreStart` is safe, as far as I can tell. llvm-svn: 251097
* LoopPass: Remove redoLoop, it isn't used. NFCJustin Bogner2015-10-221-13/+0
| | | | | | | | In r251064 I removed a logically unreachable call to `redoLoop`, and now there aren't any callers of this API at all. Remove the needless complexity. llvm-svn: 251067
* LoopPass: Simplify the API for adding a new loop. NFCJustin Bogner2015-10-221-27/+18
| | | | | | | The insertLoop() API is only used to add new loops, and has confusing ownership semantics. Simplify it by replacing it with addLoop(). llvm-svn: 251064
* [SCEV] Commute zero extends through <nuw> additionsSanjoy Das2015-10-221-0/+12
| | | | llvm-svn: 251052
* [SCEV] Opportunistically interpret unsigned constraints as signedSanjoy Das2015-10-221-0/+7
| | | | | | | | | | | | | | | Summary: An unsigned comparision is equivalent to is corresponding signed version if both the operands being compared are positive. Teach SCEV to use this fact when profitable. Reviewers: atrick, hfinkel, reames, nlewycky Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13687 llvm-svn: 251051
* [SCEV] Teach SCEV some axioms about non-wrapping arithmeticSanjoy Das2015-10-221-2/+57
| | | | | | | | | | | | | | | | | | | Summary: - A s< (A + C)<nsw> if C > 0 - A s<= (A + C)<nsw> if C >= 0 - (A + C)<nsw> s< A if C < 0 - (A + C)<nsw> s<= A if C <= 0 Right now `C` needs to be a constant, but we can later generalize it to be a non-constant if needed. Reviewers: atrick, hfinkel, reames, nlewycky Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D13686 llvm-svn: 251050
* [SCEV] Commute sign extends through nsw additionsSanjoy Das2015-10-221-0/+10
| | | | | | | | | | | | Summary: Depends on D13613. Reviewers: atrick, hfinkel, reames, nlewycky Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13685 llvm-svn: 251049
* [SCEV] Mark AddExprs as nsw or nuw if legalSanjoy Das2015-10-221-5/+30
| | | | | | | | | | | | | | Summary: This uses `ScalarEvolution::getRange` and not potentially control dependent `nsw` and `nuw` bits on the arithmetic instruction. Reviewers: atrick, hfinkel, nlewycky Subscribers: llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D13613 llvm-svn: 251048
* [GlobalsAA] Loosen an overly conservative bailoutJames Molloy2015-10-221-9/+71
| | | | | | | | | | Instead of bailing out when we see loads, analyze them. If we can prove that the loaded-from address must escape, then we can conclude that a load from that address must escape too and therefore cannot alias a non-addr-taken global. When checking if a Value can alias a non-addr-taken global, if the Value is a LoadInst of a non-global, recurse instead of bailing. If we can follow a trail of loads up to some base that is captured, we know by inference that all the loads we followed are also captured. llvm-svn: 251017
* [BasicAA] Non-equal indices in a GEP of a SequentialType don't overlapJames Molloy2015-10-221-8/+38
| | | | | | | | If the final indices of two GEPs can be proven to not be equal, and the GEP is of a SequentialType (not a StructType), then the two GEPs do not alias. llvm-svn: 251016
* [ValueTracking] Add a new predicate: isKnownNonEqual()James Molloy2015-10-222-0/+64
| | | | | | | | | | | | | | isKnownNonEqual(A, B) returns true if it can be determined that A != B. At the moment it only knows two facts, that a non-wrapping add of nonzero to a value cannot be that value: A + B != A [where B != 0, addition is nsw or nuw] and that contradictory known bits imply two values are not equal. This patch also hooks this up to InstSimplify; InstSimplify had a peephole for the first fact but not the second so this teaches InstSimplify a new trick too (alas no measured performance impact!) llvm-svn: 251012
* [AA] Enhance the new AliasAnalysis infrastructure with an optionalChandler Carruth2015-10-211-0/+40
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | "external" AA wrapper pass. This is a generic hook that can be used to thread custom code into the primary AAResultsWrapperPass for the legacy pass manager in order to allow it to merge external AA results into the AA results it is building. It does this by threading in a raw callback and so it is *very* powerful and should serve almost any use case I have come up with for extending the set of alias analyses used. The only thing not well supported here is using a *different order* of alias analyses. That form of extension *is* supportable with the new pass manager, and I can make the callback structure here more elaborate to support it in the legacy pass manager if this is a critical use case that people are already depending on, but the only use cases I have heard of thus far should be reasonably satisfied by this simpler extension mechanism. It is hard to test this using normal facilities (the built-in AAs don't use this for obvious reasons) so I've written a fairly extensive set of custom passes in the alias analysis unit test that should be an excellent test case because it models the out-of-tree users: it adds a totally custom AA to the system. This should also serve as a reasonably good example and guide for out-of-tree users to follow in order to rig up their existing alias analyses. No support in opt for commandline control is provided here however. I'm really unhappy with the kind of contortions that would be required to support that. It would fully re-introduce the analysis group self-recursion kind of patterns. =/ I've heard from out-of-tree users that this will unblock their use cases with extending AAs on top of the new infrastructure and let us retain the new analysis-group-free-world. Differential Revision: http://reviews.llvm.org/D13418 llvm-svn: 250894
* [GlobalsAA] Fix a really horrible iterator invalidation bugJames Molloy2015-10-191-1/+4
| | | | | | | | | | We were keeping a reference to an object in a DenseMap then mutating it. At the end of the function we were attempting to clone that reference into other keys in the DenseMap, but DenseMap may well decide to resize its hashtable which would invalidate the reference! It took an extremely complex testcase to catch this - many thanks to Zhendong Su for catching it in PR25225. This fixes PR25225. llvm-svn: 250692
* Removed parameter "Consecutive" from isLegalMaskedLoad() / isLegalMaskedStore().Elena Demikhovsky2015-10-191-6/+4
| | | | | | | | | | Originally I planned to use the same interface for masked gather/scatter and set isConsecutive to "false" in this case. Now I'm implementing masked gather/scatter and see that the interface is inconvenient. I want to add interfaces isLegalMaskedGather() / isLegalMaskedScatter() instead of using the "Consecutive" parameter in the existing interfaces. Differential Revision: http://reviews.llvm.org/D13850 llvm-svn: 250686
* [SCEV] Fix whitespace issues and remove extra braces; NFCSanjoy Das2015-10-181-10/+7
| | | | llvm-svn: 250636
* [SCEV] Use std::all_of and std::any_of; NFCSanjoy Das2015-10-181-16/+11
| | | | llvm-svn: 250635
* [SCEV] Use auto where it helps remove line breaks; NFCSanjoy Das2015-10-181-13/+6
| | | | llvm-svn: 250634
* [SCEV] Use range for loops; NFCSanjoy Das2015-10-181-22/+17
| | | | llvm-svn: 250633
* Recommit r250345, it was reverted in r250366 to investigate a bot failure.Manman Ren2015-10-152-0/+13
| | | | | | Our internal bot is still red after r250366. llvm-svn: 250415
* Silencing a -Wtype-limits warning; an unsigned value will always be >= 0; NFC.Aaron Ballman2015-10-151-1/+1
| | | | llvm-svn: 250404
* Temporarily revert r250345 to sort out bot failure.Manman Ren2015-10-152-13/+0
| | | | | | | | | | | | | | With r250345 and r250343, we start to observe the following failure when bootstrap clang with lto and pgo: PHI node entries do not match predecessors! %.sroa.029.3.i = phi %"class.llvm::SDNode.13298"* [ null, %30953 ], [ null, %31017 ], [ null, %30998 ], [ null, %_ZN4llvm8dyn_castINS_14ConstantSDNodeENS_7SDValueEEENS_10cast_rettyIT_T0_E8ret_typeERS5_.exit.i.1804 ], [ null, %30975 ], [ null, %30991 ], [ null, %_ZNK4llvm3EVT13getScalarTypeEv.exit.i.1812 ], [ %..sroa.029.0.i, %_ZN4llvm11SmallVectorIiLj8EED1Ev.exit.i.1826 ], !dbg !451895 label %30998 label %_ZNK4llvm3EVTeqES0_.exit19.thread.i LLVM ERROR: Broken function found, compilation aborted! I will re-commit this if the bot does not recover. llvm-svn: 250366
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-142-0/+13
| | | | | | | | | | Currently in JumpThreading pass, the branch weight metadata is not updated after CFG modification. Consider the jump threading on PredBB, BB, and SuccBB. After jump threading, the weight on BB->SuccBB should be adjusted as some of it is contributed by the edge PredBB->BB, which doesn't exist anymore. This patch tries to update the edge weight in metadata on BB->SuccBB by scaling it by 1 - Freq(PredBB->BB) / Freq(BB->SuccBB). This is the third attempt to submit this patch, while the first two led to failures in some FDO tests. After investigation, it is the edge weight normalization that caused those failures. In this patch the edge weight normalization is fixed so that there is no zero weight in the output and the sum of all weights can fit in 32-bit integer. Several unit tests are added. Differential revision: http://reviews.llvm.org/D10979 llvm-svn: 250345
* Tighten known bits for ctpop based on zero input bitsPhilip Reames2015-10-141-2/+12
| | | | | | | | | | This is a cleaned up patch from the one written by John Regehr based on the findings of the Souper superoptimizer. The basic idea here is that input bits that are known zero reduce the maximum count that the intrinsic could return. We know that the number of bits required to represent a particular count is at most log2(N)+1. Differential Revision: http://reviews.llvm.org/D13253 llvm-svn: 250338
* Revert r250204 and r250240 due to bot failure. We failed to build PGO-ed clang.Manman Ren2015-10-142-13/+0
| | | | llvm-svn: 250264
* [asan] Disabling speculative loads under asan. Patch by Mike AizatskyKostya Serebryany2015-10-141-1/+5
| | | | llvm-svn: 250259
* [SCEV] Use `SCEV::isAllOnesValue` directly; NFC.Sanjoy Das2015-10-131-8/+4
| | | | | | | Instead of `dyn_cast` ing to `SCEVConstant` and checking the contained `ConstantInteger. llvm-svn: 250251
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-132-0/+13
| | | | | | | | Currently in JumpThreading pass, the branch weight metadata is not updated after CFG modification. Consider the jump threading on PredBB, BB, and SuccBB. After jump threading, the weight on BB->SuccBB should be adjusted as some of it is contributed by the edge PredBB->BB, which doesn't exist anymore. This patch tries to update the edge weight in metadata on BB->SuccBB by scaling it by 1 - Freq(PredBB->BB) / Freq(BB->SuccBB). Differential revision: http://reviews.llvm.org/D10979 llvm-svn: 250204
* [GlobalsAA] Don't assume anything about functions that may be overriddenJames Molloy2015-10-131-2/+2
| | | | | | | | Weak linkage and friends allow a symbol to be overriden outside the code generator's model, so GlobalsAA shouldn't assume that anything it can compute about such a symbol is valid. llvm-svn: 250156
* Revert 250089 due to bot failure. It failed when building clang itself with PGO.Manman Ren2015-10-132-13/+0
| | | | llvm-svn: 250145
* [SCEV] Put some utilites in the ScalarEvolution classSanjoy Das2015-10-131-18/+22
| | | | | | | | | | | In a later commit, `SplitBinaryAdd` will be used outside `IsConstDiff`, so lift that out. And lift out `IsConstDiff` as `computeConstantDifference` to keep things clean and to avoid playing C++ access specifier games. NFC. llvm-svn: 250143
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-122-0/+13
| | | | | | | | In JumpThreading pass, the branch weight metadata is not updated after CFG modification. Consider the jump threading on PredBB, BB, and SuccBB. After jump threading, the weight on BB->SuccBB should be adjusted as some of it is contributed by the edge PredBB->BB, which doesn't exist anymore. This patch tries to update the edge weight in metadata on BB->SuccBB by scaling it by 1 - Freq(PredBB->BB) / Freq(BB->SuccBB). Differential revision: http://reviews.llvm.org/D10979 llvm-svn: 250089
* [LoopVectorize] Shrink integer operations into the smallest type possibleJames Molloy2015-10-121-0/+130
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | C semantics force sub-int-sized values (e.g. i8, i16) to be promoted to int type (e.g. i32) whenever arithmetic is performed on them. For targets with native i8 or i16 operations, usually InstCombine can shrink the arithmetic type down again. However InstCombine refuses to create illegal types, so for targets without i8 or i16 registers, the lengthening and shrinking remains. Most SIMD ISAs (e.g. NEON) however support vectors of i8 or i16 even when their scalar equivalents do not, so during vectorization it is important to remove these lengthens and truncates when deciding the profitability of vectorization. The algorithm this uses starts at truncs and icmps, trawling their use-def chains until they terminate or instructions outside the loop are found (or unsafe instructions like inttoptr casts are found). If the use-def chains starting from different root instructions (truncs/icmps) meet, they are unioned. The demanded bits of each node in the graph are ORed together to form an overall mask of the demanded bits in the entire graph. The minimum bitwidth that graph can be truncated to is the bitwidth minus the number of leading zeroes in the overall mask. The intention is that this algorithm should "first do no harm", so it will never insert extra cast instructions. This is why the use-def graphs are unioned, so that subgraphs with different minimum bitwidths do not need casts inserted between them. This algorithm works hard to reduce compile time impact. DemandedBits are only queried if there are extends of illegal types and if a truncate to an illegal type is seen. In the general case, this results in a simple linear scan of the instructions in the loop. No non-noise compile time impact was seen on a clang bootstrap build. llvm-svn: 250032
* SCEV: Allow simple AddRec * Parameter products in delinearizationTobias Grosser2015-10-122-11/+85
| | | | | | | | | This patch also allows the -delinearize pass to delinearize expressions that do not have an outermost SCEVAddRec expression. The SCEV::delinearize infrastructure allowed this since r240952, but the -delinearize pass was not updated yet. llvm-svn: 250018
* Analysis: Remove implicit ilist iterator conversionsDuncan P. N. Exon Smith2015-10-1022-99/+99
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Remove implicit ilist iterator conversions from LLVMAnalysis. I came across something really scary in `llvm::isKnownNotFullPoison()` which relied on `Instruction::getNextNode()` being completely broken (not surprising, but scary nevertheless). This function is documented (and coded to) return `nullptr` when it gets to the sentinel, but with an `ilist_half_node` as a sentinel, the sentinel check looks into some other memory and we don't recognize we've hit the end. Rooting out these scary cases is the reason I'm removing the implicit conversions before doing anything else with `ilist`; I'm not at all surprised that clients rely on badness. I found another scary case -- this time, not relying on badness, just bad (but I guess getting lucky so far) -- in `ObjectSizeOffsetEvaluator::compute_()`. Here, we save out the insertion point, do some things, and then restore it. Previously, we let the iterator auto-convert to `Instruction*`, and then set it back using the `Instruction*` version: Instruction *PrevInsertPoint = Builder.GetInsertPoint(); /* Logic that may change insert point */ if (PrevInsertPoint) Builder.SetInsertPoint(PrevInsertPoint); The check for `PrevInsertPoint` doesn't protect correctly against bad accesses. If the insertion point has been set to the end of a basic block (i.e., `SetInsertPoint(SomeBB)`), then `GetInsertPoint()` returns an iterator pointing at the list sentinel. The version of `SetInsertPoint()` that's getting called will then call `PrevInsertPoint->getParent()`, which explodes horribly. The only reason this hasn't blown up is that it's fairly unlikely the builder is adding to the end of the block; usually, we're adding instructions somewhere before the terminator. llvm-svn: 249925
* [WinEH] Delete the old landingpad implementation of Windows EHReid Kleckner2015-10-091-188/+0
| | | | | | | | | | | The new implementation works at least as well as the old implementation did. Also delete the associated preparation tests. They don't exercise interesting corner cases of the new implementation. All the codegen tests of the EH tables have already been ported. llvm-svn: 249918
* ValueTracking: use getAlignment in isAlignedArtur Pilipenko2015-10-091-14/+1
| | | | | | | | Reviewed By: reames Differential Revision: http://reviews.llvm.org/D13517 llvm-svn: 249841
* [SCEV] Call `StrengthenNoWrapFlags` after `GroupByComplexity`; NFCISanjoy Das2015-10-091-4/+4
| | | | | | | | | The current implementation of `StrengthenNoWrapFlags` is agnostic to the order of `Ops`, so this commit should not change anything semantic. An upcoming change will make `StrengthenNoWrapFlags` sensitive to the order of `Ops`. llvm-svn: 249802
* [SCEV] Bring some methods up to coding style; NFCSanjoy Das2015-10-081-32/+27
| | | | | | | | - Start methods with lower case - Reflow a comment - Delete header comment repeated in .cpp file llvm-svn: 249716
* [SCEV] Remove comment repeated in cpp file; NFCSanjoy Das2015-10-081-5/+0
| | | | llvm-svn: 249713
* [SCEV] Pick backedge values for phi nodes correctlySanjoy Das2015-10-081-10/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: `getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively` assumed all phi nodes in the loop header have the same order of incoming values. This is not correct, and this commit changes `getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively` to lookup the backedge value of a phi node using the loop's latch block. Unfortunately, there is still some code duplication `getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively`. At some point in the future we should extract out a helper class / method that can evolve constant evolution phi nodes across iterations. Fixes 25060. Thanks to Mattias Eriksson for the spot-on analysis! Depends on D13457. Reviewers: atrick, hfinkel Subscribers: materi, llvm-commits Differential Revision: http://reviews.llvm.org/D13458 llvm-svn: 249712
* [ValueTracking] teach computeKnownBits that a fabs() clears sign bitsSanjay Patel2015-10-081-2/+10
| | | | | | | | | | | | | This was requested in D13076: if we're going to canonicalize to fabs(), ValueTracking should know that fabs() clears sign bits. In this patch (as in D13076), we're not handling vectors yet even though computeKnownBits' fabs() case itself should be vector-ready via the splat in this patch. Fixing this will require follow-on patches to correct other logic that uses 'getScalarType'. Differential Revision: http://reviews.llvm.org/D13222 llvm-svn: 249701
* Compute demanded bits for icmp instructionsJames Molloy2015-10-081-0/+7
| | | | | | | | | Instead of bailing out when we see an icmp, we can instead at least say that if the upper bits of both operands are known zero, they are not demanded. This doesn't help with signed comparisons, but it's at least better than bailing out. llvm-svn: 249687
* Treat Mul just like Add and SubtractJames Molloy2015-10-081-0/+12
| | | | | | | | | | Like adds and subtracts, muls ripple only to the left so we can use the same logic. While we're here, add a print method to DemandedBits so it can be used with -analyze, which we'll use in the testcase. llvm-svn: 249686
* Make demanded bits lazyJames Molloy2015-10-081-7/+19
| | | | | | | | | | The algorithm itself is still eager, but it doesn't get run until a query function is called. This greatly reduces the compile-time impact of requiring DemandedBits when at runtime it is not often used. NFCI. llvm-svn: 249685
* [SCEV] Check `Pred` first in isKnownPredicateViaSplittingSanjoy Das2015-10-081-2/+2
| | | | | | | Comparing `Pred` with `ICmpInst::ICMP_ULT` is cheaper that memory access -- do that check before loading / storing `ProvingSplitPredicate`. llvm-svn: 249654
* [SCEV] Use `auto *` instead of `auto`; NFCISanjoy Das2015-10-081-7/+7
| | | | | | (As prescribed by the coding style document) llvm-svn: 249653
* Revert "Revert "This patch builds on top of D13378 to handle constant ↵Mehdi Amini2015-10-071-0/+5
| | | | | | | | | | condition."" This reverts commit r249528 and reapply r249431. The fix for the fallout has been commited in r249575. From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 249581
* [SCEV] Use some C++11'ism, NFCSanjoy Das2015-10-071-26/+21
| | | | | | | | | | Summary: Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13457 llvm-svn: 249574
* Teach computeKnownBits to use new align attribute/metadataArtur Pilipenko2015-10-071-3/+12
| | | | | | | | Reviewed By: reames Differential Revision: http://reviews.llvm.org/D13470 llvm-svn: 249557
OpenPOWER on IntegriCloud