Compiler optimization examples

Question

I'd like to see (good) examples of optimizations performed by compilers (static and JIT). Why?

• To learn what we don't have to optimize ourselves (often leading to better code)
• To be amazed

Answer 1

When I wrote the compiler for my implementation of ECMAScript I noticed that I could not perform recursion to a depth that was greater than 3000 calls. To me this was unacceptable so after a bit of experimentation I came up with the idea of replacing the return value with the arguments that were passed recursively. With this in place recursion became a viable option when writing code for my implementation.

public IDynamic Call(IDynamic thisObject, Args args)
{
    var engine = Engine.Instance.Value; // Thread Local
    var lexicalEnviroment = Scope.NewDeclarativeEnviroment();
    var thisBinding = thisObject ?? engine.GlobalEnviroment.GlobalObject;
    var newContext = new ExecutionContext(lexicalEnviroment, thisBinding);
    var result = default(IDynamic);
    var currentArgs = args;

    engine.EnterContext(newContext);
    do
    {
        result = Function.Value(newContext, currentArgs);
        currentArgs = result as Args;
    } while (currentArgs != null);
    engine.LeaveContext();

    return result;
}

NOTE

I don't believe that you would ever see this technique used in a professional context. Given the current code a strong relationship is implied (run-time -> compiler) and there really shouldn't be. I would expect any proper compiler would perform tail-call optimizations on the code itself.

Here is a proper example of tail-call optimization:

F#

let rec inner value input state =
    let r = p input state
    if r.IsEmpty then 
        value, state, input 
    else 
        inner (value @ [r.Head.Value]) r.Head.Input r.Head.State

Reflected CIL as C#

internal static Tuple<FSharpList<a>, b, LazyList<c>> inner@242<a, b, c>(FSharpFunc<LazyList<c>, FSharpFunc<b, FSharpList<Result<a, b, c>>>> p, FSharpList<a> value, LazyList<c> input, b state)
{
    while (true)
    {
        FSharpList<Result<a, b, c>> r = FSharpFunc<LazyList<c>, b>.InvokeFast<FSharpList<Result<a, b, c>>>(p, input, state);
        if (r.get_TailOrNull() == null)
        {
            return new Tuple<FSharpList<a>, b, LazyList<c>>(value, state, input);
        }
        state = r.Head.state;
        input = r.Head.input;
        value = Operators.op_Append<a>(value, FSharpList<a>.Cons(r.Head.value, FSharpList<a>.get_Empty()));
        p = p;
    }
}

Notice how the compiler is simply reusing the same stack frame in a while loop. This is very similar to what I implemented but without the unnecessary friendliness between the compiler and the run-time.

Answer 2

Someone once tried to examine optimizers in C code. They ran this code through various C compilers with different levels of optimization:

 main() {
      long i;
      double x;

      for( i=0; i<100000; i++) {
           x = sin(.3)
      }

      printf("%ld\n", i);
 }

With gcc, the code took about 20 seconds (that was in the age of the 486). With gcc -O, it took so little time, they couldn't measure it anymore. What had happened?

First the compiler noticed that x wasn't used anywhere, so it removed that:

 main() {
      long i;

      for( i=0; i<100000; i++) {
           sin(.3)
      }

      printf("%ld\n", i);
 }

sin() is a function without side effects, so we don't need to call it if no one cares for the result:

 main() {
      long i;

      for( i=0; i<100000; i++) {
      }

      printf("%ld\n", i);
 }

The loop is empty, so we can remove that, too:

 main() {
      long i = 100000;
      printf("%ld\n", i);
 }

A classical example of removing unused code.