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

Generated by mltex2html
Last modified: Fri Oct 11 18:19:52 UTC 2019 by buildd@x86-grnet-02