Chapter 6 The BOL representation

The Moby optimizer uses a low-level l-calculus base intermediate representation called BOL.

6.1 BOL types

6.1.1 Kinds

6.2 BOL terms

The BOL representation is a normalized l-calculus --- each intermediate result is bound to a variable. We go beyond many such representations in that arguments are always variables (never constants). This design choice simplifies the implementation of rewriting, but it does add some additional structure to program representations.

A BOL expression is a BOL term labeled with a program point. The E_Pt constructor builds an expression from a program point and term. The meaning of the BOL terms is as follows:

E_Let(xs, rhs, exp)
E_StackAlloc(x, sz, align, exp)
E_Fun(fbs, exp)
E_Cont(fb, exp)
E_AllocCheck(n, exp)
E_If(x, exp₁, exp₂): If x is True, then evaluate exp₁, otherwise evaluate exp₂.
E_Switch(x, cases, dflt)
E_Apply(f, xs)
E_Throw(k, xs)
E_Ret(xs): Evaluates to the values of the variables xs. When this term is in a tail position of a function body, then the values are returned as the result of the function. Otherwise, the term is the right-hand-side of some let binding and the values will be bound to the left-hand-side variables of the let.

The right-hand side of a BOL let binding is represented by the rhs datatype, which has the following constructors:

xs = E_Exp(exp): Evaluate an expression exp and bind its results to the left-hand-side variables xs.
x = E_Select(i, y, ty): Select the ith element (zero-based) of the heap object bound to y. The BOL type ty specifies the layout of the object and is used to compute the offset of the ith element.
x = E_Alloc(ys)
x = E_Wrap(y)
x = E_Unwrap(y)
x = E_IConst(n): Binds x to the integer constant n. The precision of n is determined by the type of x, which may be an enumeration.
x = E_SConst(s): Binds x to the string constant s.
x = E_FConst(f): Binds x to the floatin-point constant f. The precision of n is determined by the type of x.
x = E_BConst(b): Binds x to the boolean constant b.
x = E_Extern(a, ty)
x = E_Label(l)
x = E_Prim(p)
x = E_DictFieldSel(y, f)
x = E_DictMethSel(y, m)
x = E_FieldGet(y, s)
x = E_FieldPut(y, s, z)
x = E_MethGet(y, s)
x = E_CCall(f, ys)