summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LICM.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [LICM] *Actually* disable ControlFlowHoisting.Alina Sbirlea2018-12-051-14/+19
| | | | | | | | | | | | | | | Summary: The remaining code paths that ControlFlowHoisting introduced that were not disabled, increased compile time by 3x for some benchmarks. The time is spent in DominatorTree updates. Reviewers: john.brawn, mkazantsev Subscribers: sanjoy, jlebar, llvm-commits Differential Revision: https://reviews.llvm.org/D55313 llvm-svn: 348345
* [LICM] Reapply r347776 "Make LICM able to hoist phis" with fixJohn Brawn2018-11-291-15/+314
| | | | | | | | | | This commit caused a large compile-time slowdown in some cases when NDEBUG is off due to the dominator tree verification it added. Fix this by only doing dominator tree and loop info verification when something has been hoisted. Differential Revision: https://reviews.llvm.org/D52827 llvm-svn: 347889
* Revert "[LICM] Enable control flow hoisting by default" and "[LICM] Reapply ↵Martin Storsjo2018-11-291-312/+15
| | | | | | | | | | | r347190 "Make LICM able to hoist phis" with fix" This reverts commits r347776 and r347778. The first one, r347776, caused significant compile time regressions for certain input files, see PR39836 for details. llvm-svn: 347867
* [LICM] Enable control flow hoisting by defaultJohn Brawn2018-11-281-1/+1
| | | | | | Differential Revision: https://reviews.llvm.org/D54949 llvm-svn: 347778
* [LICM] Reapply r347190 "Make LICM able to hoist phis" with fixJohn Brawn2018-11-281-15/+312
| | | | | | | | | | | | | | | This commit caused failures because it failed to correctly handle cases where we hoist a phi, then hoist a use of that phi, then have to rehoist that use. We need to make sure that we rehoist the use to _after_ the hoisted phi, which we do by always rehoisting to the immediate dominator instead of just rehoisting everything to the original preheader. An option is also added to control whether control flow is hoisted, which is off in this commit but will be turned on in a subsequent commit. Differential Revision: https://reviews.llvm.org/D52827 llvm-svn: 347776
* Revert "[LICM] Make LICM able to hoist phis"Benjamin Kramer2018-11-191-302/+15
| | | | | | This reverts commit r347190. llvm-svn: 347225
* [LICM] Make LICM able to hoist phisJohn Brawn2018-11-191-15/+302
| | | | | | | | | | | | | | | The general approach taken is to make note of loop invariant branches, then when we see something conditional on that branch, such as a phi, we create a copy of the branch and (empty versions of) its successors and hoist using that. This has no impact by itself that I've been able to see, as LICM typically doesn't see such phis as they will have been converted into selects by the time LICM is run, but once we start doing phi-to-select conversion later it will be important. Differential Revision: https://reviews.llvm.org/D52827 llvm-svn: 347190
* [LICM] Hoist guards from non-header blocksMax Kazantsev2018-11-121-11/+3
| | | | | | | | | | | This patch relaxes overconservative checks on whether or not we could write memory before we execute an instruction. This allows us to hoist guards out of loops even if they are not in the header block. Differential Revision: https://reviews.llvm.org/D50891 Reviewed By: fedor.sergeev llvm-svn: 346643
* [NFC] Add utility function for SafetyInfo updates for moveBeforeMax Kazantsev2018-11-091-3/+11
| | | | llvm-svn: 346472
* [LICM] Remove too conservative IsMustExecute variableMax Kazantsev2018-11-061-15/+8
| | | | | | | | | | | | | | | | | | LICM relies on variable `MustExecute` which is conservatively set to `false` in all non-headers. It is used when we decide whether or not we want to hoist an instruction or a guard. For the guards, it might be too conservative to use this variable, we can instead use a more precise logic from LoopSafetyInfo. Currently it is only NFC because `IsMemoryNotModified` is also conservatively set to `false` for all non-headers, and we cannot hoist guards from non-header blocks. However once we give up using `IsMemoryNotModified` and use a smarter check instead, this will allow us to hoist guards from all mustexecute non-header blocks. Differential Revision: https://reviews.llvm.org/D50888 Reveiwed By: fedor.sergeev llvm-svn: 346204
* [LICM] Use ICFLoopSafetyInfo in LICMMax Kazantsev2018-11-061-20/+33
| | | | | | | | | | | | | | | This patch makes LICM use `ICFLoopSafetyInfo` that is a smarter version of LoopSafetyInfo that leverages power of Implicit Control Flow Tracking to keep track of throwing instructions and give less pessimistic answers to queries related to throws. The ICFLoopSafetyInfo itself has been introduced in rL344601. This patch enables it in LICM only. Differential Revision: https://reviews.llvm.org/D50377 Reviewed By: apilipenko llvm-svn: 346201
* [NFC][LICM] Factor out instruction erasing logicMax Kazantsev2018-11-021-11/+15
| | | | | | | | | | This patch factors out a function that makes all required updates whenever an instruction gets erased. Differential Revision: https://reviews.llvm.org/D54011 Reviewed By: apilipenko llvm-svn: 345914
* [NFC] Make LoopSafetyInfo abstract to allow alternative implementationsMax Kazantsev2018-10-161-1/+1
| | | | llvm-svn: 344592
* [NFC] Encapsulate work with BlockColors in LoopSafetyInfoMax Kazantsev2018-10-161-9/+6
| | | | llvm-svn: 344590
* [NFC] Turn isGuaranteedToExecute into a methodMax Kazantsev2018-10-161-3/+3
| | | | llvm-svn: 344587
* Replace most users of UnknownSize with LocationSize::unknown(); NFCGeorge Burgess IV2018-10-101-1/+1
| | | | | | | | | | | | Moving away from UnknownSize is part of the effort to migrate us to LocationSizes (e.g. the cleanup promised in D44748). This doesn't entirely remove all of the uses of UnknownSize; some uses require tweaks to assume that UnknownSize isn't just some kind of int. This patch is intended to just be a trivial replacement for all places where LocationSize::unknown() will Just Work. llvm-svn: 344186
* [LICM] Avoid duplicate work during building AliasSetTrackerSerguei Katkov2018-09-111-8/+6
| | | | | | | | | | | | | | | | | | Currently we re-use cached info from sub loops or traverse them to populate AliasSetTracker. But after that we traverse all basic blocks from the current loop. This is redundant work. All what we need is traversing the all basic blocks from the loop except those which are used to get the data from the cache. This should improve compile time only. Reviewers: mkazantsev, reames, kariddi, anna Reviewed By: reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D51715 llvm-svn: 341896
* [LICM] (re-)simplify code using MemoryLocation API [NFC]Philip Reames2018-09-111-10/+2
| | | | | | I'd made exactly this same change before, but it appears to have been accidentally reverted in another change. (I'm assuming accidental since it was without comment or test case, and in an unrelated change.) llvm-svn: 341892
* Re-enable "[NFC] Unify guards detection"Max Kazantsev2018-08-301-1/+2
| | | | | | | | | | rL340921 has been reverted by rL340923 due to linkage dependency from Transform/Utils to Analysis which is not allowed. In this patch this has been fixed, a new utility function moved to Analysis. Differential Revision: https://reviews.llvm.org/D51152 llvm-svn: 341014
* Add a todo and tests to Address a review commnt from D50925 [NFC]Philip Reames2018-08-291-1/+3
| | | | llvm-svn: 340978
* [LICM] Hoist stores of invariant values to invariant addresses out of loopsPhilip Reames2018-08-291-3/+23
| | | | | | | | | | | | Teach LICM to hoist stores out of loops when the store writes to a location otherwise unused in the loop, writes a value which is invariant, and is guaranteed to execute if the loop is entered. Worth noting is that this transformation is partially overlapping with the existing promotion transformation. Reasons this is worthwhile anyway include: * For multi-exit loops, this doesn't require duplication of the store. * It kicks in for case where we can't prove we exit through a normal exit (i.e. we may throw), but can prove the store executes before that possible side exit. Differential Revision: https://reviews.llvm.org/D50925 llvm-svn: 340974
* Revert r340921 "[NFC] Unify guards detection"Hans Wennborg2018-08-291-2/+1
| | | | | | | | | | | | | | | | | | This broke the build, see e.g. http://lab.llvm.org:8011/builders/clang-cmake-armv8-lnt/builds/4626/ http://lab.llvm.org:8011/builders/clang-ppc64be-linux-lnt/builds/18647/ http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/5856/ http://lab.llvm.org:8011/builders/lld-x86_64-freebsd/builds/22800/ > We have multiple places in code where we try to identify whether or not > some instruction is a guard. This patch factors out this logic into a separate > utility function which works uniformly in all places. > > Differential Revision: https://reviews.llvm.org/D51152 > Reviewed By: fedor.sergeev llvm-svn: 340923
* [NFC] Unify guards detectionMax Kazantsev2018-08-291-1/+2
| | | | | | | | | | | We have multiple places in code where we try to identify whether or not some instruction is a guard. This patch factors out this logic into a separate utility function which works uniformly in all places. Differential Revision: https://reviews.llvm.org/D51152 Reviewed By: fedor.sergeev llvm-svn: 340921
* [AST] Simplify code minorly using pattern match [NFC]Philip Reames2018-08-241-8/+4
| | | | llvm-svn: 340638
* [LICM] Hoist an invariant_start out of loops if there are no stores executed ↵Philip Reames2018-08-241-1/+3
| | | | | | | | | | before it Once the invariant_start is reached, we know that no instruction *after* it can modify the memory. So, if we can prove the location isn't read *between entry into the loop and the execution of the invariant_start*, we can execute the invariant_start before entering the loop. Differential Revision: https://reviews.llvm.org/D51181 llvm-svn: 340617
* Update MemorySSA in BasicBlockUtils.Alina Sbirlea2018-08-211-1/+1
| | | | | | | | | | | Summary: Extend BasicBlocksUtils to update MemorySSA. Subscribers: sanjoy, arsenm, nhaehnle, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D45300 llvm-svn: 340365
* [LICM] Refactor some AliasSetTracker code to get rid of new/deletes. NFCMarcello Maggioni2018-08-211-43/+33
| | | | | | Differential Revision: https://reviews.llvm.org/D51024 llvm-svn: 340333
* [AST] Remove notion of volatile from alias sets [NFCI]Philip Reames2018-08-211-3/+1
| | | | | | | | | | Volatility is not an aliasing property. We used to model volatile as if it had extremely conservative aliasing implications, but that hasn't been true for several years now. So, it doesn't make sense to be in AliasSet. It also turns out the code is entirely a noop. Outside of the AST code to update it, there was only one user: load store promotion in LICM. L/S promotion doesn't need the check since it walks all the users of the address anyway. It already checks each load or store via !isUnordered which causes us to bail for volatile accesses. (Look at the lines immediately following the two remove asserts.) There is the possibility of some small compile time impact here, but the only case which will get noticeably slower is a loop with a large number of loads and stores to the same address where only the last one we inspect is volatile. This is sufficiently rare it's not worth optimizing for.. llvm-svn: 340312
* [LICM] Hoist guards with invariant conditionsMax Kazantsev2018-08-211-0/+17
| | | | | | | | | | This patch teaches LICM to hoist guards from the loop if they are guaranteed to execute and if there are no side effects that could prevent that. Differential Revision: https://reviews.llvm.org/D50501 Reviewed By: reames llvm-svn: 340256
* [LICM] Add a diagnostic analysis for identifying alias informationAnna Thomas2018-08-171-14/+69
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Currently, in LICM, we use the alias set tracker to identify if the instruction (we're interested in hoisting) aliases with instruction that modifies that memory location. This patch adds an LICM alias analysis diagnostic tool that checks the mod ref info of the instruction we are interested in hoisting/sinking, with every instruction in the loop. Because of O(N^2) complexity this is now only a diagnostic tool to show the limitation we have with the alias set tracker and is OFF by default. Test cases show the difference with the diagnostic analysis tool, where we're able to hoist out loads and readonly + argmemonly calls from the loop, where the alias set tracker analysis is not able to hoist these instructions out. Reviewers: reames, mkazantsev, fedor.sergeev, hfinkel Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D50854 llvm-svn: 340026
* [LICM][NFC] Restructure pointer invalidation API in terms of MemoryLocationPhilip Reames2018-08-161-19/+10
| | | | | | | | Main value is just simplifying code. I'll further simply the argument handling case in a bit, but that involved a slightly orthogonal change so I went with the mildy ugly intermediate for this patch. Note that the isSized check in the old LICM code was not carried across. It turns out that check was dead. a) no test exercised it, and b) langref and verifier had been updated to disallow unsized types used in loads. llvm-svn: 339930
* [NFC] Remove const modifier to allow further development in LICMMax Kazantsev2018-08-161-3/+2
| | | | llvm-svn: 339846
* [NFC] Refactoring of LoopSafetyInfo, step 1Max Kazantsev2018-08-151-2/+2
| | | | | | | | | Turn structure into class, encapsulate methods, add clarifying comments. Differential Revision: https://reviews.llvm.org/D50693 Reviewed By: reames llvm-svn: 339752
* [NFC][LICM] Make hoist method voidMax Kazantsev2018-08-151-4/+4
| | | | | | | | | Method hoist always returns true. This patch makes it void. Differential Revision: https://reviews.llvm.org/D50696 Reviewed By: hiraditya llvm-svn: 339750
* [LICM] Hoist assumes out of loopsPhilip Reames2018-08-101-0/+9
| | | | | | | | If we have an assume which is known to execute and whose operand is invariant, we can lift that into the pre-header. So long as we don't change which paths the assume executes on, this is a legal transformation. It's likely to be a useful canonicalization as other transforms only look for dominating assumes. Differential Revision: https://reviews.llvm.org/D50364 llvm-svn: 339481
* [LICM] Suppress a compiler warning noticed by one of the botsPhilip Reames2018-08-091-0/+1
| | | | llvm-svn: 339388
* [LICM] hoist fences out of loops w/o memory operationsPhilip Reames2018-08-091-0/+15
| | | | | | | | | | The motivating case is an otherwise dead loop with a fence in it. At the moment, this goes all the way through the optimizer and we end up emitting an entirely pointless loop on x86. This case may seem a bit contrived, but we've seen it in real code as the result of otherwise reasonable lowering strategies combined w/thread local memory optimizations (such as escape analysis). To handle this simple case, we can teach LICM to hoist must execute fences when there is no other memory operation within the loop. Differential Revision: https://reviews.llvm.org/D50489 llvm-svn: 339378
* [LICM] Add an assert to ensure all instruction types needing aliasing are ↵Philip Reames2018-08-091-0/+2
| | | | | | handled [NFC] llvm-svn: 339308
* [LICM] Extract a helper function for readability [NFC]Philip Reames2018-08-061-8/+12
| | | | llvm-svn: 339069
* [LICM] Remove unneccessary safety check to increase sinking effectivenessPhilip Reames2018-08-031-8/+1
| | | | | | | | | | | | This one requires a bit of explaination. It's not every day you simply delete code to implement an optimization. :) The transform in question is sinking an instruction from a loop to the uses in loop exiting blocks. We know (from LCSSA) that all of the uses outside the loop must be phi nodes, and after predecessor splitting, we know all phi users must have a single operand. Since the use must be strictly dominated by the def, we know from the definition of dominance/ssa that the exit block must execute along a (non-strict) subset of paths which reach the def. As a result, duplicating a potentially faulting instruction can not *introduce* a fault that didn't previously exist in the program. The full story is that this patch builds on "rL338671: [LICM] Factor out fault legality from canHoistOrSinkInst [NFC]" which pulled this logic out of a common helper routine. As best I can tell, this check was originally added to the helper function for hoisting legality, later an incorrect fastpath for loads/calls was added, and then the bug was fixed by duplicating the fault safety check in the hoist path. This left the redundant check in the common code to pessimize sinking for no reason. I split it out in an NFC, and am not removing the unneccessary check. I wanted there to be something easy to revert in case I missed something. Reviewed by: Anna Thomas (in person) llvm-svn: 338794
* [LICM] Factor out fault legality from canHoistOrSinkInst [NFC]Philip Reames2018-08-021-17/+15
| | | | | | | | | This method has three callers, each of which wanted distinct handling: 1) Sinking into a loop is moving an instruction known to execute before a loop into the loop. We don't need to worry about introducing a fault at all in this case. 2) Hoisting from a loop into a preheader already duplicated the check in the caller. 3) Sinking from the loop into an exit block was the only true user of the code within the routine. For the moment, this has just been lifted into the caller, but up next is examining the logic more carefully. Whitelisting of loads and calls - while consistent with the previous code - is rather suspicious. Either way, a behavior change is worthy of it's own patch. llvm-svn: 338671
* [LICM] hoisting/sinking legality - bail early for unsupported instructionsPhilip Reames2018-08-021-8/+19
| | | | | | Originally, this was part of a larger refactoring I'd planned, but had to abandoned. I figured the minor improvement in readability was worthwhile. llvm-svn: 338663
* Remove trailing spaceFangrui Song2018-07-301-4/+4
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* Replace "Replacable" with "Replaceable". [NFC]Alina Sbirlea2018-07-021-13/+13
| | | | llvm-svn: 336133
* Fix invariant fdiv hoisting in LICMStanislav Mekhanoshin2018-06-231-14/+14
| | | | | | | | | | | | | FDiv is replaced with multiplication by reciprocal and invariant reciprocal is hoisted out of the loop, while multiplication remains even if invariant. Switch checks for all invariant operands and only invariant denominator to fix the issue. Differential Revision: https://reviews.llvm.org/D48447 llvm-svn: 335411
* Move Analysis/Utils/Local.h back to TransformsDavid Blaikie2018-06-041-1/+1
| | | | | | | | | | Review feedback from r328165. Split out just the one function from the file that's used by Analysis. (As chandlerc pointed out, the original change only moved the header and not the implementation anyway - which was fine for the one function that was used (since it's a template/inlined in the header) but not in general) llvm-svn: 333954
* [LICM] Preserve DT and LoopInfo specificallyJun Bum Lim2018-05-241-2/+6
| | | | | | | | | | | | | | | | | | | Summary: In LICM, CFG could be changed in splitPredecessorsOfLoopExit(), which update only DT and LoopInfo. Therefore, we should preserve only DT and LoopInfo specifically, instead of all analyses that depend on the CFG (setPreservesCFG()). This change should fix PR37323. Reviewers: uabelho, davide, dberlin, Ka-Ka Reviewed By: dberlin Subscribers: mzolotukhin, bjope, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D46775 llvm-svn: 333198
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-7/+8
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* [LICM] Compute a must execute property for the prefix of the header as we goPhilip Reames2018-05-041-3/+14
| | | | | | | | Computing this property within the existing walk ensures that the cost is linear with the size of the block. If we did this from within isGuaranteedToExecute, it would be quadratic without some very fancy caching. This allows us to reliably catch a hoistable instruction within a header which may throw at some point *after* our hoistable instruction. It doesn't do anything for non-header cases, but given how common single block loops are, this seems very worthwhile. llvm-svn: 331557
* [LICM] Reduce nesting with an early return [NFC]Philip Reames2018-04-271-48/+50
| | | | llvm-svn: 331080
OpenPOWER on IntegriCloud