Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/branches/SMLNJ/src/MLRISC/ra/ra-graph.sig
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 498 - (view) (download) (as text)

1 : monnier 469 (*
2 :     * This is the new interference graph used by the new register allocator.
3 :     *
4 :     * -- Allen
5 :     *)
6 : monnier 427
7 :     signature RA_GRAPH =
8 :     sig
9 :    
10 :     (*
11 :     * The following are the data structures used in the register allocator.
12 :     *)
13 :    
14 : monnier 469 (* 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 : monnier 427
25 :     exception Nodes
26 :    
27 : monnier 469 type priority = int
28 :     type cost = int
29 :    
30 :     (*
31 :     * The following represent a program point in the program.
32 :     *
33 :     * The last instruction in the block is numbered 1, i.e. the instruction
34 :     * numbering is in reverse. The number 0 is reserved for "live-out".
35 :     *
36 :     *)
37 :     type programPoint = int
38 :    
39 : monnier 498 type mode = word
40 :    
41 : monnier 427 datatype interferenceGraph =
42 : monnier 469 GRAPH of
43 :     { bitMatrix : bitMatrix ref,
44 :     nodes : node Intmap.intmap,
45 :     regmap : int Intmap.intmap,
46 :     K : int,
47 :     firstPseudoR : int,
48 :     dedicated : bool Array.array,
49 :     getreg : {pref:int list, stamp:int, proh:int Array.array} -> int,
50 :     getpair : {pref:int list, stamp:int, proh:int Array.array} -> int,
51 :     proh : int Array.array,
52 :     stamp : int ref,
53 : monnier 427
54 : monnier 469 (* Info to undo a spill when an optimistic spill has occurred *)
55 :     spillFlag : bool ref,
56 : monnier 427
57 : monnier 469 spilledRegs : bool Intmap.intmap, (*registers that have been spilled*)
58 :     trail : trailInfo ref,
59 :    
60 :     (* how to pretty print a register *)
61 :     showReg : int -> string,
62 :    
63 :     (* how many registers there are? *)
64 :     numRegs : int,
65 :     maxRegs : unit -> int,
66 :    
67 :     (* dead copies *)
68 :     deadCopies : int list ref,
69 : monnier 498 copyTmps : node list ref,
70 :     memMoves : move list ref,
71 :     memRegs : node list ref,
72 : monnier 469
73 :     (* spill locations *)
74 : monnier 498 spillLoc : int ref,
75 :    
76 :     (* span indexed by node id *)
77 :     span : int Intmap.intmap,
78 :    
79 :     (* mode *)
80 :     mode : mode,
81 :    
82 :     pseudoCount : int ref,
83 :     blockedCount : int ref
84 : monnier 469 }
85 :    
86 : monnier 498 and moveStatus = BRIGGS_MOVE (* not yet coalesceable *)
87 :     | GEORGE_MOVE (* not yet coalesceable *)
88 :     | COALESCED (* coalesced *)
89 :     | CONSTRAINED (* src and target intefere *)
90 :     | LOST (* frozen moves *)
91 :     | WORKLIST (* on the move worklist *)
92 : monnier 469
93 : monnier 427 and move =
94 : monnier 469 MV of {src : node, (* source register of move *)
95 :     dst : node, (* destination register of move *)
96 :     (*kind : moveKind, *) (* kind of move *)
97 :     cost : cost, (* cost *)
98 : monnier 498 status : moveStatus ref, (* coalesced? *)
99 :     hicount: int ref (* neighbors of high degree *)
100 : monnier 427 }
101 :    
102 : monnier 469 and moveKind = REG_TO_REG (* register to register *)
103 :     | EVEN_TO_REG (* even register in pair to register *)
104 :     | ODD_TO_REG (* odd register in pair to register *)
105 :     | PAIR_TO_PAIR (* register pair to register pair *)
106 :     | REG_TO_EVEN (* register to even register in pair *)
107 :     | REG_TO_ODD (* register to odd register in pair *)
108 : monnier 427
109 : monnier 469 and nodeStatus =
110 :     PSEUDO (* pseudo register *)
111 :     | REMOVED (* removed from the interference graph *)
112 :     | ALIASED of node (* coalesced *)
113 :     | COLORED of int (* colored *)
114 :     | SPILLED of int (* spilled *)
115 :    
116 : monnier 498 (* Note on SPILLED:
117 :     * SPILLED ~1 means that the spill location is still undetermined
118 :     * SPILLED c, c >= 0 means that c is a fixed "memory register"
119 :     * SPILLED c, c < ~1 means that c is a logical spill location
120 :     * assigned by the register allocator
121 :     *)
122 :    
123 : monnier 427 and node =
124 :     NODE of { number : int, (* node number *)
125 :     movecnt: int ref, (* #moves this node is involved in *)
126 :     movelist: move list ref, (* moves associated with this node *)
127 :     degree : int ref, (* current degree *)
128 :     color : nodeStatus ref, (* status *)
129 : monnier 469 adj : node list ref, (* adjacency list *)
130 :     pri : priority ref, (* priority *)
131 :     movecost : cost ref, (* move cost *)
132 :     (* pair : bool, *) (* register pair? *)
133 :     defs : programPoint list ref,
134 :     uses : programPoint list ref
135 : monnier 427 }
136 :    
137 : monnier 469 and trailInfo = END | UNDO of node * moveStatus ref * trailInfo
138 : monnier 427
139 : monnier 469 (* Create a new bitMatrix *)
140 :     val newBitMatrix : {edges : int, maxRegs : int} -> bitMatrix
141 : monnier 427
142 : monnier 469 (* Create a new interference graph *)
143 :     val newGraph : { nodes : node Intmap.intmap,
144 : monnier 427 regmap : int Intmap.intmap,
145 :     numRegs : int,
146 : monnier 469 maxRegs : unit -> int,
147 : monnier 427 K : int,
148 :     firstPseudoR : int,
149 : monnier 469 dedicated : bool Array.array,
150 :     showReg : int -> string,
151 : monnier 427 getreg :
152 : monnier 469 {pref:int list,stamp:int,proh:int Array.array} -> int,
153 :     getpair :
154 :     {pref:int list,stamp:int,proh:int Array.array} -> int,
155 : monnier 498 proh : int Array.array,
156 :     mode : mode,
157 :     spillLoc : int ref,
158 :     firstMemReg : int,
159 :     numMemRegs : int
160 : monnier 469 } -> interferenceGraph
161 : monnier 427
162 :     end

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