Notes for week 13

1. Constant Folding (P) Example from P.
   1. x := 3 + 4 + 2; -> x := 11 at compile time;
   2. If Abs, Chr,Hi,Length,Lo,Odd,Ord Pred,Ptr,Round,Succ,Swap or Trunc is called on a constant, the results are computed at compile time.
   3. A[5,5] has its address computed at compile time.
   4. Example from book

      const 
      	lgth = 2;
      	amount = 3;
      
      x := lgth * amount;
      or 
      
      x := lgth *(b + c/a)*amount; {may cause problems if reordered}
      

2. Copy Propagation:(C)
   Usual problem:
   
   T := a + b;
   c := T{This is copy propagation}
3. Reduction in Strength (C under induction variables, P shift replaces multiply by power of 2)
   1. In Turbo x * c is replaced by x shl k if c = 2k
   2. In C++ strength reduction in loops
4. Substitution of In-line Code(C++) Even string functions such as strcpy can be made inline
5. Common Subexpressions C++ gives the option of global or local elimination of commons subexpressions (a + b)*(b + a)
6. Loop Optimization
   1. Loop-invariant Instructions (C++)
      1. Standard example:

         for k := 1 to 1000 do
         	c[k] := 2*(p-q)*(n-k+1)/(sqr(n) + n;
         
         

         changes to

         fact := 2*(p-q);
         denom := sqr(n) + n;
         for k := 1 to 1000 do
         	c[k] := fact*(n-k+1)/denom;
         

      2. problems might occur if there are function calls in the loop

         for k := 1 to 1000 do
         	c[k] := 2*(p-q)*fun(k)/(sqr(n) + n;

         fun might have side effect of changing the "constants" p, q, or n
      3. Nested loops:

         for i := 1 to 100 do
            for j := 1 to 100 do
               a[i,j] := b[i,j];

         in this loop, computations on i are constant inside the inner loop, so should be removed to a block preceding this inner loop.

   2. Reduction of strength(C++) replace:

      i := i + 1;{induction variable eliminated}
      offset := i*4 {multiplication replaced by addition}
      

      with
      

      offset := offset + 4;
      

   3. Loop Unrolling (Microsoft C++ not Borland)

      for i := 1 to 20 do
      begin
         for j := 1 to 2 do
            write(x[i,j]:9:3);
         writeln;
      end;

      unrolled:
      

      for i := 1 to 20 do
         writeln(x[i,1]:9:3,w[i,2]:9:3);
      

      Borland claims this is best done by the programmer!
   4. Dead Code elimination (C and P)

      if trace then
      begin
      	blah,blah,blah
      

      where trace is set as a constant.
   5. Code motion (code hoisting) similar to elimination of common expressions

      case p of
      	1: c:= a + b*d;
      	2: m := b*d -r;
      	3: f := a-b*d;
      	4: c:= q/(b*d+r);
      end;
      
      T := b*d;
      case p of
      	1: c := a+T;
      	2: m := T - r;
      etc.