summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/Reassociate.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Reassociate: cannot negate a INT_MIN valueMehdi Amini2015-02-111-1/+1
| | | | | | | | | | | | | | | | | | Summary: When trying to canonicalize negative constants out of multiplication expressions, we need to check that the constant is not INT_MIN which cannot be negated. Reviewers: mcrosier Reviewed By: mcrosier Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D7286 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 228872
* Fix Reassociate handling of constant in presence of undef floatMehdi Amini2015-01-161-3/+6
| | | | | | http://reviews.llvm.org/D6993 llvm-svn: 226245
* [Reassociate] Use dbgs() instead of errs().Chad Rosier2014-12-121-2/+2
| | | | llvm-svn: 224125
* This Reassociate change unintentionally slipped in r222499David Majnemer2014-11-211-7/+0
| | | | llvm-svn: 222500
* SROA: The alloca type isn't a candidate promotion type for vectorsDavid Majnemer2014-11-211-0/+7
| | | | | | | | | | | | The alloca's type is irrelevant, only those types which are used in a load or store of the exact size of the slice should be considered. This manifested as an assertion failure when we compared the various types: we had a size mismatch. This fixes PR21480. llvm-svn: 222499
* Revert "[Reassociate] As the expression tree is rewritten make sure the ↵Chad Rosier2014-11-191-8/+7
| | | | | | | | | | | | | operands are" This reverts commit r222142. This is causing/exposing an execution-time regression in spec2006/gcc and coremark on AArch64/A57/Ofast. Conflicts: test/Transforms/Reassociate/optional-flags.ll llvm-svn: 222398
* Update SetVector to rely on the underlying set's insert to return a ↵David Blaikie2014-11-191-4/+4
| | | | | | | | | | | | | pair<iterator, bool> This is to be consistent with StringSet and ultimately with the standard library's associative container insert function. This lead to updating SmallSet::insert to return pair<iterator, bool>, and then to update SmallPtrSet::insert to return pair<iterator, bool>, and then to update all the existing users of those functions... llvm-svn: 222334
* [Reassociate] Rename local variable to not use same name as a memberChad Rosier2014-11-181-4/+4
| | | | | | variable. NFC. llvm-svn: 222248
* [Reassociate] As the expression tree is rewritten make sure the operands areChad Rosier2014-11-171-7/+8
| | | | | | emitted in canonical form. llvm-svn: 222142
* [Reassociate] Canonicalize constants to RHS operand.Chad Rosier2014-11-171-1/+4
| | | | | | Fix a thinko where the RHS was already a constant. llvm-svn: 222139
* [Reassociate] Canonicalize the operands of all binary operators.Chad Rosier2014-11-141-12/+12
| | | | llvm-svn: 222008
* [Reassociate] Canonicalize operands of vector binary operators.Chad Rosier2014-11-141-6/+1
| | | | | | | | Prior to this commit fmul and fadd binary operators were being canonicalized for both scalar and vector versions. We now canonicalize add, mul, and, or, and xor vector instructions. llvm-svn: 222006
* [Reassociate] Canonicalize constants to RHS operand.Chad Rosier2014-11-141-12/+17
| | | | llvm-svn: 222005
* [Reassociate] Improve rank debug information. NFC.Chad Rosier2014-11-141-4/+5
| | | | llvm-svn: 221999
* [Reassociate] Update comment. NFC.Chad Rosier2014-11-131-1/+1
| | | | llvm-svn: 221894
* [Reassociate] Canonicalize negative constants out of expressions.Chad Rosier2014-11-111-1/+2
| | | | | | Add support for FDiv, which was regressed by the previous commit. llvm-svn: 221738
* [Reassociate] Canonicalize negative constants out of expressions.Chad Rosier2014-11-111-42/+91
| | | | | | | | This is a reapplication of r221171, but we only perform the transformation on expressions which include a multiplication. We do not transform rem/div operations as this doesn't appear to be safe in all cases. llvm-svn: 221721
* [Reassociate] Better preserve NSW/NUW flags.Chad Rosier2014-11-071-0/+11
| | | | | | | | Part of PR12985. Phabricator Revision: http://reviews.llvm.org/D6172 llvm-svn: 221555
* [Reassociate] Don't reassociate when mixing regular and fast-math FPChad Rosier2014-11-061-3/+9
| | | | | | | | | instructions. Inlining might cause such cases and it's not valid to reassociate floating-point instructions without the unsafe algebra flag. Patch by Mehdi Amini <mehdi_amini@apple.com>! llvm-svn: 221462
* Revert "[Reassociate] Canonicalize negative constants out of expressions."Reid Kleckner2014-11-041-101/+42
| | | | | | | | | | | | This reverts commit r221171. It performs this invalid transformation: - %div.i = urem i64 -1, %add - %sub.i = sub i64 -2, %div.i + %div.i = urem i64 1, %add + %sub.i1 = add i64 %div.i, -2 llvm-svn: 221317
* [Reassociate] Canonicalize negative constants out of expressions.Chad Rosier2014-11-031-42/+101
| | | | | | | | | This gives CSE/GVN more options to eliminate duplicate expressions. This is a follow up patch to http://reviews.llvm.org/D4904. http://reviews.llvm.org/D5363 llvm-svn: 221171
* [Reassociate] Don't canonicalize X - undef to X + (-undef).Chad Rosier2014-10-091-0/+4
| | | | | | | Phabricator Revision: http://reviews.llvm.org/D5674 PR21205 llvm-svn: 219434
* Give the Reassociate pass a bit more flexibility and autonomy when ↵Owen Anderson2014-10-051-2/+12
| | | | | | | | | | optimizing expressions. Particularly, it addresses cases where Reassociate breaks Subtracts but then fails to optimize combinations like I1 + -I2 where I1 and I2 have the same rank and are identical. Patch by Dmitri Shtilman. llvm-svn: 219092
* Reassociate x + -0.1234 * y into x - 0.1234 * yErik Verbruggen2014-08-211-2/+49
| | | | | | | | | | | This does not require -ffast-math, and it gives CSE/GVN more options to eliminate duplicate expressions in, e.g.: return ((x + 0.1234 * y) * (x - 0.1234 * y)); Differential Revision: http://reviews.llvm.org/D4904 llvm-svn: 216169
* [Reassociation] Add support for reassociation with unsafe algebra.Chad Rosier2014-08-141-81/+228
| | | | | | | Vector instructions are (still) not supported for either integer or floating point. Hopefully, that work will be landed shortly. llvm-svn: 215647
* [Reassociate] Similar to "X + -X" -> "0", added code to handle "X + ~X" -> "-1".Benjamin Kramer2014-05-311-8/+23
| | | | | | | | | | | | Handle "X + ~X" -> "-1" in the function Value *Reassociate::OptimizeAdd(Instruction *I, SmallVectorImpl<ValueEntry> &Ops); This patch implements: TODO: We could handle "X + ~X" -> "-1" if we wanted, since "-X = ~X+1". Patch by Rahul Jain! Differential Revision: http://reviews.llvm.org/D3835 llvm-svn: 209973
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-20/+20
| | | | llvm-svn: 207196
* [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
OpenPOWER on IntegriCloud