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
On Sep 19, 2012, at 10:13 AM, dag at cray.com wrote:> 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 at 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. :)>> 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