17 Dec 1997 14:12:10 -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: | Paul Haahr <haahr@netcom.com> |

Newsgroups: | comp.compilers |

Date: | 17 Dec 1997 14:12:10 -0500 |

Organization: | Compilers Central |

Keywords: | optimize, analysis, question |

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?

Thanks,

Paul

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.