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/branches/SMLNJ/src/MLRISC/ra/ra-graph.sml
ViewVC logotype

Diff of /sml/branches/SMLNJ/src/MLRISC/ra/ra-graph.sml

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

revision 468, Wed Nov 10 22:42:52 1999 UTC revision 469, Wed Nov 10 22:42:52 1999 UTC
# Line 1  Line 1 
1  (*  (*
2   * Graph data structure used by the modular register allocator.   * This is the new interference graph used by the new register allocator.
3   *   *
4   * -- Allen   * -- Allen
5   *)   *)
# Line 7  Line 7 
7  structure RAGraph : RA_GRAPH =  structure RAGraph : RA_GRAPH =
8  struct  struct
9    
10    structure BM = TriangularBitMatrix    (* A new bit matrix datatype.
11       * We use the small representation whenever possible to save space.
12       *)
13      datatype bitMatrix = BM of {table:hashTable,
14                                  elems:int ref,
15                                  edges:int}
16      and hashTable = SMALL of word list Array.array ref * word
17                    | LARGE of bucket Array.array ref * word
18                 (* | BITMATRIX of Word8Array.array *)
19      and bucket = NIL | B of int * int * bucket
20    
21      type priority = int
22    
23      type programPoint = int
24    
25      type cost = int
26    
27    datatype interferenceGraph =    datatype interferenceGraph =
28     GRAPH of { bitMatrix    : BM.bitMatrix,     GRAPH of { bitMatrix    : bitMatrix ref,
29                nodes        : node Intmap.intmap,                nodes        : node Intmap.intmap,
30                regmap       : int Intmap.intmap,                regmap       : int Intmap.intmap,
31                K            : int,                K            : int,
32                firstPseudoR : int,                firstPseudoR : int,
33                  dedicated    : bool Array.array,
34                getreg       :                getreg       :
35                   {pref:int list,stamp:int,proh:int Array.array} -> int,                   {pref:int list,stamp:int,proh:int Array.array} -> int,
36                  getpair       :
37                      {pref:int list, stamp:int, proh:int Array.array} -> int,
38                proh         : int Array.array,                proh         : int Array.array,
39                stamp        : int ref,                stamp        : int ref,
40    
41               (* Info to undo a spill when an optimistic spill has occurred *)               (* Info to undo a spill when an optimistic spill has occurred *)
42                spillFlag    : bool ref,                spillFlag    : bool ref,
43                undoInfo     : (node * moveStatus ref) list ref                spilledRegs  : bool Intmap.intmap,
44                  trail        : trailInfo ref,
45    
46                  showReg      : int -> string,
47                  numRegs      : int,
48                  maxRegs      : unit -> int,
49    
50                  deadCopies   : int list ref,
51                  spillLoc     : int ref
52              }              }
53    
54    and moveStatus = MOVE | COALESCED | CONSTRAINED | LOST | WORKLIST    and moveStatus = MOVE | COALESCED | CONSTRAINED | LOST | WORKLIST
# Line 29  Line 56 
56    and move =    and move =
57      MV of {src : node,                  (* source register of move *)      MV of {src : node,                  (* source register of move *)
58             dst : node,                  (* destination register of move *)             dst : node,                  (* destination register of move *)
59               (* kind: moveKind, *)        (* what kind of move *)
60               cost : cost,                 (* cost *)
61             status : moveStatus ref      (* coalesced? *)             status : moveStatus ref      (* coalesced? *)
62            }            }
63    
64    and nodeStatus = REMOVED | PSEUDO | ALIASED of node | COLORED of int    and moveKind = REG_TO_REG      (* register to register *)
65                   | EVEN_TO_REG     (* even register in pair to register *)
66                   | ODD_TO_REG      (* odd register in pair to register *)
67                   | PAIR_TO_PAIR    (* register pair to register pair *)
68                   | REG_TO_EVEN     (* register to even register in pair *)
69                   | REG_TO_ODD      (* register to odd register in pair *)
70    
71      and nodeStatus =
72            PSEUDO                (* pseudo register *)
73          | REMOVED               (* removed from the interference graph *)
74          | ALIASED of node       (* coalesced *)
75          | COLORED of int        (* colored *)
76          | SPILLED of int        (* spilled *)
77          | ALIASED_SPILL of node (* aliased spill node *)
78    
79    and node =    and node =
80      NODE of { number : int,             (* node number *)      NODE of { number : int,             (* node number *)
# Line 40  Line 82 
82                movelist: move list ref,  (* moves associated with this node *)                movelist: move list ref,  (* moves associated with this node *)
83                degree : int ref,         (* current degree *)                degree : int ref,         (* current degree *)
84                color : nodeStatus ref,   (* status *)                color : nodeStatus ref,   (* status *)
85                adj : node list ref       (* adjacency list *)                adj : node list ref,      (* adjacency list *)
86              }                pri : priority ref,       (* priority *)
87    (*                movecost : cost ref,      (* move cost *)
88     * The valid transitions for a node are:                (* pair : bool, *)        (* register pair? *)
89     * PSEUDO -> REMOVED                  % during simplify                defs : programPoint list ref,
90     * PSEUDO -> ALIASED(n)               % during coalescing                uses : programPoint list ref
    * REMOVED -> COLORED(r)              % assigning a color  
    *  
    *  ... all others are illegal.  
    *)  
   
    type 'a worklist = 'a list  
    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 *)  
91        }        }
92    
93     type worklists = (nodelist,movelist,nodelist,nodelist,nodelist) lists    and trailInfo = END | UNDO of node * moveStatus ref * trailInfo
94    
95    exception Nodes    exception Nodes
96    
97      fun error msg = MLRiscErrorMsg.error("RAGraph", msg)
98    
99      val stampCounter = ref 0
100    
101      (* Create a new bitMatrix *)
102      fun roundSize size =
103      let fun f(x, shift) =
104            if x >= size then (x, Word.>>(shift, 0w1))
105            else f(x+x, shift+0w1)
106      in f(64, 0w6) end
107    
108      val max = Word.<<(0w1,Word.>>(Word.fromInt Word.wordSize,0w1))
109      val _ = if max < Word.<<(0w1,0w15)
110              then error "word size too small" else ()
111    
112      fun newBitMatrix{edges, maxRegs} =
113      let val table =
114            (* if maxRegs < 1024 then
115              let val denseBytes  = (maxRegs * (maxRegs + 1) + 15) div 16
116              in  BITMATRIX(Word8Array.array(denseBytes,0w0))
117              end
118              else *)
119              let val (tableSize, shift) = roundSize edges
120              in  if Word.fromInt maxRegs < max then
121                     SMALL(ref(Array.array(tableSize,[])),shift)
122                  else
123                     LARGE(ref(Array.array(tableSize,NIL)),shift)
124              end
125      in  BM{table=table, elems=ref 0, edges=edges}
126      end
127    
128    (* Create a new interference graph *)    (* Create a new interference graph *)
129    fun newGraph{nodes,regmap,K,firstPseudoR,getreg,numRegs} =    fun newGraph{nodes,regmap,K,firstPseudoR,dedicated,
130                   getreg,getpair,showReg,maxRegs,numRegs,proh} =
131    let (* lower triangular bitmatrix primitives *)    let (* lower triangular bitmatrix primitives *)
132        (* NOTE: The average ratio of E/N is about 16 *)        (* NOTE: The average ratio of E/N is about 16 *)
133        val bitMatrix = BM.new numRegs        val bitMatrix = newBitMatrix{edges=numRegs * 16,maxRegs=maxRegs()}
134    in  GRAPH{ bitMatrix    = bitMatrix,    in  if !stampCounter > 10000000 then stampCounter := 0 else ();
135          GRAPH{ bitMatrix    = ref bitMatrix,
136               nodes        = nodes,               nodes        = nodes,
137               regmap       = regmap,               regmap       = regmap,
138               K            = K,               K            = K,
139               firstPseudoR = firstPseudoR,               firstPseudoR = firstPseudoR,
140                 dedicated    = dedicated,
141               getreg       = getreg,               getreg       = getreg,
142               proh         = Array.array(firstPseudoR,~1),               getpair      = getpair,
143               stamp        = ref 0,               proh         = proh,
144                 stamp        = stampCounter,
145               spillFlag    = ref false,               spillFlag    = ref false,
146               undoInfo     = ref []               spilledRegs  = Intmap.new(2,Nodes),
147                 trail        = ref END,
148                 showReg      = Int.toString,
149                 numRegs      = numRegs,
150                 maxRegs      = maxRegs,
151                 deadCopies   = ref [],
152                 spillLoc     = ref ~2
153             }             }
154    end    end
155    
156  end  end
   

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

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