[LLVMdev] InlineSpiller Questions

[Jakob Stoklund Olesen]

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