\section{MLTree Extensions} \label{sec:mltree-extension} Pattern matching over the MLTREE intermediate representation may not be sufficient to provide access to all the registers or operations provided on a specific architecture. MLTREE extensions is a method of extending the MLTREE intermediate language so that it is a better match for the target architecture. \subsection{Why Extensions} Pattern matching over the MLTREE intermediate representation may not be sufficient to provide access to all the registers or operations provided on a specific architecture. MLTREE extensions is a method of extending the MLTREE intermediate language so that it is a better match for the target architecture. For example there may be special registers to support the increment-and-test operation on loop indices, or support for complex mathematical functions such as square root, or access to hardware specific registers such as the current register window pointer on the SPARC architecture. It is not usually possible to write expression trees that would directly generate these instructions. Some complex operations can be generated by performing a peephole optimization over simpler instructions, however this is not always the most convenient or simple thing to do. \subsection{Cyclic Dependency} The easiest way to provide extensions is to parameterize the MLTREE interface with types that extend the various kinds of trees. Thus if the type \sml{sext} represented statement extensions, we might define MLTREE statement trees as : \begin{SML} datatype stm = ... | SEXT of sext * mlrisc list * stm list and mlrisc = GPR of rexp | FPR of fexp | CCR of ccexp \end{SML} where the constructor \sml{SEXT} applies the extension to a list of arguments. This approach is unsatisfactory in several ways, for example, if one wanted to extend MLTREEs with for-loops, then the following could be generated: \begin{SML} SEXT(FORLOOP, [GPR from, GPR to, GPR step], body) \end{SML} First, the loop arguments have to be wrapped up in \sml{GPR} and there is little self documentation on the order of elements that are arguments to the for-loop. It would be better to be able to write something like: \begin{SML} SEXT(FORLOOP\{from=f, to=t, step=s, body=b\}) \end{SML} Where \sml{f}, \sml{t}, and \sml{s} are \sml{rexp} trees representing the loop index start, end, and step size; \sml{b} is a stm list representing the body of the loop. Unfortunately, there is a cyclic dependency as MLTREEs are defined in terms of \sml{sext}, and {\tt sext} is defined in terms of MLTREEs. The usual way to deal with cyclic dependencies is to use polymorphic type variables. \subsection{MLTREE EXTENSION} The statement extension type \sml{sext}, is now a type constructor with arity four, i.e. \sml{('s, 'r, 'f, 'c) sx} where \sml{sx} is used instead of {\tt sext}, and \sml{'s}, \sml{'r}, \sml{'f}, and \sml{'c} represents MLTREE statement expressions, register expressions, floating point expressions, and condition code expressions. Thus the for-loop extension could be declared using something like: \begin{SML} datatype ('s,'r,'f,'c) sx = FORLOOP of \{from: 'r, to: 'r, step: 'r, body: 's\} \end{SML} and the MLTREE interface is defined as: \begin{SML} signature MLTREE = sig type ('s, 'r, 'f, 'c) sx datatype stm = = ... | SEXT of sext withtype sext = (stm, rexp, fexp, cexp) sx end \end{SML} where \sml{sext} is the user defined statement extension but the type variables have been instantiated to the final form the the MLTREE \sml{stm}, \sml{rexp}, \sml{fexp}, and \sml{cexp} components. \subsection{Compilation} There are dedicated modules that perform pattern matching over MLTREEs and emit native instructions, and similar modules must be written for extensions. However, the same kinds of choices used in regular MLTREE patterns must be repeated for extensions. For example, one may define an extension for the Intel IA32 of the form: \begin{SML} datatype ('s,'r,'f,'c) sx = PUSHL of 'r | POPL of 'r | ... \end{SML} that translate directly to the Intel push and pop instructions; the operands in each case are either memory locations or registers, but immediates are allowed in the case of \sml{PUSHL}. Considerable effort has been invested into pattern matching the extensive set of addressing modes for the Intel architecture, and one would like to reuse this when compiling extensions. The pattern matching functions are exposed by a set of functions exported from the instruction selection module, and provided in the MLTREE interface. They are: \begin{SML} struture I : INSTRUCTIONS datatype reducer = REDUCER of \{ reduceRexp : rexp -> reg, reduceFexp : fexp -> reg, reduceCCexp : ccexp -> reg, reduceStm : stm * an list -> unit, operand : rexp -> I.operand, reduceOperand : I.operand -> reg, addressOf : rexp -> I.addressing_mode, emit : I.instr * an list -> unit, instrStream : (I.instr, I.regmap, I.cellset) stream, mltreeStream : (stm, I.regmap, mlrisc list) stream \} \end{SML} where \sml{I} is the native instruction set. \begin{description} \item[\tt reduceRexp]: reduces an MLTREE \sml{rexp} to a register, and similarly for \sml{reduceFexp} and \sml{reduceCCexp}. \item[\tt reduceStm]: reduces an MLTREE \sml{stm} to a set of instructions that implement the set of statements. \item[\tt operand]: reduced an MLTREE \sml{rexp} into an instruction operand --- usually an immediate or memory address. \item[\tt operand]: moves a native operand into a register. \item[\tt addressOf]: reduces an MLTREE \sml{rexp} into a memory address. \item[\tt emit]: emits an instruction together with an annotation. \item[\tt instrStream]: is the native instruction output stream, and \item[\tt mltreeStream]: is the MLTREE output stream. \end{description} Each extension must provide a function \sml{compileSext} that compiles a statement extension into native instructions. In the \sml{MLTREE_EXTENSION_COMP} interface we have: \begin{SML} val compileSext: reducer -> {stm: MLTREE.sexp, an:MLTREE.an list} -> unit \end{SML} The use of extensions must follow a special structure. \begin{enumerate} \item A module defining the extension type using a type constructor of arity four. Let us call this structure \sml{ExtTy} and must match the \sml{MLTREE_EXTENSION} interface. \item The extension module must be used to specialize MLTREEs. \item A module that describes how to compile the extension must be created, and must match the \sml{MLTREE_EXTENSION_COMP} interace. This module will typically be functorized over the MLTREE interface. Let us call the result of applying the functor, \sml{ExtComp}. \item The extension compiler must be passed as a parameter to the instruction selection module that will invoke it whenever an extension is seen. \end{enumerate} \subsection{Multiple Extensions} Multiple extensions are handled in a similar fashion, except that the extension type used to specialize MLTREEs is a tagged union of the individual extensions. The functor to compile the extension dispatches to the compilation modules for the individual extensions. \subsection{Example} Suppose you are in the process of writing a compiler for a digital signal processing(\newdef{DSP}) programming language using the MLRISC framework. This wonderful language that you are developing allows the programmer to specify high level looping and iteration, and aggregation constructs that are common in DSP applications. Furthermore, since saturated and fixed point arithmetic are common constructs in DSP applications, the language and consequently the compiler should directly support these operators. For simplicity, we would like to have a unified intermediate representation that can be used to directly represent high level constructs in our language, and low level constructs that are already present in MLTree. Since, MLTree does not directly support these constructs, it seems that it is not possible to use MLRISC for such a compiler infrastructure without substantial rewrite of the core components. Let us suppose that for illustration that we would like to implement high level looping and aggregation constructs such as \begin{verbatim} for i := lower bound ... upper bound body x := sum{i := lower bound ... upper bound} expression \end{verbatim} together with saturated arithmetic mentioned above. Here is a first attempt: \begin{SML} structure DSPMLTreeExtension struct structure Basis = MLTreeBasis datatype ('s,'r,'f,'c) sx = FOR of Basis.var * 'r * 'r * 's and ('s,'r,'f,'c) rx = SUM of Basis.var * 'r * 'r * 'r | SADD of 'r * 'r | SSUB of 'r * 'r | SMUL of 'r * 'r | SDIV of 'r * 'r type ('s,'r,'f,'c) fx = unit type ('s,'r,'f,'c) ccx = unit end structure DSPMLTree : MLTreeF (structure Extension = DSPMLTreeExtension ... ) \end{SML} In the above signature, we have defined two new datatypes \newtype{sx} and \newtype{rx} that are used for representing the DSP statement and integer expression extensions. Integer expression extensions include the high level sum construct, and the low levels saturated arithmetic operators. The recursive type definition is necessary to ``inject'' these new constructors into the basic MLTree definition. The following is an example of how these new constructors that we have defined can be used. Suppose the source program in our DSP language is: \begin{verbatim} for i := a ... b { s := sadd(s, table[i]); } \end{verbatim} \noindent where \verb|sadd| is the saturated add operator. For simplicity, let us also assume that all operations and addresses are in 32-bits. Then the translation of the above into our extended DSP-MLTree could be: \begin{SML} EXT(FOR(\(i\), REG(32, \(a\)), REG(32, \(b\)), MV(32, \(s\), REXT(32, SADD(REG(32, \(s\)), LOAD(32, ADD(32, REG(32, \(table\)), SLL(32, REG(32, \(i\)), LI 2)), \(region\))))) )) \end{SML} One potential short coming of our DSP extension to MLTree is that the extension does not allow any further extensions. This restriction may be entirely satisfactory if DSP-MLTree is only used in your compiler applications and no where else. However, if DSP-MLTree is intended to be an extension library for MLRISC, then we must build in the flexibility for extension. This can be done in the same way as in the base MLTree definition, like this: \begin{SML} functor ExtensibleDSPMLTreeExtension (Extension : \mlrischref{mltree/mltree-extension.sig}{MLTREE_EXTENSION}) = struct structure Basis = MLTreeBasis structure Extension = Extension datatype ('s,'r,'f,'c) sx = FOR of Basis.var * 'r * 'r * 's | EXT of ('s,'r,'f,'c) Extension.sx and ('s,'r,'f,'c) rx = SUM of Basis.var * 'r * 'r * 'r | SADD of 'r * 'r | SSUB of 'r * 'r | SMUL of 'r * 'r | SDIV of 'r * 'r | REXT of ('s,'r,'f,'c) Extension.rx withtype ('s,'r,'f,'c) fx = ('s,'r,'f,'c) Extension.fx and ('s,'r,'f,'c) ccx = ('s,'r,'f,'c) Extension.ccx end \end{SML} As in MLTREE, we provide two new extension constructors \verb|EXT| and \verb|REXT| in the definition of \sml{DSP_MLTREE}, which can be used to further enhance the extended MLTREE language.