Compilers – Code Optimization

Pages: 1 2 3 4 5 6

High-level optimizations III

Tail call optimizations

		`To iterate is human, to recurse divine’ – L. Peter Deutsch

As I said earlier subroutines are dealt with by pushing the return address onto the stack and popping it off at the end of the subroutine. This creates an interesting possibility. Consider the code:-

   sub fred {
      jim;
      sheila;
      }

`jim’ and `sheila’ are calls to other subroutines. Also `sheila’ is the last piece of code before the end of the subroutine, a `tail call’. Normally the address of the instruction after `sheila’ (the first instruction of the epilogue) would be placed on the stack then sheila would be called. As sheila finishes it will pop the return address of the stack and use it, now returning to the end of `fred’, the address fred was given will be popped off the stack. A trick can be done here, sheila can be jumped to without recording anything on the stack, if this is done the return by popping the stack will still work right. At the end of sheila the return address of fred will be at the top of the stack.

Okay what’s the point? Calls aren’t that expensive. A `self-recursive call’ is a subroutine calling itself. A `self tail call’ is a recursive call and the last call in a routine. A special optimization can be implemented in this case (which isn’t that rare), the call can be replaced by a straight jump. Because the call is executed many times in this situation it is a profitable trick. This is an interesting optimization because it has effects that ripple far from the reduced call overhead. If any arguments are passed then once optimized the activation record isn’t rebuilt each time. Imagine a recursive routine that is called 1 billion times and has one integer in its activation record, it’ll use over 4GB of memory, whereas after the optimization has been done it will use 4 bytes. So the routine will crash or seg-fault without the optimization and work with it. As you may imagine this can’t be used in portable code. Lisps have had this optimization for decades and lisp programmers often rely on it, a very useful state of affairs.

e.g.

   foo()
   {
      if (l = "X") {
         bar();
         foo();
      }
   }

becomes

   foo()
   {
      L: if (l = "X") {
         bar();
         goto L;
      }
   }

Loop optimizations

Very commonly most of the work of a program is done in one or two small loops that are iterated huge numbers of times. The following high-level optimizations are targeted specifically at loops because of the large amount of work they do. In mathematical code the situation I mention above where most of the work is done by a loop is almost universal, for this reason loop optimizations are the most important. Compilers for supercomputers and number-crunching clusters spend most of their time and have most of their complexity in performing loop optimizations. Loops often access arrays and many loop optimizations rely on this fact. Programmers know the importance of loops and only pay attention only to their code when evaluating algorithms.

Loop invariant hoisting

This optimization is often referred to as “strength reduction” although properly strength reduction is a more general term. Anyway, the operations in the body of a loop are done many more times than those outside the loop, so it’s better to do as much as possible outside the loop. Loop invariant hoisting moves loop invariant calculations out of the loop. Advanced implementations work out whether it is better (or possible) to move the invariant part out to the beginning of the loop or the end.


Pages: « Prev   1 2 3 4 5 6   Next »

Discuss (15 comments)