# Question about Optimistic Register Coalescing

## "weimingxx@gmail.com" <weimingxx@gmail.com>15 Mar 2005 01:41:09 -0500

From comp.compilers

Related articles
Question about Optimistic Register Coalescing weimingxx@gmail.com (weimingxx@gmail.com) (2005-03-15)
| List of all articles for this month |

 From: "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)?