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.84/ra/chaitin-spillheur.sml
ViewVC logotype

Annotation of /MLRISC/releases/release-110.84/ra/chaitin-spillheur.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 624 - (view) (download)
Original Path: sml/trunk/src/MLRISC/ra/chaitin-spillheur.sml

1 : monnier 467 (*
2 :     * This module implements the Chaitin heuristic (but weighted by
3 :     * priorities)
4 :     *)
5 :     structure ChaitinSpillHeur : RA_SPILL_HEURISTICS =
6 :     struct
7 :    
8 : george 545 structure G = RAGraph
9 : monnier 467
10 :     open G
11 :    
12 :     exception NoCandidate
13 :    
14 :     (*
15 :     * This dummy node is used during spilling.
16 :     *)
17 :     val dummyNode = NODE{pri=ref 0,adj=ref [],degree=ref 0,movecnt=ref 0,
18 :     color=ref PSEUDO, defs=ref [], uses=ref [],
19 :     movecost=ref 0,movelist=ref [], number= ~1}
20 :    
21 : george 545 val mode = RACore.NO_OPTIMIZATION
22 : monnier 498
23 :     fun init() = ()
24 :    
25 : monnier 467 (*
26 :     * Potential spill phase.
27 :     * Find a cheap node to spill according to Chaitin's heuristic.
28 :     *)
29 : monnier 498 fun chooseSpillNode{graph, hasBeenSpilled, spillWkl} =
30 : monnier 467 let fun chase(NODE{color=ref(ALIASED n),...}) = chase n
31 :     | chase n = n
32 :     val infiniteCost = 123456789.0
33 :     val don'tUse = 223456789.0
34 :    
35 :     (* The spill worklist is maintained only lazily. So we have
36 :     * to prune away those nodes that are already removed from the
37 :     * interference graph. After pruning the spillWkl,
38 :     * it may be the case that there aren't anything to be
39 :     * spilled after all.
40 :     *)
41 :    
42 :     (*
43 :     * Choose node with the lowest cost and have the maximal degree
44 :     *)
45 :     fun chaitin([], best, lowestCost, spillWkl) =
46 :     (best, lowestCost, spillWkl)
47 :     | chaitin(node::rest, best, lowestCost, spillWkl) =
48 :     (case chase node of
49 :     node as NODE{number, pri, defs, uses,
50 :     degree=ref deg, color=ref PSEUDO,...} =>
51 : leunga 624 let fun cost() = real(!pri) / real deg
52 : monnier 467 val cost =
53 :     case (!defs, !uses) of
54 :     (_,[]) => (* defs but no use *)
55 :     ~1.0 - real deg
56 :     | ([d],[u]) => (* defs after use; don't use *)
57 : leunga 624 if d = u+1 orelse d = u+2 then don'tUse else cost()
58 :     | _ => cost()
59 : monnier 467 in if cost < lowestCost andalso not(hasBeenSpilled number)
60 :     then
61 :     if lowestCost >= infiniteCost then (* not a real node *)
62 :     chaitin(rest, node, cost, spillWkl)
63 :     else
64 :     chaitin(rest, node, cost, best::spillWkl)
65 :     else
66 :     chaitin(rest, best, lowestCost, node::spillWkl)
67 :     end
68 :     | _ => (* discard node *)
69 :     chaitin(rest, best, lowestCost, spillWkl)
70 :     )
71 :    
72 :     (* val _ = print("["^Int.toString(length spillWkl)^"]") *)
73 :    
74 :     val (potentialSpillNode, cost, newSpillWkl) =
75 :     chaitin(spillWkl, dummyNode, infiniteCost, [])
76 :     in case (potentialSpillNode, newSpillWkl) of
77 :     (NODE{number= ~1, ...}, []) => {node=NONE, cost=cost, spillWkl=[]}
78 :     | (NODE{number= ~1, ...}, _) => raise NoCandidate
79 :     | (node, spillWkl) => {node=SOME node, cost=cost, spillWkl=spillWkl}
80 :     end
81 :     end

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