summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Factor out a loopHasNoAbnormalExits; NFCSanjoy Das2016-06-091-9/+8
| | | | llvm-svn: 272236
* [PM] Refector LoopAccessInfo analysis code Xinliang David Li2016-06-081-12/+11
| | | | | | | | This is the preparation patch to port the analysis to new PM Differential Revision: http://reviews.llvm.org/D20560 llvm-svn: 272194
* Apply most suggestions of clang-tidy's performance-unnecessary-value-paramBenjamin Kramer2016-06-085-14/+9
| | | | | | | Avoids unnecessary copies. All changes audited & pass tests with asan. No functional change intended. llvm-svn: 272190
* Attempt #2 to appease the buildbots.George Burgess IV2016-06-081-3/+3
| | | | | | | MSVC calls the copy ctor on StratifiedSets for some reason. So, undelete it. llvm-svn: 272184
* [SCEV] Break out of loop if there is no more work to doSanjoy Das2016-06-081-1/+1
| | | | | | | This is NFC as far as externally visible behavior is concerned, but will keep us from spinning in the worklist traversal algorithm unnecessarily. llvm-svn: 272182
* [SCEV] Track no-abnormal-exits instead of no-throw callsSanjoy Das2016-06-081-10/+10
| | | | | | | | | | | Absence of may-unwind calls is not enough to guarantee that a UB-generating use of an add-rec poison in the loop latch will actually cause UB. We also need to guard against calls that terminate the thread or infinite loop themselves. This partially addresses PR28012. llvm-svn: 272181
* Teach isGuarantdToTransferExecToSuccessor about debug info intrinsicsSanjoy Das2016-06-081-3/+6
| | | | | | Calls to `@llvm.dbg.*` can be assumed to terminate. llvm-svn: 272180
* Fix a bug in SCEV's poison value propagationSanjoy Das2016-06-081-12/+13
| | | | | | | | | | | | | The worklist algorithm introduced in rL271151 didn't check to see if the direct users of the post-inc add recurrence propagates poison. This change fixes the problem and makes the code structure more obvious. Note for release managers: correctness wise, this bug wasn't a regression introduced by rL271151 -- the behavior of SCEV around post-inc add recurrences was strictly improved (in terms of correctness) in rL271151. llvm-svn: 272179
* Try to appease buildbots.George Burgess IV2016-06-081-3/+8
| | | | | | | r272064 apparently made them angry. This undoes some changes made in r272064 (defaulting move ctors) to make them happy again. llvm-svn: 272173
* Avoid copies of std::strings and APInt/APFloats where we only read from itBenjamin Kramer2016-06-083-5/+5
| | | | | | | | As suggested by clang-tidy's performance-unnecessary-copy-initialization. This can easily hit lifetime issues, so I audited every change and ran the tests under asan, which came back clean. llvm-svn: 272126
* [CFLAA] Kill dead code/fix comments in StratifiedSets.George Burgess IV2016-06-071-87/+23
| | | | | | | | Also use default/delete instead of hand-written ctors. Thanks to Jia Chen for bringing this stuff up. llvm-svn: 272064
* [CFLAA] Add AttrEscaped, remove bit twiddling functions.George Burgess IV2016-06-072-63/+58
| | | | | | | | | | | | | | | | | | | | | This patch does a few things: - Unifies AttrAll and AttrUnknown (since they were used for more or less the same purpose anyway). - Introduces AttrEscaped, an attribute that notes that a value escapes our analysis for a given set, but not that an unknown value flows into said set. - Removes functions that take bit indices, since we also had functions that took bitsets, and the use of both (with similar names) was unclear and bug-prone. Patch by Jia Chen. Differential Revision: http://reviews.llvm.org/D21000 llvm-svn: 272040
* [LAA] Improve non-wrapping pointer detection by handling loop-invariant case.Andrey Turetskiy2016-06-071-4/+14
| | | | | | | | | | | | | This fixes PR26314. This patch adds new helper “isNoWrap” with detection of loop-invariant pointer case. Patch by Roman Shirokiy. Ref: https://llvm.org/bugs/show_bug.cgi?id=26314 Differential Revision: http://reviews.llvm.org/D17268 llvm-svn: 272014
* [LoopUnrollAnalyzer] Fix a crash in analyzeLoopUnrollCost.Michael Zolotukhin2016-06-061-3/+5
| | | | | | | | | | | In some cases, when simplifying with SCEV, we might consider pointer values as just usual integer values. Thus, we might get a different type from what we had originally in the map of simplified values, and hence we need to check types before operating on the values. This fixes PR28015. llvm-svn: 271931
* [LAA] Use load and store vectors (NFC)Matthew Simpson2016-06-061-11/+7
| | | | | | | Contributed-by: Aditya Kumar <hiraditya@msn.com> Differential Revision: http://reviews.llvm.org/D20953 llvm-svn: 271895
* [Analysis] Enabled BITREVERSE as a vectorizable intrinsicSimon Pilgrim2016-06-041-0/+1
| | | | | | Allows XOP to vectorize BITREVERSE - other targets will follow as their costmodels improve. llvm-svn: 271803
* Reapply r271728 after adding move cobstructor for ProfileSummaryInfoEaswaran Raman2016-06-032-0/+162
| | | | llvm-svn: 271745
* Revert r271728 as it breaks Windows buildEaswaran Raman2016-06-032-162/+0
| | | | llvm-svn: 271738
* Analysis pass to access profile summary infoEaswaran Raman2016-06-032-0/+162
| | | | | | Differential Revision: http://reviews.llvm.org/D20648 llvm-svn: 271728
* transform obscured FP sign bit ops into a fabs/fneg using TLI hookSanjay Patel2016-06-021-10/+2
| | | | | | | | | | | | | | | | | | | This is effectively a revert of: http://reviews.llvm.org/rL249702 - [InstCombine] transform masking off of an FP sign bit into a fabs() intrinsic call (PR24886) and: http://reviews.llvm.org/rL249701 - [ValueTracking] teach computeKnownBits that a fabs() clears sign bits and a reimplementation as a DAG combine for targets that have IEEE754-compliant fabs/fneg instructions. This is intended to resolve the objections raised on the dev list: http://lists.llvm.org/pipermail/llvm-dev/2016-April/098154.html and: https://llvm.org/bugs/show_bug.cgi?id=24886#c4 In the interest of patch minimalism, I've only partly enabled AArch64. PowerPC, MIPS, x86 and others can enable later. Differential Revision: http://reviews.llvm.org/D19391 llvm-svn: 271573
* Inline isDereferenceableFromAttribute; NFCSanjoy Das2016-06-021-19/+8
| | | | | | | | Now that `Value::getPointerDereferenceableBytes` looks beyond just attributes, the name `isDereferenceableFromAttribute` is misleading. Just inline the function, since it is small and only used once. llvm-svn: 271456
* Remove Value::isPointerDereferenceable; NFCISanjoy Das2016-06-021-11/+1
| | | | | | | | ... and merge into `Value::getPointerDereferenceableBytes`. This was suggested by Artur Pilipenko in D20764 -- since we no longer allow loads of unsized types, there is no need anymore to have this special logic. llvm-svn: 271455
* [SCEV] Keep SCEVExpander insert points consistent.Geoff Berry2016-06-011-35/+52
| | | | | | | | | | | | | | | | | | | | | Summary: Make sure that the SCEVExpander Builder insert point and any saved/restored insert points are kept consistent (i.e. their Instruction and BasicBlock match) when moving instructions in SCEVExpander. This fixes an issue triggered by http://reviews.llvm.org/D18001 [LSR] Create fewer redundant instructions. Test case will be added in reapply commit of above change: http://reviews.llvm.org/D18480 Reapply [LSR] Create fewer redundant instructions. Reviewers: sanjoy Subscribers: mzolotukhin, sanjoy, qcolombet, mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20703 llvm-svn: 271424
* Revert "Claim NoAlias if two GEPs index different fields of the same struct"Daniel Berlin2016-06-011-36/+2
| | | | | | This reverts commit 2d5d6493f43eb68493a3852b8c226ac9fafdc7eb. llvm-svn: 271422
* [CFLAA] Recognize builtin allocation functions.George Burgess IV2016-06-011-30/+55
| | | | | | | | | | | This patch extends CFLAA to recognize allocation functions such as malloc, free, etc, so we can treat them more aggressively. Patch by Jia Chen. Differential Revision: http://reviews.llvm.org/D20776 llvm-svn: 271421
* Claim NoAlias if two GEPs index different fields of the same structDaniel Berlin2016-06-011-2/+36
| | | | | | | | | | | | | | Patch by Taewook Oh Summary: Patch for Bug 27478. Make BasicAliasAnalysis claims NoAlias if two GEPs index different fields of the same structure. Reviewers: hfinkel, dberlin Subscribers: dberlin, mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20665 llvm-svn: 271415
* Reduce dependence on pointee types when deducing dereferenceabilitySanjoy Das2016-06-011-72/+35
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Change some of the internal interfaces in Loads.cpp to keep track of the number of bytes we're trying to prove dereferenceable using an explicit `Size` parameter. Before this, the `Size` parameter was implicitly inferred from the pointee type of the pointer whose dereferenceability we were trying to prove, causing us to be conservative around bitcasts. This was unfortunate since bitcast instructions are no-ops and should never break optimizations. With an explicit `Size` parameter, we're more precise (as shown in the test cases), and the code is simpler. We should eventually move towards a `DerefQuery` struct that groups together a base pointer, an offset, a size and an alignment; but this patch is a first step. Reviewers: apilipenko, dblaikie, hfinkel, reames Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20764 llvm-svn: 271406
* [CFLAA] Don't link GEP pointers to GEP indices.George Burgess IV2016-05-311-2/+0
| | | | | | | | | | | | | | | | | Code like the following is considered broken, and doesn't need to be supported by our AA magicks: void getFoo(int *P) { int *PAlias = (int *)((char *)NULL + (uintptr_t)P); } This patch makes CFLAA drop support for code like this. Patch by Jia Chen. Differential Revision: http://reviews.llvm.org/D20775 llvm-svn: 271322
* X86: permit using SjLj EH on x86 targets as an optionSaleem Abdulrasool2016-05-311-0/+2
| | | | | | | | | | | This adds support to the backed to actually support SjLj EH as an exception model. This is *NOT* the default model, and requires explicitly opting into it from the frontend. GCC supports this model and for MinGW can still be enabled via the `--using-sjlj-exceptions` options. Addresses PR27749! llvm-svn: 271244
* [SCEV] Consolidate comments; NFCSanjoy Das2016-05-291-240/+86
| | | | | | | Consolidate documentation by removing comments from the .cpp file where the comments in the .cpp file were copy-pasted from the header. llvm-svn: 271157
* [SCEV] Rename functions to LLVM style; NFCSanjoy Das2016-05-291-13/+13
| | | | llvm-svn: 271156
* [SCEV] See through op.with.overflow intrinsics (re-apply)Sanjoy Das2016-05-292-5/+110
| | | | | | | | | | | | | | | | | | | Summary: This change teaches SCEV to see reduce `(extractvalue 0 (op.with.overflow X Y))` into `op X Y` (with a no-wrap tag if possible). This was first checked in at r265912 but reverted in r265950 because it exposed some issues around how SCEV handled post-inc add recurrences. Those issues have now been fixed. Reviewers: atrick, regehr Subscribers: mcrosier, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D18684 llvm-svn: 271152
* [SCEV] Don't always add no-wrap flags to post-inc add recsSanjoy Das2016-05-291-7/+91
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Fixes PR27315. The post-inc version of an add recurrence needs to "follow the same rules" as a normal add or subtract expression. Otherwise we miscompile programs like ``` int main() { int a = 0; unsigned a_u = 0; volatile long last_value; do { a_u += 3; last_value = (long) ((int) a_u); if (will_add_overflow(a, 3)) { // Leave, and don't actually do the increment, so no UB. printf("last_value = %ld\n", last_value); exit(0); } a += 3; } while (a != 46); return 0; } ``` This patch changes SCEV to put no-wrap flags on post-inc add recurrences only when the poison from a potential overflow will go ahead to cause undefined behavior. To avoid regressing performance too much, I've assumed infinite loops without side effects is undefined behavior to prove poison<->UB equivalence in more cases. This isn't ideal, but is not new to LLVM as a whole, and far better than the situation I'm trying to fix. llvm-svn: 271151
* [ValueTracking] ICmp instructions propagate poisonSanjoy Das2016-05-291-0/+5
| | | | | | | This is a stripped down version of D19211, leaving out the questionable "branching in poison is UB" bit. llvm-svn: 271150
* [LoopUnrollAnalyzer] Add a comment to visitCastInst.Michael Zolotukhin2016-05-281-0/+6
| | | | llvm-svn: 271086
* Apply clang-tidy's misc-move-constructor-init throughout LLVM.Benjamin Kramer2016-05-271-1/+2
| | | | | | No functionality change intended, maybe a tiny performance improvement. llvm-svn: 270997
* [LoopUnrollAnalyzer] Bail out instead of dying with assert when facing huge ↵Michael Zolotukhin2016-05-271-2/+2
| | | | | | | | index. This fixes PR27902. llvm-svn: 270946
* [BasicAA] Extend inbound GEP negative offset logic to GlobalVariablesMichael Kuperstein2016-05-261-10/+18
| | | | | | | | | | | | | | r270777 improved the precision of alloca vs. inbounbds GEP alias queries: if we have (a) an inbounds GEP and (b) a pointer based on an alloca, and the beginning of the object the GEP points to would have a negative offset with respect to the alloca, then the GEP can not alias pointer (b). This makes the same logic fire when (b) is based on a GlobalVariable instead of an alloca. Differential Revision: http://reviews.llvm.org/D20652 llvm-svn: 270893
* [CaptureTracking] Volatile operations capture their memory locationDavid Majnemer2016-05-261-11/+36
| | | | | | | | | | The memory location that corresponds to a volatile operation is very special. They are observed by the machine in ways which we cannot reason about. Differential Revision: http://reviews.llvm.org/D20555 llvm-svn: 270879
* MemorySSA: Revert r269678 and r268068; replace with special casing in MemorySSA.Peter Collingbourne2016-05-261-9/+0
| | | | | | | | | | | | | It turns out that too many passes are relying on alias analysis results for control dependencies. Until we fix that by introducing a more accurate modelling of control dependencies, special case assume in MemorySSA instead. Also introduce tests to ensure we don't regress the FunctionAttrs or LICM passes. Differential Revision: http://reviews.llvm.org/D20658 llvm-svn: 270823
* [LazyValueInfo] Simplify `return after else`. NFCI.Davide Italiano2016-05-251-4/+3
| | | | llvm-svn: 270779
* [BasicAA] Improve precision of alloca vs. inbounds GEP alias queriesMichael Kuperstein2016-05-251-82/+120
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | If a we have (a) a GEP and (b) a pointer based on an alloca, and the beginning of the object the GEP points would have a negative offset with repsect to the alloca, then the GEP can not alias pointer (b). For example, consider code like: struct { int f0, int f1, ...} foo; ... foo alloca; foo *random = bar(alloca); int *f0 = &alloca.f0 int *f1 = &random->f1; Which is lowered, approximately, to: %alloca = alloca %struct.foo %random = call %struct.foo* @random(%struct.foo* %alloca) %f0 = getelementptr inbounds %struct, %struct.foo* %alloca, i32 0, i32 0 %f1 = getelementptr inbounds %struct, %struct.foo* %random, i32 0, i32 1 Assume %f1 and %f0 alias. Then %f1 would point into the object allocated by %alloca. Since the %f1 GEP is inbounds, that means %random must also point into the same object. But since %f0 points to the beginning of %alloca, the highest %f1 can be is (%alloca + 3). This means %random can not be higher than (%alloca - 1), and so is not inbounds, a contradiction. Differential Revision: http://reviews.llvm.org/D20495 llvm-svn: 270777
* Look for a loop's starting location in the llvm.loop metadataHal Finkel2016-05-251-0/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Getting accurate locations for loops is important, because those locations are used by the frontend to generate optimization remarks. Currently, optimization remarks for loops often appear on the wrong line, often the first line of the loop body instead of the loop itself. This is confusing because that line might itself be another loop, or might be somewhere else completely if the body was inlined function call. This happens because of the way we find the loop's starting location. First, we look for a preheader, and if we find one, and its terminator has a debug location, then we use that. Otherwise, we look for a location on an instruction in the loop header. The fallback heuristic is not bad, but will almost always find the beginning of the body, and not the loop statement itself. The preheader location search often fails because there's often not a preheader, and even when there is a preheader, depending on how it was formed, it sometimes carries the location of some preceeding code. I don't see any good theoretical way to fix this problem. On the other hand, this seems like a straightforward solution: Put the debug location in the loop's llvm.loop metadata. A companion Clang patch will cause Clang to insert llvm.loop metadata with appropriate locations when generating debugging information. With these changes, our loop remarks have much more accurate locations. Differential Revision: http://reviews.llvm.org/D19738 llvm-svn: 270771
* [TLI] Also cover Linux 64 libfunc (stat64, ...) prototype checking.Ahmed Bougacha2016-05-251-2/+2
| | | | | | My script missed those in r270750. llvm-svn: 270763
* [TLI] Fix NumParams==0 prototype checking typo.Ahmed Bougacha2016-05-251-57/+43
| | | | | | | | | | | | | There was a typo in r267758. It caused invalid accesses when given something like "void @free(...)", as NumParams == 0, and we then try to look at the 0th parameter. Turns out, most of these were untested; add both attribute and missing-prototype checks for all libc libfuncs. Differential Revision: http://reviews.llvm.org/D20543 llvm-svn: 270750
* [SCEV] No-wrap flags are not propagated when folding "{S,+,X}+T ==> {S+T,+,X}"Oleg Ranevskyy2016-05-251-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: **Description** This makes `WidenIV::widenIVUse` (IndVarSimplify.cpp) fail to widen narrow IV uses in some cases. The latter affects IndVarSimplify which may not eliminate narrow IV's when there actually exists such a possibility, thereby producing ineffective code. When `WidenIV::widenIVUse` gets a NarrowUse such as `{(-2 + %inc.lcssa),+,1}<nsw><%for.body3>`, it first tries to get a wide recurrence for it via the `getWideRecurrence` call. `getWideRecurrence` returns recurrence like this: `{(sext i32 (-2 + %inc.lcssa) to i64),+,1}<nsw><%for.body3>`. Then a wide use operation is generated by `cloneIVUser`. The generated wide use is evaluated to `{(-2 + (sext i32 %inc.lcssa to i64))<nsw>,+,1}<nsw><%for.body3>`, which is different from the `getWideRecurrence` result. `cloneIVUser` sees the difference and returns nullptr. This patch also fixes the broken LLVM tests by adding missing <nsw> entries introduced by the correction. **Minimal reproducer:** ``` int foo(int a, int b, int c); int baz(); void bar() { int arr[20]; int i = 0; for (i = 0; i < 4; ++i) arr[i] = baz(); for (; i < 20; ++i) arr[i] = foo(arr[i - 4], arr[i - 3], arr[i - 2]); } ``` **Clang command line:** ``` clang++ -mllvm -debug -S -emit-llvm -O3 --target=aarch64-linux-elf test.cpp -o test.ir ``` **Expected result:** The ` -mllvm -debug` log shows that all the IV's for the second `for` loop have been eliminated. Reviewers: sanjoy Subscribers: atrick, asl, aemerson, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D20058 llvm-svn: 270695
* [LoopUnrollAnalyzer] Fix a crash in UnrolledInstAnalyzer::visitCastInst.Michael Zolotukhin2016-05-241-5/+1
| | | | | | This fixes PR27847. Now for real. llvm-svn: 270629
* [ValueTracking, InstSimplify] extend isKnownNonZero() to handle vector constantsSanjay Patel2016-05-241-1/+14
| | | | | | | | | | | | | Similar in spirit to D20497 : If all elements of a constant vector are known non-zero, then we can say that the whole vector is known non-zero. It seems like we could extend this to FP scalar/vector too, but isKnownNonZero() says it only works for integers and pointers for now. Differential Revision: http://reviews.llvm.org/D20544 llvm-svn: 270562
* [LoopUnrollAnalyzer] Fix a crash in UnrolledInstAnalyzer::visitCastInst.Michael Zolotukhin2016-05-241-1/+6
| | | | | | This fixes PR27847. llvm-svn: 270517
* fix formatting; NFCSanjay Patel2016-05-231-4/+2
| | | | llvm-svn: 270465
OpenPOWER on IntegriCloud