Class 38: Additional Improvement Techniques

Held Wednesday, May 2, 2001

Summary

Today we continue our study of optimization with an extended example.

Overview

• Improvement, reviewed
• Loop optimization
• An example

Improvement, Continued

• I've said a few times that I prefer the term code improvement to code optimization. Why?
  • ``Optimize'' implies ``optimal'' as in ``you can't be any better than this''.
  • Few ``optimizations'' are guaranteed to produce unimprovable code because it may always be possible to choose a better program
• Code improvement can typically be done at many stages in a program:
  • Source code
    • You can choose better algorithms.
    • You can identify slower parts of the program and recode them.
    • You can turn tail-recursion into iteration (if your compiler doesn't do it for you).
    • You can choose better data types _ ...
  • Intermediate code
    • Many of the transformations we've talked about so far
  • Code generation
    • Select registers well
    • Select translations well
  • Target code
    • "Peephole" improvement (look at a few lines at a time)
• Algorithmic improvements are often among the most important. For some problems, the improvement in algorithms outpaced the improvements in processors.
  • You were better off running the newer algorithm on older equipment than running the older algorithm on newer equipment.
• It's also worthwhile thinking about the data. For example, integer calculations are typically much faster than real calculations.
• It's also worth thinking about the arrangement of arrays. In most systems, one of the following two nested loops will run much faster for very large arrays. Can you tell why?

  for i := 1 to N do
    for j := 1 to N do
      B[i,j] := A[i,j];
  
  for j := 1 to N do
    for i := 1 to N do
      B[i,j] := A[i,j]
  

Loop Optimizations

• We typically want to spend the most effort where it will make the most difference.
  • The typical observation is that 10% of the code does 90% of the work.
  • At the source level, we can profile the code to figure out where most of the work goes on and then carefully recode that section.
  • At the intermediate level, we can identify loops and optimize there.
• How do we identify loops? By looking at the flow graph.
• What optimizations are available?
• Code movement: If we can get statements out of loops, we're much better off.
• Induction variables and reduction in strength not all operations are the same (for example, multiplication may take more time than addition). At times, we can trade one for the other by observing when two variables change in lockstep.
• Consider the following sample code

  LOOP:
    add t1, $1, t1
    mul t1, $4, t2
    ...
  

• We call t1 and t2 induction variables because they change in relation to the loop and because a proof of the loop's termination will typically involve inducation on one of these variables
• Some simple analysis tells us that at every step of the loop, t1 is incremented by 1 which means that t2 is incremented by 4.
• If t1 is never used again, we can replace the code with

  LOOP:
    add t2, $4, t2
  ...
  

• Even if t1 is used again, the add is still cheaper than the multiply.

A Longer Example

• Let's look at a slightly longer program and consider how to optimize it.
• Consider the code fragment

  for i := 1 to n do
    for j := 1 to n do
      B[j,i] := A[i,j]
  

• Assumptions for translation:
  • Integers take four bytes
  • Each dimension of the array is indexed from 1..n.
  • The array is stored in row-major order. That is, if n is 3, we have the following elements in sequence A[1,1], A[1,2], A[1,3], A[2,1], A[2,2], A[2,3], A[3,1], A[3,2], A[3,3].

 
  mov $1, i
NEXT_OUTER:
  je i, n END_OUTER
  mov $1, j
NEXT_INNER:
  je   j,   n,   END_INNER
  sub  i,   $1,  t1
  mul  t1,  $4,  t2
  mul  t2,  n,   t3
  sub  j,   $1,  t4
  mul  t4,  $4,  t5
  add  t3,  t5,  t6
  mov  offset(A,t6), t7
  sub  j,   $1,  t8
  mul  t8,  $4,  t9
  mul  t9,  n,   t10
  sub  i,   $1,  t11
  mul  t11, $4,  t12
  add  t10, t12, t13
  mov  t7, offset(B,t13)
  add  j, $1, j
  jump NEXT_INNER
END_INNER:
  add  i, $1, i
  jump NEXT_OUTER
END_OUTER:
  ...