InlineSpiller Questions

The InlineSpiller in 3.1 is quite different from the old spiller so I am
trying to slog through the code and learn a bit.

On a spill, the spiller calls traceSiblingValue. I gather that this is
supposed to find the "original" def point of a value, checking back
through copies, phis, etc. At the end we have an interval being spilled
and the original def instruction of the value.

For example:

r1 = load
...
r2 = r1
...
r3 = r2
...
   use r3

If we decide to spill r3, we call traceSiblingValue to find the original
def (the load). After traceSiblingValue we have the load instruction to
define r1 and the value number information for r3. We don't have the
value information from r2 as far as I can tell.

Is that correct? Does that information exist anywhere or is it lost
after traceSiblingValue terminates?

What does propagateSiblingValue have to do with all of this? The
comment is not very helpful:

/// propagateSiblingValue - Propagate the value in SVI to dependents if it is
/// known. Otherwise remember the dependency for later.

Thanks for your help!

                            -Dave

The InlineSpiller in 3.1 is quite different from the old spiller so I am
trying to slog through the code and learn a bit.

On a spill, the spiller calls traceSiblingValue. I gather that this is
supposed to find the "original" def point of a value, checking back
through copies, phis, etc. At the end we have an interval being spilled
and the original def instruction of the value.

For example:

r1 = load
...
r2 = r1
...
r3 = r2
...
  use r3

If we decide to spill r3, we call traceSiblingValue to find the original
def (the load). After traceSiblingValue we have the load instruction to
define r1 and the value number information for r3. We don't have the
value information from r2 as far as I can tell.

Is that correct?

Sounds right.

Does that information exist anywhere or is it lost
after traceSiblingValue terminates?

The r2 value would be cached in the SibValueInfo Deps array for the r1 value.

What does propagateSiblingValue have to do with all of this?

It's a performance optimization to handle the quadratic number of CFG edges appearing after tail-duplicating an indirectbr. It's cheap enough to search up the dominator tree until you hit a PHI, but it can be very expensive to enumerate all the PHI predecessors.

By processing PHIs in bulk and propagating the found values down to dependent value numbers, the quadratic edges are bypassed.

/jakob

Jakob Stoklund Olesen <stoklund@2pi.dk> writes:

If we decide to spill r3, we call traceSiblingValue to find the original
def (the load). After traceSiblingValue we have the load instruction to
define r1 and the value number information for r3. We don't have the
value information from r2 as far as I can tell.

Is that correct?

Sounds right.

Oh good, I'm understanding something. :slight_smile:

Does that information exist anywhere or is it lost after
traceSiblingValue terminates?

The r2 value would be cached in the SibValueInfo Deps array for the r1
value.

So if there are multiple values between r2 and r3 (r2.1, r2.2, etc.) I
would just follow the chains implied by the SibValueInfo Deps array?
Basically, I want to find all of the live ranges related to r1.

What does propagateSiblingValue have to do with all of this?

It's a performance optimization to handle the quadratic number of CFG
edges appearing after tail-duplicating an indirectbr.

Ok, so it just makes traceSiblingValue faster. Thanks for your help Jakob!

                           -Dave

It really depends on what you're trying to do.

The whole sibling value machinery is only concerned with tracking different virtual register value numbers that are known to have the same value. It doesn't really apply to anything else.

/jakob

Jakob Stoklund Olesen <stoklund@2pi.dk> writes:

Jakob Stoklund Olesen <stoklund@2pi.dk> writes:

So if there are multiple values between r2 and r3 (r2.1, r2.2, etc.) I
would just follow the chains implied by the SibValueInfo Deps array?
Basically, I want to find all of the live ranges related to r1.

It really depends on what you're trying to do.

The whole sibling value machinery is only concerned with tracking
different virtual register value numbers that are known to have the
same value. It doesn't really apply to anything else.

Are all of those sibling values guaranteed to ultimately derive from the
same def, in the sense that they can be traced through copies, phis,
etc. back to a single instruction? I'm looking at scheduling the load
in my example and I need to be able to check for conflicting stores
within relevant live ranges.

Is there a design document for the new InlineSpiller and SplitKit
somewhere?

                             -Dave

Jakob Stoklund Olesen <stoklund@2pi.dk> writes:

Jakob Stoklund Olesen <stoklund@2pi.dk> writes:

So if there are multiple values between r2 and r3 (r2.1, r2.2, etc.) I
would just follow the chains implied by the SibValueInfo Deps array?
Basically, I want to find all of the live ranges related to r1.

It really depends on what you're trying to do.

The whole sibling value machinery is only concerned with tracking
different virtual register value numbers that are known to have the
same value. It doesn't really apply to anything else.

Are all of those sibling values guaranteed to ultimately derive from the
same def, in the sense that they can be traced through copies, phis,
etc. back to a single instruction?

They are known the all come from the same value in the original live range from before live range splitting.

The defining instruction may not exists any longer. It could have been rematerialized somewhere else. It could also have been PHI.

Is there a design document for the new InlineSpiller and SplitKit
somewhere?

No.

/jakob

s/the/to/

See InlineSpiller::Original and VRM::getOriginal().

/jakob

Jakob Stoklund Olesen <stoklund@2pi.dk> writes:

Are all of those sibling values guaranteed to ultimately derive from the
same def, in the sense that they can be traced through copies, phis,
etc. back to a single instruction?

They are known the all come from the same value in the original live range from before live range splitting.

Ok, that's exactly what I need.

The defining instruction may not exists any longer. It could have been
rematerialized somewhere else. It could also have been PHI.

Ok, so in that case the traced-to VNInfo will have a def SlotIndex of
Slot_Block or something?

                               -David

VNI->isPHIDef()

Jakob Stoklund Olesen <stoklund@2pi.dk> writes:

Ok, so in that case the traced-to VNInfo will have a def SlotIndex of
Slot_Block or something?

VNI->isPHIDef()

Ah, that's what that means. Thanks a bunch for your help!

                         -David