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/Doc/mlrisc-ir.html
 [smlnj] / sml / trunk / src / MLRISC / Doc / mlrisc-ir.html

# Annotation of /sml/trunk/src/MLRISC/Doc/mlrisc-ir.html

Original Path: sml/branches/SMLNJ/src/MLRISC/Doc/mlrisc-ir.html

 1 : monnier 409 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 :
10 :

11 : The MLRISC IR

12 :

Introduction

13 : 14 : In this section we will describe the MLRISC intermediate representation. 15 : 16 :

Control Flow Graph

17 : 18 : The control flow graph is the main view of the IR. 19 : A control flow graph satisfies the following signature: 20 :
21 :                 signature CONTROL_FLOW_GRAPH = sig
22 :                 structure I : INSTRUCTIONS
23 :                 structure B : BLOCK_NAMES
24 :                 structure P : PSEUDO_OPS
25 :                 structure C : CELLS
26 :                 structure W : FIXED_POINT
27 :                 sharing I.C = C
28 :
29 :                 {\it definition of type} weight
30 :                 {\it definition of type} block_kind
31 :                 {\it definition of type} data
32 :                 {\it definition of type} block
33 :                 {\it definition of type} edge_kind
34 :                 {\it definition of type} edge_info
35 :                 {\it definition of type} cfg
36 :                 {\it operations on a cfg}
37 :                 end
38 :
39 : 40 : The following structures nested within a CFG: 41 :
42 :
• I : INSTRUCTIONS is the instruction structure. 43 :
• B : BLOCK_NAMES is the block name structure 44 :
• P : PSEUDO_OPS is the structure with the definition 45 : of pseudo ops. 46 :
• C : CELLS is the cells structure describing the 47 : register conventions of the architecture. 48 :
• W : FIXED_POINT is a structure that contains 49 : a fixed point type used in execution frequency annotations. 50 :
51 : 52 : The type weight below is used in execution frequency annotations: 53 :
54 :                 type weight = W.fixed_point
55 :
56 : 57 : There are a few different kinds of basic blocks, described 58 : by the type block_kind below: 59 :
60 :                 datatype block_kind =
61 :                 START
62 :                 | STOP
63 :                 | FUNCTION_ENTRY
64 :                 | NORMAL
65 :                 | HYPERBLOCK
66 :
67 : 68 : A basic block is defined as the datatype block, defined below: 69 :
70 :                 and data = LABEL  of Label.label
71 :                 | PSEUDO of P.pseudo_op
72 :
73 :                 and block =
74 :                 BLOCK of
75 :                 {  id          : int,
76 :                 kind        : block_kind,                 {\it(* block kind *)}
77 :                 name        : B.name,                     {\it(* block name *)}
78 :                 freq        : weight ref,                 {\it(* execution frequency *) }
79 :                 data        : data list ref,              {\it(* data preceding block *) }
80 :                 labels      : Label.label list ref,       {\it(* labels on blocks *) }
81 :                 insns       : I.instruction list ref,     {\it(* in rev order *)}
82 :                 annotations : Annotations.annotations ref {\it(* annotations *)}
83 :                 }
84 :
85 : 86 : Edges in a CFG are annotated with the type edge_info, 87 : defined below: 88 :
89 :                 and edge_kind = ENTRY
90 :                 | EXIT
91 :                 | JUMP
92 :                 | FALLSTHRU
93 :                 | BRANCH of bool
94 :                 | SWITCH of int
95 :                 | SIDEEXIT of int
96 :
97 :                 and edge_info =
98 :                 EDGE of { k : edge_kind,                  {\it(* edge kind *)}
99 :                 w : weight ref,                 {\it(* edge freq *)}
100 :                a : Annotations.annotations ref {\it(* annotations *)}
101 :                }
102 :
103 : 104 : Type cfg below defines a control flow graph: 105 :
106 :                type edge = edge_info edge
107 :                type node = block node
108 :
109 :                datatype info =
110 :                INFO of { regmap      : C.regmap,
111 :                annotations : Annotations.annotations ref,
112 :                firstBlock  : int ref,
113 :                reorder     : bool ref
114 :                }
115 :                type cfg = (block,edge_info,info) graph
116 :
117 : 118 : \paragraph{Low-level Interface} 119 : The following subsection describes the low-level interface to a CFG. 120 : These functions should be used with care since they do not 121 : always maintain high-level structural invariants imposed on 122 : the representation. In general, higher level interfaces exist 123 : so knowledge of this interface is usually not necessary for customizing 124 : MLRISC. 125 : 126 : Various kinds of annotations on basic blocks are defined below: 127 :
128 :                exception LIVEOUT of C.cellset
129 :                exception CHANGED of unit -> unit
130 :                exception CHANGEDONCE of unit -> unit
131 :
132 : The annotation LIVEOUT is used record live-out information 133 : on an escaping block. 134 : The annotations CHANGED and CHANGEDONCE are used 135 : internally for maintaining views on a CFG. These should not be used 136 : directly. 137 : 138 : The following are low-level functions for building new basic blocks. 139 : The functions newXXX build empty basic blocks of a specific 140 : type. The function defineLabel returns a label to a basic block; 141 : and if one does not exist then a new label will be generated automatically. 142 : The functions emit and show_block are low-level 143 : routines for displaying a basic block. 144 :
145 :                val newBlock          : int * B.name -> block
146 :                val newStart          : int -> block
147 :                val newStop           : int -> block
148 :                val newFunctionEntry  : int -> block
149 :                val copyBlock         : int * block -> block
150 :                val defineLabel       : block -> Label.label
151 :                val emit              : C.regmap -> block -> unit
152 :                val show_block        : C.regmap -> block -> string
153 :
154 : 155 : Methods for building a CFG are listed as follows: 156 :
157 :                val cfg      : info -> cfg
158 :                val new      : C.regmap -> cfg
159 :                val subgraph : cfg -> cfg
160 :                val init     : cfg -> unit
161 :                val changed  : cfg -> unit
162 :                val removeEdge : cfg -> edge -> unit
163 :
164 : Again, these methods should be used only with care. 165 : 166 : The following functions allow the user to extract low-level information 167 : from a flowgraph. Function regmap returns the current register map. 168 : Function regmap returns a function that lookups the current register 169 : map. Function liveOut returns liveOut information from a block; 170 : it returns the empty cellset if the block is not an escaping block. 171 : Function fallsThruFrom takes a node id v and locates the 172 : block u (if any) that flows into v without going through a branch 173 : instruction. Similarly, the function fallsThruTo takes 174 : a node id u and locates the block (if any) that u flows into 175 : with going through a branch instruction. If u falls through to 176 : v in any feasible code layout u must preceed v. 177 :
178 :                val regmap    : cfg -> C.regmap
179 :                val reglookup : cfg -> C.register -> C.register
180 :                val liveOut   : block -> C.cellset
181 :                val fallsThruFrom : cfg * node_id -> node_id option
182 :                val fallsThruTo   : cfg * node_id -> node_id option
183 :
184 : 185 : To support graph viewing of a CFG, the following low-level 186 : primitives are provided: 187 :
188 :                val viewStyle      : cfg -> (block,edge_info,info) GraphLayout.style
189 :                val viewLayout     : cfg -> GraphLayout.layout
190 :                val headerText     : block -> string
191 :                val footerText     : block -> string
192 :                val subgraphLayout : { cfg : cfg, subgraph : cfg } -> GraphLayout.layout
193 :
194 : 195 : Finally, a miscellany function for control dependence graph building. 196 :
197 :                val cdgEdge : edge_info -> bool
198 :
199 : 200 :

IR

201 : The MLRISC intermediate representation is a composite 202 : view of various compiler data structures, including the control 203 : flow graph, (post-)dominator trees, control dependence graph, and 204 : loop nesting tree. Basic compiler optimizations in MLRISC 205 : operate on this data structure; advance optimizations 206 : operate on more complex representations which use this 207 : representation as the base layer. 208 : \begin{wrapfigure}{r}{4.5in} 209 : \begin{Boxit} 210 : \psfig{figure=Figures/mlrisc-ir.eps,width=4.5in} 211 : \end{Boxit} 212 : \caption{The MLRISC IR} 213 : \end{wrapfigure} 214 : 215 : This IR provides a few additional functionalities: 216 :
217 :
• {\bf Edge frequencies} -- execution frequencies 218 : are maintained on all control flow edges. 219 :
• {\bf Extensible annotations} -- semantics information can be 220 : represented as annotations on the graph. 221 :
• {\bf Multiple facets} -- 222 : Facets are high-level views that automatically keep themselves 223 : up-to-date. Computed facets are cached and out-of-date facets 224 : are recomputed by demand. 225 : The IR defines a mechanism to attach multiple facets to the IR. 226 :
227 : 228 : The signature of the IR is listed in Figure~\ref{fig:mlrisc-ir}. 229 : \begin{Figure} 230 :
231 :                signature MLRISC_IR = sig
232 :                structure I    : INSTRUCTIONS
233 :                structure CFG  : CONTROL_FLOW_GRAPH
234 :                structure Dom  : DOMINATOR_TREE
235 :                structure CDG  : CONTROL_DEPENDENCE_GRAPH
236 :                structure Loop : LOOP_STRUCTURE
237 :                structure Util : CFG_UTIL
238 :                sharing Util.CFG = CFG
239 :                sharing CFG.I = I
240 :                sharing Loop.Dom = CDG.Dom = Dom
241 :
242 :                type cfg  = CFG.cfg
243 :                type IR   = CFG.cfg
244 :                type dom  = (CFG.block,CFG.edge_info,CFG.info) Dom.dominator_tree
245 :                type pdom = (CFG.block,CFG.edge_info,CFG.info) Dom.postdominator_tree
246 :                type cdg  = (CFG.block,CFG.edge_info,CFG.info) CDG.cdg
247 :                type loop = (CFG.block,CFG.edge_info,CFG.info) Loop.loop_structure
248 :
249 :                val dom   : IR -> dom
250 :                val pdom  : IR -> pdom
251 :                val cdg   : IR -> cdg
252 :                val loop  : IR -> loop
253 :
254 :                val changed : IR -> unit
255 :                val memo : (IR -> 'facet) -> IR -> 'facet
256 :                val addLayout : string -> (IR -> GraphLayout.layout) -> unit
257 :                val view : string -> IR -> unit
258 :                val views : string list -> IR -> unit
259 :                val viewSubgraph : IR -> cfg -> unit
260 :                end
261 :
262 : \caption{\label{fig:mlrisc-ir}MLRISC IR} 263 : \end{Figure} 264 : 265 : The following facets are predefined: dominator, post-dominator tree, 266 : control dependence graph and loop nesting structure. 267 : The functions dom, pdom, cdg, loop 268 : are facet extraction methods that 269 : compute up-to-date views of these facets. 270 : 271 : The following protocol is used for facets: 272 :
273 :
• {\bf When the IR is changed}, 274 : the function changed should be called to 275 : signal that all facets attached to the IR should be updated. 276 :
• {\bf To add a new facet} of type F that is computed by demand, 277 : the programmer has to provide a facet construction 278 : function f : IR -> F. Call the function mem 279 : to register the new facet. For example, let val g = memo f. 280 : Then the function g can be used to as a new facet extraction 281 : function for facet F. 282 :
• {\bf To register a graph viewing function}, call 283 : the function addLayout and provide an appropriate 284 : graph layout function. For example, we can say 285 : addLayout "F" layoutF to register a graph layout function 286 : for a facet called F''. 287 :
288 : 289 : To view an IR, the functions view, views or 290 : viewSubgraph can be used. They have the following interpretation: 291 :
292 :
• view computes a layout for one facet of the IR and displays 293 : it. The predefined facets are called 294 : dom'', pdom'', cdg'', loop.'' The IR can be 295 : viewed as the facet cfg.'' In addition, there is a layout 296 : named doms'' which displays the dominator tree and the post-dominator 297 : tree together, with the post-dominator inverted. 298 :
• views computes a set of facets and displays it together 299 : in one single picture. 300 :
• viewSubgraph layouts a subgraph of the IR. 301 : This creates a picture with the subgraph highlighted and embedded 302 : in the whole IR. 303 :
304 : 305 :

Building a CFG

306 : 307 : There are two basic methods of building a CFG: 308 :
309 :
• convert a sequence of machine instructions 310 : into a CFG through the emitter interface, described below, and 311 :
• convert it from a cluster, which is 312 : the basic linearized representation used in the \MLRISC{} system. 313 :
314 : The first method requires you to perform instruction selection 315 : from a compiler front-end, but allows you to bypass all other 316 : \MLRISC{} phases if desired. The second method allows you 317 : to take advantage of various \MLRISC's instruction selection modules 318 : currently available. We describe these methods in this section. 319 : 320 : \paragraph{Directly from Instructions} 321 : Signature CODE_EMITTER below describes an abstract emitter interface 322 : for accepting a linear stream of instructions from a source 323 : and perform a sequence of actions based on this 324 : stream\footnote{Unlike the signature {\tt EMITTER\_NEW} or 325 : {\tt FLOWGRAPH\_GEN}, it has the advantage that it is not 326 : tied into any form of specific flowgraph representation.}. 327 : 328 :
329 :                signature CODE_EMITTER = sig
330 :                structure I : INSTRUCTIONS
331 :                structure C : CELLS
332 :                structure P : PSEUDO_OPS
333 :                structure B : BLOCK_NAMES
334 :                sharing I.C = C
335 :
336 :                type emitter =
337 :                {  defineLabel : Label.label -> unit,
338 :                entryLabel  : Label.label -> unit,
339 :                exitBlock   : C.cellset -> unit,
340 :                pseudoOp    : P.pseudo\_op -> unit,
341 :                emitInstr   : I.instruction -> unit,
342 :                blockName   : B.name -> unit,
343 :                comment     : string -> unit,
344 :                init        : int -> unit,
345 :                finish      : unit -> unit
346 :                }
347 :                end
348 :
349 : 350 : The code emitter interface has the following informal protocol. 351 : \begin{methods} 352 : init(n) & Initializes the emitter and signals that 353 : the back-end should 354 : allocate space for n bytes of machine code. 355 : The number is ignored for non-machine code back-ends. \\ 356 : defineLabel(l) & Defines a new label l at the current position.\\ 357 : entryLabel(l) & Defines a new entry label l at the current position. 358 : An entry label defines an entry point into the current flow graph. 359 : Note that multiple entry points are allowed\\ 360 : exitBlock(c) & Defines an exit at the current position. 361 : The cellset c represents the live-out information \\ 362 : pseudOp(p) & Emits an pseudo op p at the current position \\ 363 : emitInstr(i) & Emits an instruction i at the current position \\ 364 : blockName(b) & Changes the block name to b \\ 365 : comment(msg) & Emits a comment msg at the current position \\ 366 : finish & Signals that the use of the emitter is finished. 367 : The emitter is free to perform its post-processing functions. 368 : When this is finished the CFG is built. 369 : \end{methods} 370 : 371 : The functor ControlFlowGraphGenFn below can be 372 : used to create a CFG builder that uses the CODE_EMITTER interface. 373 :
374 :                signature CONTROL_FLOW_GRAPH_GEN = sig
375 :                structure CFG     : CONTROL_FLOW_GRAPH
376 :                structure Emitter : CODE_EMITTER
377 :                sharing Emitter.I = CFG.I
378 :                sharing Emitter.P = CFG.P
379 :                val emitter : CFG.cfg -> Emitter.emitter
380 :                end
381 :                functor ControlFlowGraphGenFn
382 :                (structure CFG     : CONTROL_FLOW_GRAPH
383 :                structure Emitter : CODE_EMITTER
384 :                structure P       : INSN_PROPERTIES
385 :                sharing CFG.I = Emitter.I = P.I
386 :                sharing CFG.P = Emitter.P
387 :                sharing CFG.B = Emitter.B
388 :                ) : CONTROL_FLOW_GRAPH_GEN
389 :
390 : 391 : \paragraph{Cluster to CFG} 392 : 393 : The core \MLRISC{} system implements many instruction selection 394 : front-ends. The result of an instruction selection module is a linear 395 : code layout block called a cluster. The functor Cluster2CFGFn below 396 : generates a translator that translates a cluster into a CFG: 397 :
398 :                signature CLUSTER2CFG = sig
399 :                structure CFG : CONTROL_FLOW_GRAPH
400 :                structure F   : FLOWGRAPH
401 :                sharing CFG.I = F.I
402 :                sharing CFG.P = F.P
403 :                sharing CFG.B = F.B
404 :                val cluster2cfg : F.cluster -> CFG.cfg
405 :                end
406 :                functor Cluster2CFGFn
407 :                (structure CFG : CONTROL_FLOW_GRAPH
408 :                structure F   : FLOWGRAPH
409 :                structure P   : INSN_PROPERTIES
410 :                sharing CFG.I = F.I = P.I
411 :                sharing CFG.P = F.P
412 :                sharing CFG.B = F.B
413 :                ) : CLUSTER2CFG
414 :
415 : 416 : \paragraph{CFG to Cluster} 417 : 418 : The basic \MLRISC{} system also implements many back-end functions 419 : such as register allocation, assembly output and machine code output. 420 : These modules all utilize the cluster representation. The 421 : functor CFG2ClusterFn 422 : below generates a translator 423 : that converts a CFG into a cluster. With the previous functor, 424 : the CFG and the cluster presentation can be freely inter-converted. 425 :
426 :                signature CFG2CLUSTER = sig
427 :                structure CFG : CONTROL_FLOW_GRAPH
428 :                structure F   : FLOWGRAPH
429 :                sharing CFG.I = F.I
430 :                sharing CFG.P = F.P
431 :                sharing CFG.B = F.B
432 :                val cfg2cluster : { cfg : CFG.cfg, relayout : bool } -> F.cluster
433 :                end
434 :                functor CFG2ClusterFn
435 :                (structure CFG  : CONTROL_FLOW_GRAPH
436 :                structure F    : FLOWGRAPH
437 :                sharing CFG.I = F.I
438 :                sharing CFG.P = F.P
439 :                sharing CFG.B = F.B
440 :                val patchBranch : {instr:CFG.I.instruction, backwards:bool} ->
441 :                CFG.I.instruction list
442 :                ) : CFG2CLUSTER
443 :
444 : 445 : When a CFG originates from a cluster, we try to preserve 446 : the same code layout through out all optimizations when possible. 447 : The function cfg2cluster takes an optional flag 448 : that specifies we should force the recomputation of 449 : the code layout of a control flow graph when translating a CFG 450 : back into a cluster. 451 : 452 :

Basic CFG Transformations

453 : 454 : Basic CFG transformations are implemented in the functor 455 : CFGUtilFn. These transformations include splitting edges, merging 456 : edges, removing unreachable code and tail duplication. 457 :
458 :                functor CFGUtilFn
459 :                (structure CFG : CONTROL_FLOW_GRAPH
460 :                structure P   : INSN_PROPERTIES
461 :                sharing P.I = CFG.I
462 :                ) : CFG_UTIL
463 :
464 : 465 : The signature of CFGUtilFn is defined below: 466 :
467 :                signature CFG_UTIL = sig
468 :                structure CFG : CONTROL_FLOW_GRAPH
469 :                val updateJumpLabel : CFG.cfg -> node_id -> unit
470 :                val mergeEdge       : CFG.cfg -> CFG.edge -> bool
471 :                val eliminateJump   : CFG.cfg -> node_id -> bool
472 :                val insertJump      : CFG.cfg -> node_id -> bool
473 :                val splitEdge  : CFG.cfg -> { edge : CFG.edge, jump : bool }
474 :                -> { edge : CFG.edge, node : CFG.node }
475 :                val isMerge        : CFG.cfg -> node_id -> bool
476 :                val isSplit        : CFG.cfg -> node_id -> bool
477 :                val hasSideExits   : CFG.cfg -> node_id -> bool
478 :                val isCriticalEdge : CFG.cfg -> CFG.edge -> bool
479 :                val splitAllCriticalEdges : CFG.cfg -> unit
480 :                val ceed : CFG.cfg -> node_id * node_id -> bool
481 :                val tailDuplicate : CFG.cfg -> { subgraph : CFG.cfg, root : node_id }
482 :                -> { nodes : CFG.node list,
483 :                edges : CFG.edge list }
484 :                val removeUnreachableCode : CFG.cfg -> unit
485 :                val mergeAllEdges : CFG.cfg -> unit
486 :                end
487 :
488 : 489 : These functions perform the following functions: 490 :
491 :
• updateJumpLabel G u. This function 492 : updates the label of the branch instruction in a block u 493 : to be consistent with the control flow edges with source u. 494 : This is an nop if the CFG is already consistent. 495 :
• mergeEdge G e. This function merges edge e \equiv u \edge{} v 496 : in the graph G if possible. This is successful only if 497 : there are no other edges flowing into v and no other edges 498 : flowing out from u. It returns true if the merge 499 : operation is successful. If successful, the nodes u and v 500 : will be coalesced into the block u. The jump instruction (if any) 501 : in the node u will also be elided. 502 :
• eliminateJump G u. This function eliminate the 503 : jump instruction at the end of block u if it is feasible. 504 :
• insertJump G u. This function inserts a jump 505 : instruction in block u if it is feasible. 506 :
• splitEdge G e. This function 507 : split the control flow edge e, and return a new edge e' and the 508 : new block u as return values. It addition, it takes as 509 : argument a flag jump. If this flag is true, 510 : then a jump instruction is always placed in the 511 : split; otherwise, we try to eliminate the jump when feasible. 512 :
• isMerge G u. This function tests whether block u 513 : is a merge node. A merge node is a node that 514 : has two or more incoming flow edges. 515 :
• isSplit G u. This function tests whether block u 516 : is a split node. A split node is a node that 517 : has two or more outgoing flow edges. 518 :
• hasSideExits G u. This function tests whether 519 : a block has side exits G. This assumes that u 520 : is a hyperblock. 521 :
• isCriticalEdge G e. This function tests whether 522 : the edge e is a critical edge. The 523 : edge e \equiv u \edge{} v is critical iff 524 : there are u is merge node and v is a split node. 525 :
• splitAllCriticalEdges G. This function goes 526 : through the CFG G and splits 527 : all critical edges in the CFG. 528 : This can introduce extra jumps and basic blocks in the program. 529 :
• mustPreceed G (u,v). This function 530 : checks whether two blocks u and v are necessarily adjacent. 531 : Blocks u and v must be adjacent iff u must preceed v 532 : in any feasible code layout. 533 :
• tailDuplicate. 534 :
535 :                val tailDuplicate : CFG.cfg -> { subgraph : CFG.cfg, root : node_id }
536 :                -> { nodes : CFG.node list,
537 :                edges : CFG.edge list }
538 :
539 : \begin{Figure} 540 : %\begin{tabular}{|c|} \hline 541 : \begin{boxit} 542 : \cpsfig{figure=Figures/tail-duplication.eps,width=3in} 543 : \end{boxit} 544 : %\hline 545 : %\end{tabular} 546 : \caption{\label{fig:tail-duplication} Tail-duplication} 547 : \end{Figure} 548 : 549 : This function tail-duplicates the region subgraph 550 : until it only has a single entry root. 551 : Return the set of new nodes and new edges. 552 : The region is represented as a subgraph view of the CFG. 553 : Figure~\ref{fig:tail-duplication} illustrates 554 : this transformation. 555 : 556 :
• removeUnreachableCode G. This function 557 : removes all unreachable code from the graph. 558 :
• mergeAllEdges G. This function tries to merge all 559 : the edges in the flowgraph G. Merging is performed in the 560 : non-increasing order of edge frequencies. 561 :
562 : 563 :

Dataflow Analysis

564 : MLRISC provides a simple customizable module for performing 565 : iterative dataflow analysis. A dataflow analyzer 566 : has the following signature: 567 : 568 :
569 :                signature DATAFLOW_ANALYZER = sig
570 :                structure CFG : CONTROL_FLOW_GRAPH
571 :                type dataflow_info
572 :                val analyze : CFG.cfg * dataflow_info -> dataflow_info
573 :                end
574 :
575 : 576 : A dataflow problem is described by the signature DATAFLOW_PROBLEM, 577 : described below: 578 :
579 :                signature DATAFLOW_PROBLEM = sig
580 :                structure CFG : CONTROL_FLOW_GRAPH
581 :                type domain
582 :                type dataflow_info
583 :                val forward   : bool
584 :                val bot       : domain
585 :                val ==        : domain * domain -> bool
586 :                val join      : domain list -> domain
587 :                val prologue  : CFG.cfg * dataflow_info ->
588 :                CFG.block node ->
589 :                { input    : domain,
590 :                output   : domain,
591 :                transfer : domain -> domain
592 :                }
593 :                val epilogue  : CFG.cfg * dataflow_info ->
594 :                { node   : CFG.block node,
595 :                input  : domain,
596 :                output : domain
597 :                } -> unit
598 :                end
599 :
600 : This description contains the following items 601 :
602 :
• type domain is the abstract lattice domain D. 603 :
• type dataflow_info is where the dataflow information 604 : is stored. 605 :
• forward is true iff the dataflow problem is in the 606 : forward direction 607 :
• bot is the bottom element of D. 608 :
• == is the equality function on D. 609 :
• join is the least-upper-bound function on D. 610 :
• prologue is a user-supplied function that performs 611 : pre-processing and setup. For each CFG node X, this function 612 : computes 613 :
614 :
• input -- which is the initial input value of X 615 :
• output -- which is the initial output value of X 616 :
• transfer -- which is the transfer function on X. 617 :
618 :
• epilogue is a function that performs post-processing. 619 : It visits each node X in the flowgraph and return the resulting 620 : input and output value for X. 621 :
622 : 623 : To generate a new dataflow analyzer from a dataflow problem, 624 : the functor DataflowFn can be used: 625 :
626 :                functor DataflowFn(P : DATAFLOW_PROBLEM) : DATAFLOW_ANALYZER =
627 :
628 : 629 :

Static Branch Prediction

630 : 631 :

Branch Optimizations

632 : 633 : 634 : 635 :
636 : 637 :
638 : Allen Leung
639 :
640 : 641 : 642 :