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 /MLRISC/trunk/ra/ra-graph.sig
ViewVC logotype

Diff of /MLRISC/trunk/ra/ra-graph.sig

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

sml/branches/SMLNJ/src/MLRISC/ra/ra-graph.sig revision 428, Wed Sep 8 09:47:00 1999 UTC sml/trunk/src/MLRISC/ra/ra-graph.sig revision 1009, Wed Jan 9 19:44:22 2002 UTC
# Line 1  Line 1 
1  (** Graph coloring register allocation.  (*
2   ** Implements the 'iterated register coalescing' scheme described   * This is the new interference graph used by the new register allocator.
3   ** in POPL'96, and TOPLAS v18 #3, pp 325-353.   *
4   **   * -- Allen
5   ** RA CORE defines the core of the register allocator.   *)
  ** This basically means the enableMove, coalesce, simplify and freeze phases.  
  ** These are separated out from the rest for more modularity  
  ** and customizability.  
  **  
  ** -- Allen  
  **)  
   
6    
7  signature RA_GRAPH =  signature RA_GRAPH =
8  sig  sig
9    
10       structure C : CELLS_BASIS
11    
12    (*    (*
13     * The following are the data structures used in the register allocator.     * The following are the data structures used in the register allocator.
14     *)     *)
15    
16    structure BM : BITMATRIX    (* A new bit matrix datatype.
17       * We use the small representation whenever possible to save space.
18       *)
19      datatype bitMatrix = BM of {table:hashTable,
20                                  elems:int ref,
21                                  edges:int}
22      and hashTable = SMALL of word list Array.array ref * word
23                    | LARGE of bucket Array.array ref * word
24                 (* | BITMATRIX of Word8Array.array *)
25      and bucket = NIL | B of int * int * bucket
26    
27    exception Nodes    exception Nodes
28    
29      type priority = int
30      type cost = int
31    
32      (*
33       * The following represent a program point in the program.
34       *
35       * The last instruction in the block is numbered 1, i.e. the instruction
36       * numbering is in reverse.  The number 0 is reserved for "live-out".
37       *
38       *)
39      type programPoint = {block:int, insn:int}
40    
41      (* Hash table indexed by program point *)
42      structure PPtHashTable : MONO_HASH_TABLE
43          where type Key.hash_key = programPoint
44    
45      type frame_offset = int
46      type logical_spill_id = int
47    
48      datatype spillLoc =
49         FRAME   of logical_spill_id  (* spill to a new frame location *)
50       | MEM_REG of C.cell            (* spill to a memory register *)
51    
52      (* Hash table indexed by spill location *)
53      structure SpillLocHashTable : MONO_HASH_TABLE
54          where type Key.hash_key = spillLoc
55    
56      type mode = word
57    
58    datatype interferenceGraph =    datatype interferenceGraph =
59     GRAPH of { bitMatrix    : BM.bitMatrix,       GRAPH of
60                nodes        : node Intmap.intmap,       { bitMatrix    : bitMatrix ref,
61                regmap       : int Intmap.intmap,         nodes        : node IntHashTable.hash_table,
62                K            : int,                K            : int,
63                firstPseudoR : int,                firstPseudoR : int,
64                getreg       :         dedicated    : int -> bool,
65                   {pref:int list,stamp:int,proh:int Array.array} -> int,         getreg       : {pref:int list, stamp:int, proh:int Array.array} -> int,
66           getpair      : {pref:int list, stamp:int, proh:int Array.array} -> int,
67                proh         : int Array.array,                proh         : int Array.array,
68                stamp        : int ref,                stamp        : int ref,
69    
70               (* Info to undo a spill when an optimistic spill has occurred *)               (* Info to undo a spill when an optimistic spill has occurred *)
71                spillFlag    : bool ref,                spillFlag    : bool ref,
72                undoInfo     : (node * moveStatus ref) list ref  
73           spilledRegs  : bool IntHashTable.hash_table,
74                               (*registers that have been spilled*)
75           trail        : trailInfo ref,
76    
77           (* how to pretty print a register *)
78           showReg      : C.cell -> string,
79    
80           (* how many registers there are? *)
81           numRegs      : int,
82           maxRegs      : unit -> int,
83    
84           (* dead copies *)
85           deadCopies   : C.cell list ref,
86           copyTmps     : node list ref,
87           memMoves     : move list ref,
88           memRegs      : node list ref,
89    
90           (* spill locations *)
91           spillLoc     : int ref,
92    
93           (* span indexed by node id *)
94           span         : int IntHashTable.hash_table option ref,
95    
96           (* mode *)
97           mode         : mode,
98    
99           pseudoCount  : int ref,
100           blockedCount : int ref
101              }              }
102    
103    and moveStatus = MOVE | COALESCED | CONSTRAINED | LOST | WORKLIST    and moveStatus = BRIGGS_MOVE             (* not yet coalesceable *)
104                     | GEORGE_MOVE             (* not yet coalesceable *)
105                     | COALESCED               (* coalesced *)
106                     | CONSTRAINED             (* src and target intefere *)
107                     | LOST                    (* frozen moves *)
108                     | WORKLIST                (* on the move worklist *)
109    
110    and move =    and move =
111      MV of {src : node,                  (* source register of move *)      MV of {src : node,                  (* source register of move *)
112             dst : node,                  (* destination register of move *)             dst : node,                  (* destination register of move *)
113             status : moveStatus ref      (* coalesced? *)  (*           kind   : moveKind,           (* kind of move *) *)
114               cost   : cost,               (* cost *)
115               status : moveStatus ref,     (* coalesced? *)
116               hicount: int ref             (* neighbors of high degree *)
117            }            }
118    
119    and nodeStatus = REMOVED | PSEUDO | ALIASED of node | COLORED of int    and moveKind = REG_TO_REG      (* register to register *)
120                   | EVEN_TO_REG     (* even register in pair to register *)
121                   | ODD_TO_REG      (* odd register in pair to register *)
122                   | PAIR_TO_PAIR    (* register pair to register pair *)
123                   | REG_TO_EVEN     (* register to even register in pair *)
124                   | REG_TO_ODD      (* register to odd register in pair *)
125    (*  and moveKind = REGmvk                (* register-register move *)
126                   | MEMREGmvk       (* move involving memReg  *)
127    
128    *)
129    
130      and nodeStatus =
131            PSEUDO                (* pseudo register *)
132          | REMOVED               (* removed from the interference graph *)
133          | ALIASED of node       (* coalesced *)
134          | COLORED of int        (* colored *)
135          | MEMREG of int * C.cell(* register implemented in memory *)
136          | SPILLED               (* spilled *)
137          | SPILL_LOC of int      (* spilled at logical location *)
138    
139           (* Note on SPILLED:
140            *  SPILLED ~1 means that the spill location is still undetermined
141            *  SPILLED c, c >= 0 means that c is a fixed "memory register"
142            *  SPILLED c, c < ~1 means that c is a logical spill location
143            *                    assigned by the register allocator
144            *)
145    
146    and node =    and node =
147      NODE of { number : int,             (* node number *)      NODE of { number : int,             (* node number *)
148                  cell:    C.cell,
149                movecnt: int ref,         (* #moves this node is involved in *)                movecnt: int ref,         (* #moves this node is involved in *)
150                movelist: move list ref,  (* moves associated with this node *)                movelist: move list ref,  (* moves associated with this node *)
151                degree : int ref,         (* current degree *)                degree : int ref,         (* current degree *)
152                color : nodeStatus ref,   (* status *)                color : nodeStatus ref,   (* status *)
153                adj : node list ref       (* adjacency list *)                adj : node list ref,      (* adjacency list *)
154                  pri : priority ref,       (* priority *)
155                  movecost : cost ref,      (* move cost *)
156                  (* pair : bool, *)        (* register pair? *)
157                  defs : programPoint list ref,
158                  uses : programPoint list ref
159              }              }
   (*  
    * The valid transitions for a node are:  
    * PSEUDO -> REMOVED                  % during simplify  
    * PSEUDO -> ALIASED(n)               % during coalescing  
    * REMOVED -> COLORED(r)              % assigning a color  
    *  
    *  ... all others are illegal.  
    *)  
160    
161     type 'a worklist = 'a list    and trailInfo = END | UNDO of node * moveStatus ref * trailInfo
    type nodelist    = node worklist  
    type movelist    = move worklist  
   
    type ('sim,'move,'freeze,'spill,'stack) lists =  
       {simplifyWkl: 'sim,   (* nodes that can be simplified *)  
        moveWkl : 'move,     (* moves to be considered for coalescing *)  
        freezeWkl : 'freeze, (* all n, s.t. degree(n)<K and moveRelated(n) *)  
        spillWkl : 'spill,   (* all n, s.t. degree(n)>=K  *)  
        stack : 'stack       (* nodes removed from the graph *)  
       }  
162    
163     type worklists = (nodelist,movelist,nodelist,nodelist,nodelist) lists    (* Create a new bitMatrix *)
164      val newBitMatrix : {edges : int, maxRegs : int} -> bitMatrix
165    
166     (* Create a new interference graph *)     (* Create a new interference graph *)
167     val newGraph : {nodes        : node Intmap.intmap,    val newGraph : { nodes        : node IntHashTable.hash_table,
                    regmap       : int Intmap.intmap,  
168                     numRegs      : int,                     numRegs      : int,
169                       maxRegs      : unit -> int,
170                     K            : int,                     K            : int,
171                     firstPseudoR : int,                     firstPseudoR : int,
172                       dedicated    : int -> bool,
173                       showReg      : C.cell -> string,
174                     getreg       :                     getreg       :
175                        {pref:int list,stamp:int,proh:int Array.array} -> int                       {pref:int list,stamp:int,proh:int Array.array} -> int,
176                       getpair      :
177                         {pref:int list,stamp:int,proh:int Array.array} -> int,
178                       proh         : int Array.array,
179                       mode         : mode,
180                       spillLoc     : int ref,
181                       memRegs      : C.cell list
182                    } -> interferenceGraph                    } -> interferenceGraph
183    
184  end  end
   

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

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