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

sml/branches/SMLNJ/src/MLRISC/ra/ra.sml revision 475, Wed Nov 10 22:59:58 1999 UTC sml/trunk/src/MLRISC/ra/ra.sml revision 576, Fri Mar 10 07:27:16 2000 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         memRegs      : (C.cell * C.cell) list, (* memory registers *)
62         K            : int,                    (* number of colors *)
63         dedicated    : bool Array.array,       (* dedicated registers *)
64         getreg       : getreg,                 (* how to find a color *)
65         copyInstr    : F.Spill.copyInstr,      (* how to make a copy *)
66         spill        : F.Spill.spill,          (* spill callback *)
67         spillSrc     : F.Spill.spillSrc,       (* spill callback *)
68         spillCopyTmp : F.Spill.spillCopyTmp,   (* spill callback *)
69         reload       : F.Spill.reload,         (* reload callback *)
70         reloadDst    : F.Spill.reloadDst,      (* reload callback *)
71         renameSrc    : F.Spill.renameSrc,      (* rename callback *)
72         mode         : mode                    (* mode *)
73       }
74    
75       val debug = false
76    
77       val NO_OPTIMIZATION        = 0wx0
78       val DEAD_COPY_ELIM         = Core.DEAD_COPY_ELIM
79       val BIASED_SELECTION       = Core.BIASED_SELECTION
80       val HAS_PARALLEL_COPIES    = Core.HAS_PARALLEL_COPIES
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 71  Line 95 
95     val cfg_before_ra     = MLRiscControl.getFlag "dump-cfg-before-ra"     val cfg_before_ra     = MLRiscControl.getFlag "dump-cfg-before-ra"
96     val cfg_after_ra      = MLRiscControl.getFlag "dump-cfg-after-ra"     val cfg_after_ra      = MLRiscControl.getFlag "dump-cfg-after-ra"
97     val cfg_after_spill   = MLRiscControl.getFlag "dump-cfg-after-spilling"     val cfg_after_spill   = MLRiscControl.getFlag "dump-cfg-after-spilling"
98       val cfg_before_ras    = MLRiscControl.getFlag "dump-cfg-before-all-ra"
99       val cfg_after_ras     = MLRiscControl.getFlag "dump-cfg-after-all-ra"
100     val dump_graph        = MLRiscControl.getFlag "dump-interference-graph"     val dump_graph        = MLRiscControl.getFlag "dump-interference-graph"
101     val debug_spill       = MLRiscControl.getFlag "ra-debug-spilling"     val debug_spill       = MLRiscControl.getFlag "ra-debug-spilling"
102     val ra_count          = MLRiscControl.getCounter "ra-count"     val ra_count          = MLRiscControl.getCounter "ra-count"
103     val rebuild_count     = MLRiscControl.getCounter "ra-rebuild"     val rebuild_count     = MLRiscControl.getCounter "ra-rebuild"
104    
105    (*
106     val count_dead        = MLRiscControl.getFlag "ra-count-dead-code"     val count_dead        = MLRiscControl.getFlag "ra-count-dead-code"
107     val dead              = MLRiscControl.getCounter "ra-dead-code"     val dead              = MLRiscControl.getCounter "ra-dead-code"
108     *)
109     val debug_stream      = MLRiscControl.debug_stream     val debug_stream      = MLRiscControl.debug_stream
110    
111     (*     (*
112      * Optimization flags      * Optimization flags
113      *)      *)
114    (*
115     val rematerialization = MLRiscControl.getFlag "ra-rematerialization"     val rematerialization = MLRiscControl.getFlag "ra-rematerialization"
116     *)
117    
118     exception NodeTable     exception NodeTable
119    
# Line 95  Line 126 
126      * Register allocator.      * Register allocator.
127      *    spillProh is a list of registers that are not candidates for spills.      *    spillProh is a list of registers that are not candidates for spills.
128      *)      *)
129     fun ra mode params flowgraph =     fun ra params flowgraph =
130     let     let
131         (* Flowgraph methods *)         (* Flowgraph methods *)
132         val {build=buildMethod, spill=spillMethod, ...} = F.services flowgraph         val {build=buildMethod, spill=spillMethod, ...} = F.services flowgraph
133    
134           (* global spill location counter *)
135           val spillLoc=ref ~256
136    
137           (* How to dump the flowgraph *)
138           fun dumpFlowgraph(flag, title) =
139               if !flag then F.dumpFlowgraph(title, flowgraph,!debug_stream) else ()
140    
141         (* Main function *)         (* Main function *)
142         fun regalloc{getreg, K, dedicated, copyInstr,         fun regalloc{getreg, K, dedicated, copyInstr,
143                      spill, reload, spillProh, cellkind, optimizations} =                      spill, spillSrc, spillCopyTmp, renameSrc,
144         if C.numCell cellkind () = 0                      reload, reloadDst, spillProh, cellkind, mode,
145                        memRegs} =
146           let val numCell = C.numCell cellkind ()
147           in  if numCell = 0
148         then ()         then ()
149         else         else
150         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 *)  
151             val regmap = F.regmap flowgraph (* the register map *)             val regmap = F.regmap flowgraph (* the register map *)
152    
153             (* the nodes table *)             (* the nodes table *)
154             val nodes  = Intmap.new(32,NodeTable)             val nodes  = Intmap.new(numCell,NodeTable)
155               val mode   = if isOn(HAS_PARALLEL_COPIES, mode) then
156                               Word.orb(Core.SAVE_COPY_TEMPS, mode)
157                            else mode
158             (* create an empty interference graph *)             (* create an empty interference graph *)
159             val G      = G.newGraph{nodes=nodes,             val G      = G.newGraph{nodes=nodes,
160                                     K=K,                                     K=K,
161                                     dedicated=dedicated,                                     dedicated=dedicated,
162                                     numRegs=C.numCell cellkind (),                                     numRegs=numCell,
163                                     maxRegs=C.maxCell,                                     maxRegs=C.maxCell,
164                                     regmap=regmap,                                     regmap=regmap,
165                                     showReg=C.toString cellkind,                                     showReg=C.toString cellkind,
166                                     getreg=getreg,                                     getreg=getreg,
167                                     getpair=fn _ => error "getpair",                                     getpair=fn _ => error "getpair",
168                                     firstPseudoR=C.firstPseudo,                                     firstPseudoR=C.firstPseudo,
169                                     proh=proh                                     proh=proh,
170                                       mode=Word.orb(Flowgraph.mode,
171                                             Word.orb(mode,SpillHeuristics.mode)),
172                                       spillLoc=spillLoc,
173                                       memRegs=memRegs
174                                    }                                    }
175             val G.GRAPH{spilledRegs,...} = G             val G.GRAPH{spilledRegs, pseudoCount, spillFlag, ...} = G
176    
177             val hasBeenSpilled = Intmap.mapWithDefault (spilledRegs,false)             val hasBeenSpilled = Intmap.mapWithDefault (spilledRegs,false)
178    
# Line 156  Line 188 
188              * Build the interference graph              * Build the interference graph
189              *)              *)
190             fun buildGraph(G) =             fun buildGraph(G) =
191             let val moves = buildMethod(G,cellkind)             let val _ = if debug then print "build..." else ()
192                 val worklists = (Core.initWorkLists G)                 val moves = buildMethod(G,cellkind)
193                                   {moves=moves, deadCopyElim=deadCopyElim}                 val worklists =
194             in  if !count_dead then                     (Core.initWorkLists G) {moves=moves}
195               in  (* if !count_dead then
196                    Intmap.app (fn (_,NODE{uses=ref [],...}) => dead := !dead + 1                    Intmap.app (fn (_,NODE{uses=ref [],...}) => dead := !dead + 1
197                                 | _ => ()) nodes                                 | _ => ()) nodes
198                 else ();                 else (); *)
199                 logGraph("build",G);                 logGraph("build",G);
200                   if debug then
201                   let val G.GRAPH{bitMatrix=ref(G.BM{elems, ...}), ...} = G
202                   in  print ("done: nodes="^Int.toString(Intmap.elems nodes)^
203                              " edges="^Int.toString(!elems)^
204                              " moves="^Int.toString(length moves)^
205                              "\n")
206                   end else ();
207                 worklists                 worklists
208             end             end
209    
# Line 176  Line 216 
216                      app (fn n => print(Core.show G n^" ")) spillWkl;                      app (fn n => print(Core.show G n^" ")) spillWkl;
217                      print "\n"                      print "\n"
218                     )                     )
219                   (* Initialize if it is the first time we spill *)
220                   val _ = if !spillFlag then () else SpillHeuristics.init()
221                   (* Choose a node *)
222                 val {node,cost,spillWkl} =                 val {node,cost,spillWkl} =
223                     SpillHeuristics.chooseSpillNode                     SpillHeuristics.chooseSpillNode
224                         {hasBeenSpilled=hasBeenSpilled,                         {graph=G, hasBeenSpilled=hasBeenSpilled,
225                          spillWkl=spillWkl}                          spillWkl=spillWkl}
226                      handle SpillHeuristics.NoCandidate =>                      handle SpillHeuristics.NoCandidate =>
227                        (Core.dumpGraph G (!debug_stream);                        (Core.dumpGraph G (!debug_stream);
# Line 195  Line 238 
238                                " uses="^Int.toString(length(!uses))^"\n"                                " uses="^Int.toString(length(!uses))^"\n"
239                               )                               )
240                    ) else ();                    ) else ();
241                 {node=node,spillWkl=spillWkl}                 {node=node,cost=cost,spillWkl=spillWkl}
242             end             end
243    
244             (*             (*
# Line 207  Line 250 
250                   | loop(NODE{color, ...}::ns) = (color := marker; loop ns)                   | loop(NODE{color, ...}::ns) = (color := marker; loop ns)
251             in  loop nodesToSpill end             in  loop nodesToSpill end
252    
253               (* Mark nodes that are immediately aliased to mem regs;
254                * These are nodes that need also to be spilled
255                *)
256               fun markMemRegs [] = ()
257                 | markMemRegs(NODE{number=r, color as ref(ALIASED
258                              (NODE{color=ref(col as SPILLED c), ...})), ...}::ns) =
259                    (if c >= 0 then color := col else ();
260                     markMemRegs ns)
261                 | markMemRegs(_::ns) = markMemRegs ns
262    
263             (*             (*
264              * Actual spill phase.              * Actual spill phase.
265              *   Insert spill node and incrementally              *   Insert spill node and incrementally
266              *   update the interference graph.              *   update the interference graph.
267              *)              *)
268             fun actualSpills{spills} =             fun actualSpills{spills} =
269             let val _ = if spillProp orelse spillCoalescing orelse             let val _ = if debug then print "spill..." else ();
270                            spillColoring then markSpillNodes spills                 val _ = if isOn(mode,
271                                   SPILL_COALESCING+
272                                   SPILL_PROPAGATION+
273                                   SPILL_COLORING) then
274                               markSpillNodes spills
275                           else ()
276                   val _ = if isOn(mode,SPILL_PROPAGATION+SPILL_COALESCING) then
277                              Core.initMemMoves G
278                         else ()                         else ()
279                 val spills = if spillProp then                 (*
280                   val spills = if isOn(mode,SPILL_PROPAGATION) then
281                                Core.spillPropagation G spills else spills                                Core.spillPropagation G spills else spills
282                 val _ = if spillCoalescing then                 val _ = if isOn(mode,SPILL_COALESCING) then
283                            Core.spillCoalescing G spills else ()                            Core.spillCoalescing G spills else ()
284                 val _ = if spillColoring then                 val _ = if isOn(mode,SPILL_COLORING) then
285                            Core.spillColoring G spills else ()                            Core.spillColoring G spills else ()
286                   val _ = if isOn(mode,SPILL_COALESCING+SPILL_PROPAGATION) then
287                              markMemRegs spills else ()
288                    *)
289                   val _ = logGraph("actual spill",G);
290                 val {simplifyWkl,freezeWkl,moveWkl,spillWkl} =                 val {simplifyWkl,freezeWkl,moveWkl,spillWkl} =
291                      Core.initWorkLists G                      Core.initWorkLists G
292                         {moves=spillMethod{graph=G, cellkind=cellkind,                         {moves=spillMethod{graph=G, cellkind=cellkind,
293                                            spill=spill, reload=reload,                                            spill=spill, spillSrc=spillSrc,
294                                              spillCopyTmp=spillCopyTmp,
295                                              renameSrc=renameSrc,
296                                              reload=reload, reloadDst=reloadDst,
297                                            copyInstr=copyInstr, nodes=spills                                            copyInstr=copyInstr, nodes=spills
                                          },  
                         deadCopyElim=deadCopyElim  
298                         }                         }
299                 val _ = if !cfg_after_spill then                         }
300                           F.dumpFlowgraph("after spilling",                 val _ = dumpFlowgraph(cfg_after_spill,"after spilling")
                                          flowgraph,!debug_stream)  
                        else ()  
301             in  logGraph("rebuild",G);             in  logGraph("rebuild",G);
302                   if debug then print "done\n" else ();
303                 rebuild_count := !rebuild_count + 1;                 rebuild_count := !rebuild_count + 1;
304                 (simplifyWkl, moveWkl, freezeWkl, spillWkl, [])                 (simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
305             end             end
# Line 265  Line 330 
330                     in  case spillWkl of                     in  case spillWkl of
331                           [] => stack (* nothing to spill *)                           [] => stack (* nothing to spill *)
332                         |  _ =>                         |  _ =>
333                           let val {node,spillWkl} =                           if !pseudoCount = 0 (* all nodes simplified *)
334                             then stack
335                             else
336                             let val {node,cost,spillWkl} =
337                                      chooseVictim{spillWkl=spillWkl}                                      chooseVictim{spillWkl=spillWkl}
338                           in  case node of                           in  case node of
339                                 SOME node => (* spill node and continue *)                                 SOME node => (* spill node and continue *)
340                                 let val {moveWkl,freezeWkl,stack} =                                 let val _ = if debug then print "-" else ()
341                                         potentialSpill{node=node,stack=stack}                                     val {moveWkl,freezeWkl,stack} =
342                                           potentialSpill{node=node,
343                                                          cost=cost,
344                                                          stack=stack}
345                                 in  iterate([],moveWkl,freezeWkl,spillWkl,stack)                                 in  iterate([],moveWkl,freezeWkl,spillWkl,stack)
346                                 end                                 end
347                               | NONE => stack (* nothing to spill *)                               | NONE => stack (* nothing to spill *)
348                           end                           end
349                     end                     end
350    
351                     (* simplify the nodes *)                     val {spills} =
352                           if K = 0 then
353                             {spills=spillWkl}
354                           else
355                             let (* simplify the nodes *)
356                     val stack = iterate                     val stack = iterate
357                            (simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)                            (simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)
358                     (* color the nodes *)                     (* color the nodes *)
359                     val {spills} = (Core.select G)                           in  (Core.select G) {stack=stack}
360                                      {stack=stack, biased= biasedSelection}                           end
361                 in  (* check for actual spills *)                 in  (* check for actual spills *)
362                     case spills of                     case spills of
363                       [] => ()                       [] => ()
364                     | spills =>                     | spills =>
365                       (case mode of                       (if isOn(mode,COPY_PROPAGATION) then ()
366                         REGISTER_ALLOCATION => loop(actualSpills{spills=spills})                        else loop(actualSpills{spills=spills})
                      | COPY_PROPAGATION => ()  
367                       )                       )
368                 end                 end
369    
# Line 304  Line 378 
378                     if r <= to then (markAsSpilled(r,true); loop(r+1)) else ()                     if r <= to then (markAsSpilled(r,true); loop(r+1)) else ()
379             in  loop from end             in  loop from end
380    
381         in  if !cfg_before_ra then         in  dumpFlowgraph(cfg_before_ra,"before register allocation");
               F.dumpFlowgraph("before register allocation",  
                               flowgraph,!debug_stream)  
            else ();  
382             app initSpillProh spillProh;             app initSpillProh spillProh;
383             main(G); (* main loop *)             main(G); (* main loop *)
384             (* update the regmap *)             (* update the regmap *)
385             logGraph("done",G);             logGraph("done",G);
386             case mode of             if isOn(mode,COPY_PROPAGATION)
387               REGISTER_ALLOCATION => Core.finishRA G             then Core.finishCP G
388             | COPY_PROPAGATION => Core.finishCP G             else Core.finishRA G
389             ;             ;
390             ra_count := !ra_count + 1;             ra_count := !ra_count + 1;
391             if !cfg_after_ra then             dumpFlowgraph(cfg_after_ra,"after register allocation");
392                F.dumpFlowgraph("after register allocation",             (* Clean up spilling *)
393                                flowgraph,!debug_stream)             SpillHeuristics.init()
394             else ()         end
395         end         end
396    
397         fun regallocs [] = ()         fun regallocs [] = ()
398           | regallocs(p::ps) = (regalloc p; regallocs ps)           | regallocs(p::ps) = (regalloc p; regallocs ps)
399    
400     in  regallocs params;     in  dumpFlowgraph(cfg_before_ras,"before register allocation");
401           regallocs params;
402           dumpFlowgraph(cfg_after_ras,"after register allocation");
403         flowgraph         flowgraph
404     end     end
405    

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

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