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 933 - (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 :     | HYPERBLOCK (* hyperblock *)
26 :    
27 :     and data = LABEL of Label.label
28 :     | PSEUDO of P.pseudo_op
29 :    
30 :     (*
31 :     * NOTE: the instructions are listed in reverse order.
32 :     * This choice is for a few reasons:
33 :     *
34 :     * i) Clusters represent instructions in reverse order, so keeping this
35 :     * the same avoid having to do conversions.
36 :     *
37 :     * ii) This makes it easier to add instructions at the end of the block,
38 :     * which is more common than adding instructions to the front.
39 :     *
40 :     * iii) This also makes it easier to manipulate the branch/jump instruction
41 :     * at the end of the block.
42 :     *)
43 :    
44 :     and block =
45 :     BLOCK of
46 :     { id : int, (* block id *)
47 :     kind : block_kind, (* block kind *)
48 :     freq : weight ref, (* execution frequency *)
49 :     data : data list ref, (* data preceeding block *)
50 :     labels : Label.label list ref, (* labels on blocks *)
51 :     insns : I.instruction list ref, (* in rev order *)
52 :     annotations : Annotations.annotations ref (* annotations *)
53 :     }
54 :    
55 :    
56 :     and edge_kind = ENTRY (* entry edge *)
57 :     | EXIT (* exit edge *)
58 :     | JUMP (* unconditional jump *)
59 :     | FALLSTHRU (* falls through to next block *)
60 :     | BRANCH of bool (* branch *)
61 :     | SWITCH of int (* computed goto *)
62 :     | SIDEEXIT of int (* the ith side exit in a hyperblock *)
63 :    
64 :     and edge_info = EDGE of { k : edge_kind, (* edge kind *)
65 :     w : weight ref, (* edge freq *)
66 :     a : Annotations.annotations ref (* annotations *)
67 :     }
68 :    
69 :     type edge = edge_info Graph.edge
70 :     type node = block Graph.node
71 :    
72 :     datatype info =
73 :     INFO of { annotations : Annotations.annotations ref,
74 :     firstBlock : int ref, (* id of first block *)
75 :     reorder : bool ref (* has the CFG been reordered? *)
76 :     }
77 :    
78 :     type cfg = (block,edge_info,info) Graph.graph
79 :    
80 :     (*========================================================================
81 :     *
82 :     * Various kinds of annotations on basic blocks
83 :     *
84 :     *========================================================================*)
85 :     val LIVEOUT : I.C.cellset Annotations.property
86 :     (* escaping live out information *)
87 :     val CHANGED : (string * (unit -> unit)) Annotations.property
88 :    
89 :     (*========================================================================
90 :     *
91 :     * Methods for manipulating basic blocks
92 :     *
93 :     *========================================================================*)
94 :     val newBlock : int * W.freq ref -> block (* empty *)
95 :     val newStart : int * W.freq ref -> block (* start node *)
96 :     val newStop : int * W.freq ref -> block (* stop node *)
97 :     val copyBlock : int * block -> block (* copy a block *)
98 :     val defineLabel : block -> Label.label (* define a label *)
99 :     val insns : block -> I.instruction list ref
100 :     val freq : block -> W.freq ref
101 :     val branchOf : edge_info -> bool option
102 :    
103 :     (* emit assembly *)
104 : jhr 926 val emit : Annotations.annotations -> block -> unit
105 : george 906
106 :     (*========================================================================
107 :     *
108 :     * Methods for manipulating CFG
109 :     *
110 :     *========================================================================*)
111 :     val cfg : info -> cfg (* create a new cfg *)
112 :     val new : unit -> cfg (* create a new cfg *)
113 :     val subgraph : cfg -> cfg (* mark as subgraph *)
114 :     val init : cfg -> unit (* add start/stop nodes *)
115 :     val changed : cfg -> unit (* mark cfg as changed *)
116 :    
117 :     val annotations : cfg -> Annotations.annotations ref
118 :     val liveOut : block -> I.C.cellset
119 :     val fallsThruFrom : cfg * Graph.node_id -> Graph.node_id option
120 :     val fallsThruTo : cfg * Graph.node_id -> Graph.node_id option
121 :     val removeEdge : cfg -> edge -> unit
122 :     val setBranch : cfg * Graph.node_id * bool -> I.instruction
123 :     val edgeDir : edge_info Graph.edge -> bool option
124 :    
125 :     (*========================================================================
126 :     *
127 :     * For viewing
128 :     *
129 :     *========================================================================*)
130 :     (*****
131 :     val viewStyle : cfg -> (block,edge_info,info) GraphLayout.style
132 :     val viewLayout : cfg -> GraphLayout.layout
133 :     val headerText : block -> string
134 :     val footerText : block -> string
135 :     val subgraphLayout : { cfg : cfg, subgraph : cfg } -> GraphLayout.layout
136 :     *****)
137 :    
138 :     (*========================================================================
139 :     *
140 :     * Miscellaneous stuff
141 :     *
142 :     *========================================================================*)
143 :     val cdgEdge : edge_info -> bool (* for building a CDG *)
144 :    
145 : jhr 926 (*========================================================================
146 :     *
147 :     * Methods for printing CFGs
148 :     *
149 :     *========================================================================*)
150 :     val show_block : Annotations.annotations -> block -> string
151 :     val show_edge : edge_info -> string
152 :    
153 : george 906 end
154 :    

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