Optimize core language by inlining expressions

[julianhyde]

Optimize core language by inlining expressions.

The paper Secrets of the Glasgow Haskell Compiler inliner (Peyton Jones and Marlow, 1999, revised 2002) describes the approach.

Given the query

let
  val emp = scott.emps
in
  from e in emp
    yield e.deptno
end

we need the compiler (in particular the Calcite compiler) to know that emp is always equivalent to scott.emps and therefore can be translated to a Calcite TableScan. Without inlining, to be safe, we would have to generate a Calcite plan involving a TableFunctionScan (i.e. indirecting at runtime rather than compile time) and that seriously limits query optimization opportunities on the Calcite side.

Inlining also has some other nice effects, such as

• let val f = fn x => x + 1 in f 3 end → 3 + 1
• let val x = 3 in isOdd 3 end → isOdd 3
• (fn x => x + 1) 5 → let x = 5 in x + 1 end (beta reduction)
• let x = 1 and y = 2 in y + 3 → let y = 2 in y + 3 (remove dead declarations)

Inlining is implemented in class Inliner, which is a shuttle that makes multiple passes over the expression tree. It also converts references to built-in functions (say String.length or #length String) into function literals which can be more easily matched by subsequent optimization rules.

The paper has guidelines for when inlining can be done safely (without causing code size or runtime to increase). We implement those guidelines in class Analyzer.

[julianhyde]

Fixed in julianhyde@ab22295.