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/IR/mlrisc-cfg.sig
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/IR/mlrisc-cfg.sig

Parent Directory Parent Directory | Revision Log Revision Log


Revision 411 - (view) (download) (as text)
Original Path: sml/branches/SMLNJ/src/MLRISC/IR/mlrisc-cfg.sig

1 : monnier 245 (*
2 : monnier 411 * Control flow graph data structure used by the MLRISC IR.
3 :     * All basic optimizations are based on this representation.
4 :     *
5 :     * -- Allen
6 : monnier 245 *)
7 :    
8 :     signature CONTROL_FLOW_GRAPH =
9 :     sig
10 :    
11 :     structure I : INSTRUCTIONS
12 :     structure B : BLOCK_NAMES
13 :     structure P : PSEUDO_OPS
14 :     structure C : CELLS
15 : monnier 411 structure W : FREQ
16 : monnier 245 sharing I.C = C
17 :    
18 : monnier 411 type weight = W.freq
19 : monnier 245
20 :     datatype block_kind =
21 :     START (* entry node *)
22 :     | STOP (* exit node *)
23 :     | FUNCTION_ENTRY (* for SSA transformations *)
24 :     | NORMAL (* normal node *)
25 :     | HYPERBLOCK (* hyperblock *)
26 :    
27 :     and data = LABEL of Label.label
28 :     | PSEUDO of P.pseudo_op
29 :    
30 : monnier 411 (*
31 :     * NOTE: the instructions are listed in reverse order.
32 :     * This choice is for a few reasons:
33 :     * i) Clusters represent instructions in reverse order, so keeping this
34 :     * the same avoid having to do conversions.
35 :     * ii) This makes it easier to add instructions at the end of the block,
36 :     * which is more common than adding instructions to the front.
37 :     * iii) This also makes it easier to manipulate the branch/jump instruction
38 :     * at the end of the block.
39 :     *)
40 :    
41 : monnier 245 and block =
42 :     BLOCK of
43 :     { id : int, (* block id *)
44 :     kind : block_kind, (* block kind *)
45 :     name : B.name, (* block name *)
46 :     freq : weight ref, (* execution frequency *)
47 :     data : data list ref, (* data preceeding block *)
48 :     labels : Label.label list ref, (* labels on blocks *)
49 :     insns : I.instruction list ref, (* in rev order *)
50 :     annotations : Annotations.annotations ref (* annotations *)
51 :     }
52 :    
53 :    
54 :     and edge_kind = ENTRY (* entry edge *)
55 :     | EXIT (* exit edge *)
56 :     | JUMP (* unconditional jump *)
57 :     | FALLSTHRU (* falls through to next block *)
58 :     | BRANCH of bool (* branch *)
59 :     | SWITCH of int (* computed goto *)
60 :     | SIDEEXIT of int (* the ith side exit in a hyperblock *)
61 :    
62 :     and edge_info = EDGE of { k : edge_kind, (* edge kind *)
63 :     w : weight ref, (* edge freq *)
64 :     a : Annotations.annotations ref (* annotations *)
65 :     }
66 :    
67 :     type edge = edge_info Graph.edge
68 :     type node = block Graph.node
69 :    
70 :     datatype info =
71 : monnier 411 INFO of { regmap : C.regmap ref,
72 : monnier 245 annotations : Annotations.annotations ref,
73 :     firstBlock : int ref,
74 :     reorder : bool ref
75 :     }
76 :    
77 :     type cfg = (block,edge_info,info) Graph.graph
78 :    
79 :     (*========================================================================
80 :     *
81 :     * Various kinds of annotations on basic blocks
82 :     *
83 :     *========================================================================*)
84 :     exception LIVEOUT of C.cellset (* escaping live out information *)
85 :     exception CHANGED of unit -> unit
86 :     exception CHANGEDONCE of unit -> unit
87 :    
88 :     (*========================================================================
89 :     *
90 :     * Methods for manipulating basic blocks
91 :     *
92 :     *========================================================================*)
93 : monnier 411 val newBlock : int * B.name * W.freq ref -> block (* empty *)
94 :     val newStart : int * W.freq ref -> block (* start node *)
95 :     val newStop : int * W.freq ref -> block (* stop node *)
96 :     val newFunctionEntry : int * W.freq ref -> block (* fun entry node *)
97 : monnier 245 val copyBlock : int * block -> block (* copy a block *)
98 :     val defineLabel : block -> Label.label (* define a label *)
99 :     val emit : C.regmap -> block -> unit (* emit assembly *)
100 :     val show_block : C.regmap -> block -> string
101 :    
102 :     (*========================================================================
103 :     *
104 :     * Methods for manipulating CFG
105 :     *
106 :     *========================================================================*)
107 :     val cfg : info -> cfg (* create a new cfg *)
108 :     val new : C.regmap -> cfg (* create a new cfg *)
109 :     val subgraph : cfg -> cfg (* mark as subgraph *)
110 :     val init : cfg -> unit (* add start/stop nodes *)
111 :     val changed : cfg -> unit (* mark cfg as changed *)
112 :    
113 : monnier 411 val regmap : cfg -> C.regmap
114 :     val setRegmap : cfg * C.regmap -> unit
115 :     val setAnnotations : cfg * Annotations.annotations -> unit
116 : monnier 245 val reglookup : cfg -> C.register -> C.register
117 :     val liveOut : block -> C.cellset
118 :     val fallsThruFrom : cfg * Graph.node_id -> Graph.node_id option
119 :     val fallsThruTo : cfg * Graph.node_id -> Graph.node_id option
120 :     val removeEdge : cfg -> edge -> unit
121 :    
122 :     (*========================================================================
123 :     *
124 :     * For viewing
125 :     *
126 :     *========================================================================*)
127 :     val viewStyle : cfg -> (block,edge_info,info) GraphLayout.style
128 :     val viewLayout : cfg -> GraphLayout.layout
129 :     val headerText : block -> string
130 :     val footerText : block -> string
131 :     val subgraphLayout : { cfg : cfg, subgraph : cfg } -> GraphLayout.layout
132 :    
133 :     (*========================================================================
134 :     *
135 :     * Miscellaneous stuff
136 :     *
137 :     *========================================================================*)
138 :     val cdgEdge : edge_info -> bool (* for building a CDG *)
139 :    
140 :     end
141 :    

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