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 926, Fri Sep 14 15:49:15 2001 UTC revision 1162, Fri Mar 22 15:16:46 2002 UTC
# Line 13  Line 13 
13    
14     structure P : PSEUDO_OPS     structure P : PSEUDO_OPS
15     structure I : INSTRUCTIONS     structure I : INSTRUCTIONS
    sharing I.T.PseudoOp = P  
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 *)
24       | STOP           (* exit node *)       | STOP           (* exit node *)
25       | NORMAL         (* normal node *)       | NORMAL         (* normal node *)
      | HYPERBLOCK     (* hyperblock *)  
   
    and data = LABEL  of Label.label  
             | PSEUDO of P.pseudo_op  
26    
27     (*     (*
28      * NOTE: the instructions are listed in reverse order.      * NOTE 1: the instructions are listed in reverse order.
29      * This choice is for a few reasons:      * This choice is for a few reasons:
30      *      *
31      * i)  Clusters represent instructions in reverse order, so keeping this      * i)  Clusters represent instructions in reverse order, so keeping this
# Line 40  Line 36 
36      *      *
37      * iii) This also makes it easier to manipulate the branch/jump instruction      * iii) This also makes it easier to manipulate the branch/jump instruction
38      *      at the end of the block.      *      at the end of the block.
39        *
40        * NOTE 2:
41        *  Alignment always appear before labels in a block.
42      *)      *)
43    
44     and block =     and block =
# Line 47  Line 46 
46        {  id          : int,                        (* block id *)        {  id          : int,                        (* block id *)
47           kind        : block_kind,                 (* block kind *)           kind        : block_kind,                 (* block kind *)
48           freq        : weight ref,                 (* execution frequency *)           freq        : weight ref,                 (* execution frequency *)
          data        : data list ref,              (* data preceeding block *)  
49           labels      : Label.label list ref,       (* labels on blocks *)           labels      : Label.label list ref,       (* labels on blocks *)
50           insns       : I.instruction list ref,     (* in rev order *)           insns       : I.instruction list ref,     (* in rev order *)
51             align       : P.pseudo_op option ref,     (* alignment only *)
52           annotations : Annotations.annotations ref (* annotations *)           annotations : Annotations.annotations ref (* annotations *)
53        }        }
54    
55    
56     and edge_kind = ENTRY           (* entry edge *)    (* We have the following invariant on blocks and out-edge kinds:
57                   | EXIT            (* exit edge *)     *
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       *
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 *)
83          = ENTRY                   (* edge from START node *)
84          | 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 *)
88                   | SWITCH of int   (* computed goto *)                   | SWITCH of int   (* computed goto *)
89                   | SIDEEXIT of int (* the ith side exit in a hyperblock *)        | FLOWSTO                 (* FLOW_TO edge *)
90    
91     and edge_info = EDGE of { k : edge_kind,                  (* edge kind *)      and edge_info = EDGE of {
92            k : edge_kind,                  (* edge kind *)
93                               w : weight ref,                 (* edge freq *)                               w : weight ref,                 (* edge freq *)
94                               a : Annotations.annotations ref (* annotations *)                               a : Annotations.annotations ref (* annotations *)
95                             }                             }
# Line 71  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                   reorder     : bool ref (* has the CFG been reordered? *)           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    
108     type cfg = (block,edge_info,info) Graph.graph     type cfg = (block,edge_info,info) Graph.graph
# Line 92  Line 121 
121     *  Methods for manipulating basic blocks     *  Methods for manipulating basic blocks
122     *     *
123     *========================================================================*)     *========================================================================*)
124     val newBlock          : int * W.freq ref -> block (* empty *)     val newBlock          : int * weight ref -> block    (* empty *)
125     val newStart          : int * W.freq ref -> block          (* start node *)     val newStart          : int * weight ref -> block    (* start node *)
126     val newStop           : int * W.freq ref -> block          (* stop node *)     val newStop           : int * weight ref -> block    (* stop node *)
127     val copyBlock         : int * block -> block       (* copy a block *)     val copyBlock         : int * block -> block       (* copy a block *)
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 -> W.freq 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 114  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 123  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       val entryId : cfg -> Graph.node_id   (* the unique entry node ID *)
161       val exitId : cfg -> Graph.node_id    (* the unique exit node ID *)
162       val entry : cfg -> node              (* the unique entry node *)
163       val exit : cfg -> node               (* the unique exit node *)
164    
165       (*=======================================================================
166        *
167        *  More complex methods for manipulating CFG.
168        *  These methods will guarantee all CFG invariants, like frequencies,
169        *  are preserved.
170        *
171        *=======================================================================*)
172    
173           (* get a label from block; generate one if necessary *)
174       val labelOf : cfg -> Graph.node_id -> Label.label
175    
176          (*
177           *  Update the label of the branch instruction in a block
178           *  to be consistent with the control flow edges.
179           *  This is an NOP if the CFG is already consistent.
180           *  This is used internally after changing CFG edges,
181           *  but it could also be useful for others.
182           *)
183       val updateJumpLabel : cfg -> Graph.node_id -> unit
184    
185          (*
186           *  Deep copy an edge info
187           *)
188       val copyEdge : edge_info -> edge_info
189    
190          (*
191           *  Merge a control flow edge.
192           *  [See also the mustPreceed test below]
193           *  Return false if merging is unsuccessful.
194           *)
195       val mergeEdge : cfg -> edge -> bool
196    
197          (*
198           *  Eliminate the jump/insert a jump
199           *     at the end of the current block if it is feasible.
200           *  Return true iff it is successful.
201           *)
202       val eliminateJump : cfg -> Graph.node_id -> bool
203       val insertJump    : cfg -> Graph.node_id -> bool
204    
205          (*
206           *  Edge splitting:
207           *
208           *  Split n groups of control flow edges, all initially entering block j,
209           *
210           *     i_11 -> j,  i_12 -> j, ...         group 1
211           *     i_21 -> j,  i_22 -> j, ...         group 2
212           *             ....
213           *     i_n1 -> j,  i_n2 -> j, ...         group n
214           *
215           *  into
216           *
217           *     i_11 -> k_1
218           *     i_12 -> k_1
219           *        ...
220           *     i_21 -> k_2
221           *     i_22 -> k_2
222           *        ...
223           *     i_n1 -> k_n
224           *     i_n2 -> k_n
225           *        ...
226           *
227           *  and k_1 -> k_2
228           *      k_2 -> k_3
229           *        ...
230           *      k_n -> j
231           *
232           *  Return the new edges
233           *       k_1->j,...,k_n -> j
234           *
235           *  and the new blocks
236           *       k_1, ..., k_n.
237           *
238           *  Each block k_1, ..., k_n can have instructions placed in them.
239           *
240           *  If the jump flag is true, then a jump is always placed in the
241           *  new block k_n; otherwise, we try to eliminate the jump when feasible.
242           *)
243       val splitEdges : cfg ->
244                        { groups : (edge list *
245                                    I.instruction list (* reverse order *)
246                                   ) list,  (* i_11 -> j, ..., i_n1 -> j *)
247                          jump : bool
248                        } -> (node * edge) list  (* k_i and k_i -> j *)
249    
250           (*
251            *  Test if an edge is critical.  An edge i->j is critical iff
252            *  there are multiple entries into j and multiple exits out of i,
253            *  i.e. it is both a merge and a split node.
254            *
255            *  Test if a node is a merge or split node.
256            *)
257        val isCriticalEdge : cfg -> edge -> bool
258        val isMerge        : cfg -> Graph.node_id -> bool
259        val isSplit        : cfg -> Graph.node_id -> bool
260    
261    
262           (*
263            *  Split all critical edges in the CFG.
264            *  This may introduce extra jumps into the program.
265            *)
266        val splitAllCriticalEdges : cfg -> unit
267    
268           (*
269            *  Check whether two blocks are necessary connected.
270            *  Blocks i and j are connected iff i must be placed before j
271            *  in all feasible layouts..
272            *)
273        val mustPreceed : cfg -> Graph.node_id * Graph.node_id -> bool
274    
275           (*
276            *  Try to merge all edges
277            *)
278        val mergeAllEdges : cfg -> unit
279    
280    (*========================================================================    (*========================================================================
281     *     *
282     *  For viewing     *  For viewing
# Line 148  Line 302 
302     *  Methods for printing CFGs     *  Methods for printing CFGs
303     *     *
304     *========================================================================*)     *========================================================================*)
305       val kindName : block_kind -> string
306     val show_block : Annotations.annotations -> block -> string     val show_block : Annotations.annotations -> block -> string
307     val show_edge  : edge_info -> string     val show_edge  : edge_info -> string
308       val dumpBlock : (TextIO.outstream * cfg) -> node -> unit
309       val dump : (TextIO.outstream * string * cfg) -> unit
310    
311  end  end
312    

Legend:
Removed from v.926  
changed lines
  Added in v.1162

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