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

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   * 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       * As a convention, program point is computed by
33       *
34       *    block number * 16384 + instruction number
35       *
36       * The last instruction in the block is numbered 1, i.e. the instruction
37       * numbering is in reverse.  The number 0 is reserved for "live-out".
38       *
39       * This implies that there can be a maximum of 16k-1 instructions
40       * per basic block/hyperblock, plus a maximum of 32k blocks.
41       * Let's hope this is enough. (I'm not kidding, aggressive inlining
42       * and unrolling can produce large blocks.)
43       *)
44      type programPoint = int
45    
46    datatype interferenceGraph =    datatype interferenceGraph =
47     GRAPH of { bitMatrix    : BM.bitMatrix,       GRAPH of
48         { bitMatrix    : bitMatrix ref,
49                nodes        : node Intmap.intmap,                nodes        : node Intmap.intmap,
50                regmap       : int Intmap.intmap,                regmap       : int Intmap.intmap,
51                K            : int,                K            : int,
52                firstPseudoR : int,                firstPseudoR : int,
53                getreg       :         dedicated    : bool Array.array,
54                   {pref:int list,stamp:int,proh:int Array.array} -> int,         getreg       : {pref:int list, stamp:int, proh:int Array.array} -> int,
55           getpair      : {pref:int list, stamp:int, proh:int Array.array} -> int,
56                proh         : int Array.array,                proh         : int Array.array,
57                stamp        : int ref,                stamp        : int ref,
58    
59               (* Info to undo a spill when an optimistic spill has occurred *)               (* Info to undo a spill when an optimistic spill has occurred *)
60                spillFlag    : bool ref,                spillFlag    : bool ref,
61                undoInfo     : (node * moveStatus ref) list ref  
62           spilledRegs  : bool Intmap.intmap, (*registers that have been spilled*)
63           trail        : trailInfo ref,
64    
65           (* how to pretty print a register *)
66           showReg      : int -> string,
67    
68           (* how many registers there are? *)
69           numRegs      : int,
70           maxRegs      : unit -> int,
71    
72           (* dead copies *)
73           deadCopies   : int list ref,
74    
75           (* spill locations *)
76           spillLoc     : int ref
77              }              }
78    
79    and moveStatus = MOVE | COALESCED | CONSTRAINED | LOST | WORKLIST    and moveStatus = MOVE         (* not yet coalesced *)
80                     | COALESCED    (* coalesced *)
81                     | CONSTRAINED  (* src and target intefere *)
82                     | LOST         (* frozen moves *)
83                     | WORKLIST     (* on the move worklist *)
84    
85    and move =    and move =
86      MV of {src : node,                  (* source register of move *)      MV of {src : node,                  (* source register of move *)
87             dst : node,                  (* destination register of move *)             dst : node,                  (* destination register of move *)
88               (*kind   : moveKind, *)      (* kind of move *)
89               cost   : cost,               (* cost *)
90             status : moveStatus ref      (* coalesced? *)             status : moveStatus ref      (* coalesced? *)
91            }            }
92    
93    and nodeStatus = REMOVED | PSEUDO | ALIASED of node | COLORED of int    and moveKind = REG_TO_REG      (* register to register *)
94                   | EVEN_TO_REG     (* even register in pair to register *)
95                   | ODD_TO_REG      (* odd register in pair to register *)
96                   | PAIR_TO_PAIR    (* register pair to register pair *)
97                   | REG_TO_EVEN     (* register to even register in pair *)
98                   | REG_TO_ODD      (* register to odd register in pair *)
99    
100      and nodeStatus =
101            PSEUDO                (* pseudo register *)
102          | REMOVED               (* removed from the interference graph *)
103          | ALIASED of node       (* coalesced *)
104          | COLORED of int        (* colored *)
105          | SPILLED of int        (* spilled *)
106          | ALIASED_SPILL of node (* aliased spill node *)
107    
108    and node =    and node =
109      NODE of { number : int,             (* node number *)      NODE of { number : int,             (* node number *)
# Line 53  Line 111 
111                movelist: move list ref,  (* moves associated with this node *)                movelist: move list ref,  (* moves associated with this node *)
112                degree : int ref,         (* current degree *)                degree : int ref,         (* current degree *)
113                color : nodeStatus ref,   (* status *)                color : nodeStatus ref,   (* status *)
114                adj : node list ref       (* adjacency list *)                adj : node list ref,      (* adjacency list *)
115                  pri : priority ref,       (* priority *)
116                  movecost : cost ref,      (* move cost *)
117                  (* pair : bool, *)        (* register pair? *)
118                  defs : programPoint list ref,
119                  uses : programPoint list ref
120              }              }
   (*  
    * 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.  
    *)  
121    
122     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 *)  
       }  
123    
124     type worklists = (nodelist,movelist,nodelist,nodelist,nodelist) lists    (* Create a new bitMatrix *)
125      val newBitMatrix : {edges : int, maxRegs : int} -> bitMatrix
126    
127     (* Create a new interference graph *)     (* Create a new interference graph *)
128     val newGraph : {nodes        : node Intmap.intmap,     val newGraph : {nodes        : node Intmap.intmap,
129                     regmap       : int Intmap.intmap,                     regmap       : int Intmap.intmap,
130                     numRegs      : int,                     numRegs      : int,
131                       maxRegs      : unit -> int,
132                     K            : int,                     K            : int,
133                     firstPseudoR : int,                     firstPseudoR : int,
134                       dedicated    : bool Array.array,
135                       showReg      : int -> string,
136                     getreg       :                     getreg       :
137                        {pref:int list,stamp:int,proh:int Array.array} -> int                       {pref:int list,stamp:int,proh:int Array.array} -> int,
138                       getpair      :
139                         {pref:int list,stamp:int,proh:int Array.array} -> int,
140                       proh         : int Array.array
141                    } -> interferenceGraph                    } -> interferenceGraph
142    
143  end  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