summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/Reassociate.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Teach the reassociate pass to fold chains of multiplies with repeatedChandler Carruth2012-04-261-10/+247
| | | | | | | | | | | | | | | | | elements to minimize the number of multiplies required to compute the final result. This uses a heuristic to attempt to form near-optimal binary exponentiation-style multiply chains. While there are some cases it misses, it seems to at least a decent job on a very diverse range of inputs. Initial benchmarks show no interesting regressions, and an 8% improvement on SPASS. Let me know if any other interesting results (in either direction) crop up! Credit to Richard Smith for the core algorithm, and helping code the patch itself. llvm-svn: 155616
* Prune some includes and forward declarations.Craig Topper2012-03-261-5/+5
| | | | llvm-svn: 153429
* Silence a bunch (but not all) "variable written but not read" warningsDuncan Sands2011-08-121-1/+1
| | | | | | when building with assertions disabled. llvm-svn: 137460
* Revert r136503 and r136480 in an effort to fix non-determinism in the ↵Owen Anderson2011-08-021-22/+1
| | | | | | llvm-gcc buildbots on i386. Devang is looking into the root cause. llvm-svn: 136674
* Clear DbgValues in the end.Devang Patel2011-07-291-0/+1
| | | | llvm-svn: 136503
* Clean up debug info after reassociation.Devang Patel2011-07-291-1/+21
| | | | llvm-svn: 136480
* start using the new helper methods a bit.Chris Lattner2011-07-151-1/+1
| | | | llvm-svn: 135251
* Preserve line number information.Devang Patel2011-04-281-0/+7
| | | | llvm-svn: 130450
* Fix reassociate to use a worklist instead of recursing when newDan Gohman2011-04-121-59/+67
| | | | | | | | | reassociation opportunities are exposed. This fixes a bug where the nested reassociation expects to be the IR to be consistent, but it isn't, because the outer reassociation has disconnected some of the operands. rdar://9167457 llvm-svn: 129324
* RecursivelyDeleteTriviallyDeadInstructions only needs aDan Gohman2011-03-101-3/+2
| | | | | | | | Value, not an Instruction, so casting is not necessary. Also, it's theoretically possible that the Value is not an Instruction, since WeakVH follows RAUWs. llvm-svn: 127427
* Fix reassociate to postpone certain instruction deletions untilDan Gohman2011-03-101-3/+11
| | | | | | | | | | after it has finished all of its reassociations, because its habit of unlinking operands and holding them in a datastructure while working means that it's not easy to determine when an instruction is really dead until after all its regular work is done. rdar://9096268. llvm-svn: 127424
* fix PR9215, preventing -reassociate from clearing nsw/nuw whenChris Lattner2011-02-171-3/+4
| | | | | | it swaps the LHS/RHS of a single binop. llvm-svn: 125700
* Fix reassociate to clear optional flags, such as nsw.Dan Gohman2011-02-021-0/+16
| | | | llvm-svn: 124712
* Fix PR9039, a use-after-free in reassociate. The issue was that theDuncan Sands2011-01-261-4/+11
| | | | | | | | operand being factorized (and erased) could occur several times in Ops, resulting in freed memory being used when the next occurrence in Ops was analyzed. llvm-svn: 124287
* Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson2010-10-191-1/+3
| | | | | | | | | | | | | | | | | exposes an initializeMyPassFunction(), which must be called in the pass's constructor. This function uses static dependency declarations to recursively initialize the pass's dependencies. Clients that only create passes through the createFooPass() APIs will require no changes. Clients that want to use the CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h before parsing commandline arguments. I have tested this with all standard configurations of clang and llvm-gcc on Darwin. It is possible that there are problems with the static dependencies that will only be visible with non-standard options. If you encounter any crash in pass registration/creation, please send the testcase to me directly. llvm-svn: 116820
* Now with fewer extraneous semicolons!Owen Anderson2010-10-071-1/+1
| | | | llvm-svn: 115996
* Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson2010-08-061-1/+1
| | | | llvm-svn: 110460
* Revert r110396 to fix buildbots.Owen Anderson2010-08-061-1/+1
| | | | llvm-svn: 110410
* Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson2010-08-051-1/+1
| | | | | | | | address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. llvm-svn: 110396
* Fix batch of converting RegisterPass<> to INTIALIZE_PASS().Owen Anderson2010-07-211-1/+2
| | | | llvm-svn: 109045
* cache dereferenced iteratorsGabor Greif2010-07-121-2/+3
| | | | llvm-svn: 108138
* fix a nice subtle reassociate bug which would only occurChris Lattner2010-03-051-5/+21
| | | | | | | in a very specific use pattern embodied in the carefully reduced testcase. llvm-svn: 97794
* There are two ways of checking for a given type, for example isa<PointerType>(T)Duncan Sands2010-02-161-1/+1
| | | | | | | and T->isPointerTy(). Convert most instances of the first form to the second form. Requested by Chris. llvm-svn: 96344
* Uniformize the names of type predicates: rather than having isFloatTy andDuncan Sands2010-02-151-3/+3
| | | | | | isInteger, we now have isFloatTy and isIntegerTy. Requested by Chris! llvm-svn: 96223
OpenPOWER on IntegriCloud