[hcoop/debian/mlton.git] / mlton / ssa / ssa-tree2.sig

(* Copyright (C) 2009,2017 Matthew Fluet.
 * Copyright (C) 1999-2008 Henry Cejtin, Matthew Fluet, Suresh
 *    Jagannathan, and Stephen Weeks.
 * Copyright (C) 1997-2000 NEC Research Institute.
 *
 * MLton is released under a BSD-style license.
 * See the file MLton-LICENSE for details.
 *)

signature SSA_TREE2_STRUCTS = 
   sig
      include ATOMS
   end

signature SSA_TREE2 = 
   sig
      include SSA_TREE2_STRUCTS

      structure Prod:
         sig
            type 'a t

            val allAreImmutable: 'a t -> bool
            val allAreMutable: 'a t -> bool
            val dest: 'a t -> {elt: 'a, isMutable: bool} vector
            val elt: 'a t * int -> 'a
            val empty: unit -> 'a t
            val fold: 'a t * 'b * ('a * 'b -> 'b) -> 'b
            val foreach: 'a t * ('a -> unit) -> unit
            val isEmpty: 'a t -> bool
            val keepAllMap: 'a t * ('a -> 'b option) -> 'b t
            val layout: 'a t * ('a -> Layout.t) -> Layout.t
            val length: 'a t -> int
            val make: {elt: 'a, isMutable: bool} vector -> 'a t
            val map: 'a t * ('a -> 'b) -> 'b t
            val someIsImmutable: 'a t -> bool
            val someIsMutable: 'a t -> bool
            val sub: 'a t * int -> {elt: 'a, isMutable: bool}
         end

      structure ObjectCon:
         sig
            datatype t =
               Con of Con.t
             | Tuple
             | Vector

            val isVector: t -> bool
            val layout: t -> Layout.t
         end

      structure Type:
         sig
            type t

            datatype dest =
               CPointer
             | Datatype of Tycon.t
             | IntInf
             | Object of {args: t Prod.t,
                          con: ObjectCon.t}
             | Real of RealSize.t
             | Thread
             | Weak of t
             | Word of WordSize.t

            val array1: t -> t
            val bool: t
            val conApp: Con.t * t Prod.t -> t
            val checkPrimApp: {args: t vector,
                               prim: t Prim.t,
                               result: t} -> bool
            val cpointer: t
            val datatypee: Tycon.t -> t
            val dest: t -> dest
            val deVector1: t -> t
            val deVectorOpt: t -> t Prod.t option
            val equals: t * t -> bool
            val intInf: t
            val isVector: t -> bool
            val isUnit: t -> bool
            val layout: t -> Layout.t
            val object: {args: t Prod.t, con: ObjectCon.t} -> t
            val ofConst: Const.t -> t
            val plist: t -> PropertyList.t
            val real: RealSize.t -> t
            val reff1: t -> t
            val thread: t
            val tuple: t Prod.t -> t
            val vector: t Prod.t -> t
            val vector1: t -> t
            val weak: t -> t
            val word: WordSize.t -> t
            val unit: t
         end

      structure Base:
         sig
            datatype 'a t =
               Object of 'a
             | VectorSub of {index: 'a,
                             vector: 'a}

            val foreach: 'a t * ('a -> unit) -> unit
            val layout: 'a t * ('a -> Layout.t) -> Layout.t
            val map: 'a t * ('a -> 'b) -> 'b t
            val object: 'a t -> 'a
         end

      structure Exp:
         sig
            datatype t =
               Const of Const.t
             | Inject of {sum: Tycon.t,
                          variant: Var.t}
             | Object of {args: Var.t vector,
                          con: Con.t option}
             | PrimApp of {args: Var.t vector,
                           prim: Type.t Prim.t}
             | Select of {base: Var.t Base.t,
                          offset: int}
             | Var of Var.t

            val equals: t * t -> bool
            val foreachVar: t * (Var.t -> unit) -> unit
            val hash: t -> Word.t
            val layout: t -> Layout.t
            val maySideEffect: t -> bool
            val replaceVar: t * (Var.t -> Var.t) -> t
            val unit: t
         end

      structure Statement:
         sig
            datatype t =
               Bind of {exp: Exp.t,
                        ty: Type.t,
                        var: Var.t option}
             | Profile of ProfileExp.t
             | Update of {base: Var.t Base.t,
                          offset: int,
                          value: Var.t}

            val clear: t -> unit (* clear the var *)
            val foreachDef: t * (Var.t * Type.t -> unit) -> unit
            val foreachUse: t * (Var.t -> unit) -> unit
            val layout: t -> Layout.t
            val profile: ProfileExp.t -> t
            val replaceUses: t * (Var.t -> Var.t) -> t
         end

      structure Cases:
         sig
            datatype t =
               Con of (Con.t * Label.t) vector
             | Word of WordSize.t * (WordX.t * Label.t) vector

            val forall: t * (Label.t -> bool) -> bool
            val foreach: t * (Label.t -> unit) -> unit
            val hd: t -> Label.t
            val isEmpty: t -> bool
            val map: t * (Label.t -> Label.t) -> t
         end

      structure Handler: HANDLER
      sharing Handler.Label = Label

      structure Return: RETURN
      sharing Return.Handler = Handler

      structure Transfer:
         sig
            datatype t =
               Arith of {args: Var.t vector,
                         overflow: Label.t, (* Must be nullary. *)
                         prim: Type.t Prim.t,
                         success: Label.t, (* Must be unary. *)
                         ty: Type.t} (* int or word *)
             | Bug  (* MLton thought control couldn't reach here. *)
             | Call of {args: Var.t vector,
                        func: Func.t,
                        return: Return.t}
             | Case of {cases: Cases.t,
                        default: Label.t option, (* Must be nullary. *)
                        test: Var.t}
             | Goto of {args: Var.t vector,
                        dst: Label.t}
             (* Raise implicitly raises to the caller.  
              * I.E. the local handler stack must be empty.
              *)
             | Raise of Var.t vector
             | Return of Var.t vector
             | Runtime of {args: Var.t vector,
                           prim: Type.t Prim.t,
                           return: Label.t} (* Must be nullary. *)

            val equals: t * t -> bool
            val foreachFunc : t * (Func.t -> unit) -> unit
            val foreachLabel: t * (Label.t -> unit) -> unit
            val foreachLabelVar: t * (Label.t -> unit) * (Var.t -> unit) -> unit
            val foreachVar: t * (Var.t -> unit) -> unit
            val hash: t -> Word.t 
            val layout: t -> Layout.t
            val replaceLabelVar: t * (Label.t -> Label.t) * (Var.t -> Var.t) -> t
            val replaceLabel: t * (Label.t -> Label.t) -> t
            val replaceVar: t * (Var.t -> Var.t) -> t
         end

      structure Block:
         sig
            datatype t =
               T of {args: (Var.t * Type.t) vector,
                     label: Label.t,
                     statements: Statement.t vector,
                     transfer: Transfer.t}

            val args: t -> (Var.t * Type.t) vector
            val clear: t -> unit
            val label: t -> Label.t
            val layout: t -> Layout.t
            val transfer: t -> Transfer.t
         end

      structure Datatype:
         sig
            datatype t =
               T of {cons: {args: Type.t Prod.t,
                            con: Con.t} vector,
                     tycon: Tycon.t}

            val layout: t -> Layout.t
         end

      structure Function:
         sig
            type t

            val alphaRename: t -> t
            val blocks: t -> Block.t vector
            (* clear the plists for all bound variables and labels that appear
             * in the function, but not the function name's plist.
             *)
            val clear: t -> unit
            val controlFlow:
               t -> {graph: unit DirectedGraph.t,
                     labelNode: Label.t -> unit DirectedGraph.Node.t,
                     nodeBlock: unit DirectedGraph.Node.t -> Block.t}
            val dest: t -> {args: (Var.t * Type.t) vector,
                            blocks: Block.t vector,
                            mayInline: bool,
                            name: Func.t,
                            raises: Type.t vector option,
                            returns: Type.t vector option,
                            start: Label.t}
            (* dfs (f, v) visits the blocks in depth-first order, applying v b
             * for block b to yield v', then visiting b's descendents,
             * then applying v' ().
             *)
            val dfs: t * (Block.t -> unit -> unit) -> unit
            val dominatorTree: t -> Block.t Tree.t
            val foreachVar: t * (Var.t * Type.t -> unit) -> unit
            val layout: t -> Layout.t
            val layoutDot:
               t * (Var.t -> Layout.t) -> {destroy: unit -> unit,
                                           controlFlowGraph: Layout.t,
                                           dominatorTree: unit -> Layout.t,
                                           loopForest: unit -> Layout.t}
            val name: t -> Func.t
            val new: {args: (Var.t * Type.t) vector,
                      blocks: Block.t vector,
                      mayInline: bool,
                      name: Func.t,
                      raises: Type.t vector option,
                      returns: Type.t vector option,
                      start: Label.t} -> t
            val profile: t * SourceInfo.t -> t
         end

      structure Program:
         sig
            datatype t =
               T of {datatypes: Datatype.t vector,
                     functions: Function.t list,
                     globals: Statement.t vector,
                     main: Func.t (* Must be nullary. *)}

            val clear: t -> unit
            val clearTop: t -> unit
            (* dfs (p, v) visits the functions in depth-first order, applying v f
             * for function f to yield v', then visiting f's descendents,
             * then applying v' ().
             *)
            val dfs: t * (Function.t -> unit -> unit) -> unit
            val foreachPrimApp:
               t * ({args: Var.t vector, prim: Type.t Prim.t} -> unit) -> unit
            val foreachVar: t * (Var.t * Type.t -> unit) -> unit
            val hasPrim: t * (Type.t Prim.t -> bool) -> bool
            val layouts: t * (Layout.t -> unit) -> unit
            val layoutStats: t -> Layout.t
         end
   end
Commit	Line	Data
7f918cf1 CE	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_TREE2_STRUCTS =
	11	sig
	12	include ATOMS
	13	end
	14
	15	signature SSA_TREE2 =
	16	sig
	17	include SSA_TREE2_STRUCTS
	18
	19	structure Prod:
	20	sig
	21	type 'a t
	22
	23	val allAreImmutable: 'a t -> bool
	24	val allAreMutable: 'a t -> bool
	25	val dest: 'a t -> {elt: 'a, isMutable: bool} vector
	26	val elt: 'a t * int -> 'a
	27	val empty: unit -> 'a t
	28	val fold: 'a t * 'b * ('a * 'b -> 'b) -> 'b
	29	val foreach: 'a t * ('a -> unit) -> unit
	30	val isEmpty: 'a t -> bool
	31	val keepAllMap: 'a t * ('a -> 'b option) -> 'b t
	32	val layout: 'a t * ('a -> Layout.t) -> Layout.t
	33	val length: 'a t -> int
	34	val make: {elt: 'a, isMutable: bool} vector -> 'a t
	35	val map: 'a t * ('a -> 'b) -> 'b t
	36	val someIsImmutable: 'a t -> bool
	37	val someIsMutable: 'a t -> bool
	38	val sub: 'a t * int -> {elt: 'a, isMutable: bool}
	39	end
	40
	41	structure ObjectCon:
	42	sig
	43	datatype t =
	44	Con of Con.t
	45	\| Tuple
	46	\| Vector
	47
	48	val isVector: t -> bool
	49	val layout: t -> Layout.t
	50	end
	51
	52	structure Type:
	53	sig
	54	type t
	55
	56	datatype dest =
	57	CPointer
	58	\| Datatype of Tycon.t
	59	\| IntInf
	60	\| Object of {args: t Prod.t,
	61	con: ObjectCon.t}
	62	\| Real of RealSize.t
	63	\| Thread
	64	\| Weak of t
65	\| Word of WordSize.t
66
67	val array1: t -> t
68	val bool: t
69	val conApp: Con.t * t Prod.t -> t
70	val checkPrimApp: {args: t vector,
71	prim: t Prim.t,
72	result: t} -> bool
73	val cpointer: t
74	val datatypee: Tycon.t -> t
75	val dest: t -> dest
76	val deVector1: t -> t
77	val deVectorOpt: t -> t Prod.t option
78	val equals: t * t -> bool
79	val intInf: t
80	val isVector: t -> bool
81	val isUnit: t -> bool
82	val layout: t -> Layout.t
83	val object: {args: t Prod.t, con: ObjectCon.t} -> t
84	val ofConst: Const.t -> t
85	val plist: t -> PropertyList.t
86	val real: RealSize.t -> t
87	val reff1: t -> t
88	val thread: t
89	val tuple: t Prod.t -> t
90	val vector: t Prod.t -> t
91	val vector1: t -> t
92	val weak: t -> t
93	val word: WordSize.t -> t
94	val unit: t
95	end
96
97	structure Base:
98	sig
99	datatype 'a t =
100	Object of 'a
101	\| VectorSub of {index: 'a,
102	vector: 'a}
103
104	val foreach: 'a t * ('a -> unit) -> unit
105	val layout: 'a t * ('a -> Layout.t) -> Layout.t
106	val map: 'a t * ('a -> 'b) -> 'b t
107	val object: 'a t -> 'a
108	end
109
110	structure Exp:
111	sig
112	datatype t =
113	Const of Const.t
114	\| Inject of {sum: Tycon.t,
115	variant: Var.t}
116	\| Object of {args: Var.t vector,
117	con: Con.t option}
118	\| PrimApp of {args: Var.t vector,
119	prim: Type.t Prim.t}
120	\| Select of {base: Var.t Base.t,
121	offset: int}
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 unit: t
131	end
132
133	structure Statement:
134	sig
135	datatype t =
136	Bind of {exp: Exp.t,
137	ty: Type.t,
138	var: Var.t option}
139	\| Profile of ProfileExp.t
140	\| Update of {base: Var.t Base.t,
141	offset: int,
142	value: Var.t}
143
144	val clear: t -> unit (* clear the var *)
145	val foreachDef: t * (Var.t * Type.t -> unit) -> unit
146	val foreachUse: t * (Var.t -> unit) -> unit
147	val layout: t -> Layout.t
148	val profile: ProfileExp.t -> t
149	val replaceUses: t * (Var.t -> Var.t) -> t
150	end
151
152	structure Cases:
153	sig
154	datatype t =
155	Con of (Con.t * Label.t) vector
156	\| Word of WordSize.t * (WordX.t * Label.t) vector
157
158	val forall: t * (Label.t -> bool) -> bool
159	val foreach: t * (Label.t -> unit) -> unit
160	val hd: t -> Label.t
161	val isEmpty: t -> bool
162	val map: t * (Label.t -> Label.t) -> t
163	end
164
165	structure Handler: HANDLER
166	sharing Handler.Label = Label
167
168	structure Return: RETURN
169	sharing Return.Handler = Handler
170
171	structure Transfer:
172	sig
173	datatype t =
174	Arith of {args: Var.t vector,
175	overflow: Label.t, (* Must be nullary. *)
176	prim: Type.t Prim.t,
177	success: Label.t, (* Must be unary. *)
178	ty: Type.t} (* int or word *)
179	\| Bug (* MLton thought control couldn't reach here. *)
180	\| Call of {args: Var.t vector,
181	func: Func.t,
182	return: Return.t}
183	\| Case of {cases: Cases.t,
184	default: Label.t option, (* Must be nullary. *)
185	test: Var.t}
186	\| Goto of {args: Var.t vector,
187	dst: Label.t}
188	(* Raise implicitly raises to the caller.
189	* I.E. the local handler stack must be empty.
190	*)
191	\| Raise of Var.t vector
192	\| Return of Var.t vector
193	\| Runtime of {args: Var.t vector,
194	prim: Type.t Prim.t,
195	return: Label.t} (* Must be nullary. *)
196
197	val equals: t * t -> bool
198	val foreachFunc : t * (Func.t -> unit) -> unit
199	val foreachLabel: t * (Label.t -> unit) -> unit
200	val foreachLabelVar: t * (Label.t -> unit) * (Var.t -> unit) -> unit
201	val foreachVar: t * (Var.t -> unit) -> unit
202	val hash: t -> Word.t
203	val layout: t -> Layout.t
204	val replaceLabelVar: t * (Label.t -> Label.t) * (Var.t -> Var.t) -> t
205	val replaceLabel: t * (Label.t -> Label.t) -> t
206	val replaceVar: t * (Var.t -> Var.t) -> t
207	end
208
209	structure Block:
210	sig
211	datatype t =
212	T of {args: (Var.t * Type.t) vector,
213	label: Label.t,
214	statements: Statement.t vector,
215	transfer: Transfer.t}
216
217	val args: t -> (Var.t * Type.t) vector
218	val clear: t -> unit
219	val label: t -> Label.t
220	val layout: t -> Layout.t
221	val transfer: t -> Transfer.t
222	end
223
224	structure Datatype:
225	sig
226	datatype t =
227	T of {cons: {args: Type.t Prod.t,
228	con: Con.t} vector,
229	tycon: Tycon.t}
230
231	val layout: t -> Layout.t
232	end
233
234	structure Function:
235	sig
236	type t
237
238	val alphaRename: t -> t
239	val blocks: t -> Block.t vector
240	(* clear the plists for all bound variables and labels that appear
241	* in the function, but not the function name's plist.
242	*)
243	val clear: t -> unit
244	val controlFlow:
245	t -> {graph: unit DirectedGraph.t,
246	labelNode: Label.t -> unit DirectedGraph.Node.t,
247	nodeBlock: unit DirectedGraph.Node.t -> Block.t}
248	val dest: t -> {args: (Var.t * Type.t) vector,
249	blocks: Block.t vector,
250	mayInline: bool,
251	name: Func.t,
252	raises: Type.t vector option,
253	returns: Type.t vector option,
254	start: Label.t}
255	(* dfs (f, v) visits the blocks in depth-first order, applying v b
256	* for block b to yield v', then visiting b's descendents,
257	* then applying v' ().
258	*)
259	val dfs: t * (Block.t -> unit -> unit) -> unit
260	val dominatorTree: t -> Block.t Tree.t
261	val foreachVar: t * (Var.t * Type.t -> unit) -> unit
262	val layout: t -> Layout.t
263	val layoutDot:
264	t * (Var.t -> Layout.t) -> {destroy: unit -> unit,
265	controlFlowGraph: Layout.t,
266	dominatorTree: unit -> Layout.t,
267	loopForest: unit -> Layout.t}
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	end
278
279	structure Program:
280	sig
281	datatype t =
282	T of {datatypes: Datatype.t vector,
283	functions: Function.t list,
284	globals: Statement.t vector,
285	main: Func.t (* Must be nullary. *)}
286
287	val clear: t -> unit
288	val clearTop: t -> unit
289	(* dfs (p, v) visits the functions in depth-first order, applying v f
290	* for function f to yield v', then visiting f's descendents,
291	* then applying v' ().
292	*)
293	val dfs: t * (Function.t -> unit -> unit) -> unit
294	val foreachPrimApp:
295	t * ({args: Var.t vector, prim: Type.t Prim.t} -> unit) -> unit
296	val foreachVar: t * (Var.t * Type.t -> unit) -> unit
297	val hasPrim: t * (Type.t Prim.t -> bool) -> bool
298	val layouts: t * (Layout.t -> unit) -> unit
299	val layoutStats: t -> Layout.t
300	end
301	end