summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [InstSimplify] Handle some overflow intrinsics in InstSimplifyDavid Majnemer2015-05-221-5/+43
| | | | | | | | | This change does a few things: - Move some InstCombine transforms to InstSimplify - Run SimplifyCall from within InstCombine::visitCallInst - Teach InstSimplify to fold [us]mul_with_overflow(X, undef) to 0. llvm-svn: 237995
* Revert r236894 "[BasicAA] Fix zext & sext handling"Hans Wennborg2015-05-221-199/+60
| | | | | | This seems to have caused PR23626: Clang miscompiles webkit's base64 decoder llvm-svn: 237984
* Test commit. Fix typo in MemDerefPrinter.cpp comment.Artur Pilipenko2015-05-211-1/+1
| | | | llvm-svn: 237893
* Reapply r237539 with a fix for the Chromium build.James Molloy2015-05-201-2/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Make sure if we're truncating a constant that would then be sign extended that the sign extension of the truncated constant is the same as the original constant. > Canonicalize min/max expressions correctly. > > This patch introduces a canonical form for min/max idioms where one operand > is extended or truncated. This often happens when the other operand is a > constant. For example: > > %1 = icmp slt i32 %a, i32 0 > %2 = sext i32 %a to i64 > %3 = select i1 %1, i64 %2, i64 0 > > Would now be canonicalized into: > > %1 = icmp slt i32 %a, i32 0 > %2 = select i1 %1, i32 %a, i32 0 > %3 = sext i32 %2 to i64 > > This builds upon a patch posted by David Majenemer > (https://www.marc.info/?l=llvm-commits&m=143008038714141&w=2). That pass > passively stopped instcombine from ruining canonical patterns. This > patch additionally actively makes instcombine canonicalize too. > > Canonicalization of expressions involving a change in type from int->fp > or fp->int are not yet implemented. llvm-svn: 237821
* Change Function::getIntrinsicID() to return an Intrinsic::ID. NFC.Pete Cooper2015-05-202-3/+3
| | | | | | | | Now that Intrinsic::ID is a typed enum, we can forward declare it and so return it from this method. This updates all users which were either using an unsigned to store it, or had a now unnecessary cast. llvm-svn: 237810
* Dereferenceable, dereferenceable_or_null metadata for loadsSanjoy Das2015-05-191-0/+13
| | | | | | | | | | | | | | | | | | | | Summary: Introduce dereferenceable, dereferenceable_or_null metadata for loads with the same semantic as corresponding attributes. This patch depends on http://reviews.llvm.org/D9253 Patch by Artur Pilipenko! Reviewers: hfinkel, sanjoy, reames Reviewed By: sanjoy, reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9365 llvm-svn: 237720
* Exploit dereferenceable_or_null attribute in LICM passSanjoy Das2015-05-181-17/+99
| | | | | | | | | | | | | | | | | | | | Summary: Allow hoisting of loads from values marked with dereferenceable_or_null attribute. For values marked with the attribute perform context-sensitive analysis to determine whether it's known-non-null or not. Patch by Artur Pilipenko! Reviewers: hfinkel, sanjoy, reames Reviewed By: reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9253 llvm-svn: 237593
* [ScalarEvolution] refactor: extract interface getGEPExprJingyue Wu2015-05-181-41/+55
| | | | | | | | | | | | | | | | | | Summary: This allows other passes (such as SLSR) to compute the SCEV expression for an imaginary GEP. Test Plan: no regression Reviewers: atrick, sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9786 llvm-svn: 237589
* [LoopAccesses] If shouldRetryWithRuntimeCheck, reset InterestingDependencesAdam Nemet2015-05-181-2/+7
| | | | | | | | When dependence analysis encounters a non-constant distance between memory accesses it aborts the analysis and falls back to run-time checks only. In this case we weren't resetting the array of dependences. llvm-svn: 237574
* [LoopAccesses] Rearrange printed lines in -analyzeAdam Nemet2015-05-181-4/+4
| | | | | | | "Store to invariant address..." is moved as the last line. This is not the prime result of the analysis. Plus it simplifies some of the tests. llvm-svn: 237573
* [LoopAccesses] Debug improvementAdam Nemet2015-05-181-0/+1
| | | | | | Report pointers with unknown bounds. llvm-svn: 237572
* Allow min/max detection to see through casts.James Molloy2015-05-151-14/+56
| | | | | | | | | | | | | | This teaches the min/max idiom detector in ValueTracking to see through casts such as SExt/ZExt/Trunc. SCEV can already do this, so we're bringing non-SCEV analyses up to the same level. The returned LHS/RHS will not match the type of the original SelectInst any more, so a CastOp is returned too to inform the caller how to convert to the SelectInst's type. No in-tree users yet; this will be used by InstCombine in a followup. llvm-svn: 237452
* [DependenceAnalysis] Fix for PR21585: collectUpperBound triggers assertsJames Molloy2015-05-151-2/+20
| | | | | | | | | | collectUpperBound hits an assertion when the back edge count is wider then the desired type. If that happens, truncate the backedge count. Patch by Philip Pfaffe! llvm-svn: 237439
* [ValueTracking] refactor: extract method haveNoCommonBitsSetJingyue Wu2015-05-141-0/+15
| | | | | | | | | | | | | | | | | | | | | Summary: Extract method haveNoCommonBitsSet so that we don't have to duplicate this logic in InstCombine and SeparateConstOffsetFromGEP. This patch also makes SeparateConstOffsetFromGEP more precise by passing DominatorTree to computeKnownBits. Test Plan: value-tracking-domtree.ll that tests ValueTracking indeed leverages dominating conditions Reviewers: broune, meheff, majnemer Reviewed By: majnemer Subscribers: jholewinski, llvm-commits Differential Revision: http://reviews.llvm.org/D9734 llvm-svn: 237407
* [ConstantFolding] Fix wrong folding of intrinsic 'convert.from.fp16'.Andrea Di Biagio2015-05-141-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Function 'ConstantFoldScalarCall' (in ConstantFolding.cpp) works under the wrong assumption that a call to 'convert.from.fp16' returns a value of type 'float'. However, intrinsic 'convert.from.fp16' can be overloaded; for example, we can call 'convert.from.fp16.f64' to convert from half to double; etc. Before this patch, the following example would have triggered an assertion failure in opt (with -constprop): ``` define double @foo() { entry: %0 = call double @llvm.convert.from.fp16.f64(i16 0) ret double %0 } ``` This patch fixes the problem in ConstantFolding.cpp. When folding a call to convert.from.fp16, we perform a different kind of conversion based on the call return type. Added test 'Transform/ConstProp/convert-from-fp16.ll'. Differential Revision: http://reviews.llvm.org/D9771 llvm-svn: 237377
* Add llvm::all_of which wraps std::all_of.Pete Cooper2015-05-131-5/+1
| | | | | | | | | | This version doesn't need begin/end but can instead just take a type which has begin/end methods. Use this to replace an eligible foreach loop in LoopInfo found by David Blaikie in r237224. Reviewed by David Blaikie. llvm-svn: 237301
* Test commit: Remove unnecessary spaces.Teresa Johnson2015-05-131-1/+1
| | | | llvm-svn: 237259
* Constify arguments in AliasSetTracker methods. NFCPete Cooper2015-05-131-4/+5
| | | | llvm-svn: 237225
* Change a loop in LoopInfo to foreach. NFCPete Cooper2015-05-131-2/+2
| | | | llvm-svn: 237224
* Constify arguments to methods in LoopInfo. NFCPete Cooper2015-05-131-3/+3
| | | | llvm-svn: 237223
* Convert PHI getIncomingValue() to foreach over incoming_values(). NFC.Pete Cooper2015-05-125-21/+15
| | | | | | | | We already had a method to iterate over all the incoming values of a PHI. This just changes all eligible code to use it. Ineligible code included anything which cared about the index, or was also trying to get the i'th incoming BB. llvm-svn: 237169
* Rip min/max pattern matching out of InstCombine and intoJames Molloy2015-05-111-0/+81
| | | | | | | | | | | ValueTracking. This matching functionality is useful in more than just InstCombine, so make it available in ValueTracking. NFC. llvm-svn: 236998
* [BasicAA] Fix zext & sext handlingSanjoy Das2015-05-081-60/+199
| | | | | | | | | | | | | | | | | | | | | | | Summary: There are several unhandled edge cases in BasicAA's GetLinearExpression method. This changes fixes outstanding issues, including zext / sext of a constant with the sign bit set, and the refusal to decompose zexts or sexts of wrapping arithmetic. Test Plan: Unit tests added in //q.ext.ll//. Patch by Nick White. Reviewers: hfinkel, sanjoy Reviewed By: hfinkel, sanjoy Subscribers: sanjoy, llvm-commits, hfinkel Differential Revision: http://reviews.llvm.org/D6682 llvm-svn: 236894
* Fix information loss in branch probability computation.Diego Novillo2015-05-071-12/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This addresses PR 22718. When branch weights are too large, they were being clamped to the range [1, MaxWeightForBB]. But this clamping is only applied to edges that go outside the range, so it distorts the relative branch probabilities. This patch changes the weight calculation to scale every branch so the relative probabilities are preserved. The scaling is done differently now. First, all the branch weights are added up, and if the sum exceeds 32 bits, it computes an integer scale to bring all the weights within the range. The patch fixes an existing test that had slightly wrong branch probabilities due to the previous clamping. It now gets branch weights scaled accordingly. Reviewers: dexonsmith Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9442 llvm-svn: 236750
* Populate list of vectorizable functions for Accelerate library.Michael Zolotukhin2015-05-071-4/+32
| | | | | | | | | | | | | | | | | | | Summary: This patch adds majority of supported by Accelerate library functions to the list of vectorizable functions. The full list of available vector functions could be found here: https://developer.apple.com/library/mac/documentation/Performance/Conceptual/vecLib/index.html Test Plan: Unit tests are added. Reviewers: hfinkel, aschwaighofer, nadav Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9543 llvm-svn: 236747
* Added support for building against Android API-9 SDKVince Harron2015-05-071-1/+1
| | | | | | | | | | Created an abstraction for log2, llvm::Log2 in Support/MathExtras.h Hid Android problems inside of it Differential Revision: http://reviews.llvm.org/D9467 llvm-svn: 236680
* Allow 0-weight branches in BranchProbabilityInfo.Diego Novillo2015-05-061-5/+7
| | | | | | | | | | | | | | | | | | | | | | | Summary: When computing branch weights in BPI, we used to disallow branches with weight 0. This is a minor nuisance, because a branch with weight 0 is different to "don't have information". In the context of instrumentation, it may mean "never executed", in the context of sampling, it means "never or seldom executed". In allowing 0 weight branches, I ran into issues with the switch expansion code in selection DAG. It is currently hardwired to not handle branches with weight 0. To maintain the current behaviour, I changed it to use 1 when it finds 0, but perhaps the algorithm needs changes to tolerate branches with weight zero. Reviewers: hansw Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9533 llvm-svn: 236617
* [X86] Disable loop unrolling in loop vectorization pass when VF is 1.Wei Mi2015-05-061-2/+2
| | | | | | | | | | | | | The patch disabled unrolling in loop vectorization pass when VF==1 on x86 architecture, by setting MaxInterleaveFactor to 1. Unrolling in loop vectorization pass may introduce the cost of overflow check, memory boundary check and extra prologue/epilogue code when regular unroller will unroll the loop another time. Disable it when VF==1 remove the unnecessary cost on x86. The same can be done for other platforms after verifying interleaving/memory bound checking to be not perf critical on those platforms. Differential Revision: http://reviews.llvm.org/D9515 llvm-svn: 236613
* [Statepoint] Clean up Statepoint.h: accessor names.Sanjoy Das2015-05-061-1/+2
| | | | | | Use getFoo() as accessors consistently and some other naming changes. llvm-svn: 236564
* Update BasicAliasAnalysis to understand that nothing aliases with undef values.Daniel Berlin2015-05-051-0/+5
| | | | | | | | | | It got this in some cases (if one of them was an identified object), but not in all cases. This caused stores to undef to block load-forwarding in some cases, etc. Added test to Transforms/GVN to verify optimization occurs as expected. llvm-svn: 236511
* Fix -Wpessimizing-move warnings by removing std::move calls.Richard Trieu2015-04-301-1/+1
| | | | llvm-svn: 236278
* [WinEH] Start EH preparation for 32-bit x86, it uses no argumentsReid Kleckner2015-04-291-2/+2
| | | | | | | | | | | | | | | | | | 32-bit x86 MSVC-style exceptions are functionaly similar to 64-bit, but they take no arguments. Instead, they implicitly use the value of EBP passed in by the caller as a pointer to the parent's frame. In LLVM, we can represent this as llvm.frameaddress(1), and feed that into all of our calls to llvm.framerecover. The next steps are: - Add an alloca to the fs:00 linked list of handlers - Add something like llvm.sjlj.lsda or generalize it to store in the alloca - Move state number calculation to WinEHPrepare, arrange for FunctionLoweringInfo to call it - Use the state numbers to insert explicit loads and stores in the IR llvm-svn: 236172
* IR: Give 'DI' prefix to debug info metadataDuncan P. N. Exon Smith2015-04-291-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Finish off PR23080 by renaming the debug info IR constructs from `MD*` to `DI*`. The last of the `DIDescriptor` classes were deleted in r235356, and the last of the related typedefs removed in r235413, so this has all baked for about a week. Note: If you have out-of-tree code (like a frontend), I recommend that you get everything compiling and tests passing with the *previous* commit before updating to this one. It'll be easier to keep track of what code is using the `DIDescriptor` hierarchy and what you've already updated, and I think you're extremely unlikely to insert bugs. YMMV of course. Back to *this* commit: I did this using the rename-md-di-nodes.sh upgrade script I've attached to PR23080 (both code and testcases) and filtered through clang-format-diff.py. I edited the tests for test/Assembler/invalid-generic-debug-node-*.ll by hand since the columns were off-by-three. It should work on your out-of-tree testcases (and code, if you've followed the advice in the previous paragraph). Some of the tests are in badly named files now (e.g., test/Assembler/invalid-mdcompositetype-missing-tag.ll should be 'dicompositetype'); I'll come back and move the files in a follow-up commit. llvm-svn: 236120
* Make getModRefInfo(Instruction *) not crash on certain types of instructionsDaniel Berlin2015-04-281-10/+13
| | | | llvm-svn: 236023
* Fix typo in comment.Diego Novillo2015-04-241-1/+1
| | | | llvm-svn: 235723
* [getUnderlyingOjbects] Analyze loop PHIs further to remove false positivesAdam Nemet2015-04-232-11/+57
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Specifically, if a pointer accesses different underlying objects in each iteration, don't look through the phi node defining the pointer. The motivating case is the underlyling-objects-2.ll testcase. Consider the loop nest: int **A; for (i) for (j) A[i][j] = A[i-1][j] * B[j] This loop is transformed by Load-PRE to stash away A[i] for the next iteration of the outer loop: Curr = A[0]; // Prev_0 for (i: 1..N) { Prev = Curr; // Prev = PHI (Prev_0, Curr) Curr = A[i]; for (j: 0..N) Curr[j] = Prev[j] * B[j] } Since A[i] and A[i-1] are likely to be independent pointers, getUnderlyingObjects should not assume that Curr and Prev share the same underlying object in the inner loop. If it did we would try to dependence-analyze Curr and Prev and the analysis of the corresponding SCEVs would fail with non-constant distance. To fix this, the getUnderlyingObjects API is extended with an optional LoopInfo parameter. This is effectively what controls whether we want the above behavior or the original. Currently, I only changed to use this approach for LoopAccessAnalysis. The other testcase is to guard the opposite case where we do want to look through the loop PHI. If we step through an array by incrementing a pointer, the underlying object is the incoming value of the phi as the loop is entered. Fixes rdar://problem/19566729 llvm-svn: 235634
* Move Value.isDereferenceablePointer to ValueTracking [NFC]Philip Reames2015-04-232-2/+143
| | | | | | | | | | | Move isDereferenceablePointer function to Analysis. This function recursively tracks dereferencability over a chain of values like other functions in ValueTracking. This refactoring is motivated by further changes to support dereferenceable_or_null attribute (http://reviews.llvm.org/D8650). isDereferenceablePointer will be extended to perform context-sensitive analysis and IR is not a good place to have such functionality. Patch by: Artur Pilipenko <apilipenko@azulsystems.com> Differential Revision: reviews.llvm.org/D9075 llvm-svn: 235611
* Fix a type mismatch assert in SCEV divisionBrendon Cahoon2015-04-221-0/+8
| | | | | | | | | | | | An assert was triggered when attempting to create a new SCEV with operands of different types in the visitAddRecExpr. In this test case, the operand types of the numerator and denominator are different. The SCEV division code should generate a conservative answer when this happens. Differential Revision: http://reviews.llvm.org/D9021 llvm-svn: 235511
* Revamp PredIteratorCache interface to be cleaner.Daniel Berlin2015-04-211-14/+11
| | | | | | | | | | | | | Summary: This lets us use range based for loops. Reviewers: chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9169 llvm-svn: 235416
* Move IDF Calculation to a separate file, expose an interface to it.Daniel Berlin2015-04-212-0/+96
| | | | | | | | | | | | | | | Summary: MemorySSA uses this algorithm as well, and this enables us to reuse the code in both places. There are no actual algorithm or datastructure changes in here, just code movement. Reviewers: qcolombet, chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9118 llvm-svn: 235406
* DebugInfo: Drop rest of DIDescriptor subclassesDuncan P. N. Exon Smith2015-04-211-1/+1
| | | | | | | Delete the remaining subclasses of (the already deleted) `DIDescriptor`. Part of PR23080. llvm-svn: 235404
* Recognize n/1 in the SCEV divide functionBrendon Cahoon2015-04-201-0/+7
| | | | | | | | | | | | n/1 generates a quotient equal to n and a remainder of 0. If this case is not recognized, then the SCEV divide() function can return a remainder that is greater than or equal to the denominator, which means the delinearized subscripts for the test case will be incorrect. Differential Revision: http://reviews.llvm.org/D9003 llvm-svn: 235311
* [LoopAccesses] Improve debug outputAdam Nemet2015-04-171-4/+8
| | | | llvm-svn: 235238
* DebugInfo: Gut DIType and subclassesDuncan P. N. Exon Smith2015-04-161-11/+11
| | | | | | | | Continuing PR23080, gut `DIType` and its various subclasses, leaving behind thin wrappers around the pointer types in the new debug info hierarchy. llvm-svn: 235064
* DebugInfo: Gut DICompileUnit and DIFileDuncan P. N. Exon Smith2015-04-151-4/+4
| | | | | | | Continuing gutting `DIDescriptor` subclasses; this edition, `DICompileUnit` and `DIFile`. In the name of PR23080. llvm-svn: 235055
* One more -Wrange-loop-analysis cleanup.Richard Trieu2015-04-151-1/+1
| | | | llvm-svn: 235044
* Add range iterators for post order and inverse post order. Use themDaniel Berlin2015-04-151-12/+10
| | | | llvm-svn: 235026
* Re-apply r234898 and fix tests.Daniel Jasper2015-04-151-0/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit makes LLVM not estimate branch probabilities when doing a single bit bitmask tests. The code that originally made me discover this is: if ((a & 0x1) == 0x1) { .. } In this case we don't actually have any branch probability information and should not assume to have any. LLVM transforms this into: %and = and i32 %a, 1 %tobool = icmp eq i32 %and, 0 So, in this case, the result of a bitwise and is compared against 0, but nevertheless, we should not assume to have probability information. CodeGen/ARM/2013-10-11-select-stalls.ll started failing because the changed probabilities changed the results of ARMBaseInstrInfo::isProfitableToIfCvt() and led to an Ifcvt of the diamond in the test. AFAICT, the test was never meant to test this and thus changing the test input slightly to not change the probabilities seems like the best way to preserve the meaning of the test. llvm-svn: 234979
* Change range-based for-loops to be -Wrange-loop-analysis clean.Richard Trieu2015-04-151-1/+1
| | | | | | No functionality change. llvm-svn: 234963
* [Inliner] Don't inline functions with frameescape callsReid Kleckner2015-04-141-8/+19
| | | | | | | | | | | Inlining such intrinsics is very difficult, since you need to simultaneously transform many calls to llvm.framerecover and potentially duplicate the functions containing them. Normally this intrinsic isn't added until EH preparation, which is part of the backend pass pipeline after inlining. However, if it were to get fed through the inliner, this change will ensure that it doesn't break the code. llvm-svn: 234937
OpenPOWER on IntegriCloud