Chapter 14 The code-generator generator

We use a tool for generating significant portions of the Moby compiler's BOL optimizer and code generator.

14.1 The specification language

Specification
	::=	Header Spec⁺
Spec
	::=	ForBinding^* Operators
	\|	ForBinding^* RewriteRules
	\|	ForBinding^* Translation
ForBinding
	::=	`for` `<` Id (`,` Id)^* `>` `in` `{` ExpansionGrp (`,` ExpansionGrp)^* `}`
ExpansionGrp
	::=	`<` Expansion (`,` Expansion)^* `>`
Expansion
	::=	Id
	\|	String
RewriteRules
	::=	`rules` RewriteRule⁺
RewriteRule
	::=	ForBinding^* Pattern WhenClause^opt `=>` Term WhereClause^opt
Pattern
	::=	Operator `(` Pattern (`,` Pattern)^* `)`
	\|	`?` Id
	\|	`_`
Term
	::=	Operator `(` Term (`,` Term)^* `)`
	\|	`!` Id
Operator
	::=	Id
	\|	`<` Id `>`
WhenClause
	::=	`when` Expression
WhereClause
	::=	`where` (Id `=` Expression)⁺
Expression

14.2 Generating the rewriting rules

For example, the following three rewrite rules:

IAdd32(IConst ?a, IConst ?b) => IConst(!c) where c = CA.iadd32(!a, !b) IAdd32(a, IConst 0) => a IAdd32(IConst 0, b) => b

are translated to the following SML code:

PRIM(IAdd32(x1, x2)) => (case (bind x2) of (IConst b) => (case (bind x1) of (IConst a) => let val c = CA.iadd32(a, b) in dec x1; dec x2; OK(IConst c) end | a => if CA.eq(CA.iconst_0, b) then (dec x2; OK a) else FAIL (* end case *)) | _ => (case (bind x1) of (IConst a) => if CA.eq(CA.iconst_0, a) then (dec x1; OK b) else FAIL | => FAIL (* end case *)) (* end case *))

In this code, the bind function maps variables to their binding expression and the function dec decrements the argument usage count of a variable.