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 499, Tue Dec 7 15:44:50 1999 UTC revision 545, Thu Feb 24 13:56:44 2000 UTC
# Line 30  Line 30 
30                                structure Asm       = Asm                                structure Asm       = Asm
31                               )                               )
32    
33     structure PrintCluster = PrintClusterFn     structure PrintCluster = PrintCluster
34        (structure Flowgraph = F        (structure Flowgraph = F
35         structure Asm = Asm         structure Asm = Asm
36        )        )
# Line 119  Line 119 
119                (* blocks indexed by block id *)                (* blocks indexed by block id *)
120         val blockTable   = A.array(N, dummyLabel)         val blockTable   = A.array(N, dummyLabel)
121    
122         (* definitions indexed by block id+instruction id *)         fun fillBlockTable [] = ()
123         val defsTable    = A.array(N, A.array(0, [])) : node list A.array A.array           | fillBlockTable((b as F.BBLOCK{blknum, ...})::blocks) =
124                 (UA.update(blockTable, blknum, b); fillBlockTable blocks)
125             | fillBlockTable(_::blocks) = fillBlockTable blocks
126           val _ = fillBlockTable blocks
127    
128           (*
129            * Building the interference graph
130            *)
131           fun buildIt (cellkind, regmap,
132                        G as GRAPH{nodes, dedicated, mode, span, copyTmps, ...}) =
133    
134           let (* definitions indexed by block id+instruction id *)
135               val defsTable    = A.array(N, A.array(0, [] : node list))
136         val marked       = A.array(N, ~1)         val marked       = A.array(N, ~1)
137    
138         val stamp = ref 0         val stamp = ref 0
139    
140         (* Build the initial interference graph *)             (* Allocate the arrays *)
141         fun init [] = ()             fun alloc [] = ()
142           | init((b as F.BBLOCK{blknum, insns, ...})::blocks) =               | alloc((b as F.BBLOCK{blknum, insns, ...})::blocks) =
143             let val n = length(!insns)             let val n = length(!insns)
                (* val m = Word.toIntX(Word.>>(Word.fromInt(n+8),0w3)) *)  
144                 val m = n+1                 val m = n+1
145             in  UA.update(blockTable, blknum, b);                 in  UA.update(defsTable, blknum, A.array(m, []));
146                 UA.update(defsTable, blknum, A.array(m, []));                     alloc blocks
                init blocks  
147             end             end
148           | init(_::blocks) = init blocks               | alloc(_::blocks) = alloc blocks
149         val _ = init blocks             val _ = alloc blocks
150    
151         (*         (*
152          * Remove pseudo use generated by copy temporaries          * Remove pseudo use generated by copy temporaries
# Line 145  Line 155 
155           | rmPseudoUses(NODE{uses,...}::ns) = (uses := []; rmPseudoUses ns)           | rmPseudoUses(NODE{uses,...}::ns) = (uses := []; rmPseudoUses ns)
156    
157         (*         (*
        val marker = NODE{pri=ref 0,adj=ref [],degree=ref 0,movecnt=ref 0,  
                          color=ref PSEUDO, defs=ref [], uses=ref [],  
                          movecost=ref 0,movelist=ref [], number= ~1}  
         *)  
   
        (*  
         * Remove duplicates on use sites  
         *)  
        (*  
        fun uniq [] = []  
          | uniq (l as [_]) = l  
          | uniq (l as [x,y]) = if x = y then [x] else l  
          | uniq uses =  
        let fun mark([], uses') = uses'  
              | mark(u::uses, uses') =  
                let val b    = blockNum u  
                    val i    = instrNum u  
                    val defs = UA.sub(defsTable, b)  
                in  case A.sub(defs, i) of  
                       NODE{number= ~1, ...}::_ => mark(uses, uses')  
                    | instrs => (UA.update(defs, i, marker::instrs);  
                                 mark(uses, u::uses'))  
                end  
            val useSites = mark(uses, [])  
            fun unmark [] = ()  
              | unmark(u::uses) =  
                let val b    = blockNum u  
                    val i    = instrNum u  
                    val defs = UA.sub(defsTable, b)  
                    val _::instrs = UA.sub(defs, i)  
                in  UA.update(defs, i, instrs); unmark uses end  
        in  unmark useSites;  
            useSites  
        end  
         *)  
   
        (*  
158          * Mark the use site as definitions so that the traversal would          * Mark the use site as definitions so that the traversal would
159          * end properly.          * end properly.
160          *)          *)
# Line 229  Line 202 
202                 let fun foreachPred([]) = ()                 let fun foreachPred([]) = ()
203                       | foreachPred((b, _)::pred) =                       | foreachPred((b, _)::pred) =
204                          (liveOutAtBlock(b); foreachPred(pred))                          (liveOutAtBlock(b); foreachPred(pred))
205                     val F.BBLOCK{pred, ...} = block                     in  case block of
206                 in  foreachPred(!pred) end                           F.BBLOCK{pred, ...} => foreachPred(!pred)
207                           | _ => error "visitPred"
208                       end
209    
210             and liveOutAtStmt(block, defs, pos) =             and liveOutAtStmt(block, defs, pos) =
211                    (* v is live out *)                    (* v is live out *)
# Line 240  Line 215 
215                           liveOutAtStmt(block, defs, pos+1)                           liveOutAtStmt(block, defs, pos+1)
216                       | foreachDef((d as NODE{number=r, ...})::ds, kill) =                       | foreachDef((d as NODE{number=r, ...})::ds, kill) =
217                         if r = v then foreachDef(ds, true)                         if r = v then foreachDef(ds, true)
218                         else if r < 256 andalso v < 256 then foreachDef(ds, kill)                             else if r < 256 andalso v < 256
219                                    then foreachDef(ds, kill)
220                         else (addEdge(d,v'); foreachDef(ds, kill))                         else (addEdge(d,v'); foreachDef(ds, kill))
221                 in  foreachDef(UA.sub(defs, pos), false)                 in  foreachDef(UA.sub(defs, pos), false)
222                 end                 end
# Line 272  Line 248 
248               | foreachUseSite(u::uses, span) =               | foreachUseSite(u::uses, span) =
249                 let val b = blockNum u                 let val b = blockNum u
250                     val i = instrNum u                     val i = instrNum u
251                     val block as F.BBLOCK{freq, ...} = UA.sub(blockTable, b)                     in  case UA.sub(blockTable, b) of
252                     val span =                           block as F.BBLOCK{freq, ...} =>
253                             let val span =
254                     if i = 0 then                     if i = 0 then
255                         liveOutAtBlock(block, span) (* live out *)                         liveOutAtBlock(block, span) (* live out *)
256                     else                     else
# Line 283  Line 260 
260                         end;                         end;
261                 in  foreachUseSite(uses, span)                 in  foreachUseSite(uses, span)
262                 end                 end
263                           | _ => error "liveness2"
264                       end
265    
266             and visitPred(block, span) =             and visitPred(block, span) =
267                 let fun foreachPred([], span) = span                 let fun foreachPred([], span) = span
268                       | foreachPred((b, _)::pred, span) =                       | foreachPred((b, _)::pred, span) =
269                         let val span = liveOutAtBlock(b, span)                         let val span = liveOutAtBlock(b, span)
270                         in  foreachPred(pred, span) end                         in  foreachPred(pred, span) end
271                     val F.BBLOCK{pred, ...} = block                     in  case block of
272                 in  foreachPred(!pred, span) end                           F.BBLOCK{pred, ...} => foreachPred(!pred, span)
273                           | _ => error "visitPred"
274                       end
275    
276             and liveOutAtStmt(block, defs, pos, freq, span) =             and liveOutAtStmt(block, defs, pos, freq, span) =
277                    (* v is live out *)                    (* v is live out *)
# Line 318  Line 299 
299             val useSites = SortedList.uniq(!uses)             val useSites = SortedList.uniq(!uses)
300             val _        = markUseSites(v', useSites)             val _        = markUseSites(v', useSites)
301             val span     = foreachUseSite (useSites, 0)             val span     = foreachUseSite (useSites, 0)
           (*val _ = print("Span(r"^Int.toString v^")="^Int.toString span^"\n")*)  
302             val _        = unmarkUseSites useSites             val _        = unmarkUseSites useSites
303         in  setSpan(v, span)         in  setSpan(v, span)
304         end         end
305    
306         (*             val newNodes   = Core.newNodes G
         * Building the interference graph  
         *)  
        fun buildIt (cellkind, regmap,  
                     G as GRAPH{nodes, dedicated, mode, span, copyTmps, ...}) =  
        let val newNodes   = Core.newNodes G  
307             val getnode    = Intmap.map nodes             val getnode    = Intmap.map nodes
308             val insnDefUse = Props.defUse cellkind             val insnDefUse = Props.defUse cellkind
309             val getCell    = C.getCell cellkind             val getCell    = C.getCell cellkind
# Line 357  Line 332 
332                           let fun chase(NODE{color=ref(ALIASED n), ...}) =                           let fun chase(NODE{color=ref(ALIASED n), ...}) =
333                                    chase n                                    chase n
334                                 | chase n = n                                 | chase n = n
335                               val tmp as NODE{uses,defs=ref [d],...} =                           in  case chase(getnode r) of
336                                      chase(getnode r)                                 tmp as NODE{uses,defs=ref [d],...} =>
337                           in  uses := [d-1]; (dst, tmp::tmps) end                                    (uses := [d-1]; (dst, tmp::tmps))
338                                 | _ => error "mkMoves"
339                             end
340                         | (_, dst) => (dst, tmps)                         | (_, dst) => (dst, tmps)
341                     fun moves([], [], mv) = mv                     fun moves([], [], mv) = mv
342                       | moves(d::ds, s::ss, mv) =                       | moves(d::ds, s::ss, mv) =
# Line 407  Line 384 
384                     val _ = if pt >= progPt(blknum+1, 0) then                     val _ = if pt >= progPt(blknum+1, 0) then
385                                error("mkNodes: too many instructions")                                error("mkNodes: too many instructions")
386                             else ()                             else ()
387                     fun fill i =                     (* fun fill i =
388                         if i < A.length dtab then                         if i < A.length dtab then
389                            (UA.update(dtab, i, []); fill(i+1))                            (UA.update(dtab, i, []); fill(i+1))
390                         else ()                         else () *)
391                 in  fill i;                 in  (* fill i; *)
392                     (* If the block is escaping, then all liveout                     (* If the block is escaping, then all liveout
393                      * registers are considered used here.                      * registers are considered used here.
394                      *)                      *)
# Line 433  Line 410 
410             val addEdge = Core.addEdge G             val addEdge = Core.addEdge G
411         in  Intmap.app         in  Intmap.app
412               (if isOn(mode,Core.COMPUTE_SPAN) then               (if isOn(mode,Core.COMPUTE_SPAN) then
413                 let val setSpan = Intmap.add span                 let val spanMap = Intmap.new(Intmap.elems nodes, NotThere)
414                       val setSpan = Intmap.add spanMap
415                       val _       = span := SOME spanMap
416                 in  fn (v, v' as NODE{color=ref(PSEUDO | COLORED _), ...}) =>                 in  fn (v, v' as NODE{color=ref(PSEUDO | COLORED _), ...}) =>
417                        liveness2(v, v', addEdge, setSpan)                        liveness2(v, v', addEdge, setSpan)
418                      | (v, v' as NODE{color=ref(SPILLED c), ...}) =>                      | (v, v' as NODE{color=ref(SPILLED c), ...}) =>
# Line 461  Line 440 
440         (*         (*
441          * Grow a table          * Grow a table
442          *)          *)
443           (*
444         fun grow(b, n) =         fun grow(b, n) =
445         let (* val m = Word.toIntX(Word.>>(Word.fromInt(n+8),0w3)) *)         let (* val m = Word.toIntX(Word.>>(Word.fromInt(n+8),0w3)) *)
446             val m = n+1             val m = n+1
# Line 471  Line 451 
451                UA.update(defsTable, b, A.array(m, []))                UA.update(defsTable, b, A.array(m, []))
452             else ()             else ()
453         end         end
454           *)
455    
456         (*         (*
457          * Rebuild the interference graph;          * Rebuild the interference graph;
# Line 588  Line 569 
569    
570             (* Rewrite all affected blocks *)             (* Rewrite all affected blocks *)
571             fun rewriteAll (blknum, _) =             fun rewriteAll (blknum, _) =
572                 let val F.BBLOCK{annotations, insns as ref instrs, ...} =                 case A.sub(blockTable, blknum) of
573                            A.sub(blockTable, blknum)                    F.BBLOCK{annotations, insns as ref instrs, ...} =>
574                     val instrs = spillRewrite{pt=progPt(blknum, length instrs),                    let val instrs =
575                              spillRewrite{pt=progPt(blknum, length instrs),
576                                               instrs=instrs,                                               instrs=instrs,
577                                               annotations=annotations}                                               annotations=annotations}
578                 in  insns := instrs;                    in  insns := instrs
579                     grow(blknum, length instrs)                        (* grow(blknum, length instrs) *)
580                 end                 end
581                   | _ => error "rewriteAll"
582    
583         in  Intmap.app rewriteAll affectedBlocks;         in  Intmap.app rewriteAll affectedBlocks;
584             let val spilledMarker = SPILLED ~2             let val spilledMarker = SPILLED ~2

Legend:
Removed from v.499  
changed lines
  Added in v.545

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