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-spillheur.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 744 - (view) (download)

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

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