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

sml/branches/SMLNJ/src/MLRISC/ra/cluster-ra.sml revision 468, Wed Nov 10 22:42:52 1999 UTC sml/trunk/src/MLRISC/ra/cluster-ra.sml revision 909, Fri Aug 24 17:48:53 2001 UTC
# Line 1  Line 1 
1  (*  (*
2   * This module provides services for the new RA when using the cluster   * This module provides services for the new RA when using the cluster
3   * representation.   * representation.
4     * The algorithm is adapted from
5     * Algorithm 19.17 from Appel, Modern Compiler Implementation in ML,
6     * Calculation of live ranges in SSA form.  We don't directly use SSA
7     * here but the principles are the same.
8   *   *
9   * -- Allen   * -- Allen
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 = Asm.I = InsnProps.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(InsnProps)     structure Spill  = Spill
   
    structure PrintCluster = PrintClusterFn  
       (structure Flowgraph = F  
        structure Asm = Asm  
       )  
30    
31     open G     open G
32       structure C      = I.C
33       structure CB     = CellsBasis
34    
35     type flowgraph = F.cluster (* flowgraph is a cluster *)     fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0
36    
37       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     fun regmap(F.CLUSTER{regmap, ...}) = regmap     val mode = 0w0
44    
45       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))
80    
81       fun services(cfg as Graph.GRAPH graph) = let
82           val CFG.INFO{annotations=clAnns, ...} = #graph_info graph
83           val blocks = #nodes graph ()
84           fun maxBlockId ((id, CFG.BLOCK _)::rest, curr) =
85               if id > curr then maxBlockId(rest, id) else maxBlockId(rest, curr)
86             | maxBlockId([], curr) = curr
87    
88           val N = maxBlockId(blocks, #capacity graph ())
89    
90           fun computeShift(0w0, max) = 0w31-max
91             | computeShift(N, max) = computeShift(Word.>>(N, 0w1), Word.+(max,0w1))
92           val shift = computeShift(Word.>>(Word.fromInt N, 0w15), 0w15)
93           val mask  = Word.<<(0w1, shift) - 0w1
94    
95     fun inc n = Word.toIntX(Word.fromInt n + 0w1)         (*
96            * Construct program point
97     fun length l =          *)
98     let fun loop([],n)   = n         fun progPt(blknum, instrId) =
99           | loop(_::l,n) = loop(l,inc n)             Word.toIntX(Word.+(Word.<<(Word.fromInt blknum, shift),
100     in  loop(l,0) end                                        Word.fromInt instrId))
101           fun blockNum pt = Word.toIntX(Word.>>(Word.fromInt pt, shift))
102     fun services(cluster as F.CLUSTER{regmap, blocks, blkCounter, ...}) =         fun instrNum pt = Word.toIntX(Word.andb(Word.fromInt pt, mask))
    let (* Create a graph based view of cluster *)  
        val N            = !blkCounter  
        val _            = if N >= 65536 then  
                               error "too many blocks" else ()  
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))
   
        (* definitions indexed by block id+instruction id *)  
        val defsTable    = A.array(N, A.array(0, [])) : node list A.array A.array  
        val marked       = A.array(N, A.array(0, ~1))  
106    
107         val stamp = ref 0         fun fillBlockTable [] = ()
108             | fillBlockTable((b as (nid, _))::blocks) =
109                 (UA.update(blockTable, nid, b); fillBlockTable blocks)
110           val _ = fillBlockTable blocks
111    
112         (* Build the initial interference graph *)         val EXIT = (case #exits graph () of [e] => e | _ => error "EXIT")
        fun init [] = ()  
          | init((b as F.BBLOCK{blknum, insns, ...})::blocks) =  
            let val n = length(!insns)  
                (* val m = Word.toIntX(Word.>>(Word.fromInt(n+8),0w3)) *)  
                val m = n+1  
            in  UA.update(blockTable, blknum, b);  
                UA.update(marked, blknum, A.array(m, ~1));  
                UA.update(defsTable, blknum, A.array(m, []));  
                init blocks  
            end  
          | init(_::blocks) = init blocks  
        val _ = init blocks  
113    
114         (*         (*
115          * Construct program point          * Building the interference graph
116          *)          *)
117         fun progPt(blknum, instrId) =         fun buildIt (cellkind,
118             Word.toIntX(Word.<<(Word.fromInt blknum,0w14) + Word.fromInt instrId)                      G as GRAPH{nodes, dedicated, mode, span, copyTmps, ...}) =
119         fun blockNum pt = Word.toIntX(Word.>>(Word.fromInt pt,0w14))  
120         fun instrNum pt = Word.toIntX(Word.andb(Word.fromInt pt,0w16383))         let (* definitions indexed by block id+instruction id *)
121               val defsTable    = A.array(N, A.array(0, [] : node list))
122               val marked       = A.array(N, ~1)
123               val addEdge      = Core.addEdge G
124    
125               (* copies indexed by source
126                * This table maps variable v to the program points where
127                * v is a source of a copy.
128                *)
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
137    
138         fun freq(pt) =             (* Allocate the arrays *)
139             let val F.BBLOCK{freq, ...} = A.sub(blockTable, blockNum pt)             fun alloc [] = ()
140             in  !freq end               | alloc((id, CFG.BLOCK{insns, ...})::blocks) =
141                    (UA.update(defsTable, id, A.array(length(!insns)+1, []));
142                     alloc blocks)
143               val _ = alloc blocks
144    
145         (*         (*
146          * Remove pseudo use              * Remove pseudo use generated by copy temporaries
147          *)          *)
148         fun rmPseudoUses [] = ()         fun rmPseudoUses [] = ()
149           | rmPseudoUses(NODE{uses,...}::ns) = (uses := []; rmPseudoUses ns)           | rmPseudoUses(NODE{uses,...}::ns) = (uses := []; rmPseudoUses ns)
150    
151         (*         (*
152                * Initialize the definitions before computing the liveness for v.
153                *)
154               fun initialize(v, v', useSites) = let
155                   (* First we remove all definitions for all copies
156                    * 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
165                     | markCopies({pt, dst}::copies, trail) =
166                       let val b     = blockNum pt
167                           val i     = instrNum pt
168                           val defs  = UA.sub(defsTable, b)
169                           val nodes = UA.sub(defs, i)
170                           fun revAppend([], nodes) = nodes
171                             | revAppend(n::ns, nodes) = revAppend(ns, n::nodes)
172                           val dstColor = colorOf dst
173                           fun removeDst([], nodes') = nodes'
174                             | removeDst((d as NODE{number=r,...})::nodes, nodes')=
175                               if r = dstColor then revAppend(nodes', nodes)
176                               else removeDst(nodes, d::nodes')
177                           val nodes' = removeDst(nodes, [])
178                       in  UA.update(defs, i, nodes');
179                           markCopies(copies, (defs, i, nodes)::trail)
180                       end
181    
182                   (*
183                    * 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
187                     | markUseSites(pt::pts, trail) =
188                       let val b     = blockNum pt
189                           val i     = instrNum pt
190                           val defs  = UA.sub(defsTable, b)
191                           val nodes = UA.sub(defs, i)
192                       in  UA.update(defs, i, v'::nodes);
193                           markUseSites(pts, (defs, i, nodes)::trail)
194                       end
195    
196                   val copies = lookupCopy v
197                   val trail  = markCopies(copies, [])
198                   val trail  = markUseSites(useSites, trail)
199               in  trail end
200    
201               fun cleanup [] = ()
202                 | cleanup ((defs, i, nodes)::trail) =
203                     (UA.update(defs, i, nodes); cleanup trail)
204               (*
205          * Perform incremental liveness analysis on register v          * Perform incremental liveness analysis on register v
206                * 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 [] = ()                 fun foreachUseSite([], span) = span
212               | foreachUseSite(u::uses) =                   | 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                     val block = UA.sub(blockTable, b)                       val block as (_, CFG.BLOCK{freq, ...}) = UA.sub(blockTable, b)
216                 in  if i = 0 then                       val span =
217                         liveOutAtBlock(block) (* live out *)                         if i = 0 then liveOutAtBlock(block, span) (* live out *)
218                     else                         else let
219                         liveInAtStmt(block,                             val f = !freq
220                                      UA.sub(defsTable, b),                             val defs = UA.sub(defsTable, b)
221                                      UA.sub(marked, b), i);                           in  liveOutAtStmt(block, A.length defs, defs, i+1, f, span+f)
222                     foreachUseSite uses                           end
223                 end                     in foreachUseSite(uses, span)
224                       end
225             and visitPred block =  
226                 let fun foreachPred([]) = ()                 and visitPred((nid, _), span) =
227                       | foreachPred((b, _)::pred) =                     let fun foreachPred([], span) = span
228                          (liveOutAtBlock b; foreachPred pred)                           | foreachPred(nid::pred, span) = let
229                     val F.BBLOCK{pred, ...} = block                                val span = liveOutAtBlock((nid, #node_info graph nid), span)
230                 in  foreachPred(!pred) end                             in  foreachPred(pred, span)
231                               end
232             and liveInAtStmt(block, defs, marked, pos) =                     in
233                 if pos >= A.length defs then visitPred block                       foreachPred(#pred graph nid, span)
234                 else if UA.sub(marked, pos) = st then ()                     end
                else (UA.update(marked, pos, st);  
                      liveOutAtStmt(block, defs, marked, inc pos)  
                     )  
235    
236             and liveOutAtStmt(block, defs, marked, pos) =                 and liveOutAtStmt(block, nDefs, defs, pos, freq, span) =
237                    (* v is live out *)                    (* v is live out *)
238                 if pos < A.length defs then                     if pos < nDefs then
239                 let fun foreachDef([], kill) = kill                     let fun foreachDef([], true) = span
240                             | foreachDef([], false) =
241                                  liveOutAtStmt(block, nDefs, defs,
242                                                pos+1, freq, span+freq)
243                       | foreachDef((d as NODE{number=r, ...})::ds, kill) =                       | foreachDef((d as NODE{number=r, ...})::ds, kill) =
244                         if r = v then foreachDef(ds, true)                         if r = v then foreachDef(ds, true)
245                         else (addEdge(d, v'); foreachDef(ds, kill))                         else (addEdge(d, v'); foreachDef(ds, kill))
246                     val killed = foreachDef(UA.sub(defs, pos), false)                     in foreachDef(UA.sub(defs, pos), false)
                in  if killed then ()  
                    else liveInAtStmt(block, defs, marked, pos)  
247                 end                 end
248                 else visitPred block                     else visitPred(block, span)
249    
250             and liveOutAtBlock(block as F.BBLOCK{blknum, ...}) =                 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                 let val marked = UA.sub(marked, blknum)                     if UA.sub(marked, nid) = st then span
253                 in  if UA.sub(marked, 0) = st then ()                     else let
254                     else                         val defs = UA.sub(defsTable, nid)
255                      (UA.update(marked, 0, st);                       in
256                       liveOutAtStmt(block, UA.sub(defsTable, blknum),                         UA.update(marked, nid, st);
257                                     marked, 1)                         liveOutAtStmt(block, A.length defs, defs, 1, !freq, span)
258                      )                       end
259    
260                   val useSites = SortedList.uniq(!uses)
261                   val trail    = initialize(v, v', useSites)
262                   val span     = foreachUseSite (useSites, 0)
263                   val _        = cleanup trail
264               in
265                 span
266                 end                 end
              | liveOutAtBlock _ = ()  
267    
268         in  foreachUseSite (!uses)             val newNodes   = Core.newNodes G
269         end             val getnode    = IntHashTable.lookup nodes
   
        (*  
         * Building the interference graph  
         *)  
        fun buildIt (cellkind, regmap, G as GRAPH{nodes, dedicated, ...}) =  
        let val newNodes   = Core.newNodes G  
            val addEdge    = Core.addEdge G  
            val getnode    = Intmap.map 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
               r < 0 orelse  
               r < A.length dedicated andalso UA.sub(dedicated, r)  
   
            fun chase(NODE{color=ref(ALIASED n), ...}) = chase n  
              | chase n = n  
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             (*             (*
291              * Create parallel move              * Create parallel move
292              *)              *)
293             fun mkMoves(insn, dst, src, cost, mv, tmps) =             fun mkMoves(insn, pt, dst, src, cost, mv, tmps) =
294                 if Props.moveInstr insn then                 if Props.moveInstr insn then
295                 let val (dst, tmps) =                 let val (dst, tmps) =
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 val tmp as NODE{uses,defs=ref [d],...} =                            (case chase(getnode(colorOf r)) of
300                                      chase(getnode r)                               tmp as NODE{uses,defs=ref [d],...} =>
301                             in  uses := [d-1]; (dst, tmp::tmps) end                                 (uses := [d-1]; (dst, tmp::tmps))
302                              | _ => error "mkMoves"
303                              )
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 val dst as NODE{number=d, ...} = chase(getnode d)                               let val _ =
314                             val src as NODE{number=s, ...} = chase(getnode s)                                    addCopy(cs, {dst=d, pt=pt}::lookupCopy cs);
315                         in if d = s then moves(ds, ss, mv)                                   val dst = chase(getnode cd)
316                            else moves(ds, ss, MV{dst=dst, src=src,                                   val src = chase(getnode cs)
317                                 in  moves(ds, ss, MV{dst=dst, src=src,
318                                                  status=ref WORKLIST,                                                  status=ref WORKLIST,
319                                                       hicount=ref 0,
320                                                  (* kind=REG_TO_REG, *)                                                  (* kind=REG_TO_REG, *)
321                                                  cost=cost}::mv)                                                     cost=cost}::mv
322                                          )
323                                 end
324                         end                         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(insns as 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
341                             val defs = rmvDedicated d                             val defs = rmvDedicated d
342                             val uses = rmvDedicated u                             val uses = rmvDedicated u
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, d, u, w, mv, tmps)                           val (mv, tmps) =
347                         in  scan(rest, inc pt, inc i, mv, tmps)                                 mkMoves(insn, pt, d, u, w, mv, tmps)
348                         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                                error "mkNodes: too many instructions"                     if pt >= progPt(nid+1, 0) then
354                             else ()                        error("mkNodes: too many instructions")
                    fun fill i =  
                        if i < A.length dtab then  
                           (UA.update(dtab, i, []); fill(inc i))  
355                         else ()                         else ()
356                 in  fill i;                 in
357                     (* If the block is escaping, then all liveout                     (* 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 *)
            fun mkEdges(v, v' as NODE{color=ref(PSEUDO | COLORED _), ...}) =  
                  liveness(v, v', addEdge)  
              | mkEdges _ = ()  
375    
376             val (moves, tmps) = mkNodes(blocks, [], [])             val (moves, tmps) = mkNodes(blocks, [], [])
377         in  Intmap.app mkEdges nodes;         in
378               IntHashTable.appi
379                 (let val setSpan =
380                      if isOn(mode,Core.COMPUTE_SPAN) then
381                      let val spanMap = IntHashTable.mkTable
382                                            (IntHashTable.numItems nodes, NotThere)
383                          val setSpan = IntHashTable.insert spanMap
384                          val _       = span := SOME spanMap
385                      in  setSpan end
386                      else fn _ => ()
387                  in  fn (v, v' as NODE{cell, color, ...}) =>
388                      let fun computeLiveness() =
389                               setSpan(v, liveness(v, v', cell))
390                      in  case !color of
391                            PSEUDO => computeLiveness()
392                          | COLORED _ => computeLiveness()
393                          | MEMREG _ => computeLiveness()
394                          | _ => ()
395                      end
396                  end
397                 ) nodes;
398               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          * Grow a table         in
410          *)           if !dump_size then let
411         fun grow(b, n) =                val GRAPH{nodes, bitMatrix,...} = G
412         let (* val m = Word.toIntX(Word.>>(Word.fromInt(n+8),0w3)) *)                val insns =
413             val m = n+1                  foldr (fn ((_,CFG.BLOCK{insns,...}),n) => length(!insns) + n) 0 blocks
414         in  if A.length(A.sub(marked, b)) < m then              in
415                UA.update(marked, b, A.array(m, ~1))                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 ();              else ();
424             if A.length(A.sub(defsTable, b)) < m then           moves
               UA.update(defsTable, b, A.array(m, []))  
            else ()  
425         end         end
426    
427         (*         (*
# Line 294  Line 429 
429          * We'll just do it from scratch for now.          * We'll just do it from scratch for now.
430          *)          *)
431         fun rebuild(cellkind, G) =         fun rebuild(cellkind, G) =
432             (Core.clearGraph G; Core.clearNodes G;             (Core.clearNodes G;
433              buildIt(cellkind, Core.regmap G, G))              buildIt(cellkind, G)
434               )
        val regs = foldr(fn (r, "") => Int.toString r  
                          | (r, l)  => Int.toString r^","^l) ""  
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, reload, graph as G.GRAPH{regmap,...},         fun spill{copyInstr, spill, spillSrc, spillCopyTmp,
440                     reload, reloadDst, renameSrc, graph,
441                   cellkind, nodes=nodesToSpill} =                   cellkind, nodes=nodesToSpill} =
442         let         let (* Remove the interference graph now *)
443             val spillRewrite = Spill.spillRewrite             val _ = Core.clearGraph graph
                               { graph=graph,  
                                 spill=spill,  
                                 reload=reload,  
                                 copyInstr=copyInstr,  
                                 cellkind=cellkind  
                               }  
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
455                                  { graph=graph,
456                                    spill=spill,
457                                    spillSrc=spillSrc,
458                                    spillCopyTmp=spillCopyTmp,
459                                    reload=reload,
460                                    reloadDst=reloadDst,
461                                    renameSrc=renameSrc,
462                                    copyInstr=copyInstr,
463                                    cellkind=cellkind,
464                                    spillSet=spillSet,
465                                    reloadSet=reloadSet,
466                                    killSet=killSet
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             in  fn (x, r) =>                 val look = fn r => case look r of SOME s => s | NONE => []
478                 (add (x, r::look x);                 fun enter(r, []) = ()
479                  addAffectedBlocks (blockNum x, true)                   | enter(r, pt::pts) =
480                       (add (pt, r::look pt);
481                        addAffectedBlocks (blockNum pt, true);
482                        enter(r, pts)
483                 )                 )
484               in  enter
485             end             end
486    
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             in  fn (x, r) => add (x, r::look x) end                 val look = IntHashTable.find killSet
493                   val look = fn r => case look r of SOME s => s | NONE => []
494             fun get set = Intmap.mapWithDefault (set, [])                 fun enter(r, []) = ()
495             val getSpillSet  = get spillSet                   | enter(r, pt::pts) = (add(pt, r::look pt); enter(r, pts))
496             val getReloadSet = get reloadSet               in  enter
497             val getKillSet   = get killSet               end
498    
499             val _ = app (fn G.NODE{number, defs=ref defs, uses=ref uses, ...} =>             (* Mark all spill/reload locations *)
500                          (app (fn pt => insSpillSet (pt, number)) defs;             fun markSpills(G.NODE{color, number, cell, defs, uses, ...}) =
501                           app (fn pt => insReloadSet (pt, number)) uses;                 let fun spillIt(defs, uses) =
502                           (insSpillSet(cell, defs);
503                            insReloadSet(cell, uses);
504                           (* Definitions but no use! *)                           (* Definitions but no use! *)
505                           case uses of                           case uses of
506                              [] => app (fn pt => insKillSet(pt, number)) defs                             [] => insKillSet(cell, defs)
507                             | _ => ()
508                           )
509                       val d = !defs
510                       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)
517                            | _ => ()                            | _ => ()
                         )) nodesToSpill  
   
            (* Rewrite a basic block *)  
            fun rewrite(annotations, blknum, pt, [], newInstrs) = rev newInstrs  
              | rewrite(annotations, blknum, pt, i::rest, newInstrs) =  
                let val spillRegs  = getSpillSet pt  
                    val reloadRegs = getReloadSet pt  
                    val killRegs   = getKillSet pt  
                in  case (spillRegs, reloadRegs) of  
                      ([], []) =>  
                         rewrite(annotations, blknum, inc pt, rest, i::newInstrs)  
                    | _ =>  
                    (* do something with this instruction, dude! *)  
                    let (* val _ = (print("Spilling: "^regs spillRegs);  
                                 print(" Reloading: "^regs reloadRegs);  
                                 emit (C.lookup regmap) i) *)  
                        val {code} =  
                         spillRewrite{instr=i,  
                                      spillRegs=spillRegs,  
                                      reloadRegs=reloadRegs,  
                                      killRegs=killRegs,  
                                      annotations=annotations}  
                        (* val _ = (print("Code:");  
                                 app (emit (C.lookup regmap)) code) *)  
                    in  rewrite(annotations,  
                                blknum, inc pt, rest, code @ newInstrs)  
                    end  
518                 end                 end
519               val _ = app markSpills nodesToSpill
520    
521             (* Rewrite all affected blocks *)             (* Rewrite all affected blocks *)
522             fun rewriteAll (blknum, _) =             fun rewriteAll (blknum, _) = let
523                 let val F.BBLOCK{annotations, insns, ...} =               val (_, CFG.BLOCK{insns as ref instrs, annotations, ...}) =
524                            A.sub(blockTable, blknum)                            A.sub(blockTable, blknum)
525                     val instrs =                     val instrs =
526                          rewrite(annotations,                 spillRewrite{pt=progPt(blknum, length instrs),
527                                  blknum, progPt(blknum, 1), !insns, [])                              instrs=instrs, annotations=annotations}
528                 in  insns := instrs;             in
529                     grow(blknum, length instrs)               insns := instrs
530                 end                 end
531    
532         in  Intmap.app rewriteAll affectedBlocks;  
533             app (fn G.NODE{color=ref(ALIASED_SPILL _), ...} => ()             fun mark(G.NODE{color, ...}) =
534                   | G.NODE{color, ...} => color := (SPILLED 0)               (case !color
535                 ) nodesToSpill;                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)             rebuild(cellkind, graph)
547           end (* spill *)
548       in
549         { build       = build,
550           spill       = spill,
551           programPoint= fn{block,instr} => progPt(block,instr),
552           blockNum    = blockNum,
553           instrNum    = instrNum
554          }
555         end         end
   
    in  {build=build, spill=spill, freq=freq}  
556     end     end
557    
 end  

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

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