Processing large inputs without stack overflows

The compiler accepts large inputs such as:

• Large literals, such aslet str = "a1" + "a2" + ... + "a1000"
• Large array expressions
• Large list expressions
• Long lists of sequential expressions
• Long lists of bindings, such aslet v1 = e1 in let v2 = e2 in ....
• Long sequences ofif .. then ... else expressions
• Long sequences ofmatch x with ... | ... expressions
• Combinations of these

The compiler performs constant folding for large constants so there are no costs to using them at runtime. However, this is subject to a machine's stack size when compiling, leading toStackOverflow exceptions if those constants are very large. The same can be observed for certain kinds of array, list, or sequence expressions. This appears to be more prominent when compiling on macOS because macOS has a smaller stack size.

Many sources ofStackOverflow exceptions prior to F# 4.7 when processing these kinds of constructs were resolved by processing them on the heap via continuation passing techniques. This avoids filling data on the stack and appears to have negligible effects on overall throughput or memory usage of the compiler.

There are two techniques to deal with this

1. Linearizing processing of specific input shapes, keeping stacks small
2. Using stack guards to simply temporarily move to a new thread when a certain threshold is reached.

Linearizing processing if certain inputs

Aside from array expressions, most of the previously-listed inputs are called "linear" expressions. This means that there is a single linear hole in the shape of expressions. For example:

• expr :: HOLE (list expressions or other right-linear constructions)
• expr; HOLE (sequential expressions)
• let v = expr in HOLE (let expressions)
• if expr then expr else HOLE (conditional expression)
• match expr with pat[vs] -> e1[vs] | pat2 -> HOLE (for example,match expr with Some x -> ... | None -> ...)

Processing these constructs with continuation passing is more difficult than a more "natural" approach that would use the stack.

For example, consider the following contrived example:

andremapLinearExprgcompgentmenvexprcontf=matchexprwith|Expr.Let(bind,bodyExpr,m,_)->...// tailcall for the linear positionremapLinearExprgcompgentmenvinnerbodyExpr(contf<<(funbodyExpr'->...))|Expr.Sequential(expr1,expr2,dir,spSeq,m)->...// tailcall for the linear positionremapLinearExprgcompgentmenvexpr2(contf<<(funexpr2'->...))|LinearMatchExpr(spBind,exprm,dtree,tg1,expr2,sp2,m2,ty)->...// tailcall for the linear positionremapLinearExprgcompgentmenvexpr2(contf<<(funexpr2'->...))|LinearOpExpr(op,tyargs,argsFront,argLast,m)->...// tailcall for the linear positionremapLinearExprgcompgentmenvargLast(contf<<(funargLast'->...))|_->contf(remapExprgcompgentmenve)andremapExpr(g:TcGlobals)(compgen:ValCopyFlag)(tmenv:Remap)expr=matchexprwith...|LinearOpExpr_|LinearMatchExpr_|Expr.Sequential_|Expr.Let_->remapLinearExprgcompgentmenvexpr(funx->x)

TheremapExpr operation becomes two functions,remapExpr (for non-linear cases) andremapLinearExpr (for linear cases).remapLinearExpr uses tailcalls for constructs in theHOLE positions mentioned previously, passing the result to the continuation.

Some common aspects of this style of programming are:

• The tell-tale use ofcontf (continuation function)
• The processing of the body expressione of a let-expression is tail-recursive, if the next construct is also a let-expression.
• The processing of thee2 expression of a sequential-expression is tail-recursive
• The processing of the second expression in a cons is tail-recursive

The previous example is considered incomplete, because arbitrarycombinations oflet and sequential expressions aren't going to be dealt with in a tail-recursive way. The compiler generally tries to do these combinations as well.

Stack Guards

TheStackGuard type is used to count synchronous recursive processing and move to a new thread if a limit is reached. Compilation globals are re-installed. Sample:

letTcStackGuardDepth=StackGuard.GetDepthOption"Tc"...stackGuard=StackGuard(TcMaxStackGuardDepth)letrec....andTcExprcenvty(env:TcEnv)tpenv(expr:SynExpr)=// Guard the stack for deeply nested expressionscenv.stackGuard.Guard<|fun()->...

Note stack guarding doesn't result in a tailcall so will appear in recursive stack frames, because a counter must be decremented after the call. This is used systematically for recursive processing of:

• SyntaxTree SynExpr
• TypedTree Expr

We don't use it for other inputs.