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 1053 - (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 1053 structure BM : RA_BITMATRIX
13 : george 545 structure MV : RA_PRIORITY_QUEUE where type elem = G.move
14 :     structure FZ : RA_PRIORITY_QUEUE where type elem = G.node
15 : monnier 427
16 : monnier 469 type move_queue
17 :     type freeze_queue
18 :    
19 : george 545 val NO_OPTIMIZATION : G.mode
20 :     val BIASED_SELECTION : G.mode
21 :     val DEAD_COPY_ELIM : G.mode
22 :     val COMPUTE_SPAN : G.mode
23 :     val SAVE_COPY_TEMPS : G.mode
24 :     val HAS_PARALLEL_COPIES : G.mode
25 : monnier 498
26 : monnier 427 (*
27 :     * Basic functions
28 :     *)
29 : monnier 469
30 :     (* dump the interference graph to a stream *)
31 :     val dumpGraph : G.interferenceGraph -> TextIO.outstream -> unit
32 :     val show : G.interferenceGraph -> G.node -> string
33 :    
34 :     (* add an edge to the interference graph *)
35 : monnier 427 val addEdge : G.interferenceGraph -> G.node * G.node -> unit
36 :    
37 : monnier 469 (*
38 :     * Function to create new nodes
39 :     *)
40 :     val newNodes : G.interferenceGraph ->
41 : leunga 744 {cost:int,pt:G.programPoint,defs:G.C.cell list,uses:G.C.cell list} ->
42 : monnier 469 G.node list (* defs *)
43 :    
44 :     (*
45 : leunga 744 * Update the colors of cell to reflect the current interference graph
46 : monnier 469 *)
47 : leunga 744 val updateCellColors : G.interferenceGraph -> unit
48 :     val updateCellAliases : G.interferenceGraph -> unit
49 : monnier 469
50 : leunga 744 val markDeadCopiesAsSpilled : G.interferenceGraph -> unit
51 :    
52 : monnier 469 (*
53 : leunga 744 * Return the spill location id of the interference graph
54 :     *)
55 :     val spillLoc : G.interferenceGraph -> int -> int
56 :     val spillLocToString : G.interferenceGraph -> int -> string
57 :    
58 :     (*
59 : monnier 469 * 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 : monnier 427 (*
82 : monnier 469 * Simplify, Coalease and Freeze until the work list is done
83 : monnier 427 *)
84 : monnier 469 val iteratedCoalescing :
85 :     G.interferenceGraph ->
86 :     { simplifyWkl : G.node list,
87 :     moveWkl : move_queue,
88 :     freezeWkl : freeze_queue,
89 :     stack : G.node list
90 :     } ->
91 :     { stack : G.node list
92 :     }
93 : monnier 427
94 : monnier 469 (*
95 :     * potentially spill a node.
96 :     *)
97 :     val potentialSpillNode :
98 :     G.interferenceGraph ->
99 :     { node : G.node,
100 : george 545 cost : real,
101 : monnier 469 stack : G.node list
102 :     } ->
103 :     { moveWkl : move_queue,
104 :     freezeWkl : freeze_queue,
105 :     stack : G.node list
106 :     }
107 : monnier 427
108 : monnier 469 (*
109 :     * Color nodes on the stack, using Briggs' optimistic spilling.
110 :     * Return a list of actual spills
111 :     *)
112 :     val select :
113 :     G.interferenceGraph ->
114 : monnier 498 { stack : G.node list
115 : monnier 469 } ->
116 :     { spills : G.node list (* actual spills *)
117 :     }
118 : monnier 427
119 : monnier 469 (*
120 : monnier 498 * Incorporate memory <-> register moves
121 :     *)
122 :     val initMemMoves : G.interferenceGraph -> unit
123 :    
124 :     (*
125 : george 545 * Compute spill savings due to memory <-> register moves
126 :     *)
127 :     val moveSavings : G.interferenceGraph -> (int -> int)
128 :    
129 : monnier 427 end

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