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 1125, Thu Mar 7 21:04:13 2002 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 18  Line 20 
20    
21    fun error msg = MLRiscErrorMsg.error("RACore", msg)    fun error msg = MLRiscErrorMsg.error("RACore", msg)
22    
   (* No overflow checking necessary here *)  
   fun x + y = W.toIntX(W.+(W.fromInt x, W.fromInt y))  
   fun x - y = W.toIntX(W.-(W.fromInt x, W.fromInt y))  
   
23    fun concat([], b) = b    fun concat([], b) = b
24      | concat(x::a, b) = concat(a, x::b)      | concat(x::a, b) = concat(a, x::b)
25    
# Line 32  Line 30 
30    
31    fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0    fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0
32    
33      fun isMemLoc(SPILLED) = true
34        | isMemLoc(SPILL_LOC _) = true
35        | isMemLoc(MEMREG _) = true
36        | isMemLoc _ = false
37    
38    (*    (*
39     * Spill coalescing.     * Spill coalescing.
40     * Coalesce non-interfering moves between spilled nodes,     * Coalesce non-interfering moves between spilled nodes,
41     * in non-increasing order of move cost.     * in non-increasing order of move cost.
42     *)     *)
43    fun spillCoalescing(GRAPH{bitMatrix, ...}) =    fun spillCoalescing(GRAPH{bitMatrix, ...}) = let
44    let val member = BM.member(!bitMatrix)        val member = BM.member(!bitMatrix)
45        val addEdge = BM.add(!bitMatrix)        val addEdge = BM.add(!bitMatrix)
46    in  fn nodesToSpill =>    in
47        let      fn nodesToSpill => let
48            (* Find moves between two spilled nodes *)            (* Find moves between two spilled nodes *)
49            fun collectMoves([], mv') = mv'            fun collectMoves([], mv') = mv'
50              | collectMoves(NODE{movelist, color=ref(SPILLED _), ...}::ns, mv') =          | collectMoves(NODE{movelist, color, ...}::ns, mv') = let
51                let fun ins([], mv') = collectMoves(ns, mv')              fun ins([], mv') = collectMoves(ns, mv')
52                      | ins(MV{status=ref(COALESCED | CONSTRAINED), ...}::mvs,                | ins(MV{status=ref(COALESCED | CONSTRAINED), ...}::mvs, mv') =
53                            mv') = ins(mvs, mv')                    ins(mvs, mv')
54                      | ins((mv as MV{dst, src, ...})::mvs, mv') =                | ins((mv as MV{dst, src, ...})::mvs, mv') = let
55                         (case (chase dst, chase src) of                    val NODE{color=ref cd, number=nd, ...} = chase dst
56                            (NODE{color=ref(SPILLED x), number=d, ...},                    val NODE{color=ref cs, number=ns, ...} = chase src
57                             NODE{color=ref(SPILLED y), number=s, ...}) =>                  in
58                                if d = s orelse            (* trival move *)                    if nd=ns then ins(mvs, mv')
59                                   (x >= 0 andalso y >= 0) (* both are fixed *)                    else (case (cd, cs)
60                                then ins(mvs, mv')                      of (MEMREG _, MEMREG _) => ins(mvs, mv')
61                                else ins(mvs, MV.add(mv, mv'))                       |  _ =>
62                          | _ => ins(mvs, mv')                          if isMemLoc cd andalso isMemLoc cs then
63                         )                            ins(mvs, MV.add(mv, mv'))
64                in  ins(!movelist, mv') end                          else
65              | collectMoves(_::ns, mv') = collectMoves(ns, mv')                            ins(mvs, mv')
66                       (*esac*))
67            val mvs = collectMoves(nodesToSpill, MV.EMPTY)                  end
68              in
69                if isMemLoc (!color) then ins(!movelist, mv')
70                else collectMoves(ns, mv')
71              end
72    
73            (* Coalesce moves between two spilled nodes *)            (* Coalesce moves between two spilled nodes *)
74            fun coalesceMoves(MV.EMPTY) = ()            fun coalesceMoves(MV.EMPTY) = ()
# Line 69  Line 76 
76                let val dst as NODE{color=colorDst, ...} = chase dst                let val dst as NODE{color=colorDst, ...} = chase dst
77                    val src = chase src                    val src = chase src
78    
79                    (* Make sure that dst is the non-mem reg node *)                (* Make sure that dst has not been assigned a spill location *)
80                    val (dst, src) =                    val (dst, src) =
81                         case !colorDst of                  case !colorDst of SPILLED => (dst, src) | _ => (src, dst)
                          SPILLED ~1 => (dst, src)  
                        | _ => (src, dst)  
82    
83                    val dst as NODE{number=d, color=colorDst, adj=adjDst,                    val dst as NODE{number=d, color=colorDst, adj=adjDst,
84                                    defs=defsDst, uses=usesDst,  ...} = dst                                    defs=defsDst, uses=usesDst,  ...} = dst
# Line 85  Line 90 
90                      | union((n as NODE{color, adj=adjT,                      | union((n as NODE{color, adj=adjT,
91                                         number=t, ...})::adjDst, adjSrc) =                                         number=t, ...})::adjDst, adjSrc) =
92                        (case !color of                        (case !color of
93                           (SPILLED _ | PSEUDO) =>                       (SPILLED | MEMREG _ | SPILL_LOC _ | PSEUDO) =>
94                             if addEdge(s, t) then                             if addEdge(s, t) then
95                                (adjT := src :: !adjT; union(adjDst, n::adjSrc))                                (adjT := src :: !adjT; union(adjDst, n::adjSrc))
96                             else union(adjDst, adjSrc)                             else union(adjDst, adjSrc)
# Line 94  Line 99 
99                             else union(adjDst, adjSrc)                             else union(adjDst, adjSrc)
100                         | _ => union(adjDst, adjSrc)                         | _ => union(adjDst, adjSrc)
101                        )                        )
102    
103                    val mvs = MV.merge(l,r)                    val mvs = MV.merge(l,r)
104                in  if d = s then          (* trivial *)  
105                       coalesceMoves mvs                fun f() =
                   else  
                   (case !colorDst of  
                     SPILLED x =>  
                        if x >= 0 orelse  (* both dst and src are mem regs *)  
                           member(d, s)   (* they interfere *)  
                        then  
                          ((* print("Bad "^Int.toString d ^  
                                    "<->"^Int.toString s^"\n")*))  
                        else  
106                           ((* print(Int.toString d ^"<->"^Int.toString s^"\n");*)                           ((* print(Int.toString d ^"<->"^Int.toString s^"\n");*)
107                            ra_spill_coal := !ra_spill_coal + 1;                            ra_spill_coal := !ra_spill_coal + 1;
108                             (* unify *)                             (* unify *)
109                            colorDst := ALIASED src;                            colorDst := ALIASED src;
110                            adjSrc := union(!adjDst, !adjSrc);                            adjSrc := union(!adjDst, !adjSrc);
111                            if x >= 0 then ()                   defsSrc := concat(!defsDst, !defsSrc);
112                            else                   usesSrc := concat(!usesDst, !usesSrc);
113                              (defsSrc := concat(!defsDst, !defsSrc);                   coalesceMoves mvs)
114                               usesSrc := concat(!usesDst, !usesSrc))            in
115                           )                if d = s then coalesceMoves mvs
116                     | _ => error "coalesceMoves";                else (case !colorDst
117                     coalesceMoves mvs                  of MEMREG _ => coalesceMoves mvs
118                    )                   | SPILLED =>
119                end                      if member(d,s) then coalesceMoves mvs else f()
120       in  coalesceMoves mvs                   | SPILL_LOC loc =>
121                        if member(d,s) then coalesceMoves mvs else f()
122                     | _ => error "coalesceMoves"
123                   (*esac*))
124       end       end
125         in coalesceMoves(collectMoves(nodesToSpill, MV.EMPTY))
126    end    end
127      end (*spillCoalesce*)
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
135        exception SpillProp        exception SpillProp
136        val visited = Intmap.new(32, SpillProp) : bool Intmap.intmap        val visited = IntHashTable.mkTable(32, SpillProp)
137        val hasBeenVisited = Intmap.mapWithDefault (visited, false)                       : bool IntHashTable.hash_table
138        val markAsVisited = Intmap.add visited        val hasBeenVisited = IntHashTable.find visited
139          val hasBeenVisited = fn r => case hasBeenVisited r of NONE => false
140                                                              | SOME _ => true
141          val markAsVisited = IntHashTable.insert visited
142        val member = BM.member(!bitMatrix)        val member = BM.member(!bitMatrix)
143    
144        (* compute savings due to spill coalescing.        (* compute savings due to spill coalescing.
# Line 140  Line 146 
146         * The pinned flag is to prevent the spill node from coalescing         * The pinned flag is to prevent the spill node from coalescing
147         * two different fixed memory registers.         * two different fixed memory registers.
148         *)         *)
149        fun coalescingSavings([], pinned, sc) = (pinned, sc+sc)        fun coalescingSavings
150          | coalescingSavings(MV{status=ref(CONSTRAINED | COALESCED), ...}::mvs,             (node as NODE{number=me, movelist, pri=ref spillcost, ...}) =
151                              pinned, sc) = coalescingSavings(mvs, pinned, sc)        let fun interferes(x,[]) = false
152          | coalescingSavings(MV{dst, src, cost, ...}::mvs, pinned, sc) =              | interferes(x,NODE{number=y, ...}::ns) =
153                     x = y orelse member(x,y) orelse interferes(x, ns)
154    
155              fun moveSavings([], pinned, total) = (pinned, total+total)
156                | moveSavings(MV{status=ref(CONSTRAINED | COALESCED), ...}::mvs,
157                              pinned, total) =
158                     moveSavings(mvs, pinned, total)
159                | moveSavings(MV{dst, src, cost, ...}::mvs, pinned, total) =
160            let val NODE{number=d, color=dstCol, ...} = chase dst            let val NODE{number=d, color=dstCol, ...} = chase dst
161                val NODE{number=s, color=srcCol, ...} = chase src                val NODE{number=s, color=srcCol, ...} = chase src
162    
163                      (* How much can be saved by coalescing with the memory
164                       * location x.
165                       *)
166                fun savings(x) =                fun savings(x) =
167                    if member(d, s) then coalescingSavings(mvs, pinned, sc)                        if member(d, s) then
168                    else if x = ~1 then coalescingSavings(mvs, pinned, sc+cost)                          (if debug then print "interfere\n" else ();
169                             moveSavings(mvs, pinned, total))
170                          else if x = ~1 then
171                            (if debug then print (Real.toString cost^"\n") else ();
172                             moveSavings(mvs, pinned, total+cost))
173                    else if pinned >= 0 andalso pinned <> x then                    else if pinned >= 0 andalso pinned <> x then
174                       (* already coalesced with another mem reg *)                       (* already coalesced with another mem reg *)
175                       coalescingSavings(mvs, pinned, sc)                          (if debug then print "pinned\n" else ();
176                             moveSavings(mvs, pinned, total))
177                    else                    else
178                       (* coalescingSavings(mvs, x, sc+cost) *) (* XXX *)                          (if debug then print (Real.toString cost^"\n") else ();
179                       coalescingSavings(mvs, x, sc+cost)                           moveSavings(mvs, x, total+cost))
180    
181                     val _ = if debug then
182                                (print("Savings "^Int.toString d^" <-> "^
183                                                  Int.toString s^"=")
184                                ) else ()
185            in  if d = s then            in  if d = s then
186                   coalescingSavings(mvs, pinned, sc)                      (if debug then print "0 (trivial)\n" else ();
187                         moveSavings(mvs, pinned, total)
188                        )
189                else                else
190                   case (!dstCol, !srcCol) of                   case (!dstCol, !srcCol) of
191                     (SPILLED x, PSEUDO) => savings(x)                        (SPILLED, PSEUDO) => savings(~1)
192                   | (PSEUDO, SPILLED x) => savings(x)                      | (MEMREG(m, _), PSEUDO) => savings(m)
193                   | _ => coalescingSavings(mvs, pinned, sc)                      | (SPILL_LOC s, PSEUDO) => savings(~s)
194                        | (PSEUDO, SPILLED) => savings(~1)
195                        | (PSEUDO, MEMREG(m, _)) => savings(m)
196                        | (PSEUDO, SPILL_LOC s) => savings(~s)
197                        | _ => (if debug then print "0 (other)\n" else ();
198                                moveSavings(mvs, pinned, total))
199                  end
200    
201              (* Find initial budget *)
202              val _ = if debug then
203                          print("Trying to propagate "^Int.toString me^
204                                " spill cost="^Real.toString spillcost^"\n")
205                      else ()
206    
207              val (pinned, savings) = moveSavings(!movelist, ~1, 0.0)
208              val budget = spillcost - savings
209              val S      = [node]
210    
211              (* Find lookahead nodes *)
212              fun lookaheads([], L) = L
213                | lookaheads(MV{cost, dst, src, ...}::mvs, L) =
214                  let val dst as NODE{number=d, ...} = chase dst
215                      val src as NODE{number=s, ...} = chase src
216                      fun check(n, node as NODE{color=ref PSEUDO, ...}) =
217                          if n = me orelse member(n, me) then
218                              lookaheads(mvs, L)
219                          else
220                              add(n, node, L, [])
221                        | check _ = lookaheads(mvs, L)
222                      and add(x, x', (l as (c,n' as NODE{number=y, ...}))::L, L') =
223                           if x = y then
224                              lookaheads(mvs, (cost+c, n')::List.revAppend(L', L))
225                           else add(x, x', L, l::L')
226                        | add(x, x', [], L') =
227                              lookaheads(mvs, (cost, x')::L')
228                  in  if d = me then check(s, src) else check(d, dst)
229                  end
230    
231              (* Now try to improve it by also propagating the lookahead nodes *)
232              fun improve([], pinned, budget, S) = (budget, S)
233                | improve((cost, node as NODE{number=n, movelist, pri, ...})::L,
234                          pinned, budget, S) =
235                  if interferes(n, S) then
236                      (if debug then
237                          print ("Excluding "^Int.toString n^" (interferes)\n")
238                       else ();
239                      improve(L, pinned, budget, S))
240                  else
241                  let val (pinned', savings) = moveSavings(!movelist, pinned, 0.0)
242                      val defUseSavings = cost+cost
243                      val spillcost     = !pri
244                      val budget' = budget - savings - defUseSavings + spillcost
245                  in  if budget' <= budget then
246                         (if debug then print ("Including "^Int.toString n^"\n")
247                          else ();
248                          improve(L, pinned', budget', node::S)
249                         )
250                      else
251                         (if debug then print ("Excluding "^Int.toString n^"\n")
252                          else ();
253                          improve(L, pinned, budget, S))
254                  end
255    
256          in  if budget <= 0.0 then (budget, S)
257              else improve(lookaheads(!movelist, []), pinned, budget, S)
258            end            end
259    
260        (* Insert all spillable neighbors onto the worklist *)        (* Insert all spillable neighbors onto the worklist *)
# Line 173  Line 266 
266                  insert(adj, node::worklist))                  insert(adj, node::worklist))
267          | insert(_::adj, worklist) = insert(adj, worklist)          | insert(_::adj, worklist) = insert(adj, worklist)
268    
269        val marker = SPILLED(~1)        fun insertAll([], worklist) = worklist
270            | insertAll(NODE{adj, ...}::nodes, worklist) =
271                 insertAll(nodes, insert(!adj, worklist))
272    
273          val marker = SPILLED
274    
275        (* Process all nodes from the worklist *)        (* Process all nodes from the worklist *)
276        fun propagate([], spilled) = spilled        fun propagate([], spilled) = spilled
277          | propagate((node as NODE{color as ref PSEUDO,          | propagate((node as NODE{color=ref PSEUDO, ...})::worklist,
                                   pri=ref spillcost, number,  
                                   adj, movelist, ...})::worklist,  
278                      spilled) =                      spilled) =
279            let val (pinned, savings) = coalescingSavings(!movelist, ~1, 0)            let val (budget, S) = coalescingSavings(node)
280            in  (* if (if pinned >= 0 then savings > spillcost                fun spillNodes([]) = ()
281                   else savings >= spillcost) *) (* XXX *)                  | spillNodes(NODE{color, ...}::nodes) =
               if savings >= spillcost  
               then  (* propagate spill *)  
282                   (ra_spill_prop := !ra_spill_prop + 1;                   (ra_spill_prop := !ra_spill_prop + 1;
283                    color := marker; (* spill the node *)                    color := marker; (* spill the node *)
284                    (* print("Propagating "^Int.toString number^" "^                     spillNodes nodes
285                          "savings="^Int.toString(savings)^                    )
286                         " cost="^Int.toString spillcost^"\n"); *)  
287              in  if budget <= 0.0
288                  then  (* propagate spill *)
289                     (if debug then
290                        (print("Propagating ");
291                         app (fn NODE{number=x, ...} => print(Int.toString x^" "))
292                             S;
293                         print "\n")
294                      else ();
295                      spillNodes S;
296                    (* run spill coalescing *)                    (* run spill coalescing *)
297                    spillCoalescing [node];                    spillCoalescing S;
298                    propagate(insert(!adj, worklist), node::spilled)                    propagate(insertAll(S, worklist), List.revAppend(S,spilled))
299                   )                   )
300                else                else
301                   propagate(worklist, spilled)                   propagate(worklist, spilled)
# Line 203  Line 305 
305    
306        (* Initialize worklist *)        (* Initialize worklist *)
307        fun init([], worklist) = worklist        fun init([], worklist) = worklist
308          | init(NODE{adj, color=ref(SPILLED _), ...}::rest, worklist) =          | init(NODE{adj, color=ref(c), ...}::rest, worklist) =
309               if isMemLoc (c) then
310              init(rest, insert(!adj, worklist))              init(rest, insert(!adj, worklist))
311          | init(_::rest, worklist) = init(rest, worklist)             else
312                 init(rest, worklist)
313    
314        (*        (*
315         * Iterate between spill coalescing and propagation         * Iterate between spill coalescing and propagation
# Line 224  Line 328 
328    in  iterate(nodesToSpill, nodesToSpill)    in  iterate(nodesToSpill, nodesToSpill)
329    end    end
330    
331    
332    (*    (*
333     * Spill coloring.     * Spill coloring.
334     * Assign logical spill locations to all the spill nodes.     * Assign logical spill locations to all the spill nodes.
# Line 232  Line 337 
337     *    Spilled copy temporaries are assigned its own set of colors and     *    Spilled copy temporaries are assigned its own set of colors and
338     * cannot share with another other nodes.   They can share colors with     * cannot share with another other nodes.   They can share colors with
339     * themselves however.     * themselves however.
340       *
341       * spillLoc is the first available (logical) spill location.
342     *)     *)
343    fun spillColoring(GRAPH{spillLoc, copyTmps, mode, ...}) nodesToSpill =  
344    let val proh     = A.array(length nodesToSpill, ~1)    fun spillColoring(GRAPH{spillLoc, copyTmps, mode, ...}) nodesToSpill = let
345        val firstLoc = !spillLoc      val proh = A.array(length nodesToSpill, ~1)
346        val _ = spillLoc := firstLoc - 1 (* allocate one location first *)      val firstColor= !spillLoc
347    
348        fun colorCopyTmps(tmps) =      fun colorCopyTmps(tmps) = let
349        let fun loop([], found) = found        fun spillTmp(NODE{color as ref(SPILLED), ...}, found) =
350              | loop(NODE{color as ref(SPILLED ~1), ...}::tmps, found) =             (color := SPILL_LOC(firstColor); true)
351                  (color := SPILLED firstLoc; loop(tmps, true))          | spillTmp(_, found) = found
352              | loop(_::tmps, found) = loop(tmps, found)      in
353        in  if loop(tmps, false) then        if List.foldl spillTmp false tmps then
354               (spillLoc := !spillLoc - 1; firstLoc - 1)          (spillLoc := !spillLoc + 1; firstColor + 1)
355            else firstLoc        else firstColor
       end  
   
       fun selectColor([], firstColor, currLoc) = ()  
         | selectColor(NODE{color as ref(SPILLED ~1), number, adj, ...}::nodes,  
                       firstColor, currLoc) =  
           let fun neighbors [] = ()  
                 | neighbors(n::ns) =  
                   let fun mark(NODE{color=ref(SPILLED loc), ...}) =  
                            (if loc >= ~1 then () (* no location yet *)  
                             else A.update(proh, firstLoc - loc, number);  
                             neighbors ns  
                            )  
                         | mark(NODE{color=ref(ALIASED n), ...}) = mark n  
                         | mark _ = neighbors ns  
                   in  mark n end  
               val _ = neighbors(!adj)  
               fun findColor(loc, startingPoint) =  
                   let val loc = if loc < firstColor then !spillLoc + 1 else loc  
                   in  if A.sub(proh, firstLoc - loc) <> number then loc (* ok *)  
                       else if loc = startingPoint then (* new location *)  
                       let val loc = !spillLoc  
                       in  spillLoc := loc - 1; loc end  
                       else findColor(loc - 1, startingPoint)  
                   end  
               val currLoc = if currLoc < firstColor then !spillLoc + 1  
                             else currLoc  
               val loc = findColor(currLoc, currLoc)  
               (* val _ = print("Spill("^Int.toString number^")="^  
                             Int.toString loc^"\n") *)  
           in  color := SPILLED loc; (* mark with color *)  
               selectColor(nodes, firstColor, loc - 1)  
356            end            end
         | selectColor(_::nodes, firstColor, currLoc) =  
               selectColor(nodes, firstColor, currLoc)  
357    
358        (* color the copy temporaries first *)        (* color the copy temporaries first *)
359         val firstColor = if isOn(mode, RACore.HAS_PARALLEL_COPIES)      val firstColor =
360                          then colorCopyTmps(!copyTmps) else firstLoc        if isOn(mode, RACore.HAS_PARALLEL_COPIES) then
361        (* color the rest of the spilled nodes *)          colorCopyTmps(!copyTmps)
362    in  selectColor(nodesToSpill, firstColor, !spillLoc)        else firstColor
363    
364        fun selectColor([], _, lastLoc) = (spillLoc := lastLoc)
365          | selectColor(NODE{color as ref(SPILLED), number, adj, ...}::nodes,
366                        currLoc, lastLoc) =
367            let
368              fun neighbors(NODE{color=ref(SPILL_LOC s), ...}) =
369                    A.update(proh, s - firstColor, number)
370                | neighbors(NODE{color=ref(ALIASED n), ...}) = neighbors n
371                | neighbors _ = ()
372    
373              val _ =  app neighbors (!adj)
374    
375              fun findColor(loc, startingPt) =
376                if loc = lastLoc then findColor(firstColor, startingPt)
377                else if A.sub(proh, loc-firstColor) <> number then (loc, lastLoc)
378                else if loc  = startingPt then (lastLoc, lastLoc+1)
379                     else findColor(loc+1, startingPt)
380    
381              val (loc, lastLoc) = findColor(currLoc + 1, currLoc)
382    
383            in
384              color := SPILL_LOC(loc); (* mark with color *)
385              selectColor(nodes, loc, lastLoc)
386    end    end
387          | selectColor(_::nodes, currLoc, lastLoc) =
388              selectColor(nodes, currLoc, lastLoc)
389      in
390        (* color the rest of the spilled nodes *)
391        selectColor(nodesToSpill, firstColor, !spillLoc + 1)
392      end (* spillColoring *)
393    
394    end (* local *)    end (* local *)
395    
# Line 309  Line 412 
412         * These are nodes that need also to be spilled         * These are nodes that need also to be spilled
413         *)         *)
414        fun markMemRegs [] = ()        fun markMemRegs [] = ()
415          | markMemRegs(NODE{number=r, color as ref(ALIASED          | markMemRegs(NODE{number=r,
416                       (NODE{color=ref(col as SPILLED c), ...})), ...}::ns) =                             color as ref(ALIASED
417             (if c >= 0 then color := col else ();                                          (NODE{color=ref(col), ...})), ...}::ns) =
418              markMemRegs ns)             (case col of MEMREG _ => color := col | _ => ();
419                markMemRegs(ns))
420          | markMemRegs(_::ns) = markMemRegs ns          | markMemRegs(_::ns) = markMemRegs ns
421    
422        (*        (*
# Line 323  Line 427 
427        fun spillIt{graph = G as GRAPH{mode, ...}, nodes,        fun spillIt{graph = G as GRAPH{mode, ...}, nodes,
428                    copyInstr, spill, spillSrc, spillCopyTmp,                    copyInstr, spill, spillSrc, spillCopyTmp,
429                    reload, reloadDst, renameSrc, cellkind} =                    reload, reloadDst, renameSrc, cellkind} =
430        let val nodes = if isOn(mode,SPILL_PROPAGATION) then        let
431              val nodes = if isOn(mode,SPILL_PROPAGATION) then
432                            spillPropagation G nodes else nodes                            spillPropagation G nodes else nodes
433            val _ = if isOn(mode,SPILL_COALESCING) then            val _ = if isOn(mode,SPILL_COALESCING) then
434                       spillCoalescing G nodes else ()                       spillCoalescing G nodes else ()

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

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