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/releases/release-110.84/ra/ra-graph.sml
ViewVC logotype

Annotation of /MLRISC/releases/release-110.84/ra/ra-graph.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4728 - (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 : jhr 1125 type priority = real
15 : monnier 469
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 : jhr 1125 type cost = real
40 : monnier 469
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 : jhr 1125 span : cost IntHashTable.hash_table option ref,
72 : monnier 498 mode : mode,
73 : george 1065 pseudoCount : int ref
74 : monnier 427 }
75 :    
76 : monnier 498 and moveStatus = BRIGGS_MOVE | GEORGE_MOVE
77 :     | COALESCED | CONSTRAINED | LOST | WORKLIST
78 : monnier 427
79 :     and move =
80 :     MV of {src : node, (* source register of move *)
81 :     dst : node, (* destination register of move *)
82 : monnier 469 (* kind: moveKind, *) (* what kind of move *)
83 :     cost : cost, (* cost *)
84 : monnier 498 status : moveStatus ref, (* coalesced? *)
85 :     hicount : int ref (* neighbors of high degree *)
86 : monnier 427 }
87 :    
88 : monnier 469 and moveKind = REG_TO_REG (* register to register *)
89 :     | EVEN_TO_REG (* even register in pair to register *)
90 :     | ODD_TO_REG (* odd register in pair to register *)
91 :     | PAIR_TO_PAIR (* register pair to register pair *)
92 :     | REG_TO_EVEN (* register to even register in pair *)
93 :     | REG_TO_ODD (* register to odd register in pair *)
94 : monnier 427
95 : monnier 469 and nodeStatus =
96 :     PSEUDO (* pseudo register *)
97 :     | REMOVED (* removed from the interference graph *)
98 :     | ALIASED of node (* coalesced *)
99 :     | COLORED of int (* colored *)
100 : leunga 744 | MEMREG of int * C.cell(* register implemented in memory *)
101 : george 705 | SPILLED (* spilled *)
102 :     | SPILL_LOC of int (* spilled at logical location *)
103 : monnier 469
104 : monnier 427 and node =
105 : leunga 744 NODE of { number : int, (* node number *)
106 :     cell : C.cell,
107 : monnier 427 movecnt: int ref, (* #moves this node is involved in *)
108 :     movelist: move list ref, (* moves associated with this node *)
109 :     degree : int ref, (* current degree *)
110 :     color : nodeStatus ref, (* status *)
111 : monnier 469 adj : node list ref, (* adjacency list *)
112 :     pri : priority ref, (* priority *)
113 :     movecost : cost ref, (* move cost *)
114 :     (* pair : bool, *) (* register pair? *)
115 :     defs : programPoint list ref,
116 :     uses : programPoint list ref
117 : monnier 427 }
118 :    
119 : monnier 469 and trailInfo = END | UNDO of node * moveStatus ref * trailInfo
120 : monnier 427
121 : monnier 469 exception Nodes
122 : monnier 427
123 : monnier 475 fun error msg = MLRiscErrorMsg.error("NewRAGraph", msg)
124 : monnier 427
125 : monnier 469 val stampCounter = ref 0
126 : monnier 427
127 : monnier 469 (* Create a new bitMatrix *)
128 :     fun roundSize size =
129 :     let fun f(x, shift) =
130 :     if x >= size then (x, Word.>>(shift, 0w1))
131 :     else f(x+x, shift+0w1)
132 :     in f(64, 0w6) end
133 :    
134 :     val max = Word.<<(0w1,Word.>>(Word.fromInt Word.wordSize,0w1))
135 :     val _ = if max < Word.<<(0w1,0w15)
136 :     then error "word size too small" else ()
137 :    
138 :     fun newBitMatrix{edges, maxRegs} =
139 :     let val table =
140 :     (* if maxRegs < 1024 then
141 :     let val denseBytes = (maxRegs * (maxRegs + 1) + 15) div 16
142 :     in BITMATRIX(Word8Array.array(denseBytes,0w0))
143 :     end
144 :     else *)
145 :     let val (tableSize, shift) = roundSize edges
146 :     in if Word.fromInt maxRegs < max then
147 : george 1053 BM.SMALL(ref(Array.array(tableSize,[])),shift)
148 : monnier 469 else
149 : george 1053 BM.LARGE(ref(Array.array(tableSize, BM.NIL)),shift)
150 : monnier 469 end
151 : george 1053 in BM.BM{table=table, elems=ref 0, edges=edges}
152 : monnier 469 end
153 :    
154 : monnier 427 (* Create a new interference graph *)
155 : leunga 744 fun newGraph{nodes,K,firstPseudoR,dedicated,spillLoc,
156 : monnier 498 getreg,getpair,showReg,maxRegs,numRegs,proh,
157 : leunga 576 memRegs,mode} =
158 : monnier 427 let (* lower triangular bitmatrix primitives *)
159 :     (* NOTE: The average ratio of E/N is about 16 *)
160 : monnier 469 val bitMatrix = newBitMatrix{edges=numRegs * 16,maxRegs=maxRegs()}
161 : monnier 498
162 :     (* Make memory register nodes *)
163 : leunga 576 fun makeMemRegs [] = []
164 : leunga 744 | makeMemRegs(cells) =
165 : blume 733 let val add = IntHashTable.insert nodes
166 : leunga 744 fun loop([], ns) = ns
167 :     | loop(cell::cells, ns) =
168 :     let val id = C.registerId cell
169 :     val node =
170 :     NODE{number=id,
171 : jhr 1125 pri=ref 0.0,adj=ref [],degree=ref 0,movecnt=ref 0,
172 : leunga 744 color=ref(MEMREG(id,cell)),
173 :     defs=ref [], uses=ref [],
174 : jhr 1125 movecost=ref 0.0,movelist=ref [], cell=cell}
175 : leunga 744 in add(id, node); loop(cells, node::ns)
176 : monnier 498 end
177 : leunga 744 in loop(cells, [])
178 : monnier 498 end
179 :    
180 : leunga 576 val memRegs = makeMemRegs memRegs
181 : monnier 498
182 : monnier 469 in if !stampCounter > 10000000 then stampCounter := 0 else ();
183 :     GRAPH{ bitMatrix = ref bitMatrix,
184 : monnier 427 nodes = nodes,
185 :     K = K,
186 :     firstPseudoR = firstPseudoR,
187 : monnier 469 dedicated = dedicated,
188 : monnier 427 getreg = getreg,
189 : monnier 469 getpair = getpair,
190 :     proh = proh,
191 :     stamp = stampCounter,
192 : monnier 427 spillFlag = ref false,
193 : blume 733 spilledRegs = IntHashTable.mkTable(2,Nodes),
194 : monnier 469 trail = ref END,
195 : leunga 744 showReg = fn _ => raise Match,
196 : monnier 469 numRegs = numRegs,
197 :     maxRegs = maxRegs,
198 :     deadCopies = ref [],
199 : monnier 498 copyTmps = ref [],
200 :     memMoves = ref [],
201 :     memRegs = ref memRegs,
202 :     spillLoc = spillLoc,
203 : george 545 span = ref NONE,
204 : monnier 498 mode = mode,
205 : george 1065 pseudoCount = ref 0
206 : monnier 427 }
207 :     end
208 : monnier 469
209 : monnier 427 end

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