Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /MLRISC/trunk/ra/ra-graph.sig
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 427 - (view) (download) (as text)
Original Path: sml/trunk/src/MLRISC/ra/ra-graph.sig

1 : monnier 427 (** Graph coloring register allocation.
2 :     ** Implements the 'iterated register coalescing' scheme described
3 :     ** in POPL'96, and TOPLAS v18 #3, pp 325-353.
4 :     **
5 :     ** RA CORE defines the core of the register allocator.
6 :     ** This basically means the enableMove, coalesce, simplify and freeze phases.
7 :     ** These are separated out from the rest for more modularity
8 :     ** and customizability.
9 :     **
10 :     ** -- Allen
11 :     **)
12 :    
13 :    
14 :     signature RA_GRAPH =
15 :     sig
16 :    
17 :     (*
18 :     * The following are the data structures used in the register allocator.
19 :     *)
20 :    
21 :     structure BM : BITMATRIX
22 :    
23 :     exception Nodes
24 :    
25 :     datatype interferenceGraph =
26 :     GRAPH of { bitMatrix : BM.bitMatrix,
27 :     nodes : node Intmap.intmap,
28 :     regmap : int Intmap.intmap,
29 :     K : int,
30 :     firstPseudoR : int,
31 :     getreg :
32 :     {pref:int list,stamp:int,proh:int Array.array} -> int,
33 :     proh : int Array.array,
34 :     stamp : int ref,
35 :     (* Info to undo a spill when an optimistic spill has occurred *)
36 :     spillFlag : bool ref,
37 :     undoInfo : (node * moveStatus ref) list ref
38 :     }
39 :    
40 :     and moveStatus = MOVE | COALESCED | CONSTRAINED | LOST | WORKLIST
41 :    
42 :     and move =
43 :     MV of {src : node, (* source register of move *)
44 :     dst : node, (* destination register of move *)
45 :     status : moveStatus ref (* coalesced? *)
46 :     }
47 :    
48 :     and nodeStatus = REMOVED | PSEUDO | ALIASED of node | COLORED of int
49 :    
50 :     and node =
51 :     NODE of { number : int, (* node number *)
52 :     movecnt: int ref, (* #moves this node is involved in *)
53 :     movelist: move list ref, (* moves associated with this node *)
54 :     degree : int ref, (* current degree *)
55 :     color : nodeStatus ref, (* status *)
56 :     adj : node list ref (* adjacency list *)
57 :     }
58 :     (*
59 :     * The valid transitions for a node are:
60 :     * PSEUDO -> REMOVED % during simplify
61 :     * PSEUDO -> ALIASED(n) % during coalescing
62 :     * REMOVED -> COLORED(r) % assigning a color
63 :     *
64 :     * ... all others are illegal.
65 :     *)
66 :    
67 :     type 'a worklist = 'a list
68 :     type nodelist = node worklist
69 :     type movelist = move worklist
70 :    
71 :     type ('sim,'move,'freeze,'spill,'stack) lists =
72 :     {simplifyWkl: 'sim, (* nodes that can be simplified *)
73 :     moveWkl : 'move, (* moves to be considered for coalescing *)
74 :     freezeWkl : 'freeze, (* all n, s.t. degree(n)<K and moveRelated(n) *)
75 :     spillWkl : 'spill, (* all n, s.t. degree(n)>=K *)
76 :     stack : 'stack (* nodes removed from the graph *)
77 :     }
78 :    
79 :     type worklists = (nodelist,movelist,nodelist,nodelist,nodelist) lists
80 :    
81 :     (* Create a new interference graph *)
82 :     val newGraph : {nodes : node Intmap.intmap,
83 :     regmap : int Intmap.intmap,
84 :     numRegs : int,
85 :     K : int,
86 :     firstPseudoR : int,
87 :     getreg :
88 :     {pref:int list,stamp:int,proh:int Array.array} -> int
89 :     } -> interferenceGraph
90 :    
91 :     end
92 :    

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