summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [RewriteStatepointsForGC] Strengthen a confusingly weak assertion [NFC]Philip Reames2015-09-101-3/+3
| | | | | | The assertion was weaker than it should be and gave the impression we're growing the number of base defining values being considered during the fixed point interation. That's not true. The tighter form of the assert is useful documentation. llvm-svn: 247221
* [RewriteStatepointsForGC] One last bit of naming [NFCI]Philip Reames2015-09-101-7/+7
| | | | llvm-svn: 247220
* [RewriteStatepointsForGC] Further style/naming fixup [NFCI]Philip Reames2015-09-101-26/+26
| | | | llvm-svn: 247217
* [RewriteStatepointsForGC] More naming cleanup [NFCI]Philip Reames2015-09-101-6/+6
| | | | llvm-svn: 247213
* [RewriteStatepointsForGC] Code cleanup [NFC]Philip Reames2015-09-091-25/+26
| | | | | | Factor out common code related to naming values, fix a small style issue. More to follow in separate changes. llvm-svn: 247211
* [RewriteStatepointsForGC] Extend base pointer inference to handle insertelementPhilip Reames2015-09-091-58/+61
| | | | | | | | | | | | This change is simply enhancing the existing inference algorithm to handle insertelement instructions by conservatively inserting a new instruction to propagate the vector of associated base pointers. In the process, I'm ripping out the peephole optimizations which mostly helped cover the fact this hadn't been done. Note that most of the newly inserted nodes will be nearly immediately removed by the post insertion optimization pass introduced in 246718. Arguably, we should be trying harder to avoid the malloc traffic here, but I'd rather get the code correct, then worry about compile time. Unlike previous extensions of the algorithm to handle more case, I discovered the existing code was causing miscompiles in some cases. In particular, we had an implicit assumption that the peephole covered *all* insert element instructions, so if we had a value directly based on a insert element the peephole didn't cover, we proceeded as if it were a base anyways. Not good. I believe we had the same issue with shufflevector which is why I adjusted the predicate for them as well. Differential Revision: http://reviews.llvm.org/D12583 llvm-svn: 247210
* [RewriteStatepointsForGC] Make base pointer inference deterministicPhilip Reames2015-09-091-44/+35
| | | | | | | | | | | | | | Previously, the base pointer algorithm wasn't deterministic. The core fixed point was (of course), but we were inserting new nodes and optimizing them in an order which was unspecified and variable. We'd somewhat hacked around this for testing by sorting by value name, but that doesn't solve the general determinism problem. Instead, we can use the order of traversal over the def/use graph to give us a single consistent ordering. Today, this is a DFS order, but the exact order doesn't mater provided it's deterministic for a given input. (Q: It is safe to rely on a deterministic order of operands right?) Note that this only fixes the determinism within a single inference step. The inference step is currently invoked many times in a non-deterministic order. That's a future change in the sequence. :) Differential Revision: http://reviews.llvm.org/D12640 llvm-svn: 247208
* [RewriteStatepointsForGC] Extract common code, comment, and fix a build ↵Philip Reames2015-09-031-55/+48
| | | | | | warning [NFC] llvm-svn: 246810
* [RewriteStatepointsForGC] Strengthen invariants around BDVsPhilip Reames2015-09-031-29/+65
| | | | | | | | | | As a first step towards a new implementation of the base pointer inference algorithm, introduce an abstraction for BDVs, strengthen the assertions around them, and rewrite the BDV relation code in terms of the abstraction which includes an explicit notion of whether the BDV is also a base. The later is motivated by the fact we had a bug where insertelement was always assumed to be a base pointer even though the BDV code knew it wasn't. The strengthened assertions in this patch would have caught that bug. The next step will be to separate the DefiningValueMap into a BDV use list cache (entirely within findBasePointers) and a base pointer cache. Having the former will allow me to use a deterministic visit order when visiting BDVs in the inference algorithm and remove a bunch of ordering related hacks. Before actually doing the last step, I'm likely going to extend the lattice with a 'BaseN' (seen only base inputs) state so that I can kill the post process optimization step. Phabricator Revision: http://reviews.llvm.org/D12608 llvm-svn: 246809
* [RewriteStatepointsForGC] Workaround a lack of determinism in visit orderPhilip Reames2015-09-031-4/+9
| | | | | | | | The visit order being used in the base pointer inference algorithm is currently non-deterministic. When working on http://reviews.llvm.org/D12583, I discovered that we were relying on a peephole optimization to get deterministic ordering in one of the test cases. This change is intented to let me test and land http://reviews.llvm.org/D12583. The current code will not be long lived. I'm starting to investigate a rewrite of the algorithm which will combine the post-process step into the initial algorithm and make the visit order determistic. Before doing that, I wanted to make sure the existing code was complete and the test were stable. Hopefully, patches should be up for review for the new algorithm this week or early next. llvm-svn: 246801
* [RewriteStatepointsForGC] Delete stale comment [NFC]Philip Reames2015-09-021-3/+0
| | | | llvm-svn: 246722
* [RewriteStatepointsForGC] Pull a function out of anon namespace [NFC]Philip Reames2015-09-021-1/+5
| | | | | | Thanks to David Blaikie for noticing in previous commit. llvm-svn: 246721
* [RewriteStatepointsForGC] Bugfix for change 246133Philip Reames2015-09-021-16/+16
| | | | | | | | Fix a bug in change 246133. I didn't handle the case where we had a cycle in the use graph and could add an instruction we were about to erase back on to the worklist. Oddly, I have not been able to write a small test case for this, even with the AssertingVH added. I have confirmed the basic theory for the fix on a large failing example, but all attempts to reduce that to something appropriate for a test case have failed. Differential Revision: http://reviews.llvm.org/D12575 llvm-svn: 246718
* Fix release build warning for unused functionPhilip Reames2015-09-021-1/+2
| | | | llvm-svn: 246717
* [RewriteStatepointsForGC] Improve debug output [NFC]Philip Reames2015-09-021-30/+36
| | | | llvm-svn: 246713
* [RewriteStatepointsForGC] Reduce the number of new instructions for base ↵Philip Reames2015-08-271-3/+57
| | | | | | | | | | | | | | pointers When computing base pointers, we introduce new instructions to propagate the base of existing instructions which might not be bases. However, the algorithm doesn't make any effort to recognize when the new instruction to be inserted is the same as an existing one already in the IR. Since this is happening immediately before rewriting, we don't really have a chance to fix it after the pass runs without teaching loop passes about statepoints. I'm really not thrilled with this patch. I've rewritten it 4 different ways now, but this is the best I've come up with. The case where the new instruction is just the original base defining value could be merged into the existing algorithm with some complexity. The problem is that we might have something like an extractelement from a phi of two vectors. It may be trivially obvious that the base of the 0th element is an existing instruction, but I can't see how to make the algorithm itself figure that out. Thus, I resort to the call to SimplifyInstruction instead. Note that we can only adjust the instructions we've inserted ourselves. The live sets are still being tracked in side structures at this point in the code. We can't easily muck with instructions which might be in them. Long term, I'm really thinking we need to materialize the live pointer sets explicitly in the IR somehow rather than using side structures to track them. Differential Revision: http://reviews.llvm.org/D12004 llvm-svn: 246133
* [RewriteStatepointsForGC] Avoid using unrelocated pointers after safepointsPhilip Reames2015-08-121-0/+31
| | | | | | | | | | | | | | | | To be clear: this is an *optimization* not a correctness change. CodeGenPrep likes to duplicate icmps feeding branch instructions to take advantage of x86's ability to fuze many comparison/branch patterns into a single micro-op and to reduce the need for materializing i1s into general registers. PlaceSafepoints likes to place safepoint polls right at the end of basic blocks (immediately before terminators) when inserting entry and backedge safepoints. These two heuristics interact in a somewhat unfortunate way where the branch terminating the original block will be controlled by a condition driven by unrelocated pointers. This forces the register allocator to keep both the relocated and unrelocated values of the pointers feeding the icmp alive over the safepoint poll. One simple fix would have been to just adjust PlaceSafepoints to move one back in the basic block, but you can reach similar cases as a result of LICM or other hoisting passes. As a result, doing a post insertion fixup seems to be more robust. I considered doing this in CodeGenPrep itself, but having to update the live sets of already rewritten safepoints gets complicated fast. In particular, you can't just use def/use information because by moving the icmp, we're extending the live range of it's inputs potentially. Instead, this patch teaches RewriteStatepointsForGC to make the required adjustments before making the relocations explicit in the IR. This change really highlights the fact that RSForGC is a CodeGenPrep-like pass which is performing target specific lowering. In the long run, we may even want to combine the two though this would require a lot more smarts to be integrated into RSForGC first. We currently rely on being able to run a set of cleanup passes post rewriting because the IR RSForGC generates is pretty damn ugly. Differential Revision: http://reviews.llvm.org/D11819 llvm-svn: 244821
* [RewriteStatepointsForGC] Handle extractelement fully in the base pointer ↵Philip Reames2015-08-121-61/+96
| | | | | | | | | | algorithm When rewriting the IR such that base pointers are available for every live pointer, we potentially need to duplicate instructions to propagate the base. The original code had only handled PHI and Select under the belief those were the only instructions which would need duplicated. When I added support for vector instructions, I'd added a collection of hacks for ExtractElement which caught most of the common cases. Of course, I then found the one test case my hacks couldn't cover. :) This change removes all of the early hacks for extract element. By defining extractelement as a BDV (rather than trying to look through it), we can extend the rewriting algorithm to duplicate the extract as needed. Note that a couple of peephole optimizations were left in for the moment, because while we now handle extractelement as a first class citizen, we're not yet handling insertelement. That change will follow in the near future. llvm-svn: 244808
* Fix some comment typos.Benjamin Kramer2015-08-081-19/+19
| | | | llvm-svn: 244402
* Rename inst_range() to instructions() for consistency. NFCNico Rieck2015-08-061-2/+2
| | | | llvm-svn: 244248
* De-constify pointers to Type since they can't be modified. NFCCraig Topper2015-08-011-2/+2
| | | | | | This was already done in most places a while ago. This just fixes the ones that crept in over time. llvm-svn: 243842
* [RewriteStatepointsForGC] Adjust naming scheme to be more stablePhilip Reames2015-07-241-3/+7
| | | | | | The names for instructions inserted were previous dependent on iteration order. By deriving the names from the original instructions, we can avoid instability in tests without resorting to ordered traversals. It also makes the IR mildly easier to read at large scale. llvm-svn: 243140
* [RewriteStatepointsForGC] Fix release build warningPhilip Reames2015-07-241-0/+2
| | | | llvm-svn: 243076
* [RewriteStatepointsForGC] Use a worklist algorithm for first part of base ↵Philip Reames2015-07-241-36/+39
| | | | | | | | | | pointer algorithm [NFC] The new code should hopefully be equivalent to the old code; it just uses a worklist to track instructions which need to visited rather than iterating over all instructions visited each time. This should be faster, but the primary benefit is that the purpose should be more clear and the diff of adding another instruction type (forthcoming) much more obvious. Differential Revision: http://reviews.llvm.org/D11480 llvm-svn: 243071
* [RewriteStatepointsForGC] Rename PhiState to reflect that it's associated ↵Philip Reames2015-07-231-41/+43
| | | | | | | | w/more than just PHIs Today, Select instructions also have associated PhiStates. In the near future, so will ExtractElement and SuffleVector. llvm-svn: 243056
* [RewriteStatepointsForGC] Use idomatic mechanisms for debug tracing [NFC]Philip Reames2015-07-231-21/+22
| | | | | | Deleting much of the code using trace-rewrite-statepoints and use idiomatic DEBUG statements instead. This includes adding operator<< to a helper class. llvm-svn: 243054
* [RewriteStatepointsForGC] Simplify code around meet of PhiStates [NFC]Philip Reames2015-07-231-33/+34
| | | | | | We don't need to pass in the map from BDV to PhiStates; we can instead handle that externally and let the MeetPhiStates helper class just meet PhiStates. llvm-svn: 243045
* [PM/AA] Remove all of the dead AliasAnalysis pointers being threadedChandler Carruth2015-07-221-1/+1
| | | | | | | | | | 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
* [RewriteStatepointsForGC] minor style cleanupPhilip Reames2015-07-211-26/+25
| | | | | | Use a named lambda for readability, common some code, remove a stale comments, and use llvm style variable names. llvm-svn: 242827
* [RewriteStatepointsForGC] Hoist some code out of a loopPhilip Reames2015-07-211-12/+13
| | | | llvm-svn: 242808
* [RewriteStatepointsForGC] Delete trivial codePhilip Reames2015-07-211-13/+5
| | | | | | A bit more code cleanup: delete some a trivial true assertion and supporting code, remove a redundant cast, and use count in assertions where feasible. llvm-svn: 242805
* [RewriteStatepointsForGC] Minor code cleanup [NFC]Philip Reames2015-07-211-21/+5
| | | | | | We can use builders to simplify part of the code and we only check for the existance of the metadata value; this enables us to delete some redundant code. llvm-svn: 242751
* [RewriteStatepointsForGC] Generalized vector phi/select handling for base ↵Philip Reames2015-06-261-55/+124
| | | | | | | | | | | | | | | pointers This change extends the detection of base pointers for vector constructs to handle arbitrary phi and select nodes. The existing non-vector code already handles those, so this is basically just extending the vector special case to be less special cased. It still isn't generalized vector handling since we can't handle arbitrary vector instructions (e.g. shufflevectors), but it's a lot closer. The general structure of the change is as follows: * Extend the base defining value relation over a subset of vector instructions and vector typed phi & select instructions. * Move scalarization from before base pointer rewriting to after base pointer rewriting. The extension of the BDV relation is sufficient to find vector base phis for vector inputs. * Preserve the existing special case logic for when the base of a vector element is locally obvious. This general idea could be extended to the scalar case as well. Differential Revision: http://reviews.llvm.org/D10461#inline-84275 llvm-svn: 240850
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-2/+2
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-2/+2
| | | | | | | | | | | | | 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
* [Statepoints] Skip a vector copy when uniquing values.Benjamin Kramer2015-06-131-11/+4
| | | | | | No functionality change intended. llvm-svn: 239688
* Remove stray semicolon. NFC.Vasileios Kalintiris2015-06-031-1/+1
| | | | llvm-svn: 238908
* [RewriteStatepointsForGC] Strip deref info after rewriting.Sanjoy Das2015-06-021-0/+102
| | | | | | | | | | | | | | | | | | | | | Summary: Once a gc.statepoint has been rewritten to relocate live references, the SSA values represent physical pointers instead of logical references. Logical dereferencability does not imply physical dereferencability and after RewriteStatepointsForGC has run any attributes that imply dereferencability of the logical references need to be stripped. This current approach is conservative, and can be made more precise later if needed. For starters, we need to strip dereferencable attributes only from pointers that live in the GC address space. Reviewers: reames, pgavlin Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10105 llvm-svn: 238883
* [NFCI] Change RewriteStatepointsForGC to a ModulePass.Sanjoy Das2015-06-021-13/+16
| | | | | | | | | | | | | | Summary: A later change that has RewriteStatepointsForGC change function attributes throughout the module depends on this. Reviewers: reames, pgavlin Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10104 llvm-svn: 238882
* Reformat.NAKAMURA Takumi2015-05-251-3/+2
| | | | llvm-svn: 238126
* Prune CRLFs.NAKAMURA Takumi2015-05-251-9/+9
| | | | llvm-svn: 238125
* [RewriteStatepointsForGC] Fix debug assertion during derivable pointer ↵Igor Laevsky2015-05-211-6/+6
| | | | | | | | | | rematerialization Correct assertion would be that there is no other uses from chain we are currently cloning. It is ok to have other uses of values not from this chain. Differential Revision: http://reviews.llvm.org/D9882 llvm-svn: 237899
* Silencing a -Wsign-compare warning; NFC.Aaron Ballman2015-05-201-1/+1
| | | | llvm-svn: 237794
* Add a GCStrategy for CoreCLRSwaroop Sridhar2015-05-201-3/+8
| | | | | | | | | | | | | | This change adds a new GC strategy for supporting the CoreCLR runtime. This strategy is currently identical to Statepoint-example GC, but is necessary for several upcoming changes specific to CoreCLR, such as: 1. Base-pointers not explicitly reported for interior pointers 2. Different format for stack-map encoding 3. Location of Safe-point polls: polls are only needed before loop-back edges and before tail-calls (not needed at function-entry) 4. Runtime specific handshake between calls to managed/unmanaged functions. llvm-svn: 237753
* [RewriteStatepointsForGC] Fix up naming in "relocationViaAlloca" and run it ↵Igor Laevsky2015-05-191-56/+56
| | | | | | | | through clang-format. Differential Revision: http://reviews.llvm.org/D9774 llvm-svn: 237703
* [RewriteStatepointsForGC] For some values (like gep's and bitcasts) it's ↵Igor Laevsky2015-05-191-6/+278
| | | | | | | | cheaper to clone them after statepoint than to emit proper relocates for them. This change implements this logic. There is alredy similar optimization in CodeGenPrepare, but doing so during RewriteStatepointsForGC allows to capture more opprtunities such as relocates in loops and longer instruction chains. Differential Revision: http://reviews.llvm.org/D9774 llvm-svn: 237701
* Simplify IRBuilder::CreateCall* by using ArrayRef+initializer_list/braced ↵David Blaikie2015-05-181-2/+2
| | | | | | init only llvm-svn: 237624
* [RewriteStatepointsForGC] Extend base pointer to handle more cases w/vectorsPhilip Reames2015-05-121-9/+36
| | | | | | | | | | When relocating a pointer, we need to determine a base pointer for the derived pointer being relocated. We have limited support for handling a pointer extracted from a vector; the current code only handled the case where the entire vector was known to contain base pointers. This patch extends the reasoning to handle chains of insertelements where the indices are constants. This case turns out to be fairly common in vectorized code. We can now handle vectors which contains mixtures of base and derived pointers provided the insertelements use constant indices. Note that this doesn't solve the general problem. To handle variable indexed insertelements, we'd need to scalarize and introduce conditional branching based on the index. Alternatively, we could eagerly scalarize, but the code structure doesn't currently make either fix easy. The patch also doesn't handle shufflevector or other vector manipulation for much the same reasons. I plan to defer this work until I have a motivating test case. Differential Revision: http://reviews.llvm.org/D9676 llvm-svn: 237200
* Rename variables in gc_relocate related functions to follow LLVM's naming ↵Sanjoy Das2015-05-111-39/+39
| | | | | | | | | | | | | | | | | | | | conventions. Summary: This patch is to rename some variables to CamelCase in gc_relocate related functions. There is no functionality change. Patch by Chen Li! Reviewers: reames, AndyAyers, sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9681 llvm-svn: 237069
* [RewriteStatepointsForGC] Fix a bug on creating gc_relocate for pointer to ↵Sanjoy Das2015-05-111-3/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | vector of pointers Summary: In RewriteStatepointsForGC pass, we create a gc_relocate intrinsic for each relocated pointer, and the gc_relocate has the same type with the pointer. During the creation of gc_relocate intrinsic, llvm requires to mangle its type. However, llvm does not support mangling of all possible types. RewriteStatepointsForGC will hit an assertion failure when it tries to create a gc_relocate for pointer to vector of pointers because mangling for vector of pointers is not supported. This patch changes the way RewriteStatepointsForGC pass creates gc_relocate. For each relocated pointer, we erase the type of pointers and create an unified gc_relocate of type i8 addrspace(1)*. Then a bitcast is inserted to convert the gc_relocate to the correct type. In this way, gc_relocate does not need to deal with different types of pointers and the unsupported type mangling is no longer a problem. This change would also ease further merge when LLVM erases types of pointers and introduces an unified pointer type. Some minor changes are also introduced to gc_relocate related part in InstCombineCalls, CodeGenPrepare, and Verifier accordingly. Patch by Chen Li! Reviewers: reames, AndyAyers, sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9592 llvm-svn: 237009
OpenPOWER on IntegriCloud