Register allocation by priority-based coloring
Frederick Chow, John LeRoy Hennessy · 1984
The classic problem of global register allocation is treated in a heuristic and practical manner by adopting the notion of priorities in node-coloring. The assignment of priorities is based on estimates of the benefits that can be derived from allocating individual quantities in registers. Using the priorities, the exponential coloring process can be made to run in linear time. Since the costs involved in register allocation are taken into account, the algorithm does not over-allocate. The algorithm can be parameterized to cater to different fetch characteristics and register configurations among machines. Measurements indicate that the register allocation scheme is effective on a number of target machines. The results confirm that, using priority-based coloring, global register allocation can be performed practically and efficiently.
Cited by 220 works. doi:10.1145/502874.502896
Authors
References
- Register allocation & spilling via graph coloring
- Register allocation & spilling via graph coloring
- On programming : an interim report on the SETL Project
- Review of On programming
- A portable machine-independent global optimizer--design and measurements
- Register allocation via usage counts
- Machine-independent PASCAL code optimization
- Register allocation and spilling via graph coloring
- Register Allocation in Optimizing Compilers
- Machine-independent register allocation