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 475, Wed Nov 10 22:59:58 1999 UTC sml/trunk/src/MLRISC/ra/ra-graph.sig revision 1009, Wed Jan 9 19:44:22 2002 UTC
# Line 7  Line 7 
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     *)     *)
# Line 29  Line 31 
31    
32    (*    (*
33     * The following represent a program point in the program.     * The following represent a program point in the program.
    * As a convention, program point is computed by  
    *  
    *    block number * 16384 + instruction number  
34     *     *
35     * The last instruction in the block is numbered 1, i.e. the instruction     * 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".     * numbering is in reverse.  The number 0 is reserved for "live-out".
37     *     *
    * This implies that there can be a maximum of 16k-1 instructions  
    * per basic block/hyperblock, plus a maximum of 32k blocks.  
    * Let's hope this is enough. (I'm not kidding, aggressive inlining  
    * and unrolling can produce large blocks.)  
38     *)     *)
39    type programPoint = int    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       GRAPH of
60       { bitMatrix    : bitMatrix ref,       { bitMatrix    : bitMatrix ref,
61         nodes        : node Intmap.intmap,         nodes        : node IntHashTable.hash_table,
        regmap       : int Intmap.intmap,  
62         K            : int,         K            : int,
63         firstPseudoR : int,         firstPseudoR : int,
64         dedicated    : bool Array.array,         dedicated    : int -> bool,
65         getreg       : {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,         getpair      : {pref:int list, stamp:int, proh:int Array.array} -> int,
67         proh         : int Array.array,         proh         : int Array.array,
# Line 59  Line 70 
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    
73         spilledRegs  : bool Intmap.intmap, (*registers that have been spilled*)         spilledRegs  : bool IntHashTable.hash_table,
74                               (*registers that have been spilled*)
75         trail        : trailInfo ref,         trail        : trailInfo ref,
76    
77         (* how to pretty print a register *)         (* how to pretty print a register *)
78         showReg      : int -> string,         showReg      : C.cell -> string,
79    
80         (* how many registers there are? *)         (* how many registers there are? *)
81         numRegs      : int,         numRegs      : int,
82         maxRegs      : unit -> int,         maxRegs      : unit -> int,
83    
84         (* dead copies *)         (* dead copies *)
85         deadCopies   : int list ref,         deadCopies   : C.cell list ref,
86           copyTmps     : node list ref,
87           memMoves     : move list ref,
88           memRegs      : node list ref,
89    
90         (* spill locations *)         (* spill locations *)
91         spillLoc     : int ref         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         (* not yet coalesced *)    and moveStatus = BRIGGS_MOVE             (* not yet coalesceable *)
104                     | GEORGE_MOVE             (* not yet coalesceable *)
105                   | COALESCED    (* coalesced *)                   | COALESCED    (* coalesced *)
106                   | CONSTRAINED  (* src and target intefere *)                   | CONSTRAINED  (* src and target intefere *)
107                   | LOST         (* frozen moves *)                   | LOST         (* frozen moves *)
# Line 85  Line 110 
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             (*kind   : moveKind, *)      (* kind of move *)  (*           kind   : moveKind,           (* kind of move *) *)
114             cost   : cost,               (* cost *)             cost   : cost,               (* cost *)
115             status : moveStatus ref      (* coalesced? *)             status : moveStatus ref,     (* coalesced? *)
116               hicount: int ref             (* neighbors of high degree *)
117            }            }
118    
119    and moveKind = REG_TO_REG      (* register to register *)    and moveKind = REG_TO_REG      (* register to register *)
# Line 96  Line 122 
122                 | PAIR_TO_PAIR    (* register pair to register pair *)                 | PAIR_TO_PAIR    (* register pair to register pair *)
123                 | REG_TO_EVEN     (* register to even register in pair *)                 | REG_TO_EVEN     (* register to even register in pair *)
124                 | REG_TO_ODD      (* register to odd register in pair *)                 | 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 =    and nodeStatus =
131          PSEUDO                (* pseudo register *)          PSEUDO                (* pseudo register *)
132        | REMOVED               (* removed from the interference graph *)        | REMOVED               (* removed from the interference graph *)
133        | ALIASED of node       (* coalesced *)        | ALIASED of node       (* coalesced *)
134        | COLORED of int        (* colored *)        | COLORED of int        (* colored *)
135        | SPILLED of int        (* spilled *)        | 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 *)
# Line 124  Line 164 
164    val newBitMatrix : {edges : int, maxRegs : int} -> bitMatrix    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,                     maxRegs      : unit -> int,
170                     K            : int,                     K            : int,
171                     firstPseudoR : int,                     firstPseudoR : int,
172                     dedicated    : bool Array.array,                     dedicated    : int -> bool,
173                     showReg      : int -> string,                     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      :                     getpair      :
177                       {pref:int list,stamp:int,proh:int Array.array} -> int,                       {pref:int list,stamp:int,proh:int Array.array} -> int,
178                     proh         : int Array.array                     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.475  
changed lines
  Added in v.1009

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