Work Note 8, DM546, Spring 2018
Lecture March 2
-
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 2
-
Finish left-over exercises from earlier work notes.
-
Consider C-programs as you (or maybe a less competent friend) write them.
Can you identify local patterns in statements or a sequence of
statements that one could improve? That is, some patterns that
have enough structure and commonality that one could write a
program to optimize. Try to come up with at least a few suggestions.
Are there any possible dangers (in terms of the speed of the final
executable) in writing a high-level
optimizer for C-programs where simple but inefficient code
is replaced by more complicated but also more efficient code?
-
Most often when we say "optimization", we are referring to time.
When is space an interesting target?
Consider possible targets for optimization other than
(directly) time and space and describe plausible goals.
-
Take a look at code generated by gcc (compile with gcc -S)
for a few well-known and relatively short source files,
such as factorial, for instance.
Try to investigate the effect of the three options
-O1, -O2, and -O3
with regards to code optimization.
-
Assume that you have (structured) Intel Pentium code
in a linked list of structs. Thus, entries are typically op-fields,
parameter-fields, and possibly a pointer in connection with
jump-instructions (therefore the term "structured").
Sketch the C-code which recognizes assembler code
of the nature "x = x + 1" and replaces it by the
appropriate "inc x" equivalent code.
Local pattern-based adjustments such as this one are referred
to as peep-hole optimization.
-
Can you think of other patterns one could handle in a peep-hole optimizer?