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

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

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

sml/trunk/src/MLRISC/ra/ra-graph.sig revision 427, Wed Sep 8 09:40:08 1999 UTC sml/branches/SMLNJ/src/MLRISC/ra/ra-graph.sig revision 498, Tue Dec 7 15:44:50 1999 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
# Line 18  Line 11 
11     * The following are the data structures used in the register allocator.     * The following are the data structures used in the register allocator.
12     *)     *)
13    
14    structure BM : BITMATRIX    (* A new bit matrix datatype.
15       * We use the small representation whenever possible to save space.
16       *)
17      datatype bitMatrix = BM of {table:hashTable,
18                                  elems:int ref,
19                                  edges:int}
20      and hashTable = SMALL of word list Array.array ref * word
21                    | LARGE of bucket Array.array ref * word
22                 (* | BITMATRIX of Word8Array.array *)
23      and bucket = NIL | B of int * int * bucket
24    
25    exception Nodes    exception Nodes
26    
27      type priority = int
28      type cost = int
29    
30      (*
31       * The following represent a program point in the program.
32       *
33       * The last instruction in the block is numbered 1, i.e. the instruction
34       * numbering is in reverse.  The number 0 is reserved for "live-out".
35       *
36       *)
37      type programPoint = int
38    
39      type mode = word
40    
41    datatype interferenceGraph =    datatype interferenceGraph =
42     GRAPH of { bitMatrix    : BM.bitMatrix,       GRAPH of
43         { bitMatrix    : bitMatrix ref,
44                nodes        : node Intmap.intmap,                nodes        : node Intmap.intmap,
45                regmap       : int Intmap.intmap,                regmap       : int Intmap.intmap,
46                K            : int,                K            : int,
47                firstPseudoR : int,                firstPseudoR : int,
48                getreg       :         dedicated    : bool Array.array,
49                   {pref:int list,stamp:int,proh:int Array.array} -> int,         getreg       : {pref:int list, stamp:int, proh:int Array.array} -> int,
50           getpair      : {pref:int list, stamp:int, proh:int Array.array} -> int,
51                proh         : int Array.array,                proh         : int Array.array,
52                stamp        : int ref,                stamp        : int ref,
53    
54               (* Info to undo a spill when an optimistic spill has occurred *)               (* Info to undo a spill when an optimistic spill has occurred *)
55                spillFlag    : bool ref,                spillFlag    : bool ref,
56                undoInfo     : (node * moveStatus ref) list ref  
57           spilledRegs  : bool Intmap.intmap, (*registers that have been spilled*)
58           trail        : trailInfo ref,
59    
60           (* how to pretty print a register *)
61           showReg      : int -> string,
62    
63           (* how many registers there are? *)
64           numRegs      : int,
65           maxRegs      : unit -> int,
66    
67           (* dead copies *)
68           deadCopies   : int list ref,
69           copyTmps     : node list ref,
70           memMoves     : move list ref,
71           memRegs      : node list ref,
72    
73           (* spill locations *)
74           spillLoc     : int ref,
75    
76           (* span indexed by node id *)
77           span         : int Intmap.intmap,
78    
79           (* mode *)
80           mode         : mode,
81    
82           pseudoCount  : int ref,
83           blockedCount : int ref
84              }              }
85    
86    and moveStatus = MOVE | COALESCED | CONSTRAINED | LOST | WORKLIST    and moveStatus = BRIGGS_MOVE             (* not yet coalesceable *)
87                     | GEORGE_MOVE             (* not yet coalesceable *)
88                     | COALESCED               (* coalesced *)
89                     | CONSTRAINED             (* src and target intefere *)
90                     | LOST                    (* frozen moves *)
91                     | WORKLIST                (* on the move worklist *)
92    
93    and move =    and move =
94      MV of {src : node,                  (* source register of move *)      MV of {src : node,                  (* source register of move *)
95             dst : node,                  (* destination register of move *)             dst : node,                  (* destination register of move *)
96             status : moveStatus ref      (* coalesced? *)             (*kind   : moveKind, *)      (* kind of move *)
97               cost   : cost,               (* cost *)
98               status : moveStatus ref,     (* coalesced? *)
99               hicount: int ref             (* neighbors of high degree *)
100            }            }
101    
102    and nodeStatus = REMOVED | PSEUDO | ALIASED of node | COLORED of int    and moveKind = REG_TO_REG      (* register to register *)
103                   | EVEN_TO_REG     (* even register in pair to register *)
104                   | ODD_TO_REG      (* odd register in pair to register *)
105                   | PAIR_TO_PAIR    (* register pair to register pair *)
106                   | REG_TO_EVEN     (* register to even register in pair *)
107                   | REG_TO_ODD      (* register to odd register in pair *)
108    
109      and nodeStatus =
110            PSEUDO                (* pseudo register *)
111          | REMOVED               (* removed from the interference graph *)
112          | ALIASED of node       (* coalesced *)
113          | COLORED of int        (* colored *)
114          | SPILLED of int        (* spilled *)
115    
116           (* Note on SPILLED:
117            *  SPILLED ~1 means that the spill location is still undetermined
118            *  SPILLED c, c >= 0 means that c is a fixed "memory register"
119            *  SPILLED c, c < ~1 means that c is a logical spill location
120            *                    assigned by the register allocator
121            *)
122    
123    and node =    and node =
124      NODE of { number : int,             (* node number *)      NODE of { number : int,             (* node number *)
# Line 53  Line 126 
126                movelist: move list ref,  (* moves associated with this node *)                movelist: move list ref,  (* moves associated with this node *)
127                degree : int ref,         (* current degree *)                degree : int ref,         (* current degree *)
128                color : nodeStatus ref,   (* status *)                color : nodeStatus ref,   (* status *)
129                adj : node list ref       (* adjacency list *)                adj : node list ref,      (* adjacency list *)
130                  pri : priority ref,       (* priority *)
131                  movecost : cost ref,      (* move cost *)
132                  (* pair : bool, *)        (* register pair? *)
133                  defs : programPoint list ref,
134                  uses : programPoint list ref
135              }              }
   (*  
    * 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.  
    *)  
136    
137     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 *)  
       }  
138    
139     type worklists = (nodelist,movelist,nodelist,nodelist,nodelist) lists    (* Create a new bitMatrix *)
140      val newBitMatrix : {edges : int, maxRegs : int} -> bitMatrix
141    
142     (* Create a new interference graph *)     (* Create a new interference graph *)
143     val newGraph : {nodes        : node Intmap.intmap,     val newGraph : {nodes        : node Intmap.intmap,
144                     regmap       : int Intmap.intmap,                     regmap       : int Intmap.intmap,
145                     numRegs      : int,                     numRegs      : int,
146                       maxRegs      : unit -> int,
147                     K            : int,                     K            : int,
148                     firstPseudoR : int,                     firstPseudoR : int,
149                       dedicated    : bool Array.array,
150                       showReg      : int -> string,
151                     getreg       :                     getreg       :
152                        {pref:int list,stamp:int,proh:int Array.array} -> int                       {pref:int list,stamp:int,proh:int Array.array} -> int,
153                       getpair      :
154                         {pref:int list,stamp:int,proh:int Array.array} -> int,
155                       proh         : int Array.array,
156                       mode         : mode,
157                       spillLoc     : int ref,
158                       firstMemReg  : int,
159                       numMemRegs   : int
160                    } -> interferenceGraph                    } -> interferenceGraph
161    
162  end  end
   

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

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