summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/ConstantHoisting.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [multiversion] Thread a function argument through all the callers of theChandler Carruth2015-02-011-1/+1
| | | | | | | | | | | | | | getTTI method used to get an actual TTI object. No functionality changed. This just threads the argument and ensures code like the inliner can correctly look up the callee's TTI rather than using a fixed one. The next change will use this to implement per-function subtarget usage by TTI. The changes after that should eliminate the need for FTTI as that will have become the default. llvm-svn: 227730
* [PM] Change the core design of the TTI analysis to use a polymorphicChandler Carruth2015-01-311-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | type erased interface and a single analysis pass rather than an extremely complex analysis group. The end result is that the TTI analysis can contain a type erased implementation that supports the polymorphic TTI interface. We can build one from a target-specific implementation or from a dummy one in the IR. I've also factored all of the code into "mix-in"-able base classes, including CRTP base classes to facilitate calling back up to the most specialized form when delegating horizontally across the surface. These aren't as clean as I would like and I'm planning to work on cleaning some of this up, but I wanted to start by putting into the right form. There are a number of reasons for this change, and this particular design. The first and foremost reason is that an analysis group is complete overkill, and the chaining delegation strategy was so opaque, confusing, and high overhead that TTI was suffering greatly for it. Several of the TTI functions had failed to be implemented in all places because of the chaining-based delegation making there be no checking of this. A few other functions were implemented with incorrect delegation. The message to me was very clear working on this -- the delegation and analysis group structure was too confusing to be useful here. The other reason of course is that this is *much* more natural fit for the new pass manager. This will lay the ground work for a type-erased per-function info object that can look up the correct subtarget and even cache it. Yet another benefit is that this will significantly simplify the interaction of the pass managers and the TargetMachine. See the future work below. The downside of this change is that it is very, very verbose. I'm going to work to improve that, but it is somewhat an implementation necessity in C++ to do type erasure. =/ I discussed this design really extensively with Eric and Hal prior to going down this path, and afterward showed them the result. No one was really thrilled with it, but there doesn't seem to be a substantially better alternative. Using a base class and virtual method dispatch would make the code much shorter, but as discussed in the update to the programmer's manual and elsewhere, a polymorphic interface feels like the more principled approach even if this is perhaps the least compelling example of it. ;] Ultimately, there is still a lot more to be done here, but this was the huge chunk that I couldn't really split things out of because this was the interface change to TTI. I've tried to minimize all the other parts of this. The follow up work should include at least: 1) Improving the TargetMachine interface by having it directly return a TTI object. Because we have a non-pass object with value semantics and an internal type erasure mechanism, we can narrow the interface of the TargetMachine to *just* do what we need: build and return a TTI object that we can then insert into the pass pipeline. 2) Make the TTI object be fully specialized for a particular function. This will include splitting off a minimal form of it which is sufficient for the inliner and the old pass manager. 3) Add a new pass manager analysis which produces TTI objects from the target machine for each function. This may actually be done as part of #2 in order to use the new analysis to implement #2. 4) Work on narrowing the API between TTI and the targets so that it is easier to understand and less verbose to type erase. 5) Work on narrowing the API between TTI and its clients so that it is easier to understand and less verbose to forward. 6) Try to improve the CRTP-based delegation. I feel like this code is just a bit messy and exacerbating the complexity of implementing the TTI in each target. Many thanks to Eric and Hal for their help here. I ended up blocked on this somewhat more abruptly than I expected, and so I appreciate getting it sorted out very quickly. Differential Revision: http://reviews.llvm.org/D7293 llvm-svn: 227669
* Remove unnecessary copying or replace it with moves in a bunch of places.Benjamin Kramer2014-10-041-2/+2
| | | | | | NFC. llvm-svn: 219061
* ConstantHoisting.cpp: Add <tuple> for std::tie, since r207593 removed ↵NAKAMURA Takumi2014-04-301-0/+1
| | | | | | FileSystem.h, it includes <tuple>. llvm-svn: 207614
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-1/+2
| | | | llvm-svn: 207196
* [Constant Hoisting] Materialize the constant before the cloned cast instruction.Juergen Ributzka2014-04-221-2/+11
| | | | | | | | | | | | In the case where the constant comes from a cloned cast instruction, the materialization code has to go before the cloned cast instruction. This commit fixes the method that finds the materialization insertion point by making it aware of this case. This fixes <rdar://problem/15532441> llvm-svn: 206913
* [Constant Hoisting] Print the instructions in the correct order for ↵Juergen Ributzka2014-04-221-2/+2
| | | | | | debugging. No functional change. llvm-svn: 206912
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | | | | | | 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. llvm-svn: 206844
* Revert "[Constant Hoisting] Lazily compute the idom and cache the result."Juergen Ributzka2014-04-031-43/+4
| | | | | | | This code is no longer usefull, because we only compute and use the IDom once. There is no benefit in caching it anymore. llvm-svn: 205498
* [Constant Hoisting] Make the constant candidate map local to the ↵Juergen Ributzka2014-03-251-11/+14
| | | | | | collectConstantCandidates method. llvm-svn: 204758
* [Constant Hoisting] Erase dead cast instructions.Juergen Ributzka2014-03-221-1/+1
| | | | | | | The cleanup code that removes dead cast instructions only removed them from the basic block, but didn't delete them. This fix erases them now too. llvm-svn: 204538
* [Constant Hoisting] Fix multiple entries for the same basic block in PHI nodes.Juergen Ributzka2014-03-221-3/+36
| | | | | | | | | | | | | | | | | | | | A PHI node usually has only one value/basic block pair per incoming basic block. In the case of a switch statement it is possible that a following PHI node may have more than one such pair per incoming basic block. E.g.: %0 = phi i64 [ 123456, %case2 ], [ 654321, %Entry ], [ 654321, %Entry ] This is valid and the verfier doesn't complain, because both values are the same. Constant hoisting materializes the constant for each operand separately and the value is still the same, but the variable names have changed. As a result the verfier can't recognize anymore that they are the same value and complains. This fix adds special update code for PHI node in constant hoisting to prevent this corner case. This fixes <rdar://problem/16394449> llvm-svn: 204537
* [Constant Hoisting] Make the constant materialization cost operand dependentJuergen Ributzka2014-03-211-7/+7
| | | | | | | | | Extend the target hook to take also the operand index into account when calculating the cost of the constant materialization. Related to <rdar://problem/16381500> llvm-svn: 204435
* [Constant Hoisting] Lazily compute the idom and cache the result.Juergen Ributzka2014-03-211-4/+43
| | | | | | Related to <rdar://problem/16381500> llvm-svn: 204434
* [Constant Hoisting] Change the algorithm to only track constants for ↵Juergen Ributzka2014-03-211-239/+321
| | | | | | | | | | | | | | | | | | | | | | | | instructions. Originally the algorithm would search for expensive constants and track their users, which could be instructions and constant expressions. This change only tracks the constants for instructions, but constant expressions are indirectly covered too. If an operand is an constant expression, then we look through the expression to find anny expensive constants. The algorithm keep now track of the instruction and the operand index where the constant is used. This allows more precise hoisting of constant materialization code for PHI instructions, because we only hoist to the basic block of the incoming operand. Before we had to find the idom of all PHI operands and hoist the materialization code there. This also makes updating of instructions easier. Before we had to keep track of the original constant, find it in the instructions, and then replace it. Now we can just simply update the operand. Related to <rdar://problem/16381500> llvm-svn: 204433
* [Constant Hoisting] Fix capitalization of function names.Juergen Ributzka2014-03-211-33/+34
| | | | llvm-svn: 204432
* [Constant Hoisting] Replace the MapVector with a separate Map and Vector to ↵Juergen Ributzka2014-03-211-38/+51
| | | | | | | | | | | keep track of constant candidates. This simplifies working with the constant candidates and removes the tight coupling between the map and the vector. Related to <rdar://problem/16381500> llvm-svn: 204431
* Revert "[Constant Hoisting] Extend coverage of the constant hoisting pass."Juergen Ributzka2014-03-201-391/+259
| | | | | | I will break this up into smaller pieces for review and recommit. llvm-svn: 204393
* [Constant Hoisting] Extend coverage of the constant hoisting pass.Juergen Ributzka2014-03-201-259/+391
| | | | | | | | | This commit extends the coverage of the constant hoisting pass, adds additonal debug output and updates the function names according to the style guide. Related to <rdar://problem/16381500> llvm-svn: 204389
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-8/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. =] llvm-svn: 203364
* [C++11] Convert sort predicates into lambdas.Benjamin Kramer2014-03-071-13/+8
| | | | | | No functionality change. llvm-svn: 203288
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-3/+3
| | | | | | class. llvm-svn: 202953
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-2/+2
| | | | | | Remove the old functions. llvm-svn: 202636
* [C++11] Switch all uses of the llvm_move macro to use std::moveChandler Carruth2014-03-021-1/+1
| | | | | | directly, and remove the macro. llvm-svn: 202612
* Fix typosAlp Toker2014-02-251-1/+1
| | | | llvm-svn: 202107
* [Constant Hoisting] Fix insertion point for constant materialization.Juergen Ributzka2014-02-081-18/+21
| | | | | | | | | | The bitcast instruction during constant materialization was not placed correcly in the presence of phi nodes. This commit fixes the insertion point to be in the idom instead. This fixes PR18768 llvm-svn: 201009
* [Constant Hoisting] Don't update the use list while traversing it - DOH!Juergen Ributzka2014-02-081-5/+16
| | | | | | | | This fix first traverses the whole use list of the constant expression and keeps track of the instructions that need to be updated. Then perform the fixup afterwards. llvm-svn: 201008
* ConstantHoisting: We can't insert instructions directly in front of a PHI node.Benjamin Kramer2014-01-271-3/+18
| | | | | | Insert before the terminating instruction of the dominating block instead. llvm-svn: 200218
* Revert "Revert "Add Constant Hoisting Pass" (r200034)"Juergen Ributzka2014-01-251-0/+436
| | | | | | | This reverts commit r200058 and adds the using directive for ARMTargetTransformInfo to silence two g++ overload warnings. llvm-svn: 200062
* Revert "Add Constant Hoisting Pass" (r200034)Hans Wennborg2014-01-251-436/+0
| | | | | | | | | | | | | | | This commit caused -Woverloaded-virtual warnings. The two new TargetTransformInfo::getIntImmCost functions were only added to the superclass, and to the X86 subclass. The other targets were not updated, and the warning highlighted this by pointing out that e.g. ARMTTI::getIntImmCost was hiding the two new getIntImmCost variants. We could pacify the warning by adding "using TargetTransformInfo::getIntImmCost" to the various subclasses, or turning it off, but I suspect that it's wrong to leave the functions unimplemnted in those targets. The default implementations return TCC_Free, which I don't think is right e.g. for ARM. llvm-svn: 200058
* Add Constant Hoisting PassJuergen Ributzka2014-01-241-0/+436
| | | | | | | | Retry commit r200022 with a fix for the build bot errors. Constant expressions have (unlike instructions) module scope use lists and therefore may have users in different functions. The fix is to simply ignore these out-of-function uses. llvm-svn: 200034
* Revert "Add Constant Hoisting Pass"Juergen Ributzka2014-01-241-429/+0
| | | | | | This reverts commit r200022 to unbreak the build bots. llvm-svn: 200024
* Add Constant Hoisting PassJuergen Ributzka2014-01-241-0/+429
This pass identifies expensive constants to hoist and coalesces them to better prepare it for SelectionDAG-based code generation. This works around the limitations of the basic-block-at-a-time approach. First it scans all instructions for integer constants and calculates its cost. If the constant can be folded into the instruction (the cost is TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't consider it expensive and leave it alone. This is the default behavior and the default implementation of getIntImmCost will always return TCC_Free. If the cost is more than TCC_BASIC, then the integer constant can't be folded into the instruction and it might be beneficial to hoist the constant. Similar constants are coalesced to reduce register pressure and materialization code. When a constant is hoisted, it is also hidden behind a bitcast to force it to be live-out of the basic block. Otherwise the constant would be just duplicated and each basic block would have its own copy in the SelectionDAG. The SelectionDAG recognizes such constants as opaque and doesn't perform certain transformations on them, which would create a new expensive constant. This optimization is only applied to integer constants in instructions and simple (this means not nested) constant cast experessions. For example: %0 = load i64* inttoptr (i64 big_constant to i64*) Reviewed by Eric llvm-svn: 200022
OpenPOWER on IntegriCloud