[RS4GC] Refactor code for Rematerializing in presence of phi. NFC

Summary:
This is an NFC refactoring change as a precursor to the actual fix for rematerializing in
presence of phi.
https://reviews.

[RS4GC] Refactor code for Rematerializing in presence of phi. NFC

Summary:
This is an NFC refactoring change as a precursor to the actual fix for rematerializing in
presence of phi.
https://reviews.llvm.org/D24399

Pasted from review:
findRematerializableChainToBasePointer changed to return the root of the
chain. instead of true or false.
move the PHI matching logic into the caller by inspecting the root return value.
This includes an assertion that the alternate root is in the liveset for the
call.

Tested with current RS4GC tests.

Reviewers: reames, sanjoy

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D24780

llvm-svn: 282023

show more ...

[statepoints][experimental] Add support for live-in semantics of values in deopt bundles

This is a first step towards supporting deopt value lowering and reporting entirely with the register allocat

[statepoints][experimental] Add support for live-in semantics of values in deopt bundles

This is a first step towards supporting deopt value lowering and reporting entirely with the register allocator. I hope to build on this in the near future to support live-on-return semantics, but I have a use case which allows me to test and investigate code quality with just the live-in semantics so I've chosen to start there. For those curious, my use cases is our implementation of the "__llvm_deoptimize" function we bind to @llvm.deoptimize. I'm choosing not to hard code that fact in the patch and instead make it configurable via function attributes.

The basic approach here is modelled on what is done for the "Live In" values on stackmaps and patchpoints. (A secondary goal here is to remove one of the last barriers to merging the pseudo instructions.) We start by adding the operands directly to the STATEPOINT SDNode. Once we've lowered to MI, we extend the remat logic used by the register allocator to fold virtual register uses into StackMap::Indirect entries as needed. This does rely on the fact that the register allocator rematerializes. If it didn't along some code path, we could end up with more vregs than physical registers and fail to allocate.

Today, we *only* fold in the register allocator. This can create some weird effects when combined with arguments passed on the stack because we don't fold them appropriately. I have an idea how to fix that, but it needs this patch in place to work on that effectively. (There's some weird interaction with the scheduler as well, more investigation needed.)

My near term plan is to land this patch off-by-default, experiment in my local tree to identify any correctness issues and then start fixing codegen problems one by one as I find them. Once I have the live-in lowering fully working (both correctness and code quality), I'm hoping to move on to the live-on-return semantics. Note: I don't have any *known* miscompiles with this patch enabled, but I'm pretty sure I'll find at least a couple. Thus, the "experimental" tag and the fact it's off by default.

Differential Revision: https://reviews.llvm.org/D24000

llvm-svn: 280250

show more ...

[RewriteStatepointsForGC] Update comment for same PHI node check. NFC

llvm-svn: 280052

ADT: Give ilist<T>::reverse_iterator a handle to the current node

Reverse iterators to doubly-linked lists can be simpler (and cheaper)
than std::reverse_iterator. Make it so.

In particular, chang

ADT: Give ilist<T>::reverse_iterator a handle to the current node

Reverse iterators to doubly-linked lists can be simpler (and cheaper)
than std::reverse_iterator. Make it so.

In particular, change ilist<T>::reverse_iterator so that it is *never*
invalidated unless the node it references is deleted. This matches the
guarantees of ilist<T>::iterator.

(Note: MachineBasicBlock::iterator is *not* an ilist iterator, but a
MachineInstrBundleIterator<MachineInstr>. This commit does not change
MachineBasicBlock::reverse_iterator, but it does update
MachineBasicBlock::reverse_instr_iterator. See note at end of commit
message for details on bundle iterators.)

Given the list (with the Sentinel showing twice for simplicity):

[Sentinel] <-> A <-> B <-> [Sentinel]

the following is now true:
1. begin() represents A.
2. begin() holds the pointer for A.
3. end() represents [Sentinel].
4. end() holds the poitner for [Sentinel].
5. rbegin() represents B.
6. rbegin() holds the pointer for B.
7. rend() represents [Sentinel].
8. rend() holds the pointer for [Sentinel].

The changes are #6 and #8. Here are some properties from the old
scheme (which used std::reverse_iterator):
- rbegin() held the pointer for [Sentinel] and rend() held the pointer
for A;
- operator*() cost two dereferences instead of one;
- converting from a valid iterator to its valid reverse_iterator
involved a confusing increment; and
- "RI++->erase()" left RI invalid. The unintuitive replacement was
"RI->erase(), RE = end()".

With vector-like data structures these properties are hard to avoid
(since past-the-beginning is not a valid pointer), and don't impose a
real cost (since there's still only one dereference, and all iterators
are invalidated on erase). But with lists, this was a poor design.

Specifically, the following code (which obviously works with normal
iterators) now works with ilist::reverse_iterator as well:

for (auto RI = L.rbegin(), RE = L.rend(); RI != RE;)
fooThatMightRemoveArgFromList(*RI++);

Converting between iterator and reverse_iterator for the same node uses
the getReverse() function.

reverse_iterator iterator::getReverse();
iterator reverse_iterator::getReverse();

Why doesn't iterator <=> reverse_iterator conversion use constructors?

In order to catch and update old code, reverse_iterator does not even
have an explicit conversion from iterator. It wouldn't be safe because
there would be no reasonable way to catch all the bugs from the changed
semantic (see the changes at call sites that are part of this patch).

Old code used this API:

std::reverse_iterator::reverse_iterator(iterator);
iterator std::reverse_iterator::base();

Here's how to update from old code to new (that incorporates the
semantic change), assuming I is an ilist<>::iterator and RI is an
ilist<>::reverse_iterator:

[Old] ==> [New]
reverse_iterator(I) (--I).getReverse()
reverse_iterator(I) ++I.getReverse()
--reverse_iterator(I) I.getReverse()
reverse_iterator(++I) I.getReverse()
RI.base() (--RI).getReverse()
RI.base() ++RI.getReverse()
--RI.base() RI.getReverse()
(++RI).base() RI.getReverse()
delete &*RI, RE = end() delete &*RI++
RI->erase(), RE = end() RI++->erase()

=======================================
Note: bundle iterators are out of scope
=======================================

MachineBasicBlock::iterator, also known as
MachineInstrBundleIterator<MachineInstr>, is a wrapper to represent
MachineInstr bundles. The idea is that each operator++ takes you to the
beginning of the next bundle. Implementing a sane reverse iterator for
this is harder than ilist. Here are the options:
- Use std::reverse_iterator<MBB::i>. Store a handle to the beginning of
the next bundle. A call to operator*() runs a loop (usually
operator--() will be called 1 time, for unbundled instructions).
Increment/decrement just works. This is the status quo.
- Store a handle to the final node in the bundle. A call to operator*()
still runs a loop, but it iterates one time fewer (usually
operator--() will be called 0 times, for unbundled instructions).
Increment/decrement just works.
- Make the ilist_sentinel<MachineInstr> *always* store that it's the
sentinel (instead of just in asserts mode). Then the bundle iterator
can sniff the sentinel bit in operator++().

I initially tried implementing the end() option as part of this commit,
but updating iterator/reverse_iterator conversion call sites was
error-prone. I have a WIP series of patches that implements the final
option.

llvm-svn: 280032

show more ...

[StatepointsForGC] Rematerialize in the presence of PHIs

Summary:
While walking the use chain for identifying rematerializable values in RS4GC,
add the case where the current value and base value ar

[StatepointsForGC] Rematerialize in the presence of PHIs

Summary:
While walking the use chain for identifying rematerializable values in RS4GC,
add the case where the current value and base value are the same PHI nodes.

This will aid rematerialization of geps and casts instead of relocating.

Reviewers: sanjoy, reames, igor

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D23920

llvm-svn: 279975

show more ...

Use the range variant of remove_if instead of unpacking begin/end

No functionality change is intended.

llvm-svn: 278475

Use the range variant of find instead of unpacking begin/end

If the result of the find is only used to compare against end(), just
use is_contained instead.

No functionality change is intended.

ll

Use the range variant of find instead of unpacking begin/end

If the result of the find is only used to compare against end(), just
use is_contained instead.

No functionality change is intended.

llvm-svn: 278433

show more ...

Use range algorithms instead of unpacking begin/end

No functionality change is intended.

llvm-svn: 278417

Apply clang-tidy's modernize-loop-convert to most of lib/Transforms.

Only minor manual fixes. No functionality change intended.

llvm-svn: 273808

[RSForGC] Appease MSVC

llvm-svn: 273805

[RSForGC] Bring the BDVState struct up to code; NFC

llvm-svn: 273800

[RSForGC] Bring computeLiveInValues up to code; NFC

llvm-svn: 273799

[RSForGC] Bring computeLiveOutSeed up to code; NFC

llvm-svn: 273798

[RSForGC] Bring computeLiveInValues up to code; NFC

llvm-svn: 273797

[RSForGC] Bring recomputeLiveInValues up to code; NFC

llvm-svn: 273796

[RSForGC] Bring containsGCPtrType, isGCPointerType up to code; NFC

llvm-svn: 273795

[RSForGC] Bring analyzeParsePointLiveness up to code; NFC

llvm-svn: 273794

[RSForGC] Bring meetBDVStateImpl up to code; NFC

llvm-svn: 273793

[RSForGC] Get rid of the unnecessary MeetBDVStates struct; NFC

All of its implementation is in just one function.

llvm-svn: 273792

[RSForGC] Bring findBasePointer up to code; NFC

Name-casing and minor style changes to bring the function up to the LLVM
coding style.

llvm-svn: 273791

Fix unused variable warning by folding the temporary into the debug statement.

llvm-svn: 273523

[RS4GC] Use StringRef; NFC

Spotted during random inspection.

llvm-svn: 273512

Avoid duplicated map lookups. No functionality change intended.

llvm-svn: 273030

[RS4GC] Pass CallSite by value instead of const ref; NFC

That's the idiomatic LLVM pattern.

llvm-svn: 272981

[RewriteStatepointsForGC] All constant should have null base pointer

Currently we consider that each constant has itself as a base value. I.e "base(const) = const".
This introduces couple of proble

[RewriteStatepointsForGC] All constant should have null base pointer

Currently we consider that each constant has itself as a base value. I.e "base(const) = const".
This introduces couple of problems when we are trying to avoid reporting constants in statepoint live sets:

1. When querying "base( phi(const1, const2) )" we will get "phi(const1, const2)" as a base pointer. Since
it's not a constant we will record it in a stack map. However on practice we don't want this to happen
(constant are never relocated).
2. base( phi(const, gc ptr) ) = phi( const, base(gc ptr) ). This particular case imposes challenge on our
runtime - we don't expect to see constant base pointers other than null. This problems can be avoided
by treating all constant as if they were derived from null pointer base. I.e in a first case we will
not include constant pointer in a stack map at all. In a second case we will get "phi(null, base(gc ptr))"
as a base pointer which is a lot more convenient.

Differential Revision: http://reviews.llvm.org/D20584

llvm-svn: 270993

show more ...