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 /sml/trunk/src/MLRISC/ra/chow-hennessy-spillheur2.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/ra/chow-hennessy-spillheur2.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 744 - (view) (download)

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

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