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/ra-core.sig
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/ra/ra-core.sig

Parent Directory Parent Directory | Revision Log Revision Log


Revision 628 - (view) (download) (as text)

1 : monnier 469 (*
2 :     * Note: This is the core of the new register allocator, i.e. the portion
3 :     * that manipulates only the interference graph and not the flowgraph.
4 :     *
5 :     * -- Allen
6 :     *)
7 : monnier 427
8 :     signature RA_CORE =
9 :     sig
10 :    
11 : monnier 469 structure G : RA_GRAPH
12 : george 545 structure BM :
13 :     sig
14 : leunga 628 val size : G.bitMatrix -> int
15 : george 545 val member : G.bitMatrix -> int * int -> bool
16 :     val add : G.bitMatrix -> int * int -> bool
17 :     end
18 :     structure MV : RA_PRIORITY_QUEUE where type elem = G.move
19 :     structure FZ : RA_PRIORITY_QUEUE where type elem = G.node
20 : monnier 427
21 : monnier 469 type move_queue
22 :     type freeze_queue
23 :    
24 : george 545 val NO_OPTIMIZATION : G.mode
25 :     val BIASED_SELECTION : G.mode
26 :     val DEAD_COPY_ELIM : G.mode
27 :     val COMPUTE_SPAN : G.mode
28 :     val SAVE_COPY_TEMPS : G.mode
29 :     val HAS_PARALLEL_COPIES : G.mode
30 : monnier 498
31 : monnier 427 (*
32 :     * Basic functions
33 :     *)
34 : monnier 469
35 :     (* dump the interference graph to a stream *)
36 :     val dumpGraph : G.interferenceGraph -> TextIO.outstream -> unit
37 :     val show : G.interferenceGraph -> G.node -> string
38 :    
39 :     (* add an edge to the interference graph *)
40 : monnier 427 val addEdge : G.interferenceGraph -> G.node * G.node -> unit
41 :    
42 : monnier 469 (* remove an edge from the interference graph *)
43 :     val removeEdge : G.interferenceGraph -> G.node * G.node -> unit
44 : monnier 427
45 : monnier 469 (*
46 :     * Function to create new nodes
47 :     *)
48 :     val newNodes : G.interferenceGraph ->
49 :     {cost:int,pt:G.programPoint,defs:int list,uses:int list} ->
50 :     G.node list (* defs *)
51 :    
52 :     (*
53 :     * Update regmap after finishing register allocation or copy propagation
54 :     *)
55 :     val finishRA : G.interferenceGraph -> unit
56 :     val finishCP : G.interferenceGraph -> unit
57 :    
58 :     (*
59 :     * Create an initial set of worklists from a new interference graph
60 :     * and a list of moves
61 :     *)
62 :     val initWorkLists : G.interferenceGraph ->
63 : monnier 498 { moves : G.move list
64 : monnier 469 } ->
65 :     { simplifyWkl : G.node list,
66 :     moveWkl : move_queue,
67 :     freezeWkl : freeze_queue,
68 :     spillWkl : G.node list (* high degreee nodes *)
69 :     }
70 :    
71 :     (*
72 :     * Clear the interference graph but keep the nodes table intact
73 :     *)
74 :     val clearGraph : G.interferenceGraph -> unit
75 :    
76 :     (*
77 : leunga 579 * Remove all adjacency lists from the nodes table.
78 : monnier 469 *)
79 :     val clearNodes : G.interferenceGraph -> unit
80 :    
81 :     (*
82 :     * Return a regmap function that reflects the current interference graph.
83 :     * Spilled registers are given the special value ~1
84 :     *)
85 :     val regmap : G.interferenceGraph -> (int -> int)
86 :     val spillRegmap : G.interferenceGraph -> (int -> int)
87 :     val spillLoc : G.interferenceGraph -> (int -> int)
88 :    
89 : monnier 427 (*
90 : monnier 469 * Simplify, Coalease and Freeze until the work list is done
91 : monnier 427 *)
92 : monnier 469 val iteratedCoalescing :
93 :     G.interferenceGraph ->
94 :     { simplifyWkl : G.node list,
95 :     moveWkl : move_queue,
96 :     freezeWkl : freeze_queue,
97 :     stack : G.node list
98 :     } ->
99 :     { stack : G.node list
100 :     }
101 : monnier 427
102 : monnier 469 (*
103 :     * potentially spill a node.
104 :     *)
105 :     val potentialSpillNode :
106 :     G.interferenceGraph ->
107 :     { node : G.node,
108 : george 545 cost : real,
109 : monnier 469 stack : G.node list
110 :     } ->
111 :     { moveWkl : move_queue,
112 :     freezeWkl : freeze_queue,
113 :     stack : G.node list
114 :     }
115 : monnier 427
116 : monnier 469 (*
117 :     * Color nodes on the stack, using Briggs' optimistic spilling.
118 :     * Return a list of actual spills
119 :     *)
120 :     val select :
121 :     G.interferenceGraph ->
122 : monnier 498 { stack : G.node list
123 : monnier 469 } ->
124 :     { spills : G.node list (* actual spills *)
125 :     }
126 : monnier 427
127 : monnier 469 (*
128 : monnier 498 * Incorporate memory <-> register moves
129 :     *)
130 :     val initMemMoves : G.interferenceGraph -> unit
131 :    
132 :     (*
133 : george 545 * Compute spill savings due to memory <-> register moves
134 :     *)
135 :     val moveSavings : G.interferenceGraph -> (int -> int)
136 :    
137 : monnier 427 end

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