Module Fang_ir

An intermediate representation (IR) for Tiger.

As with Tiger, the IR is encoded in the tagless-final style.

Language specification

The IR is a language that expresses programs as a "tree" of values and effects.

For example, the following program prints the integers from 1 to 5 and produces the value 0 as a result.

(perform
 (seq
  (move (box #1) (const 1))
  (seq
   (def loop_start)
   (seq
    (cjump LE (box #1) (const 5) loop_body loop_end)
    (seq
     (def loop_body)
     (seq
      (discard (call (loc print_int) (box #1)))
      (seq
       (jump (loc loop_start) loop_start)
       (def loop_end)))))))
 (const 0))
type value = private
| Value_tag
type effect = private
| Effect_tag
type rel = [
| `Equal
| `Not_equal
| `Less
| `Less_or_equal
| `Greater
| `Greater_or_equal
]
module type IR = sig ... end

Interpreters

module Pretty : sig ... end

Pretty-printing IR fragments.

module Tree : sig ... end

In-memory storage of IR fragments.

Rewriting engine

This is an implementation of the optimization framework described by Oleg Kiselyov.

module type REWRITE = sig ... end
module Lift : functor (I : IR) -> REWRITE with type 'a observation = 'a I.t
module type TRANSFORM = sig ... end
module Identity : functor (X : TRANSFORM) -> functor (Next : REWRITE with type 'a t = 'a X.from) -> REWRITE with type 'a observation = 'a Next.observation

Canonical IR

module Canonical : functor (Next : REWRITE) -> REWRITE with type 'a observation = 'a Next.observation