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
|
(*
* This module manages the spill/reload process.
*
* -- Allen
*)
signature RA_SPILL =
sig
structure I : INSTRUCTIONS
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 C : CELLS
(* sharing I.C = C *)
structure CB : CELLS_BASIS (* = CellsBasis *)
where type CellSet.cellset = CellsBasis.CellSet.cellset
and type 'a ColorTable.hash_table = 'a CellsBasis.ColorTable.hash_table
and type 'a HashTable.hash_table = 'a CellsBasis.HashTable.hash_table
and type SortedCells.sorted_cells = CellsBasis.SortedCells.sorted_cells
and type cell = CellsBasis.cell
and type cellColor = CellsBasis.cellColor
and type cellkind = CellsBasis.cellkind
and type cellkindDesc = CellsBasis.cellkindDesc
and type cellkindInfo = CellsBasis.cellkindInfo
type copyInstr =
(CB.cell list * CB.cell list) * I.instruction -> I.instruction list
(*
* Spill the value associated with reg into spillLoc.
* All definitions of instr should be renamed to a new temporary newReg.
*)
type spill =
{instr : I.instruction, (* instruction where spill is to occur *)
reg : CB.cell, (* register to spill *)
spillLoc : G.spillLoc, (* logical spill location *)
kill : bool, (* can we kill the current node? *)
annotations : Annotations.annotations ref (* annotations *)
} ->
{code : I.instruction list, (* instruction + spill code *)
proh : CB.cell list, (* prohibited from future spilling *)
newReg : CB.cell option (* the spilled value is available here *)
}
(* Spill the register src into spillLoc.
* The value is originally from register reg.
*)
type spillSrc =
{src : CB.cell, (* register to spill from *)
reg : CB.cell, (* the register *)
spillLoc : G.spillLoc, (* logical spill location *)
annotations : Annotations.annotations ref (* annotations *)
} -> I.instruction list (* spill code *)
(*
* Spill the temporary associated with a copy into spillLoc
*)
type spillCopyTmp =
{copy : I.instruction, (* copy to spill *)
reg : CB.cell, (* the register *)
spillLoc : G.spillLoc, (* logical spill location *)
annotations : Annotations.annotations ref (* annotations *)
} -> I.instruction (* spill code *)
(*
* Reload the value associated with reg from spillLoc.
* All uses of instr should be renamed to a new temporary newReg.
*)
type reload =
{instr : I.instruction, (* instruction where spill is to occur *)
reg : CB.cell, (* register to spill *)
spillLoc : G.spillLoc, (* logical spill location *)
annotations : Annotations.annotations ref (* annotations *)
} ->
{code : I.instruction list, (* instr + reload code *)
proh : CB.cell list, (* prohibited from future spilling *)
newReg : CB.cell option (* the reloaded value is here *)
}
(*
* Rename all uses fromSrc to toSrc
*)
type renameSrc =
{instr : I.instruction, (* instruction where spill is to occur *)
fromSrc : CB.cell, (* register to rename *)
toSrc : CB.cell (* register to rename to *)
} ->
{code : I.instruction list, (* renamed instr *)
proh : CB.cell list, (* prohibited from future spilling *)
newReg : CB.cell option (* the renamed value is here *)
}
(* Reload the register dst from spillLoc.
* The value is originally from register reg.
*)
type reloadDst =
{dst : CB.cell, (* register to reload to *)
reg : CB.cell, (* the register *)
spillLoc : G.spillLoc, (* logical spill location *)
annotations : Annotations.annotations ref (* annotations *)
} -> I.instruction list (* reload code *)
(*
* The following function rewrites an instruction and insert
* spill and reload code around it. The list of spill and reload
* registers may have duplicates.
*)
val spillRewrite :
{ graph : G.interferenceGraph,
spill : spill,
spillSrc : spillSrc,
spillCopyTmp : spillCopyTmp,
reload : reload,
reloadDst : reloadDst,
renameSrc : renameSrc,
copyInstr : copyInstr,
cellkind : CB.cellkind,
spillSet : CB.cell list G.PPtHashTable.hash_table,
reloadSet : CB.cell list G.PPtHashTable.hash_table,
killSet : CB.cell list G.PPtHashTable.hash_table
} ->
{ pt : G.programPoint, (* starting program pt *)
annotations : Annotations.annotations ref, (* annotations *)
instrs : I.instruction list (* instructions to spill *)
} ->
I.instruction list (* instruction sequence after rewriting *)
(* Note, instructions are in reverse order *)
end
|
