6 Jan 1998 22:42:51 -0500

Related articles |
---|

algorithm for computing the interference graph in SSA form? haahr@netcom.com (Paul Haahr) (1997-12-17) |

Re: algorithm for computing the interference graph in SSA form? preston@cs.rice.edu (1997-12-19) |

Re: algorithm for computing the interference graph in SSA form? cliff.click@Eng.Sun.COM (cliffc) (1997-12-23) |

Re: algorithm for computing the interference graph in SSA form? cliff.click@Eng.Sun.COM (cliffc) (1998-01-06) |

Re: algorithm for computing the interference graph in SSA form? mwolfe@pgroup.com (1998-01-08) |

Re: algorithm for computing the interference graph in SSA form? cliff.click@Eng.Sun.COM (cliffc) (1998-01-13) |

From: | cliffc <cliff.click@Eng.Sun.COM> |

Newsgroups: | comp.compilers |

Date: | 6 Jan 1998 22:42:51 -0500 |

Organization: | Sun Microsystems |

References: | 97-12-141 |

Keywords: | optimize, analysis |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.