summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/GVNHoist.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Revert "GVN-hoist: fix store past load dependence analysis (PR30216, PR30499)"Reid Kleckner2016-10-131-48/+41
| | | | | | | | | | | This CL didn't actually address the test case in PR30499, and clang still crashes. Also revert dependent change "Memory-SSA cleanup of clobbers interface, NFC" Reverts r283965 and r283967. llvm-svn: 284093
* Memory-SSA cleanup of clobbers interface, NFCSebastian Pop2016-10-121-15/+16
| | | | | | | | | This implements the cleanup that Danny asked to commit separately from the previous fix to GVN-hoist in https://reviews.llvm.org/D25476#inline-219818 Tested with ninja check on x86_64-linux. llvm-svn: 283967
* GVN-hoist: fix store past load dependence analysis (PR30216, PR30499)Sebastian Pop2016-10-121-28/+34
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a refreshed version of a patch that was reverted: it fixes the problems reported in both PR30216 and PR30499, and contains all the test-cases from both bugs. To hoist stores past loads, we used to search for potential conflicting loads on the hoisting path by following a MemorySSA def-def link from the store to be hoisted to the previous defining memory access, and from there we followed the def-use chains to all the uses that occur on the hoisting path. The problem is that the def-def link may point to a store that does not alias with the store to be hoisted, and so the loads that are walked may not alias with the store to be hoisted, and even as in the testcase of PR30216, the loads that may alias with the store to be hoisted are not visited. The current patch visits all loads on the path from the store to be hoisted to the hoisting position and uses the alias analysis to ask whether the store may alias the load. I was not able to use the MemorySSA functionality to ask for whether load and store are clobbered: I'm not sure which function to call, so I used a call to AA->isNoAlias(). Store past store is still working as before using a MemorySSA query: I added an extra test to pr30216.ll to make sure store past store does not regress. Tested on x86_64-linux with check and a test-suite run. Differential Revision: https://reviews.llvm.org/D25476 llvm-svn: 283965
* Revert r282168 "GVN-hoist: fix store past load dependence analysis (PR30216)"Hans Wennborg2016-09-221-35/+28
| | | | | | | | and also the dependent r282175 "GVN-hoist: do not dereference null pointers" It's causing compiler crashes building Harfbuzz (PR30499). llvm-svn: 282199
* GVN-hoist: do not dereference null pointersSebastian Pop2016-09-221-0/+3
| | | | | | | there may be basic blocks without memory accesses, in which case the list of accesses is a null pointer. llvm-svn: 282175
* GVN-hoist: fix store past load dependence analysis (PR30216)Sebastian Pop2016-09-221-29/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | | | To hoist stores past loads, we used to search for potential conflicting loads on the hoisting path by following a MemorySSA def-def link from the store to be hoisted to the previous defining memory access, and from there we followed the def-use chains to all the uses that occur on the hoisting path. The problem is that the def-def link may point to a store that does not alias with the store to be hoisted, and so the loads that are walked may not alias with the store to be hoisted, and even as in the testcase of PR30216, the loads that may alias with the store to be hoisted are not visited. The current patch visits all loads on the path from the store to be hoisted to the hoisting position and uses the alias analysis to ask whether the store may alias the load. I was not able to use the MemorySSA functionality to ask for whether load and store are clobbered: I'm not sure which function to call, so I used a call to AA->isNoAlias(). Store past store is still working as before using a MemorySSA query: I added an extra test to pr30216.ll to make sure store past store does not regress. Differential Revision: https://reviews.llvm.org/D24517 llvm-svn: 282168
* GVN-hoist: fix typoSebastian Pop2016-09-221-1/+1
| | | | llvm-svn: 282165
* GVN-hoist: only hoist relevant scalar instructionsSebastian Pop2016-09-221-0/+4
| | | | | | | | | | | | | | | | | | | Without this patch, GVN-hoist would think that a branch instruction is a scalar instruction and would try to value number it. The patch filters out all such kind of irrelevant instructions. A bit frustrating is that there is no easy way to discard all those very infrequent instructions, a bit like isa<TerminatorInst> that stands for a large family of instructions. I'm thinking that checking for those very infrequent other instructions would cost us more in compilation time than just letting those instructions getting numbered, so I'm still thinking that a simpler check: if (isa<TerminatorInst>(I)) return false; is better than listing all the other less frequent instructions. Differential Revision: https://reviews.llvm.org/D23929 llvm-svn: 282160
* IR: Remove Value::intersectOptionalDataWith, replace all calls with calls to ↵Peter Collingbourne2016-09-071-2/+2
| | | | | | | | | | Instruction::andIRFlags. The two functions are functionally equivalent. Differential Revision: https://reviews.llvm.org/D22830 llvm-svn: 280884
* GVN-hoist: invalidate MD cache (PR29144)Sebastian Pop2016-08-271-0/+2
| | | | | | | | | Without invalidating the entries in the MD cache we would try to access instructions that were removed in previous iterations of hoisting. Differential Revision: https://reviews.llvm.org/D23927 llvm-svn: 279907
* GVN-hoist: fix hoistingFromAllPaths for loops (PR29034)Sebastian Pop2016-08-251-31/+46
| | | | | | | | | | | | | | | | It is invalid to hoist stores or loads if they are not executed on all paths from the hoisting point to the exit of the function. In the testcase, there are paths in the loop that do not execute the stores or the loads, and so hoisting them within the loop is unsafe. The problem is that the current implementation of hoistingFromAllPaths is incomplete: it walks all blocks dominated by the hoisting point, and does not return false when the loop contains a path on which the hoisted ld/st is not executed. Differential Revision: https://reviews.llvm.org/D23843 llvm-svn: 279732
* GVNHoist: Use the pass version of MemorySSA and preserve it.Daniel Berlin2016-08-231-9/+12
| | | | | | | | | | | | Summary: GVNHoist: Use the pass version of MemorySSA and preserve it. Reviewers: sebpop, george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23782 llvm-svn: 279504
* Test commitAditya Kumar2016-08-131-2/+4
| | | | llvm-svn: 278598
* Use range algorithms instead of unpacking begin/endDavid Majnemer2016-08-111-2/+1
| | | | | | No functionality change is intended. llvm-svn: 278417
* Fix PR 28933Daniel Berlin2016-08-111-5/+11
| | | | | | | | | | | | | | Summary: This fixes PR 28933 by making sure GVNHoist does not try to recreate memory accesses when it has not actually moved them. Reviewers: sebpop Subscribers: llvm-commits, george.burgess.iv Differential Revision: https://reviews.llvm.org/D23411 llvm-svn: 278401
* Consistently use FunctionAnalysisManagerSean Silva2016-08-091-1/+1
| | | | | | | | | | | Besides a general consistently benefit, the extra layer of indirection allows the mechanical part of https://reviews.llvm.org/D23256 that requires touching every transformation and analysis to be factored out cleanly. Thanks to David for the suggestion. llvm-svn: 278077
* GVN-hoist: fix early exit logicSebastian Pop2016-08-041-4/+11
| | | | | | | | | | The patch splits a complex && if condition into easier to read and understand logic. That wrong early exit condition was letting some instructions with not all operands available pass through when HoistingGeps was true. Differential Revision: https://reviews.llvm.org/D23174 llvm-svn: 277785
* GVNHoist: Don't hoist convergent callsMatt Arsenault2016-08-041-0/+4
| | | | llvm-svn: 277767
* GVN-hoist: limit the length of dependent instructionsSebastian Pop2016-08-031-0/+10
| | | | | | | | | | Limit the number of times the while(1) loop is executed. With this restriction the number of hoisted instructions does not change in a significant way on the test-suite. Differential Revision: https://reviews.llvm.org/D23028 llvm-svn: 277651
* GVN-hoist: compute DFS numbers onceSebastian Pop2016-08-031-12/+22
| | | | | | | | | With this patch we compute the DFS numbers of instructions only once and update them during the code generation when an instruction gets hoisted. Differential Revision: https://reviews.llvm.org/D23021 llvm-svn: 277650
* GVN-hoist: compute MSSA once per function (PR28670)Sebastian Pop2016-08-031-12/+49
| | | | | | | | With this patch we compute the MemorySSA once and update it in the code generator. Differential Revision: https://reviews.llvm.org/D22966 llvm-svn: 277649
* [GVNHoist] Fix typo in assert.George Burgess IV2016-07-271-1/+1
| | | | | | This fixes PR28730. llvm-svn: 276844
* GVN-hoist: improve code generation for recursive GEPsSebastian Pop2016-07-271-42/+82
| | | | | | | | | | | | | | | | | | | When loading or storing in a field of a struct like "a.b.c", GVN is able to detect the equivalent expressions, and GVN-hoist would fail in the code generation. This is because the GEPs are not hoisted as scalar operations to avoid moving the GEPs too far from their ld/st instruction when the ld/st is not movable. So we end up having to generate code for the GEP of a ld/st when we move the ld/st. In the case of a GEP referring to another GEP as in "a.b.c" we need to code generate all the GEPs necessary to make all the operands available at the new location for the ld/st. With this patch we recursively walk through the GEP operands checking whether all operands are available, and in the case of a GEP operand, it recursively makes all its operands available. Code generation happens from the inner GEPs out until reaching the GEP that appears as an operand of the ld/st. Differential Revision: https://reviews.llvm.org/D22599 llvm-svn: 276841
* GVN-hoist: use DFS numbers instead of walking the instruction streamSebastian Pop2016-07-271-10/+3
| | | | | | | | | The patch replaces a function that walks the IR with a call to firstInBB() that uses the DFS numbering. NFC. Differential Revision: https://reviews.llvm.org/D22809 llvm-svn: 276840
* GVN-hoist: use a DFS numbering of instructions (PR28670)Sebastian Pop2016-07-261-31/+26
| | | | | | | | | | | Instead of DFS numbering basic blocks we now DFS number instructions that avoids the costly operation of which instruction comes first in a basic block. Patch mostly written by Daniel Berlin. Differential Revision: https://reviews.llvm.org/D22777 llvm-svn: 276714
* GVN-hoist: limit hoisting depth (PR28670)Sebastian Pop2016-07-261-0/+11
| | | | | | | | | | This patch adds an option to specify the maximum depth in a BB at which to consider hoisting instructions. Hoisting instructions from a deeper level is not profitable as it increases register pressure and compilation time. Differential Revision: https://reviews.llvm.org/D22772 llvm-svn: 276713
* Revert NewGVN N^2 behavior patchDaniel Berlin2016-07-251-22/+19
| | | | llvm-svn: 276670
* NFC: Make a few asserts in GVNHoist do the same thing, but cheaper.Daniel Berlin2016-07-251-4/+8
| | | | llvm-svn: 276662
* Fix N^2 instruction ordering comparisons in GVNHoist.Daniel Berlin2016-07-251-19/+18
| | | | | | This fixes GVNHoist's portion of PR28670. llvm-svn: 276658
* NFC: Refactor GVNHoist class so not everything is publicDaniel Berlin2016-07-251-37/+36
| | | | llvm-svn: 276657
* [GVNHoist] Merge metadata on hoisted instructions less conservativelyDavid Majnemer2016-07-251-7/+17
| | | | | | | We can combine metadata from multiple instructions intelligently for certain metadata nodes. llvm-svn: 276602
* [GVNHoist] Properly merge alignments when hoistingDavid Majnemer2016-07-251-4/+14
| | | | | | | | | If we two loads of two different alignments, we must use the minimum of the two alignments when hoisting. Same deal for stores. For allocas, use the maximum of the two allocas. llvm-svn: 276601
* GVN-hoist: move check before mutating the IRSebastian Pop2016-07-221-6/+8
| | | | llvm-svn: 276368
* GVN-hoist: add missing check for all GEP operands availableSebastian Pop2016-07-211-0/+3
| | | | llvm-svn: 276364
* GVH-hoist: only clone GEPs (PR28606)Sebastian Pop2016-07-211-14/+7
| | | | | | | | | Do not clone stored values unless they are GEPs that are special cased to avoid hoisting them without hoisting their associated ld/st. Differential revision: https://reviews.llvm.org/D22652 llvm-svn: 276358
* [GVNHoist] Preserve optimization hints which agreeDavid Majnemer2016-07-211-3/+17
| | | | | | | If we have optimization hints with agree with each other along different paths, preserve them. llvm-svn: 276248
* [GVNHoist] Don't wrongly preserve TBAADavid Majnemer2016-07-211-0/+12
| | | | | | | We hoisted loads/stores without taking into account which can cause miscompiles. llvm-svn: 276240
* [GVNHoist] Don't hoist PHI nodesDavid Majnemer2016-07-201-4/+8
| | | | | | | | | We hoisted PHIs without respecting their special insertion point in the block, leading to verfier errors. This fixes PR28626. llvm-svn: 276181
* Make GVN Hoisting obey optnone/bisect.Paul Robinson2016-07-191-0/+2
| | | | | | Differential Revision: http://reviews.llvm.org/D22545 llvm-svn: 276048
* [GVNHoist] Remove a home-grown version of replaceUsesOfWithDavid Majnemer2016-07-181-15/+2
| | | | | | | | | replaceUsesOfWith will, on average, consider fewer values when trying to do the replacement. No functional change is intended. llvm-svn: 275884
* Fix -Wmicrosoft-enum-value in GVNHoist.cppReid Kleckner2016-07-181-1/+1
| | | | llvm-svn: 275879
* [GVNHoist] Change the key for VNtoInsns to a pairDavid Majnemer2016-07-181-9/+13
| | | | | | | | | | | | | | | | | | | | | While debugging GVNHoist, I found it confusing that the entries in a VNtoInsns were not always value numbers. They _usually_ were except for StoreInst in which case they were a hash of two different value numbers. This leads to two observations: - It is more difficult to debug things when the semantic contents of VNtoInsns changes over time. - Using a single value number is not much cheaper, the value of VNtoInsns is a SmallVector. - It is not immediately clear what the algorithm would do if there were hash collisions in the StoreInst case. Using a DenseMap of std::pair sidesteps all of this. N.B. The changes in the test were due their sensitivity to the iteration order of VNtoInsns which has changed. llvm-svn: 275761
* [GVNHoist] Sink HoistedCtr into GVNHoistDavid Majnemer2016-07-181-3/+3
| | | | | | | HoistedCtr cannot be a mutated global variable, that will open us up to races between threads compiling code in parallel. llvm-svn: 275744
* [GVNHoist] Some small cleanupsDavid Majnemer2016-07-181-26/+22
| | | | | | | No functional change is intended, just trying to clean things up a little. llvm-svn: 275743
* code hoisting pass based on GVNSebastian Pop2016-07-151-0/+823
| | | | | | | | | | | | | This pass hoists duplicated computations in the program. The primary goal of gvn-hoist is to reduce the size of functions before inline heuristics to reduce the total cost of function inlining. Pass written by Sebastian Pop, Aditya Kumar, Xiaoyu Hu, and Brian Rzycki. Important algorithmic contributions by Daniel Berlin under the form of reviews. Differential Revision: http://reviews.llvm.org/D19338 llvm-svn: 275561
* Revert r275401, it caused PR28551.Nico Weber2016-07-141-820/+0
| | | | llvm-svn: 275420
* code hoisting pass based on GVNSebastian Pop2016-07-141-0/+820
| | | | | | | | | | | | | This pass hoists duplicated computations in the program. The primary goal of gvn-hoist is to reduce the size of functions before inline heuristics to reduce the total cost of function inlining. Pass written by Sebastian Pop, Aditya Kumar, Xiaoyu Hu, and Brian Rzycki. Important algorithmic contributions by Daniel Berlin under the form of reviews. Differential Revision: http://reviews.llvm.org/D19338 llvm-svn: 275401
* Revert "code hoisting pass based on GVN"Duncan P. N. Exon Smith2016-07-011-740/+0
| | | | | | | | | | | | This reverts commit r274305, since it breaks self-hosting: http://lab.llvm.org:8080/green/job/clang-stage1-configure-RA_build/22349/ http://lab.llvm.org:8011/builders/clang-x86_64-linux-selfhost-modules/builds/17232 Note that the blamelist on lab.llvm.org:8011 is incorrect. The previous build was r274299, but somehow r274305 wasn't included in the blamelist: http://lab.llvm.org:8011/builders/clang-x86_64-linux-selfhost-modules llvm-svn: 274320
* code hoisting pass based on GVNSebastian Pop2016-07-011-0/+740
This pass hoists duplicated computations in the program. The primary goal of gvn-hoist is to reduce the size of functions before inline heuristics to reduce the total cost of function inlining. Pass written by Sebastian Pop, Aditya Kumar, Xiaoyu Hu, and Brian Rzycki. Important algorithmic contributions by Daniel Berlin under the form of reviews. Differential Revision: http://reviews.llvm.org/D19338 llvm-svn: 274305
OpenPOWER on IntegriCloud