summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* 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
* use 'auto' with 'dyn_cast'; fix formatting; NFCSanjay Patel2016-05-221-10/+8
| | | | llvm-svn: 270370
* [ValueTracking, InstCombine] extend isKnownToBeAPowerOfTwo() to handle ↵Sanjay Patel2016-05-221-3/+4
| | | | | | | | | | | | | | vector splat constants We could try harder to handle non-splat vector constants too, but that seems much rarer to me. Note that the div test isn't resolved because there's a check for isIntegerTy() guarding that transform. Differential Revision: http://reviews.llvm.org/D20497 llvm-svn: 270369
* Revert r270268 due to unused variable warnings.Michael Kuperstein2016-05-201-12/+17
| | | | llvm-svn: 270272
* [BasicAA] Turn DecomposeGEPExpression runtime checks into asserts.Michael Kuperstein2016-05-201-17/+12
| | | | | | | | When it has a DataLayout, DecomposeGEPExpression() should return the same object as GetUnderlyingObject(). Per the FIXME, it currently always has a DL, so the runtime check is redundant and can become an assert. llvm-svn: 270268
* Allow -inline-threshold to override default threshold.Easwaran Raman2016-05-191-4/+7
| | | | | | | | Before r257832, the threshold used by SimpleInliner was explicitly specified or generated from opt levels and passed to the base class Inliner's constructor. There, it was first overridden by explicitly specified -inline-threshold. The refactoring in r257832 did not preserve this behavior for all opt levels. This change brings back the original behavior. Differential Revision: http://reviews.llvm.org/D20452 llvm-svn: 270153
* [LAA] Check independence of strided accesses before forward caseMatthew Simpson2016-05-191-10/+11
| | | | | | | | | | | | This patch changes the order in which we attempt to prove the independence of strided accesses. We previously did this after we knew the dependence distance was positive. With this change, we check for independence before handling the negative distance case. The patch prevents LAA from reporting forward dependences for independent strided accesses. This change was requested in the review of D19984. llvm-svn: 270072
* [SCEV] Be more aggressive in proving NUWSanjoy Das2016-05-171-7/+20
| | | | | | | | | | ... for AddRec's in loops for which SCEV is unable to compute a max tripcount. This is the NUW variant of r269211 and fixes PR27691. (Note: PR27691 is not a correct or stability bug, it was created to track a pending task). llvm-svn: 269790
* [BasicAA] Update comments based on feedback from hfinkel. NFCI.Geoff Berry2016-05-161-1/+4
| | | | | | | Original change Hal's comments were based on: http://reviews.llvm.org/D19730 llvm-svn: 269678
* [LAA] Rename forwarding conflict detection option (NFC)Matthew Simpson2016-05-161-6/+6
| | | | | | | This patch renames the option enabling the store-to-load forwarding conflict detection optimization. This change was requested in the review of D20241. llvm-svn: 269668
* [LAA] Comment couldPreventStoreLoadForward. NFCAdam Nemet2016-05-161-2/+8
| | | | | | | Also s/Cycles/Iters/ in NumCyclesForStoreLoadThroughMemory to make it clear that this is not about clock cycles but loop cycles/iterations. llvm-svn: 269667
* [LAA] clang-format the function couldPreventStoreLoadForward. NFCAdam Nemet2016-05-161-9/+9
| | | | llvm-svn: 269666
* [LAA] Add option to disable conflict detection (NFC)Matthew Simpson2016-05-161-2/+9
| | | | llvm-svn: 269654
* [LAA] Include MaxSafeDepDistBytes in the analysis print-outAdam Nemet2016-05-131-0/+3
| | | | llvm-svn: 269508
* [LAA] Prepare the code to print more things in the summary. NFCAdam Nemet2016-05-131-3/+3
| | | | llvm-svn: 269507
* Revert "Revert "[Unroll] Implement a conservative and monotonically ↵Michael Zolotukhin2016-05-131-0/+10
| | | | | | | | | | increasing cost tracking system during the full unroll heuristic analysis that avoids counting any instruction cost until that instruction becomes "live" through a side-effect or use outside the..."" This reverts commit r269395. Try to reapply with a fix from chapuni. llvm-svn: 269486
* [scan-build] fix warnings emiited on LLVM Analysis code baseSilviu Baranga2016-05-132-24/+26
| | | | | | | | | | | | Fix "Logic error" warnings of the type "Called C++ object pointer is null" reported by Clang Static Analyzer on the following files: lib/Analysis/ScalarEvolution.cpp, lib/Analysis/LoopInfo.cpp. Patch by Apelete Seketeli! llvm-svn: 269424
* Revert "[Unroll] Implement a conservative and monotonically increasing cost ↵Michael Zolotukhin2016-05-131-10/+0
| | | | | | | | | | | tracking system during the full unroll heuristic analysis that avoids counting any instruction cost until that instruction becomes "live" through a side-effect or use outside the..." This reverts commit r269388. It caused some bots to fail, I'm reverting it until I investigate the issue. llvm-svn: 269395
* [Unroll] Implement a conservative and monotonically increasing cost tracking ↵Michael Zolotukhin2016-05-131-0/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | system during the full unroll heuristic analysis that avoids counting any instruction cost until that instruction becomes "live" through a side-effect or use outside the... Summary: ...loop after the last iteration. This is really hard to do correctly. The core problem is that we need to model liveness through the induction PHIs from iteration to iteration in order to get the correct results, and we need to correctly de-duplicate the common subgraphs of instructions feeding some subset of the induction PHIs. All of this can be driven either from a side effect at some iteration or from the loop values used after the loop finishes. This patch implements this by storing the forward-propagating analysis of each instruction in a cache to recall whether it was free and whether it has become live and thus counted toward the total unroll cost. Then, at each sink for a value in the loop, we recursively walk back through every value that feeds the sink, including looping back through the iterations as needed, until we have marked the entire input graph as live. Because we cache this, we never visit instructions more than twice -- once when we analyze them and put them into the cache, and once when we count their cost towards the unrolled loop. Also, because the cache is only two bits and because we are dealing with relatively small iteration counts, we can store all of this very densely in memory to avoid this from becoming an excessively slow analysis. The code here is still pretty gross. I would appreciate suggestions about better ways to factor or split this up, I've stared too long at the algorithmic side to really have a good sense of what the design should probably look at. Also, it might seem like we should do all of this bottom-up, but I think that is a red herring. Specifically, the simplification power is *much* greater working top-down. We can forward propagate very effectively, even across strange and interesting recurrances around the backedge. Because we use data to propagate, this doesn't cause a state space explosion. Doing this level of constant folding, etc, would be very expensive to do bottom-up because it wouldn't be until the last moment that you could collapse everything. The current solution is essentially a top-down simplification with a bottom-up cost accounting which seems to get the best of both worlds. It makes the simplification incremental and powerful while leaving everything dead until we *know* it is needed. Finally, a core property of this approach is its *monotonicity*. At all times, the current UnrolledCost is a conservatively low estimate. This ensures that we will never early-exit from the analysis due to exceeding a threshold when if we had continued, the cost would have gone back below the threshold. These kinds of bugs can cause incredibly hard to track down random changes to behavior. We could use a techinque similar (but much simpler) within the inliner as well to avoid considering speculated code in the inline cost. Reviewers: chandlerc Subscribers: sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D11758 llvm-svn: 269388
* [LoopUnrollAnalyzer] Don't treat gep-instructions with simplified offset as ↵Michael Zolotukhin2016-05-131-1/+1
| | | | | | | | | | | | | | | | | | simplified. Summary: Currently we consider such instructions as simplified, which is incorrect, because if their user isn't simplified, we can't actually simplify them too. This biases our estimates of profitability: for instance the analyzer expects much more gains from unrolling memcpy loops than there actually are. Reviewers: hfinkel, chandlerc Subscribers: mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D17365 llvm-svn: 269387
* [PM] Port of the DepndenceAnalysis to the new PM.Chandler Carruth2016-05-122-228/+173
| | | | | | | | | | | | | Ported DA to the new PM by splitting the former DependenceAnalysis Pass into a DependenceInfo result type and DependenceAnalysisWrapperPass type and adding a new PM-style DependenceAnalysis analysis pass returning the DependenceInfo. Patch by Philip Pfaffe, most of the review by Justin. Differential Revision: http://reviews.llvm.org/D18834 llvm-svn: 269370
OpenPOWER on IntegriCloud