Logo F# Compiler Guide

Code Optimizations

Code optimizations are in Compiler/Optimize/*.

Some of the optimizations performed in Optimizer.fs are:

In DetupleArgs.fs, tuples at call sites are eliminated if possible. Concretely, functions that accept a tuple at all call sites are replaced by functions that accept each of the tuple's arguments individually. This may require inlining to activate.

Considering the following example:

let max3 t =
    let (x, y, z) = t
    max x (max y z)

max3 (1, 2, 3)

The max3 function gets rewritten to simply accept three arguments, and depending on how it gets called it will either get inlined at the call site or called with 3 arguments instead of a new tuple. In either case, the tuple allocation is eliminated.

However, sometimes this optimization is not applied unless a function is marked inline. Consider a more complicated case:

let rec runWithTuple t offset times =
    let offsetValues x y z offset =
        (x + offset, y + offset, z + offset)
    if times <= 0 then
        t
    else
        let (x, y, z) = t
        let r = offsetValues x y z offset
        runWithTuple r offset (times - 1)

The inner function offsetValues will allocate a new tuple when called. However, if offsetValues is marked as inline then it will no longer allocate a tuple.

Currently, these optimizations are not applied to struct tuples or explicit ValueTuples passed to a function. In most cases, this doesn't matter because the handling of ValueTuple is well-optimized and may be erased at runtime. However, in the previous runWithTuple function, the overhead of allocating a ValueTuple each call ends up being higher than the previous example with inline applied to offsetValues. This may be addressed in the future.

In InnerLambdasToTopLevelFuncs.fs, inner functions and lambdas are analyzed and, if possible, rewritten into separate methods that do not require an FSharpFunc allocation.

Consider the following implementation of sumBy on an F# list:

let sumBy f xs =
    let rec loop xs acc =
        match xs with
        | [] -> acc
        | x :: t -> loop t (f x + acc)
    loop xs 0

The inner loop function is emitted as a separate static method named loop@2 and incurs no overhead involved with allocating an FSharpFunc at runtime.

In LowerCalls.fs:

In LowerSequences.fs:

Potential future optimizations: Better Inlining

Consider the following example:

let inline f k = (fun x -> k (x + 1))
let inline g k = (fun x -> k (x + 2))

let res = (f << g) id 1 // 4

Intermediate values that inherit from FSharpFunc are allocated at the call set of res to support function composition, even if the functions are marked as inline. Currently, if this overhead needs removal, you need to rewrite the code to be more like this:

let f x = x + 1
let g x = x + 2

let res = id 1 |> g |> f // 4

The downside of course being that the id function can't propagate to composed functions, meaning the code is now different despite yielding the same result.

More generally, any time a first-order function is passed as an argument to a second-order function, the first-order function is not inlined even if everything is marked as inline. This results in a performance penalty.

Optimization phases

OptimizeInputs.fs (ApplyAllOptimizations) runs these phases on each implementation file, in order:

  1. firstLoop: Optimizer.fs. Only this pass produces the cross-module optimization data saved for other assemblies.
  2. lowerRuntimeAsync: LowerRuntimeAsync.fs, see Runtime-async optimizations.
  3. lowerLocalMutables: LowerLocalMutables.fs turns mutable locals captured by closures into reference cells.
  4. ExtraLoop: Optimizer.fs again, only with --extraoptimizationloops:n for n > 0.
  5. Detuple: DetupleArgs.fs, only when optimizing.
  6. InnerLambdasToToplevelFuncs: InnerLambdasToTopLevelFuncs.fs, only when optimizing.
  7. LowerCalls: LowerCalls.fs.
  8. FinalSimplify: Optimizer.fs again, only when optimizing.

Sequence expressions, resumable state machines, list and array comprehensions, and runtime-async sequences are lowered later, during code generation in IlxGen.fs.

Runtime-async optimizations

Runtime async adds rewrites that keep suspensions inside the runtime-async method they belong to. They run only in a runtime-async context or in the lowerRuntimeAsync phase, never on ordinary code; a new rewrite should keep that boundary. runtime-async.md describes each rewrite in detail.

Terms

Rewrites

The optimizer also changes some ordinary behavior for runtime-async code:

A suspension that none of these can move into a runtime-async method is reported as FS3918.

val max3: 'a * 'a * 'a -> 'a (requires comparison)
val t: 'a * 'a * 'a (requires comparison)
val x: 'a (requires comparison)
val y: 'a (requires comparison)
val z: 'a (requires comparison)
val max: e1: 'T -> e2: 'T -> 'T (requires comparison)
val runWithTuple:
    int *
    int *
    int ->
    offset: int ->
    times: int ->
        int * int * int
val t: int * int * int
val offset: int
val times: int
val offsetValues: x: int -> y: int -> z: int -> offset: int -> int * int * int
val x: int
val y: int
val z: int
val r: int * int * int
val sumBy: f: ('a -> int) -> xs: 'a list -> int
val f: ('a -> int)
val xs: 'a list
val loop: xs: 'a list -> acc: int -> int
val acc: int
val x: 'a
val t: 'a list
val f: k: (int -> 'a) -> x: int -> 'a
val k: (int -> 'a)
val g: k: (int -> 'a) -> x: int -> 'a
val res: int
val id: x: 'T -> 'T
val f: x: int -> int
val g: x: int -> int

Type something to start searching.