summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/Reassociate.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [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
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-13/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-2/+2
| | | | | | class. llvm-svn: 202953
* [Modules] Move CFG.h to the IR library as it defines graph traits overChandler Carruth2014-03-041-1/+1
| | | | | | IR types. llvm-svn: 202827
* [Modules] Move ValueHandle into the IR library where Value itself lives.Chandler Carruth2014-03-041-1/+1
| | | | | | | | | | | 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. llvm-svn: 202821
* Now that we have C++11, turn simple functors into lambdas and remove a ton ↵Benjamin Kramer2014-03-011-13/+0
| | | | | | | | of boilerplate. No intended functionality change. llvm-svn: 202588
* [reassociate] Switch two std::sort calls into std::stable_sort calls asChandler Carruth2014-02-251-2/+2
| | | | | | | | | | | | | | | their inputs come from std::stable_sort and they are not total orders. I'm not a huge fan of this, but the really bad std::stable_sort is right at the beginning of Reassociate. After we commit to stable-sort based consistent respect of source order, the downstream sorts shouldn't undo that unless they have a total order or they are used in an order-insensitive way. Neither appears to be true for these cases. I don't have particularly good test cases, but this jumped out by inspection when looking for output instability in this pass due to changes in the ordering of std::sort. llvm-svn: 202196
* Disable most IR-level transform passes on functions marked 'optnone'.Paul Robinson2014-02-061-0/+3
| | | | | | | | | 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. llvm-svn: 200892
* Put the functionality for printing a value to a raw_ostream as anChandler Carruth2014-01-091-2/+1
| | | | | | | | | | | | operand into the Value interface just like the core print method is. That gives a more conistent organization to the IR printing interfaces -- they are all attached to the IR objects themselves. Also, update all the users. This removes the 'Writer.h' header which contained only a single function declaration. llvm-svn: 198836
* Move the LLVM IR asm writer header files into the IR directory, as theyChandler Carruth2014-01-071-1/+1
| | | | | | | | | | | | | | | | | are part of the core IR library in order to support dumping and other basic functionality. Rename the 'Assembly' include directory to 'AsmParser' to match the library name and the only functionality left their -- printing has been in the core IR library for quite some time. Update all of the #includes to match. All of this started because I wanted to have the layering in good shape before I started adding support for printing LLVM IR using the new pass infrastructure, and commandline support for the new pass infrastructure. llvm-svn: 198688
* Use switch instead of if. No functionality change.Jakub Staszak2013-07-221-14/+17
| | | | llvm-svn: 186892
* Reassociate: Remove unnecessary default operator=.Benjamin Kramer2013-07-061-10/+0
| | | | llvm-svn: 185757
* Fix a XOR reassociation bug. Shuxin Yang2013-04-271-3/+6
| | | | | | | | | | When Reassociator optimize "(x | C1)" ^ "(X & C2)", it may swap the two subexpressions, however, it forgot to swap cached constants (of C1 and C2) accordingly. rdar://13739160 llvm-svn: 180676
* Redo the fix Benjamin Kramer committed in r178793 about iterator ↵Shuxin Yang2013-04-081-12/+14
| | | | | | | | | | | | | | | | | invalidation in Reassociate. I brazenly think this change is slightly simpler than r178793 because: - no "state" in functor - "OpndPtrs[i]" looks simpler than "&Opnds[OpndIndices[i]]" While I can reproduce the probelm in Valgrind, it is rather difficult to come up a standalone testing case. The reason is that when an iterator is invalidated, the stale invalidated elements are not yet clobbered by nonsense data, so the optimizer can still proceed successfully. Thank Benjamin for fixing this bug and generously providing the test case. llvm-svn: 179062
* Reassociate: Avoid iterator invalidation.Benjamin Kramer2013-04-041-7/+12
| | | | | | | | OpndPtrs stored pointers into the Opnd vector that became invalid when the vector grows. Store indices instead. Sadly I only have a large testcase that only triggers under valgrind, so I didn't include it. llvm-svn: 178793
* Correct assertion conditionShuxin Yang2013-04-011-1/+1
| | | | llvm-svn: 178484
* Implement XOR reassociation. It is based on following rules:Shuxin Yang2013-03-301-1/+325
| | | | | | | | | | | | | | | rule 1: (x | c1) ^ c2 => (x & ~c1) ^ (c1^c2), only useful when c1=c2 rule 2: (x & c1) ^ (x & c2) = (x & (c1^c2)) rule 3: (x | c1) ^ (x | c2) = (x & c3) ^ c3 where c3 = c1 ^ c2 rule 4: (x | c1) ^ (x & c2) => (x & c3) ^ c1, where c3 = ~c1 ^ c2 It reduces an application's size (in terms of # of instructions) by 8.9%. Reviwed by Pete Cooper. Thanks a lot! rdar://13212115 llvm-svn: 178409
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-6/+6
| | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-7/+7
| | | | | | | | | | | | | | | | | 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. =] llvm-svn: 169131
* Remove the last bit of constant folding from LinearizeExprTree (most of it wasDuncan Sands2012-11-181-11/+0
| | | | | | removed in commit 168035, but I missed this bit). llvm-svn: 168292
* Fix PR14060, an infinite loop in reassociate. The problem was that one of theDuncan Sands2012-11-181-6/+24
| | | | | | | | | | operands of the expression being written was wrongly thought to be reusable as an inner node of the expression resulting in it turning up as both an inner node *and* a leaf, creating a cycle in the def-use graph. This would have caused the verifier to blow up if things had gotten that far, however it managed to provoke an infinite loop first. llvm-svn: 168291
* Fix a crash observed by Shuxin Yang. The issue here is that LinearizeExprTree,Duncan Sands2012-11-151-54/+21
| | | | | | | | | | | | | | the utility for extracting a chain of operations from the IR, thought that it might as well combine any constants it came across (rather than just returning them along with everything else). On the other hand, the factorization code would like to see the individual constants (this is quite reasonable: it is much easier to pull a factor of 3 out of 2*3 than it is to pull it out of 6; you may think 6/3 isn't so hard, but due to overflow it's not as easy to undo multiplications of constants as it may at first appear). This patch therefore makes LinearizeExprTree stupider: it now leaves optimizing to the optimization part of reassociate, and sticks to just analysing the IR. llvm-svn: 168035
* revert r167740Shuxin Yang2012-11-131-314/+8
| | | | llvm-svn: 167787
* This change is to fix rdar://12571717 which is about assertion in ↵Shuxin Yang2012-11-121-8/+314
| | | | | | | | | | | | | | | | | | Reassociate pass. The assertion is trigged when the Reassociater tries to transform expression ... + 2 * n * 3 + 2 * m + ... into: ... + 2 * (n*3 + m). In the process of the transformation, a helper routine folds the constant 2*3 into 6, confusing optimizer which is trying the to eliminate the common factor 2, and cannot find 2 any more. Review is pending. But I'd like commit first in order to help those who are waiting for this fix. llvm-svn: 167740
* Stop reassociate from looking through expressions of arbitrary complexity. ThisDuncan Sands2012-07-261-0/+2
| | | | | | is a temporary measure until my fix for PR13021 is ready. llvm-svn: 160778
* Clean whitespaces.Nadav Rotem2012-07-241-1/+1
| | | | llvm-svn: 160668
* Suppress a warning.Nadav Rotem2012-07-231-1/+2
| | | | llvm-svn: 160629
* Rework this to clarify where the removal of nodes from the queue isDuncan Sands2012-06-291-8/+9
| | | | | | really happening. No intended functionality change. llvm-svn: 159451
* Fix a reassociate crash on sozefx when compiling with dragonegg+gcc-4.7 due toDuncan Sands2012-06-291-5/+13
| | | | | | | the optimizers producing a multiply expression with more multiplications than the original (!). llvm-svn: 159426
* Move llvm/Support/IRBuilder.h -> llvm/IRBuilder.hChandler Carruth2012-06-291-6/+6
| | | | | | | | | | | | | | | | | This was always part of the VMCore library out of necessity -- it deals entirely in the IR. The .cpp file in fact was already part of the VMCore library. This is just a mechanical move. I've tried to go through and re-apply the coding standard's preferred header sort, but at 40-ish files, I may have gotten some wrong. Please let me know if so. I'll be committing the corresponding updates to Clang and Polly, and Duncan has DragonEgg. Thanks to Bill and Eric for giving the green light for this bit of cleanup. llvm-svn: 159421
* Some reassociate optimizations create new instructions, which they insert justDuncan Sands2012-06-271-11/+7
| | | | | | | | | | | before the expression root. Any existing operators that are changed to use one of them needs to be moved between it and the expression root, and recursively for the operators using that one. When I rewrote RewriteExprTree I accidentally inverted the logic, resulting in the compacting going down from operators to operands rather than up from operands to the operators using them, oops. Fix this, resolving PR12963. llvm-svn: 159265
* Remove a dangling reference to a deleted instruction. Fixes PR13185!Nick Lewycky2012-06-241-0/+1
| | | | llvm-svn: 159096
* Fix issues (infinite loop and/or crash) with self-referential instructions, forDuncan Sands2012-06-151-6/+14
| | | | | | | example degenerate phi nodes and binops that use themselves in unreachable code. Thanks to Charles Davis for the testcase that uncovered this can of worms. llvm-svn: 158508
* It is possible for several constants which aren't individually absorbing toDuncan Sands2012-06-131-1/+6
| | | | | | | combine to the absorbing element. Thanks to nbjoerg on IRC for pointing this out. llvm-svn: 158399
* When linearizing a multiplication, return at once if we see a factor of zero,Duncan Sands2012-06-131-40/+14
| | | | | | | | | since then the entire expression must equal zero (similarly for other operations with an absorbing element). With this in place a bunch of reassociate code for handling constants is dead since it is all taken care of when linearizing. No intended functionality change. llvm-svn: 158398
* Use DenseMap as SmallMap workaround rather than std::map, at Chandler's request.Duncan Sands2012-06-121-1/+1
| | | | llvm-svn: 158371
* Use std::map rather than SmallMap because SmallMap assumes that the value hasDuncan Sands2012-06-121-2/+1
| | | | | | | POD type, causing memory corruption when mapping to APInts with bitwidth > 64. Merge another crash testcase into crash.ll while there. llvm-svn: 158369
* Now that Reassociate's LinearizeExprTree can look through arbitrary expressionDuncan Sands2012-06-121-25/+204
| | | | | | | | | | | | | | | | | topologies, it is quite possible for a leaf node to have huge multiplicity, for example: x0 = x*x, x1 = x0*x0, x2 = x1*x1, ... rapidly gives a value which is x raised to a vast power (the multiplicity, or weight, of x). This patch fixes the computation of weights by correctly computing them no matter how big they are, rather than just overflowing and getting a wrong value. It turns out that the weight for a value never needs more bits to represent than the value itself, so it is enough to represent weights as APInts of the same bitwidth and do the right overflow-avoiding dance steps when computing weights. As a side-effect it reduces the number of multiplies needed in some cases of large powers. While there, in view of external uses (eg by the vectorizer) I made LinearizeExprTree static, pushing the rank computation out into users. This is progress towards fixing PR13021. llvm-svn: 158358
* Reapply commit 158073 with a fix (the testcase was already committed). TheDuncan Sands2012-06-081-123/+120
| | | | | | | | | | | | | | | | | | problem was that by moving instructions around inside the function, the pass could accidentally move the iterator being used to advance over the function too. Fix this by only processing the instruction equal to the iterator, and leaving processing of instructions that might not be equal to the iterator to later (later = after traversing the basic block; it could also wait until after traversing the entire function, but this might make the sets quite big). Original commit message: Grab-bag of reassociate tweaks. Unify handling of dead instructions and instructions to reoptimize. Exploit this to more systematically eliminate dead instructions (this isn't very useful in practice but is convenient for analysing some testcase I am working on). No need for WeakVH any more: use an AssertingVH instead. llvm-svn: 158226
* Revert commit 158073 while waiting for a fix. The issue is that reassociateDuncan Sands2012-06-081-111/+123
| | | | | | | | | | | | | | | | can move instructions within the instruction list. If the instruction just happens to be the one the basic block iterator is pointing to, and it is moved to a different basic block, then we get into an infinite loop due to the iterator running off the end of the basic block (for some reason this doesn't fire any assertions). Original commit message: Grab-bag of reassociate tweaks. Unify handling of dead instructions and instructions to reoptimize. Exploit this to more systematically eliminate dead instructions (this isn't very useful in practice but is convenient for analysing some testcase I am working on). No need for WeakVH any more: use an AssertingVH instead. llvm-svn: 158199
* Grab-bag of reassociate tweaks. Unify handling of dead instructions andDuncan Sands2012-06-061-123/+111
| | | | | | | | | instructions to reoptimize. Exploit this to more systematically eliminate dead instructions (this isn't very useful in practice but is convenient for analysing some testcase I am working on). No need for WeakVH any more: use an AssertingVH instead. llvm-svn: 158073
* Fix typos found by http://github.com/lyda/misspell-checkBenjamin Kramer2012-06-021-1/+1
| | | | llvm-svn: 157885
* Since commit 157467, if reassociate isn't actually going to change an expressionDuncan Sands2012-05-261-17/+20
| | | | | | | | | | | then it doesn't alter the instructions composing it, however it would continue to move the instructions to just before the expression root. Ensure it doesn't move them either, so now it really does nothing if there is nothing to do. That commit also ensured that nsw etc flags weren't cleared if the expression was not being changed. Tweak this a bit so that it doesn't clear flags on the initial part of a computation either if that part didn't change but later bits did. llvm-svn: 157518
* Move this debug statement earlier so it is easy to see the order inDuncan Sands2012-05-261-2/+2
| | | | | | which operands come flying out of the linearization stage. llvm-svn: 157512
* Make the reassociation pass more powerful so that it can handle expressionsDuncan Sands2012-05-251-255/+405
| | | | | | | | | | | | | | | | | with arbitrary topologies (previously it would give up when hitting a diamond in the use graph for example). The testcase from PR12764 is now reduced from a pile of additions to the optimal 1617*%x0+208. In doing this I changed the previous strategy of dropping all uses for expression leaves to one of dropping all but one use. This works out more neatly (but required a bunch of tweaks) and is also safer: some recently fixed bugs during recursive linearization were because the linearization code thinks it completely owns a node if it has no uses outside the expression it is linearizing. But if the node was also in another expression that had been linearized (and thus all uses of the node from that expression dropped) then the conclusion that it is completely owned by the expression currently being linearized is wrong. Keeping one use from within each linearized expression avoids this kind of mistake. llvm-svn: 157467
* Calling ReassociateExpression recursively is extremely dangerous since it willDuncan Sands2012-05-081-7/+7
| | | | | | | | | | | | | replace the operands of expressions with only one use with undef and generate a new expression for the original without using RAUW to update the original. Thus any copies of the original expression held in a vector may end up referring to some bogus value - and using a ValueHandle won't help since there is no RAUW. There is already a mechanism for getting the effect of recursion non-recursively: adding the value to be recursed on to RedoInsts. But it wasn't being used systematically. Have various places where recursion had snuck in at some point use the RedoInsts mechanism instead. Fixes PR12169. llvm-svn: 156379
* Teach reassociate to commute FMul's and FAdd's in order to canonicalize the ↵Owen Anderson2012-05-071-4/+28
| | | | | | order of their operands across instructions. This allows for greater CSE opportunities. llvm-svn: 156323
* Add 'landingpad' instructions to the list of instructions to ignore.Bill Wendling2012-05-041-7/+9
| | | | | | Also combine the code in the 'assert' statement. llvm-svn: 156155
* Whitespace cleanup.Bill Wendling2012-05-021-87/+80
| | | | llvm-svn: 156034
* The value held in the vector may be RAUW'ed by some of the canonicalizationBill Wendling2012-05-021-2/+3
| | | | | | | methods. Use a weak value handle to keep up with this. PR12245 llvm-svn: 155984
OpenPOWER on IntegriCloud