mir

package
v0.0.0-...-535c093 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 4, 2020 License: MIT Imports: 6 Imported by: 8

README

Language Spec of Mid-Level Intermediate Representation

MIR (mid-level intermediate representation) is an IR for GoCaml. It is SSA and K-normalized form, low-layer representation of GoCaml code converted from AST. It maintains high level type information for high-level optimizations.

You can see the string representation of MIR from command line.

gocaml -mir test.ml

MIR consists of basic blocks. Since MinCaml program has only one expression as root of AST, MIR has one root basic block as program.

BEGIN: program

...

END: program

Basic block has a list of instructions to execute. Instructions are run sequentially.

MIR is an SSA and K-normalized form. So one instruction contains one assignment and one operation.

var = operation

var is assigned only once and never be changed (SSA). Operation does only one thing (e.g. make a constant, add two integer, access to array element, ...) (K-normalization).

Below is a small example of let foo = 1 + 2 in -foo expression.

$k1 = int 1 ; type=int
$k2 = int 2 ; type=int
foo$t1 = binary + $k1 $k2 ; type=int
$k4 = ref foo$t1 ; type=int
$k5 = unary - $k4 ; type=int

Variable names follow below naming convention.

  • $k{number}: Variables inserted automatically by K-normalization.
  • name$t{number}: Alpha-transformed variables to identify variables which has the same name, but actually different because of shadowing. Original variable name is name.
  • name: External symbols which will be linked by linker. It's not modified because external symbol names can't be changed.
  • $unused{number}: Unused variable produced by sequence expression (an expression separated with ;). The value is guaranteed not to be used.

Instructions

Instruction Description
unit Create a () value.
bool {constant} Create a boolean value (true or false).
int {constant} Create an integer value.
float {constant} Create a floating point number value.
string {constant} Create string value. {constant} is a quoted and escaped string literal.
unary {op} {id} Apply unary operator to {id}. {op} is - or not or -..
binary {op} {id} {id} Apply binary operator. Two {id}s are lhs and rhs for the operation.
ref {id} Reference to {id} variable.
if {id} {block} {block} When {id} is true, then enter to first {block} . Otherwise inter to second {block}.
fun {ids...} {block} Function. {ids...} are comma separated parameter IDs. {block} is its body.
recfun {ids...} {block} The same as fun, but it contains recursive self call.
app {id} {ids...} Apply function. First {id} is called function. Following comma separated IDs are arguments.
appcls {id} {ids...} Apply function. First {id} is called closure. Following comma separated IDs are arguments.
appx {id} {ids...} Apply function. First {id} is external symbol. Following comma separated IDs are arguments.
tuple {ids...} Tuple value.
array {id} {id} Array value. First {id} is index and second {id} is element value.
arrlit {id} {id} Array literal value. {ids...} means elements of the literal and may be empty.
tplload {constant} {id} Load element value of tuple. Index must be constant.
arrload {id} {id} Load element value of array. First {id} is index value.
arrstore {id} {id} {id} Store value to array. First {id} is index, second {id} is array, third {id} is set value.
arrsize {id} Get array size of first {id}.
xref {id} Reference to external symbol. {id} represents the symbol.
makecls {ids...} {id} Closure object for second {id}. First {ids...} is a list for captures of the closure.
some {id} Make Some value containing {id} value
none Make None value
issome {id} Create a bool value which represents {id} is a Some value or not.
derefsome {id} Derefernce Some value in {id}
nop No operation instruction. Currently it's only used as the centinel of instructions list.

Documentation

Overview

Package mir provides definition of MIR and converter from AST.

MIR is an abbreviation of GoCaml Intermediate Language. It's an original intermediate language to fill the gap between machine code and syntax tree. MIR is a SSA form and K-normalized, and has high-level type information.

It discards many things from syntax tree because it's no longer needed. For example, position of nodes, display name of symbols and nested tree structure are discarded.

MIR consists of block (basic block), instruction and value. There is a one root block. Block contains sequence of instructions. Instruction contains a bound identifier name and its value. Some value (`if`, `fun`, ...) contains recursive blocks.

Please see spec file in the gocaml repository.

https://github.com/rhysd/gocaml/blob/master/mir/README.md

You can see its string representation by command 

gocaml -mir test.ml

e.g. 

let x = 1 in
let rec f a b = if a < 0 then a + b - x else x in
if true then print_int (f 3 4) else ()

root:
x$t1 = int 1
f$t2 = fun a$t3,b$t4
  $k1 = int 0
  $k2 = less a$t3 $k1
  $k3 = if $k2
  then:
    $k4 = add $at3 $bt4
    $k5 = sub $k4 x$t1
  else:
    $k6 = ref x$t1
$k7 = bool true
$k8 = if $k7
  then:
    $k9 = xref print_int
    $k10 = ref f$t2
    $k11 = int 3
    $k12 = int 4
    $k13 = app $k10 $k11,$k12
    $k14 = app $k9 $k13
  else:
    $k15 = unit

Index

Constants

This section is empty.

Variables

View Source 
var (
	UnitVal = &Unit{}
	NOPVal  = &NOP{}
	NoneVal = &None{}
)
View Source 
var OpTable = [...]string{
	NOT:  "not",
	NEG:  "-",
	FNEG: "-.",
	ADD:  "+",
	SUB:  "-",
	MUL:  "*",
	DIV:  "/",
	MOD:  "%",
	FADD: "+.",
	FSUB: "-.",
	FMUL: "*.",
	FDIV: "/.",
	LT:   "<",
	LTE:  "<=",
	EQ:   "=",
	NEQ:  "<>",
	GT:   ">",
	GTE:  ">=",
	AND:  "&&",
	OR:   "||",
}

Functions

This section is empty.

Types

type App 

type App struct {
	Callee string
	Args   []string
	Kind   AppKind
}

func (*App) Print 

func (v *App) Print(out io.Writer)

type AppKind 

type AppKind int

Kind of function call. 

const (
	// Means to call a function without closure
	DIRECT_CALL AppKind = iota
	CLOSURE_CALL
	EXTERNAL_CALL
)

type ArrLen 

type ArrLen struct {
	Array string
}

func (*ArrLen) Print 

func (v *ArrLen) Print(out io.Writer)

type ArrLit 

type ArrLit struct {
	Elems []string
}

func (*ArrLit) Print 

func (v *ArrLit) Print(out io.Writer)

type ArrLoad 

type ArrLoad struct {
	From, Index string
}

func (*ArrLoad) Print 

func (v *ArrLoad) Print(out io.Writer)

type ArrStore 

type ArrStore struct {
	To, Index, RHS string
}

func (*ArrStore) Print 

func (v *ArrStore) Print(out io.Writer)

type Array 

type Array struct {
	Size, Elem string
}

func (*Array) Print 

func (v *Array) Print(out io.Writer)

type Binary 

type Binary struct {
	Op       OperatorKind
	LHS, RHS string
}

func (*Binary) Print 

func (v *Binary) Print(out io.Writer)

type Block 

type Block struct {
	Top    *Insn
	Bottom *Insn
	Name   string
}

Block struct represents basic block. It has a name and instruction sequence to execute. Note that top and bottom of the sequence are always NOP instruction in order to make modifying instructions easy.

func NewBlock 

func NewBlock(name string, top, bottom *Insn) *Block

func NewBlockFromArray 

func NewBlockFromArray(name string, insns []*Insn) *Block

func NewEmptyBlock 

func NewEmptyBlock(name string) *Block

func (*Block) Append 

func (b *Block) Append(i *Insn)

func (*Block) Prepend 

func (b *Block) Prepend(i *Insn)

func (*Block) Println 

func (b *Block) Println(out io.Writer, types *types.Env)

func (*Block) WholeRange 

func (b *Block) WholeRange() (begin *Insn, end *Insn)

Returns range [begin, end)

type Bool 

type Bool struct {
	Const bool
}

func (*Bool) Print 

func (v *Bool) Print(out io.Writer)

type Closures 

type Closures map[string][]string

Closures is a map from closure name to its captures

type DerefSome 

type DerefSome struct {
	SomeVal string
}

func (*DerefSome) Print 

func (v *DerefSome) Print(out io.Writer)

type Float 

type Float struct {
	Const float64
}

func (*Float) Print 

func (v *Float) Print(out io.Writer)

type Fun 

type Fun struct {
	Params      []string
	Body        *Block
	IsRecursive bool
}

func (*Fun) Print 

func (v *Fun) Print(out io.Writer)

type FunInsn 

type FunInsn struct {
	Name string
	Val  *Fun
	Pos  locerr.Pos
}

type If 

type If struct {
	Cond string
	Then *Block
	Else *Block
}

func (*If) Print 

func (v *If) Print(out io.Writer)

type Insn 

type Insn struct {
	Ident string
	Val   Val
	Next  *Insn
	Prev  *Insn
	Pos   locerr.Pos
}

Instruction. Its form is always `ident = val`

func Concat 

func Concat(a, b *Insn) *Insn

func NewInsn 

func NewInsn(n string, v Val, pos locerr.Pos) *Insn

func Reverse 

func Reverse(insn *Insn) *Insn

Reverse the instruction list. `insn` is assumed to point head of the list

func (*Insn) Append 

func (insn *Insn) Append(other *Insn)

func (*Insn) Last 

func (insn *Insn) Last() *Insn

func (*Insn) RemoveFromList 

func (insn *Insn) RemoveFromList()

type Int 

type Int struct {
	Const int64
}

func (*Int) Print 

func (v *Int) Print(out io.Writer)

type IsSome 

type IsSome struct {
	OptVal string
}

func (*IsSome) Print 

func (v *IsSome) Print(out io.Writer)

type MakeCls 

type MakeCls struct {
	Vars []string
	Fun  string
}

Introduced at closure-transform.

func (*MakeCls) Print 

func (v *MakeCls) Print(out io.Writer)

type NOP 

type NOP struct {
}

func (*NOP) Print 

func (v *NOP) Print(out io.Writer)

type None 

type None struct {
}

func (*None) Print 

func (v *None) Print(out io.Writer)

type OperatorKind 

type OperatorKind int
const (
	NOT OperatorKind = iota
	NEG
	FNEG
	ADD
	SUB
	MUL
	DIV
	MOD
	FADD
	FSUB
	FMUL
	FDIV
	LT
	LTE
	EQ
	NEQ
	GT
	GTE
	AND
	OR
)

Operators

type Program 

type Program struct {
	Toplevel Toplevel // Mapping from function name to its instruction
	Closures Closures // Mapping from closure name to it free variables
	Entry    *Block
}

Program representation. Program can be obtained after closure transform because all functions must be at the top.

func (*Program) Dump 

func (prog *Program) Dump(out io.Writer, env *types.Env)

func (*Program) PrintToplevels 

func (prog *Program) PrintToplevels(out io.Writer, env *types.Env)

func (*Program) Println 

func (prog *Program) Println(out io.Writer, env *types.Env)

type Ref 

type Ref struct {
	Ident string
}

func (*Ref) Print 

func (v *Ref) Print(out io.Writer)

type Some 

type Some struct {
	Elem string
}

func (*Some) Print 

func (v *Some) Print(out io.Writer)

type String 

type String struct {
	Const string
}

func (*String) Print 

func (v *String) Print(out io.Writer)

type Toplevel 

type Toplevel map[string]FunInsn

func NewToplevel 

func NewToplevel() Toplevel

func (Toplevel) Add 

func (top Toplevel) Add(n string, f *Fun, p locerr.Pos)

type TplLoad 

type TplLoad struct {
	From  string
	Index int
}

func (*TplLoad) Print 

func (v *TplLoad) Print(out io.Writer)

type Tuple 

type Tuple struct {
	Elems []string
}

func (*Tuple) Print 

func (v *Tuple) Print(out io.Writer)

type Unary 

type Unary struct {
	Op    OperatorKind
	Child string
}

func (*Unary) Print 

func (v *Unary) Print(out io.Writer)

type Unit 

type Unit struct{}

func (*Unit) Print 

func (v *Unit) Print(out io.Writer)

type Val 

type Val interface {
	Print(io.Writer)
}

type XRef 

type XRef struct {
	Ident string
}

func (*XRef) Print 

func (v *XRef) Print(out io.Writer)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.