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 1084, Thu Feb 21 18:52:44 2002 UTC revision 1192, Wed May 15 14:02:06 2002 UTC
# Line 14  Line 14 
14     structure P : PSEUDO_OPS     structure P : PSEUDO_OPS
15     structure I : INSTRUCTIONS     structure I : INSTRUCTIONS
16    
17     structure W : FREQ    (* used to represent frequency of execution; we use reals because some
18       * static prediction methods produce such.
19     type weight = W.freq     *)
20       type weight = real
21    
22     datatype block_kind =     datatype block_kind =
23         START          (* entry node *)         START          (* entry node *)
# Line 70  Line 71 
71     *    If the block ends with a call that has been wrapped with a FLOW_TO,     *    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     *    then there will be one FALLSTHRU out edges and one or more FLOWSTO
73     *    out edges.     *    out edges.
74       *
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     *)     *)
82      and edge_kind           (* edge kinds *)      and edge_kind           (* edge kinds *)
83        = ENTRY                   (* entry edge *)        = ENTRY                   (* edge from START node *)
84        | EXIT                    (* exit edge *)        | EXIT                    (* unlabeled edge to STOP node *)
85        | JUMP                    (* unconditional jump *)        | JUMP                    (* unconditional jump *)
86        | FALLSTHRU               (* falls through to next block *)        | FALLSTHRU               (* falls through to next block *)
87        | BRANCH of bool          (* branch *)        | BRANCH of bool          (* branch *)
# Line 90  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             decls       : P.pseudo_op list ref (* pseudo-ops before first section *)
107                 }                 }
108    
109     type cfg = (block,edge_info,info) Graph.graph     type cfg = (block,edge_info,info) Graph.graph
# Line 112  Line 122 
122     *  Methods for manipulating basic blocks     *  Methods for manipulating basic blocks
123     *     *
124     *========================================================================*)     *========================================================================*)
125     val newBlock          : int * W.freq ref -> block (* empty *)     val newBlock          : int * weight ref -> block    (* new empty block *)
126     val newStart          : int * W.freq ref -> block          (* start node *)     val newNode           : cfg -> weight -> node        (* new empty block hooked *)
127     val newStop           : int * W.freq ref -> block          (* stop node *)                                                          (* into the cfg *)
128       val newStart          : int * weight ref -> block    (* start node *)
129       val newStop           : int * weight ref -> block    (* stop node *)
130     val copyBlock         : int * block -> block       (* copy a block *)     val copyBlock         : int * block -> block       (* copy a block *)
131     val defineLabel       : block -> Label.label       (* define a label *)     val defineLabel       : block -> Label.label       (* define a label *)
132     val insns             : block -> I.instruction list ref     val insns             : block -> I.instruction list ref
133     val freq              : block -> W.freq ref     val freq              : block -> weight ref
134       val edgeFreq          : edge -> weight ref
135       val sumEdgeFreqs      : edge list -> weight
136     val branchOf          : edge_info -> bool option     val branchOf          : edge_info -> bool option
137    
138                 (* emit assembly *)                 (* emit assembly *)
# Line 134  Line 148 
148     val subgraph : cfg -> cfg       (* mark as subgraph *)     val subgraph : cfg -> cfg       (* mark as subgraph *)
149     val init     : cfg -> unit      (* add start/stop nodes *)     val init     : cfg -> unit      (* add start/stop nodes *)
150     val changed  : cfg -> unit      (* mark cfg as changed *)     val changed  : cfg -> unit      (* mark cfg as changed *)
151           (* IMPORTANT note: you MUST call this function after
152            * changing the topology of the CFG.
153            *)
154    
155     val annotations    : cfg -> Annotations.annotations ref     val annotations    : cfg -> Annotations.annotations ref
156     val liveOut        : block -> I.C.cellset     val liveOut        : block -> I.C.cellset
# Line 143  Line 160 
160     val setBranch      : cfg * Graph.node_id * bool -> I.instruction     val setBranch      : cfg * Graph.node_id * bool -> I.instruction
161     val edgeDir        : edge_info Graph.edge -> bool option     val edgeDir        : edge_info Graph.edge -> bool option
162    
163       val entryId : cfg -> Graph.node_id   (* the unique entry node ID *)
164       val exitId : cfg -> Graph.node_id    (* the unique exit node ID *)
165       val entry : cfg -> node              (* the unique entry node *)
166       val exit : cfg -> node               (* the unique exit node *)
167    
168       (*=======================================================================
169        *
170        *  More complex methods for manipulating CFG.
171        *  These methods will guarantee all CFG invariants, like frequencies,
172        *  are preserved.
173        *
174        *=======================================================================*)
175    
176           (* get a label from block; generate one if necessary *)
177       val labelOf : cfg -> Graph.node_id -> Label.label
178    
179          (*
180           *  Update the label of the branch instruction in a block
181           *  to be consistent with the control flow edges.
182           *  This is an NOP if the CFG is already consistent.
183           *  This is used internally after changing CFG edges,
184           *  but it could also be useful for others.
185           *)
186       val updateJumpLabel : cfg -> Graph.node_id -> unit
187    
188          (*
189           *  Deep copy an edge info
190           *)
191       val copyEdge : edge_info -> edge_info
192    
193          (*
194           *  Merge a control flow edge.
195           *  [See also the mustPreceed test below]
196           *  Return false if merging is unsuccessful.
197           *)
198       val mergeEdge : cfg -> edge -> bool
199    
200          (*
201           *  Eliminate the jump/insert a jump
202           *     at the end of the current block if it is feasible.
203           *  Return true iff it is successful.
204           *)
205       val eliminateJump : cfg -> Graph.node_id -> bool
206       val insertJump    : cfg -> Graph.node_id -> bool
207    
208          (*
209           *  Edge splitting:
210           *
211           *  Split n groups of control flow edges, all initially entering block j,
212           *
213           *     i_11 -> j,  i_12 -> j, ...         group 1
214           *     i_21 -> j,  i_22 -> j, ...         group 2
215           *             ....
216           *     i_n1 -> j,  i_n2 -> j, ...         group n
217           *
218           *  into
219           *
220           *     i_11 -> k_1
221           *     i_12 -> k_1
222           *        ...
223           *     i_21 -> k_2
224           *     i_22 -> k_2
225           *        ...
226           *     i_n1 -> k_n
227           *     i_n2 -> k_n
228           *        ...
229           *
230           *  and the chain
231           *      k_1 -> k_2
232           *      k_2 -> k_3
233           *        ...
234           *      k_n -> j
235           *
236           *  where k_1, ..., k_n are new basic blocks.
237           *
238           *  Return the new edges
239           *       k_1-> k_2, ..., k_n -> j
240           *
241           *  and the new blocks
242           *       k_1, ..., k_n.
243           *
244           *  Each block k_1, ..., k_n can have instructions placed in them.
245           *
246           *  If the jump flag is true, then a jump is always placed in the
247           *  new block k_n; otherwise, we try to eliminate the jump when feasible.
248           *)
249       val splitEdges : cfg ->
250                        { groups : (edge list *
251                                    I.instruction list (* reverse order *)
252                                   ) list,
253                          jump : bool
254                        } -> (node * edge) list  (* k_i and k_i -> k_{i+1} *)
255    
256           (*
257            *  Test if an edge is critical.  An edge i->j is critical iff
258            *  there are multiple entries into j and multiple exits out of i,
259            *  i.e. it is both a merge and a split node.
260            *
261            *  Test if a node is a merge or split node.
262            *)
263        val isCriticalEdge : cfg -> edge -> bool
264        val isMerge        : cfg -> Graph.node_id -> bool
265        val isSplit        : cfg -> Graph.node_id -> bool
266    
267    
268           (*
269            *  Split all critical edges in the CFG.
270            *  This may introduce extra jumps into the program.
271            *)
272        val splitAllCriticalEdges : cfg -> unit
273    
274           (*
275            *  Check whether two blocks are necessary connected.
276            *  Blocks i and j are connected iff i must be placed before j
277            *  in all feasible layouts..
278            *)
279        val mustPreceed : cfg -> Graph.node_id * Graph.node_id -> bool
280    
281           (*
282            *  Try to merge all edges
283            *)
284        val mergeAllEdges : cfg -> unit
285    
286    (*========================================================================    (*========================================================================
287     *     *
288     *  For viewing     *  For viewing
# Line 168  Line 308 
308     *  Methods for printing CFGs     *  Methods for printing CFGs
309     *     *
310     *========================================================================*)     *========================================================================*)
311       val kindName : block_kind -> string
312     val show_block : Annotations.annotations -> block -> string     val show_block : Annotations.annotations -> block -> string
313     val show_edge  : edge_info -> string     val show_edge  : edge_info -> string
314       val dumpBlock : (TextIO.outstream * cfg) -> node -> unit
315       val dump : (TextIO.outstream * string * cfg) -> unit
316    
317  end  end
318    

Legend:
Removed from v.1084  
changed lines
  Added in v.1192

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