Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/Doc/latex/mltree.tex
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/Doc/latex/mltree.tex

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 566, Mon Mar 6 07:20:58 2000 UTC revision 567, Mon Mar 6 22:17:41 2000 UTC
# Line 657  Line 657 
657     CCMARK : ccexp * Annotations.annotation -> ccexp     CCMARK : ccexp * Annotations.annotation -> ccexp
658     ANNOTATION : stm * Annotations.annotation -> stm     ANNOTATION : stm * Annotations.annotation -> stm
659  \end{SML}  \end{SML}
   
 \subsection{Extending the MLTree Language} \label{sec:mltree-extension}  
   
 The following constructors are available for extending the MLTree language  
 with client defined types:  
 \begin{SML}  
   EXT : sext -> stm  
   REXT : ty * rext -> rexp  
   FEXT : fty * fext -> fexp  
   CCEXT : ty * ccext -> ccexp  
 \end{SML}  
   
 The extension types \sml{sext, rext, fext, ccext} are defined in terms  
 of the client supplied extension types:  
 \begin{SML}  
    type sext = (stm, rexp, fexp, ccexp) Extension.sx  
    type rext = (stm, rexp, fexp, ccexp) Extension.rx  
    type fext = (stm, rexp, fexp, ccexp) Extension.fx  
    type ccext = (stm, rexp, fexp, ccexp) Extension.ccx  
 \end{SML}  
   
 Here is an example of how these extension constructors may be used.  
 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.  
   
 This is where the extension mechanism comes in.  
 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 simplication, 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.  
   
 \subsubsection{Compilation for MLTree Extensions}  
 Of course, after extending the MLTree language, the client must provide  
 an \emph{extension} module describing how to compile the extensions.  
 How this is done is described in Section~\ref{sec:instrsel}.  
   
 \subsection{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}  
   
   

Legend:
Removed from v.566  
changed lines
  Added in v.567

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0