summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* Refactor: Simplify boolean conditional return statements in llvm/lib/AnalysisAlexander Kornienko2015-11-054-18/+6
| | | | | | | | Patch by Richard Thomson! Differential revision: http://reviews.llvm.org/D9967 llvm-svn: 252209
* Fix LoopAccessAnalysis when potentially nullptr check are involvedMehdi Amini2015-11-051-1/+6
| | | | | | | | | | | | | | Summary: GetUnderlyingObjects() can return "null" among its list of objects, we don't want to deduce that two pointers can point to the same memory in this case, so filter it out. Reviewers: anemet Subscribers: dexonsmith, llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 252149
* [CaptureTracking] Support operand bundles conservativelySanjoy Das2015-11-041-2/+3
| | | | | | | | | | | | | | | | | | | | | Summary: Earlier CaptureTracking would assume all "interesting" operands to a call or invoke were its arguments. With operand bundles this is no longer true. Note: an earlier change got `doesNotCapture` working correctly with operand bundles. This change uses DSE to test the changes to CaptureTracking. DSE is a vehicle for testing only, and is not directly involved in this change. Reviewers: reames, majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14306 llvm-svn: 252095
* PM: Rephrase PrintLoopPass as a wrapper around a new-style pass. NFCJustin Bogner2015-11-042-17/+23
| | | | | | | Splits PrintLoopPass into a new-style pass and a PrintLoopPassWrapper, much like we already do for PrintFunctionPass and PrintModulePass. llvm-svn: 252085
* [LVI] Update a comment to clarify what's actually happening and whyPhilip Reames2015-11-041-3/+22
| | | | llvm-svn: 252033
* [LAA] LLE 5/6: Add predicate functions Dependence::isForward/isBackward, NFCAdam Nemet2015-11-031-2/+22
| | | | | | | | | | | | Summary: Will be used by the LoopLoadElimination pass. Reviewers: hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13258 llvm-svn: 252016
* [LAA] LLE 3/6: Rename InterestingDependence to Dependences, NFCAdam Nemet2015-11-031-27/+21
| | | | | | | | | | | | | | Summary: We now collect all types of dependences including lexically forward deps not just "interesting" ones. Reviewers: hfinkel Subscribers: rengolin, llvm-commits Differential Revision: http://reviews.llvm.org/D13256 llvm-svn: 251985
* [LAA] LLE 2/6: Fix a NoDep case that should be a Forward dependenceAdam Nemet2015-11-031-1/+1
| | | | | | | | | | | | | | | | | | | | | Summary: When the dependence distance in zero then we have a loop-independent dependence from the earlier to the later access. No current client of LAA uses forward dependences so other than potentially hitting the MaxDependences threshold earlier, this change shouldn't affect anything right now. This and the previous patch were tested together for compile-time regression. None found in LNT/SPEC. Reviewers: hfinkel Subscribers: rengolin, llvm-commits Differential Revision: http://reviews.llvm.org/D13255 llvm-svn: 251973
* [LAA] LLE 1/6: Expose Forward dependencesAdam Nemet2015-11-031-13/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Before this change, we didn't use to collect forward dependences since none of the current clients (LV, LDist) required them. The motivation to also collect forward dependences is a new pass LoopLoadElimination (LLE) which discovers store-to-load forwarding opportunities across the loop's backedge. The pass uses both lexically forward or backward loop-carried dependences to detect these opportunities. The new pass also analyzes loop-independent (forward) dependences since they can conflict with the loop-carried dependences in terms of how the data flows through memory. The newly added test only covers loop-carried forward dependences because loop-independent ones are currently categorized as NoDep. The next patch will fix this. The two patches were tested together for compile-time regression. None found in LNT/SPEC. Note that with this change LAA provides all dependences rather than just "interesting" ones. A subsequent NFC patch will remove the now trivial isInterestingDependence and rename the APIs. Reviewers: hfinkel Subscribers: jmolloy, rengolin, llvm-commits Differential Revision: http://reviews.llvm.org/D13254 llvm-svn: 251972
* Fix PR25372 - teach replaceCongruentPHIs to handle cases where SE evaluates ↵Silviu Baranga2015-11-031-1/+14
| | | | | | | | | | | | | | | | | | | | | a PHI to a SCEVConstant Summary: Since now Scalar Evolution can create non-add rec expressions for PHI nodes, it can also create SCEVConstant expressions. This will confuse replaceCongruentPHIs, which previously relied on the fact that SCEV could not produce constants in this case. We will now replace the node with a constant in these cases - or avoid processing the Phi in case of a type mismatch. Reviewers: sanjoy Subscribers: llvm-commits, majnemer Differential Revision: http://reviews.llvm.org/D14230 llvm-svn: 251938
* TvOS: add missing support for some libcalls.Tim Northover2015-11-021-0/+7
| | | | llvm-svn: 251811
* [SCEV][LV] Add SCEV Predicates and use them to re-implement stride versioningSilviu Baranga2015-11-023-25/+209
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: SCEV Predicates represent conditions that typically cannot be derived from static analysis, but can be used to reduce SCEV expressions to forms which are usable for different optimizers. ScalarEvolution now has the rewriteUsingPredicate method which can simplify a SCEV expression using a SCEVPredicateSet. The normal workflow of a pass using SCEVPredicates would be to hold a SCEVPredicateSet and every time assumptions need to be made a new SCEV Predicate would be created and added to the set. Each time after calling getSCEV, the user will call the rewriteUsingPredicate method. We add two types of predicates SCEVPredicateSet - implements a set of predicates SCEVEqualPredicate - tests for equality between two SCEV expressions We use the SCEVEqualPredicate to re-implement stride versioning. Every time we version a stride, we will add a SCEVEqualPredicate to the context. Instead of adding specific stride checks, LoopVectorize now adds a more generic SCEV check. We only need to add support for this in the LoopVectorizer since this is the only pass that will do stride versioning. Reviewers: mzolotukhin, anemet, hfinkel, sanjoy Subscribers: sanjoy, hfinkel, rengolin, jmolloy, llvm-commits Differential Revision: http://reviews.llvm.org/D13595 llvm-svn: 251800
* [SCEV] Fix PR25369Sanjoy Das2015-11-021-27/+26
| | | | | | | | | | | | | Have `getConstantEvolutionLoopExitValue` work correctly with multiple entry loops. As far as I can tell, `getConstantEvolutionLoopExitValue` never did the right thing for multiple entry loops; and before r249712 it would silently return an incorrect answer. r249712 changed SCEV to fail an assert on a multiple entry loop, and this change fixes the underlying issue. llvm-svn: 251770
* [LibraryInfo] Point to FreeBSD HEAD repo and not to a dolphin branch.Davide Italiano2015-11-011-2/+2
| | | | | | The latter might go away (anytime soon). llvm-svn: 251765
* [SCEV] Don't create SCEV expressions that break LCSSASanjoy Das2015-10-311-0/+5
| | | | | | | | | | | | | Prevent `createNodeFromSelectLikePHI` from creating SCEV expressions that break LCSSA. A better fix for the same issue is to teach SCEVExpander to not break LCSSA by inserting PHI nodes at appropriate places. That's planned for the future. Fixes PR25360. llvm-svn: 251756
* [SCEV] Use auto and range for; NFCSanjoy Das2015-10-311-10/+7
| | | | llvm-svn: 251755
* [SCEV] Generalize the SCEV algorithm for creating expressions for PHI nodesSilviu Baranga2015-10-301-14/+77
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: When forming expressions for phi nodes having an incoming value from outside the loop A and a value coming from the previous iteration B we were forming an AddRec if: - B was an AddRec - the value A was equal to the value for B at iteration -1 (or equal to the value of B shifted by one iteration, at iteration 0) In this case, we were computing the expression to be the expression of B, shifted by one iteration. This changes generalizes the logic above by removing the restriction that B needs to be an AddRec. For this we introduce two expression rewriters that allow us to - shift an expression by one iteration - get the value of an expression at iteration 0 This allows us to get SCEV expressions for PHI nodes when these expressions are not AddRecExprs. Reviewers: sanjoy Subscribers: llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D14175 llvm-svn: 251700
* Fix an unused variable warning which broke the clang-cmake-mips builderPhilip Reames2015-10-291-1/+1
| | | | llvm-svn: 251614
* [LVI/CVP] Teach LVI about range metadataPhilip Reames2015-10-291-0/+26
| | | | | | | | | | | | | | Somewhat shockingly for an analysis pass which is computing constant ranges, LVI did not understand the ranges provided by range metadata. As part of this change, I included a change to CVP primarily because doing so made it much easier to write small self contained test cases. CVP was previously only handling the non-local operand case, but given that LVI can sometimes figure out information about instructions standalone, I don't see any reason to restrict this. There could possibly be a compile time impact from this, but I suspect it should be minimal. If anyone has an example which substaintially regresses, please let me know. I could restrict the block local handling to ICmps feeding Terminator instructions if needed. Note that this patch continues a somewhat bad practice in LVI. In many cases, we know facts about values, and separate context sensitive facts about values. LVI makes no effort to distinguish and will frequently cache the same value fact repeatedly for different contexts. I would like to change this, but that's a large enough change that I want it to go in separately with clear documentation of what's changing. Other examples of this include the non-null handling, and arguments. As a meta comment: the entire motivation of this change was being able to write smaller (aka reasonable sized) test cases for a future patch teaching LVI about select instructions. Differential Revision: http://reviews.llvm.org/D13543 llvm-svn: 251606
* [InstSimplify] sgt on i1s also encodes implicationPhilip Reames2015-10-291-0/+11
| | | | | | | | | | | | | | | Follow on to http://reviews.llvm.org/D13074, implementing something pointed out by Sanjoy. His truth table from his comment on that bug summarizes things well: LHS | RHS | LHS >=s RHS | LHS implies RHS 0 | 0 | 1 (0 >= 0) | 1 0 | 1 | 1 (0 >= -1) | 1 1 | 0 | 0 (-1 >= 0) | 0 1 | 1 | 1 (-1 >= -1) | 1 The key point is that an "i1 1" is the value "-1", not "1". Differential Revision: http://reviews.llvm.org/D13756 llvm-svn: 251597
* ARM: teach backend about WatchOS and TvOS libcalls.Tim Northover2015-10-281-2/+8
| | | | | | | The most substantial changes are again for watchOS: libcalls are hard-float if needed and sincos has a different calling convention. llvm-svn: 251571
* Revert "r251451 - [AliasSetTracker] Use mod/ref information for UnknownInstr"Hal Finkel2015-10-281-75/+39
| | | | | | | | | | | | | | | It looks like this broke the stage 2 builder: http://lab.llvm.org:8080/green/job/clang-stage2-configure-Rlto/6989/ Original commit message: AliasSetTracker does not need to convert the access mode to ModRefAccess if the new visited UnknownInst has only 'REF' modrefinfo to existing pointers in the sets. Patch by Andrew Zhogin! llvm-svn: 251562
* [SCEV] Compute max backedge count for loops with "shift ivs"Sanjoy Das2015-10-281-0/+149
| | | | | | | | | | | | | | This teaches SCEV to compute //max// backedge taken counts for loops like for (int i = k; i != 0; i >>>= 1) whatever(); SCEV yet cannot represent the exact backedge count for these loops, and this patch does not change that. This is really geared towards teaching SCEV that loops like the above are *not* infinite. llvm-svn: 251558
* [AliasAnalysis] Take into account readnone attribute for the function argumentsIgor Laevsky2015-10-281-0/+3
| | | | | | Differential Revision: http://reviews.llvm.org/D13992 llvm-svn: 251535
* WebAssembly: disable some loop-idiom recognitionJF Bastien2015-10-281-1/+3
| | | | | | | memset/memcpy aren't fully supported yet. We should invert this test once they are supported. llvm-svn: 251534
* [AliasAnalysis] Take into account readonly attribute for the function argumentsIgor Laevsky2015-10-281-0/+3
| | | | | | | | | | In getArgModRefInfo we consider all arguments as having MRI_ModRef. However for arguments marked with readonly attribute we can return more precise answer - MRI_Ref. Differential Revision: http://reviews.llvm.org/D13992 llvm-svn: 251525
* Put global classes into the appropriate namespace.Benjamin Kramer2015-10-282-0/+4
| | | | | | | Most of the cases belong into an anonymous namespace. No functionality change intended. llvm-svn: 251515
* [GlobalsAA] An indirect global that is initialized is not fair gameJames Molloy2015-10-281-1/+6
| | | | | | | | When checking if an indirect global (a global with pointer type) is only assigned by allocation functions, first check if the global is itself initialized. If it is, it's not only assigned by allocation functions. This fixes PR25309. Thanks to David Majnemer for reducing the test case! llvm-svn: 251508
* [ValueTracking] Expose `implies` via ValueTracking, NFCSanjoy Das2015-10-282-50/+42
| | | | | | | | | | | | Summary: This will allow a later patch to `JumpThreading` use this functionality. Reviewers: reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13971 llvm-svn: 251488
* [ValueTracking] Use !range metadata more aggressively in KnownBitsSanjoy Das2015-10-281-9/+15
| | | | | | | | | | | | | | Summary: Teach `computeKnownBitsFromRangeMetadata` to use `!range` metadata more aggressively. Reviewers: majnemer, nlewycky, jingyue Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14100 llvm-svn: 251487
* [AliasSetTracker] Use mod/ref information for UnknownInstrHal Finkel2015-10-271-39/+75
| | | | | | | | | | AliasSetTracker does not need to convert the access mode to ModRefAccess if the new visited UnknownInst has only 'REF' modrefinfo to existing pointers in the sets. Patch by Andrew Zhogin! llvm-svn: 251451
* [ScalarEvolutionExpander] PHI on a catchpad can be used on both edgesDavid Majnemer2015-10-271-11/+5
| | | | | | | | A PHI on a catchpad might be used by both edges out of the catchpad, feeding back into a loop. In this case, just use the insertion point. Anything more clever would require new basic blocks or PHI placement. llvm-svn: 251442
* [ScalarEvolutionExpander] Properly insert no-op casts + EH PadsDavid Majnemer2015-10-271-15/+40
| | | | | | | | | | | We want to insert no-op casts as close as possible to the def. This is tricky when the cast is of a PHI node and the BasicBlocks between the def and the use cannot hold any instructions. Iteratively walk EH pads until we hit a non-EH pad. This fixes PR25326. llvm-svn: 251393
* [ValueTracking] Don't special case wrapped ConstantRanges; NFCISanjoy Das2015-10-271-3/+1
| | | | | | | | | | | | | | | | | | | Use `getUnsignedMax` directly instead of special casing a wrapped ConstantRange. The previous code would have been "buggy" (and this would have been a semantic change) if LLVM allowed !range metadata to denote full ranges. E.g. in %val = load i1, i1* %ptr, !range !{i1 1, i1 1} ;; == full set ValueTracking would conclude that the high bit (IOW the only bit) in %val was zero. Since !range metadata does not allow empty or full ranges, this change is just a minor stylistic improvement. llvm-svn: 251380
* [SCEV] Refactor out ScalarEvolution::getDataLayout; NFCSanjoy Das2015-10-271-17/+13
| | | | llvm-svn: 251375
* Initialize BasicAAWrapperPass in it's constructorKeno Fischer2015-10-261-0/+4
| | | | | | | | | | | | Summary: This idiom is used elsewhere in LLVM, but was overlooked here. Reviewers: chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13628 llvm-svn: 251348
* Check the case that the numerator and denominator are both zeros when ↵Cong Hou2015-10-261-0/+10
| | | | | | | | getting edge probabilities in BPI and return 100% in this case. This issue is triggered in PGO mode when bootstrapping LLVM. It seems that it is not guaranteed that edge weights are always greater than zero which are read from profile data. llvm-svn: 251317
* [ValueTracking] Extend r251146 to catch a fairly common caseJames Molloy2015-10-261-2/+22
| | | | | | | | | | | | | Even though we may not know the value of the shifter operand, it's possible we know the shifter operand is non-zero. This can allow us to infer more known bits - for example: %1 = load %p !range {1, 5} %2 = shl %q, %1 We don't know %1, but we do know that it is nonzero so %2[0] is known zero, and importantly %2 is known non-zero. Calling isKnownNonZero is nontrivially expensive so use an Optional to run it lazily and cache its result. llvm-svn: 251294
* [ScalarEvolution] Throw away dead code.Davide Italiano2015-10-251-17/+0
| | | | llvm-svn: 251256
* [ScalarEvolution] Get rid of NDEBUG in header (correctly this time).Davide Italiano2015-10-251-0/+6
| | | | llvm-svn: 251255
* [ScalarEvolution] Get rid of NDEBUG in header.Davide Italiano2015-10-251-7/+0
| | | | llvm-svn: 251249
* Scalarizer for masked.gather and masked.scatter intrinsics.Elena Demikhovsky2015-10-251-0/+8
| | | | | | | | | | When the target does not support these intrinsics they should be converted to a chain of scalar load or store operations. If the mask is not constant, the scalarizer will build a chain of conditional basic blocks. I added isLegalMaskedGather() isLegalMaskedScatter() APIs. Differential Revision: http://reviews.llvm.org/D13722 llvm-svn: 251237
* Use all_of to simplify control flow. NFC.Benjamin Kramer2015-10-242-16/+4
| | | | llvm-svn: 251202
* Use find_if to simplify control flow. NFC.Benjamin Kramer2015-10-241-10/+5
| | | | llvm-svn: 251200
* [BasicAliasAnalysis] Simplify expression, no functional change.Benjamin Kramer2015-10-241-3/+2
| | | | | | (-1) - x + 1 is the same as -x. llvm-svn: 251185
* Extract out getConstantRangeFromMetadata; NFCSanjoy Das2015-10-243-51/+30
| | | | | | | | | | | | The loop idiom creating a ConstantRange is repeated twice in the codebase, time to give it a name and a home. The loop is also repeated in `rangeMetadataExcludesValue`, but using `getConstantRangeFromMetadata` there would not be an NFC -- the range returned by `getConstantRangeFromMetadata` may contain a value that none of the subranges did. llvm-svn: 251180
* Fix whitespace issues in two places; NFCSanjoy Das2015-10-242-3/+4
| | | | llvm-svn: 251179
* Handle non-constant shifts in computeKnownBits, and use computeKnownBits for ↵Hal Finkel2015-10-232-34/+122
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | constant folding in InstCombine/Simplify First, the motivation: LLVM currently does not realize that: ((2072 >> (L == 0)) >> 7) & 1 == 0 where L is some arbitrary value. Whether you right-shift 2072 by 7 or by 8, the lowest-order bit is always zero. There are obviously several ways to go about fixing this, but the generic solution pursued in this patch is to teach computeKnownBits something about shifts by a non-constant amount. Previously, we would give up completely on these. Instead, in cases where we know something about the low-order bits of the shift-amount operand, we can combine (and together) the associated restrictions for all shift amounts consistent with that knowledge. As a further generalization, I refactored all of the logic for all three kinds of shifts to have this capability. This works well in the above case, for example, because the dynamic shift amount can only be 0 or 1, and thus we can say a lot about the known bits of the result. This brings us to the second part of this change: Even when we know all of the bits of a value via computeKnownBits, nothing used to constant-fold the result. This introduces the necessary code into InstCombine and InstSimplify. I've added it into both because: 1. InstCombine won't automatically pick up the associated logic in InstSimplify (InstCombine uses InstSimplify, but not via the API that passes in the original instruction). 2. Putting the logic in InstCombine allows the resulting simplifications to become part of the iterative worklist 3. Putting the logic in InstSimplify allows the resulting simplifications to be used by everywhere else that calls SimplifyInstruction (inlining, unrolling, and many others). And this requires a small change to our definition of an ephemeral value so that we don't break the rest case from r246696 (where the icmp feeding the @llvm.assume, is also feeding a br). Under the old definition, the icmp would not be considered ephemeral (because it is used by the br), but this causes the assume to remove itself (in addition to simplifying the branch structure), and it seems more-useful to prevent that from happening. llvm-svn: 251146
* [SCEV] Fix stylistic issue in MatchBinaryAddToConst; NFCISanjoy Das2015-10-231-1/+1
| | | | | | | | | | Instead of checking `(FlagsPresent & ExpectedFlags) != 0`, check `(FlagsPresent & ExpectedFlags) == ExpectedFlags`. Right now they're equivalent since `ExpectedFlags` can only be either `FlagNUW` or `FlagNSW`, but if we ever pass in `ExpectedFlags` as `FlagNUW | FlagNSW` then checking `(FlagsPresent & ExpectedFlags) != 0` would be wrong. llvm-svn: 251142
* [BasicAA] Bugfix for r251016James Molloy2015-10-231-2/+8
| | | | | | | | If the loaded type sizes don't match the element type of the sequential type, all bets are off and the addresses may, indeed, overlap. Surprisingly, this just got caught in one test, on one builder, out of the 30+ builders testing this change. Congratulations go to http://lab.llvm.org:8011/builders/clang-aarch64-lnt/builds/5205. llvm-svn: 251112
OpenPOWER on IntegriCloud