The MLTREE Language

Introduction

MLTree is the RTL-like intermediate language used to communicate between the MLRISC system and the compiler front-end.

In order to allow the client to specify operations that operate on operands of various widths, all integer and floating point operators in MLTREE now takes an additional width paramater.

For example,

   MV(32,t,
      ADDT(32,MULT(32,REG(32,b),REG(32,b)),
              MULT(32,MULT(32,LI(4),REG(32,a)),REG(32,c))))
computes t := b*b + 4*a*c, all in 32-bit precision; while

   MV(32,t,
      ADD(32,CVTI2I(32,SIGN_EXTEND,
               LOAD(8,ADD(32,REG(32,a),REG(32,i))))))
loads the byte in address a+i and sign extend it to a 32-bit value.

The Details

MLTREE_BASIS
signature MLTREE_BASIS =
sig
 
  datatype cond = LT | LTU | LE | LEU | EQ | NE | GE | GEU | GT | GTU 

  datatype fcond = ? | !<=> | == | ?= | !<> | !?>= | < | ?< | !>= | !?> |
                   <= | ?<= | !> | !?<= | > | ?> | !<= | !?< | >= | ?>= |
                   !< | !?= | <> | != | !? | <=> | ?<>

  datatype ext = SIGN_EXTEND | ZERO_EXTEND

  datatype rounding_mode = TO_NEAREST | TO_NEGINF | TO_POSINF | TO_ZERO

  type attribs = word

  type misc_op = {ty:int,name:string,attribs:attribs,hash:word}

  (* Should be datatypes, but FLINT does not optimize them well *)
  type ty = int
  type fty = int

end
MLTREE
signature MLTREE = sig
  structure Constant : CONSTANT
  structure PseudoOp : PSEUDO_OPS
  structure Region   : REGION
  structure BNames   : BLOCK_NAMES

  include MLTREE_BASIS

  type rextension 
  type fextension 

  type var = int (* variable *)
  type src = var (* source variable *)
  type dst = var (* destination variable *)
  type reg = var (* physical register *)

  (* phi-functions for SSA form *)
  datatype phi =
      PHI  of ty * dst * src list 
    | FPHI of fty * dst * src list 
    | CCPHI of dst * src list 

  (* aliasing declarations 
   * These are used to define physical register bindings for SSA names 
   *)
  datatype alias = ALIAS   of ty * var * reg  
                 | FALIAS  of fty * var * reg 
                 | CCALIAS of var * reg

  (* statements *)
  datatype stm =
      MV      of ty * dst * rexp	
    | CCMV    of dst * ccexp
    | FMV     of fty * dst * fexp	
    | COPY    of ty * dst list * src list
    | FCOPY   of fty * dst list * src list
    | JMP     of rexp * Label.label list
    | CALL    of rexp * mlrisc list * mlrisc list * Region.region
    | RET

    | STORE  of ty * rexp * rexp * Region.region	(* address, data *)
    | STORE_UNALIGNED of ty * rexp * rexp * Region.region
    | FSTORE of fty * rexp * fexp * Region.region	(* address, data *)
    | FSTORE_UNALIGNED of fty * rexp * fexp * Region.region
    | BCC    of cond * ccexp * Label.label 
    | FBCC   of fcond * ccexp * Label.label
    | ANNOTATION of stm * Annotations.annotation

      (* The following are used internally by SSA optimizations; 
       * The frontend should not generate these.
       *)
    | RTL of word ref * word * stm (* a RTL that has been cached *) 
    | RTLPHI of int (* a phi-function at block id *)
    | RTLPINNED of stm (* pinned statement *)
    | RTLPAR of stm list (* parallel execution *)
   
  and rexp = 
      REG    of ty * src

      (* sizes of constants are inferred by context *)
    | LI     of int   
    | LI32   of Word32.word
    | LI64   of Word64.word
    | LABEL  of LabelExp.labexp
    | CONST  of Constant.const

    | ADD    of ty * rexp * rexp
    | SUB    of ty * rexp * rexp 

      (* signed multiplication etc. *)
    | MULS   of ty * rexp * rexp
    | DIVS   of ty * rexp * rexp
    | REMS   of ty * rexp * rexp

      (* unsigned multiplication etc. *)
    | MULU   of ty * rexp * rexp
    | DIVU   of ty * rexp * rexp 
    | REMU   of ty * rexp * rexp

      (* trapping versions of above. These are all signed *)
    | ADDT   of ty * rexp * rexp 
    | SUBT   of ty * rexp * rexp 
    | MULT   of ty * rexp * rexp
    | DIVT   of ty * rexp * rexp
    | REMT   of ty * rexp * rexp 

    | ANDB   of ty * rexp * rexp
    | ORB    of ty * rexp * rexp
    | XORB   of ty * rexp * rexp
    | NOTB   of ty * rexp

    | SRA   of ty * rexp * rexp		(* value, shift *)
    | SRL   of ty * rexp * rexp
    | SLL   of ty * rexp * rexp

      (* type promotion *)
    | CVTI2I of ty * ext * rexp
    | CVTF2I of ty * rounding_mode * fexp

      (* 
       * COND(ty,cc,e1,e2):
       * Evaluate into either e1 or e2, depending on cc.  
       * Both e1 and e2 can be evaluated eagerly.
       *)
    | COND of ty * ccexp * rexp * rexp 

      (* integer load *)
    | LOAD of ty * rexp * Region.region
    | LOAD_UNALIGNED of ty * rexp * Region.region

    | SEQ of stm * rexp

    | EXTENSION of rextension * rexp list

    | MARK of rexp * Annotations.annotation

      (* Used in RTL *)
    | RTLPC (* the program counter; used for describing relative addressing *)
    | RTLMISC of misc_op ref * rexp list

  and fexp =
      FREG   of fty * src
    | FLOAD  of fty * rexp * Region.region
    | FLOAD_UNALIGNED  of fty * rexp * Region.region

    | FADD   of fty * fexp * fexp
    | FMUL   of fty * fexp * fexp
    | FSUB   of fty * fexp * fexp 
    | FDIV   of fty * fexp * fexp
    | FABS   of fty * fexp 
    | FNEG   of fty * fexp
    | FSQRT  of fty * fexp

    | CVTI2F of fty * ext * rexp
    | CVTF2F of fty * rounding_mode * fexp
    | FSEQ   of stm * fexp

    | FEXTENSION of fextension * fexp list

    | FMARK of fexp * Annotations.annotation

      (* used in RTL *)
    | RTLFMISC of misc_op ref * fexp list

  and ccexp =
      CC     of src
    | CMP    of ty * cond * rexp * rexp 
    | FCMP   of fty * fcond * fexp * fexp
    | CCMARK of ccexp * Annotations.annotation
    | RTLCCMISC of misc_op ref * ccexp list

  and mlrisc = CCR of ccexp | GPR of rexp | FPR of fexp

  datatype mltree = 
      BEGINCLUSTER
    | PSEUDO_OP of PseudoOp.pseudo_op
    | DEFINELABEL of Label.label
    | ENTRYLABEL of Label.label
    | CODE of stm list
    | ALIASDECLS of alias list
    | PHIFUNS of phi list
    | BLOCK_NAME of BNames.name
    | BLOCK_ANNOTATION of Annotations.annotation
    | ESCAPEBLOCK of mlrisc list 
    | ENDCLUSTER of int Intmap.intmap * Annotations.annotations

  exception Unsupported of string * rexp

end (* MLTREE *)


Allen Leung

Click to toggle
does not end with </html> tag
does not end with </body> tag
The output has ended thus: E="-2"> <ADDRESS> <A HREF="mailto:leunga@cs.nyu.edu">Allen Leung</A></ADDRESS> <BR> </BODY> </HTML>