mlton/ssa/ssa-tree.sig

   1 (* Copyright (C) 2009,2017 Matthew Fluet.
   2  * Copyright (C) 1999-2008 Henry Cejtin, Matthew Fluet, Suresh
   3  *    Jagannathan, and Stephen Weeks.
   4  * Copyright (C) 1997-2000 NEC Research Institute.
   5  *
   6  * MLton is released under a BSD-style license.
   7  * See the file MLton-LICENSE for details.
   8  *)
   9
  10 signature SSA_TREE_STRUCTS =
  11    sig
  12       include ATOMS
  13    end
  14
  15 signature HANDLER =
  16    sig
  17       structure Label: LABEL
  18
  19       datatype t =
  20          Caller
  21        | Dead
  22        | Handle of Label.t
  23
  24       val equals: t * t -> bool
  25       val foldLabel: t * 'a * (Label.t * 'a -> 'a) -> 'a
  26       val foreachLabel: t * (Label.t -> unit) -> unit
  27       val layout: t -> Layout.t
  28       val map: t * (Label.t -> Label.t) -> t
  29    end
  30
  31 signature RETURN =
  32    sig
  33       structure Label: LABEL
  34
  35       structure Handler: HANDLER
  36       sharing Label = Handler.Label
  37
  38       datatype t =
  39          Dead
  40        | NonTail of {cont: Label.t,
  41                      handler: Handler.t}
  42        | Tail
  43
  44       val compose: t * t -> t
  45       val foldLabel: t * 'a * (Label.t * 'a -> 'a) -> 'a
  46       val foreachHandler: t * (Label.t -> unit) -> unit
  47       val foreachLabel: t * (Label.t -> unit) -> unit
  48       val layout: t -> Layout.t
  49       val map: t * (Label.t -> Label.t) -> t
  50    end
  51
  52 signature SSA_TREE =
  53    sig
  54       include SSA_TREE_STRUCTS
  55
  56       structure Type:
  57          sig
  58             type t
  59
  60             datatype dest =
  61                Array of t
  62              | CPointer
  63              | Datatype of Tycon.t
  64              | IntInf
  65              | Real of RealSize.t
  66              | Ref of t
  67              | Thread
  68              | Tuple of t vector
  69              | Vector of t
  70              | Weak of t
  71              | Word of WordSize.t
  72
  73             val array: t -> t
  74             val bool: t
  75             val checkPrimApp: {targs: t vector,
  76                                args: t vector,
  77                                prim: t Prim.t,
  78                                result: t} -> bool
  79             val cpointer: t
  80             val datatypee: Tycon.t -> t
  81             val dest: t -> dest
  82             val deArray: t -> t
  83             val deDatatype: t -> Tycon.t
  84             val deRef: t -> t
  85             val deTuple: t -> t vector
  86             val deTupleOpt: t -> t vector option
  87             val deVector: t -> t
  88             val deWeak: t -> t
  89             val deWord: t -> WordSize.t
  90             val deWordOpt: t -> WordSize.t option
  91             val equals: t * t -> bool
  92             val hash: t -> word
  93             val intInf: t
  94             val isTuple: t -> bool
  95             val isUnit: t -> bool
  96             val layout: t -> Layout.t
  97             val ofConst: Const.t -> t
  98             val plist: t -> PropertyList.t
  99             val real: RealSize.t -> t
 100             val reff: t -> t
 101             val thread: t
 102             val tuple: t vector -> t
 103             val vector: t -> t
 104             val weak: t -> t
 105             val word: WordSize.t -> t
 106             val unit: t
 107          end
 108
 109       structure Exp:
 110          sig
 111             datatype t =
 112                ConApp of {args: Var.t vector,
 113                           con: Con.t}
 114              | Const of Const.t
 115              | PrimApp of {args: Var.t vector,
 116                            prim: Type.t Prim.t,
 117                            targs: Type.t vector}
 118              | Profile of ProfileExp.t
 119              | Select of {offset: int,
 120                           tuple: Var.t}
 121              | Tuple of Var.t vector
 122              | Var of Var.t
 123
 124             val equals: t * t -> bool
 125             val foreachVar: t * (Var.t -> unit) -> unit
 126             val hash: t -> Word.t
 127             val layout: t -> Layout.t
 128             val maySideEffect: t -> bool
 129             val replaceVar: t * (Var.t -> Var.t) -> t
 130             val size: t -> int
 131             val unit: t
 132          end
 133
 134       structure Statement:
 135          sig
 136             datatype t = T of {exp: Exp.t,
 137                                ty: Type.t,
 138                                var: Var.t option}
 139
 140             val clear: t -> unit (* clear the var *)
 141             val exp: t -> Exp.t
 142             val layout: t -> Layout.t
 143             val profile: ProfileExp.t -> t
 144             val var: t -> Var.t option
 145          end
 146
 147       structure Cases:
 148          sig
 149             datatype t =
 150                Con of (Con.t * Label.t) vector
 151              | Word of WordSize.t * (WordX.t * Label.t) vector
 152
 153             val forall: t * (Label.t -> bool) -> bool
 154             val foreach: t * (Label.t -> unit) -> unit
 155             val hd: t -> Label.t
 156             val isEmpty: t -> bool
 157             val length: t -> int
 158             val map: t * (Label.t -> Label.t) -> t
 159          end
 160
 161       structure Handler: HANDLER
 162       sharing Handler.Label = Label
 163
 164       structure Return: RETURN
 165       sharing Return.Handler = Handler
 166
 167       structure Transfer:
 168          sig
 169             datatype t =
 170                Arith of {args: Var.t vector,
 171                          overflow: Label.t, (* Must be nullary. *)
 172                          prim: Type.t Prim.t,
 173                          success: Label.t, (* Must be unary. *)
 174                          ty: Type.t} (* int or word *)
 175              | Bug  (* MLton thought control couldn't reach here. *)
 176              | Call of {args: Var.t vector,
 177                         func: Func.t,
 178                         return: Return.t}
 179              | Case of {cases: Cases.t,
 180                         default: Label.t option, (* Must be nullary. *)
 181                         test: Var.t}
 182              | Goto of {args: Var.t vector,
 183                         dst: Label.t}
 184              (* Raise implicitly raises to the caller.
 185               * I.E. the local handler stack must be empty.
 186               *)
 187              | Raise of Var.t vector
 188              | Return of Var.t vector
 189              | Runtime of {args: Var.t vector,
 190                            prim: Type.t Prim.t,
 191                            return: Label.t} (* Must be nullary. *)
 192
 193             val equals: t * t -> bool
 194             val foreachFunc : t * (Func.t -> unit) -> unit
 195             val foreachLabel: t * (Label.t -> unit) -> unit
 196             val foreachLabelVar: t * (Label.t -> unit) * (Var.t -> unit) -> unit
 197             val foreachVar: t * (Var.t -> unit) -> unit
 198             val hash: t -> Word.t
 199             val layout: t -> Layout.t
 200             val replaceLabelVar: t * (Label.t -> Label.t) * (Var.t -> Var.t) -> t
 201             val replaceLabel: t * (Label.t -> Label.t) -> t
 202             val replaceVar: t * (Var.t -> Var.t) -> t
 203             val size: t -> int
 204          end
 205
 206       structure Block:
 207          sig
 208             datatype t =
 209                T of {args: (Var.t * Type.t) vector,
 210                      label: Label.t,
 211                      statements: Statement.t vector,
 212                      transfer: Transfer.t}
 213
 214             val args: t -> (Var.t * Type.t) vector
 215             val clear: t -> unit
 216             val label: t -> Label.t
 217             val layout: t -> Layout.t
 218             val sizeV: t vector * {sizeExp: Exp.t -> int, sizeTransfer: Transfer.t -> int} -> int
 219             val statements: t -> Statement.t vector
 220             val transfer: t -> Transfer.t
 221          end
 222
 223       structure Datatype:
 224          sig
 225             datatype t =
 226                T of {cons: {args: Type.t vector,
 227                             con: Con.t} vector,
 228                      tycon: Tycon.t}
 229
 230             val layout: t -> Layout.t
 231          end
 232
 233       structure Function:
 234          sig
 235             type t
 236
 237             val alphaRename: t -> t
 238             val blocks: t -> Block.t vector
 239             (* clear the plists for all bound variables and labels that appear
 240              * in the function, but not the function name's plist.
 241              *)
 242             val clear: t -> unit
 243             val controlFlow:
 244                t -> {graph: unit DirectedGraph.t,
 245                      labelNode: Label.t -> unit DirectedGraph.Node.t,
 246                      nodeBlock: unit DirectedGraph.Node.t -> Block.t}
 247             val dest: t -> {args: (Var.t * Type.t) vector,
 248                             blocks: Block.t vector,
 249                             mayInline: bool,
 250                             name: Func.t,
 251                             raises: Type.t vector option,
 252                             returns: Type.t vector option,
 253                             start: Label.t}
 254             (* dfs (f, v) visits the blocks in depth-first order, applying v b
 255              * for block b to yield v', then visiting b's descendents,
 256              * then applying v' ().
 257              *)
 258             val dfs: t * (Block.t -> unit -> unit) -> unit
 259             val dominatorTree: t -> Block.t Tree.t
 260             val foreachVar: t * (Var.t * Type.t -> unit) -> unit
 261             val layout: t -> Layout.t
 262             val layoutDot:
 263                t * (Var.t -> Layout.t) -> {destroy: unit -> unit,
 264                                            controlFlowGraph: Layout.t,
 265                                            dominatorTree: unit -> Layout.t,
 266                                            loopForest: unit -> Layout.t}
 267             val mayInline: t -> bool
 268             val name: t -> Func.t
 269             val new: {args: (Var.t * Type.t) vector,
 270                       blocks: Block.t vector,
 271                       mayInline: bool,
 272                       name: Func.t,
 273                       raises: Type.t vector option,
 274                       returns: Type.t vector option,
 275                       start: Label.t} -> t
 276             val profile: t * SourceInfo.t -> t
 277             val size: t * {sizeExp: Exp.t -> int, sizeTransfer: Transfer.t -> int} -> int
 278             val sizeMax: t * {max: int option, sizeExp: Exp.t -> int, sizeTransfer: Transfer.t -> int} -> int option
 279          end
 280
 281       structure Program:
 282          sig
 283             datatype t =
 284                T of {datatypes: Datatype.t vector,
 285                      functions: Function.t list,
 286                      globals: Statement.t vector,
 287                      main: Func.t (* Must be nullary. *)}
 288
 289             val clear: t -> unit
 290             val clearTop: t -> unit
 291             (* dfs (p, v) visits the functions in depth-first order, applying v f
 292              * for function f to yield v', then visiting f's descendents,
 293              * then applying v' ().
 294              *)
 295             val dfs: t * (Function.t -> unit -> unit) -> unit
 296             val foreachPrim: t * (Type.t Prim.t -> unit) -> unit
 297             val foreachVar: t * (Var.t * Type.t -> unit) -> unit
 298             val hasPrim: t * (Type.t Prim.t -> bool) -> bool
 299             val layouts: t * (Layout.t -> unit) -> unit
 300             val layoutStats: t -> Layout.t
 301             val mainFunction: t -> Function.t
 302          end
 303    end