summaryrefslogtreecommitdiff
path: root/lib/Transforms/Vectorize/BBVectorize.cpp
Commit message (Collapse)AuthorAge
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207196 91177308-0d34-0410-b5e6-96231b3b80d8
* Allow vectorization of bit intrinsics in BB Vectorizer.Karthik Bhat2014-04-25
| | | | | | | | This patch adds support for vectorization of bit intrinsics such as bswap,ctpop,ctlz,cttz. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207174 91177308-0d34-0410-b5e6-96231b3b80d8
* Allow vectorization of few missed llvm intrinsic calls in BBVectorizor by ↵Karthik Bhat2014-04-24
| | | | | | handling them in isVectorizableIntrinsic function. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207085 91177308-0d34-0410-b5e6-96231b3b80d8
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-22
| | | | | | | | | | | | | | | | | definition below all of the header #include lines, lib/Transforms/... edition. This one is tricky for two reasons. We again have a couple of passes that define something else before the includes as well. I've sunk their name macros with the DEBUG_TYPE. Also, InstCombine contains headers that need DEBUG_TYPE, so now those headers #define and #undef DEBUG_TYPE around their code, leaving them well formed modular headers. Fixing these headers was a large motivation for all of these changes, as "leaky" macros of this form are hard on the modules implementation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206844 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-09
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@203364 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-05
| | | | | | class. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202953 91177308-0d34-0410-b5e6-96231b3b80d8
* [Modules] Move ValueHandle into the IR library where Value itself lives.Chandler Carruth2014-03-04
| | | | | | | | | | | Move the test for this class into the IR unittests as well. This uncovers that ValueMap too is in the IR library. Ironically, the unittest for ValueMap is useless in the Support library (honestly, so was the ValueHandle test) and so it already lives in the IR unittests. Mmmm, tasty layering. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202821 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-02
| | | | | | Remove the old functions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202636 91177308-0d34-0410-b5e6-96231b3b80d8
* Make DataLayout a plain object, not a pass.Rafael Espindola2014-02-25
| | | | | | | Instead, have a DataLayoutPass that holds one. This will allow parts of LLVM don't don't handle passes to also use DataLayout. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202168 91177308-0d34-0410-b5e6-96231b3b80d8
* Make some DataLayout pointers const.Rafael Espindola2014-02-24
| | | | | | No functionality change. Just reduces the noise of an upcoming patch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202087 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename many DataLayout variables from TD to DL.Rafael Espindola2014-02-21
| | | | | | | | | I am really sorry for the noise, but the current state where some parts of the code use TD (from the old name: TargetData) and other parts use DL makes it hard to write a patch that changes where those variables come from and how they are passed along. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@201827 91177308-0d34-0410-b5e6-96231b3b80d8
* Reduce code duplication resulting from the ConstantVector/ConstantDataVector ↵Benjamin Kramer2014-02-13
| | | | | | | | split. No intended functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@201344 91177308-0d34-0410-b5e6-96231b3b80d8
* [Vectorizer] Add a new 'OperandValueKind' in TargetTransformInfo calledAndrea Di Biagio2014-02-12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 'OK_NonUniformConstValue' to identify operands which are constants but not constant splats. The cost model now allows returning 'OK_NonUniformConstValue' for non splat operands that are instances of ConstantVector or ConstantDataVector. With this change, targets are now able to compute different costs for instructions with non-uniform constant operands. For example, On X86 the cost of a vector shift may vary depending on whether the second operand is a uniform or non-uniform constant. This patch applies the following changes: - The cost model computation now takes into account non-uniform constants; - The cost of vector shift instructions has been improved in X86TargetTransformInfo analysis pass; - BBVectorize, SLPVectorizer and LoopVectorize now know how to distinguish between non-uniform and uniform constant operands. Added a new test to verify that the output of opt '-cost-model -analyze' is valid in the following configurations: SSE2, SSE4.1, AVX, AVX2. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@201272 91177308-0d34-0410-b5e6-96231b3b80d8
* Disable most IR-level transform passes on functions marked 'optnone'.Paul Robinson2014-02-06
| | | | | | | | | | Ideally only those transform passes that run at -O0 remain enabled, in reality we get as close as we reasonably can. Passes are responsible for disabling themselves, it's not the job of the pass manager to do it for them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@200892 91177308-0d34-0410-b5e6-96231b3b80d8
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-13
| | | | | | | | | | | | | | | | | | | | | | | can be used by both the new pass manager and the old. This removes it from any of the virtual mess of the pass interfaces and lets it derive cleanly from the DominatorTreeBase<> template. In turn, tons of boilerplate interface can be nuked and it turns into a very straightforward extension of the base DominatorTree interface. The old analysis pass is now a simple wrapper. The names and style of this split should match the split between CallGraph and CallGraphWrapperPass. All of the users of DominatorTree have been updated to match using many of the same tricks as with CallGraph. The goal is that the common type remains the resulting DominatorTree rather than the pass. This will make subsequent work toward the new pass manager significantly easier. Also in numerous places things became cleaner because I switched from re-running the pass (!!! mid way through some other passes run!!!) to directly recomputing the domtree. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@199104 91177308-0d34-0410-b5e6-96231b3b80d8
* [cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth2014-01-13
| | | | | | | | | | | | | | | | | | directory. These passes are already defined in the IR library, and it doesn't make any sense to have the headers in Analysis. Long term, I think there is going to be a much better way to divide these matters. The dominators code should be fully separated into the abstract graph algorithm and have that put in Support where it becomes obvious that evn Clang's CFGBlock's can use it. Then the verifier can manually construct dominance information from the Support-driven interface while the Analysis library can provide a pass which both caches, reconstructs, and supports a nice update API. But those are very long term, and so I don't want to leave the really confusing structure until that day arrives. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@199082 91177308-0d34-0410-b5e6-96231b3b80d8
* Use more type helper functionsMatt Arsenault2013-10-21
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193109 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix code duplicationMatt Arsenault2013-10-01
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191716 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix spelling intruction -> instruction.Robert Wilhelm2013-09-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191610 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Add initial stores to the write set when tracking usesHal Finkel2013-08-13
| | | | | | | | | | | | | | | | When computing the use set of a store, we need to add the store to the write set prior to iterating over later instructions. Otherwise, if there is a later aliasing load of that store, that load will not be tagged as a use, and bad things will happen. trackUsesOfI still adds later dependent stores of an instruction to that instruction's write set, but it never sees the original instruction, and so when tracking uses of a store, the store must be added to the write set by the caller. Fixes PR16834. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188329 91177308-0d34-0410-b5e6-96231b3b80d8
* Use SmallVectorImpl& instead of SmallVector to avoid repeating small vector ↵Craig Topper2013-07-14
| | | | | | size. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186274 91177308-0d34-0410-b5e6-96231b3b80d8
* Use SmallVectorImpl::iterator/const_iterator instead of SmallVector to avoid ↵Craig Topper2013-07-04
| | | | | | specifying the vector size. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185606 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Fixup debugging statementsHal Finkel2013-03-10
| | | | | | | After the recent data-structure improvements, a couple of debugging statements were broken (printing pointer values). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176791 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Fix an invalid reference bugHal Finkel2013-02-17
| | | | | | | | | | | | | | This fixes PR15289. This bug was introduced (recently) in r175215; collecting all std::vector references for candidate pairs to delete at once is invalid because subsequent lookups in the owning DenseMap could invalidate the references. bugpoint was able to reduce a useful test case. Unfortunately, because whether or not this asserts depends on memory layout, this test case will sometimes appear to produce valid output. Nevertheless, running under valgrind will reveal the error. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175397 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Call a DAG and DAG instead of a treeHal Finkel2013-02-15
| | | | | | | | | | Several functions and variable names used the term 'tree' to refer to what is actually a DAG. Correcting this mistake will, hopefully, prevent confusion in the future. No functionality change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175278 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Cap the number of candidate pairs in each instruction groupHal Finkel2013-02-15
| | | | | | | | | | | | | | | | | | | | | | | For some basic blocks, it is possible to generate many candidate pairs for relatively few pairable instructions. When many (tens of thousands) of these pairs are generated for a single instruction group, the time taken to generate and rank the different vectorization plans can become quite large. As a result, we now cap the number of candidate pairs within each instruction group. This is done by closing out the group once the threshold is reached (set now at 3000 pairs). Although this will limit the overall compile-time impact, this may not be the best way to achieve this result. It might be better, for example, to prune excessive candidate pairs after the fact the prevent the generation of short, but highly-connected groups. We can experiment with this in the future. This change reduces the overall compile-time slowdown of the csa.ll test case in PR15222 to ~5x. If 5x is still considered too large, a lower limit can be used as the default. This represents a functionality change, but only for very large inputs (thus, there is no regression test). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175251 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Remove the remaining instances of std::multimapHal Finkel2013-02-14
| | | | | | | | | | All instances of std::multimap have now been replaced by DenseMap<K, std::vector<V> >, and this yields a speedup of 5% on the csa.ll test case from PR15222. No functionality change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175216 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Don't store candidate pairs in a std::multimapHal Finkel2013-02-14
| | | | | | | | | | This is another commit on the road to removing std::multimap from BBVectorize. This gives an ~1% speedup on the csa.ll test case in PR15222. No functionality change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175215 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Don't over-search when building the dependency mapHal Finkel2013-02-11
| | | | | | | | | | | | | When building the pairable-instruction dependency map, don't search past the last pairable instruction. For large blocks that have been divided into multiple instruction groups, searching past the last instruction in each group is very wasteful. This gives a 32% speedup on the csa.ll test case from PR15222 (when using 50 instructions in each group). No functionality change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174915 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Omit unnecessary entries in PairableInstUsersHal Finkel2013-02-11
| | | | | | | | | | | This map is queried only for instructions in pairs of pairable instructions; so make sure that only pairs of pairable instructions are added to the map. This gives a 3.5% speedup on the csa.ll test case from PR15222. No functionality change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174914 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Eliminate one more restricted linear searchHal Finkel2013-02-11
| | | | | | | | | | This eliminates one more linear search over a range of std::multimap entries. This gives a 22% speedup on the csa.ll test case from PR15222. No functionality change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174893 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Remove the linear searches from pair connection searchingHal Finkel2013-02-11
| | | | | | | | | This removes the last of the linear searches over ranges of std::multimap iterators, giving a 7% speedup on the doduc.bc input from PR15222. No functionality change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174859 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Avoid linear searches within the load-move setHal Finkel2013-02-11
| | | | | | | | | This is another cleanup aimed at eliminating linear searches in ranges of std::multimap. No functionality change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174858 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: isa/cast cleanup in getInstructionTypesHal Finkel2013-02-11
| | | | | | | | | | Profiling suggests that getInstructionTypes is performance-sensitive, this cleans up some double-casting in that function in favor of using dyn_cast. No functionality change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174857 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Make the bookkeeping to support full cycle checking less expensiveHal Finkel2013-02-11
| | | | | | | | | | | By itself, this does not have much of an effect, but only because in the default configuration the full cycle checks are used only for small problem sizes. This is part of a general cleanup of uses of iteration over std::multimap ranges only for the purpose of checking membership. No functionality change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174856 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Use TTI->getAddressComputationCostHal Finkel2013-02-08
| | | | | | | | | | | | | This is a follow-up to the cost-model change in r174713 which splits the cost of a memory operation between the address computation and the actual memory access. In r174713, this cost is always added to the memory operation cost, and so BBVectorize will do the same. Currently, this new cost function is used only by ARM, and I don't have any ARM test cases for BBVectorize. Assistance in generating some good ARM test cases for BBVectorize would be greatly appreciated! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174743 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Better use of TTI->getShuffleCostHal Finkel2013-01-27
| | | | | | | | | | | | | | | | | | | | When flipping the pair of subvectors that form a vector, if the vector length is 2, we can use the SK_Reverse shuffle kind to get more-accurate cost information. Also we can use the SK_ExtractSubvector shuffle kind to get accurate subvector extraction costs. The current cost model implementations don't yet seem complex enough for this to make a difference (thus, there are no test cases with this commit), but it should help in future. Depending on how the various targets optimize and combine shuffles in practice, we might be able to get more-accurate costs by combining the costs of multiple shuffle kinds. For example, the cost of flipping the subvector pairs could be modeled as two extractions and two subvector insertions. These changes, however, should probably be motivated by specific test cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173621 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Add a additional comment about the cost computationHal Finkel2013-01-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173580 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Fix anomalous capital letter in commentHal Finkel2013-01-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173579 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch BBVectorize to directly depend on having a TTI analysis.Chandler Carruth2013-01-07
| | | | | | | | | | | | | This could be simplified further, but Hal has a specific feature for ignoring TTI, and so I preserved that. Also, I needed to use it because a number of tests fail when switching from a null TTI to the NoTTI nonce implementation. That seems suspicious to me and so may be something that you need to look into Hal. I worked it by preserving the old behavior for these tests with the flag that ignores all target info. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171722 91177308-0d34-0410-b5e6-96231b3b80d8
* Move TargetTransformInfo to live under the Analysis library. This noChandler Carruth2013-01-07
| | | | | | | longer would violate any dependency layering and it is in fact an analysis. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171686 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch the BB vectorizer from the VTTI interface to the simple TTIChandler Carruth2013-01-05
| | | | | | interface. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171618 91177308-0d34-0410-b5e6-96231b3b80d8
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-02
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171366 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Use VTTI to compute costs for intrinsics vectorizationHal Finkel2012-12-26
| | | | | | | | | | | | For the time being this includes only some dummy test cases. Once the generic implementation of the intrinsics cost function does something other than assuming scalarization in all cases, or some target specializes the interface, some real test cases can be added. Also, for consistency, I changed the type of IID from unsigned to Intrinsic::ID in a few other places. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171079 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Enable vectorization of the fmuladd intrinsicHal Finkel2012-12-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171075 91177308-0d34-0410-b5e6-96231b3b80d8
* BB-Vectorizer: Check the cost of the store pointer typeNadav Rotem2012-12-21
| | | | | | | | | and not the return type, which is void. A number of test cases fail after adding the assertion in TTImpl. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@170828 91177308-0d34-0410-b5e6-96231b3b80d8
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-03
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
* BBVectorize: Correctly merge SubclassOptionalDataHal Finkel2012-11-28
| | | | | | | When two instructions are combined into a vector instruction, the resulting instruction must have the most-conservative flags. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168765 91177308-0d34-0410-b5e6-96231b3b80d8
* Replace std::vector -> SmallVector in BBVectorizeHal Finkel2012-11-14
| | | | | | | | | For now, this uses 8 on-stack elements. I'll need to do some profiling to see if this is the best number. Pointed out by Jakob in post-commit review. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167966 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix the largest offender of determinism in BBVectorizeHal Finkel2012-11-14
| | | | | | | | | | | | | | | | | Iterating over the children of each node in the potential vectorization plan must happen in a deterministic order (because it affects which children are erased when two children conflict). There was no need for this data structure to be a map in the first place, so replacing it with a vector is a small change. I believe that this was the last remaining instance if iterating over the elements of a Dense* container where the iteration order could matter. There are some remaining iterations over std::*map containers where the order might matter, but so long as the Value* for instructions in a block increase with the order of the instructions in the block (or decrease) monotonically, then this will appear to be deterministic. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167942 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-15 03:11:11 +0000