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

SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/ra/mem-ra.sml
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/ra/mem-ra.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 554, Thu Mar 2 21:29:44 2000 UTC revision 585, Wed Mar 29 23:55:35 2000 UTC
# Line 9  Line 9 
9    structure A = Array    structure A = Array
10    structure W = Word    structure W = Word
11    
12      val debug = false
13    
14    open G RACore    open G RACore
15    
16    val ra_spill_coal = MLRiscControl.getCounter "ra-spill-coalescing"    val ra_spill_coal = MLRiscControl.getCounter "ra-spill-coalescing"
# Line 126  Line 128 
128    
129    (*    (*
130     * Spill propagation.     * Spill propagation.
131       * This one uses a simple local lookahead algorithm.
132     *)     *)
133    fun spillPropagation(G as GRAPH{bitMatrix, memRegs, ...}) nodesToSpill =    fun spillPropagation(G as GRAPH{bitMatrix, memRegs, ...}) nodesToSpill =
134    let val spillCoalescing = spillCoalescing G    let val spillCoalescing = spillCoalescing G
# Line 140  Line 143 
143         * The pinned flag is to prevent the spill node from coalescing         * The pinned flag is to prevent the spill node from coalescing
144         * two different fixed memory registers.         * two different fixed memory registers.
145         *)         *)
146        fun coalescingSavings([], pinned, sc) = (pinned, sc+sc)        fun coalescingSavings
147          | coalescingSavings(MV{status=ref(CONSTRAINED | COALESCED), ...}::mvs,             (node as NODE{number=me, movelist, pri=ref spillcost, ...}) =
148                              pinned, sc) = coalescingSavings(mvs, pinned, sc)        let fun interferes(x,[]) = false
149          | coalescingSavings(MV{dst, src, cost, ...}::mvs, pinned, sc) =              | interferes(x,NODE{number=y, ...}::ns) =
150                     x = y orelse member(x,y) orelse interferes(x, ns)
151    
152              fun moveSavings([], pinned, total) = (pinned, total+total)
153                | moveSavings(MV{status=ref(CONSTRAINED | COALESCED), ...}::mvs,
154                              pinned, total) =
155                     moveSavings(mvs, pinned, total)
156                | moveSavings(MV{dst, src, cost, ...}::mvs, pinned, total) =
157            let val NODE{number=d, color=dstCol, ...} = chase dst            let val NODE{number=d, color=dstCol, ...} = chase dst
158                val NODE{number=s, color=srcCol, ...} = chase src                val NODE{number=s, color=srcCol, ...} = chase src
159    
160                      (* How much can be saved by coalescing with the memory
161                       * location x.
162                       *)
163                fun savings(x) =                fun savings(x) =
164                    if member(d, s) then coalescingSavings(mvs, pinned, sc)                        if member(d, s) then
165                    else if x = ~1 then coalescingSavings(mvs, pinned, sc+cost)                          (if debug then print "interfere\n" else ();
166                             moveSavings(mvs, pinned, total))
167                          else if x = ~1 then
168                            (if debug then print (Int.toString cost^"\n") else ();
169                             moveSavings(mvs, pinned, total+cost))
170                    else if pinned >= 0 andalso pinned <> x then                    else if pinned >= 0 andalso pinned <> x then
171                       (* already coalesced with another mem reg *)                       (* already coalesced with another mem reg *)
172                       coalescingSavings(mvs, pinned, sc)                          (if debug then print "pinned\n" else ();
173                             moveSavings(mvs, pinned, total))
174                    else                    else
175                       (* coalescingSavings(mvs, x, sc+cost) *) (* XXX *)                          (if debug then print (Int.toString cost^"\n") else ();
176                       coalescingSavings(mvs, x, sc+cost)                           moveSavings(mvs, x, total+cost))
177    
178                     val _ = if debug then
179                                (print("Savings "^Int.toString d^" <-> "^
180                                                  Int.toString s^"=")
181                                ) else ()
182            in  if d = s then            in  if d = s then
183                   coalescingSavings(mvs, pinned, sc)                      (if debug then print "0 (trivial)\n" else ();
184                         moveSavings(mvs, pinned, total)
185                        )
186                else                else
187                   case (!dstCol, !srcCol) of                   case (!dstCol, !srcCol) of
188                     (SPILLED x, PSEUDO) => savings(x)                     (SPILLED x, PSEUDO) => savings(x)
189                   | (PSEUDO, SPILLED x) => savings(x)                   | (PSEUDO, SPILLED x) => savings(x)
190                   | _ => coalescingSavings(mvs, pinned, sc)                      | _ => (if debug then print "0 (other)\n" else ();
191                                moveSavings(mvs, pinned, total))
192                  end
193    
194              (* Find initial budget *)
195              val _ = if debug then
196                          print("Trying to propagate "^Int.toString me^
197                                " spill cost="^Int.toString spillcost^"\n")
198                      else ()
199    
200              val (pinned, savings) = moveSavings(!movelist, ~1, 0)
201              val budget = spillcost - savings
202              val S      = [node]
203    
204              (* Find lookahead nodes *)
205              fun lookaheads([], L) = L
206                | lookaheads(MV{cost, dst, src, ...}::mvs, L) =
207                  let val dst as NODE{number=d, ...} = chase dst
208                      val src as NODE{number=s, ...} = chase src
209                      fun check(n, node as NODE{color=ref PSEUDO, ...}) =
210                          if n = me orelse member(n, me) then
211                              lookaheads(mvs, L)
212                          else
213                              add(n, node, L, [])
214                        | check _ = lookaheads(mvs, L)
215                      and add(x, x', (l as (c,n' as NODE{number=y, ...}))::L, L') =
216                           if x = y then
217                              lookaheads(mvs, (cost+c, n')::List.revAppend(L', L))
218                           else add(x, x', L, l::L')
219                        | add(x, x', [], L') =
220                              lookaheads(mvs, (cost, x')::L')
221                  in  if d = me then check(s, src) else check(d, dst)
222                  end
223    
224              (* Now try to improve it by also propagating the lookahead nodes *)
225              fun improve([], pinned, budget, S) = (budget, S)
226                | improve((cost, node as NODE{number=n, movelist, pri, ...})::L,
227                          pinned, budget, S) =
228                  if interferes(n, S) then
229                      (if debug then
230                          print ("Excluding "^Int.toString n^" (interferes)\n")
231                       else ();
232                      improve(L, pinned, budget, S))
233                  else
234                  let val (pinned', savings) = moveSavings(!movelist, pinned, 0)
235                      val defUseSavings = cost+cost
236                      val spillcost     = !pri
237                      val budget' = budget - savings - defUseSavings + spillcost
238                  in  if budget' <= budget then
239                         (if debug then print ("Including "^Int.toString n^"\n")
240                          else ();
241                          improve(L, pinned', budget', node::S)
242                         )
243                      else
244                         (if debug then print ("Excluding "^Int.toString n^"\n")
245                          else ();
246                          improve(L, pinned, budget, S))
247                  end
248    
249          in  if budget <= 0 then (budget, S)
250              else improve(lookaheads(!movelist, []), pinned, budget, S)
251            end            end
252    
253        (* Insert all spillable neighbors onto the worklist *)        (* Insert all spillable neighbors onto the worklist *)
# Line 173  Line 259 
259                  insert(adj, node::worklist))                  insert(adj, node::worklist))
260          | insert(_::adj, worklist) = insert(adj, worklist)          | insert(_::adj, worklist) = insert(adj, worklist)
261    
262          fun insertAll([], worklist) = worklist
263            | insertAll(NODE{adj, ...}::nodes, worklist) =
264                 insertAll(nodes, insert(!adj, worklist))
265    
266        val marker = SPILLED(~1)        val marker = SPILLED(~1)
267    
268        (* Process all nodes from the worklist *)        (* Process all nodes from the worklist *)
269        fun propagate([], spilled) = spilled        fun propagate([], spilled) = spilled
270          | propagate((node as NODE{color as ref PSEUDO,          | propagate((node as NODE{color=ref PSEUDO, ...})::worklist,
                                   pri=ref spillcost, number,  
                                   adj, movelist, ...})::worklist,  
271                      spilled) =                      spilled) =
272            let val (pinned, savings) = coalescingSavings(!movelist, ~1, 0)            let val (budget, S) = coalescingSavings(node)
273            in  (* if (if pinned >= 0 then savings > spillcost                fun spillNodes([]) = ()
274                   else savings >= spillcost) *) (* XXX *)                  | spillNodes(NODE{color, ...}::nodes) =
               if savings >= spillcost  
               then  (* propagate spill *)  
275                   (ra_spill_prop := !ra_spill_prop + 1;                   (ra_spill_prop := !ra_spill_prop + 1;
276                    color := marker; (* spill the node *)                    color := marker; (* spill the node *)
277                    (* print("Propagating "^Int.toString number^" "^                     spillNodes nodes
278                          "savings="^Int.toString(savings)^                    )
279                         " cost="^Int.toString spillcost^"\n"); *)  
280              in  if budget <= 0
281                  then  (* propagate spill *)
282                     (if debug then
283                        (print("Propagating ");
284                         app (fn NODE{number=x, ...} => print(Int.toString x^" "))
285                             S;
286                         print "\n")
287                      else ();
288                      spillNodes S;
289                    (* run spill coalescing *)                    (* run spill coalescing *)
290                    spillCoalescing [node];                    spillCoalescing S;
291                    propagate(insert(!adj, worklist), node::spilled)                    propagate(insertAll(S, worklist), List.revAppend(S,spilled))
292                   )                   )
293                else                else
294                   propagate(worklist, spilled)                   propagate(worklist, spilled)
# Line 224  Line 319 
319    in  iterate(nodesToSpill, nodesToSpill)    in  iterate(nodesToSpill, nodesToSpill)
320    end    end
321    
322    
323    (*    (*
324     * Spill coloring.     * Spill coloring.
325     * Assign logical spill locations to all the spill nodes.     * Assign logical spill locations to all the spill nodes.

Legend:
Removed from v.554  
changed lines
  Added in v.585

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