# Control flow graph data package used by the lowhalf IR.
# All basic optimizations are based on this representation.
#
# -- Allen Leung
api Machcode_Controlflow_Graph =
api
package i: Machcode
package p: Pseudo_Ops
package c: Cells
package w: FREQ
sharing i::C = C
type weight = w::freq
enum block_kind =
START # entry node
| STOP # exit node
| NORMAL # normal node
| HYPERBLOCK # hyperblock
and data = LABEL of label::label
| PSEUDO of p::pseudo_op
# NOTE: the instructions are listed in reverse order.
# This choice is for a few reasons:
# i) Clusters represent instructions in reverse order, so keeping this
# the same avoid having to do conversions.
# ii) This makes it easier to add instructions at the end of the block,
# which is more common than adding instructions to the front.
# iii) This also makes it easier to manipulate the branch/jump instruction
# at the end of the block.
and block =
BLOCK of
{ id: Int, # Block id
kind: block_kind, # Block kind
freq: Ref( weight ), # execution frequency
data: Ref( List( data ) ), # data preceeding block
labels: Ref( List( label::label ) ), # labels on blocks
instructions: Ref( List( i::instruction ) ), # in reverse order
annotations: Ref( Annotations::annotations ) # Annotations
}
and edge_kind = ENTRY /* entry edge */
| EXIT # exit edge
| JUMP # unconditional jump
| FALLSTHRU /* falls through to next block */
| BRANCH of Bool /* branch */
| SWITCH of Int /* computed goto */
| SIDEEXIT of Int # the ith side exit in a hyperblock
and edge_info = EDGE of { k: edge_kind, # edge kind
w: Ref( weight ), # edge freq
a: REF( Annotations::annotations ) # Annotations
}
type edge = graph::edge( edge_info )
type node = graph::node( block )
enum info =
INFO of { annotations: Ref( Annotations::annotations ),
first_block: Ref( Int ), # id of first block
reorder: REF( Bool ) # has the machcode_controlflow_graph been reordered?
}
type mcg = graph::graph( block, edge_info, info)
# ========================================================================
#
# Various kinds of annotations on basic blocks
#
# ========================================================================
my LIVEOUT: Annotations::property( c::registerset )
# escaping live out information
my CHANGED: Annotations::property( String * (Void -> Void))
# ========================================================================
#
# Methods for manipulating basic blocks
#
# ========================================================================
my newBlock: Int * Ref( w::freq ) -> block # empty
my newStart: Int * Ref( w::freq ) -> block # start node
my newStop: Int * Ref( w::freq ) -> block # stop node
my copyBlock: Int * block -> block # Copy a block
my put_private_label: block -> label::label # Define a label
my instructions: block -> Ref( List( i::instruction ) )
my freq: block -> Ref( w::freq )
my branchOf: edge_info -> Null_Or( Bool )
# emit assembly
my emit: Annotations::annotations -> block -> Void
my show_block: Annotations::annotations -> block -> String
# ========================================================================
#
# Methods for manipulating machcode_controlflow_graph
#
# ========================================================================
my mcg: info -> mcg /* create a new mcg */
my new: Void -> mcg # Create a new mcg
my subgraph: mcg -> mcg # mark as subgraph
my init: mcg -> Void # Add start/stop nodes
my changed: mcg -> Void /* mark mcg as changed */
my annotations: mcg -> Ref( Annotations::annotations )
my liveOut: block -> c::registerset
my fallsThruFrom: mcg * graph::node_id -> Null_Or( graph::node_id )
my fallsThruTo: mcg * graph::node_id -> Null_Or( graph::node_id )
my removeEdge: mcg -> edge -> Void
my setBranch: mcg * graph::node_id * Bool -> i::instruction
my edgeDir: edge_info graph::edge -> Null_Or( Bool )
# ========================================================================
#
# For viewing
#
# ========================================================================
my viewStyle: mcg -> graph_layout::style (block, edge_info, info)
my viewLayout: mcg -> graph_layout::layout
my headerText: block -> String
my footerText: block -> String
my subgraphLayout: { mcg: mcg, subgraph: mcg } -> graph_layout::layout
# ========================================================================
#
# Miscellaneous stuff
#
# ========================================================================
my cdgEdge: edge_info -> Bool # for building a CDG
end