1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
(* ra-core.sig
*
* COPYRIGHT (c) 2002 Bell Labs, Lucent Technologies.
*
* Note: This is the core of the new register allocator, i.e. the portion
* that manipulates only the interference graph and not the flowgraph.
*
* -- Allen
*)
signature RA_CORE =
sig
structure G : RA_GRAPH (* = RAGraph *)
where type C.CellSet.cellset = RAGraph.C.CellSet.cellset
and type 'a C.ColorTable.hash_table = 'a RAGraph.C.ColorTable.hash_table
and type 'a C.HashTable.hash_table = 'a RAGraph.C.HashTable.hash_table
and type C.SortedCells.sorted_cells = RAGraph.C.SortedCells.sorted_cells
and type C.cell = RAGraph.C.cell
and type C.cellColor = RAGraph.C.cellColor
and type C.cellkind = RAGraph.C.cellkind
and type C.cellkindDesc = RAGraph.C.cellkindDesc
and type C.cellkindInfo = RAGraph.C.cellkindInfo
and type 'a PPtHashTable.hash_table = 'a RAGraph.PPtHashTable.hash_table
and type 'a SpillLocHashTable.hash_table = 'a RAGraph.SpillLocHashTable.hash_table
and type interferenceGraph = RAGraph.interferenceGraph
and type move = RAGraph.move
and type moveKind = RAGraph.moveKind
and type moveStatus = RAGraph.moveStatus
and type node = RAGraph.node
and type nodeStatus = RAGraph.nodeStatus
and type spillLoc = RAGraph.spillLoc
and type trailInfo = RAGraph.trailInfo
structure BM : RA_BITMATRIX
structure MV : RA_PRIORITY_QUEUE where type elem = G.move
structure FZ : RA_PRIORITY_QUEUE where type elem = G.node
type move_queue
type freeze_queue
val NO_OPTIMIZATION : G.mode
val BIASED_SELECTION : G.mode
val DEAD_COPY_ELIM : G.mode
val COMPUTE_SPAN : G.mode
val SAVE_COPY_TEMPS : G.mode
val HAS_PARALLEL_COPIES : G.mode
(*
* Basic functions
*)
(* dump the interference graph to a stream *)
val dumpGraph : G.interferenceGraph -> TextIO.outstream -> unit
val show : G.interferenceGraph -> G.node -> string
(* add an edge to the interference graph *)
val addEdge : G.interferenceGraph -> G.node * G.node -> unit
(*
* Function to create new nodes
*)
val newNodes : G.interferenceGraph ->
{cost:real,pt:G.programPoint,defs:G.C.cell list,uses:G.C.cell list} ->
G.node list (* defs *)
(*
* Update the colors of cell to reflect the current interference graph
*)
val updateCellColors : G.interferenceGraph -> unit
val updateCellAliases : G.interferenceGraph -> unit
val markDeadCopiesAsSpilled : G.interferenceGraph -> unit
(*
* Return the spill location id of the interference graph
*)
val spillLoc : G.interferenceGraph -> int -> int
val spillLocToString : G.interferenceGraph -> int -> string
(*
* Create an initial set of worklists from a new interference graph
* and a list of moves
*)
val initWorkLists : G.interferenceGraph ->
{ moves : G.move list
} ->
{ simplifyWkl : G.node list,
moveWkl : move_queue,
freezeWkl : freeze_queue,
spillWkl : G.node list (* high degreee nodes *)
}
(*
* Clear the interference graph but keep the nodes table intact
*)
val clearGraph : G.interferenceGraph -> unit
(*
* Remove all adjacency lists from the nodes table.
*)
val clearNodes : G.interferenceGraph -> unit
(*
* Simplify, Coalease and Freeze until the work list is done
*)
val iteratedCoalescing :
G.interferenceGraph ->
{ simplifyWkl : G.node list,
moveWkl : move_queue,
freezeWkl : freeze_queue,
stack : G.node list
} ->
{ stack : G.node list
}
(*
* potentially spill a node.
*)
val potentialSpillNode :
G.interferenceGraph ->
{ node : G.node,
cost : real,
stack : G.node list
} ->
{ moveWkl : move_queue,
freezeWkl : freeze_queue,
stack : G.node list
}
(*
* Color nodes on the stack, using Briggs' optimistic spilling.
* Return a list of actual spills
*)
val select :
G.interferenceGraph ->
{ stack : G.node list
} ->
{ spills : G.node list (* actual spills *)
}
(*
* Incorporate memory <-> register moves
*)
val initMemMoves : G.interferenceGraph -> unit
(*
* Compute spill savings due to memory <-> register moves
*)
val moveSavings : G.interferenceGraph -> (int -> real)
end
|
