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

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