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

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

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

revision 475, Wed Nov 10 22:59:58 1999 UTC revision 498, Tue Dec 7 15:44:50 1999 UTC
# Line 48  Line 48 
48     structure Core   = RACore     structure Core   = RACore
49     structure G      = Core.G     structure G      = Core.G
50    
    datatype mode = REGISTER_ALLOCATION | COPY_PROPAGATION  
   
    datatype optimization = DEAD_COPY_ELIM  
                          | SPILL_PROPAGATION  
                          | SPILL_COALESCING  
                          | SPILL_COLORING  
                          | BIASED_SELECTION  
   
51     type getreg = { pref  : C.cell list,     type getreg = { pref  : C.cell list,
52                     stamp : int,                     stamp : int,
53                     proh  : int Array.array                     proh  : int Array.array
54                   } -> C.cell                   } -> C.cell
55    
56       type mode = word
57    
58       type raClient =
59       { cellkind     : C.cellkind,             (* kind of register *)
60         spillProh    : (C.cell * C.cell) list, (* don't spill these *)
61         K            : int,                    (* number of colors *)
62         dedicated    : bool Array.array,       (* dedicated registers *)
63         getreg       : getreg,                 (* how to find a color *)
64         copyInstr    : F.Spill.copyInstr,      (* how to make a copy *)
65         spill        : F.Spill.spill,          (* spill callback *)
66         spillSrc     : F.Spill.spillSrc,       (* spill callback *)
67         spillCopyTmp : F.Spill.spillCopyTmp,   (* spill callback *)
68         reload       : F.Spill.reload,         (* reload callback *)
69         reloadDst    : F.Spill.reloadDst,      (* reload callback *)
70         renameSrc    : F.Spill.renameSrc,      (* rename callback *)
71         firstMemReg  : C.cell,
72         numMemRegs   : int,
73         mode         : mode                    (* mode *)
74       }
75    
76       val debug = false
77    
78       val NO_OPTIMIZATION   = 0wx0
79       val DEAD_COPY_ELIM    = Core.DEAD_COPY_ELIM
80       val BIASED_SELECTION  = Core.BIASED_SELECTION
81       val SPILL_COALESCING  = 0wx100
82       val SPILL_COLORING    = 0wx200
83       val SPILL_PROPAGATION = 0wx400
84       val COPY_PROPAGATION  = 0wx800
85    
86       fun isOn(flag, mask) = Word.andb(flag,mask) <> 0w0
87    
88     open G     open G
89    
90     fun error msg = MLRiscErrorMsg.error("RegisterAllocator",msg)     fun error msg = MLRiscErrorMsg.error("RegisterAllocator",msg)
# Line 75  Line 99 
99     val debug_spill       = MLRiscControl.getFlag "ra-debug-spilling"     val debug_spill       = MLRiscControl.getFlag "ra-debug-spilling"
100     val ra_count          = MLRiscControl.getCounter "ra-count"     val ra_count          = MLRiscControl.getCounter "ra-count"
101     val rebuild_count     = MLRiscControl.getCounter "ra-rebuild"     val rebuild_count     = MLRiscControl.getCounter "ra-rebuild"
102    
103    (*
104     val count_dead        = MLRiscControl.getFlag "ra-count-dead-code"     val count_dead        = MLRiscControl.getFlag "ra-count-dead-code"
105     val dead              = MLRiscControl.getCounter "ra-dead-code"     val dead              = MLRiscControl.getCounter "ra-dead-code"
106     *)
107     val debug_stream      = MLRiscControl.debug_stream     val debug_stream      = MLRiscControl.debug_stream
108    
109     (*     (*
110      * Optimization flags      * Optimization flags
111      *)      *)
112    (*
113     val rematerialization = MLRiscControl.getFlag "ra-rematerialization"     val rematerialization = MLRiscControl.getFlag "ra-rematerialization"
114     *)
115    
116     exception NodeTable     exception NodeTable
117    
# Line 95  Line 124 
124      * Register allocator.      * Register allocator.
125      *    spillProh is a list of registers that are not candidates for spills.      *    spillProh is a list of registers that are not candidates for spills.
126      *)      *)
127     fun ra mode params flowgraph =     fun ra params flowgraph =
128     let     let
129         (* Flowgraph methods *)         (* Flowgraph methods *)
130         val {build=buildMethod, spill=spillMethod, ...} = F.services flowgraph         val {build=buildMethod, spill=spillMethod, ...} = F.services flowgraph
131    
132           (* global spill location counter *)
133           val spillLoc=ref ~256
134    
135           (* How to dump the flowgraph *)
136           fun dumpFlowgraph(flag, title) =
137               if !flag then F.dumpFlowgraph(title, flowgraph,!debug_stream) else ()
138    
139         (* Main function *)         (* Main function *)
140         fun regalloc{getreg, K, dedicated, copyInstr,         fun regalloc{getreg, K, dedicated, copyInstr,
141                      spill, reload, spillProh, cellkind, optimizations} =                      spill, spillSrc, spillCopyTmp, renameSrc,
142         if C.numCell cellkind () = 0                      reload, reloadDst, spillProh, cellkind, mode,
143                        firstMemReg, numMemRegs} =
144           let val numCell = C.numCell cellkind ()
145           in  if numCell = 0
146         then ()         then ()
147         else         else
148         let fun getOpt([], dce, sp, sc, scolor, bs) = (dce, sp, sc, scolor, bs)         let (* extract the regmap and blocks from the flowgraph *)
              | getOpt(DEAD_COPY_ELIM::opts, dce, sp, sc, scolor, bs) =  
                  getOpt(opts, true, sp, sc, scolor, bs)  
              | getOpt(SPILL_PROPAGATION::opts, dce, sp, sc, scolor, bs) =  
                  getOpt(opts, dce, true, sc, scolor, bs)  
              | getOpt(SPILL_COALESCING::opts, dce, sp, sc, scolor, bs) =  
                  getOpt(opts, dce, sp, true, scolor, bs)  
              | getOpt(SPILL_COLORING::opts, dce, sp, sc, scolor, bs) =  
                  getOpt(opts, dce, sp, sc, true, bs)  
              | getOpt(BIASED_SELECTION::opts, dce, sp, sc, scolor, bs) =  
                  getOpt(opts, dce, sp, sc, scolor, true)  
   
            val (deadCopyElim, spillProp, spillCoalescing,  
                 spillColoring, biasedSelection) =  
                getOpt(optimizations, false, false, false, false, false)  
   
            (* extract the regmap and blocks from the flowgraph *)  
149             val regmap = F.regmap flowgraph (* the register map *)             val regmap = F.regmap flowgraph (* the register map *)
150    
151             (* the nodes table *)             (* the nodes table *)
152             val nodes  = Intmap.new(32,NodeTable)             val nodes  = Intmap.new(numCell,NodeTable)
153             (* create an empty interference graph *)             (* create an empty interference graph *)
154             val G      = G.newGraph{nodes=nodes,             val G      = G.newGraph{nodes=nodes,
155                                     K=K,                                     K=K,
156                                     dedicated=dedicated,                                     dedicated=dedicated,
157                                     numRegs=C.numCell cellkind (),                                     numRegs=numCell,
158                                     maxRegs=C.maxCell,                                     maxRegs=C.maxCell,
159                                     regmap=regmap,                                     regmap=regmap,
160                                     showReg=C.toString cellkind,                                     showReg=C.toString cellkind,
161                                     getreg=getreg,                                     getreg=getreg,
162                                     getpair=fn _ => error "getpair",                                     getpair=fn _ => error "getpair",
163                                     firstPseudoR=C.firstPseudo,                                     firstPseudoR=C.firstPseudo,
164                                     proh=proh                                     proh=proh,
165                                       mode=Word.orb(Flowgraph.mode,
166                                             Word.orb(mode,SpillHeuristics.mode)),
167                                       spillLoc=spillLoc,
168                                       firstMemReg=firstMemReg,
169                                       numMemRegs=numMemRegs
170                                    }                                    }
171             val G.GRAPH{spilledRegs,...} = G             val G.GRAPH{spilledRegs, pseudoCount, spillFlag, ...} = G
172    
173             val hasBeenSpilled = Intmap.mapWithDefault (spilledRegs,false)             val hasBeenSpilled = Intmap.mapWithDefault (spilledRegs,false)
174    
# Line 156  Line 184 
184              * Build the interference graph              * Build the interference graph
185              *)              *)
186             fun buildGraph(G) =             fun buildGraph(G) =
187             let val moves = buildMethod(G,cellkind)             let val _ = if debug then print "build..." else ()
188                 val worklists = (Core.initWorkLists G)                 val moves = buildMethod(G,cellkind)
189                                   {moves=moves, deadCopyElim=deadCopyElim}                 val worklists =
190             in  if !count_dead then                     (Core.initWorkLists G) {moves=moves}
191               in  (* if !count_dead then
192                    Intmap.app (fn (_,NODE{uses=ref [],...}) => dead := !dead + 1                    Intmap.app (fn (_,NODE{uses=ref [],...}) => dead := !dead + 1
193                                 | _ => ()) nodes                                 | _ => ()) nodes
194                 else ();                 else (); *)
195                 logGraph("build",G);                 logGraph("build",G);
196                   if debug then
197                   let val G.GRAPH{bitMatrix=ref(G.BM{elems, ...}), ...} = G
198                   in  print ("done: nodes="^Int.toString(Intmap.elems nodes)^
199                              " edges="^Int.toString(!elems)^
200                              " moves="^Int.toString(length moves)^
201                              "\n")
202                   end else ();
203                 worklists                 worklists
204             end             end
205    
# Line 176  Line 212 
212                      app (fn n => print(Core.show G n^" ")) spillWkl;                      app (fn n => print(Core.show G n^" ")) spillWkl;
213                      print "\n"                      print "\n"
214                     )                     )
215                   (* Initialize if it is the first time we spill *)
216                   val _ = if !spillFlag then () else SpillHeuristics.init()
217                   (* Choose a node *)
218                 val {node,cost,spillWkl} =                 val {node,cost,spillWkl} =
219                     SpillHeuristics.chooseSpillNode                     SpillHeuristics.chooseSpillNode
220                         {hasBeenSpilled=hasBeenSpilled,                         {graph=G, hasBeenSpilled=hasBeenSpilled,
221                          spillWkl=spillWkl}                          spillWkl=spillWkl}
222                      handle SpillHeuristics.NoCandidate =>                      handle SpillHeuristics.NoCandidate =>
223                        (Core.dumpGraph G (!debug_stream);                        (Core.dumpGraph G (!debug_stream);
# Line 207  Line 246 
246                   | loop(NODE{color, ...}::ns) = (color := marker; loop ns)                   | loop(NODE{color, ...}::ns) = (color := marker; loop ns)
247             in  loop nodesToSpill end             in  loop nodesToSpill end
248    
249               (* Mark nodes that are immediately aliased to mem regs;
250                * These are nodes that need also to be spilled
251                *)
252               fun markMemRegs [] = ()
253                 | markMemRegs(NODE{number=r, color as ref(ALIASED
254                              (NODE{color=ref(col as SPILLED c), ...})), ...}::ns) =
255                    (if c >= 0 then color := col else ();
256                     markMemRegs ns)
257                 | markMemRegs(_::ns) = markMemRegs ns
258    
259             (*             (*
260              * Actual spill phase.              * Actual spill phase.
261              *   Insert spill node and incrementally              *   Insert spill node and incrementally
262              *   update the interference graph.              *   update the interference graph.
263              *)              *)
264             fun actualSpills{spills} =             fun actualSpills{spills} =
265             let val _ = if spillProp orelse spillCoalescing orelse             let val _ = if debug then print "spill..." else ();
266                            spillColoring then markSpillNodes spills                 val _ = if isOn(mode,
267                                   SPILL_COALESCING+
268                                   SPILL_PROPAGATION+
269                                   SPILL_COLORING) then
270                               markSpillNodes spills
271                         else ()                         else ()
272                 val spills = if spillProp then                 val _ = if isOn(mode,SPILL_PROPAGATION+SPILL_COALESCING) then
273                              Core.initMemMoves G
274                           else ()
275                   val spills = if isOn(mode,SPILL_PROPAGATION) then
276                                Core.spillPropagation G spills else spills                                Core.spillPropagation G spills else spills
277                 val _ = if spillCoalescing then                 val _ = if isOn(mode,SPILL_COALESCING) then
278                            Core.spillCoalescing G spills else ()                            Core.spillCoalescing G spills else ()
279                 val _ = if spillColoring then                 val _ = if isOn(mode,SPILL_COLORING) then
280                            Core.spillColoring G spills else ()                            Core.spillColoring G spills else ()
281                   val _ = if isOn(mode,SPILL_COALESCING+SPILL_PROPAGATION) then
282                              markMemRegs spills else ()
283                   val _ = logGraph("actual spill",G);
284                 val {simplifyWkl,freezeWkl,moveWkl,spillWkl} =                 val {simplifyWkl,freezeWkl,moveWkl,spillWkl} =
285                      Core.initWorkLists G                      Core.initWorkLists G
286                         {moves=spillMethod{graph=G, cellkind=cellkind,                         {moves=spillMethod{graph=G, cellkind=cellkind,
287                                            spill=spill, reload=reload,                                            spill=spill, spillSrc=spillSrc,
288                                              spillCopyTmp=spillCopyTmp,
289                                              renameSrc=renameSrc,
290                                              reload=reload, reloadDst=reloadDst,
291                                            copyInstr=copyInstr, nodes=spills                                            copyInstr=copyInstr, nodes=spills
                                          },  
                         deadCopyElim=deadCopyElim  
292                         }                         }
293                 val _ = if !cfg_after_spill then                         }
294                           F.dumpFlowgraph("after spilling",                 val _ = dumpFlowgraph(cfg_after_spill,"after spilling")
                                          flowgraph,!debug_stream)  
                        else ()  
295             in  logGraph("rebuild",G);             in  logGraph("rebuild",G);
296                   if debug then print "done\n" else ();
297                 rebuild_count := !rebuild_count + 1;                 rebuild_count := !rebuild_count + 1;
298                 (simplifyWkl, moveWkl, freezeWkl, spillWkl, [])                 (simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
299             end             end
# Line 265  Line 324 
324                     in  case spillWkl of                     in  case spillWkl of
325                           [] => stack (* nothing to spill *)                           [] => stack (* nothing to spill *)
326                         |  _ =>                         |  _ =>
327                             if !pseudoCount = 0 (* all nodes simplified *)
328                             then stack
329                             else
330                           let val {node,spillWkl} =                           let val {node,spillWkl} =
331                                      chooseVictim{spillWkl=spillWkl}                                      chooseVictim{spillWkl=spillWkl}
332                           in  case node of                           in  case node of
333                                 SOME node => (* spill node and continue *)                                 SOME node => (* spill node and continue *)
334                                 let val {moveWkl,freezeWkl,stack} =                                 let val _ = if debug then print "-" else ()
335                                       val {moveWkl,freezeWkl,stack} =
336                                         potentialSpill{node=node,stack=stack}                                         potentialSpill{node=node,stack=stack}
337                                 in  iterate([],moveWkl,freezeWkl,spillWkl,stack)                                 in  iterate([],moveWkl,freezeWkl,spillWkl,stack)
338                                 end                                 end
# Line 281  Line 344 
344                     val stack = iterate                     val stack = iterate
345                            (simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)                            (simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)
346                     (* color the nodes *)                     (* color the nodes *)
347                     val {spills} = (Core.select G)                     val {spills} = (Core.select G) {stack=stack}
                                     {stack=stack, biased= biasedSelection}  
348                 in  (* check for actual spills *)                 in  (* check for actual spills *)
349                     case spills of                     case spills of
350                       [] => ()                       [] => ()
351                     | spills =>                     | spills =>
352                       (case mode of                       (if isOn(mode,COPY_PROPAGATION) then ()
353                         REGISTER_ALLOCATION => loop(actualSpills{spills=spills})                        else loop(actualSpills{spills=spills})
                      | COPY_PROPAGATION => ()  
354                       )                       )
355                 end                 end
356    
# Line 304  Line 365 
365                     if r <= to then (markAsSpilled(r,true); loop(r+1)) else ()                     if r <= to then (markAsSpilled(r,true); loop(r+1)) else ()
366             in  loop from end             in  loop from end
367    
368         in  if !cfg_before_ra then         in  dumpFlowgraph(cfg_before_ra,"before register allocation");
               F.dumpFlowgraph("before register allocation",  
                               flowgraph,!debug_stream)  
            else ();  
369             app initSpillProh spillProh;             app initSpillProh spillProh;
370             main(G); (* main loop *)             main(G); (* main loop *)
371             (* update the regmap *)             (* update the regmap *)
372             logGraph("done",G);             logGraph("done",G);
373             case mode of             if isOn(mode,COPY_PROPAGATION)
374               REGISTER_ALLOCATION => Core.finishRA G             then Core.finishCP G
375             | COPY_PROPAGATION => Core.finishCP G             else Core.finishRA G
376             ;             ;
377             ra_count := !ra_count + 1;             ra_count := !ra_count + 1;
378             if !cfg_after_ra then             dumpFlowgraph(cfg_after_ra,"after register allocation");
379                F.dumpFlowgraph("after register allocation",             (* Clean up spilling *)
380                                flowgraph,!debug_stream)             SpillHeuristics.init()
381             else ()         end
382         end         end
383    
384         fun regallocs [] = ()         fun regallocs [] = ()

Legend:
Removed from v.475  
changed lines
  Added in v.498

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