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/cluster-ra.sml
ViewVC logotype

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

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

revision 624, Fri Apr 21 03:06:21 2000 UTC revision 909, Fri Aug 24 17:48:53 2001 UTC
# Line 10  Line 10 
10   *)   *)
11    
12  functor ClusterRA  functor ClusterRA
13     (structure Flowgraph : FLOWGRAPH     (structure Flowgraph : CONTROL_FLOW_GRAPH
14      structure Asm       : INSTRUCTION_EMITTER      structure Asm       : INSTRUCTION_EMITTER
15      structure InsnProps : INSN_PROPERTIES      structure InsnProps : INSN_PROPERTIES
16        sharing Flowgraph.I = InsnProps.I = Asm.I      structure Spill : RA_SPILL
17          sharing Flowgraph.I = InsnProps.I = Asm.I = Spill.I
18        sharing Asm.P = Flowgraph.P        sharing Asm.P = Flowgraph.P
19     ) : RA_FLOWGRAPH =     ) : RA_FLOWGRAPH =
20  struct  struct
21     structure F      = Flowgraph     structure CFG    = Flowgraph
22     structure I      = F.I     structure I      = CFG.I
23     structure W      = F.W     structure W      = CFG.W
    structure C      = I.C  
24     structure G      = RAGraph     structure G      = RAGraph
25     structure Props  = InsnProps     structure Props  = InsnProps
26     structure Core   = RACore     structure Core   = RACore
27     structure A      = Array     structure A      = Array
28     structure UA     = Unsafe.Array (* okay, I'm cheating a bit here *)     structure UA     = Unsafe.Array (* okay, I'm cheating a bit here *)
29     structure Spill  = RASpill(structure InsnProps = InsnProps     structure Spill  = Spill
                               structure Asm       = Asm  
                              )  
   
    structure PrintCluster = PrintCluster  
       (structure Flowgraph = F  
        structure Asm = Asm  
       )  
30    
31     open G     open G
32       structure C      = I.C
33       structure CB     = CellsBasis
34    
35     fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0     fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0
36    
37     type flowgraph = F.cluster (* flowgraph is a cluster *)     val dump_size = MLRiscControl.getFlag "ra-dump-size"
38    
39       type flowgraph = CFG.cfg  (* flowgraph is a cluster *)
40    
41     fun error msg = MLRiscErrorMsg.error("ClusterRA", msg)     fun error msg = MLRiscErrorMsg.error("ClusterRA", msg)
42    
43     val mode = 0w0     val mode = 0w0
44    
45     fun regmap(F.CLUSTER{regmap, ...}) = regmap     fun uniqCells s = CB.SortedCells.return(CB.SortedCells.uniq s)
46    
47     fun dumpFlowgraph(msg, cluster, stream) =     fun chaseCell(c as CB.CELL{col=ref(CB.MACHINE r),...}) = (c,r)
48         PrintCluster.printCluster stream       | chaseCell(CB.CELL{col=ref(CB.ALIASED c), ...}) = chaseCell c
49            ("------------------ "^msg^" ------------------") cluster       | chaseCell(c as CB.CELL{col=ref CB.SPILLED, ...}) = (c,~1)
50         | chaseCell(c as CB.CELL{col=ref CB.PSEUDO, id, ...}) = (c,id)
51    
52       fun colorOf(CB.CELL{col=ref(CB.MACHINE r),...}) = r
53         | colorOf(CB.CELL{col=ref(CB.ALIASED c), ...}) = colorOf c
54         | colorOf(CB.CELL{col=ref CB.SPILLED, ...}) = ~1
55         | colorOf(CB.CELL{col=ref CB.PSEUDO, id, ...}) = id
56    
57       fun chase(NODE{color=ref(ALIASED n), ...}) = chase n
58         | chase n = n
59    
60     exception NotThere     exception NotThere
61    
    (*  
62     val Asm.S.STREAM{emit, ...} = Asm.makeStream []     val Asm.S.STREAM{emit, ...} = Asm.makeStream []
     *)  
63    
64     val dummyLabel = F.LABEL(Label.Label{id= ~1, addr=ref ~1, name=""})     fun dumpFlowgraph(txt, cfg as Graph.GRAPH graph, outstrm) = let
65         fun say txt = TextIO.output(outstrm, txt)
66         fun dump (nid, CFG.BLOCK{data, labels, insns, ...}) = let
67           fun dumpData(CFG.LABEL lab) = say(Label.toString lab ^ "\n")
68             | dumpData(CFG.PSEUDO pOp) = say(CFG.P.toString pOp ^ "\n")
69         in
70           app dumpData (!data);
71           app (fn lab => say(Label.toString lab ^ "\n")) (!labels);
72           app emit (rev (!insns))
73         end
74       in app dump (#nodes graph ())
75       end
76    
77       val dummyBlock =   CFG.newBlock(~1, ref 0)
78    
79     fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))     fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))
80    
81     fun length l =     fun services(cfg as Graph.GRAPH graph) = let
82     let fun loop([],n)   = n         val CFG.INFO{annotations=clAnns, ...} = #graph_info graph
83           | loop(_::l,n) = loop(l,n+1)         val blocks = #nodes graph ()
84     in  loop(l,0) end         fun maxBlockId ((id, CFG.BLOCK _)::rest, curr) =
85               if id > curr then maxBlockId(rest, id) else maxBlockId(rest, curr)
86     fun services(cluster as F.CLUSTER{regmap, blocks, blkCounter, ...}) =           | maxBlockId([], curr) = curr
87     let (* Create a graph based view of cluster *)  
88         val N = !blkCounter         val N = maxBlockId(blocks, #capacity graph ())
89    
90         fun computeShift(0w0, max) = 0w31-max         fun computeShift(0w0, max) = 0w31-max
91           | computeShift(N, max) = computeShift(Word.>>(N, 0w1), Word.+(max,0w1))           | computeShift(N, max) = computeShift(Word.>>(N, 0w1), Word.+(max,0w1))
# Line 85  Line 102 
102         fun instrNum pt = Word.toIntX(Word.andb(Word.fromInt pt, mask))         fun instrNum pt = Word.toIntX(Word.andb(Word.fromInt pt, mask))
103    
104             (* blocks indexed by block id *)             (* blocks indexed by block id *)
105         val blockTable   = A.array(N, dummyLabel)         val blockTable   = A.array(N, (#new_id graph (), dummyBlock))
106    
107         fun fillBlockTable [] = ()         fun fillBlockTable [] = ()
108           | fillBlockTable((b as F.BBLOCK{blknum, ...})::blocks) =           | fillBlockTable((b as (nid, _))::blocks) =
109               (UA.update(blockTable, blknum, b); fillBlockTable blocks)               (UA.update(blockTable, nid, b); fillBlockTable blocks)
          | fillBlockTable(_::blocks) = fillBlockTable blocks  
110         val _ = fillBlockTable blocks         val _ = fillBlockTable blocks
111    
112           val EXIT = (case #exits graph () of [e] => e | _ => error "EXIT")
113    
114         (*         (*
115          * Building the interference graph          * Building the interference graph
116          *)          *)
117         fun buildIt (cellkind, regmap,         fun buildIt (cellkind,
118                      G as GRAPH{nodes, dedicated, mode, span, copyTmps, ...}) =                      G as GRAPH{nodes, dedicated, mode, span, copyTmps, ...}) =
119    
120         let (* definitions indexed by block id+instruction id *)         let (* definitions indexed by block id+instruction id *)
121             val defsTable    = A.array(N, A.array(0, [] : node list))             val defsTable    = A.array(N, A.array(0, [] : node list))
122             val marked       = A.array(N, ~1)             val marked       = A.array(N, ~1)
123               val addEdge      = Core.addEdge G
124    
125             (* copies indexed by source *)             (* copies indexed by source
126             val copyTable    = Intmap.new(N, NotThere)              * This table maps variable v to the program points where
127             val lookupCopy   = Intmap.mapWithDefault(copyTable, [])              * v is a source of a copy.
128             val addCopy      = Intmap.add copyTable              *)
129               val copyTable    = IntHashTable.mkTable(N, NotThere)
130                    : {dst:CB.cell,pt:int} list IntHashTable.hash_table
131               val lookupCopy   = IntHashTable.find copyTable
132               val lookupCopy   = fn r => case lookupCopy r of SOME c => c
133                                                             | NONE => []
134               val addCopy      = IntHashTable.insert copyTable
135    
136             val stamp = ref 0             val stamp = ref 0
137    
138             (* Allocate the arrays *)             (* Allocate the arrays *)
139             fun alloc [] = ()             fun alloc [] = ()
140               | alloc((b as F.BBLOCK{blknum, insns, ...})::blocks) =               | alloc((id, CFG.BLOCK{insns, ...})::blocks) =
141                 let val n = length(!insns)                  (UA.update(defsTable, id, A.array(length(!insns)+1, []));
142                     val m = n+1                   alloc blocks)
                in  UA.update(defsTable, blknum, A.array(m, []));  
                    alloc blocks  
                end  
              | alloc(_::blocks) = alloc blocks  
143             val _ = alloc blocks             val _ = alloc blocks
144    
145             (*             (*
# Line 131  Line 151 
151             (*             (*
152              * Initialize the definitions before computing the liveness for v.              * Initialize the definitions before computing the liveness for v.
153              *)              *)
154             fun initialize(v,v',useSites) =             fun initialize(v, v', useSites) = let
155             let (* First we remove all definitions for all copies                 (* First we remove all definitions for all copies
156                  * with v as source.                  * with v as source.
157                    * When we have a copy and while we are processing v
158                    *
159                    *      x <- v
160                    *
161                    *  x does not really interfere with v at this point,
162                    *  so we remove the definition of x temporarily.
163                  *)                  *)
164                 fun markCopies([], trail) = trail                 fun markCopies([], trail) = trail
165                   | markCopies({pt, dst}::copies, trail) =                   | markCopies({pt, dst}::copies, trail) =
# Line 143  Line 169 
169                         val nodes = UA.sub(defs, i)                         val nodes = UA.sub(defs, i)
170                         fun revAppend([], nodes) = nodes                         fun revAppend([], nodes) = nodes
171                           | revAppend(n::ns, nodes) = revAppend(ns, n::nodes)                           | revAppend(n::ns, nodes) = revAppend(ns, n::nodes)
172                           val dstColor = colorOf dst
173                         fun removeDst([], nodes') = nodes'                         fun removeDst([], nodes') = nodes'
174                           | removeDst((d as NODE{number=r,...})::nodes, nodes')=                           | removeDst((d as NODE{number=r,...})::nodes, nodes')=
175                             if r = dst then revAppend(nodes', nodes)                             if r = dstColor then revAppend(nodes', nodes)
176                             else removeDst(nodes, d::nodes')                             else removeDst(nodes, d::nodes')
177                         val nodes' = removeDst(nodes, [])                         val nodes' = removeDst(nodes, [])
178                     in  UA.update(defs, i, nodes');                     in  UA.update(defs, i, nodes');
# Line 153  Line 180 
180                     end                     end
181    
182                 (*                 (*
183                  * Then we mark all use sites of v                  * Then we mark all use sites of v with a fake definition so that
184                    * the scanning will terminate correctly at these points.
185                  *)                  *)
186                 fun markUseSites([], trail) = trail                 fun markUseSites([], trail) = trail
187                   | markUseSites(pt::pts, trail) =                   | markUseSites(pt::pts, trail) =
# Line 177  Line 205 
205              * Perform incremental liveness analysis on register v              * Perform incremental liveness analysis on register v
206              * and compute the span              * and compute the span
207              *)              *)
208             fun liveness(v, v' as NODE{uses, ...}, addEdge) =             fun liveness(v, v' as NODE{uses, ...}, cellV) = let
209             let val st = !stamp                 val st = !stamp
210                 val _  = stamp := st + 1                 val _  = stamp := st + 1
211                 fun foreachUseSite([], span) = span                 fun foreachUseSite([], span) = span
212                   | foreachUseSite(u::uses, span) =                   | foreachUseSite(u::uses, span) = let
213                     let val b = blockNum u                       val b = blockNum u
214                         val i = instrNum u                         val i = instrNum u
215                     in  case UA.sub(blockTable, b) of                       val block as (_, CFG.BLOCK{freq, ...}) = UA.sub(blockTable, b)
216                           block as F.BBLOCK{freq, ...} =>                       val span =
217                           let val span =                         if i = 0 then liveOutAtBlock(block, span) (* live out *)
218                                 if i = 0 then                         else let
219                                    liveOutAtBlock(block, span) (* live out *)                             val f = !freq
                               else  
                                   let val f = !freq  
220                                        val defs = UA.sub(defsTable, b)                                        val defs = UA.sub(defsTable, b)
221                                    in  liveOutAtStmt(block, A.length defs,                           in  liveOutAtStmt(block, A.length defs, defs, i+1, f, span+f)
                                                     defs, i+1, f, span+f)  
                                   end;  
                          in  foreachUseSite(uses, span)  
222                           end                           end
223                         | _ => error "liveness2"                     in foreachUseSite(uses, span)
224                     end                     end
225    
226                 and visitPred(block, span) =                 and visitPred((nid, _), span) =
227                     let fun foreachPred([], span) = span                     let fun foreachPred([], span) = span
228                           | foreachPred((b, _)::pred, span) =                           | foreachPred(nid::pred, span) = let
229                             let val span = liveOutAtBlock(b, span)                                val span = liveOutAtBlock((nid, #node_info graph nid), span)
230                             in  foreachPred(pred, span) end                             in  foreachPred(pred, span)
231                     in  case block of                             end
232                           F.BBLOCK{pred, ...} => foreachPred(!pred, span)                     in
233                         | _ => error "visitPred"                       foreachPred(#pred graph nid, span)
234                     end                     end
235    
236                 and liveOutAtStmt(block, nDefs, defs, pos, freq, span) =                 and liveOutAtStmt(block, nDefs, defs, pos, freq, span) =
# Line 224  Line 247 
247                     end                     end
248                     else visitPred(block, span)                     else visitPred(block, span)
249    
250                 and liveOutAtBlock(block as F.BBLOCK{blknum, freq, ...}, span) =                 and liveOutAtBlock(block as (nid, CFG.BLOCK{freq, ...}), span) =
251                     (* v is live out at the current block *)                     (* v is live out at the current block *)
252                     if UA.sub(marked, blknum) = st then span                     if UA.sub(marked, nid) = st then span
253                     else                     else let
254                        (UA.update(marked, blknum, st);                         val defs = UA.sub(defsTable, nid)
255                         let val defs = UA.sub(defsTable, blknum)                       in
256                         in  liveOutAtStmt(block, A.length defs, defs,                         UA.update(marked, nid, st);
257                                           1, !freq, span)                         liveOutAtStmt(block, A.length defs, defs, 1, !freq, span)
258                         end                         end
                       )  
                  | liveOutAtBlock(_, span) = span  
259    
260                 val useSites = SortedList.uniq(!uses)                 val useSites = SortedList.uniq(!uses)
261                 val trail    = initialize(v, v', useSites)                 val trail    = initialize(v, v', useSites)
262                 val span     = foreachUseSite (useSites, 0)                 val span     = foreachUseSite (useSites, 0)
263                 val _        = cleanup trail                 val _        = cleanup trail
264             in  span             in
265                 span
266             end             end
267    
268             val newNodes   = Core.newNodes G             val newNodes   = Core.newNodes G
269             val getnode    = Intmap.map nodes             val getnode    = IntHashTable.lookup nodes
270             val insnDefUse = Props.defUse cellkind             val insnDefUse = Props.defUse cellkind
271             val getCell    = C.getCell cellkind             val getCell    = C.getCellsByKind cellkind
272    
273             fun isDedicated r =             fun isDedicated r = dedicated r
               Word.fromInt r < Word.fromInt(A.length dedicated)  
               andalso UA.sub(dedicated, r)  
274    
275            (* Remove all dedicated or spilled registers from the list *)            (* Remove all dedicated or spilled registers from the list *)
276             fun rmvDedicated regs =             fun rmvDedicated regs =
277             let fun loop([], rs') = rs'             let fun loop([], rs') = rs'
278                   | loop(r::rs, rs') =                   | loop(r::rs, rs') =
279                 let val r = regmap r                     let fun rmv(r as CB.CELL{col=ref(CB.PSEUDO), id, ...}) =
280                 in  loop(rs, if isDedicated r then rs' else r::rs') end                               if isDedicated(id) then loop(rs, rs') else loop(rs, r::rs')
281                             | rmv(CB.CELL{col=ref(CB.ALIASED r), ...}) = rmv r
282                             | rmv(r as CB.CELL{col=ref(CB.MACHINE col), ...}) =
283                                 if isDedicated col then loop(rs, rs')
284                                 else loop(rs, r::rs')
285                             | rmv(CB.CELL{col=ref(CB.SPILLED), ...}) = loop(rs,rs')
286                       in  rmv r
287                       end
288             in  loop(regs, []) end             in  loop(regs, []) end
289    
290             (*             (*
# Line 269  Line 296 
296                         case (Props.moveTmpR insn, dst) of                         case (Props.moveTmpR insn, dst) of
297                           (SOME r, _::dst) =>                           (SOME r, _::dst) =>
298                             (* Add a pseudo use for tmpR *)                             (* Add a pseudo use for tmpR *)
299                           let fun chase(NODE{color=ref(ALIASED n), ...}) =                            (case chase(getnode(colorOf r)) of
                                   chase n  
                                | chase n = n  
                          in  case chase(getnode r) of  
300                                 tmp as NODE{uses,defs=ref [d],...} =>                                 tmp as NODE{uses,defs=ref [d],...} =>
301                                    (uses := [d-1]; (dst, tmp::tmps))                                    (uses := [d-1]; (dst, tmp::tmps))
302                               | _ => error "mkMoves"                               | _ => error "mkMoves"
303                           end                            )
304                         | (_, dst) => (dst, tmps)                         | (_, dst) => (dst, tmps)
305                     fun moves([], [], mv) = mv                     fun moves([], [], mv) = mv
306                       | moves(d::ds, s::ss, mv) =                       | moves(d::ds, s::ss, mv) =
307                         if isDedicated d orelse isDedicated s                         let val (d, cd) = chaseCell d
308                               val (s, cs) = chaseCell s
309                           in  if isDedicated cd orelse isDedicated cs
310                         then moves(ds, ss, mv)                         then moves(ds, ss, mv)
311                               else if cd = cs then moves(ds, ss, mv)
312                         else                         else
313                         let fun chases(NODE{color=ref(ALIASED src), ...}, dst) =                               let val _ =
314                                   chases(src, dst)                                    addCopy(cs, {dst=d, pt=pt}::lookupCopy cs);
315                               | chases(src, dst) = chases'(src, dst)                                   val dst = chase(getnode cd)
316                             and chases'(src, NODE{color=ref(ALIASED dst), ...}) =                                   val src = chase(getnode cs)
317                                   chases'(src, dst)                               in  moves(ds, ss, MV{dst=dst, src=src,
                              | chases'(src, dst) = (src, dst)  
                            val (src as NODE{number=s, ...},  
                                 dst as NODE{number=d, ...}) =  
                                    chases(getnode s, getnode d)  
                        in if d = s then moves(ds, ss, mv)  
                           else (addCopy(s, {dst=d, pt=pt}::lookupCopy s);  
                                 moves(ds, ss, MV{dst=dst, src=src,  
318                                                  status=ref WORKLIST,                                                  status=ref WORKLIST,
319                                                  hicount=ref 0,                                                  hicount=ref 0,
320                                                  (* kind=REG_TO_REG, *)                                                  (* kind=REG_TO_REG, *)
321                                                  cost=cost}::mv)                                                     cost=cost}::mv
322                                 )                                 )
323                         end                         end
324                           end
325                       | moves _ = error "moves"                       | moves _ = error "moves"
326                 in  (moves(dst, src, mv), tmps) end                 in  (moves(dst, src, mv), tmps) end
327                 else (mv, tmps)                 else (mv, tmps)
328    
329    
330    
331             (* Add the nodes first *)             (* Add the nodes first *)
332             fun mkNodes([], mv, tmps) = (mv, tmps)             fun mkNodes([], mv, tmps) = (mv, tmps)
333               | mkNodes(F.BBLOCK{blknum, insns, succ, freq=ref w,               | mkNodes((nid, blk)::blocks, mv, tmps) = let
334                                  liveOut, ...}::blks, mv, tmps)=                   val CFG.BLOCK{insns, freq=ref w, annotations, ...} = blk
335                 let val dtab = A.sub(defsTable, blknum)                   val succ = #succ graph nid
336                     val liveOut = CFG.liveOut blk
337                     val dtab = A.sub(defsTable, nid)
338                     fun scan([], pt, i, mv, tmps) = (pt, i, mv, tmps)                     fun scan([], pt, i, mv, tmps) = (pt, i, mv, tmps)
339                       | scan(insn::rest, pt, i, mv, tmps) =                       | scan(insn::rest, pt, i, mv, tmps) =
340                         let val (d, u) = insnDefUse insn                         let val (d, u) = insnDefUse insn
# Line 318  Line 343 
343                             val defs = newNodes{cost=w, pt=pt,                             val defs = newNodes{cost=w, pt=pt,
344                                                 defs=defs, uses=uses}                                                 defs=defs, uses=uses}
345                             val _    = UA.update(dtab, i, defs)                             val _    = UA.update(dtab, i, defs)
346                             val (mv, tmps) = mkMoves(insn, pt, d, u, w, mv, tmps)                           val (mv, tmps) =
347                                   mkMoves(insn, pt, d, u, w, mv, tmps)
348                         in  scan(rest, pt+1, i+1, mv, tmps)                         in  scan(rest, pt+1, i+1, mv, tmps)
349                         end                         end
350                     val (pt, i, mv, tmps) =                     val (pt, i, mv, tmps) =
351                         scan(!insns, progPt(blknum,1), 1, mv, tmps)                     scan(!insns, progPt(nid,1), 1, mv, tmps)
352                     val _ = if pt >= progPt(blknum+1, 0) then                   val _ =
353                       if pt >= progPt(nid+1, 0) then
354                                error("mkNodes: too many instructions")                                error("mkNodes: too many instructions")
355                             else ()                             else ()
356                 in  (* If the block is escaping, then all liveout                 in
357                     (* If the block is escaping, then all liveout
358                      * registers are considered used here.                      * registers are considered used here.
359                      *)                      *)
360                     case !succ of                    case succ
361                        [(F.EXIT _, _)] =>                     of [id] =>
362                        let val liveSet = rmvDedicated(getCell(!liveOut))                        if id = EXIT then let
363                        in  newNodes{cost=w, pt=progPt(blknum, 0),                            val liveSet = rmvDedicated(
364                                               uniqCells(getCell(liveOut)))
365                            in  newNodes{cost=w, pt=progPt(nid, 0),
366                                     defs=[], uses=liveSet}; ()                                     defs=[], uses=liveSet}; ()
367                        end                        end
368                          else ()
369                     | _ => ()                     | _ => ()
370                     ;                    (*esac*);
371                     mkNodes(blks, mv, tmps)                    mkNodes(blocks, mv, tmps)
372                 end                 end
              | mkNodes(_::blks, mv, tmps) = mkNodes(blks, mv, tmps)  
373    
374            (* Add the edges *)            (* Add the edges *)
375    
376             val (moves, tmps) = mkNodes(blocks, [], [])             val (moves, tmps) = mkNodes(blocks, [], [])
377             val addEdge = Core.addEdge G         in
378         in  Intmap.app             IntHashTable.appi
379               (let val setSpan =               (let val setSpan =
380                    if isOn(mode,Core.COMPUTE_SPAN) then                    if isOn(mode,Core.COMPUTE_SPAN) then
381                    let val spanMap = Intmap.new(Intmap.elems nodes, NotThere)                    let val spanMap = IntHashTable.mkTable
382                        val setSpan = Intmap.add spanMap                                          (IntHashTable.numItems nodes, NotThere)
383                          val setSpan = IntHashTable.insert spanMap
384                        val _       = span := SOME spanMap                        val _       = span := SOME spanMap
385                    in  setSpan end                    in  setSpan end
386                    else fn _ => ()                    else fn _ => ()
387                in  fn (v, v' as NODE{color=ref(PSEUDO | COLORED _), ...}) =>                in  fn (v, v' as NODE{cell, color, ...}) =>
388                       setSpan(v, liveness(v, v', addEdge))                    let fun computeLiveness() =
389                     | (v, v' as NODE{color=ref(SPILLED c), ...}) =>                             setSpan(v, liveness(v, v', cell))
390                       if c >= 0 then setSpan(v, liveness(v, v', addEdge)) else ()                    in  case !color of
391                            PSEUDO => computeLiveness()
392                          | COLORED _ => computeLiveness()
393                          | MEMREG _ => computeLiveness()
394                     | _ => ()                     | _ => ()
395                end                end
396                  end
397               ) nodes;               ) nodes;
398             if isOn(Core.SAVE_COPY_TEMPS, mode) then copyTmps := tmps else ();             if isOn(Core.SAVE_COPY_TEMPS, mode) then copyTmps := tmps else ();
399             rmPseudoUses tmps;             rmPseudoUses tmps;
400             moves             moves
401         end         end (* buildIt *)
402    
403         (*         (*
404          * Build the interference graph initially.          * Build the interference graph initially.
405          *)          *)
406         fun build(G, cellkind) = buildIt(cellkind, C.lookup regmap, G)         fun build(G, cellkind) = let
407             val moves = buildIt(cellkind, G)
408             val i2s = Int.toString
409           in
410             if !dump_size then let
411                  val GRAPH{nodes, bitMatrix,...} = G
412                  val insns =
413                    foldr (fn ((_,CFG.BLOCK{insns,...}),n) => length(!insns) + n) 0 blocks
414                in
415                  TextIO.output
416                     (!MLRiscControl.debug_stream,
417                      "RA #blocks="^i2s N ^
418                        " #insns="^i2s insns ^
419                        " #nodes="^i2s(IntHashTable.numItems nodes) ^
420                        " #edges="^i2s(Core.BM.size(!bitMatrix)) ^
421                        " #moves="^i2s(length moves)^"\n")
422                end
423             else ();
424             moves
425           end
426    
427         (*         (*
428          * Rebuild the interference graph;          * Rebuild the interference graph;
# Line 376  Line 430 
430          *)          *)
431         fun rebuild(cellkind, G) =         fun rebuild(cellkind, G) =
432             (Core.clearNodes G;             (Core.clearNodes G;
433              buildIt(cellkind, Core.regmap G, G)              buildIt(cellkind, G)
434             )             )
435    
436         (*         (*
437          * Spill a set of nodes and rewrite the flowgraph          * Spill a set of nodes and rewrite the flowgraph
438          *)          *)
439         fun spill{copyInstr, spill, spillSrc, spillCopyTmp,         fun spill{copyInstr, spill, spillSrc, spillCopyTmp,
440                   reload, reloadDst, renameSrc, graph as G.GRAPH{regmap, ...},                   reload, reloadDst, renameSrc, graph,
441                   cellkind, nodes=nodesToSpill} =                   cellkind, nodes=nodesToSpill} =
442         let (* Remove the interference graph now *)         let (* Remove the interference graph now *)
443             val _ = Core.clearGraph graph             val _ = Core.clearGraph graph
444    
445             (* maps program point to registers to be spilled *)             (* maps program point to registers to be spilled *)
446             val spillSet = Intmap.new(32, NotThere) : C.cell list Intmap.intmap             val spillSet = IntHashTable.mkTable(32, NotThere)
447    
448             (* maps program point to registers to be reloaded *)             (* maps program point to registers to be reloaded *)
449             val reloadSet = Intmap.new(32, NotThere) : C.cell list Intmap.intmap             val reloadSet = IntHashTable.mkTable(32, NotThere)
450    
451             (* maps program point to registers to be killed *)             (* maps program point to registers to be killed *)
452             val killSet = Intmap.new(32, NotThere) : C.cell list Intmap.intmap             val killSet = IntHashTable.mkTable(32, NotThere)
453    
454             val spillRewrite = Spill.spillRewrite             val spillRewrite = Spill.spillRewrite
455                                { graph=graph,                                { graph=graph,
# Line 413  Line 467 
467                                }                                }
468    
469             (* set of basic blocks that are affected *)             (* set of basic blocks that are affected *)
470             val affectedBlocks = Intmap.new(32, NotThere) : bool Intmap.intmap             val affectedBlocks = IntHashTable.mkTable(32, NotThere)
471    
472             val addAffectedBlocks = Intmap.add affectedBlocks             val addAffectedBlocks = IntHashTable.insert affectedBlocks
473    
474             fun ins set =             fun ins set = let
475             let val add  = Intmap.add set                 val add  = IntHashTable.insert set
476                 val look = Intmap.mapWithDefault(set, [])                 val look = IntHashTable.find set
477                   val look = fn r => case look r of SOME s => s | NONE => []
478                 fun enter(r, []) = ()                 fun enter(r, []) = ()
479                   | enter(r, pt::pts) =                   | enter(r, pt::pts) =
480                     (add (pt, r::look pt);                     (add (pt, r::look pt);
# Line 432  Line 487 
487             val insSpillSet  = ins spillSet             val insSpillSet  = ins spillSet
488             val insReloadSet = ins reloadSet             val insReloadSet = ins reloadSet
489             val insKillSet   =             val insKillSet   =
490             let val add  = Intmap.add killSet               let
491                 val look = Intmap.mapWithDefault(killSet, [])                 val add  = IntHashTable.insert killSet
492                   val look = IntHashTable.find killSet
493                   val look = fn r => case look r of SOME s => s | NONE => []
494                 fun enter(r, []) = ()                 fun enter(r, []) = ()
495                   | enter(r, pt::pts) = (add(pt, r::look pt); enter(r, pts))                   | enter(r, pt::pts) = (add(pt, r::look pt); enter(r, pts))
496             in  enter             in  enter
497             end             end
498    
499             (* Mark all spill/reload locations *)             (* Mark all spill/reload locations *)
500             fun markSpills [] = ()             fun markSpills(G.NODE{color, number, cell, defs, uses, ...}) =
              | markSpills(  
                 G.NODE{color, number, defs as ref d, uses as ref u, ...}::ns) =  
501                 let fun spillIt(defs, uses) =                 let fun spillIt(defs, uses) =
502                         (insSpillSet(number, defs);                         (insSpillSet(cell, defs);
503                          insReloadSet(number, uses);                          insReloadSet(cell, uses);
504                          (* Definitions but no use! *)                          (* Definitions but no use! *)
505                          case uses of                          case uses of
506                             [] => insKillSet(number, defs)                             [] => insKillSet(cell, defs)
507                           | _ => ()                           | _ => ()
508                         )                         )
509                 in  case !color of                     val d = !defs
510                       G.SPILLED c => spillIt(d, u)                     val u = !uses
511                   in
512                     case !color
513                     of G.SPILLED     => spillIt(d,u)
514                      | G.SPILL_LOC _ => spillIt(d,u)
515                      | G.MEMREG _    => spillIt(d,u)
516                     | G.PSEUDO => spillIt(d, u)                     | G.PSEUDO => spillIt(d, u)
517                     | _ => ();                    | _ => ()
                    markSpills ns  
518                 end                 end
519             val _ = markSpills nodesToSpill             val _ = app markSpills nodesToSpill
520    
521             (* Rewrite all affected blocks *)             (* Rewrite all affected blocks *)
522             fun rewriteAll (blknum, _) =             fun rewriteAll (blknum, _) = let
523                 case A.sub(blockTable, blknum) of               val (_, CFG.BLOCK{insns as ref instrs, annotations, ...}) =
524                    F.BBLOCK{annotations, insns as ref instrs, ...} =>                 A.sub(blockTable, blknum)
525                    let val instrs =               val instrs =
526                            spillRewrite{pt=progPt(blknum, length instrs),                            spillRewrite{pt=progPt(blknum, length instrs),
527                                         instrs=instrs,                              instrs=instrs, annotations=annotations}
528                                         annotations=annotations}             in
529                    in  insns := instrs               insns := instrs
                   end  
                | _ => error "rewriteAll"  
   
        in  Intmap.app rewriteAll affectedBlocks;  
            let val spilledMarker = SPILLED ~2  
                fun mark [] = ()  
                  | mark(G.NODE{number, color as ref(SPILLED c), ...}::rest)=  
                      (if number <> c then color := spilledMarker else ();  
                       mark rest)  
                  | mark(G.NODE{color as ref PSEUDO, ...}::rest) =  
                       (color := spilledMarker; mark rest)  
                  | mark(_::rest) = mark rest  
            in  mark nodesToSpill  
            end;  
            rebuild(cellkind, graph)  
530         end         end
531    
532     in  {build=build, spill=spill,  
533               fun mark(G.NODE{color, ...}) =
534                 (case !color
535                  of PSEUDO => color := SPILLED
536                   | SPILLED => ()
537                   | SPILL_LOC _ => ()
538                   | ALIASED _ => ()
539                   | MEMREG _ => ()
540                   | COLORED _ => error "mark: COLORED"
541                   | REMOVED =>  error "mark: REMOVED"
542                 (*esac*))
543           in
544             IntHashTable.appi rewriteAll affectedBlocks;
545             app mark nodesToSpill;
546             rebuild(cellkind, graph)
547           end (* spill *)
548       in
549         { build       = build,
550           spill       = spill,
551          programPoint=fn{block,instr} => progPt(block,instr),          programPoint=fn{block,instr} => progPt(block,instr),
552          blockNum=blockNum,          blockNum=blockNum,
553          instrNum=instrNum          instrNum=instrNum
554         }         }
555     end     end
   
556  end  end
557    

Legend:
Removed from v.624  
changed lines
  Added in v.909

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