TY - GEN

T1 - Register allocation in structured programs

AU - Kannan, Sampath

AU - Proebsting, Todd

N1 - Funding Information:
in part by NSF Grant

PY - 1995/1/22

Y1 - 1995/1/22

N2 - In this paper we look at the register allocation problem. In the literature this problem is frequently reduced to the general graph coloring problem and the solutions to the problem are obtained from graph coloring heuristics. Hence, no algorithm with a good performance guarantee is known. Here we show that when attention is restricted to structured programs which we define to be programs whose control-flow graphs are series-parallel, there is an efficient algorithm that produces a solution which is within a factor of 2 of the optimal solution. We note that even with the above restriction the resulting coloring problem is NP-complete. We also consider how to delete a minimum number of edges from arbitrary control-flow graphs to make them series-parallel and apply our algorithm. We show that this problem is Max SNP hard. However, we define the notion of an approximate articulation point and give efficient algorithms to find approximate articulation points. We present a heuristic for the edge deletion problem based on this notion which seems to work well when the given graph is close to series-parallel.

AB - In this paper we look at the register allocation problem. In the literature this problem is frequently reduced to the general graph coloring problem and the solutions to the problem are obtained from graph coloring heuristics. Hence, no algorithm with a good performance guarantee is known. Here we show that when attention is restricted to structured programs which we define to be programs whose control-flow graphs are series-parallel, there is an efficient algorithm that produces a solution which is within a factor of 2 of the optimal solution. We note that even with the above restriction the resulting coloring problem is NP-complete. We also consider how to delete a minimum number of edges from arbitrary control-flow graphs to make them series-parallel and apply our algorithm. We show that this problem is Max SNP hard. However, we define the notion of an approximate articulation point and give efficient algorithms to find approximate articulation points. We present a heuristic for the edge deletion problem based on this notion which seems to work well when the given graph is close to series-parallel.

UR - http://www.scopus.com/inward/record.url?scp=84912068039&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84912068039&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84912068039

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 360

EP - 368

BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

PB - Association for Computing Machinery

T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

Y2 - 22 January 1995 through 24 January 1995

ER -