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 1156 - (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 :     val mode = RACore.NO_OPTIMIZATION
20 :    
21 :     fun init() = ()
22 :    
23 :     (*
24 :     * Potential spill phase.
25 :     * Find a cheap node to spill according to Chaitin's heuristic.
26 :     *)
27 :     fun chooseSpillNode{graph, hasBeenSpilled, spillWkl} =
28 :     let fun chase(NODE{color=ref(ALIASED n),...}) = chase n
29 :     | chase n = n
30 :     val infiniteCost = 123456789.0
31 :     val don'tUse = 223456789.0
32 :    
33 :     (* Savings due to coalescing when a node is not spilled *)
34 :     fun moveSavings(NODE{movecnt=ref 0, ...}) = 0.0
35 :     | moveSavings(NODE{movelist, ...}) =
36 :     let fun loop([], savings) =
37 : leunga 1156 foldr (fn ((_,a),b) => Real.max(a,b)) 0.0 savings
38 : leunga 624 | loop(MV{status=ref(WORKLIST | GEORGE_MOVE | BRIGGS_MOVE),
39 :     dst, src, cost, ...}::mvs, savings) =
40 :     let fun add(c,[]) = [(c,cost)]
41 :     | add(c,(x as (c':int,s))::savings) =
42 :     if c = c' then (c',s+cost)::savings
43 :     else x::add(c,savings)
44 :     val savings =
45 :     case chase dst of
46 :     NODE{color=ref(COLORED c), ...} => add(c,savings)
47 :     | _ =>
48 :     case chase src of
49 :     NODE{color=ref(COLORED c), ...} => add(c,savings)
50 :     | _ => savings
51 :     in loop(mvs, savings) end
52 :     | loop(_::mvs, savings) = loop(mvs, savings)
53 :     in loop(!movelist, []) end
54 :    
55 :     (* The spill worklist is maintained only lazily. So we have
56 :     * to prune away those nodes that are already removed from the
57 :     * interference graph. After pruning the spillWkl,
58 :     * it may be the case that there aren't anything to be
59 :     * spilled after all.
60 :     *)
61 :    
62 :     (*
63 :     * Choose node with the lowest cost and have the maximal degree
64 :     *)
65 :     fun chaitin([], best, lowestCost, spillWkl) =
66 :     (best, lowestCost, spillWkl)
67 :     | chaitin(node::rest, best, lowestCost, spillWkl) =
68 :     (case chase node of
69 :     node as NODE{number, pri, defs, uses,
70 :     degree=ref deg, color=ref PSEUDO,...} =>
71 :     let fun cost() =
72 :     let val moveSavings = moveRatio * moveSavings(node)
73 : leunga 1156 in (!pri + moveSavings) / real deg end
74 : leunga 624 val cost =
75 :     case (!defs, !uses) of
76 :     (_,[]) => (* defs but no use *)
77 :     ~1.0 - real deg
78 :     | ([d],[u]) => (* defs after use; don't use *)
79 : george 958 let fun plus({block,insn},n) = {block=block,insn=insn+n}
80 :     in if d = plus(u,1) orelse d = plus(u,2)
81 :     then don'tUse else cost()
82 :     end
83 : leunga 624 | _ => cost()
84 :     in if cost < lowestCost andalso not(hasBeenSpilled number)
85 :     then
86 : leunga 744 (case best of
87 :     NONE => chaitin(rest, SOME node, cost, spillWkl)
88 :     | SOME best =>
89 :     chaitin(rest, SOME node, cost, best::spillWkl)
90 :     )
91 : leunga 624 else
92 :     chaitin(rest, best, lowestCost, node::spillWkl)
93 :     end
94 :     | _ => (* discard node *)
95 :     chaitin(rest, best, lowestCost, spillWkl)
96 :     )
97 :    
98 :     (* val _ = print("["^Int.toString(length spillWkl)^"]") *)
99 :    
100 :     val (potentialSpillNode, cost, newSpillWkl) =
101 : leunga 744 chaitin(spillWkl, NONE, infiniteCost, [])
102 : leunga 624 in case (potentialSpillNode, newSpillWkl) of
103 : leunga 744 (NONE, []) => {node=NONE, cost=cost, spillWkl=[]}
104 :     | (NONE, _) => raise NoCandidate
105 :     | (SOME node, spillWkl) =>
106 :     {node=SOME node, cost=cost, spillWkl=spillWkl}
107 : leunga 624 end
108 :     end

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