summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* [LAA] Use std::min. NFCAdam Nemet2016-05-121-4/+2
| | | | llvm-svn: 269356
* [SCEVExpander] Fix a failed cast<> assertionSanjoy Das2016-05-111-43/+47
| | | | | | | | | SCEVExpander::replaceCongruentIVs assumes the backedge value of an SCEV-analysable PHI to always be an instruction, when this is not necessarily true. For now address this by bailing out of the optimization if the backedge value of the PHI is a non-Instruction. llvm-svn: 269213
* [SCEVExpander] Don't break SSA in replaceCongruentIVsSanjoy Das2016-05-111-2/+1
| | | | | | | | | | | | `SCEVExpander::replaceCongruentIVs` bypasses `hoistIVInc` if both the original and the isomorphic increments are PHI nodes. Doing this can break SSA if the isomorphic increment is not dominated by the original increment. Get rid of the bypass, and let `hoistIVInc` do the right thing. Fixes PR27232 (compile time crash/hang). llvm-svn: 269212
* [SCEV] Be more aggressive around proving no-wrapSanjoy Das2016-05-111-4/+17
| | | | | | | | | | | | | | | ... for AddRec's in loops for which SCEV is unable to compute a max tripcount. This is not a problem for "normal" loops[0] that don't have guards or assumes, but helps in cases where we have guards or assumes in the loop that can be used to constrain incoming values over the backedge. This partially fixes PR27691 (we still don't handle the NUW case). [0]: for "normal" loops, in the cases where we'd be able to prove no-wrap via isKnownPredicate, we'd also be able to compute a max tripcount. llvm-svn: 269211
* [BasicAA] Compare GEP indices based on value (Fix PR27418)Vedant Kumar2016-05-111-1/+1
| | | | | | | | | | | | Equivalent GEP indices with different types are treated as different indices altogether, leading to an incorrect AA result. Fix the issue by comparing indices based on their values. Thanks to Mikael Holmén for reporting the issue! Differential Revision: http://reviews.llvm.org/D19935 llvm-svn: 269197
* NFC. Introduce Value::isPointerDereferenceableArtur Pilipenko2016-05-111-12/+5
| | | | | | | | | | Extract a part of isDereferenceableAndAlignedPointer functionality to Value: Reviewed By: hfinkel, sanjoy Differential Revision: http://reviews.llvm.org/D17611 llvm-svn: 269190
* Revert r269131Easwaran Raman2016-05-102-5/+3
| | | | llvm-svn: 269138
* Reapply r266477 and r266488Easwaran Raman2016-05-102-3/+5
| | | | llvm-svn: 269131
* [InstSimplify] use computeKnownBits on shift amount operandsSanjay Patel2016-05-101-0/+16
| | | | | | | | | | | | | | Do simplifications common to all shift instructions based on the amount shifted: 1. If the shift amount is known larger than the bitwidth, the result is undefined. 2. If the valid bits of the shift amount are all known to be 0, it's a shift by zero, so the shift operand is the result. Note that we could generalize the shift-by-zero transform into a shift-by-constant if all of the valid bits in the shift amount are known, but that would have to be done in InstCombine rather than here because it would mean we need to create a new shift instruction. Differential Revision: http://reviews.llvm.org/D19874 llvm-svn: 269114
* Re-apply r269081 and r269082 with a fix for MSVC.Peter Collingbourne2016-05-102-0/+83
| | | | llvm-svn: 269094
* Revert r269081 and r269082 while I try to find the right incantation to fix ↵Peter Collingbourne2016-05-102-83/+0
| | | | | | MSVC build. llvm-svn: 269091
* WholeProgramDevirt: Move logic for finding devirtualizable call sites to ↵Peter Collingbourne2016-05-102-0/+83
| | | | | | | | | | | | | Analysis. The plan is to eventually make this logic simpler, however I expect it to be a little tricky for the foreseeable future (at least until we're rid of pointee types), so move it here so that it can be reused to build a summary index for devirtualization. Differential Revision: http://reviews.llvm.org/D20005 llvm-svn: 269081
* [LAA] Use re-written SCEV expressions when computing distancesSilviu Baranga2016-05-101-7/+2
| | | | | | | | | | | | This removes a redundant stride versioning step (we already do it in getPtrStride, so it has no effect) and uses PSE to get the SCEV expressions for the source and destination (this might have changed when getPtrStride was called). I discovered this through code inspection, and couldn't produce a regression test for it. llvm-svn: 269052
* Revert "[VectorUtils] Query number of sign bits to allow more truncations"James Molloy2016-05-101-14/+4
| | | | | | | | This was a fairly simple patch but on closer inspection was seriously flawed and caused PR27690. This reverts commit r268921. llvm-svn: 269051
* [LAA] Rename "isStridedPtr" with "getPtrStride". NFC.Denis Zobnin2016-05-101-5/+5
| | | | | | | Changing misleading function name was approved in http://reviews.llvm.org/D17268. Patch by Roman Shirokiy. llvm-svn: 269021
* [ValueTracking] Use guards to prove non-nullness of a valueSanjoy Das2016-05-101-9/+11
| | | | | | | | | | Reviewers: apilipenko, majnemer, reames Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20044 llvm-svn: 269008
* [BasicAA] Guard intrinsics don't write to memorySanjoy Das2016-05-101-4/+32
| | | | | | | | | | | | | | | | Summary: The idea is very close to what we do for assume intrinsics: we mark the guard intrinsics as writing to arbitrary memory to maintain control dependence, but under the covers we teach AA that they do not mod any particular memory location. Reviewers: chandlerc, hfinkel, gbiv, reames Subscribers: george.burgess.iv, mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D19575 llvm-svn: 269007
* [SCEVExpander] Clang format expressions; NFCSanjoy Das2016-05-101-17/+16
| | | | | | The boolean expressions are somewhat hard to read otherwise. llvm-svn: 268998
* [SCEV] Use guards to prove predicatesSanjoy Das2016-05-101-3/+44
| | | | | | | | | We can use calls to @llvm.experimental.guard to prove predicates, relying on the fact that in all locations domianted by a call to @llvm.experimental.guard the predicate it is guarding is known to be true. llvm-svn: 268997
* [LV] Hint at the new loop distribution pragma in optimization remarkAdam Nemet2016-05-091-2/+6
| | | | | | | | | | When we encounter unsafe memory dependencies, loop distribution could help. Even though, the diagnostics is in LAA, it's only currently emitted in the vectorizer. llvm-svn: 268987
* [Inliner] don't assume that a Constant alloca size is a ConstantInt (PR27277)Sanjay Patel2016-05-091-4/+4
| | | | | | Differential Revision: http://reviews.llvm.org/D20077 llvm-svn: 268980
* DivergenceAnalysis: Fix crash with no return blocksMatt Arsenault2016-05-091-1/+7
| | | | | | The post dominator tree does not have a root node in this case. llvm-svn: 268933
* fix spelling; NFCSanjay Patel2016-05-091-2/+2
| | | | llvm-svn: 268929
* [VectorUtils] Query number of sign bits to allow more truncationsJames Molloy2016-05-091-4/+14
| | | | | | When deciding if a vector calculation can be done in a smaller bitwidth, use sign bit information from ValueTracking to add more information and allow more truncations. llvm-svn: 268921
* [X86] Promote several single precision FP libcalls on WindowsDavid Majnemer2016-05-081-0/+2
| | | | | | | | | | | | A number of libcalls don't exist in any particular lib but are, instead, defined in math.h as inline functions (even in C mode!). Don't rely on their existence when lowering @llvm.{cos,sin,floor,..}.f32, promote them instead. N.B. We had logic to handle FREM but were missing out on a number of others. This change generalizes the FREM handling. llvm-svn: 268875
* [ValueTracking] Hoist some computation out of a loop; NFCSanjoy Das2016-05-071-20/+11
| | | | | | There is no need to match the comparison instruction repeatedly. llvm-svn: 268836
* Clean up comment; NFCSanjoy Das2016-05-071-1/+1
| | | | llvm-svn: 268835
* Delete trailing whitespace; NFCSanjoy Das2016-05-071-8/+8
| | | | llvm-svn: 268834
* ThinLTO: fix assertion and refactor check for hidden use from inline ASM in ↵Mehdi Amini2016-05-061-31/+43
| | | | | | | | | | | a helper function This test was crashing, and currently it breaks bootstrapping clang with debuginfo Differential Revision: http://reviews.llvm.org/D20008 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 268715
* [LAA] Fix confusing debug messageAdam Nemet2016-05-051-1/+1
| | | | | | | | This message used to be correct, when all we cared about was whether the dependence was safe (i.e. NoDep) or unsafe. With the current more precise characterization, this is a forward dep. llvm-svn: 268695
* [PM] port Branch Frequency Analaysis pass to new PMXinliang David Li2016-05-051-0/+27
| | | | llvm-svn: 268687
* [ValueTracking] Early exit when further analysis won't be fruitful.Chad Rosier2016-05-051-15/+30
| | | | | | | This should have NFC in the context of codegen, but may have positive implications on compile-time. llvm-svn: 268651
OpenPOWER on IntegriCloud