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 499 - (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 : monnier 469 (* A new bit matrix datatype.
11 :     * We use the small representation whenever possible to save space.
12 :     *)
13 :     datatype bitMatrix = BM of {table:hashTable,
14 :     elems:int ref,
15 :     edges:int}
16 :     and hashTable = SMALL of word list Array.array ref * word
17 :     | LARGE of bucket Array.array ref * word
18 :     (* | BITMATRIX of Word8Array.array *)
19 :     and bucket = NIL | B of int * int * bucket
20 : monnier 427
21 : monnier 469 type priority = int
22 :    
23 :     type programPoint = int
24 :    
25 :     type cost = int
26 :    
27 : monnier 498 type mode = word
28 :    
29 : monnier 427 datatype interferenceGraph =
30 : monnier 469 GRAPH of { bitMatrix : bitMatrix ref,
31 : monnier 427 nodes : node Intmap.intmap,
32 :     regmap : int Intmap.intmap,
33 :     K : int,
34 :     firstPseudoR : int,
35 : monnier 469 dedicated : bool Array.array,
36 : monnier 427 getreg :
37 : monnier 469 {pref:int list, stamp:int, proh:int Array.array} -> int,
38 :     getpair :
39 :     {pref:int list, stamp:int, proh:int Array.array} -> int,
40 : monnier 427 proh : int Array.array,
41 :     stamp : int ref,
42 : monnier 469
43 : monnier 427 (* Info to undo a spill when an optimistic spill has occurred *)
44 :     spillFlag : bool ref,
45 : monnier 469 spilledRegs : bool Intmap.intmap,
46 :     trail : trailInfo ref,
47 :    
48 :     showReg : int -> string,
49 :     numRegs : int,
50 :     maxRegs : unit -> int,
51 :    
52 :     deadCopies : int list ref,
53 : monnier 498 copyTmps : node list ref,
54 :     memMoves : move list ref,
55 :     memRegs : node list ref,
56 :    
57 :     spillLoc : int ref,
58 :     span : int Intmap.intmap,
59 :     mode : mode,
60 :     pseudoCount : int ref,
61 :     blockedCount : int ref
62 : monnier 427 }
63 :    
64 : monnier 498 and moveStatus = BRIGGS_MOVE | GEORGE_MOVE
65 :     | COALESCED | CONSTRAINED | LOST | WORKLIST
66 : monnier 427
67 :     and move =
68 :     MV of {src : node, (* source register of move *)
69 :     dst : node, (* destination register of move *)
70 : monnier 469 (* kind: moveKind, *) (* what kind of move *)
71 :     cost : cost, (* cost *)
72 : monnier 498 status : moveStatus ref, (* coalesced? *)
73 :     hicount : int ref (* neighbors of high degree *)
74 : monnier 427 }
75 :    
76 : monnier 469 and moveKind = REG_TO_REG (* register to register *)
77 :     | EVEN_TO_REG (* even register in pair to register *)
78 :     | ODD_TO_REG (* odd register in pair to register *)
79 :     | PAIR_TO_PAIR (* register pair to register pair *)
80 :     | REG_TO_EVEN (* register to even register in pair *)
81 :     | REG_TO_ODD (* register to odd register in pair *)
82 : monnier 427
83 : monnier 469 and nodeStatus =
84 :     PSEUDO (* pseudo register *)
85 :     | REMOVED (* removed from the interference graph *)
86 :     | ALIASED of node (* coalesced *)
87 :     | COLORED of int (* colored *)
88 :     | SPILLED of int (* spilled *)
89 :    
90 : monnier 427 and node =
91 :     NODE of { number : int, (* node number *)
92 :     movecnt: int ref, (* #moves this node is involved in *)
93 :     movelist: move list ref, (* moves associated with this node *)
94 :     degree : int ref, (* current degree *)
95 :     color : nodeStatus ref, (* status *)
96 : monnier 469 adj : node list ref, (* adjacency list *)
97 :     pri : priority ref, (* priority *)
98 :     movecost : cost ref, (* move cost *)
99 :     (* pair : bool, *) (* register pair? *)
100 :     defs : programPoint list ref,
101 :     uses : programPoint list ref
102 : monnier 427 }
103 :    
104 : monnier 469 and trailInfo = END | UNDO of node * moveStatus ref * trailInfo
105 : monnier 427
106 : monnier 469 exception Nodes
107 : monnier 427
108 : monnier 475 fun error msg = MLRiscErrorMsg.error("NewRAGraph", msg)
109 : monnier 427
110 : monnier 469 val stampCounter = ref 0
111 : monnier 427
112 : monnier 469 (* Create a new bitMatrix *)
113 :     fun roundSize size =
114 :     let fun f(x, shift) =
115 :     if x >= size then (x, Word.>>(shift, 0w1))
116 :     else f(x+x, shift+0w1)
117 :     in f(64, 0w6) end
118 :    
119 :     val max = Word.<<(0w1,Word.>>(Word.fromInt Word.wordSize,0w1))
120 :     val _ = if max < Word.<<(0w1,0w15)
121 :     then error "word size too small" else ()
122 :    
123 :     fun newBitMatrix{edges, maxRegs} =
124 :     let val table =
125 :     (* if maxRegs < 1024 then
126 :     let val denseBytes = (maxRegs * (maxRegs + 1) + 15) div 16
127 :     in BITMATRIX(Word8Array.array(denseBytes,0w0))
128 :     end
129 :     else *)
130 :     let val (tableSize, shift) = roundSize edges
131 :     in if Word.fromInt maxRegs < max then
132 :     SMALL(ref(Array.array(tableSize,[])),shift)
133 :     else
134 :     LARGE(ref(Array.array(tableSize,NIL)),shift)
135 :     end
136 :     in BM{table=table, elems=ref 0, edges=edges}
137 :     end
138 :    
139 : monnier 427 (* Create a new interference graph *)
140 : monnier 498 fun newGraph{nodes,regmap,K,firstPseudoR,dedicated,spillLoc,
141 :     getreg,getpair,showReg,maxRegs,numRegs,proh,
142 :     firstMemReg, numMemRegs,mode} =
143 : monnier 427 let (* lower triangular bitmatrix primitives *)
144 :     (* NOTE: The average ratio of E/N is about 16 *)
145 : monnier 469 val bitMatrix = newBitMatrix{edges=numRegs * 16,maxRegs=maxRegs()}
146 : monnier 498
147 :     (* Make memory register nodes *)
148 :     fun makeMemRegs(_, 0) = []
149 :     | makeMemRegs(reg, n) =
150 :     let val add = Intmap.add nodes
151 :     fun loop(r, 0, ns) = ns
152 :     | loop(r, n, ns) =
153 :     let val node =
154 :     NODE{pri=ref 0,adj=ref [],degree=ref 0,movecnt=ref 0,
155 :     color=ref(SPILLED r), defs=ref [], uses=ref [],
156 :     movecost=ref 0,movelist=ref [], number=r}
157 :     in add(r, node); loop(r+1, n-1, node::ns)
158 :     end
159 :     in loop(reg, n, [])
160 :     end
161 :    
162 :     val memRegs = makeMemRegs(firstMemReg, numMemRegs)
163 :    
164 : monnier 469 in if !stampCounter > 10000000 then stampCounter := 0 else ();
165 :     GRAPH{ bitMatrix = ref bitMatrix,
166 : monnier 427 nodes = nodes,
167 :     regmap = regmap,
168 :     K = K,
169 :     firstPseudoR = firstPseudoR,
170 : monnier 469 dedicated = dedicated,
171 : monnier 427 getreg = getreg,
172 : monnier 469 getpair = getpair,
173 :     proh = proh,
174 :     stamp = stampCounter,
175 : monnier 427 spillFlag = ref false,
176 : monnier 469 spilledRegs = Intmap.new(2,Nodes),
177 :     trail = ref END,
178 :     showReg = Int.toString,
179 :     numRegs = numRegs,
180 :     maxRegs = maxRegs,
181 :     deadCopies = ref [],
182 : monnier 498 copyTmps = ref [],
183 :     memMoves = ref [],
184 :     memRegs = ref memRegs,
185 :     spillLoc = spillLoc,
186 :     span = Intmap.new(2,Nodes),
187 :     mode = mode,
188 :     pseudoCount = ref 0,
189 :     blockedCount = ref 0
190 : monnier 427 }
191 :     end
192 : monnier 469
193 : monnier 427 end

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