Diff of /sml/branches/SMLNJ/src/MLRISC/ir-moved/dominator.sml

Parent Directory | Revision Log | Patch

	revision 428, Wed Sep 8 09:47:00 1999 UTC	revision 429, Wed Sep 8 09:47:00 1999 UTC
#	Line 1	Line 1
1	(*	(*
2	* Computation of the dominator tree representation from the	* Computation of the dominator tree representation from the
3	* control flow graph.   Can also compute the DJgraph.	* control flow graph.  I'm using the old algorithm by Lengauer and Tarjan.
	* I'm using the old algorithm by Lengauer and Tarjan.
4	*	*
5	* Note: to deal with CFG with endless loops,	* Note: to deal with CFG with endless loops,
6	* by default we assume instructions are postdominated by STOP.	* by default we assume instructions are postdominated by STOP.
7	*	*
	* The algorithm for dominance frontier and iterated dominance
	* frontier is due to Sreedhar, Gao and Lee.   The algorithm as cited
	* uses the DJgraph.  In order not to bother with constructing and
	* maintaining the DJgraph, we'll just use a combination of the dominator tree
	* and the original cfg.
	*
8	* -- Allen	* -- Allen
9	*)	*)
10
#	Line 27	Line 20
20
21	exception Dominator	exception Dominator
22
23	datatype 'n dom_node =	type node = G.node_id
	DOM of { node : 'n, level : int, preorder : int, postorder : int }
	type dominator_methods =
	{ dominates              : G.node_id * G.node_id -> bool,
	immediately_dominates  : G.node_id * G.node_id -> bool,
	strictly_dominates     : G.node_id * G.node_id -> bool,
	postdominates          : G.node_id * G.node_id -> bool,
	immediately_postdominates : G.node_id * G.node_id -> bool,
	strictly_postdominates : G.node_id * G.node_id -> bool,
	control_equivalent     : G.node_id * G.node_id -> bool,
	idom         : G.node_id -> G.node_id,
	idoms        : G.node_id -> G.node_id list,
	doms         : G.node_id -> G.node_id list,
	ipdom        : G.node_id -> G.node_id,
	ipdoms       : G.node_id -> G.node_id list,
	pdoms        : G.node_id -> G.node_id list,
	dom_lca      : Graph.node_id * Graph.node_id -> Graph.node_id,
	pdom_lca     : Graph.node_id * Graph.node_id -> Graph.node_id,
	dom_level    : Graph.node_id -> int,
	pdom_level   : Graph.node_id -> int,
	control_equivalent_partitions : unit -> Graph.node_id list list
	}
24
25	type ('n,'e,'g) dom_info =	datatype ('n,'e,'g) dom_info =
26	{ cfg : ('n,'e,'g) G.graph, edge_label : string,	INFO of
27	methods : (unit -> dominator_methods) ref,	{ cfg : ('n,'e,'g) G.graph,
28		edge_label : string,
29		levelsMap  : int Array.array,
30		preorder   : int Array.array option ref,
31		postorder  : int Array.array option ref,
32	max_levels : int ref	max_levels : int ref
33	}	}
34	type ('n,'e,'g) dominator_tree     =	type ('n,'e,'g) dominator_tree     = ('n,unit,('n,'e,'g) dom_info) G.graph
35	('n dom_node,unit,('n,'e,'g) dom_info) G.graph	type ('n,'e,'g) postdominator_tree = ('n,unit,('n,'e,'g) dom_info) G.graph
	type ('n,'e,'g) postdominator_tree =
	('n dom_node,unit,('n,'e,'g) dom_info) G.graph
36
37	fun graph_info (G.GRAPH dom) : ('n,'e,'g) dom_info = #graph_info dom	fun graph_info (G.GRAPH dom) : ('n,'e,'g) dom_info = #graph_info dom
38
39	fun cfg dom        = #cfg(graph_info dom)	fun cfg(G.GRAPH dom) = let val INFO{cfg,...} = #graph_info dom in cfg end
40	fun max_levels dom = !(#max_levels(graph_info dom))	fun max_levels(G.GRAPH dom) =
41	fun methods dom    = (!(#methods(graph_info dom)))()	let val INFO{max_levels,...} = #graph_info dom in !max_levels end
42
43	(*	(*
44	* This is the main Lengauer/Tarjan algorithm	* This is the main Lengauer/Tarjan algorithm
45	*)	*)
46	fun tarjan_lengauer (name,edge_label) (CFG as (G.GRAPH cfg)) =	fun tarjan_lengauer (name,edge_label) (origCFG,CFG as (G.GRAPH cfg)) =
47	let val N           = #order cfg ()	let val N           = #order cfg ()
48	val M           = #capacity cfg ()	val M           = #capacity cfg ()
49	val r           = case #entries cfg () of	val r           = case #entries cfg () of
#	Line 81	Line 54
54	val dfnum       = A.array (M, ~1)	val dfnum       = A.array (M, ~1)
55	val vertex      = A.array (N, ~1)	val vertex      = A.array (N, ~1)
56	val parent      = A.array (M, ~1)	val parent      = A.array (M, ~1)
57	val bucket      = A.array (M, [])    : G.node_id list array	val bucket      = A.array (M, []) : node list array
58	val semi        = A.array (M, r)	val semi        = A.array (M, r)
59	val ancestor    = A.array (M, ~1)	val ancestor    = A.array (M, ~1)
60	val idom        = A.array (M, r)	val idom        = A.array (M, r)
61	val samedom     = A.array (M, ~1)	val samedom     = A.array (M, ~1)
62	val best        = A.array (M, ~1)	val best        = A.array (M, ~1)
63	val max_levels  = ref 0	val max_levels  = ref 0
64	val dom_info    = { cfg = CFG, edge_label = edge_label,	val levelsMap   = A.array(M,~1000000)
65	methods = ref(fn _ => raise G.Graph "dom"),	val dom_info    = INFO{ cfg        = origCFG,
66	max_levels = max_levels }	edge_label = edge_label,
67		levelsMap  = levelsMap,
68		preorder   = ref NONE,
69		postorder  = ref NONE,
70		max_levels = max_levels
71		}
72	val Dom as G.GRAPH domtree = GI.graph(name, dom_info, N)	val Dom as G.GRAPH domtree = GI.graph(name, dom_info, N)
73
74	(* step 1	(* step 1
#	Line 201	Line 179
179	val _ = dumpArray "idom" idom	val _ = dumpArray "idom" idom
180	*)	*)
181
182	(* Create the nodes of the dominator tree *)	(* Create the nodes/edges of the dominator tree *)
183	fun addNode ~1 = ()	fun buildGraph(i,maxLevel) =
184	| addNode i  = let val v = A.sub(vertex,i)	if i < N then
185	in  #add_node domtree (v,	let val v = A.sub(vertex,i)
186	DOM { node      = #node_info cfg v,	in  #add_node domtree (v,#node_info cfg v);
	level     = 0,
	preorder  = 0,
	postorder = 0
	});
	addNode (i-1)
	end
	val _ = addNode (N-1)
	(* Create the edges of the dominator tree *)
	val _ = #forall_nodes domtree
	(fn (v,_) =>
187	if v <> r then	if v <> r then
188	let val w = A.sub(idom,v)	let val w = A.sub(idom,v)
189	in  #add_edge domtree (w,v,()) end	val l = A.sub(levelsMap,w)+1
190	else  ())	in  A.update(levelsMap,v,l);
191		#add_edge domtree (w,v,());
192	(* Compute the level/preorder/postorder numbers *)	buildGraph(i+1,l)
193	fun computeNumbering(level,preorder,postorder,n) =	end
194	let val DOM { node, ... } = #node_info domtree n	else
195	val (preorder',postorder',max_level) =	(A.update(levelsMap,v,0);
196	computeNumbering'(level+1,preorder+1,postorder,	buildGraph(i+1,maxLevel)
197	#succ domtree n)	)
	in  #add_node domtree (n,
	DOM{node=node,level=level,
	preorder=preorder,postorder=postorder'});
	(preorder',postorder'+1,max_level)
	end
	and computeNumbering'(level,preorder,postorder,[]) =
	(preorder,postorder,level)
	| computeNumbering'(level,preorder,postorder,n::ns) =
	let val (preorder',postorder',max1) =
	computeNumbering(level,preorder,postorder,n)
	val (preorder',postorder',max2) =
	computeNumbering'(level,preorder',postorder',ns)
	in  (preorder',postorder',Int.max(max1,max2))
198	end	end
199		else maxLevel
200
201	val (_,_,max) = computeNumbering(0,0,0,r)	val max = buildGraph(0,1)
202	in	in
203	max_levels := max+1;	max_levels := max+1;
204	#set_entries domtree [r];	#set_entries domtree [r];
#	Line 253	Line 206
206	Dom	Dom
207	end	end
208
	(* The algorithm specialized to making dominators and postdominators *)
209
210	fun dominator_trees (cfg as (G.GRAPH g)) =	(* The algorithm specialized to making dominators and postdominators *)
211	let val Dom as G.GRAPH D =	fun makeDominator cfg = tarjan_lengauer("Dom","dom") (cfg,cfg)
212	tarjan_lengauer ("Dom","dom") cfg	fun makePostdominator cfg =
213	val PDom as G.GRAPH P =	tarjan_lengauer("PDom","pdom") (cfg,Rev.rev_view cfg)
	tarjan_lengauer ("PDom","pdom") (Rev.rev_view cfg)
214
215	fun immediately_dominates (i,j) =	(* Methods *)
	case #in_edges D j of
	(k,_,_)::_ => i = k
	|  _          => false
216
217	fun immediately_postdominates (i,j) =	(* Does i immediately dominate j? *)
218		fun immediately_dominates (G.GRAPH D) (i,j) =
219	case #in_edges D j of	case #in_edges D j of
220	(k,_,_)::_ => i = k	(k,_,_)::_ => i = k
221	|  _          => false	|  _          => false
222
223	(* immediate dominator of n *)	(* immediate dominator of n *)
224	fun idom n = case #in_edges D n of	fun idom (G.GRAPH D) n =
225		case #in_edges D n of
226	(n,_,_)::_ => n	(n,_,_)::_ => n
227	|  _          => ~1	|  _          => ~1
228
229	fun idoms n = #succ D n	(* nodes that n immediately dominates *)
230		fun idoms (G.GRAPH D) = #succ D
231
232	fun subtree (succ,[],S) = S	(* nodes that n dominates *)
233	| subtree (succ,n::ns,S) = subtree(succ,succ n,	fun doms (G.GRAPH D) =
234	subtree(succ,ns,n::S))	let fun subtree ([],S) = S
235		| subtree (n::ns,S) = subtree(#succ D n,subtree(ns,n::S))
236	fun dom_level i =	in  fn n => subtree([n], [])
237	let val DOM{level,...} = #node_info D i in level end	end
238	fun pdom_level i =
239	let val DOM{level,...} = #node_info P i in level end
240		fun prePostOrders(G.GRAPH dom) =
241	(* Least common ancestors *)	let val INFO{ preorder,postorder,...} = #graph_info dom
242	fun dom_lca(a,b) =	(* Compute the preorder/postorder numbers *)
243	let val l_a = dom_level a	fun computeThem() =
244	val l_b = dom_level b	let val N   = #capacity dom ()
245		val [r] = #entries dom ()
246		val pre  = A.array(N,~1000000)
247		val post = A.array(N,~1000000)
248		fun computeNumbering(preorder,postorder,n) =
249		let val (preorder',postorder') =
250		computeNumbering'(preorder+1,postorder,#out_edges dom n)
251		in  A.update(pre,n,preorder);
252		A.update(post,n,postorder');
253		(preorder',postorder'+1)
254		end
255
256		and computeNumbering'(preorder,postorder,[]) =
257		(preorder,postorder)
258		| computeNumbering'(preorder,postorder,(_,n,_)::es) =
259		let val (preorder',postorder') =
260		computeNumbering(preorder,postorder,n)
261		val (preorder',postorder') =
262		computeNumbering'(preorder',postorder',es)
263		in  (preorder',postorder')
264		end
265		in  computeNumbering(0,0,r) ;
266		preorder := SOME pre;
267		postorder := SOME post;
268		(pre,post)
269		end
270		in  case (!preorder,!postorder) of
271		(SOME pre,SOME post) => (pre,post)
272		| _ => computeThem()
273		end
274
275		(* Level *)
276		fun level (G.GRAPH D) =
277		let val INFO{levelsMap,...} = #graph_info D
278		in  fn i => A.sub(levelsMap,i) end
279
280		(* Least common ancestor *)
281		fun lca (Dom as G.GRAPH D) (a,b) =
282		let val l_a = level Dom a
283		val l_b = level Dom b
284	fun idom i = case #in_edges D i of (j,_,_)::_ => j	fun idom i = case #in_edges D i of (j,_,_)::_ => j
285	fun up_a(a,l_a) = if l_a > l_b then up_a(idom a,l_a-1) else a	fun up_a(a,l_a) = if l_a > l_b then up_a(idom a,l_a-1) else a
286	fun up_b(b,l_b) = if l_b > l_a then up_b(idom b,l_b-1) else b	fun up_b(b,l_b) = if l_b > l_a then up_b(idom b,l_b-1) else b
287	val a = up_a(a,l_a)	val a = up_a(a,l_a)
288	val b = up_b(b,l_b)	val b = up_b(b,l_b)
289	fun up_both(a,b) = if a = b then a else up_both(idom a,idom b)	fun up_both(a,b) = if a = b then a else up_both(idom a,idom b)
290	in  up_both(a,b)	in  up_both(a,b) end
	end
	fun pdom_lca(a,b) =
	let val l_a = pdom_level a
	val l_b = pdom_level b
	fun ipdom i = case #in_edges P i of (j,_,_)::_ => j
	fun up_a(a,l_a) = if l_a > l_b then up_a(ipdom a,l_a-1) else a
	fun up_b(b,l_b) = if l_b > l_a then up_b(ipdom b,l_b-1) else b
	val a = up_a(a,l_a)
	val b = up_b(b,l_b)
	fun up_both(a,b) = if a = b then a else up_both(ipdom a,ipdom b)
	in  up_both(a,b)
	end
	fun doms n = subtree(#succ D, [n], [])
	(* immediate postdominator of n *)
	fun ipdom n = case #in_edges P n of
	(n,_,_)::_ => n
	|  _          => ~1
	fun ipdoms n = #succ P n
	fun pdoms n  = subtree(#succ P, [n], [])
291
292	(* is x and ancestor of y in D?	(* is x and ancestor of y in D?
293	* This is true iff PREORDER(x) <= PREORDER(y) and	* This is true iff PREORDER(x) <= PREORDER(y) and
294	*                  POSTORDER(x) >= POSTORDER(y)	*                  POSTORDER(x) >= POSTORDER(y)
295	*)	*)
296	fun dominates (x,y) =	fun dominates Dom =
297	let val DOM { preorder = a, postorder = b, ... } = #node_info D x	let val (pre,post) = prePostOrders Dom
298	val DOM { preorder = c, postorder = d, ... } = #node_info D y	in  fn (x,y) =>
299		let val a = A.sub(pre,x)
300		val b = A.sub(post,x)
301		val c = A.sub(pre,y)
302		val d = A.sub(post,y)
303	in  a <= c andalso b >= d	in  a <= c andalso b >= d
304	end	end
305		end
306
307	fun strictly_dominates (x,y) =	fun strictly_dominates Dom =
308	let val DOM { preorder = a, postorder = b, ... } = #node_info D x	let val (pre,post) = prePostOrders Dom
309	val DOM { preorder = c, postorder = d, ... } = #node_info D y	in  fn (x,y) =>
310		let val a = A.sub(pre,x)
311		val b = A.sub(post,x)
312		val c = A.sub(pre,y)
313		val d = A.sub(post,y)
314	in  a < c andalso b > d	in  a < c andalso b > d
315	end	end
	fun postdominates (x,y) =
	let val DOM { preorder = a, postorder = b, ... } = #node_info P x
	val DOM { preorder = c, postorder = d, ... } = #node_info P y
	in  a <= c andalso b >= d
316	end	end
317
318	fun strictly_postdominates (x,y) =	fun control_equivalent (Dom,PDom) =
319	let val DOM { preorder = a, postorder = b, ... } = #node_info P x	let val dom  = dominates Dom
320	val DOM { preorder = c, postorder = d, ... } = #node_info P y	val pdom = dominates PDom
321	in  a < c andalso b > d	in  fn (x,y) => dom(x,y) andalso pdom(y,x) orelse dom(y,x) andalso pdom(x,y)
322	end	end
323
	fun control_equivalent (x,y) =
	dominates(x,y) andalso postdominates(y,x) orelse
	dominates(y,x) andalso postdominates(x,y)
324	(* control equivalent partitions	(* control equivalent partitions
325	* two nodes a and b are control equivalent iff	* two nodes a and b are control equivalent iff
326	*    a dominates b and b postdominates a (or vice versa)	*    a dominates b and b postdominates a (or vice versa)
#	Line 360	Line 329
329	*          k not pdom i	*          k not pdom i
330	* This algorithm runs in O(n)	* This algorithm runs in O(n)
331	*)	*)
332	fun control_equivalent_partitions() =	fun control_equivalent_partitions (G.GRAPH D,PDom) =
333	let fun walkDom([],S) = S	let val postdominates = dominates PDom
334		fun walkDom([],S) = S
335	| walkDom(n::waiting,S) =	| walkDom(n::waiting,S) =
336	let val (waiting,S,S') =	let val (waiting,S,S') =
337	findEquiv(n,#out_edges D n,waiting,S,[n])	findEquiv(n,#out_edges D n,waiting,S,[n])
#	Line 381	Line 351
351	equivSets	equivSets
352	end	end
353
354	(* Methods for dominators/postdominator manipulation *)	fun levelsMap(G.GRAPH dom) =
355	val methods = { dominates              = dominates,	let val INFO{levelsMap,...} = #graph_info dom
356	strictly_dominates     = strictly_dominates,	in  levelsMap end
	postdominates          = postdominates,
	strictly_postdominates = strictly_postdominates,
	control_equivalent     = control_equivalent,
	idom                   = idom,
	idoms                  = idoms,
	doms                   = doms,
	ipdom                  = ipdom,
	ipdoms                 = ipdoms,
	pdoms                  = pdoms,
	dom_level              = dom_level,
	pdom_level             = pdom_level,
	dom_lca                = dom_lca,
	pdom_lca               = pdom_lca,
	immediately_dominates  = immediately_dominates,
	immediately_postdominates = immediately_postdominates,
	control_equivalent_partitions =
	control_equivalent_partitions
	}
	fun get_methods _ = methods
	in
	#methods (#graph_info D) := get_methods;
	#methods (#graph_info P) := get_methods;
	(Dom, PDom)
	end
	fun levels(G.GRAPH dom) =
	let val levels = A.array(#capacity dom (),~1)
	in  #forall_nodes dom (fn (i,DOM{level,...}) => A.update(levels,i,level));
	levels
	end
357
358	fun idoms(G.GRAPH dom) =	fun idomsMap(G.GRAPH dom) =
359	let val idoms = A.array(#capacity dom (),~1)	let val idoms = A.array(#capacity dom (),~1)
360	in  #forall_edges dom (fn (i,j,_) => A.update(idoms,j,i));	in  #forall_edges dom (fn (i,j,_) => A.update(idoms,j,i));
361	idoms	idoms

---

Colored Diff Long Colored Diff Unidiff Context Diff Side by Side

Legend: Removed from v.428   changed lines   Added in v.429

---

root@smlnj-gforge.cs.uchicago.edu	ViewVC Help
Powered by ViewVC 1.0.0