Implementation of basic optimizations

Important

This section is in a draft status. Mistakes are possible. Comments and clarifications are particularly welcome.

This section explains the implementation of basic optimizations for the language of Expression Programs.

Recall the compiler phases for expression programs. In the assignment, machine code generation works directly on the AST, and the optimizations described on the optimizations page are formulated at that level too. This section instead follows the structure of the general picture: the AST is first translated into an intermediate representation (IR), and the optimizations are implemented as rewritings of the IR. The IR of this section is the language sprog of simplified expression programs, introduced below, and the translation into it is the flattening of expression trees. The picture of the phases then becomes the following.

Machine code generation from sprog is not part of this section; the flattened form is, however, much closer to assembly than the AST is, and the translation would be considerably simpler than the one from the AST. The rest of this section covers the two remaining phases: the IR generation, and the optimization loop on the IR.

The auxiliary files for this section are available as basic-opt-demo.zip. They form a small dune project; run dune build and then dune exec ./main.exe. All the traces shown in this section are produced by that program, one example per run.

Note

The code uses a few pieces of OCaml beyond the basics: a function whose body uses a mutable reference bound outside it, List.fold_left_map and List.filter_map, the standard library’s Map and Set modules, and one functor. We briefly explain these concepts at the point where they are used; see also the Scala/OCaml cheat sheet.

Intermediate language

As a first stepping stone, we introduce an intermediate language of simplified expression programs, with the following definitions.

(* sprog.ml *)
type binop = Eprog.binop
(* type binop = | Add | Sub | Mul | Div *)
type varname = Eprog.varname

type operand = Lit of int
             | Var of varname

type sstmt =
   | ValBinop of varname * binop * operand * operand
   | Input of varname

type sprog = sstmt list * operand

An important characterization of this intermediate language is that the program representation is flattened. There are no tree-like structures to be found in here. In particular, check the declaration of the type operand that we now use in the right-hand-side of the statements and the return position.

Flattening of expression trees into a list of statements is a relatively standard transformation in compilers. In the auxiliary material this functionality is implemented in module EprogToSprogDestDriven (file eprogToSprogDestDriven.ml). We explain a few key ingredients of this module below.

Fresh name generation in OCaml

An important ingredient of many compiler translations is generation of fresh names. Consider the code below.

let fresh_variable, current_counter_value =
  let ctr = ref 0 in
  ( fun x -> let c = !ctr in ctr := c + 1; x ^ (string_of_int c))
  , fun () -> !ctr

There is quite a bit packed in this short snippet. The top-level let binding declares a tuple (in many places OCaml syntax allows omitting the tuple-surrounding parentheses for clarity) of two values fresh_variable and current_counter_value. These values are functions bound to the values fun x -> ... and fun () -> ... respectively. Both of these functions have access to the counter ctr that is declared in the scope of the let statement as a reference with the initial value set to 0. This scoped declaration implements encapsulation of the counter implementation. For outer code, there is no access to the raw value of the counter other than through those functions above. For example, the above snippet exposes no ways of resetting the counter value.

Note also that ref 0 is evaluated once, when the let binding is evaluated, so every call of either function uses the same cell. With ref 0 inside the function body instead, each call creates a new cell and the counter never advances. The OCaml textbook by Clarkson et al. [C+26] discusses exactly this contrast (chapter on refs, example “Mutable Counter”).

Before reading further, check your understanding of this code by working out the types of the two functions. They are fresh_variable : string -> string and current_counter_value : unit -> int; the counter itself does not appear in either type.

Constant and copy propagation, the need for an environment

The shape of our target language introduces one subtlety. Consider the source-level program Examples.example_program_1.

let example_program_1: eprog = (
      [Val ("a", Int 5);
       Val ("b", Var "a")],
      Var "b"
)

corresponding, in the source syntax of the assignment, to

val a = 5
val b = a
return b

Now, observe that the language of sprog has no facilities for representing a non-computational move instruction. Neither of the assignments to a and b can be represented! It is then the job of this translation to do an on-the-fly substitution for such moves.

For the example above, the translation is

return 5

This already implements two forms of optimization known as constant propagation and copy propagation. To achieve this, we need some notion of environment. For simplicity, we let the environment type be just an associative list for association of variable names to operands.

type t_env = (varname * operand) list

Flattening translation of expressions

The main workhorse of flattening of expressions is the function tr_expr defined as follows. This function assumes that the generated names never coincide with the names used in the source program.

Note

Here, this is arranged by a naming convention: every generated name starts with $, a character that the lexer of the source language does not accept in an identifier, and so no source-level name can ever look like $t3. Nothing in the code enforces the convention.

(* Simplification that assumes there is a way to avoid name clashing! *)
let rec tr_expr env (dest:varname option) (e:Eprog.expr) =
  match e with
    Int n -> [], Lit n
  | BinOp (op, e1, e2) ->
      let i1, o1 = tr_expr env None e1 in
      let i2, o2 = tr_expr env None e2 in
      let x =
          match dest with
            None -> fresh_variable "$t"
          | Some y -> y in
      i1 @ i2 @ [ ValBinop (x, op, o1, o2)], Var x
  | Eprog.Var x -> [],
          match List.assoc_opt x env with
            None -> Var x
          | Some o -> o

The type of tr_expr is t_env -> varname option -> Eprog.expr -> sstmt list * operand. The first argument is the environment we introduced above. The second argument is the optional destination that we discuss below. The third argument is the expression to translate. This function returns the list of statements that correspond to the body of the expression (remember it may be rather deep) and the operand where the result is to be found.

Let us review the three outer cases that we match on.

1. When the source-level expression is just an integer literal, e.g., Int 5, there are no statements that correspond to it, and so the result of this case is an empty list, paired with the literal in the target language Lit 5.

2. When the source-level expression is a complex binop, we recursively translate the subexpressions.

   Here, let us revisit the argument dest. It specifies what variable to use for storing the result of complex binops. It is optional because for the subexpressions there is no expected source-level destination, and in that case we use a fresh name.

   The final list of instructions we return is the concatenation of what is returned from the recursive calls, together with one more instruction implementing the binop of the current expression. Note how we consult the destination with a match, and propagate the resulting operand back to the caller through the Var operand constructor.

3. The varname case is the one place where the environment is accessed. We check if the variable is associated with an operand in the environment and use it – this is the on-the-fly substitution alluded to earlier. For a well-scoped program every variable is in the environment by the time it is used (see the translation of statements below), so the None branch is never taken; we keep the variable name in that case rather than fail.

This idiom of passing the destination down from the caller is an instance of a more general technique known as destination-driven code generation.

Note

The pattern is written Eprog.Var x, while Int and BinOp are unqualified. The module Sprog, which this file opens, also has a constructor named Var (of type operand), and the qualification tells OCaml which of the two we mean. The constructors Int and BinOp have no such clash.

Translation of statements

Translation of statements has type t_env -> Eprog.estmt -> t_env * Sprog.sstmt list

This return value is a tuple of an environment that is updated and a list of sprog statements.

let tr_stmt env =
  let open Eprog in function
    Val (x,e) ->
        let i, o = tr_expr env (Some x) e
        in (x, o)::env, i
  | Input x ->
        (x, Sprog.Var x) :: env,
        [Sprog.Input x]

We consider each of the outer matches in detail.

1. For Val bindings, we call into tr_expr defined above, explicitly providing the destination. Here i is the returned list of instructions, and o is the operand. The returned environment extends the original with the entry (x,o).

2. Inputs are simply translated to inputs. The environment is extended with the entry (x, Var x): an input variable stands for itself, and later uses of it resolve to the variable.

Translation of the whole program

Translation of the whole program is done as follows. We use the built-in List.fold_left_map that combines both map and fold operations, and remember to translate the return expression. The last concatenation is a bit clunky, but it is necessary.

let eprog_to_sprog (stmts, e) =
  let env', stmts' = List.fold_left_map tr_stmt [] stmts in
  let e_insts, e_op = tr_expr env' None e in
  ((List.concat stmts') @ e_insts), e_op

Alternative translation

We also include a module EprogToSprog (file eprogToSprog.ml) that uses more efficient environments and a slightly different traversal structure. One visible difference: it does not use the source-level names as destinations, so every binop lands in a fresh temporary. See the exercises at the end of this section.

Optimization driver and the main function

We organize our optimizations using a simple loop.

(* opt.ml *)
let rec opt sprog =
  let s_opt =
    sprog
    (* |> ConstFoldSimpl.const_fold_sprog_1    *)
    |> ConstFold.const_fold_sprog
    (* |> CSE.cse *)
    (* |> DCE.dce  *)
  in if s_opt = sprog then sprog
  else
    let _ = Printf.printf "--\n" in
    let _ = Printf.printf "%s\n" (Sprog.string_of_sprog s_opt) in
    opt s_opt

The function opt repeatedly applies a sequence of different optimizations, until the program representation no longer changes. Whenever the program has changed, the new version is printed, preceded by a line --; this is what produces the traces shown below. In the file as shipped, only constant folding is enabled. The other optimizations are switched on by uncommenting the corresponding lines, which is what we do as we introduce them.

The main function of the whole program lives in file main.ml.

let _ =
  let s1 =
           EprogToSprogDestDriven.eprog_to_sprog
           (* EprogToSprog.eprog_to_sprog  *)
           Examples.example_program_1
         in
  (* print the program after translating to sprog
     representation before any optimizations *)
  let _ = Printf.printf "%s\n" (Sprog.string_of_sprog s1) in
  let s2 = Opt.opt s1 in
  Printf.printf "-----------\n";
  (* final program after optimization *)
  Printf.printf "%s\n" (Sprog.string_of_sprog s2)

The main function is meant to be edited: change the example, or plug in the pretty printer for source programs from your assignment.

What an optimization may change

An optimization is a rewriting of the program that must preserve its observable behaviour. For expression programs, the observable behaviour consists of the value returned and the sequence of inputs consumed. A rewriting is therefore admissible when the rewritten program returns the same value as the original and consumes the same inputs in the same order; the decisions in the following sections – which statements may be deleted, which algebraic laws may be applied, which statements must be kept – are each justified by this condition.

Constant folding

Starting point

We start by switching the driver to the simplified constant folder in file constFoldSimpl.ml, and within that file, with a version that does nothing.

(* constFoldSimpl.ml *)
let const_fold_do_nothing x = x

Consider Examples.example_program_2.

val a = 5
val b = a
return a + b

Running our implementation on this example demonstrates the flattening (and the associated constant/copy propagation). But afterwards, the program does not change.

$t0 = 5 + 5;
return $t0
-----------
$t0 = 5 + 5;
return $t0

A simplified constant folder

Let us now implement the first version of this optimization.

let subst_oper env = function
   Lit n -> Lit n
 | Var x  ->
      match List.assoc_opt x env with
        None -> Var x
      | Some op -> op

let f_op = let open Eprog in function
    Add -> ( + ) | Sub -> ( - ) | Mul -> ( * ) | Div -> ( / )

let const_fold_stmt_1 env stmt =
   match stmt with
   | ValBinop (x, op, Lit a, Lit b) when not (op = Eprog.Div && b = 0) ->
        (x, Lit ((f_op op) a b)) :: env,
        stmt (* keep the statement, even though it's dead code *)
   | ValBinop (x, op, o1, o2) ->
        env,
        ValBinop (x, op, subst_oper env o1, subst_oper env o2)
   | Input _ -> env, stmt

let const_fold_sprog_1 (stmts, e) =
   let env', stmts'  = List.fold_left_map const_fold_stmt_1 [] stmts in
   let e' = subst_oper env' e in
   (stmts', e')

The overall structure should by now look familiar.

1. Just like before, we use an environment for copy/constant propagation. We stick to a list-based environment in this simple version.

2. Function const_fold_stmt_1 works on a single statement and distinguishes three cases.

   1. The case when the binop is over two constants. In this case, we extend our environment with statically precomputed result of the binop. We keep the statement around, even though we expect it to be dead code from now on: this version only substitutes, and deleting statements is left to the dead code elimination that we implement later. The guard excludes division by zero, which the compiler cannot evaluate; such a statement falls through to the second case and is kept. The full constant folder below discusses this case with an example.

   2. The general binop case. This means that at least one of the operands is a variable. We proceed to propagate the substitution of the operands, leaving the environment unchanged.

   3. The input case, which changes neither the program nor the environment.

3. Function const_fold_sprog_1 works on the whole program, with List.fold_left_map, just like eprog_to_sprog. It threads the environment through the statements and finally substitutes into the return operand.

Let’s run this on example_program_2. We get the following

$t0 = 5 + 5;
return $t0
--
$t0 = 5 + 5;
return 10
-----------
$t0 = 5 + 5;
return 10

Observe that the return value is folded, but the dead statement stays behind, as announced.

Let’s try another test, asg1_task4.

$t0 = 10 + 49;
$t1 = 6 / $t0;
$t2 = $t1 + 10;
$t3 = 70 * 77;
$t4 = 12 / 9;
$t5 = $t3 - $t4;
$t6 = $t5 + 5;
$t7 = $t2 * $t6;
return $t7
--
$t0 = 10 + 49;
$t1 = 6 / 59;
$t2 = $t1 + 10;
$t3 = 70 * 77;
$t4 = 12 / 9;
$t5 = 5390 - 1;
$t6 = $t5 + 5;
$t7 = $t2 * $t6;
return $t7
--
$t0 = 10 + 49;
$t1 = 6 / 59;
$t2 = 0 + 10;
$t3 = 70 * 77;
$t4 = 12 / 9;
$t5 = 5390 - 1;
$t6 = 5389 + 5;
$t7 = $t2 * $t6;
return $t7

Two more passes fold $t7 and then the return operand, giving in the end

$t0 = 10 + 49;
$t1 = 6 / 59;
$t2 = 0 + 10;
$t3 = 70 * 77;
$t4 = 12 / 9;
$t5 = 5390 - 1;
$t6 = 5389 + 5;
$t7 = 10 * 5394;
return 53940

So far so good, but the folding takes many passes. Each pass folds one more level of the original expression tree: a statement receives its substituted operands in one pass, and is recognized as a binop over two literals only in the next. There are also opportunities to do more rewriting when the value of a variable is not known, but algebraic laws allow us to do simplifications, e.g., in val y = 0 + x. We turn to both points next.

Algebraic simplification and the full constant folder

The full implementation of constant folding lives in constFold.ml. Compared to the simplified version, it makes three changes: the environment is a StringMap instead of an associative list; a folded statement is dropped from the program instead of being kept as dead code; and a handful of algebraic laws are applied.

(* constFold.ml *)
module StringMap = Map.Make (String)

type const_fold_env = operand StringMap.t

let subst_oper env = function
   Lit n -> Lit n
 | Var x  ->
      match StringMap.find_opt x env with
        None -> Var x
      | Some op -> op

let const_fold_stmt env stmt =
  let (|->) x op = StringMap.add x op env, None in
  (* substitute the operands BEFORE matching, so that the algebraic
     rules below see the folded operands and not the original ones *)
  let stmt' = match stmt with
    | ValBinop (x, op, o1, o2) ->
        ValBinop (x, op, subst_oper env o1, subst_oper env o2)
    | s -> s in
  match stmt' with
  | ValBinop (x, op, Lit a, Lit b) when not (op = Eprog.Div && b = 0) ->
      x |-> Lit ((f_op op) a b)
  | ValBinop (x, Add, Lit 0, Var y) -> x |-> Var y
  | ValBinop (x, Add, Var y, Lit 0) -> x |-> Var y
  | ValBinop (x, Sub, Var y, Lit 0) -> x |-> Var y
  | ValBinop (x, Mul, Lit 0, _    ) -> x |-> Lit 0
  | ValBinop (x, Mul, _,     Lit 0) -> x |-> Lit 0
  | ValBinop (x, Mul, Lit 1, Var y) -> x |-> Var y
  | ValBinop (x, Mul, Var y, Lit 1) -> x |-> Var y
  | ValBinop (x, Sub, Var a, Var b) when a = b -> x |-> Lit 0
  | ValBinop (_, _, _, _ ) -> env, Some stmt'
  | Input _ -> env, Some stmt'

The function f_op is as before. The type of const_fold_stmt is const_fold_env -> sstmt -> const_fold_env * sstmt option; compare this with the type of tr_stmt. Note the option in the result: None means that the statement is deleted from the program. The definition has the following parts.

1. The locally defined operator |-> is a small piece of notational convenience: x |-> op produces the pair (env', None), where env' extends the environment with the binding of x to the operand op. In other words, every rule of the form x |-> ... replaces the statement defining x by a binding in the environment; the statement itself is gone, and all later uses of x are substituted. This is why the full version, unlike const_fold_stmt_1, does not need to keep dead statements around.

2. Before matching, we substitute the operands of the statement, and it is the substituted statement stmt' that we match on. In this way, the rules always see the operands as they are after the earlier statements have been folded. Let us follow one pass over the program Examples.prog_11.

   val y = 1 + 2
   val x = 0 + y
   return x
   

   The first statement, y = 1 + 2, has two literal operands. The first rule applies, y is bound to 3 in the environment, and the statement is deleted. The second statement, x = 0 + y, is substituted first, using this environment, and becomes x = 0 + 3. It now has two literal operands as well, so the first rule applies again: x is bound to 3 and the statement is deleted. Finally, the return operand x is substituted, and the program is return 3, after a single pass.

   Two things follow from substituting first. One is that folding needs a single pass, whereas the simplified version needs one pass per level of the expression tree: each statement is folded as soon as it is reached. The other is that the algebraic rules, which bind a variable to another variable, only ever do so for a variable that is still defined in the program, that is, for an input variable or for a variable whose statement is kept. Matching the second statement with its original operands instead, the rule for 0 + y binds x to y, a variable whose statement is deleted just before.

3. The first rule is the one we already know: a binop over two literals is computed at compile time, except for a division by zero, which is excluded by the guard exactly as in the simplified version. Consider Examples.prog_13.

   val y = 1 / 0
   val z = 1 + 2
   return y + z
   

   The statement defining y is not a computation that the compiler can perform; the guard fails, the general case at the end applies, and the statement is kept. The rest of the program is folded as usual.

   y = 1 / 0;
   z = 1 + 2;
   $t0 = y + z;
   return $t0
   --
   y = 1 / 0;
   $t0 = y + 3;
   return $t0
   -----------
   y = 1 / 0;
   $t0 = y + 3;
   return $t0
   

4. The next eight rules are algebraic laws: 0 is a unit of addition (on either side) and of subtraction (on the right); 0 annihilates multiplication; 1 is a unit of multiplication; and y - y is 0. Notice that in each of these rules the result is again an operand, either a literal or a variable, and so each of them results in a binding rather than in a rewritten statement. Also notice which laws are not in the list. Division has no rule at all. A rule for x / 1 could be added. A rule for 0 / x could not: the value of 0 / x is 0 for every x except 0, where the program fails, and the condition of What an optimization may change requires the rewritten program to fail there too.

5. The last two cases are the general binop, which is now simply passed on with its substituted operands, and the input statement, which is passed on unchanged.

Note

Two points of OCaml notation in this code. First, a name made of operator characters, such as |->, is an ordinary function that is applied in infix position. It is defined by enclosing the name in parentheses, as in let (|->) x op = ..., and x |-> op is then the same as (|->) x op. The OCaml manual’s section on operators lists which characters are allowed and how the precedence of such an operator is determined by its first character. Second, the constructors Add, Sub and Mul in the patterns are those of Eprog.binop, and OCaml resolves them from the type of the value being matched; in the guard op = Eprog.Div the constructor appears in an ordinary expression, where no such type information is available, and must be qualified.

With these rules in place, all of asg1_task4 is folded in a single pass:

$t0 = 10 + 49;
$t1 = 6 / $t0;
$t2 = $t1 + 10;
$t3 = 70 * 77;
$t4 = 12 / 9;
$t5 = $t3 - $t4;
$t6 = $t5 + 5;
$t7 = $t2 * $t6;
return $t7
--
return 53940
-----------
return 53940

Factoring out the traversal

The remaining part of constFold.ml is the traversal of the statement list. We have seen its shape already, twice: fold over the statements from left to right, threading an environment through, collect the resulting statements, and finally substitute into the return operand. Common subexpression elimination, which we implement below, has exactly the same shape. Rather than writing the traversal a third time, we factor it out into module SimpleRewriter (file simpleRewriter.ml).

(* simpleRewriter.ml *)
module type SimpleRewriter = sig
  type env
  val empty : env
  val rewrite_stmt : env -> sstmt -> env * sstmt option
  val rewrite_oper : env -> operand -> operand
end

module Make (S: SimpleRewriter) = struct
  let traverse (stmts, e) =
    let env', stmts' = List.fold_left_map S.rewrite_stmt S.empty stmts in
    (List.filter_map Fun.id stmts', S.rewrite_oper env' e)
end

The module type SimpleRewriter lists what a traversal needs to know about the optimization it is running. There are four items.

1. The type env is the type of the environment. Constant folding uses operand StringMap.t; the traversal does not need to know the exact type, it only passes environments along.

2. The value empty is the environment at the start of the program, before any statement is processed.

3. The function rewrite_stmt processes one statement. Given the environment before the statement and the statement itself, it returns the environment after the statement, and either Some s, meaning that the statement s stays in the program, or None, meaning that the statement is deleted. Note that this matches the type of const_fold_stmt.

4. The function rewrite_oper processes the return operand. Given the environment after the last statement and the operand, it returns the operand with the substitution applied. Note that this matches the type of subst_oper.

The function traverse runs these over a whole program. Its two lines do the following.

The first line is List.fold_left_map S.rewrite_stmt S.empty stmts. The library function List.fold_left_map walks a list from left to right, applying a function to an accumulator and each element in turn; the function returns the new accumulator and a result for the element. At the end, fold_left_map returns the final accumulator and the list of all results. Here the accumulator is the environment, the elements are the statements, and the results are optional statements. So env' is the environment after the last statement, and stmts' is a list with one entry per original statement, Some s for the statements that stay and None for the statements that are deleted.

The second line builds the result. The expression List.filter_map Fun.id stmts' turns the list of optional statements into a list of statements by dropping the None entries and unwrapping the Some entries; for example, [Some s1; None; Some s3] becomes [s1; s3]. (Fun.id is the identity function; filter_map applies it to each entry and keeps the entries for which it returns Some.) The order of the statements is unchanged. The second component, S.rewrite_oper env' e, is the return operand after substitution in the final environment.

As an illustration, here is what traverse computes for constant folding on prog_09, the program input x; y = x + 1; z = y - y; return z. The fold starts with the empty environment. The statement input x returns the environment unchanged and Some (input x). The statement y = x + 1 has a variable operand, so it is passed on: the environment is unchanged and the result is Some (y = x + 1). The statement z = y - y matches the rule for y - y: the environment becomes {z ↦ 0} and the result is None. So stmts' is [Some (input x); Some (y = x + 1); None], which filter_map turns into [input x; y = x + 1], and the return operand z is substituted in {z ↦ 0}, giving 0. This is the trace shown at the beginning of the next section.

This is how the traversal is written once, for any optimization of this shape. The way it is parameterized is a functor. A functor is, informally, a function from modules to modules: Make takes a module, here one with the four items of SimpleRewriter, and produces a module, here one containing traverse. Unlike an ordinary function, a functor is not a value: it is applied at the module level, as in SimpleRewriter.Make (S), and the application is resolved when the program is compiled. This is the same mechanism as Map.Make (String), which we used above: the functor Map.Make takes an argument that supplies the type of the keys and their ordering, and returns a module of maps over that key type. The OCaml manual’s chapter on the module system describes functors in detail. In this section, Make (S) reads as “the traversal, specialized to the rewriter S”.

Constant folding is now one instantiation of the functor. The argument is written as an anonymous module, struct ... end, that provides the four components.

(* constFold.ml, continued *)
module T = SimpleRewriter.Make ( struct
               type env = const_fold_env
               let empty = StringMap.empty
               let rewrite_stmt = const_fold_stmt
               let rewrite_oper = subst_oper
               end )

let const_fold_sprog = T.traverse

Dead code elimination

Constant folding now deletes the statements that it folds, but it cannot delete a statement that merely becomes unused. Consider Examples.prog_09.

input x
val y = x + 1
val z = y - y
return z

Running constant folding alone on this program gives

input x;
y = x + 1;
z = y - y;
return z
--
input x;
y = x + 1;
return 0
-----------
input x;
y = x + 1;
return 0

The rule for y - y binds z to 0 and deletes the definition of z. But that definition is the only use of y, and the statement defining y is left behind. It is dead code: the value it computes is never used. Module DCE (file DCE.ml) removes dead code.

(* DCE.ml *)
module StringSet = Set.Make (String)

let uses_of_operand = function
    Lit _ -> [ ]
  | Var x -> [x]

let defs_and_uses_of_stmt = function
    Input x -> x, []
  | ValBinop (x, _, o1, o2) ->
      x, (uses_of_operand o1)@(uses_of_operand o2)

let dce ((stmts, e) as eprog) =
  let def_list, use_lists_pre =
      List.map defs_and_uses_of_stmt stmts |> List.split in
  let use_lists = uses_of_operand e :: use_lists_pre in
  let def_set = StringSet.of_list def_list in
  let use_set = StringSet.of_list (List.concat use_lists) in
  let unused_set = StringSet.diff def_set use_set in
  if StringSet.is_empty unused_set
    then eprog
    else List.filter_map
           (fun st -> match st with
              ValBinop (x,_, _,_) when StringSet.mem x unused_set
                -> None
            | _ -> Some st )
            stmts, e

This optimization has a different structure from the previous one. There is no environment and no left-to-right rewriting; instead, the program is inspected as a whole, in two steps.

1. The functions uses_of_operand and defs_and_uses_of_stmt compute, for one operand and for one statement respectively, which variables are defined and which are used. Every statement defines exactly one variable, and a binop statement uses the variables among its operands. The return operand uses its variable, if it is one, and defines nothing; this is why use_lists gets one more entry than use_lists_pre.

2. Function dce collects the definitions and the uses of the whole program into two sets. The variables that are defined but never used form the set unused_set. If it is empty, the program is returned as is. Otherwise, the statements that define an unused variable are filtered out.

Let us compute these sets by hand for the program above, as it is after constant folding:

input x;
y = x + 1;
return 0

The statement input x defines x and uses nothing; the statement y = x + 1 defines y and uses x; the return operand 0 uses nothing. Hence def_set = {x, y}, use_set = {x}, and unused_set = {y}. The statement defining y is removed. On the next pass, x is defined and no longer used, yet its statement is kept.

The pattern in the filter removes only ValBinop statements. An input statement whose variable is unused is kept, because reading an input is an effect that the program’s environment can observe. A program that reads two inputs and returns 0 is not the same program as one that reads none and returns 0; keeping the input is what the condition of What an optimization may change requires.

One pass of dce removes only the statements whose variable is directly unused. If the removed statement is itself the only user of some earlier definition, that definition becomes dead only now, and is removed in the next pass. Consider Examples.prog_14, a chain of two bindings, neither of which reaches the return value.

input x
val y = x + 1
val z = y + 1
return 0

Running dead code elimination alone (comment out the other optimizations in opt.ml to try this) removes one statement per pass.

input x;
y = x + 1;
z = y + 1;
return 0
--
input x;
y = x + 1;
return 0
--
input x;
return 0
-----------
input x;
return 0

We could of course iterate inside dce itself. There is no need, because the driver loop already repeats the optimizations until nothing changes.

Running constant folding followed by dead code elimination on prog_09 now gives the following.

input x;
y = x + 1;
z = y - y;
return z
--
input x;
return 0
-----------
input x;
return 0

Common subexpression elimination

The last optimization targets programs that compute the same thing twice. Consider Examples.prog_10.

input x
val y = x + 1
val z = 1 + x
return z + y

Neither constant folding nor dead code elimination can do anything with this program: nothing is constant and nothing is dead. But y and z are the same value, and the second computation is redundant. Common subexpression elimination, in module CSE (file CSE.ml), detects such repetitions and replaces the later variable with the earlier one.

The environment of this optimization has two parts: a map from expressions – an operator together with its two operands – to the variable that already holds their value, and a map from variables that have been eliminated to the variables that replace them.

Two expressions that differ only in the order of the operands of a commutative operator compute the same value, and the first map treats them as the same key: its comparison function, cse_compare, brings the operands of + and * into a fixed order before comparing.

(* CSE.ml *)
(* Two expressions that differ only in the order of the operands of a
   commutative operator are the same key; the comparison brings both
   to a fixed operand order. The statements themselves are not reordered. *)
let cse_compare (op1, a1, b1) (op2, a2, b2) =
   let norm op a b =
     if (op = Eprog.Add || op = Eprog.Mul) && compare a b > 0
       then (op, b, a) else (op, a, b) in
   compare (norm op1 a1 b1) (norm op2 a2 b2)

module StringMap = Map.Make (String)
module BinopMap = Map.Make
    (struct type t = Eprog.binop * operand * operand
            let compare = cse_compare
     end )

type cse_env = varname BinopMap.t
type subst_env = varname StringMap.t

Which of the two orders is chosen is immaterial, as long as it is the same for x + 1 and 1 + x. The reordering happens inside the comparison only; the statements in the program keep their operands in the order in which they are written. As cse_compare is the built-in compare on the reordered triples, it is a total order, which is what Map.Make requires of its argument.

The rest of the module follows the pattern of the constant folder.

let subst_oper (_, subst_env) = function
     Lit n -> Lit n
   | Var x ->
       match StringMap.find_opt x subst_env with
         None -> Var x
       | Some y -> Var y

let cse_stmt ((cse_env, subst_env) as _env) stmt =
  match stmt with
    ValBinop (x, op, o1, o2) ->
      let o1' = subst_oper _env o1 in
      let o2' = subst_oper _env o2 in
      ( match BinopMap.find_opt (op, o1', o2') cse_env with
          None -> (BinopMap.add (op, o1', o2') x cse_env, subst_env ),
                  Some (ValBinop (x, op, o1', o2'))
        | Some y ->
              (cse_env, StringMap.add x y subst_env), None)
  | Input _ -> _env, Some stmt

module T = SimpleRewriter.Make ( struct
      type env = cse_env * subst_env
      let empty = (BinopMap.empty, StringMap.empty)
      let rewrite_stmt = cse_stmt
      let rewrite_oper = subst_oper
    end )

let cse = T.traverse

1. Substitution of operands only consults the second part of the environment: a variable that has been eliminated is replaced by its representative. Literals are left alone.

2. For a binop statement, we first substitute the operands – again, before anything else – and look up the resulting expression in the map. If it is not there, this is the first time we see this expression: we keep the statement (with the substituted operands) and record that its value is available in x. If it is there, bound to some earlier variable y, the statement is redundant: we delete it and record that x is to be replaced by y from now on.

3. Input statements are passed on. They are not expressions, and two inputs of the same variable do not compute the same value.

Running CSE alone on prog_10 gives

input x;
y = x + 1;
z = 1 + x;
$t0 = z + y;
return $t0
--
input x;
y = x + 1;
$t0 = y + y;
return $t0
-----------
input x;
y = x + 1;
$t0 = y + y;
return $t0

Observe that the statement defining z is deleted by CSE itself, and not left for DCE: once we know that z is replaced by y everywhere, there is no reason to keep it.

Combining the optimizations

With the three optimizations in place, we uncomment all of them in the driver.

(* opt.ml, all optimizations enabled *)
let rec opt sprog = 
  let s_opt = 
    sprog 
    |> ConstFold.const_fold_sprog
    |> CSE.cse
    |> DCE.dce
  in if s_opt = sprog then sprog 
  else 
    let _ = Printf.printf "--\n" in
    let _ = Printf.printf "%s\n" (Sprog.string_of_sprog s_opt) in  
    opt s_opt

Each optimization can expose opportunities for the others, which is why the driver loops until the program stops changing. The program Examples.prog_12 exercises all three.

input x
val y = x + 1
val z = 1 + x
val w = y - z
return w

input x;
y = x + 1;
z = 1 + x;
w = y - z;
return w
--
input x;
y = x + 1;
w = y - y;
return w
--
input x;
return 0
-----------
input x;
return 0

In the first iteration, constant folding does nothing (the operands of w are two different variables) and CSE replaces z by y; nothing is dead yet. In the second iteration, constant folding recognizes y - y and binds w to 0, whereupon the definition of y has no users left and DCE removes it. A third iteration confirms that nothing changes any more. No single pass reaches this result, in whichever order the three optimizations are applied: the definition of y becomes dead only after w has been folded, and w can be folded only after CSE has run.

Exercises

An exercise marked with an asterisk requires more than the material of this section.

1. Read eprogToSprog.ml, the alternative translation. It uses a StringMap for the environment and List.fold_left for the traversal. Explain why it needs no counterpart of the None branch of tr_expr, and what happens if a source program uses a variable before defining it.

2. Add a rule for x / 1 to const_fold_stmt. Then explain, using the condition of What an optimization may change, why a rule for 0 / x must not be added.

3. The function dce removes only directly unused statements and relies on the driver for chains. Change it to iterate internally until no statement is removed, and compare the traces of the two versions on prog_14.

4. The function cse_compare treats + and * as commutative. Explain why - and / are not, and construct a program where treating - as commutative would produce a wrong result.

5. (*) The compiled program computes in 64-bit two’s-complement arithmetic (see Expression Programs), while f_op evaluates with OCaml’s 63-bit int. Give a program on which the folded program and the compiled, unfolded program return different values. Which of the folding rules is responsible, and what would f_op have to do instead? Does the same problem arise for the algebraic rules?

6. Extend main.ml to take the name of the example and the set of enabled optimizations from the command line, so that experiments no longer require editing opt.ml.