summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/GVN.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [GVN] Factor out common code [NFCI]Philip Reames2016-01-251-40/+21
| | | | | | We had the same code duplicated for each type of Def. We also have the entire block duplicated between the local and non-local case, but let's start with local cleanup. llvm-svn: 258740
* [opaque pointer types] [NFC] Add an explicit type argument to ↵Eduard Burtescu2016-01-221-2/+2
| | | | | | | | | | | | ConstantFoldLoadFromConstPtr. Reviewers: mjacob, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D16418 llvm-svn: 258472
* Fix for two constant propagation problems in GVN with the assume intrinsicDavid L Kreitzer2016-01-211-3/+4
| | | | | | | | | | instruction. Patch by Yuanrui Zhang. Differential Revision: http://reviews.llvm.org/D16100 llvm-svn: 258435
* Use range-based for loops. NFCCraig Topper2015-11-281-37/+20
| | | | llvm-svn: 254222
* [WinEH] Fix a case where GVN could incorrectly PRE a load into an EH pad.Andrew Kaylor2015-11-231-0/+10
| | | | | | Differential Revision: http://reviews.llvm.org/D14842 llvm-svn: 253908
* Fix bug 25440: GVN assertion after coercing loadsWeiming Zhao2015-11-191-1/+12
| | | | | | | | | | | | | | | | Optimizations like LoadPRE in GVN will insert new instructions. If the insertion point is in a already processed BB, they should get a value number explicitly. If the insertion point is after current instruction, then just leave it. However, current GVN framework has no support for it. In this patch, we just bail out if a VN can't be found. Dfferential Revision: http://reviews.llvm.org/D14670 A test/Transforms/GVN/pr25440.ll M lib/Transforms/Scalar/GVN.cpp llvm-svn: 253536
* Fix returned value for GVN: could return "false" even after modifying the IRMehdi Amini2015-11-181-1/+1
| | | | | | | | | | | | | | | | | | | | | | This bug would manifest in some very specific cases where all the following conditions are fullfilled: - GVN didn't remove block - The regular GVN iteration didn't change the IR - PRE is enabled - PRE will not split critical edge - The last instruction processed by PRE didn't change the IR Because the CallGraph PassManager relies on this returned value to decide if it needs to recompute a node after the execution of Function passes, not returning the right value can lead to unexpected results. Fix for: https://llvm.org/bugs/show_bug.cgi?id=24715 Patch by Wenxiang Qiu <vincentqiuuu@gmail.com> From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 253518
* Disable gvn non-local speculative loads under asan.Mike Aizatsky2015-11-181-0/+4
| | | | | | | | Summary: Fix for https://llvm.org/bugs/show_bug.cgi?id=25550 Differential Revision: http://reviews.llvm.org/D14763 llvm-svn: 253498
* [PRE] Preserve !invariant.load metadataPhilip Reames2015-11-171-0/+2
| | | | | | Spoted via inspection. Test case included. llvm-svn: 253275
* Revert "Fix bug 25440: GVN assertion after coercing loads"Tobias Grosser2015-11-121-41/+13
| | | | | | This reverts 252919 which broke LNT: MultiSource/Applications/SPASS llvm-svn: 252936
* Fix bug 25440: GVN assertion after coercing loadsWeiming Zhao2015-11-121-13/+41
| | | | | | | | | | | | | | | | Summary: when coercing loads, it inserts some instructions, which have no GV assigned. https://llvm.org/bugs/show_bug.cgi?id=25440 Reviewers: hfinkel, dberlin Subscribers: dberlin, llvm-commits Differential Revision: http://reviews.llvm.org/D14479 llvm-svn: 252919
* GVN: don't try to replace instruction with itself.Tim Northover2015-10-231-5/+9
| | | | | | | | | | | After some look-ahead PRE was added for GEPs, an instruction could end up in the table of candidates before it was actually inspected. When this happened the pass might decide it was the best candidate to replace itself. This didn't go well. Should fix PR25291 llvm-svn: 251145
* Scalar: Remove some implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-10-131-5/+5
| | | | | | | Remove some of the implicit ilist iterator conversions in LLVMScalarOpts. More to go. llvm-svn: 250197
* inariant.group handling in GVNPiotr Padlewski2015-10-021-8/+9
| | | | | | | | | | | | The most important part required to make clang devirtualization works ( ͡°͜ʖ ͡°). The code is able to find non local dependencies, but unfortunatelly because the caller can only handle local dependencies, I had to add some restrictions to look for dependencies only in the same BB. http://reviews.llvm.org/D12992 llvm-svn: 249196
* gvn small fixPiotr Padlewski2015-09-171-3/+1
| | | | | | http://reviews.llvm.org/D12928 llvm-svn: 247935
* [PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatibleChandler Carruth2015-09-091-4/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | with the new pass manager, and no longer relying on analysis groups. This builds essentially a ground-up new AA infrastructure stack for LLVM. The core ideas are the same that are used throughout the new pass manager: type erased polymorphism and direct composition. The design is as follows: - FunctionAAResults is a type-erasing alias analysis results aggregation interface to walk a single query across a range of results from different alias analyses. Currently this is function-specific as we always assume that aliasing queries are *within* a function. - AAResultBase is a CRTP utility providing stub implementations of various parts of the alias analysis result concept, notably in several cases in terms of other more general parts of the interface. This can be used to implement only a narrow part of the interface rather than the entire interface. This isn't really ideal, this logic should be hoisted into FunctionAAResults as currently it will cause a significant amount of redundant work, but it faithfully models the behavior of the prior infrastructure. - All the alias analysis passes are ported to be wrapper passes for the legacy PM and new-style analysis passes for the new PM with a shared result object. In some cases (most notably CFL), this is an extremely naive approach that we should revisit when we can specialize for the new pass manager. - BasicAA has been restructured to reflect that it is much more fundamentally a function analysis because it uses dominator trees and loop info that need to be constructed for each function. All of the references to getting alias analysis results have been updated to use the new aggregation interface. All the preservation and other pass management code has been updated accordingly. The way the FunctionAAResultsWrapperPass works is to detect the available alias analyses when run, and add them to the results object. This means that we should be able to continue to respect when various passes are added to the pipeline, for example adding CFL or adding TBAA passes should just cause their results to be available and to get folded into this. The exception to this rule is BasicAA which really needs to be a function pass due to using dominator trees and loop info. As a consequence, the FunctionAAResultsWrapperPass directly depends on BasicAA and always includes it in the aggregation. This has significant implications for preserving analyses. Generally, most passes shouldn't bother preserving FunctionAAResultsWrapperPass because rebuilding the results just updates the set of known AA passes. The exception to this rule are LoopPass instances which need to preserve all the function analyses that the loop pass manager will end up needing. This means preserving both BasicAAWrapperPass and the aggregating FunctionAAResultsWrapperPass. Now, when preserving an alias analysis, you do so by directly preserving that analysis. This is only necessary for non-immutable-pass-provided alias analyses though, and there are only three of interest: BasicAA, GlobalsAA (formerly GlobalsModRef), and SCEVAA. Usually BasicAA is preserved when needed because it (like DominatorTree and LoopInfo) is marked as a CFG-only pass. I've expanded GlobalsAA into the preserved set everywhere we previously were preserving all of AliasAnalysis, and I've added SCEVAA in the intersection of that with where we preserve SCEV itself. One significant challenge to all of this is that the CGSCC passes were actually using the alias analysis implementations by taking advantage of a pretty amazing set of loop holes in the old pass manager's analysis management code which allowed analysis groups to slide through in many cases. Moving away from analysis groups makes this problem much more obvious. To fix it, I've leveraged the flexibility the design of the new PM components provides to just directly construct the relevant alias analyses for the relevant functions in the IPO passes that need them. This is a bit hacky, but should go away with the new pass manager, and is already in many ways cleaner than the prior state. Another significant challenge is that various facilities of the old alias analysis infrastructure just don't fit any more. The most significant of these is the alias analysis 'counter' pass. That pass relied on the ability to snoop on AA queries at different points in the analysis group chain. Instead, I'm planning to build printing functionality directly into the aggregation layer. I've not included that in this patch merely to keep it smaller. Note that all of this needs a nearly complete rewrite of the AA documentation. I'm planning to do that, but I'd like to make sure the new design settles, and to flesh out a bit more of what it looks like in the new pass manager first. Differential Revision: http://reviews.llvm.org/D12080 llvm-svn: 247167
* assuem(X) handling in GVN bugfixPiotr Padlewski2015-09-021-1/+20
| | | | | | | | | | There was infinite loop because it was trying to change assume(true) into assume(true) Also added handling when assume(false) appear http://reviews.llvm.org/D12516 llvm-svn: 246697
* Constant propagation after hitting assume(cmp) bugfixPiotr Padlewski2015-09-021-9/+26
| | | | | | | | | Last time code run into assertion `BBE.isSingleEdge()` in lib/IR/Dominators.cpp:200. http://reviews.llvm.org/D12170 llvm-svn: 246696
* Constant propagation after hiting llvm.assumePiotr Padlewski2015-09-021-3/+68
| | | | | | | | | | | After hitting @llvm.assume(X) we can: - propagate equality that X == true - if X is icmp/fcmp (with eq operation), and one of operand is constant we can change all variables with constants in the same BasicBlock http://reviews.llvm.org/D11918 llvm-svn: 246695
* Revert r246244 and r246243Steven Wu2015-08-281-93/+11
| | | | | | These two commits cause clang/llvm bootstrap to hang. llvm-svn: 246279
* Constant propagation after hitting assume(cmp) bugfixPiotr Padlewski2015-08-281-9/+26
| | | | | | | | | Last time code run into assertion `BBE.isSingleEdge()` in lib/IR/Dominators.cpp:200. http://reviews.llvm.org/D12170 llvm-svn: 246244
* Constant propagation after hiting llvm.assumePiotr Padlewski2015-08-281-3/+68
| | | | | | | | | | | After hitting @llvm.assume(X) we can: - propagate equality that X == true - if X is icmp/fcmp (with eq operation), and one of operand is constant we can change all variables with constants in the same BasicBlock http://reviews.llvm.org/D11918 llvm-svn: 246243
* Rename Instruction::dropUnknownMetadata() to dropUnknownNonDebugMetadata()Adrian Prantl2015-08-201-1/+0
| | | | | | | | | | | and make it always preserve debug locations, since all callers wanted this behavior anyway. This is addressing a post-commit review feedback for r245589. NFC (inside the LLVM tree). llvm-svn: 245622
* Fix a bug that caused SimplifyCFG to drop DebugLocs.Adrian Prantl2015-08-201-0/+1
| | | | | | | | | | | Instruction::dropUnknownMetadata(KnownSet) is supposed to preserve all metadata in KnownSet, but the condition for DebugLocs was inverted. Most users of dropUnknownMetadata() actually worked around this by not adding LLVMContext::MD_dbg to their list of KnowIDs. This is now made explicit. llvm-svn: 245589
* Fix a debug location handling bug in GVN.Adrian Prantl2015-08-201-1/+2
| | | | | | | | | | | | | | Caught by the famous "DebugLoc describes the currect SubProgram" assertion. When GVN is removing a nonlocal load it updates the debug location of the SSA value it replaced the load with with the one of the load. In the testcase this actually overwrites a valid debug location with an empty one. In reality GVN has to make an arbitrary choice between two equally valid debug locations. This patch changes to behavior to only update the location if the value doesn't already have a debug location. llvm-svn: 245588
* Revert "Constant propagation after hiting llvm.assume"Justin Bogner2015-08-181-68/+3
| | | | | | | | | | This was also failing bootstrap: http://lab.llvm.org:8080/green/job/clang-stage2-configure-Rlto_build This reverts r245265. llvm-svn: 245269
* Constant propagation after hiting llvm.assumePiotr Padlewski2015-08-181-3/+68
| | | | | | | | | | | After hitting @llvm.assume(X) we can: - propagate equality that X == true - if X is icmp/fcmp (with eq operation), and one of operand is constant we can change all variables with constants in the same BasicBlock http://reviews.llvm.org/D11918 llvm-svn: 245265
* Fix some comment typos.Benjamin Kramer2015-08-081-2/+2
| | | | llvm-svn: 244402
* Drive-by fixes for LandingPad -> EHPadDavid Majnemer2015-08-041-4/+4
| | | | | | | | This change was done as an audit and is by inspection. The new EH system is still very much a work in progress. NFC for the landingpad case. llvm-svn: 243965
* Fix typo "fuction" noticed in comments in AssumptionCache.h, and also all ↵Nick Lewycky2015-07-291-1/+1
| | | | | | | | the other files that have the same typo. All comments, no functionality change! (Merely a "fuctionality" change.) Bonus change to remove emacs major mode marker from SystemZMachineFunctionInfo.cpp because emacs already knows it's C++ from the extension. Also fix typo "appeary" in AMDGPUMCAsmInfo.h. llvm-svn: 243585
* [PM/AA] Remove all of the dead AliasAnalysis pointers being threadedChandler Carruth2015-07-221-5/+5
| | | | | | | | | | through APIs that are no longer necessary now that the update API has been removed. This will make changes to the AA interfaces significantly less disruptive (I hope). Either way, it seems like a really nice cleanup. llvm-svn: 242882
* [PM/AA] Remove the addEscapingUse update API that won't be easy toChandler Carruth2015-07-181-30/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | directly model in the new PM. This also was an incredibly brittle and expensive update API that was never fully utilized by all the passes that claimed to preserve AA, nor could it reasonably have been extended to all of them. Any number of places add uses of values. If we ever wanted to reliably instrument this, we would want a callback hook much like we have with ValueHandles, but doing this for every use addition seems *extremely* expensive in terms of compile time. The only user of this update mechanism is GlobalsModRef. The idea of using this to keep it up to date doesn't really work anyways as its analysis requires a symmetric analysis of two different memory locations. It would be very hard to make updates be sufficiently rigorous to *guarantee* symmetric analysis in this way, and it pretty certainly isn't true today. However, folks have been using GMR with this update for a long time and seem to not be hitting the issues. The reported issue that the update hook fixes isn't even a problem any more as other changes to GetUnderlyingObject worked around it, and that issue stemmed from *many* years ago. As a consequence, a prior patch provided a flag to control the unsafe behavior of GMR, and this patch removes the update mechanism that has questionable compile-time tradeoffs and is causing problems with moving to the new pass manager. Note the lack of test updates -- not one test in tree actually requires this update, even for a contrived case. All of this was extensively discussed on the dev list, this patch will just enact what that discussion decides on. I'm sending it for review in part to show what I'm planning, and in part to show the *amazing* amount of work this avoids. Every call to the AA here is something like three to six indirect function calls, which in the non-LTO pipeline never do any work! =[ Differential Revision: http://reviews.llvm.org/D11214 llvm-svn: 242605
* GVN: use a static array instead of regenerating it each time. NFC.Tim Northover2015-07-141-1/+1
| | | | llvm-svn: 242202
* GVN: tolerate an instruction being replaced without existing in the leaderboardTim Northover2015-07-141-1/+4
| | | | | | | | | | | | | | Sometimes an incidentally created instruction can duplicate a Value used elsewhere. It then often doesn't end up in the leader table. If it's later removed, we attempt to remove it from the leader table and segfault. Instead we should just ignore the removal request, which won't cause any problems. The reverse situation, where the original instruction is replaced by the new one (which you might think could leave the leader table empty) cannot occur, because the incidental instruction will never be found in the first place. llvm-svn: 242199
* [PM/AA] Completely remove the AliasAnalysis::copyValue interface.Chandler Carruth2015-07-111-5/+1
| | | | | | | | | | | | | | | | | | | | | No in-tree alias analysis used this facility, and it was not called in any particularly rigorous way, so it seems unlikely to be correct. Note that one of the only stateful AA implementations in-tree, GlobalsModRef is completely broken currently (and any AA passes like it are equally broken) because Module AA passes are not effectively invalidated when a function pass that fails to update the AA stack runs. Ultimately, it doesn't seem like we know how we want to build stateful AA, and until then trying to support and maintain correctness for an untested API is essentially impossible. To that end, I'm planning to rip out all of the update API. It can return if and when we need it and know how to build it on top of the new pass manager and as part of *tested* stateful AA implementations in the tree. Differential Revision: http://reviews.llvm.org/D10889 llvm-svn: 241975
* GVN: If a branch has two identical successors, we cannot declare either dead.Peter Collingbourne2015-06-251-0/+4
| | | | | | | | | This previously caused miscompilations as a result of phi nodes receiving undef incoming values from blocks dominated by such successors. Differential Revision: http://reviews.llvm.org/D10726 llvm-svn: 240670
* [GVN] Intersect the IR flags when CSE'ing two instructionsDavid Majnemer2015-06-241-7/+3
| | | | | | | | | We performed a simple, but incomplete, intersection when it came time to CSE instructions. It didn't handle, for example, the 'exact' flag. This fixes PR23922. llvm-svn: 240595
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-3/+3
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-3/+3
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* [GVN] Use a simpler form of IRBuilder constructor.Alexey Samsonov2015-06-121-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: A side effect of this change is that it IRBuilder now automatically created debug info locations for new instructions, which is the same as debug location of insertion point. This is fine for the functions in questions (GetStoreValueForLoad and GetMemInstValueForLoad), as they are used in two situations: * GVN::processLoad, which tries to eliminate a load. In this case new instructions would have the same debug location as the load they eventually replace; * MaterializeAdjustedValue, which adds new instructions to the end of the basic blocks, which could later be used to replace the load definition. In this case we don't yet know the way the load would be eventually replaced (either by assembling the precomputed values via PHI, or by using them directly), so just using the basic block strategy seems to be reasonable. There is also a special case in the code that *would* adjust the location of the last instruction replacing the load definition to the location of the load. Test Plan: regression test suite Reviewers: echristo, dberlin, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10405 llvm-svn: 239585
* [GVN] Use IRBuilder more actively instead of creating instructions manually.Alexey Samsonov2015-06-121-20/+21
| | | | llvm-svn: 239584
* [GVN] Set proper debug locations for some instructions created by GVN.Alexey Samsonov2015-06-101-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Determining proper debug locations for instructions created in PHITransAddr is tricky. We use a simple approach here and simply copy debug locations from instructions computing load address to "corresponding" instructions re-creating the address computation in predecessor basic blocks. This may not always be correct, given all the rearrangement and simplification going on, and debug locations may jump around a lot, as the basic blocks we copy locations between may be very far from each other. Still, this would work good in most simple cases (e.g. when chain of address computing instruction is short, or our mapping turns out to be 1-to-1), and we desire to have *some* reasonable debug locations associated with newly inserted instructions. See http://reviews.llvm.org/D10351 review thread for more details. Test Plan: regression test suite Reviewers: spatel, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10351 llvm-svn: 239479
* Extend EarlyCSE to handle basic cases from JumpThreading and CVPPhilip Reames2015-05-221-21/+2
| | | | | | | | | | | | | | This patch extends EarlyCSE to take advantage of the information that a controlling branch gives us about the value of a Value within this and dominated basic blocks. If the current block has a single predecessor with a controlling branch, we can infer what the branch condition must have been to execute this block. The actual change to support this is downright simple because EarlyCSE's existing scoped hash table logic deals with most of the complexity around merging. The patch actually implements two optimizations. 1) The first is analogous to JumpThreading in that it enables EarlyCSE's CSE handling to fold branches which are exactly redundant due to a previous branch to branches on constants. (It doesn't actually replace the branch or change the CFG.) This is pretty clearly a win since it enables substantial CFG simplification before we start trying to inline. 2) The second is analogous to CVP in that it exploits the knowledge gained to replace dominated *uses* of the original value. EarlyCSE does not otherwise reason about specific uses, so this is the more arguable one. It does enable further simplication and constant folding within the rest of the visit by EarlyCSE. In both cases, the added code only handles the easy dominance based case of each optimization. The general case is deferred to the existing passes. Differential Revision: http://reviews.llvm.org/D9763 llvm-svn: 238071
* [opaque pointer type] API migration for GEP constant factoriesDavid Blaikie2015-04-021-2/+4
| | | | | | | | | | | | | Require the pointee type to be passed explicitly and assert that it is correct. For now it's possible to pass nullptr here (and I've done so in a few places in this patch) but eventually that will be disallowed once all clients have been updated or removed. It'll be a long road to get all the way there... but if you have the cahnce to update your callers to pass the type explicitly without depending on a pointer's element type, that would be a good thing to do soon and a necessary thing to do eventually. llvm-svn: 233938
* Re-sort includes with sort-includes.py and insert raw_ostream.h where it's used.Benjamin Kramer2015-03-231-1/+2
| | | | llvm-svn: 232998
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-72/+58
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Now that the DataLayout is a mandatory part of the module, let's start cleaning the codebase. This patch is a first attempt at doing that. This patch is not exactly NFC as for instance some places were passing a nullptr instead of the DataLayout, possibly just because there was a default value on the DataLayout argument to many functions in the API. Even though it is not purely NFC, there is no change in the validation. I turned as many pointer to DataLayout to references, this helped figuring out all the places where a nullptr could come up. I had initially a local version of this patch broken into over 30 independant, commits but some later commit were cleaning the API and touching part of the code modified in the previous commits, so it seemed cleaner without the intermediate state. Test Plan: Reviewers: echristo Subscribers: llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231740
* Make DataLayout Non-Optional in the ModuleMehdi Amini2015-03-041-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: DataLayout keeps the string used for its creation. As a side effect it is no longer needed in the Module. This is "almost" NFC, the string is no longer canonicalized, you can't rely on two "equals" DataLayout having the same string returned by getStringRepresentation(). Get rid of DataLayoutPass: the DataLayout is in the Module The DataLayout is "per-module", let's enforce this by not duplicating it more than necessary. One more step toward non-optionality of the DataLayout in the module. Make DataLayout Non-Optional in the Module Module->getDataLayout() will never returns nullptr anymore. Reviewers: echristo Subscribers: resistor, llvm-commits, jholewinski Differential Revision: http://reviews.llvm.org/D7992 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231270
* only propagate equality comparisons of FP values that we are certain are ↵Sanjay Patel2015-02-251-3/+7
| | | | | | | | | | | | non-zero This is a follow-on to r227491 which tightens the check for propagating FP values. If a non-constant value happens to be a zero, we would hit the same bug as before. Bug noted and patch suggested by Eli Friedman. llvm-svn: 230564
* remove function names from comments; NFCSanjay Patel2015-02-241-42/+38
| | | | llvm-svn: 230391
* Allow PRE to insert no-cost phi nodesDaniel Berlin2015-02-031-44/+68
| | | | llvm-svn: 228024
OpenPOWER on IntegriCloud