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 733, Fri Nov 17 05:13:45 2000 UTC revision 744, Fri Dec 8 04:11:42 2000 UTC
# Line 13  Line 13 
13     (structure Flowgraph : FLOWGRAPH     (structure Flowgraph : FLOWGRAPH
14      structure Asm       : INSTRUCTION_EMITTER      structure Asm       : INSTRUCTION_EMITTER
15      structure InsnProps : INSN_PROPERTIES      structure InsnProps : INSN_PROPERTIES
16          where C = CellsBasis
17      structure Spill : RA_SPILL      structure Spill : RA_SPILL
18        sharing Flowgraph.I = InsnProps.I = Asm.I = Spill.I        sharing Flowgraph.I = InsnProps.I = Asm.I = Spill.I
19        sharing Asm.P = Flowgraph.P        sharing Asm.P = Flowgraph.P
# Line 21  Line 22 
22     structure F      = Flowgraph     structure F      = Flowgraph
23     structure I      = F.I     structure I      = F.I
24     structure W      = F.W     structure W      = F.W
    structure C      = I.C  
25     structure G      = RAGraph     structure G      = RAGraph
26     structure Props  = InsnProps     structure Props  = InsnProps
27     structure Core   = RACore     structure Core   = RACore
# Line 35  Line 35 
35        )        )
36    
37     open G     open G
38       structure C  = I.C
39    
40     fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0     fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0
41    
# Line 44  Line 45 
45    
46     fun error msg = MLRiscErrorMsg.error("ClusterRA", msg)     fun error msg = MLRiscErrorMsg.error("ClusterRA", msg)
47    
48       val i2s = Int.toString
49    
50     val mode = 0w0     val mode = 0w0
51    
52     fun regmap(F.CLUSTER{regmap, ...}) = regmap     fun uniqCells s = C.SortedCells.return(C.SortedCells.uniq s)
53    
54       fun chaseCell(c as C.CELL{col=ref(C.MACHINE r),...}) = (c,r)
55         | chaseCell(C.CELL{col=ref(C.ALIASED c), ...}) = chaseCell c
56         | chaseCell(c as C.CELL{col=ref C.SPILLED, ...}) = (c,~1)
57         | chaseCell(c as C.CELL{col=ref C.PSEUDO, id, ...}) = (c,id)
58    
59       fun colorOf(C.CELL{col=ref(C.MACHINE r),...}) = r
60         | colorOf(C.CELL{col=ref(C.ALIASED c), ...}) = colorOf c
61         | colorOf(C.CELL{col=ref C.SPILLED, ...}) = ~1
62         | colorOf(C.CELL{col=ref C.PSEUDO, id, ...}) = id
63    
64       fun chase(NODE{color=ref(ALIASED n), ...}) = chase n
65         | chase n = n
66    
67     fun dumpFlowgraph(msg, cluster, stream) =     fun dumpFlowgraph(msg, cluster, stream) =
68         PrintCluster.printCluster stream         PrintCluster.printCluster stream
# Line 63  Line 79 
79           | loop(_::l,n) = loop(l,n+1)           | loop(_::l,n) = loop(l,n+1)
80     in  loop(l,0) end     in  loop(l,0) end
81    
82     fun services(cluster as F.CLUSTER{regmap, blocks, blkCounter, ...}) =     fun services(cluster as F.CLUSTER{blocks, blkCounter, ...}) =
83     let (* Create a graph based view of cluster *)     let (* Create a graph based view of cluster *)
84         val N = !blkCounter         val N = !blkCounter
85    
# Line 93  Line 109 
109         (*         (*
110          * Building the interference graph          * Building the interference graph
111          *)          *)
112         fun buildIt (cellkind, regmap,         fun buildIt (cellkind,
113                      G as GRAPH{nodes, dedicated, mode, span, copyTmps, ...}) =                      G as GRAPH{nodes, dedicated, mode, span, copyTmps, ...}) =
114    
115         let (* definitions indexed by block id+instruction id *)         let (* definitions indexed by block id+instruction id *)
116             val defsTable    = A.array(N, A.array(0, [] : node list))             val defsTable    = A.array(N, A.array(0, [] : node list))
117             val marked       = A.array(N, ~1)             val marked       = A.array(N, ~1)
118               val addEdge      = Core.addEdge G
119    
120             (* copies indexed by source *)             (* copies indexed by source
121                * This table maps variable v to the program points where
122                * v is a source of a copy.
123                *)
124             val copyTable    = IntHashTable.mkTable(N, NotThere)             val copyTable    = IntHashTable.mkTable(N, NotThere)
125             fun lookupCopy i = getOpt (IntHashTable.find copyTable i, [])                  : {dst:C.cell,pt:int} list IntHashTable.hash_table
126               val lookupCopy   = IntHashTable.find copyTable
127               val lookupCopy   = fn r => case lookupCopy r of SOME c => c
128                                                             | NONE => []
129             val addCopy      = IntHashTable.insert copyTable             val addCopy      = IntHashTable.insert copyTable
130    
131    
# Line 131  Line 154 
154             fun initialize(v,v',useSites) =             fun initialize(v,v',useSites) =
155             let (* First we remove all definitions for all copies             let (* 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 140  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 150  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 174  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) =
209             let val st = !stamp             let val st = !stamp
210                 val _  = stamp := st + 1                 val _  = stamp := st + 1
211                 fun foreachUseSite([], span) = span                 fun foreachUseSite([], span) = span
# Line 243  Line 274 
274             val newNodes   = Core.newNodes G             val newNodes   = Core.newNodes G
275             val getnode    = IntHashTable.lookup nodes             val getnode    = IntHashTable.lookup nodes
276             val insnDefUse = Props.defUse cellkind             val insnDefUse = Props.defUse cellkind
277             val getCell    = C.getCell cellkind             val getCell    = C.CellSet.get cellkind
278    
279             fun isDedicated r =             fun isDedicated r =
280                Word.fromInt r < Word.fromInt(A.length dedicated)                Word.fromInt r < Word.fromInt(A.length dedicated)
# Line 253  Line 284 
284             fun rmvDedicated regs =             fun rmvDedicated regs =
285             let fun loop([], rs') = rs'             let fun loop([], rs') = rs'
286                   | loop(r::rs, rs') =                   | loop(r::rs, rs') =
287                 let val r = regmap r                     let fun rmv(r as C.CELL{col=ref(C.PSEUDO), ...}) =
288                 in  loop(rs, if isDedicated r then rs' else r::rs') end                               loop(rs, r::rs')
289                             | rmv(C.CELL{col=ref(C.ALIASED r), ...}) = rmv r
290                             | rmv(r as C.CELL{col=ref(C.MACHINE col), ...}) =
291                                 if isDedicated col then loop(rs, rs')
292                                 else loop(rs, r::rs')
293                             | rmv(C.CELL{col=ref(C.SPILLED), ...}) = loop(rs,rs')
294                       in  rmv r
295                       end
296             in  loop(regs, []) end             in  loop(regs, []) end
297    
298             (*             (*
# Line 266  Line 304 
304                         case (Props.moveTmpR insn, dst) of                         case (Props.moveTmpR insn, dst) of
305                           (SOME r, _::dst) =>                           (SOME r, _::dst) =>
306                             (* Add a pseudo use for tmpR *)                             (* Add a pseudo use for tmpR *)
307                           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  
308                                 tmp as NODE{uses,defs=ref [d],...} =>                                 tmp as NODE{uses,defs=ref [d],...} =>
309                                    (uses := [d-1]; (dst, tmp::tmps))                                    (uses := [d-1]; (dst, tmp::tmps))
310                               | _ => error "mkMoves"                               | _ => error "mkMoves"
311                           end                            )
312                         | (_, dst) => (dst, tmps)                         | (_, dst) => (dst, tmps)
313                     fun moves([], [], mv) = mv                     fun moves([], [], mv) = mv
314                       | moves(d::ds, s::ss, mv) =                       | moves(d::ds, s::ss, mv) =
315                         if isDedicated d orelse isDedicated s                         let val (d, cd) = chaseCell d
316                               val (s, cs) = chaseCell s
317                           in  if isDedicated cd orelse isDedicated cs
318                         then moves(ds, ss, mv)                         then moves(ds, ss, mv)
319                               else if cd = cs then moves(ds, ss, mv)
320                         else                         else
321                         let fun chases(NODE{color=ref(ALIASED src), ...}, dst) =                               let val _ =
322                                   chases(src, dst)                                    addCopy(cs, {dst=d, pt=pt}::lookupCopy cs);
323                               | chases(src, dst) = chases'(src, dst)                                   val dst = chase(getnode cd)
324                             and chases'(src, NODE{color=ref(ALIASED dst), ...}) =                                   val src = chase(getnode cs)
325                                   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,  
326                                                  status=ref WORKLIST,                                                  status=ref WORKLIST,
327                                                  hicount=ref 0,                                                  hicount=ref 0,
328                                                  (* kind=REG_TO_REG, *)                                                  (* kind=REG_TO_REG, *)
329                                                  cost=cost}::mv)                                                     cost=cost}::mv
330                                 )                                 )
331                         end                         end
332                           end
333                       | moves _ = error "moves"                       | moves _ = error "moves"
334                 in  (moves(dst, src, mv), tmps) end                 in  (moves(dst, src, mv), tmps) end
335                 else (mv, tmps)                 else (mv, tmps)
# Line 315  Line 347 
347                             val defs = newNodes{cost=w, pt=pt,                             val defs = newNodes{cost=w, pt=pt,
348                                                 defs=defs, uses=uses}                                                 defs=defs, uses=uses}
349                             val _    = UA.update(dtab, i, defs)                             val _    = UA.update(dtab, i, defs)
350                             val (mv, tmps) = mkMoves(insn, pt, d, u, w, mv, tmps)                             val (mv, tmps) =
351                                     mkMoves(insn, pt, d, u, w, mv, tmps)
352                         in  scan(rest, pt+1, i+1, mv, tmps)                         in  scan(rest, pt+1, i+1, mv, tmps)
353                         end                         end
354                     val (pt, i, mv, tmps) =                     val (pt, i, mv, tmps) =
# Line 328  Line 361 
361                      *)                      *)
362                     case !succ of                     case !succ of
363                        [(F.EXIT _, _)] =>                        [(F.EXIT _, _)] =>
364                        let val liveSet = rmvDedicated(getCell(!liveOut))                        let val liveSet = rmvDedicated(
365                                               uniqCells(getCell(!liveOut)))
366                        in  newNodes{cost=w, pt=progPt(blknum, 0),                        in  newNodes{cost=w, pt=progPt(blknum, 0),
367                                     defs=[], uses=liveSet}; ()                                     defs=[], uses=liveSet}; ()
368                        end                        end
# Line 341  Line 375 
375            (* Add the edges *)            (* Add the edges *)
376    
377             val (moves, tmps) = mkNodes(blocks, [], [])             val (moves, tmps) = mkNodes(blocks, [], [])
            val addEdge = Core.addEdge G  
378         in  IntHashTable.appi         in  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 =                    let val spanMap = IntHashTable.mkTable
382                            IntHashTable.mkTable(IntHashTable.numItems nodes,                                          (IntHashTable.numItems nodes, NotThere)
                                                NotThere)  
383                        val setSpan = IntHashTable.insert spanMap                        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                in  fn (v, v' as NODE{cell, color, ...}) =>
388                  fn (v, v' as NODE{color=ref(PSEUDO | COLORED _), ...}) =>                    let fun computeLiveness() =
389                       setSpan(v, liveness(v, v', addEdge))                             setSpan(v, liveness(v, v', cell))
390                   | (v, v' as NODE{color=ref(MEMREG _), ...}) =>                    in  case !color of
391                       setSpan(v, liveness(v, v', addEdge))                          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;
# Line 369  Line 404 
404          * Build the interference graph initially.          * Build the interference graph initially.
405          *)          *)
406         fun build(G, cellkind) =         fun build(G, cellkind) =
407         let val moves = buildIt(cellkind, C.lookup regmap, G)         let val moves = buildIt(cellkind, G)
408         in  if !dump_size then         in  if !dump_size then
409                let val GRAPH{nodes, bitMatrix,...} = G                let val GRAPH{nodes, bitMatrix,...} = G
410                    val insns =                    val insns =
411                        foldr (fn (F.BBLOCK{insns,...},n) => length(!insns) + n                        foldr (fn (F.BBLOCK{insns,...},n) => length(!insns) + n
412                                | (_,n) => n) 0 blocks                                | (_,n) => n) 0 blocks
413                in  TextIO.output(!MLRiscControl.debug_stream,                in  TextIO.output(!MLRiscControl.debug_stream,
414                          "RA #blocks="^Int.toString N^                          "RA #blocks="^i2s N^
415                          " #insns="^Int.toString insns^                          " #insns="^i2s insns^
416                          " #nodes="^Int.toString(IntHashTable.numItems nodes)^                          " #nodes="^i2s(IntHashTable.numItems nodes)^
417                          " #edges="^Int.toString(Core.BM.size(!bitMatrix))^                          " #edges="^i2s(Core.BM.size(!bitMatrix))^
418                          " #moves="^Int.toString(length moves)^"\n")                          " #moves="^i2s(length moves)^"\n")
419                end                end
420             else ();             else ();
421             moves             moves
# Line 392  Line 427 
427          *)          *)
428         fun rebuild(cellkind, G) =         fun rebuild(cellkind, G) =
429             (Core.clearNodes G;             (Core.clearNodes G;
430              buildIt(cellkind, Core.regmap G, G)              buildIt(cellkind, G)
431             )             )
432    
433         (*         (*
434          * Spill a set of nodes and rewrite the flowgraph          * Spill a set of nodes and rewrite the flowgraph
435          *)          *)
436         fun spill{copyInstr, spill, spillSrc, spillCopyTmp,         fun spill{copyInstr, spill, spillSrc, spillCopyTmp,
437                   reload, reloadDst, renameSrc, graph as G.GRAPH{regmap, ...},                   reload, reloadDst, renameSrc, graph,
438                   cellkind, nodes=nodesToSpill} =                   cellkind, nodes=nodesToSpill} =
439         let (* Remove the interference graph now *)         let (* Remove the interference graph now *)
440             val _ = Core.clearGraph graph             val _ = Core.clearGraph graph
441    
442             (* maps program point to registers to be spilled *)             (* maps program point to registers to be spilled *)
443             val spillSet = IntHashTable.mkTable(32, NotThere)             val spillSet = IntHashTable.mkTable(32, NotThere)
                           : C.cell list IntHashTable.hash_table  
444    
445             (* maps program point to registers to be reloaded *)             (* maps program point to registers to be reloaded *)
446             val reloadSet = IntHashTable.mkTable(32, NotThere)             val reloadSet = IntHashTable.mkTable(32, NotThere)
                            : C.cell list IntHashTable.hash_table  
447    
448             (* maps program point to registers to be killed *)             (* maps program point to registers to be killed *)
449             val killSet = IntHashTable.mkTable(32, NotThere)             val killSet = IntHashTable.mkTable(32, NotThere)
                          : C.cell list IntHashTable.hash_table  
450    
451             val spillRewrite = Spill.spillRewrite             val spillRewrite = Spill.spillRewrite
452                                { graph=graph,                                { graph=graph,
# Line 433  Line 465 
465    
466             (* set of basic blocks that are affected *)             (* set of basic blocks that are affected *)
467             val affectedBlocks = IntHashTable.mkTable(32, NotThere)             val affectedBlocks = IntHashTable.mkTable(32, NotThere)
                                 : bool IntHashTable.hash_table  
468    
469             val addAffectedBlocks = IntHashTable.insert affectedBlocks             val addAffectedBlocks = IntHashTable.insert affectedBlocks
470    
471             fun ins set = let             fun ins set = let
472                 val add  = IntHashTable.insert set                 val add  = IntHashTable.insert set
473                 fun look i = getOpt (IntHashTable.find set i, [])                 val look = IntHashTable.find set
474                   val look = fn r => case look r of SOME s => s | NONE => []
475                 fun enter(r, []) = ()                 fun enter(r, []) = ()
476                   | enter(r, pt::pts) =                   | enter(r, pt::pts) =
477                     (add (pt, r::look pt);                     (add (pt, r::look pt);
# Line 454  Line 486 
486             val insKillSet   =             val insKillSet   =
487               let               let
488                 val add  = IntHashTable.insert killSet                 val add  = IntHashTable.insert killSet
489                 fun look i = getOpt (IntHashTable.find killSet i, [])                 val look = IntHashTable.find killSet
490                   val look = fn r => case look r of SOME s => s | NONE => []
491                 fun enter(r, []) = ()                 fun enter(r, []) = ()
492                   | enter(r, pt::pts) = (add(pt, r::look pt); enter(r, pts))                   | enter(r, pt::pts) = (add(pt, r::look pt); enter(r, pts))
493               in  enter               in  enter
494               end               end
495    
496             (* Mark all spill/reload locations *)             (* Mark all spill/reload locations *)
497             fun markSpills(G.NODE{color, number, defs, uses, ...}) =             fun markSpills(G.NODE{color, number, cell, defs, uses, ...}) =
498                 let fun spillIt(defs, uses) =                 let fun spillIt(defs, uses) =
499                         (insSpillSet(number, defs);                         (insSpillSet(cell, defs);
500                          insReloadSet(number, uses);                          insReloadSet(cell, uses);
501                          (* Definitions but no use! *)                          (* Definitions but no use! *)
502                          case uses of                          case uses of
503                             [] => insKillSet(number, defs)                             [] => insKillSet(cell, defs)
504                           | _ => ()                           | _ => ()
505                         )                         )
506                     val d = !defs                     val d = !defs

Legend:
Removed from v.733  
changed lines
  Added in v.744

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