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 651 - (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 :     val lookupSpan = Intmap.mapWithDefault (Option.valOf(!span),0)
62 :     val _ = span := NONE
63 :     fun loop([], L, pruned) = (L, pruned)
64 :     | loop(node::rest, L, pruned) =
65 :     (case chase node of
66 :     node as NODE{number, pri, defs, uses,
67 :     degree=ref deg, color=ref PSEUDO,...} =>
68 :     if hasBeenSpilled number
69 :     then loop(rest, L, false)
70 :     else
71 :     let fun newnode() =
72 :     let val span = lookupSpan number
73 :     val savings = spillSavings number
74 :     val spillCost = !pri
75 :     val totalCost = spillCost - savings
76 :     (*val rank = ((real totalCost)+0.01) / real(span)*)
77 :     val rank = (real totalCost + 0.5 + moveSavings(node))
78 :     / real(span+deg)
79 :     in loop(rest, (node, rank)::L, false) end
80 :     in case (!defs, !uses) of
81 :     (_, []) => (* one def no use *)
82 :     loop(rest, (node, ~1.0 - real(deg))::L, false)
83 :     | ([d], [u]) => (* defs after use; don't use *)
84 :     if d = u+1 orelse d = u+2 then
85 :     loop(rest, L, false)
86 :     else
87 :     newnode()
88 :     | _ => newnode()
89 :     end
90 :     | _ => loop(rest, L, pruned) (* discard node *)
91 :     )
92 :     in loop(spills, [], true)
93 :     end
94 :    
95 :     fun chooseNode heap =
96 :     let fun loop() =
97 :     let val (node,cost) = Heap.deleteMin heap
98 :     in case chase node of
99 :     node as NODE{color=ref PSEUDO, ...} =>
100 :     {node=SOME(node), cost=cost, spillWkl=spillWkl}
101 :     | _ => loop()
102 :     end
103 :     in loop()
104 :     end handle _ => {node=NONE, cost=0.0, spillWkl=[]}
105 :    
106 :     in case !cache of
107 :     SOME heap => chooseNode heap
108 :     | NONE =>
109 :     let val (L, pruned) = chowHennessy(spillWkl)
110 :     in if pruned then (* done *)
111 :     {node=NONE, cost=0.0, spillWkl=[]}
112 :     else
113 :     (case L of
114 :     [] => raise NoCandidate
115 :     | _ => let fun rank((_,x), (_,y)) = Real.<(x, y)
116 :     val heap = Heap.fromList rank L
117 :     in cache := SOME heap;
118 :     chooseNode heap
119 :     end
120 :     )
121 :     end
122 :     end
123 :     end

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