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/flowgraph/cfg.sig
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/flowgraph/cfg.sig

Parent Directory Parent Directory | Revision Log Revision Log


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

1 : jhr 926 (* cfg.sig
2 :     *
3 :     * COPYRIGHT (c) 2001 Bell Labs, Lucent Technologies
4 :     *
5 : george 906 * Control flow graph data structure used by the MLRISC IR.
6 :     * All basic optimizations are based on this representation.
7 :     *
8 :     * -- Allen
9 :     *)
10 :    
11 :     signature CONTROL_FLOW_GRAPH =
12 :     sig
13 :    
14 :     structure P : PSEUDO_OPS
15 :     structure I : INSTRUCTIONS
16 :    
17 : jhr 1125 (* used to represent frequency of execution; we use reals because some
18 :     * static prediction methods produce such.
19 :     *)
20 :     type weight = real
21 : george 906
22 :     datatype block_kind =
23 :     START (* entry node *)
24 :     | STOP (* exit node *)
25 :     | NORMAL (* normal node *)
26 :    
27 :     (*
28 : george 984 * NOTE 1: the instructions are listed in reverse order.
29 : george 906 * This choice is for a few reasons:
30 :     *
31 :     * i) Clusters represent instructions in reverse order, so keeping this
32 :     * the same avoid having to do conversions.
33 :     *
34 :     * ii) This makes it easier to add instructions at the end of the block,
35 :     * which is more common than adding instructions to the front.
36 :     *
37 :     * iii) This also makes it easier to manipulate the branch/jump instruction
38 :     * at the end of the block.
39 : george 984 *
40 :     * NOTE 2:
41 :     * Alignment always appear before labels in a block.
42 : george 906 *)
43 :    
44 :     and block =
45 :     BLOCK of
46 :     { id : int, (* block id *)
47 :     kind : block_kind, (* block kind *)
48 :     freq : weight ref, (* execution frequency *)
49 :     labels : Label.label list ref, (* labels on blocks *)
50 :     insns : I.instruction list ref, (* in rev order *)
51 : george 984 align : P.pseudo_op option ref, (* alignment only *)
52 : george 906 annotations : Annotations.annotations ref (* annotations *)
53 :     }
54 :    
55 :    
56 : jhr 1084 (* We have the following invariant on blocks and out-edge kinds:
57 :     *
58 :     * If the last instruction of the block is an unconditional jump, then
59 :     * there is one out edge labeled with JUMP.
60 :     *
61 :     * If the last instruction of the block is a conditional jump, then
62 :     * there are two out edges. The one corresponding to the jump is
63 :     * labeled BRANCH(true) and the other is labeled BRANCH(false).
64 :     *
65 :     * If the last instruction of the block is not a jump, then there is
66 :     * one out edge labeled with FALLSTHRU.
67 :     *
68 :     * If the block ends with a switch, then the out edges are labeled with
69 :     * SWITCH.
70 :     *
71 :     * If the block ends with a call that has been wrapped with a FLOW_TO,
72 :     * then there will be one FALLSTHRU out edges and one or more FLOWSTO
73 :     * out edges.
74 : jhr 1107 *
75 :     * Control-flow to outside the CFG is represented by edges to the unique
76 :     * STOP node. When such edges are to labels that are defined outside
77 :     * the CFG, then JUMP, BRANCH, or SWITCH edges are used (as appropriate).
78 :     * When such edges are to unkonwn places (e.g., traps, returns, and
79 :     * indirect jumps), then an EXIT edge is used. There should never be
80 :     * a FALLSTHRU or ENTRY edge to the STOP node.
81 : jhr 1084 *)
82 :     and edge_kind (* edge kinds *)
83 : jhr 1107 = ENTRY (* edge from START node *)
84 :     | EXIT (* unlabeled edge to STOP node *)
85 : jhr 1084 | JUMP (* unconditional jump *)
86 :     | FALLSTHRU (* falls through to next block *)
87 :     | BRANCH of bool (* branch *)
88 :     | SWITCH of int (* computed goto *)
89 :     | FLOWSTO (* FLOW_TO edge *)
90 :    
91 :     and edge_info = EDGE of {
92 :     k : edge_kind, (* edge kind *)
93 :     w : weight ref, (* edge freq *)
94 :     a : Annotations.annotations ref (* annotations *)
95 :     }
96 : george 906
97 :     type edge = edge_info Graph.edge
98 :     type node = block Graph.node
99 :    
100 :     datatype info =
101 : leunga 1156 INFO of
102 :     { annotations : Annotations.annotations ref,
103 :     firstBlock : int ref, (* id of first block (UNUSED?) *)
104 :     reorder : bool ref, (* has the CFG been reordered? *)
105 :     data : P.pseudo_op list ref (* reverse order of generation *)
106 :     }
107 : george 906
108 :     type cfg = (block,edge_info,info) Graph.graph
109 :    
110 :     (*========================================================================
111 :     *
112 :     * Various kinds of annotations on basic blocks
113 :     *
114 :     *========================================================================*)
115 :     val LIVEOUT : I.C.cellset Annotations.property
116 :     (* escaping live out information *)
117 :     val CHANGED : (string * (unit -> unit)) Annotations.property
118 :    
119 :     (*========================================================================
120 :     *
121 :     * Methods for manipulating basic blocks
122 :     *
123 :     *========================================================================*)
124 : jhr 1172 val newBlock : int * weight ref -> block (* new empty block *)
125 :     val newNode : cfg -> weight -> node (* new empty block hooked *)
126 :     (* into the cfg *)
127 : jhr 1125 val newStart : int * weight ref -> block (* start node *)
128 :     val newStop : int * weight ref -> block (* stop node *)
129 :     val copyBlock : int * block -> block (* copy a block *)
130 :     val defineLabel : block -> Label.label (* define a label *)
131 : george 906 val insns : block -> I.instruction list ref
132 : jhr 1125 val freq : block -> weight ref
133 : leunga 1156 val edgeFreq : edge -> weight ref
134 :     val sumEdgeFreqs : edge list -> weight
135 : george 906 val branchOf : edge_info -> bool option
136 :    
137 :     (* emit assembly *)
138 : jhr 926 val emit : Annotations.annotations -> block -> unit
139 : george 906
140 :     (*========================================================================
141 :     *
142 :     * Methods for manipulating CFG
143 :     *
144 :     *========================================================================*)
145 :     val cfg : info -> cfg (* create a new cfg *)
146 :     val new : unit -> cfg (* create a new cfg *)
147 :     val subgraph : cfg -> cfg (* mark as subgraph *)
148 :     val init : cfg -> unit (* add start/stop nodes *)
149 :     val changed : cfg -> unit (* mark cfg as changed *)
150 : leunga 1156 (* IMPORTANT note: you MUST call this function after
151 :     * changing the topology of the CFG.
152 :     *)
153 : george 906
154 :     val annotations : cfg -> Annotations.annotations ref
155 :     val liveOut : block -> I.C.cellset
156 :     val fallsThruFrom : cfg * Graph.node_id -> Graph.node_id option
157 :     val fallsThruTo : cfg * Graph.node_id -> Graph.node_id option
158 :     val removeEdge : cfg -> edge -> unit
159 :     val setBranch : cfg * Graph.node_id * bool -> I.instruction
160 :     val edgeDir : edge_info Graph.edge -> bool option
161 :    
162 : jhr 1162 val entryId : cfg -> Graph.node_id (* the unique entry node ID *)
163 :     val exitId : cfg -> Graph.node_id (* the unique exit node ID *)
164 :     val entry : cfg -> node (* the unique entry node *)
165 :     val exit : cfg -> node (* the unique exit node *)
166 : leunga 1156
167 :     (*=======================================================================
168 :     *
169 :     * More complex methods for manipulating CFG.
170 :     * These methods will guarantee all CFG invariants, like frequencies,
171 :     * are preserved.
172 :     *
173 :     *=======================================================================*)
174 :    
175 :     (* get a label from block; generate one if necessary *)
176 :     val labelOf : cfg -> Graph.node_id -> Label.label
177 :    
178 :     (*
179 :     * Update the label of the branch instruction in a block
180 :     * to be consistent with the control flow edges.
181 :     * This is an NOP if the CFG is already consistent.
182 :     * This is used internally after changing CFG edges,
183 :     * but it could also be useful for others.
184 :     *)
185 :     val updateJumpLabel : cfg -> Graph.node_id -> unit
186 :    
187 :     (*
188 :     * Deep copy an edge info
189 :     *)
190 :     val copyEdge : edge_info -> edge_info
191 :    
192 :     (*
193 :     * Merge a control flow edge.
194 :     * [See also the mustPreceed test below]
195 :     * Return false if merging is unsuccessful.
196 :     *)
197 :     val mergeEdge : cfg -> edge -> bool
198 :    
199 :     (*
200 :     * Eliminate the jump/insert a jump
201 :     * at the end of the current block if it is feasible.
202 :     * Return true iff it is successful.
203 :     *)
204 :     val eliminateJump : cfg -> Graph.node_id -> bool
205 :     val insertJump : cfg -> Graph.node_id -> bool
206 :    
207 :     (*
208 :     * Edge splitting:
209 :     *
210 :     * Split n groups of control flow edges, all initially entering block j,
211 :     *
212 :     * i_11 -> j, i_12 -> j, ... group 1
213 :     * i_21 -> j, i_22 -> j, ... group 2
214 :     * ....
215 :     * i_n1 -> j, i_n2 -> j, ... group n
216 :     *
217 :     * into
218 :     *
219 :     * i_11 -> k_1
220 :     * i_12 -> k_1
221 :     * ...
222 :     * i_21 -> k_2
223 :     * i_22 -> k_2
224 :     * ...
225 :     * i_n1 -> k_n
226 :     * i_n2 -> k_n
227 :     * ...
228 :     *
229 : leunga 1174 * and the chain
230 :     * k_1 -> k_2
231 : leunga 1156 * k_2 -> k_3
232 :     * ...
233 :     * k_n -> j
234 : leunga 1174 *
235 :     * where k_1, ..., k_n are new basic blocks.
236 : leunga 1156 *
237 :     * Return the new edges
238 : leunga 1174 * k_1-> k_2, ..., k_n -> j
239 : leunga 1156 *
240 :     * and the new blocks
241 :     * k_1, ..., k_n.
242 :     *
243 :     * Each block k_1, ..., k_n can have instructions placed in them.
244 :     *
245 :     * If the jump flag is true, then a jump is always placed in the
246 :     * new block k_n; otherwise, we try to eliminate the jump when feasible.
247 :     *)
248 :     val splitEdges : cfg ->
249 :     { groups : (edge list *
250 :     I.instruction list (* reverse order *)
251 : leunga 1174 ) list,
252 : leunga 1156 jump : bool
253 : leunga 1174 } -> (node * edge) list (* k_i and k_i -> k_{i+1} *)
254 : leunga 1156
255 :     (*
256 :     * Test if an edge is critical. An edge i->j is critical iff
257 :     * there are multiple entries into j and multiple exits out of i,
258 :     * i.e. it is both a merge and a split node.
259 :     *
260 :     * Test if a node is a merge or split node.
261 :     *)
262 :     val isCriticalEdge : cfg -> edge -> bool
263 :     val isMerge : cfg -> Graph.node_id -> bool
264 :     val isSplit : cfg -> Graph.node_id -> bool
265 :    
266 :    
267 :     (*
268 :     * Split all critical edges in the CFG.
269 :     * This may introduce extra jumps into the program.
270 :     *)
271 :     val splitAllCriticalEdges : cfg -> unit
272 :    
273 :     (*
274 :     * Check whether two blocks are necessary connected.
275 :     * Blocks i and j are connected iff i must be placed before j
276 :     * in all feasible layouts..
277 :     *)
278 :     val mustPreceed : cfg -> Graph.node_id * Graph.node_id -> bool
279 :    
280 :     (*
281 :     * Try to merge all edges
282 :     *)
283 :     val mergeAllEdges : cfg -> unit
284 :    
285 :     (*========================================================================
286 : george 906 *
287 :     * For viewing
288 :     *
289 :     *========================================================================*)
290 :     (*****
291 :     val viewStyle : cfg -> (block,edge_info,info) GraphLayout.style
292 :     val viewLayout : cfg -> GraphLayout.layout
293 :     val headerText : block -> string
294 :     val footerText : block -> string
295 :     val subgraphLayout : { cfg : cfg, subgraph : cfg } -> GraphLayout.layout
296 :     *****)
297 :    
298 :     (*========================================================================
299 :     *
300 :     * Miscellaneous stuff
301 :     *
302 :     *========================================================================*)
303 :     val cdgEdge : edge_info -> bool (* for building a CDG *)
304 :    
305 : jhr 926 (*========================================================================
306 :     *
307 :     * Methods for printing CFGs
308 :     *
309 :     *========================================================================*)
310 : jhr 1135 val kindName : block_kind -> string
311 : jhr 926 val show_block : Annotations.annotations -> block -> string
312 :     val show_edge : edge_info -> string
313 : jhr 1118 val dumpBlock : (TextIO.outstream * cfg) -> node -> unit
314 : jhr 1104 val dump : (TextIO.outstream * string * cfg) -> unit
315 : jhr 926
316 : george 906 end
317 :    

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