Register Assignment is considered a very important optimization, because it can
ID: 3770402 • Letter: R
Question
Register Assignment is considered a very important optimization, because it can lead to significant execution time savings relative to other optimizations. Why is this the case?
EXPLAIN WHY YOU CHOSE YOUR ANSWER.
(a) Register assignment reduces the number of registers required for a program, and thus saves time because fewer registers are needed.
(b) By storing values in registers instead of memory, register assignment makes it possible to remove many loads and stores.
(c) Register assignment is necessary because arithmetic can only be done in registers.
(d) Good register assignment leads to better cache behavior.
(e) Nobody really knows.
Explanation / Answer
d)Good register assignment leads to better cache behavior.
Register allocation
The most frequently used variables should be kept in processor registers for fastest access. To find which variables to put in registers an interference-graph is created. Each variable is a vertex and when two variables are used at the same time (have an intersecting liverange) they have an edge between them. This graph is colored using for example Chaitin's algorithm using the same number of colors as there are registers. If the coloring fails one variable is "spilled" to memory and the coloring is retried.