MLRISC
MLRISC
Contributors
Requirements
How to Obtain MLRISC
Overview
Problem Statement
Contributions
MLRISC Based Compiler
MLRISC Intermediate Representation
MLRisc Generation
Back End Optimizations
Register Allocation
Machine Description
Garbage Collection Safety
System Integration
Optimizations
Graphical Interface
Line Counts
Systems Using MLRISC
Future Work
System
Architecture of MLRISC
The MLTREE Language
MLTree Extensions
MLTree Utilities
Instruction Selection
Assemblers
Machine Code Emitters
Delay Slot Filling
Span Dependency Resolution
The Graph Library
The Graph Visualization Library
Basic Compiler Graphs
The MLRISC IR
SSA Optimizations
ILP Optimizations
Optimizations for VLIW/EPIC Architectur...
Register Allocator
Back Ends
The Alpha Back End
The PA RISC Back End
The Sparc Back End
The Intel x86 Back End
The PowerPC Back End
The MIPS Back End
The TI C6x Back End
Basic Types
Annotations
Cells
Cluster
Client Defined Constants
Client Defined Pseudo Ops
Instructions
Instruction Streams
Label Expressions
Labels
Regions
Regmap

MLTree Utilities


MLTree Utilities
-Hashing, Equality, Pretty Printing
-MLTree Fold
-MLTree Rewriting
-MLTree Simplifier
The MLRISC system contains numerous utilities for working with MLTree datatypes. Some of the following utilizes are also useful for clients use:
MLTreeUtils
implements basic hashing, equality and pretty printing functions,
MLTreeFold
implements a fold function over the MLTree datatypes,
MLTreeRewrite
implements a generic rewriting engine,
MLTreeSimplify
implements a simplifier that performs algebraic simplification and constant folding.

Hashing, Equality, Pretty Printing

The functor 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:
 signature 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 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 =
 
The types hasher, equality, and printer represent functions for hashing, equality and pretty printing. These are defined as:
 
    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
       }
 
For example, to instantiate a Utils module for our DSPMLTree, we can write:
    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 _ _ = ""
      )
 

MLTree Fold

The functor MLTreeFold provides the basic functionality for implementing various forms of aggregation function over the MLTree datatypes. Its signature is
 signature MLTREE_FOLD =
 sig
    structure T : MLTREE
 
    val fold : 'b folder -> 'b folder
 end
 functor 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 =
 
The type folder is defined as:
    type 'b folder =
        { stm   : T.stm * 'b -> 'b,
          rexp  : T.rexp * 'b -> 'b,
          fexp  : T.fexp * 'b -> 'b, 
          ccexp : T.ccexp * 'b -> 'b
        }
 

MLTree Rewriting

The functor MLTreeRewrite implements a generic term rewriting engine which is useful for performing various transformations on MLTree terms. Its signature is
 signature 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 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 =
 
The type rewriter is defined in signature MLTREE as:
    type rewriter = 
        { stm   : T.stm -> T.stm,
          rexp  : T.rexp -> T.rexp,
          fexp  : T.fexp -> T.fexp,
          ccexp : T.ccexp -> T.ccexp
        } 
 

MLTree Simplifier

The functor MLTreeSimplify implements algebraic simplification and constant folding for MLTree. Its signature is:
 signature MLTREE_SIMPLIFIER =
 sig
 
    structure T : MLTREE
 
    val simplify  :
        { addressWidth : int } -> T.simplifier
    
 end
 functor 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 =
 
Where type simplifier is defined in signature MLTREE as:
    type simplifier =
        { stm   : T.stm -> T.stm,
          rexp  : T.rexp -> T.rexp,
          fexp  : T.fexp -> T.fexp,
          ccexp : T.ccexp -> T.ccexp
        }
 

Lal George
Allen Leung
SML/NJ Validate this page
Generated by mltex2html
Last modified: Thu Jan 9 19:38:15 EST 2003 by leunga@slinky