Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/flowgraph/cfg.sig
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1135, Tue Mar 12 16:09:26 2002 UTC revision 1156, Thu Mar 21 22:01:11 2002 UTC
# Line 98  Line 98 
98     type node = block Graph.node     type node = block Graph.node
99    
100     datatype info =     datatype info =
101         INFO of { annotations : Annotations.annotations ref,         INFO of
102                   firstBlock  : int ref, (* id of first block *)         { annotations : Annotations.annotations ref,
103             firstBlock  : int ref, (* id of first block (UNUSED?) *)
104                   reorder     : bool ref, (* has the CFG been reordered? *)                   reorder     : bool ref, (* has the CFG been reordered? *)
105                   data        : P.pseudo_op list ref (* reverse order of generation *)                   data        : P.pseudo_op list ref (* reverse order of generation *)
106                 }                 }
# Line 127  Line 128 
128     val defineLabel       : block -> Label.label         (* define a label *)     val defineLabel       : block -> Label.label         (* define a label *)
129     val insns             : block -> I.instruction list ref     val insns             : block -> I.instruction list ref
130     val freq              : block -> weight ref     val freq              : block -> weight ref
131       val edgeFreq          : edge -> weight ref
132       val sumEdgeFreqs      : edge list -> weight
133     val branchOf          : edge_info -> bool option     val branchOf          : edge_info -> bool option
134    
135                 (* emit assembly *)                 (* emit assembly *)
# Line 142  Line 145 
145     val subgraph : cfg -> cfg       (* mark as subgraph *)     val subgraph : cfg -> cfg       (* mark as subgraph *)
146     val init     : cfg -> unit      (* add start/stop nodes *)     val init     : cfg -> unit      (* add start/stop nodes *)
147     val changed  : cfg -> unit      (* mark cfg as changed *)     val changed  : cfg -> unit      (* mark cfg as changed *)
148           (* IMPORTANT note: you MUST call this function after
149            * changing the topology of the CFG.
150            *)
151    
152     val annotations    : cfg -> Annotations.annotations ref     val annotations    : cfg -> Annotations.annotations ref
153     val liveOut        : block -> I.C.cellset     val liveOut        : block -> I.C.cellset
# Line 151  Line 157 
157     val setBranch      : cfg * Graph.node_id * bool -> I.instruction     val setBranch      : cfg * Graph.node_id * bool -> I.instruction
158     val edgeDir        : edge_info Graph.edge -> bool option     val edgeDir        : edge_info Graph.edge -> bool option
159    
160    
161       (*=======================================================================
162        *
163        *  More complex methods for manipulating CFG.
164        *  These methods will guarantee all CFG invariants, like frequencies,
165        *  are preserved.
166        *
167        *=======================================================================*)
168    
169           (* get a label from block; generate one if necessary *)
170       val labelOf : cfg -> Graph.node_id -> Label.label
171    
172          (*
173           *  Update the label of the branch instruction in a block
174           *  to be consistent with the control flow edges.
175           *  This is an NOP if the CFG is already consistent.
176           *  This is used internally after changing CFG edges,
177           *  but it could also be useful for others.
178           *)
179       val updateJumpLabel : cfg -> Graph.node_id -> unit
180    
181          (*
182           *  Deep copy an edge info
183           *)
184       val copyEdge : edge_info -> edge_info
185    
186          (*
187           *  Merge a control flow edge.
188           *  [See also the mustPreceed test below]
189           *  Return false if merging is unsuccessful.
190           *)
191       val mergeEdge : cfg -> edge -> bool
192    
193          (*
194           *  Eliminate the jump/insert a jump
195           *     at the end of the current block if it is feasible.
196           *  Return true iff it is successful.
197           *)
198       val eliminateJump : cfg -> Graph.node_id -> bool
199       val insertJump    : cfg -> Graph.node_id -> bool
200    
201          (*
202           *  Edge splitting:
203           *
204           *  Split n groups of control flow edges, all initially entering block j,
205           *
206           *     i_11 -> j,  i_12 -> j, ...         group 1
207           *     i_21 -> j,  i_22 -> j, ...         group 2
208           *             ....
209           *     i_n1 -> j,  i_n2 -> j, ...         group n
210           *
211           *  into
212           *
213           *     i_11 -> k_1
214           *     i_12 -> k_1
215           *        ...
216           *     i_21 -> k_2
217           *     i_22 -> k_2
218           *        ...
219           *     i_n1 -> k_n
220           *     i_n2 -> k_n
221           *        ...
222           *
223           *  and k_1 -> k_2
224           *      k_2 -> k_3
225           *        ...
226           *      k_n -> j
227           *
228           *  Return the new edges
229           *       k_1->j,...,k_n -> j
230           *
231           *  and the new blocks
232           *       k_1, ..., k_n.
233           *
234           *  Each block k_1, ..., k_n can have instructions placed in them.
235           *
236           *  If the jump flag is true, then a jump is always placed in the
237           *  new block k_n; otherwise, we try to eliminate the jump when feasible.
238           *)
239       val splitEdges : cfg ->
240                        { groups : (edge list *
241                                    I.instruction list (* reverse order *)
242                                   ) list,  (* i_11 -> j, ..., i_n1 -> j *)
243                          jump : bool
244                        } -> (node * edge) list  (* k_i and k_i -> j *)
245    
246           (*
247            *  Test if an edge is critical.  An edge i->j is critical iff
248            *  there are multiple entries into j and multiple exits out of i,
249            *  i.e. it is both a merge and a split node.
250            *
251            *  Test if a node is a merge or split node.
252            *)
253        val isCriticalEdge : cfg -> edge -> bool
254        val isMerge        : cfg -> Graph.node_id -> bool
255        val isSplit        : cfg -> Graph.node_id -> bool
256    
257    
258           (*
259            *  Split all critical edges in the CFG.
260            *  This may introduce extra jumps into the program.
261            *)
262        val splitAllCriticalEdges : cfg -> unit
263    
264           (*
265            *  Check whether two blocks are necessary connected.
266            *  Blocks i and j are connected iff i must be placed before j
267            *  in all feasible layouts..
268            *)
269        val mustPreceed : cfg -> Graph.node_id * Graph.node_id -> bool
270    
271           (*
272            *  Try to merge all edges
273            *)
274        val mergeAllEdges : cfg -> unit
275    
276    (*========================================================================    (*========================================================================
277     *     *
278     *  For viewing     *  For viewing

Legend:
Removed from v.1135  
changed lines
  Added in v.1156

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