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-core.sig
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/ra/ra-core.sig

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

revision 428, Wed Sep 8 09:47:00 1999 UTC revision 469, Wed Nov 10 22:42:52 1999 UTC
# Line 1  Line 1 
1  (** Graph coloring register allocation.  (*
2   ** Implements the 'iterated register coalescing' scheme described   * Note: This is the core of the new register allocator, i.e. the portion
3   ** in POPL'96, and TOPLAS v18 #3, pp 325-353.   * that manipulates only the interference graph and not the flowgraph.
4   **   *
5   ** RA CORE defines the core of the register allocator.   * -- Allen
6   ** This basically means the enableMove, coalesce, simplify and freeze phases.   *)
  ** These are separated out from the rest for more modularity  
  ** and customizability.  
  **  
  ** -- Allen  
  **)  
   
7    
8  signature RA_CORE =  signature RA_CORE =
9  sig  sig
10    
11     structure G : RA_GRAPH     structure G : RA_GRAPH
12    
13       type move_queue
14       type freeze_queue
15    
16     (*     (*
17      * Basic functions      * Basic functions
18      *)      *)
19         (* add an edge *)  
20       (* dump the interference graph to a stream *)
21       val dumpGraph : G.interferenceGraph -> TextIO.outstream -> unit
22       val show      : G.interferenceGraph -> G.node -> string
23    
24       (* add an edge to the interference graph *)
25     val addEdge : G.interferenceGraph -> G.node * G.node -> unit     val addEdge : G.interferenceGraph -> G.node * G.node -> unit
        (* debugging *)  
    val dumpGraph : G.interferenceGraph -> unit  
26    
27       (* remove an edge from the interference graph *)
28       val removeEdge : G.interferenceGraph -> G.node * G.node -> unit
29    
30     (*     (*
31      * Core phases      * Function to create new nodes
32      *)      *)
33     val makeWorkLists : G.interferenceGraph -> G.movelist  -> G.worklists     val newNodes : G.interferenceGraph ->
34     val simplifyPhase : G.interferenceGraph -> G.worklists -> G.worklists          {cost:int,pt:G.programPoint,defs:int list,uses:int list} ->
35     val coalescePhase : G.interferenceGraph -> G.worklists -> G.worklists              G.node list (* defs *)
    val freezePhase   : G.interferenceGraph -> G.worklists -> G.worklists  
    val wklFromFrozen : int * G.node -> G.node list  
   
       (* Return a list of spill nodes *)  
    val optimisticSpilling : G.interferenceGraph -> G.worklists -> G.node list  
   
       (* simplify/coalesce/freeze *)  
    val simplifyCoalesceFreeze : G.interferenceGraph -> G.worklists -> G.worklists  
36    
37        (* Update the regmap to be consistent with the node set,     (*
38         * after register allocation or copy propagation      * Update regmap after finishing register allocation or copy propagation
39         *)         *)
40     val finishRA : G.interferenceGraph -> unit     val finishRA : G.interferenceGraph -> unit
41     val finishCP : G.interferenceGraph -> unit     val finishCP : G.interferenceGraph -> unit
 end  
42    
43       (*
44        * Create an initial set of worklists from a new interference graph
45        * and a list of moves
46        *)
47       val initWorkLists : G.interferenceGraph ->
48              { moves : G.move list,
49                deadCopyElim : bool
50              } ->
51              { simplifyWkl : G.node list,
52                moveWkl     : move_queue,
53                freezeWkl   : freeze_queue,
54                spillWkl    : G.node list   (* high degreee nodes *)
55              }
56    
57       (*
58        * Clear the interference graph but keep the nodes table intact
59        *)
60       val clearGraph : G.interferenceGraph -> unit
61    
62       (*
63        * Remove all adjacency lists from the nodes table
64        *)
65       val clearNodes : G.interferenceGraph -> unit
66    
67       (*
68        * Return a regmap function that reflects the current interference graph.
69        * Spilled registers are given the special value ~1
70        *)
71       val regmap      : G.interferenceGraph -> (int -> int)
72       val spillRegmap : G.interferenceGraph -> (int -> int)
73       val spillLoc    : G.interferenceGraph -> (int -> int)
74    
75       (*
76        * Simplify, Coalease and Freeze until the work list is done
77        *)
78       val iteratedCoalescing :
79            G.interferenceGraph ->
80               { simplifyWkl : G.node list,
81                 moveWkl     : move_queue,
82                 freezeWkl   : freeze_queue,
83                 stack       : G.node list
84               } ->
85               { stack : G.node list
86               }
87    
88       (*
89        * potentially spill a node.
90        *)
91       val potentialSpillNode :
92            G.interferenceGraph ->
93               { node  : G.node,
94                 stack : G.node list
95               } ->
96               { moveWkl   : move_queue,
97                 freezeWkl : freeze_queue,
98                 stack     : G.node list
99               }
100    
101       (*
102        * Color nodes on the stack, using Briggs' optimistic spilling.
103        * Return a list of actual spills
104        *)
105       val select :
106            G.interferenceGraph ->
107               { biased : bool, (* use biased coloring too? *)
108                 stack  : G.node list
109               } ->
110               { spills : G.node list (* actual spills *)
111               }
112    
113       (*
114        * Spill coalescing
115        *)
116        val spillCoalescing : G.interferenceGraph -> G.node list -> unit
117    
118       (*
119        * Spill coloring
120        *)
121        val spillColoring : G.interferenceGraph -> G.node list -> unit
122    
123    end

Legend:
Removed from v.428  
changed lines
  Added in v.469

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