ICS 142 Klefstad

Code Optimization

Outline Requirements for Optimizations Two Approaches to Optimization Source Level Optimizations Some Optimization Techniques Symbolic Debugging of Optimized Code Global Data-Flow Analysis

Requirements for Optimizations

must preserve the meaning of a program
- side-effects and aliases may prevent some optimizations
- EG
```
INT i, *ip = &i;
i = 10; *ip = 20; printf ("%d\n", i); 
```
must provide a measurable improvement in code
- IE the benefits must justify the cost (in time and space)
improvement must be worth the implementation effort

Two Optimization Philosophies

C allows the user to specify algorithms efficiently
- EG registers, pointer arithmetic, macros, large set of operators
- programmer may do many optimizations
- compiler may also do some optimizations
- programmer must be aware of micro-optimizations
- allows run-time profiling followed by hand-optimizations
Ada/Pascal allow the programmer to specify algorithms abstractly
- programmer need not/cannot deal with micro-optimizations
- compiler may do some optimizations, at mercy of implementer
- compiler must guess which portions of code to optimize
- usually optimize inner loops to get largest improvements

Source Level Optimizations

loop unrolling, especially important for pipelined architectures
a call graph is useful for performing certain optimizations:
- it detects which subroutines may call other subroutines
- main program is the root
- cycles indicate recursion (direct or indirect)
static allocation of activation records
- just like overlaying declare-block activation records
- address is known for each local variable reference
- no need to reference local variable as contents (variable offset + frame pointer)
eliminating recursion
- convert simple recursion to looping

inline substitution of subprogram bodies
- eliminates subprogram call overhead
- not the same as macro expansion
  - parameter passing?
  - referencing environment?
- good candidates for inline expansion
  - subprograms with only 1 or 2 callers
  - small subprograms (body size <= call + return sequence)
interprocedural data flow analysis
- local analysis assumes subexpression values in registers are killed on each subprogram call
- interprocedural data flow analysis can determine which are really killed

Some Optimization Concerns

instruction selection
register allocation
evaluation orders
common subexpression elimination
copy propagation
constant propagation

algebraic transformations
- constant folding, EG ~((UNSIGNED) 0)>>1
- arithmetic transformations
  - x + 0 == 0 + x == x
  - x * 1 == 1 * x == x
  - x ** 2 == x * x
  - x * 2 == x << 1 == x + x
- logical transformations (short-circuiting may disallow some)
  - true && x == x && true == x
  - false && x == x && false == false
  - false || x == x || false == x
  - true || x == x || true == true
loop optimizations
- code motion, loop-invariant removal
- induction-variable elimination
- reduction in strength

dead code elimination: EG IF (0) { ... }
reusing temporary variables
packing or unpacking data structures
Peephole Optimization
- recognize inefficient patterns in short sequences of code
- usually a small number of instructions, perhaps 2-4
  - EG
    - redundant loads and stores
      move r0, A move A, r0
    - flow of control (3 possible optimizations here)
      jump L1 L1: move a, b jump L2 move a, c L2: jump L3

Symbolic Debugging of Optimized Code

due to code motion certain variables may not be assigned when the user expects
we can keep the DAGs around at run-time, (encoded as symbol table info used by the debugger)
the node labels tell us which variables have the value represented by the evaluation of that node
inline subprograms or macros can cause problems too

Introduction to Global Data-Flow Analysis

allows the following optimizations
- elimination of global common subexpressions
- copy propagation
- detection of loop-invariant computations and subsequent code motion
- elimination of induction variables
point
- the places between two adjacent statements
path
- a sequence of points through which control might flow sequentially
kill a value in a variable if we assign the variable

reaching definitions
- a definition reaches a point
  - there is a control flow path from that definition to that point
  - and, if it is not killed along THAT path
- a conservative estimate of the life-time of a definition
data-flow equations for structured programs
- see figure 10.21 on page 612 of the text
- may have circular dependencies (which make them difficult to solve)
use-definition chains
- computed for each variable use
- a set of definitions reaching the point before that use
- includes all reaching definitions along ALL paths to that point
- may include multiple definitions for the same variable

reducible flow graphs
- basically, no jumps to the middle of loops
- includes flow graphs from practical programs without gotos
- some with restricted use of gotos are reducible (EG, Ada goto)
- data flow equations may be solved using syntax-directed approach
data-flow equations for general flow graphs
- can be solved by iterative method
- general iterative solution (section 10.6, and 10.10)