summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/Reassociate.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Reassociate: add global reassociation algorithmFiona Glaser2017-12-121-2/+110
| | | | | | | | | | | | | | | | | | | | | | | This algorithm (explained more in the source code) takes into account global redundancies by building a "pair map" to find common subexprs. The primary motivation of this is to handle situations like foo = (a * b) * c bar = (a * d) * c where we currently don't identify that "a * c" is redundant. Accordingly, it prioritizes the emission of a * c so that CSE can remove the redundant calculation later. Does not change the actual reassociation algorithm -- only the order in which the reassociated operand chain is reconstructed. Gives ~1.5% floating point math instruction count reduction on a large offline suite of graphics shaders. llvm-svn: 320515
* [Reassociate] simplify code; NFCISanjay Patel2017-11-151-6/+3
| | | | llvm-svn: 318298
* [Reassociate] use dyn_cast instead of isa+cast; NFCISanjay Patel2017-11-141-9/+9
| | | | llvm-svn: 318212
* [Reassociate] don't name values "tmp"; NFCISanjay Patel2017-11-091-2/+2
| | | | | | | | | | The toxic stew of created values named 'tmp' and tests that already have values named 'tmp' and CHECK lines looking for values named 'tmp' causes bad things to happen in our test line auto-generation scripts because it wants to use 'TMP' as a prefix for unnamed values. Use less 'tmp' to avoid that. llvm-svn: 317818
* [IR] redefine 'UnsafeAlgebra' / 'reassoc' fast-math-flags and add 'trans' ↵Sanjay Patel2017-11-061-7/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | fast-math-flag As discussed on llvm-dev: http://lists.llvm.org/pipermail/llvm-dev/2016-November/107104.html and again more recently: http://lists.llvm.org/pipermail/llvm-dev/2017-October/118118.html ...this is a step in cleaning up our fast-math-flags implementation in IR to better match the capabilities of both clang's user-visible flags and the backend's flags for SDNode. As proposed in the above threads, we're replacing the 'UnsafeAlgebra' bit (which had the 'umbrella' meaning that all flags are set) with a new bit that only applies to algebraic reassociation - 'AllowReassoc'. We're also adding a bit to allow approximations for library functions called 'ApproxFunc' (this was initially proposed as 'libm' or similar). ...and we're out of bits. 7 bits ought to be enough for anyone, right? :) FWIW, I did look at getting this out of SubclassOptionalData via SubclassData (spacious 16-bits), but that's apparently already used for other purposes. Also, I don't think we can just add a field to FPMathOperator because Operator is not intended to be instantiated. We'll defer movement of FMF to another day. We keep the 'fast' keyword. I thought about removing that, but seeing IR like this: %f.fast = fadd reassoc nnan ninf nsz arcp contract afn float %op1, %op2 ...made me think we want to keep the shortcut synonym. Finally, this change is binary incompatible with existing IR as seen in the compatibility tests. This statement: "Newer releases can ignore features from older releases, but they cannot miscompile them. For example, if nsw is ever replaced with something else, dropping it would be a valid way to upgrade the IR." ( http://llvm.org/docs/DeveloperPolicy.html#ir-backwards-compatibility ) ...provides the flexibility we want to make this change without requiring a new IR version. Ie, we're not loosening the FP strictness of existing IR. At worst, we will fail to optimize some previously 'fast' code because it's no longer recognized as 'fast'. This should get fixed as we audit/squash all of the uses of 'isFast()'. Note: an inter-dependent clang commit to use the new API name should closely follow commit. Differential Revision: https://reviews.llvm.org/D39304 llvm-svn: 317488
* [Transforms] Fix some Clang-tidy modernize and Include What You Use ↵Eugene Zelenko2017-10-181-17/+30
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 316128
* [Reassociate] Do not drop debug location if replacement is missingMikael Holmen2017-08-241-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: When reassociating an expression, do not drop the instruction's original debug location in case the replacement location is missing. The debug location must at least not be dropped for inlinable callsites of debug-info-bearing functions in debug-info-bearing functions. Failing to do so would result in an "inlinable function " "call in a function with debug info must have a !dbg location" error in the verifier. As preserving the original debug location is not expected to result in overly jumpy debug line information, it is preserved for all other cases too. This fixes PR34231: https://bugs.llvm.org/show_bug.cgi?id=34231 Original patch by David Stenberg Reviewers: davide, craig.topper, mcrosier, dblaikie, aprantl Reviewed By: davide, aprantl Subscribers: aprantl Differential Revision: https://reviews.llvm.org/D36865 llvm-svn: 311642
* [Reassociate] Don't canonicalize x + (-Constant * y) -> x - (Constant * y)..Chad Rosier2017-08-231-0/+6
| | | | | | | | | | | | | ..if the resulting subtract will be broken up later. This can cause us to get into an infinite loop. x + (-5.0 * y) -> x - (5.0 * y) ; Canonicalize neg const x - (5.0 * y) -> x + (0 - (5.0 * y)) ; Break up subtract x + (0 - (5.0 * y)) -> x + (-5.0 * y) ; Replace 0-X with X*-1. PR34078 llvm-svn: 311554
* [Reassociate] Use a range loop for clarity. NFCI.Davide Italiano2017-08-071-5/+6
| | | | | | | | While here, rename `i` to `Rank` as the latter is more self-explanatory (and this code also uses `I` two lines below to identify an Instruction). llvm-svn: 310238
* [Reassociate] Try to bail out early when canonicalizing.Davide Italiano2017-08-071-6/+2
| | | | | | | This commit rearranges the checks to avoid calls to getRank() when not needed (e.g. when RHS == LHS). llvm-svn: 310237
* [Constants] If we already have a ConstantInt*, prefer to use ↵Craig Topper2017-07-061-1/+1
| | | | | | | | isZero/isOne/isMinusOne instead of isNullValue/isOneValue/isAllOnesValue inherited from Constant. NFCI Going through the Constant methods requires redetermining that the Constant is a ConstantInt and then calling isZero/isOne/isMinusOne. llvm-svn: 307292
* [Reassociate] Make sure EraseInst sets MadeChangeMikael Holmen2017-06-271-0/+2
| | | | | | | | | | | | | | | | | | | | | Summary: EraseInst didn't report that it made IR changes through MadeChange. It is essential that changes to the IR are reported correctly, since for example ReassociatePass::run() will indicate that all analyses are preserved otherwise. And the CGPassManager determines if the CallGraph is up-to-date based on status from InstructionCombiningPass::runOnFunction(). Reviewers: craig.topper, rnk, davide Reviewed By: rnk, davide Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34616 llvm-svn: 306368
* [Reassociate] Use early returns in a couple places to reduce indentation and ↵Craig Topper2017-06-211-26/+26
| | | | | | improve readability. NFC llvm-svn: 305946
* [Reassociate] Const correct a helper function. NFCCraig Topper2017-06-211-2/+2
| | | | llvm-svn: 305945
* [Reassociate] Support xor reassociating for splat vectorsCraig Topper2017-06-211-24/+22
| | | | | | | | | | | | | | Summary: This patch adds support for xors of splat vectors. Reviewers: mcrosier Reviewed By: mcrosier Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34354 llvm-svn: 305925
* [Reassociate] Support some reassociation of vector xorsCraig Topper2017-06-191-6/+7
| | | | | | | | | | | | | | | | | Summary: Currently we don't try to do anything with vector xors. This patch adds support for removing duplicate pairs from a chain of vector xors as its pretty easy to support. We still dont' try to combine the xors with and/ors, but I might try that in a future patch. Reviewers: mcrosier, davide, resistor Reviewed By: mcrosier Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34338 llvm-svn: 305704
* [Reassociate] Make one of the helper methods static because it doesn't use ↵Craig Topper2017-06-191-2/+2
| | | | | | any class variables. NFC llvm-svn: 305703
* [Reassociate] Use APInt::isNullValue() instead of comparing with 0. NFCCraig Topper2017-06-181-8/+9
| | | | | | This should compile to slightly better code. llvm-svn: 305651
* [IR] De-virtualize ~Value to save a vptrReid Kleckner2017-05-181-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Implements PR889 Removing the virtual table pointer from Value saves 1% of RSS when doing LTO of llc on Linux. The impact on time was positive, but too noisy to conclusively say that performance improved. Here is a link to the spreadsheet with the original data: https://docs.google.com/spreadsheets/d/1F4FHir0qYnV0MEp2sYYp_BuvnJgWlWPhWOwZ6LbW7W4/edit?usp=sharing This change makes it invalid to directly delete a Value, User, or Instruction pointer. Instead, such code can be rewritten to a null check and a call Value::deleteValue(). Value objects tend to have their lifetimes managed through iplist, so for the most part, this isn't a big deal. However, there are some places where LLVM deletes values, and those places had to be migrated to deleteValue. I have also created llvm::unique_value, which has a custom deleter, so it can be used in place of std::unique_ptr<Value>. I had to add the "DerivedUser" Deleter escape hatch for MemorySSA, which derives from User outside of lib/IR. Code in IR cannot include MemorySSA headers or call the MemoryAccess object destructors without introducing a circular dependency, so we need some level of indirection. Unfortunately, no class derived from User may have any virtual methods, because adding a virtual method would break User::getHungOffOperands(), which assumes that it can find the use list immediately prior to the User object. I've added a static_assert to the appropriate OperandTraits templates to help people avoid this trap. Reviewers: chandlerc, mehdi_amini, pete, dberlin, george.burgess.iv Reviewed By: chandlerc Subscribers: krytarowski, eraman, george.burgess.iv, mzolotukhin, Prazek, nlewycky, hans, inglorion, pcc, tejohnson, dberlin, llvm-commits Differential Revision: https://reviews.llvm.org/D31261 llvm-svn: 303362
* [IR] Prefer use_empty() to !hasNUsesOrMore(1) for clarity.Davide Italiano2017-05-161-1/+1
| | | | llvm-svn: 303218
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-05-011-2/+2
| | | | | | This relands r301424. llvm-svn: 301812
* Reverts commit r301424, r301425 and r301426Sanjoy Das2017-04-261-2/+2
| | | | | | | | | | | | Commits were: "Use WeakVH instead of WeakTrackingVH in AliasSetTracker's UnkownInsts" "Add a new WeakVH value handle; NFC" "Rename WeakVH to WeakTrackingVH; NFC" The changes assumed pointers are 8 byte aligned on all architectures. llvm-svn: 301429
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-04-261-2/+2
| | | | | | | | | | | | | | | | Summary: I plan to use WeakVH to mean "nulls itself out on deletion, but does not track RAUW" in a subsequent commit. Reviewers: dblaikie, davide Reviewed By: davide Subscribers: arsenm, mehdi_amini, mcrosier, mzolotukhin, jfb, llvm-commits, nhaehnle Differential Revision: https://reviews.llvm.org/D32266 llvm-svn: 301424
* [Reassociate] Add negated value of negative constant to the Duplicates list.Chad Rosier2017-02-231-4/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In OptimizeAdd, we scan the operand list to see if there are any common factors between operands that can be factored out to reduce the number of multiplies (e.g., 'A*A+A*B*C+D' -> 'A*(A+B*C)+D'). For each operand of the operand list, we only consider unique factors (which is tracked by the Duplicate set). Now if we find a factor that is a negative constant, we add the negated value as a factor as well, because we can percolate the negate out. However, we mistakenly don't add this negated constant to the Duplicates set. Consider the expression A*2*-2 + B. Obviously, nothing to factor. For the added value A*2*-2 we over count 2 as a factor without this change, which causes the assert reported in PR30256. The problem is that this code is assuming that all the multiply operands of the add are already reassociated. This change avoids the issue by making OptimizeAdd tolerate multiplies which haven't been completely optimized; this sort of works, but we're doing wasted work: we'll end up revisiting the add later anyway. Another possible approach would be to enforce RPO iteration order more strongly. If we have RedoInsts, we process them immediately in RPO order, rather than waiting until we've finished processing the whole function. Intuitively, it seems like the natural approach: reassociation works on expression trees, so the optimization only works in one direction. That said, I'm not sure how practical that is given the current Reassociate; the "optimal" form for an expression depends on its use list (see all the uses of "user_back()"), so Reassociate is really an iterative optimization of sorts, so any changes here would probably get messy. PR30256 Differential Revision: https://reviews.llvm.org/D30228 llvm-svn: 296003
* [Reassociate] Remove an unused argument. NFC.Chad Rosier2017-02-081-5/+4
| | | | llvm-svn: 294489
* [PM] Introduce an analysis set used to preserve all analyses overChandler Carruth2017-01-151-2/+2
| | | | | | | | | | | | | | | a function's CFG when that CFG is unchanged. This allows transformation passes to simply claim they preserve the CFG and analysis passes to check for the CFG being preserved to remove the fanout of all analyses being listed in all passes. I've gone through and removed or cleaned up as many of the comments reminding us to do this as I could. Differential Revision: https://reviews.llvm.org/D28627 llvm-svn: 292054
* Fixed the lost FastMathFlags in Reassociate optimization.Vyacheslav Klochkov2016-11-221-0/+6
| | | | | | | Reviewer: Hal Finkel. Differential Revision: https://reviews.llvm.org/D26957 llvm-svn: 287695
* Remove redundant condition (PR28352) NFCI.Simon Pilgrim2016-11-141-2/+3
| | | | | | We were already testing is the op was not a leaf, so need to then test if it was a leaf (added it to the assert instead). llvm-svn: 286817
* [Reassociate] Skip analysis of dead code to avoid infinite loop.Bjorn Pettersson2016-11-021-4/+13
| | | | | | | | | | | | | | | | | | | | | | | | Summary: It was detected that the reassociate pass could enter an inifite loop when analysing dead code. Simply skipping to analyse basic blocks that are dead avoids such problems (and as a side effect we avoid spending time on optimising dead code). The solution is using the same Reverse Post Order ordering of the basic blocks when doing the optimisations, as when building the precalculated rank map. A nice side-effect of this solution is that we now know that we only try to do optimisations for blocks with ranked instructions. Fixes https://llvm.org/bugs/show_bug.cgi?id=30818 Reviewers: llvm-commits, davide, eli.friedman, mehdi_amini Subscribers: dberlin Differential Revision: https://reviews.llvm.org/D26154 llvm-svn: 285793
* [Reassociate] Removing instructions mutates the IR.Davide Italiano2016-10-281-1/+3
| | | | | | | | | Fixes PR 30784. Discussed with Justin, who pointed out that in the new PassManager infrastructure we can have more fine-grained control on which analyses we want to preserve, but this is the best we can do with the current infrastructure. llvm-svn: 285380
* [Reassociate] Add additional debug output. NFC.Chad Rosier2016-08-301-0/+2
| | | | llvm-svn: 280090
* Revert "Reassociate: Reprocess RedoInsts after each inst".Chad Rosier2016-08-171-37/+27
| | | | | | | | This reverts commit r258830, which introduced a bug described in PR28367. PR28367 llvm-svn: 278938
* Revert "[Reassociate] Avoid iterator invalidation when negating value."Chad Rosier2016-08-171-9/+0
| | | | | | This reverts commit r278928 due to lit test failures. llvm-svn: 278929
* [Reassociate] Avoid iterator invalidation when negating value.Chad Rosier2016-08-171-0/+9
| | | | | | | Differential Revision: https://reviews.llvm.org/D23464 PR28367 llvm-svn: 278928
* [PM] Normalize FIXMEs for missing PreserveCFG to have the same wording.Michael Kuperstein2016-06-281-2/+1
| | | | llvm-svn: 273974
* Apply clang-tidy's modernize-loop-convert to most of lib/Transforms.Benjamin Kramer2016-06-261-6/+4
| | | | | | Only minor manual fixes. No functionality change intended. llvm-svn: 273808
* [PM] Remove support for omitting the AnalysisManager argument to newChandler Carruth2016-06-171-2/+3
| | | | | | | | | | | | | | | | | | | | pass manager passes' `run` methods. This removes a bunch of SFINAE goop from the pass manager and just requires pass authors to accept `AnalysisManager<IRUnitT> &` as a dead argument. This is a small price to pay for the simplicity of the system as a whole, despite the noise that changing it causes at this stage. This will also helpfull allow us to make the signature of the run methods much more flexible for different kinds af passes to support things like intelligently updating the pass's progression over IR units. While this touches many, many, files, the changes are really boring. Mostly made with the help of my trusty perl one liners. Thanks to Sean and Hal for bouncing ideas for this with me in IRC. llvm-svn: 272978
* Avoid copies of std::strings and APInt/APFloats where we only read from itBenjamin Kramer2016-06-081-1/+1
| | | | | | | | As suggested by clang-tidy's performance-unnecessary-copy-initialization. This can easily hit lifetime issues, so I audited every change and ran the tests under asan, which came back clean. llvm-svn: 272126
* [PM] Reassociate: cache analyses more aggressively.Davide Italiano2016-05-291-2/+7
| | | | | | While here, add a FIXME for setPreserveCFG(). llvm-svn: 271159
* PM: Port Reassociate to the new pass managerJustin Bogner2016-04-261-139/+101
| | | | llvm-svn: 267631
* Reassociate: Convert another functor into a lambda. NFCJustin Bogner2016-04-261-15/+13
| | | | | | Also move the explanatory comment with it. llvm-svn: 267628
* Reassociate: Simplify using lambdas. NFCJustin Bogner2016-04-261-17/+7
| | | | llvm-svn: 267614
* Re-commit optimization bisect support (r267022) without new pass manager ↵Andrew Kaylor2016-04-221-1/+1
| | | | | | | | | | support. The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the OptBisect handling). Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267231
* Revert "Initial implementation of optimization bisect support."Vedant Kumar2016-04-221-1/+1
| | | | | | | | This reverts commit r267022, due to an ASan failure: http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549 llvm-svn: 267115
* Initial implementation of optimization bisect support.Andrew Kaylor2016-04-211-1/+1
| | | | | | | | | | | | This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to track down test failures that are caused by incorrect optimizations. The bisection is enabled using a new command line option (-opt-bisect-limit). Individual passes that may be skipped call the OptBisect object (via an LLVMContext) to see if they should be skipped based on the bisect limit. A finer level of control (disabling individual transformations) can be managed through an addition OptBisect method, but this is not yet used. The skip checking in this implementation is based on (and replaces) the skipOptnoneFunction check. Where that check was being called, a new call has been inserted in its place which checks the bisect limit and the optnone attribute. A new function call has been added for module and SCC passes that behaves in a similar way. Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267022
* ADT: Remove == and != comparisons between ilist iterators and pointersDuncan P. N. Exon Smith2016-02-211-1/+1
| | | | | | | | | | | | | | I missed == and != when I removed implicit conversions between iterators and pointers in r252380 since they were defined outside ilist_iterator. Since they depend on getNodePtrUnchecked(), they indirectly rely on UB. This commit removes all uses of these operators. (I'll delete the operators themselves in a separate commit so that it can be easily reverted if necessary.) There should be NFC here. llvm-svn: 261498
* Reassociate: Reprocess RedoInsts after each instAditya Nandakumar2016-01-261-28/+39
| | | | | | | | | | Previously the RedoInsts was processed at the end of the block. However it was possible that it left behind some instructions that were not canonicalized. This should guarantee that any previous instruction in the basic block is canonicalized before we process a new instruction. llvm-svn: 258830
* Instructions to be redone only if from the same BBAditya Nandakumar2016-01-071-1/+2
| | | | | | | While adding instructions(possible roots) to be redone, make sure they are from the same basic block. llvm-svn: 257112
* Remove dead instructions before RedoingAditya Nandakumar2016-01-041-1/+33
| | | | | | | | | Before reevaluating instructions, iterate over all instructions to be reevaluated and remove trivially dead instructions and if any of it's operands become trivially dead, mark it for deletion until all trivially dead instructions have been removed llvm-svn: 256773
* Fix funciton->function typo.Eric Christopher2015-12-161-1/+1
| | | | llvm-svn: 255841
OpenPOWER on IntegriCloud