summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [LV] Move InterleaveGroup and InterleavedAccessInfo to VectorUtils.h (NFC)Florian Hahn2018-09-121-0/+327
| | | | | | | | | | | | | Move the 2 classes out of LoopVectorize.cpp to make it easier to re-use them for VPlan outside LoopVectorize.cpp Reviewers: Ayal, mssimpso, rengolin, dcaballe, mkuper, hsaito, hfinkel, xbolva00 Reviewed By: rengolin, xbolva00 Differential Revision: https://reviews.llvm.org/D49488 llvm-svn: 342027
* Remove unused include from IVDescriptors.cpp.Ilya Biryukov2018-09-121-1/+0
| | | | | | | | | This fixes a layering violation: Analysis/IVDescrtors.cpp can't include Transforms/Utils/BasicBlockUtils.h, since TransformUtils depends on Analysis. llvm-svn: 342024
* Break LoopUtils into an Analysis file.Vikram TV2018-09-122-0/+1031
| | | | | | | | | | | | | | | | | | | Summary: The InductionDescriptor and RecurrenceDescriptor classes basically analyze the IR to identify the respective IVs. So, it is better to have them in the "Analysis" directory instead of the "Transforms" directory. The rationale for this is to make the Induction and Recurrence descriptor classes available for analysis passes. Currently including them in an analysis pass produces link error (http://lists.llvm.org/pipermail/llvm-dev/2018-July/124456.html). Induction and Recurrence descriptors are moved from Transforms/Utils/LoopUtils.h|cpp to Analysis/IVDescriptors.h|cpp. Reviewers: dmgreen, llvm-commits, hfinkel Reviewed By: dmgreen Subscribers: mgorny Differential Revision: https://reviews.llvm.org/D51153 llvm-svn: 342016
* [MemorySSAUpdater] Avoid creating self-referencing MemoryDefsAlexandros Lamprineas2018-09-111-4/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Fix for https://bugs.llvm.org/show_bug.cgi?id=38807, which occurred while compiling SemaTemplateInstantiate.cpp with clang and GVNHoist enabled. In the following example: 1=def(entry) / \ 2=def(1) 4=def(1) 3=def(2) 5=def(4) When removing the MemoryDef 2=def(1) from its basic block, and just before adding it to the end of the parent basic block, we first replace all its uses with the defining memory access: 3=def(2) -> 3=def(1) Then we call insertDef for adding 2=def(1) to the parent basic block, where we replace the uses of 1=def(entry) with 2=def(1). Doing so we create a self reference: 2=def(1) -> 2=def(2) (bad) 3=def(1) -> 3=def(2) (ok) 4=def(1) -> 4=def(2) (ok) Differential Revision: https://reviews.llvm.org/D51801 llvm-svn: 341947
* [LoopInfo] Fix Loop::getLoopID() for loops with multiple latchesJohannes Doerfert2018-09-111-12/+5
| | | | | | | | The previous implementation traversed all loop blocks and bailed if one was not a latch block. Since we are only interested in latch blocks, we should only traverse those. llvm-svn: 341926
* [NFC] Sanitizing asserts for OrderedBasicBlockMax Kazantsev2018-09-111-0/+3
| | | | llvm-svn: 341917
* [NFC] Rename variableMax Kazantsev2018-09-111-2/+2
| | | | llvm-svn: 341901
* Prevent Constant Folding From Optimizing inrange GEPPeter Collingbourne2018-09-111-9/+2
| | | | | | | | | | | | | | | This patch does the following things: 1. update SymbolicallyEvaluateGEP so that it bails out if it cannot preserve inrange arribute; 2. update llvm/test/Analysis/ConstantFolding/gep.ll to remove UB in it; 3. remove inaccurate comment above ConstantFoldInstOperandsImpl in llvm/lib/Analysis/ConstantFolding.cpp; 4. add a new regression test that makes sure that no optimizations change an inrange GEP in an unexpected way. Patch by Zhaomo Yang! Differential Revision: https://reviews.llvm.org/D51698 llvm-svn: 341888
* API to update MemorySSA for cloned blocks and added CFG edges.Alina Sbirlea2018-09-102-15/+548
| | | | | | | | | | | | | | | | Summary: End goal is to update MemorySSA in all loop passes. LoopUnswitch clones all blocks in a loop. SimpleLoopUnswitch clones some blocks. LoopRotate clones some instructions. Some of these loop passes also make CFG changes. This is an API based on what I found needed in LoopUnswitch, SimpleLoopUnswitch, LoopRotate, LoopInstSimplify, LoopSimplifyCFG. Adding dependent patches using this API for context. Reviewers: george.burgess.iv, dberlin Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D45299 llvm-svn: 341855
* [AST] Visit memtransfer arguments in orderPhilip Reames2018-09-101-1/+1
| | | | | | | | | | The only point to this change is the test diffs. When I remove this code entirely (in favor of the recently added generic handling), I don't want there to be any confusion due to spurious test diffs. As an aside, the fact out tests are AST construction order dependent is not great. I thought about fixing that, but the reasonable schemes I might want (e.g. sort by name) need the test diffs anyways. Philip llvm-svn: 341841
* [MemorySSA] Relax verification of clobbering accesses.Alina Sbirlea2018-09-071-2/+12
| | | | llvm-svn: 341733
* [AST] Generalize argument specific aliasingPhilip Reames2018-09-072-3/+44
| | | | | | | | | | | | | | AliasSetTracker has special case handling for memset, memcpy and memmove which pre-existed argmemonly on functions and readonly and writeonly on arguments. This patch generalizes it using the AA infrastructure to any call correctly annotated. The motivation here is to cut down on confusion, not performance per se. For most instructions, there is a direct mapping to alias set. However, this is not guaranteed by the interface and was not in fact true for these three intrinsics *and only these three intrinsics*. I kept getting myself confused about this invariant, so I figured it would be good to clearly distinguish between a instructions and alias sets. Calls happened to be an easy target. The nice side effect is that custom implementations of memset/memcpy/memmove - including wrappers discovered by IPO - can now be optimized the same as builts by LICM. Note: The actual removal of the memset/memtransfer specific handling will happen in a follow on NFC patch. It was originally part of this one, but separate for ease of review and rebase. Differential Revision: https://reviews.llvm.org/D50730 llvm-svn: 341713
* [MemorySSA] Update MemoryPhi wiring for block splitting to consider if ↵Alina Sbirlea2018-09-071-1/+10
| | | | | | | | | | | | | | | | | identical edges were merged. Summary: Block splitting is done with either identical edges being merged, or not. Only critical edges can be split without merging identical edges based on an option. Teach the memoryssa updater to take this into account: for the same edge between two blocks only move one entry from the Phi in Old to the new Phi in New. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D51563 llvm-svn: 341709
* Output per-function size-info remarksJessica Paquette2018-09-062-4/+8
| | | | | | | | | | | This patch adds per-function size information remarks. Previously, passing -Rpass-analysis=size-info would only give you per-module changes. By adding the ability to do this per-function, it's easier to see which functions contributed the most to size changes. https://reviews.llvm.org/D51467 llvm-svn: 341588
* [LoopPassManager] MemorySSA should be preserved when enabled.Alina Sbirlea2018-09-061-2/+2
| | | | llvm-svn: 341587
* [NFC] Simplify inner structure of InstructionPrecedenceTrackingMax Kazantsev2018-09-061-32/+17
| | | | | | | | | | | | | | Currently it has a set KnownBlocks that marks blocks as having cached answers and a map FirstSpecialInsts that maps these blocks to first special instructions in them. The value in the map is always non-null, and for blocks that are known to have no special instructions the map does not have an instance. This patch removes KnownBlocks as obsolete. Instead, for blocks that are known to have no special instructions, we just put a nullptr value. This makes the code much easier to read. llvm-svn: 341531
* Return "[NFC] Add severe validation of InstructionPrecedenceTracking"Max Kazantsev2018-09-061-0/+60
| | | | | | | | | | This validation patch has been reverted as rL341147 because of conserns raised by @reames. This revision returns it as is to raise a discussion and address the concerns. Differential Revision: https://reviews.llvm.org/D51523 Reviewed By: reames llvm-svn: 341526
* [NFC] Optionally pass a function to emitInstrCountChangedRemarkJessica Paquette2018-08-311-1/+1
| | | | | | | | | In basic block, loop, and function passes, we already have a function that we can use to emit optimization remarks. We can use that instead of searching the module for the first suitable function (that is, one that contains at least one basic block.) llvm-svn: 341253
* [NFC] Pass the instruction delta to emitInstrCountChangedRemarkJessica Paquette2018-08-312-5/+5
| | | | | | | | | | | | | | | Instead of counting the size of the entire module every time we run a pass, pass along a delta instead and use that to emit the remark. This means we only have to use (on average) smaller IR units to calculate instruction counts. E.g, in a BB pass, we only need to look at the delta of the BB instead of the delta of the entire module. 6/6 (This improved compile time for size remarks on sqlite3 + O2 significantly) llvm-svn: 341250
* [NFC] Pre-calculate SCC IR counts in size remarks.Jessica Paquette2018-08-311-5/+13
| | | | | | | | | | | | | | | | | | | Same vein as the previous commits. Pre-calculate the size of the module and use that to decide if we're going to emit a remark. This one comes with a FIXME and TODO. First off, CallGraphSCC and CallGraphNode don't have a getInstructionCount function. So, for now, we do the same thing as in a module pass. Second off, we're not really saving anything here yet, because as before, I need to change emitInstrCountChangedRemark to take in a delta. Keeping the patches small though, so that's coming up next. 5/6 llvm-svn: 341249
* [NFC] Pre-calculate loop IR counts in size remarks.Jessica Paquette2018-08-311-5/+18
| | | | | | | | | | | | Another commit reducing compile time in size remarks. Cache the size of the module and loop, and update values based off of deltas instead. Avoid recalculating the size of the whole module whenever possible. 3/6 llvm-svn: 341247
* Revert "[NFC] Add severe validation of InstructionPrecedenceTracking" for ↵Max Kazantsev2018-08-311-39/+0
| | | | | | discussion llvm-svn: 341147
* Reverting r340807.Andrew Kaylor2018-08-301-1/+1
| | | | | | This patch restores the old behavior of getAllocationDataForFunction in MemoryBuiltins.cpp. llvm-svn: 341091
* [NFC] Rename the DivergenceAnalysis to LegacyDivergenceAnalysisNicolai Haehnle2018-08-303-12/+12
| | | | | | | | | | | | | | | | | | | | Summary: This is patch 1 of the new DivergenceAnalysis (https://reviews.llvm.org/D50433). The purpose of this patch is to free up the name DivergenceAnalysis for the new generic implementation. The generic implementation class will be shared by specialized divergence analysis classes. Patch by: Simon Moll Reviewed By: nhaehnle Subscribers: jvesely, jholewinski, arsenm, nhaehnle, mgorny, jfb, llvm-commits Differential Revision: https://reviews.llvm.org/D50434 Change-Id: Ie8146b11be2c50d5312f30e11c7a3036a15b48cb llvm-svn: 341071
* [NFC] Add severe validation of InstructionPrecedenceTrackingMax Kazantsev2018-08-301-0/+39
| | | | llvm-svn: 341051
* [NFC] Rename map to make the naming consistentMax Kazantsev2018-08-301-6/+6
| | | | llvm-svn: 341043
* [NFC] Move OrderedInstructions and InstructionPrecedenceTracking to AnalysisMax Kazantsev2018-08-303-0/+152
| | | | | | | | These classes don't make any changes to IR and have no reason to be in Transform/Utils. This patch moves them to Analysis folder. This will allow us reusing these classes in some analyzes, like MustExecute. llvm-svn: 341015
* Re-enable "[NFC] Unify guards detection"Max Kazantsev2018-08-304-4/+26
| | | | | | | | | | rL340921 has been reverted by rL340923 due to linkage dependency from Transform/Utils to Analysis which is not allowed. In this patch this has been fixed, a new utility function moved to Analysis. Differential Revision: https://reviews.llvm.org/D51152 llvm-svn: 341014
* [MemorySSA] Silence warning.Alina Sbirlea2018-08-291-0/+1
| | | | llvm-svn: 340995
* [MemorySSA] Fix checkClobberSanity to skip Start only for Defs and Uses.Alina Sbirlea2018-08-291-5/+10
| | | | llvm-svn: 340981
* [LICM] Hoist stores of invariant values to invariant addresses out of loopsPhilip Reames2018-08-291-3/+16
| | | | | | | | | | | | Teach LICM to hoist stores out of loops when the store writes to a location otherwise unused in the loop, writes a value which is invariant, and is guaranteed to execute if the loop is entered. Worth noting is that this transformation is partially overlapping with the existing promotion transformation. Reasons this is worthwhile anyway include: * For multi-exit loops, this doesn't require duplication of the store. * It kicks in for case where we can't prove we exit through a normal exit (i.e. we may throw), but can prove the store executes before that possible side exit. Differential Revision: https://reviews.llvm.org/D50925 llvm-svn: 340974
* [MemorySSA] Add expesive check for validating clobber accesses.Alina Sbirlea2018-08-291-11/+45
| | | | | | | | | | | | Summary: Add validation of clobber accesses as expensive check. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D51327 llvm-svn: 340951
* Revert r340921 "[NFC] Unify guards detection"Hans Wennborg2018-08-292-4/+4
| | | | | | | | | | | | | | | | | | This broke the build, see e.g. http://lab.llvm.org:8011/builders/clang-cmake-armv8-lnt/builds/4626/ http://lab.llvm.org:8011/builders/clang-ppc64be-linux-lnt/builds/18647/ http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/5856/ http://lab.llvm.org:8011/builders/lld-x86_64-freebsd/builds/22800/ > We have multiple places in code where we try to identify whether or not > some instruction is a guard. This patch factors out this logic into a separate > utility function which works uniformly in all places. > > Differential Revision: https://reviews.llvm.org/D51152 > Reviewed By: fedor.sergeev llvm-svn: 340923
* [NFC] Unify guards detectionMax Kazantsev2018-08-292-4/+4
| | | | | | | | | | | We have multiple places in code where we try to identify whether or not some instruction is a guard. This patch factors out this logic into a separate utility function which works uniformly in all places. Differential Revision: https://reviews.llvm.org/D51152 Reviewed By: fedor.sergeev llvm-svn: 340921
* [NFC][PassTiming] factor out generic PassTimingInfoFedor Sergeev2018-08-283-0/+3
| | | | | | | | Moving PassTimingInfo from legacy pass manager code into a separate header. Making it suitable for both legacy and new pass manager. Adding a test on -time-passes main functionality. llvm-svn: 340872
* Fix in getAllocationDataForFunctionDavid Chisnall2018-08-281-1/+1
| | | | | | | | | | | | | | | | Summary: Correct to use set like behaviour of AllocType. Should check for subset, not precise value. Reviewers: theraven Reviewed By: theraven Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D50959 llvm-svn: 340807
* [MemorySSA] Add NDEBUG checks to verifiers; NFCGeorge Burgess IV2018-08-281-0/+4
| | | | | | | | verify*() methods are intended to have no side-effects (unless we detect broken MSSA, in which case they assert()), and all of the other verify methods are wrapped by `#ifndef NDEBUG`. llvm-svn: 340793
* Revert "[SCEV][NFC] Check NoWrap flags before lexicographical comparison of ↵Roman Tereshin2018-08-271-8/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | SCEVs" This reverts r319889. Unfortunately, wrapping flags are not a part of SCEV's identity (they do not participate in computing a hash value or in equality comparisons) and in fact they could be assigned after the fact w/o rebuilding a SCEV. Grep for const_cast's to see quite a few of examples, apparently all for AddRec's at the moment. So, if 2 expressions get built in 2 slightly different ways: one with flags set in the beginning, the other with the flags attached later on, we may end up with 2 expressions which are exactly the same but have their operands swapped in one of the commutative N-ary expressions, and at least one of them will have "sorted by complexity" invariant broken. 2 identical SCEV's won't compare equal by pointer comparison as they are supposed to. A real-world reproducer is added as a regression test: the issue described causes 2 identical SCEV expressions to have different order of operands and therefore compare not equal, which in its turn prevents LoadStoreVectorizer from vectorizing a pair of consecutive loads. On a larger example (the source of the test attached, which is a bugpoint) I have seen even weirder behavior: adding a constant to an existing SCEV changes the order of the existing terms, for instance, getAddExpr(1, ((A * B) + (C * D))) returns (1 + (C * D) + (A * B)). Differential Revision: https://reviews.llvm.org/D40645 llvm-svn: 340777
* [IR] Replace `isa<TerminatorInst>` with `isTerminator()`.Chandler Carruth2018-08-264-6/+6
| | | | | | | | | | | | This is a bit awkward in a handful of places where we didn't even have an instruction and now we have to see if we can build one. But on the whole, this seems like a win and at worst a reasonable cost for removing `TerminatorInst`. All of this is part of the removal of `TerminatorInst` from the `Instruction` type hierarchy. llvm-svn: 340701
* [IR] Begin removal of TerminatorInst by removing successor manipulation.Chandler Carruth2018-08-262-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The core get and set routines move to the `Instruction` class. These routines are only valid to call on instructions which are terminators. The iterator and *generic* range based access move to `CFG.h` where all the other generic successor and predecessor access lives. While moving the iterator here, simplify it using the iterator utilities LLVM provides and updates coding style as much as reasonable. The APIs remain pointer-heavy when they could better use references, and retain the odd behavior of `operator*` and `operator->` that is common in LLVM iterators. Adjusting this API, if desired, should be a follow-up step. Non-generic range iteration is added for the two instructions where there is an especially easy mechanism and where there was code attempting to use the range accessor from a specific subclass: `indirectbr` and `br`. In both cases, the successors are contiguous operands and can be easily iterated via the operand list. This is the first major patch in removing the `TerminatorInst` type from the IR's instruction type hierarchy. This change was discussed in an RFC here and was pretty clearly positive: http://lists.llvm.org/pipermail/llvm-dev/2018-May/123407.html There will be a series of much more mechanical changes following this one to complete this move. Differential Revision: https://reviews.llvm.org/D47467 llvm-svn: 340698
* [PhiValues] Use callback value handles to invalidate deleted valuesJohn Brawn2018-08-241-0/+17
| | | | | | | | | | | The way that PhiValues is integrated with BasicAA it is possible for a pass which uses BasicAA to pick up an instance of BasicAA that uses PhiValues without intending to, and then delete values from a function in a way that causes PhiValues to return dangling pointers to these deleted values. Fix this by having a set of callback value handles to invalidate values when they're deleted. llvm-svn: 340613
* [ValueTracking] Fix assert message and add test case for r340546 and PR38677.Craig Topper2018-08-231-1/+1
| | | | | | The bug was already fixed. This just adds a test case for it. llvm-svn: 340556
* [ValueTracking] Fix an assert from r340480.Craig Topper2018-08-231-1/+3
| | | | | | | | | | We need to allow ConstantExpr Selects in addition to SelectInst. I'll try to put together a test case, but I wanted to fix the issues being reported. Fixes PR38677 llvm-svn: 340546
* [ValueTracking] Teach computeNumSignBits to understand min/max clamp ↵Craig Topper2018-08-221-1/+37
| | | | | | | | | | patterns with constant/splat values If we have a min/max pair we can do a better job of counting sign bits if we look at them together. This is similar to what is done in the SelectionDAG version of computeNumSignBits for ISD::SMAX/SMIN. Differential Revision: https://reviews.llvm.org/D51112 llvm-svn: 340480
* [MemorySSA] Invalidate optimized Defs upon moving them; NFCGeorge Burgess IV2018-08-221-5/+14
| | | | | | | | | | | | | | | | | We're currently getting this behavior implicitly, since we determine if a Def's optimization is valid based on the ID of its defining access. This is incorrect, though I wouldn't be surprised if this was masked in part by that we're using a WeakVH to track what Defs are optimized to. (Not to mention that we don't move Defs super often, AFAICT). I'll submit a patch to fix this shortly. This also includes a minor refactor to reduce duplication a bit. No test is included, since like said, this already happens to be our behavior. I'll add a test for this with my fix to the other bug mentioned above. llvm-svn: 340461
* [AA] Remove a needless variable [NFC]Philip Reames2018-08-221-3/+1
| | | | | | There's no need to track a seperate variable for argmemonly aliasing. This falls out naturally of the modinfo union. Note that we may return earlier than we would have earlier if all arguments are explicitly readnone. The overall result doesn't change, just how we get there. llvm-svn: 340443
* [AST] Minor whitespace cleanup [NFC]Philip Reames2018-08-221-11/+7
| | | | llvm-svn: 340440
* [MemorySSA] Move two simple getters; NFCGeorge Burgess IV2018-08-221-8/+0
| | | | | | | | We're calling these functions quite a bit from outside of MemorySSA.cpp now. Given that they're relatively simple one-liners, I think the style preference is to have them inline. llvm-svn: 340430
* [AST] Fix a whitespace typo [NFC]Philip Reames2018-08-221-1/+1
| | | | llvm-svn: 340384
* [AST] Reorder code to reduce a future patch diff [NFC]Philip Reames2018-08-221-3/+3
| | | | llvm-svn: 340383
OpenPOWER on IntegriCloud