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/chaitin-spillheur2.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/ra/chaitin-spillheur2.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 651 - (view) (download)

1 : leunga 624 (*
2 :     * This module implements the Chaitin heuristic (but weighted by
3 :     * priorities). This version also takes into account of savings in
4 :     * coalescing if a virtual is not spilled. You should use this version
5 :     * if your program uses direct style and makes use of calleesave registers.
6 :     *)
7 :     functor ImprovedChaitinSpillHeur
8 :     (val moveRatio : real
9 :     (* cost of move compared to load/store; should be <= 1.0 *)
10 :     ) : RA_SPILL_HEURISTICS =
11 :     struct
12 :    
13 :     structure G = RAGraph
14 :    
15 :     open G
16 :    
17 :     exception NoCandidate
18 :    
19 :     (*
20 :     * This dummy node is used during spilling.
21 :     *)
22 :     val dummyNode = NODE{pri=ref 0,adj=ref [],degree=ref 0,movecnt=ref 0,
23 :     color=ref PSEUDO, defs=ref [], uses=ref [],
24 :     movecost=ref 0,movelist=ref [], number= ~1}
25 :    
26 :     val mode = RACore.NO_OPTIMIZATION
27 :    
28 :     fun init() = ()
29 :    
30 :     (*
31 :     * Potential spill phase.
32 :     * Find a cheap node to spill according to Chaitin's heuristic.
33 :     *)
34 :     fun chooseSpillNode{graph, hasBeenSpilled, spillWkl} =
35 :     let fun chase(NODE{color=ref(ALIASED n),...}) = chase n
36 :     | chase n = n
37 :     val infiniteCost = 123456789.0
38 :     val don'tUse = 223456789.0
39 :    
40 :     (* Savings due to coalescing when a node is not spilled *)
41 :     fun moveSavings(NODE{movecnt=ref 0, ...}) = 0.0
42 :     | moveSavings(NODE{movelist, ...}) =
43 :     let fun loop([], savings) =
44 :     real(foldr (fn ((_,a),b) => Int.max(a,b)) 0 savings)
45 :     | loop(MV{status=ref(WORKLIST | GEORGE_MOVE | BRIGGS_MOVE),
46 :     dst, src, cost, ...}::mvs, savings) =
47 :     let fun add(c,[]) = [(c,cost)]
48 :     | add(c,(x as (c':int,s))::savings) =
49 :     if c = c' then (c',s+cost)::savings
50 :     else x::add(c,savings)
51 :     val savings =
52 :     case chase dst of
53 :     NODE{color=ref(COLORED c), ...} => add(c,savings)
54 :     | _ =>
55 :     case chase src of
56 :     NODE{color=ref(COLORED c), ...} => add(c,savings)
57 :     | _ => savings
58 :     in loop(mvs, savings) end
59 :     | loop(_::mvs, savings) = loop(mvs, savings)
60 :     in loop(!movelist, []) end
61 :    
62 :     (* The spill worklist is maintained only lazily. So we have
63 :     * to prune away those nodes that are already removed from the
64 :     * interference graph. After pruning the spillWkl,
65 :     * it may be the case that there aren't anything to be
66 :     * spilled after all.
67 :     *)
68 :    
69 :     (*
70 :     * Choose node with the lowest cost and have the maximal degree
71 :     *)
72 :     fun chaitin([], best, lowestCost, spillWkl) =
73 :     (best, lowestCost, spillWkl)
74 :     | chaitin(node::rest, best, lowestCost, spillWkl) =
75 :     (case chase node of
76 :     node as NODE{number, pri, defs, uses,
77 :     degree=ref deg, color=ref PSEUDO,...} =>
78 :     let fun cost() =
79 :     let val moveSavings = moveRatio * moveSavings(node)
80 :     in (real(!pri) + moveSavings) / real deg end
81 :     val cost =
82 :     case (!defs, !uses) of
83 :     (_,[]) => (* defs but no use *)
84 :     ~1.0 - real deg
85 :     | ([d],[u]) => (* defs after use; don't use *)
86 :     if d = u+1 orelse d = u+2 then don'tUse else cost()
87 :     | _ => cost()
88 :     in if cost < lowestCost andalso not(hasBeenSpilled number)
89 :     then
90 :     if lowestCost >= infiniteCost then (* not a real node *)
91 :     chaitin(rest, node, cost, spillWkl)
92 :     else
93 :     chaitin(rest, node, cost, best::spillWkl)
94 :     else
95 :     chaitin(rest, best, lowestCost, node::spillWkl)
96 :     end
97 :     | _ => (* discard node *)
98 :     chaitin(rest, best, lowestCost, spillWkl)
99 :     )
100 :    
101 :     (* val _ = print("["^Int.toString(length spillWkl)^"]") *)
102 :    
103 :     val (potentialSpillNode, cost, newSpillWkl) =
104 :     chaitin(spillWkl, dummyNode, infiniteCost, [])
105 :     in case (potentialSpillNode, newSpillWkl) of
106 :     (NODE{number= ~1, ...}, []) => {node=NONE, cost=cost, spillWkl=[]}
107 :     | (NODE{number= ~1, ...}, _) => raise NoCandidate
108 :     | (node, spillWkl) => {node=SOME node, cost=cost, spillWkl=spillWkl}
109 :     end
110 :     end

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