Lesson 10--Register Allocation

Question 1

True or False: Register allocation is a must for CISC

Answer 1

False. All operands are in memory and there are long instructions to retrieve and use them.

Question 2

True or False: Register allocation is a must for RISC

Answer 2

True

Question 3

True or False: Register allocation is a must for VLIW

Answer 3

True

Question 4

True or False: Register allocation saves energy on embedded processors

Answer 4

True. It reduces memory accesses, which are energy hogs.

Question 5

Register allocation

Answer 5

Determines which of the values should be in registers at each execution point

Question 6

Register assignment

Answer 6

Determines which register should be used by each allocated value

Question 7

Goal of register allocation

Answer 7

To minimize the traffic between the CPU and the memory hierarchy

Question 8

Three parameters that are positively impacted by better register allocation

Answer 8

Speed
Code size
energy efficiency

Question 9

gen

Answer 9

variable is newly defined

Question 10

kill

Answer 10

old value is no longer accessible

Question 11

def

Answer 11

on the left hand side

Question 12

use

Answer 12

on the right hand side

Question 13

live

Answer 13

variable will be used again

Question 14

dead

Answer 14

variable will never be used again

Question 15

web

Answer 15

The live range for each value

Question 16

interference

Answer 16

overlapping ranges

Question 17

spill cost

Answer 17

how many definitions and uses are in a range

Question 18

allocation

Answer 18

which webs get a register

Question 19

spilling and splitting

Answer 19

Split webs if needed

Question 20

def-use (DU) chains

Answer 20

­–connects definition to all reachable uses
­–conditions for putting defs and uses into the same web
­–definition and all reachable uses must be part of the same web
­–all defs that reach the same use must be in the same web

Question 21

Graph Coloring Heuristics

Answer 21

–Remove nodes that have degree < N
­–push the removed nodes onto the stack
­–When all the remaining nodes have a degree >= N
­–Find the node with the least spill cost and push it onto the stack
­–What we are doing is ordering the nodes on the stack in the order of their spill cost. The
top of the stack will have the highest spill cost, the bottom of the stack will have the least
spill cost. The nodes with the highest spill costs will get registers.
­–When all the list of nodes is empty, it is time to start coloring.

Question 22

Options when coloring fails

Answer 22

1. Pick a web and allocate the value in memory. All the definitions go to memory, all uses come from memory.
2. Split the web into multiple webs.

Question 23

Cost

Answer 23

of executions * cost of instruction