Diff of /sml/branches/SMLNJ/src/MLRISC/ra/ra-graph.sml

Parent Directory | Revision Log | Patch

	revision 468, Wed Nov 10 22:42:52 1999 UTC	revision 469, Wed Nov 10 22:42:52 1999 UTC
#	Line 1	Line 1
1	(*	(*
2	* Graph data structure used by the modular register allocator.	* This is the new interference graph used by the new register allocator.
3	*	*
4	* -- Allen	* -- Allen
5	*)	*)
#	Line 7	Line 7
7	structure RAGraph : RA_GRAPH =	structure RAGraph : RA_GRAPH =
8	struct	struct
9
10	structure BM = TriangularBitMatrix	(* A new bit matrix datatype.
11		* We use the small representation whenever possible to save space.
12		*)
13		datatype bitMatrix = BM of {table:hashTable,
14		elems:int ref,
15		edges:int}
16		and hashTable = SMALL of word list Array.array ref * word
17		| LARGE of bucket Array.array ref * word
18		(* | BITMATRIX of Word8Array.array *)
19		and bucket = NIL | B of int * int * bucket
20
21		type priority = int
22
23		type programPoint = int
24
25		type cost = int
26
27	datatype interferenceGraph =	datatype interferenceGraph =
28	GRAPH of { bitMatrix    : BM.bitMatrix,	GRAPH of { bitMatrix    : bitMatrix ref,
29	nodes        : node Intmap.intmap,	nodes        : node Intmap.intmap,
30	regmap       : int Intmap.intmap,	regmap       : int Intmap.intmap,
31	K            : int,	K            : int,
32	firstPseudoR : int,	firstPseudoR : int,
33		dedicated    : bool Array.array,
34	getreg       :	getreg       :
35	{pref:int list,stamp:int,proh:int Array.array} -> int,	{pref:int list,stamp:int,proh:int Array.array} -> int,
36		getpair       :
37		{pref:int list, stamp:int, proh:int Array.array} -> int,
38	proh         : int Array.array,	proh         : int Array.array,
39	stamp        : int ref,	stamp        : int ref,
40
41	(* Info to undo a spill when an optimistic spill has occurred *)	(* Info to undo a spill when an optimistic spill has occurred *)
42	spillFlag    : bool ref,	spillFlag    : bool ref,
43	undoInfo     : (node * moveStatus ref) list ref	spilledRegs  : bool Intmap.intmap,
44		trail        : trailInfo ref,
45
46		showReg      : int -> string,
47		numRegs      : int,
48		maxRegs      : unit -> int,
49
50		deadCopies   : int list ref,
51		spillLoc     : int ref
52	}	}
53
54	and moveStatus = MOVE | COALESCED | CONSTRAINED | LOST | WORKLIST	and moveStatus = MOVE | COALESCED | CONSTRAINED | LOST | WORKLIST
#	Line 29	Line 56
56	and move =	and move =
57	MV of {src : node,                  (* source register of move *)	MV of {src : node,                  (* source register of move *)
58	dst : node,                  (* destination register of move *)	dst : node,                  (* destination register of move *)
59		(* kind: moveKind, *)        (* what kind of move *)
60		cost : cost,                 (* cost *)
61	status : moveStatus ref      (* coalesced? *)	status : moveStatus ref      (* coalesced? *)
62	}	}
63
64	and nodeStatus = REMOVED | PSEUDO | ALIASED of node | COLORED of int	and moveKind = REG_TO_REG      (* register to register *)
65		| EVEN_TO_REG     (* even register in pair to register *)
66		| ODD_TO_REG      (* odd register in pair to register *)
67		| PAIR_TO_PAIR    (* register pair to register pair *)
68		| REG_TO_EVEN     (* register to even register in pair *)
69		| REG_TO_ODD      (* register to odd register in pair *)
70
71		and nodeStatus =
72		PSEUDO                (* pseudo register *)
73		| REMOVED               (* removed from the interference graph *)
74		| ALIASED of node       (* coalesced *)
75		| COLORED of int        (* colored *)
76		| SPILLED of int        (* spilled *)
77		| ALIASED_SPILL of node (* aliased spill node *)
78
79	and node =	and node =
80	NODE of { number : int,             (* node number *)	NODE of { number : int,             (* node number *)
#	Line 40	Line 82
82	movelist: move list ref,  (* moves associated with this node *)	movelist: move list ref,  (* moves associated with this node *)
83	degree : int ref,         (* current degree *)	degree : int ref,         (* current degree *)
84	color : nodeStatus ref,   (* status *)	color : nodeStatus ref,   (* status *)
85	adj : node list ref       (* adjacency list *)	adj : node list ref,      (* adjacency list *)
86	}	pri : priority ref,       (* priority *)
87	(*	movecost : cost ref,      (* move cost *)
88	* The valid transitions for a node are:	(* pair : bool, *)        (* register pair? *)
89	* PSEUDO -> REMOVED                  % during simplify	defs : programPoint list ref,
90	* PSEUDO -> ALIASED(n)               % during coalescing	uses : programPoint list ref
	* REMOVED -> COLORED(r)              % assigning a color
	*
	*  ... all others are illegal.
	*)
	type 'a worklist = 'a list
	type nodelist    = node worklist
	type movelist    = move worklist
	type ('sim,'move,'freeze,'spill,'stack) lists =
	{simplifyWkl: 'sim,   (* nodes that can be simplified *)
	moveWkl : 'move,     (* moves to be considered for coalescing *)
	freezeWkl : 'freeze, (* all n, s.t. degree(n)<K and moveRelated(n) *)
	spillWkl : 'spill,   (* all n, s.t. degree(n)>=K  *)
	stack : 'stack       (* nodes removed from the graph *)
91	}	}
92
93	type worklists = (nodelist,movelist,nodelist,nodelist,nodelist) lists	and trailInfo = END | UNDO of node * moveStatus ref * trailInfo
94
95	exception Nodes	exception Nodes
96
97		fun error msg = MLRiscErrorMsg.error("RAGraph", msg)
98
99		val stampCounter = ref 0
100
101		(* Create a new bitMatrix *)
102		fun roundSize size =
103		let fun f(x, shift) =
104		if x >= size then (x, Word.>>(shift, 0w1))
105		else f(x+x, shift+0w1)
106		in f(64, 0w6) end
107
108		val max = Word.<<(0w1,Word.>>(Word.fromInt Word.wordSize,0w1))
109		val _ = if max < Word.<<(0w1,0w15)
110		then error "word size too small" else ()
111
112		fun newBitMatrix{edges, maxRegs} =
113		let val table =
114		(* if maxRegs < 1024 then
115		let val denseBytes  = (maxRegs * (maxRegs + 1) + 15) div 16
116		in  BITMATRIX(Word8Array.array(denseBytes,0w0))
117		end
118		else *)
119		let val (tableSize, shift) = roundSize edges
120		in  if Word.fromInt maxRegs < max then
121		SMALL(ref(Array.array(tableSize,[])),shift)
122		else
123		LARGE(ref(Array.array(tableSize,NIL)),shift)
124		end
125		in  BM{table=table, elems=ref 0, edges=edges}
126		end
127
128	(* Create a new interference graph *)	(* Create a new interference graph *)
129	fun newGraph{nodes,regmap,K,firstPseudoR,getreg,numRegs} =	fun newGraph{nodes,regmap,K,firstPseudoR,dedicated,
130		getreg,getpair,showReg,maxRegs,numRegs,proh} =
131	let (* lower triangular bitmatrix primitives *)	let (* lower triangular bitmatrix primitives *)
132	(* NOTE: The average ratio of E/N is about 16 *)	(* NOTE: The average ratio of E/N is about 16 *)
133	val bitMatrix = BM.new numRegs	val bitMatrix = newBitMatrix{edges=numRegs * 16,maxRegs=maxRegs()}
134	in  GRAPH{ bitMatrix    = bitMatrix,	in  if !stampCounter > 10000000 then stampCounter := 0 else ();
135		GRAPH{ bitMatrix    = ref bitMatrix,
136	nodes        = nodes,	nodes        = nodes,
137	regmap       = regmap,	regmap       = regmap,
138	K            = K,	K            = K,
139	firstPseudoR = firstPseudoR,	firstPseudoR = firstPseudoR,
140		dedicated    = dedicated,
141	getreg       = getreg,	getreg       = getreg,
142	proh         = Array.array(firstPseudoR,~1),	getpair      = getpair,
143	stamp        = ref 0,	proh         = proh,
144		stamp        = stampCounter,
145	spillFlag    = ref false,	spillFlag    = ref false,
146	undoInfo     = ref []	spilledRegs  = Intmap.new(2,Nodes),
147		trail        = ref END,
148		showReg      = Int.toString,
149		numRegs      = numRegs,
150		maxRegs      = maxRegs,
151		deadCopies   = ref [],
152		spillLoc     = ref ~2
153	}	}
154	end	end
155
156	end	end

---

Colored Diff Long Colored Diff Unidiff Context Diff Side by Side

Legend: Removed from v.468   changed lines   Added in v.469

---

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