|
|
Basic Compiler Graphs
Introduction
In this section we describe the set of core compiler specific graphs and
algorithms implemented in MLRISC.
Mostly of these algorithms are parameterized with respect
to the actual intermediate representation, and as such they
do not provide many facilities that are provided by higher abstraction
layers, such as in MLRISC IR,
or in SSA.
Dominator/Post-dominator Trees
Dominance
is a fundamental concept in compiler optimizations.
Node
iff all paths from the start node
to intersects A. A dual notion is the concept of
:
post-dominates iff all paths from to the stop node
intersects . A (post-)dominator tree can be used
to summarize the dominance/post-dominance relationship.
functor DominatorTree
(GraphImpl : GRAPH_IMPLEMENTATION) : DOMINATOR_TREE
The functor implements dominator analysis and
creates a dominator/post-dominator tree from a graph . A dominator tree is implemented as a graph
with the following definition:
signature DOMINATOR_TREE = sig
exception Dominator
datatype 'n dom_node =
DOM of { node : 'n, level : int, preorder : int, postorder : int }
type ('n,'e,'g) dom_info
type ('n,'e,'g) dominator_tree = ('n dom_node,unit,('n,'e,'g) dom_info) graph
type ('n,'e,'g) postdominator_tree = ('n dom_node,unit,('n,'e,'g) dom_info) graph
We annotated each node in
a dominator tree with three extra fields of information, which
is useful for other algorithms:
- level is the nesting level of the tree. The root
node has level 0, children of the root has level 1 and so on.
- preorder is the preorder numbering of a node
- preorder is the postorder numbering of a node.
To create a dominator tree and a postdominator tree
from a graph, the following function should be called.
val dominator_trees : ('n,'e,'g) graph ->
('n,'e,'g) dominator_tree * ('n,'e,'g) postdominator_tree
We use the algorithm of Tarjan and Lengauer, which
runs in time where is the functional
inverse of the Ackermann function.
To perform many common queries on a dominator tree, we first
call the function methods to obtain a method object.
val methods : ('n,'e,'g) dominator_tree -> dominator_methods
The methods are packed into the following type:
type dominator_methods =
{ dominates : node_id * node_id -> bool,
immediately_dominates : node_id * node_id -> bool,
strictly_dominates : node_id * node_id -> bool,
postdominates : node_id * node_id -> bool,
immediately_postdominates : node_id * node_id -> bool,
strictly_postdominates : node_id * node_id -> bool,
control_equivalent : node_id * node_id -> bool,
idom : node_id -> node_id, $(* ~1 if none *)$
idoms : node_id -> node_id list,
doms : node_id -> node_id list,
ipdom : node_id -> node_id, $(* ~1 if none *)$
ipdoms : node_id -> node_id list,
pdoms : node_id -> node_id list,
dom_lca : node_id * node_id -> node_id,
pdom_lca : node_id * node_id -> node_id,
dom_level : node_id -> int,
pdom_level : node_id -> int,
control_equivalent_partitions : unit -> node_id list list
}
The query methods are as follows:
-
dominates()
- returns true iff dominates
-
immediately_dominates()
- returns true iff immediately dominates
-
strictly_dominates()
- returns true iff strictly dominates
-
postdominates()
- returns true iff post-dominates
-
immediately_postdominates()
- returns true iff immediately post-dominates
-
strictly_postdominates()
- returns true iff strictly post-dominates
-
control_equivalent()
-
returns true iff dominates and vice versa
-
idom()
- returns the immediate dominator of , or if none exists
-
idoms()
- returns all nodes that immediately dominates
-
doms()
- returns all nodes that dominates (including itself)
-
ipdom()
- returns the immediate post-dominator of , or if none exists
-
ipdoms()
- returns all nodes that immediately post-dominates
-
pdoms()
- returns all nodes that post-dominates (including itself)
-
dom_lca()
- returns the least common ancestor of and in
the dominator tree
-
pdom_lca()
- returns the least common ancestor of and
in the post-dominator tree
-
dom_level()
- returns the nesting level of in the dominator tree
-
pdom_level()
- returns the nesting level of in the post-dominator
tree
-
control_equivalent_partitions
- partitions the graph into
a set of control equivalent nodes.
The methods dom_lca, pdom_lca and
control_equivalent_partitions executes in time, where
is the size of the dominator tree. The other methods run in time.
Control Dependence Graph
Given two nodes and in a control flow graph ,
we say that is control dependent on iff
- post-dominates a successor of
- does not strictly post-dominates
Intuitively, is control dependent on means that
some path in the program that goes through can by-passed ,
and furthermore, is the point in which this divergence can occur.
Control dependence is used to various kinds of analysis and optimizations in
a compiler, such as code motion and global scheduling[bernstein-rodeh].
To build a control dependence graph, the functor
ControlDependenceGraph can be used:
signature CONTROL_DEPENDENCE_GRAPH = sig
type ('n,'e,'g) cdg = ('n,'e,'g) graph
val control_dependence_graph :
('e -> bool) ->
('n,'e,'g) dominator_tree *
('n,'e,'g) postdominator_tree ->
('n,'e,'g) cdg
end
functor ControlDependenceGraph
(structure Dom : DOMINATOR_TREE
structure GraphImpl : GRAPH_IMPLEMENTATION
) : CONTROL_DEPENDENCE_GRAPH
The control depedence graph is a subcomponent of the
program dependence graph commonly used in
modern compiler optimizations.
Dominance Frontiers
Many algorithms involving the notion of control dependence or dominance
can be rephrased in terms of dominance frontiers.
A node is in the dominance frontiers of iff
dominates a predecessor of but does not strictly-dominate .
We denote this as .
The dual notion of post-dominance frontiers can be defined
analogously using the post-dominator tree\footnote{Control dependence
can be defined in terms of post-dominance frontiers.}.
functor DominanceFrontiers(Dom : DOMINATOR_TREE) : DOMINANCE_FRONTIERS
The functor DominanceFrontiers can be used to
compute all the dominance frontiers of all the nodes in a graph.
It has the following signature.
signature DOMINANCE_FRONTIERS = sig
structure Dom : DOMINATOR_TREE
type dominance_frontiers = node_id list array
val DFs : ('n,'e,'g) Dom.dominator_tree -> dominance_frontiers
end
Iterated Dominance Frontiers
Iterated dominance frontiers (denoted as ) are defined
as the least fixed point of iterating the operation . Formally,
define the dominance frontiers on a set as follows:
-
Define iteration of , denoted as , as follows:
-
The iterated dominance frontiers on a set are defined as
the limit:
-
Iterated dominance frontiers of a set can be computed in
time using the
algorithm by Sreedhar and Gao[linear-time-IDF]\footnote{
In practice it is often sub-linear in .}.
functor DJGraph(Dom : DOMINATOR_TREE) : DJ_GRAPH
The functor DJGraph implements this algorithm.
It satisfies the signature below:
signature DJ_GRAPH = sig
structure Dom : DOMINATOR_TREE
type ('n,'e,'g) dj_graph = ('n,'e,'g) Dom.dominator_tree
val dj_graph : ('n,'e,'g) dj_graph ->
{ DF : node_id -> node_id list,
IDF : node_id -> node_id list,
IDFs : node_id list -> node_id list
}
end
The function dj_graph takes a dominator tree and returns
three query methods for computing dominance and iterated dominance frontiers.
Method DF computes for a single node .
Method IDF computes the , and method
IDFs computes when given a set of node ids.
The dominator tree must not be updated while these operations
are being performed.
Sreedhar's original algorithm is phrased in terms of the
DJ-graph, which is a fusion of the dominator tree
with its underlying flowgraph. Our variant operates on the
dominator tree and the flowgraph at the same time, without
building an intermediate data structure.
Iterated dominance frontiers are used
in many algorithms that deal with the notion of dominance.
For example, our SSA construction algorithm uses iterated
dominance frontiers to identify confluent points in the program
where -functions are to be placed.
Loop Nesting Tree
A natural loop in a graph is a maximal
strongly connected component
such that all nodes in are dominated by a single node , called
the loop header. Loops tend to form good optimization candidates
and consequently loop detection is an essential task in a compiler.
The functor
functor structure .sml" target=code>LoopStructure
(structure GraphImpl : GRAPH_IMPLEMENTATION
structure Dom : DOMINATOR_TREE
) : LOOP_STRUCTURE
recognizes all natural loops in a graph and built a
loop nesting tree
that describes the loop nesting relationship between graphs.
signature structure .sig" target=code>LOOP_STRUCTURE = sig
structure Dom : DOMINATOR_TREE
datatype ('n,'e,'g) loop =
LOOP of { nesting : int,
header : node_id,
loop_nodes : node_id list,
backedges : 'e edge list,
exits : 'e edge list
}
type ('n,'e,'g) loop_info
type ('n,'e,'g) loop_structure = (('n,'e,'g) loop,unit, ('n,'e,'g) loop_info) graph
val loop_structure : ('n,'e,'g) Dom.dominator_tree -> ('n,'e,'g) loop_structure
val nesting_level : ('n,'e,'g) loop_structure -> node_id array
val header : ('n,'e,'g) loop_structure -> node_id array
end
Our algorithm computes the loop nesting tree in time
.
Each node in this tree represents a loop in the flowgraph, except the
root of the tree, which represents the entire graph.
Given a flowgraph , the root
of the loop nesting tree is defined to be the sole vertex in
#entry . Other nodes in the tree
are indexed by the loop header node ids.
Loop detection classifies each loop and for
each loop , the following information is obtained:
- An integer nesting. The root of the tree has nesting
depth 0. The top level loops have nesting depth 1, etc.
- The node id of the loop header .
- A set of loop_nodes. Loop nodes are
nodes that are in the strongly connected
component , but excluding the header
and all nodes that are part of any nested loops.
Thus all nodes are uniquely partitioned in header nodes and
loop nodes, and loop nodes are further partitioned into different
sets according to which headers they are immediately nested under.
- A set of backedges. A back-edge is an
edge that targets the header and originates from a loop node
in .
- A set of loop exits. An exit-edge is an edge
that originates from a loop node within
targets a node outside of . Note that this set does not include
any exit-edges contained in loops nested in but
target a node out of .
Static Single Assignment
An SSA construction algorithm based on[SSA,Briggs-SSA,linear-time-IDF]
is implemented in the following functor:
functor StaticSingleAssignmentForm
(Dom : DOMINATOR_TREE) : STATIC_SINGLE_ASSIGNMENT_FORM
SSA-based optimizations in MLRISC
are actually implemented on top of a
high-level SSA layer described in Section SSA Optimizations.
So it is not necessary to use this module directly. Nevertheless,
there can be situations in which this module can be specialized in other
ways; for example, in the construction of sparse evaluation graphs.
signature STATIC_SINGLE_ASSIGNMENT_FORM = sig
structure Dom : DOMINATOR_TREE
type var = int
type phi = var * var * var list $(* orig def/def/uses *)$
type renamer = {defs : var list, uses: var list} ->
{defs : var list, uses: var list}
type copy = {dst : var list, src: var list} -> unit
val compute_ssa :
('n,'e,'g) Dom.dominator_tree ->
{ max_var : var,
defs : 'n node -> var list,
is_live : var * int -> bool,
rename_var : var -> var,
rename_stmt : {rename:renamer,copy:copy} -> 'n node -> unit,
insert_phi : {block : 'n node,
in_edges : 'e edge list,
phis : phi list
} -> unit
} -> unit
end
This module defines the function compute_ssa, which
constructs an SSA graph. It requires
the following information from the client:
- A dominator tree of the flowgraph.
- max_var -- the maximum variable id (integer) that exists
in the flowgraph. All variables are assumed to be indexed by non-negative
integers.
- defs() -- a function that returns ,
i.e.~the set of variable names defined in block .
If a minimal SSA form is desired, this set should include all the definitions
in . If a pruned SSA form is required, this set should
include only the set of names that are live-out in .
- is_live() -- a function that determines if
variable is live-in into block . If not, a -function will
not be placed in . For example, to compute
the minimal-SSA form, this function should always return true.
- rename_var() -- a function that returns a new
unique name for variable .
- rename_stmt -- a function of type
\sml{{rename:renamer,copy:copy} -> 'n node -> unit} where
type renamer = {defs : var list, uses: var list} ->
{defs : var list, uses: var list}
type copy = {dst : var list, src: var list} -> unit
Function rename_stmt is called for each block
in the flowgraph in the order of the dominator tree, and
is responsible for renaming all the variables in by
calling the functions renamer or copy.
Function renamer renames all definitions and uses of
a statement, while function copy renames
of a set of parallel assignments
- insert_phi(,,) --
a function that inserts a set of
-definitions in block , where
is the list of control flow edges that merge into block .
IDEFS/IUSE sets
Reif and Tarjan define the following useful notions for
computing approximate birth-points for expressions, which in turn
can be used to drive other optimizations.
Given a node , let denote the immediate dominator of .
Let () denote all the definitions (uses) in .
Given a path , define () as
-
Let denotes all the paths from to
that does not cross internally. Then define
() as:
-
The sets and are defined analogously
using the postdominator tree.
signature IDEFS = sig
type var = int
val compute_idefs :
{def_use : 'n Graph.node -> var list * var list,
cfg : ('n,'e,'g) Graph.graph
} ->
{ idefuse : unit -> (RegSet.regset * RegSet.regset) Array.array,
ipostdefuse : unit -> (RegSet.regset * RegSet.regset) Array.array
}
end
structure IDefs : IDEFS
Structure IDefs implements the function
comput_idefs for computing
the , , and sets of a control flow
graph. It takes as arguments a flowgraph and a function def_use, which
takes a graph node and returns the def/use sets of the node.
It returns two functions idefuse and ipostdefuse which
compute the and sets. These sets
are returned as arrays indexed by node ids.
|
|
Generated by
mltex2html
|
Last modified: Mon Jun 8 14:18:05 UTC 2009 by buildd@vernadsky
|
|