Note 8, DM546, fall 2019
Lecture March 5
Background material: Appel Chapter 13.
Exercises March 8
-
Appel 10.1, 10.4, 10.5.
-
Estimate the asymptotic complexity of finding a fixed point
as a function of the number of temporaries and the size of
the control flow graph (with the lecture transparencies as
the starting point).
Consider the representation of sets carefully.
Next, consider the complexity of building the conflict graph
and the complexity of coloring by simplification,
including which supporting data structures to employ.
-
Try to formulate how many temporary memory (or register)
locations one needs to evaluate an expression.
For instance
a+b-c+d only requires one,
whereas (a+b-c+d)*(e-f) requires two.
What about (a-b)*c - d/(e+f-g*h)?
In general, how can we compute how many are necessary?
-
We have seen in the lecture that it could be good to
spill vertices with a large degree. Could it have some
bad effects?
-
We have seen in the lecture that it could be good to
always use the smallest possible color. Could it have some
bad effects?