15 Mar 2005 01:41:09 -0500

Related articles |
---|

Question about Optimistic Register Coalescing weimingxx@gmail.com (weimingxx@gmail.com) (2005-03-15) |

From: | "weimingxx@gmail.com" <weimingxx@gmail.com> |

Newsgroups: | comp.compilers |

Date: | 15 Mar 2005 01:41:09 -0500 |

Organization: | http://groups.google.com |

Keywords: | registers, optimize |

Posted-Date: | 15 Mar 2005 01:41:09 EST |

I am now doing some work about register allocation. I have read the

article "Optimistic Register Coalescing".

ACM Transactions on Programming Languages and Systems (TOPLAS) archive,

Volume 26 , Issue 4 (July 2004)

Pages: 735 - 765

Year of Publication: 2004

ISSN:0164-0925

I have confused something,

1. Because of coalesing or simplify nodes, all nodes' degree have been

changed, according to the formula of computing the spill cost, if we

have to count spill cost of all nodes again? If we undo one of

coalesced node, if we have to count it again because we still got some

coalesced node and degree of nodes changed again?

2. In the article section 4.2.3, it was written they tested the

colorability of every combination of the colorable primitive nodes. in

the example, (section 4.1),"assume that the split x is colorable and is

associated with the minimum cost( the cost of spilling y and z is the

minimum", suppose the spill cost x, y, z are 10, 3, 4 respectively, if

we compare spill cost 10 with 7 (sum of 3 and 4), or we count the

coalesced node yz and x again with current degree(because the node x

degree is changed, so I think we should count spill cost for x again)?

then we compare x and yz(maybe x is 8, yz is 6) and choose x as

colorable split.

3. another example, if the spill cost of x, y ,z are 5, 6, 7

respectively, assume all of them can be colored individually, we test

all combination of splits, x, y, z ,xy, yz, zx, xyz if the can be

colorable with a given color, which one should be colorable? In section

4.2.3, they had a heuristic solution because the first way is time

exhausted. So Could you please give me a detail example with two

solutions (time exhausted and heuristic solution)?

I would appreciate your help.

Thank you again!

email: weimingxx@gmail.com

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.