Weekly Note 8, DM18, Spring 2007

Lecture March 6

• Introduction to optimization.
• Peep-hole optimization.

Exercises March 15

• Consider possible targets for optimization other than time and space and describe plausible goals.
• Try to find patterns which could be used in a high-level peep-hole optimization of for instance C-programs. Are there any possible dangers in writing a high-level optimizer for C-programs where simple but inefficient code is replaced by more complicated but also more efficient code?
• 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"). Write the C-code which recognizes assembler code of the nature "x = x + 1" and replaces it by the appropriate "inc x" equivalent code.
• Find more patterns in the categories from the lecture or from new catagories that you come up with.
• Project consultations: use any extra time to resolve questions related to part 3 with your teaching assistant.

Announcements

• Example programs and a check program are available in /home/IMADA/courses/dm18/. See the beginning of the file check.py for how to use the check program.