summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/GVNHoist.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* [GVNHoist] Mark GlobalsAA as preserved by GVNHoist.Nikolai Bozhenov2017-04-181-0/+3
| | | | | | | | | | | | | Reviewers: sebpop, hiraditya Reviewed By: sebpop Subscribers: n.bozhenov, llvm-commits Differential Revision: https://reviews.llvm.org/D32158 Patch by Andrei Elovikov <andrei.elovikov@intel.com> llvm-svn: 300552
* MemorySSA: Move to Analysis, from Transforms/Utils. It's used asDaniel Berlin2017-04-111-2/+2
| | | | | | | | Analysis, it has Analysis passes, and once NewGVN is made an Analysis, this removes the cross dependency from Analysis to Transform/Utils. NFC. llvm-svn: 299980
* [GVNHoist] Call isGuaranteedToTransferExecutionToSuccessor on each instructionGeoff Berry2017-04-101-17/+55
| | | | | | | | | | | w.r.t. https://bugs.llvm.org/show_bug.cgi?id=32153 The consensus seems to be isGuaranteedToTransferExecutionToSuccessor should be called for each function. Patch by Aditya Kumar Differential Revision: https://reviews.llvm.org/D31035 llvm-svn: 299882
* Move defClobbersUseOrDef to being a protected member of a class since we ↵Daniel Berlin2017-03-021-2/+2
| | | | | | don't want anyone else using it llvm-svn: 296838
* [GVNHoist] Don't hoist unsafe scalars at -Oz (PR31729)Hans Wennborg2017-03-011-22/+8
| | | | | | | | Based on Aditya Kumar's patch: Differential Revision: https://reviews.llvm.org/D29092 llvm-svn: 296642
* Move updating functions to MemorySSAUpdater.Daniel Berlin2017-02-221-9/+13
| | | | | | | | | | | | | | | Add updater to passes that now need it. Move around code in MemorySSA to expose needed functions. Summary: Mostly cleanup Reviewers: george.burgess.iv Subscribers: llvm-commits, Prazek Differential Revision: https://reviews.llvm.org/D30221 llvm-svn: 295887
* Revert "[GVNHoist] Merge DebugLoc metadata on hoisted instructions"Reid Kleckner2017-02-071-7/+0
| | | | | | | | | This reverts commit r294250. It caused PR31891. Add a test case that shows that inlinable calls retain location information with an accurate scope. llvm-svn: 294317
* [GVNHoist] Merge DebugLoc metadata on hoisted instructionsTaewook Oh2017-02-061-0/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: When instructions are hoisted, current implementation keeps DebugLoc metadata of the instruction that chosen as Repl (and its GEP operand if Repl is a load or a store). However, DebugLoc metadata should be updated to the 'merged' location across all hoisted instructions. See the following example code: ``` 1: typedef struct { 2: int a[10]; 3: } S1; 4: 5: extern S1 *s1[10]; 6: 7: void foo(int x, int y, int i) { 8: if (y) 9: s1[i]->a[i] = x + y; 10: else 11: s1[i]->a[i] = x; 12: } ``` Below is LLVM IR representation of the program before gvn-hoist: ``` %struct.S1 = type { [10 x i32] } @s1 = external local_unnamed_addr global [10 x %struct.S1*], align 16 define void @foo(i32 %x, i32 %y, i32 %i) !dbg !4 { entry: %tobool = icmp ne i32 %y, 0, !dbg !8 br i1 %tobool, label %if.then, label %if.else, !dbg !10 if.then: ; preds = %entry %add = add nsw i32 %x, %y, !dbg !11 %idxprom = sext i32 %i to i64, !dbg !12 %arrayidx = getelementptr inbounds [10 x %struct.S1*], [10 x %struct.S1*]* @s1, i64 0, i64 %idxprom, !dbg !12 %0 = load %struct.S1*, %struct.S1** %arrayidx, align 8, !dbg !12, !tbaa !13 %a = getelementptr inbounds %struct.S1, %struct.S1* %0, i32 0, i32 0, !dbg !17 br label %if.end, !dbg !12 if.else: ; preds = %entry %idxprom3 = sext i32 %i to i64, !dbg !18 %arrayidx4 = getelementptr inbounds [10 x %struct.S1*], [10 x %struct.S1*]* @s1, i64 0, i64 %idxprom3, !dbg !18 %1 = load %struct.S1*, %struct.S1** %arrayidx4, align 8, !dbg !18, !tbaa !13 %a5 = getelementptr inbounds %struct.S1, %struct.S1* %1, i32 0, i32 0, !dbg !19 br label %if.end if.end: ; preds = %if.else, %if.then %a5.sink = phi [10 x i32]* [ %a5, %if.else ], [ %a, %if.then ] %.sink = phi i32 [ %x, %if.else ], [ %add, %if.then ] %idxprom6 = sext i32 %i to i64 %arrayidx7 = getelementptr inbounds [10 x i32], [10 x i32]* %a5.sink, i64 0, i64 %idxprom6 store i32 %.sink, i32* %arrayidx7, align 4, !tbaa !20 ret void, !dbg !22 } ``` where ``` !11 = !DILocation(line: 9, column: 18, scope: !9) !12 = !DILocation(line: 9, column: 5, scope: !9) !18 = !DILocation(line: 11, column: 5, scope: !9) !19 = !DILocation(line: 11, column: 9, scope: !9) ``` . And below is after gvn-hoist: ``` define void @foo(i32 %x, i32 %y, i32 %i) !dbg !4 { entry: %tobool = icmp ne i32 %y, 0, !dbg !8 %idxprom = sext i32 %i to i64, !dbg !10 %0 = getelementptr inbounds [10 x %struct.S1*], [10 x %struct.S1*]* @s1, i64 0, i64 %idxprom, !dbg !10 %1 = load %struct.S1*, %struct.S1** %0, align 8, !dbg !10, !tbaa !11 br i1 %tobool, label %if.then, label %if.else, !dbg !15 if.then: ; preds = %entry %add = add nsw i32 %x, %y, !dbg !16 %arrayidx = getelementptr inbounds [10 x %struct.S1*], [10 x %struct.S1*]* @s1, i64 0, i64 %idxprom, !dbg !10 %a = getelementptr inbounds %struct.S1, %struct.S1* %1, i32 0, i32 0, !dbg !17 br label %if.end, !dbg !10 if.else: ; preds = %entry %arrayidx4 = getelementptr inbounds [10 x %struct.S1*], [10 x %struct.S1*]* @s1, i64 0, i64 %idxprom, !dbg !18 %a5 = getelementptr inbounds %struct.S1, %struct.S1* %1, i32 0, i32 0, !dbg !19 br label %if.end if.end: ; preds = %if.else, %if.then %a5.sink = phi [10 x i32]* [ %a5, %if.else ], [ %a, %if.then ] %.sink = phi i32 [ %x, %if.else ], [ %add, %if.then ] %arrayidx7 = getelementptr inbounds [10 x i32], [10 x i32]* %a5.sink, i64 0, i64 %idxprom store i32 %.sink, i32* %arrayidx7, align 4, !tbaa !20 ret void, !dbg !22 } ``` As you see, loads and their GEPs have been hosited from if.then/if.else block to entry block. However, DebugLoc metadata of these new instructions are still same as the instructions in if.then block, as they are moved/cloned from if.then block. This may result incorrect stepping and imprecise sample profile result. Reviewers: majnemer, pcc, sebpop Reviewed By: sebpop Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29377 llvm-svn: 294250
* [GVNHoist] Invalidate MemDep when an instruction is moved.Eli Friedman2016-12-071-0/+1
| | | | | | | | | | See also r279907. Fixes https://llvm.org/bugs/show_bug.cgi?id=30991 . Differential Revision: https://reviews.llvm.org/D27493 llvm-svn: 288968
* [GVNHoist] Rename variables.Aditya Kumar2016-11-291-14/+16
| | | | | | Differential Revision: https://reviews.llvm.org/D27110 llvm-svn: 288142
* [GVNHoist] Enable aggressive hoisting when optimizing for code-sizeAditya Kumar2016-11-291-5/+13
| | | | | | | | | Enable scalar hoisting at -Oz as it is safe to hoist scalars to a place where they are partially needed. Differential Revision: https://reviews.llvm.org/D27111 llvm-svn: 288141
* [MemorySSA] Tighten up types to make our API prettier. NFC.George Burgess IV2016-11-011-4/+3
| | | | | | | | Patch by bryant. Differential Revision: https://reviews.llvm.org/D26126 llvm-svn: 285750
* commit back "GVN-hoist: fix store past load dependence analysis (PR30216, ↵Sebastian Pop2016-10-131-41/+48
| | | | | | | | | | PR30499)" This is with an extra change to avoid calling MemoryLocation::get() on a call instruction. Differential Revision: https://reviews.llvm.org/D25542 llvm-svn: 284098
* 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
OpenPOWER on IntegriCloud