\section{MLTree Utilities} The \MLRISC{} system contains numerous utilities for working with MLTree datatypes. Some of the following utilizes are also useful for clients use: \begin{description} \item[MLTreeUtils] implements basic hashing, equality and pretty printing functions, \item[MLTreeFold] implements a fold function over the MLTree datatypes, \item[MLTreeRewrite] implements a generic rewriting engine, \item[MLTreeSimplify] implements a simplifier that performs algebraic simplification and constant folding. \end{description} \subsubsection{Hashing, Equality, Pretty Printing} The functor \mlrischref{mltree/mltree-utils.sml}{MLTreeUtils} provides the basic utilities for hashing an MLTree term, comparing two MLTree terms for equality and pretty printing. The hashing and comparision functions are useful for building hash tables using MLTree datatype as keys. The signature of the functor is: \begin{SML} signature \mlrischref{mltree/mltree-utils.sig}{MLTREE_UTILS} = sig structure T : MLTREE (* * Hashing *) val hashStm : T.stm -> word val hashRexp : T.rexp -> word val hashFexp : T.fexp -> word val hashCCexp : T.ccexp -> word (* * Equality *) val eqStm : T.stm * T.stm -> bool val eqRexp : T.rexp * T.rexp -> bool val eqFexp : T.fexp * T.fexp -> bool val eqCCexp : T.ccexp * T.ccexp -> bool val eqMlriscs : T.mlrisc list * T.mlrisc list -> bool (* * Pretty printing *) val show : (string list * string list) -> T.printer val stmToString : T.stm -> string val rexpToString : T.rexp -> string val fexpToString : T.fexp -> string val ccexpToString : T.ccexp -> string end functor \mlrischref{mltree/mltree-utils.sml}{MLTreeUtils} (structure T : MLTREE (* Hashing extensions *) val hashSext : T.hasher -> T.sext -> word val hashRext : T.hasher -> T.rext -> word val hashFext : T.hasher -> T.fext -> word val hashCCext : T.hasher -> T.ccext -> word (* Equality extensions *) val eqSext : T.equality -> T.sext * T.sext -> bool val eqRext : T.equality -> T.rext * T.rext -> bool val eqFext : T.equality -> T.fext * T.fext -> bool val eqCCext : T.equality -> T.ccext * T.ccext -> bool (* Pretty printing extensions *) val showSext : T.printer -> T.sext -> string val showRext : T.printer -> T.ty * T.rext -> string val showFext : T.printer -> T.fty * T.fext -> string val showCCext : T.printer -> T.ty * T.ccext -> string ) : MLTREE_UTILS = \end{SML} The types \sml{hasher}, \sml{equality}, and \sml{printer} represent functions for hashing, equality and pretty printing. These are defined as: \begin{SML} type hasher = \{stm : T.stm -> word, rexp : T.rexp -> word, fexp : T.fexp -> word, ccexp : T.ccexp -> word \} type equality = \{ stm : T.stm * T.stm -> bool, rexp : T.rexp * T.rexp -> bool, fexp : T.fexp * T.fexp -> bool, ccexp : T.ccexp * T.ccexp -> bool \} type printer = \{ stm : T.stm -> string, rexp : T.rexp -> string, fexp : T.fexp -> string, ccexp : T.ccexp -> string, dstReg : T.ty * T.var -> string, srcReg : T.ty * T.var -> string \} \end{SML} For example, to instantiate a \sml{Utils} module for our \sml{DSPMLTree}, we can write: \begin{SML} structure U = MLTreeUtils (structure T = DSPMLTree fun hashSext \{stm, rexp, fexp, ccexp\} (FOR(i, a, b, s)) = Word.fromIntX i + rexp a + rexp b + stm s and hashRext \{stm, rexp, fexp, ccexp\} e = (case e of SUM(i,a,b,c) => Word.fromIntX i + rexp a + rexp b + rexp c | SADD(a,b) => rexp a + rexp b | SSUB(a,b) => 0w12 + rexp a + rexp b | SMUL(a,b) => 0w123 + rexp a + rexp b | SDIV(a,b) => 0w1245 + rexp a + rexp b ) fun hashFext _ _ = 0w0 fun hashCCext _ _ = 0w0 fun eqSext \{stm, rexp, fexp, ccexp\} (FOR(i, a, b, s), FOR(i', a', b', s')) = i=i' andalso rexp(a,a') andalso rexp(b,b') andalso stm(s,s') fun eqRext \{stm, rexp, fexp, ccexp\} (e,e') = (case (e,e') of (SUM(i,a,b,c),SUM(i',a',b',c')) => i=i' andalso rexp(a,a') andalso rexp(b,b') andalso stm(c,c') | (SADD(a,b),SADD(a',b')) => rexp(a,a') andalso rexp(b,b') | (SSUB(a,b),SSUB(a',b')) => rexp(a,a') andalso rexp(b,b') | (SMUL(a,b),SMUL(a',b')) => rexp(a,a') andalso rexp(b,b') | (SDIV(a,b),SDIV(a',b')) => rexp(a,a') andalso rexp(b,b') | _ => false ) fun eqFext _ _ = true fun eqCCext _ _ = true fun showSext \{stm, rexp, fexp, ccexp, dstReg, srcReg\} (FOR(i, a, b, s)) = "for("^dstReg i^":="^rexp a^".."^rexp b^")"^stm s fun ty t = "."^Int.toString t fun showRext \{stm, rexp, fexp, ccexp, dstReg, srcReg\} e = (case (t,e) of SUM(i,a,b,c) => "sum"^ty t^"("^dstReg i^":="^rexp a^".."^rexp b^")"^rexp c | SADD(a,b) => "sadd"^ty t^"("rexp a^","^rexp b^")" | SSUB(a,b) => "ssub"^ty t^"("rexp a^","^rexp b^")" | SMUL(a,b) => "smul"^ty t^"("rexp a^","^rexp b^")" | SDIV(a,b) => "sdiv"^ty t^"("rexp a^","^rexp b^")" ) fun showFext _ _ = "" fun showCCext _ _ = "" ) \end{SML} \subsubsection{MLTree Fold} The functor \mlrischref{mltree/mltree-fold.sml}{MLTreeFold} provides the basic functionality for implementing various forms of aggregation function over the MLTree datatypes. Its signature is \begin{SML} signature \mlrischref{mltree/mltree-fold.sig}{MLTREE_FOLD} = sig structure T : MLTREE val fold : 'b folder -> 'b folder end functor \mlrischref{mltree/mltree-fold.sml}{MLTreeFold} (structure T : MLTREE (* Extension mechnism *) val sext : 'b T.folder -> T.sext * 'b -> 'b val rext : 'b T.folder -> T.ty * T.rext * 'b -> 'b val fext : 'b T.folder -> T.fty * T.fext * 'b -> 'b val ccext : 'b T.folder -> T.ty * T.ccext * 'b -> 'b ) : MLTREE_FOLD = \end{SML} The type \newtype{folder} is defined as: \begin{SML} type 'b folder = \{ stm : T.stm * 'b -> 'b, rexp : T.rexp * 'b -> 'b, fexp : T.fexp * 'b -> 'b, ccexp : T.ccexp * 'b -> 'b \} \end{SML} \subsubsection{MLTree Rewriting} The functor \mlrischref{mltree/mltree-rewrite.sml}{MLTreeRewrite} implements a generic term rewriting engine which is useful for performing various transformations on MLTree terms. Its signature is \begin{SML} signature \mlrischref{mltree/mltree-rewrite.sig}{MLTREE_REWRITE} = sig structure T : MLTREE val rewrite : (* User supplied transformations *) \{ rexp : (T.rexp -> T.rexp) -> (T.rexp -> T.rexp), fexp : (T.fexp -> T.fexp) -> (T.fexp -> T.fexp), ccexp : (T.ccexp -> T.ccexp) -> (T.ccexp -> T.ccexp), stm : (T.stm -> T.stm) -> (T.stm -> T.stm) \} -> T.rewriters end functor \mlrischref{mltre/mltree-rewrite.sml}{MLTreeRewrite} (structure T : MLTREE (* Extension *) val sext : T.rewriter -> T.sext -> T.sext val rext : T.rewriter -> T.rext -> T.rext val fext : T.rewriter -> T.fext -> T.fext val ccext : T.rewriter -> T.ccext -> T.ccext ) : MLTREE_REWRITE = \end{SML} The type \newtype{rewriter} is defined in signature \mlrischref{mltree/mltree.sig}{MLTREE} as: \begin{SML} type rewriter = \{ stm : T.stm -> T.stm, rexp : T.rexp -> T.rexp, fexp : T.fexp -> T.fexp, ccexp : T.ccexp -> T.ccexp \} \end{SML} \subsubsection{MLTree Simplifier} The functor \mlrischref{mltree/mltree-simplify.sml}{MLTreeSimplify} implements algebraic simplification and constant folding for MLTree. Its signature is: \begin{SML} signature \mlrischref{mltree/mltree-simplify.sig}{MLTREE_SIMPLIFIER} = sig structure T : MLTREE val simplify : { addressWidth : int } -> T.simplifier end functor \mlrischref{mltree/mltree-simplify.sml}{MLTreeSimplifier} (structure T : MLTREE (* Extension *) val sext : T.rewriter -> T.sext -> T.sext val rext : T.rewriter -> T.rext -> T.rext val fext : T.rewriter -> T.fext -> T.fext val ccext : T.rewriter -> T.ccext -> T.ccext ) : MLTREE_SIMPLIFIER = \end{SML} Where type \newdef{simplifier} is defined in signature \mlrischref{mltree/mltree.sig}{MLTREE} as: \begin{SML} type simplifier = \{ stm : T.stm -> T.stm, rexp : T.rexp -> T.rexp, fexp : T.fexp -> T.fexp, ccexp : T.ccexp -> T.ccexp \} \end{SML}