Unit 9: Code Optimization
Simply compiling and executing a program is not enough to get the most out of your code. It is the optimization process that allows your code to run as effectively and efficiently as possible. In this unit, we will first take a look at optimization, learning what it is and why we are interested in it. Next, we will review different optimization categories, including Peephole, Local, Loop, Language Dependent, and Machine Dependent. We will conclude with a discussion of different optimization techniques. By the end of this unit, you will have a basic understanding of a wide range of optimization techniques and how they improve the effectiveness of your program.
Completing this unit should take you approximately 22 hours.
Upon successful completion of this unit, you will be able to:
- Define optimization.
- Describe approaches and give examples of local optimizations.
- Describe approaches and give examples of global optimizations.
- Describe approaches and give examples of code optimizations.
9.1: The What and Why of Code Optimizations
Read Chapter 11 through section 11.1.
9.2: Fundamentals of Code Optimization
Read slides 1 through 8.
9.3: Local Intermediate Code Optimizations: Definitions and Examples
Read pages 1 through 10 of the handout, and the associated lecture notes, which are an excellent unified formal treatment of the topic.
9.4: Global Intermediate Code Optimizations: Definitions and Examples
Read these slides. Global optimization uses forward analysis (e.g., constant propagation), which moves information forward, and backward analysis (e.g., liveness), which moves information backward. Note slide 5, which states that dynamic properties of a program are undecidable.
Read these pages, which cover the material in more detail and present it in a unified formal way using semilattices.
Read these slides. They repeat some of the material from above readings. However, they are an excellent review, and go into detail on the formalism that underlies global optimizations.
9.5: Code Optimization
- Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Notes for Lectures 13-18" URL
- Introduction to code optimization: instruction scheduling
- Loop optimization: instruction scheduling
- More loop optimizations
- Register allocation
- Parallelization
- Memory optimization
Read these slides. If you find a part that is helpful and adds to your knowledge of optimizations, read it. These slides repeat some of the material from above readings. However, they are an excellent review, concise and clear, and reinforce key points. They also provide additional examples.
9.6: Verification and Validation of Code Optimization
Do Exercise 11.1 parts a) and b) on page 254.
This exercise will give you some practice with code optimization and is based on Chapter 11, which covers analysis and optimization. The exercise uses common subexpression elimination as an example of optimization. You can check your answers against the Answer Key.