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/branches/SMLNJ/src/MLRISC/ra/ra.sml
ViewVC logotype

Diff of /sml/branches/SMLNJ/src/MLRISC/ra/ra.sml

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

revision 474, Wed Nov 10 22:59:58 1999 UTC revision 475, Wed Nov 10 22:59:58 1999 UTC
# Line 3  Line 3 
3   * the 'iterated register coalescing' scheme described   * the 'iterated register coalescing' scheme described
4   * in POPL'96, and TOPLAS v18 #3, pp 325-353.   * in POPL'96, and TOPLAS v18 #3, pp 325-353.
5   *   *
6   * Now with numerous extension:   * Now with numerous extensions:
7   *   *
8     *   0. Dead copy elimination (optional)
9   *   1. Priority based coalescing   *   1. Priority based coalescing
10   *   2. Priority based freezing   *   2. Priority based freezing
11   *   3. Priority based spilling   *   3. Priority based spilling
12   *   4. Biased coloring (optional)   *   4. Biased selection (optional)
13   *   5. Rematerialization (optional)   *   5. Spill Coalescing (optional)
14   *   6. Register pair coloring (to support Sparc, C6, and others)   *   6. Spill Propagation (optional)
15   *   7. Splitting (optional)   *   7. Spill Coloring (optional)
16     *
17     * For details, please see the paper from
18     *
19     *    http://cm.bell-labs.com/cm/cs/what/smlnj/compiler-notes/index.html
20   *   *
21   * The basic structure of this register allocator is as follows:   * The basic structure of this register allocator is as follows:
22   *   1.  RAGraph.  This module enscapsulates the interference graph   *   1.  RAGraph.  This module enscapsulates the interference graph
# Line 29  Line 34 
34   *       to make spilling fast.   *       to make spilling fast.
35   *   4.  This functor.  This functor drives the entire process.   *   4.  This functor.  This functor drives the entire process.
36   *   *
37   * -- Allen   * -- Allen Leung (leunga@cs.nyu.edu)
38   *)   *)
39    
40  functor RegisterAllocator  functor RegisterAllocator
# Line 46  Line 51 
51     datatype mode = REGISTER_ALLOCATION | COPY_PROPAGATION     datatype mode = REGISTER_ALLOCATION | COPY_PROPAGATION
52    
53     datatype optimization = DEAD_COPY_ELIM     datatype optimization = DEAD_COPY_ELIM
54                             | SPILL_PROPAGATION
55                           | SPILL_COALESCING                           | SPILL_COALESCING
56                           | SPILL_COLORING                           | SPILL_COLORING
57                             | BIASED_SELECTION
58    
59     type getreg = { pref  : C.cell list,     type getreg = { pref  : C.cell list,
60                     stamp : int,                     stamp : int,
# Line 59  Line 66 
66     fun error msg = MLRiscErrorMsg.error("RegisterAllocator",msg)     fun error msg = MLRiscErrorMsg.error("RegisterAllocator",msg)
67    
68     (*     (*
69      * Debugging flags      * Debugging flags + counters
70      *)      *)
71     val cfg_before_ra     = MLRiscControl.getFlag "dump-cfg-before-ra"     val cfg_before_ra     = MLRiscControl.getFlag "dump-cfg-before-ra"
72     val cfg_after_ra      = MLRiscControl.getFlag "dump-cfg-after-ra"     val cfg_after_ra      = MLRiscControl.getFlag "dump-cfg-after-ra"
# Line 75  Line 82 
82     (*     (*
83      * Optimization flags      * Optimization flags
84      *)      *)
    val biasedColoring    = MLRiscControl.getFlag "ra-biased-coloring"  
85     val rematerialization = MLRiscControl.getFlag "ra-rematerialization"     val rematerialization = MLRiscControl.getFlag "ra-rematerialization"
86    
87     exception NodeTable     exception NodeTable
# Line 100  Line 106 
106         if C.numCell cellkind () = 0         if C.numCell cellkind () = 0
107         then ()         then ()
108         else         else
109         let fun getOpt([], dce, sc, sp) = (dce, sc, sp)         let fun getOpt([], dce, sp, sc, scolor, bs) = (dce, sp, sc, scolor, bs)
110               | getOpt(DEAD_COPY_ELIM::opts, dce, sc, sp) =               | getOpt(DEAD_COPY_ELIM::opts, dce, sp, sc, scolor, bs) =
111                   getOpt(opts, true, sc, sp)                   getOpt(opts, true, sp, sc, scolor, bs)
112               | getOpt(SPILL_COALESCING::opts, dce, sc, sp) =               | getOpt(SPILL_PROPAGATION::opts, dce, sp, sc, scolor, bs) =
113                   getOpt(opts, dce, true, sp)                   getOpt(opts, dce, true, sc, scolor, bs)
114               | getOpt(SPILL_COLORING::opts, dce, sc, sp) =               | getOpt(SPILL_COALESCING::opts, dce, sp, sc, scolor, bs) =
115                   getOpt(opts, dce, sc, true)                   getOpt(opts, dce, sp, true, scolor, bs)
116                 | getOpt(SPILL_COLORING::opts, dce, sp, sc, scolor, bs) =
117             val (deadCopyElim, spillCoalescing, spillColoring) =                   getOpt(opts, dce, sp, sc, true, bs)
118                 getOpt(optimizations, false, false, false)               | getOpt(BIASED_SELECTION::opts, dce, sp, sc, scolor, bs) =
119                     getOpt(opts, dce, sp, sc, scolor, true)
120    
121               val (deadCopyElim, spillProp, spillCoalescing,
122                    spillColoring, biasedSelection) =
123                   getOpt(optimizations, false, false, false, false, false)
124    
125             (* extract the regmap and blocks from the flowgraph *)             (* extract the regmap and blocks from the flowgraph *)
126             val regmap = F.regmap flowgraph (* the register map *)             val regmap = F.regmap flowgraph (* the register map *)
# Line 188  Line 199 
199             end             end
200    
201             (*             (*
202              * Rematerialization              * Mark spill nodes
203              *)              *)
204             fun rematerialize{node} = error "rematerialize"             fun markSpillNodes nodesToSpill =
205               let val marker = SPILLED(~1)
206             (*                 fun loop [] = ()
207              * Splitting                   | loop(NODE{color, ...}::ns) = (color := marker; loop ns)
208              *)             in  loop nodesToSpill end
            fun split{node} = error "split"  
209    
210             (*             (*
211              * Actual spill phase.              * Actual spill phase.
# Line 203  Line 213 
213              *   update the interference graph.              *   update the interference graph.
214              *)              *)
215             fun actualSpills{spills} =             fun actualSpills{spills} =
216             let val _ = if spillCoalescing then             let val _ = if spillProp orelse spillCoalescing orelse
217                              spillColoring then markSpillNodes spills
218                           else ()
219                   val spills = if spillProp then
220                                  Core.spillPropagation G spills else spills
221                   val _ = if spillCoalescing then
222                            Core.spillCoalescing G spills else ()                            Core.spillCoalescing G spills else ()
223                 val _ = if spillColoring then                 val _ = if spillColoring then
224                            Core.spillColoring G spills else ()                            Core.spillColoring G spills else ()
# Line 267  Line 282 
282                            (simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)                            (simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)
283                     (* color the nodes *)                     (* color the nodes *)
284                     val {spills} = (Core.select G)                     val {spills} = (Core.select G)
285                                      {stack=stack, biased= !biasedColoring}                                      {stack=stack, biased= biasedSelection}
286                 in  (* check for actual spills *)                 in  (* check for actual spills *)
287                     case spills of                     case spills of
288                       [] => ()                       [] => ()

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

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