Previous Next |

A *functional* coding language is one in which (as discussed in ) execution proceeds by binding variables to values, and never modifying a variable once it is initialized. This permits equational reasoning, which is useful to the programmer. But equational reasoning is even *more* useful to the compiler - many compiler optimizations involve the rewriting of a slow program into an equivalent faster program. When the compiler doesn't have to worry about *x*'s value *now* versus *x*'s value *later*, then these transformations are easier to express. This single-assignment property is at the heart of both functional coding and SSA form. There is a close relationship between the functional intermediate representations used by functional-language compilers and the SSA form used by imperative-language compilers. Image 19.18 shows the abstract syntax of the kind of intermediate representation used in modern functional-language compilers. It aspires to the best qualities of quadruples, SSA form, and lambda-calculus. As in quadruple notation, expressions are broken down into primitive operations whose order of evaluation is specified, every intermediate result is an explicitly named temporary, and every argument of an operator or function is an *atom* (variable or constant). As in SSA form and lambda-calculus, every variable has a single assignment (or *binding*), and every use of the variable is within the *scope* of the binding. As in lambda-calculus, scope is a simple syntactic notion, not requiring calculation of dominators.

atom→cConstant integeratom→sConstant string pointeratom→vVariableexp→letfundefsinexpFunction declarationexp→let=vatominexpCopyexp→let=vbinop(atom, atom)inexpArithmetic operatorexp→let=vM[atom]inexpFetch from memoryexp→M[atom]:=atom;expStore to memoryexp→ifatom relop atomthenexpelseexpConditional branchexp→atom(args) Tail callexp→let=vatom(args)inexpNon-tail callexp→returnatomReturnargs→args→atom args fundefs→fundefs→fundefsfunction(vformals) =exp formals→formals→vformalsbinop→plus|minus|mul| ...relop→eq|ne|lt| ...

Image 19.18: Functional intermediate representation. Binding occurrences of variables are underlined.

**Scope** No variable name can be used in more than one binding. Every binding of a variable has a scope within which all the uses of that variable must occur. For a variable bound by **let** *v* = … **in** *exp*, the scope of *v* is just the

exp. The scope of a function variablefbound in_{i}let functionf_{1}(...) =exp_{1}::functionf(_{k}...) =exp_{k}inexp

includes *all* the *exp _{j}* (to allow for mutually recursive functions) as well as the

`Translate(`*node*)=
let *C* be the children of *node* in the dominator tree
let *p*_{1}*,..., p*_{n} be the nodes of *C* that have more than one predecessor
for *i* ← 1 to *n*
let *a*_{1}*,..., a*_{k} be the targets of φ functions in *p*_{i} (possibly *k* = 0)
let *S*_{i} = Translate(*p*_{i})
let *F*_{i} = "`function` *f *_{pi} (*a*_{1},..., *a*_{k}) = *S*_{i}"
let *F* = *F*_{1} *F*_{2} ... *F*_{n}
return Statements(*node*, 1, *F*)
Statements(*node, j, F*)=
if there are < *j* statements in *node*
then let *s* be the successor of *node*
if *s* has only one predecessor
then return Statements(*s*, 1, *F*)
else *s* has *m* predecessors
suppose *node* is the *i*th predecessor of *s*
suppose the φ-functions in *s* are *a*_{1} ← φ(*a*_{11},..., *a*_{1}_{m}), ...
*a*_{k} ← φ(*a*_{k}_{1},..., *a*_{km})
return "`let` *F* `in` *f*_{s}(*a*_{1}_{i},..., *a*_{ki} )"
else if the *j*th statement of *node* is a φ-function
then return Statements(*node, j* + 1, *F*)
else if the *j*th statement of *node* is "return *a*"
then return "`let` *F* `in return` *a*"
else if the *j*th statement of *node* is *a* ← *b* ⊕ *c* The cases for *a* ← *b*,
then let *S* = Statements(*node, j* + 1, *F*) *a* ← *M*[*b*], and *M*[*a*] ← *b*
return "`let` *a* = *b* ⊕ *c* in *S*" are similar.
else if the *j*th statement of *node* is "if *a* < *b* goto *s*_{1} else *s*_{2}"
then (in edge-split SSA form) *s*_{1} has only one predecessor, as does *s*_{2}
let *S*_{1} = Translate(*s*_{1})
let *S*_{2} = Translate(*s*_{2})
return "let *F* in if *a* < *b* then *S*_{1} else *S*_{2}"

**Translating functional programs into functional intermediate form** A functional program in a language such as PureFun-MiniJava starts in a form that obeys all the scope rules, but arguments are not atomic and variables are not unique. It is a simple matter to introduce well-scoped intermediate temporaries by a recursive walk of expression trees; dominator and SSA calculations are unnecessary.

All of the SSA-based optimization algorithms work equally well on a functional intermediate form; so will the optimizations and transformations on functional programs described in . Functional intermediate forms can also be made explicitly typed, type-checkable, and polymorphic as described in . All in all, this kind of intermediate representation has much to recommend it.

JaVa |
Previous Next |