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

Parent Directory | Revision Log

---

Revision 1118 - (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	1118	val dumpBlock : (TextIO.outstream * cfg) -> node -> unit
181 :	jhr	1104	val dump : (TextIO.outstream * string * cfg) -> unit
182 :	jhr	926
183 :	george	906	end
184 :

---

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