Java Reference
In-Depth Information
Node
X Z
|
X
=
idom
(
Z
)
DF
local
DF
(
X
)
DF
up
(
X
)
12
{
7
,
11
} {
7
,
11
} {
7
,
11
}
13
{
12
} {
12
}
{}
11
12
,
13
{} {
7
,
11
} {
7
}
2
11
{
3
,
4
} {
3
,
4
,
7
}
{}
6
{
5
,
7
} {
5
,
7
}
{}
4
{
5
,
8
} {
5
,
8
}
{}
5
{
6
,
3
} {
6
,
3
}
{}
10
{
6
}
{
6
}
{
6
}
9
10
{
8
} {
6
,
8
} {
6
,
8
}
3
9
{
4
} {
4
,
6
,
8
}
{}
7
{}
{}
{}
8
{
6
}
{
6
}
{}
Figure 14.30: Example of dominance frontier computation.
traversed bottom-up, visiting each node
X
only after visiting each of its chil-
dren. The dominance frontiers for the flow graph in Figure 14.10 are shown in
Figure 14.30.
14.2.9
Intervals
Optimization is primarily concerned with reducing the execution time of pro-
grams. Because most execution time is spent in the loops of programs, trans-
formations often attempt to reduce the cost of operations that are deeply nested
in the loops of a program. For example,
code motion
attempts to move code
out of loops.
Reduction in strength
replaces a costly operation by a cheaper
equivalent. Such optimization requires computing a program's
intervals
—a
data structure that represents the looping constructs of a program. Intervals
are also useful for evaluating data flow frameworks [Bur90].
We first consider the following definition of an interval based on the control
flow graph:
Definition 14.19
A
Cocke-Allen interval
I
(
x
)
in
G
f
with
header
node x is a
subset of
N
f
that contains x and has the following properties:
1. The interval can be entered only through its
header
node x. Thus, all edges
in
G
f
that enter I
(
x
)
from a node not in I
(
x
)
must do so through x. More
formally, if
(
y
,
z
)
∈E
f
,y
I
(
x
)
,andz
∈
I
(
x
)
,thenz
=
x.
2. All nodes in I
(
x
)
can be reached from x along a path contained in I
(
x
)
.
3. All cycles wholly contained in I
(
x
)
must contain x.
