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 1107 - (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 :     structure W : FREQ
18 :    
19 :     type weight = W.freq
20 :    
21 :     datatype block_kind =
22 :     START (* entry node *)
23 :     | STOP (* exit node *)
24 :     | NORMAL (* normal node *)
25 :    
26 :     (*
27 : george 984 * NOTE 1: the instructions are listed in reverse order.
28 : george 906 * This choice is for a few reasons:
29 :     *
30 :     * i) Clusters represent instructions in reverse order, so keeping this
31 :     * the same avoid having to do conversions.
32 :     *
33 :     * ii) This makes it easier to add instructions at the end of the block,
34 :     * which is more common than adding instructions to the front.
35 :     *
36 :     * iii) This also makes it easier to manipulate the branch/jump instruction
37 :     * at the end of the block.
38 : george 984 *
39 :     * NOTE 2:
40 :     * Alignment always appear before labels in a block.
41 : george 906 *)
42 :    
43 :     and block =
44 :     BLOCK of
45 :     { id : int, (* block id *)
46 :     kind : block_kind, (* block kind *)
47 :     freq : weight ref, (* execution frequency *)
48 :     labels : Label.label list ref, (* labels on blocks *)
49 :     insns : I.instruction list ref, (* in rev order *)
50 : george 984 align : P.pseudo_op option ref, (* alignment only *)
51 : george 906 annotations : Annotations.annotations ref (* annotations *)
52 :     }
53 :    
54 :    
55 : jhr 1084 (* We have the following invariant on blocks and out-edge kinds:
56 :     *
57 :     * If the last instruction of the block is an unconditional jump, then
58 :     * there is one out edge labeled with JUMP.
59 :     *
60 :     * If the last instruction of the block is a conditional jump, then
61 :     * there are two out edges. The one corresponding to the jump is
62 :     * labeled BRANCH(true) and the other is labeled BRANCH(false).
63 :     *
64 :     * If the last instruction of the block is not a jump, then there is
65 :     * one out edge labeled with FALLSTHRU.
66 :     *
67 :     * If the block ends with a switch, then the out edges are labeled with
68 :     * SWITCH.
69 :     *
70 :     * If the block ends with a call that has been wrapped with a FLOW_TO,
71 :     * then there will be one FALLSTHRU out edges and one or more FLOWSTO
72 :     * out edges.
73 : jhr 1107 *
74 :     * Control-flow to outside the CFG is represented by edges to the unique
75 :     * STOP node. When such edges are to labels that are defined outside
76 :     * the CFG, then JUMP, BRANCH, or SWITCH edges are used (as appropriate).
77 :     * When such edges are to unkonwn places (e.g., traps, returns, and
78 :     * indirect jumps), then an EXIT edge is used. There should never be
79 :     * a FALLSTHRU or ENTRY edge to the STOP node.
80 : jhr 1084 *)
81 :     and edge_kind (* edge kinds *)
82 : jhr 1107 = ENTRY (* edge from START node *)
83 :     | EXIT (* unlabeled edge to STOP node *)
84 : jhr 1084 | JUMP (* unconditional jump *)
85 :     | FALLSTHRU (* falls through to next block *)
86 :     | BRANCH of bool (* branch *)
87 :     | SWITCH of int (* computed goto *)
88 :     | FLOWSTO (* FLOW_TO edge *)
89 :    
90 :     and edge_info = EDGE of {
91 :     k : edge_kind, (* edge kind *)
92 :     w : weight ref, (* edge freq *)
93 :     a : Annotations.annotations ref (* annotations *)
94 :     }
95 : george 906
96 :     type edge = edge_info Graph.edge
97 :     type node = block Graph.node
98 :    
99 :     datatype info =
100 :     INFO of { annotations : Annotations.annotations ref,
101 :     firstBlock : int ref, (* id of first block *)
102 : george 984 reorder : bool ref, (* has the CFG been reordered? *)
103 :     data : P.pseudo_op list ref (* reverse order of generation *)
104 : george 906 }
105 :    
106 :     type cfg = (block,edge_info,info) Graph.graph
107 :    
108 :     (*========================================================================
109 :     *
110 :     * Various kinds of annotations on basic blocks
111 :     *
112 :     *========================================================================*)
113 :     val LIVEOUT : I.C.cellset Annotations.property
114 :     (* escaping live out information *)
115 :     val CHANGED : (string * (unit -> unit)) Annotations.property
116 :    
117 :     (*========================================================================
118 :     *
119 :     * Methods for manipulating basic blocks
120 :     *
121 :     *========================================================================*)
122 :     val newBlock : int * W.freq ref -> block (* empty *)
123 :     val newStart : int * W.freq ref -> block (* start node *)
124 :     val newStop : int * W.freq ref -> block (* stop node *)
125 :     val copyBlock : int * block -> block (* copy a block *)
126 :     val defineLabel : block -> Label.label (* define a label *)
127 :     val insns : block -> I.instruction list ref
128 :     val freq : block -> W.freq ref
129 :     val branchOf : edge_info -> bool option
130 :    
131 :     (* emit assembly *)
132 : jhr 926 val emit : Annotations.annotations -> block -> unit
133 : george 906
134 :     (*========================================================================
135 :     *
136 :     * Methods for manipulating CFG
137 :     *
138 :     *========================================================================*)
139 :     val cfg : info -> cfg (* create a new cfg *)
140 :     val new : unit -> cfg (* create a new cfg *)
141 :     val subgraph : cfg -> cfg (* mark as subgraph *)
142 :     val init : cfg -> unit (* add start/stop nodes *)
143 :     val changed : cfg -> unit (* mark cfg as changed *)
144 :    
145 :     val annotations : cfg -> Annotations.annotations ref
146 :     val liveOut : block -> I.C.cellset
147 :     val fallsThruFrom : cfg * Graph.node_id -> Graph.node_id option
148 :     val fallsThruTo : cfg * Graph.node_id -> Graph.node_id option
149 :     val removeEdge : cfg -> edge -> unit
150 :     val setBranch : cfg * Graph.node_id * bool -> I.instruction
151 :     val edgeDir : edge_info Graph.edge -> bool option
152 :    
153 :     (*========================================================================
154 :     *
155 :     * For viewing
156 :     *
157 :     *========================================================================*)
158 :     (*****
159 :     val viewStyle : cfg -> (block,edge_info,info) GraphLayout.style
160 :     val viewLayout : cfg -> GraphLayout.layout
161 :     val headerText : block -> string
162 :     val footerText : block -> string
163 :     val subgraphLayout : { cfg : cfg, subgraph : cfg } -> GraphLayout.layout
164 :     *****)
165 :    
166 :     (*========================================================================
167 :     *
168 :     * Miscellaneous stuff
169 :     *
170 :     *========================================================================*)
171 :     val cdgEdge : edge_info -> bool (* for building a CDG *)
172 :    
173 : jhr 926 (*========================================================================
174 :     *
175 :     * Methods for printing CFGs
176 :     *
177 :     *========================================================================*)
178 :     val show_block : Annotations.annotations -> block -> string
179 :     val show_edge : edge_info -> string
180 : jhr 1104 val dump : (TextIO.outstream * string * cfg) -> unit
181 : jhr 926
182 : george 906 end
183 :    

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