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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 428 - (view) (download)

1 : monnier 427 (*
2 :     * Graph data structure used by the modular register allocator.
3 :     *
4 :     * -- Allen
5 :     *)
6 :    
7 :     structure RAGraph : RA_GRAPH =
8 :     struct
9 :    
10 :     structure BM = TriangularBitMatrix
11 :    
12 :     datatype interferenceGraph =
13 :     GRAPH of { bitMatrix : BM.bitMatrix,
14 :     nodes : node Intmap.intmap,
15 :     regmap : int Intmap.intmap,
16 :     K : int,
17 :     firstPseudoR : int,
18 :     getreg :
19 :     {pref:int list,stamp:int,proh:int Array.array} -> int,
20 :     proh : int Array.array,
21 :     stamp : int ref,
22 :     (* Info to undo a spill when an optimistic spill has occurred *)
23 :     spillFlag : bool ref,
24 :     undoInfo : (node * moveStatus ref) list ref
25 :     }
26 :    
27 :     and moveStatus = MOVE | COALESCED | CONSTRAINED | LOST | WORKLIST
28 :    
29 :     and move =
30 :     MV of {src : node, (* source register of move *)
31 :     dst : node, (* destination register of move *)
32 :     status : moveStatus ref (* coalesced? *)
33 :     }
34 :    
35 :     and nodeStatus = REMOVED | PSEUDO | ALIASED of node | COLORED of int
36 :    
37 :     and node =
38 :     NODE of { number : int, (* node number *)
39 :     movecnt: int ref, (* #moves this node is involved in *)
40 :     movelist: move list ref, (* moves associated with this node *)
41 :     degree : int ref, (* current degree *)
42 :     color : nodeStatus ref, (* status *)
43 :     adj : node list ref (* adjacency list *)
44 :     }
45 :     (*
46 :     * The valid transitions for a node are:
47 :     * PSEUDO -> REMOVED % during simplify
48 :     * PSEUDO -> ALIASED(n) % during coalescing
49 :     * REMOVED -> COLORED(r) % assigning a color
50 :     *
51 :     * ... all others are illegal.
52 :     *)
53 :    
54 :     type 'a worklist = 'a list
55 :     type nodelist = node worklist
56 :     type movelist = move worklist
57 :    
58 :     type ('sim,'move,'freeze,'spill,'stack) lists =
59 :     {simplifyWkl: 'sim, (* nodes that can be simplified *)
60 :     moveWkl : 'move, (* moves to be considered for coalescing *)
61 :     freezeWkl : 'freeze, (* all n, s.t. degree(n)<K and moveRelated(n) *)
62 :     spillWkl : 'spill, (* all n, s.t. degree(n)>=K *)
63 :     stack : 'stack (* nodes removed from the graph *)
64 :     }
65 :    
66 :     type worklists = (nodelist,movelist,nodelist,nodelist,nodelist) lists
67 :    
68 :     exception Nodes
69 :    
70 :     (* Create a new interference graph *)
71 :     fun newGraph{nodes,regmap,K,firstPseudoR,getreg,numRegs} =
72 :     let (* lower triangular bitmatrix primitives *)
73 :     (* NOTE: The average ratio of E/N is about 16 *)
74 :     val bitMatrix = BM.new numRegs
75 :     in GRAPH{ bitMatrix = bitMatrix,
76 :     nodes = nodes,
77 :     regmap = regmap,
78 :     K = K,
79 :     firstPseudoR = firstPseudoR,
80 :     getreg = getreg,
81 :     proh = Array.array(firstPseudoR,~1),
82 :     stamp = ref 0,
83 :     spillFlag = ref false,
84 :     undoInfo = ref []
85 :     }
86 :     end
87 :    
88 :     end
89 :    

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