Class 37: General Techniques

Held Monday, April 30, 2001

Summary

Today we look at some of the issues involved in the optimization of intermediate code.

Notes:

• Reminder: Wednesday is the last day to turn in your type checkers.
  • That only gives you two weeks to write your code generators.
• Mr. Stone will be visiting class this week and next to observe my teaching and your presentations.

Overview

• Why build improvable code?
• Why improve code?
• Basic analyses:
  • Basic blocks
  • Variable lifetimes and usage
• Generating better assembly
• Some common optimizations

Introduction to Code Improvement

• Since the first compiler, one of the goals of compilation is to generate code "nearly as good as that hand coded by a talented programmer."
• However, it is often better to generate less-good code on the first pass.
  • It may require less effort to generate that code.
  • An early optimization at one point may prevent optimizations at other points.
  • The original code may be more readable.
  • The original code may be easier to provie equivalent to the original program.
• While it is possible for a compiler to improve its code ``on the fly,'' as it generates code from portions of the annotated parse tree (or as it parsers the program), it is often easier to improve the code in a separate pass.
• Traditionally, code improvement is called optimization, although the code it produces is often not optimal (a true optimizer should be able to do things like pick a better algorithm :-).
• We can do improvement on intermediate code, machine code, and even source code.
  • We'll focus on intermediate code.
• These improvements can be broken down into local/peephole improvements (look at a small section of code and make it better) and more global improvements (reorder the flow of control, duplicate some code rather than do a procedure call, ...).
• Many optimizations (both local and global) require an understanding of control flow and data flow in the program.
  • So that's where we'll begin.

Flow Graphs

• In order to do most optimizations, it's important to get a sense of the control and data flow in a program. We do this by breaking the program up into so called basic blocks and edges between them.
• A basic block is a sequence of consecutive statements in which control enters only at the top and leaves only at the end. That is, you're guaranteed to execute all the instructions in the block if you enter the block.
• How to build basic blocks:
  • Identify the possible starts of basic blocks (called leaders)
  • Anything between a leader and the next leader (not including the next leader) is a basic block.
• How to identify leaders:
  • The first statement is a leader
  • The target of a branch is a leader
  • Anything immediately following a branch is a leader

Simple Dataflow Analysis

• As we've seen in our discussion of register analysis, for each ``piece of code'' (e.g., statement, series of statements, block, and group of blocks), we might consider the variables that provide values that are used in the code (uses) and those variables that have values set by the code (defines).
• It's fairly easy to specify uses and defines for individual instructions (e.g., for ADD b c a, the instruction uses b and c and defines a).
• We should then consider how uses and defines might be defined for groups of statements. We might find that we have to define variants of uses and defines to deal with the interaction of types of use.
  • Sequencing (S1; S2). What if S1 defines something S2 uses?
  • Alternation: (if E then S1 else S2). How general should we be for combining the defines? The uses?
  • Loops (while E do S).

Code Generation, Revisited

• As I suggested earlier, many of the issues for building good programs require a careful understanding of the underlying assembly language.
• It also requires some understanding of how data are currently organized
• For example, if we've been using a three-parameter add (as I like to do), there are many ways to translate that two a two-parameter add, depending on what you already have in registers.
• Different but similar code can require different numbers of cycles. For example, given variables a, b, and c, how should we implement add b c -> a
  • We can put b in a register, add to that register, and move into a.
  • We can put b and c into registers, do register addition, and move the result into a.
  • Which is faster? It depends on the relative costs of the different kinds of move and add operations.
  • If any of the values are already in registers, we can eliminate one or more of the moves.
• We'll leave such careful consideration as a future topic.

Basic Transformations

• Once we've broken the program down into blocks and thought about the relationships between blocks, we can then do some simple transformations on the program.
• Common subexpression elimination Suppose we have a series of statements like

  add y z -> x
  ...
  add y z -> a
  

  and there are no changes to y and z in the ellided code. Then we can replace the latter operation with mov x a.
  • This kind of optimization is possible between blocks, but can be more difficult. Consider the case in which we have three identical assignments in three separate blocks, two of which lead to the third. If there are no other ways to enter the third block, we can use a copy rather than a computation.
• Copy propagation Whenever we have code for the form mov x y, we can use x in place of y in subsequent statements (until x or y is updated).
• Dead-code elimination If no code reachable from a statement that defines x uses x, then we don't need to execute that statement, and can eliminate it.
  • Note that careful copy propagation may lead to dead code.
• Renaming variables We can rename all instances of a variable. This is particularly useful with temporary variables.
• Statement swapping (interchange) Given two subsequent statements, s1 and s2, if the intersection of uses(s1) and defines(s2) is empty and the intersection of uses(s2) defines(s1) is empty, then we can swap s1 and s2.
  • Why is this helpful? It can lead to other transofrmations.
• Algebraic transformations. We can rewrite some mathematical operations with more efficient code. For example, rather than multiplying by 2, we can add to itself or left shift one bit (depending on the underlying implementation of integers).