summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Specify explicit storage type for AllocType. NFC.George Burgess IV2015-11-171-1/+1
| | | | llvm-svn: 253366
* [AliasAnalysis] CatchPad and CatchRet can modify escaped memoryDavid Majnemer2015-11-171-0/+26
| | | | | | | CatchPad and CatchRet behave a lot like function calls: they can potentially modify any memory which has been escaped. llvm-svn: 253323
* Fix a typo in BasicAliasAnalysisDavid Majnemer2015-11-171-1/+1
| | | | llvm-svn: 253322
* Move helper classes into anonymous namespaces. NFC.Benjamin Kramer2015-11-161-0/+4
| | | | llvm-svn: 253189
* Revert r252990.Akira Hatanaka2015-11-131-1/+10
| | | | | | Some of the buildbots are still failing. llvm-svn: 252999
* Provide a way to specify inliner's attribute compatibility and merging.Akira Hatanaka2015-11-131-10/+1
| | | | | | | | | | | | | | | | | | This reapplies r252949. I've changed the type of FuncName to be std::string instead of StringRef in emitFnAttrCompatCheck. Original commit message for r252949: Provide a way to specify inliner's attribute compatibility and merging rules using table-gen. NFC. This commit adds new classes CompatRule and MergeRule to Attributes.td, which are used to generate code to check attribute compatibility and merge attributes of the caller and callee. rdar://problem/19836465 llvm-svn: 252990
* Revert r252949.Akira Hatanaka2015-11-121-1/+10
| | | | | | It broke some of the bots including clang-x64-ninja-win7. llvm-svn: 252951
* Provide a way to specify inliner's attribute compatibility and mergingAkira Hatanaka2015-11-121-10/+1
| | | | | | | | | | | | rules using table-gen. NFC. This commit adds new classes CompatRule and MergeRule to Attributes.td, which are used to generate code to check attribute compatibility and merge attributes of the caller and callee. rdar://problem/19836465 llvm-svn: 252949
* Revert r243347 "Add TargetTransformInfo::isZExtFree."Sanjoy Das2015-11-121-4/+0
| | | | | | | | | | | r243347 was intended to support a change to LSR (r243348). That change to LSR has since had to be reverted (r243939) because it was buggy, and now the code added in r243347 is untested and unexercised. Given that, I think it is appropriate to revert r243347 for now, with the intent of adding it back in later if I get around to checking in a fixed version of r243348. llvm-svn: 252948
* [ValueTracking] Remove untested / unreachable code, NFCSanjoy Das2015-11-111-18/+5
| | | | | | | | Right now isTruePredicate is only ever called with Pred == ICMP_SLE or ICMP_ULE, and the ICMP_SLT and ICMP_ULT cases are dead. This change removes the untested dead code so that the function is not misleading. llvm-svn: 252676
* [ValueTracking] Teach isImpliedCondition a new bitwise trickSanjoy Das2015-11-101-0/+30
| | | | | | | | | | | | | | | | | | | Summary: This change teaches isImpliedCondition to prove things like (A | 15) < L ==> (A | 14) < L if the low 4 bits of A are known to be zero. Depends on D14391 Reviewers: majnemer, reames, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14392 llvm-svn: 252673
* [ValueTracking] Use m_APInt instead of m_ConstantInt, NFCSanjoy Das2015-11-101-7/+8
| | | | | | | | This change would add functionality if isImpliedCondition worked on vector types; but since it bail out on vector predicates this change is an NFC. llvm-svn: 252672
* [ValueTracking] Recognize that and(x, add (x, -1)) clears the low bitPhilip Reames2015-11-101-0/+16
| | | | | | | | | | This is a cleaned up version of a patch by John Regehr with permission. Originally found via the souper tool. If we add an odd number to x, then bitwise-and the result with x, we know that the low bit of the result must be zero. Either it was zero in x originally, or the add cleared it in the temporary value. As a result, one of the two values anded together must have the bit cleared. Differential Revision: http://reviews.llvm.org/D14315 llvm-svn: 252629
* Revert "Strip metadata when speculatively hoisting instructions"Renato Golin2015-11-101-7/+0
| | | | | | | This reverts commit r252604, as it broke all ARM and AArch64 buildbots, as well as some x86, et al. llvm-svn: 252623
* Strip metadata when speculatively hoisting instructionsIgor Laevsky2015-11-101-0/+7
| | | | | | | | | | | | | | | | This is fix for PR24059. When we are hoisting instruction above some condition it may turn out that metadata on this instruction was control dependant on the condition. This metadata becomes invalid and we need to drop it. This patch should cover most obvious places of speculative execution (which I have found by greping isSafeToSpeculativelyExecute). I think there are more cases but at least this change covers the severe ones. Differential Revision: http://reviews.llvm.org/D14398 llvm-svn: 252604
* Inliner: Do zero-cost inlines even if above a negative threshold (PR24851)Hans Wennborg2015-11-101-1/+1
| | | | | | Differential Revision: http://reviews.llvm.org/D14499 llvm-svn: 252595
* [TargetLibraryInfo] Add support for fls, flsl, flsll.Davide Italiano2015-11-091-0/+10
| | | | | | | | | This is a prerequisite for further optimisations of these functions, which will be commited as a separate patch. Differential Revision: http://reviews.llvm.org/D14219 llvm-svn: 252535
* [LoopVectorize] Address post-commit feedback on r250032James Molloy2015-11-091-19/+19
| | | | | | | | | | Implemented as many of Michael's suggestions as were possible: * clang-format the added code while it is still fresh. * tried to change Value* to Instruction* in many places in computeMinimumValueSizes - unfortunately there are several places where Constants need to be handled so this wasn't possible. * Reduce the pass list on loop-vectorization-factors.ll. * Fix a bug where we were querying MinBWs for I->getOperand(0) but using MinBWs[I]. llvm-svn: 252469
* ADT: Remove last implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-11-071-3/+3
| | | | | | | | | | Some implicit ilist iterator conversions have crept back into Analysis, Transforms, Hexagon, and llvm-stress. This removes them. I'll commit a patch immediately after this to disallow them (in a separate patch so that it's easy to revert if necessary). llvm-svn: 252371
* [ValueTracking] Add parameters to isImpliedCondition; NFCSanjoy Das2015-11-062-11/+25
| | | | | | | | | | | | | | | | Summary: This change makes the `isImpliedCondition` interface similar to the rest of the functions in ValueTracking (in that it takes a DataLayout, AssumptionCache etc.). This is an NFC, intended to make a later diff less noisy. Depends on D14369 Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14391 llvm-svn: 252333
* [ValueTracking] De-pessimize isImpliedCondition around unsigned comparesSanjoy Das2015-11-061-4/+4
| | | | | | | | | | | | | | | Summary: Currently `isImpliedCondition` will optimize "I +_nuw C < L ==> I < L" only if C is positive. This is an unnecessary restriction -- the implication holds even if `C` is negative. Reviewers: reames, majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14369 llvm-svn: 252332
* [ValueTracking] Add a framework for encoding implication rulesSanjoy Das2015-11-061-21/+67
| | | | | | | | | | | | | | | | | | | | | Summary: This change adds a framework for adding more smarts to `isImpliedCondition` around inequalities. Informally, `isImpliedCondition` will now try to prove "A < B ==> C < D" by proving "C <= A && B <= D", since then it follows "C <= A < B <= D". While this change is in principle NFC, I could not think of a way to not handle cases like "i +_nsw 1 < L ==> i < L +_nsw 1" (that ValueTracking did not handle before) while keeping the change understandable. I've added tests for these cases. Reviewers: reames, majnemer, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14368 llvm-svn: 252331
* Re-apply r251050 with a for PR25421Sanjoy Das2015-11-051-1/+58
| | | | | | | | | | | | | | | | | | | | | | | | | The bug: I missed adding break statements in the switch / case. Original commit message: [SCEV] Teach SCEV some axioms about non-wrapping arithmetic 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: 252236
* Revert r251050 to fix miscompile when running Clang -O1Richard Trieu2015-11-051-56/+1
| | | | | | | See bug for details: https://llvm.org/bugs/show_bug.cgi?id=25421 Some comparisons were incorrectly replaced with a constant value. llvm-svn: 252231
* 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
OpenPOWER on IntegriCloud