Compiler Optimizations

Constant Folding

Evaluate constants at compiler time, e.g 1 + 2 -> 3

Constant Propagation

If we know the value of a variable, we can use constant folding

def main(x: int, y: Int): Int = {
    x + x // Cannot propagate
    
    x = 1
    x + x // Can propagate
    
    x = y
    x + x // Cannot propagate
}

Common Subexpression Elimination

If you call a function twice, just memoize its value.

This doesn't always work. For example:

def f(x: Int): Int = {
    println(x)
    
    x * 2
}

def main(a: Int, b: Int): Int = {
    f(a) + f(a)
}

Since f has side effects (printing to stdout), we need to run the function twice.

Dead Code Elimination

See Simplifying Conditionals

We can determine if a block of code never runs

E.g

def main(x: Int, y: Int): Int = {
    var releaseVersion: Int;

    releaseVersion = 0;

    if (releaseVersion == 1) {
        x = 1; // DEAD CODE
    } else {
        x * y
    }
}

Since releaseVersion == 1 will never be true, we can simplify this code:

def main(x: Int, y: Int): Int = {
    x * y
}

Register Allocation

Peephole Optimization

Simplify sequential instructions, e.g

ADD(Reg(3), Reg(1), Reg(0))
ADD(Reg(7), Reg(3), Reg(0))

you can optimize to

ADD(Reg(7), Reg(1), Reg(0))

Inlining Functions

Replace functional call with function body

def foo(x: Int): Int = {
    x + x
}
def main(a: Int, b: Int): Int = {
    foo(a)
}

can be optimized to:

def main(a: Int, b: Int): Int = {
    a + a
}