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 889, Thu Jul 19 20:35:20 2001 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      structure Spill : RA_SPILL      structure Spill : RA_SPILL
# Line 18  Line 18 
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
24     structure G      = RAGraph     structure G      = RAGraph
25     structure Props  = InsnProps     structure Props  = InsnProps
26     structure Core   = RACore     structure Core   = RACore
# Line 28  Line 28 
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  = Spill     structure Spill  = Spill
30    
    structure PrintCluster = PrintCluster  
       (structure Flowgraph = F  
        structure Asm = Asm  
       )  
   
31     open G     open G
32     structure C      = I.C     structure C      = I.C
33     structure CB     = CellsBasis     structure CB     = CellsBasis
# Line 41  Line 36 
36    
37     val dump_size = MLRiscControl.getFlag "ra-dump-size"     val dump_size = MLRiscControl.getFlag "ra-dump-size"
38    
39     type flowgraph = F.cluster (* flowgraph is a cluster *)     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    
    val i2s = Int.toString  
   
43     val mode = 0w0     val mode = 0w0
44    
45     fun uniqCells s = CB.SortedCells.return(CB.SortedCells.uniq s)     fun uniqCells s = CB.SortedCells.return(CB.SortedCells.uniq s)
# Line 64  Line 57 
57     fun chase(NODE{color=ref(ALIASED n), ...}) = chase n     fun chase(NODE{color=ref(ALIASED n), ...}) = chase n
58       | chase n = n       | chase n = n
59    
    fun dumpFlowgraph(msg, cluster, stream) =  
        PrintCluster.printCluster stream  
           ("------------------ "^msg^" ------------------") cluster  
   
60     exception NotThere     exception NotThere
61    
62     val dummyLabel = F.LABEL(Label.Label{id= ~1, addr=ref ~1, name=""})     val Asm.S.STREAM{emit,...} = Asm.makeStream []
63    
64       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{blocks, blkCounter, annotations=clAnns, ...}) =           | 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 98  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          *)          *)
# Line 128  Line 133 
133                                                           | NONE => []                                                           | NONE => []
134             val addCopy      = IntHashTable.insert copyTable             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 151  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                  *  When we have a copy and while we are processing v
158                  *                  *
# Line 205  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, ...}, cellV) =             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 252  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    = IntHashTable.lookup nodes             val getnode    = IntHashTable.lookup nodes
270             val insnDefUse = Props.defUse cellkind             val insnDefUse = Props.defUse cellkind
271             val getCell    = C.CellSet.get cellkind             val getCell    = C.getCellsByKind cellkind
272    
273             fun isDedicated r = dedicated r             fun isDedicated r = dedicated r
274    
# Line 332  Line 326 
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 350  Line 348 
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(                        if id = EXIT then let
363                                             uniqCells(getCell(!liveOut)))                            val liveSet = rmvDedicated(
364                        in  newNodes{cost=w, pt=progPt(blknum, 0),                                             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         in  IntHashTable.appi         in
378               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 = IntHashTable.mkTable                    let val spanMap = IntHashTable.mkTable
# Line 396  Line 398 
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) =         fun build(G, cellkind) = let
407         let val moves = buildIt(cellkind, G)           val moves = buildIt(cellkind, G)
408         in  if !dump_size then           val i2s = Int.toString
409                let val GRAPH{nodes, bitMatrix,...} = G         in
410             if !dump_size then let
411                  val GRAPH{nodes, bitMatrix,...} = G
412                    val insns =                    val insns =
413                        foldr (fn (F.BBLOCK{insns,...},n) => length(!insns) + n                  foldr (fn ((_,CFG.BLOCK{insns,...}),n) => length(!insns) + n) 0 blocks
414                                | (_,n) => n) 0 blocks              in
415                in  TextIO.output(!MLRiscControl.debug_stream,                TextIO.output
416                     (!MLRiscControl.debug_stream,
417                          "RA #blocks="^i2s N^                          "RA #blocks="^i2s N^
418                          " #insns="^i2s insns^                          " #insns="^i2s insns^
419                          " #nodes="^i2s(IntHashTable.numItems nodes)^                          " #nodes="^i2s(IntHashTable.numItems nodes)^
# Line 514  Line 519 
519             val _ = app 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)               val (_, CFG.BLOCK{insns as ref instrs, annotations, ...}) =
524                of F.BBLOCK{annotations, insns as ref instrs, ...} => let                 A.sub(blockTable, blknum)
525                      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
530                    end                    end
               | _ => error "rewriteAll"  
              (*esac*))  
531    
532    
533             fun mark(G.NODE{color, ...}) =             fun mark(G.NODE{color, ...}) =

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

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