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
|
(*
* This module implements the Chaitin heuristic (but weighted by
* priorities)
*)
structure ChaitinSpillHeur : RA_SPILL_HEURISTICS =
struct
structure G = RAGraph
open G
exception NoCandidate
val mode = RACore.NO_OPTIMIZATION
fun init() = ()
(*
* Potential spill phase.
* Find a cheap node to spill according to Chaitin's heuristic.
*)
fun chooseSpillNode{graph, hasBeenSpilled, spillWkl} =
let fun chase(NODE{color=ref(ALIASED n),...}) = chase n
| chase n = n
val infiniteCost = 123456789.0
val don'tUse = 223456789.0
(* 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.
*)
(*
* Choose node with the lowest cost and have the maximal degree
*)
fun chaitin([], best, lowestCost, spillWkl) =
(best, lowestCost, spillWkl)
| chaitin(node::rest, best, lowestCost, spillWkl) =
(case chase node of
node as NODE{number, pri, defs, uses,
degree=ref deg, color=ref PSEUDO,...} =>
let fun cost() = !pri / real deg
val cost =
case (!defs, !uses) of
(_,[]) => (* defs but no use *)
~1.0 - real deg
| ([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 don'tUse else cost()
end
| _ => cost()
in if cost < lowestCost andalso not(hasBeenSpilled number)
then
(case best of
NONE => chaitin(rest, SOME node, cost, spillWkl)
| SOME best =>
chaitin(rest, SOME node, cost, best::spillWkl)
)
else
chaitin(rest, best, lowestCost, node::spillWkl)
end
| _ => (* discard node *)
chaitin(rest, best, lowestCost, spillWkl)
)
(* val _ = print("["^Int.toString(length spillWkl)^"]") *)
val (potentialSpillNode, cost, newSpillWkl) =
chaitin(spillWkl, NONE, infiniteCost, [])
in case (potentialSpillNode, newSpillWkl) of
(NONE, []) => {node=NONE, cost=cost, spillWkl=[]}
| (NONE, _) => raise NoCandidate
| (SOME node, spillWkl) =>
{node=SOME node, cost=cost, spillWkl=spillWkl}
end
end
|
