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
|
(*
* This module implements a Chow-Hennessy-style spill heuristic
*)
functor ImprovedChowHennessySpillHeur
(val moveRatio : real) : RA_SPILL_HEURISTICS =
struct
structure G = RAGraph
structure Heap = PriorityHeap
open G
exception NoCandidate
val mode = RACore.COMPUTE_SPAN
val cache = ref NONE : (G.node * real) Heap.priority_queue option ref
fun init() = cache := NONE
(*
* Potential spill phase.
* Find a cheap node to spill according to Chow Hennessy's heuristic.
*)
fun chooseSpillNode{graph as G.GRAPH{span, ...},
hasBeenSpilled, spillWkl} =
let fun chase(NODE{color=ref(ALIASED n),...}) = chase n
| chase n = n
(* Savings due to coalescing when a node is not spilled *)
fun moveSavings(NODE{movecnt=ref 0, ...}) = 0.0
| moveSavings(NODE{movelist, ...}) =
let fun loop([], savings) =
foldr (fn ((_,a),b) => Real.max(a,b)) 0.0 savings
| loop(MV{status=ref(WORKLIST | GEORGE_MOVE | BRIGGS_MOVE),
dst, src, cost, ...}::mvs, savings) =
let fun add(c,[]) = [(c,cost)]
| add(c,(x as (c':int,s))::savings) =
if c = c' then (c',s+cost)::savings
else x::add(c,savings)
val savings =
case chase dst of
NODE{color=ref(COLORED c), ...} => add(c,savings)
| _ =>
case chase src of
NODE{color=ref(COLORED c), ...} => add(c,savings)
| _ => savings
in loop(mvs, savings) end
| loop(_::mvs, savings) = loop(mvs, savings)
in loop(!movelist, []) end
(* The spill worklist is maintained only lazily. So we have
* to prune away those nodes that are already removed from the
* interference graph. After pruning the spillWkl,
* it may be the case that there aren't anything to be
* spilled after all.
*)
fun chowHennessy spills =
let (* Compute savings due to moves *)
val spillSavings = RACore.moveSavings graph
val lookupSpan = IntHashTable.find (Option.valOf(!span))
val lookupSpan =
fn r => case lookupSpan r of SOME s => s | NONE => 0.0
val _ = span := NONE
fun loop([], L, pruned) = (L, pruned)
| loop(node::rest, L, pruned) =
(case chase node of
node as NODE{number, pri, defs, uses,
degree=ref deg, color=ref PSEUDO,...} =>
if hasBeenSpilled number
then loop(rest, L, false)
else
let fun newnode() =
let val span = lookupSpan number
val savings = spillSavings number
val spillCost = !pri
val totalCost = spillCost - savings
(*val rank = ((real totalCost)+0.01) / real(span)*)
val rank = (totalCost + 0.5 + moveSavings(node))
/ (span+ real deg)
in loop(rest, (node, rank)::L, false) end
in case (!defs, !uses) of
(_, []) => (* one def no use *)
loop(rest, (node, ~1.0 - real(deg))::L, false)
| ([d], [u]) => (* defs after use; don't use *)
let fun plus({block,insn},n) = {block=block,insn=insn+n}
in if d = plus(u,1) orelse d = plus(u,2) then
loop(rest, L, false)
else
newnode()
end
| _ => newnode()
end
| _ => loop(rest, L, pruned) (* discard node *)
)
in loop(spills, [], true)
end
fun chooseNode heap =
let fun loop() =
let val (node,cost) = Heap.deleteMin heap
in case chase node of
node as NODE{color=ref PSEUDO, ...} =>
{node=SOME(node), cost=cost, spillWkl=spillWkl}
| _ => loop()
end
in loop()
end handle _ => {node=NONE, cost=0.0, spillWkl=[]}
in case !cache of
SOME heap => chooseNode heap
| NONE =>
let val (L, pruned) = chowHennessy(spillWkl)
in if pruned then (* done *)
{node=NONE, cost=0.0, spillWkl=[]}
else
(case L of
[] => raise NoCandidate
| _ => let fun rank((_,x), (_,y)) = Real.<(x, y)
val heap = Heap.fromList rank L
in cache := SOME heap;
chooseNode heap
end
)
end
end
end
|
