Re: algorithm for computing the interference graph in SSA form?

Paul Haahr wrote:
>
> I'm looking for an algorithm to quickly compute the interference graph
> (suitable for use in register allocation) for a program in SSA form.
>
> It's probably just that I'm not clever enough, but all I've been able
> to come up with is something that looks like an iterative data flow
> analysis, which can be somewhat improved by paying attention to loops
> -- that is, the number of times you need to iterate through a basic
> block is its depth of loop nesting. (Strongly-connected components
> appear to be a useful guide here.)
>
> My instinct says that there should be a more direct way of computing
> liveness and interference if you've got the program in SSA form, but I
> haven't been able to come up with such a mechanism.
>
> Is there any literature (or folklore) on the subject that someone could
> point me at?


At least Briggs & myself go from SSA to interference graph directly.
Briggs is published; check his thesis from Rice (and he has some other
papers out, sorry no refs handy).


For me, at least, the process is very straightforward. I have a
Control Flow Graph of basic blocks; basic blocks effectively contain
tuple instructions (def/op/src1/src2). Phi functions are just another
instruction (the opcode is "Phi").


(1) Solve the classic LIVE problem any way you like. Phis need special
        handling. Normally you start with a live-out set for a block, then
        roll backwards through the block. DEF values are removed from the
        live set and USE values are added to the live set. For Phis, the
        use effectively occurs at the end of the prior block. E.g. a Phi
        instruction "X <= Phi Y Z" kills X, defines Y in the live-out set
        of the left predecessor block and defines Z in the live-out set of
        the right predecessor block.


        You can be clever and do various kinds of incremental and sparse
        things which are mostly discussed in the literature.


(2) Build the InterFerence Graph (IFG) based on this SSA-LIVE info.
        Same basic technique as with normal LIVE: roll backwards through
        the block DEFd things interference with what is currently LIVE.
        Normal USEs are added to the current LIVE set; Phi uses are not.


(3) Create a mapping from the defined values to Live RanGes (LRG).
        Simple array of LRG structures will do, assuming your defined
        values are numbered with dense-packed integers.


(4) Coalesce the Phi inputs with the Phi result, as in "copy-coalesce".
        Where you fail due to IFG conflicts you'll have to insert a Copy
        later. Basically you are acting as if you inserted a Copy before
        each Phi to move the Phi input to the same virtual register as the
        Phi result. The actual coalescing is typically done with Tarjan's
        Union-Find algorithm. Coalesce the copys in some priority order,
        usually loops inside-out, or based on some kind of frequency info.


(5) Where the input LRG to a Phi does not match the Phi LRG, go ahead
        a manifest the actual copy.


(6) You now have a 1-time aggressively coalesced IFG, and the Phis are
        all accounted for. Coalescing makes a conservative approximation
        to the IFG, so the IFG is not as precise as you might like.
        Your options include:
        (A) Use the IFG for allocation as-is. Faster, less accurate.
        (B) Recompute LIVE and rebuild the IFG. Basically, you are no longer
        in SSA form so you can go back to using classic Briggs-Chaitin.


I typically choose (A). If the first round allocates then Happy Happy.
If not, I'll spill and have to recompute LIVE/IFG anyways.


Any comments, Register-Allocation-Gurus?


Cliff


--
Cliff Click Compiler Designer and Researcher
cliffc at acm.org JavaSoft
(408) 863-3266 MS UCUP02-302
--

Return to the comp.compilers page.
Search the comp.compilers archives again.