|Question about Optimistic Register Coalescing firstname.lastname@example.org (email@example.com) (2005-03-15)|
|Date:||15 Mar 2005 01:41:09 -0500|
|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
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
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!
Return to the
Search the comp.compilers archives again.