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 /MLRISC/trunk/ra/ra-graph.sig
ViewVC logotype

Annotation of /MLRISC/trunk/ra/ra-graph.sig

Parent Directory Parent Directory | Revision Log Revision Log


Revision 475 - (view) (download) (as text)
Original Path: sml/branches/SMLNJ/src/MLRISC/ra/ra-graph.sig

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 :     * 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 : monnier 427 datatype interferenceGraph =
47 : monnier 469 GRAPH of
48 :     { bitMatrix : bitMatrix ref,
49 :     nodes : node Intmap.intmap,
50 :     regmap : int Intmap.intmap,
51 :     K : int,
52 :     firstPseudoR : int,
53 :     dedicated : bool Array.array,
54 :     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,
57 :     stamp : int ref,
58 : monnier 427
59 : monnier 469 (* Info to undo a spill when an optimistic spill has occurred *)
60 :     spillFlag : bool ref,
61 : monnier 427
62 : monnier 469 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 (* not yet coalesced *)
80 :     | COALESCED (* coalesced *)
81 :     | CONSTRAINED (* src and target intefere *)
82 :     | LOST (* frozen moves *)
83 :     | WORKLIST (* on the move worklist *)
84 :    
85 : monnier 427 and move =
86 : monnier 469 MV of {src : node, (* source register of move *)
87 :     dst : node, (* destination register of move *)
88 :     (*kind : moveKind, *) (* kind of move *)
89 :     cost : cost, (* cost *)
90 : monnier 427 status : moveStatus ref (* coalesced? *)
91 :     }
92 :    
93 : monnier 469 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 : monnier 427
100 : monnier 469 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 :    
107 : monnier 427 and node =
108 :     NODE of { number : int, (* node number *)
109 :     movecnt: int ref, (* #moves this node is involved in *)
110 :     movelist: move list ref, (* moves associated with this node *)
111 :     degree : int ref, (* current degree *)
112 :     color : nodeStatus ref, (* status *)
113 : monnier 469 adj : node list ref, (* adjacency list *)
114 :     pri : priority ref, (* priority *)
115 :     movecost : cost ref, (* move cost *)
116 :     (* pair : bool, *) (* register pair? *)
117 :     defs : programPoint list ref,
118 :     uses : programPoint list ref
119 : monnier 427 }
120 :    
121 : monnier 469 and trailInfo = END | UNDO of node * moveStatus ref * trailInfo
122 : monnier 427
123 : monnier 469 (* Create a new bitMatrix *)
124 :     val newBitMatrix : {edges : int, maxRegs : int} -> bitMatrix
125 : monnier 427
126 : monnier 469 (* Create a new interference graph *)
127 :     val newGraph : { nodes : node Intmap.intmap,
128 : monnier 427 regmap : int Intmap.intmap,
129 :     numRegs : int,
130 : monnier 469 maxRegs : unit -> int,
131 : monnier 427 K : int,
132 :     firstPseudoR : int,
133 : monnier 469 dedicated : bool Array.array,
134 :     showReg : int -> string,
135 : monnier 427 getreg :
136 : monnier 469 {pref:int list,stamp:int,proh:int Array.array} -> int,
137 :     getpair :
138 :     {pref:int list,stamp:int,proh:int Array.array} -> int,
139 :     proh : int Array.array
140 :     } -> interferenceGraph
141 : monnier 427
142 :     end

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