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

Annotation of /sml/trunk/src/MLRISC/ra/ra-graph.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1053 - (view) (download)

1 : monnier 427 (*
2 : monnier 469 * This is the new interference graph used by the new register allocator.
3 :     *
4 : monnier 427 * -- Allen
5 :     *)
6 :    
7 :     structure RAGraph : RA_GRAPH =
8 :     struct
9 :    
10 : leunga 744 structure C = CellsBasis
11 :    
12 : george 1053 structure BM = RaBitmatrix
13 : monnier 427
14 : monnier 469 type priority = int
15 :    
16 : george 958 type programPoint = {block:int, insn:int}
17 : monnier 469
18 : george 958 structure PPtHashTable = HashTableFn
19 :     (type hash_key = programPoint
20 :     fun hashVal{block,insn} =
21 :     Word.<<(Word.fromInt block,0w7) + Word.fromInt insn
22 :     fun sameKey(x:programPoint,y) = x = y
23 :     )
24 : leunga 744
25 :     type frame_offset = int
26 :     type logical_spill_id = int
27 :     datatype spillLoc = FRAME of logical_spill_id
28 :     | MEM_REG of C.cell
29 :    
30 :     structure SpillLocHashTable = HashTableFn
31 :     (type hash_key = spillLoc
32 :     fun hashVal(FRAME i) = Word.fromInt i
33 :     | hashVal(MEM_REG r) = C.hashCell r
34 :     fun sameKey(FRAME i, FRAME j) = i = j
35 :     | sameKey(MEM_REG x,MEM_REG y) = C.sameColor(x, y)
36 :     | sameKey _ = false
37 :     )
38 :    
39 : monnier 469 type cost = int
40 :    
41 : monnier 498 type mode = word
42 :    
43 : monnier 427 datatype interferenceGraph =
44 : george 1053 GRAPH of { bitMatrix : BM.bitMatrix ref,
45 : blume 733 nodes : node IntHashTable.hash_table,
46 : monnier 427 K : int,
47 :     firstPseudoR : int,
48 : george 823 dedicated : int -> bool,
49 : monnier 427 getreg :
50 : monnier 469 {pref:int list, stamp:int, proh:int Array.array} -> int,
51 :     getpair :
52 :     {pref:int list, stamp:int, proh:int Array.array} -> int,
53 : monnier 427 proh : int Array.array,
54 :     stamp : int ref,
55 : monnier 469
56 : monnier 427 (* Info to undo a spill when an optimistic spill has occurred *)
57 :     spillFlag : bool ref,
58 : blume 733 spilledRegs : bool IntHashTable.hash_table,
59 : monnier 469 trail : trailInfo ref,
60 :    
61 : leunga 744 showReg : C.cell -> string,
62 : monnier 469 numRegs : int,
63 :     maxRegs : unit -> int,
64 :    
65 : leunga 744 deadCopies : C.cell list ref,
66 : monnier 498 copyTmps : node list ref,
67 :     memMoves : move list ref,
68 :     memRegs : node list ref,
69 :    
70 :     spillLoc : int ref,
71 : blume 733 span : int IntHashTable.hash_table option ref,
72 : monnier 498 mode : mode,
73 :     pseudoCount : int ref,
74 :     blockedCount : int ref
75 : monnier 427 }
76 :    
77 : monnier 498 and moveStatus = BRIGGS_MOVE | GEORGE_MOVE
78 :     | COALESCED | CONSTRAINED | LOST | WORKLIST
79 : monnier 427
80 :     and move =
81 :     MV of {src : node, (* source register of move *)
82 :     dst : node, (* destination register of move *)
83 : monnier 469 (* kind: moveKind, *) (* what kind of move *)
84 :     cost : cost, (* cost *)
85 : monnier 498 status : moveStatus ref, (* coalesced? *)
86 :     hicount : int ref (* neighbors of high degree *)
87 : monnier 427 }
88 :    
89 : monnier 469 and moveKind = REG_TO_REG (* register to register *)
90 :     | EVEN_TO_REG (* even register in pair to register *)
91 :     | ODD_TO_REG (* odd register in pair to register *)
92 :     | PAIR_TO_PAIR (* register pair to register pair *)
93 :     | REG_TO_EVEN (* register to even register in pair *)
94 :     | REG_TO_ODD (* register to odd register in pair *)
95 : monnier 427
96 : monnier 469 and nodeStatus =
97 :     PSEUDO (* pseudo register *)
98 :     | REMOVED (* removed from the interference graph *)
99 :     | ALIASED of node (* coalesced *)
100 :     | COLORED of int (* colored *)
101 : leunga 744 | MEMREG of int * C.cell(* register implemented in memory *)
102 : george 705 | SPILLED (* spilled *)
103 :     | SPILL_LOC of int (* spilled at logical location *)
104 : monnier 469
105 : monnier 427 and node =
106 : leunga 744 NODE of { number : int, (* node number *)
107 :     cell : C.cell,
108 : monnier 427 movecnt: int ref, (* #moves this node is involved in *)
109 :     movelist: move list ref, (* moves associated with this node *)
110 :     degree : int ref, (* current degree *)
111 :     color : nodeStatus ref, (* status *)
112 : monnier 469 adj : node list ref, (* adjacency list *)
113 :     pri : priority ref, (* priority *)
114 :     movecost : cost ref, (* move cost *)
115 :     (* pair : bool, *) (* register pair? *)
116 :     defs : programPoint list ref,
117 :     uses : programPoint list ref
118 : monnier 427 }
119 :    
120 : monnier 469 and trailInfo = END | UNDO of node * moveStatus ref * trailInfo
121 : monnier 427
122 : monnier 469 exception Nodes
123 : monnier 427
124 : monnier 475 fun error msg = MLRiscErrorMsg.error("NewRAGraph", msg)
125 : monnier 427
126 : monnier 469 val stampCounter = ref 0
127 : monnier 427
128 : monnier 469 (* Create a new bitMatrix *)
129 :     fun roundSize size =
130 :     let fun f(x, shift) =
131 :     if x >= size then (x, Word.>>(shift, 0w1))
132 :     else f(x+x, shift+0w1)
133 :     in f(64, 0w6) end
134 :    
135 :     val max = Word.<<(0w1,Word.>>(Word.fromInt Word.wordSize,0w1))
136 :     val _ = if max < Word.<<(0w1,0w15)
137 :     then error "word size too small" else ()
138 :    
139 :     fun newBitMatrix{edges, maxRegs} =
140 :     let val table =
141 :     (* if maxRegs < 1024 then
142 :     let val denseBytes = (maxRegs * (maxRegs + 1) + 15) div 16
143 :     in BITMATRIX(Word8Array.array(denseBytes,0w0))
144 :     end
145 :     else *)
146 :     let val (tableSize, shift) = roundSize edges
147 :     in if Word.fromInt maxRegs < max then
148 : george 1053 BM.SMALL(ref(Array.array(tableSize,[])),shift)
149 : monnier 469 else
150 : george 1053 BM.LARGE(ref(Array.array(tableSize, BM.NIL)),shift)
151 : monnier 469 end
152 : george 1053 in BM.BM{table=table, elems=ref 0, edges=edges}
153 : monnier 469 end
154 :    
155 : monnier 427 (* Create a new interference graph *)
156 : leunga 744 fun newGraph{nodes,K,firstPseudoR,dedicated,spillLoc,
157 : monnier 498 getreg,getpair,showReg,maxRegs,numRegs,proh,
158 : leunga 576 memRegs,mode} =
159 : monnier 427 let (* lower triangular bitmatrix primitives *)
160 :     (* NOTE: The average ratio of E/N is about 16 *)
161 : monnier 469 val bitMatrix = newBitMatrix{edges=numRegs * 16,maxRegs=maxRegs()}
162 : monnier 498
163 :     (* Make memory register nodes *)
164 : leunga 576 fun makeMemRegs [] = []
165 : leunga 744 | makeMemRegs(cells) =
166 : blume 733 let val add = IntHashTable.insert nodes
167 : leunga 744 fun loop([], ns) = ns
168 :     | loop(cell::cells, ns) =
169 :     let val id = C.registerId cell
170 :     val node =
171 :     NODE{number=id,
172 :     pri=ref 0,adj=ref [],degree=ref 0,movecnt=ref 0,
173 :     color=ref(MEMREG(id,cell)),
174 :     defs=ref [], uses=ref [],
175 :     movecost=ref 0,movelist=ref [], cell=cell}
176 :     in add(id, node); loop(cells, node::ns)
177 : monnier 498 end
178 : leunga 744 in loop(cells, [])
179 : monnier 498 end
180 :    
181 : leunga 576 val memRegs = makeMemRegs memRegs
182 : monnier 498
183 : monnier 469 in if !stampCounter > 10000000 then stampCounter := 0 else ();
184 :     GRAPH{ bitMatrix = ref bitMatrix,
185 : monnier 427 nodes = nodes,
186 :     K = K,
187 :     firstPseudoR = firstPseudoR,
188 : monnier 469 dedicated = dedicated,
189 : monnier 427 getreg = getreg,
190 : monnier 469 getpair = getpair,
191 :     proh = proh,
192 :     stamp = stampCounter,
193 : monnier 427 spillFlag = ref false,
194 : blume 733 spilledRegs = IntHashTable.mkTable(2,Nodes),
195 : monnier 469 trail = ref END,
196 : leunga 744 showReg = fn _ => raise Match,
197 : monnier 469 numRegs = numRegs,
198 :     maxRegs = maxRegs,
199 :     deadCopies = ref [],
200 : monnier 498 copyTmps = ref [],
201 :     memMoves = ref [],
202 :     memRegs = ref memRegs,
203 :     spillLoc = spillLoc,
204 : george 545 span = ref NONE,
205 : monnier 498 mode = mode,
206 :     pseudoCount = ref 0,
207 :     blockedCount = ref 0
208 : monnier 427 }
209 :     end
210 : monnier 469
211 : monnier 427 end

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