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 744 - (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 : leunga 744 structure G : RA_GRAPH = RAGraph
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 (*
43 :     * Function to create new nodes
44 :     *)
45 :     val newNodes : G.interferenceGraph ->
46 : leunga 744 {cost:int,pt:G.programPoint,defs:G.C.cell list,uses:G.C.cell list} ->
47 : monnier 469 G.node list (* defs *)
48 :    
49 :     (*
50 : leunga 744 * Update the colors of cell to reflect the current interference graph
51 : monnier 469 *)
52 : leunga 744 val updateCellColors : G.interferenceGraph -> unit
53 :     val updateCellAliases : G.interferenceGraph -> unit
54 : monnier 469
55 : leunga 744 val markDeadCopiesAsSpilled : G.interferenceGraph -> unit
56 :    
57 : monnier 469 (*
58 : leunga 744 * Return the spill location id of the interference graph
59 :     *)
60 :     val spillLoc : G.interferenceGraph -> int -> int
61 :     val spillLocToString : G.interferenceGraph -> int -> string
62 :    
63 :     (*
64 : monnier 469 * Create an initial set of worklists from a new interference graph
65 :     * and a list of moves
66 :     *)
67 :     val initWorkLists : G.interferenceGraph ->
68 : monnier 498 { moves : G.move list
69 : monnier 469 } ->
70 :     { simplifyWkl : G.node list,
71 :     moveWkl : move_queue,
72 :     freezeWkl : freeze_queue,
73 :     spillWkl : G.node list (* high degreee nodes *)
74 :     }
75 :    
76 :     (*
77 :     * Clear the interference graph but keep the nodes table intact
78 :     *)
79 :     val clearGraph : G.interferenceGraph -> unit
80 :    
81 :     (*
82 : leunga 579 * Remove all adjacency lists from the nodes table.
83 : monnier 469 *)
84 :     val clearNodes : G.interferenceGraph -> unit
85 :    
86 : monnier 427 (*
87 : monnier 469 * Simplify, Coalease and Freeze until the work list is done
88 : monnier 427 *)
89 : monnier 469 val iteratedCoalescing :
90 :     G.interferenceGraph ->
91 :     { simplifyWkl : G.node list,
92 :     moveWkl : move_queue,
93 :     freezeWkl : freeze_queue,
94 :     stack : G.node list
95 :     } ->
96 :     { stack : G.node list
97 :     }
98 : monnier 427
99 : monnier 469 (*
100 :     * potentially spill a node.
101 :     *)
102 :     val potentialSpillNode :
103 :     G.interferenceGraph ->
104 :     { node : G.node,
105 : george 545 cost : real,
106 : monnier 469 stack : G.node list
107 :     } ->
108 :     { moveWkl : move_queue,
109 :     freezeWkl : freeze_queue,
110 :     stack : G.node list
111 :     }
112 : monnier 427
113 : monnier 469 (*
114 :     * Color nodes on the stack, using Briggs' optimistic spilling.
115 :     * Return a list of actual spills
116 :     *)
117 :     val select :
118 :     G.interferenceGraph ->
119 : monnier 498 { stack : G.node list
120 : monnier 469 } ->
121 :     { spills : G.node list (* actual spills *)
122 :     }
123 : monnier 427
124 : monnier 469 (*
125 : monnier 498 * Incorporate memory <-> register moves
126 :     *)
127 :     val initMemMoves : G.interferenceGraph -> unit
128 :    
129 :     (*
130 : george 545 * Compute spill savings due to memory <-> register moves
131 :     *)
132 :     val moveSavings : G.interferenceGraph -> (int -> int)
133 :    
134 : monnier 427 end

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