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

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	(** Graph coloring register allocation.	(*
2	** Implements the 'iterated register coalescing' scheme described	* This is the new interference graph used by the new register allocator.
3	** in POPL'96, and TOPLAS v18 #3, pp 325-353.	*
4	**	* -- Allen
5	** RA CORE defines the core of the register allocator.	*)
	** This basically means the enableMove, coalesce, simplify and freeze phases.
	** These are separated out from the rest for more modularity
	** and customizability.
	**
	** -- Allen
	**)
6
7	signature RA_GRAPH =	signature RA_GRAPH =
8	sig	sig
#	Line 18	Line 11
11	* The following are the data structures used in the register allocator.	* The following are the data structures used in the register allocator.
12	*)	*)
13
14	structure BM : BITMATRIX	(* A new bit matrix datatype.
15		* We use the small representation whenever possible to save space.
16		*)
17		datatype bitMatrix = BM of {table:hashTable,
18		elems:int ref,
19		edges:int}
20		and hashTable = SMALL of word list Array.array ref * word
21		| LARGE of bucket Array.array ref * word
22		(* | BITMATRIX of Word8Array.array *)
23		and bucket = NIL | B of int * int * bucket
24
25	exception Nodes	exception Nodes
26
27		type priority = int
28		type cost = int
29
30		(*
31		* The following represent a program point in the program.
32		* As a convention, program point is computed by
33		*
34		*    block number * 16384 + instruction number
35		*
36		* The last instruction in the block is numbered 1, i.e. the instruction
37		* numbering is in reverse.  The number 0 is reserved for "live-out".
38		*
39		* This implies that there can be a maximum of 16k-1 instructions
40		* per basic block/hyperblock, plus a maximum of 32k blocks.
41		* Let's hope this is enough. (I'm not kidding, aggressive inlining
42		* and unrolling can produce large blocks.)
43		*)
44		type programPoint = int
45
46	datatype interferenceGraph =	datatype interferenceGraph =
47	GRAPH of { bitMatrix    : BM.bitMatrix,	GRAPH of
48		{ bitMatrix    : bitMatrix ref,
49	nodes        : node Intmap.intmap,	nodes        : node Intmap.intmap,
50	regmap       : int Intmap.intmap,	regmap       : int Intmap.intmap,
51	K            : int,	K            : int,
52	firstPseudoR : int,	firstPseudoR : int,
53	getreg       :	dedicated    : bool Array.array,
54	{pref:int list,stamp:int,proh:int Array.array} -> int,	getreg       : {pref:int list, stamp:int, proh:int Array.array} -> int,
55		getpair      : {pref:int list, stamp:int, proh:int Array.array} -> int,
56	proh         : int Array.array,	proh         : int Array.array,
57	stamp        : int ref,	stamp        : int ref,
58
59	(* Info to undo a spill when an optimistic spill has occurred *)	(* Info to undo a spill when an optimistic spill has occurred *)
60	spillFlag    : bool ref,	spillFlag    : bool ref,
61	undoInfo     : (node * moveStatus ref) list ref
62		spilledRegs  : bool Intmap.intmap, (*registers that have been spilled*)
63		trail        : trailInfo ref,
64
65		(* how to pretty print a register *)
66		showReg      : int -> string,
67
68		(* how many registers there are? *)
69		numRegs      : int,
70		maxRegs      : unit -> int,
71
72		(* dead copies *)
73		deadCopies   : int list ref,
74
75		(* spill locations *)
76		spillLoc     : int ref
77	}	}
78
79	and moveStatus = MOVE | COALESCED | CONSTRAINED | LOST | WORKLIST	and moveStatus = MOVE         (* not yet coalesced *)
80		| COALESCED    (* coalesced *)
81		| CONSTRAINED  (* src and target intefere *)
82		| LOST         (* frozen moves *)
83		| WORKLIST     (* on the move worklist *)
84
85	and move =	and move =
86	MV of {src : node,                  (* source register of move *)	MV of {src : node,                  (* source register of move *)
87	dst : node,                  (* destination register of move *)	dst : node,                  (* destination register of move *)
88		(*kind   : moveKind, *)      (* kind of move *)
89		cost   : cost,               (* cost *)
90	status : moveStatus ref      (* coalesced? *)	status : moveStatus ref      (* coalesced? *)
91	}	}
92
93	and nodeStatus = REMOVED | PSEUDO | ALIASED of node | COLORED of int	and moveKind = REG_TO_REG      (* register to register *)
94		| EVEN_TO_REG     (* even register in pair to register *)
95		| ODD_TO_REG      (* odd register in pair to register *)
96		| PAIR_TO_PAIR    (* register pair to register pair *)
97		| REG_TO_EVEN     (* register to even register in pair *)
98		| REG_TO_ODD      (* register to odd register in pair *)
99
100		and nodeStatus =
101		PSEUDO                (* pseudo register *)
102		| REMOVED               (* removed from the interference graph *)
103		| ALIASED of node       (* coalesced *)
104		| COLORED of int        (* colored *)
105		| SPILLED of int        (* spilled *)
106		| ALIASED_SPILL of node (* aliased spill node *)
107
108	and node =	and node =
109	NODE of { number : int,             (* node number *)	NODE of { number : int,             (* node number *)
#	Line 53	Line 111
111	movelist: move list ref,  (* moves associated with this node *)	movelist: move list ref,  (* moves associated with this node *)
112	degree : int ref,         (* current degree *)	degree : int ref,         (* current degree *)
113	color : nodeStatus ref,   (* status *)	color : nodeStatus ref,   (* status *)
114	adj : node list ref       (* adjacency list *)	adj : node list ref,      (* adjacency list *)
115		pri : priority ref,       (* priority *)
116		movecost : cost ref,      (* move cost *)
117		(* pair : bool, *)        (* register pair? *)
118		defs : programPoint list ref,
119		uses : programPoint list ref
120	}	}
	(*
	* The valid transitions for a node are:
	* PSEUDO -> REMOVED                  % during simplify
	* PSEUDO -> ALIASED(n)               % during coalescing
	* REMOVED -> COLORED(r)              % assigning a color
	*
	*  ... all others are illegal.
	*)
121
122	type 'a worklist = 'a list	and trailInfo = END | UNDO of node * moveStatus ref * trailInfo
	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 *)
	}
123
124	type worklists = (nodelist,movelist,nodelist,nodelist,nodelist) lists	(* Create a new bitMatrix *)
125		val newBitMatrix : {edges : int, maxRegs : int} -> bitMatrix
126
127	(* Create a new interference graph *)	(* Create a new interference graph *)
128	val newGraph : {nodes        : node Intmap.intmap,	val newGraph : {nodes        : node Intmap.intmap,
129	regmap       : int Intmap.intmap,	regmap       : int Intmap.intmap,
130	numRegs      : int,	numRegs      : int,
131		maxRegs      : unit -> int,
132	K            : int,	K            : int,
133	firstPseudoR : int,	firstPseudoR : int,
134		dedicated    : bool Array.array,
135		showReg      : int -> string,
136	getreg       :	getreg       :
137	{pref:int list,stamp:int,proh:int Array.array} -> int	{pref:int list,stamp:int,proh:int Array.array} -> int,
138		getpair      :
139		{pref:int list,stamp:int,proh:int Array.array} -> int,
140		proh         : int Array.array
141	} -> interferenceGraph	} -> interferenceGraph
142
143	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