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 /MLRISC/releases/release-110.79/ra/chow-hennessy-spillheur.sml
ViewVC logotype

Annotation of /MLRISC/releases/release-110.79/ra/chow-hennessy-spillheur.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4168 - (view) (download)

1 : monnier 496 (*
2 :     * This module implements a Chow-Hennessy-style spill heuristic
3 :     *)
4 :     structure ChowHennessySpillHeur : RA_SPILL_HEURISTICS =
5 :     struct
6 :    
7 :     structure G = RAGraph
8 :     structure Heap = PriorityHeap
9 :    
10 :     open G
11 :    
12 :     exception NoCandidate
13 :    
14 : george 545 val mode = RACore.COMPUTE_SPAN
15 : monnier 496
16 :     val cache = ref NONE : (G.node * real) Heap.priority_queue option ref
17 :    
18 :     fun init() = cache := NONE
19 :    
20 :     (*
21 :     * Potential spill phase.
22 :     * Find a cheap node to spill according to Chow Hennessy's heuristic.
23 :     *)
24 : george 545 fun chooseSpillNode{graph as G.GRAPH{span, ...},
25 :     hasBeenSpilled, spillWkl} =
26 : monnier 496 let fun chase(NODE{color=ref(ALIASED n),...}) = chase n
27 :     | chase n = n
28 :     (* The spill worklist is maintained only lazily. So we have
29 :     * to prune away those nodes that are already removed from the
30 :     * interference graph. After pruning the spillWkl,
31 :     * it may be the case that there aren't anything to be
32 :     * spilled after all.
33 :     *)
34 : george 545 fun chowHennessy spills =
35 :     let (* Compute savings due to moves *)
36 :     val spillSavings = RACore.moveSavings graph
37 : leunga 744 val lookupSpan = IntHashTable.find (Option.valOf(!span))
38 :     val lookupSpan =
39 : jhr 1125 fn r => case lookupSpan r of SOME s => s | NONE => 0.0
40 : leunga 744 val _ = span := NONE
41 : george 545 fun loop([], L, pruned) = (L, pruned)
42 :     | loop(node::rest, L, pruned) =
43 :     (case chase node of
44 :     node as NODE{number, pri, defs, uses,
45 :     degree=ref deg, color=ref PSEUDO,...} =>
46 :     if hasBeenSpilled number
47 :     then loop(rest, L, false)
48 :     else
49 :     let fun newnode() =
50 :     let val span = lookupSpan number
51 :     val savings = spillSavings number
52 :     val spillCost = !pri
53 :     val totalCost = spillCost - savings
54 :     (*val rank = ((real totalCost)+0.01) / real(span)*)
55 : jhr 1125 val rank = (totalCost + 0.5) / (span + real deg)
56 : george 545 in loop(rest, (node, rank)::L, false) end
57 :     in case (!defs, !uses) of
58 :     (_, []) => (* one def no use *)
59 :     loop(rest, (node, ~1.0 - real(deg))::L, false)
60 :     | ([d], [u]) => (* defs after use; don't use *)
61 : george 958 let fun plus({block,insn},n) = {block=block,insn=insn+n}
62 :     in if d = plus(u,1) orelse d = plus(u,2) then
63 :     loop(rest, L, false)
64 :     else
65 :     newnode()
66 :     end
67 : george 545 | _ => newnode()
68 :     end
69 :     | _ => loop(rest, L, pruned) (* discard node *)
70 :     )
71 :     in loop(spills, [], true)
72 :     end
73 : monnier 496
74 :     fun chooseNode heap =
75 :     let fun loop() =
76 :     let val (node,cost) = Heap.deleteMin heap
77 :     in case chase node of
78 :     node as NODE{color=ref PSEUDO, ...} =>
79 :     {node=SOME(node), cost=cost, spillWkl=spillWkl}
80 :     | _ => loop()
81 :     end
82 :     in loop()
83 :     end handle _ => {node=NONE, cost=0.0, spillWkl=[]}
84 :    
85 :     in case !cache of
86 :     SOME heap => chooseNode heap
87 :     | NONE =>
88 : george 545 let val (L, pruned) = chowHennessy(spillWkl)
89 : monnier 496 in if pruned then (* done *)
90 :     {node=NONE, cost=0.0, spillWkl=[]}
91 :     else
92 :     (case L of
93 :     [] => raise NoCandidate
94 :     | _ => let fun rank((_,x), (_,y)) = Real.<(x, y)
95 :     val heap = Heap.fromList rank L
96 :     in cache := SOME heap;
97 :     chooseNode heap
98 :     end
99 :     )
100 :     end
101 :     end
102 :     end

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