Work Note 7, DM516, Spring 2010
Lecture February 25
-
Liveness analysis and register allocation.
Background material: Appel Chapters 10 and 11.
It is recommended that you first skim over the material in the book
and read in detail later based on the focus in the lecture.
Supplementary literature:
A note on lattices and fixed points
(not part of the curriculum).
Exercises March 5
-
Finish left-over exercises from the last times.
-
Appel 10.1, 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.
Last modified: Mon Feb 22 10:00:11 CET 2010
Kim Skak Larsen
(kslarsen@imada.sdu.dk)