Sat, 5 Oct 91 18:52:02 -0500

Related articles |
---|

Looking for conflict graph generators johnsson@cs.chalmers.se (Thomas Johnsson) (1991-09-26) |

Re: Looking for conflict graph generators preston@dawn.rice.edu (1991-09-27) |

Re: Looking for conflict graph generators hankd@ecn.purdue.edu (1991-10-05) |

Re: Looking for conflict graph generators preston@dawn.rice.edu (1991-10-06) |

Newsgroups: | comp.compilers |

From: | hankd@ecn.purdue.edu (Hank Dietz) |

Summary: | Easy to do, if you know max live |

Keywords: | optimize, theory |

Organization: | Compilers Central |

References: | 91-09-076 91-09-086 |

Date: | Sat, 5 Oct 91 18:52:02 -0500 |

In article 91-09-086 preston@dawn.rice.edu (Preston Briggs) writes:

*>Thomas Johnsson <johnsson@cs.chalmers.se> writes:*

*>>I'm looking for an algorithm, or better yet, a program, which generates*

*>>conflict graphs `similar' to those obtained from a graph coloring register*

*>>allocator.*

...

*>For the purposes of register allocation, I don't much like measurements*

*>made on random graphs. Real interference graphs aren't that densely*

*>connected, but tend to require a relatively large number of colors. (Just*

*>look at the code and count the maximum liveness. You'll need at least*

*>that many colors.) Results on random graphs tend tend suggest things like*

*>"3 registers are enough to avoid spilling". Don't believe it.*

Back in 1987-1988, Chi and I did a fair amount of work in graph-based

register allocation. We wrote a simple program to generate random graphs

where the number of nodes, number of arcs, and the minimum number of

colors (i.e., max live) were independently-specified. Results:

[1] For our random graphs with known max live, optimal colorings

were nearly always found. Hence, the number of colors is

generally max live, perhaps plus 1 or 2.

[2] Max live depends not only on the program being examined, but

also on how you measure liveness. Do globals and array

elements count? Is liveness based on live values, or on live

variable names (using names is wrong, but common, and it

increases the apparent value of max live)? Further, max live

is not invariant wrt to code motions and code scheduling...

do we attempt to minimize max live?

Despite all these differences, typical max live values have

been quoted in many places, and are usually between 5 and 7.

Global compiler analysis & RISC code motions tend to increase

these numbers somewhat....

[3] Although Preston is correct that real graphs are very sparse,

for our studies using random graphs WITHOUT max live specified,

we used very large, dense, graphs.

Our result was that 10-12 registers were enough for the vast

majority of these random graphs (although Chaitin's coloring

scheme needed many more colors). I don't know where Preston

got the number 3, but it wasn't from us....

Our register allocation techniques, both our graph coloring algorithm (a

random walk) and a different scheme which directly minimizes execution

time, were discussed in:

C-H. Chi and H. G. Dietz, "Register Allocation for GaAs Computer

Systems," 1988 Hawaii International Conference on Systems Sciences,

Architecture Track, vol. 1, pp. 266-274, January 1988.

-hankd

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.