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

Annotation of /MLRISC/trunk/ra/chaitin-spillheur.sml

Parent Directory Parent Directory | Revision Log Revision Log


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

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