algorithm for computing the interference graph in SSA form?

Paul Haahr <haahr@netcom.com>
17 Dec 1997 14:12:10 -0500

          From comp.compilers

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)
| List of all articles for this month |

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.